本人从事游戏行业，因此这个缓存系统主要针对网络游戏的数据访问模式设计。
首先分析下网络游戏的数据访问模式：
1）关系性弱：对于绝对大多数的游戏类型来说，能通过一个 key 来访问数据就够了。
2）读多写多：用户登录时通常需要加载大量数据，查询其它玩家信息也是一个频繁的操作请求。在不考虑定时回写的情况下，玩家的每个更新类请求都会产生一次数据库回写请求，对于一个在线 10W, 养成类游戏，每秒写请求达到 10W+ 是可能的。
3）冷数据多：游戏的注册用户数和活跃用户数差距非常大。大量数据平时几乎不被访问，只有偶尔做活动用户回流时才被访问。
4）响应及时性：即使是一个查看其它用户信息的查询请求，响应时间超过 200ms 也是非常不友好的。
基于以上考量，我设计了一套名为 flyfish 的冷热缓存系统，系统设计目标如下：
1）作为数据访问的统一接口：所有数据访问都通过 flyfish，由 flyfish 负责数据的加载，回写以及冷数据淘汰。
2）面向行缓存：最终数据要同步到关系数据库，因此，flyfish 的 value 缓存的是关系数据库中的一行。value 类似 redis 中的 hash，可以单独访问每个 field。
3）高可用与强一致性：通过部署多个副本，在部分节点出现故障时系统依旧可以对外提供强一致的数据服务。
4）动态伸缩：在不中断系统服务的情况下，通过增加 / 移除节点调整系统的负载能力。
5）高吞吐低延迟：对于已缓存数据，单一节点每秒支持 10W+ 的读写能力，平均延迟 50ms 以内。
6）在后端数据库故障的情况下提供受限服务：flyfish 作为数据访问接口，除了要容忍系统本身故障外，还需要容忍后端数据库的故障。在后端数据库出现故障的情况下，需要保证对已缓存的数据继续提供无丢失的读写服务。
7）支持单 key 的 cas 以及原子递增操作。
8）支持版本号以实现悲观事务。
9）分布式事务。
目前 flyfish 的第一个版本尚未实现 pd 及 proxy, 只支持静态分片。所以仅达成了除 4，9 以外的目标。
数据库表格定义
flyfish 作为一个行级缓存，其缓存的 value 对应到数据库表中的一行，因此，flyfish 是有模式的 kv 缓存。flyfish 支持 string，blob，int64，uint64，float64 五种字段类型。
定义表格时，必须定义两个 flyfish 使用的内部字段__key__(string)，以及__version__(int64)，其中__key__需要被设定为主键。
定义表格后，向 table_conf 插入一行以描述表格元数据，例如，有一个 user 表其字段定义如下：
__key__(string),__version__(int64),age(int64),phone(string)
则需要向 table_conf 插入下面行：
table conf
users age:int:0,phone:string:10086
表格元数据规则：
字段 1: 类型: 默认值, 字段 2: 类型: 默认值, 字段 3: 类型: 默认值
kvnode
每一个 kv 对归属于一个 region，每个 region 可以在 1 - N 个 kvnode 节点上保存副本，编号相同的 region 组成一个 raftgroup。在这个 raftgroup 中，通过 raft 协议选举出一个 leader, 由 leader 负责这个 region 上 kv 的访问请求。
kv 访问流程
只读请求
1）客户端使用 unikey(key:table) 向 leader 发起访问请求。
2）如果缓存中没有数据，向 sql 数据库发起加载请求。用数据库加载的结果向所有副本发起添加 kv 的复制请求（如果记录不存在，请求添加一条标记为缺失的 kv），当复制被提交，向本地缓存添加 kv 并返回响应。
3）如果缓存有数据，向所有副本发起 readIndex 请求，请求被提交后返回响应。
更新请求
1）客户端使用 unikey(key:table) 向 leader 发起访问请求。
2）如果缓存中没有数据，向 sql 数据库发起加载请求，加载成功后在原数据的基础上产生修改请求，向所有副本复制请求，复制被提交后修改本地缓存返回响应。将 kv 插入更新队列，执行异步 sql 回写。
3）如果缓存有数据，在原数据的基础上产生修改请求，向所有副本复制请求，复制被提交后修改本地缓存返回响应。将 kv 插入更新队列，执行异步 sql 回写。
从以上处理可以看出，flyfish 保证各副本之间的强一致性，而与 sql 数据库保持最终一致性。因为 flyfish 中缓存的数据可以通过 raft 快照和日志重建，并保证最终一定会回写到 sql 数据库。因此，即使在 sql 数据库出现故障的情况下，对于已缓存的数据依旧可以提供读写服务。
sql 回写的数据安全性
flyfish 采用异步回写策略，并且回写请求是针对一个 kv 而不是每次变更。即，一个 kv 被推入回写队列之后，实际执行回写之前，如果又发生了多次变更，这些变更将会被合并为一次 sql 回写请求。因此，回写的操作频率与 kv 更新的频率无关，只与发生变更的 kv 数量有关。因此不用担心 sql 回写执行太慢而导致回写队列被撑爆。
因为 flyfish 采用异步回写策略，因此存在数据回写覆盖的风险。flyfish 保证只有 leader 可以提供数据访问服务，因此也只有 leader 有权执行 sql 回写。考虑一下场景：
A 是 leader，执行 sql 回写前，因为网络分区，集群选举 B 为 leader, 此时 A 尚未感知到自己已经不是 leader 继续发出 sql 回写请求。
B 此时也收到更新请求，执行回写。如果 A 回写在 B 之后执行，将导致老数据覆盖新数据。
为了避免此类问题的出现，回写必须在获得 lease 的情况下才能执行：
一个节点在成为 leader 之后才能申请 lease,lease 通过 raft 的 proposal 提交，一旦提交成功获得 lease，按约定的时间间隔定期续约。
对于上面描述的场景，B 在成为 leader 后，发现之前的 lease 尚未失效，所以它没有回写权限。必须等到 A 所持有的 lease 到期后才会申请 lease。而对于 A, 因为网络分区，它的续约请求将无法通过，因此当它感知到失去 leader 或 lease 过期之后就会停止执行回写。
回写前节点崩溃导致回写丢失
考虑下面的场景:
leader 在执行回写前崩溃。新的 leader 并不知道相应的 kv 是 dirty 的。这个 kv 长时间没有被访问，最后被 lru 淘汰。此时这个 kv 的数据更新就丢失了。为了避免以上情况，新 leader 在第一次获得 lease 时，需要将所有的 kv 标记为 dirty 并请求执行回写。这样就保证了任何情况下都不会丢失数据更新。
flyfish