Как Google оптимизирует хранение и скорость доступа к индексу с помощью кодирования фиксированной ширины (Fixed Width Encoding)

Описание

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

Патент решает фундаментальную инфраструктурную проблему в системах информационного поиска: баланс между скоростью доступа к данным (время декодирования) и объемом занимаемой памяти при хранении инвертированного индекса. Кодирование переменной длины (Variable Length Encoding, VLE) экономит место, но медленно декодируется. Кодирование фиксированной длины (Fixed Width Encoding, FWE) быстрое, но может неэффективно использовать пространство. Патент предлагает оптимизированный вариант FWE.

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

Запатентован метод оптимизированного кодирования фиксированной ширины для списков идентификаторов документов (Posting Lists). Суть изобретения заключается в (1) итеративном поиске оптимальной фиксированной ширины (например, 1, 2, 3 или 4 байта), которая минимизирует общий размер хранения для конкретного списка, и (2) механизме обработки переполнения (overflow handling), позволяющем кодировать большие значения путем их разбиения на несколько записей фиксированной ширины.

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

Система работает следующим образом:

• Генерация Дельт: Список идентификаторов документов (DocIDs) преобразуется в последовательность дельт (разниц между соседними ID).
• Итеративный анализ: Система тестирует различные фиксированные ширины (Width).
• Обработка переполнения: Для каждой ширины проверяется, помещаются ли дельты. Если дельта слишком велика (например, 400 при ширине 1 байт, максимум 255), она разбивается (255 и 145).
• Расчет размера: Вычисляется общий размер (TotalSize) закодированного списка для текущей ширины, учитывая разбиения.
• Оптимизация: Выбирается ширина, дающая наименьший общий размер (MinimumSize).
• Декодирование: При поиске система знает фиксированную ширину и может очень быстро декодировать список (упоминается использование эффективных инструкций SSE2), что ускоряет извлечение результатов.

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

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

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

Влияние на SEO минимальное (1/10). Это чисто инфраструктурный патент, описывающий внутренние механизмы хранения и извлечения данных в индексе Google. Он не описывает факторы ранжирования, сигналы качества или анализ контента. SEO-специалисты не могут повлиять на то, как Google кодирует свои Posting Lists. Значение патента заключается только в понимании технической сложности инфраструктуры Google.

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

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

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

В контексте инвертированного индекса — это список идентификаторов документов (DocIDs), которые содержат определенный термин.

Document Identification Number (DocID) (Идентификатор документа)

Уникальный номер, присваиваемый документу в индексе.

Delta (Дельта)

Разница между последовательными DocIDs в отсортированном списке. Используется для уменьшения величины чисел, подлежащих кодированию.

Fixed Width Encoding (FWE) (Кодирование фиксированной ширины)

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

Variable Length Encoding (VLE) (Кодирование переменной длины)

Схема кодирования, при которой для хранения разных элементов может использоваться разное количество байт.

Width (Ширина)

Фиксированное количество байт, используемое для кодирования элементов в данном списке.

MaximumEntry / Maximum Value (Максимальное значение)

Наибольшее число, которое может быть закодировано при заданной Width. Например, для 1 байта это 255 (2^(8*1) — 1).

Overflow (Переполнение)

Ситуация, когда значение дельты превышает MaximumEntry для текущей ширины.

MinimumSize (Минимальный размер)

Наименьший общий размер закодированного списка, достигнутый в процессе оптимизации ширины.

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

Патент описывает внутренние процессы Google без прямых рекомендаций для SEO. Анализ сфокусирован на понимании инфраструктуры поиска.

Claim 1 (Независимый пункт): Описывает основной механизм обработки списка для одной предопределенной ширины (first predetermined byte number).

1. Получение последовательного списка DocIDs.
2. Генерация последовательности дельт.
3. Для каждой дельты проверка: больше ли она или равна максимальному значению (first maximum value) для этой ширины.
4. Если ДА (переполнение): пересчет дельты как одного или нескольких кратных максимальному значению плюс остаток (remainder value). (Например, если ширина 1 байт (макс. 255), а дельта 400, она пересчитывается как 1 * 255 + 145).
5. Определение общего количества байт (first total number of bytes), необходимого для кодирования всего списка с этой шириной.

Ядром изобретения является шаг 4 – механизм обработки переполнений в рамках фиксированной ширины.

Claim 2 (Зависимый от 1): Расширяет Claim 1, указывая, что процесс повторяется для второй предопределенной ширины (second predetermined byte number) и вычисляется второй общий размер (second total number of bytes).

Claim 3 (Зависимый от 2): Описывает процесс оптимизации и выбора.

1. Сравнение первого и второго общих размеров.
2. Выбор и применение той ширины кодирования (первой или второй), которая привела к меньшему общему размеру.

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

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

INDEXING – Индексирование и извлечение признаков
На этом этапе происходит кодирование данных. Когда система строит или обновляет инвертированный индекс, Encoder Engine применяет описанный алгоритм для сжатия Posting Lists перед сохранением в базе данных (например, Encoder DB).

RANKING – Ранжирование (L1 Retrieval / Отбор кандидатов)
На этом этапе происходит декодирование данных. Decoder Engine использует соответствующий алгоритм декодирования для быстрого восстановления DocIDs из сжатого формата. Скорость декодирования FWE значительно выше, чем у VLE, что критично на этом этапе.

Входные данные (для кодирования):

• Отсортированный последовательный список Document Identification Numbers.

Выходные данные (после кодирования):

• Закодированный (сжатый) Posting List с указанием выбранной оптимальной фиксированной ширины.

На что влияет

Патент влияет исключительно на технические параметры работы поисковой системы:

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

