分布式BiPartite图

Question

我有一个用例，其中我有一个双部图。将一种节点称为“A型”，另一种称为“B型”。现在，当一个Type A节点被添加时，它会根据B型节点的准则形成一些边(通常B型节点有多少条现有的边？)类型A节点的添加是一致的(例如，对于每个HTTP请求)。所使用的条件非常简单，因为HTTP请求的延迟不能很大。

在某个时间间隔X之后，一个进程运行在获取图形快照的背景中，并根据一个更优的准则“重组”边缘，运行时间要长得多。现在，在完成重组之后，它需要更新为HTTP请求提供服务的进程，使其达到图形的新状态。

现在，这种情况发生在分布式环境中。有几个盒子为HTTP请求提供服务。

1. 如何存储分布式图形？

一种选择是在Redis中存储边缘和节点。然后，当请求与类型A节点一起出现时，首先获取所有B类型节点(不会太多)，形成所有边缘并再次保存Redis中的边缘。问题是，约束条件是B型节点可以具有的边数。因此，如果一个B型节点有4个边，限制为5，并且两个并发请求试图添加一个边，那么其中一个就会失败。我看到这样做的唯一方法是

(1)在Redis或

(2)对图进行切分，使B型节点的子集总是由一个框(次优)获取。

1. 如何在最优周期之后更新分布式图？

最优周期获取图的快照，并对边进行优化(重新设置它们)。现在这需要一些时间。因此，在此期间，HTTP请求还将节点添加到Redis中的快照中。“合并”这两个图的最佳方法是什么。

一种选择是在最优周期运行之后，它

(1)设置一个标志，表示暂时停止在HTTP请求中添加新节点(这些请求很可能会阻塞或发送异步消息，稍后通过Kafka/RabbitMQ发送给调用方)

(2)添加在运行过程中添加的任何新节点(如果运行时间为30秒，并且每秒钟添加一个新节点，则需要增加30个不在其快照中的节点)。

(3)替换Redis中的图边。

(4)解除标志以重新开始处理HTTP请求。

然而，当HTTP请求被阻止处理时，这个过程会导致HTTP请求的延迟太高，这是不好的。

Answer 1

别抓锁。您的图表必须始终可用，用于阅读和更新。

要执行离线重组(30秒)，您需要立即将图形分割成两个副本。也就是说，一个网络得到，然后你分裂，然后第二个得到，它不会注意到一个不寻常的延迟。实现这一目标的一个典型技术是COW，抄写。

现在你有两个不同的图表，一个被在线网络请求改变，另一个被重组。另外还会记录Web请求。

一旦重组完成，根据重组后的图形重放所有记录在案的web请求。在此过程中，会有更多的请求到达，所以请一直保持到队列耗尽为止。

此时，您可以安全地删除在线图，并将离线重组图切换到联机请求中。

就每个节点K边的极限而言，只需在重组过程中将其放宽到K+3或2K或其他地方，并将K以外的边缘修剪为最后一步，然后再将图形按到在线服务中。