面试题目分析
    │
    ├─ 题目是否涉及"聚合"、"统计"、"Top K"、"Analytics"？
    │   │
    │   ├─ YES → Aggregation/Analytics 系统
    │   │   └─ 继续判断处理方式...
    │   │
    │   └─ NO → 可能是其他类型（Search, Storage, etc.）
    │
    ├─ 是否需要处理事件流（event stream）？
    │   │
    │   ├─ YES → 流处理架构（Flink/Spark Streaming）
    │   │   └─ 实时或近实时聚合
    │   │
    │   └─ NO → 批处理架构（Spark Batch）
    │       └─ 定期批量聚合
    │
    ├─ 查询延迟要求？
    │   │
    │   ├─ < 100ms → 预计算 + 缓存
    │   ├─ < 1s → 流处理 + 预聚合
    │   └─ > 1s → 批处理可能足够
    │
    └─ 数据精确性要求？
        │
        ├─ 必须精确 → 完整聚合
        └─ 可以近似 → Count-Min Sketch, HyperLogLog 等

输入：事件流（Event Stream）
Input: Event Stream
- Click events
- View events  
- Purchase events
- 任何需要计数的事件
  Any events that need counting

输出：聚合结果（Aggregated Results）
Output: Aggregated Results
- Counts（计数）
- Sums（求和）
- Top K（前K个）
- Averages（平均值）
- Percentiles（百分位数）

查询模式：
Query Patterns:
- 时间窗口查询（last hour, last day, last month）
  Time window queries (last hour, last day, last month)
- 按维度聚合（by adId, by videoId, by userId）
  Aggregate by dimension (by adId, by videoId, by userId)
- 多维度组合查询
  Multi-dimensional queries

Event Stream (Kafka/Kinesis)
    ↓
Stream Processor (Flink/Spark Streaming)
    ↓
Aggregation (In-memory state)
    ↓
Pre-aggregated Storage (Redis/OLAP DB)
    ↓
Query Service (Reads from storage)

Event Stream (Kafka/Kinesis)
    ↓
Raw Event Storage (Cassandra/S3)
    ↓
Batch Processor (Spark)
    ↓
Aggregated Storage (OLAP DB: Redshift/Snowflake)
    ↓
Query Service

Event Stream
    ├─→ Stream Processor (Real-time layer)
    │       ↓
    │   Approximate Results (Redis)
    │
    └─→ Batch Processor (Batch layer)
            ↓
        Accurate Results (OLAP DB)
            ↓
    Query Service (Merge both layers)

优点：
Advantages:
- 实现简单
  Simple implementation
- 窗口边界清晰
  Clear window boundaries
- 易于预计算
  Easy to precompute

缺点：
Disadvantages:
- 查询时间可能不在窗口边界
  Query time may not be at window boundary
- 需要等待完整窗口才能查询
  Need to wait for complete window to query

示例：
Example:
- 10:06 查询 → 返回 9:00-10:00 的数据
  10:06 query → returns 9:00-10:00 data

优点：
Advantages:
- 查询更灵活
  More flexible queries
- 实时性更好
  Better real-time performance

缺点：
Disadvantages:
- 实现复杂
  Complex implementation
- 需要维护更多状态
  Need to maintain more state
- 存储开销大
  High storage overhead

示例：
Example:
- 10:06 查询 → 返回 9:06-10:06 的数据
  10:06 query → returns 9:06-10:06 data

适用场景：
Use Cases:
- 财务数据
  Financial data
- 需要精确计数的场景
  Scenarios requiring exact counts
- 数据量可接受
  Acceptable data volume

实现方式：
Implementation:
- 完整的事件计数
  Complete event counting
- 使用精确数据结构（HashMap, Sorted Set）
  Use exact data structures (HashMap, Sorted Set)

存储需求：
Storage Requirements:
- 高（需要存储所有事件或完整计数）
  High (need to store all events or complete counts)

适用场景：
Use Cases:
- Top K 问题（前几名通常差距很大）
  Top K problems (top items usually have large gaps)
- 趋势分析（不需要精确数字）
  Trend analysis (exact numbers not needed)
- 数据量巨大
  Massive data volume

实现方式：
Implementation:
- Count-Min Sketch（频率估计）
  Count-Min Sketch (frequency estimation)
- HyperLogLog（去重计数）
  HyperLogLog (distinct count)
- Probabilistic Data Structures
  概率数据结构

存储需求：
Storage Requirements:
- 低（只需要 sketch 数据结构）
  Low (only need sketch data structure)

查询延迟要求：< 100ms
聚合计算时间：秒级或分钟级
→ 必须在查询前完成计算

细粒度（Minute-level）：
- 优点：查询灵活，可以组合任意时间窗口
- 缺点：存储量大，计算开销高

粗粒度（Hour/Day-level）：
- 优点：存储量小，计算开销低
- 缺点：查询灵活性受限

混合粒度：
- 最近数据：细粒度（minute）
- 历史数据：粗粒度（hour/day）
- 最佳实践！

1. Cron Job（定时任务）
   - 简单，但可能有延迟
   - 适合批处理场景

2. Window Completion（窗口完成时）
   - 流处理中自动触发
   - 延迟低，实时性好

3. On-demand（按需计算）
   - 首次查询时计算
   - 需要缓存结果

用途：存储原始事件
选择：
- Cassandra (LSM-tree)
- Kafka (Log-based)
- S3 (Object storage)

特点：
- 高写入吞吐量
- 不适合复杂查询

用途：存储预聚合结果
选择：
- Redis (In-memory)
- OLAP DB (Redshift, Snowflake, BigQuery)
- TimescaleDB (Time-series)

