00:00
好,各位同学快速的复习了一下hyper log log的基操命令,Red的常用命令,那个简单就是三条命令的事,那接下来hyper log log的原理,它是如何做到的?它是如何演化出来的?它有什么优缺点?好,那么同学们。基数统计,咱们用hyper log log去重复以后的统计数,计算方法用它,那么假设我现在给你个诉求,就是去重复统计,也就不能有重复。按照Java程序员的想法,你会想到哪些方法?请大家思考一下。感谢各位同学的讨论,那最经典的去重复弟兄们,你做一个Java程序。最快的最自然的应该想到是不是应该有种数据结构叫哈西set呀,那么是不是无序无重复啊,那最经典啊,弟兄们,我们来这么看第一个,那么假设这个呢,是我们的一个a list,弟兄们,这个我相信的大家呢,没有任何问题对吧?好,那么这一个list子我们这啊我们的IP假设是22.10.11.1对不对,然后呢,幺九二点幺六八点幺幺幺点。
01:24
二那么再来,比如说这就是192.168.111.2,这个人又登录了一次,然后呢,是幺九二点幺六八点07:51等等等等,那么请告诉我,我们现在呢,就记录了今天谁登录了我。那么假设现在有四个,那么我们认为这个IP就是同一个UV,同一个用户,那么请问怎么把这个list去除?那最经典,弟兄们是不是学过一种东西叫哈希set,这个我不用多解释吧,弟兄们,那你告诉我哈西塞的构造方法里面是不是有专门有这么一个传进来一个什么鬼,是不是collection就是可以天生的,就可以把我们的这个list里面的元素给它干掉,重复的。
02:18
去掉以后形成一个新的哈希赛特,弟兄们,这个是不是最基本功中的基本功,也就是说你作为一个Java程序员,如果以后跟你说去重重复,那么肯定是多条记录,多条记录自自然而然要装到一个容器,是不是就应该装到一个数组里面,然后哈西塞拿过来去个重复搞定,所以弟兄们,这个呢,是我们的东道最经典的。那接下来我们呢?Bit map啥意思啊?来吧,弟兄们,请看一眼我们现在啊,搁到这去重复啊,有没有看过,登没登录这样的,如果数据显示较大,一级统计,那么使用。
03:06
Bit map同样会遇到一些相关的问题,那啥意思啊,弟兄们?我这是四条,如果这个耳朵列存里面有四个亿呢,就是数据量小的时候,我们用这样的方法先装起来,把所有数据搞一个全集装起来,然后再用一些数据结构的特性给它去除,思路没有错,但是最坑爹的是什么量变引起了我们的质变,同意吗?对呢,各位同学,我们这样的话就是小范围呢可以统计,那么大了以后弟兄们来吧,Bit map也可以啊,我们来做个映射也好,或者反正这个IP反问了就是个一,没有反问就是零。那么来bit map通过用为比特四组来表示各个元素是否出现,那么这个元素可以是地址,可以是用户编号,可以是IP,每个元素对应一位,那么所需的总类存数就是N个比特位,那么基数统计的话呢,我们呢,将每一个元素,那么假设每一个访问的IP对应到比特数组中的。
04:10
其中的一位,比如比特数组010010101,那么按照从零下面开始,那么就是146801,有人反问。234有人反问,那么五六有人反问,七八有人反问,那么假设1468就对应着一号位存的假设就是某个IP,四号位存的假设又是另外一个I,这样听懂了吧?那么这样的话呢?新进入的元素。只需要将已经有的IP数组和心障元素进行为这样的计算,就知道他有没有反问过,对吧?那么操作起来当然要比便利一个list要快。但是下面这个问题是,假设一个样板案例是1亿个激素。也就说1亿位,那爽死你了,弟兄们露眼。
05:01
如果我们用这种数据结构来记录,你要是记录一家公司三万人今天有没有打卡登录,用它是可以,但是用它来统计我们的这张首页。一级流量的访问量,我们要统计一个亿的数据位置啊,需要一算12兆内存减少占用的效果就非常显著,就是比起我们的啊,你说那杨杨哥一个亿也不大呀,12兆吗?给得起。这样我们得到一个统计对象的样本基数,12兆B,好。如果我现在是1万个亿级。1万亿,那么就需要120个G,可见我这个bit map不大适合大数据下面的这样的基数统计的。由此可见,对于我们的bit map。你存少一点比百万级别以内的也可以,但是只要是一级的这样的基数统计他又有点持不住,但是呢,Bit map的好处是方法是精确计算的,那举个案例啊,就是我们刚刚。
06:12
所说的我们呢可以去做哈西上呢去做一个分配,假设一就对标的是22.16.21153这个IP第四位,那么假设就是192.168.111.5,那么第六位,那么就是幺九二点。五十二点零点幺幺七等等,那我们来判断这个IP它有没有反卖,我们就去看某个bit map,这个K下面的第六位有没有,有就说明他反问了,没有就说明他没反问,那么有这么一张映射表,我们也可以非常明白这个每一位对应的是哪个IP,哪个IP有就是反问,没有就没反问,所以它的方法是存数据,是精确计算过,确确实实实有这些数据的,但是多少120G,那么所以说弟兄们样本元素越多,内存消耗就急剧增大,难以管控,加各种慢,对于一级统计是不太合适的,大数据是会害死人,因为量变会引起质变,那接下来。
07:22
我们怎么办呢?来只能用一种概率算法,弟兄们,请看我们通过牺牲什么性准确率来换取空间,你不用给我记那么精确了,哎,大差不差啊,比如说。今天的流量是一个亿啊,约1亿。前面讲过,到底是9990、99947,还是9990、99812。有这么一点数据上的差距,无所谓,我们都叫约1亿就行了,所以我们这儿就是对于不要求绝对准确率的场景下,可以使用淘宝的首页,对吧,我们不要求绝对精确,它不是像是银行系统那个钱错一分钱都不行。
08:10
因为首页上的统计嘛,可以有点打个马虎眼,不用那么精确,因为概率算法不直接存储数据,本身通过一定的概率统计方法得到一个预估的基数值,去重以后的同时保证误差在一定范围内可接受,那么也不存储数据,所以它大大的节约了内存,那么还log log就是一种概率算法的体现,这个也就是它的原理。最重要的值得我们去关注的底层细节。下面简单的给大家说一下hyper log log的原理,它是如何牺牲一定的准确度,允许在一定的误差范围以内来进行激素的去重统计来,同学们。首先一定要明白啊哈,Lolo只是进行不重复的基数统计,它最终就是给你一个数字,你可以把它理解为就是一条记录,不是集合,也不保存数据,只记录统计的数量,而不是具体的一个个内容。
09:14
第二个它有误差,这个数字要求背下来,人家会问你,你知道害怕logo的缺点吗?有误差好不精确好,请问误差的概率是多少?挺好哈,Lo是提供一种不精确的去重复统计,牺牲精准性来保证大数据的统计,牺牲准确率来换取空间,误差仅仅只是0.81左右,我靠,杨哥。有鼻子有眼的,你哪来的这个数据?这个误差怎么来的?论文的地址和出处来自于哪?杨哥求证明,不能乱说,对吧?我们是理工科,为什么是0.81?可不可以是0.37更小一点?那么来,弟兄们请看一下red之父安特雷斯他自己的个人博客。
10:04
这个是他专门介绍了一种什么新的数据结构hyper log log来首先一个问题啊,大家看我们的资料是来自于哪?呃,我先找一下命令,这提前给大家说一下,首先这三个命令大家有一种奇怪的感觉啊,它为什么是PF开头,它这个命令呢?哈,它的前缀是PF,它呢是记纪念他的一个叫这么一个名字的一个朋友,所以添加统计整合,这是它的三大命令。第二个请大家看它直接跟你说的red的实现是降点,标准的hylo的容错率是多少?1.04除以M开平方,那么这个M就是red的它的什么16384个槽位,所以它标准的容错率就是0.81,这个是海log log的底层算法,OK,好,那各位同学,那假设啊,你要是有兴趣,你可以把。
11:03
整篇文档可以读一下,那么red实现中使用散列的函数,什么具有64位输出,我们呢,用14位来寻指我们的16KB的存储器,前面我们是不是说过那个为什么16384个槽位,这个我们讲过啊,那么所以在这块有兴趣的同学可以读一下,简单一句话,安德雷斯呢,想用12KB的字节就可以存16KB这样的一个内容,OK,那么越小存的越多啊,极致性能的压榨,那接下来同学们捞眼啊,这个是它的回答,那么这块是怎么得到这个呢?来按照这。1.04啊,对于Java里面must SQ rt对16384,算术平方根一除刚好就是0.008125,所以它的误差率就是干嘛1%都不大,就算你是1%,假设你提供啊淘宝首页它的反问统计数正确率是99%,那我认为你们的老板也是可以接受的,OK,所以这个就是海log log他是氧化和它的优缺点,就一句话去重复统计第二个牺山的准确率来换取的空间误差率0.81,好,那么接下来咱们呢,就要做一个真实的案例落地。
我来说两句