文章来源于网络收集而来，版权归原创者所有，如有侵权请及时联系！

键值数据的分区

发布于 2024-08-24 16:53:17 字数 4161 浏览 0 评论 0 收藏 0

假设你有大量数据并且想要分区,如何决定在哪些节点上存储哪些记录呢？

分区目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分享数据和负载，那么理论上 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 所示。

图 6-3 按哈希键分区

这种技术擅长在分区之间分配键。分区边界可以是均匀间隔的，也可以是伪随机选择的（在这种情况下，该技术有时也被称为 一致性哈希（consistent hashing） ）。

一致性哈希
一致性哈希由 Karger 等人定义。【7】用于跨互联网级别的缓存系统，例如 CDN 中，是一种能均匀分配负载的方法。它使用随机选择的 分区边界（partition boundaries） 来避免中央控制或分布式一致性的需要。请注意，这里的一致性与复制一致性（请参阅第 5 章）或 ACID 一致性（参阅第 7 章）无关，而是描述了重新平衡的特定方法。
正如我们将在重新平衡分区中所看到的，这种特殊的方法对于数据库实际上并不是很好，所以在实际中很少使用（某些数据库的文档仍然指的是一致性哈希，但是它往往是不准确的）。因为有可能产生混淆，所以最好避免使用一致性哈希这个术语，而只是把它称为 散列分区（hash partitioning） 。

不幸的是，通过使用 Key 散列进行分区，我们失去了键范围分区的一个很好的属性：高效执行范围查询的能力。曾经相邻的密钥现在分散在所有分区中，所以它们之间的顺序就丢失了。在 MongoDB 中，如果您使用了基于散列的分区模式，则任何范围查询都必须发送到所有分区【4】。Riak 【9】，Couchbase 【10】或 Voldemort 不支持主键上的范围查询。

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

组合索引方法为一对多关系提供了一个优雅的数据模型。例如，在社交媒体网站上，一个用户可能会发布很多更新。如果更新的主键被选择为 (user_id, update_timestamp) ，那么您可以有效地检索特定用户在某个时间间隔内按时间戳排序的所有更新。不同的用户可以存储在不同的分区上，对于每个用户，更新按时间戳顺序存储在单个分区上。