瑞安天气:高可用服务设计之若何应对缓存穿透

admin 4个月前 (06-10) 科技 46 1

靠山

用户中央是授权逻辑与用户信息相关逻辑构建的应用。分布式系统中,大多数营业都需要和用户中央打交道,为了保证用户中央服务的高可用,避免不了做缓存、导入搜索引擎从而降低数据库的压力。然而有些不经由用户中央授权的营业场景查询用户中央的数据,可能引发大量无效的查询,发生缓存穿透,直接对搜索引擎和数据库造成压力。若何解决用户中央缓存穿透的问题呢?接下来就着重说一下布隆过滤器是怎么“隔档”这些无效查询的

缓存穿透

缓存穿透是指用户查询数据,在数据库没有,自然在缓存中也不会有。这样就导致用户查询的时刻,在缓存中找不到对应keyvalue,每次都要去数据库再查询一遍,然后返回空(相当于举行了两次无用的查询)。这样请求就绕过缓存直接查数据库

布隆过滤器

基本概念

  • 布隆过滤器(Bloom Filter)是1970年由布隆提出的。它现实上是一个很长的二进制向量(位图)和一系列随机映射函数(哈希函数)。
  • 布隆过滤器可以用于检索一个元素是否在一个聚集中。它的优点是空间效率和查询时间都远远跨越一样平常的算法,瑕玷是有一定的误识别率和删除难题。

特点

  • 空间效率高和查询效率高的概率型数据结构。
  • 对于一个元素检测是否存在的挪用,BloomFilter会告诉挪用者两个效果之一:可能存在或者一定不存在。
  • 一个很长的二进制向量 (位数组)
  • 一系列随机函数哈希)。
  • 有一定的误判率(哈希表是正确匹配)

原理

布隆过滤器(Bloom Filter)的焦点实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k

(1) 添加元素历程

  • 将要添加的元素给k个哈希函数。
  • 获得对应于位数组上的k个位置。
  • 将这k个位置设为1。

(2) 查询元素历程

  • 将要查询的元素给k个哈希函数。
  • 获得对应于位数组上的k个位置。
  • 若是k个位置有一个为0,则一定不在聚集中。
  • 若是k个位置所有为1,则可能在聚集中。

相关公式

很显然,凭据布隆过滤器的原理和特征,bit数组巨细和哈希函数的个数都市影响误判率。那么布隆过滤器是若何权衡bit数组巨细和哈希函数个数的呢?

布隆过滤器bit数组巨细为m,样本数目为n,失误率为p

假设样本容量n=5000W,误判率是0.03,那么所需要的内存空间巨细是m = -5000W * -3.057 / (0.7)^2 318,437,500 39.8MB

演示

(1)参考地址

https://www.jasondavies.com/bloomfilter

(2)可能存在

 瑞安天气:高可用服务设计之若何应对缓存穿透 第1张

 

 

 (3)一定不存在

瑞安天气:高可用服务设计之若何应对缓存穿透 第2张

Guava Bloom Filter

Guava中,布隆过滤器的实现主要涉及到2个类, BloomFilterBloomFilterStrategies首先来看一下 BloomFilter的成员变量。需要注重的是差别Guava版本的 BloomFilter实现差别。

瑞安天气:高可用服务设计之若何应对缓存穿透 第3张

  • BitArrays 是界说在BloomFilterStrategies中的内部类,封装了布隆过滤器底层bit数组的操作。
  • numHashFunctions示意哈希函数的个数,即上文公式提到的k
  • Funnel主要是把随便类型的数据转化成Java基本数据类型(primitive value,如charbyteint……),默认用java.nio.ByteBuffer实现,最终均转化为byte数组。
  • Strategy是界说在BloomFilter类内部的接口,代码如下,有3个方式,put(插入元素),mightContain(判断元素是否存在)和ordinal方式(可以理解为枚举类中谁人默认方式)。

 

 瑞安天气:高可用服务设计之若何应对缓存穿透 第4张

BloomFilterStrategies类,首先它是实现了BloomFilter.Strategy 接口的一个枚举类,其次它有两个2枚举值,MURMUR128_MITZ_32MURMUR128_MITZ_64,划分对应了32位哈希映射函数和64位哈希映射函数,后者使用了murmur3 hash天生128哈希值,具有更大的空间,不外原理是相通的

MURMUR128_MITZ_64实现原理可以参考(http://rrd.me/gDkD5)。

 

瑞安天气:高可用服务设计之若何应对缓存穿透 第5张

BitArrayguava bloom filter底层bit数组的一个实现类。Guava使用的是一个long型数组实现了类似BitSet的数据结构。第一个组织函数传入了一个bit位的位数bits,然后bits除以64并向上取整获得long型数组的巨细。getset操作凭据bit位的索引index,找到对应的操作工具data[index >>> 6](等价于data[index / 64]),划分跟(1L << index)与操作和或操作响应的效果。

Redis Bloom Filter

分布式系统直接使用guava bloom filter在某些营业场景下不是很利便,既然是分布式环境,最好照样通过分布式缓存封装一版布隆过滤器。

通过对guava bloom filter的剖析,由单机版革新成分布式版,只需要重新实现三个guava bloom filter的三个类(BloomFilterBloomFilterStrategiesBitArray)。

瑞安天气:高可用服务设计之若何应对缓存穿透 第6张

RedisBitArray革新不是很贫苦,只需要引入操作分布式缓存的JedisCluster工具就好了。getset操作对应JedisCluster工具的getbitsetbit操作(针对String类型的值,Redis通过 位操作 实现了BitMap数据结构)。

BloomFilterBloomFilterStrategies的革新相对比较简单,这里就不详细说明晰。

Routing Bloom Filter

为什么要有路由布隆过滤器?通过上面的公式可以知道,当要插入的样本数目n越大,那么需要分配的内存容量m也会越大。也就是布隆过滤器的欠妥使用极易发生大 Value,增添 内存溢出或者壅闭风险,因此天生环境中建议对体积重大的布隆过滤器举行拆分,拆分的规则我们界说为根据一定的路由规则对应到差别的布隆过滤器。

(1) 设计方案

 瑞安天气:高可用服务设计之若何应对缓存穿透 第7张

(2) 路由计谋

瑞安天气:高可用服务设计之若何应对缓存穿透 第8张

  • routing方式凭据样本盘算出路由key值。
  • exceptedInsertions方式凭据样本获取到路由key值,然后盘算期望插入的样本数目。

 

(3) 成员变量

瑞安天气:高可用服务设计之若何应对缓存穿透 第9张

  • ROUTE_MAP是内陆缓存,存储RoutingStrategy工具routing方式盘算出的路由key值以及对应的RedisBloomFilter实例。
  • routingStrategy是路由计谋RoutingStrategy实例。
  • bfRedisKeyPrefixRedis布隆过滤器bit数组在redis中对应的key值前缀。
  • bfKeysMappingRedisKey存储了所有Redis布隆过滤器bit数组在redis中对应的key(即bfRedisKeyPrefix + 路由key)的聚集。

 

(4) put操作

瑞安天气:高可用服务设计之若何应对缓存穿透 第10张

获取当前样本工具的routeKeyROUTE_MAPcomputeIfAbsent方式凭据routeKey获取对应的Redis Bloom Filter,若是不存在则建立一个新的Redis Bloom Filter工具实例并保存到ROUTE_MAP中。变量bloomFilterRedisKey = bfRedisKeyPrefix + routeKey,也就是Redis Bloom Filter bit数组在redis中存储的key值,最后保存在分布式缓存的聚集中(即bfKeysMappingRedisKey对应的聚集)。

 

(5) mightContain操作

瑞安天气:高可用服务设计之若何应对缓存穿透 第11张

put操作的流程基本一致,在获取routeKey对应的Redis Bloom Filter实例的时刻,若是不存在需要判断分布式缓存bfKeysMappingRedisKey对应的聚集中是否存在bloomFilterRedisKey,若是不存在说明put操作没有建立对应的Redis Bloom Filter实例,直接返回null

 

(6) 监控信息

瑞安天气:高可用服务设计之若何应对缓存穿透 第12张

  • approximateElementCount,布隆过滤器中可能存在的元素个数。
  • bitSize,布隆过滤器bit数组巨细。
  • bitCount,布隆过滤器bit数组中bit位是1的数目。
  • keyLength,布隆过滤器bit数组通过strlen统计的长度。

注:布隆过滤器的bit数组在redis中对应的数据类型是String哦!

应用场景

  • 网页爬虫对URL的去重。
  • 黑名单,垃圾邮件过滤。
  • 解决数据库缓存击穿。

现实应用

新闻中央给用户推送新闻的时刻,是根据先微信小程序用户,否则民众号用户串行逻辑来执行的(大多数新闻都是根据用户手机号推送的)。小程序的用户系统相对民众号的用户系统是较少的,而且小程序用户订阅新闻的量级增进的缓慢。这就泛起了许多不是小程序用户的查询请求,也就是泛起了上面提到 缓存穿透 征象,无形之中会增添搜索引擎和数据库压力。

小程序用户查询服务集成了布隆过滤器,很优雅的解决了缓存穿透的问题。营业上线初期,天天大约有200W300W的请求,可以过滤掉90%以上的无效用户查询请求。看着这鲜明的效果,欣喜若狂,心想着这方案集成的太完美了,真香!

源码参考

请关注微信订阅号(算法和手艺SHARING),回复:bloomfilter, 便可查看。

参考资料

https://www.jianshu.com/p/2104d11ee0a2

https://zhuanlan.zhihu.com/p/43263751

https://blog.csdn.net/u012422440/article/details/94088166

https://www.jianshu.com/p/44b4b42931d4

,

皇冠APP

皇冠体育APP是一个开放皇冠代理APP下载、皇冠会员APP下载、皇冠线路APP下载、皇冠登录APP下载的平台,皇冠体育APP上最新登录线路、新2皇冠网址更新最快,皇冠体育APP开放皇冠会员注册、皇冠代理开户等业务。

皇冠APP声明:该文看法仅代表作者自己,与本平台无关。转载请注明:瑞安天气:高可用服务设计之若何应对缓存穿透

网友评论

  • (*)

最新评论

  • 联博开奖网 2020-06-10 00:06:49 回复

    欧博网址www.cx11yj.cn欢迎进入欧博网址(Allbet Gaming),欧博网址开放会员注册、代理开户、电脑客户端下载、苹果安卓下载等业务。更新蛮勤,适合消遣

    1

文章归档

站点信息

  • 文章总数:556
  • 页面总数:0
  • 分类总数:8
  • 标签总数:967
  • 评论总数:157
  • 浏览总数:3312