特点：
- 快速查询
- 支持聚合查询
- 写入相对较慢

Hot Data (最近数据):
- Redis (内存)
- 快速查询
- 小数据量

Warm Data (近期数据):
- OLAP DB
- 快速查询
- 中等数据量

Cold Data (历史数据):
- S3/Blob Storage
- 慢查询
- 大数据量

写入吞吐量：
Write Throughput:
- Events/second
- 峰值 vs 平均值
  Peak vs average

存储需求：
Storage Requirements:
- 原始事件大小
  Raw event size
- 聚合结果大小
  Aggregated result size
- 保留时间
  Retention period

查询负载：
Query Load:
- Queries/second
- 查询复杂度
  Query complexity

Views/day = 70B
Views/second = 70B / 100k = 700k/sec

Videos = 3.6B
Storage (naive) = 3.6B * 16 bytes = 64 GB

1. Event Ingestion
   - Kafka/Kinesis stream
   - Partition by key (videoId, adId, etc.)

2. Basic Aggregation
   - Simple counter per key
   - Store in database

3. Query
   - Query database
   - Sort and return top K

优势：
- 低延迟（毫秒级）
- 强大的状态管理
- 精确一次语义（Exactly-once）
- 支持复杂窗口操作

适用场景：
- 实时聚合
- 复杂事件处理
- 需要精确结果的场景

关键概念：
- KeyedStream（按键分组）
- Window Functions（窗口函数）
- State Backend（状态后端）
- Checkpointing（检查点）

优势：
- 批处理风格的流处理
- 与 Spark 生态集成好
- 适合微批处理

适用场景：
- 微批处理（秒级延迟可接受）
- 需要与 Spark 批处理统一
- 复杂的数据处理 pipeline

关键概念：
- DStream（离散化流）
- Micro-batch（微批）
- RDD operations

优点：
- 速度快
- 实现简单

缺点：
- 内存限制
- 故障恢复困难

适用场景：
- 小规模数据
- 短期窗口

选择：
- RocksDB（Flink 默认）
- Redis
- Cassandra

优点：
- 可扩展
- 故障恢复支持

缺点：
- 性能开销
- 复杂度增加

适用场景：
- 大规模数据
- 长期窗口
- 需要故障恢复

每个窗口维护一个 Heap（最小堆）
- 大小固定为 K
- 新元素如果 > min(heap)，则替换
- 窗口结束时输出 Top K

复杂度：O(n log K)

1. 每个分片计算自己的 Top K
2. 查询时合并所有分片的 Top K
3. 从合并结果中取全局 Top K

优点：
- 可扩展
- 并行处理

注意：
- 需要确保全局 Top K 在分片 Top K 的并集中

1. 识别题目类型
   "这是一个聚合/分析系统设计问题"

2. 明确核心需求
   "需要处理事件流，聚合数据，支持时间窗口查询"

3. 询问关键参数
   - 事件频率
   - 查询延迟要求
   - 数据精确性要求
   - 时间窗口类型

1. 从简单开始
   "我们先设计一个基础方案：事件 → 数据库 → 查询"

2. 识别瓶颈
   "这个方案在规模上会有问题：写入瓶颈、查询慢"

3. 逐步优化
   "引入流处理 → 预计算 → 缓存 → 分片"

4. 讨论权衡
   "精确性 vs 性能，延迟 vs 成本"

❌ 不要：
- 一开始就提出复杂方案
- 忽略规模估算
- 不考虑故障恢复
- 忽略数据精确性

✅ 应该：
- 从简单方案开始
- 明确识别瓶颈
- 逐步优化
- 讨论权衡

"这是一个典型的聚合/分析系统设计问题。
"This is a typical aggregation/analytics system design problem.

核心需求是：
Core requirements:
1. 处理大量事件流（[具体事件类型]）
   Process large event streams ([specific event type])
2. 实时或近实时聚合数据
   Real-time or near-real-time data aggregation
3. 支持时间窗口查询（[具体窗口]）
   Support time window queries ([specific windows])
4. 返回聚合结果（[Top K/Count/Sum]）
   Return aggregated results ([Top K/Count/Sum])

让我先澄清几个关键问题：
Let me clarify a few key questions:
- 事件频率是多少？
  What's the event frequency?
- 查询延迟要求？
  What's the query latency requirement?
- 是否需要精确结果？
  Do we need exact results?
- 支持哪些时间窗口？
  What time windows should we support?"

"我先设计一个基础方案：

1. 事件摄入：使用 Kafka，按 [key] 分区
2. 流处理：使用 Flink，按时间窗口聚合
3. 存储：聚合结果写入 Redis/OLAP DB
4. 查询：查询服务从存储读取结果

这个方案可以工作，但有几个瓶颈：
- 写入可能成为瓶颈
- 查询延迟可能不满足要求
- 需要处理故障恢复

让我逐步优化..."

"针对 [具体问题]，我提出以下优化：

1. 写入优化：
   - 使用 Batching 减少写入次数
   - Sharding 分散写入负载
   - 处理 Hot Partition

2. 查询优化：
   - Precomputation：提前计算聚合结果
   - Caching：缓存热门查询
   - 分层存储：Hot/Warm/Cold data

3. 故障恢复：
   - Checkpointing：定期保存状态
   - 从 Kafka 重新消费
   - Reconciliation：批处理验证准确性"

实时性要求高 + 数据量大
→ 流处理架构（Flink）

可以容忍延迟 + 数据量巨大
→ 批处理架构（Spark）

需要实时 + 需要精确性
→ Lambda 架构（流处理 + 批处理）

查询延迟 < 100ms
→ 必须预计算 + 缓存

可以容忍近似结果
→ 使用概率数据结构（CMS, HLL）