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

Question

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

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

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

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

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

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

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

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

MySQL имеет BIGINT max 2 ^ 64

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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