Как Google масштабирует расчет кратчайших путей в графе ссылок от авторитетных сайтов («Seed Nodes»)

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

Adaptive Propagation Threshold (Адаптивный порог распространения)

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

Checkpoint (Контрольная точка)

Файл, сохраняемый shard server в надежном хранилище (например, GFS). Представляет собой инкрементальный снимок состояния вычислений (изменения в Distance Table и Leaf Table) на определенный момент времени. Используется для восстановления состояния сервера после сбоя.

Dirty Bit («Грязный» бит)

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

Distance Table (Таблица расстояний)

Структура данных, хранящаяся в оперативной памяти shard server. Для каждого узла в шарде она содержит n пар (Seed Node, расстояние), представляющих текущую лучшую информацию о n ближайших Seed Nodes и расстояниях до них.

GFS (Google File System)

Распределенная глобальная файловая система, используемая для хранения исходного графа ссылок и checkpoints.

Leaf Table (Таблица листьев)

Структура данных, аналогичная Distance Table, но предназначенная для «листьев» — узлов без исходящих ссылок (или узлов, чьи исходящие ссылки неизвестны системе). Поскольку листья не распространяют обновления, для них не нужно хранить Dirty Bit. Может храниться частично в RAM и частично на диске.

Link Table (Таблица ссылок)

Структура данных, хранящаяся на диске shard server. Представляет собой часть графа ссылок, назначенную данному шарду. Содержит информацию об исходящих ссылках для каждого узла.

Seed Node (Начальный узел, «Семя»)

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

Shard (Шард, Сегмент)

Часть графа веб-ссылок, назначенная одному серверу для обработки.

Shard Server (Сервер шарда)

Сервер, отвечающий за обработку назначенного ему шарда, хранение соответствующих Link Table, Distance Table и Leaf Table, а также за обмен обновлениями с другими серверами.

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

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

Claim 1 (Независимый пункт, Система): Описывает основную архитектуру системы.

1. Система состоит из множества серверов.
2. Направленный граф (веб-ресурсы и ссылки) делится на шарды. Каждый шард представляет собой часть графа.
3. Каждый шард назначается соответствующему серверу. Сервер получает данные, описывающие ссылки для ресурсов в этом шарде (Link Table).
4. Таблица расстояний (Distance Table) рассчитывается параллельно для каждого ресурса в каждом шарде с использованием вычисления ближайшего Seed Node (nearest seed computation) на сервере, которому назначен шард, с использованием данных о ссылках.

Claim 9 (Независимый пункт, Метод): Описывает метод, соответствующий системе в Claim 1.

1. Разделение направленного графа на шарды.
2. Назначение каждого шарда и соответствующих данных о ссылках соответствующему серверу.
3. Параллельное вычисление Distance Table для ресурсов в каждом шарде с помощью nearest seed computation на назначенном сервере.

Claim 4 и 12 (Зависимые): Детализируют процесс вычисления Distance Table.

Вычисление включает определение n ближайших Seed Nodes к узлу, представляющему веб-ресурс, и соответствующих расстояний от узла до каждого из этих n ближайших Seed Nodes. n — это заранее определенное небольшое положительное целое число (например, в Claim 5 и 13 указано, что n может быть равно трем). Данные, идентифицирующие n ближайших Seed Nodes и расстояния, сохраняются в Distance Table.

Claim 8 и 16 (Зависимые): Детализируют механизм параллельного вычисления.

На каждом сервере генерируется начальная Distance Table. Затем сервер получает от других серверов данные о расстояниях от Seed Nodes до ресурсов в своем шарде. Начальная Distance Table обновляется с использованием этих полученных данных.

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

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

INDEXING – Индексирование и извлечение признаков
Основное применение патента. Система используется для анализа графа ссылок и вычисления статических (не зависящих от запроса) сигналов авторитетности или качества, основанных на структуре графа.

1. Анализ ссылок: Система обрабатывает весь граф веб-ссылок (полученный на этапе CRAWLING).
2. Вычисление признаков (Feature Extraction): Основная задача — вычислить расстояние от каждого узла до ближайших Seed Nodes. Эти расстояния затем могут использоваться как признаки (сигналы) качества или авторитетности для этапа RANKING (как указано в Claim 2).

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

• Система состоит из Мастер-сервера (Master Server) и множества Shard Servers.
• Shard Servers взаимодействуют друг с другом для обмена обновлениями расстояний (distance updates).
• Все серверы взаимодействуют с распределенной файловой системой (GFS) для чтения исходного графа и записи/чтения checkpoints.

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

• Направленный граф веб-ссылок (может быть взвешенным).
• Список идентификаторов Seed Nodes.

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

• Объединенная таблица расстояний (Merged Distance Table) — фактически или виртуально объединенные Distance Tables и Leaf Tables всех шардов. Для каждого узла в графе эта таблица содержит идентификаторы n ближайших Seed Nodes и расстояния до них.

Ключевые технические особенности:

