Анатомия крупномасштабного гипертекстового поискового движка | Сергей Брин, Лоуренс Пейдж

Сергей Брин и Лоуренс Пейдж

Отдел компьютерных наук, Стэнфордский университет, Стэнфорд, Калифорния 94305, США

sergey@cs.stanford.edu и page@cs.stanford.edu

Аннотация

В этой статье мы представляем Google, прототип крупномасштабной поисковой системы, которая интенсивно использует структуру, присутствующую в гипертексте. Google предназначен для эффективного сканирования и индексации в Интернете, а также для получения гораздо более удовлетворительных результатов поиска, чем существующие системы. Прототип с полнотекстовой базой данных и гиперссылками объемом не менее 24 миллионов страниц доступен по адресу http://google.stanford.edu/

Создание поисковой системы — сложная задача. Поисковые системы индексируют от десятков до сотен миллионов веб-страниц, содержащих сопоставимое количество различных терминов. Они отвечают на десятки миллионов запросов каждый день. Несмотря на важность крупных поисковых систем в Интернете, очень мало академических исследований было сделано на них. Кроме того, благодаря быстрому прогрессу в технологиях и распространении в Интернете, создание системы веб-поиска сегодня сильно отличается от трехлетней давности.

Эта статья содержит подробное описание нашей крупномасштабной поисковой системы в Интернете — первое подробное публичное описание, которое мы знаем на сегодняшний день. Помимо проблем масштабирования традиционных методов поиска для данных такого масштаба, существуют новые технические проблемы, связанные с использованием дополнительной информации, представленной в гипертексте, для получения лучших результатов поиска. В этой статье рассматривается вопрос о том, как построить практическую крупномасштабную систему, которая может использовать дополнительную информацию, представленную в гипертексте. Также мы рассмотрим проблему того, как эффективно справляться с неконтролируемыми коллекциями гипертекста, где каждый может публиковать все, что хочет.

 

Ключевые слова

Всемирная паутина, поисковые системы, поиск информации, PageRank, Google

Оглавление

1. Введение
1.1. Поисковые системы в Интернете — расширение масштабов: 1994 — 2000
1.2. Google: масштабирование с помощью Интернета
1.3 Цели дизайна
1.3.1 Улучшенное качество поиска
1.3.2 Академические исследования в поисковых системах
2. Особенности системы
2.1 PageRank: наведение порядка в Интернете
2.1.1 Описание расчета PageRank
2.1.2 Интуитивное обоснование
2.2 Якорный текст
2.3 Другие особенности
3. Сопутствующая работа
3.1 Поиск информации
3.2 Различия между сетью и хорошо управляемыми коллекциями
4. Системная анатомия
4.1 Обзор архитектуры Google
4.2 Основные структуры данных
4.2.1 BigFiles
4.2.2 Репозиторий
4.2.3 Индекс документа
4.2.4 Лексикон
4.2.5 Хит-листы
4.2.6 Форвардный индекс
4.2.7 Инвертированный индекс
4.3 Сканирование в Интернете
4.4 Индексирование в Интернете
4.5 Поиск
4.5.1 Система ранжирования
4.5.2 Обратная связь
5. Результаты и производительность
5.1 Требования к хранению
5.2 Производительность системы
5.3. Производительность поиска
6. Выводы
6.1 Будущая работа
6.2 Высококачественный поиск
6.3 Масштабируемая архитектура
6.4 Инструмент исследования
7. Благодарности
Рекомендации
Краткая биография авторов
8. Приложение А: Реклама и смешанные мотивы
9. Приложение B: Масштабируемость
9.1 Масштабируемость Google
9.2 Масштабируемость архитектур централизованного индексирования

 

 

1. Введение

Примечание: есть две версии этого документа — более длинная полная версия и более короткая печатная версия. Полная версия доступна в Интернете и на компакт-диске конференции.

Интернет создает новые проблемы для поиска информации. Количество информации в Интернете быстро растет, а также количество новых пользователей, неопытных в искусстве веб-исследований. Люди могут просматривать веб-страницы, используя граф ссылок, часто начиная с высококачественных поддерживаемых человеком индексов, таких как Yahoo! или с поисковыми системами. Поддерживаемые человеком списки эффективно охватывают популярные темы, но они субъективны, дороги в создании и обслуживании, медленно улучшаются и не могут охватывать все эзотерические темы.

