Инвертированный индекс: как устроен полнотекстовый поиск и Elasticsearch

Как работает инвертированный индекс: токенизация и анализаторы, posting lists, пересечение списков, сжатие, ранжирование TF-IDF и BM25, сегменты и шардирование, как в Elasticsearch.

14 мин чтениясистемный дизайн · поиск · структуры данных · python

Коротко

ВопросОтвет
Что этоСловарь «термин → отсортированный список документов, где он встречается»
ЗачемНайти документы по словам без полного перебора всех текстов
Запрос A AND BПересечение двух отсортированных списков: O(n+m)O(n + m) или быстрее с пропусками
РанжированиеTF-IDF или BM25: редкое слово весит больше, частое в документе — больше, но с насыщением
МасштабированиеИндекс режется на шарды по документам, запрос идёт во все шарды, топ-K сливается
Где используетсяLucene, Elasticsearch, OpenSearch, Solr, полнотекстовый поиск в PostgreSQL (GIN)
  • «Инвертированный» — потому что обычное хранение идёт от документа к словам, а индекс переворачивает связь: от слова к документам.
  • Качество поиска на 80% решает не структура данных, а анализатор: как текст режется на токены и приводится к нормальной форме.
  • На собеседовании тема всплывает в задачах «спроектируйте поиск по твитам / товарам / логам» и как подвопрос в автодополнении и веб-краулере.

Почему не LIKE '%кот%'

Представьте 100 миллионов товаров и запрос «красные кроссовки». Наивный вариант — пройти по всем описаниям и проверить подстроку. Это O(суммарная длина текстов)O(\text{суммарная длина текстов}) на каждый запрос, и обычный B-tree-индекс не поможет: индекс базы данных ускоряет поиск по префиксу значения, а не по слову в середине строки.

Кроме скорости, у подстроки плохая семантика: «кроссовки» не найдут «кроссовок», зато %кот% найдёт «скотч» и «котлету». И никакого порядка результатов: какой из тысяч товаров показывать первым?

Инвертированный индекс решает все три проблемы. Работу переносим на время записи: один раз разбираем каждый документ и раскладываем его слова по «корзинам». Запрос потом читает только корзины своих слов.

Анализ текста: от строки к терминам

Прежде чем что-то индексировать, текст проходит через анализатор. В Elasticsearch он состоит из трёх стадий:

  1. Character filters — чистка сырой строки: убрать HTML-теги, заменить «ё» на «е».
  2. Tokenizer — нарезка на токены. Стандартный токенизатор режет по границам слов по правилам Unicode, есть варианты для n-грамм, путей, email.
  3. Token filters — нормализация каждого токена: нижний регистр, удаление стоп-слов («и», «в», «the»), стемминг («кроссовки» → «кроссовк»), синонимы.

Главное правило: запрос должен проходить через тот же анализатор, что и документы. Если документ проиндексирован со стеммингом, а запрос — без, слово «кроссовки» не совпадёт с термином «кроссовк», и поиск молча вернёт пусто. Это классический баг, который всплывает и в продакшене, и в вопросах интервьюера.

Для русского стемминг особенно важен: у одного существительного до 12 форм. Есть два подхода — стеммер (отрезает окончания по правилам, быстро и грубо) и лемматизатор (приводит к словарной форме по морфологическому словарю, точнее и дороже).

Упрощённый анализатор на Python — нижний регистр, нарезка по словам, стоп-слова:

import re from collections import defaultdict STOP = {"и", "в", "на", "the", "a", "of"} def analyze(text): tokens = re.findall(r"\w+", text.lower()) return [t for t in tokens if t not in STOP]

Строим индекс

Для каждого термина храним posting list — список вхождений, отсортированный по doc_id. Каждый элемент (posting) содержит id документа и, если нужны фразовые запросы, позиции слова в документе. Отдельно запоминаем длину каждого документа — она пригодится для ранжирования.

