数据分片方式脑图

数据分布设计原则
在分布式数据存储系统中,存储方案选型时,通常会考虑数据均匀、数据稳定和节点异构性这三个维度。
数据均匀
每个节点存储的数据相差不太大即可
数据稳定
当存储节点出现故障需要移除或者扩增时,数据按照分布规则得到的结果应该尽量保持稳定,不要出现大范围的数据迁移。
数据稳定,就是尽可能只迁移移除节点上的数据到其他节点上,而不需要对大范围或所有数据进行迁移存储。当然,如果有扩展同类型节点,也是尽可能小范围迁移数据到扩展的节点上。具体的迁移方法,可以采用下文介绍的一致性哈希方法。
节点异构性
不同存储节点的硬件配置可能差别很大。比如,有的节点硬件配
置很高,可以存储大量数据,也可以承受更多的请求;但,有的节点硬件配置就不怎么样,
存储的数据量不能过多,用户访问也不能过多。
如果这种差别很大的节点,分到的数据量、用户访问量都差不多,本质就是一种不均衡。所
以,一个好的数据分布算法应该考虑节点异构性
隔离故障域
是为了保证数据的可用和可靠性。比如,我们通常通过备份来实现数据的可靠性。但如果每个数据及它的备份,被分布到了同一块硬盘或节点上,就有点违背备份的初衷了。所以,一个好的数据分布算法,应该为每个数据映射一组存储节点,这些节点应该尽量在不同的故障域,比如不同机房、不同机架等。
性能稳定性
是指,数据存储和查询的效率要有保证,不能因为节点的添加或者移除,造成存
储或访问性能的严重下降。
了解了数据分布的设计原则后,接下来我们再看看主流的数据分布式方法,哈希和一致性哈
希吧。其中,哈希和一致性哈希是数据分布的基础方法,在不同场景下,数据分布设计的原
则需要考虑的维度也不一样。随着维度的增加,一致性哈希又可进一步演进为带有限负载的
一致性哈希和带虚拟节点的一致性哈希方法。
数据分布方法
哈希是指,将数据按照提前规定好的函数(哈希函数)映射到相应的存储节点,即进行一个
哈希计算,得到的结果就是数据应该存储的节点。
一致性哈希同样是采用哈希函数,进行两步哈希:1. 对存储节点进行哈希计算,也就是对存储节点做哈希映射;
2. 当对数据进行存储或访问时,首先对数据进行映射得到一个结果,然后找到比该结果大
的第一个存储节点,就是该数据应该存储的地方。我会在下面的内容中,与你详细介绍
其中的原理。
总结来讲,哈希是一步计算直接得到相应的存储节点,而一致性哈希需要两步才可以找到相
应的存储节点。这,是不是就是“掐指一算”与“掐指两算”的事呢?
哈希
哈希是一种非常常用的数据分布方法,其核心思想是,首先确定一个哈希函数,然后通过计
算得到对应的存储节点。我们通过一个具体的例子来看一下吧。
假设,有三个存储节点,分别为 Node1、Node2 和 Node3;现有以下数据,ID 的范围为
[0,1000]:D0:{ id:100, name:‘a0’}、D1:{ id:200, name:‘a1’} 、D2:{ id:300,
name:‘a2’}、D3:{ id:400, name:‘a3’}、D4:{ id:500, name:‘a4’}、D5:{ id:600,
name:‘a5’}和 D6:{ id:700, name:‘a6’}。
假设,哈希函数为“id% 节点个数”,通过计算可以得到每个数据应该存入的节点。在这
个例子中,哈希函数是“id%3”,结果为 0 的数据存入 Node1、结果为 1 的数据存入
Node2、结果为 2 的数据存入 Node3。
如图所示,Node1 将存储数据 D2(300%3=0)和 D5(600%3=0),Node2 将存储数
据 D0(100%3=1)、D3(400%3=1)和 D6(700%3=1),Node3 将存储数据
D1(200%3=2)和 D4(500%3=2)。

