巨大的排行榜排名與過濾

Question

我們正在構建一個巨大的多玩家教育遊戲，在領導板（根據聚集的XPs獲得）的數百萬條目。遊戲結束後，我們需要顯示排行榜以及該玩家/學生的排名。 但是這個排行榜有一些過濾器（全球/按國家，按月份/年份/今天，按年齡等），可以混合在一起，例如'給我排行榜for my Countryfor the last month'。組合數是〜20。

我的問題是如何存儲這樣一個定期更新的結構;重新計算排名必須在每場比賽後進行。目前，一個典型的完整排行榜對來自150多個國家的玩家來說有500萬的參賽作品。

1. 我曾經有MySQL簇表（用戶ID，XPS，countryid）與3個節點，但排序由（這需要從DB的所有數據或者在DBMS或應用程序）被證明XPS是爲數字太慢變得更大（> 20K的用戶）。這是一個有趣的post，但對於每個查詢而言，又是半秒太多。

2. 然後我們使用REDIS（見post），但過濾是這裏的問題。我們使用單獨的名單TOP 5和其他。 TOP 5立即更新，其餘時間延遲20-30分鐘。實際上，我們根據排行榜的一個緩存實例對這個用戶進行了排名（儘管使用了真正的XPs，而不是緩存），所以這是可以接受的。非Top5的實時並不是先決條件。 這對一個全球排名很合適，但是如何根據月份和/或國家和/或年齡過濾結果。我們是否需要爲每個過濾組合列出清單？我們還測試了Java中的自定義結構（使用它作爲與REDIS功能類似的Java緩存服務器），但仍在嘗試使用它。哪個是結構的最佳組合來實現我們的目標？我們最終使用每個過濾組合的一個列表，例如Map<FilteringCombination, SortedList<User>>，然後執行二進制搜索到特定鍵的列表。通過這種方式，完成的遊戲需要插入一些X，但它需要X * NumOfPlayers空間，這比保存單個列表多了X倍（不確定這是否適合內存，但我們總是可以在這裏創建一個集羣將組合分割到不同的服務器）。這裏有一個關於如何在發生故障時重建緩存的問題，但這是我們可以處理的另一個問題。

3. 擴展上述方法，如果我們在每個列表中定義評分桶（例如0-100xp的桶，101-1000xp的另一個桶，1001-10000xp的另一個等等），我們可能會略微提高性能。分組策略將基於玩家在我們遊戲中的xp分佈。確實，這種分佈在現實世界中是動態的，但我們已經看到，在幾個月後的變化是微不足道的，考慮到XP總是在增加，但新用戶也會來。

4. 我們還利用集羣鍵和白行功能測試Cassandra的自然排序，儘管我們知道有幾百萬行可能不容易處理。

總之，這就是我們需要實現的。如果用戶（讓我們命名她的用戶X）不包含在TOP5名單，我們需要顯示該用戶的一些周圍的玩家一起排名（以上如2和表2）如下面的例子：

Global TOP 5  My Global Ranking (425) My Country Ranking  Other Rankings  
1. karen (12000xp)   423. george    1. david  
2. greg (11280xp)   424. nancy    2. donald 
3. philips (10293xp)  **425. UserX**    3. susan 
4. jason (9800xp)   426. rebecca   **4. UserX** 
5. barbara (8000xp)   427. james    5. teresa 

我已經研究了許多SO或其他帖子，但仍無法找到有效更新和過濾大型Leaderboard表的解決方案。您會選擇哪一種候選解決方案，以及可能的性能改進（空間+內存+（插入/搜索CPU成本））？

Answer 1

這是一個非常有趣的問題 - 感謝發佈。一般來說，數據庫擅長處理需要過濾和搜索大量數據的這類問題。我的第一個猜測是你沒有正確使用MySQL索引。話雖如此，您顯然需要定期查找有序列表中的第n行，這是SQL一點都不擅長的。

如果您正在尋找某種形式的內存數據庫，那麼您需要比REDIS更復雜的東西。我建議你看看VoltDB，它非常快但不便宜。

如果您想構建自己的內存存儲，那麼您需要計算內存使用情況，看看它是否可行。您需要爲每個要搜索或過濾的行以及每個用戶的記錄索引（稍後在此答案中討論）。然而，即使對於1000萬行和20個字段，它仍然會小於1Gb RAM，這在現代計算機上應該不錯。

現在的數據結構。我相信你正在使用地圖列表的正確軌道。我不認爲這些清單需要進行排序 - 您只需要能夠獲得具有特定價值的用戶組。事實上，設置可能更合適（再次值得測試性能）。這裏是我的建議，嘗試（我剛剛加入的國家，年齡領域 - 我認爲你需要別人，但它是一個合理的例子來開始）：

enum Country { 
    ... 
} 

class User { 
    String givenName; 
    String familyName; 
    int xp; 
    Country country; 
    int age; 
} 

class LeaderBoard { 
    Set<User> users; 
    Map<Integer, Set<User>> xpIndex; 
    Map<Country, Set<User>> countryIndex; 
    Map<Integer, Set<User>> ageIndex; 
} 

