usb接口,大数据分析中常见的重复数据消除算法分析-安博电竞网站-安博电竞app下载-安博电竞手机版

西甲联赛 411℃ 0

去重剖析在企业日常剖析中的运用频率十分高,如安在大数据场景下快速地进行去重剖析一向是一大难点。在近期的 Apache Kylin 沙龙上, Kyligence 大数据研制工程师陶加涛为咱们揭开了大数据剖析常用去重算法的奥秘面纱。作者:陶加涛

首要,请咱们考虑一个问题:在大数据处理领域中,什么环节是你最不期望见到的?以我的观念来看,shuffle 是我最不乐意见到的环节,因为一旦呈现了十分多的 shuffle,就会占用许多的磁盘和网usb接口,大数据剖析中常见的重复数据消除算法剖析-安博电竞网站-安博电竞app下载-安博电竞手机版络 IO,然后导李仰珍致使命进行得十分缓慢。而今日咱们所评论的去重剖析,便是一个会发作十分多 shuffle 的场景,先来看以下场景:

咱们有一张产品拜访表,表上有 item 和 user_id 两个列,咱们期望求产品的 UV,这是去重十分典型的一个场景。咱们的数据是存储在散布式平台上的,别离在数据节点 1 和 2 上。

咱们从物理履行层面上想一下这句 SQL 背面会发作什么故事:首要散布式核算结构发动使命, 从两个节点上去拿数据, 因为 SQL group by 了 item 列, 所以需求以 item 为 key 对两个表中的原始数据进行西湖牛肉羹一次 shuffle。咱们来看看需求 shuffle 哪些数据:因为 select/group by 了 item,所以 item 需求 shuffle 。可是,user_id 咱们只需求它的一个核算值,能不能不 shuffle 整个 user_id 的原始值呢?

假如仅仅简略的求 count 的话, 每个数据节点别离求出对应 item 的 user_id 的 count, 然后只需 shuffle 这个 count 就行了,因为 count 仅仅一个数字, 所以 shuffle 的量十分小。可是因为剖析的目标是 count distinct,咱们不能简略相加两个节点 user_id 的 count distinct 值,咱们只要得到一个 key 对应的一切 user_id 才干核算出正确的 count distinct 值,而这些值原先或许散布在不同的节点上,所以咱们只能经过 shuffle 把这些值收集到同一个节点上再做去重。而当 user_id 这一列的数据量十分大的时分,需求 shuffle 的数据量也会十分大。咱们其实终究只需求一个 count 值,那么有方法能够不 shuffle 整个列的原始值吗?我下面要介绍的两种算法就供给了这样的一种思路,运用更少的信息位,相同能够求出该列不重复元素的个数(基数)。


准确算法: Bitmap

榜首种要介绍的算法是一种准确的去重算法,首要利用了 Bitmap 的原理。Bitmap 也称之为 Bitset,它本质上是界说了一个很大的 bit 数组,每个元素对应到 bit 数组的其间一位。例如有早晨插母亲一个调集[2,3,5,8]对应的 Bitmap 数组是[001101001],调集中的 2 对应到数组 index 为 2 的方位,3 对应到 index 为 3 的方位,下同,得到的这样一个数组,咱们就称之为 Bitmap。很直观的,数组中 1 的数量便是调集的基数。追根究底,咱们的光速是多少意图是用更小的存储去表明更多的信息,而在核算机最小的信息单位是 bit,假如能够用汪永芳一个 bit 来表明调集中的一个元素,比起原始元素,能够节约十分多的存储。

这便是最根底的 Bitmap,咱们能够把 Bitmap 幻想成一个容器,咱们知道一个 Integer 是 32 位的,假如一个 Bitmap 能够寄存最多 Integer.MAX_VALUE 个值,那么这个 Bitmap 最少需求 32 的长度。一个 32 位长度的 Bitmap 占用的空间是 512 M (2^32/8/1024/1024),这种 Bitmap 存在着十分显着的问题:这种 Bitmap 中不管只要 1 个元素或许有 40 亿个元素,它都需求占有 512 M 的空间。回到方才求 UV 的场景,不是捷安特每一个产品都会有那么多的拜访,一些爆款或许会有上亿的拜访,可是一些比较冷门的产品或许只要几个用户阅览,假如都用这种 Bitmap,它们占用的空间都是相同大的,这显然是不行承受的。


升级版 Bitmap: Roaring Bitmap

