Redis数据结构HyperLogLog以及布隆过滤器

HyperLogLog

引言

在开始之前，先思考一个常见的业务问题：如果负责开发维护一个大型的网站，有一天老板找产品经理要网站每个网页每天的UV数据，然后来开发这个统计模块，需要如何实现？

如果统计PV非常好办，给每个网页一个独立的Redis计数器即可，这个计数器的key后缀加上当天的日期。这样每次一个请求，incrby一次，最终就可以统计出所有的PV数据。

但是UV不一样，他要去重，同一个用户一天之内的多次访问请求只能计数一次，这就要求每一个网页请求都需要带上用户ID。无论是登录用户还是未登录用户都需要一个唯一ID来标识。也许你已经想到了一个简单的方案，那就是为每一个页面设置一个独立的set集合来存储所有当天访问过此页面的用户ID，当一个请求过来时，使用sadd将用户ID塞进去即可，通过scard可以取出这个集合的大小，这个数字就是这个页面的UV数据。

但是，如果页面的访问量非常大，比如一个爆款页面几千万的UV，此时就需要一个很大的set集合来统计，这非常浪费空间。如果这样的页面很多，那么所需要的存储空间是惊人的。为了这样一个去重功能耗费如此多的存储空间，其结果必然是不值得。其实，老板需要的数据不需要太精确，105w和106w这两个数字对于老板们来说并没有多大区别，因此，需要探讨一种更好的解决方案。

因此，本文主要讨论，Redis提供的HyperLogLog来解决这个问题。HyperLogLog提供不精确的去重计数方案，其标准误差是0.81%，这样的精确度足够满足很多UV需求。

使用方法

HyperLogLog提供了两个指令pfadd和pfcount，一个是增加计数，一个是获取计数。pfadd用法和set集合的sadd一样，来一个用ID，就将用户ID塞进去即可。pfcount和scard用法一样，直接获取计数值。

127.0.0.1:6379> pfadd codehole user1 
(integer) 1
127.0.0.1:6379> pfcount codehole 
(integer) 1
127.0.0.1:6379> pfadd codehole user2 
(integer) 1
127.0.0.1:6379> pfcount codehole 
(integer) 2
127.0.0.1:6379> pfadd codehole user3 user4 user5 user6
(integer) 6

简单试了一下，发现还蛮精确的，一个没多一个也没少，接下来，使用脚本，灌入更多的数据，看看是否还可以继续精确下去，如果不能精确，差距有多大。

public class PfTest {
    public static void main(String[] args) {
        Jedis jedis = new Jedis();
        for (int i = 0; i < 100000; i++) {
            jedis.pfadd("codehole", "user" + i);
            long total = jedis.pfcount("codehole");
            if (total != i + 1) {
                System.out.printf("%d %d\n", total, i + 1);
                break;
            }
        }
        jedis.close();
    }
}

当加入10w数据的时候，输出结果为99723，差了277，按照百分比是0.277%。当再次运行这个脚本的时候输出结果仍然是99723（redis运行过一次已经存在数据的情况下），说明他确实具备去重功能。

pfmerge

HyperLogLog除了上面的pfadd和pfcount之外，还提供了第三个指令pfmerge,用于将多个pf计数值累加在一起形成一个新的pf值。比如在网站中我们有两个内容差不多的页面，需要将这两个页面的数据进行合并，其中页面的UV访问量也需要合并，那么这个时候pfmerge就可以派上用场。

布隆过滤器

引言

上文讲述了使用HyperLogLog数据结构来进行估数，可以解决很多精确度不高的统计需求。但是，如果我们想知道某一个值是不是已经在HyperLogLog结构里面了，他就无能为力，他只提供pfadd和pfcount方法，没有提供pfcontains方法。

举个使用场景，我们在使用新闻客户端看新闻时，他会给我们不停的推荐新的内容，他每次推荐时要去重，去掉那些已经看过的内容。新闻客户端的推荐系统如何实现推送去重？

很容易想到服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。问题是当用户量很大，每个用户看过的新闻又很多的情况下，这种方式，推荐系统的去重工作在性能上跟得上吗？

实际上，如果历史记录存储在关系数据库里，去重就需要频繁的对数据库进行exists查询，当系统并发量很高时，数据库是很难扛住压力的。

如果将如此多的历史记录全部缓存起来，那得浪费多大存储空间。而且这个存储空间是随着时间线性增长，很难长时间撑的住。但是不缓存的话，性能又跟不上，此时该如何解决。

这时，布隆过滤器（Bloom Filter）闪亮登场，他就是专门用来解决去重问题的。他在起到去重的同时，在空间上还能节省90%以上，只是稍微有点不精确，也就是有一定的误判概率。

