基于Raft协议的NoSQL数据库的设计和实现-Partition和StoreServer
在前文中，已经简单介绍了DistKV关于Partition和Store Server的部分内容。而这部分我们主要将我们在CAP方面的妥协。讲述为什么DistKV的一致性强于Redis，性能弱于Redis。
1. 一致性
首先在讲一致性前，先说明我们对比的维度。在通常用户使用kv的增删查改过程中，涉及到同时读，先写后读，先读后写，写后写，在分布式环境下，是否能够保持时序一致。
通常情况下，大部分公司使用的是Redis Sentinel 模式，普通的主从备份，订阅发布的模式由于主节点一旦宕机就会导致不可用这种方式目前基本不作为线上系统的常用模式。因此我们，就拿Redis Sentinel模式与Distkv进行对比。
Redis Sentinel是一个分布式架构，其中包含若干个Sentinel节点和Redis数据节点，每个Sentinel节点会对数据节点和其余Sentinel节点进行监控，当它发现节点不可达时，会对节点做下线标识。如果被标识的是主节点，它还会和其他Sentinel节点进行“协商”，当大多数Sentinel节点都认为主节点不可达时，它们会选举出一个Sentinel节点来完成自动故障转移的工作，同时会将这个变化通知给Redis应用方。整个过程完全是自动的，不需要人工来介入，所以这套方案很有效地解决了Redis的高可用问题。
但是这套模式有个问题就是对于横向扩展的支持，最大的存储量受限于单机最大存储量。Redis3.0的cluster模式解决了这个问题，但是却又带来了新的问题，就是分片的一致性降低。
1.1 数据丢失
那么为什么一致性会降低呢？在Redis的分片中，采用的策略是最基本的主从同步，Redis主从同步都是通过异步的方式去同步。而当主节点收到一些请求而这些请求还未收到从节点的确认时主节点出现宕机，即使流量瞬间切换到了从节点，也会导致数据丢失，造成不一致。
然而对于DistKV来说就没有这种情况，在DistKV中，分片内部采用raft作为一致性协议，下图模拟这种情况下raft的实现：
和Redis不同，当raft集群中，leader收到来自client的请求后，会同步向follower同步日志，而这个过程中，如果失败，可以向client返回写入失败。在同步的过程中，如果主节点宕机，客户端也会直接出错，而不会得到错误提示。
因为在Raft中采用同步日志复制的方式提高一致性，而Redis使用了异步的方式，虽然提升了性能（客户端延迟），但是却降低了数据一致性。
1.2 线性一致性
在讲线性一致性前，可以通过图二来看一个显示情况。
- Referee：更新比赛的最终结果，先 insert 到数据库 leader 副本，然后 Leader 再复制给两个 Follower 副本
- Alice：从 Follower 1 中查到了最新的比赛分数
- Bob：从 Follower 2 中确没查到最新的比赛分数，确显示比赛正在进行
图二展示的情况就是最终一致性，属于一致性要求里面最低的，一致性其实主要是描述了在故障和延迟的情况下副本间的状态协调的问题
图三展示了线性一致性的系统在应对相同场景下的情况。在Redis分布式下，采用的是图二的方式，这种会明显提升性能，但却损失了一致性，而对于DistKV来说，使其符合线性一致性是我们和Redis不同的地方，而这种区别也决定了许多，比如我们可以在DistKV上很轻松的支持事务操作，而对于Redis则需要额外的辅助工作。
2. 多线程模型
在前面我们讲到了DistKV在多线程提升性能方面遇到的问题：
- 对于key的存取会存在竞争
- 线程等待导致延时过高
最终我们采用异步RPC Server + 无锁队列实现高性能线程安全的store。本方案依赖异步rpc server的能力，且整个过程是没有资源竞争的，也就是不需要对MAP的读取加任何锁。
设计n个工作线程，每个工作线程拥有一个与之对应的queue和一个SkipListMap，每个独立的存取线程和内部保存的数据被我们称之为Shard。rpc services会将请求post到不同的queue中，然后worker thread会从queue中fetch request来执行(类似于生产者消费者)。rpc services根据一些策略来决定将request投递到哪个queue中，但不管怎样必须保证，对于同一个key的所有requests，必须投递到同一个queue中,也就是我们保证同一个key的所有requests必须在同一个线程执行，这样就不会有任何的race condition。
当worker thread拿到一个request时，他会解析request并且做对应的执行，执行完之后，需要产生结果给io thread进行返回。