申请专栏作者
投稿发布
您的当前位置:主页 > 数据挖掘 > 正文

我们是如何删除 PB 级重复数据的?

来源: 时间:2019-08-01
请点击下面的广告后浏览!

Mixpanel 通过网络从移动端、浏览器端和服务器端的客户接入了千万亿字节的事件数据。由于网络的不可靠性,客户可能会不断重复发送事件请求,直到他们收到来自 Mixpanel 的 200 OK(连接成功)消息。虽然这种重试策略避免了数据丢失,但是在系统中创建了大量的重复事件。对这类重复事件的数据的分析也非常容易产生问题,因为它对所发生的事给出了一个不准确的描述,这也会导致 Mixpanel 偏离其它正在同步的客户端数据系统,如数据仓库。这也是为什么我们非常关心数据完整性的原因。

本文来自可思数据(sykv.com),转载请联系本站及注明出处

今天,我们很高兴在这里分享我们的 PB 级规模的事件数据去重解决方案。 可思数据sykv.com

要求 可思数据sykv.com,sykv.cn

为解决这个问题,我们需要一个能够满足以下要求的方案: 可思数据sykv.com

可扩展性:能够扩展到百万事件 / 秒的接入量
低成本:为接入、存储和查询优化成本 / 性能负载
可追溯性:能够对任意发送的事件进行重复识别
可恢复性:保留重复数据从而在配置错误时可以回滚
可维护性:最小化运营负载

本文来自可思数据(sykv.com),转载请联系本站及注明出处

最新技术:接入 - 时间去重

可思数据sykv.com,sykv.cn

业界有很多富有创造性的方法来解决数据去重问题。其核心策略是在接入层构建一个能够去重的的基础设施。客户发送的每个事件都有一个唯一的 insertid属性标识。数据去重基础设施会将所有事件的insertid属性标识。数据去重基础设施会将所有事件的insert_id 保存一定期限(例如 7 天),期间将会与每个新事件进行匹对,以查找去重标识。键值通常是用存储的分片的 RocksDB 或 Cassandra。通过使用布隆过滤器来优化存储中的查找成本。这种架构能够确保在系统入口点就将重复内容清除。

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

但是,这种方法并不符合我们的要求,原因如下:

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

√ 扩展性:分片键值存储可以水平扩展
× 低成本:需要一个单独的数据库和基础设施来保存重复数据
× 可追溯性:只能抓取一定时间段的重复数据
× 可恢复性:抓取时丢弃数据,不能回滚
× 可维护性:删除重复数据成为一个额外的服务,必须 24x7 不间断

可思数据-人工智能资讯平台sykv.com

我们的方案

可思数据-人工智能资讯平台sykv.com

我们的方案是接入所有事件并在读取时去重,该方案也满足了前面所有的要求。每次查询时,通过构建一个包含所有 $insert_id 的哈希表可以很容易地在读取时实现去重;但是,这会给我们的系统增加一些额外的开销。在详细介绍这个方案之前,让我们先回顾一下 Mixpanel 架构的几个关键技术。

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

Mixpanel 架构

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

基于项目、用户和时间的分片

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

Mixpanel 的分析数据库 Arb 按照项目、用户和时间对数据文件进行了分片。这可以确保指定用户的所有数据都可以共同保存在一个位置,查询时也可以在相关的时间段同时覆盖多个用户。

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

Lambda 架构

可思数据sykv.com

在 Arb 中,所有事件都被写入 AOF(只允许追加的文件),这些文件被周期性地索引(压缩)到后台的柱状文件中。AOF 在达到某个大小或时间阈值时,就会被索引。Arb 通过扫描小型的、实时的 AOF 和大型的、历史的、索引的文件,从而确保查询的实时性和高效性。 本文来自可思数据(sykv.com),转载请联系本站及注明出处

  内容来自可思数据sykv.com

  可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

Mixpanel 架构 可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

我们主要利用架构中的这两类文件来提高读时去重的效率。根据第一准则,重复事件具有以下属性:

可思数据-www.sykv.cn,sykv.com

重复事件属于同一项目
重复事件项属于同一用户
重复事件属于同一事件时间

可思数据sykv.com