def build_index(docs): index = defaultdict(list) # term -> [(doc_id, [positions])] doc_len = {} for doc_id, text in sorted(docs.items()): terms = analyze(text) doc_len[doc_id] = len(terms) positions = defaultdict(list) for pos, term in enumerate(terms): positions[term].append(pos) for term, pos_list in positions.items(): index[term].append((doc_id, pos_list)) return index, doc_len docs = { 1: "Кот спит на диване", 2: "Собака и кот играют", 3: "Кот ловит мышь, мышь убегает", 4: "Собака спит", } index, doc_len = build_index(docs) print(index["кот"]) # [(1, [0]), (2, [1]), (3, [0])] print(index["мышь"]) # [(3, [2, 3])] print(doc_len) # {1: 3, 2: 3, 3: 5, 4: 2}

Документы обходятся в порядке возрастания id, поэтому списки получаются отсортированными без отдельной сортировки. Это не мелочь: на сортированности держатся и быстрое пересечение, и сжатие.

Словарь терминов (term dictionary) в настоящих движках — не хеш-таблица. Lucene хранит его в виде конечного автомата (FST): он компактный и умеет искать по префиксу, что нужно для запросов кросс* и нечёткого поиска. Идея родственна префиксному дереву.

Булев поиск: пересечение posting lists

Запрос «кот спит» с семантикой AND — это пересечение двух списков doc_id. Списки отсортированы, значит работает техника двух указателей, как в слиянии в сортировке слиянием:

def intersect(a, b): i = j = 0 out = [] while i < len(a) and j < len(b): if a[i] == b[j]: out.append(a[i]) i += 1 j += 1 elif a[i] < b[j]: i += 1 else: j += 1 return out def ids(term): return [d for d, _ in index.get(term, [])] def search_and(query): # Начинаем с самого короткого списка: промежуточный результат меньше terms = sorted(analyze(query), key=lambda t: len(index.get(t, []))) if not terms: return [] result = ids(terms[0]) for t in terms[1:]: result = intersect(result, ids(t)) if not result: break return result print(search_and("кот спит")) # [1] print(search_and("собака кот")) # [2]

Сложность — O(n+m)O(n + m). Порядок пересечения важен: результат не длиннее самого короткого списка, поэтому начинать надо с самого редкого термина. Это та же оптимизация, что делает планировщик запросов в БД, выбирая порядок JOIN.

OR — слияние списков без дублей, тоже O(n+m)O(n + m). NOT — проход по списку с вычитанием. Для запроса из kk терминов в OR используется слияние k списков через кучу.

Когда списки сильно разной длины

Слово «и» встречается в 50 млн документов, а «рекурсия» — в 2 тысячах. Линейное пересечение прочитает все 50 млн элементов ради 2000 совпадений. Решение — не идти по длинному списку шаг за шагом, а прыгать:

  • Skip pointers / skip lists. В длинный список встраиваются указатели «вперёд на n\sqrt{n} элементов» или многоуровневый skip list, как в Lucene. Если следующий кандидат далеко, перепрыгиваем целый блок.
  • Галопирующий поиск (exponential search). Для каждого элемента короткого списка ищем позицию в длинном: удваиваем шаг 1, 2, 4, 8… пока не перелетим, затем бинарный поиск внутри последнего интервала.
from bisect import bisect_left def gallop_intersect(small, big): out, lo = [], 0 for x in small: step, hi = 1, lo while hi < len(big) and big[hi] < x: lo = hi hi += step step *= 2 k = bisect_left(big, x, lo, min(hi + 1, len(big))) if k < len(big) and big[k] == x: out.append(x) lo = k return out print(gallop_intersect([3, 7], [1, 2, 3, 4, 5, 6, 8])) # [3]

Сложность — O(mlog⁡(n/m))O(m \log(n / m)), где mm — длина короткого списка. При m≪nm \ll n это намного лучше O(n+m)O(n + m).

Фразовые запросы

Запрос "кот спит" в кавычках требует, чтобы слова стояли рядом и в нужном порядке. Для этого и хранились позиции: сначала пересекаем списки документов, затем в каждом общем документе проверяем, что есть позиция pp у первого слова и p+1p + 1 у второго.

