阅读 63

缓存穿透 缓存雪崩

缓存穿透

概念

缓存穿透是指查询一个一定不存在的数据,由于缓存是不命中时需要从DB查询,查不到数据则不写入缓存,这将导致这个不存在的数据每次请求都要到数据库去查询,造成缓存穿透。

解决方案

  1. 采用布隆过滤器,使用一个足够大的bitmap,用于存储可能访问的key,不存在的key直接被过滤

    bloomfilter 就类似于一个 hash set ,用于快速判断某个元素是否存在于集合中,其典型的应用场景就是快速判断一个key是否存在于某容器,不存在就直接返回,布隆过滤器的关键就在于hash算法和容器大小。

    和一般的的hash set不同的是,这个算法无需存储key的值,对于每个key,只需要k个比特位,每个存储一个标志,用于判断key是否在集合中。

    算法:

    第一步:开辟空间

    开辟一个长度为m的位数组(或者称二进制向量),这个不同的语言有不同的实现方式,甚至你可以用文件来实现。

    第二步:寻找hash函数

    获取几个hash函数,前辈们已经发明了很多运行良好的hash函数,比如BKDRHash,JSHash,RSHash等等。这些hash函数我们直接获取就可以了。

    第三步:写入数据

    将所需要判断的内容经过这些hash函数计算,得到几个值,比如用3个hash函数,得到值分别是1000,2000,3000。之后设置m位数组的第1000,2000,3000位的值位二进制

    第四步:判断

    接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。

    优点:不需要存储key,节省空间

    缺点:1.算法判断key在集合中,有一定概率key其实不在集合中

    2.无法删除

    典型的应用场景:

    某些存储系统的设计,会存在空查询缺陷:当查询一个不存在的key时,需要访问慢设备,导致效率低下。

    比如一个前端页面的缓存系统,可能这样设计:先查询某个页面在本地是否存在,如果存在就直接返回,如果不存在,就从后端获取。但是当频繁从缓存系统查询一个页面时,缓存系统将会频繁请求后端,把压力导入后端。

    这是只要增加一个bloom算法的服务,后端插入一个key时,在这个服务中设置一次
    需要查询后端时,先判断key在后端是否存在,这样就能避免后端的压力。


    布隆过滤器是由布隆在1970年提出的,他实际上是由一个很长的二进制向量和一些列随机映射函数组成。布隆过滤器可以用于检索一个元素是否在一个集合中。

    它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率(假正例False positives,即Bloom Filter报告某一元素存在于某集合中,但是实际上该元素并不在集合中)和删除困难,但是没有识别错误的情形(即假反例False negatives,如果某个元素确实没有在该集合中,那么Bloom Filter 是不会报告该元素存在于集合中的,所以不会漏报)。


  2. 访问key未来在DB查询到值,也可将空值写进缓存,但可以设置较短过期时间

    如果一个查询返回的数据为空(不管是数据不存在,还是系统故障),我们仍然把这个空结果进入缓存,但它的过期时间会很短,最长不超过五分钟。

    缓存空对象会有两个问题

    第一,空值做了缓存,意味着缓存层中存了更多的键,需要更多的内存空间,比较有效的方法是针对这类数据设置一个较短的过期时间,让其自动剔除。

    缓存层和存储层的数据会有一段时间窗口的不一致,可能会对业务有一定影响。例如过期时间设置为5分钟,如果此时存储层添加了这个数据,那此段时间就会出现缓存层和存储层数据的不一致,此时可以利用消息系统或其他方式清除掉缓存层中的空对象。

缓存雪崩

概念

大量的key设置了相同的过期时间,导致缓存在同一时刻全部失效,造成瞬间DB请求量大,压力骤增,引起雪崩

解决方案

可以在缓存设置过期时间加上一个随机值时间,使得每个key的过期时间分不开来,不会集中在同一时刻失效。

这个没有完美解决方法,但是可以分析用户行为,尽量让失效时间点均匀分布。大多数系统设计者考虑加锁或者队列的方式保证缓存的单线程写,从而能避免失效时大量的并发请求落到底层存储系统上。

解决方法

1.加锁排队,限流--限流算法。

1.计数2.滑动窗口3.令牌桶4.漏桶

在缓存失效后,通过加锁或者队列来控制读数据库谢缓存的线程数量。比如对某个key只允许一个线程查询数据和写缓存,其他线程等待。

业界比较常用的做法,是使用mutex。简单地来说,就是缓存失效的时候(判断拿出来的值为空),不是立即去load db,而是先使用缓存工具的某些带成功操作返回值的操作(比如Redis的SETNX或者Memcache的ADD)去set一个mutex key,当操作返回成功时,再进行load db的操作并回设缓存;否则,就重试整个get缓存的方法。

