本章主要是对大牛写的 分布式缓存 的思考和总结，希望能给正在学习的同学一点灵感。
第一天 缓存淘汰机制
算法选择
因为缓存都是存在内存中的，当超过固定大小的时候，需要选择行的删除旧数据，称为缓存淘汰机制。
其中缓存淘汰机制包含了以下几种：
- FIFO(First In First Out)：先进先出，即队列。缺点：最早添加的数据及时被不断访问也会最早的被删除，导致命中率低下。
- LFU(Least Frequently Used)：最少使用。缺点：如果有某个数据的访问在一段时间内很高，那即使后续没有命中也会存留在缓存中。
- LRU(Least Recently Used)：最近最少使用。当前缓存设计所使用的缓存淘汰机制。
算法设计
1
设计的时候需要时刻考虑对键值对的添加、获取和删除的时间复杂度。
- Q：如何对元素进行添加和删除，并且又较优的时间复杂度？
A：使用一个双向链表，当数据被访问的时候，移到队尾。当内存不足时，删除队头元素。添加和删除的时间复杂度为O(1)。 - Q：这种设计会导致每次获取元素的时候遍历一次链表，有没有什么优化方式？
A：使用一个Map，K/V分别为元素的键和指定的链表元素。时间复杂度为O(1)。
第二天 单机并发缓存
满足并发读写需求（加锁）
并发的状况下，变量的读写就会冲突；以Map为例，多个协程同时对Map读写就会报panic错误。 所以实现一个结构体并且给读写都上锁，防止变量冲突。这里需要注意的是，锁不直接写在上述实现的算法中以造成逻辑层和业务层的冲突。
添加Group概念
为了满足一部分数据存在一个命名空间下，另一部分存在另一个命名空间下的需求，需要抽象出Group的概念，比如我能够有一个visitor的Group，存放访客信息；另一个cart存放购物车指定用户的购物车信息。
第三天 HTTP服务端
实现一个HTTP服务端，用于提供缓存的访问，访问形式如 /{GROUP}/{KEY}。
若需要使用原生的http包实现，只需要标准库中的http.Handler 接口。
1
2
3
4
5
package http
type Handler interface {
ServeHTTP(w ResponseWriter, r *Request)
}
本节的内容比较简单，不做过多描述。
第四天 一致性哈希
和其他分布式系统不一样的是，缓存的分布式不需要将数据存放在多个节点，因为当缓存不存在的时候，节点会到源处获取。
这一章为了实现当存在多个节点的时候（分布式），需要到哪一个节点进行缓存的获取。 设计思路是将不同的Key分散到不同的节点上，减轻单节点压力并且保证命中率。一致性哈希算法就是为了解决该问题出现的。
算法思路：
一致性哈希算法将 key 映射到 2^32 的空间中，将这个数字首尾相连，形成一个环。
- 计算节点/机器(通常使用节点的名称、编号和 IP 地址)的哈希值，放置在环上。
- 计算 key 的哈希值，放置在环上，顺时针寻找到的第一个节点，就是应选取的节点/机器。
- Q：增加/减少节点的时候会对缓存造成影响吗？
A：会，若是使用自定义的hash算法，则可能会使所有的元素都失效，造成缓存雪崩。但是一致性hash只会对部分的键造成影响，当节点更换时，只需要重新到源进行获取即可。
缓存雪崩：缓存在同一时刻全部失效，造成瞬时DB请求量大、压力骤增，引起雪崩。常因为缓存服务器宕机，或缓存设置了相同的过期时间引起。
- Q：如果服务器的节点过少，容易引起 key 的倾斜，如何解决这个问题？
A：引入虚拟节点的概念，设计一个真实节点对应多个虚拟节点。假设 1 个真实节点对应 3 个虚拟节点，那么 peer1 对应的虚拟节点是 peer1-1、 peer1-2、 peer1-3（通常以添加编号的方式实现），其余节点也以相同的方式操作。- 第一步，计算虚拟节点的 Hash 值，放置在环上。
- 第二步，计算 key 的 Hash 值，在环上顺时针寻找到应选取的虚拟节点，例如是 peer2-1，那么就对应真实节点 peer2。
第五天 分布式节点
这节主要是将前面实现前面论述的内容，然后通过master将接口暴露出来。其中master和worker之间的通讯使用的是HTTP协议。
由于基本上都是代码实现，这里不做过多赘述。
第六天 防止缓存击穿
缓存雪崩：缓存在同一时刻全部失效，造成瞬时DB请求量大、压力骤增，引起雪崩。缓存雪崩通常因为缓存服务器宕机、缓存的 key 设置了相同的过期时间等引起。
缓存击穿：一个存在的key，在缓存过期的一刻，同时有大量的请求，这些请求都会击穿到 DB ，造成瞬时DB请求量大、压力骤增。
缓存穿透：查询一个不存在的数据，因为不存在则不会写到缓存中，所以每次都会去请求 DB，如果瞬间流量过大，穿透到 DB，导致宕机。
为了避免缓存击穿，这节使用了一个新的结构体保存首次获取到的元素值。
第七天 使用Protobuf通信
Protobuf是一种通信的数据类型，使用Protobuf的原因是因为简单，快。
