Skip to content

SCALING.md

Latest commit

 

History

History
142 lines (93 loc) · 5.13 KB

SCALING.md

File metadata and controls

142 lines (93 loc) · 5.13 KB
Raw

Scaling to 500 Million Repositories

This document outlines how to scale the crawler from 100,000 to 500 million repositories.

Current System Design

Our current implementation uses adaptive range subdivision which automatically handles GitHub's 1,000 result limit. When a star range hits the cap, it splits into smaller ranges and continues. This design is already scalable in concept, but has practical limitations at 500M scale:

Limitation Impact at 500M Scale
Single-threaded execution Would take months to complete
Single GitHub token 5,000 requests/hour = ~20 days minimum
Single PostgreSQL instance Would struggle with 500M row inserts
In-memory batch buffering Memory constraints
In-memory range queue Loses progress on failure

Scaling Strategy

1. Parallel Workers with Distributed Queue

Current approach: One worker processes ranges from an in-memory queue.

Scaled approach: Replace the in-memory deque with a distributed queue (Redis, Kafka, or SQS).

The current StarRange objects can be serialized and pushed to a message queue. Multiple workers can then:

  1. Pull ranges from the queue
  2. Crawl the range
  3. If hitting the 1000 cap, push subdivided ranges back to the queue
  4. Continue until queue is empty

This requires minimal code changes because the queue-based architecture is already in place. Each worker operates independently, writing to the same database.

2. Token Rotation

Current approach: Single GitHub token with 5,000 requests/hour.

Scaled approach: Pool of N tokens, rotating between them.

With 10 tokens: 50,000 requests/hour With 50 tokens: 250,000 requests/hour

This directly multiplies our throughput.

3. Async I/O

Current approach: Synchronous requests library, blocking on each API call.

Scaled approach: Use aiohttp for async HTTP and asyncpg for async database operations.

Benefits:

  • Multiple API requests in flight simultaneously
  • Non-blocking database writes
  • 10-100x throughput improvement per worker

4. Database Scaling

Current approach: Single PostgreSQL instance.

Scaled approaches:

Option A - Partitioning: Partition the table by github_id hash. PostgreSQL handles routing automatically.

Option B - Read Replicas: Write to primary, query from replicas to avoid contention.

Option C - Distributed PostgreSQL: Use Citus or CockroachDB for horizontal scaling across nodes.

For 500M rows, we would need approximately 50GB of storage.

5. Message Queue Architecture

Current approach: Direct API-to-database pipeline.

Scaled approach: Decouple with a message queue.

Flow: GitHub API -> Crawler Workers -> Kafka/Redis -> Consumer Workers -> PostgreSQL

Benefits:

  • Backpressure handling (consumers can lag behind producers)
  • Retry capabilities without re-fetching
  • Multiple consumer groups for different processing

6. Checkpointing and Resumability

Current approach: Start from scratch on failure.

Scaled approach: Save cursor position for each star range to Redis or a state table.

On restart, workers resume from their last known position instead of re-crawling.

Infrastructure Comparison

Component 100K Scale 500M Scale
Workers 1 20-50 (distributed)
Tokens 1 10-50
Database Single node, 10MB Sharded cluster, 50GB
Memory 1GB 16GB+ per worker
Crawl time ~15 minutes ~1 week
Architecture Monolithic Distributed

Estimated Performance

Configuration Repos/Hour Time for 500M
Current (1 worker, 1 token) ~20,000 ~25,000 hours (3 years)
10 workers, 10 tokens ~200,000 ~2,500 hours (104 days)
50 workers, 50 tokens, async ~2,000,000 ~250 hours (10 days)
Optimized distributed system ~5,000,000 ~100 hours (4 days)

Schema Evolution for Additional Metadata

To collect issues, PRs, commits, comments, and CI checks, we would add normalized tables:

Table Rows at 500M repos Size Estimate
repositories 500M 50GB
issues ~2B 200GB
pull_requests ~1B 100GB
comments ~5B 500GB
commits ~50B 5TB

Each table uses its GitHub node ID as primary key, enabling efficient upserts.

When a PR gets new comments (10 today, 20 tomorrow), we:

  1. Insert the 20 new comments
  2. Duplicates are ignored via ON CONFLICT DO NOTHING
  3. Only 10 new rows are actually written

This minimizes write amplification and keeps updates efficient.

Summary

Scaling to 500M repositories requires transformation from a single-threaded script to a distributed system:

  1. Parallelize - Multiple workers with partitioned workloads
  2. Multiply rate limits - Token rotation and pooling
  3. Go async - Non-blocking I/O throughout
  4. Distribute storage - Sharded or distributed database
  5. Add resilience - Message queues and checkpointing
  6. Monitor everything - Metrics, alerting, and dashboards

The core design principles (star range slicing, upsert patterns, immutable DTOs) remain the same; we simply scale each component horizontally.