面试准备07-Redis和缓存

面试准备之redis和缓存

---

Redis

面试时总结的Redis相关内容都已整理到笔记 Redis 中

---

哈希

常用哈希算法

MD5 信息摘要算法

全称为 Message-Digest Algorithm 5，用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一，主流编程语言普遍已有 MD5 实现。MD5 的作用是把大容量信息压缩成一种保密的格式（就是把一个任意长度的字节串变换成定长的16进制数字串）。常见的文件完整性校验就是使用 MD5。

CRC 循环冗余校验

全称为 CyclicRedundancyCheck，中文名称为循环冗余校验。它是一类重要的，编码和解码方法简单，检错和纠错能力强的哈希算法，在通信领域广泛地用于实现差错控制。

MurmurHash 算法

高运算性能，低碰撞率，由 Austin Appleby 创建于 2008 年，现已应用到 Hadoop、libstdc++、nginx、libmemcached 等开源系统。Java 界中 Redis，Memcached，Cassandra，HBase，Lucene和Guava 都在使用它。

FNV 算法

全称为 Fowler-Noll-Vo 算法，是以三位发明人 Glenn Fowler，Landon Curt Noll，Phong Vo 的名字来命名的，最早在 1991 年提出。 FNV 能快速 hash 大量数据并保持较小的冲突率，它的高度分散使它适用于 hash 一些非常相近的字符串，比如 URL，hostname，文件名，text 和 IP 地址等。

Ketama 算法

一致性哈希算法的实现之一，其他的哈希算法有通用的一致性哈希算法实现，只不过是替换了哈希映射函数而已，但 Ketama 是一整套的流程

---

缓存

缓存淘汰算法

LFU(Least Frequently Used 最不经常使用)

LFU（Least Frequently Used 最不经常使用）算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。
实现：LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。
具体实现如下：

1. 新加入数据插入到队列尾部（因为引用计数为1）；
2. 队列中的数据被访问后，引用计数增加，队列重新排序；
3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除。

LRU(Least recently used 最近最少使用)

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
最常见的实现是使用一个链表保存缓存数据

1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。

---

读缓存

读操作流程

有了数据库和缓存两个地方存放数据之后,每当需要读取相关数据时，操作流程一般是这样的：
（1）读取缓存中是否有相关数据
（2）如果缓存中有相关数据，则返回【这就是所谓的数据命中“hit”】
（3）如果缓存中没有相数据，则从数据库读取相关数据【这就是所谓的数据未命中“miss”】，放入缓存中，再返回
缓存的命中率 = 命中缓存的请求个数/总缓存访问请求个数 = hit/(hit+miss)

---

缓存穿透(查询不存在的数据)

缓存穿透：key对应的数据在数据源一定不存在，每次针对此key的请求从缓存获取不到，请求都会到数据源，从而可能压垮数据源。

穿透带来的问题
试想一下，如果有黑客会对你的系统进行攻击，拿一个不存在的id 去查询数据，会产生大量的请求到数据库去查询。可能会导致你的数据库由于压力过大而宕掉。

解决方法

---

布隆过滤器

Bloom filter
适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集
布隆在1970年提出了布隆过滤器（Bloom Filter），是一个很长的二进制向量（可以想象成一个序列）和一系列随机映射函数（hash function）。

基本原理及要点：
对于原理来说很简单，位数组 bitmap 和 k 个独立 hash 函数。
将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。添加时增加计数器，删除时减少计数器。

如下：x,y,z经由哈希函数映射将各自在Bitmap中的3个位置置为1，当w出现时，仅当3个标志位都为1时，才表示w在集合中。图中所示的情况，布隆过滤器将判定w不在集合中。

布隆过滤器是概率性的，或者说是有误差的：
布隆过滤器不会漏报，但是会有误报。当可以承受一些误报时，布隆过滤器比其它表示集合的数据结构有着很大的空间优势。
当布隆过滤器说某个值存在时，这个值可能不存在; 当布隆过滤器说某个值不存在时，那就肯定不存在。

