Apache Spark 3.5.7 · Catalyst / Tungsten · Verified CI Passing

Large-Scale PageRank & HITS Engine in PySpark

A production-grade Apache Spark batch graph analytics platform implementing PageRank, Topic-Sensitive PageRank, and HITS over real Stanford SNAP graphs up to 68.47M directed edges — paired with a controlled Baseline Python RDD vs. Optimized DataFrame benchmark harness and live Spark REST stage telemetry.

68.47M
Canonical directed edges converged (soc-LiveJournal1, 4.85M nodes, 8.5 min on M4)
4.34x–8.37x
Measured wall-time speedup vs. Python RDD baseline across real SNAP graphs
0 B
Disk & memory spill across all 4 verified runs (up to 11.12 GB Peak RSS)
1.43e-16
Max L1 difference vs. baseline (exact 20/20 Top-20 match; 7/7 NetworkX tests)

System Architecture

Designed for zero driver graph collection, deterministic SHA-256 dataset acquisition, compact 32-bit integer storage, and strict mathematical equivalence across engines.

Stage 01 · Ingest SNAP + SHA-256 Manifest

Downloads official Stanford SNAP archives (cit-HepPh, web-Google, soc-LiveJournal1) with streaming SHA-256 verification.

Stage 02 · Canonicalize Parquet Graph Store

Casts node IDs to INT, removes self-loops (518K in LiveJournal) & duplicates, and audits dangling nodes into graph_audit.json.

Stage 03 · Compute Catalyst / Tungsten Engine

Compact adjacency lists (collect_list + explode), zero Python UDFs in hot loop, exact dangling mass redistribution, and localCheckpoint(eager=True).

Stage 04 · Verify Telemetry & Ground Truth

Captures Spark REST UI stage metrics (shuffle/spill bytes), psutil process-tree RSS, and L1/Top-20 equivalence vs. NetworkX & RDD baseline.

Verified Real-Data Benchmarks

Measured natively on Apple M4 (10 cores, 24 GiB RAM, NVMe SSD) running OpenJDK 17.0.21, Python 3.11.18, PySpark 3.5.7, and KryoSerializer. Select a workload below to inspect exact telemetry and raw JSON evidence.

SNAP cit-HepPh — PageRank (34,546 nodes · 421,534 directed edges)

4.34x Faster · L1 = 1.29e-16

Wall-Clock Execution Time (Lower is Better)

Optimized DataFrame (Tungsten)27.10s
Baseline Python RDD117.62s

Process-Tree Peak RSS Memory (Lower is Better)

Optimized DataFrame (Tungsten)4.68 GB
Baseline Python RDD5.98 GB
Engine Iterations Wall Time Shuffle Write Disk Spill Peak RSS Verification
dataframe_optimized 49 (converged, tol=1e-8) 27.10s 331.6 MB 0 B 4.68 GB Exact 20/20 Top-20 match
baseline_rdd 49 (converged, tol=1e-8) 117.62s 120.4 MB 0 B 5.98 GB L1 diff = 1.29e-16

Engineering Decisions & Honest Trade-Offs

Key Spark internals lessons surfaced by real profiling and automated tests rather than theoretical assumptions.

1. Preventing O(2k) Catalyst Plan Blowup in HITS

In iterative Spark DataFrame loops (especially HITS, which chains authority and hub joins every iteration), un-truncated lineage causes Catalyst's logical plan DAG to expand exponentially and exhaust driver heap inside AdaptiveSparkPlanExec.explainString().

  • Truncating lineage via localCheckpoint(eager=True) every 1–2 iterations keeps plan depth strictly O(1).
  • Disabling AQE (spark.sql.adaptive.enabled=false) removes per-iteration plan re-optimization overhead.

2. Wall-Time Speedup vs. Shuffle-Byte Trade-Off

Moving execution out of Python RDD workers into native JVM Tungsten eliminates per-stage pickle serialization, cutting wall time by 4.34x–8.37x and Peak RSS by ~1 GB.

  • Transparent caveat: In Spark 3.5, localCheckpoint() clears HashPartitioning metadata, so SortMergeJoin writes more shuffle bytes than an RDD holding a fixed HashPartitioner.
  • Despite higher shuffle bytes, native Tungsten stays dramatically faster end-to-end with 0 B disk spill.
Explicit Scope Boundary: All benchmarks ran in Spark local[8] single-node mode on Apple M4 (24 GiB RAM). Multi-node network shuffle latency is outside local workstation scope, and raw SNAP archives are excluded from git and fetched reproducibly via CLI with SHA-256 verification.

3-Command Reproducibility

Reproduce the full mathematical verification suite locally (Python 3.11 + OpenJDK 17) or inside Docker with zero manual configuration.

Local Native Run (PySpark + Pytest)

python3.11 -m venv .venv && source .venv/bin/activate
pip install -e ".[dev]" && pytest -v
spark-graph-ranking ingest --dataset hepph
spark-graph-ranking benchmark --dataset hepph --algorithm pagerank

Containerized Reviewer Verification (Docker)

git clone https://github.com/emilianodesu/spark-graph-ranking.git
cd spark-graph-ranking
docker build -t spark-graph-ranking .
docker run --rm spark-graph-ranking