10 подписчиков
Играл частично из-за прокрастинации, не так уж и просто эти фантомные записи оказалось реализовать. Изначально я думал просто в записях добавить поле phantoms: {phantomId => value}, но потом подумал, что ерунда получается, записи перестают быть фиксированной величины (хотя они и сейчас не такие из-за переменных длин ключей и значений, но это чуть другое), решил что буду хранить фантомы в физически других записях с добавлением поля phantomId. Тогда их в теории будет проще хранить в будущем, плюс по этому полю легко смотреть, можно ли просто проигнорировать эту запись когда читаем без учёта фантомов (в случае с полем с отображениями всё равно флаг пришлось бы добавлять «была ли такая реальная запись»).
Ну и как-то совсем сложно стало по массиву бегать для совершения разных операций.
Храню я данные сейчас так. Есть у меня массив, в котором лежат объекты {key: string, generationId: string, phantomId: string | undefined, value: string | null}. И он отсортирован сначала по ключу, затем по идентификатору поколения, затем по phantomId.
Есть четыре разных операции которые я хочу совершать:
◾️ Получение значения по ключу (опционально с учётом поколения)
◾️ Получение диапазона значений по ключу (опционально с учётом поколения)
◾️ Вставка изменения по ключу и поколению
◾️ Взятие разницы между поколениями
Для получения я бинарным поиском нахожу нужную запись, начинаю бежать по записям вперёд, собираю максимальное количество элементов в одной пачке, запоминаю ключ/поколение/фантом последней записи, эти данные запоминаю в курсоре, который может продолжать получать следующие данные. Как его заиспользуют, эта же запись так же бинарным поиском найдётся, ну и продолжится.
Для вставки тоже сначала бинарным поиском нахожу нужное место, затем прицеливаюсь и вставляю новую запись куда нужно (или мутирую существующую, если это ещё незакоммиченное поколение/это фантомная запись).
... ох, кажется я затупил. Хотел рассказать, зачем я сделал класс который позвоняет взять этот массив и которому потом можно говорить «перейди к следующему ключу», «давай в текущем ключе перейдём к следующему поколению», «найди мне место для вставки с вот таким вот поколением». И что этот класс стал сильно большой, а логики в функциях замного, что решил выкинуть его и сделать набор утилиток с довольно простыми операциями, чтобы потом переиспользовать их друг в друге, ну и разделить путешествия назад/вперёд, чтобы было поменьше if'ов.
... а когда написал два абзаца после списка операций понял, что я дурачок и на самом деле вся моя проблема в том, что я поленился бинарный поиск делать не только по ключам, но и по поколению/фантому тоже. Тогда я бы сразу находил нужное место и всё, половина утилит не нужна была бы.
Ну да ладно, превозмогая трудности, семь бед — один ответ, вставь костыль, изобрети велосипед, вот это всё. Утилитки, возможно, всё равно пригодятся, когда более хитрые обходы буду делать/разного рода фоновые подчистки хранилища буду делать (поколения/фантомы эти прибрать устаревшие, пока я их чищу перед тем как дамп сделать и беру при этом эксклюзивную блокировку всего).
#diffbelt
2 минуты
23 ноября 2022