Course All lectures for ZH purposes - Lecture: 分片：反面

2.1 如何分片减速N次？

您可以像这样分片并减慢 N 次：

按顺序发送 docs00...docs15 请求，而不是并行发送。
在简单查询中，不通过 key进行选择，WHERE something=234。

在这种情况下，序列化部分（serial）不是 1% 也不是 5%，而是现代数据库中的大约 20%。如果您使用极其高效的二进制协议访问数据库或将其作为动态库链接到 Python 脚本中，您还可以获得 50% 的序列化部分。

一个简单请求的其余处理时间将被解析请求、准备计划等不可并行化的操作占用。即不读记录变慢。

如果我们将数据分成 16 个表并按顺序运行，例如 PHP 编程语言中的习惯（它不太擅长启动异步进程），那么我们将减速 16 倍。而且，也许甚至更多，因为还将添加网络往返。

突然间，分片时编程语言的选择变得很重要。

请记住编程语言的选择，因为如果您按顺序向数据库（或搜索服务器）发送查询，那么加速从何而来？相反，会出现放缓。

2.2 关于半自动

在某些地方，信息技术的复杂性激发了 chthonic 恐怖。例如，开箱即用的 MySQL 肯定没有实现对某些版本的分片，但是，战斗中使用的数据库的大小增长到不合适的值。

面对个别DBA的苦难人性已经被折磨了很多年，白手起家写了几个不好的sharding解决方案。之后，编写了一种或多或少体面的分片解决方案，称为 ProxySQL（MariaDB/Spider、PG/pg_shard/Citus，...）。这是这个斑点的一个众所周知的例子。

ProxySQL 作为一个整体，当然是一个成熟的企业级开源解决方案，用于路由等。但是要解决的任务之一是数据库的分片，它本身不能以人类的方式分片。你看，没有“shards = 16”开关，你要么必须重写应用程序中的每个请求，并且有很多地方，要么在应用程序和数据库之间放置一些中间层，看起来：“嗯... 从文档中选择 *？是的，它必须分成 16 个小的 SELECT * FROM server1.document1, SELECT * FROM server2.document2 - 使用这样的登录名/密码到此服务器，再到另一个。如果一个人没有回答，那么……”，等等。这恰恰可以通过中间斑点来完成。它们略低于所有数据库。对于 PostgreSQL，据我了解，

配置每个特定的补丁是一个单独的大主题，无法放在一份报告中，因此我们将只讨论基本概念。让我们更好地谈谈嗡嗡声的理论。

2.3 绝对完美的自动化？

在这个字母F()中分片的情况下变高的整个理论，基本原理总是大致相同：shard_id = F(object)。

分片 - 它是关于什么的？我们有 20 亿条记录（或 64 条）。我们想把它们分成几块。出现了一个意想不到的问题——如何？我应该根据什么原则将我的 20 亿条记录（或 64 条）分散到我可用的 16 台服务器上？

我们潜在的数学家应该建议，最终总会有一些神奇的功能，对于每个文档（对象、行等），将决定将它放在哪一块。

深入数学，这个函数总是不仅取决于对象本身（行本身），还取决于外部设置，例如分片总数。对于每个对象必须告诉将其放置在何处的函数，返回的值不能超过系统中的服务器数。并且功能略有不同：

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

但是我们不会深入研究这些个别函数的荒野，我们只会讨论 F() 是什么神奇函数。

2.4 什么是 F()？

他们可以想出很多不同的很多不同的实现机制。示例摘要：

F = rand() % nums_shards 数量
F = somehash(object.id) % num_shards
F = 对象.日期 % num_shards
F = object.user_id % num_shards
...
F = shard_table [ somehash() |... object.date |... ]

一个有趣的事实——你可以自然地随机分散所有数据——我们将下一条记录扔到任意服务器、任意核心、任意表中。这样做不会有太多快乐，但它会起作用。

有一些更智能的方法可以通过可重现甚至一致的哈希函数进行分片，或者通过某些属性进行分片。让我们来看看每种方法。

F = 兰德（）

四处散布不是很正确的方法。一个问题：我们将 20 亿条记录随机分散在一千台服务器上，而且我们不知道记录在哪里。我们需要拉出 user_1，但我们不知道他在哪里。我们访问一千台服务器并对所有内容进行分类——不知何故这是低效的。

F = somehash()

让我们用大人的方式来打散用户：从user_id计算出可重现的hash函数，除以服务器的个数取余，马上联系到想要的服务器。

我们为什么要这样做呢？然后，我们有一个高负载，没有其他东西适合一台服务器。如果合适，生活就会如此简单。

太好了，情况已经好转了，为了获得一条记录，我们提前去一个已知的服务器。但是，如果我们有一个键范围，那么在这个整个范围内，我们需要遍历键的所有值，并且在极限情况下，要么转到与范围内的键一样多的分片，要么甚至到每个服务器。当然，情况有所改善，但并非针对所有请求。一些查询已受到影响。

自然分片（F = object.date % num_shards）