Патент не влияет на конкретные типы контента, тематики (включая YMYL), типы запросов или форматы контента с точки зрения их ранжирования или SEO-оптимизации.

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

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

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

Процесс А: Кодирование (Encoding) и Оптимизация

1. Получение данных и конвертация: Система получает список DocIDs и преобразует его в последовательность дельт.
2. Инициализация: Устанавливаются начальные параметры: текущая ширина (Width) = 1, максимальная ширина (MaximumWidth), например, 4, минимальный размер (MinimumSize) = Бесконечность.
3. Цикл оптимизации (по ширине):
   1. Инициализация расчета размера: Общий размер (TotalSize) = 0.
   2. Расчет параметров: Расчет максимального значения (MaximumEntry = 2^(8*Width)-1).
   3. Цикл по дельтам: Для каждой дельты в последовательности:
      1. Обработка переполнения (Цикл): Пока значение дельты больше или равно MaximumEntry:
         • Записать MaximumEntry в буфер.
         • Вычесть MaximumEntry из дельты.
         • Увеличить TotalSize на Width.
      2. Запись остатка: Записать оставшееся значение дельты в буфер и увеличить TotalSize на Width.
   4. Сравнение и выбор: Если TotalSize меньше MinimumSize:
      1. Обновить MinimumSize = TotalSize.
      2. Запомнить текущую Width как оптимальную.
   5. Инкремент ширины: Увеличить Width на 1. Повторить цикл, если Width меньше или равно MaximumWidth.
4. Вывод результата: Вывод закодированной последовательности, используя оптимальную ширину.

Процесс Б: Декодирование (Decoding)

1. Получение данных: Система получает закодированный список и целевой идентификатор (Integer), который нужно найти или превысить.
2. Извлечение ширины: Из закодированного списка извлекается использованная ширина (Width) (например, из первого байта). Рассчитывается MaximumEntry.
3. Инициализация: Текущее значение (CurrentValue, сумма декодированных дельт) = 0.
4. Цикл декодирования: Пока CurrentValue меньше целевого идентификатора (Integer):
   1. Чтение дельты: Считать следующие Width байт (LastValue).
   2. Обновление суммы: Добавить LastValue к CurrentValue.
   3. Проверка переполнения: Если LastValue равен MaximumEntry:
      • Это означает, что следующая запись является частью той же дельты.
      • Необходимо продолжить чтение и суммирование (повторить шаги a и b), пока не будет считано значение меньше MaximumEntry.
5. Возврат результата: Вернуть итоговое CurrentValue.

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

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

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

• Системные данные: Последовательные списки идентификаторов документов (Document Identification Numbers).

Никакие контентные, технические, ссылочные, поведенческие или иные факторы, имеющие отношение к SEO, в данном патенте не упоминаются и не используются.

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

• Width (Ширина): Предопределенное количество байт (например, 1, 2, 3, 4).
• MaximumEntry (Максимальное значение): Вычисляется по формуле 2^(8 * Width) — 1.
• TotalSize (Общий размер): Сумма байт, необходимая для кодирования всего списка при заданной Width, с учетом дополнительных байт, требуемых для обработки переполнений.
• MinimumSize (Минимальный размер): Минимальное значение TotalSize, найденное среди всех протестированных Width.

Выводы

1. Патент чисто инфраструктурный. Он не дает практических выводов для SEO-специалистов относительно стратегий продвижения, контента или ссылочного профиля.
2. Фокус на балансе Скорость/Память. Патент демонстрирует, как Google решает задачу оптимизации хранения инвертированного индекса, стремясь к скорости декодирования FWE при сохранении эффективности использования памяти, близкой к VLE.
3. Ключевая инновация – обработка переполнений в FWE. Механизм разбиения больших дельт (overflow handling) на несколько записей фиксированной ширины является центральным элементом, который делает этот подход жизнеспособным.
4. Адаптивный выбор ширины. Система не использует единую ширину для всего индекса, а выбирает оптимальную ширину (например, 1 или 4 байта) для каждого конкретного Posting List на основе статистического распределения дельт в нем.
5. Понимание производительности Google. Быстрое извлечение кандидатов (Retrieval) позволяет использовать более сложные и ресурсоемкие алгоритмы на последующих этапах ранжирования (L2/L3 Ranking).

Практика

ВАЖНО: Патент является инфраструктурным и не дает практических выводов для SEO.

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

Практических рекомендаций для SEO (технических, контентных или ссылочных), основанных на механизмах этого патента, нет.

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

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

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

Стратегическое значение для SEO отсутствует. Патент имеет значение для инженеров поисковых систем, так как описывает эффективный метод оптимизации индекса. Для SEO-специалистов он представляет только академический интерес, помогая лучше понять устройство инфраструктуры Google и то, как она обеспечивает скорость и масштабируемость.

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

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

Сценарий: Кодирование списка DocID

1. Исходный список DocID: (10, 15, 400, 450)
2. Последовательность дельт: (10, 5, 385, 50)
3. Анализ (Ширина = 1 байт): MaximumEntry = 255.
   • 10 (1 байт)
   • 5 (1 байт)
   • 385 (Переполнение): Кодируется как (255, 130) (2 байта)
   • 50 (1 байт)

   TotalSize (1-byte) = 5 байт.

4. Анализ (Ширина = 2 байта): MaximumEntry = 65535.
   • 10 (2 байта)
   • 5 (2 байта)
   • 385 (2 байта)
   • 50 (2 байта)

   TotalSize (2-byte) = 8 байт.

5. Выбор: 1-байтное кодирование более эффективно (5 байт < 8 байт).
6. Результат (Закодированный список): (10, 5, 255, 130, 50) с указанием, что используется ширина 1 байт.

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