Умение искать информацию в Интернете имеет жизненно важное значение.
Когда мы нажимаем кнопку «Поиск» в нашей любимой поисковой системе, в течение доли секунды мы получаем ответ. Большинство людей совершенно не задумываются о том, что происходит «под капотом», однако поисковая система — это не только полезный инструмент, но и сложный технологический продукт. Современная поисковая система использует для своей работы практически все передовые достижения компьютерной индустрии: большие данные, теорию графов и сетей, анализ текста на естественном языке, машинное обучение, персонализацию и ранжирование.
Понимание того, как работает поисковая система, дает представление о состоянии технологий и, следовательно, полезно для понимания любому инженеру.
В нескольких статьях я пошагово расскажу, как работает поисковая система, а кроме того, для иллюстрации построю свою небольшую поисковую систему, чтобы не быть голословным.
Эта поисковая система будет, конечно, «образовательной», с очень сильным упрощением того, что происходит внутри Google или Яндекса, но, с другой стороны, я не буду ее слишком упрощать.
Первый шаг — сбор данных (или, как его еще называют, сканирование).
Сеть — это график
Та часть Интернета, которая нас интересует, состоит из веб-страниц.Чтобы поисковая система могла найти конкретную веб-страницу по запросу пользователя, она должна заранее знать, что такая страница существует и содержит информацию, релевантную запросу.
Пользователь обычно узнает о существовании веб-страницы из поисковой системы.
Откуда сама поисковая система узнает о существовании веб-страницы? Ведь никто не обязан ей об этом прямо сообщать.
К счастью, веб-страницы не существуют сами по себе; они содержат ссылки друг на друга.
Поисковый робот может переходить по этим ссылкам и открывать все больше и больше новых веб-страниц.
Фактически структура страниц и связей между ними описывает структуру данных, называемую «графом».
Граф по определению состоит из вершин (в нашем случае веб-страниц) и ребер (соединений между вершинами, в нашем случае гиперссылок).
Другими примерами графов являются социальная сеть (люди — вершины, ребра — дружеские отношения), карта дорог (города — вершины, ребра — дороги между городами) и даже все возможные комбинации в шахматах (шахматная комбинация — вершина, ребро — между вершинами существует, если один из Вас может перейти из одной позиции в другую за один ход).
Графы могут быть ориентированными и неориентированными в зависимости от того, указано ли направление на ребрах.
Интернет представляет собой ориентированный граф, поскольку по гиперссылкам можно переходить только в одном направлении.
Для дальнейшего описания мы будем предполагать, что Интернет представляет собой сильно связанный граф, то есть, если вы начнете в любой точке Интернета, вы можете попасть в любую другую точку.
Это предположение явно неверно (я легко могу создать новую веб-страницу, которая нигде не будет иметь ссылок и, следовательно, на нее нельзя будет попасть), но для задачи проектирования поисковой системы его можно принять: как правило, веб-страницы, которые не имеют ссылки не представляют большого интереса для поиска.
Небольшая часть веб-графика: 
Алгоритмы обхода графа: поиск в ширину и в глубину
Поиск в глубину
Существует два классических алгоритма обхода графа.Первый – простой и мощный – алгоритм называется поиск в глубину (Поиск в глубину, DFS).
Он основан на рекурсии и состоит из следующей последовательности действий:
- Отмечаем текущую вершину как обработанную.
- Обрабатываем текущую вершину (в случае с поисковым роботом обработка будет просто сохранением копии).
- Для всех вершин, к которым можно перейти из текущей: если вершина еще не обработана, рекурсивно обрабатываем и ее.
Полный код на github Например, примерно так же работает стандартная утилита Linux wget с параметром -r, указывающим на то, что сайт необходимо загружать рекурсивно:seen_links = set() def dfs(url): seen_links.add(url) print('processing url ' + url) html = get(url) save_html(url, html) for link in get_filtered_links(url, html): if link not in seen_links: dfs(link) dfs(START_URL)
wget -r habrahabr.ru
Метод поиска в глубину целесообразно использовать для сканирования веб-страниц небольшого сайта, но для сканирования всего Интернета он не очень удобен:
- Содержащийся в нем рекурсивный вызов не очень хорошо распараллеливается.
- При такой реализации алгоритм будет углубляться в ссылки все глубже и глубже, и в конце концов ему, скорее всего, не хватит места в стеке рекурсивных вызовов и мы получим ошибку переполнения стека.
Поиск в ширину
Поиск в ширину (поиск в ширину, BFS) работает аналогично поиску в глубину, но он обходит вершины графа в порядке расстояния от начальной страницы.Для этого алгоритм использует структуру данных «очередь» — в очереди можно добавлять элементы с конца и брать с начала.
- Алгоритм можно описать следующим образом:
- Добавляем первую вершину в очередь и в набор «видимых».
- Если очередь не пуста, берем на обработку следующую вершину из очереди.
- Обработка верха.
- Для всех ребер, исходящих из обрабатываемой вершины, не входящих в число «видимых»:
- Добавьте к «виденному»;
- Добавить в очередь.
- Перейти к пункту 2.
def bfs(start_url):
queue = Queue()
queue.put(start_url)
seen_links = {start_url}
while not (queue.empty()):
url = queue.get()
print('processing url ' + url)
html = get(url)
save_html(url, html)
for link in get_filtered_links(url, html):
if link not in seen_links:
queue.put(link)
seen_links.add(link)
bfs(START_URL)Полный код на github
Понятно, что в очереди сначала будут находиться вершины, расположенные на расстоянии одного звена от исходного, затем две ссылки, затем три ссылки и т. д., то есть алгоритм поиска в ширину всегда достигает вершины кратчайшим путем.
Еще один важный момент: очередь и набор «увиденных» вершин в этом случае используют только простые интерфейсы (добавить, взять, проверить на включение) и легко могут быть перенесены на отдельный сервер, который общается с клиентом через эти интерфейсы.
Эта функция дает нам возможность реализовать многопоточный обход графа — мы можем запустить несколько процессоров одновременно, используя одну очередь.
Роботы.
txt Прежде чем описывать саму реализацию, хотелось бы отметить, что корректный краулер учитывает запреты, установленные владельцем сайта в файле robots.txt. Вот, например, содержимое robots.txt для сайта lenta.ru: User-agent: YandexBot
Allow: /rss/yandexfull/turbo
User-agent: Yandex
Disallow: /search
Disallow: /check_ed
Disallow: /auth
Disallow: /my
Host: https://lenta.ru
User-agent: GoogleBot
Disallow: /search
Disallow: /check_ed
Disallow: /auth
Disallow: /my
User-agent: *
Disallow: /search
Disallow: /check_ed
Disallow: /auth
Disallow: /my
Sitemap: https://lenta.ru/sitemap.xml.gz
Видно, что есть определенные разделы сайта, посещение которых запрещено роботам Яндекса, роботам Google и всем остальным.
Чтобы учесть содержимое robots.txt в Python, можно использовать реализацию фильтра, входящую в стандартную библиотеку: In [1]: from urllib.robotparser import RobotFileParser
.
: rp = RobotFileParser() .
: rp.set_url(' https://lenta.ru/robots.txt ') .
: rp.read() .
: In [3]: rp.can_fetch('*', ' https://lenta.ru/news/2017/12/17/vivalarevolucion/ ') Out[3]: True In [4]: rp.can_fetch('*', ' https://lenta.ru/searchЭquery=big%20data#size=10|sort=2|domain=1 .
: |modified,format=yyyy-MM-dd')
Out[4]: False
Выполнение
Итак, мы хотим просканировать Интернет и сохранить его для последующей обработки.Конечно, для демонстрационных целей обойти и сохранить весь интернет не получится - это будет ОЧЕНЬ дорого, но мы будем разрабатывать код с прицелом на то, что его потенциально можно будет масштабировать под размер всего Интернет. Это означает, что мы должны работать на большом количестве серверов одновременно и сохранять результат в какое-то хранилище, из которого его можно будет легко обработать.
В качестве основы для работы своего решения я выбрал Веб-сервисы Amazon , так как там можно легко поднять определенное количество машин, обработать результат и сохранить его в распределенное хранилище Амазонка S3 .
Есть подобные решения, например Google , Майкрософт и в Яндекс .
Архитектура разработанного решения
Центральным элементом моей схемы сбора данных является сервер очередей, на котором хранится очередь URL-адресов, подлежащих загрузке и обработке, а также набор URL-адресов, которые наши процессоры уже «увидели».В моей реализации они основаны на простейших структурах данных Queue и Set языка Python. В реальной производственной системе, скорее всего, вместо этого стоит использовать какое-нибудь существующее решение для организации очередей (например, Кафка ) и для распределенного хранения наборов (например, решения класса «ключ-значение в памяти» таких баз данных, как аэроспайк ).
Это позволило бы нам добиться полной горизонтальной масштабируемости, но в целом нагрузка на сервер очередей не очень велика, поэтому в моем небольшом демо-проекте нет смысла в таком масштабировании.
Рабочие сервера периодически подбирают новую группу URL для скачивания (подбираем сразу много, чтобы не создавать лишней нагрузки на очередь), загружаем веб-страницу, сохраняем ее на s3 и добавляем новые найденные URL в очередь загрузки .
Чтобы уменьшить нагрузку на добавление URL-адресов, добавления также происходят группами (я добавляю сразу все новые URL-адреса, найденные на веб-странице).
Я также периодически синхронизирую множество «просмотренных» URL-адресов с производственными серверами, чтобы предварительно отфильтровать уже добавленные страницы на стороне производственного узла.
Скачанные веб-страницы я сохраняю в распределенном облачном хранилище (S3) — это будет удобно в дальнейшем для распределенной обработки.
Очередь периодически отправляет на сервер статистики статистику о количестве добавленных и обработанных запросов.
Статистику мы отправляем суммарно и отдельно по каждому работающему узлу — это нужно для того, чтобы было понятно, что загрузка происходит в обычном режиме.
Читать логи каждой отдельной работающей машины невозможно, поэтому будем следить за поведением на графиках.
В качестве решения для мониторинга загрузок я выбрал графит .
Запустить сканер
Как я уже писал, чтобы скачать весь интернет, нужно огромное количество ресурсов, поэтому я ограничился лишь небольшой его частью — а именно сайтами habrahabr.ru и geektimes.ru. Однако это ограничение весьма условно, и его распространение на другие сайты — всего лишь вопрос количества доступного оборудования.
Для начала я реализовал простые скрипты, которые поднимают новый кластер в облаке Amazon, копируют туда исходный код и запускают соответствующий сервис: #deploy_queue.py
from deploy import *
def main():
master_node = run_master_node()
deploy_code(master_node)
configure_python(master_node)
setup_graphite(master_node)
start_urlqueue(master_node)
if __name__ == main():
main()
#deploy_workers.py
#run as: http://<queue_ip>:88889
from deploy import *
def main():
master_node = run_master_node()
deploy_code(master_node)
configure_python(master_node)
setup_graphite(master_node)
start_urlqueue(master_node)
if __name__ == main():
main()
Код сценария Deploy.py, содержащий все функции, которые нужно вызвать.
Использование графита в качестве инструмента статистики позволяет рисовать красивые графики: 
Красный график — найденные URL-адреса, зеленый — загруженные, синий — URL-адреса в очереди.
За весь период было скачано 5,5 млн страниц.
Количество страниц, просканированных в минуту, с разбивкой по рабочим узлам.
Графики не прерываются, сканирование происходит в обычном режиме.
Результаты
На скачивание хабрахабра и geektimes у меня ушло три дня.Можно было бы скачивать гораздо быстрее, увеличив количество рабочих экземпляров на каждой рабочей машине, а также увеличив количество воркеров, но тогда нагрузка на сам хаб была бы очень большой — зачем создавать проблемы любимому сайту? В ходе работы я добавил в сканер пару фильтров, начав отфильтровывать некоторые явно ненужные страницы, не имеющие отношения к разработке поисковых систем.
Разработанный краулер хоть и является демо, но в целом масштабируем и может использоваться для сбора больших объемов данных с большого количества сайтов одновременно (хотя, возможно, в продакшене имеет смысл ориентироваться на существующие краулинговые решения, такие как наследница .
Настоящий продакшен-сканер также должен запускаться периодически, а не один раз, и реализовывать множество дополнительных функций, которыми я до сих пор пренебрегал.
За время сканирования я потратил около 60 долларов на облако Amazon. Всего было скачано 5,5 млн страниц общим объемом 668 гигабайт. В следующей статье серии я создам индекс загруженных веб-страниц с использованием технологий больших данных и разработаю простую поисковую систему для фактического поиска на загруженных страницах.
Код проекта доступен на github. Теги: #python #Облачные вычисления #Веб-сервисы Amazon #Поисковые технологии #поисковые системы
-
Эцп – Неужели Все Так Просто?
19 Oct, 24 -
Икра. Первый День
19 Oct, 24 -
Это Мой Путь В Китай (Часть 3)
19 Oct, 24 -
Wireguard «Приедет» В Ядро Linux — Почему?
19 Oct, 24 -
100 Тысяч Посетителей В День, Что Ли? Да!
19 Oct, 24