对所有可能查询的参数以hash形式存储，在控制层先进行校验，不符合则丢弃。还有最常见的则是采用布隆过滤器，将所有可能存在的数据哈希到一个足够大的bitmap中，一个一定不存在的数据会被这个bitmap拦截掉，从而避免了对底层存储系统的查询压力。

redis-lua-scaling-bloom-filter

计算 bloom filter 所需 bitmap 大小
https://www.di-mgt.com.au/bloom-calculator.html

erikdubbelboer / redis-lua-scaling-bloom-filter
https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter

最佳实践 缓存穿透,瞬间并发,缓存雪崩的解决方法
https://blog.csdn.net/fei33423/article/details/79027790

大量数据去重：Bitmap和布隆过滤器(Bloom Filter)
http://blog.csdn.net/zdxiq000/article/details/57626464

布隆过滤器的简单介绍与实例(BloomFilter)
https://www.2cto.com/net/201712/702254.html

缓存不存在的空值

也可以采用一个更为简单粗暴的方法，如果一个查询返回的数据为空（不管是数 据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。

比如系统中不存在 id=5322 的用户，但同样把 key = 5322, value = null 放入缓存，下次有来查 5322的，就能在缓存中命中。

缓存空对象会有两个问题：
第一，空值做了缓存，意味着缓存层中存了更多的键，需要更多的内存空间 ( 如果是攻击，问题更严重 )，比较有效的方法是针对这类数据设置一个较短的过期时间，让其自动剔除。
第二，缓存层和存储层的数据会有一段时间窗口的不一致，可能会对业务有一定影响。例如过期时间设置为 5分钟，如果此时存储层添加了这个数据(比如添加了id=5322的用户)，那此段时间就会出现缓存层和存储层数据的不一致，此时可以利用消息系统或者其他方式清除掉缓存层中的空对象。

最佳实践 缓存穿透,瞬间并发,缓存雪崩的解决方法
https://blog.csdn.net/fei33423/article/details/79027790

---

缓存击穿(数据存在但缓存失效了)

缓存击穿：key对应的数据存在，但在redis中过期，此时若有大量并发请求过来，这些请求发现缓存过期一般都会从后端DB加载数据并回设到缓存，这个时候大并发的请求可能会瞬间把后端DB压垮。

会带来什么问题
会造成某一时刻数据库请求量过大，压力剧增。

解决

互斥锁

上面的现象是多个线程同时去查询数据库的这条数据，那么我们可以在第一个查询数据的请求上使用一个 互斥锁来锁住它。
其他的线程走到这一步拿不到锁就等着，等第一个线程查询到了数据，然后做缓存。后面的线程进来发现已经有缓存了，就直接走缓存。

互斥锁方案的思路就是如果从redis中没有获取到数据，就让一个线程去数据库查询数据，然后构建缓存，其他的线程就等着，过一段时间后再从redis中去获取。

Guava缓存的get方法如何解决并发回源的击穿问题？

在高并发场景下，被动更新（先从缓存获取，没有则回源取，再放回缓存）的回源是要格外小心的，如果有太多请求在同一时间回源，可能导致后端服务无法支撑这么高并发而宕机，这就是所谓的缓存击穿问题。

Guava Cache 里的 CacheLoader 在回源的 load 方法上加了控制，对于同一个key，只让一个请求回源load，其他线程阻塞等待结果。

---

缓存雪崩(缓存集中失效)

缓存雪崩：当缓存服务器重启或者大量缓存集中在某一个时间段失效，这样在失效的时候，也会给后端系统(比如DB)带来很大压力。

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

解决方法：
1、加锁排队
在缓存失效后，通过加锁或者队列来控制读数据库写缓存的线程数量。比如对某个key只允许一个线程查询数据和写缓存，其他线程等待。
业界比较常用的做法，是使用mutex。简单地来说，就是在缓存失效的时候（判断拿出来的值为空），不是立即去load db，而是先使用缓存工具的某些带成功操作返回值的操作（比如Redis的SETNX或者Memcache的ADD）去set一个mutex key，当操作返回成功时，再进行load db的操作并回设缓存；否则，就重试整个get缓存的方法。
SETNX，是「SET if Not eXists」的缩写，也就是只有不存在的时候才设置，可以利用它来实现锁的效果。

