Все дороги ведут в Рим?

лабиринт

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

Канонизация веб-адресов

Каждый учтенный адрес должен быть уникальным, как уникальны паспортные данные налогоплательщика. Но вот беда: ссылки, ведущие на одну и ту же страницу, могут выглядеть по-разному. Скажем, http://crawlers.info/ можно записать как:

  • HTTP://CRAWLERS.INFO/
  • http://crawlers.info//// (слэшей в конце может быть сколько угодно)
  • http://crawlers.info... (точек — тоже)
  • http://crawlers.info (а можно без того и без другого)
  • http://crawlers.info:80/

Перед сохранением URL-а его следует нормализовать или канонизировать — то есть, как минимум:

  1. привести к единому регистру;
  2. убрать лишние слэши и точки;
  3. убрать номер порта по умолчанию.

Международные имена доменов

Еще одна проблема — не-латинские имена доменов. Нахлынувшие в Сеть, подобно мигрантам, они существуют в двух ипостасях. То что, пользователю представляется как деньги-сразу-питербург.рф 1 , сервер доменных имен видит как:

XN-----7KCFGEBIESIE2D8ALGBIZQH6P.XN--P1AI

Второе представление, машинное, является результатом работы алгоритма кодировки Punicode. В Python-е для перевода имен доменов из UTF-8 в IDN 2 и обратно не требуется никаких дополнительных библиотек:

>>> u'деньги-сразу-питербург.рф'.encode('idna')   
'xn-----7kcfgebiesie2d8algbizqh6p.xn--p1ai'
>>>

Библиотека urlnorm

