Анатомия крупномасштабного гипертекстового поискового движка

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

Отдел компьютерных наук, Стэнфордский университет, Стэнфорд, Калифорния 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 страниц доступен в репозитории.

Поисковое исследование в Интернете имеет краткую и краткую историю. 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 высокого уровня

В этом разделе мы дадим общий обзор того, как работает вся система, как показано на рисунке 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. Прямой и обратный индексы и лексикон

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

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

В итоге мы выбрали компактное кодирование с ручной оптимизацией, поскольку оно требовало гораздо меньше места, чем простое кодирование, и гораздо меньше манипуляций с битами, чем кодирование Хаффмана. Детали попаданий показаны на рисунке 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. Затем сортировщик загружает каждую корзину в память, сортирует ее и записывает ее содержимое в короткий перевернутый ствол и полностью перевернутый ствол.

4.5 Поиск

Цель поиска — обеспечить качественные результаты поиска. Многие из крупных коммерческих поисковых систем, похоже, добились большого прогресса в плане эффективности. Поэтому мы больше внимания уделяем качеству поиска в наших исследованиях, хотя считаем, что наши решения можно масштабировать до коммерческих объемов с чуть большими усилиями. Процесс оценки запроса Google показан на рисунке 4.

1. Разбор запроса.
2. Преобразуйте слова в идентификаторы слов.
3. Искать начало списка документооборота в каждом слове.
4. Просматривайте списки документов, пока не найдете документ, соответствующий всем условиям поиска.
5. Вычислите рейтинг этого документа для запроса.
6. Если мы находимся в коротких бочках и в конце любого списка документирования, ищите начало списка документооборота в полном конце каждого слова и переходите к шагу 4.
7. Если мы не находимся в конце какого-либо списка документов, перейдите к шагу 4. Сортируйте документы, которые соответствуют рангу, и верните верхний k.

Чтобы наложить ограничение на время ответа, как только определенное количество (в настоящее время 40 000) совпадающих документов найдено, поисковик автоматически переходит к шагу 8 на рисунке 4. Это означает, что, возможно, будут возвращены неоптимальные результаты. В настоящее время мы изучаем другие способы решения этой проблемы. В прошлом мы сортировали хиты по PageRank, что, казалось, улучшило ситуацию.

4.5.1 Система ранжирования

Google хранит гораздо больше информации о веб-документах, чем обычные поисковые системы. Каждый хит-лист содержит информацию о позиции, шрифте и заглавных буквах. Кроме того, мы учитываем попадания из текста привязки и PageRank документа. Объединить всю эту информацию в ранг сложно. Мы разработали нашу функцию ранжирования так, чтобы ни один конкретный фактор не мог оказывать слишком большого влияния. Сначала рассмотрим простейший случай — запрос из одного слова. Чтобы ранжировать документ по запросу из одного слова, Google просматривает список совпадений этого слова по этому слову. Google считает, что каждое попадание относится к одному из нескольких различных типов (заголовок, якорь, URL, большой шрифт обычного текста, маленький шрифт обычного текста, …), каждый из которых имеет свой собственный вес шрифта. Веса типов составляют вектор, индексированный по типу. Google подсчитывает количество совпадений каждого типа в списке совпадений. Затем каждый отсчет преобразуется в счетный вес. Веса счетчика сначала увеличиваются линейно с счетом, но быстро сужаются, так что больше определенного счета не поможет. Мы берем скалярное произведение вектора весов типов с вектором весов типов, чтобы вычислить оценку IR для документа. Наконец, IR балл объединяется с PageRank, чтобы дать итоговый рейтинг документу.

Для поиска по нескольким словам ситуация более сложная. Теперь несколько списков совпадений должны сканироваться одновременно, чтобы совпадения, встречающиеся близко друг к другу в документе, были взвешены выше, чем совпадения, происходящие далеко друг от друга. Хиты из нескольких списков совпадений сопоставляются друг с другом, поэтому соседние совпадения сопоставляются друг с другом. Для каждого соответствующего набора совпадений вычисляется близость. Близость основана на том, насколько далеко друг от друга находятся совпадения в документе (или привязке), но классифицируется на 10 различных «корзин» значений в диапазоне от совпадения фразы до «даже не близко — not even close». Счет рассчитывается не только для каждого типа попадания, но и для каждого типа и близости. У каждого типа и пары близости есть тип-прокс-вес (type-prox-weights). Счетчики преобразуются в весовые коэффициенты, и мы берем точечное произведение весовых значений счетчиков и весов типа prox для расчета IR-оценки. Все эти числа и матрицы могут отображаться в результатах поиска в специальном режиме отладки. Эти показы были очень полезны при разработке системы ранжирования.

