前言：
布隆过滤器有很多使用场景比如说反垃圾邮件，从数十亿的垃圾邮件列表中判断某邮件是否为垃圾。或者说解决缓存击穿问题。或者在一些去重场景中都可以使用到，例如推送新闻不重复。
布隆过滤器是redis的一个插件功能，redis4.0之后提供了插件功能才正式登场。
bloomfilter版本：v1.1.1
参考资料：
redis modulesAPI：
http://www.redis.cn/topics/modules-api-ref.html
Bloom_filter:
https://en.wikipedia.org/wiki/Bloom_filter
Byte pair encoding ：
https://en.wikipedia.org/wiki/Byte_pair_encoding
（一）安装布隆过滤器插件
下载
#wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz
解压并且编译
#tar -zxvf v1.1.1.tar.gz
#cd RedisBloom-1.1.1/
#make
配置redis.conf
loadmodule /Users/edz/Desktop/src-source/RedisBloom-1.1.1/rebloom.so
启动
#redis-server redis.conf
（二）命令解析
//布隆过滤器命令
#指定错误率
BF.RESERVE
#添加布隆过滤
BF.ADD
#添加多个值到过滤器中
BF.MADD ...
#该命令将向bloom过滤器添加一个或多个项，如果它还不存在，则默认情况下创建它。
BF.INSERT [CAPACITY {cap}] [ERROR {ERROR}] [NOCREATE] ITEMS {item…}
#判断值是否存在
BF.EXISTS
#判断多个值是否存在
BF.MEXISTS ..
#查看键值相关信息
BF.DEBUG
#布隆过滤持久化操作
BF.SCANDUMP
BF.LOADCHUNK
// 布谷鸟过滤器命令
#指定布谷鸟过滤器错误率
CF.RESERVE
#添加布谷鸟过滤
CF.ADD
#该命令将布谷鸟过滤器添加一个或多个项，如果它还不存在，则默认情况下创建它。
CF.INSERT [CAPACITY {cap}] [ERROR {ERROR}] [NOCREATE] ITEMS {item…}
#判断布谷鸟过滤器值是否存在
CF.EXISTS
#判断布谷鸟过滤器多个值是否存在
CF.MEXISTS ..
#统计布谷鸟过滤器某个键值出现次数
CF.COUNT
#删除布谷鸟过滤器某个键值
CF.DEL
#布谷鸟过滤器持久化
CF.SCANDUMP
CF.LOADCHUNK
#查看布谷鸟过滤器键值相关信息
CF.DEBUG
布谷鸟过滤器与布隆过滤器相比，布谷鸟过滤器占用资源相对来说少一些。并且精准度会更高一些，还支持删除命令。和统计命令。
(三) 如何编写一个modules
3.1 如下是一个简单的例子：
#include"redismodule.h"
#include
intHelloworld_RedisCommand(RedisModuleCtx *ctx, RedisModuleString **argv, int argc) {
RedisModule_ReplyWithLongLong(ctx,1);
return REDISMODULE_OK;
}
intRedisModule_OnLoad(RedisModuleCtx *ctx, RedisModuleString **argv, int argc) {
if (RedisModule_Init(ctx,"helloworld",1,REDISMODULE_APIVER_1)
== REDISMODULE_ERR) return REDISMODULE_ERR;
if (RedisModule_CreateCommand(ctx,"helloworld.get",
Helloworld_RedisCommand) == REDISMODULE_ERR)
return REDISMODULE_ERR;
return REDISMODULE_OK;
}
RedisModule_OnLoad在每个插件中都会存在，它是要初始化模块、注册其命令以及可能使用的其他私有数据结构的入口点。
RedisModule_OnLoad函数中如小例子，我们会调用两个函数：
RedisModule_Init 和RedisModule_CreateCommand，RedisModule_Init用于初始化Module信息。
而我们Helloworld_RedisCommand函数，是通过RedisModule_CreateCommand注册的一个命令。
（四）原理解析
4.1什么是布隆过滤器
布隆过滤器可以理解成一个不精准的set结构,你用它可以判断某个值是否存在。但是由于布隆过滤器也不是特别精准，不过可以通过参数设置。只要参数合理，它的精准度相对来说足够精准，只会有小小的误判。
一个布隆过滤器是一串被指为0的数组。如果要知道某个值是否存在。通过hash获得这个值的位置，这个值的位置为1则是存在。
4.2 命令注册
intRedisModule_OnLoad(RedisModuleCtx *ctx, RedisModuleString **argv, int argc) {
if (RedisModule_Init(ctx, "bf", REBLOOM_MODULE_VERSION, REDISMODULE_APIVER_1) !=
REDISMODULE_OK) {
return REDISMODULE_ERR;
}
//。。。省略
#define CREATE_CMD(name, tgt, attr) //创建命令宏 \
do { \
if (RedisModule_CreateCommand(ctx, name, tgt, attr, 1, 1, 1) != REDISMODULE_OK) { \
return REDISMODULE_ERR; \
} \
} while (0)
#define CREATE_WRCMD(name, tgt) CREATE_CMD(name, tgt, "write deny-oom")
#define CREATE_ROCMD(name, tgt) CREATE_CMD(name, tgt, "readonly fast")
CREATE_WRCMD("BF.RESERVE", BFReserve_RedisCommand);
CREATE_WRCMD("BF.ADD", BFAdd_RedisCommand);
CREATE_WRCMD("BF.MADD", BFAdd_RedisCommand);
CREATE_WRCMD("BF.INSERT", BFInsert_RedisCommand);
CREATE_ROCMD("BF.EXISTS", BFCheck_RedisCommand);
CREATE_ROCMD("BF.MEXISTS", BFCheck_RedisCommand);
// Bloom - Debug
CREATE_ROCMD("BF.DEBUG", BFInfo_RedisCommand);
// Bloom - AOF
CREATE_ROCMD("BF.SCANDUMP", BFScanDump_RedisCommand);
CREATE_WRCMD("BF.LOADCHUNK", BFLoadChunk_RedisCommand);
// Cuckoo Filter commands
CREATE_WRCMD("CF.RESERVE", CFReserve_RedisCommand);
CREATE_WRCMD("CF.ADD", CFAdd_RedisCommand);
CREATE_WRCMD("CF.ADDNX", CFAdd_RedisCommand);
CREATE_WRCMD("CF.INSERT", CFInsert_RedisCommand);
CREATE_WRCMD("CF.INSERTNX", CFInsert_RedisCommand);
CREATE_ROCMD("CF.EXISTS", CFCheck_RedisCommand);
CREATE_ROCMD("CF.MEXISTS", CFCheck_RedisCommand);
CREATE_ROCMD("CF.COUNT", CFCheck_RedisCommand);
// Technically a write command, but doesn't change memory profile
CREATE_CMD("CF.DEL", CFDel_RedisCommand, "write fast"); //谢
// AOF:
CREATE_ROCMD("CF.SCANDUMP", CFScanDump_RedisCommand);
CREATE_WRCMD("CF.LOADCHUNK", CFLoadChunk_RedisCommand);
CREATE_ROCMD("CF.DEBUG", CFInfo_RedisCommand);
//...省略
return REDISMODULE_OK;
}
代码中我们可以看到注册命令时，携带了一些内容如"readonly fast"，这个是创建命令的信号量， 限定了命令的操作，用空格隔开的C 字符串组成。信号量如下：
“write”: 该命令会修改数据集
“readonly”: 该命令仅返回值，不做修改
“admin”: 管理命令(可以调整复制或类似操作)
“deny-oom”: 该命令使用额外内存，在内存超用的场景下应当被拒绝
“deny-script”: 禁止使用Lua 脚本
“allow-loading”: 允许Redis 服务器加载数据时执行该命令，只有不和数据集交互的命令在该模式下被允许执行。否则不设置该信号量。
“pubsub”: 该命令回想发布/订阅频道里发布内容.
“random”: 该命令接收相同的输入可能会有不同的输出
“allow-stale”: 该命令允许在slave上执行，即使slave提供的数据不一致。
“no-monitor”: 不监控该命令。如果命令参数有敏感数据可以使用该设置
“fast”: 该命令的时间复杂度应当低于O(log(N)),其中N是集合的大小等
“getkeys-api”: 该命令实现了返回keys的接口。
“no-cluster”: 该命令不在Redis群集中注册，因为该命令不是为群集设计的。
3.3判断布隆过滤是否存在
bloom 链条结构：
typedefstructSBChain {
SBLink *filters; //< 当前过滤器
size_t size; //< 所有过滤器中的项目总数
size_t nfilters; //< 链节数
unsigned options; //< 直接传递给bloom_init的选项
} SBChain;
bloom link结构：
typedefstructSBLink {
structbloominner;//< bloom内部结构
size_t size; // < 链接中的项目数
} SBLink;
bloom结构
structbloom {
uint32_t hashes; //哈希 hashes = bpe * ln(2)
uint8_t force64; //总是强制64位哈希，即使太小
uint8_t n2; //取模使用，这个参数是用于64和32的取模
uint32_t entries; //条目个数：要插入的条目的预期数目。必须至少1000（实际上，可能要大得多）。
double error; //错误率：碰撞概率（只要条目不是超出）。
double bpe; //字节对编码，用于计算。
unsignedchar *bf; //过滤器字符串
size_t bytes; //字节数
uint32_t bits; //位数，最佳位数bits = (entries * ln(error)) / ln(2)^2
};
判断布隆命令是否存在方法：
/**
* Check for the existence of an item
* BF.CHECK
* Returns true or false
*/
staticintBFCheck_RedisCommand(RedisModuleCtx *ctx, RedisModuleString **argv, int argc) {
RedisModule_AutoMemory(ctx);
int is_multi = isMulti(argv[0]);
if ((is_multi == 0 && argc != 3) || (is_multi && argc < 3)) {
RedisModule_WrongArity(ctx);
return REDISMODULE_ERR;
}
RedisModuleKey *key = RedisModule_OpenKey(ctx, argv[1], REDISMODULE_READ);
SBChain *sb;
int status = bfGetChain(key, &sb); //获得key链条
int is_empty = 0;
if (status != SB_OK) { . //判断key是否为空
is_empty = 1;
}
// Check if it exists?
if (is_multi) {
RedisModule_ReplyWithArray(ctx, argc - 2);
}
for (size_t ii = 2; ii < argc; ++ii) {
if (is_empty == 1) { //空情况下直接返回0
RedisModule_ReplyWithLongLong(ctx, 0);
} else {
size_t n;
constchar *s = RedisModule_StringPtrLen(argv[ii], &n);
int exists = SBChain_Check(sb, s, n); //检测值是否存在
RedisModule_ReplyWithLongLong(ctx, exists);
}
}
return REDISMODULE_OK;
}
检测链条值是否存在
intSBChain_Check(const SBChain *sb, constvoid *data, size_t len) {
bloom_hashval hv = SBChain_GetHash(sb, data, len); //计算链条hansh
for (int ii = sb->nfilters - 1; ii >= 0; --ii) {
if (bloom_check_h(&sb->filters[ii].inner, hv)) { .
return1;
}
}
return0;
}
//通过hash值，计算映射到字符串的哪个字节上
intbloom_check_h(const struct bloom *bloom, bloom_hashval hash) {
if (bloom->force64 || bloom->n2 > 31) {
return bloom_check_add64((void *)bloom, hash, MODE_READ);
} elseif (bloom->n2 > 0) {
return bloom_check_add32((void *)bloom, hash, MODE_READ);
} else {
return bloom_check_add_compat((void *)bloom, hash, MODE_READ);
}
}
#define CHECK_ADD_FUNC(T, modExp) \
T i; \
int found_unset = 0; \
const register T mod = modExp; \
for (i = 0; i < bloom->hashes; i++) { \
T x = ((hashval.a + i * hashval.b)) % mod; \
if (!test_bit_set_bit(bloom->bf, x, mode)) { \
if (mode == MODE_READ) { \
return0; \
} \
found_unset = 1; \
} \
} \
if (mode == MODE_READ) { \
return1; \
} \
return found_unset;
//32位检测
staticintbloom_check_add32(struct bloom *bloom, bloom_hashval hashval, int mode) {
CHECK_ADD_FUNC(uint32_t, (1 << bloom->n2));
}
//64位检测
staticintbloom_check_add64(struct bloom *bloom, bloom_hashval hashval, int mode) {
CHECK_ADD_FUNC(uint64_t, (1LLU << bloom->n2));
}
判断bf字符串存放hash位置
inlinestaticinttest_bit_set_bit(unsignedchar *buf, uint64_t x, int mode) {
uint64_t byte = x >> 3;
uint8_t mask = 1 << (x % 8);
uint8_t c = buf[byte]; // 获得对应的字节，高昂的内存访问
if (c & mask) {
return1;
} else {
if (mode == MODE_WRITE) { //写字节
buf[byte] = c | mask;
}
return0;
}
}
通过计算出来的hash取模计算bf字符串的值是否设置，这一块很类似我们的bit存储结构。
总结：
1.布隆过滤器是redis的一个插件功能；
2.布隆过滤器有很多使用场景比如说反垃圾邮件，从数十亿的垃圾邮件列表中判断某邮件是否为垃圾。或者说解决缓存击穿问题。或者在一些去重场景中都可以使用到，例如推送新闻不重复。
3.bloomfilter过滤器插件除了布隆过滤器以外，还有布谷鸟过滤器。布谷鸟过滤器会比布隆过滤器多一个DEl功能。而且携带统计功能。
4.RedisModule_OnLoad在每个插件中都会存在、RedisModule_Init用于初始化Module信息、RedisModule_CreateCommand注册的一个命令。
5.数据存储在bloom 中的bf字符串中，是通过hash取模后。存储到bf字符串中。
