01排行榜需要哪些 window——任意范围，还是固定的时／日／月？
只有固定 window：过去一小时、一天、一个月，以及全时段。任意时间范围不在范围内。
免费完整指南
Top K Songs (Spotify)
设计Top K Songs (Spotify)。请覆盖Framing top-K as a heavy-hitters/frequency-estimation problem over a play-count stream, Count-Min Sketch + heap (bounded error, memory trade-off) vs exact per-partition...
00
练习检查点
面试节奏保持精简,让页面能把注意力花在真正的设计决策上。
- 01澄清范围
- 02需求 + 规模
- 03API + 数据模型
- 04画出架构
- 05深入探讨
- 06取舍决策
01
塑造设计的需求
不要只是陈述需求,要主动问出来。每张卡把设计约束和一句你可以在画架构前说出口的澄清问句配成一组。
功能需求
02K 最大能到多少？
每份排行榜最多 1,000 首歌。
03一次新的播放要多快出现在排行榜上？
约一分钟内——近乎实时，不是瞬间。
04两首歌在第 K 名打平——用什么打破平手？
一个确定性的 tiebreak（先比次数，再比 song id）——同一个查询两次必须返回同一份列表；排行榜不能闪烁。
05地区和曲风排行榜——现在还是以后？
以后再做——全局排行榜先出货；地区与曲风变体是一个明确的后续阶段。
06一首歌被下架——它什么时候离开排行榜？
立即——一首被下架的歌必须同时从每一份排行榜上消失，永远不用等次数重算。
范围外任意时间范围（from/to 查询） · 每用户或每地区的个性化排行榜 · 播放刷量检测
非功能需求
01摄取要为多少事件率做规划？
峰值每秒数十万次播放事件。
02一次排行榜读取要多快？
数十毫秒——打开排行榜必须感觉即时。
03数字非得精确不可吗？
要问——它会改变设计。这里的主路径：精确计数；这些数字可能喂进版税报表，所以系统性的高估不可接受。
04如果有东西在一个小时进行到一半时崩溃，丢几次播放可以接受吗——还是每次播放最终都必须被计入？
什么都不能丢——每次播放最终都必须被计入；恢复期间新鲜度短暂下滑可以接受。
05一首歌吃掉一半播放量怎么办？
单一热门歌曲可能一下子吃掉全部播放量的巨大份额——那不能拖慢计数，也不能让排行榜变旧。
持续追问 —— 面试是一场对话
真实面试探得比一份整齐清单深得多。这些范围问句,区分出真正拷问问题的人和只是背诵的人。
- 过去的排行榜必须保留多久——有人能调出去年三月的日榜吗，还是只有当前这些 window？
- 机器人与刷量播放在范围内吗，还是在到达我们之前就被上游过滤？
- 日榜的「一天」由哪个时区定义——UTC，还是听众的本地时间？
- 全时段有多长——它会重置吗？
- 如果唱片公司对某个排行榜名次提出争议，我们需不需要一条从排行榜追回原始播放的审计线索？
02
逼出架构决策的数字
把每个估算都当成一种压力,用来合理化一个组件:缓存、队列、分片、副本、worker pool 或退路。
事件摄取率
每日数百亿次播放（刻意设的 70B/day 压力上限——比今天的流量高一个数量级）70B ÷ 86,400 s ≈ 810K events/s
只有分割式 log 吸收得了这个；聚合器按分区并行消费。
预先聚合的好处
聚合器在写入前，把每首歌每分钟的次数批量起来一首歌每分钟播 10,000 次 → 1 次写入而非 10,000 次
流预先聚合把热门歌的存储写入砍掉 3-4 个数量级。
精确计数的内存
假设约 1 亿首不同的歌 × 计数器 + key ≈ 50 B100M × 50 B ≈ 5 GB per window
精确计数在这里负担得起——这正是它是主路径、而非 sketch 的原因。
Sketch 替代方案
Count-Min Sketch，4 个 hash 行 × 200 万个 bucket × 4 B≈ 32 MB per window vs 5 GB 精确
当每 window 的内存开始要紧时（很多 window、很多地区），sketch 用一个有界的高估换来约 150 倍更小的状态。
排行榜刷新成本
以一个 min-heap 在次数更新上维护 Top-1,000heap 更新 O(log 1,000) ≈ 每首被计数的歌-分钟约 10 次比较
持续维护排行榜很便宜；每次查询都从头重算则不然。
决策示例
数字
每秒八十万次播放进来，而产品问题很小：四个固定 window 的前 1,000 首歌，一分钟内新鲜。
我的选择
我会把每次播放落进一个分割式的事件 log，在流处理器内以一分钟批量聚合每首歌的精确次数，把分钟卷进小时、小时卷进天——每个 window 各自保有自己的次数。每个 window 一个小 heap 持续维护前 1,000 名，API 服务一份每分钟刷新、并在 window 交界处预热的缓存快照。
避免
我不会做的事：用数据库递增来计播放次数——每秒 810K 次递增是一场写入风暴，预先聚合的流免费就吸收掉了。我也不会默认就伸手去拿 Count-Min Sketch：精确计数在这里每 window 约 5 GB，负担得起，而精确数字为版税级的用途留了一扇门。Sketch 是 window 数翻倍时的正确工具——每地区排行榜、数十个 window——而且有界的高估可以接受。
何时改变
如果产品加上每地区和每曲风排行榜（数百个 window），我会把分布头部翻成精确计数器、长尾翻成 Count-Min Sketch——热门歌维持精确，尾巴几乎不花成本。
03
架构路径
先看一张完整的图,再把每条路径各自画成一张图 —— 写入路径与读取路径承载不同流量,合理化不同的组件。
完整全貌
总览 —— 每个组件
- 播放由左往右流动；每 window 的 heap 持续让前 1,000 名的答案保持热。
- 虚线 = 不在实时路径上：每夜一次在事件 log 上的批量重算，校正任何漂移。
- 下架发生在 serve 时：Chart API 通过一份 denylist 过滤被下架的歌，所以移除是立即的，永远不用等次数重算。
路径 1
写入路径——先计数，再排名
流内的预先聚合把一首热门歌的 10,000 次播放变成一次被计数的写入；heap 随着次数变化而更新。
路径 2
读取路径——服务快照
读取永远看不到原始次数。快照每分钟刷新，并在 window 交界处预热，所以整点的请求跟其他任何请求一样快。
04
API 与数据模型
在优化之前,先让契约可被检视:端点、实体、所有权、重试与状态。
GET/charts/top?window={hour|day|month|all}&k=100
响应200 [{ song_id, plays }] (≤1,000 entries)
从缓存服务最新的 ChartSnapshot——cache key charts:{window}:{window_start}，在 window 翻转时预热，让交界那一分钟永远不会慢。
STREAMplay-events topic (partitioned by song_id + hot-key salt)
响应consumed by the windowed aggregator
唯一的写入路径。生产者 fire-and-forget；持久性来自 log，不是来自生产者。
核心实体
PlayEventsong_id · user_id · played_at
仅追加的流记录；带保留期的 log 是重放的真相来源。
WindowCountsong_id · window (hour/day/month/all) · window_start · plays
精确的每 window 次数，随着 window rollup 而在更粗的粒度上聚合（小时 → 天 → 月）。
ChartSnapshotwindow · window_start · top_k: [song_id, plays][]
API 服务的那份预先算好的答案；每分钟刷新一次，带 TTL 缓存。
05
深入方向
在面试最后三分之一挑一条路线。每条路线给你主题、它该回答的面试官问题,以及要避免的失败模式。
精确还是近似
问
在这里 Count-Min Sketch 什么时候才是对的选择，你到底放弃了什么——用数字说？
回答
就用精确计数。这里每个窗口大约 5 GB，1 亿首歌、每首约 50 字节，负担得起。只有当窗口成倍增长到成百上千个地区和曲风榜单时，才去动 Count-Min Sketch。它能把状态砍到 150 分之一、只剩 32 MB，但每个计数都可能偏高，绝不会偏低。做榜单没问题，算版税就错了。
避免
反射性地伸手去拿 sketch——每 window 5 GB，精确计数负担得起，而且严格来说更有用。
一首歌吃掉整条流
问
一首热门单曲吃掉 30% 的播放。它的分区会怎样，你又如何在不搞坏次数的前提下把它铺开？
回答
给分区 key 加盐。在爆款歌曲的 key 后面加一个小的随机后缀，让它的播放量分散到好几个分区，而不是压垮一个。然后在排序之前，把这些部分计数合并成这首歌的一个总数。省掉合并，这首爆款就会裂成好几条，每条只占它真实播放量的一小块。
避免
把分区 key 加了 salt，却忘了把加了 salt 的次数合并回一首歌的总数。
window 交界
问
现在是 00:00:01，所有人都在要新的每小时排行榜。那个答案从哪里来？
回答
从一份已经预热好的快照来。在边界之前，聚合器就把即将收尾的那个窗口的 top-1,000 定稿，写进缓存。所以翻窗之后的第一个请求，就是一次普通的缓存命中，跟其他请求没两样。要是改成在那第一个请求上现算榜单，你就把这一小时里最忙的一秒变成了最慢的一秒。
避免
在翻转后的第一个请求上才计算排行榜——改成预热快照。
聚合器挂掉
问
流处理器在一个小时 window 进行到第十分钟时崩溃。排行榜显示什么，次数又如何恢复？
回答
榜单继续拿上一份缓存快照往外发。它会有一两分钟不准，但绝不会开天窗。一个接替的处理器加载它最后的 checkpoint，从那个 offset 开始重放事件日志，只把当前窗口的尾巴重新数一遍。什么都不会丢，因为每一次播放都是先落进日志、才被计数的。
避免
在处理器内存里计数却没有 checkpoint——从 log 重放才是整个安全故事。
为什么不用时序数据库
问
Prometheus 式的时序引擎会存储随时间变化的次数——为什么它们在这里不合适？
回答
两个原因，cardinality 是第一个。1 亿个歌曲 ID 当 tag 值，早在写入速率造成麻烦之前，就把索引和内存撑爆了。查询形态也不对。那些引擎擅长回答“单条序列随时间变化”，却答不好“所有序列里的 top 1,000”——而后者恰恰是这个系统存在的意义。
避免
忽略基数：1 亿个 song ID 当 tag 值，正是时序引擎会噎住的东西。
准备好练习了吗?
把 Top K Songs (Spotify) 大声讲一遍,让 AI 为你的说明评分。