缓存雪崩、缓存击穿、缓存穿透的概念和解决方案。
布隆过滤器的简单原理和应用。
缓存雪崩
就是缓存层里的数据同一个时间点失效，那么这些数据就会集中打向 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