2、数据预热
可以通过缓存reload机制，预先去更新缓存，再即将发生大并发访问前手动触发加载缓存

3、设置不同过期时间(错峰过期)
不同的key，设置不同的过期时间，让缓存失效的时间点尽量均匀

4、做二级缓存，或者双缓存策略
做二级缓存，或者双缓存策略。A1为原始缓存，A2为拷贝缓存，A1失效时，可以访问A2，A1缓存失效时间设置为短期，A2设置为长期。

5、缓存永远不过期
这里的“永远不过期”包含两层意思：
(1) 从缓存上看，确实没有设置过期时间，这就保证了，不会出现热点key过期问题，也就是“物理”不过期。
(2) 从功能上看，如果不过期，那不就成静态的了吗？所以我们把过期时间存在key对应的value里，如果发现要过期了，通过一个后台的异步线程进行缓存的构建，也就是“逻辑”过期.

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

最佳实践 缓存穿透,瞬间并发,缓存雪崩的解决方法
https://blog.csdn.net/fei33423/article/details/79027790

《redis学习》– 缓存穿透和缓存雪崩的预防和解决
https://blog.csdn.net/lizhi_java/article/details/68953014?locationNum=14&fps=1

缓存穿透，缓存击穿，缓存雪崩解决方案分析
https://blog.csdn.net/zeb_perfect/article/details/54135506

---

缓存更新策略

缓存的更新策略主要有两种：被动失效和主动更新
什么是更新缓存：数据不但写入数据库，还会写入缓存
什么是淘汰缓存：数据只会写入数据库，不会写入缓存，只会把数据淘汰掉

淘汰缓存(被动失效)

一般来说，缓存数据主要是服务读请求的，并设置一个过期时间;或者当数据库状态改变时，通过一个简单的delete操作，使数据失效掉;当下次再去读取时，如果发现数据过期了或者不存在了，那么就重新去持久层读取，然后更新到缓存中;这即是所谓的被动失效策略。

但是在被动失效策略中存在一个问题，就是从缓存失效或者丢失开始直到新的数据再次被更新到缓存中的这段时间，所有的读请求都将会直接落到数据库上;而对于一个大访问量的系统来说，这有可能会带来风险。所以我们换一种策略就是，当数据库更新时，主动去同步更新缓存，这样在缓存数据的整个生命期内，就不会有空窗期，前端请求也就没有机会去亲密接触数据库。

先淘汰缓存还是先写库？

当写操作发生时，假设淘汰缓存作为对缓存通用的处理方式，又面临两种抉择：
（1）先写数据库，再淘汰缓存
（2）先淘汰缓存，再写数据库

假设先写数据库，再淘汰缓存：第一步写数据库操作成功，第二步淘汰缓存失败，则会出现DB中是新数据，Cache中是旧数据，数据不一致。
假设先淘汰缓存，再写数据库：第一步淘汰缓存成功，第二步写数据库失败，则只会引发一次Cache miss。

结论：数据和缓存的操作时序，结论是清楚的：先淘汰缓存，再写数据库。

缓存架构设计二三事
https://blog.csdn.net/justinsause/article/details/51063631

主动更新缓存

前面我们提到主动更新主要是为了解决空窗期的问题，但是这同样会带来另一个问题，就是并发更新的情况;

在集群环境下，多台应用服务器同时访问一份数据是很正常的，这样就会存在一台服务器读取并修改了缓存数据，但是还没来得及写入的情况下，另一台服务器也读取并修改旧的数据，这时候，后写入的将会覆盖前面的，从而导致数据丢失;这也是分布式系统开发中，必然会遇到的一个问题。

主动更新缓存的数据一致问题

更新数据和缓存的操作顺序：
1、对于insert数据，先插入数据库，再创建缓存。
2、对于update数据，先淘汰缓存（删除key），再update数据库，改库成功再重新设置缓存。

