Что на самом деле нужно сохранять при сериализации сложной структуры?
TL;DR: Важно отделить логические данные от производного состояния: часть структур можно восстановить после загрузки, а часть - вообще заменить другим физическим представлением под нужный сценарий.
Вспомним хотя бы слайс: само значение - это дескриптор с указателем на нижележащий массив, len и cap. После рестарта старого расположения памяти всё равно не будет: появится новый массив и новый дескриптор. То же самое относится к lookup-таблицам, оффсетам, кешу и другим производным структурам, которые
существуют ради удобной работы с данными в рантайме.
Поэтому в вопросе сохранения структур для дальнейшего переиспользования можно отделить основные данные от производного состояния: сохранить то, что нельзя потерять, а всё, что однозначно выводится из данных, построить заново после загрузки.
В инвертированном индексе каждый раз заниматься переиндексацией дорого, поэтому были добавлены два варианта экспорта структур в файлы:
snapshot, если после загрузки есть необходимость менять индекс (например, дополнять его новыми термами), и
sealed segment, если после загрузки индекс используется только для поиска.
Возьмём упрощённый пример:
"go" -> doc 10: [2, 7]
doc 14: [3]
go — term, 10 и 14 — документы в posting list, [2,7] и [3] — позиции слова.
Например flat.Index состоит из следующих частей:
type Index struct {
arena []byte // где лежат термы
entries []entry // где хранятся оффсеты термов в арене и список документов
byHash map[uint64]int32 // поиск entry по его term hash
positions [][][]uint32 // позиции слова для каждого документа внутри каждого entry
}
Snapshot: сохранить данные для восстановления mutable-структуры
В snapshot мы сериализуем в отдельный файл термы, документы и позиции слов - то есть логическое состояние индекса. При загрузке по этим данным заново собирается flat.Index, после чего в него снова можно добавлять данные.
Чтобы уменьшить размер snapshot, DocOrd сохраняются как разница с предыдущим ordinal, а получившиеся числа кодируются через uvarint. Про uvarint и delta encoding я рассказывала
тут.
При загрузке декодер восстанавливает абсолютные DocOrd, последовательно прибавляя сохранённые дельты, а затем собирает структуру индекса заново. byHash мапа после этого тоже строится заново по загруженным термам.
(де)сериализация на примере flat индекса
Segment: сохранить read-only индекс без восстановления структуры вообще
В segment режиме сериализации экспортируются те же основные данные: термы, списки документов, позиции термов - в отдельный read-only бинарный формат. Он разделен на области байт по назначению:
[header][postings area][positions area][term index][footer]
Postings и positions участки лежат подряд, а term index хранит оффсеты и длины диапазонов для каждого терма.
Поэтому при загрузке такого сегмента обратного преобразования индекса в структуру flat.Index уже нет. Для запроса "go" мы находим его оффсеты в term index, берём через mmap (или через обычный `ReadAt`) только нужный диапазон данных и декодируем postings: подробнее про
построение segment.
То есть в snapshot данные сначала декодируются, а производные структуры типо byHash собираются заново - получаем готовую к использованию структуру индекса.
В sealed segment эти структуры вообще не нужны: данные сразу раскладываются в компактный формат с оффсетами, который оптимизирован под чтение.
Получается, что одни и те же логические данные можно сохранить по-разному в зависимости от того, что нужно после загрузки.
Этот вывод не относится только к поисковым системам: при сохранении сложной структуры не нужна ее in-memory копия. Производное состояние можно не сохранять, если его дешевле восстановить. А если после загрузки данные будут использоваться иначе, из одного и того же состояния можно вообще построить другое физическое представление - под запись или только под чтение.
PS: finally совесть чиста и можно готовить вторую часть про HSNW
#fts #perf #projects