分布式存储系统数据分布的考虑与方法

野性酷女 2021-12-11 13:09 433阅读 0赞

### 文章目录 ###

*  哈希分布
 *   *   *  一致性哈希算法
         *  如何维护每台机器在哈希环中的位置信息？
         *  哈希环的负载均衡（Dynamo改动过的一致性哈希）
         *  分片
         *  CRUSH算法
 *  顺序分布
 *  负载均衡
 *  数据分布需要考虑什么？

Of course，分布式区别于单机就在于能够将数据分布到多个节点，并在多个节点之间实现负载均衡．主要的数据分布的方式有两种：

1.  **哈希分布：主要还是一致性哈希**
2.  **顺序分布：即将每张表格上的数据按照主键整体有序．**

衡量负载自然有许多的因素了．如：CPU，内存，磁盘，请求数等等．．当某台机器负载高时，分布式存储系统应该自动实现负载均衡（即将服务的部分数据迁移到其他负载较低的机器上）

# 哈希分布 #

先不管什么数据的哈希分布，我们先来学习下一致性哈希算法是什么，然后再来看数据的哈希分布．

### 一致性哈希算法 ###

主要就是**为了避免服务器数目增加／减少引发的大规模数据迁移／失效的问题**．

众所周知，数据按照哈希存放时几乎都是取模（服务器数量），而一致性哈希为了规避这个问题，采用了对 `2^n`取模的方式，将空间分为 0~2^(n-1) 。这个环就称之为Hash环。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]  
然后将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中四台服务器使用IP地址哈希后在环空间的位置如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]  
接下来，自然是对应的存放数据了，那么对于数据如何存放呐？

**将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]  
一致性哈希是如何解决前面提到的失效/迁移的问题的：

*  服务器增加

假设增加了一台服务器 Node X ,则只影响图中标红的部分数据的存放。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]

*  服务器减少

假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性Hash算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据（图中标红的数据），其它不会受到影响，如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 4]  
参考：[https://zhuanlan.zhihu.com/p/34985026][https_zhuanlan.zhihu.com_p_34985026]

### 如何维护每台机器在哈希环中的位置信息？ ###

*  查找时间复杂度：O(N)

双向链表的形式。每台机器记录前一个和后一个机器的位置信息。

*  查找时间复杂度： O(logN)

在每台机器上维护一张路由表。记录多个机器的位置信息。

*  查找时间复杂度：O(1)

**在每台机器上记录所有机器的位置信息。一般工程上都选择使用这种方法**。比如：Dynamo 这样的p2p系统。

### 哈希环的负载均衡（Dynamo改动过的一致性哈希） ###

为什么需要均衡？

*  一：服务节点太少

如何解决？

该算法给Hash环上的每个节点一个负载上限为1 + e倍的平均负载，这个e可以自定义，当key在Hash环上顺时针找到合适的节点后，会判断这个节点的负载是否已经到达上限，**如果已达上限，则需要继续找之后的节点进行分配**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 5]  
这个算法最吸引人的地方在于当有节点变化时，需要迁移的数据量是1/e^2相关，而与节点数或数据数均无关，也就是说**当集群规模扩大时，数据迁移量并不会随着显著增加**。另外，使用者可以通过调整e的值来控制均匀性和稳定性之间的权衡。无论是一致性Hash还是带负载限制的一致性Hash都无法解决**节点异构**的问题。

*  二：每个服务节点的差异较大

如何解决？

**对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。**

例如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 6]  
**同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射**，例如定位到“Node A\#1”、“Node A\#2”、“Node A\#3”三个虚拟节点的数据均定位到Node A上。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

\*\*如果新添加了一个节点进来，那就把之前算好的虚拟节点上的映射改为指向新的节点。从而实现负载均衡。\*\*如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 7]  
**实践中将一个虚拟节点重新分配给新的实际节点时需要将这部分数据遍历出来发送给新节点**。这里的话，只影响了两个节点，那如果是前面说的32个虚拟节点的话，后果不堪设想！

### 分片 ###

### CRUSH算法 ###

