TairBloom是一种可动态扩容的布隆过滤器,本文介绍TairBloom数据支持的命令。

TairBloom简介

TairBloom首先是一种概率性数据结构(space-efficient probabilistic data structure),主要使用较低的内存消耗来判断一个元素是否存在;其次,TairBloom具有动态扩容的能力,可在扩容的同时维持误判率的稳定。

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

主要特性
  • 内存占用低。
  • 可动态扩容。
  • 可自定义的误判率(False Positive Rate)且在扩容时保持不变。
典型场景
适用于直播、音乐、电商等行业的推荐系统或爬虫系统等,例如:
  • 推荐系统:将用户读过的文章通过TairBloom记录,并在给用户推荐新文章前进行查询,实现给用户推荐感兴趣,且没读过的文章。
  • 爬虫系统:在面对海量的URL时,将已经爬取过的URL进行过滤、去重操作,减少重复爬取的无效工作量。

最佳实践

TairBloom的原理与最佳实践

前提条件

注意事项

  • 操作对象为性能增强型实例中的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...>

在key指定的TairBloom中一次性添加多个元素,添加时可以指定大小和错误率,且可以控制在TairBloom不存在的时候是否自动创建。

DEL DEL <key> [key ...] 使用原生Redis的DEL命令可以删除一条或多条TairBloom数据。
说明 已加入TairBloom数据中的元素无法单独删除,您可以使用DEL命令删除整条TairBloom数据。

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...>
时间复杂度

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