BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

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

| 作者 郑柯 关注 3 他的粉丝 发布于 2013年2月22日. 估计阅读时间: 7 分钟 | Google、Facebook、Pinterest、阿里、腾讯 等顶尖技术团队的上百个可供参考的架构实例!

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

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

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

bitly工程团队的Micha GorelickMike 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语言两种实现。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT