👨🏿 🕴🏿 🔀 Apache Ignite中的数据分发 📌 👏 🤜🏻

你好！这篇文章是我在Apache Ignite社区会议上的同名演讲的简短摘要。您可以在此处观看完整的视频版本以及问题和答案，并在此处下载幻灯片。在报告中，我尝试通过示例展示如何在Apache Ignite中分发数据。

你为什么需要分发任何东西

任何需要数据存储和处理的系统的发展的相当标准的历史就是一定的上限。要么有很多数据，而且它们没有物理地放置在存储设备上，要么负载正在以这样的速度增长，即一台服务器不再能够处理如此多的请求。经常发生两种情况。

通常，它们采用两种解决方案之一：分片现有存储，或切换到分布式数据库。两种解决方案都有许多共同的特征，最明显的是使用多个节点来处理数据。此外，我将许多节点称为拓扑。

拓扑节点之间的数据分布问题可以表述为一组要求，我们的分布必须满足以下要求：

需要一种算法，该算法将允许拓扑和客户端应用程序的所有节点就特定对象（或键）位于哪个或哪些节点上得出相同的结论。
分布均匀。节点之间的数据分布越均匀，这些节点上的负载分布就越均匀。在这里，我假设我们的节点具有大约相同的资源。
最小的分配变化。当由于节点故障而更改拓扑时，分布中的更改应仅涉及位于该节点上的数据。另外，应注意，当拓扑中包含新节点时，拓扑中已经存在的节点之间不应进行数据交换。

实现前两个要求相当容易。

一种常见的方法，通常在平衡功能相同的服务器之间的负载时使用，取模N，其中N是拓扑中的节点数，节点号与其标识符一一对应。然后，我们要做的就是使用哈希函数将对象的键表示为数值，然后将剩余的除以N所得的值，

该图显示了16个键在3个节点上的分布。可以看出，这种分布是均匀的，并且获得对象节点的算法很简单，并且可以保证如果拓扑的所有节点都使用此算法，则对于相同的密钥和相同的N将获得相同的结果。

但是，如果将第4个节点引入拓扑，会发生什么？

我们的功能发生了变化，现在我们将除数的其余部分除以4，而不是3。如果函数发生了变化，则分布也发生了变化，而且变化很大。

在这里，三个节点的拓扑的先前版本的对象的先前位置显示为红色，四个节点的拓扑的新版本的对象的位置分别为绿色。这与通常的diff文件非常相似，但是我们有节点而不是文件。

不难看出，数据不仅已移动到新节点，而且已经在拓扑中的节点之间交换了数据。那些。我们观察到节点之间的虚假流量，并且未满足最小分布变化的要求。

考虑到列出的要求，两种解决数据分发问题的流行方法如下：

一致的哈希
最大随机权重算法（HRW），也称为集合哈希。

这两种算法都非常简单。他们在Wikipedia上的描述可分为几句话。尽管很难说出它们是显而易见的。对于那些感兴趣的人，我建议阅读原始文章“ 一致性哈希和随机树：用于缓解万维网上的热点的分布式缓存协议和基于名称的集合点映射方案”。在我看来，最可理解的是，在本斯坦福课程中传达了一致哈希算法的思想。

让我们更详细地了解这些算法。

一致的散列

一致性哈希算法的基础是将节点和存储的对象都映射到同一标识符空间。这使我们看似不同的实体，对象和节点具有可比性。

为了获得这样的映射，我们只需将相同的哈希函数应用于对象的键和节点的标识符。该节点的哈希函数的结果将称为令牌，这对我们以后将很有用。

我们以圆圈的形式表示我们的标识符空间，即我们仅假设最大标识符值紧随最小标识符值。

现在，为了确定对象在哪个节点上，您需要从其键中获取哈希函数的值，然后简单地沿圆周顺时针移动，直到我们在途中遇到节点的令牌。运动方向并不重要，但必须固定。

假想的顺时针运动在功能上等同于节点令牌排序的数组中的二进制搜索。

在该图中，特定颜色的每个扇区反映了特定节点负责的标识符空间。

如果我们添加一个新节点，则

它将把扇区之一分为两部分，并完全接管相应的密钥。

在此示例中，节点3接管了节点1的部分密钥。

如您所见，这种方法使对象在节点之间的分布相当不均匀，因为它高度依赖于节点本身的标识符。如何改进这种方法？

您可以将多个令牌分配给节点（通常为数百个）。例如，这可以通过为节点引入许多哈希函数（每个令牌一个）或将相同的哈希函数重复应用于上一步中获得的令牌来实现。但是我们决不能忘记冲突。不应有两个具有相同令牌的节点。

