键值数据的分片

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

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

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

Range-based sharding，基于范围分片

基于范围的分片假定数据库系统中的所有键都可以排序，并且将键的连续部分作为分片单元。如果知道范围之间的边界，则可以轻松确定哪个分区包含某个值。如果您还知道分区所在的节点，那么可以直接向相应的节点发出请求（对于百科全书而言，就像从书架上选取正确的书籍）。

键的范围不一定均匀分布，因为数据也很可能不均匀分布。例如在上图中，第1卷包含以A和B开头的单词，但第12卷则包含以T，U，V，X，Y和Z开头的单词。只是简单的规定每个卷包含两个字母会导致一些卷比其他卷大。为了均匀分配数据，分区边界需要依据数据调整。

分区边界可以由管理员手动选择，也可以由数据库自动选择，Bigtable，HBase，RethinkDB以及2.4版本之前的MondoDB都是使用了这种分片策略。HBase Keys按字节顺序排序，而MySQL密钥按自动增量ID顺序排序。对于譬如对于日志结构的合并树（LSM-Tree）和B-Tree，键自然是有序的。

如上图就是MongoDB的基于范围的分片策略，键空间（Key Space）被划分为了 (minKey, maxKey)。每个分片单元（块）都是连续键的一部分。基于范围的分片的优点是相邻数据在一起的可能性很高（例如具有公共前缀的数据），可以很好地支持“范围扫描（Range Scan）”之类的操作。例如，HBase Region是一种典型的基于范围的分片策略。

在每个分区中，我们可以按照一定的顺序保存键，好处是进行范围扫描非常简单，您可以将键作为联合索引来处理，以便在一次查询中获取多个相关记录。例如，假设我们有一个程序来存储传感器网络的数据，其中主键是测量的时间戳（年月日时分秒）。范围扫描在这种情况下非常有用，因为我们可以轻松获取某个月份的所有数据。关系数据库通常需要执行“表扫描”或“索引扫描”，因此它们常选择基于范围的分片。

但是，基于范围的分片对工作量大的顺序写入不友好。还是刚才的物联网例子中，在时间序列类型的写入负载的时候，写入热点始终位于最后一个区域中。发生这种情况是因为日志键通常与时间戳有关，并且时间单调增加。为了避免传感器数据库中的这个问题，需要使用除了时间戳以外的其他东西作为主键的第一个部分例如，可以在每个时间戳前添加传感器名称，这样会首先按传感器名称，然后按时间进行分区假设有多个传感器同时运行，写入负载将最终均匀分布在不同分区上。现在，当想要在一个时间范围内获取多个传感器的值时，您需要为每个传感器名称执行一个单独的范围查询。

Hash-based sharding

由于偏斜和热点的风险，许多分布式数据存储使用哈希函数来确定给定键的分区，即基于哈希的分片使用哈希函数处理密钥，然后使用结果获取分片ID。一个好的哈希函数可以将将偏斜的数据均匀分布。假设你有一个32位哈希函数,无论何时给定一个新的字符串输入，它将返回一个0到$2^{32}$ -1之间的"随机"数。即使输入的字符串非常相似，它们的哈希也会均匀分布在这个数字范围内。

出于分区的目的，哈希函数不需要多么强壮的加密算法：例如，Cassandra和MongoDB使用MD5，Voldemort使用Fowler-Noll-Vo函数。许多编程语言都有内置的简单哈希函数（它们用于哈希表），但是它们可能不适合分区：例如，在Java的Object.hashCode()和Ruby的Object#hash，同一个键可能在不同的进程中有不同的哈希值。一旦你有一个合适的键哈希函数，你可以为每个分区分配一个哈希范围（而不是键的范围），每个通过哈希哈希落在分区范围内的键将被存储在该分区中。

基于哈希的分片的一些典型示例是Cassandra一致性哈希，Redis Cluster和Codis的Presharding以及Twemproxy一致性哈希。如下图所示的就是MongoDB中基于Hash的分片策略：

与基于范围的分片相反，基于哈希的分片具有以下优点：密钥几乎是随机分布的，因此分布是均匀的。因此，它对于写入工作量和读取工作量几乎都是随机的系统更为友好。这是因为写入压力可以均匀地分布在群集中，从而使“范围扫描”之类的操作非常困难。

不幸的是，通过使用Key哈希进行分区，我们失去了键范围分区的一个很好的属性：高效执行范围查询的能力。曾经相邻的密钥现在分散在所有分区中，所以它们之间的顺序就丢失了。在MongoDB中，如果您使用了基于哈希的分区模式，则任何范围查询都必须发送到所有分区。Riak，Couchbase或Voldemort不支持主键上的范围查询。Cassandra采取了折衷的策略Cassandra中的表可以使用由多个列组成的复合主键来声明。键中只有第一列会作为哈希的依据，而其他列则被用作Casssandra的SSTables中排序数据的连接索引。尽管查询无法在复合主键的第一列中按范围扫表，但如果第一列已经指定了固定值，则可以对该键的其他列执行有效的范围扫描。

请注意，基于哈希和基于范围的分片策略不是隔离的。相反，您可以灵活地组合它们。例如，您可以建立一个多级分片策略，该策略在最上层使用哈希，而在每个基于哈希的分片单元中，数据将按顺序存储。譬如在社交媒体网站上，一个用户可能会发布很多更新。如果更新的主键被选择为 (user_id, update_timestamp)，那么您可以有效地检索特定用户在某个时间间隔内按时间戳排序的所有更新。不同的用户可以存储在不同的分区上，对于每个用户，更新按时间戳顺序存储在单个分区上。

策略选择

对于弹性可伸缩性，使用基于范围的分片的系统很容易实现：只需拆分Region。假设您有一个范围区域[1，100），则只需选择一个分割点，例如50。然后将此区域分为 [1，50) 和 [50，100)。之后，将两个区域移动到两台不同的计算机中，并且负载达到平衡。

基于范围的分片可能会带来读写热点，但是可以通过拆分和移动消除这些热点。热点的拆分和移动落后于基于哈希的分片。但是总的来说，对于关系数据库，基于范围的分片是一个不错的选择。

相反，为使用基于哈希的分片的系统实现弹性可伸缩性非常昂贵。原因很明显。假定当前系统有三个节点，然后添加一个新的物理节点。在哈希模型中，n从3更改为4，这会导致较大的系统抖动。尽管您可以使用像Ketama这样的一致的哈希算法来尽可能减少系统抖动，但很难完全避免这种情况。这是因为在应用哈希函数后，数据将随机分配，并且调整哈希算法肯定会更改大多数数据的分配规则。

负载倾斜与消除热点

如前所述，哈希分区可以帮助减少热点。但是，它不能完全避免它们：在极端情况下，所有的读写操作都是针对同一个键的，所有的请求都会被路由到同一个分区。这种场景也许并不常见，但并非闻所未闻：例如，在社交媒体网站上，一个拥有数百万追随者的名人用户在做某事时可能会引发一场风暴。这个事件可能导致大量写入同一个键（键可能是名人的用户ID，或者人们正在评论的动作的ID）。哈希策略不起作用，因为两个相同ID的哈希值仍然是相同的。

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

然而，将主键进行分割之后，任何读取都必须要做额外的工作，因为他们必须从所有100个主键分布中读取数据并将其合并。此技术还需要额外的记录：只需要对少量热点附加随机数;对于写入吞吐量低的绝大多数主键来是不必要的开销。因此，您还需要一些方法来跟踪哪些键需要被分割。