可以看出,哈希算法的一个优点是,只要哈希函数设置得当,可以很好地保证数据均匀性,
但有一个较为严重的缺点,就是稳定性较差。
比如,随着数据量的增加,三个节点的容量无法再满足存储需求了,需要再添加一个节点。
这时,哈希函数变成了 id%4,原先存储在那三个节点的数据需要重新计算,然后存入相应
节点,即需要大规模的数据迁移,显然会降低稳定性。
所以,哈希方法适用于同类型节点且节点数量比较固定的场景。目前,Redis 就使用了哈希
方法,你可以再回顾下第 10 篇文章“分布式体系结构之非集中式结构:众生平等”中的相
关内容。
接下来,我们再看看一致性哈希吧。
一致性哈希
一致性哈希是指将存储节点和数据都映射到一个首尾相连的哈希环上,存储节点可以根据
IP 地址进行哈希,数据通常通过顺时针方向寻找的方式,来确定自己所属的存储节点,即
从数据映射在环上的位置开始,顺时针方向找到的第一个存储节点。
我们看看如何用一致性哈希方法,来实现上述案例的数据存储吧。
如图所示,假设数据 D0~D7 按照 ID 进行等值映射,即映射值与 ID 值相等,比如数据
D0 映射到哈希环上的值为 100,数据 D1 映射到哈希环上的值为 200······;同时,假设存
储节点 Node1、Node2 和 Node3 映射到哈希环上的值分别为 400、600、900。
按照规则,D0,D1,D2 和 D3 顺时针方向的下一个存储节点为 Node1,因此 Node1 将
存储数据 D0(id = 100)、D1(id = 200)、D2(id = 300)和 D3(id = 400);同
理,Node2 将存取数据 D4(id = 500)和 D5(id = 600),Node3 将存取数据 D6(id
= 700)。
可以看出,一致性哈希是对哈希方法的改进,在数据存储时采用哈希方式确定存储位置的基
础上,又增加了一层哈希,也就是在数据存储前,对存储节点预先进行了哈希。
这种改进可以很好地解决哈希方法存在的稳定性问题。当节点加入或退出时,仅影响该节点
在哈希环上顺时针相邻的后继节点。比如,当 Node2 发生故障需要移除时,由于 Node3
是 Node2 顺时针方向的后继节点,本应存储到 Node2 的数据就会存储到 Node3 中,其
他节点不会受到影响,因此不会发生大规模的数据迁移。
所以,一致性哈希方法比较适合同类型节点、节点规模会发生变化的场景。目前,
Cassandra 就使用了一致性哈希方法,你可以再回顾下第 10 篇文章“分布式体系结构之非
集中式结构:众生平等”中的相关内容。
一致性哈希方法虽然提升了稳定性,但随之而来的均匀性问题也比较明显,即对后继节点的
负载会变大。有节点退出后,该节点的后继节点需要承担该节点的所有负载,如果后继节点承受不住,便会出现节点故障,导致后继节点的后继节点也面临同样的问题。
那么,有没有更好的方法来解决这个问题呢?
Google 在 2017 年提出了带有限负载的一致性哈希算法,就对这个问题做了一些优化。
带有限负载的一致性哈希
带有限负载的一致性哈希方法的核心原理是,给每个存储节点设置了一个存储上限值来控制
存储节点添加或移除造成的数据不均匀。当数据按照一致性哈希算法找到相应的存储节点
时,要先判断该存储节点是否达到了存储上限;如果已经达到了上限,则需要继续寻找该存
储节点顺时针方向之后的节点进行存储。
我们看看如何用带有限负载的一致性哈希方法,来实现上述案例的数据存储吧。
如图所示,假设每个存储节点设置的上限值为 3,按照一致性哈希算法,当存储数据
D3(id = 400)时,会发现应该存储到 Node1 中,但 Node1 已经存储了三个数据
D0(id = 100)、D1(id = 200)和 D2(id = 300),达到了存储上限,因此会存储到
该节点顺时针方向的下一个节点 Node2 中。当然,在存储前,也会先检查 Node2 是否达
到了存储上限,如果达到了,会继续寻找其他节点。

如果你想要了解该算法的详细内容,可以阅读“Consistent Hashing with Bounded
Loads”这篇论文。
带有限负载的一致性哈希方法比较适合同类型节点、节点规模会发生变化的场景。目前,在
Google Cloud Pub/Sub、HAProxy 中已经实现该方法,应用于 Google、Vimeo 等公司
的负载均衡项目中。
其实,哈希、一致性哈希、带有限负载的一致性哈希,都没有考虑节点异构性的问题。如果
存储节点的性能好坏不一,数据分布方案还按照这些方法的话,其实还是没做到数据的均匀
分布。
接下来,我们再看一种主要针对存储节点为异构节点场景的方法,即带虚拟节点的一致性哈
希吧。
带虚拟节点的一致性哈希
带虚拟节点的一致性哈希方法,核心思想是根据每个节点的性能,为每个节点划分不同数量
的虚拟节点,并将这些虚拟节点映射到哈希环中,然后再按照一致性哈希算法进行数据映射
和存储。
假设,Node1 性能最差,Node2 性能一般,Node3 性能最好。以 Node1 的性能作为参
考基准,Node2 是 Node1 的 2 倍,Node3 是 Node1 的 3 倍。
因此,Node1 对应一个虚拟节点 Node1_1,Node2 对应 2 个虚拟节点 Node2_1 和
Node2_2,Node3 对应 3 个虚拟节点 Node3_1、Node3_2 和 Node3_3。
假设,虚拟节点 Node1_1、Node2_1、Node2_2、Node3_1、Node3_2、Node3_3 的
哈希值,分别为 100、200、300、400、500、600。
那么,按照带虚拟节点的哈希一致性方法, 数据 D0 和 D6 按顺时针方向的下一个虚拟存
储节点为 Node 1-1,因此节点 Node1 将会存储数据 D0(id = 100)和 D6(id =
700);同理,Node2 将会存储数据 D1(id = 200)和 D2(id = 300),Node3 将会
存储数据 D3(id = 400)、D4(id = 500)和 D5(id = 600)。

可以看出,带虚拟节点的一致性哈希方法比较适合异构节点、节点规模会发生变化的场景。
目前 Memcached 缓存系统实现了该方法,我会在第 27 篇文章中与你详细分析。
这种方法不仅解决了节点异构性问题,还提高了系统的稳定性。当节点变化时,会有多个节
点共同分担系统的变化,因此稳定性更高。
比如,当某个节点被移除时,对应该节点的多个虚拟节点均会移除,而这些虚拟节点按顺时
针方向的下一个虚拟节点,可能会对应不同的物理节点,即这些不同的物理节点共同分担了
节点变化导致的压力。
当然,这种方法引入了虚拟节点,增加了节点规模,从而增加了节点的维护和管理的复杂
度,比如新增一个节点或一个节点故障时,对应到虚拟节点构建的哈希环上需要新增和删除
多个节点,数据的迁移等操作相应地也会很复杂。
四种数据分布方法对比
为方便理解与记忆,我再通过一个表格和你对比分析下这四种方法吧。请注意,以下方法之
间的对比都是相对的比较,实际性能优劣与哈希函数的设定以及具体的数据场景密切相关。