具体的有时间再研究，先知道有这个东西。

# 顺序分布 #

**会支持顺序扫描。**

**一般在分布式表格系统中比较常见。就是将大表分为连续的范围，每个范围称为一个子表，然后总控服务器将这些子表按照一定的策略分配到存储节点上即可。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 8]  
在实际操作过程中需要考虑到子表的合并和分裂，设置阈值等，这会增加系统的复杂性。类似B+树。

这里我想到的有一个问题就是：如果某台机器垮了，他需要把数据分散到各个机器，那么如何去保证主键顺序的连续性呐？？比如6001~7000垮了，然后分散，就是1-1000,6001-xxxx，这样子的吗？

# 负载均衡 #

现在的集群都是一个总控节点，多个工作节点的工作模式，那自然总控节点就承担起了负载均衡的工作。

**工作节点可通过心跳包向总控节点传输信息。需要注意数据迁移的节奏，一般就是部分迁移到整体迁移。时长一般应该在30分钟到1小时。**

# 数据分布需要考虑什么？ #

无论上层接口是KV存储、对象存储、块存储、亦或是列存储，在这个问题上大体是一致的。下文将介绍在分布式存储系统中做数据分布目标及可选的方案，并总结他们之间的关系及权衡。

*  指标  
    这里假设目标数据是以key标识的数据块或对象，在一个包含多个存储节点的集群中，数据分布算法需要为每一个给定的key指定一个或多个对应的存储节点负责，数据分布算法有两个基本目标：
    
     *  **均匀性**(Uniformity) ：不同存储节点的负载应该均衡；
     *  **稳定性**(Consistency)：每次一个key通过数据分布算法得到的分布结果应该保持基本稳定，即使在有存储节点发生变化的情况下。

可以看出，这两个目标在一定程度上是相互矛盾的，当有存储节点增加或删除时，为了保持稳定应该尽量少的进行数据的移动和重新分配，而这样又势必会带来负载不均。同样追求极致均匀也会导致较多的数据迁移。所以我们希望在这两个极端之间找到一个点以获得合适的均匀性和稳定性。除了上述两个基本目标外，工程中还需要从以下几个方面考虑数据分布算法的优劣：

*  **性能可扩展性**，这个主要考虑的是算法相对于存储节点规模的时间复杂度，为了整个系统的可扩展性，数据分布算法不应该在集群规模扩大后显著的增加运行时间。
 *  **考虑节点异构**，实际工程中，不同存储节点之间可能会有很大的性能或容量差异，好的数据分布算法应该能很好的应对这种异构，提供加权的数据均匀。
 *  **隔离故障域**，为了数据的高可用，数据分布算法应该为每个key找到一组存储节点，这些节点可能提供的是数据的镜像副本，也可能是类似擦除码的副本方式。数据分布算法应该尽量隔离这些副本的故障域，如不同机房、不同机架、不同交换机、不同机器。也就是**尽量的从最近的地点取到数据即可。**

参考：[https://zhuanlan.zhihu.com/p/32181800][https_zhuanlan.zhihu.com_p_32181800]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]: /images/20211211/a430adfd4be146aab5cc691c93479f15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]: /images/20211211/c66eed7f80f44c49ba898b7cd9bfd4c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]: /images/20211211/6cd36c4064e54565921e71fcb012349c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]: /images/20211211/bbca74123a104345a4f42181f3082123.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 4]: /images/20211211/548e1bdf67f24504b27fc81bedf0df75.png
[https_zhuanlan.zhihu.com_p_34985026]: https://zhuanlan.zhihu.com/p/34985026
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 5]: /images/20211211/82b8142798b542a78c5cd1005d40be81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 6]: /images/20211211/bee9bb6e639648c792e9fa5ba26c4ea5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 7]: /images/20211211/8afcc83c455c461faf79e42524b0983b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 8]: /images/20211211/8f97d0dd83dd454f8d5b3f990d410501.png
[https_zhuanlan.zhihu.com_p_32181800]: https://zhuanlan.zhihu.com/p/32181800