本文介绍了一致性哈希算法和CRUSH算法，这两种算法都是用于解决分布式系统中的数据存储和管理问题。该算法通过将服务器和数据映射到一个虚拟的圆环上，确保数据被均匀地分布到各个服务器上，同时在服务器增减时，只影响相邻的数据，从而保证了系统的高容错性和可扩展性。为了避免数据倾斜问题，一致性哈希算法还引入了虚拟节点机制，通过计算多个哈希值来分布数据，使得即使在服务节点较少的情况下也能达到均匀的数据分布。
CRUSH算法是Ceph分布式存储系统中用于数据定位的一种算法，它通过伪随机的路由选择来确定数据应该存储在哪些物理节点上。CRUSH算法考虑了存储节点的物理分布，通过精心设计的哈希函数和规则来选择存储节点，从而实现了数据的高效率和可靠性。CRUSH算法的特点包括计算独立性、稳定性和可预测性，但它也存在一些局限性，比如处理权重失衡的困难、数据迁移问题以及可能导致的使用率不均衡。为了解决这些问题，Ceph从Luminous版本起提供了upmap机制，允许手动指定PG的分布位置，以达到更优的数据均衡效果。

0、    背景

假如有一个图片存取服务，为了快速获取图片，使用3台缓存服务器，用简单的Hash映射决定图片存储在哪台缓存上。比如: 

f(x) % 3 = 0 存储在s0上 

f(x) % 3 = 1 存储在s1上 

f(x) % 3 = 2存储在s2上 

某天，缓存负载过高，需要扩容1台，缓存数量由3变为4，那么按获取图片按公式：f(x) % n,很多会请求失败，这样会直接访问后台服务，给后台服务造成很大的压力，可能造成雪崩。是否有这样的算法，解决分布式缓存中，解决简单Hash随缓存服务器伸缩，造成大面积缓存失效的问题

1、    一致性hash

一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题，解决了简单哈希算法在分布式哈希表中存在的动态伸缩等问题。

计算一致性hash时采用如下步骤：

l  首先求出memcached服务器（节点）的哈希值，并将其配置到0～232的圆（continuum）上。

l  然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。

l  然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台memcached服务器上。

从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化而影响缓存的命中率，但Consistent Hashing中，只有在环上增加服务器的地点逆时针方向的第一台服务器上的键会受到影响，如下图所示：

一致性hash算法应该满足以下几个方面：

平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod (P)，在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

分散性(Spread)

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

平滑性(Smoothness)

平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

 

算法原理

一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：

整个空间按顺时针方向组织。0和232-1在零点中方向重合。

下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中四台服务器使用ip地址哈希后在环空间的位置如下：

接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：

根据一致性哈希算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。

下面分析一致性哈希算法的容错性和可扩展性。现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

下面考虑另外一种情况，如果在系统中增加一台服务器Node X，如下图所示：

此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X 。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

另外，一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器，其环分布如下，

此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：

同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

但是其仍然存在一定的计算：新增节点，新的虚拟节点插入hash环中，那么受影响的虚拟节点上的数据需要全部遍历一遍，重新的计算hash值，然后决定是否需要迁移。

固化虚拟节点：

为了解决数据需要移动的问题，其实在两个虚节点中，数据不需要发生真实的移动，虚节点个数在集群的整个生命周期中是不会变化的。也就是系统虚拟节点数是不会变的，每个object和虚拟节点的映射关系不会发生变化，无论是增加，还是减少物理节点，只需要改变虚拟节点和物理节点之间的映射关系就可以了。当物理节点和虚拟节点的映射关系改变之后，只需要迁移虚拟节点即可，相比成万亿级的obj来说，虚拟节点的数目相对少很多，从此不会因为数据迁移而产生大量的计算。减少节点容易处理，相应的物理节点的虚拟节点，迁移到其相邻的虚拟节点的物理节点上。增加节点的时候，浮动虚拟节点增加物理节点也会增加相应的虚拟节点，但是固定虚拟节点以后，不能增加虚拟节点。如何才能继续做到迁移数据最小化呢？（也就是仅仅会有数据迁往新增节点，而原先节点之间不会产生数据相互迁移）

在分布式系统中为了保障可靠性一般都是多副本存储的，在dynamo存储系统中，用一致性hash算法查找到第一个vnode节点后，会顺序的向下找更多vnode节点，用来存储多副本(中间会跳过同台机器上的vnode，以达到隔离故障域的要求)，并且第一个vnode是协调节点。在开源swift对象存储系统中，节点会先分组，比如3个一组，形成一个副本对，然后vnode会分配到某组机器上，一组机器上会有很多的vnode，并且这组机器上的vnode的leader节点在3台机器上会打散，分摊压力。

2、    Swift Rings

Swift采用基于固定虚拟节点的一致性hash模型。但是存在一个问题，以上例子中，1000个虚结点对应着100个结点，结点变动时，虚结点就需要重新分配到结点。当100个结点扩展到1001个结点时，此时至少有一个结点分配不到虚结点，那么就需要再增加虚结点数，而虚结点是与数据项对应的哈希关系，如果改变了虚节点数，那么就需要重新分配所有的数据项，这将导致移动大量的数据。所以在设置虚结点数的时候，需要对系统预期的规模做充分考虑，假如集群的规模不会超过6000个结点，那么可以将虚结点数设置为结点数的100倍。这样，变动任意一个结点的负载仅影响1%的数据项。此时有6百万个vnode数，使用2bytes来存储结点数(0~65535)。基本的内存占用是6*106*2bytes=12Mb，对于服务器来说完全可以承受。

Swift中引入replica的概念使用冗余副本来保证数据的安全。replica的默认值为3，其理论依据主要来源于NWR策略。

NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。每个字母的涵义如下：

N：同一份数据的Replica的份数

W：是更新一个数据对象的时候需要确保成功更新的份数

R：读取一个数据需要读取的Replica的份数

强一致性：R+W>N，以保证对副本的读写操作会产生交集，从而保证可以读取到最新版本；如果 W=N，R=1，则需要全部更新，适合大量读少量写操作场景下的强一致性；如果 R=N，W=1，则只更新一个副本，通过读取全部副本来得到最新版本，适合大量写少量读场景下的强一致性。

弱一致性：R+W<=N，如果读写操作的副本集合不产生交集，就可能会读到脏数据；适合对一致性要求比较低的场景。

在分布式系统中，数据的单点是不允许存在的。即线上正常存在的Replica数量是1的情况是非常危险的，因为一旦这个Replica再次错误，就可能发生数据的永久性错误。假如我们把N设置成为2，那么，只要有一个存储节点发生损坏，就会有单点的存在。所以N必须大于2。N约高，系统的维护和整体成本就越高。工业界通常把N设置为3。

因此，在ring的代码中引入replica，数量设置为3，其中 node_ids记录的是3个replica存放的node id。part2node[part]是根据partition id 找到对应的node id。

3、    Ceph CRUSH算法

在固定虚拟节点模型中，我们因为虚拟节点总量是固定的，我们可以用简单hash解决对象obj到虚拟节点pg的映射，但是为了解决pg到实际物理节点osd的映射问题，ceph提出了CRUSH算法。

crush算法是一个伪随机的路由选择算法，输入pg的id，osdmap等元信息，通过crush根据这个pool配置的crush rule规则的伪随机计算，最终输出存储这个pd的副本的osd列表。由于是伪随机的，只要CRUSH Map、crush rule规则相同，在任意的机器上，针对某个pg id，计算的最终的osd列表都是相同的。

crush算法支持在crush rule上配置故障域，crush会根据故障域的配置，沿着CRUSH Map，搜索出符合条件的osd，然后由这些osd抽签来决定由哪个osd来存储这个pg，crush算法内部核心是这个称为straw2的osd的抽签算法。针对每个pg，符合故障域配置条件的osd来抽检决定谁来存储这个pg，osd抽签也是一个伪随机的过程，谁抽到的签最长，谁赢。并且每个osd的签的长度，都是osd独立伪随机计算的，不依赖于其他osd，这样当增删osd节点时，需要迁移的数据最少。简单来说，可以将这个过程看成一个函数：

CRUSH(id，CRUSH Map，Placement Rules)-----{OSD1，OSD2 ...... OSDi}

输入参数有三个，包括需要映射的PG的id，Cluster Map中的CRUSH Map，即OSD集群拓扑结构和Placement Rules放置策略。输出即一组可用的OSD列表。CRUSH算法即通过一系列精心设计的哈希算法去访问和遍历CRUSH Map，按照用户定义的规则选择OSD。

Pg id由简单hash算法求出，计算公式如下：

       Id = Int（Hash(object_name)%PG_num）。

其中pg_num是用来

下面介绍CRUSH Map和Placement Rules:

1、 CRUSH Map

CRUSH算法与一致性哈希相比，可以感知到存储节点的实际物理分布，其中，ceph的Cluster Map(集群运行图)就是这个关键。Cluster Map包含很多运行图，例如CRUSH Map，OSD Map等。CRUSH Map主要描述各OSD的物理组织和层次结构，OSD Map保存了各OSD设备的运行状态。CRUSH Map的叶子结点表示OSD设备，所有非叶子结点表示bucket。bucket根据层次划分可以定义不同的类型（例如root,host）。

2、 Placement Rules

Placement Rules设定了一个PG的副本如何分布的规则，可以用户自定义，从而实现个性化的数据分布策略。它的步骤分为take，choose，emit三步。具体过程如下：

（1）step take：take选择一个bucket，通常是root类型。

（2）step choose: 这一步是CRUSH算法的核心，执行过程对应最终的分布。

（3）emit:表示选择结束，输出选择的位置。

用户定义的Placement Rules如下：

 

由Placement rules定义和上图Cluster Map可以得出：take步骤选择了一个root类型的bucket；随后choose步骤如下：

首先，从root类型的bucket中选择一个row类型的子桶，选择算法在root的定义中设置，一般为straw算法；接着，从raw中选择3个cabinet，选择算法一般在raw中定义;最后，从每个cabinet中分别选择一个OSD。

根据Placement Rules的规则，选出来的3个OSD设备分布在一个row上的3个cabinet中。

CRUSH算法的特点，一言以蔽之，依赖于Hash实现的纯伪随机算法。具体来说：

 

计算独立性：每次计算完全独立，不依赖于集群分配情况或已选择结果（先计算再判断冲突，而不是将冲突项从备选项中移除）；仅依靠多次重试解决选择失败问题

稳定性：只有OSD的增删或者weight/reweight变化才会影响到计算结果；正常运行时结果不变

可预测性：通过对指定的CRUSH map进行离线计算即可预测出PG的分布情形，且与集群内实际使用完全一致

虽然CRUSH算法为Ceph数据定位提供了有力的技术支持，但也依然存在一些缺陷，如：

假失败：因为计算的独立性CRUSH很难处理权重失衡（weight skew）的情形。例如，假设3个hosts的weight值分别为10，10，1，MAX_TRIES为50，现已经选中了前两个hosts，那么第三个replica有大约(20/21)^50=8.72%的概率选择失败，即使低weight的那个host其实是可用的。因此，在实践中应尽量避免权重失衡的情形出现。

故障额外迁移：解决了OSD状态由in到out的额外迁移，实际环境中还会因为OSD的增删产生一定量的数据额外迁移，对集群造成影响。

使用率不均衡：这也是CRUSH被诟病最多的缺陷，即完全依赖Hash的随机导致集群中OSD的容量使用率出现明显失衡（实践中遇到过差40%以上），造成空间浪费。因此，自Luminous版本起，Ceph提供了被称为upmap的新机制（可以看成记录了一张特例表），用以手动指定PG的分布位置，来达到均衡数据的效果。