Как Яндекс оптимизирует хранение и скорость чтения обратного индекса с помощью таблиц шаблонов кодирования

Описание

Какую задачу решает

Патент решает критическую инфраструктурную задачу: достижение оптимального баланса между плотностью сжатия (compression density) и скоростью декомпрессии (decompression speed) инвертированного индекса (Inverted Index). Цель — минимизировать объем оперативной памяти (RAM), занимаемый индексом, и одновременно ускорить чтение списков документов (Posting Lists) во время поиска. Патент устраняет неэффективность существующих методов сжатия (PFor, ParaPFor) при работе на стандартных серверных архитектурах, особенно на процессорах с SIMD-расширениями (например, SSE на x86).

Что запатентовано

Запатентована система индексации и поиска, использующая новый подход к сжатию Posting Lists. Суть изобретения заключается в отказе от хранения параметров сжатия (базовая длина, данные о патчах) непосредственно в заголовке каждого блока данных. Вместо этого используется короткий указатель (Pointer) на запись в предопределенной таблице шаблонов кодирования (Encoding Pattern Table).

Как это работает

Инвертированный индекс делится на блоки фиксированного размера. Для каждого блока определяется оптимальный шаблон сжатия на основе значений ID документов (часто в формате Delta Encoding). Система находит этот шаблон в предопределенной таблице и записывает в заголовок блока только указатель на эту запись. Во время поиска система использует этот указатель для мгновенного вызова специализированной, высокооптимизированной процедуры декодирования (Decoding Routine), соответствующей данному шаблону. Это ускоряет распаковку, особенно при использовании параллельных вычислений (SIMD).

Актуальность для SEO

Высокая (с точки зрения инфраструктуры). Эффективное хранение и максимально быстрый доступ к инвертированному индексу являются фундаментальными требованиями для любой крупной поисковой системы. Оптимизация производительности с использованием SIMD-инструкций остается стандартом для обеспечения высокой скорости поиска.

Важность для SEO

Минимальное влияние (1/10). Это чисто инфраструктурный патент, описывающий внутренние механизмы компрессии и хранения данных в инвертированном индексе Яндекса. Он не влияет на факторы ранжирования, оценку качества контента, ссылочный профиль или поведенческие метрики. Его влияние ограничивается скоростью, с которой Яндекс может обработать запрос на самых ранних этапах (Retrieval).

Детальный разбор

Термины и определения

Inverted Index (Инвертированный индекс)

Основная структура данных поисковой системы. Представляет собой словарь терминов, где для каждого термина хранится список документов, в которых он встречается.

Posting List (Список документов, Постинг-лист)

Список идентификаторов (ID) документов, соответствующих определенному термину в инвертированном индексе.

Block (Блок)

Сегмент Posting List фиксированной длины M (например, M=8 элементов), который сжимается как единое целое.

Delta Encoding (Дельта-кодирование)

Метод сжатия. Вместо хранения полных значений ID документов хранятся только разницы (дельты) между соседними значениями в отсортированном списке.

PFor (Patched Frame of Reference)

Класс алгоритмов сжатия. Основан на выборе базовой длины (b) в битах для кодирования большинства элементов и отдельной обработке исключений (Patches).

Patches (Патчи/Исключения)

Элементы блока, значения которых слишком велики для кодирования базовой длиной (b). Характеризуются количеством (n), позициями (p) и значениями (v).

SIMD (Single Instruction, Multiple Data)

Принцип параллельных вычислений, позволяющий процессору выполнять одну и ту же операцию одновременно над несколькими элементами данных (например, SSE на x86). Используется для ускорения декомпрессии.

Encoding Pattern (Шаблон кодирования)

Конкретная конфигурация параметров сжатия для блока (b, n, p, v).

Encoding Pattern Table (Таблица шаблонов кодирования)

Предопределенная таблица, хранящая наиболее часто используемые шаблоны кодирования.

Pointer (Указатель)

Индекс (например, 8-битное число), хранящийся в заголовке сжатого блока и указывающий на соответствующую запись в Encoding Pattern Table.

Decoding Routine (Процедура декодирования)

Специализированный фрагмент кода, оптимизированный для декомпрессии блока, сжатого с использованием определенного шаблона.

Skip Routine (Процедура пропуска)

