一种分布式布隆过滤器设计

作者：朱江，腾讯工程师。

| 导语  布隆过滤器是一种很实用的数据结构，能快速判断某个数据是否存在于特定集合中，比如可以用一个布隆过滤器记录读过某篇文章的所有用户，或者记录一个月内访问过某个URL所有用户。这样可以快速判断某个用户是否读过某篇文章、某个用户是否访问过某个URL，同时消耗内存极少。为了可以让各个业务都能方便使用，借鉴DCache设计，方便申请使用、管理，而背后的分配、主备、异常管理不需要业务关心。

01

写在前面

1.布隆过滤器特点

一种概率型的数据结构，可以高效地插入和查询，能告诉你”某个数据一定不存在或可能存在”。

优点：需要内存极少，大量比特位被复用，比如一亿个数据，误判率万分之一的前提下，只需要250多MB内存。

缺点：存在误判，判断某个数据不存在，那就一定不存在，但判断某个数据存在，可能并不一定存在，只是刚好哈希算法计算出来的位和某数据相同，误判率是可以控制的。

2.分布式布隆过滤器集群特点

a.对外提供丰富多样接口满足业务需要(详见下面)；

b.支持管理平台申请、停用、删除布隆过滤器，比如手动配置布隆过滤器名称、预估初始容量、误判率、有效期；

c.支持接口动态创建、删除布隆过滤器，针对有一些业务需要动态管理布隆过滤器；

d.每个布隆过滤器支持主备，当备节点异常，会重新选取新的备节点，并向主节点同步数据。如果主节点异常，会先主备切换，再为备重新选取新的备节点；

e.支持本地dump文件备份，服务或机器异常重启会自动重新加载数据恢复；

f.支持主备节点间的增量同步；

02

有图有真相

03

整体设计

Proxy服务：接入层，节点都是无状态的，能部署任意个节点。Proxy用于屏蔽后端的路由细节，根据从Router服务得到的路由信息和业务提供的filter名和data，去访问BloomFilter服务；

Router服务：路由管理服务（单个节点，使用taf平台主备主动切换），提供根据配置分配节点、异常的主备切换机制、异常重分配机制；

BloomFilter：布隆过滤器服务，除提供基本接口（如add，check等），需具备增量主备节点间的同步机制、本地磁盘dump文件备份机制；

04

BloomProxy设计

接口设计：

interface BloomProxyObj

{

int helloTest ( out string rsp ) ;

int add ( AddReq req, out AddRsp rsp ) ;

int addCond ( AddCondReq req, out AddCondRsp rsp ) ;

int mAdd ( MAddReq req, out MAddRsp rsp ) ;

int check ( CheckReq req, out CheckRsp rsp ) ;

int mCheck ( MCheckReq req, out MCheckRsp rsp ) ;

int createBloom ( CreateBloomReq req, out CreateBloomRsp rsp ) ;

int getBloomInfo ( GetBloomInfoReq req, out GetBloomInfoRsp rsp ) ;

};

基本功能：

1.定时向BloomRouter获取最新路由表（路由表无更新不需要返回）；

2.处理客户端请求，根据路由表访问对应的BloomFilter主节点；

3.提供add,madd,check,mcheck等布隆过滤器接口（taf/http）；

4.对于读请求，访问BloomFilter主节点失败，继续访问其备节点。对于写请求，访问BloomFilter主节点失败，则直接失败，防止对主备节点同时出现写；

05

BloomRouter服务设计

接口设计：

struct Router

{

0 optional string filter;

1 optional string master;

2 optional string slave;

3 optional int status; //路由状态

4 optional int enable; //0:禁用 1:启用

};

struct GetRouterTabReq

{

0 optional long routerTabUpTime = 0 ; //路由表最后更新时间

};

struct GetRouterTabRsp

{

0 optional int code = 0 ;

1 optional string msg = “success” ;

2 optional bool isUpdate = true ;

3 optional vector routerTab;

4 optional long routerTabUpTime = 0 ;

};

interface BloomRouterObj

{

int getRouterTab ( GetRouterTabReq req, out GetRouterTabRsp rsp ) ;

int createBloom ( THBFProxy::CreateBloomReq req, out THBFProxy::CreateBloomRsp rsp ) ;

};

基本功能：

1.Router服务定时获取所有BloomFilter节点负载信息（主要是内存负载、已分配的布隆过滤器），需定时刷到DB；

2.获取管理平台配置的所有过滤器配置信息（名称，预估容量，误判率，有效期等）；

3.根据分配算法（见下面）为新布隆过滤器分配主备节点，为失效的节点重分配；

分配算法：

a.内存多的节点优先分配；

b.内存相同，主布隆过滤器个数少的节点优先分配；

4.生成内存路由表并更新到DB持久化保存；

