对缓存的理解：第一次请求时将一些耗时操作的结果暂存，以后遇到相同的请求，直接返回暂存的数据。

缓存最简单的形式就是存储在内存中的键值对缓存，但需要考虑以下问题： 1. 内存不够：需要设计一个合理的淘汰策略 2. 并发写入冲突：map这个数据结构不是线程安全的，在并发场景下进行修改操作时需要加锁 3. 单机性能不够：单机资源有限，常需要做水平扩展，利用多台机器的资源并行处理。与水平扩展相对应的是垂直扩展，即通过增加单个节点的计算、存储、带宽等，来提高系统的性能，硬件的成本和性能并非呈线性关系，大部分情况下，分布式系统是一个更优的选择。

设计一个分布式缓存需要考虑的基本问题： 1. 资源控制：键值对如何分配到不同的机器上 2. 淘汰策略 3. 并发访问的问题 4. 分布式节点间的通信 本分布式缓存实现的功能有： 1. 单机缓存和基于HTTP的分布式缓存 2. LRU缓存策略 3. 使用锁机制防止缓存击穿 4. 使用一致性哈希算法选择节点，实现负载均衡

1. LFU：淘汰缓存中访问频率最低的记录。如果数据过去被访问多次，那么将来被访问的频率也更高。命中率比较高，但要维护每个记录的访问次数，内存消耗高。此外，当数据的访问模式变化时需要较长时间适应，比如某个数据历史上访问次数很高，但在某个时间点后几乎不再被访问，但迟迟不被淘汰。

2. LRU：最近最少使用，结合了访问时间和访问频率提出的算法，如果数据最近被访问过那么将来被访问的概率也会更高。采用哈希链表实现，哈希表存储key到key在链表中的位置的映射，链表是双向链表，存储了key和对应的value。使得整个数据结构的插入、删除和查询效率都是O(1)

为了保证存储数据的多样性，存储的key为string类型，但是value则为一个实现了Len()方法的接口，该方法返回该value所占的字节数. 淘汰策略的触发机制是：当新增或者更新键值对时，缓存容量超过了最大可用容量，则触发淘汰策略，删除最近最少使用的键值对，直到当前已用容量小于最大可用容量。

1. 缓存的容量是有限的，所以可以规定缓存最大可用容量
2. 为了避免已有缓存容量超过最大可用容量，所以需要记录缓存当前已用容量
3. 哈希链表，用于存储键值对以及实现LRU淘汰策略
4. 回调函数，可有可无，用于删除记录时执行

为了保障数据的安全性，防止缓存数据被意外修改，设计一个“只读”数据结构表示缓存值，在查询操作时返回该结构。该结构包含一个[]byte数组用于存储缓存值，使得缓存值可以是各种类型。同时实现了一个拷贝函数返回缓存值的一份拷贝，避免意外修改。

同一时间可能有多个进程对单机缓存进行操作，这可能造成冲突，所以需要借助锁机制避免单机并发访问的冲突。采用go的sync.Mutex，互斥锁，在查询、新增或者修改缓存时先加互斥锁，等操作完成后再解锁

单机接收到key之后的处理流程： 1. 检查key是否被缓存，是的话直接返回缓存值 2. 若key不在本地，则从远程节点获取缓存值 3. 若不从远程节点获取，则调用回调函数从数据源获取缓存值并添加到本机缓存 当缓存不存在时，我们会从数据源获取数据并添加到缓存中，但由于数据源种类太多，没办法实现对每种数据源的匹配，而且如何从数据源获取数据是用户可以自己决定的事，所以设计一个回调函数，在缓存不存在时调用这个函数得到源数据。

整个分布式缓存的设计包括内存的缓存结构的设计以及与用户交互的结构。 可以将缓存分为多个部分，每一部分属于一个命名空间，可以认为是缓存某一类型数据的集合。一个命名空间的主要结构包括： 1. 空间名称 2. 缓存未命中时需要执行的回调函数，获取源数据 3. 存储属于该空间的键值对的缓存结构 4. 分布式节点的信息，用于从其他节点获取数据

每个节点需要启动HTTP服务，通过ip:port识别不同的节点，且根据约定好的统一url前缀来进行通信，因为一个主机上可能承载着其他服务。开启HTTP服务需要借助net/http并实现核心的ServeHTTP方法。

节点间通信的url格式为/basePath/groupName/key，由于传输的数据类型不确定，所以请求头要设置为“application/octet-stream”，表示传输的是二进制流数据

每个节点也需要实现通信的HTTP客户端，用户向其他节点获取数据，这需要构造使用GET方法的http请求，包括构造url和其中的参数（group和key）。构造url需要注意，url中的字符是明文发送的，但有些字符不能明文正确发送，需要转义。

