go 布隆过滤器_布隆过滤器 redis

go 布隆过滤器_布隆过滤器 redis最近面临这样的场景:2亿+数据需要调用后端服务A,业务需要1min处理完成,那么A服务承载的tps达到惊人的300w……必须想办法降低tps。那么方案来了:1、把时间窗口拉长2、降低待处理数据量。拉长时间业务肯定是接受不了的,但是按照以往的经验,这部分数据并不全部需要处理,可能仅有一半真正需要调用A服务,所以我们可以把1亿数据给过滤掉。这里我们维护一个布隆过滤器来进行数据的过滤。—————-以上都是导语—————-1.布隆过滤器的概

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

最近面临这样的场景:

2亿+数据需要调用后端服务A,业务需要1min处理完成,那么A服务承载的tps达到惊人的300w……必须想办法降低tps。

那么方案来了:1、把时间窗口拉长 2、降低待处理数据量。

拉长时间业务肯定是接受不了的,但是按照以往的经验,这部分数据并不全部需要处理,可能仅有一半真正需要调用A服务,所以我们可以把1亿数据给过滤掉。

这里我们维护一个布隆过滤器来进行数据的过滤。

1. 布隆过滤器的概念(百科)

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

2. 布隆过滤器应用场景

deny list

数据判重

预过滤

3. 原理

核心是一个长度为m的bit array和k个hash方法。

如下图,我们将一个newsid通过3个hash方法映射到长为8的数组上。

判断newsid是否存在,则看数组中3个位置是否都取到1:全为1,newsid可能存在于集合中;不全为1,newsid一定不存在于集合中。

 

go 布隆过滤器_布隆过滤器 redis

4. 特性

容易发现,布隆过滤器存在假阳性的情况,即将不在集合中的元素误判为在集合中。过滤器中的元素个数越多,假阳性的可能性越大。

同时,元素可以被加入过滤器,但很难从过滤器中删除(有可能删除的当前元素与其他元素共享了某一个bit,造成假阴性)。

根据假阳性率计算公式:

go 布隆过滤器_布隆过滤器 redis

 

可知在哈希函数的个数k一定的情况下:

  • 位数组长度m越大,假阳性率越低;
  • 已插入元素的个数n越大,假阳性率越高。

5. 上代码

// CalBloomSize 计算布隆过滤器位图大小
// elemNum 元素个数
// errorRate 误判率
func CalBloomSize(elemNum uint64, errRate float64) uint64 {
   var bloomBitsSize = float64(elemNum) * math.Log(errRate) / (math.Log(2) * math.Log(2)) * (-1)
   return uint64(math.Ceil(bloomBitsSize))
}

// CalHashFuncNum 计算需要的哈希函数数量
// elemNum 元素个数
// bloomSize 布隆过滤器位图大小
func CalHashFuncNum(elemNum, bloomSize uint64) uint64 {
   var k = math.Log(2) * float64(bloomSize) / float64(elemNum)
   return uint64(math.Ceil(k))
}

// Filter
type Filter struct {
   ElemNum     uint64
   BloomSize   uint64 
   HashFuncNum uint64
   ErrRate     float64

   bitMap *bitset.BitSet
   keys   map[uint32]bool
}

// NewFilter NewFilter
func NewFilter(elemNum, bloomSize, hashFuncNum uint64, errRate float64) *Filter {
   return &Filter{ElemNum: elemNum, BloomSize: bloomSize, HashFuncNum: hashFuncNum, ErrRate: errRate}
}

// Init 初始化布隆过滤器
func (f *Filter) Init() {
   // 分配布隆过滤器位图
   f.bitMap = bitset.New(uint(f.BloomSize))
   // 初始化哈希函数
   // 是否是类似HMAC-SHA256那种通过改变passphase值形成不同的哈希函数
   f.keys = make(map[uint32]bool)
   for uint64(len(f.keys)) < f.HashFuncNum {
      randNum, err := rand.Int(rand.Reader, new(big.Int).SetUint64(math.MaxUint32))
      if err != nil {
         panic(err)
      }
      f.keys[uint32(randNum.Uint64())] = true
   }
}

// Add  Add
func (f *Filter) Add(elem []byte) {
   var buf [4]byte
   for k := range f.keys {
      binary.LittleEndian.PutUint32(buf[:], k)
      hashResult := new(big.Int).SetBytes(HMACWithSHA128(elem, buf[:]))
      result := hashResult.Mod(hashResult, big.NewInt(int64(f.BloomSize)))
      // 把result对应的bit置1
      f.bitMap.Set(uint(result.Uint64()))
   }
}

// IsContain 判断元素是否在集合里面
func (f *Filter) IsContain(elem []byte) bool {
   var buf [4]byte
   for k := range f.keys {
      binary.LittleEndian.PutUint32(buf[:], k)
      hashResult := new(big.Int).SetBytes(HMACWithSHA128(elem, buf[:]))
      result := hashResult.Mod(hashResult, big.NewInt(int64(f.BloomSize)))
      // 查询result对应的bit是否被置1
      if !f.bitMap.Test(uint(result.Uint64())) {
         return false
      }
   }
   return true
}

// HMACWithSHA128 通过加盐生成不同的hash值
func HMACWithSHA128(seed []byte, key []byte) []byte {
   hmac512 := hmac.New(sha1.New, key)
   hmac512.Write(seed)
   return hmac512.Sum(nil)
}

测试:2亿长16B的元素,失误率0.0001,分配到过滤器需要0.4G,如果放hash表,则需要3.2G

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/185284.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • CLion 激活码 2022.01【2022最新】2022.02.07

    (CLion 激活码 2022.01)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html4K…

  • java最长递增子序列_求数组中最长递增子序列「建议收藏」

    java最长递增子序列_求数组中最长递增子序列「建议收藏」什么是最长递增子序列呢?问题描述如下:设L=是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=,其中k1对于这个问题有以下几种解决思路:1、把a1,a2,…,an排序,假设得到a’1,a’2,…,a’n,然后求a的a’的最长公共子串,这样总的时间复杂度为o(nlg(n))+o(n^2)=o(n^2);2、动态规划的思路:另设一辅助数组b,定义b[n]表示以a[n]结尾的最长递增…

  • 基于matlab的Canny算法的边缘检测(附源代码)

    基于matlab的Canny算法的边缘检测(附源代码)边缘概述边缘可以认为是图像中一定数量点亮度发生变化的地方,边缘检测大体上就是计算这个亮度变化的导数,依据导数的大小,判断亮度变化大小,从而界定目标与背景。在经典的边缘检测算法中Roberts算子,Prewitt算子,Sobel算子属于一阶差分算子,LoG算子,Canny算子属于二阶差分算子。一阶差分算子,就是求图像灰度变化曲线的导数,从而可以突出图像中的对象边缘,而二阶差分算子,求图像灰度变化导数的导数,对图像中灰度变化强烈的地方很敏感,从而可以突出图像的纹理结构。即一阶求边缘,二阶不仅检测出边缘还可检测

  • druid大数据实时分析_开源分布式处理系统

    druid大数据实时分析_开源分布式处理系统Druid:一个用于大数据实时处理的开源分布式系统

  • Python机器学习实战&lt;一&gt;:环境的配置

    Python机器学习实战&lt;一&gt;:环境的配置

    2021年11月14日
  • python删除文本最后一行_用python删除文件中的最后一行

    python删除文本最后一行_用python删除文件中的最后一行如何用python删除文件的最后一行?输入文件示例:helloworldfoobar输出文件示例:helloworldfoo我创建了以下代码来查找文件中的行数,但是我不知道如何删除特定的行号。我是新来的python–所以如果有一个更简单的方法–请告诉我。try:file=open(“file”)exceptIOError:print”Failedtoreadfile.”cou…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号