並行/集羣圖節點分組的高效算法

Question

我在考慮將玩家加入遊戲的高效算法。由於會有大量玩家，因此該算法應該是異步的（即可擴展到羣集中的任意數量的機器）。 有細節： 想象一下，有一個無向圖（每個節點是一個球員）。玩家之間的每條邊都意味着玩家可以參加同一場比賽，如果沒有優勢，他們就不能參加比賽。我需要實現算法，按照以下標準對玩家進行分組：

• 每個玩家都有一個狀態：「等待遊戲」或「在遊戲中」。只有等待玩家應該分爲遊戲
• 每場比賽都有球員

我對實現的想法最小和最大行數：在集羣中 圖形將被存儲和訪問過的NoSQL數據庫（從不同的機器）。還沒有特別的模式（有什麼建議嗎？）。同時鎖定對單個玩家的訪問（又名悲觀鎖）不是一種選擇，因爲這是一個潛在的瓶頸，可能會放慢其他嘗試訪問/收集同一玩家的進程。

我的問題是：有沒有人實現過這樣的算法？有什麼建議麼？ PS：我已經有了一些想法，但首先想要討論/檢查人們的建議。

謝謝！

EDIT1： 針對托馬斯Jungblut： 使用遊戲插槽是一個有趣的想法，但（只要我理解正確的話），可能無法在某些情況下工作。 Fox例子：每個遊戲應該有3個玩家。新6個播放器（讓ABCDEF調用它們，見的exaple 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-complete。您不會爲其中一個擁有大數據集的人提供高效的精確解決方案，而僅僅是一個合理的近似值。

次優匹配的成本是多少？你不得不等待稍長時間才能找到一個人玩。不是一個真正的問題。

我會實現一些簡單的事情。有一個你正在建立的遊戲隊列。每個進來的人都會嘗試進入第一場比賽，第二場比賽失敗，第三場比賽失敗，依此類推。如果找不到任何東西，則在隊列末尾創建一個新遊戲。遊戲在達到最大尺寸時開始，或者在達到最小尺寸後進行固定時間。遊戲開始時，將從隊列的前面移除。

有了這個決定，爲什麼你認爲會有100萬活躍球員？

如果是因爲你有大夢想啓動，我會強烈建議你，你需要把重點放在儘可能高效地解決您的已知問題。在不太可能發生的情況下（嚴重的是，你看過數據嗎？），你可以稍後進行縮放。只有解決實際問題才能大幅度提高你從可怕到貧窮的成功機率。 （我並不是想讓人灰心喪氣，但創業夢真的是瘋狂回報的可能性很低，你所採取的每一個行動都應該是爲了提高賠率）

如果你是一家成熟的遊戲公司，有理由相信你會擊中這些數字，繼續閱讀。

，我不應該說的明顯需要注意的是，你要在一個相對較快的語言來實現性能的關鍵位。例如，如果您主要使用Python編寫代碼，那麼使用Java，Go或C++編寫代碼是一件好事。

接下來，將無法形成規模的第一件事就是玩家參考。所以分發一下。這樣做會減慢你的「可以參加比賽的球員」檢查。所以添加每個遊戲的鎖定，並且異步地分配這個計算。限制你在放棄創建新遊戲之前努力進入遊戲的難度。

下一個瓶頸是遊戲匹配計算。因此，繼續將「新遊戲在這裏」分發給多臺機器。現在一名球員出現，獲得一個核心遊戲清單，開始檢查他們。爲了避免瓶頸，玩家應該隨機排列等待遊戲的列表。

淨瓶頸是要求清單。該列表大部分是隻讀的，因此您可以使用Redis的複製實例。寫入（用於新遊戲和開始標記遊戲）可以發送給主人，可以根據需要將讀取分佈在多臺機器上。玩家將隨機拷貝Redis，獲得一個列表，隨機排序。

如果你打這個級別的規模我會感到震驚。如果你超過它，我會留下下一步，比如把Redis分解給你。

隨機附註。這是一個體面的面試問題。 「設計這個簡單的東西，讓它變大，讓它變得更大，讓它變得更大。」如果你真的想找一個理解分佈式性能的人，那麼這是一個很好的測試。 （但是，只有當面試官可以告訴壞回答好。）