节点间通信使用HTTP，节点与用户通信也使用HTTP，所以一个节点要开启两个HTTP服务，一个用于启动缓存服务器且进行节点间通信，一个用于给用户提供访问缓存服务器的接口。每个缓存服务器都维护了一个哈希环，所以整个分布式系统节点的添加只能添加一次，且需要在一开始让所有缓存服务器的哈希环保持一致。而后面无法再新增节点。若要新增节点，需要有一个主节点来维护所有缓存服务器的哈希环。

为什么使用一致性哈希： 1. 使键值对均衡分配到所有节点上 2. 防止了简单求哈希值再取模的存储方式不适用于节点数量变化的场景，可能会导致缓存雪崩。

算法原理：一致性哈希算法是一个2^32的环形空间 - 计算节点（通常使用节点名称、编号和ip地址）的哈希值，放置到环上 - 计算key的哈希值，按顺时针方向寻找key在环上的第一个节点，将key-value存储在该节点 使用一致性哈希算法，在新增/删除节点时只需要重新定位该节点附近的一小部分数据，而不需要重新定位所有的节点。

数据倾斜问题：如果服务器节点过少，可能会引起key的倾斜，导致缓存节点负载不均。为了解决这个问题，引入虚拟节点的概念，一个真实节点对应到多个虚拟节点，哈希环上放置的是虚拟节点，保存虚拟节点到真实节点的映射。使用虚拟节点，扩充了总节点数量，是一种代价比较小的方案。

主体结构： 1. 表示哈希环的数组，其中的哈希值必须是有序的 2. 真实节点的虚拟节点数量 3. 虚拟节点到真实节点的映射 4. 计算哈希值的算法

需要实现添加节点和获取key所在节点两个方法： 1. 添加节点：计算哈希值放入数组，最后对数组排序 2. 获取key所在节点，计算key的哈希值，使用二分查找查找数组中第一个大于key的哈希值的值，再映射到真实节点得到key的存储位置

type consistent struct { nodes []int // 存储节点的哈希值 v2t map[string]string // 虚拟节点到真实节点的映射表 hash func([]byte) uint32 replicas int // 真实节点对应的虚拟节点数量 }

分布式缓存的目的是水平扩展，不同的key缓存在不同的节点上，增加总负载以及单位时间内成功传输数据的数量。若每个节点缓存1G数据，理论上10个节点可以缓存10G数据。所以当与用户交互的节点没有用户要查询的key时，该节点需要从远程节点获取，但获取后不会缓存到本地节点，因为这样会造成数据冗余，就失去了水平扩展的意义。

当同一时间有大量对同一个key的查询请求到达某个节点时，可能会造成缓存击穿。缓存击穿指的是一个存在的key在缓存过期的一刻同时有大量请求到达，这些请求都会涌入到数据库查询，造成瞬时数据库请求量骤增。

为了防止这种现象发生，可以通过锁机制将同一时间的大量请求归为一个请求，其他请求只需要取第一个请求获得的缓存结果就好 用一个结构表示一个请求，用一个map存储key到请求的映射。多个请求对应多个协程，采用sync.WaitGroup实现协程同步，key映射到第一个到达的请求，其他请求获取该请求的结果，只有第一个到达的请求执行获取缓存值的函数，这个函数的功能是向远程节点查询key，若查不到则执行回调函数获取缓存值。sync.Mutex用于保障对map的操作的安全性

1. 每个节点都维护一个整个系统的哈希环，整个系统启动时确定哈希环的总节点数后不能再更改，无法动态添加节点
2. 没有设计节点失效或者移除后key的重新存储策略

用户不能感受到分布式节点的存在，所以对用户来说整个缓存的主体结构是Group，表示不同的缓存空间，整个缓存系统可以由多个缓存空间组成。而key不是基于缓存空间存储的，而是基于一致性哈希算法，计算哈希值存储的，所以同一个缓存空间的key可能散落在不同的节点上， 因此，用户创建一个缓存空间时，整个分布式系统的所有节点都必须创建相同名称的缓存空间，使得属于该缓存空间的key可以落到该节点上。

每个节点需要启动两种HTTP服务，一种是与用户交互的API服务，一种是与其他节点通信的服务。

由于同一个Group的key可能分布在不同的节点上，因此，一个Group必须有以下功能： 1. 查询本地缓存 2. 从远程节点获取缓存值 3. 执行回调函数获取源数据

一个节点要从远程节点获取缓存值，需要先计算key的哈希值然后从哈希环上选择要访问的远程节点，因此每个节点都要有整个系统的哈希环信息，且每个节点的信息都应该是一致的。由于在系统启动时节点数就已经确定，不能再增加，所以可以确保这一点。

设置一个主节点，维护整个分布式系统，不存储数据。 1. 维护整个系统的哈希环，节点的添加和删除都通过主节点进行，实现动态添加节点以及节点删除后key的转移 2. 提供与用户交互的API 3. 所有缓存服务器均由主节点启动

添加键值对的过期时间