阿里云飞天发布时刻,领先大模型限免,超7000万 tokens免费体验 了解详情
写点什么

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

  • 2013-02-21
  • 本文字数:2288 字

    阅读完需:约 8 分钟

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 语言两种实现。

2013-02-21 08:441472
用户头像

发布了 479 篇内容, 共 171.3 次阅读, 收获喜欢 52 次。

关注

评论

发布
暂无评论
发现更多内容

软件开发

Geek_8da502

软件测试/测试开发丨从原理到实战,四天带你轻松进阶Python

测试人

软件测试

通过智能钱包监控降低加密交易费用

Footprint Analytics

区块链 加密货币

Meta推出大模型开源项目Llama 2

百度开发者中心

人工智能 大模型 LLM

让数据同步纵享丝滑,ETLCloud安装指南

RestCloud

ETL

iOS应用如何签名?使用xcode签名的办法和工具 附xcode14下载安装包

南屿

Xcode Mac版 应用签名 Xcode签名

云组态是什么?云组态软件特点及应用

2D3D前端可视化开发

物联网 可视化 组态软件 工业自动化 云组态

MatrixOne 1.1.0 Release

MatrixOrigin

分布式数据库 云原生数据库 MatrixOrigin MatrixOne 超融合数据库

每日一题:LeetCode-695. 岛屿的最大面积

Geek_4z9ami

Go 面试 算法 矩阵 LeetCode

SD-WAN组网方式详解

Ogcloud

网络 SD-WAN 组网 组网网络

macOS 14 Sonoma(最新MacOS系统) pkg完整安装包 14.2正式版

南屿

苹果系统下载 macOS 14 Sonoma

微店商品详情数据接口(micro.item_get)丨微店API接口

tbapi

微店API接口 微店商品详情API接口 微店商品数据接口

引领功能型对话大模型的部署实践革新

百度开发者中心

人工智能 nlp ChatGPT

利用虚拟线程重写自定义异步功能

FunTester

什么是制造业中的数字孪生?

3D建模设计

3D场景应用 3D场景建模 3D数字孪生场景编辑器 3D场布工具

使用 Parallels Desktop 彻底改变您的开发和测试工作流程

南屿

Mac虚拟机 Parallels Desktop 18破解 Parallels Desktop 19

Beyond Compare4 for Mac怎么使用?Beyond Compare功能特点详解

南屿

Mac软件 Beyond Compare 4 注册版 Beyond Compare注册码 文件夹比较工具

解读 | Mint Blockchain 为何选择 OP Stack 作为 L2 技术方案?

NFT Research

blockchain NFT\ Layer 2

【第七在线】时尚鞋服企业商品运营如何实现智能化?

第七在线

软件测试/测试开发丨软件测试基础概念 学习笔记

测试人

软件测试 测试开发

MatrixOne 完成与飞腾处理器的兼容互认

MatrixOrigin

分布式数据库 云原生数据库 MatrixOrigin MatrixOne 超融合数据库

Bit.ly发布Forget-Table,解决非稳定类别分布问题_架构_郑柯_InfoQ精选文章