Волк в овечьей шкуре
Ничего себе, очевидно, сообщество Reddit выдвинуло (и 15 минут назад свергло) коллегу Дуга Тернбулла как мерзкого спаммера, которым он является! Видимо, он бесстыдно продвигал свои посты в блоге! И среди его тактики использование избирательных колец . Да, и даже некоторые из моих собственных коллег уступили его давлению, чтобы поддержать его рекламные предложения — включая этот, маскируемый как пост о релевантности поискового запроса, основанного на тестировании . ( Хотя я должен признать … это интересное чтение … и Даг красноречивый писатель )
Но не я. Нет, я такой белый, как снег, ведомый ветром, чистый, как горный ручей, невинный, как новорожденный. И на самом деле, все это заставило меня задуматься: как я могу предотвратить такие вещи в будущем? В частности, как я могу помочь Reddit предотвратить формирование избирательных колец в будущем? И тогда мне пришло в голову: счетчик HyperLogLog.
Что такое счетчик HyperLogLog?
Счетчик HyperLogLog — это действительно аккуратная вероятностная структура данных, которая оценивает количество уникальных элементов в списке. Например, допустим, у вас есть действительно популярная веб-страница, и вы хотите точно подсчитать количество уникальных посетителей. Чтобы вести подсчет уникальности, вы должны хранить каждый IP-адрес, который вы когда-либо видели. И после получения нового IP-адреса вы должны сначала проверить, что новый IP-адрес не был пройден ранее, и только после этого вы увеличиваете счетчик сайта. В лучших ситуациях хранение и вычисления, вероятно, масштабируются как O (log (n)). (Что бы вы использовали? Пытается? Пропустить списки?)
С помощью счетчика HyperLogLog все по-другому. Размер структуры данных определяется априори (таким образом, O (1)) и представляет собой минимальную долю любой структуры данных, из которой вы будете использовать в примере предыдущего абзаца. Вставка и подсчет данных выполняются очень быстро, а также масштабируются как O (1). Но здесь есть одна загвоздка: вы не можете знать точное количество уникальных просмотров. Скорее, вы можете иметь только оценку текущего подсчета. Я призываю вас читать больше. Эта статья была лучшим ресурсом, который я нашел. И обязательно попробуйте их классную демонстрацию JavaScript , которая действительно помогает понять, как все это работает.
Но как счетчик HyperLogLog может помочь победить в голосовании?
Вернемся к печальному примеру опального коллеги Дуга Тернбулла. Обычно, когда Даг принуждает других поднять свой пост, он использует формы вымогательства или даже угрозы физического вреда. Естественно, я никогда не поддавался этому , но те, которые обращаются к последнему посту Дуга ( многие из которых можно найти здесь ) и upvote.
Но подумайте о том, что произойдет, если мы создадим счетчик HyperLogLog для каждого пользователя в Reddit, и каждый раз, когда пользователь получает upvote, мы обновляем соответствующий счетчик HyperLogLog идентификатором пользователя, который выполнил голосование. Учитывая эту настройку, вот как мы можем определить голосование Во-первых, для данного пользователя извлеките предполагаемое количество уникальных голосов из счетчика HyperLogLog этого пользователя, и давайте пометим это количество как estimated_unique_upvotes. Затем подсчитайте общее количество фактических голосов …
эти вещи …
во всех сообщениях этого пользователя. Давайте назовем это количество как
. Вероятность того, что данный пользователь участвует в голосовании, будет сильно коррелировать с соотношением этих чисел. Другими словами, мы можем определить:
global_total_upvotes
voting_honesty = estimated_unique_upvotes / global_total_upvotes
Думаю об этом. Если пользователь не участвует в голосовании, то его голоса будут генерироваться органически от кого-то из всемирной паутины, который считает, что его ссылки интересны. Поскольку Интернет является большим местом, это пользователь estimated_unique_upvotesи global_total_upvotesбудет стремиться к тому же номеру , и их voting_honesty «вероятность» будет стремиться к 1. С другой стороны, пользователь завернутый в захудалом преступном Reddit колец голосования будет намного больше global_total_upvotesчерез все сообщений, чем они имеют estimated_unique_upvotes. Для этого пользователя значение voting_honestyбудет стремиться к 0.
Вывод
Теперь мы говорим 1 и 0. Разве компьютеры не должны быть хороши с ними? Да! Таким образом, метод, который я описал выше, должен быть масштабируемым способом автоматического обнаружения и исключения этих голосующих шарлатанов! Есть ли проблемы с этой стратегией? Конечно. Но я думаю , что estimated_unique_upvotesв global_total_upvotesсоотношении интересно. Помоги мне подумать; где это можно использовать за пределами избирательных колец Reddit?
И что теперь? Ну, это очевидно, верно? Upvote эту статью!
Идея обновления: выбрасывание 90% инфраструктуры Reddit и использование вместо этого аппроксимаций HLL.
Эй, у меня есть другая идея! Интересно, как выглядит инфраструктура Reddit? Должен быть ад, чтобы все масштабировать. Самая очевидная сложность — отслеживание всех этих голосов «за» и «против». Кроме того, наиболее важной функцией инфраструктуры является обеспечение того, чтобы никто не голосовал за пост более одного раза — в противном случае коллега, Даг Тернбулл, забил бы насмерть установкой за компьютер и голосованием своих собственных постов! Поскольку его так сложно масштабировать, почему бы просто не разорвать все это и заменить его на приближения HLL?
Вот как: каждый пост получает 2 счетчика HLL, один положительный голос и один отрицательный. Когда пользователь повышает или понижает оценку сообщения, его идентификатор отправляется соответствующему счетчику HLL. Никогда не существует шанса, что голос может быть подсчитан дважды, и нет необходимости в какой-либо инфраструктуре, которая гарантирует, что никто не проголосует дважды.
Но у этого подхода есть пара очевидных недостатков. Во-первых, голосование теперь является лишь оценкой — предположением, и хотя в среднем это сработало бы хорошо, наверняка были бы продвинутые посты, получившие повышение, и отличные посты, оштрафованные. Во-вторых, побочным эффектом всей этой инфраструктуры отслеживания кликов является то, что вы теряете возможность отслеживать свою собственную историю! И если вы снова построили инфраструктуру таким образом , чтобы вы могли увидеть историю, вы могли бы также вернуться к тому , как Reddit в настоящее время это делает. Но, по крайней мере, эту идею стоит помнить при создании и масштабировании веб-сайта, который имеет, но не показывает , голосов.