• Масштабируемость: Способность обрабатывать графы с триллионами ребер за счет шардинга и распределения данных на дисках.
• Отказоустойчивость: Асинхронное инкрементальное создание checkpoints и механизм восстановления после сбоев без необходимости перезапуска всего вычисления.
• Оптимизация производительности: Использование Adaptive Propagation Threshold для управления сетевым трафиком и техники оптимизации дискового ввода/вывода для доступа к Link Table.

На что влияет

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

• Все типы контента и ниши: Влияет на расчет авторитетности страниц и сайтов в любой тематике. Особенно важно в конкурентных и YMYL-тематиках, где сигналы доверия и авторитетности критичны.
• Взвешенные ссылки: Система поддерживает взвешенные графы, что означает, что не все ссылки могут иметь одинаковый вес при расчете расстояний (как указано в описании, система может работать с weighted directed graph).

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

• Условия применения: Применяется, когда необходимо рассчитать метрики на основе графа ссылок для всего индекса.
• Частота применения: Это пакетный (batch) процесс, который запускается периодически для обновления ссылочных метрик по мере изменения веб-графа (появления новых ссылок, удаления старых, изменения весов).

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

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

Этап 1: Инициализация и Подготовка

1. Шардинг графа: Исходный граф ссылок делится на шарды (например, с помощью хеширования идентификаторов узлов или с учетом доменной информации).
2. Распределение данных: Каждый Shard Server копирует свою часть графа (Link Table) из GFS на локальные диски. Данные реплицируются на несколько дисков для отказоустойчивости и балансировки нагрузки.
3. Инициализация таблиц: Каждый сервер создает в оперативной памяти Distance Table и Leaf Table для своих узлов.
4. Обработка Seed Nodes: Серверы читают список Seed Nodes. Для Seed Nodes, находящихся в их шарде, они инициализируют расстояния (возможно, с учетом веса Seed Node) и помечают их как dirty для начала распространения.

Этап 2: Итеративное вычисление и распространение (Параллельный процесс на каждом сервере)

1. Сканирование и Поиск: Рабочие потоки сканируют Distance Table в поисках «грязных» записей (dirty entries), которые удовлетворяют текущему Adaptive Propagation Threshold (т.е. расстояние достаточно мало для распространения).
2. Доступ к Link Table: Для найденных «грязных» узлов система выполняет поиск в Link Table (на диске), чтобы определить исходящие ссылки и целевые узлы.
3. Генерация обновлений: Для каждого целевого узла рассчитывается новое расстояние до Seed Node (расстояние до текущего узла + вес ссылки).
4. Отправка обновлений: Обновления (идентификатор целевого узла, идентификатор Seed Node, новое расстояние) отправляются на серверы, владеющие целевыми узлами. После отправки запись в Distance Table помечается как «чистая» (clean).
5. Получение обновлений: Сервер получает обновления от других серверов.
6. Обработка обновлений: Сервер проверяет, является ли полученное расстояние более коротким, чем текущее известное расстояние до данного Seed Node в Distance Table или Leaf Table.
   • Если ДА: Таблица обновляется новым расстоянием, и запись помечается как dirty (для Distance Table).
   • Если НЕТ: Обновление игнорируется.
7. Адаптация порога: Сервер динамически корректирует Adaptive Propagation Threshold для поддержания заданной частоты распространения обновлений.

Этап 3: Отказоустойчивость и Контрольные точки

1. Создание Checkpoints: Периодически или при низкой активности каждый сервер асинхронно сохраняет инкрементальные checkpoints (изменения в Distance Table и Leaf Table с момента последнего сохранения) в GFS.
2. Восстановление после сбоя: В случае сбоя сервер перезапускается, загружает свое состояние из последних валидных checkpoints и отправляет «Hello» сообщения другим серверам с временной меткой последней контрольной точки.
3. Отправка пропущенных обновлений: Другие серверы отправляют восстановленному серверу все обновления, которые были подтверждены им после указанной временной метки.

Этап 4: Завершение вычисления

1. Мониторинг состояния: Мастер-сервер отслеживает состояние всех Shard Servers (количество принятых обновлений, наличие «грязных» записей).
2. Определение завершения: Когда состояние всех серверов стабилизируется (нет новых обновлений и «грязных» записей), мастер-сервер инициирует завершение (используя протокол, аналогичный двухфазной фиксации, для обработки состояний гонки).
3. Финальная запись: Серверы записывают финальные checkpoints.
4. Объединение результатов: Все checkpoints и файлы листьев объединяются (фактически или виртуально) для формирования итоговой Merged Distance Table.

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

Патент фокусируется исключительно на инфраструктуре для обработки графовых данных.

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

• Ссылочные факторы: Ключевые данные. Используется топология графа (кто на кого ссылается). Система поддерживает взвешенные графы (weighted digraph), что подразумевает использование весов ссылок (weights assigned to the edges) при расчете расстояний.
• Системные данные: Список предопределенных Seed Nodes. Идентификаторы ресурсов (URL clusters), где кластеры URL, ведущих на одну страницу, обрабатываются как один узел.

В патенте не упоминается использование контентных, технических, поведенческих, временных или других факторов для расчета расстояний, хотя они могут использоваться для определения весов ссылок или выбора Seed Nodes на предварительном этапе.

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

