一致性哈希算法及其在分布式存储中的应用

OStorage的老板李明宇发布了一个朋友圈，是该公司企业级对象存储产品OStorage-EOS监视界面的屏幕快照. 他认为，超过92 TB的用户迅速使用了200 TB以上的集群.

“外行看活泼，外行看门口”，一位从事分布式存储的同事看到: 接近93％的存储利用率，仍在写入数据，这表明OStorage-EOS数据的一致性分配非常好，否则，如果数据分配不均匀，则可能有其他节点或磁盘有很多空间，但是磁盘或节点已满，然后继续向其中写入数据会引起问题.

那么OStorage-EOS分布式对象存储如何将数据平均分配到每个磁盘？事实证明，使用了一种称为“一致性哈希”的算法，并且在一致性哈希的基础上进行了改进，增加了权重，复制，内阁意识和区域意识等机制.

一致性哈希算法也是分布式系统领域中的经典算法，它在许多地方都有应用. 让我们一起来看一下:

哈希函数

在仔细研究一致的哈希之前，让我们看一下基本哈希. 一个示例说明了如何使用哈希函数来确定对象的存储位置.

首先看一下一种相对简单的数据定位方法. 使用MD5算法获取对象逻辑位置的哈希值，然后除以可用磁盘数即可得到剩余的磁盘数. ***将剩余的值映射到驱动器ID.

例如，对象的存储位置是/ accountA / container1 / objectX，并且使用四个磁盘来存储数据，我们将磁盘0称为磁盘3. 在这里，我们首先计算MD5值:

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

然后，我们将哈希值（十六进制值）除以磁盘数量，然后取余数（模）. 上述十六进制值到十进制的转换是:

332115198597019796159838990710599741918

在大多数编程语言中，模数函数由％运算符表示:

332115198597019796159838990710599741911918％4 = 2

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

此算法***的缺点是计算结果取决于除数，即磁盘数. 每当添加或删除磁盘（除数已更改）时，同一对象可能会获得不同的剩余部分，这些剩余部分映射到不同的磁盘. 为了说明这一点，下表显示了添加磁盘时哪个磁盘将成为对象的新存储位置.

请注意，几乎每次添加新磁盘时，都必须将对象移至新磁盘. 这仅是对象的情况. 此行为是广义的. 添加或删除节点和磁盘时，它几乎在群集中. 所有数据都需要移动. 群集将不得不花费大量资源来执行这些迁移，这还将导致沉重的网络负载，并且数据不可读.

一致哈希算法

在集群中添加或删除磁盘和节点时，一致的哈希可以减少移动的对象数量. 一致性哈希不会将每个值直接映射到磁盘分布式存储算法，而是通过将所有可能的哈希建模为环来进行映射. 除了计算对象的哈希值之外，一致性哈希算法还计算设备的哈希值. 哈希值是根据磁盘的IP地址和驱动器号来计算的. 每个磁盘都映射到哈希环上的某个点，如图所示.

当需要存储对象时，请首先计算对象的哈希值，然后将其定位在环上，如“对象的哈希”位置所示. 系统顺时针搜索环上方的下一个磁盘的哈希，并找到该磁盘，并使用该磁盘存储数据. 如上图所示，对象将存储在磁盘4上. 根据此算法，哈希环上特定间隔的哈希值将映射到磁盘. 如图所示，我们使用不同的颜色表示不同的间隔及其对应的磁盘. 如果对象的哈希值在蓝色范围内，则将其存储在磁盘1中.

使用这样的哈希环，当我们添加新磁盘（例如磁盘5）时，图中的粉红色部分将不再属于磁盘4，因为这部分数据当前属于新磁盘5. 因此，磁盘4上的对象的这一部分将移至磁盘5，其他数据将不受影响.

使用此方案，添加磁盘或节点仅需要少量数据即可移动，这比依赖于计算哈希值并划分数据以确定数据存储位置的最基本方案要好得多. 计划中需要移动很多数据.

在实际的一致性哈希算法中，每个实际的磁盘或节点对应于环上的多个标签. 在某些文献中，这些标签也被称为“虚拟节点”. 在实际应用中，一个磁盘将对应许多标签/虚拟节点，甚至每个磁盘也对应数百个标签. 多个标记表示每个磁盘相应环的哈希值范围从一个大区域分为几个小区域. 这有两个效果. 一个效果是，新添加的磁盘可能会从多个磁盘迁移对象数据，从而进一步减轻了数据迁移的压力，另一个效果是，总体数据分布更加均匀.

以上是一致性哈希的基本原理. OStorage-EOS基于一致的哈希算法实现了数据的均匀分配并对其进行了改进. 它介绍了复制，重量，机柜识别和区域识别等机制，以满足企业级用户的需求.

【编辑选择】

RocksDB数据存储格式分析. 数据泄露后分布式存储算法，企业应及时更改其安全策略以分散数据存储. 您的数据将由您来管理分布式存储中的元数据管理. 借助业界首个大数据管理云，Informatica重组了集成平台即服务

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-185511-1.html