Как устроены поисковые системы

СтуДень – это однодневная студенческая конференция, на которой можно послушать и поговорить о поисковых технологиях, Яндексе и многом другом. На первый СтуДень, 1 апреля 2010 года пришли более 700 человек.

Для разминки Анатолий предложил собравшимся поразмыслить над вопросом: – Почему поиск файла на компьютере занимает 10-20 секунд, а поиск по содержимому всех документов во всем интернете меньше секунды? Когда никто не смог дать вразумительного ответа, докладчик сказал, что его выступление как раз и посвящено ответу на этот вопрос. Анатолий пообещал рассказать, как это устроено, как Яндекс ищет, и как ему это удается.

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

Анатолий привел пример альтернативного телефонного справочника, где телефоны упорядочены не по фамилии и имени человека, а по телефону. Это реальный кошмар телефониста. Понять что-то в таком телефонном справочнике, а тем более что-то найти – очень и очень сложно. Для этого нужно просто просмотреть весь телефонный справочник. От начала и до конца. Представляете, вы звоните в телефонную справочную, а вам говорят: «Ваш заказ на поиск телефона абонента Петрова принят, перезвоните через три рабочих дня…» Это к вопросу о заранее подготовленных данных.

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

И третий пример – это предметный указатель в книге. Если посмотреть внимательно на предметный указатель, то это уже практически то же самое, что и поисковый индекс, по которому ищет поисковая система. Но есть некоторые различия:

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

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

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

Так, если посмотреть на слово «пылкает», то ясно, что оно во всем интернете встречается 11 тысяч раз и чуть меньше, чем на 5 тысячах страниц. А вот если мы возьмем слово «и», то мы увидим, что оно упоминается в интернете 38 миллиардов раз. И это очень логично, потому что слово «и» есть практически в каждом русскоязычном тексте. В поисковом индексе находятся списки всех документов, в которых упоминаются эти слова, и поисковик просто берет, идет по этим спискам и все находит.

Особенное внимание докладчик обратил на то, что для поиска вовсе не нужно просматривать все списки, потому что для данного запроса необходимо найти слово «пылкает» и слово «и», где они встречаются вместе. Для этого нужно взять те документы, где есть слово «пылкает» и поискать в них связку с «и» также, как мы ищем в телефонном справочнике. А вообще, в подобных фразах Яндекс слово «и» совсем не ищет, потому что оно слишком частое и, как правило, смысловой нагрузки не несет.

Далее Анатолий рассказал, как это устроено на практике.

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

Нужно понимать, что в то время интернет был очень, очень маленький. В то время постановка вопроса: «Давай я себе скачаю интернет и пойду почитаю его дома спокойно», – вполне работала. Вот в этом поисковом сервере вмещался весь индекс всего интернета. Сейчас, к сожалению, эти старые добрые времена кончились, и интернет уже больше не тот. И сейчас принято говорить о поисковых кластерах.

Что такое поисковый кластер? Это когда берем весь интернет, режем на кусочки и кладем каждый кусочек на свой сервер. И, в частности, там один сайт получается на одном кусочке, а другой на другом. И у Яндекса есть такой отдельный сервер, который называется «Метапоиск».

Что происходит, когда вы ищете в Яндексе? Вы набираете запрос. Наш сервер берет этот запрос и раздает его нескольким тысячам других машинок. Каждая из этих машинок ищет по своему кусочку. После чего, все данные возвращаются на сервер, все эти результаты объединяются и вам выдаются 10 самых лучших ответов. В специальной терминологии вот этот сервер, который дробит запрос, называется «Метапоиск», а сервера, на которых лежат кусочки базы, называются «базовый поиск».

Анатолий Орлов: «На самом деле, была у Яндекса такая особенность давать компьютерам какие-то имена. И даже ходила такая легенда, что мы всем компьютерам в Яндексе даем имена по буквам старорусского алфавита: аз, буки, веди, глагол и так далее. Но, как вы понимаете, у такой системы наименования есть один фатальный недостаток – в алфавите очень мало букв. И к тому моменту, когда я пришел в Яндекс, у людей уже кончились русские названия букв, они перешли на армянский алфавит. Сейчас мы уже на это плюнули и просто номеруем машины».