SETNX,是「SET if Not eXists」的缩写,也就是只有不存在的时候才设置,可以利用它来实现锁的效果。

2.数据预热

可以通过缓存reload机制,预先去更新缓存,在即将发生大并发访问前手动触发加载缓存不同的key,设置不同的过期时间,让缓存失效的时间点尽量均匀。

3.做二级缓存

  建立备份缓存,缓存A和缓存B,A设置超时时间,B不设值超时时间,先从A读缓存,A没有读B,并且更新A缓存和B缓存;

4.缓存永不过期

这里的“永不过期“包含两层意思

(1)从缓存上看,缺失没有设置过期时间,这就保证了,不会出现热点key过期问题,也就是“物理”不过期。

(2)从功能上看,如果不过期,那不就成静态的了吗?所以我们把过期时间存在key对应的value里,如果发现要过期了,通过一个后台的异步线程进行缓存的构建,也就是“逻辑”过期。

从实战看,这种方法对于性能非常友好,唯一不足的就是构建缓存时候,其余线程(非构建缓存的线程)可能访问的是老数据,但是对于一般的互联网功能来说这个还是可以忍受。


缓存击穿

概念

对于一些设置了过期时间的key,如果这些key可能会在某些时间点被超高并发地访问,是一种非常“热点”的数据。这个时候,需要考虑一个问题:缓存被“击穿”的问题,这个和缓存雪崩的区别在于这里针对某一key缓存,前者则是很多key。 缓存在某个时间点过期的时候,恰好在这个时间点对这个Key有大量的并发请求过来,这些请求发现缓存过期一般都会从后端DB加载数据并回设到缓存,这个时候大并发的请求可能会瞬间把后端DB压垮。

解决方案

和缓存雪崩解决情况一样

PHP+redis实现布隆过滤器

由于redis 是实现了setbit和getbit操作,天然是和实现布隆过滤器,redis也有布隆过滤器插件。

首先定义一个hash函数集合类,这些hash函数不一定都用到,实际上32位hash值的用3个就可以了,具体的数量可以根据你的位序列总量和你需要的存入的量决定,上面已经给出最佳值。

class BloomFilterHash
{
	/**
	 * 由Justin Sobel编写的按位散列函数
	 */
	public function JSHash($string, $len = null)
	{
    	$hash = 1315423911;
    	$len || $len = strlen($string);
    	for ($i=0; $i<$len; $i++) {
    		$hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2));
    	}
		return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
	}

	/**
	 * 该哈希算法基于AT&T贝尔实验室的Peter J. Weinberger的工作。
	 * Aho Sethi和Ulman编写的“编译器(原理,技术和工具)”一书建议使用采用此特定算法中的散列方法的散列函数。
	 */
	public function PJWHash($string, $len = null)
	{
		$bitsInUnsignedInt = 4 * 8; //(unsigned int)(sizeof(unsigned int)* 8);
    	$threeQuarters = ($bitsInUnsignedInt * 3) / 4;
    	$oneEighth = $bitsInUnsignedInt / 8;
    	$highBits = 0xFFFFFFFF << (int) ($bitsInUnsignedInt - $oneEighth);
    	$hash = 0;
    	$test = 0;
    	$len || $len = strlen($string);
    	for($i=0; $i<$len; $i++) {
			$hash = ($hash << (int) ($oneEighth)) + ord($string[$i]); } $test = $hash & $highBits; if ($test != 0) { $hash = (($hash ^ ($test >> (int)($threeQuarters))) & (~$highBits));
    	}
		return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
	}

	/**
	 * 类似于PJW Hash功能,但针对32位处理器进行了调整。
           它是基于UNIX的系统上的widley使用哈希函数。
	 */
	public function ELFHash($string, $len = null)
	{
		$hash = 0;
		$len || $len = strlen($string);
    	for ($i=0; $i<$len; $i++) {
        	$hash = ($hash << 4) + ord($string[$i]); $x = $hash & 0xF0000000; if ($x != 0) { $hash ^= ($x >> 24);
        	}
        	$hash &= ~$x;
    	}
		return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
	}

	/**
	 * 这个哈希函数来自Brian Kernighan和Dennis Ritchie的书“The C Programming Language”。
	 * 它是一个简单的哈希函数,使用一组奇怪的可能种子,它们都构成了31 .... 31 ... 31等模式,
           它似乎与DJB哈希函数非常相似。
	 */
	public function BKDRHash($string, $len = null)
	{
    	$seed = 131;  # 31 131 1313 13131 131313 etc..
    	$hash = 0;
    	$len || $len = strlen($string);
    	for ($i=0; $i<$len; $i++) {
        	$hash = (int) (($hash * $seed) + ord($string[$i]));
    	}
		return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
	}

	/**
	 * 这是在开源SDBM项目中使用的首选算法。
	 * 哈希函数似乎对许多不同的数据集具有良好的总体分布。
           它似乎适用于数据集中元素的MSB存在高差异的情况。
	 */
	public function SDBMHash($string, $len = null)
	{
		$hash = 0;
		$len || $len = strlen($string);
		for ($i=0; $i<$len; $i++) {
			$hash = (int) (ord($string[$i]) + ($hash << 6) + ($hash << 16) - $hash);
		}
		return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
	}

	/**
	 * 由Daniel J. Bernstein教授制作的算法,首先在usenet新闻组comp.lang.c上向世界展示。
	 * 它是有史以来发布的最有效的哈希函数之一。
	 */
	public function DJBHash($string, $len = null)
	{
		$hash = 5381;
		$len || $len = strlen($string);
		for ($i=0; $i<$len; $i++) {
			$hash = (int) (($hash << 5) + $hash) + ord($string[$i]);
		}
		return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
	}

	/**
	 * Donald E. Knuth在“计算机编程艺术第3卷”中提出的算法,主题是排序和搜索第6.4章。
	 */
	public function DEKHash($string, $len = null)
	{
		$len || $len = strlen($string);
		$hash = $len;
		for ($i=0; $i<$len; $i++) {
			$hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
		}
		return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
	}

	/**
	 * 参考 http://www.isthe.com/chongo/tech/comp/fnv/
	 */
	public function FNVHash($string, $len = null)
	{
		$prime = 16777619; //32位的prime 2^24 + 2^8 + 0x93 = 16777619
		$hash = 2166136261; //32位的offset
		$len || $len = strlen($string);
		for ($i=0; $i<$len; $i++) {
			$hash = (int) ($hash * $prime) % 0xFFFFFFFF;
			$hash ^= ord($string[$i]);
		}
		return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
	}
}复制代码

