Tair Bloom介绍,命令列表 -

Bloom是一种概率性数据结构（space-efficient probabilistic data structure），在大规模数据中，仅需消耗较低的内存来判断一个元素是否存在。而TairBloom基于Scalable Bloom Filter实现，具有动态扩容的能力，并且可以在扩容时维持误判率的稳定性。

TairBloom简介

在传统的Redis数据结构中，可以使用Hash、Set、String的Bitset等实现类似功能，但这些实现方式不是内存占用量非常大，就是无法动态伸缩和保持误判率不变。因此，TairBloom非常适合需要高效判断大量数据是否存在且允许一定误判率的业务场景。业务可以直接使用TairBloom提供的Bloom Filter（布隆过滤器）接口，无需二次封装，更无需在本地实现布隆过滤器的功能。

主要特性

内存占用低。
可动态扩容。
可自定义的误判率（False Positive Rate）且在扩容时保持不变。

典型场景

适用于直播、音乐、电商等行业的推荐系统或爬虫系统等，例如：

推荐系统：将用户读过的文章通过TairBloom记录，并在给用户推荐新文章前进行查询，实现给用户推荐感兴趣，且没读过的文章。
爬虫系统：在面对海量的URL时，将已经爬取过的URL进行过滤、去重操作，减少重复爬取的无效工作量。

最佳实践

基于TairBloom打造推荐系统

将已推荐给用户的文章ID通过TairBloom记录，并在推荐新文章前进行查询、判断，轻松实现给用户推荐感兴趣，且未推荐过的文章，伪代码如下：

void recommendedSystem(userid) {
    while (true) {
        // 从系统中随机（或者根据用户兴趣）获取一篇文章ID。
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // 如果发现可能已向用户推荐过该文章，则推荐下一篇文章。
            continue;
        } else {
            // 确认未向用户推荐过该文章，则向用户发送推荐。
            sendRecommendMsg(docid);
            // 同时将已推荐的文章ID记录至TairBloom。
            bf.add(userid, docid);
            break;
        }
    }
}

基于TairBloom优化爬虫系统

在面对海量的URL时，将已经爬取过的URL进行过滤、去重操作，减少重复爬取的无效工作量，伪代码如下：

bool crawlerSystem( ) {
    while (true) {
        // 获取待爬取的URL。
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // 如果该URL可能已被爬取，则跳过。
            continue;
        } else {
            // 爬取该URL内容。
            doDownload(url)
            // 并将该URL加入TairBloom。
            bf.add(url_bloom, url);
        }
    }
}

原理介绍

TairBloom作为一种Scalable Bloom Filter的实现，具有动态扩容的能力，同时误判率（False Positive Rate）维持不变。而Scalable Bloom Filter是在Bloom Filter的基础上进行优化的，下文将简单介绍Bloom Filter与Scalable Bloom Filter的基本原理。

Bloom Filter
布隆过滤器是一个高空间利用率的概率性数据结构，由Burton Bloom于1970年提出，用于测试一个元素是否在集合中。
新创建的布隆过滤器是一串被置为0的Bit数组（假设有m位），同时声明k个不同的Hash函数生成统一的随机分布（k是一个小于m的常数）。向布隆过滤器中添加元素时，通过k个Hash函数将元素映射到Bit中的k个点，并将这些位置的值设置为1，一个Bit位可能被不同数据共享。下图展示了假设布隆过滤器的k为3，向其插入X1、X2的过程。
查询元素时，仍通过k个Hash函数得到对应的k个位，判断目标位置是否为1，若目标位置全为1则认为该元素在布隆过滤器内，否则认为该元素不存在，下图展示了在布隆过滤器中查询Y1和Y2是否存在的过程。
由上图可以发现，虽然从未向布隆过滤器中插入过Y2这个元素，但是布隆过滤器却判断Y2存在，因此，布隆过滤器是可能存在误判的，即存在假阳性（false positive）。至此，可以得出关于布隆过滤器的几个特性：
- Bit位可能被不同数据共享。
- 存在假阳性（false positive），且布隆过滤器中的元素越多，假阳性的可能性越大，但不存在假阴性（false negative），即不会将存在的元素误判为不存在。
- 元素可以被加入布隆过滤器，但无法被删除，因为Bit位是可以共享的，删除时有可能会影响到其他元素。
Scalable Bloom Filter
随着布隆过滤器中添加的元素越来越多，误判率也越来越高，若希望误判率稳定不变，需同步增加布隆过滤器的大小，但是布隆过滤器由于结构限制无法进行扩容。因此，Scalable Bloom Filter提出创建新的布隆过滤器，将多个布隆过滤器组装成一个布隆过滤器使用。
下图展示了一个Scalable Bloom Filter的基本模型（下文简称SBF）。该SBF一共包含BF0和BF1两层。在一开始，SBF只包含BF0层，假设在插入a、b、c三个元素后，BF0层已经无法保证用户设定的误判率，此时会创建新的一层（BF1层）进行扩容。因此，后面的d、e、f元素会插入到BF1层中。同理，当BF1层也无法满足误判率时，会创建新的一层（BF2层），如此进行下去。
Scalable Bloom Filter只会向最后一层插入数据，同时也从最后一层开始查询，直到查询至BF0层。更多信息，请参见Scalable Bloom Filter。

