algorithm - 并行/集群中图形节点分组的有效算法

Question

我正在考虑让玩家加入游戏的高效算法。由于会有大量玩家，因此算法应该是异步的(即可扩展到集群中任意数量的机器)。有细节:想象有一个无向图(每个节点都是一个玩家)。玩家之间的每条边意味着玩家可以参加同一场比赛，如果没有边则他们不能。我需要实现按照以下标准对玩家进行分组的算法:

• 每个玩家都有一个状态:“等待游戏”或“游戏中”。只有等待的玩家才能被分组到游戏中
• 每个游戏都有最小和最大玩家数量

我对实现的看法:该图将通过 NoSQL 数据库(来自集群中的不同机器)存储和访问。目前还没有特定的模式(有什么建议吗？)。此外，锁定对单个玩家的访问权限(又名悲观锁)也不是一种选择，因为它是减慢将尝试访问/收集相同玩家的其他进程的潜在瓶颈。

我的问题是:有人实现过这样的算法吗？有什么建议吗？

PS:我已经有了初步的想法，但首先想讨论/检查人们的建议。

谢谢!

编辑1:回应 Thomas Jungblut:使用游戏老虎机是一个有趣的想法，但(只要我理解正确)它在某些情况下可能行不通。 Fox 示例:每场比赛应该正好有 3 名球员。新的 6 名玩家(我们称他们为 A B C D E F，参见示例 1)按以下顺序一一进入图表/队列:A、B、E、F、C、D。

example 1

结果只会创建一个游戏(A、B、C)，外加 2 个空槽的游戏:(D) 和 (E, F)。但最佳应该是 2 场比赛:(A, C, D) 和 (B, E, F)，对吧？

Answer 1

我怀疑您没有正确考虑业务需求。

像带有任意条件的“最佳匹配”这样的短语对我来说是 NP 完全的。对于其中一个具有大型数据集的问题，您不会找到有效的精确解决方案，而只能找到合理的近似值。

次优匹配的成本是多少？您最终不得不等待更长的时间才能找到有人玩。不是真正的问题。

我会实现像这样简单的东西。有一个你正在设置的游戏队列。每个进来的人都试图进入第一场比赛，失败的是第二场比赛，失败的是第三场比赛，依此类推。如果找不到，则在队列末尾创建一个新游戏。游戏在达到最大尺寸时开始，或者在达到最小尺寸后经过固定时间后开始。当游戏开始时，它会从队列的前面移除。

有了这个决定，为什么您认为会有 100 万活跃玩家？

如果是因为你是一个有着远大梦想的初创公司，我强烈建议你需要专注于尽可能高效地解决你已知的问题。万一成功(说真的，你看过统计数据了吗？)，你可以稍后扩展。只有解决真正的问题才能大大提高你成功的几率，从可怕到微不足道。 (我并不是要气馁。但创业梦想确实是获得疯狂返回的几率很低。你采取的每一项行动都应该着眼于提高几率。)

如果您是一家成熟的游戏公司，有充分的理由相信您会达到这些数字，请继续阅读。

我不应该提及的一个显而易见的注意事项是，您将希望以相对快速的语言实现性能关键位。例如，如果您主要使用 Python 编写，那么这篇文章很适合使用 Java、Go 或 C++ 编写。

接下来，第一个不能缩放的是玩家信息。所以分发那个。这样做会减慢“玩家是否适合游戏”检查。所以添加每个游戏锁定，并异步分发该计算。在放弃和创建新游戏之前限制您尝试进入游戏的努力程度。

下一个瓶颈是游戏匹配计算。因此，继续将“此处的新游戏”分发到多台机器。现在一个玩家出现了，得到一个要检查的中央游戏列表，开始检查它们。为避免瓶颈，玩家应随机排序等待游戏列表。

网络瓶颈是要求该列表。该列表大部分是只读的，因此您可以只使用 Redis 的复制实例。写入(用于新游戏和标记游戏开始)可以交给 master，读取可以根据需要分布在任意多台机器上。玩家将随机打一个 Redis 副本，得到一个列表，随机排序。

如果达到这种规模，我会感到震惊。如果您超过了它，我会将后续步骤(例如对 Redis 进行分片)留给您。

随机笔记。这是一个体面的面试问题。 “设计这个简单的东西。让它扩展。让它扩展更多。让它扩展更多。”如果你真的在寻找一个了解分布式性能的人，那是一个很好的测试。 (但前提是面试官能够分辨好坏答案。)