Фрагмент кода, позволяющий быстро определить длину сжатого блока и перейти к следующему, не выполняя полную декомпрессию.

Ключевые утверждения (Анализ Claims)

Патент защищает метод доступа к сжатым данным, основанный на использовании указателей на предопределенные протоколы, что отличает его от предшествующих методов PFor.

Claim 1 (Независимый пункт): Описывает метод поиска документов (процесс декодирования индекса во время запроса).

1. Система получает поисковый термин, связанный с Posting List. Этот список организован в виде сжатых блоков, каждый закодирован с использованием Encoding Pattern.
2. Считывается указатель (Pointer) из заголовка текущего блока.
3. Этот указатель используется для извлечения протокола декодирования (Decoding Protocol) из таблицы протоколов декодирования.
4. Этот протокол определяет шаблон кодирования, использованный для сжатия данного блока.

Ядром изобретения является использование косвенной адресации через таблицу протоколов. Декомпрессия управляется не параметрами, записанными в блоке (как в стандартном PFor), а указателем на предопределенный протокол или процедуру.

Claim 13 (Зависимый пункт): Определяет составные части Encoding Pattern.

• Базовая длина (b) в битах.
• Количество патчей (n).
• Если n > 0: значения патчей (v) и позиции патчей (p) в блоке.

Claim 16 (Зависимый пункт): Описывает механизм декомпрессии на основе шаблона.

1. Считываются $b \cdot M$ бит, содержащие M усеченных ссылок (Truncated References).
2. Если n > 0, для каждого патча k:
   • Вычисляется расширенное значение патча как $v_k \cdot 2^b$ (по сути, сдвиг значения патча на b бит влево).
   • Это расширенное значение добавляется к соответствующей усеченной ссылке в позиции $p_k$.

Claim 22 (Зависимый пункт): Описывает оптимизацию декомпрессии, подходящую для SIMD.

1. Определяются 2 массива (например, в SIMD-регистрах).
2. Первый массив заполняется усеченными ссылками из блока.
3. Второй массив (массив патчей) инициализируется нулями, затем в него вставляются расширенные значения патчей в соответствующие позиции.
4. Выполняется поэлементное сложение первого и второго массивов. Эта операция может быть выполнена параллельно с помощью одной SIMD-инструкции.

Где и как применяется

Изобретение применяется на фундаментальных уровнях инфраструктуры поиска.

INDEXING – Индексирование и извлечение признаков
На этапе построения или обновления Инвертированного Индекса. Когда система формирует Posting Lists, эти списки сжимаются с использованием описанного метода для эффективного хранения. Процесс включает анализ блоков данных, выбор оптимального Encoding Pattern из таблицы и запись сжатого блока с указателем на этот шаблон.

RANKING – Ранжирование (Уровень L1 — Base Search / Retrieval)
Основное применение происходит на самом первом этапе ранжирования — поиске кандидатов (Retrieval). Когда поступает запрос, системе необходимо максимально быстро получить Posting Lists для терминов запроса. Быстрая декомпрессия этих списков с использованием описанных Decoding Routines и SIMD-оптимизаций критически важна для скорости всего процесса поиска.

На что влияет

Патент имеет исключительно инфраструктурное влияние:

• Скорость поиска: Ускоряет этап извлечения кандидатов (Retrieval).
• Использование памяти: Уменьшает объем RAM, необходимый для хранения инвертированного индекса.

Патент НЕ влияет на конкретные типы контента, запросы, форматы, ниши, факторы ранжирования или оценку релевантности. Это универсальный механизм хранения индекса.

Когда применяется

• При индексации: Каждый раз, когда обновляется или создается инвертированный индекс.
• При поиске: При обработке практически каждого поискового запроса, когда системе требуется доступ к Posting Lists.

Пошаговый алгоритм

Процесс А: Индексация (Сжатие Posting List)

