Redis 大数据内存优化 (RoaringBitmap) - 简书

本文由 简悦 SimpRead 转码， 原文地址 www.jianshu.com

最近碰到手机设备匹配的业务, 用户在我司后台可以上传人群包, 里面存放的是设备的 MD5 标识符; 一个人群包大概有千万级的 MD5 数据, 与广告请求所携带设备标识进行匹配.

1. Key-Value 存储

尝试插入 1kw 条数据, key 为设备 MD5 值, value 为 1, 此时 Redis 中存在 1kw 条 key-value 键值对.

通过info指令查看内存占用:

1kw 数据 key-value 占用内存

结论:

• 可以看到, 1kw 条 MD5 数据占用 Redis 内存约为 892MB;
• 这还只是一个客户上传的人群包, 如果上传的人群包较多, 则 Redis 需要大量的集群部署, 成本会及其大;
• 无论是采用 List, Hash, Set 等结构都会出现这种情况, 所以 Redis 的这些数据结构都不适用;

2. BitMap 存储

原理

8bit = 1b = 0.001kb bitmap 即位图, 就是通过最小的单位 bit 来进行 0 或者 1 的设置，表示某个元素对应的值或者状态。 一个 bit 的值，或者是 0，或者是 1；也就是说一个 bit 能存储的最多信息是 2。

举例:

场景: 有用户 id 分别为 1, 2, 3, 4, 5, 6, 7, 8 的用户, 其中用户 2, 5 在今日登录, 统计今 日登录用户

采用位图存储: 用户 id 为偏移量, 可以看做是在位图中的索引, value 为 true

用户登录情况

通过bitcount获取登录用户数为 2:

登录用户数

测试 1:

测试 offset 从 1-1kw 连续整数时候的内存占用:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Jedis jedis = null;
        try {
            jedis = getJedis();
            Pipeline pipeline = jedis.pipelined();
            for (int offset = 0; offset < 10000000; offset ++) {
                pipeline.setbit("test", offset, true);
            }
            pipeline.sync();
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (jedis != null) jedis.close();
        }

可以发现内存占用仅为 1.19MB, 1 个亿的数据也才 12MB, 极大的减少了内存;

1kw 连续的正整数内存占用

测试 2:

由于我们的业务没有如此完美的情况出现, 采用设备 MD5 的 hash 做 Offset, 不会出现连续正整数的情况;

各常用 Hash 函数性能对比: https://byvoid.com/zhs/blog/string-hash-compare/

所以我们接下来测试 1kw 条 MD5 数据的位图内存占用:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

private void saveBitMap(List<String> values) {
        Jedis jedis = null;
        try {
            jedis = getJedis();
            Pipeline pipeline = jedis.pipelined();
            for (String arg : values) {
                int offset = arg.hashCode() & 0x7FFFFFFF;
                pipeline.setbit("audience_id", offset, true);
            }
            pipeline.sync();
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (jedis != null) jedis.close();
        }
    }

注意:

1. JAVA String 的哈希方法默认使用 BKDRHash;
2. java 字符串 hash 的返回值为有符号型 int, 所以会出现负数, 这里用 & 0x7FFFFFFF 转为无符号型, 或者使用 java 自带的Integer.toUnsignedString;

查看 Redis 内存占用:

1kwMD5 的 hash 内存占用

问题: 为什么同样 1kw 的 bitmap, MD5 数据的 Hash 占用会比测试一的多 200 倍?

1. Bitmap 索引一般用来存储整数。整数的范围是 0～2^{32-1. 所以如果用最朴素的思想, 一个 bit 位代表一个整数是否存在, 可以计算出所占用的大小就是 2}32/8/1024/1024 ＝ 512M. 而且再考虑到大多数情况下, bitmap 中元素不会太多, 反而是非常的稀疏, 用 512M 的空间来存储一个稀疏的 bitmap, 自然是不可接受的;
2. 就算测试 2kw, 3kw 条 MD5 数据, 也同样会占用这么大内存;

结论:

1. 256MB 的数据虽然相比 Key-Value 存储缩减了约 4 倍, 不过仍然比理想情况下的 bitmap 占用多出了 200 倍; 人群包较多的情况下同样无法适用;
2. 需要缩短非连续情况下 offset 的区间 (压缩算法)

3. RoaringBitmap

原理

将 32 位无符号整数按照高 16 位分桶，即最多可能有 216=65536 个桶，称为 container。存储数据时，按照数据的高 16 位找到 container（找不到就会新建一个），再将低 16 位放入 container 中。也就是说，一个 RBM 就是很多 container 的集合。

RoaringBitmap 容器构成

图中示出了三个 container：

• 高 16 位为 0000H 的 container，存储有前 1000 个 62 的倍数。
• 高 16 位为 0001H 的 container，存储有 [216, 216+100) 区间内的 100 个数。
• 高 16 位为 0002H 的 container，存储有 [2×216, 3×216) 区间内的所有偶数，共 215 个。

测试:

1kw 条 MD5 数据的插入:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

private void saveWithRoaringBitmap(List<String> values) throws IOException {
        int[] offsets = new int[values.size()];
        for (int i = 0; i < values.size(); i ++) {
            int offset = values.hashCode() & 0x7FFFFFFF;
            offsets[i] = offset;
        }

        MutableRoaringBitmap mrb = MutableRoaringBitmap.bitmapOf(offsets);
        ByteBuffer outbb = ByteBuffer.allocate(mrb.serializedSizeInBytes());
        mrb.serialize(new DataOutputStream(new OutputStream(){
            ByteBuffer mBB;
            OutputStream init(ByteBuffer mbb) {mBB=mbb; return this;}
            public void close() {}
            public void flush() {}
            public void write(int b) {
                mBB.put((byte) b);}
            public void write(byte[] b) {mBB.put(b);}
            public void write(byte[] b, int off, int l) {mBB.put(b,off,l);}
        }.init(outbb)));
        outbb.flip();

        // Base64编码后存入Redis
        String encodeString = Base64.getEncoder().encodeToString(outbb.array());
        getJedis().set("roaringMap", encodeString);
    }

RoaringBitMap 内存占用

结论:

1. 采用压缩算法后的 bitmap, 内存占用比 Key-value 缩减 100 倍, 比 Redis 自带的 bitmap 缩减 10 倍;
2. 由于 RoaringBitmap 中容器的不同, 包括 offset 的稀散性, 还是比理想的连续整型 offset 大了越 20 倍内存
3. 大家可以测试一下 2kw, 3kw 数据, 数据越多, offset 离散区间越小, 所取得的压缩效果也会更好

注意:

1. 以上代码在服务器中不考虑内存的情况下, 如果连续 for 循环 kw 次对服务器内存占用还是挺大; 特别是在服务器连接数较高时候;
2. 亿级数据, RoaringBitmap 存入 Redis 也有几十 MB 的内存占用, 每读取一次都会比较耗时; 所以建议在实际项目中对 offset 进行分片存储, 减少每次读取的耗时