非典型TOP K

来自TubiTV店面。算法+系统设计
面的senior backend. 店面问的top K. 说是输入是动态的。于是我就用了heapq 保存top k. 然后面试之后的反馈是我应该用stand library, sorting什么的。这难道不是stand lib？搞不懂。
然后问了如何scaling. 我记得提到了merge 多个top k. 而且可以用redis/memcached来存储数据，因为他们很快。我提到了那个俄国人top k视频里面的利用lambda architecture和probablistic data strucure。面试官问如果一个输入比之前存的stale top k小如何处理，大又如何‍‍‌‌‌‌‌‌‍‌‍‌‍‍‌‌‍‍处理。考虑pros and cons。不懂如何作答。有高手指点一二吗？

可以考虑用 Redis 的 sorted set存储. 把排序要依据的那个数值作为 score, 存进 Redis (ZADD). Redis 速度快就不必说了, 底层用跳表存储 sorted set, 有新元素加入就会动态调整调表的结构(O(logN)的时间复杂度非常低, 速度非常快), topK 问题可以用ZRANGE API 得到. 不只是前 K 个, 这个API 还能得到任意排名范围的值. 据我所知, 很多网站的热搜榜就是类似的设计.

至于怎么 scale, 并发量方面, Redis 单机就能抗住 ~10 万/s 的并发, 再多就加 replica也就差不多了, 因为热搜榜一般读得多写得少, 而且面试中一般没有特别变态的访问量. 至于数据量的 scale, 可以考虑用 Redis Cluster, 这还是做数据分片的思想, 同时也能分流一部分并发量. 至于其 trade off, 可以聊一下 Redis Cluster 用的是八卦协议, 在大集群下一致性不好, 但在当前场景下似乎也可以接受.

老实说我会直接用Druid偷懒直接存储实时数据，跑实时query的时候选Druid自带的top k query就是了…
需要准确的多天数据再搞一些async task来backfill/recalculate

topk可能想你用quickselect

Derekzzz 发表于 2023-05-17 11:23:49
topk可能想你用quickselect

输入是动态的怎么用quickselect？我觉得Heap没问题呀🤔

一个输入比之前存的stale top k小如何处理
这个是想问count min sketch 撞key的case吗？