• Shortest Path Distance (Расстояние кратчайшего пути): Основная вычисляемая метрика. Рассчитывается как сумма весов ребер на пути от Seed Node до целевого узла.
• N Nearest Seeds (N ближайших Seed Nodes): Для каждого узла система идентифицирует n (например, 3) Seed Nodes с наименьшим Shortest Path Distance.
• Propagation Ratio (Частота распространения): Внутренняя метрика системы, используемая для динамической настройки Adaptive Propagation Threshold (например, поддержание частоты на уровне 1 из 6 обновлений).

1. Инфраструктура для алгоритмов типа TrustRank: Патент не описывает алгоритмы ранжирования, но предоставляет необходимую масштабируемую и отказоустойчивую инфраструктуру для их работы. Он подтверждает способность Google выполнять сложные вычисления на графе ссылок, такие как определение близости к авторитетным источникам (Seed Nodes), в масштабах всего веба.
2. Критичность Seed Nodes: Система построена вокруг концепции Seed Nodes — заранее отобранных авторитетных сайтов. Расчеты фокусируются на том, насколько короток путь от этих сайтов до всех остальных ресурсов в интернете.
3. Поддержка взвешенных графов: Система может работать с взвешенными направленными графами. Это означает, что при расчете расстояний учитывается не только количество кликов (ссылок), но и вес каждой ссылки. Не все ссылки вносят одинаковый вклад в расстояние.
4. Масштаб и сложность анализа ссылок: Патент подчеркивает огромные вычислительные ресурсы, которые Google вкладывает в анализ ссылочного графа. Система спроектирована для работы с триллионами ребер и тысячами серверов, что указывает на критическую важность ссылочных сигналов для поиска.
5. Эффективность и оптимизация: Google активно оптимизирует процесс вычислений с помощью таких техник, как Adaptive Propagation Threshold, чтобы сделать анализ графа быстрым и ресурсоэффективным, позволяя чаще обновлять ссылочные метрики.

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

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

• Фокус на качестве ссылок и близости к Seed Nodes: Необходимо стремиться к получению ссылок с сайтов, которые сами находятся на коротком расстоянии от авторитетных Seed Nodes. Качество ссылочного окружения (link neighborhood) имеет решающее значение.
• Построение авторитетности (E-E-A-T): Работайте над тем, чтобы ваш сайт сам мог рассматриваться как потенциальный Seed Node или ресурс, близкий к ним. Это достигается за счет высокого качества контента, экспертности и сильных сигналов доверия.
• Анализ ссылочного профиля конкурентов: Анализируйте, из каких авторитетных источников (потенциальных Seed Nodes или близких к ним) получают ссылки конкуренты. Это помогает определить ключевые источники авторитетности в нише.
• Приоритезация ссылок с высоким весом: Поскольку система поддерживает взвешенные графы, следует фокусироваться на получении ссылок, которые с высокой вероятностью имеют большой вес (например, релевантные, видимые ссылки с авторитетных страниц).

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

• Массовая закупка низкокачественных ссылок: Построение ссылочного профиля на основе сайтов, находящихся «далеко» от Seed Nodes (спам, PBN низкого качества, ссылочные биржи), неэффективно. Описанная система позволяет Google точно рассчитать это расстояние для каждого сайта.
• Игнорирование веса ссылок: Предположение, что все ссылки одинаковы. Система учитывает веса, поэтому ссылки, которые могут быть классифицированы как низкокачественные или нерелевантные, могут иметь минимальный вес или увеличивать расстояние (если вес интерпретируется как стоимость).
• Изоляция от авторитетных ресурсов: Создание контента, который не привлекает естественных ссылок из авторитетного ссылочного окружения, приводит к увеличению расстояния до Seed Nodes.

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

Этот патент имеет важное стратегическое значение, так как он описывает движок, который позволяет Google анализировать доверие и авторитетность в масштабах всего интернета. Он подтверждает, что модель распространения авторитетности от набора доверенных сайтов (Seed Nodes) является важной частью инфраструктуры Google. Для долгосрочной SEO-стратегии это означает, что построение качественного ссылочного профиля, основанного на связях с авторитетными и релевантными источниками, является фундаментальным требованием.

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

Сценарий: Оценка качества донора ссылки с использованием концепции Seed Nodes

1. Идентификация потенциальных Seed Nodes в нише: Определите самые авторитетные и доверенные ресурсы в вашей тематике (например, ведущие университеты, государственные организации, главные новостные издания, общепризнанные экспертные сайты).
2. Анализ донора: Оцените ссылочный профиль потенциального донора ссылки. Получает ли он прямые ссылки от идентифицированных Seed Nodes? Если нет, получает ли он ссылки от сайтов, которые ссылаются на Seed Nodes (расстояние 2)?
3. Принятие решения: Приоритезируйте получение ссылки с донора, который имеет более короткий путь к Seed Nodes. Например, ссылка с локального новостного сайта, на который ссылается крупное федеральное издание (потенциальный Seed Node), будет значительно ценнее, чем ссылка с форума, который находится в 5-6 кликах от любого авторитетного ресурса. Описанная в патенте система позволяет Google рассчитать эти расстояния точно и эффективно.