DDIA Ch11
数据流引擎
Question: Top K 为什么不能每次查询现扫所有 view rows？
用数据流/批流引擎维护聚合，避免把查询路径变成海量 shuffle。
第 7 周 - 第 4 天 - 2026-09-10 THU - FULL - Top K deep dives
YouTube Top K FULL: stream aggregation, late events, approximate/exact materialized views
今日目标
完整覆盖 Top K deep dives: caching/precompute, writes, query optimization, sliding windows, approximations, specialized DB tradeoffs.
| 08:50-09:00 | Set target 写下 exact path 和 approximate path 的分界：什么产品场景能接受 fuzziness？ |
|---|---|
| 09:00-10:05 | Deep-dive reading 读 Top K all deep dives and inline solution progressions. |
| 10:05-10:45 | Mechanism sheet 画 Flink window aggregation, watermark, replay, materialized view, CMS+heap alternative. |
| 10:45-10:55 | Spoken close 用英文解释 late events and stale view tolerance. |
| 14:30-16:15 | NeetCode Trees Exactly three contiguous Trees slots. Each slot is 30m solve + 5m pattern/invariant/bug/complexity evidence. |
| 20:30-21:15 | Recall / Q&A / repair 20:30-21:15 完成 compact Chinese explainer audio check and one 30-minute Top K follow-up prompt. |
Exact source links
Use original Hello Interview titles and current canonical anchors. Inline Bad/Good/Great headings without standalone live anchors link to their parent canonical section.
| Original title / direct link | Disposition | Use |
|---|---|---|
| Potential Deep Dives | deep dive | Top K optimization ladder |
| 1) How can we cut down on the number of queries to the database? | deep dive | cache versus precompute materialized top K |
| 2) How can we handle the massive number of writes to the database? | deep dive | sharded ingestion, batching, Flink checkpoints |
| 3) How do we optimize our top K queries? | deep dive | coarser aggregates, window aggregate tables, in-memory Flink |
| 4) What if we need to support sliding windows? | deep dive | increment/decrement windows and retention costs |
| 5) Can we make use of approximations to improve performance? | deep dive | Count-Min Sketch plus heap/list |
| 6) Is there room for a specialized database here? | deep dive | time-series and realtime OLAP fit and caveats |
| What is Expected at Each Level? | level expectation | calibrate Top K interview bar |
| Mid-level | level expectation | end-to-end but suboptimal |
| Senior | level expectation | near optimal, identifies bottlenecks |
| Staff+ | level expectation | dataflow, cost, precision, variants |
| Good Solution: Cache the Top K for each time window | inline progression | fast reads with cache freshness tradeoff |
| Great Solution: Precompute the Top K for each time window | inline progression | materialized results served in tens of ms |
| Sharding Ingestion | inline subheading | partition by videoId through Kafka and DB shards |
| Batching Ingestion | inline subheading | Flink aggregates views before DB writes |
| Good Solution: Aggregate at a Coarser Granularity | inline progression | hour/minute buckets reduce scan costs |
| Great Solution: Maintain Aggregates for Each Window in the Database | inline progression | read a pre-maintained window state |
| Great Solution: (With Caveats) Do Aggregation in Memory with Flink | inline progression | lower latency with state/checkpoint concerns |
| Good Solution: Redis | inline progression | CMS and sorted list for tumbling approximations |
| Great Solution: Flink | inline progression | managed state, checkpoint, exact or approximate paths |
| Bad Solution: InfluxDB or Prometheus (time-series engine with downsampling) | inline progression | not a good fit for high-cardinality exact Top K |
| Good Solution: TimescaleDB (Postgres + hypertables + continuous aggregates) | inline progression | resembles aggregate-table path |
| Good Solution: Real-time OLAP (Druid/Pinot/ClickHouse) | inline progression | valid if candidate can defend internals |
DDIA decision cards
Only exact Ch11/Ch12/Ch13 sections that change today's design are assigned.
DDIA Ch12
重播旧消息
Question: Top K view event 可以 replay 吗，怎么不重复计算？
Kafka/Flink replay 用 offset/checkpoint；聚合更新必须按 eventId/window/videoId 幂等。
DDIA Ch12
处理滞留事件
Question: 晚到 view event 如何影响 1 小时榜？
用 watermark 和 allowed lateness；迟到过界后进入 correction/replay，不静默改旧榜。
DDIA Ch12
原子提交再现
Question: 流处理器更新 DB 和 offset 为什么会双写风险？
checkpoint、sink commit、offset advance 要形成可恢复边界；失败后不会既丢又重算。
DDIA Ch12
失败后重建状态
Question: Flink state 或 materialized Top K 坏了怎么办？
从 checkpoint 或事件日志重建，记录 replay lag 和 divergence。
DDIA Ch13
维护派生状态
Question: 派生状态为什么允许短暂陈旧？
publication truth、view truth、activity truth 与 CDN/TopK/feed 派生视图分离。
DDIA Ch13
应用演化后重新处理数据
Question: 重新处理旧事件时如何避免破坏当前线上榜单？
重处理写新版本视图，验证后原子切换 alias/cache key。
DDIA Ch13
物化视图和缓存
Question: 缓存和物化视图 stale 到什么程度可接受？
CDN manifest、TopK cache、activity feed 都需要 TTL/freshness/SLO，而不是假装强一致。
算法模块
Contiguous live NeetCode Trees order. No reviews. Three slots per day.
| # | Problem / mode | Pattern | Invariant | Bug risk | Time | Space |
|---|---|---|---|---|---|---|
| 10 | Subtree of Another Tree NEW - 30m solve + 5m evidence | 遍历 + sameTree | 任一根节点同构即为 subtree。 | 只比较值不递归结构。 | O(mn) | O(h) |
| 11 | Convert Sorted Array to Binary Search Tree NEW - 30m solve + 5m evidence | 分治建平衡 BST | 中点作为 root，左右区间仍有序。 | 区间闭开边界混用。 | O(n) | O(log n) |
| 12 | Merge Two Binary Trees NEW - 30m solve + 5m evidence | 同步 DFS 合并 | 同位置节点值相加，缺失节点直接返回另一边。 | 原地修改时误复用被覆盖子树。 | O(n) | O(h) |
今日验收
| Output | Top K compact explainer, exact/approx matrix, late-event policy, and follow-up recording. |
|---|---|
| Hard fail | Passive reading without a spoken answer; missing invariant/failure/recovery/metric; any day outside Week 7 touched. |
| Repair | Pick the weakest answer and redo it for 8 minutes with one new failure window. |
Detailed lecture notes, audio, recall scripts, PDFs, Staff Q&A, and mock packs are archived locally and are intentionally not published on this site.