TairBloom简介

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

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

主要特性：

• 内存占用低。
• 可动态扩容。
• 自定义的误判率（false positive rate）并在扩容时保持不变。

使用前提

请注意，本章节介绍的命令只有在满足以下条件时才能生效。

• Redis实例为云Redis企业版性能增强型实例。
• 操作对象为性能增强型实例中的TairBloom数据。

命令列表

BF.RESERVE

• 语法

  BF.RESERVE <key> <error_rate> <capacity>

• 时间复杂度

  O(1)

• 命令描述

  创建一个大小为capacity，错误率为error_rate的空的TairBloom。

• 参数及选项说明

  参数/选项	说明
  key	TairBloom的key，用于指定作为命令调用对象的TairBloom。
  error_rate	期望的错误率（false positive rate），该值必须介于0和1之间。该值越小，TairBloom的内存占用量越大，CPU使用率越高。
  capacity	TairBloom的初始容量，即期望添加到TairBloom中的元素的个数。 当实际添加的元素个数超过该值时，TairBloom将进行自动的扩容，该过程会导致性能有所下降，下降的程度是随着元素个数的指数级增长而线性下降的，这是因为TairBloom的扩容是通过增加Bloom Filter的层数来完成的。每增加一层，在查询的时候就可能会遍历多层Bloom Filter来完成，每一层的容量都是上一层的两倍。因此，如果对性能非常的敏感，需要在使用前充分评估要添加到TairBloom的元素个数，避免发生扩容操作。

• 返回值
  • 成功：OK。
  • 其它情况返回相应的异常信息。

BF.ADD

• 语法

  BF.ADD <key> <item>

• 时间复杂度

  O(log N) ，其中N是TairBloom的层数。

• 命令描述

  在key指定的TairBloom中添加一个元素。

• 参数及选项说明

  参数/选项	说明
  key	TairBloom的key，用于指定作为命令调用对象的TairBloom。
  item	需要添加到TairBloom的元素。

• 返回值
  • 元素一定不存在：1。
  • 元素可能已经存在：0。
  • 其它情况返回相应的异常信息。

BF.MADD

• 语法

  BF.MADD <key> <item> [item...]

• 时间复杂度

  O(log N) ，其中N是TairBloom的层数。

• 命令描述

  在key指定的TairBloom中添加多个元素。

• 参数及选项说明

  参数/选项	说明
  key	TairBloom的key，用于指定作为命令调用对象的TairBloom。
  item	需要添加到TairBloom的元素，可设置多个。

• 返回值
  • 成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素值为1，当item可能已经存在时数组元素值为0。
  • 其它情况返回相应的异常信息。

BF.EXISTS

• 语法

  BF.EXISTS <key> <item>

• 时间复杂度

  O(log N) ，其中N是TairBloom的层数。

• 命令描述

  检查一个元素是否存在于key指定的TairBloom中。

• 参数及选项说明

  参数/选项	说明
  key	TairBloom的key，用于指定作为命令调用对象的TairBloom。
  item	需要查询的元素。

• 返回值
  • 元素一定不存在：0。
  • 元素可能存在：1。
  • 其它情况返回相应的异常信息。

BF.MEXISTS

• 语法

  BF.MEXISTS <key> <item> [item...]

• 时间复杂度

  O(log N) ，其中N是TairBloom的层数。

• 命令描述

  同时检查多个元素是否存在于key指定的TairBloom中。

• 参数及选项说明

  参数/选项	说明
  key	TairBloom的key，用于指定作为命令调用对象的TairBloom。
  item	需要查询的元素，可设置多个。

• 返回值
  • 成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素值为0，当item可能已经存在时数组元素值为1。
  • 其它情况返回相应的异常信息。

BF.INSERT

• 语法

  BF.INSERT <key> [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS <item...>

• 时间复杂度

  O(log N) ，其中N是TairBloom的层数。

• 命令描述

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

• 参数及选项说明

  参数/选项	说明
  key	TairBloom的key，用于指定作为命令调用对象的TairBloom。
  CAPACITY	指定TairBloom的容量，即期望添加到TairBloom中的元素的个数，当TairBloom已经存在时该值将被忽略。 当实际添加的元素个数超过该值时，TairBloom将进行自动的扩容，该过程会导致性能有所下降，下降的程度是随着元素个数的指数级增长而线性下降的，这是因为TairBloom的扩容是通过增加Bloom Filter的层数来完成的。每增加一层，在查询的时候就可能会遍历多层Bloom Filter来完成，每一层的容量都是上一层的两倍。因此，如果对性能非常的敏感，需要在使用前充分评估要添加到TairBloom的元素个数，避免发生扩容操作。
  ERROR	期望的错误率（false positive rate），当TairBloom已经存在时该值将被忽略。该值必须介于0和1之间。该值越小，TairBloom的内存占用量越大，CPU使用率越高。
  NOCREATE	设置该选项后，当指定的TairBloom不存在的时候不要自动创建该TairBloom。该参数不能与CAPACITY和ERROR同时设置。
  ITEMS	需要添加到TairBloom中的所有元素。

• 返回值
  • 成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素为1，当item可能已经存在时数组元素值为0。
  • 其它情况返回相应的异常信息。

BF.DEBUG

• 语法

  BF.DEBUG <key>

• 时间复杂度

  O(log N) ，其中N是TairBloom的层数。

• 命令描述

  可以查看key指定的TairBloom内部信息，如当前层数和每一层的元素个数、错误率等。

• 参数及选项说明

  参数/选项	说明
  key	TairBloom的key，用于指定作为命令调用对象的TairBloom。

• 返回值
  • 成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素为1，当item可能已经存在时数组元素值为0。
  • 其它情况返回相应的异常信息。

内存占用测试结果