参考

Distributed PostgreSQL on a Google Spanner Architecture – Storage Layer
带着问题学习分布式系统之数据分片
白话解析 一致性哈希
五分钟看懂一致性哈希算法
分布式系统 - partitioning

1. 前言

分布式存储系统要解决的一大问题就是超大规模数据存储问题（单机存储不下）。分布式系统会将数据切分到多个分片，然后根据分片-机器节点的映射关系，将数据存放在集群的不同节点。切分方式主要有哈希（hash）和范围（range）两种方式。对于任何方式，都需要思考以下几个问题：

• 具体如何划分原始数据集？
• 当原问题的规模变大的时候，能否通过增加节点来动态适应？
• 当某个节点故障的时候，能否将该节点上的任务均衡的分摊到其他节点？
• 对于可修改的数据（比如数据库数据），如果某节点数据量变大，能否以及如何将部分数据迁移到其他负载较小的节点，及达到动态均衡的效果？
• 元数据的管理（即数据与物理节点的对应关系）规模？元数据更新的频率以及复杂度？

为了后面分析不同的数据分片方式，假设有三个物理节点，编号为N0， N1， N2；有以下几条记录（R0~R7，主键为 id）：

　　R0: {id: 95, name: 'aa', tag:'older'}
　　R1: {id: 302, name: 'bb',}
　　R2: {id: 759, name: 'aa',}
　　R3: {id: 607, name: 'dd', age: 18}
　　R4: {id: 904, name: 'ff',}
　　R5: {id: 246, name: 'gg',}
　　R6: {id: 148, name: 'ff',}
　　R7: {id: 533, name: 'kk',}

2. 哈希切分

2.1. 基本思路

如上图，哈希切分对每一条数据的主 key 计算哈希值，然后通过哈希值取余，就可以确定数据位于哪个分片。最简单的映射方式就是node 和 tablet 一一映射，这样就可以决定数据存放在哪个节点了。

优点

• 按照hash方式做数据分片，映射关系非常简单，需要管理的元数据也非常之少，只需要记录节点的数目以及hash方式就行了。
• 通常来说，数据的分布均匀，不存在热点问题。

缺点

• 当加入或者删除一个节点的时候，每个分片的数据都需要移动。
• 对于扫描请求，需要对所有节点进行查询。

2.2. 一致性哈希

为了降低 balance 的代价，提出了一致性哈希。

• 一致性哈希先针对 ip 计算哈希值，然后用哈希值对2^32进行取模；
• 对数据的主键做同样的操作；
• 从数据映射到的位置开始往后查找，将数据保存到找到的第一个节点上。如果超过2^32仍然找不到服务器，就会保存到第一个节点。

将2^32个点想象成一个环，则示意图如下：

一致性哈希实际上已经没有了分片的概念，直接是数据和节点的映射。

当增加或者删除一个节点，只会影响一个节点的数据。以删除节点为例：

一致性哈希可能存在 ip 地址哈希分布不均的情况，此时可以通过增加虚拟节点来解决这个问题。
相对而言，一致性哈希存储的元数据会多一些（也不大），但是可以解决 balance 移动数据很多的问题。

关于一致性哈希分区，多副本的实现可以参考dynamo的方式，在顺时针连续三个节点进行备份。

2.3. 固定分片映射

固定分片映射是另一种方式来处理 balance 处理过多数据的问题。这种方案将分片数固定，通过元数据管理分片到节点的映射。当出现节点增删的时候，只需要调整分片-节点的映射关系即可。
通常而言，4096个分片就可以满足大部分场景，如果还不够用，可以继续增加分片数。

这个方法比一致性映射更好理解，但是分片数是在建库的时候决定的，并在之后不能改变。

2.4. 总结

balance 问题解决后，优缺点总结如下：
优点

• 按照hash方式做数据分片，映射关系非常简单，需要管理的元数据也非常之少，只需要记录节点的数目以及hash方式就行了。
• 通常来说，数据的分布均匀，不容易存在热点问题。

缺点

• 扫描请求不友好，需要对所有节点进行查询。

3. 范围分区

如图，根据主键的 key 有序性，将数据分不到不同的分片，每个分片存放一个范围的数据，且分片间的范围不存在重叠。元数据再管理分片和节点的映射关系。

优点

• 扫描查询友好

缺点

• 分区容易不均，一方面，对于字符串等非数字类型，本身就不好确定上下限（除非业务上能确定上下限），首尾区间就不好确定；另一方面，某一范围的 key 较多也很正常。故需要支持分片分裂，以防止热点。
• 元数据管理更为复杂

4. 汇总对比

分区方式	映射难度	元数据	节点增删	数据动态均衡
基本hash方式	简单	非常简单，几乎不用修改	需要迁移的数据比较多	不支持
consistent hash without virtual node	简单	比较简单，取决于节点规模，几乎不用修改	增删节点的时候只影响hash环上相邻节点，但不能使所有节点都参与数据迁移过程	不支持
consistent hash with virtual node	中等	稍微复杂一些，主要取决于虚拟节点规模，很少修改	需要迁移的数据比较少，且所有节点都能贡献部分数据	若支持（修改虚拟节点与物理节点映射关系）
固定分片哈希分区	较简单	稍微复杂一些，主要是分片-节点映射关系	需要迁移的数据较少	不支持，需要重新搭建新集群，调大分片数
range based	较为复杂	取决于每个块的大小，一般来说规模较大；且修改频率较高	需要迁移的数据比较少，且所有节点都能贡献部分数据	支持，且比较容易