文章目录
  1. 1. Partitioning and Replication
  2. 2. Partitioning of Key-Value Data
    1. 2.1. Partitioning by Key Range
    2. 2.2. Partitioning by Hash of Key
    3. 2.3. Skewed Workloads and Relieving Hot Spots
  3. 3. Partitioning and Secondary Indexes
    1. 3.1. Partitioning Secondary Indexes by Document
    2. 3.2. Partitioning Secondary Indexes by Term
  4. 4. Rebalancing Partitions
    1. 4.1. Strategies for Rebalancing
      1. 4.1.1. 反面教材:hash mod N
      2. 4.1.2. 固定数量的分区
      3. 4.1.3. 动态分区
      4. 4.1.4. Partitioning proportionally to nodes
  5. 5. Request Routing

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翻译
文章目录
  1. 1. Partitioning and Replication
  2. 2. Partitioning of Key-Value Data
    1. 2.1. Partitioning by Key Range
    2. 2.2. Partitioning by Hash of Key
    3. 2.3. Skewed Workloads and Relieving Hot Spots
  3. 3. Partitioning and Secondary Indexes
    1. 3.1. Partitioning Secondary Indexes by Document
    2. 3.2. Partitioning Secondary Indexes by Term
  4. 4. Rebalancing Partitions
    1. 4.1. Strategies for Rebalancing
      1. 4.1.1. 反面教材:hash mod N
      2. 4.1.2. 固定数量的分区
      3. 4.1.3. 动态分区
      4. 4.1.4. Partitioning proportionally to nodes
  5. 5. Request Routing