Redis布隆过滤器（十三）

Author：木头脑'Blog
发布时间：June 2, 2019
1637 views
No comments
1398 words
Categories：知识分享 Redis

布隆过滤器引出

问题引出：现有50亿个电话号码，有10万个电话号码，要快速准确判断这些电话号码是否已经存在
1. 通过数据库查询：实现快速有点难
2. 数据预先放在内存集合中：50亿 * 8字节 = 40GB（内存浪费或不够）
3. hyperloglog：准确有点难

布隆过滤器原理

需要参数
- m个二进制向量（m个二进制位数）
- n个预备数据（类似于问题中的50亿个电话号码）
- k个hash函数（每个数据，逐个进行hash，将指定向量标识为1）
构建布隆过滤器
- 将n个数据逐个走一遍hash流程
判断元素是否存在
- 将元素逐个hash进行执行
- 如果得到的hash结果再向量中全都是1，则表明存在
- 反之当前元素不存在

布隆过滤器误差率

对的数据的返回结果必然是对的，但是错误的数据也可能是对的
直观因素
- m / n 的比例：比例越大，误差率越小
- hash函数的个数：个数越多，误差率越小

本地布隆过滤器

实现类库：Guava

Funnel<Integer> funnel = Funnels.integerFunnel();
int size = 1000_000;
double errorChance = 0.001;        //错误率
BloomFilter<Integer> filter = BloomFilter.create(funnel , size , errorChance);
for(int i = 0 ; i < size ; i++ ) {
    filter.put(i);
}
for(int i = 0 ; i < size ; i++ ) {
    if( !filter.mightContain(i) ) {
        System.out.println("发现不存在的数据 : " + i);
    }
}

布隆过滤器的问题
- 容量受到限制
- 多个应用存在多个布隆过滤器，构建同步过滤器复杂

Redis单机布隆过滤器

基于bitmap实现，利用setbit、getbit命令实现
hash函数：
- MD5
- murmur3_128
- murmur3_32
- sha1
- sha256
- sha512
基于Redis单机实现存在的问题
- 速度慢：与本机比，输在网络
  - 解决方法1：单独部署、与应用同机房甚至同机架部署
  - 解决方法2：使用pipeline
- 容量限制：Redis最大字符串为512MB、Redis单机容量
  - 解决方法：基于RedisCluster实现

Redis Cluster实现布隆过滤器

多个布隆过滤器：二次路由
基于pipeline提高效率

Last modification：June 2, 2019

© Allow specification reprint

如果觉得我的文章对你有用，请随意赞赏

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Comment *

Private comment

Name *

🎲

Email *

Site

Redis布隆过滤器（十三）

木头脑'Blog • 2019 年 06 月 02 日

<h1>布隆过滤器引出</h1><ul><li><p>问题引出：现有50亿个电话号码，有10万个电话号码，要<strong><em>快速准确</em></strong>判断这些电话号码是否已经存在</p><ol><li>通过数据库查询：实现<strong><em>快速</em></strong>有点难</li><li>数据预先放在内存集合中：50亿 * 8字节 = 40GB（<strong><em>内存</em></strong>浪费或不够）</li><li>hyperloglog：<strong><em>准确</em></strong>有点难</li></ol></li></ul><h1>布隆过滤器原理</h1><ul><li><p>需要参数</p><ul><li>m个二进制向量（m个二进制位数）</li><li>n个预备数据（类似于问题中的50亿个电话号码）</li><li>k个hash函数（每个数据，逐个进行hash，将指定向量标识为1）</li></ul></li><li><p>构建布隆过滤器</p><ul><li>将n个数据逐个走一遍hash流程</li></ul></li><li><p>判断元素是否存在</p><ul><li>将元素逐个hash进行执行</li><li>如果得到的hash结果再向量中全都是1，则表明存在</li><li>反之当前元素不存在</li></ul></li></ul><h1>布隆过滤器误差率</h1><ul><li>对的数据的返回结果必然是对的，但是错误的数据也可能是对的</li><li><p>直观因素</p><ul><li>m / n 的比例：比例越大，误差率越小</li><li>hash函数的个数：个数越多，误差率越小</li></ul></li></ul><h1>本地布隆过滤器</h1><ul><li><p>实现类库：Guava</p><pre><code class="lang-java">Funnel&lt;Integer&gt; funnel = Funnels.integerFunnel();
int size = 1000_000;
double errorChance = 0.001;        //错误率
BloomFilter&lt;Integer&gt; filter = BloomFilter.create(funnel , size , errorChance);
for(int i = 0 ; i &lt; size ; i++ ) {
    filter.put(i);
}
for(int i = 0 ; i &lt; size ; i++ ) {
    if( !filter.mightContain(i) ) {
        System.out.println(&quot;发现不存在的数据 : &quot; + i);
    }
}</code></pre></li><li><p>布隆过滤器的问题</p><ul><li>容量受到限制</li><li>多个应用存在多个布隆过滤器，构建同步过滤器复杂</li></ul></li></ul><h1>Redis单机布隆过滤器</h1><ul><li>基于bitmap实现，利用setbit、getbit命令实现</li><li><p>hash函数：</p><ul><li>MD5</li><li>murmur3_128</li><li>murmur3_32</li><li>sha1</li><li>sha256</li><li>sha512</li></ul></li><li><p>基于Redis单机实现存在的问题</p><ul><li><p>速度慢：与本机比，输在网络</p><ul><li>解决方法1：单独部署、与应用同机房甚至同机架部署</li><li>解决方法2：使用pipeline</li></ul></li><li><p>容量限制：Redis最大字符串为512MB、Redis单机容量</p><ul><li>解决方法：基于RedisCluster实现</li></ul></li></ul></li></ul><h1>Redis Cluster实现布隆过滤器</h1><ul><li>多个布隆过滤器：二次路由</li><li>基于pipeline提高效率</li></ul>