Что такое реплики и дата центры? Есть такая особенность, что, чем больше у вас компьютеров, тем больше они ломаются. Если есть 10 тысяч компьютеров, то из них несколько штук обязательно сломано. Что это означает для поиска? Если вдруг потеряется одна из машинок базового поиска, то потеряется возможность искать по этой базе и какой-то сайт (ваш сайт, например) может пропасть и не найтись.

Для того, чтобы этого не происходило, делается следующее. Каждая машина, как минимум, дублируется. У Яндекса существует очень много реплик машин, и если одна из них сломалась всегда можно поискать на другой. Репликация позволяет так же бороться с нагрузкой, потому что одна машина не может справиться с таким огромным потоком запросов. Когда есть несколько машинок, можно между ними поделить этот поток запросов, и все будет хорошо. Также репликация делается между разными дата центрами. Дата-центр – это комната, в которой стоят сервера. Это нужно делать на тот случай, если вдруг потеряется дата-центр целиком.

Далее Анатолий рассказал, как устроены дата-центры Яндекса.

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

Откуда берется индекс? Как уже было сказано, индекс – это заранее подготовленные данные. И эти данные надо готовить. В яндексе есть такой алгоритм, который называется робот, он готовит эти индексы и выкладывает их на поиск.

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

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

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

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

Еще есть такие сайты, которые не хотят, чтобы их обходили. Для этого есть такой файлик robots.txt , посредством которого любой сайт может сказать пауку, хочет он или не хочет, чтобы его индексировали. Почему и кому может быть выгодно не индексировать сайт? Например, мастер не хочет делиться информацией со своего сайта. Или мастер не любит нагрузку, которую ему создает робот. И это тоже нужно учитывать.

Ну, еще есть такое понятие, как спам. Именно есть огромное количество сайтов, которые пытаются целенаправленно обмануть поисковую систему, чтобы привлечь к себе пользователей. Но на этом мы, по понятным причинам, подробно останавливаться не будем. А о поиске – все.

Зал: – Как связан ваш Яндекс.Каталог с очередью в поиске? Например, у меня есть свой сайт, я его зарегистрировал в вашем яндексовском каталоге, что мне это даст?

Анатолий Орлов: – Если вкратце, то Яндекс про ваш сайт будет знать сильно больше, потому что ваш сайт заводят в каталог люди. Обычно мы каталог заводим, как некое тренировочное множество для наших классификаторов. То есть, примеры и задачи – понять про все сайты тематику. Как это сделать? Просто берем каталог, там тематика уже размечена с помощью классификаторов, все остальное получаем. В сумме, с точки зрения сеошников, регистрация в каталоге – это полезно.

Зал: – То есть, как я понимаю, мне от этого будет пользы не очень много, но от этого будет польза Яндексу и в итоге мировому сообществу?

Анатолий Орлов: – В принципе, так.

Зал: – Почему поиск на один и тот же запрос отвечает иногда немного по-разному? В смысле статистических раскладов по упоминанию записи?

Анатолий Орлов: – Потому что он по умолчанию заточен не под исследования статистического упоминания записи, а под то, чтобы дать хороший ответ пользователю. И пользователю обычно число не очень важно, а важен конкретный результат. Их мы всегда отдаем. Если для того, чтобы дать правильное число, нужно дольше подождать, заставить пользователя помучится, мы стараемся его не мучить.

Зал: – По какому признаку разбиваются сайты на разные кластеры?

