Comment on page
第六章:分区

我们必须跳出电脑指令序列的窠臼。叙述定义、描述元数据、梳理关系,而不是编写过程。—— Grace Murray Hopper,未来的计算机及其管理(1962)
[TOC]
在 第五章 中,我们讨论了复制 —— 即数据在不同节点上的副本,对于非常大的数据集,或非常高的吞吐量,仅仅进行复制是不够的:我 们需要将数据进行 分区(partitions),也称为 分片(sharding)。
术语澄清上文中的 分区(partition),在 MongoDB,Elasticsearch 和 Solr Cloud 中被称为 分片(shard),在 HBase 中称之为 区域(Region),Bigtable 中则是 表块(tablet),Cassandra 和 Riak 中是 虚节点(vnode),Couchbase 中叫做 虚桶(vBucket)。但是 分区(partitioning) 是最约定俗成的叫法。
通常情况下,每条数据(每条记录,每行或每个文档)属于且仅属于一个分区。有很多方法可以实现这一点,本章将进行深入讨论。实际上,每个分区都是自己的小型数据库,尽管数据库可能支持同时进行多个分区的操作。
对于在单个分区上运行的查询,每个节点可以独立执行对自己的查询,因此可以通过添加更多的节点来扩大查询吞吐量。大型,复杂的查询可能会跨越多个节点并行处理,尽管这也带来了新的困难。
分区数据库在 20 世纪 80 年代由 Teradata 和 NonStop SQL【1】等产品率先推出,最近因为 NoSQL 数据库和基于 Hadoop 的数据仓库重新被关注。有些系统是为事务性工作设计的,有些系统则用于分析(请参阅 “事务处理还是分析”):这种差异会影响系统的运作方式,但是分区的基本原理均适用于这两种工作方式。
在本章中,我们将首先介绍分割大型数据集的不同方法,并观察索引如何与分区配合。然后我们将讨论 分区再平衡(rebalancing),如果想要添加或删除集群中的节点,则必须进行再平衡。最后,我们将概述数据库如何将请求路由到正确的分区并执行查询。
分区通常与复制结合使用,使得每个分区的副本存储在多个节点上。这意味着,即使每条记录属于一个分区,它仍然可以存储在多个不同的节点上以获得容错能力。
一个节点可能存储多个分区。如果使用主从复制模型,则分区和复制的组合如 图 6-1 所示。每个分区领导者(主库)被分配给一个节点,追随者(从库)被分配给其他节点。每个节点可能是某些分区的主库,同时是其他分区的从库。

图 6-1 组合使用复制和分区:每个节点充当某些分区的主库,其他分区充当从库。
假设你有大量数据并且想要分区,如何决定在哪些节点上存储哪些记录呢?
分区目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分享数据和负载,那么理论上 10 个节点应该能够处理 10 倍的数据量和 10 倍的单个节点的读写吞吐量(暂时忽略复制)。
如果分区是不公平的,一些分区比其他分区有更多的数据或查询,我们称之为 偏斜(skew)。数据偏斜的存在使分区效率下降很多。在极端的情况下,所有的负载可能压在一个分区上,其余 9 个节点空闲的,瓶颈落在这一个繁忙的节点上。不均衡导致的高负载的分区被称为 热点(hot spot)。
避免热点最简单的方法是将记录随机分配给节点。这将在所有节点上平均分配数据,但是它有一个很大的缺点:当你试图读取一个特定的值时,你无法知道它在哪个节点上,所以你必须并行地查询所有的节点。
我们可以做得更好。现在假设你有一个简单的键值数据模型,其中你总是通过其主键访问记录。例如,在一本老式的纸质百科全书中,你可以通过标题来查找一个条目;由于所有条目按字母顺序排序,因此你可以快速找到你要查找的条目。
一种分区的方法是为每个分区指定一块连续的键范围(从最小值到最大值),如 纸质百科全书的卷(图 6-2)。如果知道范围之间的边界,则可以轻松确定哪个分区包含某个值。如果你还知道分区所在的节点,那么可以直接向相应的节点发出请求(对于百科全书而言,就像从书架上选取正确的书籍)。