每個指標都將需要更新當一個領域改變時。例如：

private setUserAge(User user, int age) { 
    assert users.contains(user); 
    assert ageIndex.get(user.getAge()).contains(user); 
    ageIndex.get(user.getAge()).remove(user); 
    if (!ageIndex.containsKey(age)) { 
     ageIndex.put(age, new TreeSet<>()); 
    } 
    ageIndex.get(age).add(user); 
    user.setAge(age); 
} 

讓所有的用戶，按職級，滿足給定的組合可以通過多種方式來完成：

countryIndex.get(Country.Germany).stream() 
    .filter(ageIndex.get(20)::contains) 
    .sorted(User::compareRank) 
    ... 

或

SortedSet<User> germanUsers = new TreeSet<>(User::compareRank); 
germanUsers.addAll(countryIndex.get(Country.Germany)); 
germanUsers.retainAll(ageIndex.get(20)); 

你需要檢查其中哪一個更有效 - 我猜想流實現將會是。此外，它可以很容易地轉換爲paralellStream。

您提到了更新效率的問題。如果這是一個問題，除非每秒更新一次，否則我會很驚訝。一般來說，對於這些類型的應用程序，您將獲得比寫入更多的讀取。

我看不出有任何理由手動分區索引，因爲你建議，除非你將有數以百萬計的條目。更好的做法是嘗試使用HashMap vs TreeMap作爲索引的具體實例。

如果您需要更好的性能，下一個明顯的增強是多線程應用程序。這不應該太複雜，因爲您有相對簡單的數據結構進行同步。並行流在搜索中的使用當然有幫助（你可以在Java 8中免費獲得它們）。

所以我的建議是使用這些簡單的數據結構，並在嘗試更復雜的任何事情之前使用多線程和調整具體實現（例如散列函數）來提高性能。

Answer 2

儘管我仍處於基準測試的中間，但我正在更新當前開發的狀態。當使用 最佳性能優惠的價格：

Map<Country, Map<Age, Map <TimingIdentifier, List<User>>>> （列表排序）

的一些注意事項上的按鍵：我添加了一個爲了呼籲世界國家有充分的領導人板的實例國家獨立（就好像國家過濾器沒有被選中一樣）。我爲Age（All-Ages）和TimeIdentifier（All-Time）做了同樣的事情。 TimeIdentifier鍵值爲[全時，月，周，日]

以上可以擴展爲其他過濾器，所以它也可以應用於其他場景。 Map<Filter1,Map<Filter2,Map<Filter3,Map<Filter4 ..other Map Keys here..,List<User>>>>

更新：而不是使用多個地圖包裝紙，用作在一個單一的地圖與上述字段的關鍵的一類是稍快。當然，我們需要像圖案多例創建所有可用FilterCombination對象：

class FilterCombination { 
    private int CountryId; 
    private int AgeId; 
    private int TimeId; 
    ... 
} 

然後我們定義了Map<FilterCombination, List<User>>（排序列表）

我可以用一個TreeSet，但我沒有。爲什麼？基本上，我在尋找一個Order Statistic Tree（請參閱here），但似乎沒有官方的Java實現（請參閱here）。可能這是由於List.add(index, Object)是O（n）的低效率而進入VS排序列表的方式。 LinkedList對於.add(index, Object)會更好，但不幸的是獲取第k個元素的速度很慢（排名爲O（n））。所以，每一種結構都有其優點和缺點。

目前，我結束了使用排序列表。原因是，當向排序列表添加元素時，我使用稍微修改的二進制搜索算法（請參閱here）。上述方法給出了當前用戶在插入階段的排名（因此不需要額外的搜索查詢），它是O（logn + n）（二進制搜索索引+ List.add（index，Object））。

有沒有其他的結構比O（logn + n）更好地執行insert + get rank？

*當然，如果以後我需要詢問用戶的排名，我會再次根據用戶的XP（+時間戳，如下所示）進行二分查找，而不是用戶名，因爲現在我無法搜索通過列表中的用戶ID）。

**作爲一個比較我用以下標準

1：XP點

在平局的情況下 - 第二標準：去年XP更新

這樣的時間戳，極有可能Sorted列表中的平等將非常少。更重要的是，如果兩個XP用戶的排名順序相反（即使我們的數百萬遊戲的樣本數據，我發現幾乎沒有聯繫，但不包括我不在乎的零XP）完全）。

XP更新需要一些工作和資源。幸運的是，第二個比較標準顯着提高了用戶在這個List中的搜索（再次進行二分搜索），因爲在更新用戶的XP之前，我不得不刪除列表中此用戶的以前的條目......但是我正在通過她以前的XP和時間戳，所以它是log（n）。

Answer 3

最簡單的選擇是選擇Redis的排序集，並使用主站進行復制。打開每個從站上的RDB並將RDB文件備份到S3。使用Kafka在寫入Redis之前堅持所有寫入。因此，我們可以稍後重播丟失的交易。