Автоматические поисковые системы, которые полагаются на сопоставление ключевых слов, обычно возвращают слишком много совпадений низкого качества. Что еще хуже, некоторые рекламодатели пытаются привлечь внимание людей, принимая меры, направленные на введение в заблуждение автоматизированных поисковых систем. Мы создали масштабную поисковую систему, которая решает многие проблемы существующих систем. Это делает особенно интенсивным использование дополнительной структуры, присутствующей в гипертексте, чтобы обеспечить намного более качественные результаты поиска. Мы выбрали название нашей системы, Google, потому что это обычное написание googol, или 10 в сотой степени, и хорошо вписывается в нашу цель создания очень масштабных поисковых систем.

 

1.1. Поисковые системы в Интернете — расширение масштабов: 1994 — 2000

Технологии поисковых систем пришлось масштабировать, чтобы не отставать от роста сети. В 1994 году одна из первых поисковых систем в Интернете, World Wide Web Worm (WWWW) [McBryan 94], имела индекс из 110 000 веб-страниц и документов, доступных через Интернет. По состоянию на ноябрь 1997 года ведущие поисковые системы претендуют на индексирование от 2 миллионов (WebCrawler) до 100 миллионов веб-документов (из Search Engine Watch). Предполагается, что к 2000 году всеобъемлющий индекс Интернета будет содержать более миллиарда документов.

В то же время невероятно выросло количество запросов поисковых систем. В марте и апреле 1994 года червь World Wide Web получал в среднем около 1500 запросов в день. В ноябре 1997 года Altavista утверждала, что обрабатывает около 20 миллионов запросов в день. С ростом числа пользователей в Интернете и автоматизированных систем, которые запрашивают поисковые системы, вполне вероятно, что к 2000 году ведущие поисковые системы будут обрабатывать сотни миллионов запросов в день. Цель нашей системы — решить многие из проблемы, связанные как с качеством, так и с масштабируемостью, возникающие при масштабировании технологии поисковых систем до таких необычных чисел.

 

1.2. Google: масштабирование с помощью Интернета

Создание поисковой системы, которая масштабируется даже до современной сети, ставит много задач. Технология быстрого сканирования необходима для сбора веб-документов и их обновления. Место для хранения должно быть эффективно использовано для хранения индексов и, при необходимости, самих документов. Система индексирования должна эффективно обрабатывать сотни гигабайт данных. Запросы должны обрабатываться быстро, со скоростью от сотен до тысяч в секунду.

Эти задачи становятся все сложнее по мере роста Интернета. Однако производительность и стоимость оборудования значительно улучшились, чтобы частично компенсировать сложность. Однако существует несколько заметных исключений из этого прогресса, таких как время поиска диска и надежность операционной системы. При разработке Google мы учитывали как темпы роста Интернета, так и технологические изменения. Google разработан, чтобы хорошо масштабироваться для очень больших наборов данных. Это позволяет эффективно использовать пространство для хранения индекса. Его структуры данных оптимизированы для быстрого и эффективного доступа (см. Раздел 4.2). Кроме того, мы ожидаем, что стоимость индексации и хранения текста или HTML в конечном итоге снизится относительно суммы, которая будет доступна (см. Приложение B). Это приведет к благоприятным свойствам масштабирования для централизованных систем, таких как Google.

 

1.3 Цели дизайна

 

1.3.1 Улучшенное качество поиска

Наша главная цель — улучшить качество поисковых систем. В 1994 году некоторые люди полагали, что полный поисковый индекс позволит легко найти что-либо. Согласно Best of the Web 1994 — Навигаторы: «Лучший навигационный сервис должен облегчать поиск почти всего в Интернете (после ввода всех данных)». Тем не менее, Интернет 1997 года совершенно другой. Любой, кто недавно использовал поисковую систему, может легко засвидетельствовать, что полнота индекса не является единственным фактором качества результатов поиска.

«Нежелательные результаты» часто стирают любые результаты, которые интересуют пользователя. Фактически, по состоянию на ноябрь 1997 года, обнаруживается только одна из четырех ведущих коммерческих поисковых систем (возвращает свою собственную страницу поиска в ответ на свое имя в первой десятке). Результаты). Одной из основных причин этой проблемы является то, что количество документов в индексах увеличивается на много порядков, но способность пользователя просматривать документы не увеличивается. Люди все еще хотят посмотреть на первые несколько десятков результатов.

