Redis 数据结构-Bitmap 和 HyperLogLogs

服务器

浏览数:79

2020-6-21


相关文章

Redis 初探-安装与使用

Redis 数据结构-字符串源码分析

Redis 数据结构-字典源码分析

Redis 分布式锁

文章将从以下方面介绍

前言

Redis 操作 Bitmap

Bitmap 原理

java 位运算

HyperLogLogs 使用

HyperLogLogs 原理

前言

在开发中,可能会遇到这种情况:需要统计用户的某些信息,如活跃或不活跃,登录或者不登录;又如需要记录用户一年的打卡情况,打卡了是1, 没有打卡是0,如果使用普通的 key/value存储,则要记录365条记录,如果用户量很大,需要的空间也会很大,所以 Redis 提供了 Bitmap 位图这中数据结构,Bitmap 就是通过操作二进制位来进行记录,即为 0 和 1;如果要记录 365 天的打卡情况,使用 Bitmap 表示的形式大概如下:0101000111000111………………………,这样有什么好处呢?当然就是节约内存了,365 天相当于 365 bit,又 1 字节 = 8 bit , 所以相当于使用 46 个字节即可。当然,由于公司业务关系,我还没有遇到这种需求 ^ ^。

Redis 操作 Bitmap

setbit 设置操作

set key offset value :  设置 key 的第 offset 位为value

比如 key = 010101101

现在想把 4 这个位置的值设置为 0 ,即上述红色的位置,可以进行如下操作:

set key 4 0

getbit 获取操作

get key offset 获取某个位上的值

如获取上述 5 这个位置上的值,可以进行如下操作:

get key 5

bitcount 统计操作

bitcount key [start, end] 统计 key 上位为1的个数

如果想获取 上述 key 中1的个数,可以进行如下操作

bitcount key

 

使用 bitmap 来记录上述事例中一周的打卡记录如下所示:

周一:1,周二:0,周三:0,周四:1,周五:1,周六:0,周天:0 (1 为打卡,0 为不打卡)

统计这周打卡的记录,可以看到只有3天是打卡的状态:

Redis 的 Bitmap 还有其他的操作,可以参考Redis 命令

Bitmap 原理

接下来看下 Bitmap 的原理,下面以 Java 中 int 类型举例;

Java 中 int 类型占用 4 个字节,即 4 byte,又 1 byte = 8 bit,所以 一个 int 数字的表示大概如下,

试想以下,如果有一个很大的 int 数组,如 10000000,数组中每一个数值都要占用 4 个字节,则一共需要占用 10000000 * 4 = 40000000 个字节,即 40000000 / 1024.0 / 1024.0 = 38 M,下面用程序验证下:

    final Runtime runTime = Runtime.getRuntime();

    public static int[] normalArray(int size)
    {
        // 获取剩余内存容量
        long t1 = runTime.freeMemory();

        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = i;
        }
        
        long t2 = runTime.freeMemory();
        
        System.out.println(String.format("共占用内存 %s M", (t1-t2) / 1024.0 / 1024.0));
        
        return arr;
    }

    public static void main(String[] args) {
        int size = 10000000;
        normalArray(size);
    }

结果如下:

共占用内存 38.14698791503906 M

可以看到和上面手动计算的一样。

此时,如果使用 bit 来存放上述 10000000 个元素,只需要 10000000 个 bit 即可, 10000000 / 8.0 / 1024.0 / 1024.0 = 1.19 M 左右,可以看到 bitmap 可以大大的节约内存。

使用 bit 来表示数组 [1, 2, 5] 如下所示,可以看到只用 1 字节即可表示:

接下来看下 Java 是如何表示用 Bitmap 来表示上述的大数组的;

 首先定义一个 byte 数组,根据初始容量来分配数组的大小 capacity = ( size >> 3 ) + 1:

    public byte[] bitemapArray(int size){

        byte[] arr = new byte[(size >> 3) + 1];

        return arr;
    }

byte 数组的容量为什么是 ( size >> 3 ) + 1? 还是因为 1 个字节 = 8 bit ,比如传入的大小 size = 7 ,则 capacity = ( 7 >> 3) + 1 = 1

之后,向数组中添加值,即把对应的位设置为 1,步骤如下:

1. 首先找到 byte 中的索引 index,计算公式 index = n / 8 = n >> 3

2. 找到 byte[index] 中对应的位置 position ,计算公式 position = n % 8 = n & 0x07 (因为下标从 0 开始)

3. 将 byte[inex] 和 1 << positon 做或(|)运算

代码如下:

    public void add(byte[] arr, int val)
    {
        // num/8得到byte[]的index
        int index = val >> 3; // val / 8

        // num%8得到在byte[index]的位置
        int position = val & 0x07;

        arr[index] |= 1 << position;
    }

如果现在 Bitmap 如下:

之后,将 5 添加到 Bitmap 中,index = 5 / 8 = 0,  position = 5 & 0x07 = 5,所以需要将上图中的第 5 位设置为 1:

1 << position 即 1 << 5 如下:

arr[index]  |= 1 << position 如下:

可以看到 Bitmap 中的第 5 位已经成功设置为 1 。

判断 Bitmap 中是否包含某个值,如上述的 Bitmap 中是否包含 5 ,也就是 5 对应的位是否为 1 即可,步骤如下:

Bitmap 为:

1.  position = 5 & 0x07 = 5

1 << position 即 1 << 5 如下:

2. 使用 byte[index]  =&  (1 << position)

3. 查看第 2 步的值是否为 1 ,如果为 1 则包含,否则不包含

    public boolean contain(byte[] arr, int val){
        int index = val >> 3;
        int position = val & 0x07;

        int a = arr[index] & (1 << position);
        return a != 0;
    }

 

