partition在本文中的翻译为分区。
数据量非常大的时候,在单台机器上存储和处理不再可行,则分区十分必要。分区的目标是在多台机器上均匀分布数据和查询负载,避免出现热点(负载不成比例的节点)。这需要选择适合于您的数据的分区方案,并在将节点添加到集群或从集群删除时进行再分区。分区主要是为了可扩展性(scalability)。

Partitioning and Replication

分区通常与复制结合使用,使得每个分区的副本存储在多个节点上。 这意味着,即使每条记录属于一个分区,它仍然可以存储在多个不同的节点上以获得容错能力。

Partitioning of Key-Value Data

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

避免热点最简单的方法是将记录随机分配给节点。这将在所有节点上平均分配数据,但是它有一个很大的缺点:当你试图读取一个特定的值时,你无法知道它在哪个节点上,所以你必须并行地查询所有的节点。

Partitioning by Key Range

一种分区的方法是为每个分区指定一块连续的键范围(从最小值到最大值),如果知道范围之间的边界,则可以轻松确定哪个分区包含某个值。

在每个分区中,我们可以按照一定的顺序保存键。优点是进行范围扫描非常简单,缺点是某些特定的访问模式会导致热点。

Partitioning by Hash of Key

一个好的散列函数可以将将偏斜的数据均匀分布。假设你有一个32位散列函数,无论何时给定一个新的字符串输入,它将返回一个0到2^{32}-1之间的”随机”数。即使输入的字符串非常相似,它们的散列也会均匀分布在这个数字范围内。

一旦你有一个合适的键散列函数,你可以为每个分区分配一个散列范围(而不是键的范围),每个通过哈希散列落在分区范围内的键将被存储在该分区中。如下图所示。

不幸的是,通过使用Key散列进行分区,我们失去了键范围分区的一个很好的属性:高效执行范围查询的能力。曾经相邻的Key现在分散在所有分区中,所以它们之间的顺序就丢失了。

Cassandra采取了折衷的策略。Cassandra中的表可以使用由多个列组成的复合主键来声明。键中只有第一列会作为散列的依据,而其他列则被用作Casssandra的SSTables中排序数据的连接索引。尽管查询无法在复合主键的第一列中按范围扫表,但如果第一列已经指定了固定值,则可以对该键的其他列执行有效的范围扫描。

Skewed Workloads and Relieving Hot Spots

在极端情况下,所有的读写操作都是针对同一个键的,所有的请求都会被路由到同一个分区。

​如今,大多数数据系统无法自动补偿这种高度偏斜的负载,因此应用程序有责任减少偏斜。例如,如果一个主键被认为是非常火爆的,一个简单的方法是在主键的开始或结尾添加一个随机数。只要一个两位数的十进制随机数就可以将主键分散为100钟不同的主键,从而存储在不同的分区中。

Partitioning and Secondary Indexes

Partitioning Secondary Indexes by Document

按文档分区(本地索引),其中二级索引存储在与主键和值相同的分区中。这意味着只有一个分区需要在写入时更新,但是读取二级索引需要在所有分区之间进行scatter/gather。

Partitioning Secondary Indexes by Term

按关键词分区(全局索引),其中二级索引存在不同的分区的。当文档写入时,需要更新多个分区中的二级索引;但是可以从单个分区中进行读取

Rebalancing Partitions

随着时间的推移,数据库会有各种变化。如机器出现故障,其他机器需要接管故障机器。
这些更改需要将数据和请求从一个节点移动到另一个节点。 将load从集群中的一个节点向另一个节点移动的过程称为再平衡(reblancing)。

Strategies for Rebalancing

有几种不同的分区分配方法,让我们依次简要讨论一下。

反面教材:hash mod N

模N方法的问题是,如果节点数量N发生变化,大多数Key将需要从一个节点移动到另一个节点。如此频繁的移动使得重新平衡的代价过于昂贵。

我们需要一种只移动必需数据的方法。

固定数量的分区

创建比节点更多的分区,并为每个节点分配多个分区。例如,运行在10个节点的集群上的数据库可能会从一开始就被拆分为1,000个分区,因此大约有100个分区被分配给每个节点。

现在,如果一个节点被添加到集群中,新节点可以从当前每个节点中窃取一些分区,直到分区再次公平分配。这个过程下图所示。

如果数据集的总大小难以预估(例如,如果它开始很小,但随着时间的推移可能会变得更大),选择正确的分区数是困难的。由于每个分区包含了总数据量固定比率的数据,因此每个分区的大小与集群中的数据总量成比例增长。如果分区非常大,再平衡和从节点故障恢复变得昂贵。但是,如果分区太小,则会产生太多的开销。当分区大小“恰到好处”的时候才能获得很好的性能,如果分区数量固定,但数据量变动很大,则难以达到最佳性能。

动态分区

对于使用键范围分区的数据库,具有固定边界的固定数量的分区将非常不便,手动重新配置分区边界将非常繁琐。

出于这个原因,按键的范围进行分区的数据库(如HBase)会动态创建分区。当分区增长到超过配置的大小时(在HBase上,默认值是10GB),会被分成两个分区,每个分区约占一半的数据。与之相反,如果大量数据被删除并且分区缩小到某个阈值以下,则可以将其与相邻分区合并。

动态分区的一个优点是分区数量适应总数据量。如果只有少量的数据,少量的分区就足够了,所以开销很小;如果有大量的数据,每个分区的大小被限制在一个可配置的最大值。

动态分区不仅适用于数据的范围分区,而且也适用于hash分区。

Partitioning proportionally to nodes

每个节点具有固定数量的分区,在这种情况下,每个分区的大小与数据集大小成比例地增长,而节点数量保持不变,但是当增加节点数时,分区将再次变小。由于较大的数据量通常需要较大数量的节点进行存储,因此这种方法也使每个分区的大小较为稳定。

Request Routing

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

​这个问题可以概括为 服务发现(service discovery) 。

概括来说,这个问题有几种不同的方案(如下图所示):

  1. 允许客户联系任何节点(例如,通过循环策略的负载均衡(Round-Robin Load Balancer))。如果该节点恰巧拥有请求的分区,则它可以直接处理该请求;否则,它将请求转发到适当的节点,接收回复并传递给客户端。
  2. 首先将所有来自客户端的请求发送到路由层,它决定了应该处理请求的节点,并相应地转发。此路由层本身不处理任何请求,它仅负责分区的负载均衡。
  3. 要求客户端知道分区和节点的分配。在这种情况下,客户端可以直接连接到适当的节点,而不需要任何中介。

以上所有情况中的关键问题是:作出路由决策的组件(可能是节点之一,还是路由层或客户端)如何了解分区-节点之间的分配关系变化?

许多分布式数据系统都依赖于一个独立的协调服务,比如用ZooKeeper来跟踪集群元数据,如下图所示。

每个节点在ZooKeeper中注册自己,ZooKeeper维护分区到节点的可靠映射。 其他参与者(如路由层或分区感知客户端)可以在ZooKeeper中订阅此信息。 只要分区分配发生的改变,或者集群中添加或删除了一个节点,ZooKeeper就会通知路由层使路由信息保持最新状态。

Cassandra和Riak采取不同的方法:他们在节点之间使用流言协议(gossip protocol) 来传播群集状态的变化。请求可以发送到任意节点,该节点会转发到包含所请求的分区的适当节点(图Figure 6-7中的方法1)。这个模型在数据库节点中增加了更多的复杂性,但是避免了对像ZooKeeper这样的外部协调服务的依赖。


参考资料:

  1. Vonng ddia翻译