Redis bitmap、hyperlog、布隆过滤器、RoaringBitmap原理应用场景与日活的统计的具体应用

缺点：1.空间占用大2.统计逻辑复杂，比如统计最近 30 天用户的累计活跃天(每个用户在 30 天里有 N 天使用 app，N 为 1-30，然后将月活跃用户的 N 天加总)？统计最近 7 天的用户累计使用时长？统计最近 30 天有播放的累计用户数？统计最近 30 天活跃用户有多少在最近 30 天里有连续 3 天及以上活跃？统计 28 天前活跃用户的 1、3、7、14、28 天留存率？3、mysq

云闲不收

3457人浏览 · 2022-07-07 18:11:57

云闲不收 · 2022-07-07 18:11:57 发布

传统方案-mysql

缺点：
1.空间占用大

2.统计逻辑复杂，比如

统计最近 30 天用户的累计活跃天(每个用户在 30 天里有 N 天使用 app，N 为 1-30，然后将月活跃用户的 N 天加总)？
统计最近 7 天的用户累计使用时长？
统计最近 30 天有播放的累计用户数？
统计最近 30 天活跃用户有多少在最近 30 天里有连续 3 天及以上活跃？
统计 28 天前活跃用户的 1、3、7、14、28 天留存率？

3、mysql性能消耗大，

记录需要频繁插表操作，
统计的时候还可能用到多个join，特别是用户量大的时候，计算缓慢。而且容易重复计算，比如计算月活，昨天计算的结果不能直接用，今天又得重复计算一遍，而事实上数据上只多了一天和少了一天。

比如：统计最近 30 天活跃用户有多少在最近 30 天里有连续 3 天及以上活跃？
select
    count(distinct a.qimei) active_num
  from
  ( select
        imp_date
        ,qimei
      from
        weishi_dau_active_table
      where
        imp_date>=20200701
        and imp_date<=20200730
   )a
  join --第一次join，先取出连续2天的用户，因为7月1日用户与7月2号-1天关联得上，表示一个用户在1号和2号都活跃
  ( select
        date_sub(imp_date,1) imp_date
        ,qimei
      from
        weishi_dau_active_table
      where
        imp_date>=20200701
        and imp_date<=20200730
   )b
   on
    a.imp_date=b.imp_date
    and a.qimei=b.qimei
  join --第二次join，取出连续3天的用户，因为第一次join已经取出连续两天活跃的用户了，再拿这些7月1日用户关联7月3日-2天关联得上，表示一个用户在1号和3号都活跃，结合第一步join得出用户至少3天连续活跃了
  ( select
        date_sub(imp_date,2) imp_date
        ,qimei
      from
        weishi_dau_active_table
      where
        imp_date>=20200701
        and imp_date<=20200730
   )c
   on
    a.imp_date=c.imp_date
    and a.qimei=c.qimei
当然这里也可以用窗口函数 lead 来实现，通过求每个用户后 1 条日期与后 2 条日期，再拿这两个日期分布 datediff 当前日期是否为日期相差 1 且相差 2 来判断是否 3 天以上活跃，但是这个方法也还是避免不了拿 30 天分区统计，统计更多天连续活跃时的扩展性不好的情况 5.统计 28 天前活跃用户的 1、3、7、14、28 天留存率？

4、以上统计逻辑可扩展性差，由于数据分析经常进行探索性分析，上面传统方案能解决上面几个问题，但是数据分析稍微改变一下需求，可能就得重新开发。

Redis

1、Set

可以做到去重，而且io消耗小。
缺点是：

空间占用大，只适合用户较少的场景。假设每个用户 id 占用10字节(byte)，1亿用户一天就会消耗 950M 的空间，对于 redis 这种内存型存储来说，成本巨大（特别很多时候还不止统计这一个指标）
集合中数据量大时，会产生大 key。由于 sunionstore 的时间复杂度是 O(N)， N 是所有给定集合的成员数量之，当进行 sunionstore 合并操作的时候，会导致 redis 出现阻塞，影响 redis 的整体性能。当然，也可以使用分片思想，将大 key 变小，但是随着时间推移，用户数量变多，大 key 风险依然存在。

