Redis 实用小技巧——神奇的 bitmap(上)

简介

早在《Redis 实用小技巧——一文教你如何选择合适的 Key 类型》一文中时,就有老铁跟我留言说:「听说签到用 bitmap 实现效率更高哦」。没错,我也曾「听说」过,而且在工作当中也确实用过,给我的感觉是:bitmap 确实是个神奇的东西。

很久之前就想写篇关于 bitmap 文章了,但是又感觉仅是介绍几个案例并不足以让大家认识到它的神奇之处,于是,我打算从理论基础到实战应用,分成三个部分来给大家介绍。

OK,现在就跟我一起走进神奇的 bitmap 吧~

什么是 bitmap ?

让我们先来看一组图:

5EPju9AQip.jpeg!large

一张由 ASCII 字符组成的「像素图片」,一张电影院选座示意图,一张经典的扫雷图片,三者有什么关系呢?

发挥一下你的想象力:是不是都像是在一个「矩阵」里,按规则进行了一些「占位」操作,然后使这些位置具有了某种「表达力」呢?

「矩阵」+「占位」+「表达力」,正是我们今天讨论的主角「bitmap」的功力所在

bitmap,网上有译作「位图」的,其实在我们的应用场景中,把它译为「位映射」更为贴切,为什么这么说呢?且听我道来。

我们把 bitmap 拆成两个词来看:bit 和 map 。bit 描述的是我们的数据结构,即通过 bit 位的形式来进行存储。map 描述的是算法,一种具有映射功能的算法。bit-map 连在一起就可以用一句话来描述它的特点:

通过映射算法将数据映射到固定的 bit 位进行存储

这么做有什么特性呢?或者说为什么要变着法的这么玩呢?别急,让我们从 bit 和 map 单独说一说。

bit 存储

bit 存储的思想离不开它的应用场景。首先让我们来看这样的一个应用场景:

判断某一个 int 类型数据是否存在于一个 int 类型的数据集中?

假设我们现在是一个长度为 4 的 int 类型数组:[1, 3, 5, 7],现在要判断 5 是否存在于这个数组中。
我们通常会这么做:首先我们需要把这个数组存下来。在 32 位的操作系统中,一个 int 类型的数据需要占用 4 个字节,四个 int 类型数据需要占用 16 字节,也就是说存储这个数组至少需要开辟 16 字节的内存空间。
如果现在有 20 亿 int 类型数据呢?需要分配多大空间呢?
2000000000 × 4 / 1024 / 1024 / 1024 ≈ 7.45 GB。是不是感觉快要撑爆了。
说明:
1 GB = 1024 MB
1 MB = 1024 KB
1 KB = 1024 Byte
1 Byte = 8 Bit

那有没有什么更好的存储办法呢?

让我们回过头来看一看这个场景:我们之所以需要 7.45 GB 的存储空间,是因为我们真真切切地把这些数据在计算机中存储下来了,但我们真的有必要把这些数据原封不动地存储下来吗?

还记得下面这个熟悉的画面吗?

le0poZ6DHQ.webp!large

曾几何时,一张纸也能代替三个人「占位」。如果后面的大哥不介意的话,一张纸将具有给三个人「占位」的威力。

联想到我们上面那个问题:我们的目的只是为了判断某个元素是否存在于一个数据集中。同样道理,我们能不能换种方式表达:判断某个位置上是否被「占用」呢?

这样,我们的处理思路就从原来的「存储数据」变成「位置赋值」了。那这样操作的话,存储空间上会带来什么变化呢?让我们来算一下:

同样还是 20 亿的 int 类型数据,这次我们需要申请 20 亿 bit 位的空间,占用的内存空间为:
2000000000 / 8 / 1024 / 1024 / 1024 ≈ 0.23 GB

比之前的方式节省了 32 倍的存储空间!是不是很划算呢?

但是你需要清楚,我们这么用是对应用场景有限制的:

  • 因为使用的是比特位 0 或 1 来表示是否占用,用位置「即偏移量」来表示具体的数值,所以「表达力」有限,仅限于「某个位置是否有值」或者「有多少位置被赋予了值」类似的应用场景
  • 与普通的 int 存储有所不同,在 32 位操作系统中,一个无符号的 int 类型占用 4 个字节,共 32 bit ,可以存储 0 - 2^32 - 1 之间的任意数值,而在位存储中,如果需要存储 2^32 - 1 这个数值的话,需要分配 2^32 个 bit 的内存空间,即 2^29 字节,512 MB 。可见,位存储分配的空间大小受到「最大边界」的影响,普通的存储则不会。反之,当数据集越来越大时,普通存储分配的空间也会随之变大,而位存储则不会发生变化(「最大边界」未发生变化的话)