删除 Bitmap 中的某个值,即把对应位设置为 0 ,如果把上述的 Bitmap 中 5 删除,则步骤如下:

Bitmap 为:

1.  position = 5 & 0x07 = 5

~(1 << position)即  ~(1 << 5) 如下:

2. byte[index] =& ~(1 << position)

可以看到 position 位置的值被设置为 0,代码如下:

    public void remove(byte[] arr, int val){
        int index = val >> 3;
        int position = val & 0x07;
        arr[index] &= ~(1 << position);
    }

 

现在使用 Bitmap 来测试以下刚开始的那个大数组例子,看下占用的内存是多大:

首先看下 bitemapArray 方法:

    public byte[] bitemapArray(int size){

        long t1 = runTime.freeMemory();

        byte[] arr = new byte[(size >> 3) + 1];

        for (int i = 1; i <= size; i++) {
            add(arr, i);
        }
        long t2 = runTime.freeMemory();

        System.out.println(String.format("共占用内存 %s M", (t1-t2) / 1024.0 / 1024.0));

        return arr;
    }

    public static void main(String[] args) {

        int size = 10000000;
        byte[] ret = test.bitemapArray(size);

        boolean isContain = test.contain(ret, 5555);
        System.out.println(isContain); // true

        test.remove(ret, 5555);
        boolean isContain2 = test.contain(ret, 5555);
        System.out.println(isContain2); // false

        boolean isContain3 = test.contain(ret, 9999999);
        System.out.println(isContain3); // true

    }

结果:共占用内存 1.1921157836914062 M

可以看到 10000000 个数字只用 1.2 M的内存,和上面手动计算的一致,此外,还测试了 remove 方法和 contain 方法,都是可以工作的。

以上就是 Bitmap 的一个实现原理

位运算

Java 的位运算包括 :与(&),或(|),非(~),异或(^),左移(<<),右移(>>),无符号右移(>>>)。

与运算(&)

两个数进行与(&)操作,对应的二进制位都为 1 则结果为 1,只要有一个为 0 ,则结果为 0,即:

1 & 1 = 1

1 & 0 = 0

0 & 0 = 0

例子:5 & 6 = 4

 5 的二进制表示为:0 0 0 0 0 1 0 1,6 的二进制为:0 0 0 0 0 1 1 0,5 & 6 如下:

 

或运算(|)

两个数进行或运算(|)操作,对应的二进制位只要有一个为 1 则结果为 1,即:

1 | 1 = 1

1 | 0 = 1

0 | 0 = 0

例子:5 | 6 = 7

 5 的二进制表示为:0 0 0 0 0 1 0 1,6 的二进制为:0 0 0 0 0 1 1 0,5 | 6 如下:

非(~)运算

非是一元操作符,对应的二进制位取反,0 变 1,1 变 0

0 0 0 0 0 1 0 1  -> 1 1 1 1 1 0 1 0

异或(^)

两个数进行异或(^)操作,对应的二进制位如果相同,则为 0,不同则为 1 ,即:

1 ^ 1 = 1

1 ^ 0 = 0

0 ^ 0 = 1

例子:5 ^ 6 = 3

 5 的二进制表示为:0 0 0 0 0 1 0 1,6 的二进制为:0 0 0 0 0 1 1 0,5 | 6 如下:

左移(<<)

二进制左移整体向左边移动,低位补 0 ,高位截断

例子:5 << 3 =  40

 5 的二进制表示为:0 0 0 0 0 1 0 1 ,左移 3 为如下:

右移(>>)

二进制左移整体向右边移动,高位补 0 ,低位截断

例子:5 >> 3 =  0

 5 的二进制表示为:0 0 0 0 0 1 0 1 ,右移 3 为如下:

无符号右移(>>>)

Java 中,最高位用来表示符号为,正数为 0,负数为 1,如果是负数,右移的时候,高位补 1 ,如果是无符号右移的时候,则高位补 0:

-5 >> 3 = -1

-5 >>> 3 = 536870911

HyperLogLog

Redis 的 HyperLogLog 提供了一种不太准确的基数统计方法,如统计页面的 UV (unique visitor),指访问某个站点或点击某条新闻的不同IP地址的人数),它的标准误差是 0.81%;接下来看下 HyperLogLog 的操作:

Redis 的 HyperLogLog  一共有三个:pfadd,  pfcount,  pfmerge :

pfadd 用于增加计数,pfcount 用于统计计数,而 pfmerge 用于将多个计数合并在一起,如下所示;

上述例子中, p1 添加了 6 个元素,pfcount 统计个数为 6 ,统计是正确的,p2 也添加了 6 个元素,pfcount 统计个数也是正确的,使用 pfmerge 来把 p1 中的值合并到 p2 中去,因为 p1 , p2 有两个元素是重复的,所有 p2 的统计个数为 10 个,也是正确的,接下来使用代码插入更多的数据看下统计是否正确:

    public static void main(String[] args) {

        Jedis jedis = new Jedis("127.0.0.1", 6379);

        float size = 10000000;

        for (int i = 0; i < size; i++) {
            jedis.pfadd("myk", "mky-" + i);
        }
        long total = jedis.pfcount("myk");
        System.out.println(String.format("统计个数: %s", total));
        System.out.println(String.format("正确率: %s", (total / size)));
        System.out.println(String.format("误差率: %s", 1 - (total / size)));
        jedis.close();
    }

结果:

统计个数: 9963787
正确率: 0.9963787
误差率: 0.0036212802

可以看到还是很正确的。

HyperLogLog 原理

HyperLogLog 的原理很复杂,反正我是没有看懂,有时间再看看吧,可以参考 神奇的HyperLogLog算法

 

 

作者:TSMYK