分区

分布式系统实现可扩展性的主要方式之一是对数据进行分区

  • 通过增加节点的方式增加系统的存储规模
  • 增加可用性和可扩展性

分区方式

  • 垂直分区
    • 对表的列进行拆分，减小了列的宽度
    • 每个分区都包含列对应的所有行
  • 水平分区
    • 对表的行进行拆分，减少了记录的条数
    • 每个分区的记录都包含所有的列

水平分区算法

  • 范围分区
    • 根据指定关键字，将数据集拆分成若干连续的范围，每个范围位于一个节点
    • 优势
      • 实现简单，支持使用分区键进行范围查询
    • 缺点
      • 无法使用分区键以外的键进行范围查询
      • 查询范围跨多节点时，性能较差
      • 数据分布不均匀或请求流量不均匀导致数据热点
  • 哈希分区
    • 根据分区键的哈希值决定如何将数据分布在若干节点上
    • 优势
      • 数据分布均匀
    • 缺点
      • 无法进行范围查询
      • 添加和删除节点时，需要重新映射，导致大量的数据迁移
  • 一致性哈希
    • 将节点和数据映射到哈希环，以此确定数据在节点上的分步
    • 为解决节点数过少导致的数据分布倾斜，引入虚拟节点
    • 优势
      • 添加和删除节点时，只有相邻节点上的数据需要迁移
    • 缺点
      • 无法进行范围查询

分区带来的挑战

  • 对于垂直分区，不同表数据的组合操作低效，可能跨越多个节点
  • 对于水平分区，多行范围查询导致到多个节点的读扩散
  • 带来分布式事务问题

复制

为提高可用性，除了分区还需要复制。

复制的好处：

  • 增强数据可用性和安全性
  • 选择临近的副本进行访问，减少时延
  • 多副本提供读写能力，增加吞吐量

常用的复制模型

单主的复制

单主复制也叫主从复制，指定系统中一个节点为主节点（Leader/Master/Primary），其余节点为从节点（Follower/Slave/Backup）。

客户端写请求只能发到主节点，读请求可以发到从节点。从节点从主节点同步数据。

单主复制分为三类：

  • 同步复制
    • 主节点必须等待从节点执行完毕，才回复客户端写入成功
  • 异步复制
    • 主节点执行完请求后，立即向客户端回复，无需等待从节点完成写入
  • 半同步复制
    • 主节点需要等待至少一个从节点执行完成，才回复客户端写入成功。其它从节点进行异步复制。

单主复制的优点：

  • 简单易实现
  • 仅在主节点执行并发操作，能够保证操作的顺序，避免了写入冲突的产生
  • 可以通过增加从节点提升读取性能

单主复制的缺点：

  • 只有一个主节点，写请求有性能瓶颈
  • 可能出现没有主节点或脑裂问题
    • 主节点宕机后，从节点需要一段时间才能提升为主节点
    • 由于网络分区，从节点误认为主节点异常，导致集群中出现两个主节点

多主的复制

单主复制只有一个主节点提供写服务，在性能上存在局限。对于写负载高的系统，增加多个主节点来分担写入负载，随之而来的是写入冲突的问题：

  • 多主复制不止一个节点处理写请求，由于网络存在延迟，节点会对某些请求的正确顺序产生分歧

最好的方式是避免冲突，如特定的请求只发送到特定的节点处理，避免同一份数据在多个节点上更新。

冲突发生时的解决方法：

  • 客户端解决冲突，将冲突的数据返回客户端，由客户端实现冲突解决
  • 最后写入者胜（LWW, Last Writer Win），为每个请求标记唯一时间戳或唯一自增ID，当冲突发生时，使用最新版本的数据。
    • 在分布式系统中，很难实现全局时间顺序
  • 因果关系追踪，使用一种算法判断不同请求之间的因果关系，以此判断请求的先后顺序。
    • 对于无因果关系的并发请求，系统无法做出决定

还有一种称为无冲突复制数据类型（Conflict-Free Replicated Data Type）的数据结构，能够根据一定的规则自动解决冲突，副本之间无需额外的协调和冲突处理。常用于在线聊天系统和协作式文本编辑系统。

多主复制的优点：

  • 增加主节点的容错性，一个主节点故障仍有其它主节点工作
  • 分担写请求压力
  • 选择最近的节点写入，降低写时延

多主复制的缺点：

  • 解决数据冲突带来的系统复杂性

多主复制带来的复杂性远超出它的好处，因此很少在单个数据中心使用多主复制。一般用于多数据中心的存储系统，避免写请求跨越数据中心。

无主的复制

亚马逊的Dynamo架构论文使无主复制技术引起广泛关注，启发了许多NoSQL数据库如Cassandra的实现。无主复制也称Dynamo架构（Dynamo-Style）。

无主复制中，客户端的写请求发送到多个节点。无主复制有两种协调写请求的方式：

  • 客户端直接将写请求发给多个节点
  • 客户端将写请求发送到某个协调节点，由协调节点将写请求发送到多个节点

由于写入多个节点不一定会全部成功，会带来数据不一致，因此读取也要读多个节点，获取各节点上的数据和版本号，根据版本号决定使用哪个值。

除了解决客户端识别旧数据的问题，还需要解决对旧数据的修复问题，Dynamo架构同时使用了两种数据修复方法：

  • 读修复（Read Repair），客户端发现某些节点存在旧数据后，向这些节点发送更新请求
  • 反熵过程（Anti-Entropy Process），通过后台进程找出错误数据并进行修复。反熵过程不保证写操作的数据，只保证最后结果一样。

基于Merkle Tree加速反熵过程

反熵过程可能不是一个个比较数据是否一致，这需要传输很多的数据。Dynamo使用Merkle Tree来验证数据是否产生了不一致，减少了传输的数据量。

  • Merkle Tree也叫哈希树，把数据按关键字分为若干范围，每个范围计算出一个哈希值作为树节点
  • 各节点自底向上合并到根节点
  • Merkle Tree的每个节点都可以独立进行对比，不要求传输完整的树
  • 如果两棵树根节点相同，那么下层节点也相同，就不需要再检查了
  • 如果根节点不同，再继续向下查找导致不同的子节点，直到找到冲突的关键字所在的范围

基于Quorum的数据冗余机制

Quorum法定人数机制是分布式系统中用来保证数据冗余和最终一致性的一种算法。在无主复制中，Quorum机制用来确定到底需要读写多少节点才足够。

Quorun机制要求，在一个N节点的系统中，要求至少W个节点写入成功，至少从R个节点中读取数据，并且满足 W+R>N 且 W>N/2，则读取的R个值中至少包含一个最新值。

  • W>N/2这条规则，主要用于保证数据的串行化修改，两个不同的写请求不能同时成功修改一份数据。

管理员可以根据系统负载配置W和R的值。如果一个系统写请求很少，读请求很多，可以设置W=N,R=1。

  • 当然这个设置会导致写入速度变慢，可用性降低。因为一个节点故障将导致所有写请求失败。