有时，也就是通常，95% 的流量和 95% 的负载是具有某种自然分片的请求。例如，95% 的条件社交分析查询仅影响最近 1 天、3 天、7 天的数据，其余 5% 涉及最近几年。但是 95% 的请求因此自然地按日期分片，系统用户的兴趣集中在最近几天。

在这种情况下，您可以按日期划分数据，例如按一天划分，然后根据对某一天的报告或对象的请求的响应从这一天到这个分片。

生活正在改善——我们现在不仅知道特定物体的位置，而且我们还知道范围。如果我们被要求的不是日期范围，而是其他列的范围，那么，当然，我们将不得不遍历所有分片。但是按照游戏规则，我们只有5%的这样的请求。

看起来我们已经想出了一个理想的解决一切的办法，但是有两个问题：

当 95% 的请求仅涉及上周时，此解决方案是为特定案例量身定制的。
由于 95% 的请求涉及上周，因此它们将全部落在为上周提供服务的一个分片上。这个碎片会融化，而其他所有碎片在此期间都将闲置。同时，你也不能扔掉它们；档案数据也必须存储起来。

并不是说这是一个糟糕的分片方案——我们切断了热数据，但是，需要对最热的分片做一些事情。

问题是通过滑稽动作、跳跃和药膏来解决的，即增加燃烧当天的副本数量，然后在这一天成为过去并进入档案时逐渐减少副本数量。没有理想的解决方案称为“您只需要以错误的方式使用神奇的哈希函数将数据分布在集群上”。

2.5 支付的价格

形式上，我们知道现在我们知道“一切”。的确，我们不知道一种巨大的头痛和两种较小的头痛。

1. 单纯痛：严重涂抹

这是教科书中的一个例子，战斗中几乎不会出现，而是突然出现。

以带日期为例，仅以不带日期为例！
无意的不均匀（可感知）分布。

他们选择了sharding机制，和/或数据发生了变化，当然PM没有传达需求（我们代码没有错误，PM总是不报告需求），以及分发变得异常不均匀。也就是说，他们错过了标准。

要捕捉，您需要查看碎片的大小。当我们的一个分片过热或变得比其他分片大 100 倍时，我们肯定会看到问题。您可以简单地通过更换密钥或分片功能来修复它。

这是一个简单的问题，说实话，我不认为至少一百个人中会有至少一个人会在生活中遇到这个问题，但突然间它至少会帮助某人。

2.“无敌”之痛：聚合、加入

如何进行选择，将一个表中的十亿条记录加入另一个表中的十亿条记录？

如何“快速”计算... aaa 和 bbb 之间的 randcol 在哪里？
如何“聪明地”做... users_32shards JOIN posts_1024 分片？

简答：不行，受罪！

如果您将 10 亿条记录分配给第一个表中的一千台服务器以便它们更快地工作，并且在第二个表中也这样做，那么自然地一千到一千台服务器应该成对地相互通信。一百万个连接将无法正常工作。如果我们向不适合分片的数据库（搜索、存储、文档存储或分布式文件系统）发出请求，这些请求将大幅减慢。

很重要的一点是，有些请求总是会抹黑不成功，会变慢。尽量减少他们的百分比很重要。因此，无需对 10 亿乘 10 亿的记录进行巨大的连接。如果可以将一个小表复制到所有节点，相对于您加入一个巨大的共享表，您应该这样做。例如，如果连接实际上在某种程度上是本地的，则可以将用户和他的帖子并排放置，以相同的方式对它们进行分片，并在同一台机器上进行所有连接——你需要这样做.

这是为期三天的单独课程，所以让我们继续讨论最后的地狱般的痛苦和处理它的不同算法。

2.6. 复杂/长期痛苦：重新分片

做好准备：如果您是人生中第一次对数据进行分片，那么平均而言您还会分片五次。

不管你配置多少个集群，你仍然需要重新分片。

如果你非常聪明和幸运，那么至少过度分片一次。但是一旦你确定了，因为在你认为 10 个单位对用户来说足够的那一刻，那个时候有人写了一个 30 个的请求，并计划请求 100 个单位的未知资源。碎片永远不够用。对于第一个分片方案，在任何情况下，您都会错过 - 您总是必须增加要添加的服务器数量，或者做其他事情 - 通常，以某种方式重新打包数据。

如果我们有 2 的幂次方就好了：有 16 个服务器分片，现在是 32 个。如果是 17 就更有趣了，现在是 23——两个非常质数。数据库是怎么做到的，也许它们内部有某种魔力？

正确答案是：不，里面没有魔法，他们里面有地狱。

接下来，我们会考虑什么可以“用手”来完成，或许我们会理解为“作为一台自动机器”。

在额头#1。搬迁一切

对于所有对象，我们考虑 NewF(object)，转移到一个新的分片。

NewF()=OldF() 匹配的机会很低。

让我们涵盖几乎所有内容。

哦。

我希望没有将所有 20 亿条记录从旧分片转移到新分片这样的地狱。幼稚的做法是可以理解的：有 17 台机器，6 台机器加入集群，整理出 20 亿条记录，他们从 17 台机器转移到 23 台机器。每 10 年一次，您甚至可以做到。但总的来说，这是一个糟糕的举动。

