018_尚硅谷大数据技术_用户行为数据分析Flink项目_UV统计（二）_布隆过滤器原理

我们前面已经用一个set数据结构做了一个UV统计的简单实现，那其实大家也发现了，这种统计方式呢，比较简单，但是它是有缺陷的，那就是我们用赛的数据结构，相当于是把这里的数据全部存在内存里面去了啊，当然呃，有同学可能看到我当前这个全窗口函数前面我们是把所有的这个user behavior都存到内存里了，对吧？啊，这种方式当然是不可取的，这个不是特别好啊，我们至少是可以比方说我们做一个增量聚合，就是不要把所有数据存起来，是不是只要有一个这个ID set就可以了，对吧？只要把那个所有的user ID，然后提取出来存到一个set数据结构就可以了，但是大家想这个set数据结构要存的user ID如果多的话，是不是相当于这个我们对内存的压力也很大呀。你相当于要把所有的uz ID都得放下来嘛，在有一些场景下，如果说uz ID足够多的话，放在内存里边显然就不是一个非常好的选择了啊，那怎么样去解决这个问题呢？首先大家能想到的就是我可以放在里吧，放在red里边，呃，然后用一个set数据结构去做一个去重啊，然后来一个我就去连接那个，对，对应的那个，呃，Red里面保存的那个set数据结构啊，我们连接之后查做一个查询，然后做一个判断啊，这样的话就可以实现这个功能，这是一个基本的想法，但是有一些极端的场景下。

这个red里边直接去放可能也是放不下的，比如说呃，像这个极端的场景就是如果是上亿个user ID的话。大家想一下，当前我们需要多大的空间去做存储呢？这里可能可能我们需要去算一笔账啊，大概的来琢磨一下，这个数据量大概有多大啊，那大家可能知道，一般情况我们提取出来的这个日志数据啊，一条数据应该整呃，大概的一个大小有多少呢。

可能要达到，呃，就是大到几百个字节，或者是1KB这样的一个级别，对吧？呃，大概大概是这样一个级别，那里边如果说我们要提取这个user ID的话，那应该大概是什么级别。那可能就是几十个字节到100个字节这样的一个一个级别，对吧？啊，所以假如说我们用这个以这个100个bit。呃个BAT啊，字节对吧，大B啊，100个BATBAT作为一个user ID的存储长度的话，那接下来如果说我们要有1亿个用户，那大家想我们要存多少。1亿是十的八次方对吧，然后每一个要占100个字节，那总共就应该是十的十次方个字节。好，那所以大家想一下十的十次方啊，如果按照我们的一般这个存储空间的这个划分的话，十的三次方大概就是1024，那1024个呃字节的话其实就是1KB嘛，对吧？那如果要是十的六次方，但这个不太准啊，因为有一个1000和1024的换算对吧，不太准，我们就是大概的估算，那十的六次方，那是不是就是大概就是一兆了，对吧？啊，那如果要是十的九次方大概就是一个G，那现在十的十次方大概就是对大概它是。

十个GB。哎，所以大家想象一下，十个GB如果要是放在内存里面，这不可想象是吧，我们这个内存本来才多少，你直接花十个GB，注意这还是如果我们要统计的话，这是不是相当于只只是一个窗口里面的状态啊。一个窗口一个任务，而且是一个窗口里边的状态就存了十个G啊，所以这个显然是呃，不能不能去实现的啊，那有同学可能想我丢到red里边，Red里边你直接存十个G，就专门用来保存一个窗口里边的状态，这也有点太奢侈了是不是？