由此可见,位存储只有在数据量巨大的时候,才能体现出它的优势,像简单的数据集,优势反而体现不出来。

让我们通过一张图来对比一下:

这个 1 byte 的比特位表示图,如果是普通存储的话,这里代表的是二进制整数 10001000 ,即十进制的 2^3 + 2^7 = 136 ,而在位存储中,这张图表达的含义则是:3 和 7 这两个位置被占用。直白点讲:前者表达的是整体的值,后者表达的是设置了值的偏移量。

map 映射

介绍完存储「数据结构」,接下来我们再来了解一下怎么存储的问题「算法」。我们把数据映射到具体的比特位的过程称之为「映射」,这里我们根据映射算法的区别来分成「普通映射」和「Hash 映射」介绍。

普通映射

因为在位存储中,偏移量都是通过整数来表示的,所以,所有通过整数来表达的数据我们都可以直接映射到对应的偏移量上。像上边的例子中,我们就是直接把需要存储的整数转换为对应的偏移量。

有些情况下,我们可能需要一些简单的逻辑转换,把数据转换成对应的偏移量。比如我们用 bitmap 来记录用户的签到情况,我们可以用日期来表示偏移量(20230605当成数字处理),bit 位的值表示是否签到。但这会导致我们初始分配的 bitmap 就很大,而且因为这样转换后的数字并不是连续的,在 bitmap 上会出现「断断续续」的数据分布。

更好的一种做法是换一种思路:我们可以单独记录下用户初始化签到的日期,然后用签到日期距离初始化日期的偏移量来当作 bitmap 的偏移量,这样处理就会好很多。

Hash 映射

在实际应用中,还有一些数据是无法直接用「普通映射」的方式映射成对应的偏移量的。比如,我们现在需要把每个人的信息记录到一张 bitmap 中,这里我们用用户的身份证号作为唯一标识,那么问题来了:如何把一个身份证号映射到对应的 bit 偏移量呢?

我们都知道,身份证号是一个 18 位的数字和字母(可能存在 X )组成的「字符串」,显然不能直接转换成一个整数。那可不可以通过某种算法,把一个「字符串」最终转换成一个「整数」呢?

我们可能需要一个类似以下功能的映射函数:

N = f(s)
说明:N 表示转换后的整数,f() 表示映射函数,s 表示需要转换的身份证号。

这种映射函数用更专业的叫法叫作「哈希算法」。一个好的哈希算法一般具有以下特点:

  • 正向快速: 给定明文和 Hash 算法,能在有限时间和有限资源内快速计算出 Hash 值
  • 逆向困难: 对于给定 Hash 值,在有限时间和资源内很难 (基本不可能) 逆推出明文
  • 输入敏感: 原始输入信息任意一点改动,产生的 Hash 值都应该是完全不同的
  • 冲突避免: 很难找到两段内容不同的明文,使得它们生成的的 Hash 值一致

其中「快速计算」和「均匀分布」是考量 Hash 算法是否优秀的两个主要原则。

一般情况下的哈希算法生成定长的二进制值串就可以了,但是在 bitmap 操作中,我们还需要将定长的二进制值串转成一个整数的偏移量,以达到「映射」到 bit 位的目的。

尽管一个优秀的哈希算法会尽可能地「避免冲突」,但概率再低的事件,并非意味着不可发生。当分布区间分布的值超过一定量时,碰撞的几率将会上升。所以在实战部分,我们会看到为了降低 Hash 碰撞产生的「误判」,我们将会同时通过多个 Hash 算法来计算映射的值。

总结

在本文中,我们并没有过多地介绍复杂的理论知识,而是尽量通过通俗易懂的语言,让大家对 bitmap 有更形象的认识。纵观全文,其实理解 bitmap 并不难,可以通过以下一句话来概括:

bit 位存储,哈希映射,赋予「表达力」。

在下篇部分《Redis 实用小技巧——神奇的 bitmap(下)》,我们将来介绍 Redis 中 bitmap 相关的内容。

感谢大家的持续关注~

本作品采用《CC 协议》,转载必须注明作者和本文链接
你应该了解真相,真相会让你自由。
本帖由系统于 1年前 自动加精
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 7

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!