分片和一致性

架构之路问题集锦

最近整理总结了分布式常用数据结构和算法，特此记录下常用的分布式分片算法和一致性问题。

数据分片与路由

哈希分片(Hash Partition)

一种数据分片和路由的通用模型，可以将其看作是一个二级映射关系。第一级映射是key-partition映射，其将数据记录映射到数据分片空间，这往往是多对一的映射关系，即一个数据分片包含多条记录数据；第二级映射是partition-machine映射，其将数据分片映射到物理机中，这一般也是多对一映射关系，即一台物理机容纳多个数据分片。

  • Round Robin
    • 哈希取模法。H(key) = hash(key) mod K，如果物理机增加1台，则数据和物理机之间的映射关系全被打乱。
    • 该方法缺乏扩展灵活性，原因是该方法将物理机和数据分片两个功能点合二为一，即每台物理机对应一个数据分片，这样key-paitition映射和partition-machine映射也就两位一体。
  • 虚拟桶(Virtual Buckets)
    • 所有记录先通过哈希函数映射到对应的虚拟桶，记录和虚拟桶是多对一的映射关系，即一个虚拟桶包含多条记录信息；第二层映射是虚拟桶和物理机之间的映射关系，同样也是多对一映射，一个物理机可以容纳多个虚拟桶，其具体实现是通过查表实现。
    • 当加入新机器，将某些虚拟桶从原来分配的机器重新分配给新机器，只需修改partition-machine映射表中受影响的个别条目就能实现扩展。
  • 一致性哈希(Consistent Hashing)
    • 将哈希数值空间按照大小组成一个首尾相接的环状序列。对于每台机器，可以根据其ip和端口号经过哈希函数映射到哈希数值空间内，这样不同的机器就成了环状序列中的不同节点，而这台机器则负责存储落在一段有序哈希空间内的数据。
    • 路由问题：沿着有向环顺序查找，效率低；为加快查找速度，可以在每个机器节点配置路由表。

数据一致性

1. 基本原则

  • CAP
    • 强一致性(Consisitency)：分布式系统中同一数据多副本情形下，对于数据的更新操作体现出的效果与只有单份数据是一样的
    • 可用性(Availability)：客户端在任何时刻对大规模数据系统的读/写操作都应该保证在限定延时内完成
    • 分区容忍性(Partition Tolerance)：分区间的机器无法进行网络通信的情况
  • BASE原则
    • 基本可用(Basically Available)：大多数情况下系统可用，允许偶尔的失败
    • 软状态或柔性状态(Soft State)：指数据状态不要求在任何时刻都完全保持同步
    • 最终一致性(Eventual Consistency)：一种弱一致性，不要求任意时刻数据保持一致同步，但是要求在给定时间窗口内数据会达到一致状态

2. 副本更新策略

  • 同时更新
    • 多副本同时更新
  • 主从式更新
    • 对数据的更新操作首先提交到主副本，再由主副本通知从副本更新
  • 任意节点更新
    • 数据更新请求可能发给多副本中任意一个节点，再由这个节点来负责通知其他副本进行更新

3. 一致性协议

  • 两阶段提交(Tow-Phrase Commit, 2PC) - 表决阶段 - 提交阶段 - 如果协调者崩溃，则参与者会存在长时间阻塞的可能
  • 三阶段提交 - 将2PC的提交阶段再次分为两个阶段：预提交阶段和提交阶段，用于解决2PC长时间阻塞的问题。 - 实际使用很少，一方面是2PC发生阻塞情况很少；另一方面是3PC效率过低。
  • Paxos和Raft一致性协议。

参考链接

分享到