诶，这这个感觉就好像也不能接受，那怎么办呢？接下来怎么做优化呢。啊，所以大家就自然想到了，我们现在就不太适合用这个存储啊，不同的存储工具去做扩展了，而是应该从本身存放的数据结构和算法上做一个调整，做一个优化，这里面给大家要讲的一个优化方式就是。布隆过滤器，哎，我们可以用一个比较特殊的数据结构去实现这样一个功能，那布隆过滤器的基本想法是什么呢？简单来讲的话，就是它里边要存储的是一个很大的一个位图，诶大家知道这个什么叫做位图呢？位图就是里边存储的就是。就是一个一个的beat对不对，10101010这样的这样的一组beat啊啊，所以整个合起来的话，有时候我们就直接把它叫做一个bit map，所以有时候翻译就直接翻译成叫做壁图，呃，那个位图对吧，位图呃，那么布隆过滤器里边，它主要的存储结构就是这样的一个东西。

那所以它的基本思想是什么呢？就是用这个位图里边的每一位零和幺的那个状态来表示我们当前某一个user ID是否存在，那大家想，如果做了这样一个对应关系的话，是不是就相当于一个user ID？这里面就会对应着这里的每某一位啊，如果它里边是零的话，我就表示它不存在，对吧？如果是一的话，就表示它存在，那大家想最后这样的话，我是不是只要统计一下这个bitmap里边有多少个一，是不是就代表我到底有多少user啊？

哎，所以这就是非常简单的一种实现啊，就是考虑到就是把这个user ID相当于做了一个压缩的对应，对不对，按照这样一个存储的话，是不是相当于之前我们100个bitt这样的一个100字节的一个UID是不是就相当于压缩成了一位啊，就变成了一个bit，对吧，那大家想一下，如果按照这个想法。我们最后1亿个UID想要把它存储下来的话，做驱虫的话，我们占用的空间大概是多大？啊，那就相当于是不是由1亿个100个字节变成了1亿个1亿个way啊，1亿个bit对不对啊，一个用户占一个字节就够了嘛，所以我们最后其实只需要占用十到八次方个bit，这大概是多大呢？哦，那大家知道就是，呃，首先这个就大概是一百一百兆，注意是小对吧，100兆bit，那么转换成字节的话，那是不是还要再除以八呀，所以就大概只有十几对啊，大概这个大家可能知道12.5啊，这个直接除下来是12.5，但是这个不准啊。

我们这里边大概就是十几的大壁照壁。所以十几兆一个窗口，这个看起来就很容易搞定了，对吧？啊，这个就是我们存在哪都没什么问题了啊呃，存在这个内存里边，呃是有点大，但是其实好像也没问题，能够存的下来，但是大家就会想到用这种存储方式的话。这个前提是什么？是不是每一个user ID必须要严格意义上对应这里面的一位啊？那大家想，我怎么知道一个user ID来了之后，它到底对应哪一位呢？这个对应关系又是怎么样去决定的呢？

诶，那这这个就是布隆过滤器里边另外一个非常重要的重要的这个原理，那就是它这里边用一个哈希计算去做一个对应关系的选择，所以这里面其实有一个哈希操作的。那大家能想到这个基本原理是什么吗？是不是就是user ID来了之后，我求一个它的哈希值，这是不是就得到了一个数字，数字啊，得到得到了一个数，那这个数对应在这个位图里面，应该就是个什么东西呢？我是不是把这个位图可以看成零幺，零幺这个位的一个数组啊，然后我把这个哈希值当成它对应的一个偏移量，是不是就可以找到对应这个数组对应的一位置上到底是一还是零啊？哎，所以这就是这个布轮过滤器，布轮过滤器的一个原理，它里边最重要的结构就是一个位图。就是相当于按照顺序存储的位的一个数组，另外还有就是一个哈希函数，我们定义了哈希函数之后，那就可以把一个你自己想要做这个保存做驱重的一个值啊，可以是UID，也可以item ID，对吧，什么都可以，只要来了之后可以把它当成一个字符串，那接下来用一个哈希求得一个长整形的或者一个int类型的值，那么这个值就是位图中的偏移量，或者说它的对应的那个position位置。