前提条件

实例为Tair内存型。

说明

最新小版本将提供更丰富的功能与稳定的服务，建议将实例的小版本升级到最新，具体操作请参见升级小版本。如果您的实例为集群架构或读写分离架构，请将代理节点的小版本也升级到最新，否则可能出现命令无法识别的情况。

注意事项

操作对象为Tair实例中的TairBloom数据。

提前规划好初始容量与错误率，若目标key的预计容量远大于100，请通过BF.RESERVE创建TairBloom，不建议直接执行BF.ADD命令。

直接执行BF.ADD与执行BF.RESERVE的区别如下。

BF.ADD（或BF.MADD）：执行时若目标key不存在，Tair会自动创建TairBloom，默认容量（capacity）为100，错误率（error_rate）为0.01。若您的容量远远大于100，后续仅能通过扩容增加元素。
而TairBloom的扩容是通过增加Bloom Filter的层数来完成，每一层容量将增长，但是随着不断的扩容，TairBloom内部的层数会越来越多，此时会导致完成查询任务需要遍历多层Bloom Filter，性能将严重下降。
BF.RESERVE（或BF.INSERT）：执行时需要设置capacity（初始容量），该命令会在TairBloom的第一层初始化设置的容量，在TairBloom内部的Bloom Filter层数少，查询速度快。

说明

以插入10,000,000个元素、错误率为0.01为例，直接通过BF.ADD创建，TairBloom需占用176 MB；而通过BF.RESERVE创建时仅占用16 MB。

虽然TairBloom支持扩容，但在实际使用过程中请避免发生扩容操作，建议将该功能视为保障措施，若实际容量超过预设容量时，TairBloom能通过扩容操作，保障业务正常写入，规避线上事故。

下表为通过BF.RESERVE创建不同初始容量和错误率的key所占用的内存，仅供参考。

容量（元素的个数）	false positive:0.01	false positive:0.001	false positive:0.0001
100,000	0.12 MB	0.25 MB	0.25 MB
1,000,000	2 MB	2 MB	4 MB
10,000,000	16 MB	32 MB	32 MB
100,000,000	128 MB	256 MB	256 MB
1,000,000,000	2 GB	2 GB	4 GB

由于TairBloom只能插入新元素且无法删除已有元素，因此TairBloom的内存占用量只会增加不会减少。为防止TairBloom越来越大，甚至导致Redis内存溢出（Out Of Memory），向您提供如下使用建议。
- 拆分业务数据：拆分、细化业务数据，避免将大量数据存入一个TairBloom中，这样不仅会导致这个key过大，影响查询性能，同时也会由于这个key中插入了过多数据，大部分的查询流量都会请求到这个key所在的Redis实例上，从而造成热点key，甚至发生访问倾斜的情况。
  请拆分业务数据，将数据分散到多个TairBloom中，若您的实例为集群实例，您可以将TairBloom分散到集群内的各个实例上，均衡内存容量与流量，充分发挥分布式集群的优势。
- 定期重建：如果业务允许，您可以定期重建TairBloom，通过DEL删除TairBloom，从后端数据库拉取数据并重建TairBloom，以控制TairBloom的大小。
  您也可以在初期创建多个TairBloom，并采用多个TairBloom轮转切换的方式实现控制单个TairBloom的大小。该方案的优点为仅需创建一次TairBloom，无需频繁地重建TairBloom，缺点是需要创建多个TairBloom，会浪费部分内存空间。

