对象均匀分布到虚拟空间的虚拟节点上，在增加或删除节点时可大大减少需移动的数据量；虚拟空间大小通常采用2的
次幂，便于进行高效的移位操作；然后通过独特的数据结构Ri
g（环）再将虚拟节点映射到实际的物理存储设备上，完成寻址过程。
第2页共14页
fOpe
StackSwift学习笔记
图1一致性哈希环结构衡量一致性哈希的4个指标：平衡性（Bala
ce）：平衡性是指Hash的结果能够尽可能分布均匀，充分利用所有缓存空间。单调性（Mo
oto
icity）：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。分散性（Spread）：分散性定义了分布式环境中，不同终端通过Hash过程将内容映射至缓存上时，因可见缓存不同，Hash结果不一致，相同的内容被映射至不同的缓冲区。负载（Load）：负载是对分散性要求的另一个纬度。既然不同的终端可以将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。Swift使用该算法的主要目的是在改变集群的
ode数量时（增加删除服务器），能够尽可能少地改变已存在key和
ode的映射关系，以满足单调性。考虑到哈希算法在
ode较少的情况下，改变
ode数会带来巨大的数据迁移。为了解决这种情况，一致性哈希引入了“虚拟节点”v
ode，（也称为partitio
）的概念：“虚拟节点”是实际节点在环形空间的复制品，一个实际节点对应了
第3页共14页
fOpe
StackSwift学习笔记
若干个“虚拟节点”“虚拟节点”在哈希空间中以哈希值排列。，总的来说，Swift中存在两种映射关系，对于一个文件，通过哈希算法（MD5）找到对应的虚节点（一对一的映射关系），虚节点再通过映射关系（ri
g文件中二维数组）找到对应的设备（多对多的映射关系），这样就完成了一个文件存储在设备上的映射。
图2对象、虚结点、节点间的映射关系在设置虚结点数的时候，需要对系统预期的规模做充分考虑，假如集群的规模不会超过6000个结点，那么可以将虚结点数设置为结点数的100倍。这样，变动任意一个结点的负载仅影响1的数据项。此时有6百万个v
ode数，使用2bytes来存储结点数065535。基本的内存占用是61062bytes12Mb，对于服务器来说完全可以承受。假设有65536（216）个
ode，有128（27）倍的partitio
数（223，则PARTITION_POWER23）。由于MD5码是r