Из-за этого, по мере роста размера коллекции, нам нужны инструменты, которые имеют очень высокую точность (количество соответствующих документов возвращено, скажем, в десятках лучших результатов). Действительно, мы хотим, чтобы наше понятие «релевантные» включало в себя только самые лучшие документы, поскольку может существовать десятки тысяч слегка релевантных документов. Эта очень высокая точность важна даже за счет отзыва (общее количество соответствующих документов, которые система может вернуть). В последнее время появилось немало оптимизма в отношении того, что использование более гипертекстовой информации может помочь улучшить поиск и другие приложения [Marchiori 97] [Spertus 97] [Weiss 96] [Kleinberg 98]. В частности, структура ссылок [стр. 98] и текст ссылок предоставляют много информации для оценки релевантности и фильтрации качества. Google использует как структуру ссылок, так и текст привязки (см. Разделы 2.1 и 2.2).

 

1.3.2 Академические исследования в поисковых системах

Помимо огромного роста, Интернет также становится все более коммерческим с течением времени. В 1993 году 1,5% веб-серверов были на доменах .com. Это число выросло до более чем 60% в 1997 году. В то же время поисковые системы перешли из академической сферы в коммерческую. До сих пор большинство поисковых систем продолжалось в компаниях с небольшой публикацией технических деталей. Это приводит к тому, что технологии поисковых систем остаются в основном черным искусством и ориентированы на рекламу (см. Приложение A). С Google у нас есть сильная цель — продвигать развитие и понимание в академической сфере.

Другой важной целью проекта было создание систем, которые на самом деле могут использовать разумные числа людей. Использование было важно для нас, потому что мы считаем, что некоторые из наиболее интересных исследований будут включать использование огромного количества данных об использовании, доступных из современных веб-систем. Например, каждый день выполняется много десятков миллионов поисковых запросов. Однако получить эти данные очень сложно, в основном потому, что они считаются коммерчески ценными.

Нашей конечной целью при разработке было создание архитектуры, которая могла бы поддерживать новые исследования в области крупномасштабных веб-данных. Для поддержки новых исследований, Google хранит все фактические документы, которые он сканирует, в сжатой форме. Одной из наших основных целей при разработке Google было создание среды, в которую другие исследователи могли бы быстро войти, обрабатывать большие фрагменты сети и получать интересные результаты, которые было бы очень трудно получить в противном случае. За короткое время система работала, уже было несколько статей, использующих базы данных, сгенерированные Google, и многие другие находятся в процессе разработки. Другая наша цель — создать среду, подобную Spacelab, где исследователи или даже студенты могут предлагать и проводить интересные эксперименты с нашими крупномасштабными веб-данными.

 

2. Особенности системы

Поисковая система Google имеет две важные функции, которые помогают ей получать точные результаты. Во-первых, он использует структуру ссылок в Интернете для расчета рейтинга качества для каждой веб-страницы. Этот рейтинг называется PageRank и подробно описан в [Page 98]. Во-вторых, Google использует ссылку для улучшения результатов поиска.

 

2.1 PageRank: наведение порядка в Интернете

Граф цитирования (ссылки) в Интернете является важным ресурсом, который в значительной степени не используется в существующих поисковых системах. Мы создали карты, содержащие до 518 миллионов этих гиперссылок, что является значительной выборкой. Эти карты позволяют быстро рассчитать «PageRank» веб-страницы, объективную меру ее цитируемости, которая хорошо согласуется с субъективным представлением людей о важности. Из-за этой переписки PageRank является отличным способом определения приоритетов результатов поиска по ключевым словам в Интернете.

Для большинства популярных тем простой поиск соответствия текста, который ограничен заголовками веб-страниц, работает превосходно, когда PageRank определяет приоритеты результатов (демонстрация доступна на google.stanford.edu). Для типа полнотекстового поиска в основной системе Google также очень помогает PageRank.

 

2.1.1 Описание расчета PageRank

Литература по академическому цитированию применяется в Интернете, в основном путем подсчета ссылок или обратных ссылок на данную страницу. Это дает некоторое представление о важности или качестве страницы. PageRank расширяет эту идею, не считая ссылки со всех страниц в равной степени, и нормализуя по количеству ссылок на странице. PageRank определяется следующим образом:

Мы предполагаем, что страница A имеет страницы T1 … Tn, которые указывают на нее (то есть цитаты). Параметр d представляет собой коэффициент демпфирования, который можно установить в диапазоне от 0 до 1. Обычно мы устанавливаем значение d в 0,85. Подробнее о d читайте в следующем разделе. Также C (A) определяется как количество ссылок, выходящих за пределы страницы A. PageRank страницы A определяется следующим образом:

PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

Обратите внимание, что PageRank основан на распределении вероятностей по веб-страницам, поэтому сумма PageRank всех веб-страниц будет равна единице.

PageRank или PR (A) могут быть вычислены с использованием простого итеративного алгоритма и соответствуют главному собственному вектору нормализованной матрицы ссылок сети. Кроме того, PageRank для 26 миллионов веб-страниц можно рассчитать за несколько часов на рабочей станции среднего размера. Есть много других деталей, которые выходят за рамки этой статьи.

 

2.1.2 Интуитивное обоснование

PageRank можно рассматривать как модель поведения пользователя. Мы предполагаем, что есть «случайный серфер», которому произвольно дают веб-страницу, и он продолжает нажимать на ссылки, никогда не нажимая «назад», но в конце концов ему становится скучно, и он начинает с другой случайной страницы. Вероятность того, что случайный пользователь посетит страницу, является ее PageRank. И коэффициент демпфирования d — это вероятность того, что на каждой странице «случайному пользователю» будет скучно и он запросит другую случайную страницу. Одним из важных вариантов является добавление коэффициента демпфирования d только к одной странице или группе страниц. Это позволяет персонализировать и может сделать практически невозможным намеренно ввести систему в заблуждение, чтобы получить более высокий рейтинг. У нас есть несколько других расширений для PageRank, снова см. [Page 98].

Другое интуитивное обоснование заключается в том, что страница может иметь высокий PageRank, если существует много страниц, которые на нее указывают, или если есть несколько страниц, которые указывают на нее и имеют высокий PageRank. Интуитивно понятно, что страницы, которые хорошо цитируются во многих местах в Интернете, заслуживают внимания. Кроме того, страницы, которые имеют, возможно, только одну ссылку от чего-то вроде домашней страницы Yahoo  также вообще стоит посмотреть. Если страница была не высокого качества или была неработающей ссылкой, вполне вероятно, что домашняя страница Yahoo не будет ссылаться на нее. PageRank обрабатывает как эти случаи, так и все, что находится между ними, путем рекурсивного распределения весов через структуру ссылок в Интернете.

 

2.2 Якорный текст

Текст ссылок в нашей поисковой системе обрабатывается особым образом. Большинство поисковых систем связывают текст ссылки со страницей, на которой находится ссылка. Кроме того, мы связываем его со страницей, на которую указывает ссылка. Это имеет несколько преимуществ.

Во-первых, якоря часто предоставляют более точные описания веб-страниц, чем сами страницы.

Во-вторых, якоря могут существовать для документов, которые не могут быть проиндексированы текстовой поисковой системой, такой как изображения, программы и базы данных. Это позволяет возвращать веб-страницы, которые фактически не были просканированы.

Обратите внимание, что страницы, которые не были просканированы, могут вызвать проблемы, так как они никогда не проверяются на достоверность до того, как будут возвращены пользователю. В этом случае поисковая система может даже вернуть страницу, которая фактически никогда не существовала, но имела гиперссылки, указывающие на нее. Тем не менее, можно отсортировать результаты, так что эта конкретная проблема будет возникать редко.

Эта идея распространения якорного текста на страницу, на которую он ссылается, была реализована во Всемирной паутине [McBryan 94], особенно потому, что она помогает искать нетекстовую информацию и расширяет область поиска с меньшим количеством загружаемых документов. Мы используем распространение якоря главным образом потому, что якорный текст может помочь обеспечить более качественные результаты. Эффективное использование якорного текста технически сложно из-за большого количества данных, которые должны быть обработаны. При текущем сканировании на 24 миллиона страниц у нас было более 259 миллионов якорей, которые мы проиндексировали.

 

2.3 Другие особенности

Помимо PageRank и использования якорного текста, у Google есть несколько других функций:

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

 

3. Сопутствующая работа

Поисковое исследование в Интернете имеет краткую и краткую историю. World Wide Web Worm (WWWW) [McBryan 94] был одним из первых поисковых систем в Интернете. За ним последовали несколько других академических поисковых систем, многие из которых в настоящее время являются публичными компаниями. По сравнению с ростом Интернета и важностью поисковых систем, очень мало документов о последних поисковых системах [Pinkerton 94]. По словам Майкла Молдина (главного ученого, Lycos Inc) [Mauldin], «различные службы (включая Lycos) тщательно охраняют детали этих баз данных».

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

 

3.1 Поиск информации

Работа в информационно-поисковых системах насчитывает много лет и хорошо развита [Witten 94]. Тем не менее, большая часть исследований по информационно-поисковым системам проводится на небольших хорошо контролируемых однородных коллекциях, таких как сборники научных работ или новостные сюжеты на смежную тему. Действительно, основной эталон для поиска информации, Конференция по поиску текста [TREC 96], использует довольно небольшую, хорошо контролируемую коллекцию для своих эталонов. Тест «Очень большой корпус» составляет всего 20 ГБ по сравнению с 147 ГБ из нашего сканирования 24 миллионов веб-страниц. Вещи, которые хорошо работают на TREC, часто не дают хороших результатов в Интернете.

Например, стандартная модель векторного пространства пытается вернуть документ, который наиболее близко соответствует запросу, учитывая, что и запрос, и документ являются векторами, определенными вхождением их слова. В Интернете эта стратегия часто возвращает очень короткие документы, представляющие собой запрос, плюс несколько слов. Например, мы видели, как крупная поисковая система возвращала страницу, содержащую только «Bill Clinton Sucks» и изображение из запроса «Bill Clinton». Некоторые утверждают, что в Интернете пользователи должны более точно указывать, что они хотят, и добавлять больше слов в свой запрос. Мы категорически не согласны с этой позицией. Если пользователь отправляет запрос типа «Билл Клинтон», он должен получить разумные результаты, поскольку по этой теме доступно огромное количество высококачественной информации. Принимая во внимание подобные примеры, мы считаем, что стандартная работа по поиску информации должна быть расширена для эффективного взаимодействия с сетью.

 

3.2 Различия между сетью и хорошо управляемыми коллекциями

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

Например, документы различаются:

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

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

Например, сравните информацию об использовании с главной домашней страницы, например Yahoo, которая в настоящее время ежедневно получает миллионы просмотров страниц, с неясной исторической статьей, которая может получать один просмотр каждые десять лет. Понятно, что эти два элемента должны восприниматься поисковой системой совершенно по-разному.

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

 

4. Системная анатомия

Во-первых, мы обеспечим обсуждение архитектуры на высоком уровне. Затем есть некоторые подробные описания важных структур данных. Наконец, основные приложения: сканирование, индексация и поиск будут подробно рассмотрены.

 

4.1 Обзор архитектуры Google

В этом разделе мы дадим общий обзор того, как работает вся система, как показано на рисунке 1. В следующих разделах будут обсуждаться приложения и структуры данных, не упомянутые в этом разделе. Большая часть Google реализована на C или C ++ для эффективности и может работать как в Solaris, так и в Linux.

В Google сканирование в Интернете (загрузка веб-страниц) выполняется несколькими распределенными сканерами. Существует URL-сервер, который отправляет списки URL-адресов для извлечения сканерам. Полученные веб-страницы затем отправляются на сервер хранилища. Затем сервер хранилища сжимает и сохраняет веб-страницы в хранилище. С каждой веб-страницей связан соответствующий идентификационный номер, называемый docID, который назначается при каждом анализе нового URL-адреса на веб-странице. Функция индексации выполняется индексатором и сортировщиком. Индексатор выполняет ряд функций. Он читает хранилище, распаковывает документы и анализирует их. Каждый документ преобразуется в набор вхождений слов, называемых попаданиями. Хиты записывают слово, положение в документе, приблизительный размер шрифта и заглавные буквы. Индексатор распределяет эти попадания в набор «бочек», создавая частично отсортированный форвардный индекс. Индексатор выполняет еще одну важную функцию. Он анализирует все ссылки на каждой веб-странице и сохраняет важную информацию о них в файле привязок. Этот файл содержит достаточно информации, чтобы определить, куда указывает каждая ссылка, и текст ссылки.

Средство распознавания URL-адресов считывает файл привязок и преобразует относительные URL-адреса в абсолютные URL-адреса и, в свою очередь, в docID. Он помещает текст привязки в прямой индекс, связанный с docID, на который указывает привязка. Он также создает базу данных ссылок, которые представляют собой пары docID. База данных ссылок используется для вычисления PageRanks для всех документов.