在额头#2。搬迁一半

下一个幼稚的改进——让我们放弃这样一个愚蠢的方案——将禁止 17 辆汽车重新分片为 23 辆，我们将始终将 16 辆汽车重新分片为 32 辆汽车！然后，根据理论，我们将不得不移动恰好一半的数据，实际上我们也可以这样做。

对于所有对象，我们考虑 NewF(object)，转移到一个新的分片。

严格来说是 2^N，现在严格来说是 2^(N+1) 个碎片。

匹配NewF()=OldF()的概率是0.5。

让我们传输大约 50% 的数据。

最优，但仅适用于 2 的幂。

原则上，一切都很好，除了在汽车数量方面绑定到 2 的幂。奇怪的是，这种天真的方法可以奏效。

请注意，在这种情况下，按 2 的幂对集群进行额外拆分也是最佳选择。在任何情况下，将 16 台机器添加到 16 台机器的集群中，我们都必须移动一半的数据 - 恰好一半并移动。

好吧，但人类真的没有发明任何其他东西吗——这个问题来自好奇心。

更有趣#3。一致性哈希

当然这里需要一张关于consistent hashing的带圆圈的图。

如果你google一下“consistent hashing”，那么肯定会出来一个圆圈，所有的结果都是圆圈填充的。

想法：让我们在圆圈上画出分片标识符（散列），并在顶部标记散列的服务器标识符。当您需要添加服务器时，我们在圆圈上放置一个新点，然后将靠近它的点（并且只有靠近它的点）重新定位。

添加分片时：我们不是查看所有内容，而是查看 2 个“邻居”，平均移动 1/n。

删除分片时：我们只查看被删除的分片，我们只移动它。有点最优。

在添加分片时在最小化流量方面非常有效，在正常数据平衡方面绝对令人厌恶。因为当我们散列所有这些分配给大量机器的对象时，我们做的相对不均匀：圆周围的点间隔不均匀，每个特定节点的负载可能与其他节点非常不同。

这个问题被虚拟节点的最后一行解决了。圆上的每个节点，每个服务器都由一个以上的点表示。通过添加服务器、分片等，我们正在添加几个点。每次我们删除一些东西时，我们相应地删除了几个点并移动了一小部分数据。

我用圆圈谈论这个空间，因为，例如，这样的方案在 Cassandra 内部。也就是说，当她开始在节点之间追记录时，知道圈子在看着你，很可能不赞成。

然而，与第一种方法相比，生活有所改善 - 在添加/删除分片时，我们已经查看了不是所有记录，而是仅查看了一部分，并且仅移动了一部分。

注意，问题是：是否可以进一步改进？而且还能提高加载分片的均匀性？他们说这是可能的！

更有趣#4。会合/HRW

下一个简单的想法（材料是教育性的，所以没有什么复杂的）：shard_id = arg max hash(object_id, shard_id)。

为什么它被称为 Rendezvous hashing 我不知道，但我知道它为什么被称为 Highest Random Weight。很容易想象它是这样的：

例如，我们有 16 个分片。对于每个需要放在某处的对象（字符串），我们根据分片编号中的对象计算 16 个哈希值。谁拥有最高的哈希值，谁就获胜。

这就是所谓的 HRW 哈希，又名 Rendezvous 哈希。像棍子一样笨，计算分片数量的方案首先比圆圈更容易观察，另一方面给出了均匀的负载。

唯一不利的是，添加新分片对我们来说变得更糟了。存在这样的风险，即在添加新分片时，我们仍有一些哈希值会发生变化，因此可能有必要审查所有内容。碎片去除技术没有太大变化。

另一个问题是它的计算量很大，有大量的分片。

更有趣#5。更多技巧

有趣的是，研究并没有停滞不前，谷歌每年都会发布一些新的太空技术：

跳跃哈希 - 谷歌 '2014。
多探头—Google '2015。
磁悬浮谷歌 '2016。

如果你对这个主题感兴趣，你可以阅读很多论文。我提出这个数据是为了明确问题没有解决，没有可以在所有数据库中实施的超级解决方案。直到现在，人们都在为论文辩护。

结论

有一个重要的基本技术叫做分片，以 Gallius Julius Caesar 的名字命名：“分而治之，统治并分而治之！”。如果数据放不下一台服务器，就需要拆分成20台服务器。

了解了所有这些之后，人们应该会觉得最好不要分片。如果你决定最好不要分片，这是正确的感觉。如果您可以以 100 美元的价格向服务器添加内存并且不分片任何东西，那么您应该这样做。分片时，会出现一个复杂的分布式系统，数据来回传递，数据堆积在不知何处。能避免就一定要避免。

最好不要手工完成，“基础”（搜索，DFS，...）可以自行分片更好。无论如何，迟早会出现高负载，并且必须以某种方式拆分数据。这不是事实，即使基地可以自己做，你也不会遇到任何问题。记住算法原教旨主义——你需要了解里面的一切是如何运作的。