图 6-2 印刷版百科全书按照关键字范围进行分区
键的范围不一定均匀分布,因为数据也很可能不均匀分布。例如在 图 6-2 中,第 1 卷包含以 A 和 B 开头的单词,但第 12 卷则包含以 T、U、V、X、Y 和 Z 开头的单词。只是简单的规定每个卷包含两个字母会导致一些卷比其他卷大。为了均匀分配数据,分区边界需要依据数据调整。
分区边界可以由管理员手动选择,也可以由数据库自动选择(我们会在 “分区再平衡” 中更详细地讨论分区边界的选择)。Bigtable 使用了这种分区策略,以及其开源等价物 HBase 【2, 3】、RethinkDB 和 2.4 版本之前的 MongoDB 【4】。
在每个分区中,我们可以按照一定的顺序保存键(请参阅 “SSTables 和 LSM 树”)。好处是进行范围扫描非常简单,你可以将键作为联合索引来处理,以便在一次查询中获取多个相关记录(请参阅 “多列索引”)。例如,假设我们有一个程序来存储传感器网络的数据,其中主键是测量的时间戳(年月日时分秒)。范围扫描在这种情况下非常有用,因为我们可以轻松获取某个月份的所有数据。
然而,Key Range 分区的缺点是某些特定的访问模式会导致热点。如果主键是时间戳,则分区对应于时间范围,例如,给每天分配一个分区。不幸的是,由于我们在测量发生时将数据从传感器写入数据库,因此所有写入操作都会转到同一个分区(即今天的分区),这样分区可能会因写入而过载,而其他分区则处于空闲状态【5】。
为了避免传感器数据库中的这个问题,需要使用除了时间戳以外的其他东西作为主键的第一个部分。例如,可以在每个时间戳前添加传感器名称,这样会首先按传感器名称,然后按时间进行分区。假设有多个传感器同时运行,写入负载将最终均匀分布在不同分区上。现在,当想要在一个时间范围内获取多个传感器的值时,你需要为每个传感器名称执行一个单独的范围查询。
由于偏斜和热点的风险,许多分布式数据存储使用散列函数来确定给定键的分区。
一个好的散列函数可以将偏斜的数据均匀分布。假设你有一个 32 位散列函数,无论何时给定一个新的字符串输入,它将返回一个 0 到 $2^{32}$ -1 之间的 “随机” 数。即使输入的字符串非常相似,它们的散列也会均匀分布在这个数字范围内。
出于分区的目的,散列函数不需要多么强壮的加密算法:例如,Cassandra 和 MongoDB 使用 MD5,Voldemort 使用 Fowler-Noll-Vo 函数。许多编程语言都有内置的简单哈希函数(它们用于散列表),但是它们可能不适合分区:例如,在 Java 的
Object.hashCode()
和 Ruby 的 Object#hash
,同一个键可能在不同的进程中有不同的哈希值【6】。
图 6-3 按哈希键分区
这种技术擅长在分区之间公平地分配键。分区边界可以是均匀间隔的,也可以是伪随机选择的(在这种情况下,该技术有时也被称为 一致性哈希,即 consistent hashing) 。
一致性哈希正如我们将在 “分区再平衡” 中所看到的,这种特殊的方法对于数据库实际上并不是很好,所以在实际中很少使用(某些数据库的文档仍然会使用一致性哈希的说法,但是它往往是不准确的)。因为有可能产生混淆,所以最好避免使用一致性哈希这个术语,而只是把它称为 散列分区(hash partitioning)。
不幸的是,通过使用键散列进行分区,我们失去了键范围分区的一个很好的属性:高效执行范围查询的能力。曾经相邻的键现在分散在所有分区中,所以它们之间的顺序就丢失了。在 MongoDB 中,如果你使用了基于散列的分区模式,则任何范围查询都必须发送到所有分区【4】。Riak【9】、Couchbase 【10】或 Voldemort 不支持主键上的范围查询。
Cassandra 采取了折衷的策略【11, 12, 13】。Cassandra 中的表可以使用由多个列组成的复合主键来声明。键中只有第一列会作为散列的依据,而其他列则被用作 Casssandra 的 SSTables 中排序数据的连接索引。尽管查询无法在复合主键的第一列中按范围扫表,但如果第一列已经指定了固定值,则可以对该键的其他列执行有效的范围扫描。
组合索引方法为一对多关系提供了一个优雅的数据 模型。例如,在社交媒体网站上,一个用户可能会发布很多更新。如果更新的主键被选择为
(user_id, update_timestamp)
,那么你可以有效地检索特定用户在某个时间间隔内按时间戳排序的所有更新。不同的用户可以存储在不同的分区上,对于每个用户,更新按时间戳顺序存储在单个分区上。如前所述,哈希分区可以帮助减少热点。但是,它不能完全避免它们:在极端情况下,所有的读写操作都是针对同一个 键的,所有的请求都会被路由到同一个分区。
这种场景也许并不常见,但并非闻所未闻:例如,在社交媒体网站上,一个拥有数百万追随者的名人用户在做某事时可能会引发一场风暴【14】。这个事件可能导致同一个键的大量写入(键可能是名人的用户 ID,或者人们正在评论的动作的 ID)。哈希策略不起作用,因为两个相同 ID 的哈希值仍然是相同的。
如今,大多数数据系统无法自动补偿这种高度偏斜的负载,因此应用程序有责任减少偏斜。例如,如果一个主键被认为是非常火爆的,一个简单的方法是在主键的开始或结尾添加一个随机数。只要一个两位数的十进制随机数就可以将主键分散为 100 种不同的主键,从而存储在不同的分区中。
然而,将主键进行分割之后,任何读取都必须要做额外的工作,因为他们必须从所有 100 个主键分布中读取数据并将其合并。此技术还需要额外的记录:只需要对少量热点附加随机数;对于写入吞吐量低的绝大多数主键来说是不必要的开销。因此,你还需要一些方法来跟踪哪些键需要被分割。
也许在将来,数据系统将能够自动检测和补偿偏斜的工作负载;但现在,你需要自己来权衡。
到目前为止,我们讨论的分区方案依赖于键值数据模型。如果只通过主键访问记录,我们可以从该键确定分区,并使用它来将读写请求路由到负责该键的分区。
如果涉及次级索引,情况会变得更加复杂(参考 “其他索引结构”)。次级索引通常并不能唯一地标识记录,而是一种搜索记录中出现特定值的方式:查找用户 123 的所有操作、查找包含词语
hogwash
的所有文章、查找所有颜色为红色的车辆等等。