[Draft] An alternative algorithm for calculating torrent popularity

[kozlovsky]

1. Мы хотим оценить результаты работы текущего алгоритма. Как мы можем это сделать?

• алгоритм может не давать правильных результатов в принципе (скажем, из-за низкой скорости распространения обновлений)
• реализация алгоритма может содержать баги
• мы оцениваем результаты алгоритма на реальной картине, не зная этой реальной картины

2. Предложение - параллельно считать вторым алгоритмом, независимо реализованным, и сравнивать результаты

• речь не идет о том, что новый алгоритм лучше. Речь о том, что получая популярность двумя незавимыми путями мы можем увидеть более объективную картину.

3. Описание текущего алгоритма и возможных его косяков

• основной источник информации - с трекеров. Насколько я понимаю, мы хотим по возможности быть самодостаточными, поэтому для меня выглядит неправильным, что трекеры играют такую важную роль
• другие источники - BEP33 и DHT. Проблема в том, что результаты не комбинируются. Алгоритм при обновлении информации из нескольких источников не комбинирует данные про сидеров, а берёт самый большой результат из (трекер, BEP33, DHT), и при распространении алгоритм перезатирает ранее полученные данные

4. Преимущества нового алгоритма.
   • умеет считать уникальное количество реальных сидов
   • не перезатирает предыдущие результаты, а комбинирует с новыми
   • имеет встроенную защиту от определенного вида атак
   • мы получаем возможность суммировать уникальных сидеров по всем торрентам, и в результате получать количество уникальных пиров, являющихся сидерами, во всей сети
   • при желании мы можем добавить счетчик уникальных запущенных инстансов триблера, при данном способе подсчёта мы полностью сохраняем анонимность пользователей, поскольку HyperLogLog счетчик не хранит самих значений идентификаторов
5. Храним количество реальных сидеров для каждого торрента с помощью HyperLogLog счётчика

• счетчик имеет компактное представление (значительно меньше, чем Bloob-фильтр эквивалентной вместимости и точности)
• считает количество уникальных значений (в нашем случае - сидеров), которые мы в него помещаем. Один и тот же сидер не будет посчитан более одного раза
• мы можем комбинировать результаты каунтеров, собранных от разных источников, комбинируя число уникальных сидеров

6. Описание нового алгоритма:

• считаем, что самая важная информация - количество реальных сидеров, и распространяем только её
• в памяти храним массив кортежей (торрент, time_bucket, HyperLogLog каунтер сидеров)
• только для живых торрентов
• только реальных сидеров, к которым можем подключиться. В новом алгоритме мы не перезатираем это количество при обновлении, а комбинируем
• на диск записываем для каждого торрента эстимацию HyperLogLog каунтера
• когда мы хотим поделиться информацией с соседом, мы из массива берём два случайных торрента (напоминаю, там только торренты с ненулевым количеством сидеров) сравниваем их и определяем, какой из них разослать. Чаще всего мы рассылаем тот, у кого сидеров больше, но с определенной вероятностью рассылаем случайных из двух.

7. Виды атак:

• занижение числа сидеров
• завышение числа сидеров
• DDoS-атака (не рассматриваем здесь)
  7.1. Первый тип атаки (занижение числа сидеров) автоматически исключен при использовании HyperLogLog счетчика, поскольку при мерже информация двух счетчиков складывается. Злоумышленник может не передать через себя реальное значение счетчика, но если мы получили значение счетчика от нормального пира, то данные, полученные от злоумышленника, не могут уменьшить значение счетчика.
  7.2. Завышение числа сидеров - может использоваться злоумышоенником для "раскрутки" торрента. Выглядит как более редкий тип атаки. Конкретные детали того, как противостоять данной атаке, ещё надо обдумать, но, как один из вариантов, можно добавить второй счетчик, считающий неудовлетворение. Когда человек подключается к якобы популярному торренту и видит реальное количество сидеров намного меньше заявленного, он может увеличить счетчик неудовлетворения. В результате у каждого торрента есть два счетчика, ни один из которых при распространении информации нельзя уменьшить. В то же время, если количество сидеров достаточное, торрент может уменьшить локальный счетчик неудовлетворения до нуля, замедляя передачу неудовлетворения.