【数据库】——分布式数据库的分区总结

红太狼 2022-12-29 04:45 145阅读 0赞

### **一、前言** ###

本文涉及的概念较多，同时涉及到的数据库也较多。有redis、hbase、es、mongo、zk等，行文省略了很多细节，所以本文适合有一定分布式数据库经验的人，仅供参考。本文行文主要回答下边四个问题：

1.  分区是什么？
2.  分区怎么分的？
3.  分区之后怎么平衡？
4.  分区之后如何路由？

### **二、概念** ###

**     分区(partition)**,在MongoDB,Elasticsearch中被称为**分片(shard)**,在HBase中称之为**区域(Region)**，Bigtable中则是**表块（tablet）**，Cassandra中是**虚节点（vnode)**.但是**分区(partition)**是约定俗成的叫法。

分区主要是为了可扩展性。不同的分区可以放在不共享集群中的不同节点上因此，大数据集可以分布在多个磁盘上，并且查询负载可以分布在多个处理器上。对于在单个分区上运行的查询，每个节点可以独立执行对自己的查询，因此可以通过添加更多的节点来扩大查询吞吐量。大型，复杂的查询可能会跨越多个节点并行处理。

分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。 这意味着，即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能力。一个节点可能存储多个分区。如果使用主从复制模型，则分区和复制的组合如图所示。 每个分区领导者(主)被分配给一个节点，追随者(从)被分配给其他节点。 每个节点可能是某些分区的领导者，同时是其他分区的追随者。 关于数据库复制的所有内容同样适用于分区的复制。 大多数情况下，分区方案的选择与复制方案的选择是独立的，为简单起见，本章中将忽略复制。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70][]

### **三、键值数据的分区** ###

假设你有大量数据并且想要分区,如何决定在哪些节点上存储哪些记录呢？分区目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分享数据和负载，那么理论上10个节点应该能够处理10倍的数据量和10倍的单个节点的读写吞吐量（暂时忽略复制）。

如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew）。数据偏斜的存在使分区效率下降很多。在极端的情况下，所有的负载可能压在一个分区上，其余9个节点空闲的，瓶颈落在这一个繁忙的节点上。不均衡导致的高负载的分区被称为热点（hot spot）。

避免热点最简单的方法是将记录随机分配给节点。这将在所有节点上平均分配数据，但是它有一个很大的缺点：当你试图读取一个特定的值时，你无法知道它在哪个节点上，所以你必须并行地查询所有的节点。我们可以做得更好。现在假设您有一个简单的键值数据模型，其中您总是通过其主键访问记录。例如，在一本老式的纸质百科全书中，你可以通过标题来查找一个条目;由于所有条目按字母顺序排序，因此您可以快速找到您要查找的条目。

**1、根据键的范围分区**

一种分区的方法是为每个分区指定一块连续的键范围（从最小值到最大值），如纸百科全书的卷。如果知道范围之间的边界，则可以轻松确定哪个分区包含某个值。如果您还知道分区所在的节点，那么可以直接向相应的节点发出请求（对于百科全书而言，就像从书架上选取正确的书籍）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 1][]

在每个分区中，我们可以按照一定的顺序保存键。好处是进行范围扫描非常简单，您可以将键作为联合索引来处理。然而，Key Range分区的缺点是某些特定的访问模式会导致热点。 如果主键是时间戳，则分区对应于时间范围，例如，给每天分配一个分区。 不幸的是，由于我们在测量发生时将数据从传感器写入数据库，因此所有写入操作都会转到同一个分区（即今天的分区），这样分区可能会因写入而过载，而其他分区则处于空闲状态。

**小案例：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 2][]

**2、****根据键的散列分区**

由于偏斜和热点的风险，许多分布式数据存储使用散列函数来确定给定键的分区。常见的哈希分区规则：节点取余分区规则、一致性哈希分区（Consistent hashing）、虚拟槽（Virtual slot）分区。

1.  节点取余分区

使用特定的数据，如Redis的键或用户ID，再根据节点（运行在集群模式下的Redis服务器）的数量N使用公式：hash(key) % N计算出hash值，用来决定数据存储在哪个节点上。例如，将20个数据存储在4个节点上：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 3][]

如果此时增加一个节点，那么经过重新hash计算后得到的分布如下（其中数据1、2、3、20这4个数据存储的位置没有改变，其他的数据位置都发生了改变。）

** 节点取余分区缺点：**在节点的数量变化时，如扩容或收缩节点时，数据节点映射关系需要重新计算，会导致大量数据重新迁移。

**节点取余分区优点：**实现简单。常用于数据库分库分表规则，通常先预先根据数据数量规划好区数，保证可以支撑一段时间，再根据负载情况将数据迁移到其他数据库中，扩容时通常采用翻倍扩容，这样大约只需迁移一半的数据量，从而避免映射全部被打乱导致全量迁移的情况。

1.  一致性哈希分区

