Task: compute the top 25 most common (PULocationID, DOLocationID, pickup_hour) triples across the NYC TLC High-Volume For-Hire Vehicle
dataset, using a two-phase MapReduce-style shuffle instead of
routing every partial count through the coordinator.
Phase 1: MAP + SHUFFLE Phase 2: MERGE
┌──────────┐ ┌──────────┐
│ Worker 1 │──┐ ┌──▶│ Worker 1 │──▶ top-K (shards 0,2,4,...)
└──────────┘ │ ┌──────────────┐ │ └──────────┘
├────▶│ Shuffle │──┤
┌──────────┐ │ │ Storage │ │ ┌──────────┐
│ Worker 2 │──┘ │ (local|peer) │ └──▶│ Worker 2 │──▶ top-K (shards 1,3,5,...)
└──────────┘ └──────────────┘ └──────────┘
│
▼
┌──────────────────┐
│ Coordinator │
│ global top-25 │
└──────────────────┘
Phase 1 (Map). Each worker reads its assigned partitions,
extracts "<PU>-<DO>-<hour>" from every row, and pre-aggregates
counts locally per shard before writing one partial per shard to
shuffle storage (the MapReduce local-combiner pattern).
Phase 2 (Reduce). Each worker owns a subset of shards, reads all contributing partials for each, and returns one top-K per shard to the coordinator.
Two backends behind a single Storage interface, selected at runtime
with --shuffle-mode:
| Mode | Backend | Use case | How partials move |
|---|---|---|---|
local |
LocalDirStorage |
Local dev / Docker / NFS | Shared filesystem. Every worker writes and reads the same directory. |
peer |
PeerExchange |
CloudLab shared-nothing benchmark | Each worker keeps partials on a local disk and runs a small shuffle server. Merge workers pull what they need from peers over TCP (SHARD_REQUEST / SHARD_RESPONSE). |
Same NYC TLC HVFHS dataset as Lab 1: 25 comma-separated columns with a header row.
-
Local / Docker: fetched over HTTP.
https://db.in.tum.de/teaching/ss26/cbdp-lab/data/filelist.csv(~4 GB)https://db.in.tum.de/teaching/ss26/cbdp-lab/data/filelist_test.csv(~220 MB)
-
CloudLab: the
lab2profile mounts the dataset read-only at/mnt/taxion every node, with four pre-generated filelists:Filelist Partitions Size file:///mnt/taxi/filelist_tiny.csv4 ~40 MB file:///mnt/taxi/filelist.csv406 ~4 GB file:///mnt/taxi/filelist_large.csv1500 ~15 GB file:///mnt/taxi/filelist_full.csv~3600 ~36 GB Recipe for using them in
CLOUDLAB.md.
The aggregation key is the triple (PULocationID, DOLocationID, pickup_hour): columns 7, 8, and the hour extracted from column 5.
~1.7 M distinct values (265 × 265 × 24), enough to make the shuffle
data volume visible.
7 TODOs. Start with the coordinator ones; nothing runs until
assign_map_partitions returns.
| # | Where | What |
|---|---|---|
| 1 | coordinator.cpp::assign_map_partitions |
Split partition URLs across workers |
| 2 | coordinator.cpp::assign_merge_shards |
Split shard IDs [0, R) across workers |
| 3 | coordinator.cpp::merge_global_topk |
Combine per-shard top-Ks into global top-K |
| 4 | worker.cpp::map_phase |
Fetch partitions, extract PU-DO-hour keys, partition into shards, write partials |
| 5 | worker.cpp::merge_shard |
Read every partial for a shard, merge, return top-K |
| 6 | storage.cpp::LocalDirStorage::read_shard |
Walk the shard directory, deserialize each .dat |
| 7 | storage_peer.cpp::PeerExchange::read_shard |
Read local partial, pull each peer's via SHARD_REQUEST |
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j$(nproc)Dependencies: build-essential, cmake, libcurl4-openssl-dev.
# coordinator
./build/coordinator --port 8080 --workers 2 --shards 8 \
--filelist https://db.in.tum.de/teaching/ss26/cbdp-lab/data/filelist_test.csv
# worker 1
./build/worker --host localhost --port 8080 --id worker-1 \
--shuffle-mode local --shuffle-dir ./shuffle
# worker 2
./build/worker --host localhost --port 8080 --id worker-2 \
--shuffle-mode local --shuffle-dir ./shuffleFor peer mode, swap --shuffle-mode peer + a distinct --shuffle-dir
plus --peer-host/--peer-port per worker. See
docker-compose.peer.yml for a concrete 2-worker example.
docker compose up # local mode
docker compose -f docker-compose.peer.yml up # peer modeSee CLOUDLAB.md.
ctest --test-dir build --output-on-failure
./tests/test_two_phase.sh # end-to-end correctness
./tests/test_shard_routing.sh # same top-K across (R, W) configs
./tests/test_balance.sh # every worker merges a fair share
./tests/test_peer_exchange.sh # peer matches local byte-for-byte- Working implementation: all 7 TODOs, CI green.
- A
report.md/.txt/.pdfcovering four experiments:
Same workload three ways, keeping compute (7 workers,
--shuffle-mode peer, --shards 64) constant. Vary only the input
path:
| Configuration | Input URL | Notes |
|---|---|---|
| HTTP from TUM | https://db.in.tum.de/... |
Baseline. 1 GbE control net. |
| iSCSI ltdataset | file:///mnt/taxi/filelist.csv |
All workers read from one CloudLab storage server over the 25 GbE fabric. |
| Local NVMe | file:///tmp/nyc/partitions/... |
No input traffic across the network. |
Report map, merge, and total for each; explain the gaps. The first two rows are shared-storage patterns (one backing store, many readers); the third is shared-nothing (each worker reads its own disk). The gap between them is the whole reason shared-nothing MPP exists: one server's link saturates before a cluster of local disks does.
For the shared-nothing (Local NVMe) row, you design the data
layout: decide how to partition the filelist across workers,
pre-stage each worker's slice into its local
/tmp/nyc/partitions/, and make assign_map_partitions (TODO 1)
produce the same assignment so every worker reads only local
files. Report what you picked and why.
Pick the local-NVMe row from (a) so input is not the bottleneck. Compare the two shuffle modes on CloudLab:
localwith--shuffle-dir /mnt/shuffle(NFS exported by node0, seeCLOUDLAB.md§7). Partials traverse one NFS server.peerwith--shuffle-dir /tmp/shuffle-$i. Partials traverse the 25 GbE fabric point-to-point.
Report map, merge, total.
Use
filelist_test.csv(~220 MB) for thelocalrun. NFS on one node doesn't want 4 GB of shuffle traffic through it.
Shuffle fan-out R trades merge parallelism (few shards) against
per-shard overhead (many shards).
Sweep --shards across {8, 32, 64, 256, 1024} on the same
workload, everything else fixed. Record map, merge, and total per
run.
Report:
- Runtime curve versus shard count.
- Identify the sweet spot. Explain what dominates at each end.
- Where would you set the default for a production deployment? What would make you pick a different value?
Human-readable ranking of the global top 25 (PU, DO, hour) from the
full filelist. Join each against the NYC Taxi Zone Lookup Table to
produce entries like "Penn Station → Upper West Side @ 17:00, 3912
trips".
(results in the report.md)