我正在处理一个项目，它涉及到许多客户机连接到一个服务器（如果需要的话，服务器）上，该服务器包含一系列图形信息（节点属性和边）。他们可以随时选择引入一个新的节点或边，然后从整个图中请求一些信息（两个节点之间的最短距离、图着色等）。
这显然是很容易开发的朴素算法，但后来我试图学习规模，使它可以处理许多用户更新图形的同时，许多用户要求从图形的信息，并有可能处理一个非常大的（500k+）节点，可能还有大量的边。
我可以预见的挑战：
随着一个不断更新的图形，我需要处理整个图形，每次有人要求信息…这将增加计算时间和延迟相当多
对于一个非常大的图，计算时间和延迟显然要高得多（据我所知，一些公司通过批量处理大量结果并用索引存储这些结果以备日后使用……但由于我的图不断更新，用户需要最新的信息，这不是一个可行的解决方案）
大量用户请求信息，这将是服务器上的一个相当大的负载，因为它必须处理图形很多次
我如何开始面对这些挑战？我看过hadoop和spark，但它们似乎有高延迟的解决方案（使用批处理）或者解决图形不经常变化的问题的解决方案。
我的想法可能是处理图的不同部分并对它们进行索引，然后跟踪图的更新位置并重新处理图的该部分（一种分布式动态规划方法），但我不确定这是否可行。
谢谢！
2条答案
按热度按时间7kjnsjlb1#
我如何开始面对这些挑战？
我要回答这个问题，因为它很重要。你列举了一些有效的问题，所有这些问题你都需要处理，我都不会直接解决。
为了开始，您需要完成对语义的定义。你可能认为你已经完成了，但你还没有。当你说“用户想要最新的信息”时，“最新的”是什么意思
“过去的一切”，这会导致将每个事务全部序列化到图中，从而使答案反映出每一条可能的信息？
或者“超过x秒前处理的所有事务”，这会导致部分序列化，即当前的多个数据库状态会逐渐序列化到过去？
如果1。是必需的，根据应用程序的不同，代码中可能存在不可避免的热点。由于事务不一致，您可以立即获得有关何时回滚事务的信息。
如果2。是可以接受的，你有可能得到更好的表现。不过，也有一些权衡。在某些情况下，您必须在初始接受后回滚事务。
一旦你回答了这个问题，你就开始面对你的挑战，我想，还会有更多的问题。
zzlelutf2#
我对图表了解不多，但我对网络有点了解。
我要记住的一条规则是。。。如果可以让客户机来做，就不要在服务器端做工作。
服务器需要做的就是维护原始数据，为客户端提供原始数据，并在数据更改时通知连接的客户端。
客户机可以拥有自己的原始数据副本，然后根据他们知道的内容和收到的更新生成计算/可视化结果。
客户只需要知道是否有新记录或旧记录是否已更改。
如果出于某种原因，您必须在服务器端处理数据并将其发送给客户机（例如，客户机是第三方软件，不是您可以控制的东西，它需要处理的数据，而不是原始数据），那么，您确实有点问题，所以请使用一个糟糕的服务器。。。或3或30。在这种情况下，我必须确切地知道数据是什么以及它是如何被处理的，以便对缩放配置提出任何建议。