接着就是连接redis来进行操作

/**
 * 使用redis实现的布隆过滤器
 */
abstract class BloomFilterRedis
{
	/**
	 * 需要使用一个方法来定义bucket的名字
	 */
	protected $bucket;

	protected $hashFunction;

	public function __construct($config, $id)
	{
		if (!$this->bucket || !$this->hashFunction) {
			throw new Exception("需要定义bucket和hashFunction", 1);
		}
		$this->Hash = new BloomFilterHash;
		$this->Redis = new YourRedis; //假设这里你已经连接好了
	}

	/**
	 * 添加到集合中
	 */
	public function add($string)
	{
		$pipe = $this->Redis->multi();
		foreach ($this->hashFunction as $function) {
			$hash = $this->Hash->$function($string);
			$pipe->setBit($this->bucket, $hash, 1);
		}
		return $pipe->exec();
	}

	/**
	 * 查询是否存在, 存在的一定会存在, 不存在有一定几率会误判
	 */
	public function exists($string)
	{
		$pipe = $this->Redis->multi();
		$len = strlen($string);
		foreach ($this->hashFunction as $function) {
			$hash = $this->Hash->$function($string, $len);
			$pipe = $pipe->getBit($this->bucket, $hash);
		}
		$res = $pipe->exec();
		foreach ($res as $bit) {
			if ($bit == 0) {
				return false;
			}
		}
		return true;
	}

}复制代码

上面定义的是一个抽象类,如果要使用,可以根据具体的业务来使用。比如下面是一个过滤重复内容的过滤器。

/**
 * 重复内容过滤器
 * 该布隆过滤器总位数为2^32位, 判断条数为2^30条. hash函数最优为3个.(能够容忍最多的hash函数个数)
 * 使用的三个hash函数为
 * BKDR, SDBM, JSHash
 *
 * 注意, 在存储的数据量到2^30条时候, 误判率会急剧增加, 因此需要定时判断过滤器中的位为1的的数量是否超过50%, 超过则需要清空.
 */
class FilteRepeatedComments extends BloomFilterRedis
{
	/**
	 * 表示判断重复内容的过滤器
	 * @var string
	 */
	protected $bucket = 'rptc';

	protected $hashFunction = array('BKDRHash', 'SDBMHash', 'JSHash');
}复制代码


关注下面的标签,发现更多相似文章
评论