Единица и сто нулей

Секреты хорошего поиска или чем живет Google?

Google — искаженное написание английского слова "googol", придуманного Милтоном Сироттой, племянником американского математика Эдварда Кайзера, для обозначения числа, состоящего из единицы и ста нулей.

Откуда он взялся такой?

Как и многие знаковые проекты в сфере ИТ, Google обязан своим появлением двум незаурядным людям — Лоуренсу Пейджу (Lawrence Page) и Сергею Брину (Sergey Brin). Последний, кстати, является нашим, пусть и бывшим, соотечественником, перебравшимся в Соединенные Штаты.

Работа над проектом началась в 1995 году в стенах Стэнфордского университета [1] и довольно быстро принесла первые плоды в виде Back Rub (1996) — прототипа Google. А через три года была создана компания Google и запущен собственно поисковый сервер.

Индекс ресурсов, охватывающий миллиард с лишним веб-страниц [2], размещается на массиве недорогих резервируемых серверов (RAIS). Для поиска в такой огромной базе данных (более 2 терабайт) используется пул из шести тысяч серверов, занимающих три вычислительных центра [3]. Серверы имеют оперативную память объемом от 256 Мбайт до 1 Гбайт и работают под управлением RedHat Linux.

Дисковые подсистемы тоже вполне «земные»: вместо высокоскоростных подсистем SCSI компания применяет в качестве стандарта более дешевую технологию IDE. Обширный поисковый каталог Google распределен и дублируется на более чем семи тысячах отдельных дисковых накопителей, что позволяет сбалансировать нагрузку, направляя запросы на доступные в данный момент серверы и дисковые подсистемы.

Только на своем сайте Google обрабатывает больше 20 миллионов запросов в сутки, и еще около 45 миллионов приходит с сайтов партнеров (Yahoo, Netscape, Cisco). Применение RAIS позволило создать расширяемую модульную систему, которая может приспосабливаться к пиковым нагрузкам, — весьма надежную и при этом, заметьте, относительно недорогую. Так как более половины запросов приходит из-за пределов США, компания собирается открыть филиалы в Азии и Европе, чтобы снизить потери времени при поиске.

На сегодняшний день более 30 тысяч сайтов используют Google в качестве локальной поисковой системы (примерно такой же сервис у нас предоставляет «Яндекс»).

Google Inside

Прежде всего, Google — это целый программный комплекс, объединяющий несколько взаимосвязанных компонентов.

Первый из них — «веб-паук» (Crawler), в его задачу входит непосредственная загрузка веб-страниц из Интернета. Обычно параллельно работают три таких поисковых робота, каждый из которых может одновременно загружать до трехсот документов. Все веб-пауки связаны с сервером ссылок (URLServer [4]), который хранит и передает ссылки «паукам» на обработку.

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

Затем эстафета передается индексатору (Indexer), который извлекает документ из архива и обрабатывает его. Документ конвертируется в набор входящих в него слов, так называемые хиты (hits). Каждая запись о хите содержит собственно слово, его позицию в документе, информацию о регистре и размере шрифта, которым это слово отображено. Далее индексатор распределяет хиты в хранилища, называемые цилиндрами (Barrels), тем самым создавая частично отсортированный предварительный индекс. У индексатора есть и дополнительная функция — извлечение ссылок и их запись в специальный файл, который содержит всю возможную информацию о ссылке: ее текст, к какому файлу она принадлежит и куда указывает.

Следующий компонент — обработчик ссылок (URLresolver) — читает сформированный индексатором файл ссылок, конвертирует относительные URL в абсолютные, помещает текст ссылки в предварительный индекс и устанавливает docID того документа, на который ссылка указывает. Вторая задача URLresolver — составление базы данных связей между документами. В дальнейшем эта база используется для определения ранга документа, PageRank (об этой хитрой штуке мы поговорим отдельно).

Затем за дело берется программа сортировки (Sorter). Она сортирует цилиндры по идентификаторам слов (wordIDs) и помещает результаты в инвертированный индекс. Сортировщик генерирует список идентификаторов слов и их смещение в инвертированном индексе.

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

Конечное звено этой схемы — сервер поиска (Searcher). Он работает вместе с веб-сервером и для ответов на запросы использует словарь, сформированный DumpLexicon, вместе с инвертируемым индексом и PageRank.

Секрет Google

Список наград и призовых мест, занятых Google в различных отраслевых топах, конечно, впечатляет. Чем же этот поисковый механизм завоевал сердца множества пользователей, от сетевых обозревателей до рядовых «серферов»? Одна из важнейших причин — высокая релевантность, то бишь соответствие между ожидаемым и фактически полученным. С учетом того, что это самое соответствие есть категория субъективная, возникает резонный вопрос: почему одна «бездушная железка» выдает более релевантные результаты, чем другие такие же поисковые серверы? Ведь не искусственный же интеллект отвечает на запросы! В индексировании от Google нет ничего особенного, аналогичным образом это делают и другие поисковики. «Секрет фирмы» — в том, как Google сортирует сотни и тысячи найденных страниц, выделяя из них наиболее подходящие, независимо от их посещаемости или присутствия в Интернет-каталогах.

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

