这是我关于去重Cache的一些思考，不一定正确。当然，目前的824代码框架中，并不需要考虑缓存的大小问题，而在实际生产环境中，缓存应该伴随着客户端的session失效而一起删除。 我们知道，在6.824中，为了向用户保障exactly-once语义，最直观的方法是，客户端实现超时重试机制，而Kvserver这边需要在应用层对请求进行去重（raft层不建议参与和考虑语义去重的问题，因为raft层只负责同步，它不需要关心上层的消息内容和业务去重，它只需要关心消息在raft层的log index，保障没有乱序和重复index提交）。 因此，kvserver的应用层需要维护一个用于去重的缓存，当收到来自client的请求时/从raft层拿到一条命令执行时，需要先查询缓存中是否已存在该命令的执行结果。如果缓存命中，则不执行，避免了命令被重复执行多次。并且，该缓存是kvserver状态机的一部分，需要参与进snapshot的持久化保存和shard数据迁移。 同时，该缓存的空间不能无限增长，需要及时的裁剪，因此需要为该缓存涉及淘汰算法控制空间大小。 目前缓存淘汰算法主流有三种;
- FIFO先进先出淘汰
- LFU最近最少使用淘汰，淘汰掉最近访问频率最低的内存块
- LRU最近最旧久未访问淘汰，淘汰掉最近最久未访问的内存块
在6.824中，显然LRU比较符合业务场景，因此我在6.824中实现了基于LRU的cache模块，并用于kvserver应用层的去重。 经典的LRU算法为了实现O(1)的查询和修改，需要两个数据结构辅助：hashmap和双向链表。 在Go中，map类型和container/list包分别可以扮演这两个部分。map负责key到value的直接映射，双向链表将value node按照访问时间链接起来。
- 对于Put/Append，缓存结果，使用单独的LRU淘汰，或者不参与淘汰（或者定期淘汰）。
- 对于Get，缓存结果，使用单独的LRU淘汰，且不参与shard迁移。
- 分段锁
LRU优化思路https://zhuanlan.zhihu.com/p/92159352
在把cache模块引入824之前，考虑几个问题：
- 824中，对于所有的命令类型，我们都需要缓存其执行结果吗？
- 824中，对于所有的命令类型，我们都需要使用LRU cache吗？
- 如果实现了readindex和follower read，对于Get命令的缓存是否还有必要？如果有，是否需要对Get缓存实现集群内的共识同步？
这两个问题可以一起回答，如果单个客户端只能串行发出请求，不支持并发请求（即在6.824的测试下，client在发出下一次请求前，必须等到上一次请求的回复。），那么在kvserver的应用层只需缓存每个client最近的一条命令的执行结果即可。这样完全不需要专门写LRU实现淘汰。 同时，824中只有三种命令类型：Put/Append和Get。对于任何命令，只要其被raft层经过共识push上来，就一定是需要被状态机按序应用到状态机的。在状态机的apply阶段，拿到一条Put/Append，其执行结果只有应用成功和未得到应用（中途崩溃）两种情况，没有其他的结果值和业务错误结果需要返回（例如不需要考虑key错误、执行Append有总长度限制等等）。由于是先把命令应用到状态机，再把执行结果写入缓存，然后通知客户端，因此一旦缓存中存在某个Put/Append命令，那么该命令一定是被成功执行了，不存在其他业务错误结果，并且该命令之前的Put/Append也一定被成功执行了。 所以仅就824目前的应用层业务需求上来看，一个取巧的方法是对Put/Append，只缓存最近一条的clientID和requestID，不需要缓存执行结果。对于某个client，一旦接收到其命令的requestID小于已缓存的requestID，直接可以返回执行成功。 另一边，Get命令需要返回结果值和key err这种业务错误，那么就一定需要缓存所有Get的执行结果吗？其实在824中也不一定。如果所有的Get请求都不参与去重，均完整地由leader走一遍Raft层同步（同时也保证了Get不会读出旧值），那么Get请求完全不需要任何缓存，也不需要淘汰缓存。 因此，去重模块简化了成了：
- 对每个Client，只缓存最近执行过的最大requestID，例如
map[clientID]requestID - 当kvserver收到请求调用/从raft层拿到一条命令：
- 如果是Put/Append，则判断其requestID是否大于缓存中的requestID，是则需要push到raft层/应用到状态机，执行后更新缓存；否则说明该命令已成功执行过，直接返回OK。
- 如果是Get，直接push到raft层/从状态机查询
再次强调，以上简化只适用于824目前的简单业务（并且没有实现readindex等读优化——这一点将在第三个问题回答）。 实际上，在正式的生产环境，是需要支持客户端并发请求的，因此需要实现缓存所有命令的执行结果，也需要设计类似LRU的淘汰机制来避免缓存大小的无限制增长。同时，为了避免每次向服务器发出请求时的连接开销，客户端在与服务器交互时，服务器会维护一个session，在缓存时，key需要绑定该session，因此缓存的淘汰需要考虑session的有效期。同时，实际上生产环境还需要考虑事务，实现上更加复杂。具体可参考raft作者的博士大论文。 总结：
- 仅在824的lab内，可以简化缓存去重机制
- 实际生产中需要缓存所有命令的结果并采用合适的淘汰算法以符合复杂的业务生产环境
由于读请求的性能问题(参考读请求的优化)，需要实现readindex和follower read等优化。 在实现readindex后，Get请求仍旧均路由到leader，但是不走raft层。如果不参与缓存，客户端的重试可能会读到更加新的值，导致破坏线性一直读的情况（有待商榷，重试导致的延后读会导致线性不一致吗？）。同时从性能的角度考虑，对Get的执行结果进行缓存加快了重复读请求的响应速度。 因此下面进一步讨论对Get命令执行结果进行缓存的情况：
- 如果不实现follower read，也即所有的请求包括Get都走leader，那么由于raft的强leader特性保证，任何的命令数据流、状态机的改动都是由leader传至整个集群，因此集群所有节点同步执行了所有缓存的更新，拥有相同的缓存副本。
- 而实现follower read后，Put/Append这类写命令由于会修改状态机，因此必须通过leader，再经过raft层同步到所有服务器节点。但读请求被分发给了各follower，没有经过raft层同步，因此每个服务器上收到的Get命令及其缓存结果是不一样的。也即，集群内所有服务器中关于Get命令的缓存是不一致的。因此对于读请求，当某一个服务器崩溃，客户端换另一个服务器进行重试时，永远不可能命中缓存。另一方面，缓存随对应shard迁移时，需要以leader为准开始迁移，因此当发生配置变更时，只有leader上的缓存副本得到了保存和迁移。
那么有人会想，那把关于Get的缓存的改动，由每一个follower广播同步给集群所有节点，这样所有节点不就都拥有了相同的最全的Get缓存吗？这就是第二个子问题，有必要就不一致的Get缓存进行同步吗？ 答案是不需要，完全是本末倒置。第一，它违反了raft的强leader特性，数据从follower流向了其他节点；第二，它加剧了同步的网络开销和实现的复杂度；第三，违反了readindex进行读优化的初衷，导致了更慢的响应性能。 那么看起来，实现follower read后，对于Get命令执行结果的缓存看起来就变成了没有任何意义，即使缓存了也基本上用不到。但是绝对没有意义吗？这与客户端采用的请求重试机制和服务器负载均衡相关。考虑下面的一种方案：
- 一致性hash
- 将客户端分组，对服务器进行序号排序。对于读请求，每一组客户端各固定分配一个不同的服务器节点，并优先将读请求发送给该服务器；如果该服务器不可用/超时，则再向其重试一次，如若仍旧不行，则按序请求下一个服务器。
这样，只要不发生配置变更，某一个客户端在当前配置期间的Get请求会大部分集中在某一个服务器中，因此该服务器拥有其大部分Get缓存，在服务器的应答回复仅丢失一次的情况下，客户端再次选择同一服务器重试，能够命中缓存。 当然，请求应答连续/多次丢失和服务器崩溃的情况仍旧无法利用到服务器上Get命令的缓存。同时，在发生配置变更之后，一切都需要重新累积。 总结：
- 如果不实现follower read，最好对Get进行缓存
- 如果实现了follower read，需要结合客户端重试和负载均衡机制考虑是否缓存，即使进行缓存，也只有极少情况下能命中。也即，图一乐。