干货，使用布隆过滤器实现高效缓存！

2021 年 5 月 14 日
筆記
C#随笔

前言

本文主要描述，使用布隆过滤实现高效缓存。文中采用数组做为缓存，如果需要高并发命中，则需将文中的数组换成Redis数据库。

布隆过滤

布隆缓存的创建过程如下：

1，先定义缓存bit数组（BitArray），数组的长度就是缓存数据的最大数量。

2，然后将字符串通过哈希运算，求出它的HashCode。

3，然后将HashCode作为伪随机数生成器（Random）的种子，生成一个小于最大数量的正数x。

4，然后将这x作为缓存数组的索引，将数组[x]的值设置为true。

布隆过滤

将获取到的字符串，通过上述前三步运算，计算出数组索引，然后在布隆缓存里取出指定索引的值，如果为True，则缓存存在，可以使用这个字符串去真正的数据缓存中取数据，如果未Fasle，则缓存不存在则去数据库中取数据。

代码实现

首先建立WinForm项目BloomTest。

然后编写布隆过滤器，代码如下：

public class BloomFilter
{
    //布隆缓存数组
    public BitArray BloomCache;
    //布隆缓存数组的长度
    public Int64 BloomCacheLength { get; } 
    public Int64 HashCount { get; }
     
    /// <summary>
    /// 
    /// </summary>
    /// <param name="bloomCacheLength">布隆缓存数组的长度，默认20000</param> 
    /// <param name="hashCount">hash运算次数，默认3</param>
    public BloomFilter(int bloomCacheLength = 20000,  int hashCount = 3)
    {
        BloomCache = new BitArray(bloomCacheLength);
        BloomCacheLength = bloomCacheLength; 
        HashCount = hashCount;
    }
    public void Add(string str)
    {
        var hashCode =str.GetHashCode();
        Random random = new Random(hashCode);
        for (int i = 0; i < HashCount; i++)
        {
            var x = random.Next((int)(BloomCacheLength - 1));
            BloomCache[x] = true;
        }
    }

    public bool IsExist(string str)
    {
        var hashCode = str.GetHashCode();
        Random random = new Random(hashCode);
        for (int i = 0; i < HashCount; i++)
        {
            if (!BloomCache[random.Next((int)(BloomCacheLength - 1))])
            {
                return false;
            }
        }
        return true;
    }

    //错误率查看
    public double GetFalsePositiveProbability(double setSize)
    {
        // (1 - e^(-k * n / m)) ^ k
        return Math.Pow((1 - Math.Exp(-HashCount * setSize / BloomCacheLength)), HashCount);
    }
    //计算基于布隆过滤器散列的最佳数量，即hashCount的最佳值
    public int OptimalNumberOfHashes(int setSize)
    {
        return (int)Math.Ceiling((BloomCacheLength / setSize) * Math.Log(2.0));
    }

}

然后编写布隆过滤器的使用代码，如下：

 public partial class Form1 : Form
    {
        BloomFilter bloom = new BloomFilter(20000, 3);
        int setSize = 2000;
        public Form1()
        {
            InitializeComponent();
            //生成布隆缓存数组
            for (int i = 0; i < setSize; i++)
            {
                bloom.Add("kiba" + i);
            }
        } 
        private void btnSearch_Click(object sender, EventArgs e)
        { 
            Stopwatch sw = new Stopwatch();
            sw.Start();
            string con = tbCon.Text.Trim();
            var ret = bloom.IsExist(con);
            sw.Stop();
            lblRet.Text = $@"结果:{ret}{Environment.NewLine}
耗时:{sw.ElapsedTicks}{Environment.NewLine}
错误概率:{bloom.GetFalsePositiveProbability(setSize)}{Environment.NewLine} 
最佳数量:{bloom.OptimalNumberOfHashes(setSize)}"; 
        } 
    }

测试结果

运行项目，点击查询数据。

如上图所示，我们成功命中了，如果在项目中，命中了就可以查询真实缓存了。

错误概率

布隆缓存存在命中错误，即如果两个数据的哈希运算后值相同，那么久会存在命中失败的问题。

错误概率可以通过哈希运算次数和布隆缓存数组长度和插入数据数量计算出来。

最佳数量

布隆缓存建议我们多做几次哈希运算，即多存几个缓存索引，文中默认创建3个。

我们代码中，向布隆缓存数组中插入了2000个数据，通过计算得出，最佳的哈希运算次数为7，即当插入数量为2000，布隆缓存数组长度为20000时，HashCount的最优值为7。

应用场景

布隆缓存有很多场景可以应用，比如重复URL检测，黑名单验证，垃圾邮件过滤等等。

举个例子，爬虫在爬取网站之前，会先通过布隆过滤计算出该Url是否已经爬取过，再确定是否发起Http请求。

关于缓存穿透、缓存击穿、缓存雪崩

缓存穿透

缓存穿透是指缓存和数据库中都没有的数据，这时用户不断的发起这样的请求，会对数据库和缓存造成比较大的压力。

解决方案：增加更多，更有效的数据校验，让这些请求在进入查询前被拦截。将缓存和数据库中都没有的数据写入缓存，并设置一个较短的有效期，用来防止该请求多次进入到数据库。

缓存击穿

缓存击穿是指缓存中的数据正好到期，然后又突然出现大量该数据的访问。导致大量请求直接发送到数据库。

解决方案：对数据进行热点标记，然后对热点数据进行特殊有效期设置。对普通数据进行有效期延长处理，比如被请求过一次，加长固定时间的有效期。

缓存雪崩

缓存雪崩与缓存击穿的意思类似，区别在于，缓存击穿指的是只有一条数据直接请求数据库，而雪崩指的是很多这样的数据直接请求数据库。

解决方案：缓存数据库分布式部署。

结语

布隆缓存因为存在误判，所以不能用于百分之百定位数据的场景，但如果该场景可以容错，那布隆缓存将大大提升性能。

—————————————————————————————————-

到此，到此布隆过滤就已经介绍完了。

代码已经传到Github上了，欢迎大家下载。

Github地址： //github.com/kiba518/BloomFilter_Kiba

—————————————————————————————————-

注：此文章为原创，任何形式的转载都请联系作者获得授权并注明出处！
若您觉得这篇文章还不错，请点击下方的【推荐】，非常感谢！

//www.cnblogs.com/kiba/p/14767430.html

Tags: C#随笔