def phrase(t1, t2): first = dict(index.get(t1, [])) res = [] for doc_id, pos2 in index.get(t2, []): if doc_id in first: s = set(first[doc_id]) if any(p - 1 in s for p in pos2): res.append(doc_id) return res print(phrase("кот", "спит"), phrase("собака", "спит")) # [1] [4]

Обратите внимание: в документе 1 исходный текст «Кот спит на диване», и «на» выкинуто как стоп-слово. Настоящие движки сохраняют позиции исходного текста с «дырками», чтобы фраза «спит диване» не нашлась там, где между словами было «на». В нашем упрощении позиции считаются после фильтрации — так делать не стоит.

Сжатие: почему индекс помещается в память

Posting list для частого слова — десятки миллионов чисел. По 4 байта на число это гигабайты. Выручает сортированность: вместо самих id храним разности соседних (delta encoding, или gaps). Разности маленькие, а маленькие числа кодируются в мало бит.

Простейший вариант — Variable Byte (VByte): 7 бит данных в байте, старший бит помечает последний байт числа.

def vbyte_encode(doc_ids): out = bytearray() prev = 0 for d in doc_ids: gap = d - prev prev = d while gap >= 128: out.append(gap & 0x7F) gap >>= 7 out.append(gap | 0x80) # старший бит = последний байт числа return bytes(out) postings = [5, 17, 130, 131, 1000, 100000] print(len(vbyte_encode(postings)), "байт вместо", len(postings) * 4) # 9 байт вместо 24

Lucene использует более плотные блочные схемы семейства Frame of Reference / PForDelta: числа пакуются блоками по 128 с одинаковой разрядностью, что хорошо ложится на SIMD. Плюс у сжатия есть неочевидный бонус: меньше байт — меньше чтений с диска и промахов кеша, поэтому сжатый индекс часто читается быстрее несжатого.

Ранжирование: TF-IDF и BM25

Булев поиск отвечает «подходит или нет». Пользователю нужен порядок: самые релевантные документы сверху. Две интуиции:

  • TF (term frequency) — чем чаще слово в документе, тем документ релевантнее.
  • IDF (inverse document frequency) — чем реже слово в коллекции, тем оно информативнее. Совпадение по «рекурсия» говорит больше, чем по «код».

Классический TF-IDF для термина tt и документа dd:

tfidf(t,d)=tf(t,d)⋅log⁡Ndf(t)\text{tfidf}(t, d) = \text{tf}(t, d) \cdot \log \frac{N}{\text{df}(t)}

где NN — число документов, df(t)\text{df}(t) — в скольких из них встречается tt. Оценка документа — сумма по терминам запроса. Обе величины лежат прямо в индексе: df\text{df} — длина posting list, tf\text{tf} — число позиций.

У TF-IDF две проблемы. Во-первых, линейный TF: документ, где «кот» повторён 100 раз, получает в 100 раз больше очков — подарок спамерам. Во-вторых, длинные документы выигрывают просто потому, что в них больше слов.

BM25 (Okapi BM25, вероятностная модель Робертсона и Спарк Джонс) чинит обе:

score(q,d)=∑t∈qIDF(t)⋅tf(t,d)⋅(k1+1)tf(t,d)+k1⋅(1−b+b⋅∣d∣avgdl)\text{score}(q, d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{\text{tf}(t, d) \cdot (k_1 + 1)}{\text{tf}(t, d) + k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)}
  • k1k_1 (обычно 1.2) задаёт насыщение TF: при росте tf дробь стремится к k1+1k_1 + 1, а не растёт бесконечно.
  • bb (обычно 0.75) — сила нормализации по длине: ∣d∣|d| — длина документа, avgdl\text{avgdl} — средняя длина. При b=0b = 0 длина не учитывается, при b=1b = 1 — полностью.
  • IDF(t)=ln⁡(1+N−df+0.5df+0.5)\text{IDF}(t) = \ln\left(1 + \frac{N - \text{df} + 0.5}{\text{df} + 0.5}\right) — вариант из Lucene, всегда положительный.

BM25 — модель по умолчанию в Elasticsearch с версии 5.0, до этого там был TF-IDF.