2、Bitmap

介绍与原理

bitmap 就是用一个 bit 位来标记某个元素，该元素是否存在时用 bit 位的 1,0 表示。
比如 10 亿个 int 类型的数，如果用 int 数组存储的话，那么需要大约 4G 内存，当我们用 int 类型来模拟 bitmap 时，一个 int 4 个字节共 4*8 = 32 位，可以表示 32 个数，原来 10 亿个 int 类型的数用 bitmap 只需要 4GB / 32 = 128 MB 的内存。
在计算机里，一个字节(byte)有8个二进制位，即1byte=8bit。假设有7个数字，我们可以按照编号放进一段连续内存里，对应位置中存在就显示1，其它默认都显示0 比如 3，5，1，7，11，15，4，1
在这里插入图片描述

由于一个二进制位就表示一个数字，该位上只有0，1两个值，所以将数字映射成二进制位后，不仅对数字进行了排序，还做了排重处理，可以用来统计日活、周活。

优点

节省空间 1亿个用户一天的数据量也就 1 0000 0000bit = 11.92m
速度快
可以方便的进行日活、月活、年活的统计-计算依然很快

缺点

占用空间依然很大，而且容易形成大key，
redis setbit，offset 的值最大可到2 ^ 32 - 1，即用户总数量不能大于4294967295，也就是42亿左右。由于日活、周活统计中，offset 是用户 id，所以用户 id 也不能大于4294967295。如果 offset 真要达到4294967295，redis 会分配 512M 的存储空间形成大 key，大的内存分配会造成 redis 出现阻塞。bitcount 和 bitop 的时间复杂度是 O(N)，如果对大 key 进行操作，也会导致 redis 出现阻塞
bitmap 占用的空间的大小，与用户数量是没有关系的，而是取决于最大的用户 id 是多少。
哪怕今天只有一个用户访问应用，如果他的用户 id 是1亿，那么今天统计用户活跃的 bitmap 使用空间就是12M，对于分维度的统计，比如根据地区统计日活、周活，有的地区用户不多，但是用户 id 非常大，导致该地区当天的 bitmap 使用空间很大
只能统计具有数字型连续id的数据，其他场景如ip 、或者用户id为字母符号的就不是这么合适了

使用

设置 setbit key position value
命令键名位置(id 起始为0) 值(0\1)
setbit dau 108 1
获取 getbit key
getbit dau 108
简单统计 BITCOUNT key [start] [end]
bitcount dau
高级统计 BITOP operation destkey key [key ...]
比如使用dau 但是想求mau
对一个或多个key求逻辑并，并将结果保存到destkey
BITOP 命令支持 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种参数

坑

假设设置testkey的1、2两个位置都为1

BITCOUNT testkey 2 -1
(integer) 0 //结果却是0

“redis的setbit修改的是bit位置，而bitcount检查的是byte位置，两者相差有8的倍数”
解决方式：
1、我们可以通过get命令将value取出来，自己解析。并且这个value通常不会太大。
2、在setbit 前把offset * 8 代码如下：

// 乘以8的原因是这个操作修改的是bit位置
$start = 1;
$offset = $start * 8;
$redis->setBit('bit', $offset, 1);
$count = $redis->bitCount('bit', $start, -1);
var_dump($count);

适用场景

mysql的存储也可借鉴这种思想，存二进制代表的数字或者mysql似乎也有直接存二进制的方式

bitmap 适用于用户数在1～2亿左右，且用户 id 比较连续的场合(占用12M~24M空间)，再大就有可能出现性能问题。当然，也可以使用分片思想来解决。

