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

腾讯大讲堂

发布于 2019-08-06 09:40:09

2.2K0

发布于 2019-08-06 09:40:09

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

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

写在前面

1.布隆过滤器特点

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

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

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

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

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

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

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

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

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

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

有图有真相

整体设计

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

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

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

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主节点失败，则直接失败，防止对主备节点同时出现写；

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

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<Ident> 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；

struct Head
    {
        0 optional string headPath;
        1 optional long headLen;
        2 optional string md5;
    };

    struct Chunk
    {
        0 optional string chunkPath;
        1 optional long iter;
        2 optional long chunkLen;
        3 optional string md5;
    };

    struct BloomDumpIndex
    {
        0 optional string filterName;
        1 optional long items = 0;
        2 optional long cfgChunkSize = 0;
        3 optional Head head;
        4 optional vector<Chunk> chunks;
    };

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

[mqq@9-22-34-91 ~/taf/app_log]$ ll index/
index/:
total 32
-rw-rw-r-- 1 mqq mqq 2302 Jul 12 12:22 1014-rw-rw-r-- 1 mqq mqq 2302 Jul 12 12:22 1015-rw-rw-r-- 1 mqq mqq 2302 Jul 12 12:23 1016-rw-rw-r-- 1 mqq mqq 2302 Jul 12 12:26 1019-rw-rw-r-- 1 mqq mqq 2302 Jul 11 16:08 1020-rw-rw-r-- 1 mqq mqq 2302 Jul 11 17:08 1021-rw-rw-r-- 1 mqq mqq 2302 Jul 11 20:02 1022-rw-rw-r-- 1 mqq mqq 2302 Jul 12 12:22 1023

[mqq@9-22-34-91 ~/taf/app_log]$ cat index/1014 
{"filterName":"1014","items":0,"cfgChunkSize":2097152,"head":{"headPath":"/usr/local/app/taf/app_log/dump//1014//head","headLen":35141,"md5":"9634183C403C6F9DD58EEF3E1AC51B48"},"chunks":[{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/0","iter":2097153,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/1","iter":4194305,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/2","iter":6291457,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/3","iter":8388609,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/4","iter":10485761,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/5","iter":12582913,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/6","iter":14680065,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/7","iter":16777217,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/8","iter":18874369,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/9","iter":20971521,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/10","iter":23068673,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/11","iter":25165825,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/12","iter":27262977,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/13","iter":29360129,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/14","iter":31457281,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"},{"chunkPath":"/usr/local/app/taf/app_log/dump//1014/15","iter":33554433,"chunkLen":2097152,"md5":"B2D1236C286A3C0704224FE4105ECA49"}]}

查看对应的dump文件：

[mqq@9-22-34-91 ~/taf/app_log]$ ll dump/1014/
total 32804
-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 0-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 1-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 10-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 11-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 12-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 13-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 14-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 15-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 2-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 3-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 4-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 5-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 6-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 7-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 8-rw-rw-r-- 1 mqq mqq 2097152 Jul 12 12:22 9-rw-rw-r-- 1 mqq mqq   35141 Jul 12 12:22 head

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

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

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

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

写在最后

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

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