命令列表

表 1. TairBloom命令

命令	语法	说明
BF.RESERVE	`BF.RESERVE key error_rate capacity`	创建一个大小为capacity，错误率为error_rate的空的TairBloom。
BF.ADD	`BF.ADD key item`	在Key指定的TairBloom中添加一个元素。
BF.MADD	`BF.MADD key item [item ...]`	在Key指定的TairBloom中添加多个元素。
BF.EXISTS	`BF.EXISTS key item`	检查一个元素是否存在于Key指定的TairBloom中。
BF.MEXISTS	`BF.MEXISTS key item [item ...]`	同时检查多个元素是否存在于Key指定的TairBloom中。
BF.INSERT	`BF.INSERT key [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS item [item ...]`	在Key指定的TairBloom中一次性添加多个元素，添加时可以指定大小和错误率，且可以控制在TairBloom不存在的时候是否自动创建。
BF.INFO	`BF.INFO key`	查看Key指定的TairBloom内部信息，如当前层数和每一层的元素个数、错误率等。
DEL	`DEL key [key ...]`	使用原生Redis的DEL命令可以删除一条或多条TairBloom数据。说明已加入TairBloom数据中的元素无法单独删除，您可以使用DEL命令删除整条TairBloom数据。

说明本文的命令语法定义如下：

大写关键字：命令关键字。
斜体：变量。
[options]：可选参数，不在括号中的参数为必选。
A|B：该组参数互斥，请进行二选一或多选一。
...：前面的内容可重复。

BF.RESERVE

类别	说明
语法	`BF.RESERVE key error_rate capacity`
时间复杂度	O(1)
命令描述	创建一个大小为capacity，错误率为error_rate的空的TairBloom。
选项	Key：Key名称（TairBloom数据结构），用于指定作为命令调用对象的TairBloom。 error_rate：期望的错误率（False Positive Rate），该值必须介于0和1之间。该值越小，精度越高，TairBloom的内存占用量越大，CPU使用率越高。 capacity：TairBloom的初始容量，即期望添加到TairBloom中的元素的个数。当实际添加的元素个数超过该值时，TairBloom将通过增加Bloom Filter的层数完成自动扩容，该过程会导致查询性能下降。每增加一层，就可能需要遍历多层Bloom Filter来完成查询。因此，如果对性能非常的敏感，需要在使用前充分评估要添加到TairBloom的元素个数，避免发生导致层数增加的扩容操作。
返回值	OK：表示执行成功。其它情况返回相应的异常信息。
示例	命令示例： `BF.RESERVE BFKEY 0.01 100` 返回示例： `OK`

BF.ADD

类别	说明
语法	`BF.ADD key item`
时间复杂度	O(log N) ，其中N是TairBloom的层数。
命令描述	在Key指定的TairBloom中添加一个元素。说明若目标Key不存在，Tair会自动创建一个TairBloom，创建TairBloom的默认容量（capacity）为100，错误率（error_rate）为0.01。
选项	Key：Key名称（TairBloom数据结构），用于指定作为命令调用对象的TairBloom。 item：需要添加到TairBloom的元素。
返回值	1：表示该元素之前一定不存在，并往TairBloom中添加该元素。 0：表示该元素可能已存在，所以不会进行添加或更新操作。其它情况返回相应的异常信息。
示例	命令示例： `BF.ADD BFKEY item1` 返回示例： `(integer) 1`

BF.MADD

类别	说明
语法	`BF.MADD key item [item ...]`
时间复杂度	O(log N) ，其中N是TairBloom的层数。
命令描述	在Key指定的TairBloom中添加多个元素。说明若目标Key不存在，Tair会自动创建一个TairBloom，创建TairBloom的默认容量（capacity）为100，错误率（error_rate）为0.01。
选项	Key：Key名称（TairBloom数据结构），用于指定作为命令调用对象的TairBloom。 item：需要添加到TairBloom的元素，可设置多个。
返回值	1：表示该元素之前一定不存在，并往TairBloom中添加该元素。 0：表示该元素可能已存在，所以不会进行添加或更新操作。其它情况返回相应的异常信息。
示例	命令示例： `BF.MADD BFKEY item1 item2 item3` 返回示例： `(integer) 1 (integer) 1 (integer) 1`