布隆过滤器是什么

布隆过滤器可以理解为一个不怎么精确的set结构，当使用它的contains方法判断某个对象是否存在时，他可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合适，他的精确度可以控制的相对足够精确，只会有小小的误判概率。

当布隆过滤器说某个值存在时，这个值可能不存在；当他说不存在时，那就肯定不存在。套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过的新内容，他也会过滤掉极小一部分，但是绝大多数心能容他都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。

Redis中的布隆过滤器

Redis官方提供的布隆过滤器到了Redis4.0提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到Redis Server中，给Redis提供了强大的布隆去重功能。

布隆过滤器基本使用

布隆过滤器有三个基本指令，bf.add添加元素，bf.exists查询元素是否存在，他的用法和set集合的sadd和sismember差不多。bf.add一次只能添加一个元素，如果想要一次添加多个，就需要用到bf.madd指令。同样如果需要一次查询多个元素是否存在，就需要使用bf.mexists指令。

127.0.0.1:6379> bf.add codehole user1 
(integer) 1
127.0.0.1:6379> bf.add codehole user2 
(integer) 1
127.0.0.1:6379> bf.add codehole user3 
(integer) 1
127.0.0.1:6379> bf.exists codehole user1 
(integer) 1
127.0.0.1:6379> bf.exists codehole user2 
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0

代码测试

public class BloomTest {
    public static void main(String[] args) {
        Client client = new Client();
        client.delete("codehole");
        for (int i = 0; i < 100000; i++) {
            client.add("codehole", "user" + i);
            boolean ret = client.exists("codehole", "user" + (i + 1));
            if (ret) {
                System.out.println(i);
                break;
            }
        }
        client.close();
    }
}

运行后，可以看到输出214，即到第214的时候，就出现了误判。那么如何测量误判率呢？我们先随机出一堆字符串，然后切分为2组，将其中一组塞入布隆过滤器，然后判断另外一组的字符串存在与否，取误判的个数和字符串总量一半的百分比作为误判率。

代码如下：
pom中添加依赖

  	  <dependency>
            <groupId>redis.clients</groupId>
            <artifactId>jedis</artifactId>
            <version>3.9.0</version>
        </dependency>
        <dependency>
            <groupId>com.redislabs</groupId>
            <artifactId>jrebloom</artifactId>
            <version>2.2.2</version>
        </dependency>

package example;
import io.rebloom.client.Client;
import redis.clients.jedis.Jedis;

class BloomRedis {
    private Client client;
    private Jedis jedis;
    private int capacity = 20000;
    // 容错率,只能设置0 < error rate range < 1  不然直接会异常！
    private double errorRate = 0.01;
    public BloomRedis() {
        jedis = new Jedis("127.0.0.1", 6379);
        client = new Client(jedis);

    }
    public void count(String key) {
        if (!jedis.exists(key)) {
            client.createFilter(key, capacity, errorRate);
        }
        int realCapacity = 20000;
        for (int i = 0; i < realCapacity; i++) {
            client.bfInsert(key, String.valueOf(i));
        }
        System.out.println("存入元素为=={" + realCapacity + "}");
        // 统计误判次数
        int count = 0;
        // 我在数据范围之外的数据，测试相同量的数据，判断错误率是不是符合我们当时设定的错误率
        for (int i = capacity; i < realCapacity * 2; i++) {
            if (client.exists(key, String.valueOf(i))) {
                count++;
            }
        }
        System.out.println("误判元素为=={" + count + "}");
        // 删除过滤器
        client.delete(key);
    }
}
class ExampleTest {
    public static void main(String[] args) {
        BloomRedis bloomRedis = new BloomRedis();
        bloomRedis.count("codehole");
    }
}

输出结果：

存入元素为=={20000}
误判元素为=={174}

设置处理容量为20000，容错率为0.01的情况下，输出结果最终错误率为0.0087。

一组其他测试数据

//当realCapacity为5000,capacity 20000，错误率为0
//当realCapacity为10000,capacity 20000，错误率为0
//当realCapacity为20000,capacity 20000，错误率为0.08
//当realCapacity为40000,capacity 20000，错误率为0.5
//当realCapacity为40000,capacity 80000，错误率为0

注意事项

布隆过滤器的initial_size估计的越大，会浪费存储空间，估计的过小，就会影响准确率，用户在使用之前一定要尽可能的精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会高出估计值很多。
布隆过滤器的error_rate越小，需要的存储空间越大，对于不需要过于精确的场合，error_rate设置稍大一点也无伤大雅。比如在新闻去重上而言，误判率高一点只会让小部分文章不能让合适的人看到。文章的整体阅读量不会因为这点误判率就带来巨大的改变。