import math def bm25(query, k1=1.2, b=0.75): n = len(doc_len) avgdl = sum(doc_len.values()) / n scores = defaultdict(float) for term in analyze(query): postings = index.get(term, []) df = len(postings) if df == 0: continue idf = math.log(1 + (n - df + 0.5) / (df + 0.5)) for doc_id, positions in postings: tf = len(positions) norm = k1 * (1 - b + b * doc_len[doc_id] / avgdl) scores[doc_id] += idf * tf * (k1 + 1) / (tf + norm) return sorted(scores.items(), key=lambda x: -x[1]) for doc_id, score in bm25("кот мышь"): print(doc_id, round(score, 3)) # 3 1.73 # 1 0.368 # 2 0.368

Документ 3 содержит оба слова, причём «мышь» — редкое и встречается дважды. Документы 1 и 2 совпали только по «кот», который есть в трёх документах из четырёх, поэтому вклад маленький.

Перебирать все документы для подсчёта не нужно: движки считают оценку только для документов из posting lists и держат кучу на KK лучших. Алгоритмы вроде WAND и Block-Max WAND (в Lucene с версии 8) ещё и пропускают документы, которые заведомо не попадут в топ-K, используя верхние границы оценок блоков.

Как индекс живёт на диске: сегменты

Posting lists сжаты и отсортированы, вставлять в середину дорого. Поэтому Lucene устроен как LSM-дерево:

  • Новые документы копятся в памяти, затем сбрасываются в сегмент — маленький неизменяемый инвертированный индекс.
  • Поиск идёт по всем сегментам и объединяет результаты.
  • Удаление не трогает сегмент: документ помечается в битовой маске удалённых. Обновление = удаление + новая версия.
  • Фоновый merge сливает мелкие сегменты в крупные и физически выкидывает удалённые документы.

В Elasticsearch сброс в новый сегмент называется refresh и по умолчанию происходит раз в секунду. Отсюда термин near real-time: документ становится видимым в поиске не сразу после записи, а через ~1 секунду. Надёжность до записи сегмента на диск обеспечивает журнал транзакций (translog) — тот же приём, что WAL в базах данных.

Шардирование: индекс, который не влезает в одну машину

Когда документов миллиарды, индекс режут на части. Два принципиально разных способа:

СпособКак режемЗапросПлюсы и минусы
По документам (document-partitioned)Каждый шард — полный индекс своих документовВо все шарды (scatter-gather)Просто, равномерно, но каждый запрос нагружает все шарды
По терминам (term-partitioned)Шард хранит posting lists части словТолько в шарды с терминами запросаМеньше шардов на запрос, но пересечение через сеть и горячие слова

Почти все реальные системы, включая Elasticsearch, выбирают разбиение по документам. Пересечение списков остаётся локальным, а нагрузку на частые слова равномерно делят все шарды.

Как это устроено в Elasticsearch

  • Индекс состоит из primary-шардов, каждый шард — отдельный индекс Lucene. У каждого primary есть реплики на других узлах. Подробнее о самих подходах — в статье про шардирование и репликацию.
  • Маршрутизация документа: shard = hash(_routing) % number_of_primary_shards, где _routing по умолчанию — id документа. Поэтому число primary-шардов нельзя просто поменять у живого индекса: изменится остаток от деления, и документы «потеряются». Есть API _split и _shrink с жёсткими ограничениями по кратности, а в общем случае — переиндексация. Это прямая противоположность консистентному хешированию, и интервьюер может спросить, почему так: зато маршрутизация тривиальна и не нужна таблица распределения.
  • Поиск идёт в две фазы (query then fetch). Координирующий узел рассылает запрос по одной копии каждого шарда. Фаза query: каждый шард возвращает только (doc_id, score) своих топ-K. Координатор сливает списки и выбирает глобальный топ-K. Фаза fetch: координатор запрашивает полные документы только у тех шардов, чьи документы попали в итог.
import heapq shard_results = [ [(9.1, "a"), (7.4, "b"), (3.0, "c")], [(8.8, "d"), (8.0, "e"), (1.2, "f")], [(9.5, "g"), (2.1, "h"), (0.5, "i")], ] top3 = heapq.nlargest(3, (hit for shard in shard_results for hit in shard)) print(top3) # [(9.5, 'g'), (9.1, 'a'), (8.8, 'd')]

