欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

Redis从精通到入门——bitmap实现源码详解

时间:2023-07-09
Redis数据类型之bimap详解

bitmap简介

bitmap常用操作应用场景源码阅读 布隆过滤器

图解布隆过滤器 bitmap简介

    bitmap 在Redis 中又叫 bitops ,它就是通过一个bit位来表示某个元素对应的值或者状态。
    bitmap 的实现在Redis中其实并没有去新增加一个数据类型,它的底层实现其实就是一个 String也就是一个char buf[]。而大家要知道1Byte = 8bit,所以这个数组中每一个下标对应8个元素的状态。
    bitmap 其中的key也就是元素,key只能为>=0的整数则可以当成基于bit位的 偏移量 Redis中 我们可以叫它 offset,所以它们就像数组的下标一样不需要额外的空间保存,每一次getbit/setbit都可以当做是对数组下标所对应的值的一次操作,所以bitmap本身会极大的节省储存空间。

优点

节省空间效率高setbit和getbit的时间复杂度都是O(1),其他位运算效率也高 缺点

本质上位只有0和1的区别,所以一般只能用于状态记录对于需要统计的key的数量不大,但key与key之前跨度较大的场景不适用 bitmap常用操作

SETBIT key offset value :设置或修改key上的偏移量(offset)的位(value)的值;return的不是成功失败状态,而是所修改的偏移量上原来存储的旧的值GETBIT key offset :返回指定key上偏移量(offset)的值,若key不存在,那么返回0;BITCOUNT key :返回指定key上被bit位被设置为 1 的数量;BITOP operation destkey key [key …] :

BITOP and destkey key [key …] :对一个或多个key逻辑并,结果保存到destkey;BITOP or destkey key [key …] :对一个或多个key逻辑或,结果保存到destkey;BITOP xor destkey key [key …] :对一个或多个key逻辑异或,结果保存到destkey;BITOP not destkey key :对一个key逻辑非,结果保存到destkey;注意哦 NOT操作时,key只能有一个
应用场景

各种用户活跃/登录统计广播消息用户已读未读标记 源码阅读

因为 bitmap 并不是一个新的数据类型,其表现形式是一个 char buf[],所以咱们拿setbit的源码出来看看吧

void setbitCommand(client *c) { robj *o; char *err = "bit is not an integer or out of range"; size_t bitoffset; ssize_t byte, bit; int byteval, bitval; long on; // 解析 offset if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK) return; // 解析 value if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != C_OK) return; if (on & ~1) { addReplyError(c,err); return; } if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return; byte = bitoffset >> 3; // 获取对应的字节 byteval = ((uint8_t*)o->ptr)[byte]; // 算出 bit 的位置(基于当前字节) bit = 7 - (bitoffset & 0x7); // 获得bit旧值用于操作成功后的return bitval = byteval & (1 << bit); byteval &= ~(1 << bit); byteval |= ((on & 0x1) << bit); ((uint8_t*)o->ptr)[byte] = byteval; // 发送修改通知 signalModifiedKey(c,c->db,c->argv[1]); notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id); server.dirty++; // 向客户端返回旧的值 addReply(c, bitval ? shared.cone : shared.czero);}

布隆过滤器

    布隆过滤器(Bloom Filter)是由Howard Bloom在1970年提出的一种比较巧妙的概率型数据结构,它可以告诉你某种东西 一定不存 在或者 可能存在 。当布隆过滤器说,某种东西存在时,这种东西可能不存在;当布隆过滤器说,某种东西不存在时,那么这种东西一定不存在。
    而布隆过滤器便是基于 bitmap 实现的。
    布隆过滤器的核心便是将key进行 n 次不同的 hash运算,得到n个不同的hash值,然后以hash值为 偏移量(offset) ,在bitmap中将偏移量(offset)对应的值进行标记为1。任何key进入判断是否存在时都会通过那些hash函数计算出对应的n个hash值,然后去判断hash值对应的 **偏移量(offset)**的value 是否全部等于1。如果有任何一个值为0,则该Key一定不存在;否则该Key可能存在。

图解布隆过滤器

看看布隆过滤器如何解决 缓存穿透 问题。

你的点赞就是我创作的最大动力,如果写的不错,来个三连行不行

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。