.NET/C# 使用 Redis 基于 BitMap 实现布隆算法

小渣渣 · 发表于 2023-1-2 17:37:01

需求：最近在 B 站看到一个 Redis 布隆算法的视频，解决缓存穿透的问题，简单来说就是在访问数据库前在加一层逻辑判断，判断数据是否存在，存在的话再去访问数据库。例如：某网站是一个新闻系统，文章的 URL 都是通过自增主键 Id 生成的（网址格式示例：/news-1.html），网站可能只有几万篇文章并且有缓存，如果攻击者通过这个规则恶意构造几百万的 Id 去访问，那么这些肯定无法命中缓存，从而直接访问数据库，从而对数据库造成压力。

原来：

请求新闻资源 -> 判断缓存是否存在 -> 存在 -> 缓存返回数据。
请求新闻资源 -> 判断缓存是否存在 -> 不存在 -> 从数据库查询 -> 存在 -> 缓存并返回数据。
请求新闻资源 -> 判断缓存是否存在 -> 不存在 -> 从数据库查询 -> 不存在 -> 返回 404 错误。

现在：

请求新闻资源 -> 布隆算法 -> 存在 -> 走原来的逻辑。
请求新闻资源 -> 布隆算法 -> 不存在 -> 直接返回 404错误。

布隆算法（BloomFilter）

BloomFilter算法，是一种大数据排重算法。在一个数据量很大的集合里，能准确断定一个对象不在集合里；判断一个对象有可能在集合里，而且占用的空间不大。它不适合那种要求准确率很高的情况，零错误的场景。通过牺牲部分准确率达到高效利用空间的目的。

布隆算法是一个以牺牲一定的准确率来换取低内存消耗的过滤算法，可以实现大量数据的过滤、去重等操作。

布隆算法只是一个抽象的概念，实现方式有很多种，文章中利用 Redis 中 BitMap 只是简单的实现。

参考：超链接登录可见。

BitMap 介绍

BitMap就是位图，其实也就是字节数组（byte array），用二进制表示，只有 0 和 1 两个数字，位图就是用每一个二进制位来存放或者标记某个元素对应的值。通常是用来判断某个数据存不存在的，因为是用bit为单位来存储所以Bitmap本身会极大的节省储存空间。

如下图字符串在计算机里是由二进制的形式保存的。

QQ截图20230102163903.jpg

Redis 中 BitMap 数据类型

Redis提供的数据类型BitMap（位图），每个bit位对应0和1两个状态。虽然内部还是采用String类型存储，但Redis提供了一些指令用于直接操作BitMap，可以把它看作一个bit数组，数组的下标就是偏移量。

它的优点是内存开销小，效率高且操作简单。

节省空间：通过一个bit位来表示某个元素对应的值或者状态，其中key就是对应元素的值。实际上8个bit可以组成一个Byte，所以是及其节省空间的。
效率高：setbit和getbit的时间复杂度都是O(1)，其他位运算效率也高。

使用set集合和BitMap存储的对比如下：

数据类型	每个 userid 占用空间	需要存储的用户量	全部占用内存量
set（集合）	32位也就是4个字节（假设userid用的是整型，实际很多网站用的是长整型）	50,000,000	32位 * 50,000,000 = 200 MB
BitMap	1 位（bit）	100,000,000	1 位 * 100,000,000 = 12.5 MB

时间在拉长一点

	一天	一个月	一年
set（集合）	200M	6G	72G
BitMap	12.5M	375M	4.5G

计算后发现随着时间的增加，要记录数据量的增加，对比更加明显了，BitMap所占的空间比set（集合）更少。

Redis提供了以下几个指令用于操作BitMap：

命令	说明	可用版本	时间复杂度
超链接登录可见。	对 key 所储存的字符串值，设置或清除指定偏移量上的位(bit)。	>= 2.2.0	O(1)
超链接登录可见。	对 key 所储存的字符串值，获取指定偏移量上的位(bit)。	>= 2.2.0	O(1)
超链接登录可见。	计算给定字符串中，被设置为 1 的比特位的数量。	>= 2.6.0	O(N)
超链接登录可见。	返回位图中第一个值为 bit 的二进制位的位置。	>= 2.8.7	O(N)
超链接登录可见。	对一个或多个保存二进制位的字符串 key 进行位元操作。	>= 2.6.0	O(N)
超链接登录可见。	BITFIELD 命令可以在一次调用中同时对多个位范围进行操作。	>= 3.2.0	O(1)