客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
一 背景
Swift通过引入Ring来实现对物理节点的管理，包括记录对象与物理存储位置间的映射关系，物理节点的添加和删除等。
针对决定某个对象存储在哪个节点上之类的问题，最常规的做法就是采用Hash算法，如果存储节点的数量固定，普通的Hash算法就能满足要求，但是因为Swift通过增减存储节点来实现无限的可扩展性，存储节点数量可能会发生变动，此时所有对象的Hash值都会改变，这对于部署了极多的Swift来说不太现实。因此Swift采用了一致性Hash算法来构建Ring。
二 一致性Hash
假设有N台存储节点，为使负载均衡，需要把对象均匀地映射到每个节点上，这通常使用Hash算法来实现。
对于普通的Hash算法，首先计算对象的Hash值key，然后再计算key mod N（key对N取模）的结果，得到的结果就是数据存放的节点。
比如，N=2，则值为0,1,2,3,4的key按照取模的结果分别存放在0、1、0、1、0号节点。
如果Hash算法是均匀的，数据就会平均分配在这两个节点上。如果每个数据的访问量比较平均，负载也会平均分配到两个节点上。
当然，这只是理想中的情况。在实际使用中，当数据量和访问量进一步增加，两个节点无法满足需求的时候，需要增加一个节点来满足用户的访问请求。
假设，N增加为3，映射关系变为key mod （N+1），即key mod 3，则值0,1,2,3,4的key按照取模的结果分别存放在0、1、2、0、1号节点，也就是说，上述的Hash值为2、3、4的对象需要重新分配到其它节点。
如果存储节点的数量，以及对象的数量很多时，迁移所带来的代价非常大。
为了解决这一问题，Swift采用了一致性Hash算法，在存储节点的数量发生改变时，尽量少地改变已经存在的对象与节点间的映射关系，从而大大减少需迁移的对象数量。
一致性Hash的过程由如下几个步骤组成：
1 计算每个对象名称的Hash值并将它们均匀分布到一个虚拟空间上去，一般用2^32次幂标识该虚拟空间。
2 假设有2^m个存储节点，那么将虚拟空间均匀分地分成了2^m等份，每一份长度为2^(32-m)
3 假设一个对象名称Hash之后的结果是n，那么该对象对应的存储节点为n/(2^(32-m)),转换为二进制移位操作，就是将Hash之后的二进制结果向右位移（32-m）位。
下图是m=2的情况下，具体映射过程。
一般将虚拟空间用一个环（Ring）表示，这也是为什么Swift用Ring来表示从对象到物理存储位置的映射。
|
请发表评论