Сотрудники «Фейсбука» поверили в успех, потому что Себастьяно Винья и его коллеги придумали абсолютно иной способ подсчета числа рукопожатий. Они заметили, что самая главная проблема – необходимость запоминать увиденных пользователей – совершенно аналогична задаче о подсчете. А последнюю можно решить методом HyperLogLog.
Для интересующихся читателей ниже во врезках мы объясняем основные идеи с помощью примера на рис. 7.2. Этот текст не требует математической подготовки, но, если вы не хотите вдаваться в подробности, можете его пропустить.
Применение HyperLogLog-счетчика для подсчета числа рукопожатий
Хорошая новость: можно очень легко вычислить всех друзей любого пользователя.
Присваиваем хеш-значение каждому пользователю. Запускаем счетчик HyperLogLog и просматриваем пользователей начиная с А. На каждом шаге HyperLogLog будет сообщать, сколько всего разных пользователей мы видели. Оказывается, это все, что нам нужно.
Начнем с пользователя А. Это один пользователь, на расстоянии ноль рукопожатий от самого себя. Теперь посмотрим на его друзей:
Б В Г Д Е,
HyperLogLog сообщит нам, что всего с момента запуска мы видели 6 пользователей. Минус А, получаем 5 пользователей на расстоянии одного рукопожатия. Теперь к А и его друзьям добавляем всех тех, кто дружит с друзьями А:
друзья Б: А, Ж,
друзья В: А, Г, Ж, З
друзья Г: А, В, И
друзья Д: А, Е
друзья Е: А, Д.
После этого HyperLogLog сообщит, что всего с момента запуска мы видели 9 разных пользователей. Вычитаем А и число его друзей, получается
9 − 1 − 5 = 3
пользователя на расстоянии двух рукопожатий от А. Заметьте, что нам не нужно запоминать самих друзей А, а только их количество!
В данном случае больше пользователей у нас нет. В реальности процесс продолжается. На третьем шаге мы добавляем всех «друзей друзей друзей». После этого HyperLogLog опять сообщает, сколько разных пользователей мы видели до сих пор. Вычитаем из этого числа количество пользователей на расстоянии ноль, один и два и получаем число пользователей, которых от А отделяют ровно три рукопожатия. И так далее.
Процесс будет завершен, когда мы увидим всех пользователей сети. Как вы помните, HyperLogLog держит в памяти лишь максимальное число нулей в хеш-значении. В дополнение к этому надо запомнить только число пользователей на расстоянии одного, двух, трех и так далее рукопожатий. Это тоже занимает очень скромный объем оперативной памяти.