BF.EXISTS

类别	说明
语法	`BF.EXISTS key item`
时间复杂度	O(log N) ，其中N是TairBloom的层数。
命令描述	检查一个元素是否存在于Key指定的TairBloom中。
选项	Key：Key名称（TairBloom数据结构），用于指定作为命令调用对象的TairBloom。 item：需要查询的元素。
返回值	0：表示该元素一定不存在。 1：表示该元素可能存在。其它情况返回相应的异常信息。
示例	命令示例： `BF.EXISTS BFKEY item1` 返回示例： `(integer) 1`

BF.MEXISTS

类别	说明
语法	`BF.MEXISTS key item [item ...]`
时间复杂度	O(log N) ，其中N是TairBloom的层数。
命令描述	同时检查多个元素是否存在于Key指定的TairBloom中。
选项	Key：Key名称（TairBloom数据结构），用于指定作为命令调用对象的TairBloom。 item：需要查询的元素，可设置多个。
返回值	0：表示该元素一定不存在。 1：表示该元素可能存在。其它情况返回相应的异常信息。
示例	命令示例： `BF.MEXISTS BFKEY item1 item5` 返回示例： `(integer) 1 (integer) 0`

BF.INSERT

类别	说明
语法	`BF.INSERT key [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS item [item ...]`
时间复杂度	O(log N) ，其中N是TairBloom的层数。
命令描述	在Key指定的TairBloom中一次性添加多个元素，添加时可以指定大小和错误率，且可以控制在TairBloom不存在的时候是否自动创建。
选项	Key：Key名称（TairBloom数据结构），用于指定作为命令调用对象的TairBloom。 capacity：TairBloom的初始容量，即期望添加到TairBloom中元素的个数，当TairBloom已经存在时该值将被忽略。当实际添加的元素个数超过该值时，TairBloom将进行自动的扩容，该过程会导致性能有所下降，下降的程度是随着元素个数的增长而下降的，这是因为TairBloom的扩容是通过增加Bloom Filter的层数来完成的。每增加一层，在查询的时候就可能会遍历多层Bloom Filter来完成，每一层的容量都是上一层的两倍。因此，如果对性能非常的敏感，需要在使用前充分评估要添加到TairBloom的元素个数，避免发生扩容操作。 error_rate：期望的错误率（False Positive Rate），该值必须介于0和1之间。该值越小，精度越高，TairBloom的内存占用量越大，CPU使用率越高。 NOCREATE：设置该选项后，当指定的TairBloom不存在的时候不要自动创建该TairBloom。该参数不能与CAPACITY和ERROR同时设置。 item：需要添加的元素，可设置多个。
返回值	1：表示该元素之前一定不存在，并往TairBloom中添加该元素。 0：表示该元素可能已存在，所以不会进行添加或更新操作。其它情况返回相应的异常信息。
示例	命令示例： `BF.INSERT bfkey1 CAPACITY 10000 ERROR 0.001 ITEMS item1 item2 item3` 返回示例： `(integer) 1 (integer) 1 (integer) 1`

BF.INFO

类别	说明
语法	`BF.INFO key`
时间复杂度	O(log N) ，其中N是TairBloom的层数。
命令描述	查看Key指定的TairBloom内部信息，如当前层数和每一层的元素个数、错误率等。
选项	Key：Key名称（TairBloom数据结构），用于指定作为命令调用对象的TairBloom。
返回值	执行成功将返回TairBloom信息。其它情况返回相应的异常信息。
示例	命令示例： `BF.INFO bk1` 返回示例： `1) "total_items:6,num_blooms:2" 2) "bytes:4 bits:32 hashes:7 hashwidth:64 capacity:3 items:3 error_ratio:0.01" 3) "bytes:16 bits:128 hashes:9 hashwidth:64 capacity:10 items:3 error_ratio:0.0025"` BF.INFO返回参数说明： total_items表示总元素数量、num_blooms表示总Bloom Filter层数。每层Bloom Filter的信息： bytes：占用字节数。 bits：占用bit位数，bits = bytes * 8。 hashes：Hash函数数量。 hashwidth：Hash函数宽度。 capacity：容量。 items：元素数量。 error_ratio：错误率。