Kos*_*ias 6 java database caching cassandra redis
我们正在构建一个大型多人教育游戏，排行榜中有数百万个条目（基于获得的汇总 XP）。游戏结束后，我们需要显示排行榜以及该玩家/学生的排名。但是这个排行榜有几个过滤器（全球/按国家/地区，按月/年/今天，按年龄等）可以混合在一起，例如“让我获得排行榜for my Country for the last month”。组合数约为 20。
我的问题是如何存储这样一个定期更新的结构；每场比赛后必须重新计算排名。目前一个典型的完整排行榜有来自 150 多个国家的玩家的约 500 万个条目。
我曾经有一个带有 3 个节点的 MySQL 集群表（userid、xps、countryid），但是随着数字变大（> 20K 用户）按 XP 排序（在 DBMS 或需要来自 DB 的所有数据的应用程序中）被证明太慢了）。这是一个有趣的帖子，但对于每个查询半秒也太多了。
然后我们使用了 REDIS（见这篇文章），但过滤是这里的问题。我们对 TOP 5 和其余的使用单独的列表。TOP 5 立即更新，其余部分有 20-30 分钟的延迟。事实上，我们根据排行榜的缓存实例对这个用户进行了排名（尽管使用的是真实的 XP，而不是缓存的），所以这是可以接受的。在非 Top5 上实时不是先决条件。这对于一个全球排名来说很好，但如何根据月份和/或国家和/或年龄过滤结果。我们是否需要为每个过滤组合保留一个列表？
我们还在 Java 中测试了自定义结构（将其用作 Java 缓存服务器，在功能上与 REDIS 类似），仍在试验它。哪个是实现我们目标的最佳结构组合？我们最终为每个过滤组合使用一个列表，例如Map<FilteringCombination, SortedList<User>>，然后对特定键的列表进行二分搜索。这样，一个完成的游戏需要几次插入，比如 X，但它需要 X*NumOfPlayers 空间，这是保持单个列表的 X 倍（不确定这是否适合内存，但我们总是可以在这里创建一个集群将组合拆分到不同的服务器）。这里有一个关于如何在出现故障时重建缓存的问题，但这是我们可以处理的另一个问题。
扩展上述方法，如果我们在每个列表中定义评分桶，我们可能会稍微提高性能（例如，一个桶用于 0-100xp，另一个用于 101 - 1000xp，另一个用于 1001 - 10000xp 等）。分桶策略将基于我们游戏中玩家的 xp 分布。确实，这种分布在现实世界中是动态的，但我们已经看到，几个月后变化很小，请记住 XP 总是在增加，但新用户也在不断增加。
我们还通过使用聚类键和白行功能测试 Cassandra 的自然排序，尽管我们知道拥有数百万行可能并不容易处理。
总而言之，这就是我们需要实现的目标。如果某个用户（我们将其命名为 UserX）未包含在 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 或其他帖子，但仍然找不到有效更新和过滤大型排行榜的解决方案。您会选择哪一种候选解决方案以及可能的性能改进是什么（空间 + 内存 +（插入/搜索 CPU 成本））？
这是一个非常有趣的问题 - 感谢您的发帖。一般来说，数据库擅长解决此类需要过滤和搜索的大量数据的问题。我的第一个猜测是您没有正确使用 MySQL 索引。话虽如此，您显然需要定期查找有序列表中的第 n 行，而这是 SQL 根本不擅长的。
如果您正在寻找某种形式的内存数据库，那么您将需要比 REDIS 更复杂的东西。我建议你看看 VoltDB，它非常快但不便宜。
如果您想构建自己的内存存储，那么您需要计算内存使用情况以查看是否可行。对于要搜索或过滤的每一行以及每个用户的记录，您将需要一个索引（将在本答案中稍后讨论）。然而，即使对于 1000 万行和 20 个字段，其 RAM 仍然小于 1Gb，这在现代计算机上应该没问题。
现在介绍数据结构。我相信您使用地图列表的方式是正确的。我认为列表不需要排序 - 您只需要能够获取特定值的用户集。事实上，集合可能更合适（再次值得测试性能）。这是我的尝试建议（我刚刚添加了国家/地区和年龄字段 - 我假设您需要其他字段，但这是一个合理的示例）：
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));
您需要检查其中哪一个更有效 - 我猜流实现会更有效。它还可以轻松转换为 parallellStream。
您提到了对更新效率的担忧。如果这是一个问题，我会感到非常惊讶，除非每秒有很多更新。一般来说，对于这些类型的应用程序，您获得的读取次数将多于写入次数。
我认为没有理由按照您的建议手动对索引进行分区，除非您将拥有数亿个条目。更好的方法是尝试使用 HashMap 与 TreeMap 来具体实例化索引。
如果您需要更好的性能，下一个明显的增强功能是对应用程序进行多线程处理。这不应该太复杂，因为您需要同步的数据结构相对简单。在搜索中使用并行流当然会有所帮助（并且您可以在 Java 8 中免费获得它们）。
因此，我的建议是使用这些简单的数据结构，并在尝试任何更复杂的操作之前使用多线程和调整具体实现（例如哈希函数）来寻求性能。