Это перевод моей статьи в моем блоге про архитектуру Apache Lucene, про одну из самых известных библиотек реализации поискового индекса. Elasticsearch и Solr, широко известные реализации масштабируемых решений для поиска, они используют эту библиотеку под капотом. Я работаю над созданием решений для поиска в сфере электронной коммерции, и постоянно сталкиваюсь с этой библиотекой при повседневной работе. Apache Lucene реализует большую часть необходимого функционала для построения поисковой системы. Начиная с процесса токенизации, который извлекает канонические формы слов в виде токенов, продолжая полной реализацией инвертированного индекса, и завершая репликацией сегментов в режиме близком к реальному времени. Количество практически полезных фичей, реализованных за два десялилетия существования библиотеки, колоссально. Эта библиотека интегрирует знания из лингвистики, математики и компьютерных наук.
Инвертированный индекс
Apache Lucene реализует архитектуру инвертированного индекса. На уровне реализации логический индекс содержит коллекцию неизменяемых сегментов, хранящихся как файлы в файловой системе. Каждый сегмент сам по себе является инвертированным индексом. Такой индекс — это структура данных словаря с терминами в качестве ключей и данными по размещению (postings) в качестве значений. Постинг — это список идентификаторов документов и количеств вхождений термина в данном документе. Этот словарь использует Finite State Transducers, FST [1] для поиска терминов, что можно представить как нечто похожее на отсортированные списки с пропусками [2]. Такая отсортированная навигационная карта является краеугольным камнем для эффективного поиска по огромным обьемам документов. Lucene также очень эффективен в использовании памяти. Среди прочих алгоритмов, он использует алгоритмы кодирования разницами для сжатия идентификаторов документов в постингах [3]. Упрощенно идея этого сжатия заключается в сортировке списока целых чисел и сохранения дельт между ними. Это также повышает производительность операций ввода-вывода диска.
Помимо инвертированного индекса, Lucene может использовать колоночно-ориентированное хранилище, известное как docValues, для определенных полей внутри документа. Это важная структура данных в конвейере выполнения запросов для операций группировки и сортировки. Она хранит все значения конкретного поля, отсортированные по идентификаторам документов [4]. Это превращает операцию извлечения значений полей для данного набора документов в одну последовательную операцию чтения с диска. Ранее активно использовались многократные повторяющиеся операции дискового чтения полей документа и их кэширование с помощью FieldCache.
С точки зрения классов Java, Lucene содержит два основных для доступа к файлам индекса: IndexWriter и IndexReader. Документация JavaDoc Lucene является действительно хорошим источником информации. Класс IndexWriter предполагается использовать в единственном экземпляре приложения, накапливающим обновления в памяти и при определенных условиях обновляющим, фиксирующим или сохраняющим их в файловую систему. Кроме того, Writer применяет правило слияния сегментов для контроля количества сегментов. Каждый коммит создает новые неизменяемые файлы сегментов, помечая неактивными старые и удаляя помеченные на удаление документы. В настоящее время реализацией по умолчанию является класс TieredMergePolicy.
Поиск
На первый взгляд реализация поиска может показаться простой задачей, но по мере практической имплементации возникает много нюансов. Текст запрос преобразуется в список токенов с помощью различных анализаторов. Для каждого токена выполняется поиск в индексе. Промежуточные результаты сохраняются в структуре данных битового сета. Реализации интерфейса Bits в Lucene облегчают выполнение операций объединения/пересечения над результатами поиска нескольких токенов [5]. Битовый сет упрощает кэширование на этапе применения фильтров. Когда требуется фильтрация или сортировка, это выполняется с помощью операции пересечения битового сета с docValues для данного набора идентификаторов документов.
Репликация
Существует два типа репликации: репликация документов и репликация сегментов. Долгое время Elasticsearch и OpenSearch (форк Elasticsearch от Amazon) поддерживали репликацию только отдельных документов. Apache Lucene уже некоторое время как добавил поддержку репликации сегментов в режиме близком к реальному времени [6]. Реализация репликации документов в Elasticsearch требует от координирующей ноды сбора ответов от всех реплик на операцию записи, что создает дополнительную нагрузку на ЦПУ. Интересным опытом реализации репликации сегментов поделился Yelp, создавший opensource проект Nrtsearch [7]. Amazon последовал этому подходу [8] с репликацией сегментов в OpenSearch. Они снижают нагрузку на CPU через повышение нагрузки на сеть и увеличение нагрузки на основную ноду [9]. Сейчас OpenSearch идет дальше: чтобы уменьшить пропускную способность сети, они реализуют поддержку сетевого хранилища. Также они экспериментируют с репликацией сегментов «peer-to-peer» [10].
Ссылки
1. Using Finite State Transducers in Lucene — https://dzone.com/articles/using-finite-state-transducers
2. Dissecting Lucene — The Index formathttps://kandepet.com/dissecting-lucene-the-index-format/
3. Lucene Inside Out — Dealing With Integer Encoding and Compression — https://towardsdatascience.com/lucene-inside-out-dealing-with-integer-encoding-and-compression-fe28f9dd265d
4. What is an Apache Lucene Codec? — https://www.elastic.co/blog/what-is-an-apache-lucene-codec
5. Exploring Apache Lucene — Part 2: Search and Ranking — https://j.blaszyk.me/tech-blog/exploring-apache-lucene-search-and-ranking/
6. Lucene’s near-real-time segment index replication — https://www.javacodegeeks.com/2017/09/lucenes-near-real-time-segment-index-replication.html
7. Nrtsearch: Yelp’s Fast, Scalable and Cost Effective Search Engine — https://engineeringblog.yelp.com/2021/09/nrtsearch-yelps-fast-scalable-and-cost-effective-search-engine.html
8. OpenSearch Segment Replication [RFC] — https://github.com/opensearch-project/OpenSearch/issues/1694
9. First Bite of OpenSearch Segment Replication — https://medium.com/@rockybean/first-bite-of-opensearch-segment-replication-b22d0808e4c9
10. Reduce compute costs and increase throughput with segment replication, generally available in OpenSearch 2.7 — https://opensearch.org/blog/segment-replication/