根据这些属性特征,我们可以: 可思数据-人工智能资讯平台sykv.com

在搜索空间中搜索项目、用户和日期的重复事件,即搜索单个 Arb 碎片。
通过与 lambda 架构一起摊销来最小化去重开销,从而维护查询的实时和高效。
这帮助我们实现了一个满足所有要求的解决方案。

可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

数据去重架构 可思数据sykv.com,sykv.cn

在 Mixpanel 的基础设施中,在索引和查询时都可以去重。

内容来自可思数据sykv.com

  可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

  可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

Mixpanel 架构

可思数据sykv.com

我们的索引器在内存中维护了一个 hashset,该 hashset 通过 $insert_id 保存了被索引文件中的所有事件。如果某个事件命中,则对该事件设置一个索引格式的重复标记位。这个过程的开销很小,毕竟索引是在细粒度分片级别进行的。 可思数据-人工智能资讯平台sykv.com

查询时,由于使用了 lambda 架构,我们可以同时扫描索引文件和 AOF。对于索引文件,我们可以检查是否设置了重复位,如果设置了,则跳过处理事件。对于那些小的 AOF,查询可以对 $insert_id 基于散列去重。这可以让我们既实时又高效,充分发挥了 lambda 架构的优势。

可思数据sykv.com

性能 可思数据sykv.com,sykv.cn

  可思数据sykv.com,sykv.cn

  本文来自可思数据(sykv.com),转载请联系本站及注明出处

我们从实验中发现,当索引含有 2% 重复的文件时会增加 4% 到 10% 的时间开销。但这并没有对用户体验产生直接影响,因为索引是一个离线过程。

内容来自可思数据sykv.com

对于查询时间,我们发现当额外读取一个事件的标志位时会增加大约 10ns 的时间。由于增加了额外的列,这使查询时间增加了近 2%。每读取 1000 万个事件会增加约 0.1 秒(100 毫秒)的时间开销。作为参考,由于采取了基于项目、用户和时间的分片,Mixpanel 目前最大的柱状文件包含大约 200 万个事件。我们认为在时间成本上的损失是完全可以接受的,因为我们在数据的保留期限和运营成本上都获得了更大的回报。

可思数据-人工智能资讯平台sykv.com

未来工作 可思数据-数据挖掘,智慧医疗,机器视觉,机器人sykv.com

我们的解决方案并不完美,还有以下场景有待改善:事件可能因为分别保存在 AOF 和索引文件而造成重复。我们可以分别在索引文件或 AOF 中识别出重复项,但不能识别出不同文件中的重复。我们之所以选择忽略这种情况,主要原因如下:

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

这种情况极其罕见:99.9% 的客户的数据都非常小,以至于一整天的接入量都可以放入一个 AOF 文件中。这意味着 99.9% 的客户不会受到这个问题的影响。

可思数据sykv.com

对于可能遇到此问题的大数据客户,我们估计一个事件及其重复数据分别保存到两个文件的几率为 0.5%。

可思数据sykv.com

我们的系统会在当日结算时自我修复,当天所有的数据都会重新索引到一个文件中。所以重复数据只会在这一天中短暂出现。

本文来自可思数据(sykv.com),转载请联系本站及注明出处

我们发现,这种方法的优势大大超过了其弊端。未来,我们会实现不同文件间的实时去重以及最近几天文件的数据去重。

可思数据-AI,sykv.com智能驾驶,人脸识别,区块链,大数据

结语

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

在文中,我们讨论了在索引层分发重复标识和在查询层分发重复过滤的架构。这个方案已经在 Mixpanel 内部成功运行了 6 个月的时间。

可思数据sykv.com,sykv.cn

原文链接:https://engineering.mixpanel.com/2019/07/18/petabyte-scale-data-deduplication/

可思数据-AI,sykv.com人工智能,深度学习,机器学习,神经网络

网友评论:

发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片

关于我们   免责声明   广告合作   版权声明   联系方式   原创投稿   网站地图  

Copyright©2005-2019 Sykv.com 可思数据 版权所有    ICP备案:京ICP备14056871号

人工智能资讯   人工智能资讯   人工智能资讯   人工智能资讯

扫码入群
咨询反馈
扫码关注

微信公众号

返回顶部
关闭