Сортировщик берет бочки, отсортированные по docID (это упрощение, см. Раздел 4.2.5), и сортирует их по wordID для генерации инвертированного индекса. Это делается на месте, поэтому для этой операции требуется мало временного пространства. Сортировщик также создает список идентификаторов слов и смещений в инвертированном индексе. Программа под названием DumpLexicon берет этот список вместе с лексиконом, созданным индексатором, и генерирует новый словарь, который будет использоваться поисковиком. Поисковый сервер запускается веб-сервером и использует лексикон, созданный DumpLexicon вместе с инвертированным индексом и PageRanks для ответа на запросы.

 

4.2 Основные структуры данных

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

 

4.2.1 Большие Файлы

BigFiles — это виртуальные файлы, охватывающие несколько файловых систем и адресуемые 64-разрядными целыми числами. Распределение между несколькими файловыми системами обрабатывается автоматически. Пакет BigFiles также обрабатывает размещение и освобождение файловых дескрипторов, поскольку операционные системы не обеспечивают достаточно для наших нужд. BigFiles также поддерживает элементарные параметры сжатия.

 

4.2.2 Репозиторий

Репозиторий содержит полный HTML-код каждой веб-страницы. Каждая страница сжимается с помощью zlib (см. RFC1950). Выбор метода сжатия — это компромисс между скоростью и степенью сжатия. Мы выбрали скорость zlib вместо значительного улучшения сжатия, предлагаемого bzip. Степень сжатия bzip в репозитории составляла примерно 4:1 по сравнению со сжатием 3:1 в zlib. В хранилище документы хранятся один за другим и имеют префикс docID, длину и URL, как видно на рисунке 2. Для доступа к хранилищу не требуется никаких других структур данных. Это помогает обеспечить согласованность данных и значительно упрощает разработку; мы можем перестроить все остальные структуры данных только из репозитория и файла, в котором перечислены ошибки сканера.

 

4.2.3 Индекс документа

Индекс документа хранит информацию о каждом документе. Это индекс ISAM (индекс последовательного доступа) с фиксированной шириной, упорядоченный по docID. Информация, хранящаяся в каждой записи, включает текущее состояние документа, указатель на хранилище, контрольную сумму документа и различные статистические данные. Если документ был отсканирован, он также содержит указатель на файл переменной ширины с именем docinfo, который содержит его URL и заголовок. В противном случае указатель указывает на список URL, который содержит только URL. Это дизайнерское решение было обусловлено желанием иметь достаточно компактную структуру данных и способностью извлекать запись за один поиск диска во время поиска.

Кроме того, есть файл, который используется для преобразования URL-адресов в docID. Это список контрольных сумм URL с соответствующими им docID и отсортирован по контрольной сумме. Чтобы найти docID определенного URL-адреса, вычисляется контрольная сумма URL-адреса и выполняется двоичный поиск в файле контрольных сумм, чтобы найти его docID. URL-адреса могут быть преобразованы в docID в пакетном режиме путем слияния с этим файлом. Это метод, который преобразователь URL-адресов использует для преобразования URL-адресов в docID. Этот пакетный режим обновления имеет решающее значение, потому что в противном случае мы должны выполнить один поиск для каждой ссылки, при условии, что один диск потребует более 32 месяцев для нашего набора данных из 322 миллионов ссылок.

 

4.2.4 Лексикон

Лексика имеет несколько разных форм. Одно важное отличие от более ранних систем состоит в том, что лексикон может поместиться в памяти за разумную цену. В текущей реализации мы можем хранить лексикон в памяти на машине с 256 МБ основной памяти. Текущая лексика содержит 14 миллионов слов (хотя некоторые редкие слова не были добавлены в лексикон). Он реализован в двух частях — список слов (соединенных вместе, но разделенных нулями) и хеш-таблица указателей. Для различных функций, «рисунок 2. Структура данных репозитория» В списке слов есть некоторая вспомогательная информация, которая выходит за рамки данной статьи, чтобы полностью объяснить.

 

4.2.5 Хит-листы

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

• простое кодирование (тройка целых чисел)
• компактное кодирование (распределение битов, оптимизированное вручную)
• кодирование Хаффмана

