云原生内存数据库Tair：TairBloom

TairBloom简介

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

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

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

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

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实例中的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，会浪费部分内存空间。

命令列表

BF.RESERVE

BF.RESERVE BFKEY 0.01 100

OK

BF.ADD

BF.ADD BFKEY item1

(integer) 1

BF.MADD

BF.MADD BFKEY item1 item2 item3

(integer) 1
(integer) 1
(integer) 1

BF.EXISTS

BF.EXISTS BFKEY item1

(integer) 1

BF.MEXISTS

BF.MEXISTS BFKEY item1 item5

(integer) 1
(integer) 0

BF.INSERT

BF.INSERT bfkey1 CAPACITY 10000 ERROR 0.001 ITEMS item1 item2 item3

(integer) 1
(integer) 1
(integer) 1