场景1-活跃用户的统计
场景2-简单的布尔过滤器：如用户在线状态、点赞等
场景3-用户签到比如需要根据连续签到天数给与不同的奖励、补签等。节省空间且不容易形成脏数据。还有比如用户在线次数、用户各项设置（提前定义映射id）、软件安装列表等（提前定义软件id）
场景4 - 快速的排序与查找
位图排序是一种效率极高(复杂度可达 O(n))并且很节省空间的一种排序方法，但是这种排序方法对输入的数据是有比较严格的要求(数据不能重复，大致知道数据的范围)。位图排序即利用位图或者位向量来表示集合。举个例子，假如有一个集合{3,5,7,8,2,1，我们可以用一个8位的二进制向量 set[1-8]来表示该集合，如果数据存在，则将 set 相对应的二进制位置 1,否则置 0.根据给出的集合得到的 set 为1,1,1,01,0,1,1，然后再根据 set 集合的值输出对应的下标即可得到集合[3.5,7.8.2,1的排序结果。这个就是位图排序的原理。
场景5 快速去重
- 假设让你从20亿个整数中找出不重复的整数的个数，提前是内存不足以容纳这20亿个整数，那么你会用什么办法？使用Bit-map就可以很好的解决。关键的问题就是怎么设计Bit-map来表示这20亿个数字的状态了。
  一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11，那我们大概需要存储空间2G左右。所以可以这样进行操作：
  把这20亿个数字放进去（存储），如果对应的状态位为00，则将其变为01，表示存在一次；
  如果对应的状态位为01，则将其变为11，表示已经有一个了，即出现多次；
  如果为11，则对应的状态位保持不变，仍表示出现多次。
  最后，统计状态位为01的个数，就得到了不重复的数字个数，时间复杂度为O(n)。
- 以前的搜索引擎爬虫在处理网页爬取的时候需要给已经爬取过的网页做标记,避免陷入死循环的重复爬取,当时的搜索网站的爬虫就有一些采用过bitmap来给爬取过的网页做标记,大致就是取页面的url取hash,然后处理成数字,把对应的数字位置为1
场景6 - 多条件筛选的应用（用户标签）
- 场景6的应用1
- 用户标签
  我们如果要记录一个用户对应的一个标签的信息,假如我们知道5号用户是小九,而她是一位超级会员用户(我们可以在上面的表中查到该信息)
  我们要如何使用bitmap来表示这条信息呢（存储用户和标签的关系）
  我们可以这样:
  使用一个键user:supervip 来记录所有用户是否是超级会员的信息,这个值最初是空的字符串值,表1明没有超级会员用户
  我们为了标明 5 号用户是超级会员可以使用这个键中对应位置的二进制位来表明会员的身份，将2.这个键的第 5 位置为1，这样这个user:supervip 值现在是000001’(从第0位开始计算)同样,如果user:supervip 的值现在是’01001010’我们就可以知道 1,4,6号用户都是超级会员用3
  我们根据这个数据可以做到2点:
  我们可以根据该标签数据键的对应位置的二进制位的值来判断以该位置为id的用户的标签结果。也可以查询某个标签下的所有用户
  这样我们存储上万个标签也只需要上万个键
  为了解决这个问题我们需要一个存储所有用户的键
- 场景5的应用3：如
  
  左边是用户id，右边是直接用json存的信息（里面字段可能好几种），现在来了个新需求。需要按照类型筛选出用户id。
  使用bitmap思想的方案有两种。
  一种是，新建一个类型表 uid type bitmap_id 用bitmap存上面那个表的id(但是好像当id很大且很少的时候不如直接存序号)
  另一种是在上面的表加个字段types，然后定义好规则，比如01代表只有cpu，10代表只有下载，11代表两个都有。然后跑脚本写入这个字段。这样就能快速进行多种条件的筛选了，但是缺点是类型不能很多，比如11个的话，2的十一次方是2048，以后可能还会加其他选项。要是用bitmap的话，查询的时候in也会很长（比如查询有cpu的，那就有很多很多种组合了）
场景7 关系交集 - 微博里面你关注的A也关注了B, 使用B的粉丝列表和你的关注列表进行交集运算就可以了,同样购买这件商品的人也购买了M,也可以用购买这件商品的用户列表里面取某个用户购买过的某个商品即可

优化–RoaringBitmap

介绍

以一个“40亿个数据是4个字节的unsigned int 型的数据”为例。

直接存储。(40 * 10^8) * 4byte = 14.9GB (1GB=2^10Mb=220kb=2^30byte）；
采用位图（bitmap）存储。40亿个数据都是位于[0, 2^32 - 1]，每一位指的是一个bit位，而1byte（1字节）是8个bit，2^32bit = 2^29byte = 2^19kbyte=29Mb=512Mb；

如果数据很稀疏，例如：统计某个应用的用户数，用户id范围为[0, 2^32 - 1]，如果只有几个用户在线时，还需要开辟512M的存储空间，那么浪费就大了。

于是出现了“位图压缩的方式”，roaringBitMap就是其中一种。
roaringbitmap属于是位图的一个进化，即压缩位图。在roaringbitmap中不只包含bitmap这一种数据结构，而是包涵了多种存储的方式，以此来达到压缩位图的目的。

roaringbitmap是高效压缩位图，简称RBM

官网对其的介绍：Roaring bitmaps are compressed bitmaps. They can be hundreds of times faster.

RBM的历史并不长，它于2016年由S. Chambi、D. Lemire、O. Kaser等人在论文《Better bitmap performance with Roaring bitmaps》与《Consistently faster and smaller compressed bitmaps with Roaring》中提出.

原理

将 32bit int（无符号的）类型数据划分为 2^16 个桶，即最多可能有216=65536个桶，论文内称为container。用container来存放一个数值的低16位
在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container 中（存储时如果找不到就会新建一个）
在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container 中（存储时如果找不到就会新建一个）

注意：大家需要注意大桶里面的各个小桶(container)是在需要的时候才会申请开辟

比如要将31这个数放进roarigbitmap中，它的16进制为：0000001F,前16位为0000，后16为001F。
所以先需要根据前16位的值：0，找到它对应的通的编号为0，然后根据后16位的值：31，确定这个值应该放到桶中的哪一个位置，如下图所示。
在这里插入图片描述

roaringBigMap有四种小桶container类型：

arraycontainer(数组容器)
container默认使用arraycontainer（元素都是按从大到小的顺序排列的），由于container只有16位bit位，最大[0-65535)，则用short int类型（占两个字节）即可。当ArrayContainer的容量超过4096（这里是指4096个short int即8k Byte）后，切换为bitmapcontainer(这个所占空间始终都是8k Byte，也就是16位bit)。即ArrayContainer存储稀疏数据，BitmapContainer存储稠密数据，可以最大限度地避免内存浪费。如下内存使用图：
bitmapcontainer(位图容器)
和前面的位图一样，只不过这里位图的位数为2^{16（65536）个，也就是2}16个bit,计算下来起所占内存就是8kb。
runcontainer(行程步长容器)
一种利用步长来压缩空间的方法。
比如连续的整数序列 11, 12, 13, 14, 15, 27, 28, 29 会被压缩为两个二元组 (11, 4),(27, 2) ：11后面紧跟着4个连续递增的值，27后面跟着2个连续递增的值，那么原先16个字节的空间，现在只需要8个字节，是不是节省了很多空间呢。不过这种容器不常用。
sharedcontainer(共享容器)
它本身是不存储数据的，只是用它来指向arraycontainer,bitmapcontainer或runcontainer,就好比指针的作用一样。这个指针（sharedcontainer）可以被多个对象拥有，但是指针所指针的实质东西是被这多个对象所共享的。
使用：进行roaringbitmap之间的拷贝的时候，有时并不需要将一个container拷贝多份。那么我们就可以使用sharedcontainer来指向实际的container，然后把sharedcontainer赋给多个roaringbitmap对象持有，这个roaringbitmap对象就可以根据sharedcontainer找到真正存储数据的container,这可以省去不必要的空间浪费。

与bitmap性能的对比

空间节省：bitmap比较适用于数据分布比较稠密的存储场景中；roarringBitMap在稀疏存储上空间更省，稠密和bitMap一致；
更高效的做交、并操作。
a、逻辑结构节省计算量：将大块的bitmap分成各个小块，其中每个小块在需要存储数据的时候才会存在。所以当进行交集或并集运算的时候，只需要去计算存在的一些块，而不需要像bitmap那样对整个大的块进行计算。这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。
b、逻辑结构优化程序：roaringbitmap维护了排好序的一级索引，以及有序的arraycontainer当进行交集操作的时候；计算时，根据需要在一级索引中找需要的内容。

优化 ewah compressed bitmap

在这里插入图片描述

拓展–布隆过滤器

如果语言没有可用 $rds->rawCommand(‘bf.exits’, ‘surl_exits’, ‘test’);的方式

是什么

基于 bitmap 实现的布隆过滤器，宽泛用于去重的业务场景中（如缓存穿透，爬虫 url 去重等）
当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组（Bit array）中的 K 个点，把它们置为 1 。检索时，只要看看这些点是不是都是1就知道元素是否在集合中；如果这些点有任何一个 0，则被检元素一定不在；如果都是1，则被检元素很可能在（之所以说“可能”是误差的存在）。误差举例：当bitmap的数组长度很小，而数据又很多的情况下，有可能判断元素在集合中，但是元素不在，原因：这个元素所有索引位置上面的1都是别的元素设置的，这就导致一定的误判几率。
1970 年的时候，有一个叫做布隆的前辈对于判断海量元素中元素是否存在的问题进行了研究，也就是到底需要多大的位图容量和多少个哈希函数，它发表了一篇论文，提出的这个容器就叫做布隆过滤器。
在这里插入图片描述

应用场景

缓存穿透
缓存穿透：恶意攻击不断以一个不存在的key，请求缓存，查询redis，redis没有就去mysql查，导致数据库压力增大，拖垮服务
解决方案：当redis不存在， mysql也不存在的时候，给redis中写入当前key， value为空。但是消耗内存大。所以，可以使用布隆过滤器。
布隆过滤器特性：
- 如果元素实际不存在，布隆过滤器可能判断存在。
- 如果元素实际存在，布隆过滤器一定判断存在。

利用第二个特性，我们就能解决持续从数据库查询不存在的值的问题，把要查询的值先过布隆过滤器，判断是否存在，存在就走redis缓存，不存在就直接返回，并且配合缓存空值，可以有效解决缓存穿透问题，虽然存在一定误差，但是在业务范围内允许接受。

网页爬虫对URL去重，避免爬取相同的 URL 地址;
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱;
Google Chrome 使用布隆过滤器识别恶意 URL;
Medium 使用布隆过滤器避免推荐给用户已经读过的文章;
与唯一索引结合防止重复注册

3、HyperLog

介绍

HyperLogLog算法来源于论文《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》

HyperLogLog 是一种基数估算算法。所谓基数估算，就是估算在一批数据中，不重复元素的个数有多少。
首先要说明，HyperLogLog实际上不会存储每个元素的值，它使用的是概率算法，通过存储元素的hash值的第一个1的位置，来计算元素数量。这样做存在误差，不适合绝对准确计数的场景。
redis中实现的HyperLogLog，只需要12K内存，在标准误差0.81%的前提下，能够统计2的64次方个（约184亿亿个）数据。

用法

命令	简述	使用
pfadd	添加指定元素到 HyperLogLog 中	pfadd key element [element…]
pfcount	返回给定 HyperLogLog 的基数估算值	pfcount key
pfmerge	将多个 HyperLogLog 合并为一个 HyperLogLog	pfmerge destkey sourcekey [sourcekey …]

原理

伯努利实验

伯努利试验（Bernoulli experiment）是在同样的条件下重复地、相互独立地进行的一种随机试验，其特点是该随机试验只有两种可能结果：发生或者不发生。我们假设该项试验独立重复地进行了n次，那么就称这一系列重复独立的随机试验为n重伯努利试验，或称为伯努利概型。单个伯努利试验是没有多大意义的，然而，当我们反复进行伯努利试验，去观察这些试验有多少是成功的，多少是失败的，事情就变得有意义了，这些累计记录包含了很多潜在的非常有用的信息。【注意这里区分n次伯努利实验与n重伯努利实验，n重伯努利实验是一次伯努利实验】

简单来说，就是连续抛硬币，每次只有正面、反面两种结果。

数学直觉

假设你进行了m轮实验（每轮实验抛了n次硬币）
你告诉我们，在这m轮实验中，最多只有两次扔出连续的反面，让我们猜你总共抛了多少轮硬币，我们敢打赌你抛硬币的总次数不会太多，相反，如果你说最多出现了100次连续的反面，那么我敢肯定扔硬盘的总次数非常的多，甚至我还可以给出一个估计。
【注意这里是“连续” 因为正常抛硬币正反概率差不多更可能是类似正反正反反正这种规律不强且正反交替出现的情况】

下面就可以开始我们的主题了：
首先，明确我们的目的：通过实验结果估计抛硬币的次数！
以反反正为例，可以抽象为001，由于每次抛硬币的概率是二分之一，那么抛出这个结果的概率为八分之一，那么我也就可以猜测，你抛了八次硬币才得到这个结果。但是正如上面所说，这样偶然性太大了，假设你一次实验中抛了五回硬币，那么难道我们说你要抛32次才会出现这个结果么？所以正确的思路应该是统计连续抛出正面或者反面的次数以估计总共进行了多少次实验【区分实验轮数与抛硬币的次数】

但是以上只是一种直觉的归纳，是很不精确的，需要用数学推导的方式概括出来。于是，数学家们使用极大似然估计法，将问题抽象为，进行n轮抛硬币实验，看最长要抛几次才可以得到正面（“连续出现了多少次反面”）。
在这里插入图片描述
我们用K_max表示n轮实验中，抛出第一个正面最大的次数。在上面的例子中，K_max = 7
根据极大似然法，可以得到如下关系：n=2^Kmax

理论进入应用

于是！如果我们将value，通过哈希算法得到其唯一的二进制值，那么，其结果就恰似上面的抛硬币实验！
当我们我们将一系列的value通过hash函数，得到上面的K和K_max,那么，我们就能够大概的知道一共有多少个value了（进行了多少轮实验）

HyperLogLog 在添加元素时，会通过Hash函数，将元素转为64位比特串，例如输入5，便转为101(省略前面的0，下同)。这些比特串就类似于一次抛硬币的伯努利过程。比特串中，0 代表了抛硬币落地是反面，1 代表抛硬币落地是正面，如果一个数据最终被转化了 10010000，那么从低位往高位看，我们可以认为，这串比特串可以代表一次伯努利过程，首次出现 1 的位数为5，就是抛了5次才出现正面。

优化1.1:避免极端值的影响-分桶

但上面的做法误差是很大的，比如一个值的value为00001，可能恰巧我第一次或者第二次就抛出来了，但是根据上面的计算方式，k和K_max都为5，需要32轮实验才能抛出（所以，需要明确，上述公式仅在实验轮数很多的情况下有效）。
为了避免这种极端值的影响。我们引入了分桶算法

直接用最大的ρ(x)，受随机事件的影响很大，例如如果前几次就来-个00000000000001。有一个方法，可以降低这种影响，就是分桶取平均数，例如分4个桶，取前两位作为桶的标志,
hash(key1) = 01010110，ρ(01010110)= 2, bucket 01
hash(key2) = 01110010，ρ(01110010)=0, bucket 01
hash(key3) = 00000011，ρ(00000011)= 5, bucket 00

在这里插入图片描述

优化1.2:避免极端值的影响-调和平均数

在这里插入图片描述
假设我的工资20000，马云1000000000
使用平均数的计算方式：(20000 + 1000000000) / 2 = 500010000
调和平均数的计算方式：2/(1/20000 + 1/1000000000) ≈ 40000
很明显，平均工资月薪40000更加符合实际平均值，5个亿不现实。

但是如果遇到更极端的随机事件，例如hash函数最大是2³²，去到最后一位，对分桶取算数平均数的影响还是很大的，怎么办呢?数学上有个叫调和平均数的东西，我们用调和平均数取代算数平均数即可。

HyperLogLog 将上文所说的 64 位比特串的低 14 位单独拿出，它的值就对应桶的序号，然后将剩下 50 位中第一次出现 1 的位置值设置到桶中。50位中出现1的位置值最大为50，所以每个桶中的 6 位数组正好可以表示该值。

优化1.3:修正因子

真实的算法还有很多修正因子，因为涉及到的数学理论知识过于繁多，这里就不再精确描述。
在这里插入图片描述

优化2:稀疏存储与密集存储

但是，上面就一个value啊，怎么进行多次实验呢？
我们知道一个HyperLogLog实际占用的空间大约是 13684 * 6bit / 8 = 12k 字节。但是在计数比较小的时候，大多数桶的计数值都是零。如果 12k 字节里面太多的字节都是零，那么这个空间是可以适当节约一下的。Redis 在计数值比较小的情况下采用了稀疏存储，稀疏存储的空间占用远远小于 12k 字节。相对于稀疏存储的就是密集存储，密集存储会恒定占用 12k 字节。

优势

在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存(因为 Redis 对 HyperLogLog 的存储进行了优化，在计数比较小时，它的存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵，才会占用 12k 的空间。)，就可以计算接近 2^64 个不同元素的基数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。

others-哈希函数的条件

均匀随机化

与LC一样，在使用LLC之前需要选取一个哈希函数H应用于所有元素，然后对哈希值进行基数估计。H必须满足如下条件（定性的）：

1、H的结果具有很好的均匀性，也就是说无论原始集合元素的值分布如何，其哈希结果的值几乎服从均匀分布

（完全服从均匀分布是不可能的，D. Knuth已经证明不可能通过一个哈希函数将一组不服从均匀分布的数据映射为绝对均匀分布，但是很多哈希函数可以生成几乎服从均匀分布的结果，这里我们忽略这种理论上的差异，认为哈希结果就是服从均匀分布）。

2、H的碰撞几乎可以忽略不计。也就是说我们认为对于不同的原始值，其哈希结果相同的概率非常小以至于可以忽略不计。

3、H的哈希结果是固定长度的。

以上对哈希函数的要求是随机化和后续概率分析的基础。后面的分析均认为是针对哈希后的均匀分布数据进行。

参考资料

《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》
https://www.zhihu.com/question/53416615
https://blog.csdn.net/qq_41125219/article/details/119776824
https://wenku.baidu.com/view/e6ee8b892b4ac850ad02de80d4d8d15abe230000.html
在线模拟运行网站 http://content.research.neustar.biz/blog/hll.html
https://zhuanlan.zhihu.com/p/77289303
https://mp.weixin.qq.com/s/9dtGe3d_mbbxW5FpVPDNow 熬丙的还没看

对比总结

布隆过滤器主要用来判断，某个数据存不存在
HyperLogLog用来做统计 , 没法确认某个数据在不在
bitmap即可统计也可确定数据在不在，但是占用空间较大，支支持数字类型。当仅用于统计，且数量大于12*1024*8 约等于十万的时候，建议考虑hyperlog

数据仓库 Hive

附录

bitmap快速查找实例

Bitmap方法可以用来解决海量数据的排序，包括查找缺少的数据，和重复的数据。

先说问题，话说给40亿个不重复的unsigned int型的整数，没有排过序的。然后给一个数，如何快速的判断出这个数是否存在那40亿个数当中。

我们先来捋一捋，40亿是一个什么概念。后面9个0，40亿就是4000000000。我们惯性思维最先想到的解法就是来一个for循环，找到相等的数即可，这种方法是肯定不行的，32位机器一个unsingen int型占4个字节，那么40亿个就是4000000000 / (1024 * 1024 * 1024) = 14.90116119384765625，也就是15个G，所以就这个数目，手数都会抽筋，机器都能跑冒烟好多台。当然如果那机器性能特别优秀的那就另当别论，我们考虑的是最优算法，学习的是算法思维，要考虑时间空间复杂度，开拓技能。

在解决这个问题之前，我们先回顾一下位运算的基本知识。在嵌入式开发里，bit位和字节，这两个是很宝贵的东西，因为内存很珍贵，一个bit如至宝，不能随便浪费。所以我们要灵活的使用他们，基础要扎实。

1字节（byte） = 8比特（bit），即一个字节有8个比特位

1KB = 1024字节

1M = 1024KB

那40亿等于占用多少内存，需要多少个比特位呢？我们通过上面的字节单位来换算，就可以算出来了，4000000000 / (8 * 1024 * 1024) = 476.837158203125，也就是说我们只需要476.84M内存就可以了，这一下子是不是减少了很多内存。以32位机器位例，一个32位机，一个int型占4个字节，0~31位，如果是int数组，我们画张图看看：
在这里插入图片描述
A[0]的比特位为0~31

A[1]的比特位为32~63

A[2]的比特位为64~95

A[3]的比特位为96~127

…

1个比特位就可以表示一个数字。我们假设初始值都是0，如果某个bit位值为1，就说明其代表某个数值。现在我们来模拟一下，假如有100个数，我们在这一百个数里查找。100位只需要12.5个字节（100/8=12.5），也就是只需要定义int[4]就可以了（一个int型有32bit位，4个是128位，刚好超过100）。

int[4]初始值为0，我们看下程序：

1、首先计算该值在哪个字节位置，以及对应的字节位置上的哪个比特，就是上图中的数组，位于A[n]中的哪个bit

int arr[4];

void SetBit(int n)
{
int bytePos = (n >> 5); //求出字节位置
int bitPos = (n & 0x1f); //计算在字节里的哪个bit位上

arr[bytePos] |= (1 << (bitPos - 1));  //逻辑位设置位1

}
2、搜索相应bit位的值是否为1，是就表示找到，并返回其值

int SearchBit(int n)
{
int bytePos = (n >> 5); //求出字节位置
int bitPos = (n & 0x1f); //计算在字节里的哪个bit位上

return arr[bytePos] & (1 << (bitPos - 1)); //判断此bit位是否为1，并返回其值

}
3、 Bit位清0

void ClearBit(int n)
{
int bytePos = (n >> 5); //求出字节位置
int bitPos = (n & 0x1f); //计算在字节里的哪个bit位上

arr[bytePos] &= ~(1 << (bitPos - 1));   //此逻辑位清0，原理同SetBit操作

}
主函数，请参考：

int main()
{
int a[100] = {1,10,20,30,40,50,60,70,80,90,
2,11,21,31,41,51,61,71,81,91,
3,12,22,32,42,52,62,72,82,92,
4,13,23,33,43,53,63,73,83,93,
5,14,24,34,44,54,64,74,84,94,
6,15,25,35,45,55,65,75,85,95,
7,16,26,36,46,56,66,76,86,96,
8,17,27,37,47,57,67,77,87,97,
9,18,28,38,48,58,68,78,88,98,
19,29,39,49,59,69,79,89,99,103};

for (int i = 0; i < 100; i++)  SetBit(a[i]);  //每个值设置bit位

for (int i = 1; i <= 100; i++)
{
    if (SearchBit(i)) printf("%d is exist\n", i);
    else printf("%d is not exist\n", i);
}

for(int i = 0; i < 100; i++) ClearBit(a[i]);

return 0;

}
【运行结果】
在这里插入图片描述