В итоге мы выбрали компактное кодирование с ручной оптимизацией, поскольку оно требовало гораздо меньше места, чем простое кодирование, и гораздо меньше манипуляций с битами, чем кодирование Хаффмана. Детали попаданий показаны на рисунке 3.

Наша компактная кодировка использует два байта для каждого хита. Есть два типа хитов: необычные хиты и простые хиты. Необычные совпадения включают попадания, встречающиеся в URL, заголовке, тексте привязки или метатеге. Простые хиты включают все остальное. Простое попадание состоит из бита с большой буквы, размера шрифта и 12 битов положения слова в документе (все позиции выше 4095 помечены как 4096). Размер шрифта представлен относительно остальной части документа, используя три бита (фактически используются только 7 значений, потому что 111 — это флаг, который сигнализирует о необычном попадании). Необычное попадание состоит из бита с большой буквы, размера шрифта, установленного в 7, чтобы указать, что это необычное попадание, 4 бита для кодирования типа необычного попадания и 8 бит положения. Для совпадений привязки 8 бит позиции делятся на 4 бита для позиции в привязке и 4 бита для хэша docID, в котором происходит привязка. Это дает нам некоторый ограниченный поиск по фразе, пока не так много привязок для конкретного слова. Мы ожидаем обновления способа хранения попаданий привязки, чтобы обеспечить большее разрешение в полях position и docIDhash. Мы используем размер шрифта относительно остальной части документа, потому что при поиске вы не хотите ранжировать идентичные документы иначе, просто потому, что один из документов написан более крупным шрифтом.

Длина списка совпадений сохраняется до самих совпадений. Для экономии места длина списка совпадений объединяется с wordID в прямом индексе и docID в инвертированном индексе. Это ограничивает его до 8 и 5 битов соответственно (есть некоторые приемы, которые позволяют заимствовать 8 битов из wordID). Если длина больше, чем умещается в этом количестве битов, в этих битах используется escape-код, а следующие два байта содержат фактическую длину.

 

4.2.6 Форвардный индекс

Индекс форвард на самом деле уже частично отсортирован. Он хранится в нескольких бочках (мы использовали 64). Каждый бочонок содержит ряд слов. Если документ содержит слова, попадающие в конкретный столбец, в этот столбец записывается docID, за которым следует список идентификаторов слов со списками совпадений, которые соответствуют этим словам. Эта схема требует немного больше памяти из-за дублированных docID, но разница очень мала для разумного количества сегментов и экономит значительное время и сложность кодирования на заключительном этапе индексации, выполняемом сортировщиком. Кроме того, вместо того, чтобы хранить фактические wordID, мы сохраняем каждое wordID как относительное отличие от минимального wordID, который попадает в рисунок 3. Прямой и обратный индексы и бочка лексикона, в которой находится wordID. Таким образом, мы можем использовать только 24 бита для wordID в несортированных бочках, оставляя 8 битов для длины списка совпадений.

 

4.2.7 Инвертированный индекс

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

Важным вопросом является то, в каком порядке docID должны появляться в списке документов. Одно простое решение — хранить их, отсортированные по docID. Это позволяет быстро объединять разные списки документов для запросов из нескольких слов. Другой вариант — хранить их, отсортированные по рейтингу вхождения слова в каждом документе. Это делает ответы на запросы одним словом тривиальными и делает вероятным то, что ответы на запросы с несколькими словами будут находиться в начале. Однако слияние гораздо сложнее. Кроме того, это значительно усложняет разработку, поскольку изменение функции ранжирования требует перестройки индекса. Мы выбрали компромисс между этими вариантами, сохранив два набора перевернутых стволов — один набор для списков совпадений, которые включают в себя попадания по названию или привязке, и другой набор для всех списков совпадений. Таким образом, мы сначала проверяем первый набор стволов, и если в этих стволах недостаточно совпадений, мы проверяем более крупные.

 

4.3 Сканирование в Интернете

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

Для масштабирования до сотен миллионов веб-страниц в Google существует система быстрого распределенного сканирования. Один URL-сервер обслуживает списки URL-адресов для нескольких сканеров (обычно мы использовали около 3). И URL-сервер, и сканеры реализованы на Python. Каждый сканер поддерживает примерно 300 открытых соединений одновременно. Это необходимо для получения веб-страниц в достаточно быстром темпе. На пиковых скоростях система может сканировать более 100 веб-страниц в секунду, используя четыре сканера. Это составляет примерно 600 КБ в секунду данных. Основное снижение производительности — поиск DNS. Каждый сканер поддерживает свой собственный кэш DNS, поэтому ему не нужно выполнять поиск DNS перед сканированием каждого документа. Каждое из сотен соединений может находиться в нескольких различных состояниях:

• поиск DNS
• подключение к хосту
• отправка запроса
• получение ответа

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

Оказывается, что запуск сканера, который подключается к более чем полумиллиону серверов и генерирует десятки миллионов записей журнала, генерирует достаточное количество сообщений электронной почты и телефонных звонков. Из-за огромного количества людей, которые подключаются к сети, всегда есть те, кто не знает, что такое сканер, потому что это первый, кого они увидели. Почти каждый день мы получаем по электронной почте что-то вроде: «Ух ты, ты просмотрел много страниц с моего веб-сайта. Как тебе понравилось?» Есть также некоторые люди, которые не знают о протоколе исключения роботов и считают, что их страница должна быть защищена от индексации с помощью выражения типа «Эта страница защищена авторским правом и не должна быть проиндексирована», что само собой разумеется, сложно для веб-сканеров чтобы понять. Кроме того, из-за огромного количества данных могут происходить неожиданные вещи. Например, наша система пыталась сканировать онлайн-игру. Это привело к большому количеству мусорных сообщений в середине их игры! Оказывается, это было легко исправить. Но эта проблема не возникла, пока мы не загрузили десятки миллионов страниц. Из-за огромного разнообразия веб-страниц и серверов практически невозможно протестировать сканер, не запустив его в значительной части Интернета. Неизменно, существуют сотни неясных проблем, которые могут возникнуть только на одной странице всей сети и привести к сбою сканера или, что еще хуже, вызвать непредсказуемое или неправильное поведение. Системы, которые имеют доступ к большим частям Интернета, должны быть очень надежными и тщательно протестированными. Поскольку большие сложные системы, такие как сканеры, будут неизменно вызывать проблемы, необходимы значительные ресурсы, предназначенные для чтения электронной почты и решения этих проблем по мере их появления.

 

4.4 Индексирование в Интернете

Синтаксический анализ (Parsing) — любой анализатор, предназначенный для работы во всей сети, должен обрабатывать огромное количество возможных ошибок. Они варьируются от опечаток в тегах HTML до килобайтов нулей в середине тега, не-ASCII-символов, тегов HTML, вложенных сотнями, и множества других ошибок, которые бросают вызов любому воображению, чтобы найти такие же творческие. Для максимальной скорости, вместо использования YACC для генерации парсера CFG, мы используем flex для генерации лексического анализатора, который мы оснастили собственным стеком. Разработка этого синтаксического анализатора, который работает с разумной скоростью и является очень надежным, требует значительного объема работы.

Индексирование документов в бочки (Indexing Documents into Barrels) — После анализа каждого документа он кодируется в несколько бочек. Каждое слово преобразуется в wordID с помощью хэш-таблицы в памяти — лексикона. Новые добавления в хэш-таблицу лексикона записываются в файл. После преобразования слов в wordID их вхождения в текущем документе преобразуются в списки совпадений и записываются в передние бочки. Основная трудность с распараллеливанием фазы индексации заключается в том, что лексику необходимо разделить. Вместо того, чтобы делиться лексиконом, мы взяли подход к написанию журнала всех лишних слов, которых не было в базовом лексиконе, который мы зафиксировали в 14 миллионов слов. Таким образом, несколько индексаторов могут работать параллельно, и тогда один конечный индексатор может обработать небольшой файл журнала с дополнительными словами.

Сортировка (Sorting) — чтобы создать инвертированный индекс, сортировщик берет каждую из передних бочек и сортирует ее по wordID, чтобы получить перевернутую бочку для совпадений заголовка и якоря и полнотекстовую инвертированную бочку. Этот процесс происходит по одной бочке за раз, поэтому требует небольшого временного хранения. Кроме того, мы распараллеливаем фазу сортировки, чтобы использовать столько машин, сколько у нас, просто запустив несколько сортировщиков, которые могут обрабатывать разные сегменты одновременно. Поскольку бочки не помещаются в основную память, сортировщик дополнительно подразделяет их на корзины, которые помещаются в память на основе wordID и docID. Затем сортировщик