解决的方式主要有三种：
a、锁控制;这种方式一般在客户端实现(在服务端加锁是另外一种情况)，其基本原理就是使用读写锁，即任何进程要调用写方法时，先要获取一个排他锁，阻塞住所有的其他访问，等自己完全修改完后才能释放;如果遇到其他进程也正在修改或读取数据，那么则需要等待;
锁控制虽然是一种方案，但是很少有真的这样去做的，其缺点显而易见，其并发性只存在于读操作之间，只要有写操作存在，就只能串行。

b、版本控制;这种方式也有两种实现，一种是单版本机制，即为每份数据保存一个版本号，当缓存数据写入时，需要传入这个版本号，然后服务端将传入的版本号和数据当前的版本号进行比对，如果大于当前版本，则成功写入，否则返回失败;这样解决方式比较简单;但是增加了高并发下客户端的写失败概率;

还有一种方式就是多版本机制，即存储系统为每个数据保存多份，每份都有自己的版本号，互不冲突，然后通过一定的策略来定期合并，再或者就是交由客户端自己去选择读取哪个版本的数据。很多分布式缓存一般会使用单版本机制，而很多NoSQL则使用后者。

【Redis】缓存更新的套路
https://blog.csdn.net/zzh920625/article/details/7802753

删key改库写key的数据一致性分析

更新缓存应该如何做，什么步骤？
1、删key
2、改库
3、写缓存

看起来这个步骤很合理，当 改库 失败回滚时，缓存也不会更新，下次查询从库里查到旧值，但是，在高并发情况下，还是有问题

当并发很大时，会出现什么问题？

两个线程同时 update 同一个缓存 key，线程1 要改为 3，线程2 要改为 4，
可能会有执行顺序：
1、线程1 删 key
2、线程2 看到 key 没有了，不处理
3、线程1 改库，update 为 3
4、线程2 改库，update 为 4
5、线程2 写缓存，设置redis 为 4
6、线程1 update库之后 hang 了一会儿，现在醒过来了，写缓存，设置redis为 3
发生了数据不一致，库里是 4， redis里是 3

---

缓存的扩展性

缓存系统的扩展性是指在空间不足的性情况，能够通过增加机器等方式快速的在线扩容。这也是能够支撑业务系统快速发展的一个重要因素。

---

一致性哈希consistent hashing

分布式缓存设计核心点：在设计分布式cache系统的时候，我们需要让key的分布均衡，并且在增加cache server后，cache的迁移做到最少。

首先求出机器节点的hash值（怎么算机器节点的hash？ ip+端口 可以作为hash的参数吧），然后将其分布到0～2^32的一个圆环上（顺时针分布）
如果有一个写入缓存的请求，其中Key值为K，计算器hash值Hash(K)， Hash(K) 对应于环中的某一个点，如果该点对应没有映射到具体的某一个机器节点，那么顺时针查找，直到第一次找到有映射机器的节点，该节点就是确定的目标节点。

减少结点

假如当前集群状态如图：

当 结点B 宕机后，只需要将 结点B 上的数据迁移到 结点C 上即可，其他结点完全不用动，如下图：

假如不使用一致性哈希算法来组织集群，比如使用 key % 结点数n 来组织，则其中一个结点宕机后，n发生变化，所有数据都需要做迁移，这是完全无法容忍的。

增加结点

在一致性Hash算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

虚拟结点解决数据倾斜

一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器，此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。
如下图：

为了解决这种数据倾斜问题，一致性哈希算法引入了 虚拟节点 机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。

例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点。
如图：

同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。

在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

一致性hash算法 - consistent hashing
http://blog.csdn.net/sparkliang/article/details/5279393

memcache的一致性hash算法使用
http://blog.csdn.net/kongqz/article/details/6695417

一致性哈希算法原理
https://www.cnblogs.com/lpfuture/p/5796398.html

一致性hash算法 - consistent hashing
http://blog.csdn.net/sparkliang/article/details/5279393

memcache的一致性hash算法使用
http://blog.csdn.net/kongqz/article/details/6695417

---

基于nginx的preread实现七层负载均衡

常见的四层负载均衡策略是根据连接来源 IP 进行一致性 Hash，在节点数不变的情况下这样能保证每次都 Hash 到同一个 Broker 中，甚至在节点数稍微改变时也能大概率找到之前连接的节点。