关于上节说的问题,有一种规划的十分的精巧 Bitmap,叫做 Roaring Bitmap,能够很好地处理上面说的这个问题。咱们仍是以寄存 Integer 值的 Bitmap 来举例,Roaring Bitmap 把一个 32 位的 Integer 划分为高 16 位和低 16 位,取高 16 位找到该条数据所对应的 key,每个 key 都有自己的一个 Container。咱们把剩下的低 16 位放入该 Container 中。依据不同的场景,有 3 种不同的 Container,别离是 Array Container、Bitmap Container 和 Run Container,下文将逐个介绍。

首要榜首种,是 Roaring Bitmap 初始化时默许的 Container,叫做 Array Container。Array Container 合适寄存稀少的数据,Array Container 内部的数据结构是一个 short array,这个 array 是有序的,便利查找。数组初始容量为 4,数组最大容量为 4096。超越最大容量 4096 时,会转换为 Bitmap Container。这边举例来说明数据放入一个 Array Container 的进程:有 0xFFFF0000 和 0xFFFF0001 两个数需求放到 Bitmap 中, 它们的前 16 位都是 FFFF,所以他们是同一个 key,它们的后 16 位寄存在同一个 Container 中 ; 它们的后 16 位别离蜘蛛侠2是 0 和 1, 在 Array Container 的数组中别离保存 0 和 1 就能够了,相较于原始的 Bitmap 需求占用 512M 内存来存储这两个数,这种寄存实践只占用了 2+4=6 个字节(key 占 2 Bytes,两个 value 占 4 Bytes,不考虑数组的初始容量)。

第二种 Container 是 Bitmap Con父女合体tainer,其原理便是上文说的 Bitmap。它的数据结构是一个 long 的数组,数组容量固定为 1024,和上文的 Array Container 不同,Array Container 是一个动态扩容的数组。这边推导下 1024 这个值:因为每个 Container 还需处理剩下的后 16 位数据,运用 Bitmap 来存储需求 8192 Bytes(2^16/8), 而一个 long 值占 8 个 Bytes,所以总共需求 1024(8192/8)个 long 值。所以一个 Bitmap container 固定占用内存 8 KB(102易信4 * 8 Byte)。当 Array Container 中元素到 4096 个时,也刚好占用 8 k(4096*2Bytes)的空间,正好等于 Bitmap 所占用的 8 KB。而当你寄存的元素个数超越 4096 的时分,Array Container 的巨细占用仍是会线性的添加,可是 Bitmap Container 的内存空间并不会添加,一向仍是占用 8 K,所以当 Array Container 超越最大容量(DEFAULT_MAX_SIZE)会转换为 Busb接口,大数据剖析中常见的重复数据消除算法剖析-安博电竞网站-安博电竞app下载-安博电竞手机版itmap Container。

咱们自己在 Kylin 中实践运用 Roaring Bitmap 时,咱们usb接口,大数据剖析中常见的重复数据消除算法剖析-安博电竞网站-安博电竞app下载-安博电竞手机版发现 Array Contusb接口,大数据剖析中常见的重复数据消除算法剖析-安博电竞网站-安博电竞app下载-安博电竞手机版ainer 跟着数据量的添加会不停地 resize 自己的数组,而 Java 数组的 resize 其实十分耗费功能,因为它会不停地请求新的内存,一起老的内存在仿制完结前也不会开释,导致内存占用变高,所以咱们主张把 DEFAULT_MAX_SIZE 调得低一点,调成 1024 或许 2048,减米莉波比布朗少 Array Container 后期 reszie 数组的次数和开支。

终究一种 Container 叫做 Run Container,这种 Container 适用于寄存接连的数据。比方说 1 到 100,总共 100 个数,这种类型的数据称为接连的数据。这边的 Run 指的是 Run Length Encoding(RLE),它对接连数据有比较好的紧缩作用。原理是关于接连呈现的数字, 只记载初始数字和后续数量。例如: 关于 [11, 12, 13, 14, 15, 21, 22],会被记载为 11, 4, 21, 1。很显然,该 Container 的存储占用与数据的散布严密相关。最好状况是假如数据是接连散布的,就算是寄存 65536 个元素,也只会占用 2 个 short。而最坏的状况便是当数据悉数不接连的时分,会占用 128 KB 内存。