在此示例中，每个节点具有4个令牌。

还有什么要注意的重要事项：如果要在节点离开拓扑的情况下确保数据的安全性，则需要将密钥存储在多个节点上（所谓的副本或备份）。对于一致性哈希算法，副本将是圆上的以下N-1个节点，其中N是复制因子。当然，节点的顺序应由特定的令牌（例如，由第一个令牌）确定，因为当对每个令牌使用多个令牌时，节点的排列可能会有所不同。注意该方案：它没有明确的节点重复模式。

关于改变拓扑时分布的最小变化的要求，因为圆上节点的相互顺序不变，所以可以满足。那些。从拓扑中删除节点不会更改其余节点之间的顺序关系。

集合哈希

集合哈希算法似乎比一致性哈希更简单。该算法基于顺序关系不变的相同原理。但是，我们没有使节点和对象具有可比性，而是仅使特定对象的节点具有可比性。那些。我们为每个对象独立确定节点之间的顺序关系。

同样，哈希可以帮助我们实现这一点。但是现在，为了确定给定对象O的节点N的权重，我们将对象的标识符与节点的标识符混合，并从该混合中获取哈希值。为每个节点完成此操作后，我们获得了一组权重，这些权重用于对节点进行排序。

原来是第一个节点，它将负责存储对象。

由于拓扑的所有节点都使用相同的输入数据，因此它们的结果将相同。满足第一个要求。

考虑一个例子。在这里，我们对于三个不同的键在三个节点之间具有顺序关系。黄色表示权重最高的节点，即最终将负责特定密钥的节点。

将另一个节点添加到拓扑。

我故意将其放在对角线上，以考虑所有可能的选择。此处，以绿色显示的节点3进入了拓扑。因此，每个键的节点的权重分布已更改。红色表示更改了特定键在列表中位置的节点，因为这些节点的权重小于添加的节点的权重。但是，此更改仅影响其中一个键K3。

让我们从拓扑中派生出一个节点。

再次，更改仅影响一个键，这次是K1。其余对象不受影响。与一致哈希一样，原因是任何一对节点之间的顺序关系不变。那些。满足最小分布变化的要求，并且节点之间没有虚假流量。

与一致的哈希（如令牌）相比，集合的分布看起来非常好，并且不需要其他技巧。

如果我们要支持复制，则列表中的下一个节点将是该对象的第一个副本，下一个节点将是第二个副本，依此类推。

Apache Ignite中如何使用集合点哈希

所谓的相似性函数负责在Apache Ignite中分配数据（请参阅AffinityFunction接口）。默认实现是集合点哈希（请参阅RendezvousAffinityFunction类）。

您需要注意的第一件事是Apache Ignite不会将存储的对象直接映射到拓扑节点。相反，引入了另一个概念-分区。

分区是对象和复制单元的容器。此外，特定高速缓存的分区数（这是熟悉的数据库中表的类似物）是在配置阶段设置的，并且在高速缓存生命周期中不会更改。

因此，我们可以使用有效的模除法在分区上显示对象，并使用集合哈希在节点上显示分区。

因为由于缓存的分区数是一个常数，因此我们可以一次计算节点的分区分布，并缓存结果，直到拓扑更改为止。

每个节点独立地计算此分布，但是在具有相同输入数据的所有节点上，此分布将是相同的。

分区可以有多个副本，我们称它们为备份。主分区称为主分区。

为了按节点在分区和分区之间最佳地分配密钥，必须满足以下规则：分区的数量应显着大于节点的数量，而密钥的数量应显着大于分区的数量。

Ignite中的缓存被分区和复制。

在分区缓存中，备份数量是在缓存创建阶段设置的。分区-主分区和备份分区-在节点之间平均分配。这样的缓存最适合处理操作数据，因为提供最佳的写入性能，它直接取决于备份的数量。通常，备份越多，必须确认密钥记录的节点就越多。

在此示例中，缓存具有一个备份。那些。我们可以丢失一个节点而不丢失数据，因为分区备份永远不会与主分区或其其他备份存储在同一节点上。

在复制的缓存中，备份数始终等于拓扑节点数减去1。即，每个节点始终包含所有分区的副本。

这样的缓存最适合处理很少更改的数据（例如目录），并提供最大的可用性，因为我们可以丢失N-1个节点（在本例中为3个）而不会丢失数据。同样在此选项中，如果我们允许从主分区和备份中读取数据，我们将获得最大的读取性能。

