1. 背景

面对海量数据的时候，单个节点存放不下，自然需要将数据切成分片 Partations ，存放到多个节点上（这里的 Partation 在 MongoDB 中被称为 分片(shard), 在 HBase 中称之为 区域(Region)，Bigtable中则是 表块（tablet），Cassandra 中是虚节点（vnode) [1]，Ceph 中则是 Pg）。那么需要面对两个问题：

• 首先如何切分 （Partationing）？通常数据的都可以抽象成 key-value 的模型，那么是 hash 分片，还是按 range 来
• 然后再如何放置（Placement）？如何将这些 Partations 选择合适的节点存放

这两个问题并不是孤立的，而是相辅相成，终构成系统的数据分布，从设计的角度的上需要考虑很多因素：

• 负载均衡：节点磁盘容量，数据访问（read/write）负载等均匀分布
• 可扩展性：能否友好的应对增/删节点，以及日益增长的规模
• 可靠性：数据分片需要多个副本
• 可用性：副本放置需要考虑故障域隔离，保证更好的可用性

这个话题太大，限于水平，今天挑了冰山一角来讨论分析。本文主要描述基于 hash 分片的方式，记录下自己对一致性 hash 和 ceph crush 学习的思考，行文介绍将按照 hash -> 一致性 hash -> ceph crush 的发展脉络来梳理，希望能加深大家对 hash 分片这种数据分布的理解。

2. 一致性 hash

（在接下来的表述中都将以 key-object （key为标识这个object的objId）为模型，并且假定每个objId标识一个 object，每个object都大小相同）

2.1. 简单 hash

在介绍一致性 hash 之前，首先来看看简单 hash 分片，这里以简单的取模（%）为例子： 假设 N 个节点，则 location = hash(objId) % N，这种方式非常简单。优点很明显：

• 非常简单，容易理解
• 通过 random hash，可以将数据均匀的分布在 n 个节点上，有利于消除热点，实现负载均衡

缺点也很明显：

• 扩展性差：一旦增加或者减少节点，之前的数据分布几乎全部需要重新调整，这将造成大量

（1）计算 （2）数据迁移

这里以增加一个节点为例， N 变成了 N+1，所以每一个 key 都位置都需要重新计算一遍 new location = hash(objId)%(N+1)，然后伴随的是海量的 object 位置将发生变化而产生的数据迁移，显然这是不可接受的，因为对于大规模的分布式存储系统来说，宕机和坏盘都是一种常态。

（细心的读者可能发现，挂了节点，数据从哪里恢复，这里可以暂时忽略这个问题，因为数据一般都有多个副本，这是这里为了描述的方便，现在可以假定其能从副本恢复即可，后面会在详细描述）

2.2 一致性 hash

简单 hash 取模，是将数据分布在一条直线上，而一致性 hash 思路很精妙，将 hash 取模的那条直线首尾相连，这样就变成了一个圆，一下子让原本没有关系的首和尾关联起来了。一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数的值空间为 0-2^32-1，整个空间按顺时针方向组织，0和 2^32-1 在零点中方向重合，如下图所示：

上图有4个节点，A、B、C、D根据，4个节点的id值，做hash(id)，然后映射到环上的位置如图，然后，将object的objId都计算一遍hash映射到环上面，每个object会被放置在其hahs(objId)顺时针遇到的节点上，上图中的objId1就会被放置在节点B上面。objId2和objId3会被放置在节点C上面。

然后来看看其如何应对增加节点和减少节点：

• 增加节点

如上图，增加了节点E，那么C上的数据需要重新的计算一遍，其中objId2会迁移到E上，objId3仍然放在C上面，但是A、B、C、D之间的数据并不需要迁移

• 减少节点

如上图，假设节点C down了，那么之前，C上面的数据将全部迁移到D上面，objId2和objId3都需要迁移到D上，但是A和B上面的数并不会产生任何迁移。

优点：

• 可扩展性更好，增/删节点的时候，只会影响自己负责的那部分数据，不会导致整个集群的数据重新分布

缺点：

• 负载均衡很差，（1）数据分布难以均衡：每个节点计算一个hash值，很难保证这些hash均匀的散落在整个hash环上，以一个极端的例子，A，B两个阶段，A的hash值是1，B的hash值是100，那么几乎所有的负载都会落在A；（2）数据迁移难以均衡，以机器减少为例子，节点C因为故障退出集群，那么之前C负责的ojbId2和objId3将都转向给节点D负责，这样会出现节点D负责大量的obj，导致大量的数据迁往D节点，后仍然导致数据分布的不均衡，相当于原先C和D的负载都落在了D上面
• 还是存在一些计算，例如上面增加节点E的情况，C上面的所有object都需要重新确定一遍位置

2.3. 虚拟节点

通过上面的分析会发现，基本的一致性hash，负载不均衡的问题非常严重，那如何解决这个问题呢？计算机的任何问题都可以通过增加一个虚拟层来解决问题[2]，例如操作系统可以看做是硬件的虚拟层，Java虚拟机可以看做是操作系统的虚拟层等等。为了解决负载不均衡的问题，可以将物理节点虚拟为一组虚拟节点，例如一个真实节点对应100百个虚拟节点散落在hash环上，每个object会被放置在其hash(objId)顺时针遇到的虚拟节点对应的物理节点，这样一下子可以让负载均衡起来：

• 每个物理节点对应100个虚拟节点，这些虚拟节点的hash由于数量比较多，根据hash的原理，其更能均衡的散落在hash环上，从而让每个物理节点上的数据分布也就更加均衡了
• 数据的迁移也会更加的均衡，因为一个物理节点对应100个虚拟节点，那么其每个虚拟节点相邻的物理机节点的虚拟节点也将变多，以减少一个物理节点为例，这样这个节点的数据就可能迁移到多个物理机节点上面了。

通过增加虚拟节点，不仅保留了可扩展性，也就是增/删节点的时候，只会影响自己负责的那部分数据，不会导致整个集群的数据重新分布；而且使得数据分布和迁移都更加均衡。但是其仍然存在一定的计算：新增节点，新的虚拟节点插入hash环中，那么受影响的虚拟节点上的数据需要全部遍历一遍，重新的计算hash值，然后决定是否需要迁移。

2.4. 固化虚拟节点

固化虚拟节点[3]，就是虚节点个数在集群的整个生命周期中是不会变化的。也就是系统虚拟节点数是不会变的，每个object和虚拟节点的映射关系不会发生变化，无论是增加，还是减少物理节点，只需要改变虚拟节点和物理节点之间的映射关系就可以了。当物理节点和虚拟节点的映射关系改变之后，只需要迁移虚拟节点即可，相比成万亿级的obj来说，虚拟节点的数目相对少很多，从此不会因为数据迁移而产生大量的计算。

需要注意的是需要预设合理的虚拟节点数，类似于ceph中PG的规模。需要根据集群的规模来预先设定合理的Pg数量，也就是虚拟节点的数量。因为一方面，每个物理节点对应的虚拟节点如果越少，那么均衡性就越难保证，例如集群刚开始每个物理节点100个虚拟节点，随着集群规模变大，每个物理节点只有10个虚拟节点了，那么均衡性自然难以保证。实际上，在生产环境中，扩容都是以pool为单位扩容，而不会无限制的在原pool扩容，所以这个问题一般都不会有。

但仍有一个问题：物理节点和虚拟节点如何映射的问题，拍下脑袋：假定100个物理节点，10000个虚拟节点，那么刚开始，随机给每个物理节点分配100个虚拟节点就好了；那么如何处理宕机和扩容呢 ？

减少节点

• 容易处理，相应的物理节点的虚拟节点，迁移到其相邻的虚拟节点的物理节点上

增加节点

• ？？？2.3. 小节中增加物理节点也会增加相应的虚拟节点，但是现在虚拟节点是固定的，不能增加虚拟节点。如何才能继续做到迁移数据小化呢？（也就是仅仅会有数据迁往新增节点，而原先节点之间不会产生数据相互迁移）

3. Crush

ceph是一个基于分布式对象存储的分布式存储系统，其object数据放置使用的是crush算法，crush在一致性hash算法的基础上，充分考虑了多副本，故障域隔离等约束（类似的解决方案还可以参考[3]）；其中crush的pg，就是一致性hash算法中的虚拟节点，且采用的是固化虚拟节点的方法，所以一个object数据的位置确认就可以分两步来完成：

（1）确认object所在的pg（虚拟节点）

pg id = hash(objId) % PG总数

（2）pg（虚拟节点）和物理节点的映射

这就是crush解决的问题，crush(pg id) = (osd1,osd2,osd3)，由于每个pg会有三个副本，所以crush(pg id)的输出是pg三个副本的位置，分别对应的三个osd，每个osd对应一块磁盘。

这里并不打算详细的介绍crush的算法细节，仅仅介绍crush是如何2.4.小节遗留的问题：如何实现物理节点和虚拟节点映射，才能保证数据迁移的小化？（关于crush副本放置，故障域隔离等，详细的内容可以参考[3]）

为了便于介绍，首先将问题简化一下：

N个OSD，每个OSD有一个weight，wi表示，osdi的weight值，PG如何选择一个OSD放置？

其处理过程如下：

• 每个osd，带入osd id和pg id crush_hash(osd id, pg id) 计算得到一个随机值r，ri 表示osdi计算得到的随机值r
• 用公式ri * wi 计算出osdi的straw值，strawi表示osdi的straw值
• 然后取straw值大的osd放置pg

如何保证pg分布均衡？

因为随机值ri可以通过一定算法生成保证其随机，那么随着样本数的增多，strawi大的比例也将是wi/sum(wi)，终将保证所有PG分布在OSD上面数量也是按照wi的比例来的。

• 增加节点 ？

考虑如下情况：

OSD1  OSD2   OSD3
 w1    w2     w3

那么上面的PG数量的比例成：w1:w2:w3，如果增加一个osd，假设是OSD4，weight为w4，这个时候，OSD1，OSD2，OSD3之间的关系没有变，所有他们之间没有数据迁移，因为任何一个PG从新计算之后，其strawi值都和以前是一样的，假设之前某个PG计算出来straw值分别为：straw1，straw2，straw3，那么增加osd4之后计算，仍然是straw1，straw2，straw3，因此这个计算值只跟osd id，pg id和weight值有关，而这几个值是不变的，一种情况就是straw4 > max(straw1, straw2, straw3)，这种情况需要将pg数据迁移到osd4上。但由于上面的均衡性分析可知，终osd上面的pg数量会成如下比例：

w1:w2:w3:w4

那么会有w4/(w1+w2+w3+w4)的PG移动到osd4上面。

• 减少节点？

OSD1  OSD2   OSD3
 w1    w2     w3

osd3下线了，那么osd1和osd2的计算出来的straw1和straw2的大小关系并不会变，所以，osd1和osd2之间的数据不会发生迁移，而仅仅只有之前osd3的straw3大的pg，会从straw1和straw2较大的进行选择，从而保证了仅有下线osd3的pg迁移到osd1和osd2。

4. 总结

本文介绍了基于 hash 分片的方式下，数据分布放置一些方法，从一致性 hash 到 ceph crush，限于篇幅，仅仅分析了它们如何解决负载均衡和可扩展性的问题。但此类方法并不完美，其中一个致命的缺陷就是它们赖以生存的前设：hash算法的随机性，以ceph为例，pg按照hash算法的随机性，终osd上的pg数量应该按照osd的weight值比例分布才对，但是现实确比较残酷，pg的分布似乎并不均匀。

Notes

限于作者水平，难免在理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献列表中注明，但仍有可能有疏漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章供于学习交流，转载注明出处

参考文献

[1]. Kleppmann M. Designing Data-Intensive Applications[J]. 2014.

[2]. 李智慧. 大型网站技术架构: 核心原理与案例分析[M]. 电子工业出版社, 2013.

[3]. 深入云存储系统Swift核心组件：Ring实现原理剖析. https://www.cnblogs.com/yuxc/archive/2012/06/22/2558312.html

[4]. Weil S A, Brandt S A, Miller E L, et al. Ceph: A scalable, high-performance distributed file system[C]//Proceedings of the 7th symposium on Operating systems design and implementation. USENIX Association, 2006: 307-320.