Немного о спайдерах и расчёте числа Шухарта

Хочу здесь поподробнее рассказать как именно работает спайдер, собирая данные с Хабрахабра. В основе — обычный поиск в ширину. Действует там всё довольно просто:

У паука есть очередь пользователей. В ней хранятся объекты с тремя свойствами: уровень пользователя (относительно Шухарта), имя (в том виде в котором оно входит в личный поддомен на Хабре) и путь от Шуха до пользователя. Вначале в очереди есть только Шухарт:

var shoohurt = {
    'username' : 'shoohurt',
    'level' : 0,
    'path' : ''
}

Кроме этого есть redis-хранилище, где хранятся, во первых, уже известные пауку пользователи (в виде set‘а) и, во вторых, персональные данные для каждого пользователя в виде двух ключей: users:%username%:level и users:%username%:path. Эти пары ключей спайдер только записывает, но никогда к ним не обращается (эти данные берутся из объекта очереди). Путь хранится в виде строки с именами пользователей, разделённых пробелами. Изначально там только Шух, его уровень равен 0, путь — пустая строка.

Потом спайдер действует по одному и тому же шаблону:

• Достаёт пользователя из очереди
• Получает его страницу на Хабре и достаёт оттуда список друзей
• Для каждого друга в списке:
  • Проверяет, есть ли он в Redis в списке уже известных пользователей. Если да, ничего не происходит. Если нет:
  • Добавляет его в список известных пользователей
  • Добавляет запись о его уровне = уровень того у кого был найден пользователь + 1
  • Добавляет запись о пути до него = путь до того у кого был найден пользователь плюс имя того у кого мы его нашли
• После этого паук ждёт заданное время (в первом варианте было 4 секунды) и переходит в режим готовности, повторяя этот алгоритм

Пример: мы обходим друзей пользователя shoohurt и находим Boomburum’а. Такого пользователя в известных нет, поэтому мы его добавляем. Уровень Шухарта = 0, путь к Шухарту — пустая строка. Тогда уровень Бумбурума будет 0 + 1 = 1 и путь к нему будет равен '' + ' shoohurt' = ' shoohurt'.

Пример 2: мы обходим друзей пользователя brainfucker и находим там хабраюзера nats. Такого пользователя в известных нет, поэтому мы его добавляем. Уровень brainfucker’а — 3, путь к нему — ” shoohurt absolvo Alik-Kirillovich”. Тогда для nats уровень будет 3 + 1 = 4, а путь — " shoohurt absolvo Alik-Kirillovich" + " brainfucker" = " shoohurt absolvo Alik-Kirillovich brainfucker".

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

Для показа на сайте мы проверяем есть ли такой пользователь в базе (с помощью SISMEMBER, если нет, показываем печальную страничку. Если пользователь есть, получаем его длину пути и сам путь. Путь разбивается на отдельных пользователей с помощью path.split(' ') и темизируется в виде отдельных ссылок. Последним в новый путь добавляется тот кого мы ищем (уже без последующего символа >).

Вообще изначально я задумывал это как тест графовой базы данных вроде VertexDB или FlockDB (граф-ориентированная база от создателей Twitter), но потом мне в голову пришёл этот алгоритм как упрощённый вариант изначального. Его я и реализовал.

P.S. К сожалению, как оказалось впоследствии, на Хабре топики с упоминанием Шухарта негласно запрещены независимо от их темы. Топик довольно резво набрал ~40 голосов, вышел на главную и был запилен администрацией ресурса. Есть над чем задуматься.