Apache Ignite中的数据托管

为了获得最佳性能，一个重要的概念是并置。共置是将任何对象放置在同一位置。在我们的例子中，对象是存储在缓存中的实体，而位置是节点。

如果对象是由具有相同亲和力功能的分区分配的，则逻辑上具有相同亲和力键的对象将属于同一分区，因此属于同一节点。在Ignite中，这称为亲和共置。

默认情况下，关联键是对象的主键。但是在Ignite中，您可以将对象的任何其他字段用作关联键。

并置可以显着减少在节点之间发送的用于执行计算或SQL查询的数据量，这自然可以减少花在这些任务上的时间。通过示例考虑此概念。

让我们的数据模型由两个实体组成：订单（Order）和订单位置（OrderItem）。一个订单可以对应许多项目。订单和订单项标识符是独立的，但是订单项具有引用相应订单的外键。

假设我们需要执行一些任务，该任务必须针对每个订单执行该订单位置的计算。

默认情况下，相似性键是主键。因此，订单和仓位将根据其主键在节点之间分配，我记得这些主键是独立的。

在图上，订单用正方形表示，位置用圆圈表示。颜色表示该物料属于订单。

通过这种数据分布，我们的假设任务将被发送到所需订单所在的节点，然后它将需要从所有其他节点读取位置，或将子任务发送至这些节点并获得计算结果。这是可以避免的不必要的网络交互。

如果我们告诉Ignite订单商品必须与订单本身放置在相同的节点上，该怎么办？收集数据？

作为位置的相似性键，我们使用外键OrderId，并且在计算记录所属的分区时将使用此字段。而且，在分区内部，我们总是可以通过主键找到对象。

现在，如果两个缓存（Order和OrderItem）使用具有相同参数的相同的相似性函数，则我们的数据将在附近，并且我们将不需要遍历网络来获取订单项。

Apache Ignite中的相似性配置

在当前实现中，相似性功能对象是缓存配置参数。

创建时，亲和函数本身采用以下参数：

分区数；
备份数（实际上，这也是缓存的配置参数）；
备用过滤器；
标记excludeNeighbors。

这些设置无法更改。

随着分区和备份数量的增加，一切似乎都很清楚。稍后我将讨论备份过滤器和excludeNeighbors标志。

在运行时，输入亲和力函数接收当前的群集拓扑-本质上是群集节点列表-并根据我在谈到集合哈希算法时展示的示例，按节点计算分区分布。

对于备份过滤器，这是一个谓词，它使您可以防止相似性函数将备份分区分配给该谓词返回false的节点。

例如，假设我们的物理节点（服务器）位于数据中心的不同机架中。通常，每个机架都有自己独立的电源...

...如果丢失机架，则会丢失数据。

在此示例中，我们丢失了一半的分区。

但是，如果我们设置了正确的备份过滤器，则分发将以这种方式发生变化

……如果机架丢失，则不会丢失数据，并且仍然可用。

excludeNeighbors标志执行类似的功能，实际上，它是一种特定情况的缩写。

通常，多个Ignite节点在同一物理主机上运行。这种情况与数据中心机架的示例非常相似，只是现在我们正在与主机丢失（而不是机架丢失）对抗数据丢失。

其余部分相同。您可以使用备份过滤器来实现此行为。该标志是历史遗留物，可以在下一个主要版本的Ignite中删除。

似乎我谈到了使用Apache Ignite的开发人员需要了解的所有功能和数据分发。

最后，让我们看一个根据3个节点的拓扑分布16个分区的示例。为了简单明了，我们认为分区没有备份。

我只是参加了一个小测试，为我带来了真正的分布：

如您所见，分布的均匀性并不理想。但是，随着节点和分区数量的增加，错误将明显降低。必须遵守的主要规则是分区数明显大于节点数。现在，在Ignite中，分区缓存的默认分区数为1024。

现在将新节点添加到拓扑中。

政党的一部分移交给了他。同时，观察到分配变化最少的要求：新节点接收部分分区，而其他节点不交换分区。

我们从拓扑中删除了最初存在于其中的节点：

现在，与零节点关联的所有分区都在拓扑的其他节点之间重新分配，而没有违反我们的分配要求。

如您所见，解决复杂问题的方法通常基于相当琐碎的想法，尽管并非完全显而易见。所描述的解决方案已在大多数分布式数据库中使用，并且表现出色。但是这些决定是随机的，因此分布的均匀性远非理想。是否可以在不牺牲性能和其他分配要求的情况下提高均匀性？问题仍然悬而未决。