Сложно сказать, в какой момент FTS индекс превратился в большой набор гошных структур, но это надо было как то решать, тк восстанавливать весь индекс каждый раз при старте стало не очень.
Что если вынести часть индекса из памяти на диск как отдельный
immutable segment - компактный бинарный файл со своим форматом, который собирается один раз, больше не меняется (для определенных кейсов это подходит) и используется только при чтении.И вот как может выглядеть структура для файла сегмента:
[header][postings area][positions area][term index][footer]
header хранит сигнатуру формата и версию, postings area - списки postings, positions area - позиции токенов, term index - оффсеты до данных конкретного терма, а footer помогает при чтении быстро найти term index в конце файла.Структура пригодится нам в будущем, сейчас главное запомнить, что при чтении мы не восстанавливаем весь индекс в память: мы открываем файл, читаем таблицу термов, находим в ней оффсет нужного терма и дальше берем из файла только конкретный кусок байт.
term -> offset -> byte range -> decoded postings
Переходим к двум важным компонентам:
uvarint и mmap.uvarint
Ранее я писала, что перешла со строковых
DocID документов (postings) на числовые DocOrd - порядковые номера документа. Но даже число можно хранить по разному.В posting lists часто много маленьких чисел: частота терма в документе обычно небольшая, позиции токенов тоже небольшие, а соседние
DocOrd часто лежат близко друг к другу. Поэтому можно вместо типов фиксированных размеров аля uint64 попробовать uvarintЕсли коротко, то через
uvarint маленькие числа занимают меньше байт, большие - больше. Для этого число разбивается на группы по 7 бит, где восьмой - старший бит используется как флаг продолжения.Возьмем число 300.
uvarint берем нижние 7 бит, потом сдвигает число вправо на 7 бит и повторяет процесс, пока не получит 0:
300 & 0x7F = 44
300 >> 7 = 2
2 & 0x7F = 2
2 >> 7 = 0
И у нас два 7-битных куска по 44 и 2. Первый байт будет с флагом продолжение, второй - без флага, потому что число закончилось.
Для работы с числами через
uvarint есть методы binary.AppendUvarint(buf, x) и binary.Uvarint(data)В сегменте я использую
uvarint почти везде, где нужно записать число: для длин, оффсетов, DocOrd, Count, количества позиций и самих позиций.Вместе с этим для компактного хранения используется маленькая оптимизация в виде
delta encoding. Когда то в чате по математике меня удивила простота этого метода: вместо хранения полных id документов:`1, 3, 8` - можно хранить разницы: 1, 2, 5. При чтении можно восстановить исходные значения обычным накоплением.Главное, что это хорошо сочетается с
uvarint, так как числа меньше и занимают они меньше байт. mmap - memory mapping
Фишка
mmap в том, что мы говорим ОС отобразить файл в виртуальное адресное пространство процесса. После этого мы получаем диапазон байт, к которому можно обращаться почти как к обычному []byte. Но в отличии от os.ReadFile, весь файл сразу не загрузится в память. Если файл сегмента весит 1 GB, мы не будем грузить 1 GB в память сразу. ОС может подгружать реальные страницы лениво. Если соответствующей страницы еще нет в памяти, произойдет page fault: процесс обратится к адресу, ОС поймет, что этот адрес относится к отображенному файлу, подгрузит нужную страницу и продолжит выполнение.Например, мы хотим прочитать posting list для терма
alpha, он есть в term index:
postingsOff = 120
postingsLen = 15
и берет только нужный диапазон:
data[postingsBase+120 : postingsBase+120+15]
Именно поэтому mmap хорошо подходит для immutable segment: файл не меняется, данные лежат подряд, у каждого терма есть оффсет и длина. Но
syscall.Mmap - поддерживает только Unix подобных, поэтому на других платформах нужен фоллбек типо os.ReadFile.Подробнее про сегменты. Отдельная благодарность за идею @dmedovich_notes
#fts #perf #projects #go
