Как Google распределяет запросы между серверами для оптимизации кэширования и повышения безопасности

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

Back-end server (Бэкенд-сервер)

Сервер, который выполняет основную обработку запроса — поиск в индексе или базе данных (Datastore), вычисление результатов и их кэширование.

Cache (Кэш)

Временное хранилище на бэкенд-сервере, где сохраняются результаты для конкретных запросов. Позволяет быстро отвечать на повторяющиеся запросы без повторного вычисления.

Front-end server (Фронтенд-сервер)

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

Hash collision (Хеш-коллизия)

Ситуация, когда разные входные данные (в данном случае, разные запросы) приводят к одному и тому же хеш-значению.

Hash table (Хеш-таблица)

Структура данных, которая связывает хеш-значения (индексы) с записями (в данном случае, с идентификаторами бэкенд-серверов).

Hash value (Хеш-значение / Индекс)

Результат операции хеширования. Используется как индекс для выбора сервера в хеш-таблице.

Hashing operation (Операция хеширования)

Процесс преобразования входных данных (комбинации запроса и временного семени) в хеш-значение.

Present time interval (Текущий временной интервал)

Период времени, в течение которого параметры хеширования (Random Seed) остаются постоянными. Длина этого интервала может быть фиксированной или случайной.

Query Number (Числовое представление запроса)

Результат конвертации текста запроса в числовой формат (например, ASCII, Unicode), пригодный для хеширования.

Random seed (Случайное семя)

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

Second number / Time-dependent number (Второе число / Число, зависящее от времени)

Общий термин для числа, которое комбинируется с запросом при хешировании. Может быть детерминированным (на основе временной метки time-stamp) или случайным (Random Seed).

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

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

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

1. Определение длины текущего временного интервала на основе вывода первого генератора случайных чисел.
2. Определение случайного семени (random seed) для текущего временного интервала на основе вывода второго генератора случайных чисел.
3. Конвертация запроса в query number.
4. Выполнение операции хеширования над комбинацией query number и random seed для генерации hash value.
5. Выбор сервера из множества серверов на основе hash value.
6. Отправка запроса на выбранный сервер.
7. Повторное определение длины временного интервала (с новым случайным значением) и повторное определение random seed (с новым случайным значением) по истечении текущего временного интервала.

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

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

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

Этапы поиска:

Система не относится напрямую к этапам CRAWLING или INDEXING.

Она функционирует как механизм диспетчеризации перед этапами QUNDERSTANDING и RANKING. Front-end server использует описанный механизм, чтобы определить, какой именно back-end server будет выполнять работу по пониманию запроса, отбору кандидатов и ранжированию.

Взаимодействие компонентов:

• Фронтенд-серверы: Принимают запрос, генерируют (или получают) параметры временного интервала и random seed, выполняют хеширование и маршрутизируют запрос.
• Бэкенд-серверы: Принимают маршрутизированный запрос, проверяют локальный кэш, вычисляют результат (если его нет в кэше) и возвращают ответ.

Входные данные:

• Текст входящего запроса.
• Параметры текущего временного интервала (длина и Random Seed), сгенерированные случайным образом.
• (В альтернативном варианте): Текущая временная метка (timestamp) и количество бэкенд-серверов.

Выходные данные:

• Идентификатор бэкенд-сервера, выбранного для обработки запроса.

На что влияет

Это универсальный механизм маршрутизации инфраструктуры.

• Типы контента, запросы, ниши, языки: Влияет на обработку абсолютно всех запросов равномерно. Механизм не анализирует содержание запроса или его тематику для принятия решения о маршрутизации; он использует запрос только как входные данные для хеш-функции.

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

• Условия работы: Алгоритм выбора сервера применяется при получении каждого запроса фронтенд-сервером.
• Триггеры активации: Изменение маршрутизации активируется по истечении текущего временного интервала. Поскольку длина интервала случайна (согласно Claim 1), время изменения маршрутизации непредсказуемо.

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

Описание процесса на основе рандомизированного подхода (Claim 1).

1. Инициализация Интервала: Система определяет длину для нового временного интервала, используя генератор случайных чисел.
2. Инициализация Семени: Система определяет случайное семя (Random Seed) для этого интервала, используя другой (или тот же) генератор случайных чисел.
3. Получение Запроса: Фронтенд-сервер получает входящий запрос.
4. Конвертация: Запрос конвертируется в числовое представление (Query Number). Например, путем преобразования текста в ASCII или Unicode.
5. Хеширование: Выполняется операция хеширования над комбинацией (например, суммой или конкатенацией) Query Number и текущего Random Seed.
6. Выбор Сервера: Результат хеширования (Hash Value) используется как индекс в хеш-таблице для выбора конкретного бэкенд-сервера. Может применяться операция взятия остатка от деления на количество доступных серверов.
7. Маршрутизация: Запрос отправляется на выбранный бэкенд-сервер.
8. Обработка (на бэкенде): Бэкенд-сервер проверяет локальный кэш на наличие готового результата для этого запроса.
   • Если есть: Возвращает кэшированный результат.
   • Если нет: Вычисляет результат (обращается к индексу/базе данных), кэширует его для будущих запросов в этом интервале и возвращает его.
9. Проверка Истечения: Система проверяет, истек ли текущий временной интервал.
   • Если ДА: Процесс возвращается к Шагу 1 (генерация новых случайных параметров).
   • Если НЕТ: Система ожидает следующий запрос и использует текущие параметры (возврат к Шагу 3).

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

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

Патент фокусируется исключительно на инфраструктурной маршрутизации и не использует стандартные SEO-факторы.

• Контентные, Технические, Ссылочные, Поведенческие факторы: Не используются в описанном механизме.
• Временные факторы: Время используется для определения моментов смены временных интервалов. В рандомизированном варианте используются случайные числа, которые меняются с течением времени (Random Seed). В детерминированном варианте используется непосредственно временная метка (timestamp).
• Данные запроса: Текст запроса является основным входным параметром для хеширования.

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

• Query Number: Числовое представление запроса. Рассчитывается путем конвертации текста.
• Random Seed: Случайное число, уникальное для временного интервала. Генерируется случайным образом.
• Hash Value: Результат хеширования. Рассчитывается как Hash(Query Number + Random Seed).
• Server ID: Идентификатор сервера. Может рассчитываться как Hash Value % Number_of_Servers (операция взятия остатка от деления).

Альтернативный детерминированный метод (описан в патенте, но не в Claim 1):

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

• Quantize_time (Квантованное время) (Eq. 1):