4.5.2 Обратная связь

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

5. Результаты и производительность

Наиболее важной мерой поисковой системы является качество результатов поиска. Хотя полная оценка пользователей выходит за рамки данной статьи, наш собственный опыт работы с Google показал, что она дает лучшие результаты, чем основные коммерческие поисковые системы для большинства поисковых запросов. В качестве примера, иллюстрирующего использование PageRank, текста привязки и близости, на рисунке 4 показаны результаты Google для поиска по «Биллу Клинтону». Эти результаты демонстрируют некоторые функции Google. Результаты сгруппированы по серверам. Это значительно помогает при просеивании наборов результатов. Ряд результатов взят из домена whitehouse.gov, чего можно ожидать от такого поиска. В настоящее время большинство крупных коммерческих поисковых систем не возвращают никаких результатов от whitehouse.gov, тем более правильных. Обратите внимание, что для первого результата нет заголовка. Это потому, что он не был сканирован. Вместо этого Google использовал якорный текст, чтобы определить, что это хороший ответ на запрос. Точно так же пятый результат — это адрес электронной почты, который, конечно же, нельзя сканировать. Это также результат якорного текста.

Все результаты представляют собой страницы достаточно высокого качества, и, при последней проверке, ни одна не была битой ссылкой. Это в значительной степени потому, что все они имеют высокий PageRank. PageRanks — это проценты в красном и гистограммы. Наконец, нет никаких результатов ни о Билле, кроме Клинтона, ни о Клинтоне, кроме Билла. Это потому, что мы придаем большое значение близости слов. Конечно, настоящая проверка качества поисковой системы будет включать в себя обширное изучение пользователей или анализ результатов, для которых у нас нет места для этого. Вместо этого мы приглашаем читателя попробовать Google для себя на http://google.stanford.edu.

5.1 Требования к хранению

Помимо качества поиска, Google предназначен для эффективного масштабирования по мере роста сети. Одним из аспектов этого является эффективное использование хранилища. В таблице 1 приведены некоторые статистические данные и требования к хранилищу Google. Из-за сжатия общий размер хранилища составляет около 53 ГБ, что составляет чуть более трети от общего объема данных, которые он хранит. При текущих ценах на диск это делает хранилище относительно дешевым источником полезных данных. Что еще более важно, общий объем всех данных, используемых поисковой системой, требует сопоставимого объема памяти, около 55 ГБ. Кроме того, на большинство запросов можно ответить, используя только короткий инвертированный индекс. Благодаря лучшему кодированию и сжатию индекса документов высококачественная поисковая система для Интернета может уместиться на диске 7 ГБ нового ПК.

5.2 Производительность системы

Для поисковой системы важно эффективно сканировать и индексировать. Таким образом, информация может быть обновлена, и основные изменения в системе могут быть сравнительно быстро протестированы. Для Google основными операциями являются Сканирование, Индексирование и Сортировка. Трудно измерить, как долго обходилось сканирование, потому что диски были заполнены, произошел сбой серверов имен или возникли другие проблемы, которые остановили систему. Всего для загрузки 26 миллионов страниц понадобилось около 9 дней (включая ошибки). Однако, как только система работала бесперебойно, она работала намного быстрее, загружая последние 11 миллионов страниц всего за 63 часа, в среднем чуть более 4 миллионов страниц в день или 48,5 страниц в секунду. Мы запустили индексатор и сканер одновременно. Индексатор работал быстрее, чем сканеры. Во многом это связано с тем, что мы потратили достаточно времени на оптимизацию индексатора, чтобы он не был узким местом. Эти оптимизации включали массовое обновление индекса документа и размещение критических структур данных на локальном диске. Индексатор работает со скоростью примерно 54 страницы в секунду. Сортировщики могут работать полностью параллельно; На четырех машинах весь процесс сортировки занимает около 24 часов.

5.3. Производительность поиска

