Масштабируемость времени для веб-приложения

Question

Моя цель здесь - создать систему, аналогичную системе на первой странице reddit.

У меня есть вещи, и для простоты эти вещи имеют голоса. Лучшая система, которую я сгенерировала, использует распад времени. С половиной времени в 7 дней, если сегодня голосование стоит 20 очков, то через семь дней оно стоит 10 очков, а через 14 дней оно будет стоить 5 очков.

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

Итак, я думал, что смогу отменить эту идею. Голосование сегодня стоит 1 балл. Голосование через семь дней стоит 2 балла, а через 14 дней стоит 4 балла и так далее. Это хорошо работает, потому что для каждого голосования мне нужно только обновить одну строку. Проблема в том, что к концу года мне нужен тип данных, который может содержать фантастически огромные цифры.

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

Итак, я прихожу к вам в stackoverflow. У кого есть гениальная идея или ссылка на идею о том, как моделировать эту систему, чтобы она хорошо масштабировалась для веб-приложения.

Answer 1

Я тоже пытался это сделать. Я нашел то, что похоже на решение, но, к сожалению, я забыл, как делать математику, поэтому мне трудно понять это.

Идея состоит в том, чтобы сохранить журнал вашего счета и отсортировать его, чтобы номера не переполнялись.

В этом документе описывается математика. https://docs.google.com/View?id=dg7jwgdn_8cd9bprdr

И комментарий, где я нашел его здесь: http://blog.notdot.net/2009/12/Most-popular-metrics-in-App-Engine#comment-25910828

Answer 2

Хорошо, подумал о одном решении сделать это на каждом голосовании. Уловка состоит в том, что для хранения голосов требуется связанный список с атомарным поп/нажатием на обе стороны (например, список Redis, но вы, вероятно, не хотите его в ОЗУ).

Это также требует, чтобы распад интервал постоянен (например, 1 час)

Это выглядит следующим образом:

1. На каждый голос, обновите счет нажать в следующий раз гниения этого голосования на хвост списка
2. Тогда поп первый голос из головы списка
3. Если это не достаточно стар, чтобы гниения, толкать его назад к голове
4. в противном случае вычесть требуемое сумма от общего балла и нажмите обновленную информацию к хвосту
5. Повторите с шага 2, пока вы не нажмете достаточно свежий голос (шаг 3)

Вы все равно придется проверять головы в фоновом режиме, чтобы очистить посты, на которые никто больше не голосует, конечно.

Answer 3

Здесь поздно, поэтому я надеюсь, что кто-то сможет проверить мою математику. Я думаю, что это эквивалентно экспоненциальному распаду.

MySQL имеет BIGINT максимум 2^64

Для простоты Давайте используем 1 день, как наш промежуток времени. Пусть n - количество дней с момента запуска сайта.

1. Создать целочисленную переменную. Давайте назовем его X и запустим его в 0
2. Если операция добавления привела бы счет более 2^64, сначала обновите каждый балл, разделив его на 2^n, а затем установите X равным n.
3. На каждое голосование добавьте 2^(n-X) в партитуру.

Итак, мысленно это имеет смысл для меня, используя основание 10. Когда мы добавляем вещи, наш номер становится длиннее и длиннее. Мы перестаем заботиться о цифрах в младших разрядах цифр, потому что значения, которые мы увеличиваем, имеют много цифр. Это означает, что более низкие цифры перестают считать очень сильно. Поэтому, если они не учитываются, почему бы не просто сместить десятичное место до той точки, в которой мы заботимся, и в какой-то момент усечь цифры ниже десятичной точки. Для этого нам нужно сдвинуть десятичное место на сумму, которую мы добавляем каждый раз.

Я не могу не чувствовать, что с этим что-то не так.

Answer 4

Вот два возможных псевдо-запроса, которые вы могли бы использовать. Я знаю, что они на самом деле не решить масштабируемости, но я думаю, что они обеспечивают методы, так что вы можете

SELECT article.title AS title, SUM(vp.point) AS points 
FROM article 
LEFT JOIN (SELECT 1/DATEDIFF(NOW(), vote.created_at) as point, article_id 
    FROM vote GROUP BY article_id) AS vp 
ON vp.article_id = article.id 

или (не в объединении, который будет немного быстрее, я думаю, но труднее гидрат),

SELECT SUM(1/DATEDIFF(NOW(), created_at)) AS points, article_id 
FROM vote 
WHERE article_id IN (...) GROUP BY article_id 

преимущество этих запросов является то, что они могут работать в любое время с теми же данными, и они всегда будут возвращаться одни и те же ответы. Они не уничтожают никаких данных.

Если вам нужно, вы также можете запускать запросы в фоновом задании, и они все равно будут давать одинаковый результат.