Есть и упрощенное, так сказать гуманитарное, объяснение принципа PageRank. Представьте себе человека за компьютером, «ползающего» (или летающего, в зависимости от скорости соединения) по Сети. Он открывает случайную страницу (просто набрал абракадабру в строке Location и попал на какой-то сайт) и жмет на случайно выбранную ссылку. Перемещается на другую страницу, опять жмет на случайную ссылку и так далее, постоянно переходя от страницы к странице, но никогда не нажимая кнопку Back. Иногда ему такое блуждание надоедает, и он снова перескакивает на случайную страницу — не по ссылке, а наугад набрав URL. Так вот, вероятность того, что блуждающий серфер зайдет на домашнюю страничку Васи Пупкина, и есть ее PageRank.

Очевидно, что PageRank вашей страницы тем выше, чем больше других страниц ссылается на нее и чем эти страницы популярнее. Повысить PageRank и, как следствие, переместиться вверх в списке результатов поиска можно двумя методами. Первый — сделать страницу популярной (не путать с посещаемой!), чтобы на нее как можно чаще указывали другие. Второй — добиться того, чтобы какая-то страница с высоким PageRank поставила на вас ссылку. Но сущность PageRank такова, что им сложно манипулировать: добиться, чтобы ссылку на вашу страницу разместили на Yahoo, не менее трудно, чем получить признание сотни веб-мастеров, которые будут ссылаться на ваше творение.

Чем живет Google

Большинство Интернет-компаний переживают не лучшие времена. Сокращать рекламные бюджеты и персонал дальше некуда, поэтому многие стали ликвидировать или переводить на коммерческие рельсы бесплатные услуги, пытаться активнее зарабатывать на рекламе и т. п. А за счет чего живет Google? Ответ одновременно и банален, и удивителен: за счет рекламы, той самой, которая не может прокормить и более именитых игроков на этом рынке. Не секрет, что владельцы поисковых серверов продают места в списках результатов самых популярных запросов. Одни — открыто, другие — нет, но, так или иначе, пользователь на первом месте получает не наиболее релевантную, а наиболее оплаченную ссылку. Google пошел другим путем: рекламные ссылки выдаются отдельно от основных результатов поиска и выделены визуально, что не мешает им демонстрировать хорошую отдачу — после окончания рекламных кампаний больше половины клиентов подписывают новые контракты, несмотря на довольно высокую стоимость размещения (8 до 15 долларов за тысячу показов).

Второй источник существования — доходы от лицензирования технологии Google: в настоящий момент ее используют более восьмидесяти компаний, в их числе Yahoo, Netscape и Cisco.

Планов у «единицы со ста нулями» громадье, и большинство из них носит, к чести Google, конструктивный, а не популистский характер. Так, в ближайшее время не планируется ввести поиск по FTP или MP3, несмотря на его востребованность: по технологическим причинам сделать из этого действительно полезный и релевантный сервис пока трудно, а марку ронять негоже. Зато к специализированным сервисам (поиск изображений и поиск в группах новостей) добавится поиск по PDF-файлам и новостным сайтам. Компания не оставит без внимания и корпоративный рынок: уже вышло в свет Google Search Appliance (см. «КТ» #432) — специализированное аппаратно-программное решение для поиска в интрасетях. С начала апреля Google перешел на более продвинутую технологию ранжирования сайтов, разработанную с учетом последних достижений в области биофизики, — PigeonRank (подробнее об этом можно прочитать здесь). И, как сказал в одном из интервью Сергей Брин, команда Google всегда будет заниматься совершенствованием механизмов поиска, что для нас, пользователей Интернета, есть несомненное благо.

[1] — Google — не единственная поисковая система, у которой «ноги растут» из Стэнфорда: Yahoo и Excite тоже созданы студентами этого университета.
[обратно к тексту]

[2] — Если говорить о распределении поисковых систем по объему проиндексированной информации, то Google впереди планеты всей с большим отрывом — 1,25 млрд. страниц. Altavista и Excite — по 250 миллионов, Northern Light — 200 млн., HotBot — 110 млн., Lycos — 50 млн.
[обратно к тексту]

[3] — Для сравнения: «Яндекс», один из лучших российских поисковиков, базируется на тридцати серверах. Подробнее об устройстве «Яндекса» см. тут.
[обратно к тексту]

[4] — UrlServer, как и «веб-пауки», написан на Python, а большинство прочих компонентов Google — на С и С++.
[обратно к тексту]