/GirafKV

一种高可用最终一致性的分布式键值存储系统

Primary LanguageJava

GirafKV

一种高可用最终一致性的分布式键值存储系统

系统架构

整体架构说明

GirafKV是一个最终一致性的分布式key-value存储系统，采用典型的中心管理主从架构，即Master作为中心控制节点负责协调管理，Primary作为数据存储节点负责数据存取，Slave和Secondary分别作为他们的备份提供可用性保证，Client作为分布式存储系统的接入层接受用户数据流。 在GirafKV分布式系统中，Zookeeper被使用来进行服务注册和发现，心跳监测，主从选举，以及提供分布式锁服务等。

MetaServer

MetaServer包括提供服务的Master和提供容灾容错的Slave。 Master是整个系统中的协调者，负责控制平面，不做任何数据存储工作，主要负责从哪里读写的任务，以及维持节点关系正确性的责任。具体包括以下几个重要的工作：

  1. 节点信息和状态缓存 Master节点需要保存整个集群的全局视图，为了提高性能，这个逻辑拓扑结构缓存在内存中，当zookeeper中相关信息发生变化时，相应修正缓存信息。 Master节点需要监听系统的所有数据节点和运行状态，如节点的上下线等，并对事件作出相应的处理来保证系统状态的正确性。
  2. 客户端请求转发 当客户端发起请求时，第一步会到Master节点获取目标数据节点的位置，Master负责告知客户端下一步请求的地址，然后客户端再向该地址进行数据操作。
  3. 数据分区和可拓展性 为了使得系统的数据分布和资源使用更均衡，Master节点要根据节点信息，动态调整数据分区和请求分发，并协调节点之间的数据迁移等。 Slave则负责监听Master的运行状态，并在Master宕机后，选举出新的Master，并及时提供服务。

DataServer

DataServer包括提供读写服务的Primary节点和提供读服务与备份服务的Secondary节点。主要包括以下要点：

  1. 单机存储方式 对于Key-Value存储系统而言，由于数据对象本身不大，重在提供高性能的增删改查服务，因此采用Map以in-memory的方式存储，所有数据直接驻留在内存中。 当需要持久化时，可以显式将Map对象以特定格式输出到文件中。
  2. 数据恢复和迁移 数据节点除了负责如何存储的问题，还需要承担数据恢复和迁移的任务。当宕机节点重新上线时，应当完成数据的恢复工作；当有新的数据集群上线时，为保证负载均衡，数据节点需要配合Master完成数据迁移的相关工作。
  3. 保证备份一致性 在保证备份一致性上，主从存储节点的角色就有一些区别了。对于Master节点选出的主存储节点，它需要根据主从一致性协议将数据推送到其它从节点。一般来说，采用存储节点分主从的系统都会选择强一致协议，即主节点采用将数据发送给从节点收到响应成功后，才会将数据持久化到本地，返回用户成功，这样用户读到的数据始终是一致的。鉴于这样的系统已经相当普遍，这里我们希望实现一个牺牲部分一致性来保证更高可用性的分布式系统。
  4. 汇报运行状态 对于存储节点需要保持和Zookeeper的心跳信息，将自己的运行状态间接通知到Master节点，以协助Master节点做出决策。从控制系统的角度来说，这才形成了一个负反馈系统。

Client

Client作为分布式存储系统的接入层，接受用户数据流，向Master请求目标数据节点的地址，并向该地址发起数据请求。为了提高系统整体性能和可用性， Client还会负责一些额外的功能：

  1. 集群信息缓存 主要为了减少与Master节点的交互，提高性能。可以从Master节点获取副本位置信息，缓存在本地，设置缓存过期时间。
  2. 异常处理 Client在提高系统可用性上扮演重要的角色，在性能损耗可容忍的情况下，通过简单的重试超时方式即可解决Master、Storage节点不可用的异常，最大限度地保证系统可用性。

读写请求流程

当收到写请求时，Client首先向Master请求数据服务地址，然后向Primary发送写请求。Primary会尝试向其他Secondary进行数据同步，并依据结果执行提交或者回滚的操作。Secondary发现不一致情况时，会向Primary发送CheckLog请求确认状态。 当收到读请求时，Client同样首先向Master请求数据服务地址，不同的是读请求会轮流分发给所有数据节点，以此分散压力，提高负载均衡。

Zookeeper数据结构和服务发现

Zookeeper作为中间协调者，负责元数据节点和存储节点之间的协调统一。

服务注册与发现

MetaServer创建EPHEMERAL类型的临时节点/master，来报告自己服务是否可用。 DataServer创建PERSISTENT类型的永久节点/worker/group，来报告某一个数据集群上线。其中，Primary创建EPHEMERAL类型的临时节点/worker/group/primary报告自己服务是否可用，Secondary创建EPHEMERAL_SEQUENTIAL类型的临时自增节点/worker/group/secondary报告自己服务是否可用。 其他服务通过监控以上数据节点，并获取内部存储的服务地址，来进行配置管理。

主从选举

参与选举的各个节点争抢创建同一个节点，创建成功即为选举成功。 主从选举用于MetaServer竞选区分Master/Slave，DataServer竞选区分Primary/Secondary。

心跳监测

借助临时节点在创建进程结束后自动消失的特性，只需在需要监控的节点上设置监视，即可在目标节点出现异常时捕获消息。

分布式锁服务

需要拿锁的节点在/lock目录下完成拿锁放锁流程。拿锁时，创建EPHEMERAL类型的临时节点/lock/lockname，若创建失败，即没拿到锁，此时使用exists监听该节点事件；放锁时，只需删除该节点，即可完成放锁过程。 分布式锁服务用于数据同步和数据迁移，保障数据的一致性。

基于改进型一致性哈希的Partition

普通哈希算法

该算法通过对对象哈希计算并取模，将对象放置在合适的节点上。 该算法的缺点是，一旦面临添加和删除节点时，模值就会改变。导致之前所有数据的位置都要重新计算。随之而来的就是大量的数据迁移。所以，扩展性差，数据迁移量大。

一致性哈希算法

该算法采用固定模值，通过对对象哈希计算并取模，然后向上取整，将对象放置在合适的节点上。 该算法虽然数据迁移量有所减少，但添加和删除操作，势必会造成物理节点的哈希值不均匀分布，导致节点上数据分布不均匀。此外，数据迁移是在两个节点之间进行，对于正在迁移的节点有较大压力。

改进型一致性哈希算法

改进型一致性哈希算法主要解决对象在节点间分布不均匀的问题，通过引入一层虚拟节点来解决问题。 环上的方格子不再代表一个物理节点，而是一个虚拟节点。虚拟节点和物理节点之间有一张映射表，一个物理节点对应了一个虚拟节点集合。而从对象到虚拟节点之间的映射关系永远不会变，即模值不变。 在上图的例子中，添加一个新的数据集群Group4时，Group1、Group2、Group3都会贡献一部分虚拟节点给Group4，形成Group4：（V9，V10，V11），即数据迁移时，Group1、Group2、Group3都会向Group4写数据。 如果一个对象的哈希值刚好落在V9上，那么该对象会随同虚拟节点整个Slot，一起从 Group1上迁移到Group4上。 按照这样到方式，每个节点拥有的大致相当的虚拟节点数目，数据分布更加平衡。

启发自原子更新技术的Scalability

在改进型一致性哈希算法的基础上，借鉴写时复制（Copy-On-Write）的**，实现了基于原子迁移的可扩展性。其基本思路如下：

数据迁移

当有新的数据集群Group注册后，Master通过Partitioner模块将数据按照改进型一致性哈希算法再分配，然后把迁移信息发送给新数据集群Group中Primary节点。 然后该节点依据这些迁移信息（包括迁移数据源的地址，以及需要向该地址迁移的数据槽），依次向其他数据集群Group发送数据请求，获得相应的数据。此时，这些数据在系统中存在双份。 为保证双份数据的一致性，可以在整个数据集群Group级别上增加一把分布式锁，允许读数据，但不允许新写入数据。 为了进一步提高系统的可用性，可以使用双写技术，即不拒绝写请求，但要求在两个数据集群中同时写入。

重定向

现在，新的数据集群Group中已经拿到它负责的所有数据，即完成了复制过程。接下来，它向Master发送重定向请求，将与自己相关的所有新请求由原来的数据集群重定向到自己，也即原子更新操作。 完成这一步后，系统已经可以正常工作，但为了释放没有意义的空间占用，我们还需要进行下一步。

旧数据清理

Master在完成重定向的工作后，向原数据集群中的Primary节点发送清理数据请求。Primary节点会按照要求清理已经迁移的数据。 之后由Primary节点与Secondary节点之间再进行同步。

数据节点备份的同步协议

主备同步分为两种模式：全量同步和增量同步。当新的备份节点刚上线时，需要先进行全量同步才能提供服务，之后主备节点之间进行增量同步。

全量同步

当新的备份节点上线时，首先在数据集群内部向Primary发起数据全量同步请求，在数据同步完成后，再向Master注册，提供读取服务。 值得注意的是，在Secondary向Primary发起数据同步到Secondary向Master注册期间，如果有新的写请求到来，Secondary将会丢失该数据。 为了确保数据的一致性，在Secondary发起数据同步之前，需要在数据集群Group的粒度上加一把分布式锁，确保期间不会有新的写请求到来，读请求不受影响；在Secondary向Master注册完成后，释放该锁，继续提供正常服务。

增量同步

结合了2PC（Two Phase Commit）、MySQL Binlog和WAL（Write Ahead Log）的**，实现了一种兼具一致性且更加高效的同步方式。 2PC是一种常见的协调统一调度的方式，包括两个阶段， Request 阶段和 Commit 阶段,以此保证多台服务器上的操作要么全部成功，要么全部失败,即All-or-Nothing。但2PC存在许多固有问题：

  1. 同步阻塞。在二阶段提交的执行过程中，所有参与节点都是事务独占状态，当参与者占有公共资源时，那么第三方节点访问公共资源会被阻塞。
  2. 单点故障。一旦协调者发生故障，参与者会一直阻塞下去。
  3. 数据不一致。在第二阶段中，假设协调者发出了事务 Commit 的通知，但是由于发生了局部网络异常或协调者在尚未发完 Commit 通知之前自身发生了崩溃，导致最终只有部分参与者接收到了 Commit 通知，其余的参与者没有收到通知，一直处于阻塞状态，于是整个分布式系统出现了数据不一致性现象。
  4. 太过保守。如果参与者在与协调者通信期间出现故障，协调者只能靠超时机制来判断是否需要中断事务，这个策略比较保守。 而MySQL Binlog和WAL通过记录日志的方式延迟更新，保障了更高的可用性和并发性。

结合以上两者，在2PC中增加写操作的SyncSeq序列，并保留未提交的记录缓存，实现了如下策略：

  1. 所有到达Primary的写请求，都会得到一个原子递增的序号SyncSeq。
  2. 第一阶段，Primary携带SyncSeq向所有Secondary发送尝试写请求，Secondary在收到该请求后会先在本地缓存。
  3. 如果第一阶段所有请求都成功，Primary在本地记录该SyncSeq，并在本地写入该数据，向用户返回成功。否则，跳过该SyncSeq，并向用户返回失败。
  4. 第二阶段，根据上一阶段的结果，Primary携带SyncSeq向所有Secondary发送commit或者rollback，Secondary将按照要求将缓存中的命令提交或者回滚。
  5. 如果第二阶段所有请求都成功，Primary在本地删除该SyncSeq。否则，保留该SyncSeq。
  6. 当Secondary在收到比缓存中的SyncSeq更大的写提交时，会向Primary发起CheckLog，确认之前的命令应该提交还是回滚。

该策略解决了2PC的以下问题：

  1. 因为原子递增的序号SyncSeq保证了各个请求的唯一和先后顺序，可以支持后续多个写操作的并发执行。
  2. 当只有部分Secondary收到commit/rollback通知时，由于可以在随后的操作过程中主动CheckLog，因此不会出现无限等待的问题。

仍然存在的问题包括：

  1. 单点故障的问题。如果Primary中途宕机，会导致Secondary可能没有及时CheckLog，导致数据不一致。可以在Primary重启后按照持久化Log恢复。
  2. 只承诺最终一致性，即不保证所有的写都能被及时看到，但过一段时间后一定会达成一致。

Master容灾

目前，Master在整个系统设计中是唯一的单点，即存在单点故障的问题。为实现一种简单的Master容灾策略，必须保证Master本身是无状态的。这样，在Master突发宕机后，其他Slave节点可以立即启动并提供服务。 在具体实现中，Master所有的注册配置信息均直接来源于Zookeeper，Master本身不进行任何状态的存储。 Slave节点监听Master的存活状态，当Master可用时，Slave不做任何事，简单等待；当Master宕机时，Slave监听到信号并进行选举，选举成功的新Master节点立即更新状态执行；其他竞选失败的Slave继续等待。

并发控制

对于数据同步和数据迁移中分布式锁的使用之前已经讨论过，对于日志也只需简单地增加一个读写锁，这里主要说明数据请求层面的并发控制。 在设计中，使用了Java的内置类型ConcurrentHashMap，它实现了以哈希段为粒度的读写并发控制，与读写锁相比有更高的并发性和可用性。由于所有的键值数据最终只会存留在一个数据集群Group内，且Group仅有Primary一个节点负责写请求，而所有的读写请求最终又都会交由数据节点内的ConcurrentHashMap来完成，因此不需要额外增加其他本地锁。 关于锁的粒度问题，在数据并发请求的情况下，分布式锁（无论系统级别，或者数据集群级别）的粒度都显然太大，因此这种锁的实现方式并不纳入考虑。 此外，由于在增量同步的部分中谈到，所有写请求都会拥有一个原子自增序列，也可以对并发请求的到来维持全局唯一的序列。

负载均衡

系统的负载均衡存在两个层面的均衡：数据分布的负载均衡和请求分发的负载均衡。

  1. 数据分布的负载均衡 基于改进型一致性哈希算法，实现节点动态上线环境下，各节点数据分布的均衡。
  2. 请求分发的负载均衡 Master根据当前数据集群Group中的节点情况，将写请求发给Primary，将读请求轮流分发给Primary和所有的Secondary。

总结

在这个项目中，在考虑可用性的基础上，实现了一个最终一致性的分布式键值存储系统，具备以下主要特色：

  1. 基于改进型一致性哈希的Partition
  2. 启发自原子更新技术的Scalability
  3. 数据节点的全量同步与基于2PC的改进型增量同步
  4. 数据分布与请求分发层面的负载均衡
  5. 以哈希段为粒度的读写并发控制
  6. Master容灾

此外，还包括一些细小的功能，详见前文，这里不做赘述。

设计中的细节问题处理

  1. Client如何知道Master的位置？Master挂了怎么办？ Master使用公开的知名IP和端口。其他Slave监听master，发现问题后在知名端口重启服务。
  2. Master和Worker如何启动？ 有两个大原则：一是先竞选再启动RPC服务（因为RPC需要获取数据集群地址信息），二是先准备好服务再注册Zookeeper（因为注册意味着将被发现，如果服务还没有启动好，会导致异常）。
  3. 如何进行数据迁移？ 一致性保证（原子迁移：先迁移，再重定向，后删除） 可用性保证（分布式锁禁止写/双写，懒加载）。
  4. 数据迁移以多大粒度进行？ 以Slot为粒度进行KV的存储。
  5. 冷启动如何分配数据？ 单独特殊处理，要求直接负责所有slot，不需要问其他人获取数据
  6. rpc通道连接多久？ client与master是长连接，其他连接rpc请求完成后立即关闭
  7. 为什么不采用swift ring的异构备份？ 考虑到写少读多的情况，且同构备份更简单。
  8. 数据是否持久化？ 考虑键值存储的数据量小，实时性要求高，采用in-memory的方式。可选地进行阶段性持久化存储。
  9. 备份节点如何分配？ 每个主节点可以有不同数量的备节点，依照读取的热度来分配。
  10. 主备如何同步？ 一对多同步，异步同步（强一致性的提供由Client保证，转发给主节点；更高的可用性会牺牲一定的一致性） 刚启动时全量同步，之后增量同（两阶段提交+日志序列）
  11. 是否支持缩容？ 暂不支持，假设一个组中的节点不可能同时挂掉，所以该功能不重要。
  12. 为什么不用读写锁？ 在整个数据节点粒度上的大读写锁，导致对并发的支持很差。所以使用原子计数器syncSeq，先快速定位各个操作的顺序，保证顺序一致性。使用ConcurrentHashMap支持以哈希段为粒度的高性能并发读写。
  13. 为什么不直接用2PC？ 因为不能完全保证一致，而且事务独占影响性能。
  14. zookeeper有上次运行的残留znode怎么办？ 启动前先检查清理目录。
  15. master为什么需要尽可能无状态？ 在master宕机后能够简单地由其他slave通过zookeeper重启恢复。
  16. log需要加锁吗？ 需要，读写锁，并发写log会导致异常。

典型错误和解决方式

错误一：遇到端口占用

使用 netstat -aon | findstr 8080 查找到占用端口，例如： TCP 0.0.0.0:8080 0.0.0.0:0 LISTENING 6300 TCP [::]:8080 [::]:0 LISTENING 6300

然后使用 taskkill /f /pid 6300 杀死占用端口的任务。

grpc 编译错误：

Failed to execute goal org.xolstice.maven.plugins:protobuf-maven-plugin:0.6.1:compile (default-cli) on project DistributedKV: protoc did not exit cleanly. Review output for more information.

是中文路径导致的问题，grpc对中文路径的支持并不友好……

参考资料

  1. Redis设计与实现：https://www.kancloud.cn/kancloud/redisbook/63825
  2. gRPC参考文档：https://www.grpc.io/docs/languages/java/quickstart/
  3. Zookeeper参考文档：https://zookeeper.apache.org/doc/current/zookeeperTutorial.html
  4. Zookeeper讲解：https://github.com/llohellohe/llohellohe.github.com/tree/master/readers/ZooKeeper
  5. Zookeeper设计：https://github.com/qiurunze123/zookeeperDesign
  6. 分布式存储知识体系：https://juejin.im/entry/5b0ca8f1518825158309ebec
  7. 分布式存储架构：https://zhuanlan.zhihu.com/p/55964292
  8. 分布式存储架构：https://zhuanlan.zhihu.com/p/27666295
  9. MIT 6.824 动态扩缩容/负载均衡的强一致容灾K/V集群：https://zhuanlan.zhihu.com/p/51049133
  10. Zookeeper服务发现：https://crossoverjie.top/2018/08/27/distributed/distributed-discovery-zk/
  11. 一致性哈希数据划分：https://zhuanlan.zhihu.com/p/37924185
  12. 数据迁移：https://cloud.tencent.com/developer/news/180072
  13. MIT 6.824课程主页：https://pdos.csail.mit.edu/6.824/index.html
  14. MIT 6.824：https://zhuanlan.zhihu.com/p/51049133
  15. 备份同步：https://www.cnblogs.com/glacierh/p/5734200.html
  16. redis主从复制：http://daoluan.net/redis-source-notes/redis-nei-gong-xin-fa/zhu-cong-fu-zhi.html
  17. 2PC: https://juejin.im/post/5ea1234be51d4547106e1d13
  18. 分布式一致性协议：https://matt33.com/2018/07/08/distribute-system-consistency-protocol/
  19. 主从同步：https://blog.csdn.net/tiankong_/article/details/78008736