Повышение эффективности поиска не было основной целью наших исследований до этого момента. Текущая версия Google отвечает на большинство запросов от 1 до 10 секунд. На этот раз преобладают дисковые операции ввода-вывода над NFS (поскольку диски распределены по нескольким машинам). Кроме того, Google не имеет никаких оптимизаций, таких как кэширование запросов, подиндексы на общих терминах и другие общие оптимизации. Мы намерены значительно ускорить работу Google с помощью дистрибуции, улучшений оборудования, программного обеспечения и алгоритмов. Наша цель — обрабатывать несколько сотен запросов в секунду. В таблице 2 приведены примеры времени запросов от текущей версии Google. Они повторяются, чтобы показать ускорения в результате кэшированного ввода-вывода.

6. Выводы

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

6.1 Будущая работа

Масштабная система веб-поиска — сложная система, и многое еще предстоит сделать. Нашими ближайшими целями являются повышение эффективности поиска и масштабирование примерно до 100 миллионов веб-страниц. Некоторые простые улучшения эффективности включают в себя кэширование запросов, выделение интеллектуальных дисков и подиндексы. Еще одна область, которая требует много исследований, это обновления. У нас должны быть умные алгоритмы, чтобы решить, какие старые веб-страницы следует сканировать, а какие — сканировать. Работа по достижению этой цели была проделана в [Чо 98]. Одним из перспективных направлений исследований является использование прокси-кешей для создания поисковых баз данных, поскольку они ориентированы на спрос. Мы планируем добавить простые функции, поддерживаемые коммерческими поисковыми системами, такие как булевы операторы, отрицание и stemming. Однако другие функции только начинают изучаться, такие как обратная связь по релевантности и кластеризация (Google в настоящее время поддерживает простую кластеризацию на основе имени хоста). Мы также планируем поддерживать пользовательский контекст (например, местоположение пользователя) и суммирование результатов. Мы также работаем над расширением использования структуры ссылок и текста ссылок. Простые эксперименты показывают, что PageRank можно персонализировать, увеличив вес домашней страницы пользователя или закладок. Что касается текста ссылки, мы экспериментируем с использованием текста, окружающего ссылки, в дополнение к самому тексту ссылки. Поисковая система в Интернете — это очень богатая среда для исследовательских идей. У нас слишком много, чтобы перечислять здесь, поэтому мы не ожидаем, что этот раздел будущей работы станет намного короче в ближайшем будущем.

6.2 Высококачественный поиск

Самая большая проблема, с которой сталкиваются пользователи поисковых систем сегодня, — это качество результатов, которые они получают. Хотя результаты зачастую забавны и расширяют кругозор пользователей, они часто разочаровывают и отнимают драгоценное время. Например, лучшим результатом поиска по запросу «Билл Клинтон» в одной из самых популярных коммерческих поисковых систем стала «Шутка дня» Билла Клинтона: 14 апреля 1997 года. Google разработан для обеспечения более высокого качества поиска, так что работа в Интернете продолжается. чтобы быстро расти, информацию можно легко найти. Для этого Google интенсивно использует гипертекстовую информацию, состоящую из структуры ссылок и текста ссылки (якоря). Google также использует информацию о близости и шрифтах. Хотя оценка поисковой системы является сложной, мы субъективно обнаружили, что Google возвращает результаты поиска более высокого качества, чем современные коммерческие поисковые системы. Анализ структуры ссылок через PageRank позволяет Google оценивать качество веб-страниц. Использование текста ссылки в качестве описания того, на что указывает ссылка, помогает поисковой системе возвращать релевантные (и в некоторой степени высококачественные) результаты. Наконец, использование информации о близости помогает значительно повысить релевантность для многих запросов.

6.3 Масштабируемая архитектура

Помимо качества поиска, Google рассчитан на масштабирование. Он должен быть эффективным как в пространстве, так и во времени, а постоянные факторы очень важны при работе со всей сетью. При реализации Google мы видели узкие места в ЦП, доступе к памяти, объеме памяти, поиске диска, пропускной способности диска, емкости диска и сетевом вводе-выводе. Google развился, чтобы преодолеть ряд этих узких мест во время различных операций. Основные структуры данных Google эффективно используют доступное пространство для хранения. Кроме того, операции сканирования, индексации и сортировки достаточно эффективны, чтобы создать индекс существенной части сети — 24 миллиона страниц менее чем за одну неделю. Мы ожидаем, что сможем создать индекс из 100 миллионов страниц менее чем за месяц.

6.4 Инструмент исследования

