云存储硬核技术内幕——(18) 温泉关三百勇士大败波斯(上)

在上期，我们提到了，OpenStack Swift是分布式对象存储的代表。

Openstack Swift的架构如下图：

实际上，我们很容易看出，Proxy Server只是一个接收http请求的Web前端，最终它还是需要解决分布式存储的三大灵魂拷问：

1、怎么样确定数据存到哪个节点和节点上哪块磁盘；

2、当某块磁盘损坏或某节点离线的时候，去哪里重建这块磁盘上存储的数据的副本；

3、集群扩容的时候，把哪些数据搬到新加入集群的节点；

比较聪明的同学，从Swift的这个ring上，似乎看出了答案……

是的，Swift会维护一个ring(环)，并且在这个ring的数据结构上解决这三大灵魂拷问的答案。

既然我们要解决灵魂拷问的问题，就让我们将眼光转到以人灵魂为本的古希腊时代……

在遥远的古代，古希腊城邦斯巴达面临波斯军队的入侵。列奥尼达率领三百勇士决心固守温泉关，捍卫希腊民主的荣光。

列奥尼达为了战术的需要，给300勇士每个人发放了一个10000以内的随机数号码，并且编为3个分队。这样的分组工作也很容易，每个人将自己的号码除以3取余数，按余数分组就行了，如下图所示：

激战过后，300勇士中有50人为捍卫家园，献出了宝贵的生命，又有200名勇士加入了队伍，使得参加城邦保卫战的队伍壮大到了450人。

列奥尼达觉得，队伍壮大了，应当分为更多的团队，便于管理，他决定将450人分为5个小组。

那么，是不是只要大家按自己号码除以5取余数分组就可以了呢？

当然，这种做法简单直接，但会造成每个团队中，有多达80%的战友会各奔东西。

大部分勇士们觉得，与战斗中结下深刻情谊的战友们分开，是一件让人痛心的事情，而列奥尼达也认为，拆散原有的团队有可能对战斗的配合造成不利的影响。

因此，列奥尼达决定重新构建一种分组算法，并整编队伍，无论战术需要将勇士们分为几队，都尽量不拆散原有的战斗组合；同时，有新的勇士加入队伍时，也能尽量平均加入到各团队。

列奥尼达首先重新为每个勇士分配了一个号码，这个号码从原来的五位数改为了一个64位无符号长整数(unsigned int64)。然后，大家取余数的模改为2的32次方。

列奥尼达画了一个圆，圆上有2的32次方个点，每个勇士根据自己的余数找到自己该去的点。然后，列奥尼达在圆上进行五等分：

在圆上A-B之间的，进入A队；

B-C之间的，进入B队；

……

E-A之间的，进入E队；

这样，5个队就分好了。

需要将5个队拆分为6个的时候，只需要在E和A之间再插入一个F：

这样，是不是不影响A，B，C，D四个队的勇士分配？

看起来很好。但……

我们发现，E队被拆分为两个队以后，每个队只有原来一半人数。而且，即使有新的勇士补充入队，落在新的两个队的概率，也是落在其他队的一半。

这在分布式系统的负载均衡中，叫做冷热不均问题。

怎么解决这个问题呢？

请看下回分解。

PS：虽然某迷妹向方老师指出《剑桥插图古希腊史》里边说温泉关三百勇士是150对gay，但此观点太不瑞雪，并且有造成公共卫生危机的风险，因此不予采纳。