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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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