Google не только является высококачественной поисковой системой, но и инструментом исследования. Данные, собранные Google, уже привели ко многим другим документам, представленным на конференции, и многим другим. Недавние исследования, такие как [Abiteboul 97], показали ряд ограничений на запросы о сети, на которые можно отвечать, не имея локальной сети. Это означает, что Google (или аналогичная система) является не только ценным исследовательским инструментом, но и необходимым для широкого спектра приложений. Мы надеемся, что Google станет ресурсом для поисковиков и исследователей по всему миру и станет источником нового поколения технологий для поисковых систем.

7. Благодарности

Скотт Хассан (Scott Hassan) и Алан Стеремберг (Alan Steremberg) сыграли решающую роль в развитии Google. Их талантливый вклад незаменим, и авторы должны им большую благодарность. Мы также хотели бы поблагодарить Гектора Гарсиа-Молина (Hector Garcia-Molina), Раджива Мотвани (Rajeev Motwani), Джеффа Уллмана (Jeff Ullman) и Терри Винограда (Terry Winograd) и всю группу WebBase за их поддержку и проницательные обсуждения. Наконец, мы хотели бы отметить щедрую поддержку наших доноров оборудования IBM, Intel и Sun и наших спонсоров. Описанное здесь исследование было проведено в рамках Стэнфордского проекта по созданию интегрированной цифровой библиотеки, поддержанного Национальным научным фондом в рамках Соглашения о сотрудничестве IRI-9411306. Финансирование этого соглашения о сотрудничестве также обеспечивается DARPA и NASA, а также Interval Research и промышленными партнерами Стэнфордского проекта цифровых библиотек.

Краткая биография авторов

Сергей Брин (Sergey Brin) получил степень бакалавра Степень в области математики и информатики в Университете штата Мэриленд в Колледж-Парке в 1993 году. В настоящее время он является кандидатом наук. кандидат в области компьютерных наук в Стэнфордском университете, где он получил степень магистра наук в 1995 году. Получатель стипендии Национального научного фонда. Его исследовательские интересы включают поисковые системы, извлечение информации из неструктурированных источников, а также анализ данных больших текстовых коллекций и научных данных.

Лоуренс Пейдж (Lawrence Page) родился в Ист-Лансинге, штат Мичиган, и получил степень бакалавра наук. в области компьютерной инженерии в Университете штата Мичиган Энн Арбор в 1995 году. В настоящее время он является кандидатом наук. кандидат в области компьютерных наук в Стэнфордском университете. Некоторые из его исследовательских интересов включают структуру ссылок в Интернете, взаимодействие человека с компьютером, поисковые системы, масштабируемость интерфейсов доступа к информации и интеллектуальный анализ личных данных.

8. Приложение А: Реклама и смешанные мотивы

В настоящее время преобладающей бизнес-моделью для коммерческих поисковых систем является реклама. Цели рекламной бизнес-модели не всегда соответствуют обеспечению качественного поиска пользователей. Например, в нашей прототипной поисковой системе одним из лучших результатов для сотового телефона является «Влияние использования сотового телефона на внимание водителя», исследование, которое очень подробно объясняет отвлекающие факторы и риск, связанный с разговором по мобильному телефону во время вождения. Этот результат поиска появился первым из-за его высокой важности, судя по алгоритму PageRank, приблизительной важности цитирования в Интернете [Page, 98]. Ясно, что поисковой системе, которая брала деньги за показ рекламы на сотовых телефонах, было бы трудно оправдать страницу, которую наша система вернула платящим рекламодателям. По этой причине и историческому опыту работы с другими средствами массовой информации [Багдикян 83] мы ожидаем, что поисковые системы, финансируемые рекламой, будут по своей сути смещены в сторону рекламодателей и вдали от потребностей потребителей.

