[TopK] 一些问题

系统设计
1

  1. 上课说TopK的加减都是o(1)的时间复杂度 我个人理解应该是O(m)的时间复杂度 m代表单个频率上linkedlist的平均长度

  2. 一首歌太火问题？我感觉按歌sharding还是会有这个问题 单机无法解决 不知道这个问题怎么更好的解决

谢谢

2
  1. 是 O(1)。上课时我有点没讲清楚，每个 linkedlist 里的 node 都有一个 pointer 指向图左边的 Frequency node。不需要遍历这个 Linkedlist 才能找到 frequency node。
  2. 按歌 Shard，理论上来说每个 Shard 中有火的歌概率是一样的。没什么特别的解决方法，就是 Shard。
3
  1. 如果是按歌shard 我理解最简单的就是对歌的名字取mod, 比如果我现在有一首歌特别火一下1B的users全来听， 每次Request 都会forward的同一台机器上， 那这个单机还是可能抗不出呀, 所以我理解这个没有本质上解决热点问题
4

如果是这样也只能通过在这个 Shard 上 Master-slave 来解决。

5

但我理解 master-slave的话 无法解决写的热点问题 因为写都落在master上了 topK一个大瓶颈就是写入瓶颈 我感觉读倒是master-slave OK

6

写瓶颈的话，可以考虑用 master-master，但是会降低 consistency。