布隆过滤器原理

每个布隆过滤器对应到Redis的数据结构里面就是一个大型的位数组和几个不一样的无偏hash函数。所谓无偏就是能够把元素的hash值算的比较均匀。

向布隆过滤器中添加key时，会使用多个hash函数对key进行hash算的一个整数索引值然后对位数组长度进行取模运算得到一个位置。每个hash函数都会算得一个不同的位置，再把位数组的这几个位置都置为1，就完成了add操作。

向布隆过滤器询问key是否存在时，跟add一样，也会把hash的几个位置（对一个值进行多次hash，每次hash计算得出在位数组中的一个索引，多个hash得到多个索引，每个索引位置在位数组中都是1那这个值就是存在）都算出来，看看位数组中这几个位置是否都为1.只要有一个为0，那么说明布隆过滤器这个key不存在。如果都是1，这不能说明这个key一定存在，只是极有可能存在，因为这些位置为1可能是因为其他的key存在所致。

使用时不要让实际元素大于初始化大小，当实际元素开始超出初始化大小时，应该对布隆过滤器进行重建，重新分配一个size更大的过滤器。再将所有的历史元素批量add进去（这就要求我们在其他的存储器中记录所有的历史数据）。因为error_rate不会因为数量超出就急剧增加，这就给我们重建过滤器提供了较为宽松的时间。

空间占用估计

布隆过滤器有两个参数，第一个是预计元素的数量n，第二个是错误率f。公示根据这两个输入得到两个输出，第一个输出是位数组的长度1，也就是需要的存储空间大小（bit），第二个输出是hash函数的最佳数量k。hash函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。

k = 0.7 * (1/n)
f = 0.6185 ^ (1/n)

从公式中可以看出

1. 位数组相对越长（1/n）,错误率 f 越低，这个和直观上理解一致。
2. 位数组相对越长（1/n）,hash函数需要的最佳数量也越多，影响计算效率。
3. 当一个元素平均需要1个字节（8bit）的指纹空间时（1/n =8），错误率大约为0.02.
4. 错误率为10%，一个元素需要的平均指纹空间为4.792个bit，大约为5 bit.
5. 错误率为1%，一个元素需要的平均指纹空间为9.585个bit，大约为10 bit。
6. 错误率为 0.1%，一个元素需要的平均指纹空间为 14.377 个 bit，大约为 15 bit。

此时，也许会想，如果一个元素需要占据15个bit，那相对set集合的空间优势是不是就没有那么明显了？这里需要明确的是，set会存储每个元素的内容，而布隆过滤器仅仅存储元素的指纹。元素的内容大小就是字符串的长度，他一般会有多个字节，甚至是几十个字节，每个元素还需要一个指针被set集合来引用，这个指针又会占去4个字节或者8个字节，取决于系统是32bit还是64bit。而指纹空间只有接近2个字节，所以布隆过滤器的优势还是非常明显的。

推荐使用布隆过滤器计算需要提供的存储空间。

实际元素超出时，误判率会怎样变化

当实际元素超出预计元素时，误判率变化需要引用下述计算公式。引入参数 t 表示实际元素和预计元素的倍数 t。

f = (1-0.5^t )^k. #极限近似，k是hash函数的最佳数量

当t增大时，错误率 f 也会跟着增大，分别选择错误率为 10%，1%，0.1%的k值，观察他的曲线

从这个图中可以看出曲线还是比较陡峭的

错误率为10%时，倍数比为2时，错误率就会升至40%，这就比较危险了
错误率为1%时，倍数比为2时，错误率升至15%。
错误率为0.1%，倍数比为2时，错误率升至5%。

布隆过滤器的其他应用

在爬虫系统中，我们需要对URL进行驱虫，已经爬过的网页就可以不用爬了，但是URL太多了，几千万几个亿。如果用一个集合装下这些URL地址那是非常浪费空间的，这时候就可以考虑使用布隆过滤器，他可以大幅降低去重存储消耗，只不过也会使得爬虫系统错误少量的页面。

布隆过滤器在NoSql数据库领域使用非常广泛，我们平时用到的Hbase、Cassandra还有LevelDB、RocksDB内部都有布隆过滤器结构，布隆过滤器可以显著降低数据库IO请求数量，当用户来查询某个row时，可以先通过内存中的布隆过滤器过滤掉大量不存在的row请求，然后再去磁盘进行查询。

邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些正常的邮件被放进了垃圾邮箱目录中，这个就是误判所致，概率很低。