Поскольку даже экспертам очень сложно оценивать поисковые системы, предвзятость поисковых систем особенно коварна. Хорошим примером был OpenText, который, как сообщалось, продавал компаниям право быть перечисленными в верхней части результатов поиска по конкретным запросам [Marchiori 97]. Этот тип предвзятости гораздо более коварен, чем реклама, потому что неясно, кто «заслуживает» присутствия и кто готов платить деньги за внесение в список. Эта бизнес-модель вызвала бурю негодования, и OpenText перестал быть жизнеспособной поисковой системой. Но менее явный уклон, скорее всего, будет терпеть рынок. Например, поисковая система может добавить небольшой фактор к результатам поиска от «дружественных» компаний и вычесть фактор из результатов от конкурентов. Этот тип смещения очень трудно обнаружить, но он все же может оказать существенное влияние на рынок. Кроме того, доходы от рекламы часто служат стимулом для предоставления результатов поиска низкого качества. Например, мы заметили, что главная поисковая система не будет возвращать домашнюю страницу крупной авиакомпании, когда в качестве запроса указывается название авиакомпании. Так получилось, что авиакомпания разместила дорогое объявление, связанное с запросом, которое было его названием. Лучшая поисковая система не потребовала бы этого объявления и, возможно, привела бы к потере дохода от авиакомпании поисковой системе. В целом, с точки зрения потребителя можно утверждать, что чем лучше поисковая система, тем меньше рекламы потребуется потребителю, чтобы найти то, что он хочет. Это, конечно, подрывает поддерживаемую рекламой бизнес-модель существующих поисковых систем. Однако рекламодатели всегда будут получать деньги, которые хотят, чтобы покупатель поменял товар или приобрел что-то действительно новое. Но мы считаем, что проблема рекламы вызывает достаточно смешанных стимулов, поэтому крайне важно иметь конкурентную поисковую систему, которая будет прозрачной и в академической сфере.

9. Приложение B: Масштабируемость

9.1 Масштабируемость Google

Мы разработали Google для масштабирования в ближайшем будущем до 100 миллионов веб-страниц. Мы только что получили диск и машины для обработки примерно такого количества. Все части системы, занимающие много времени, распараллеливаются и приблизительно линейны по времени. К ним относятся такие вещи, как сканеры, индексаторы и сортировщики. Мы также думаем, что большинство структур данных будут корректно работать с расширением. Тем не менее, на 100 миллионах веб-страниц мы будем очень близки ко всем видам ограничений операционной системы в распространенных операционных системах (в настоящее время мы используем как Solaris, так и Linux). К ним относятся такие вещи, как адресуемая память, количество дескрипторов открытых файлов, сетевые сокеты и пропускная способность, и многие другие. Мы считаем, что расширение до более чем 100 миллионов страниц значительно усложнит нашу систему.

9.2 Масштабируемость архитектур централизованного индексирования

По мере увеличения возможностей компьютеров становится возможным индексировать очень большое количество текста за разумную цену. Конечно, другие носители с более высокой пропускной способностью, такие как видео, могут стать более распространенными. Но, поскольку стоимость производства текста низка по сравнению со средствами массовой информации, такими как видео, текст, вероятно, останется очень распространенным. Кроме того, вполне вероятно, что вскоре у нас будет распознавание речи, которое сделает разумную работу по преобразованию речи в текст, увеличив объем доступного текста. Все это предоставляет удивительные возможности для централизованной индексации. Вот наглядный пример. Мы предполагаем, что хотим проиндексировать все, что каждый в США написал за год. Мы предполагаем, что в США 250 миллионов человек, и они пишут в среднем по 10 тысяч человек в день. Это получается около 850 терабайт. Также предположим, что индексирование терабайта может быть сделано сейчас за разумную цену. Мы также предполагаем, что методы индексации, используемые над текстом, являются линейными или почти линейными по своей сложности. Учитывая все эти предположения, мы можем вычислить, сколько времени потребуется, прежде чем мы сможем проиндексировать наши 850 терабайт по разумной цене, принимая во внимание определенные факторы роста. Закон Мура был определен в 1965 году как удвоение мощности процессора каждые 18 месяцев. Это справедливо, не только для процессоров, но и для других важных системных параметров, таких как диск. Если мы предположим, что закон Мура действует на будущее, нам потребуется всего лишь 10 удвоений, или 15 лет, чтобы достичь нашей цели — индексировать все, что каждый в США написал за год, по цене, которую может позволить небольшая компания. Конечно, эксперты по аппаратному обеспечению несколько обеспокоены тем, что закон Мура, возможно, не будет действовать в течение следующих 15 лет, но, безусловно, есть много интересных централизованных приложений, даже если мы только дойдем до нашего гипотетического примера.

Конечно, такие распределенные системы, как Gloss [Gravano 94] или Harvest, часто будут наиболее эффективным и элегантным техническим решением для индексации, но, кажется, трудно убедить мир использовать эти системы из-за высоких административных затрат на установку большого количества установок. Конечно, вполне вероятно, что резкое снижение административных расходов возможно. Если это произойдет, и все начнут использовать систему распределенной индексации, поиск, безусловно, значительно улучшится.

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