整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到232-1，也就是说0点左侧的第一个点代表232-1， 0和232-1在零点中方向重合，我们把这个由232个点组成的圆环称为Hash环。数据读写执行节点查找操作时，先根据key计算出哈希值，然后顺时针找到第一个遇到的节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 4][]

这种方式相对于节点取余的好处在于加入和删除节点只影响哈希环中相邻的节点，对其他节点无影响。

如下图表示新增一个节点，经过hash计算出其位置为在节点2和节点3之间，它对数据分布影响的范围只是节点3和节点4之间的绿色部分的数据无法命中，对其他的节点的无影响。

考虑这样的一种情况，如果只有3个节点，且节点在哈希环上的分布是可能是这个样子的，即使数据分布的均匀，大量的数据存储在节点0上，而节点1、2不会存储多少数据，节点0的负载会很高，这种情况就是哈希倾斜性导致的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 5][]

**问题：对于这种数据倾斜怎么去处理？**

答：增加"虚拟节点"

（3）虚拟槽分区

Redis Cluster采用的就是虚拟槽分区。虚拟槽分区巧妙的使用了哈希空间，使用分散度良好的哈希函数将所有的数据映射到一个固定范围的整数集合中，整数定义为槽（slot）。这个范围一般远远大于节点数，这是为了消除哈希的倾斜性，便于数据拆分和扩展。例如Redis Cluster槽的范围是0~16383。槽是集群内数据管理和迁移的基本单位，每个节点都会负责一定数量的槽。

如在Redis中，假设有5个节点，每个节点平均负责3276个槽。 由于采用了分散性较好的哈希函数，所有的数据大致均匀分布在0~16383各个槽中，计算公式为slot = CRC16(key) & 16383，当要操作数据时，只需要计算出相应的槽，并根据槽即可找到对应的节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 6][]

虚拟槽分布的特点：

1.  解耦数据和节点之间的关系，简化了节点的扩容和收缩。
2.  解决了普通一致性哈希分区只有少量节点负载不均衡问题。

支持节点、槽、键之间的映射查询，用于数据路由。

### **四、分区再平衡策略** ###

随着时间的推移，数据库会有各种变化。

1.  查询吞吐量增加，所以您想要添加更多的CPU来处理负载。
2.  数据集大小增加，所以您想添加更多的磁盘和RAM来存储它。
3.  机器出现故障，其他机器需要接管故障机器的责任。
4.  所有这些更改都需要数据和请求从一个节点移动到另一个节点。 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡（reblancing）。

无论使用哪种分区方案，再平衡通常都要满足一些最低要求：

1.  再平衡之后，负载（数据存储，读取和写入请求）应该在集群中的节点之间公平地共享。
2.  再平衡发生时，数据库应该继续接受读取和写入。
3.  节点之间只移动必须的数据，以便快速再平衡，并减少网络和磁盘I/O负载。

**1、****固定数量的分区**

幸运的是，有一个相当简单的解决方案：创建比节点更多的分区，并为每个节点分配多个分区。例如，运行在10个节点的集群上的数据库可能会从一开始就被拆分为1,000个分区，因此大约有100个分区被分配给每个节点。现在，如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配。这个过程如图6-6所示。如果从集群中删除一个节点，则会发生相反的情况。只有分区在节点之间的移动。分区的数量不会改变，键所指定的分区也不会改变。唯一改变的是分区所在的节点。这种变更并不是即时的 — 在网络上传输大量的数据需要一些时间 — 所以在传输过程中，原有分区仍然会接受读写操作。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 7][]

在这种配置中，分区的数量通常在数据库第一次建立时确定，之后不会改变。虽然原则上可以分割和合并分区（请参阅下一节），但固定数量的分区在操作上更简单，因此许多固定分区数据库选择不实施分区分割。因此，一开始配置的分区数就是您可以拥有的最大节点数量，所以您需要选择足够多的分区以适应未来的增长。但是，每个分区也有管理开销，所以选择太大的数字会适得其反。如果数据集的总大小难以预估（例如，如果它开始很小，但随着时间的推移可能会变得更大），选择正确的分区数是困难的。由于每个分区包含了总数据量固定比率的数据，因此每个分区的大小与集群中的数据总量成比例增长。如果分区非常大，再平衡和从节点故障恢复变得昂贵。但是，如果分区太小，则会产生太多的开销。当分区大小“恰到好处”的时候才能获得很好的性能，如果分区数量固定，但数据量变动很大，则难以达到最佳性能。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 8][]

**2、****动态分区**