Каждый шард обязан вернуть KK кандидатов, ведь все глобальные лучшие могут лежать в одном шарде. Отсюда проблема глубокой пагинации: страница from=10000, size=10 заставляет каждый из SS шардов отдать 10 010 записей, а координатор сортирует S⋅10010S \cdot 10010. Поэтому Elasticsearch по умолчанию ограничивает from + size значением 10 000 и предлагает search_after — курсорную пагинацию.

Ловушка: локальный IDF

BM25 зависит от NN и df\text{df}, а каждый шард считает их по своим документам. Если слово случайно скопилось в одном шарде, там его IDF ниже, и одинаковые документы получают разные оценки в зависимости от того, куда попали. На больших индексах с равномерной маршрутизацией эффект размывается, а на маленьких тестовых бывает очень заметен: «почему у меня в тесте странный порядок?».

Решение — режим dfs_query_then_fetch: перед основным запросом координатор собирает статистику терминов со всех шардов и считает глобальный IDF. Цена — лишний сетевой раунд, поэтому по умолчанию он выключен.

Сколько шардов делать

Шард — это не бесплатно: у каждого свои сегменты, кеши, файловые дескрипторы и потоки поиска. Тысячи мелких шардов перегружают кластер и метаданные мастера. С версии 7.0 Elasticsearch по умолчанию создаёт 1 primary-шард на индекс (раньше было 5). В документации Elastic ориентиром называют шарды размером от 10 до 50 ГБ. Для логов вместо одного огромного индекса делают индексы по времени (по дню или по объёму, через rollover): старые легко удалить целиком, а запросы по последним часам трогают только свежие индексы.

Как отвечать на собеседовании

Если просят спроектировать поиск, удобная последовательность:

  1. Требования. Объём документов, QPS запросов и записи, нужна ли свежесть за секунды, нужны ли фразы, опечатки, фильтры по полям.
  2. Индексация. Источник правды — основная БД, в поисковый движок данные едут асинхронно через очередь или CDC. Поисковый индекс — производная структура, его можно перестроить.
  3. Анализатор. Токенизация, нижний регистр, стемминг или лемматизация для русского, синонимы. Один и тот же для документов и запросов.
  4. Структура. Term dictionary → posting lists с id, частотами и позициями. Сжатие разностями.
  5. Запрос. Пересечение с самого короткого списка, skip-указатели, BM25, топ-K через кучу.
  6. Масштаб. Шардирование по документам, реплики для чтения и отказоустойчивости, scatter-gather, глобальный IDF при необходимости, ограничение глубокой пагинации.
  7. Оценки. Сделайте прикидку на салфетке: размер индекса обычно 20–50% от исходного текста, нужно ли держать его в RAM.

Типичные ошибки

  • Разные анализаторы при индексации и поиске — поиск молча ничего не находит.
  • Пересечение с самого длинного списка — в разы медленнее, чем с самого редкого термина.
  • Хранить позиции «на всякий случай» — индекс заметно вырастает. Если фразовые запросы не нужны, позиции отключают.
  • Считать поисковый движок основной базой. Elasticsearch — не транзакционное хранилище, refresh даёт задержку видимости, а переиндексация — штатная операция.
  • Много мелких шардов «на вырост» — накладные расходы кластера растут быстрее, чем польза.
  • Глубокая пагинация через from — вместо неё search_after или scroll/point-in-time для выгрузок.

Итог

Инвертированный индекс — это отсортированные списки документов для каждого слова. Всё остальное следует из сортированности: пересечение двумя указателями или прыжками, сжатие разностями, слияние сегментов, топ-K через кучу. Ранжирование BM25 строится на тех же списках: длина списка даёт IDF, число позиций — TF. А масштабирование в Elasticsearch — это много независимых индексов Lucene по документам и координатор, который рассылает запрос и сливает лучшие результаты.

Потренироваться в спокойной обстановке

Все задачи