Применение HyperLogLog-счетчика для подсчета числа рукопожатий

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

Присваиваем хеш-значение каждому пользователю. Запускаем счетчик HyperLogLog и просматриваем пользователей начиная с А. На каждом шаге HyperLogLog будет сообщать, сколько всего разных пользователей мы видели. Оказывается, это все, что нам нужно.

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

Б В Г Д Е,

HyperLogLog сообщит нам, что всего с момента запуска мы видели 6 пользователей. Минус А, получаем 5 пользователей на расстоянии одного рукопожатия. Теперь к А и его друзьям добавляем всех тех, кто дружит с друзьями А:

друзья Б: А, Ж,

друзья В: А, Г, Ж, З

друзья Г: А, В, И

друзья Д: А, Е

друзья Е: А, Д.

После этого HyperLogLog сообщит, что всего с момента запуска мы видели 9 разных пользователей. Вычитаем А и число его друзей, получается

9 − 1 − 5 = 3

пользователя на расстоянии двух рукопожатий от А. Заметьте, что нам не нужно запоминать самих друзей А, а только их количество!

В данном случае больше пользователей у нас нет. В реальности процесс продолжается. На третьем шаге мы добавляем всех «друзей друзей друзей». После этого HyperLogLog опять сообщает, сколько разных пользователей мы видели до сих пор. Вычитаем из этого числа количество пользователей на расстоянии ноль, один и два и получаем число пользователей, которых от А отделяют ровно три рукопожатия. И так далее.

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

Филипп Флажоле

Филипп Флажоле умер в 2011 году, когда работа над внедрением HyperLogLog была в самом разгаре. Блог под названием «HyperLogLog – краеугольный камень инфраструктуры больших данных»{26} был написан в 2012 году. Статья{27} о 4,74 виртуальных рукопожатий в «Фейсбуке» вышла в том же 2012 году, а статья сотрудников Google{28} – в 2013-м. Система Redis внедрила HyperLogLog в 2014 году. В честь Филиппа Флажоле команды HyperLogLog начинаются с его инициалов PF.

Нам неизвестно, успел ли Флажоле узнать, что его результаты уже стояли на пороге широкого внедрения. Мы закончим последними фразами из блога{29}, где автор подробно и с большим энтузиазмом объясняет HyperLogLog широкой технической публике:

…Мне очень жаль, что я не был знаком с ним лично. Я уверен, что его труды будут жить дальше, но наука и индустрия, безусловно, потеряли выдающийся интеллект. Продолжай считать, Филипп, мы на тебя рассчитываем!