CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 4 of 8 · 2 min read

Pipeline

Two queues and a DAG.

A direct chain from log watcher to aggregation service to database is synchronous. A sudden rise in traffic can overload the consumer, and one failure stops everything. The book places a message queue (Kafka) between the parts, so each scales and fails on its own.

Flow.

  1. Log watcher reads new click lines and sends them to the first queue.
  2. The aggregation service reads the first queue and counts clicks by minute, and also finds the top N ads each minute.
  3. It writes the results to a second queue.
  4. A database writer reads the second queue and stores the results in the aggregated database.
  5. The query service reads the database for dashboards.

Why a second queue? The aggregation service could write to the database directly, but writing to a queue makes it possible to commit the result and the read position of the first queue together. That gives exactly-once results (page 1 of this level), which a billing system needs.

Inside the aggregation service: a DAG. The work is split into small units joined in a directed acyclic graph (Level 11, page 4), like MapReduce.

  • Map nodes read events, clean them, and send each to the right aggregation node by a key such as ad_id % 3. This is needed because events for one ad may arrive in different queue partitions.
  • Aggregate nodes count clicks per ad in memory for each minute. Each keeps a heap, a structure that quickly finds the largest items, so it can report its top N.
  • Reduce nodes merge the top lists from all aggregate nodes into the final top N.

A worked example (made up). Three aggregate nodes each report their top 3 ads. Node 1: a 90, b 70, c 50. Node 2: d 80, e 60, f 40. Node 3: g 95, h 55, i 45. The reduce node looks at these 9 and returns the top 3: g 95, a 90, d 80.

Map, aggregate and reduce

Map transforms and routes records, aggregate summarises records that share a key, and reduce merges the summaries into a final answer.

Example: map sends a click for ad 7 to node 1, node 1 counts it, and reduce merges the node counts into one top list.

Check yourself: 1. Why put a queue between parts? 2. What does a map node do? 3. How does the reduce node build the top 3 from 9 candidates?