名称	主节点	备节点	权限
BF1	BloomFilter1@tcp -h 10.55.211.92 -p 10149 -t 60000	BloomFilter2@tcp -h 100.115.151.8 -p 10098 -t 60000	RW
BF2	BloomFilter2@tcp -h 100.115.151.8 -p 10098 -t 60000	BloomFilter3@tcp -h 100.115.151.10 -p 10012 -t 60000	RW

5.根据内存最新路由，定时通知所有BloomFilter节点的对应布隆过滤器列表配置情况，如通知节点1的布隆过滤器最新列表，列表元素如下：

struct Ident {

0 optional string filter ;

1 optional long initSize;

2 optional double errRate;

3 optional int ident; //主,备

4 optional string master; //布隆过滤器的主节点地址

};

6.划分单独线程池（可配线程数）用来检测各个节点的连通性；

检测算法：

a.BloomRouter服务间隔1秒调用BloomFilter节点的helloTest接口，如果连续失败N次（可配），则认为节点可能发生异常；

b.BloomRouter服务随机向BloomProxy服务发送M次helloTest消息，如果调用正常，则认为本身节点网络正常，是BloomFilter异常；

c.根据上述检测，修改路由表，失效节点状态改为需要重分配，由一个统一的定时任务处理所有分配，包括异常重分配；

06

BloomFilter设计

接口设计：

interface BloomFilterObj

{

int add ( AddReq req, out AddRsp rsp ) ;

int addCond ( AddCondReq req, out AddCondRsp rsp ) ;

int mAdd ( MAddReq req, out MAddRsp rsp ) ;

int check ( CheckReq req, out CheckRsp rsp ) ;

int mCheck ( MCheckReq req, out MCheckRsp rsp ) ;

int helloTest ( out string rsp ) ;

int createBloom ( CreateBloomReq req, out CommRsp rsp ) ;

int delBloom ( string filter, out CommRsp rsp ) ;

int getBloomIndex ( string filter, out GetIndexRsp rsp ) ;

int getBloomChunk ( string filter, long iter, out GetChunkRsp rsp ) ;

int syncBloomIdent (vector idents ) ;

int getNodeStatus ( out GetNodeStatusRsp rsp ) ;

int getBloomInfo ( GetBloomInfoReq req, out GetBloomInfoRsp rsp ) ;

};

布隆过滤器数据结构：

redis插件，RedisBloom-1.1.1（C语言开发），将其移到TAF服务BloomFilter中，用来提供基本的布隆过滤器接口。同样，与redis相同，也采用了单业务线程架构设计，dump备份数据由另一线程异步完成；

基本功能：

1.对外提供基本接口

add、批量接口mAdd、addCond(有条件的添加接口)、

check、批量接口mCheck、

helloTest(心跳检测)、

createBloom(创建布隆过滤器)、

delBloom(删除布隆过滤器)、

getBloomIndex(向其他节点获取索引文件，用于节点间同步布隆过滤器数据)、

getBloomChunk(向其他节点获取布隆过滤器数据，按块划分)、

syncBloomIdent(路由服务通知用)、

getNodeStatus(获取所有布隆过滤器状态数据)

2.本地dump机制

a.定时检查内存中布隆过滤器的头部数据MD5与磁盘上布隆过滤器索引文件的MD5；

b.当a检查出不同，需要把内存中的布隆过滤器dump到磁盘保存，分别为索引文件及若干块数据文件，数据结构如下，可以看出，索引文件保存了布隆过滤器的所有重要信息：元数据文件路径、长度、MD5，各块数据文件路径、块位置、块长度、块MD5；

0 optional string headPath;

1 optional long headLen;

2 optional string md5;

};

0 optional string chunkPath;

1 optional long iter;

2 optional long chunkLen;

3 optional string md5;

};

0 optional string filterName;

1 optional long items = 0 ;

2 optional long cfgChunkSize = 0 ;

3 optional Head head;

4 optional vector< Chunk > chunks;

};

查看节点上所有索引文件：

查看对应的dump文件：

c.BloomFilter服务启动时遍历index文件夹，从而把所有布隆过滤器数据加载回内存；

3.不同BloomFilter节点的主备布隆过滤器数据增量同步机制

a.前面说过，BloomRouter服务会通过syncBloomIdent接口，告诉该BloomFilter的布隆过滤器列表，包括主备信息。BloomFilter服务通过路由服务通知的信息，可以为本节点上所有备布隆过滤器增量同步数据过来；

b.比如该节点上的备布隆过滤器BF1，定时向其master调用接口getBloomIndex，获取主布隆过滤器的索引文件信息，就像和本地索引文件比较一样，如发现某个块MD5不相同，就调用getBloomChunk获取对应的块数据，并更新内存；

07

写在最后

1.应用：目前该布隆过滤器集群已应用在部门的ABTest业务中，效果良好；

2.性能：目前还没有完整测试过，根据ABTest线上服务观察，基本的add，check接口耗时普遍在1，2毫秒，后面再做完整的并发性能测试。

那些熟悉却说不出的设计法则

微信大更新！支持多任务操作，还有超好用的 10 大新功能

年度好文：腾讯工程师的自我修炼