TopK vs Leaderboard存储

系统设计
1

Spotify TopK里面讲到counter system，即hashtable+linkedlist。Leaderboard里讲到用Redis sorted set，即hashmap+skip list。这两个看起来很像，所以这两个都可以用Redis sorted set吗？两个有什么区别吗？感觉topk更倾向区间段streaming process，是因为数据量不同吗？

2

有一个区别，就是 Spotify TopK 没有找某一首歌的 Rank 的需要，所以可以上课讲到的 O(1) 的数据结构。Leaderboard 的数据结构是 O(lgN) 的。
当然，如果是现实中的话，会更接近于 Redis Sorted Set，因为现实中即使 Spotify 也会有找某一首歌 Rank 的需要。

3

  1. 为什么没有找某一首歌的需要，就适合用O(1)结构，而有找某一个user就适合用O(LgN)结构呢？不管怎么样都应该是O(1)更好呀，所以找某一首歌更应该用O(1)吧？

  2. 而且leaderboard的fix partition找一个user我有点confuse。老师讲可以先通过user的score找到这个user所在的partition，再找这个user id。但是用户搜索的时候可能没有score吧，用户就是为了得到score而搜索的user。Api是 GET v1/score/{userid}。这样怎么搜索呢？

4
  1. 因为 O(1) 结构没法支持有效找特定用户 Rank，所以 Leaderboard 这题的需求用不了 O(1) 结构只能退而求其次。
  2. 这点课上讲了，需要有一个额外的数据库存用户和分数的对应关系。
5

请问这种hashmap+linkedlist有现有的存储机制可以做吗？我知道怎么用代码来实现linked list，但是这东西要怎么存起来?

6

就是在内存里的 data structure，放在硬盘里可以 serialize 但就达不到效率要求了。