最近在看极客兔兔大佬的七天用Go从零实现系列，其中有个分布式缓存geeCache，从设计的角度整理下自己的想法和思路。
如何设计分布式缓存？
设计一个分布式缓存系统，需要考虑资源控制、淘汰策略、并发、分布式节点通信等各个方面的问题。
从上述方面考虑，我们需要实现的功能如下
1、缓存功能以及缓存淘汰策略
2、缓存支持并发读取
3、分布式节点通信 客户端和服务端
4、使用一致性哈希解决分布式负载均衡问题
1、缓存功能以及缓存淘汰策略
常见的缓存淘汰策略有三种
FIFO First In First Out 先进先出
淘汰缓存中最早添加的记录。
思想：最早添加的记录，其不被使用的可能性比刚添加的可能性大
实现：通过创建一个队列，新增记录添加到队尾，删除队首记录
缺点：很多场景下，部分记录虽然最早添加但是也常被访问，这些数据命中率会降低。
LFU Least Frequently Used 最少使用
淘汰缓存中访问频率最低的记录
思想：数据过去被访问多次，将来被访问频率会更高
实现：维护一个按照访问次数排序的队列，每次访问，次数加一。删除时找到访问次数最小的删除。
缺点：维护每个记录的访问次数，对内存消耗很高。某个数据历史访问次数奇高，但在之后几乎不被使用，这样就迟迟无法删除。
LRU Least Recently Used 最近最少使用
淘汰缓存中最近最少使用的记录
思想：如果数据最近被访问过，将来被访问的概率会更高
实现：维护一个队列，如果记录被访问，将其移动到队尾。那么队首即是最近最少访问的记录，淘汰该记录即可。
缺点：相对比较平衡
综上所述我们采用LRU算法来淘汰数据
使用双向链表+字典实现，读取和插入以及移动和删除复杂度都是O(1)
具体实现简述
1、创建一个结构体 Cache
包含缓存最大长度、缓存当前长度、双向链表、map、以及回调函数
2、实现结构体方法
2.1、new方法 实例化一个Cache
2.2、查询方法 通过key从Cache中查找记录
2.3、淘汰方法 当Cache空间满了后淘汰最近最少使用的记录
2.4、插入方法 通过key和Value将记录插入
到此我们已经实现了一个带有LRU淘汰算法的缓存系统了。
但是目前的缓存并不支持并发访问，所以我们需要使用互斥锁来封装下这个Cache，使其支持并发访问。
2、缓存支持并发读取
使用mutex来实现并发缓存
2.1、创建一个ByteView数据结构
2.2、创建一个cache结构体，包含了一个mutex互斥锁、上述实现的lru以及缓存大小
2.3、自定义数据来源
2.4、创建一个group和group池。负责与用户的交互，并且控制缓存值存储和获取的流程。group如果没有数据，则从自定义的数据来源中获取数据
3、分布式节点通信 客户端和服务端
分布式节点通信分为客户端和服务端，这个就不细说了
4、使用一致性哈希解决分布式负载均衡问题
什么是一致性哈希
一种用来解决分布式系统中分布和负载均衡问题的算法。
为什么要使用一致性哈希
解决单机服务器容量限制问题，保证某些服务器宕机时数据不丢失
在新增或删除节点时，仅需要修改部分数据，减少数据迁移量。
一致性哈希工作原理
一致性哈希算法将key有映射到2^32的环空间中
计算节点的哈希值，放置在环上。
计算key的哈希值，放置在环上，顺时针找到第一个节点，就是应该选取的节点。
如果服务器节点过少，容易引起数据倾斜，数据分布不均匀。
因此引入了虚拟节点的概念。
一个真实节点对应多个虚拟节点。
只需要新增一个map维护真实节点和虚拟节点的映射关系即可。
实现过程
创建一个结构体，包含hash函数、真实节点对应虚拟节点数量、存放所有虚拟节点的hash环、以及真实节点和虚拟节点的映射表
创建一个New方法，传入真实节点对应的虚拟节点数量和hash函数，返回一个Map实例
实现给map添加真实节点的函数Add
功能如下
对于每个真实节点，创建replicas个虚拟节点，遍历replicas，将索引和真实节点key一起hash得到虚拟节点的hash值，将其加入hash环中和映射表中。给hash环重排序
实现给key查找真实节点的函数Get
功能如下
如果hash环为空，返回空
获取key的hash值，顺时针找到环上的虚拟节点索引，然后通过映射表获取真实节点。
除了上述功能外，大佬的博客还实现了两个功能
1、缓存击穿预防
2、使用protobuf实现通信优化
1、缓存击穿预防
什么是缓存雪崩？
缓存在同一个时刻全部失效，导致瞬时DB请求量大。
通常是因为缓存服务器宕机、缓存key设置相同过期时间。
什么是缓存击穿？
一个存在的key，在缓存过期的时刻，同时有大量请求，这些请求会击穿缓存到达DB。
什么是缓存穿透？
查询不存在的数据，但是缓存没有该数据，每次都会请求DB。可能导致DB宕机
创建一个call和group结构体
call表示一个调用请求
group则表示当前所有的调用请求，用一个map存储call
实现do方法，do方法主要实现并发call调用
func (g *Group) Do(key string, fn func() (interface{}, error)) (interface{}, error)
先加锁，
如果m为初始化，先初始化m
判断如果目前的key已经被请求了，那么就等待。返回请求后的数据
否则创建一个新的调用，发起请求，请求结束后从map中删除并返回。
2、使用protobuf实现通信优化
这个也不细说了。
总结
个人认为该系统可能可以改进的地方
一、数据超时机制
二、持久化机制
三、数据冗余，一旦某个节点挂掉，因为没有持久化，也没有数据冗余，所以就没法实现数据恢复。
因此，该系统的使用场景还比较有限。
标签：缓存,hash,浅谈,访问,key,节点,分布式 From： https://www.cnblogs.com/lgh344902118/p/17401068.html