对于使用键范围分区的数据库（参阅“按键范围分区”），具有固定边界的固定数量的分区将非常不便：如果出现边界错误，则可能会导致一个分区中的所有数据或者其他分区中的所有数据为空。手动重新配置分区边界将非常繁琐。出于这个原因，按键的范围进行分区的数据库（如HBase和RethinkDB）会动态创建分区。当分区增长到超过配置的大小时（在HBase上，默认值是10GB），会被分成两个分区，每个分区约占一半的数据。与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。此过程与B树顶层发生的过程类似（参阅“B树”）。每个分区分配给一个节点，每个节点可以处理多个分区，就像固定数量的分区一样。大型分区拆分后，可以将其中的一半转移到另一个节点，以平衡负载。在HBase中，分区文件的传输通过HDFS（底层分布式文件系统）来实现。动态分区的一个优点是分区数量适应总数据量。如果只有少量的数据，少量的分区就足够了，所以开销很小;如果有大量的数据，每个分区的大小被限制在一个可配置的最大值。需要注意的是，一个空的数据库从一个分区开始，因为没有关于在哪里绘制分区边界的先验信息。数据集开始时很小，直到达到第一个分区的分割点，所有写入操作都必须由单个节点处理，而其他节点则处于空闲状态。为了解决这个问题，HBase和MongoDB允许在一个空的数据库上配置一组初始分区（这被称为预分割（pre-splitting））。在键范围分区的情况中，预分割需要提前知道键是如何进行分配的。

动态分区不仅适用于数据的范围分区，而且也适用于散列分区。从版本2.4开始，MongoDB同时支持范围和哈希分区，并且都是进行动态分割分区。

**例子：mongodb**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 9][]

在一个shard server内部，MongoDB还是会把数据分为chunks，每个chunk代表这个shard server内部一部分数据。chunk的产生，会有以下两个用途：

Splitting：当一个chunk的大小超过配置中的chunk size时，MongoDB的后台进程会把这个chunk切分成更小的chunk，从而避免chunk过大的情况。

Balancing：在MongoDB中，balancer是一个后台进程，负责chunk的迁移，从而均衡各个shard server的负载，系统初始1个chunk，chunk size默认值64M,生产库上选择适合业务的chunk size是最好的。ongoDB会自动拆分和迁移chunks。

分片集群的数据分布（shard节点）

（1）使用chunk来存储数据

（2）进群搭建完成之后，默认开启一个chunk，大小是64M，

（3）存储需求超过64M，chunk会进行分裂，如果单位时间存储需求很大，设置更大的chunk

1.  chunk会被自动均衡迁移。

随着数据的增长，其中的数据大小超过了配置的chunk size，默认是64M，则这个chunk就会分裂成两个。数据的增长会让chunk分裂得越来越多。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 10][]

这时候，各个shard 上的chunk数量就会不平衡。这时候，mongos中的一个组件balancer 就会执行自动平衡。把chunk从chunk数量最多的shard节点挪动到数量最少的节点。

### **五、请求路由** ###

**问题：**现在我们已经将数据集分割到多个机器上运行的多个节点上。但是仍然存在一个悬而未决的问题：当客户想要发出请求时，如何知道要连接哪个节点？随着分区重新平衡，分区对节点的分配也发生变化。为了回答这个问题，需要有人知晓这些变化：如果我想读或写键“foo”，需要连接哪个IP地址和端口号？

概括来说，这个问题有几种不同的方案:

1.  允许客户联系任何节点（例如，通过循环策略的负载均衡（Round-Robin Load Balancer））。如果该节点恰巧拥有请求的分区，则它可以直接处理该请求;否则，它将请求转发到适当的节点，接收回复并传递给客户端。
2.  首先将所有来自客户端的请求发送到路由层，它决定了应该处理请求的节点，并相应地转发。此路由层本身不处理任何请求；它仅负责分区的负载均衡。

要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而不需要任何中介。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 11][]

许多分布式数据系统都依赖于一个独立的协调服务，比如ZooKeeper来跟踪集群元数据，如图6-8所示。 每个节点在ZooKeeper中注册自己，ZooKeeper维护分区到节点的可靠映射。 其他参与者（如路由层或分区感知客户端）可以在ZooKeeper中订阅此信息。 只要分区分配发生的改变，或者集群中添加或删除了一个节点，ZooKeeper就会通知路由层使路由信息保持最新状态。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 12][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70]: /images/20221120/c7e5fcba44df47318f6bfa622455a9d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 1]: /images/20221120/74d60beb64624ed7800c05cc5162ee60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 2]: /images/20221120/aaed91f73935421398129ca759f3b89a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 3]: /images/20221120/8116f04c34eb457db378d9e476a19983.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 4]: /images/20221120/3b1ae5c41131494b88d6678a4f1ca2ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 5]: /images/20221120/10abb72e0aa045e882c9c61342a0c16d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 6]: /images/20221120/7a15e36d8a424f8384e8105f028729e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 7]: /images/20221120/b4a9342b929f4a10949de9c92cbcbd89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 8]: /images/20221120/370857dcf5784a9f82f7cf2ab1ed6738.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 9]: /images/20221120/4b59c6778eb64d218164b125b7e4ab4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 10]: /images/20221120/be84faa90fde4cfba8faac2c03e44eaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 11]: /images/20221120/532acbe4d82a490a8e660635f390e2f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70 12]: /images/20221120/d9da97992ff748ba8dab3cf8bba1e631.png