Дмитрий Калугин-Балашов большую часть своей жизни писал поиск: с 2011 года в компании Mail.ru был поиск по почте, затем был небольшой перерыв из-за работы в США, а сейчас это — работа над поиском в Couchbase. Одна из первых вещей, которую Дмитрий понял, работая в США — не всегда покупают самое эффективное решение. Иногда покупают то, где клиент будет иметь меньше проблем.
Поэтому ещё в 2013 году Дмитрий написал движок поиска для почтовых ящиков Mail.ru и рассказал об этом в том же году на конференции HighLoad и в статье на Хабре. А на HighLoad 2019 показал, как устроен полнотекстовый поиск в Couchbase Server, и сегодня мы предлагаем расшифровку его доклада.
![](https://habrastorage.org/webt/mn/-k/d0/mn-kd0cidatnzxrhsubdt6dvdkw.png)
На самом деле в Couchbase используется внешний опенсорсный движок Bleve:
Этот движок изначально был создан внутри Couchbase как проект для реализации полнотекстового поиска в виде библиотеки, написанной на Go. Сначала он был простым монолитным индексом — если есть хранилище «ключ-значение», то слева берём слова в виде ключей, а в виде значений ставим документы — и всё, у нас есть полнотекстовый поиск! Но в работе он становился очень большим, а обычное хранилище k-value под поиск не оптимизировано. Нагрузка под поиск очень специфичная, а если ещё и апдейты есть, то движок неизбежно начинает тупить.
Поэтому Couchbase решили создать сегментированный индекс — специальное хранилище под поисковые данные, в котором используются Immutable-сегменты, оптимизированные под поиск.
Что такое обратный индекс? Если есть книга, в которой я хочу что-то найти по слову — как это сделать? На последней странице обычно есть указатель на слово и страницу, где этот термин встречается. Обратный индекс сопоставляет слова со списком. В книге это страницы, у нас — документы в базе (у нас документно-ориентированная БД, в которой хранятся «джейсонки»).
map[string]uint. Самое простое. Кто владеет Гошкой, знает, что это хэш-таблица. Но это не очень хорошо, потому что у нас используются слова, и иногда надо по ним итерироваться. Если у нас неточный поиск, мы начинаем считать расстояние Левенштейна, нужно итерироваться местами, а это по hashmap нельзя. Но можно сделать дерево.
Tree. Но дерево — оно здоровое, поэтому тоже не годится, потому что мы делаем хранилище под поиск, а это одновременно и общее хранилище для БД.
Trie. Префиксное дерево — это уже лучше, оно довольно компактное, его можно через два массива построить. Но можно ли сделать лучше?
Finite State Transducer. Это автомат под названием Vellum, который Couchbase для себя же и написали. Есть реализация FST на Go и других языках. В нем есть всего лишь три процедуры:
Чтобы построить, нужен список слов в алфавитном порядке (например, возьмём «are, ate, see»). Так как у нас индексы сегментированные (сегменты неизменяемые), то нам это отлично подходит — мы его построили один раз и забыли.
Давайте теперь построим. Мы должны хранить пары: слово – число (потом это будет указатель). Состояния автомата просто нумеруются числами, и на каждом ребре есть буква и число. По сумме этих чисел мы считаем конечное число:
![](https://habrastorage.org/webt/8m/ew/bw/8mewbwm_lfrm8nlldbib7tdmexs.jpeg)
Таким образом слово are дает 4. Добавляем второе слово:
![](https://habrastorage.org/webt/91/y-/jp/91y-jpkjx-icap-vxuwgc-7jbp4.jpeg)
Добавляем третье слово:
![](https://habrastorage.org/webt/ow/k-/fo/owk-fokb0dog1a0syebxabueglo.jpeg)
Теперь мы делаем еще одну операцию и компактим:
![](https://habrastorage.org/webt/qn/bo/-l/qnbo-lx8vy5nqy_m0qkaensxkiy.jpeg)
Получается автомат, в котором всего два объекта:
Открыть его мы можем либо из файла через mmap (если он поддерживается в системе):
либо из массива Bytes (это нам будет очень нужно дальше), и можем загрузить прямо из буфера:
Дальше запускаем поиск в FST:
К списку слов есть список страниц в книге, а в БД PostingsList — список документов. Как его можно хранить?
Как сделать лучше? Есть RoaringBitmap, с библиотеками почти для всех языков. Работает он так: берем последовательность наших чисел и разбиваем на куски (чанки). Каждый чанк кодируем одним из трех способов:
Выбираем тот, который лучше сожмет — так мы получаем минимизацию. Там есть ряд проблем, например, не очень понятно, как делать бинарные операции (AND, OR и прочие). Но именно для хранение это получается более эффективным, чем какой-нибудь способ в отдельности. Создано это было, кстати, именно для полнотекстового поиска.
Теперь попробуем сделать полнотекстовый поиск Memory-Only. У нас есть Snapshot — это наш индекс на какую-то единицу времени. В нём есть несколько сегментов с данными. Внутри сегментов ищем обратные индексы, которые все read-only. Также есть какое-то приложение, которое работает с нашим поиском:
![](https://habrastorage.org/webt/bg/ic/jg/bgicjg4bqg5r_oogzffubaunmqa.jpeg)
Давайте пытаемся что-нибудь туда добавить. Понятно, что если мы что-то добавляем, возможно, будет удаление – какие-то данные в предыдущих сегментах инвалидируются:
![](https://habrastorage.org/webt/63/6z/13/636z13j3zny0wwhe_wgsbkoq5py.jpeg)
Но сами сегменты нам не нужны – мы копируем их под read mutex и добавляем новый сегмент. Маленькие фрагменты — это просто битовые массивы. Если что-то удаляется, мы просто выставляем там биты:
![](https://habrastorage.org/webt/hq/pk/bi/hqpkbiclbu_gjltijp6fpfhkwu8.jpeg)
То есть сам сегмент – read only (immutable), но удалить что-то можно, выставив эти биты, если в новом сегменте пришла эта информация. Это называется Segment Introduction: есть новый сегмент (битовый массив) и горутина (Introducer). Ее задача — добавить сегмент в наш Snapshot, который мы присылаем по каналу:
![](https://habrastorage.org/webt/7z/sf/aa/7zsfaawqun0qdsdlymkjcqaujlc.jpeg)
Горутина еще раз, уже под эксклюзивной блокировкой, выставляет эти биты, потому что за время, пока мы передавали, что-то могло измениться:
![](https://habrastorage.org/webt/3t/dn/-n/3tdn-n7lxrg7t_k_rc-vvzpamty.jpeg)
И все — мы переходим к четвертому Snapshot и получаем Memory-Only решение:
![](https://habrastorage.org/webt/go/vu/qf/govuqf-vro1xdyogm0ro3cxmgso.jpeg)
Для того, чтобы сохранить на диск, есть еще одна горутина — Persister. У нас есть номера эпох, также пронумеруем сегменты (a, b, c, d):
![](https://habrastorage.org/webt/6s/il/cn/6silcny-5xidrw_ykmr4-wdz-34.jpeg)
В Persister есть цикл FOR, время от времени он пробуждается и смотрит – «О! Появился новый сегмент, давайте его сохраним»:
![](https://habrastorage.org/webt/z0/7a/qe/z07aqefre0mdublfsbnwnttjsaa.jpeg)
Для этого сегмента у нас две базы данных: маленькая БД, куда он сохраняется, и корневая БД, которая просто описывает всю эту конструкцию. Таким образом мы сохраняем на диск и меняем номер эпохи после записи:
![](https://habrastorage.org/webt/43/mf/uq/43mfuqubasv8jdvybg6kjrxez2g.jpeg)
Сегменты будут расти (они все неизменяемые), когда-то мы захотим их склеить — и для этого у нас есть merger. Создаем Merge plane третьей горутиной:
![](https://habrastorage.org/webt/sq/qv/iz/sqqviz_rudkxorbae1y60j-lias.jpeg)
Также есть номер эпохи, когда мы мерджим. Далее мы делаем какие-то операции. Merge Introduction, как и обычный сегмент Introduction, попадает обратно в него и создает новый сегмент, а два склеивает, удаляя оттуда данные:
![](https://habrastorage.org/webt/em/xl/iv/emxlivhrw2ctjwoxdz1aywl21fm.jpeg)
Таким образом мы удаляем часть сегментов.
Важное примечание. После того, как мы записали zap-файл на диск, мы сегмент закрываем и тут же обратно открываем, но не как in-memory сегмент, а как сегмент на диске. Хотя у них одинаковый интерфейс, устроены они по-разному: сегмент на диске проецируется в память через mmap.
Изначально это был BoltDB. Потом создатель сказал: «Ну вас всех на фиг, я устал, я ухожу», и BoltDB закрылся. Хотя позже его форкнули в BBoltDB, работал он всё равно плохо, потому что вернулись к той же проблеме: база данных в общем не очень подходит для хранения поисковых индексов. И мы тогда заменили BBoltDB на самописный формат .zap. Корневая база осталась BBoltDB, но там ничего особо критичного хранить не надо:
![](https://habrastorage.org/webt/jj/nr/pn/jjnrpnvmku5er2aolhqxbib9_2m.jpeg)
Формат ZAP — это просто сегмент на диске. Мы его не читаем READ’ами, он читается mmap’ом, при этом данные внутри максимально удобны для in-memory работы. Сам формат ZAP с индексами выглядит так:
![](https://habrastorage.org/webt/1w/h3/z2/1wh3z2wjlix0ffwnyhwijcpbgto.jpeg)
В футере описано, где что искать, и мы по указателю находим индекс полей. Что у нас есть? Есть сколько-то (от 0 до F#) проиндексированных полей в документах, они пронумерованы и проиндексированы. Стрелками показаны указатели, сколько полей, и мы знаем заранее, сколько их. Мы находим в Fields Index указатель, а в Fields — место, и понимаем по названию поля, что это такое:
![](https://habrastorage.org/webt/-q/nf/1d/-qnf1d7eqcysxv6zllb_16u062e.jpeg)
Есть еще один указатель:
![](https://habrastorage.org/webt/oj/nx/2w/ojnx2wzik56admfay-p63fvgu6s.jpeg)
Он указывает место, где будут храниться наши словари (dictionaries), при этом, под каждое поле будет свой словарь:
![](https://habrastorage.org/webt/fe/np/tr/fenptrodkwcrq7rr8vsscimm_-m.jpeg)
Этот указатель показывает VELLUM данные:
![](https://habrastorage.org/webt/-q/t8/lb/-qt8lbpferucizefxbutnocjbzk.jpeg)
А мы помним, что VELLUM может читать данные прямо из памяти. Мы спроецировали память, нашли нужный указатель, взяли кусок данных и начали с помощью VELLUM в нём искать. Нам даже не нужны READ, мы просто к списку слов делаем список OFFSET, который ведёт к RoaringBitmap. Таким образом мы получаем номера документов, которые найдутся по этому слову в этом поле:
![](https://habrastorage.org/webt/s1/mu/5i/s1mu5iwo_zgwoqyzhkkhjrnwfl8.jpeg)
Также есть позиции вхождения, если мы хотим сделать подсветку. Если у нас длинная строка, то мы узнаем, в каком месте находится нужное нам слово. Еще мы можем получить определенную статистику частоты встречаемости и другую инфу, нужную для ранжирования:
![](https://habrastorage.org/webt/f0/g_/ju/f0g_juvmdpsv5vkz96-0ixk1_pm.jpeg)
DocValues – это вспомогательный и необязательный список полей, в нём хранятся значения полей:
![](https://habrastorage.org/webt/7p/qt/go/7pqtgo5vx2hatqa4sswihmfqv4k.jpeg)
Значения полей нужны для ранжирования, мы дублируем по номеру поля значения для каждого документа:
![](https://habrastorage.org/webt/bx/uc/gk/bxucgkhfj4uwrs83v0hef8o8mlo.jpeg)
Для каждого документа мы знаем список полей и их значение. И, что самое важное, тут есть искусственное поле — ID. Дело в том, что внутри ZAP-файла все документы нумеруются с 0 и до бесконечности, а в самой базе данных текстовые имена. Так что в ID происходит сопоставление между номером внутри ZAP-файла и внешним номером (внешним именем):
![](https://habrastorage.org/webt/9f/ra/nl/9franlimsddyo8-5memtylhuzbc.jpeg)
Остаются мелочи. Это Chunk Factor(на какие кусочки бьем, когда делаем чанки данных), версия, контрольная сумма и число документов (D#):
![](https://habrastorage.org/webt/bg/t2/kl/bgt2kl8ahvsysbiphy-t-p4pe2i.jpeg)
Это весь ZAP-файл. Как искать, думаю, уже понятно: мы отражаем в память и находим, по какому полю ищем. После этого находим слово, идем по длинной цепочке и находим результаты.
Есть интересная операция Rollback. Базе данных Rollback нужен всегда — мы можем нагородить огород, и нам нужна возможность откатиться. В нашем случае откат делается очень просто. У нас есть эпохи. Мы храним в корневой базе текущую конфигурацию и предыдущие (1-2), куда хотим откатиться. Если мы хотим откатиться на предыдущую эпоху, мы достаем конфигурацию из индекса, и получаем откат на предыдущую эпоху. В сегмент мы добавляем, когда происходит какая-то операция или группа операций (мы обычно их вставляем большой группой):
![](https://habrastorage.org/webt/bs/ta/qe/bstaqe_kovk1tnqpngpj0dfideg.jpeg)
Если же за это время у нас ничего такого не добавится, мы сделаем Rollback под эксклюзивом — это нормально.
Так работает само ядро. Как работает поиск — уже очевидно. Если поиск идет по точному совпадению, то прочитали, прошли по цепочке и нашли. Если поиск неточный, то добавляется автомат Левенштейна и начинаются итерации по vellum, но процесс проходит примерно так же.
Поэтому ещё в 2013 году Дмитрий написал движок поиска для почтовых ящиков Mail.ru и рассказал об этом в том же году на конференции HighLoad и в статье на Хабре. А на HighLoad 2019 показал, как устроен полнотекстовый поиск в Couchbase Server, и сегодня мы предлагаем расшифровку его доклада.
![](https://habrastorage.org/webt/mn/-k/d0/mn-kd0cidatnzxrhsubdt6dvdkw.png)
На самом деле в Couchbase используется внешний опенсорсный движок Bleve:
Этот движок изначально был создан внутри Couchbase как проект для реализации полнотекстового поиска в виде библиотеки, написанной на Go. Сначала он был простым монолитным индексом — если есть хранилище «ключ-значение», то слева берём слова в виде ключей, а в виде значений ставим документы — и всё, у нас есть полнотекстовый поиск! Но в работе он становился очень большим, а обычное хранилище k-value под поиск не оптимизировано. Нагрузка под поиск очень специфичная, а если ещё и апдейты есть, то движок неизбежно начинает тупить.
Поэтому Couchbase решили создать сегментированный индекс — специальное хранилище под поисковые данные, в котором используются Immutable-сегменты, оптимизированные под поиск.
Что такое обратный индекс? Если есть книга, в которой я хочу что-то найти по слову — как это сделать? На последней странице обычно есть указатель на слово и страницу, где этот термин встречается. Обратный индекс сопоставляет слова со списком. В книге это страницы, у нас — документы в базе (у нас документно-ориентированная БД, в которой хранятся «джейсонки»).
ОК, а как хранить список слов?
map[string]uint. Самое простое. Кто владеет Гошкой, знает, что это хэш-таблица. Но это не очень хорошо, потому что у нас используются слова, и иногда надо по ним итерироваться. Если у нас неточный поиск, мы начинаем считать расстояние Левенштейна, нужно итерироваться местами, а это по hashmap нельзя. Но можно сделать дерево.
Tree. Но дерево — оно здоровое, поэтому тоже не годится, потому что мы делаем хранилище под поиск, а это одновременно и общее хранилище для БД.
Trie. Префиксное дерево — это уже лучше, оно довольно компактное, его можно через два массива построить. Но можно ли сделать лучше?
Finite State Transducer. Это автомат под названием Vellum, который Couchbase для себя же и написали. Есть реализация FST на Go и других языках. В нем есть всего лишь три процедуры:
- Построение FST (один раз);
- Поиск;
- Итерирование.
Чтобы построить, нужен список слов в алфавитном порядке (например, возьмём «are, ate, see»). Так как у нас индексы сегментированные (сегменты неизменяемые), то нам это отлично подходит — мы его построили один раз и забыли.
Давайте теперь построим. Мы должны хранить пары: слово – число (потом это будет указатель). Состояния автомата просто нумеруются числами, и на каждом ребре есть буква и число. По сумме этих чисел мы считаем конечное число:
![](https://habrastorage.org/webt/8m/ew/bw/8mewbwm_lfrm8nlldbib7tdmexs.jpeg)
Таким образом слово are дает 4. Добавляем второе слово:
![](https://habrastorage.org/webt/91/y-/jp/91y-jpkjx-icap-vxuwgc-7jbp4.jpeg)
Добавляем третье слово:
![](https://habrastorage.org/webt/ow/k-/fo/owk-fokb0dog1a0syebxabueglo.jpeg)
Теперь мы делаем еще одну операцию и компактим:
![](https://habrastorage.org/webt/qn/bo/-l/qnbo-lx8vy5nqy_m0qkaensxkiy.jpeg)
Получается автомат, в котором всего два объекта:
- Builder — мы строим, операцию делаем;
- Reader — мы читаем и делаем либо поиск, либо итерацию.
Открыть его мы можем либо из файла через mmap (если он поддерживается в системе):
fst, err := vellum.Open("/tmp/vellum.fst")
либо из массива Bytes (это нам будет очень нужно дальше), и можем загрузить прямо из буфера:
fst, err := vellum.Load(buf.Bytes())
Дальше запускаем поиск в FST:
val, exists, err = fst.Get([]byte("dog"))
Как хранить PostingsList?
К списку слов есть список страниц в книге, а в БД PostingsList — список документов. Как его можно хранить?
- Просто список чисел – это массив (кстати, можно использовать дельта-кодирование);
- Битовый массив. Это удобно, если, что список чисел, как страницы в книге, начинается просто от 0 и числа идут подряд. Но только если в нем не будет повторяемых элементов.
- RLE-сжатие. Битовый массив можно еще иногда сжать.
Как сделать лучше? Есть RoaringBitmap, с библиотеками почти для всех языков. Работает он так: берем последовательность наших чисел и разбиваем на куски (чанки). Каждый чанк кодируем одним из трех способов:
- Просто список чисел
- Битовый массив
- RLE-сжатие
Выбираем тот, который лучше сожмет — так мы получаем минимизацию. Там есть ряд проблем, например, не очень понятно, как делать бинарные операции (AND, OR и прочие). Но именно для хранение это получается более эффективным, чем какой-нибудь способ в отдельности. Создано это было, кстати, именно для полнотекстового поиска.
Поиск Memory-Only?
Теперь попробуем сделать полнотекстовый поиск Memory-Only. У нас есть Snapshot — это наш индекс на какую-то единицу времени. В нём есть несколько сегментов с данными. Внутри сегментов ищем обратные индексы, которые все read-only. Также есть какое-то приложение, которое работает с нашим поиском:
![](https://habrastorage.org/webt/bg/ic/jg/bgicjg4bqg5r_oogzffubaunmqa.jpeg)
Давайте пытаемся что-нибудь туда добавить. Понятно, что если мы что-то добавляем, возможно, будет удаление – какие-то данные в предыдущих сегментах инвалидируются:
![](https://habrastorage.org/webt/63/6z/13/636z13j3zny0wwhe_wgsbkoq5py.jpeg)
Но сами сегменты нам не нужны – мы копируем их под read mutex и добавляем новый сегмент. Маленькие фрагменты — это просто битовые массивы. Если что-то удаляется, мы просто выставляем там биты:
![](https://habrastorage.org/webt/hq/pk/bi/hqpkbiclbu_gjltijp6fpfhkwu8.jpeg)
То есть сам сегмент – read only (immutable), но удалить что-то можно, выставив эти биты, если в новом сегменте пришла эта информация. Это называется Segment Introduction: есть новый сегмент (битовый массив) и горутина (Introducer). Ее задача — добавить сегмент в наш Snapshot, который мы присылаем по каналу:
![](https://habrastorage.org/webt/7z/sf/aa/7zsfaawqun0qdsdlymkjcqaujlc.jpeg)
Горутина еще раз, уже под эксклюзивной блокировкой, выставляет эти биты, потому что за время, пока мы передавали, что-то могло измениться:
![](https://habrastorage.org/webt/3t/dn/-n/3tdn-n7lxrg7t_k_rc-vvzpamty.jpeg)
И все — мы переходим к четвертому Snapshot и получаем Memory-Only решение:
![](https://habrastorage.org/webt/go/vu/qf/govuqf-vro1xdyogm0ro3cxmgso.jpeg)
Для того, чтобы сохранить на диск, есть еще одна горутина — Persister. У нас есть номера эпох, также пронумеруем сегменты (a, b, c, d):
![](https://habrastorage.org/webt/6s/il/cn/6silcny-5xidrw_ykmr4-wdz-34.jpeg)
В Persister есть цикл FOR, время от времени он пробуждается и смотрит – «О! Появился новый сегмент, давайте его сохраним»:
![](https://habrastorage.org/webt/z0/7a/qe/z07aqefre0mdublfsbnwnttjsaa.jpeg)
Для этого сегмента у нас две базы данных: маленькая БД, куда он сохраняется, и корневая БД, которая просто описывает всю эту конструкцию. Таким образом мы сохраняем на диск и меняем номер эпохи после записи:
![](https://habrastorage.org/webt/43/mf/uq/43mfuqubasv8jdvybg6kjrxez2g.jpeg)
Сегменты будут расти (они все неизменяемые), когда-то мы захотим их склеить — и для этого у нас есть merger. Создаем Merge plane третьей горутиной:
![](https://habrastorage.org/webt/sq/qv/iz/sqqviz_rudkxorbae1y60j-lias.jpeg)
Также есть номер эпохи, когда мы мерджим. Далее мы делаем какие-то операции. Merge Introduction, как и обычный сегмент Introduction, попадает обратно в него и создает новый сегмент, а два склеивает, удаляя оттуда данные:
![](https://habrastorage.org/webt/em/xl/iv/emxlivhrw2ctjwoxdz1aywl21fm.jpeg)
Таким образом мы удаляем часть сегментов.
Важное примечание. После того, как мы записали zap-файл на диск, мы сегмент закрываем и тут же обратно открываем, но не как in-memory сегмент, а как сегмент на диске. Хотя у них одинаковый интерфейс, устроены они по-разному: сегмент на диске проецируется в память через mmap.
Формат ZAP
Изначально это был BoltDB. Потом создатель сказал: «Ну вас всех на фиг, я устал, я ухожу», и BoltDB закрылся. Хотя позже его форкнули в BBoltDB, работал он всё равно плохо, потому что вернулись к той же проблеме: база данных в общем не очень подходит для хранения поисковых индексов. И мы тогда заменили BBoltDB на самописный формат .zap. Корневая база осталась BBoltDB, но там ничего особо критичного хранить не надо:
![](https://habrastorage.org/webt/jj/nr/pn/jjnrpnvmku5er2aolhqxbib9_2m.jpeg)
Формат ZAP — это просто сегмент на диске. Мы его не читаем READ’ами, он читается mmap’ом, при этом данные внутри максимально удобны для in-memory работы. Сам формат ZAP с индексами выглядит так:
![](https://habrastorage.org/webt/1w/h3/z2/1wh3z2wjlix0ffwnyhwijcpbgto.jpeg)
В футере описано, где что искать, и мы по указателю находим индекс полей. Что у нас есть? Есть сколько-то (от 0 до F#) проиндексированных полей в документах, они пронумерованы и проиндексированы. Стрелками показаны указатели, сколько полей, и мы знаем заранее, сколько их. Мы находим в Fields Index указатель, а в Fields — место, и понимаем по названию поля, что это такое:
![](https://habrastorage.org/webt/-q/nf/1d/-qnf1d7eqcysxv6zllb_16u062e.jpeg)
Есть еще один указатель:
![](https://habrastorage.org/webt/oj/nx/2w/ojnx2wzik56admfay-p63fvgu6s.jpeg)
Он указывает место, где будут храниться наши словари (dictionaries), при этом, под каждое поле будет свой словарь:
![](https://habrastorage.org/webt/fe/np/tr/fenptrodkwcrq7rr8vsscimm_-m.jpeg)
Этот указатель показывает VELLUM данные:
![](https://habrastorage.org/webt/-q/t8/lb/-qt8lbpferucizefxbutnocjbzk.jpeg)
А мы помним, что VELLUM может читать данные прямо из памяти. Мы спроецировали память, нашли нужный указатель, взяли кусок данных и начали с помощью VELLUM в нём искать. Нам даже не нужны READ, мы просто к списку слов делаем список OFFSET, который ведёт к RoaringBitmap. Таким образом мы получаем номера документов, которые найдутся по этому слову в этом поле:
![](https://habrastorage.org/webt/s1/mu/5i/s1mu5iwo_zgwoqyzhkkhjrnwfl8.jpeg)
Также есть позиции вхождения, если мы хотим сделать подсветку. Если у нас длинная строка, то мы узнаем, в каком месте находится нужное нам слово. Еще мы можем получить определенную статистику частоты встречаемости и другую инфу, нужную для ранжирования:
![](https://habrastorage.org/webt/f0/g_/ju/f0g_juvmdpsv5vkz96-0ixk1_pm.jpeg)
DocValues – это вспомогательный и необязательный список полей, в нём хранятся значения полей:
![](https://habrastorage.org/webt/7p/qt/go/7pqtgo5vx2hatqa4sswihmfqv4k.jpeg)
Значения полей нужны для ранжирования, мы дублируем по номеру поля значения для каждого документа:
![](https://habrastorage.org/webt/bx/uc/gk/bxucgkhfj4uwrs83v0hef8o8mlo.jpeg)
Для каждого документа мы знаем список полей и их значение. И, что самое важное, тут есть искусственное поле — ID. Дело в том, что внутри ZAP-файла все документы нумеруются с 0 и до бесконечности, а в самой базе данных текстовые имена. Так что в ID происходит сопоставление между номером внутри ZAP-файла и внешним номером (внешним именем):
![](https://habrastorage.org/webt/9f/ra/nl/9franlimsddyo8-5memtylhuzbc.jpeg)
Остаются мелочи. Это Chunk Factor(на какие кусочки бьем, когда делаем чанки данных), версия, контрольная сумма и число документов (D#):
![](https://habrastorage.org/webt/bg/t2/kl/bgt2kl8ahvsysbiphy-t-p4pe2i.jpeg)
Это весь ZAP-файл. Как искать, думаю, уже понятно: мы отражаем в память и находим, по какому полю ищем. После этого находим слово, идем по длинной цепочке и находим результаты.
Rollback
Есть интересная операция Rollback. Базе данных Rollback нужен всегда — мы можем нагородить огород, и нам нужна возможность откатиться. В нашем случае откат делается очень просто. У нас есть эпохи. Мы храним в корневой базе текущую конфигурацию и предыдущие (1-2), куда хотим откатиться. Если мы хотим откатиться на предыдущую эпоху, мы достаем конфигурацию из индекса, и получаем откат на предыдущую эпоху. В сегмент мы добавляем, когда происходит какая-то операция или группа операций (мы обычно их вставляем большой группой):
![](https://habrastorage.org/webt/bs/ta/qe/bstaqe_kovk1tnqpngpj0dfideg.jpeg)
Если же за это время у нас ничего такого не добавится, мы сделаем Rollback под эксклюзивом — это нормально.
Так работает само ядро. Как работает поиск — уже очевидно. Если поиск идет по точному совпадению, то прочитали, прошли по цепочке и нашли. Если поиск неточный, то добавляется автомат Левенштейна и начинаются итерации по vellum, но процесс проходит примерно так же.
Пока пандемия идет к финишу, мы продолжаем проводить встречи онлайн. В понедельник 30 ноября будем обсуждать банковскую архитектуру на встрече «Эволюция через боль. Как устроен СберБанк Онлайн изнутри?». Рассмотрим с нуля, как создается и развивается архитектура в банке и узнаем, что под капотом у крупнейшего банка страны. Узнаем, почему банку недостаточно простого приложения из одного сервиса и одной базы данных, увидим на примерах монолит и микросервис. Начало в 18 часов.
А 3 декабря будет митап «Безопасность и надёжность в финтехе». Спикеров будет несколько, и они поднимут несколько тем. Сначала будет разговор о закулисье финтеха, затем — как и какими инструментами сделать финтех надежным сервисом, и на закуску — как снизить риски ИБ в разработке финансовых систем. Начнем в 17.
Следите за новостями — Telegram, Twitter, VK и FB и присоединяйтесь к обсуждениям.