之前我们也使用过来源 IP Hash 的策略，主要有两个缺点：

• 分布不够均匀，部分来源 IP 是大型局域网 NAT 出口，上面的连接数多，导致 Broker 上连接数不均衡
• 不能准确标识客户端，当移动客户端掉线切换网络就可能无法连接回刚才的 Broker 了

所以我们考虑七层的负载均衡，根据客户端的唯一标识来进行一致性 Hash，这样随机性更好，同时也能保证在网络切换后也能正确路由。常规的方法是需要完整解析通讯协议，然后按协议的包进行转发，这样实现的成本很高，而且增加了协议解析出错的风险。

最后我们选择利用 Nginx 的 preread 机制实现七层负载均衡，对后面长连接 Broker 的实现的侵入性小，而且接入层的资源开销也小。

Nginx 在接受连接时可以指定预读取连接的数据到 preread buffer 中，我们通过解析 preread buffer 中的客户端发送的第一个报文提取客户端标识，再使用这个客户端标识进行一致性 Hash 就拿到了固定的 Broker。

知乎千万级高性能长连接网关是如何搭建的
https://mp.weixin.qq.com/s/34nM-4d04yZZTQKiAGeEig

---

使用缓存带来的问题

我们不能否认缓存给我们带来诸多便利，同时，我们不能忽略缓存确实也给我们带来了不少困扰：
1、数据的一致性、实时性受影响。（需要对数据的一致性，时效性进行评估，进而确定是否要缓存或设定缓存的过期时间，比如个性化的数据是否值得缓存？）

2、缓存介质带来的不可靠性。（一般使用内存做缓存的话，若机器故障，如何保证缓存的高可用？可考虑对缓存进行分布式做成高可用，同时，需要接受这种不可靠不安全会给数据带来的问题，在异常情况下进行补偿处理，定期持久化等方式）

3、缓存的数据使得更难排查问题。因为缓存命中是随着访问随时变化的，缓存的行为难以重现，使得出现BUG很难排查。

4、进程内缓存可能会增加GC压力：在具有垃圾收集功能的语言中（如java），大量长寿命的缓存对象会增加垃圾收集的时间和次数。

性能优化–缓存篇
https://blog.csdn.net/liaoyulin0609/article/details/51762935

---

二级缓存(本地缓存+分布式缓存)

ehcache+redis 二级缓存
redis做中心缓存的问题
redis主备作为中心节点提供缓存，其他节点都向redis中心节点取数据。
但是，随着访问量增大，大量的缓存数据访问使得应用服务器和缓存服务器之间的网络I/O消耗越大。

那么要怎么处理呢？
所以两级缓存的思想诞生了，在redis的方案上做一步优化，在缓存到远程redis的同时，缓存一份到本地进程ehcache（此处的ehcache不用做集群，避免组播带来的开销），取缓存的时候会先取本地，没有会向redis请求，这样会减少应用服务器<–>缓存服务器redis之间的网络开销。

Spring+ehcache+redis两级缓存–缓存实战篇（1）
https://blog.csdn.net/liaoyulin0609/article/details/51787020

---

ehcache memcached redis对比

ehcache
纯java实现，缓存在内存中，可持久化到硬盘，效率高于memcache；但是缓存共享麻烦，集群分布式应用不方便。如果是单个应用或者对缓存访问要求很高的应用，用ehcache。
ehcache也有缓存共享方案，不过是通过RMI或者Jgroup多播方式进行广播缓存通知更新，缓存共享复杂，维护不方便；简单的共享可以，但是涉及到缓存恢复，大数据缓存，则不合适。

memcached
多种语言实现，K/V缓存，缓存在内存中，支持分布式缓存，可通过第三方实现持久化，基于libevent的事件处理。
memcache在客户端中实现分布式缓存，通过分布式算法指定目标数据的节点。

redis
K/V缓存，支持丰富的数据结构（list, set, hash），支持数据持久化，支持分布式缓存。
通过socket访问到缓存服务，效率比ehcache低，比数据库要快很多，处理集群和分布式缓存方便，有成熟的方案。如果是大型系统，存在缓存共享、分布式部署、缓存内容很大的，建议用redis。

---