那么根据这个位置，我是不是就可以直接就可以找到对应的这个位啊，快速就能找到这个位对吧？然后接下来就可以判断它到底在不在里边了啊，这就是不明过滤器的基本原理，那当然了，这里面大家其实发现一个问题，就是说如果是哈希的话。这里边其实是有问题的，是不是我不同的UID来了之后，有可能会出现对哈希之后是不是一样的呀，这就是我们所说的这个哈希碰撞对吧？啊，就哈希冲突这样的一个问题，那怎么样去解决这个问题呢？啊，一种方式是你把这个哈希函数选的好一点，对吧？哈希函数如果选的足够好的话，当然这个碰撞概率就小，但大家想假如说啊，假如说我现在就是。

一一亿个UID，然后你就给了1亿个V，那你说这个这个碰撞概率是不是极高啊，对吧，因为它只有严格意义上你一点问题都不出，让他一个就就单独的对应一个啊，就全部排开，这才不不会出现冲突，你稍微这个这个散裂的时候，稍微出现一点问题，它就撞在一起了，对吧？所以另外我们还有一一个思路是什么呢？怎么样减降低它的这个碰撞率呢。我是不是可以把这个bit map位图再扩充一点啊，啊对吧，所以大家就想到了，我这里边十几兆放放这个，这个碰撞概率太高，那我比方说我把它扩个四倍、八倍，十几倍，对吧，我用一个几十兆或者100多兆的这样这样一个位图来保存处理这个1亿个1亿个数据的冲突的话，那是不是这个碰撞概率就很小了，相当它就全部分散开了，对吧？啊所以这里边基本的一个原则就是这里边我们想要去就是处理的这个最最大的优化的一个点就是一个是哈希函数的选取，另外一个就是位图大小的一个扩充，对吧？啊原理论上来讲的话，哈希函数足够复杂，然后你的位图又足够大，其实我们这个碰撞的概率可以无限趋近于零，对吧，但是大家注意它不会完全为零，因为从理论上来讲，我们这里边是不是总会有出现碰撞的概率啊，对吧？啊，所以大家注意就是对于这个。

布隆过滤器而言，它其实是一个概率型的数据结构，来告诉你某样东西一定不存在或者可能存存在，这是什么意思？哎，这这就是我们说的，如果哈希碰撞的话，它主要的问题就出在这个哈希碰撞对吧，那假如说我们这里边的这个假如说啊，这个用户一和这个USER2啊。

他俩经过哈希之后得到结果都是这这个位置对吧，都是这个offset，那大家其实会发现，假如说我现在这个U2来了啊，然后发现这一位是零，那其实可以说明什么呢？U2来过没有啊。U2是不是肯定没来过啊，不光U2没来过，是不是U1都没来过啊，对吧？所以我可以假如说这一位是零的话，我可以拍着胸脯保证它一定不存在，对吧，一定没来过，但如果这一位是一的话。哎，那就没准了，那是不是什么情况下，就是有可能他没来过，但是这里是一呢，对大家想，因为他有哈去碰撞嘛，他俩如果真的碰上了的话，那是不是U1来过，这一位就是一啊，U2没来过，他也以为自己来过了，对吧？哎，所以在这种场景下就会出现一些错误啊，所以我们一般在实际场景下呢，就是你可以去应用一些现成的布隆过滤器这样的一个数据结构，比方说像谷歌的这个瓜网啊，这个这样一个呃，一个一个库，它里边就提供了很多现成的数据结构和算法，里边就有布隆过滤器，那么它里边主要其实是什么呢？你你可以配置的时候就传一个什么，传一个就是相当于就是你所容忍的碰撞概率就可以啊，它默认应该是0.03啊啊，就相当于零点默认碰撞概率0.03什么意思，就相当于对我99.7%的概率，是不是他们根本不会。

碰在一起啊，所以至少我有百分之九十九九点七的把握，我最后的结果是完全正确的，对吧，只有那0.03%这种小概率出现的时候，才会导致我最后的结果有可能统计不正确啊，所以这是就是我们平常啊使用这个布隆过滤器的一个基本原理，所以接下来我们就可以用布隆过滤器实现一个UV驱虫的优化。