总结:用一张图来总结 3 种 Contain特别污的日本漫画图片er 所占的存储空间,能够看到元素个数到达 4096 之前,选用 Array Container 的收益是最好的,当元素个数超越了 4096 时,Array Container 所占用的空间仍是线性的添加,而 Bitmap Contai男变女ner 的存储占用则与数据量无关,这个时分 Bitmap Container 的收益就会更好。而 Run Container 占用的存储巨细彻底看数据的接连性, 因而只能画出一个上下限规模 [4 Bytes, 128 KB]。


在 Kylin 中的运用

咱们再来看一下 Bitmap 在 Kylin 中的运用,Kylin 中修改 measure 的时分,能够挑选 Count 金瓶双艳Distinct,且 Return Type 选为 Precisely,点保存就能够了。可是工作没有那么简略,方才上文在讲 Bitmap 时,一向都有一个条件,放入的值都是数值类型,可是假如不是数值类型的值,它们不能够直接放入 Bitmap,这时需求构建一个全区字典,做一个值到数值的映射,然后再放入 Bitmap 中。

在 Kylin 中构建大局字典,当列的基数十分高的时分,大局字典会成为一个功能的瓶颈。针对这种状况,社区也一向在尽力做优化,这边简略介绍几种优化的战略,更详细的优化战略能够见文末的参阅链接。

1)当一个列的值彻底被别的一个列包括,而另一个列有大局字典,能够复用另一个列的大局字典。

2)当准确去重目标不需求跨 Segment 聚合的时分,能够运用这个列的 Segment 字典替代(这个列需求字典编码)。在 Kylin儿子小说 中,Segmusb接口,大数据剖析中常见的重复数据消除算法剖析-安博电竞网站-安博电竞app下载-安博电竞手机版ent 就相当于时刻分片的概念。当不会发作跨 Segments 的剖析时,这个列的 Segment 字典就能够替代这个大局字典。

3)假如你的 cube 包括许多的准确去重目标,能够考虑将这些目标放到不同的列族上。不止是准确去重,像一些杂乱 measure,咱们都主张运用多列族去存储,能够提高查询的功能。

尽管 Roaring Bitmap 这种算法能大大地削减存储开支,可是跟着数据量的增大,它仍然面临着存储上的压力。下面我石琼磷们即将介绍的 HyperLogLog(下称 HLL)是一种非准确的去重算法,usb接口,大数据剖析中常见的重复数据消除算法剖析-安博电竞网站-安博电竞app下载-安博电竞手机版它的特点是具有十分优异的空间杂乱度(简直能够到达常数等级)。

HLL 算法需求完好遍历一切元素一次,而非屡次或采样;该算法只能核算调集中有多少个不重复的元素,不能给出每个元素的呈现次数或是判别一个元素是否之前曲阜天气预报呈现过;多个运用 HLL 核算出的基数值能够交融。

HLL 算法有着十分优异的空间杂乱度,能够看到它的空间占用跟着基数值的添加并没有改变。HLL 后边不同的数字代表着不同的精度,数字越大,精度越高,占用的空间也越大,能够以为 HLL 的空间占用只和精度成正相关。


HLL 算法原理理性认知

HLL 算法的原理睬涉及到比较多的数学知识,这边对这些数学原理和证明不会打开。举一个日子中的比如来协助咱们了解 HLL 算法的原理:比方你在进行一个试验,内容是不停地抛硬币,记载你接连抛到正面的次数(这是数学中的伯努利进程,感兴趣同学能够自行研讨下);如毕淑敏果你最多的连抛正面记载是 3 次,那能够幻想你并没有做这个试验太屡次,假如你最长的连抛正面记载是 20 次,那你或许进行了这个试验上千次。

一种理论上存在的状况是,你十分走运,榜首次进行这个试验就连抛了 20 次正面,咱们也会以为你进行了许屡次这个试验才得到了这个记载,这就会导致过错的预估;改善的方法是请 10 位同学进行这项试验,这样就能够观察到更多的样本数据,下降呈现上述状况的概率。这便是 HLL 算法的中心思维。


HLL 算法详细完成

HLL 会经过一个 hash 函数来求出调集中一切元素的 hash 值(二进制表明的 hash 值,就能够了解为一串抛硬币正反面成果的序列),得到一个 hash 值的调集,然后找出该 hash 值调集中,榜首个 1 呈现的最晚的方位。例如有调集为 [010, 100, 001], 调集中元素的榜首个 1 呈现的方位别离为 2, 1, 3,能够得到里边最大的值为 3,故该调集中榜首个 1 呈现的最晚的方位为 3。因为每个方位上呈现 1 的概率都是 1/2,所以咱们能够做一个简略的揣度,该调集中有 8 个不重复的元素。

能够看到这种简略的揣度核算出来调集的基数值是有较大的差错的,那怎么来削减差错呢?正如我上面的比如里说的相同,HLL 经过屡次的进行试验来削减差错。那它是怎么进行屡次的试验的呢?这儿 HLL 运用了分桶的思维,上文中咱们一向有说到一个精度的概念,比方说 HLL(10),这个 10 代表的便是取该元素对应 Hash 值二进制的后 10 位,核算出记载对应的桶,桶中会记载一个数字,代表对应到该桶的 hash 值的榜首个 1 呈现的最晚的方位。如上图,该 hash 值的后 10 位的 hash 值是 0000001001,转成 10 进制是 9,对应第 9 号桶,而该 hash 值榜首个 1 呈现的方位是第 6 位,比原先 9 号桶中的数字大,故把 9 号桶中的数字更新为 6。能够看到桶的个数越多,HLL 算法的精度就越高,HLL(10) 有 1024(210) 个桶,HLL(16) 有 65536(216) 个桶。相同的,桶的个数越多,所占用的空间也会越大。

方才的比如咱们省掉了一些细节,为了让咱们不至于迷失在细节中而忽视了要点,实在的 HLL 算法的完好描绘见上图,这边的要点是核算桶中平均数时运用谐和平均数。谐和平均数的长处是能够过滤掉不健康的核算值,运用算术平均值简略遭到极值的影响(想想你和马云的平均工资),而谐和平均数的成果会倾向于调集中比较小的元素。HLL 论文中还有更多的细节和参数,这边就不逐个细举,感兴趣的同学能够自己阅览下论文。


HLL 评价

HLL 的差错散布遵守正态散布,它的空间杂乱度: O(m log2log2N), N 为基数, m 为桶个数。这边给咱们推导一下它的空间杂乱度,我有 264 个的不重复元素 (Long. MAX_VALUE),表达为二进制一个数是 64 位,这是榜首重 log2, 那么榜首个 1 最晚或许呈现在第 64 位。64 需求 6 个 bit (26=64) 就能够存储,这是第二重 log2。假如精度为 10,则会有 1024 个桶,所以最外面还要乘以桶的女男人个数。因为需求完好的遍历元素一遍,所以它的时刻杂乱度是一个线性的时刻杂乱度。


在 Kylin 中的运用

在 Kylin 中运用 HLL 十分简略,在修改衡量的页面挑选 COUNT DISTINCT,Return Type 选为非 Precisely 的其他选项,咱们依据自己的需求挑选不同的精度就能够愉快地运用了。


总结

咱们回到最开端的去重场景,看看运用了 Bitmap 和 HLL 会给咱们带来什么增益:无优化 case 下,每个 item 对应的 user_id 就能够当作存储原始值的一个调集;在运用 Bitmap 优化的 case 下,每个 item 对应的 user_id 就能够当作一个 Bitmap 实例,同理 HLL 便是一个 HLL 的实例,Bitmap/HLL 实例占用的空间都会比直接存储原始值的调集要小,这就到达了咱们开端提的削减 shuffle 数据量的需求。


Q&A

Q1:您好,问一下关于准确去重的问题, 我挑选了非准确去重,终究的差错率有时分会比界面上提示的值要高一些,这是为什么?

A1:首要 HLL 的差错散布遵守正态散布,也便是说是在 99% 的状况下是这个差错,一起 HLL 关于基数比较低的状况,差错会偏高。假如你的基数比较低的话,我引荐运用准确去usb接口,大数据剖析中常见的重复数据消除算法剖析-安博电竞网站-安博电竞app下载-安博电竞手机版重。

Q2:我想要了解一下 Bitmap 在 Kylin 中,它终究落盘在 HBase 里边是什么姿态的?

A2:在 HBase 中存储的当然都是 Bytes。这个问题其实便是 Bitmap 的序列化的方式,Roaring Bitmap 供给了序列化和反序列化的完成,你也能够写自己的序列化 / 反序列化的完成。

Q3:Roaring Bitmap 里这些 container 要咱们自己手动的指定吗?

A3:不需求,Roaring Bitmap 会主动挑选运用哪个 Container。

作者:陶加涛,Kyligence 大数据研制工程师,电动四轮车价格首要担任 Kyligence Enterprise 存储与查询核算部分。