深入理解NoSQL数据库分布式算法及策略

wangfans · 发表于 2013-3-21 13:04

也即，将数据分片并把每个数据分片作为迁移的最小单位，这是基于效率的考虑。很明显分片数会比节点数多，数据分片可以在各节点间平均分布。按照一种简单的协议即可实现无缝数据迁移，这个协议可以在迁移数据分片的时候重定向客户的数据迁出节点和迁入节点。下图描绘了一个Redis Cluster中实现的get(key)逻辑的状态机。

wangfans · 发表于 2013-3-21 13:05

wangfans · 发表于 2013-3-21 13:05

假定每个节点都知道集群拓扑，能够把任意key映射到相应的数据分片，把数据分片映射到节点。如果节点判断被请求的key属于本地分片，就会在本地查找(上图中上面的方框)。假如节点判断请求的key属于另一个节点X，他会发送一个永久重定向命令给客户端(上图中下方的方框)。永久重定向意味着客户端可以缓存分片和节点间的映射关系。

wangfans · 发表于 2013-3-21 13:05

如果分片迁移正在进行，迁出节点和迁入节点会标记相应的分片并且将分片的数据加锁逐条加锁然后开始移动。迁出节点首先会在本地查找key，如果没有找到，重定向客户端到迁入节点，假如key已经迁移完毕的话。这种重定向是一次性的，并且不能被缓存。迁入节点在本地处理重定向，但定期查询在迁移还没完成前被永久重定向。

wangfans · 发表于 2013-3-22 15:46

动态环境中的数据分片和复制
　　我们关注的另一个问题是怎么把记录映射到物理节点。比较直接的方法是用一张表来记录每个范围的key与节点的映射关系，一个范围的key对应到一个节点，或者用key的hash值与节点数取模得到的值作为节点ID。但是hash取模的方法在集群发生更改的情况下就不是很好用，因为增加或者减少节点都会引起集群内的数据彻底重排。导致很难进行复制和故障恢复。

wangfans · 发表于 2013-3-22 15:46

有许多方法在复制和故障恢复的角度进行了增强。最著名的就是一致性hash。网上已经有很多关于一致性hash的介绍了，所以在这里我只提供一个基本介绍，仅仅为了文章内容的完整性。下图描绘了一致性hash的基本原理：

wangfans · 发表于 2013-3-22 15:46

wangfans · 发表于 2013-3-22 15:46

一致性hash从根本上来讲是一个键值映射结构 – 它把键(通常是hash过的)映射到物理节点。键经过hash之后的取值空间是一个有序的定长二进制字符串，很显然每个在此范围内的键都会被映射到图A中A、B、C三个节点中的某一个。

wangfans · 发表于 2013-3-22 15:46

为了副本复制，将取值空间闭合成一个环，沿环顺时针前行直到所有副本都被映射到合适的节点上，如图B所示。换句话说，Y将被定位在节点B上，因为它在B的范围内，第一个副本应该放置在C，第二个副本放置在A，以此类推。

wangfans · 发表于 2013-3-23 11:08

　这种结构的好处体现在增加或减少一个节点的时候，因为它只会引起临接区域的数据重新均衡。如图C所示，节点D的加入只会对数据项X产生影响而对Y无影响。同样，移除节点B(或者B失效)只会影响Y和X的副本，而不会对X自身造成影响。