Skip to content
akichoooPublic

About

Practical course projects

Resources

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

Lab 2: Distributed Shuffle

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.

Architecture

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.

Shuffle backends

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).

Data

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 lab2 profile mounts the dataset read-only at /mnt/taxi on every node, with four pre-generated filelists:

    Filelist Partitions Size
    file:///mnt/taxi/filelist_tiny.csv 4 ~40 MB
    file:///mnt/taxi/filelist.csv 406 ~4 GB
    file:///mnt/taxi/filelist_large.csv 1500 ~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.

What you implement

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

Building & Running

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j$(nproc)

Dependencies: build-essential, cmake, libcurl4-openssl-dev.

Local run

# 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 ./shuffle

For 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

docker compose up                                   # local mode
docker compose -f docker-compose.peer.yml up        # peer mode

CloudLab

See CLOUDLAB.md.

Tests

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

Deliverables

  1. Working implementation: all 7 TODOs, CI green.
  2. A report.md / .txt / .pdf covering four experiments:

(a) Where does the input come from?

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.

(b) Shared-filesystem shuffle vs peer shuffle

Pick the local-NVMe row from (a) so input is not the bottleneck. Compare the two shuffle modes on CloudLab:

  • local with --shuffle-dir /mnt/shuffle (NFS exported by node0, see CLOUDLAB.md §7). Partials traverse one NFS server.
  • peer with --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 the local run. NFS on one node doesn't want 4 GB of shuffle traffic through it.

(c) Granularity of parallelism

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?

(d) Top 25 triples

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)

About

Practical course projects

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages