沙龙晃荡 | 3月31日 京东、微博拭魅战专家与你合营商量容器技巧实践！

OStorage的老大年夜李明宇顺手发了一个同伙圈，是该公司企业级对象存储产品OStorage-EOS的监控界面截图，感慨一个200多TB的集群很快被用户用到了92%以上。

那么OStorage-EOS分布式对象存储是若何让数据平均分布到各个盘上的呢？本来是应用了一个算法叫做“一致性哈希（Consistent Hashing）”，并且在一致性哈希基本上做了改进，增长了权重、副本、机柜感知、地区感知等机制。

一致性哈希算法也是分布式舷?范畴的经典算法，在很多处所都有应用，下面，我们就一路来懂得一下它：

哈希函数

细心研究一致性哈希之前，我们先来懂得一下根本的哈希，举个例子说清楚明了我们若何应用哈希函数来肯定对象存储在哪里。

先看一个定位数据相对简单的办法，应用MD5算法来获得对象的逻辑地位的哈希值，然后除以可用的磁盘数量，获得余数。最后将余数值映射到驱动器ID。

例如，对象的存储地位为 /accountA/container1/objectX ，并且应用四个磁盘来存储数据，我们称之为磁盘0稻磁逄3。这里我们先计算MD5值:

md5 -s /accountA/container1/objectX    
MD5 ("/account/container/object") =  
f9db0f833f1545be2e40f387d6c271de 

然后我们用哈希值（十六进制数值）除以磁盘数，取余数（取模）。以上十六进制数值转化为十进制为：

“外行看热烈，内行看门道”，一位做分布式存储的同仁看到了说：接近93%的存储应用率，还在一向写数据进去，解释OStorage-EOS数据分布的平均性很好，不然，如不雅数据分布不敷平均，就有可能出现其他的节点或盘还有很多空间，但某一个盘或者某一个节点写满了，这时还持续写数据进去就会出问题。

332115198597019796159838990710599741918

取模函数在大年夜多半编程说话顶用%运算符表示:

332115198597019796159838990710599741918 % 4 = 2

因为余数是2，所以对象将被存储在磁盘2。

这种算法最大年夜的缺点是计算结不雅取决于除数也就是磁盘数量。任何时刻添加或移除某个磁盘(除数变更了)，同一个对象可能获得不合的余数，大年夜而映射到不合的磁盘。为了解释这一点，下面的表显示了当添加磁盘时，哪一个磁盘将成为对象新的存储地位。

留意，几乎每次添加新磁盘，对象都必须移动到新的磁盘上，这仅仅一个对象的情况，将这种行动推广开来，在增长或者移除节点、磁盘时，几乎集群中的所稀有据都须要进行移动。集群将不得不花费大年夜量资本来进行这些迁徙，还将产生沉重的收集负载，以及数据弗成攫取的情况。

一致性哈希算法

昔时夜集群中的增长或者移除磁盘、节点时，一致性哈希（Consistent Hashing）可以削减移动的对象数量。一致性哈希不是将每个值直接映射到一个磁盘，而是经由过程将所有可能的哈希值建模为一个环。一致性哈希算法除了计算对象的哈希以外，还计算设备的哈希，根据磁盘的IP地址、盘符等计算哈希值，每个磁盘被映射到哈希环的某个点上，如图所示。

当一个对象须要被存储时，先计算对象的哈希值，然后定位到环上，如图所示“hash of object”的地位。体系按顺时针搜刮环膳绫擎下一?磁盘的哈希然后定位该磁盘，用这个磁盘存储数据。上图中可以看到，对象将被存储在磁盘4。按照这种算法，哈希环上某个区间的哈希值会被映射到一个磁盘上，如图所示，我们用不合色彩表示不合区间和它们对应的磁盘，若某个对象的哈希值落在蓝色的区间内，则它会被存储在磁盘1上。

应用这种筹划，添加一个盘或者一个节点，只须要移动少量数据，比前面那种最根本的依附计算哈希值并模除来肯定命据存放地位的筹划要好很多，在前面那种筹划中须要移动很多半据。

在实际应用的一致性哈希算法中，每个实际的磁盘或节点会对在环上对应到多个标记，这些标记在一些文献中也被成为“虚节点（Virtual Node）”，实际应用中，一个磁盘会对应很多标记/虚节点，甚至每个磁盘对应数百个标记。多个标记意味着每块磁盘对应环的哈希值范围年腋荷琐大年夜区域切分成了数个小区域。如许做有两个效不雅，一个效不雅是一个新添加的磁盘可能大年夜多个磁盘那边迁徙对象数据，进一步降低了数据迁徙的压力，另一个效不蚜?鲕体的数据分布加倍的平均。

　　推荐阅读

　　2018 年，我们该如何使用 JavaScript？

毫无疑问，我们的 JavaScript 将在 2018 年快速成长。作为法度榜样员，我们爱好编写和应用那些让我们的生活更轻松的对象。不幸的是，这有时会导致更多的纷乱和太多的选择。值得光荣的是，敕令行对象正在>>>详细阅读

本文标题：一致性哈希算法及其在分布式存储中的应用

地址：http://www.17bianji.com/lsqh/40642.html

 1/2    1