Bit.ly 发布 Forget-Table，解决非稳定类别分布问题

URL 缩短服务 Bit.ly 工程团队最近发布了 Forget-Table 数据库项目，该项目用来存储随着时间变更的类别分布统计中的最新变化。

Forget-Table 的GitHub 页面上是这样介绍的：

Forget-Table 是用来存储非稳定类别分布的数据库，它会按要求忘记旧数据。该项目的设计目的，是要存储数百万个分布，并可以在高数据量情况下写入。从分布中忘记数据，要模拟一个泊松过程，并使用用户定义的比率。这会平衡一个分布中所有分箱，这样一来，如果没有新的数据进入，分布就会达到统一。 Forget-Table 使用 Redis 后端开发。

bitly 工程团队的Micha Gorelick和Mike Dewar在官方博客上撰写了一篇文章，介绍该项目。

要想在数据集上做任何统计，存储分布是关键。一般来说，只要计数某个特定量值的出现次数，就可以解决这个问题。但是要处理不断出现新数据的数据流，简单的计数器就不行了。之所以失败，因为几周前的数据和刚刚出现的数据有同样的权重，虽然数据描述的基本分布情况可能会变化。此外，工程师也面对新的挑战，因为计数器会很快用尽所有可用的资源。

类别分布用来指明某个事件在一系列可能事件中发生的可能性，文中举了一个例子。

进入我们系统中的每次点击都带有一个固定的国家代码（共有 260 个国家代码）。我们希望有这样一个类别分布，为每个国家赋予一个概率，描述会有多少个点击来自该国。bitly 的数据会为美国赋予一个高权重，日本和巴西的权重就相对较低。

存储这样的分布十分有用，这让 bitly 了解什么是“正常”情况。很多时候，他们会分析：多少个点击来自某国，或者是转向。这让他们的客户可以了解流量的来源。同时，他们会根据异常的流量，修正分布。

Forget-Table 要处理这样的难题：bitly 认为正常的情况，常常会发生变化。比如：他们预测旧金山的流量峰值时间和流量平稳时间与实际发生情况不同。对于什么是“正常”，他们也就没有准主意了。尤其是在社交网站中，7 月跟 12 月的行为完全不同，2012 跟 2011 也完全不同。Forget-Table 就是要将与目前理解不再相干的旧数据忘掉。

基本分布一直在变（即所谓的“非稳定”，non-stationary），只保存计数作为类别分布就会让问题更严重。交替使用多个类别分布也不能解决问题，因为当轮换到一个类别分布时，它对于当前状态并不了解。到轮换结束时，影响它的，只是在其轮换周期内的事件。这样统计得到的数据，只依赖于轮换之间的时间，其结果类似分箱（binning）统计或仅做总体计数的结果，有同样的问题。

以平滑遗忘的方式，我们的统计分布描述的，就是一个持续的时间窗口。某个事件发生的时间越早，对于分布现在的状态影响就越小。

Forget-Table 在忘记旧数据时，遵循这样的基本原则：定义出旧数据的衰退率。一个类别分布的每个分箱在忘记它的计数时，会考虑它目前的计数值以及用户指定的衰退率。在这个规则下，更活跃的分箱的衰退要快于没有多少计数的分箱。这种方法是很简单的流程，可以快速计算出结果，还有额外好处：能够让数据峰值变得平滑。

如果数据突然停止进入 Forget-Table，所有的类别分布会最后衰退到统一分布：所有分箱中的计数为 1，并且停止衰退。这说明：对于 Forget-Table 中的变量分布，已经没有任何信息。

这种方法的结果，使得每个类别分布的每个分箱中的衰退都以指数方式进行。

他们以存储的所有事件数作为“正规化常数（normalising constant）”-z。比如 260 个国家，就对应 260 个分箱。而所有分箱中的点击数之和，就是正规化常数。

bitly 的类别分布，都存在 Redis 的排序集中，主键描述变量，比如 bitly_country，值就是类别分布。集中的每一个元素就是一个国家，每个元素的值就是点击数。在集中，单独存储了一个元素，记录点击总和 z。当需要类别分布报表时，只要取出整个排序集，然后将每个计数除以总和 z，就得到了结果。

这种存储方式，让他们可以快速完成写操作，因为只需增加两个元素的值，同时能让他们在内存中保存上百万和类别分布。存储这么多数据非常重要，因为他们希望知道某个特定主键的正常行为，或是某个话题的正常行为。

说起来简单，但也面对两个问题。首先：可能有数百万个类别分布，要迭代 Redis 表中所有主键完成衰退操作，很困难；想每隔几分钟就把所有分布都衰退一遍，不可行。其次：数据总在不停地进入多个分布，bitly 有时能观察到每秒 3000 个点击，这对应每秒有几十次递增。如此高数据量，会在衰退过程和未来的增量之间造成资源竞争，出现问题。

因此，Forget-Table 真正的贡献，在于实时忘记数据。当 bitly 想操作某个特定变量的当前分布时，他们会取出存在这个变量的键之内的排序集，然后减少当时的计数。

运行一段时间后，他们发现：使用这样简单的基于衰退率的模型，他们只需从一个泊松分布中抽样一个整数，这个泊松分布的衰退率与对应分箱的当前计数、以及该分箱从上次衰退到当前的时间成比例，然后在对应分箱中减去这个整数即可。所以，只要存储少量额外信息，还有上次某分布成功衰退到现在的时间间隔，他们就可以以很低的成本计算出需要抛弃的计数值。这个算法与用来模拟随机系统的吉莱斯皮算法（Gillespie）类似。

在 Redis 中，bitly 使用管道（pipeline）实现上述功能。利用管道，他们可以读取排序集、构成分布、计算衰退计数，然后完成衰退操作。如果某个排序集中不需要写入任何数据，他们会衰退所有分箱，并更新上次衰退到当前的时间。如果管道中出现冲突，不管是另一个进程要衰退当前数据集，还是某个新的事件到达，他们会放弃当前更新。他们选择的算法，使得保存分布的衰退版本不是那么重要，只要知道读取和上次衰退之间的时间间隔即可。

可以去 GitHub 上访问Forget-Table，该项目目前有go 语言和Python 语言两种实现。