Анатолий Орлов: – На самом деле, там не совсем сайты. Если вкратце, то их разбивать нужно как можно более равномерно. Там даже не сайты, а странички. Цель простая – борьба с нагрузкой. Например, когда-то давно, несколько лет назад, у нас был следующий баг. Если поискать в Яндексе запрос Рамблер, то иногда Рамблер не находился. Это очень странно, но это можно было понять следующим образом. Когда-то Рамблер был на одной машинке. И в результате получалось, что на всех остальных машинах слово Рамблер встречается редко, а на одной машине слово Рамблер встречается очень много раз, потому что там встречается сайт Рамблера. И это приводило к тому, что вот эта машина, на которой лежал сайт Рамблера, отвечала очень-очень долго. И мы это починили, сделав так, что у нас сейчас один сайт размазан по всем машинкам, грубо говоря. Мы раздаем примерно поровну. Естественно, в этом случае машина начинает отвечать на этот запрос более менее равномерно. Какой-то там хитрой логики, кроме как для борьбы с нагрузкой нет в данный момент.

Зал: - То есть, получается, что собрать с многих машин об одной сайте проще, чем с одной машины?

Анатолий Орлов: – Да, конечно. Вы понимаете, что время, которое ждет пользователь – это время последней машины. И потом, если у нас есть выбор, чтобы все машины ответили за 300 миллисекунд или, если есть выбор, что все машины ответят за 100 миллисекунд, а одна за секунду, то в первом случае ответ пользователю будет быстрее.

Зал: – Меня очень удивило, когда вы сказали: «Куски интернета». Во-первых, что это? Как вы делите интернет?

Анатолий Орлов: - Технически, кусочек интернета называется шардом. Есть такое понятие шардирование. Реально поисковый индекс – это некий такой набор файликов. В нашем формате – это где-то в районе 10 файлов и они лежат на компьютере.

Зал: – А как вы находите новые сайты? Как вообще это происходит программно?

Анатолий Орлов: - Новые сайты находятся по всем возможным источникам. Во-первых – это ссылки с других сайтов. Если у вас есть сайт, на него, скорее всего, поставят другую ссылку. Во-вторых, у нас есть формочка «Добавить сайт». И, в-третьих, наверное, не все это понимают, но есть такая программа, как Яндекс.Бар, которая, когда ходят по сайтам, она запрашивает некоторую информацию и показывает вам. Реально она приводит к тому, что мы знаем по каким сайтам ходят пользователи. И если есть какой-то популярный сайт, у нас сейчас где-то около 3 миллионов баров, и если на него пошли люди, то мы сразу об этом узнаем и начинаем его обходить.

Зал: – Вы сказали, что есть какая-то классификация по сайтам, какие чаще обходятся роботами, какие реже. Первый вопрос – каким образом расставляются приоритеты? И второй вопрос – является ли ближайшей целью компании уменьшить время, за которое индексируются новые сайты?

Анатолий Орлов: – Да, мы активно всегда работаем над тем, чтобы у нас был свежий индекс. Мы знаем, что с этим есть некоторые проблемы. А по сайтам концепция такая. Есть сайты нескольких типов. Сайт первого типа – каждый раз, когда мы заходим на страничку, она каждый раз разная. Вот такой сайт вообще индексировать не надо. Потому что найти там ничего нельзя. Есть второй тип. Когда на сайте положили какой-то документ. Например, на lib.ru добавился какой-то роман «Война и мир» и он там будет лежать, и никогда меняться не будет. Вот такой сайт тоже не надо переиндексировать. А если сайт, грубо говоря, каждый день меняется, например, блог, то к нему надо приходить почаще. Чем сайт чаще меняется, тем его чаще надо обходить. К сожалению, все сайты обходить достаточно часто мы не можем, поэтому мы их приватизируем по тому, как мы их считаем важными. Какой-нибудь сайт, как Lenta.ru – это хороший новостной сайт, там появляются регулярно хорошие новости. И часто это приводит к тому, что мы Lenta.ru обходим раз в пять минут. И в индексе уже есть новые странички с Lenta.ru. А какой-нибудь блог Василия Пупкина мы можем обойти раз в два дня, хотя он тоже регулярно обновляется.

Источник: www.searchengines.ru