1. Подготовка данных: Получение Posting List (списка Document ID). Сортировка и применение Delta Encoding (преобразование в последовательность разниц). В патенте упоминается возможность хранения (Дельта — 1) для экономии еще одного бита.
2. Разбиение на блоки: Последовательность дельт делится на блоки фиксированного размера M (например, M=8).
3. Определение шаблона (для каждого блока): Анализ значений в блоке для выбора оптимальных параметров сжатия: базовой длины (b) и идентификации исключений (n, p, v).
4. Поиск в таблице: Найденная комбинация параметров (b, n, p, v) ищется в предопределенной Encoding Pattern Table.
5. Кодирование блока:
   • Формируется заголовок блока, содержащий только указатель (Pointer) на найденную запись в таблице шаблонов.
   • Данные блока усекаются до длины b (Truncated References) и записываются после заголовка.

Процесс Б: Поиск (Декомпрессия Posting List)

1. Чтение заголовка: Считывание указателя (Pointer) из заголовка текущего блока.
2. Выбор процедуры: Использование указателя для доступа к таблице процедур декодирования (Decoding Routines Table) и выбора соответствующей процедуры (Decoding Routine X) и процедуры пропуска (Skip Routine X).
3. Декомпрессия (SIMD-оптимизированная): Выполнение процедуры X.
   • Распаковка усеченных данных из блока в массив (регистр).
   • Применение предопределенного массива патчей (специфичного для процедуры X).
   • Сложение массива усеченных данных и массива патчей для восстановления исходных дельт (параллельная операция).
4. Восстановление ID: Преобразование дельт обратно в абсолютные Document ID.
5. Переход к следующему блоку: Выполнение Skip Routine X для определения длины текущего блока и перехода к заголовку следующего.

Какие данные и как использует

Данные на входе

Система использует только один тип данных:

• Системные данные (Идентификаторы документов): Целочисленные идентификаторы (Document IDs), составляющие инвертированный индекс.

Патент не использует контентные, технические, ссылочные, поведенческие, временные, структурные, мультимедиа, географические или пользовательские факторы.

Какие метрики используются и как они считаются

Метрики связаны исключительно с параметрами сжатия:

• b (Base length): Базовая длина в битах.
• n (Number of patches): Количество элементов в блоке, длина которых превышает b бит (значение $\geq 2^b$).
• p (Patch positions): Позиции исключений внутри блока.
• v (Patch values): Значения старших бит исключений.
• Expanded Patch Value: Рассчитывается как $v \cdot 2^b$ во время декомпрессии.

Используются базовые математические и битовые операции (вычитание, сдвиги, маскирование, сложение).

Выводы

1. Инфраструктурный фокус: Патент описывает исключительно внутренние механизмы хранения и доступа к данным Яндекса. Он не имеет отношения к алгоритмам ранжирования или оценке качества контента.
2. Ключевая инновация — Таблицы вместо метаданных: Основное улучшение по сравнению с предыдущими методами (PFor/ParaPFor) — это перенос метаданных о сжатии из заголовков блоков в предопределенные глобальные таблицы (Encoding Pattern Tables). Это экономит память и ускоряет декодирование за счет использования указателей.
3. Оптимизация производительности и Аппаратная адаптация: Метод демонстрирует глубокий уровень инженерной оптимизации, направленный на максимизацию скорости ответа системы, и специально разработан для эффективного использования возможностей современных процессоров (SIMD).
4. Отсутствие прямых SEO-выводов: Для SEO-специалистов этот патент не предоставляет никаких практических рекомендаций по оптимизации сайтов, контента или ссылочного профиля.

Практика

Патент является инфраструктурным и не дает практических выводов для SEO.

Best practices (это мы делаем)

В патенте нет информации для формирования лучших практик SEO.

Worst practices (это делать не надо)

В патенте нет информации о том, какие SEO-тактики он делает неэффективными или опасными. Он не направлен против каких-либо манипуляций.

Стратегическое значение

Стратегическое значение для SEO косвенное. Патент демонстрирует фокус Яндекса на скорости и эффективности использования аппаратных ресурсов. Быстрая работа инвертированного индекса (ускоренная данным методом на этапе L1 Retrieval) позволяет высвободить процессорное время на этапе ответа на запрос. Это, в свою очередь, позволяет Яндексу применять более сложные и ресурсоемкие модели машинного обучения (например, трансформеры YATI) на последующих этапах ранжирования (L3/L4), не жертвуя общей скоростью поиска.

Практические примеры

Практических примеров применения в SEO нет, так как патент описывает низкоуровневое сжатие данных в индексе.

Вопросы и ответы