Процедура приведения URL-ов к каноническому виду подробно описана на Википедии. Не вдаваясь в детали, остановимся на практической стороне дела. В Python-е с этой задачей хорошо справляется библиотека urlnorm. Вот что она делает:

  • приводит схему и имя хоста к нижнему регистру;
  • при необходимости имя домена перекодирует из Punicode в utf8;
  • удаляет стандартный порт (т.е. http://www.foo.com:80 превращается в http://www.foo.com);
  • минимизирует путь, убирая лишние слэши с точками;
  • переводит где возможно символы с процентами в читаемый вид 3.

Весь этот труд проделывает функция norm:

>>> from urlnorm import norm
>>> print norm('http://XN-----7KCFGEBIESIE2D8ALGBIZQH6P.XN--P1AI').encode('utf8')
>>> http://деньги-сразу-питербург.рф/

>>> print norm('http://www.foo.bar/////')
>>> http://www.foo.bar/

print norm('http://WWW.FOO.BAR:80/././././')
http://www.foo.bar/

Удаление фрагментов

Иногда ссылки содержат фрагменты, указывающие браузеру, до какого места следует прокрутить страницу после ее открытия. Допустим, где-то в HTML-коде задан "якорь":

<a name="crocodiles"></a>
<h2>О крокодилах</h2>

<p>Едва ли, любезный читатель, ты встретишь в природе более дружелюбных и ласковых существ...</p>

Ссылка, которая должна к нему привести, может выглядеть как:

<a href="http://домен/путь#crocodiles">О крокодилах</a>

Краулеру, как правило, нужна страница целиком, навигация по тексту его не интересуют.

  • http://example.com/index.html#crocodiles
  • http://example.com/index.html#snakes
  • http://example.com/index.html#dragons

Для краулера эти адреса являются синонимами. Следовательно, в процедуру канонизации должно быть включено удаление фрагментов. Библиотека urlnorm этого не делает, так что с ними придется разбираться вручную. На помощь приходит стандартный модуль urlparse 4.

1
2
3
4
5
6
7
8
9
import urlparse
import urlnorm

def canonize(url):
    '''Transform absolute URL to canonical form.'''
    parts = urlparse.urlsplit(unicode(url.strip()))
    # remove fragments
    res = urlparse.urlunsplit((parts.scheme, parts.netloc, parts.path, parts.query, ''))
    return urlnorm.norm(res)
  • Строка 6: слегка "причесанный" функцией unicode и методом string.strip адрес разбивается на части функцией urlparse.urlsplit.

  • Строка 8: "зеркальная" функция urlparse.urlunsplit складывает те же части, только вместо фрагмента подставляет пустую строку.

  • Строка 9: наконец, за дело берется "тяжелая артиллерия" — urlnorm

>>> canonize('http://www.crawlers.info/urls.html#anchor')
>>> u'http://www.crawlers.info/urls.html'

Хранение и проверка

Где хранить адреса пройденных страниц? Глобальный set в памяти годится разве что для прототипа. Аварийное завершение работы приведет к потере данных, так что хранить их лучше вовне. Решений много, выбор зависит от архитектуры и задач приложения. При выборе способа хранения стоит учесть:

  1. объем данных;
  2. необходимость параллельного доступа;
  3. требования к производительности, причем важна скорость записи;
  4. возможность горизонтального масштабирования.

Типичные решения

  • Сериализация питоновских структур, вроде shelve. Под вопросом производительность и масштабируемость, поэтому, на мой взгляд, такой подход если и имеет смысл, то лишь на этапе прототипирования.
  • Реляционные базы данных. Надежно, привычно, но производительность и масштабируемость также вызывают сомнения.
  • Различные варианты сбалансированных деревьев на диске, вроде B-Tree и BerkleyDB. Никогда не экспериментировал с ними, поэтому не смогу ничего рассказать. Понятно, что это такое же плохо масштабируемое решение, как shelve. Хотя, работать должно весьма быстро. Привет из прошлого века!
  • Фильтр Блума через питоновские библиотеки, такие как python-bloomfilter. Среди преимуществ — высокая производительность и нетребовательность к памяти при большом объеме данных. Есть небольшая вероятность ложноположительного срабатывания: элемента в множестве нет, а структура данных сообщает, что он есть5.
  • Redis. Достаточно эффективный, гибкий и масштабируемый, на мой взгляд, вариант.

Хэш-функция

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

На практике часто используют MD5-хэш в шестнадцатиричном представлении. Какую бы строку ни "съела" эта функция, результат всегда состоит из 32 символов.

>>> import hashlib
>>> m = hashlib.md5()
>>> m.update('http://example.com/')
>>> m.hexdigest()
>>> 'a6bf1757fff057f266b697df9cf176fd'

В промышленных базах данных того же позволяют добиться встроенные функции. Например, в MySQL:

> SELECT MD5('http://example.com/');
+----------------------------------+
| MD5('http://example.com/')       |
+----------------------------------+
| a6bf1757fff057f266b697df9cf176fd |
+----------------------------------+
1 row in set (0.00 sec)

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

Partitioning: cделай сам

Применив хэш-функцию и фантазию, можно организовать секционирование (partitioning) данных. Скажем, построить иерархию, взяв в качестве каталогов первые два символа из хэш-кода. Так, для строки 6d094e30f49f6c1f7934d6cf77fe27dc первые два символа, 6d, станут каталогом, а оставшааяся часть, 094e30f49f6c1f7934d6cf77fe27dc,— файлом в нем. Получится что-то вроде:

.
├── 6d
│   ├── 094e30f49f6c1f7934d6cf77fe27dc
│   ├── 38782e4f37b863342a71e56a3276ea
│   └── efb4c716e2412964705e2fec3e8505
├── 87
│   ├── 2f782e4f37b863341011e56a3276ea
│   ├── 4ce4d716e2412964705e2fec3e8505
│   └── 618b7fff0872c5c8d5c2b28ee89736
└── a6
    ├── 702f7e4f37b863341011e56a3276ea
    └── aa8b7fff0872c5c8d5c2b28ee89736

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

Другой вариант применения: распределение данных по разным хостам. Допустим, у нас четыре хоста, на каждом работает Redis. Разбиваем символы, с которых может начинаться шестнадцатиричное число (0123456789abcdef), на четыре диапазона:

  1. 0 - 3
  2. 4 - 7
  3. 8 - b
  4. c - f

Теперь известно, где какие адреса хранятся.


  1. Буква "и" вместо "е" в названии города — не опечатка, домен с таким неправильным именем взят из реального списка. Часто названия доменов с ошибками регистрируются в целях фишинга. Пользователь, набравший название банка с ошибкой, нередко попадает на сайт мошенников, который выглядит точь в точь как настоящий. 

  2. IDN — интернационализированное доменное имя. 

  3. О кодировании URL рассказано в предыдущей заметке

  4. В Python 3 — urllib.parse

  5. Примеры использования Блум-фильтра имеется на Github, интересная дискуссия: на Stackoverflow

  6. См. В ложбине белого орешника — или почему длина веб-адреса не имеет значения

  7. Для работы с алгоритмом MurmurHash из Python-а имеется библиотека mmh3

social

Яндекс.Метрика