一个网站有很多页面 ( url ), 做一个 url 排行榜功能。排行根据 url 的访问次数 (pv) 排行。
排行榜需要实时准确即:某个页面每一次访问都会实时地影响到排行数据。
提示:排行榜本身也会有很高的实时访问需求,注意读和写的时间复杂度。
考察点:数据结构的组合使用。
这道题的解题思路是不是:redis 的有序集合的跳表啊🤔
1
1194129822 2022-05-26 23:22:06 +08:00 4
的确,redis zset 可以完成任务,但是想要考察的是数据结构和并发吧,参考 zset 的实现,hash + skiplist ,在 Java 对应的并发结构是 ConcurrentHashMap(url, pv),ConcurrentSkipListMap(pv, set(url))。CHM 可以处理高并发读写,CSLM 处理实时排序(如果排序规则是最新的在最前面 set(url)换成 LinkedHashMap ),设计成事件驱动,在 url 被访问的时候加 hook 触发事件,然后面试官问问 CHM 原理之类就差不多了。 还可以优化,比如排行榜实时到什么程度?同一 pv 的 url 太多问题。排行榜既然叫排行榜,肯定不用全排行,一般都是一部分, 这就涉及 topN 问题。等等,能深挖的有很多。
|
2
Ymmmmmmmm OP 多谢,受教了
|
3
lihahahayang 2022-06-22 21:45:02 +08:00
@1194129822 pv 数量一样的时候,cslm 不是有问题了吗
|