缓存雪崩、缓存击穿、缓存穿透的概念和解决方案。

布隆过滤器的简单原理和应用。

缓存雪崩

就是缓存层里的数据同一个时间点失效,那么这些数据就会集中打向 MySQL。

缓存击穿

缓存里有一条数据,一条数据失效后也是穿过了 redis 打到了 MySQL。

缓存击穿、缓存雪崩属于缓存穿透的一种特殊表现形式。

缓存穿透

描述

当找 redis 找不到数据时候,就会出现缓存穿透。

低频率的缓存穿透不可怕,正常现象。

当高频率的穿透就影响大了。

黑客攻击的场景,模拟很多客户端发送 id = -1 的请求。

id = -1 在 redis 中找不到,穿过 redis 找到数据库,数据处理不过来就崩了(拒绝服务攻击DDOS)。

解决方案

  • 通过 MySQL 中找不到的值缓存在 redis 中。(黑客太菜了)

    当然第一次查询 id = -1 的时候可能没找到穿透了,但是这次我把 id = -1 放在了 redis 中。

    id = -2 再查询我再放。。。。也是大量的访问数据库。(UUID 黑盒 每次生成一个不一样的 ID)

    这个方案适得其反,redis 一定的数据淘汰策略(LRU、LFU…)如果每次都是 UUID,那么真正需要缓存的数据就被淘汰了,redis 里是一些垃圾数据。

  • 过滤器(redis),这个过滤器把 MySQL 里面的所有 id 号,放在 redis 和 MySQL 的中间(不行),不一定是通过 id 查询或者 id 过多,这样就会导致过滤器的效率太低,内存紧张,导致整个链路都很慢。

    解决过滤器中数据过多的场景。布隆过滤器,通过一定的错误率降低内存的占用。

    比如 id = 100,传给 hash 函数,来一个 bin(二进制, size=10) 数组,保证哈希结果在 0-9 之间。。。。。。

    拿到 id = 100,计算出的 hash 相同,就会告诉客户端你要的数据是有的。

    错误发生在计算哈希上,如果布隆过滤器告诉你数据存在,那么数据不一定存在。如果布隆过滤器告诉你数据不存在,那么这个数据一定不存在。

    宁可错杀 3k 不放过一个。发生哈希碰撞就有可能是一次错误,数组的长度影响错误率

    哈希函数的个数也有关系。布隆过滤器的简单实现是 3 个 hash 函数计算的三个位置标示一个数据是否存在。哈希函数个数多了反而错误率升高。数组长度很长会增加内存占用。

    【人生中最重要的一个字“度”】,通过算法计算合适的 hash 函数个数和数组长度。通常的布隆过滤器会要求提供允许的错误率 fpp 和存储的数据量 n。然后通过公式计算出数组大小 m 和 hash 函数的个数 k。

    m = - ( n*ln(fpp) ) / ( ln(2) ^2 )

    k = m/n * ln(2)

遇到删除数据的情况?如果 id = 100 和 id = 10 的 hash 结果相同,我删除了 id = 10 的数据,那么布隆过滤器的这个 hash 结果的位置不能设为 0,因为还有数据对应。

如果场景中有频繁的数据删除情况,建议搞一个二维的数组,第二维的数组用来计数。(长度 100亿占用 1GB 左右)

面试题:文件 A 存了 100 亿个URL,B 文件也是 100 亿个 URL。只给一个 4GB 内存文件,快速找出 AB 的交集。

模糊算法

通过布隆过滤器来计算 A 中的,B 中的 URL,然后找到对应的交集。只需要一次的磁盘 IO 即可。

精准算法

A、B 两个大文件拆分 1000 个放一个文件,分块计算 hash 值然后对 1000 取余。然后对A、B的小文件一一比较。拆分成小文件是为了可以加载入内存中。

相同 URL 的 hash 值相同,取摸后也相同。所以会出现在 1-1 对应的小文件中。


EOF