Web应用程序的可缩放时间衰减

我的目标是生成一个类似于reddit首页的系统。Web应用程序的可缩放时间衰减

我有东西，为了简单起见，这些东西都有选票。我产生的最好的系统是使用时间衰减。以7天的半衰期计算，如果今天的投票价值为20分，那么在7天内它值10分，在14天内只值5分。

问题是，虽然这产生的结果，我很高兴，它不缩放。每次投票都要求我有效地重新计算其他投票的价值。

所以，我想我可能能够扭转这个想法。今天的投票值得1分。从现在开始的七天内投票价值2分，从现在开始的14天内价值4分等等。这很有效，因为对于每次投票，我只需要更新一行。问题在于，到今年年底，我需要一个数据类型，可以保存极其庞大的数字。

所以，我尝试使用产生可怕排名的线性增长。我尝试了多项式增长（从站点启动和提交以来的平均天数），并且它产生了稍好的结果。然而，随着我的结果稍微好转，我很快就会重新接近不可维护的数字。

所以，我来找你stackoverflow。谁有一个天才想法或链接到如何建模该系统的想法，因此它适合Web应用程序。

2012-01-06 Piper Merriam

http://www.seomoz.org/blog/reddit-stumbleupon-delicious-and-hacker-news-algorithms-exposed略很有帮助，但一目了然，它们都没有显示出任何规模。 – 2012-01-06 06:57:13

我没有看到任何系统允许非线性衰减，您不必在某个时刻重新计算得分。问题是，你需要在每个投票中做到这一点，或者背景cron工作可以做到吗？ – 2012-01-06 07:01:05

cron工作吸吮。它会这样做，但我很有决心找到一个非持续性的流程样式解决方案。 – 2012-01-06 07:02:31

我一直在努力做到这一点。我发现看起来像一个解决方案，但不幸的是，我忘了如何做数学，所以我无法理解它。

这个想法是存储你的分数的日志和排序，所以数字不会溢出。

本文档介绍数学。 https://docs.google.com/View?id=dg7jwgdn_8cd9bprdr

而且，我发现它的评论是在这里： http://blog.notdot.net/2009/12/Most-popular-metrics-in-App-Engine#comment-25910828

来源

2012-01-08 20:39:03 aburgel

好吧，想到在每个投票中都要这样做的解决方案。值得注意的是，它需要一个双方都有原子弹出/推送的链表来存储投票（例如，Redis列表，但你可能不希望它在RAM中）。

它还要求衰退间隔是恒定的（例如，1小时）

它是这样的：

在每一票，更新得分的本表决衰减的下一次推到列表的尾部
然后从列表的头部弹出第一个投票
如果不是老得足以衰减，将其推回至头
否则，减去所需从总分量和从第2步推动更新的信息到尾
重复操作，直至触及新的足够投票（步骤3）

你仍然必须检查元首在后台清除当然没有人投票的帖子。

来源

2012-01-06 07:16:49

这个想法有一些好处，但它似乎仍然需要一个cron工作来完成清理工作，我倾向于做一个架构决策尝试只触摸十个脚杆。当我遇到像这样有趣的问题时，我发誓我的脑子里的齿轮开始转得更快。 – 2012-01-06 16:02:10

这里很晚，所以我希望有人可以检查我的数学。我认为这相当于指数衰减。

MySQL有一个最大BIGINT的2^64

为简单起见，让使用1天作为我们的时间间隔。设n是该网站启动以来的天数。

创建一个整型变量。我们称它为X并从0开始
如果添加操作将带来超过2^64的分数，首先将每个分数更新为除以2^n，然后将X设置为n。
在每次投票中，将2 ^（n-X）添加到分数中。

因此，从心理上来说，这对我来说使用基数为10更合适。随着我们添加内容，我们的数字会变得越来越长。我们停止关注较低数字位置的数字，因为我们增加得分的值有很多数字。这意味着非常多的停止计数的低位类型。因此，如果他们不计算，为什么不只是将小数点位置滑动到我们关心的位置，并在某点处截断小数点后面的数字。要做到这一点，我们需要将小数点位置放在每次添加的数量上。

我不禁感觉这里有什么问题。

来源

2012-01-06 07:36:29

首先，当你更新每一行，索引和X时，你会做什么？禁用该网站？ :)因为否则如果有人投票在这一小部分秒（或更多？），那篇文章将是非常幸运的。 – 2012-01-06 07:47:15

就我而言，这可能是一个可行的解决方案。更新可以作为交易运行，而我的“投票”不会以这样的速度进入，这是一个问题。然而，找到一个解决方案，包括更新单行投票和单个投票的结束会很好。 – 2012-01-06 15:57:49

这里收到新票的旧故事没有任何处罚。如果你有一个老故事，每天都会收到投票，它会留在头版。 – 2012-07-05 20:22:45

以下是您可以使用的两种可能的伪查询。我知道，他们并不真正解决可扩展性，但我认为，他们提供的方法，这样就可以

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

这些查询的好处是它们可以在任何时候用相同的数据运行，它们总是会返回相同的答案。他们不会破坏任何数据。

如果需要，还可以在后台作业中运行查询，并且它们仍然会给出相同的结果。

来源

2012-01-06 17:27:50 rockymeza

Web应用程序的可缩放时间衰减

回答

相关问题