How GitHub Sharded Their Databases Without Downtime and Broke Their Monolith

GitHub faced significant scaling challenges with its monolithic MySQL database, which stored nearly all core data. To address this, they implemented a sophisticated two-tier strategy for partitioning their relational database without incurring downtime. This approach involved both virtual and physical partitioning, meticulously designed to ensure data consistency and application availability throughout the migration.

The Challenge of Scaling GitHub’s Monolithic Database

Initially, GitHub relied on a single, massive MySQL cluster to house all its core data. To manage increasing load, especially read requests, they employed standard procedures like adding replicas and using ProxySQL as a database proxy for connection pooling and routing.

However, vertical scaling eventually hit a critical bottleneck. GitHub was experiencing a very high query volume, reaching approximately 950,000 queries per second. This monolithic architecture led to several problems:

• Haphazard Queries: Lack of clear boundaries meant any part of the application could query or join any table, leading to complex and intertwined data access patterns.
• Noisy Neighbor Problem: Load from one type of request (e.g., creating pull requests) would impact the performance of unrelated requests (e.g., accessing commits) because they shared the same underlying database infrastructure.
• Outages: A problem affecting one part of the database could lead to outages for all services relying on it.
• Convoluted Codebase: By the time these scaling issues became critical, the codebase was already complex, with queries and joins spanning numerous tables, making it difficult to identify clear boundaries for splitting.

Existing solutions for database sharding often assume clear ownership and bounded contexts, which GitHub lacked due to prevalent cross-domain transactions (e.g., a single transaction spanning stars and comments).

GitHub’s Two-Tier Sharding Strategy

To overcome these challenges, GitHub devised a two-tiered strategy:

1. Virtual Partitioning: Enforcing logical boundaries within the existing monolithic database without physical data movement.
2. Physical Partitioning: Gradually migrating data of isolated logical domains to their own dedicated clusters with zero downtime.

Tier 1: Virtual Partitioning via Schema Domains

The primary goal of virtual partitioning was to enforce logical boundaries and ensure that before any physical separation, there were no cross-domain communications within the existing workflow. This was achieved through a custom tool called Schema Domains.

Schema Domains

Schema Domains are logical groupings of tables defined in a schema_domains.yml file. For example, a gist domain might encapsulate gist_comments, gists, and starred_gists tables, while a repositories domain might include issues, pull_requests, and repositories tables. The core principle was that all queries for a specific domain should remain within that domain.

Enforcing Boundaries

GitHub used different mechanisms to enforce these boundaries in development/test and production environments:

Query Linters (Dev/Test Environment)

• Mechanism: Query linters were built to analyze SQL queries for cross-domain joins. If a query attempted to join tables belonging to different schema domains, it would raise an exception with helpful messages.
• Flexibility: Developers could exempt specific cross-domain queries by adding a structured comment in the codebase. By tracking the number of such exemptions, GitHub could gauge the isolation level of each domain.
• Outcome: This process helped identify and refactor cross-domain dependencies, ensuring that a domain was self-sufficient and ready to be moved out of the main cluster.

Production Environment (Alerting for Cross-Domain Transactions)

• Mechanism: In production, GitHub captured and analyzed all fired queries. If a transaction included queries to tables that would eventually move to separate databases, it would raise an alert rather than blocking the transaction. Blocking was avoided to prevent immediate consistency issues.
• Rationale: While individual queries could be checked for schema domain adherence, transactions might span multiple queries, some of which could be within one domain and others within another. If these queries were part of the same transaction, moving them to separate databases would break consistency guarantees.

Handling Shared/Polymorphic Tables

Some tables, like reactions (which could apply to comments, PRs, etc.), inherently span multiple domains. For such polymorphic tables, GitHub considered strategies like:

• Horizontal Splitting: Partitioning the table into smaller, domain-specific tables.
• Data Duplication: Duplicating read-only data across domains, with writes directed to a single source.

These tables were often exempted from the strict cross-domain checks, with the understanding that specific handling would be required during physical migration.

Outcome of Virtual Partitioning: By the end of this phase, GitHub had a clear understanding that a specific domain (e.g., gist) was virtually isolated, meaning all its queries and transactions were self-contained, making it ready for physical migration to its own cluster.

Tier 2: Physical Partitioning and Zero-Downtime Migration

Once a domain was virtually isolated, the next step was to physically move its data to a dedicated cluster. This process was designed to be gradual and without downtime.

Let’s assume the gist domain is being moved from Cluster A (the main primary cluster) to Cluster B (a new, dedicated cluster for gist).

Key Components

Two critical components facilitate this migration:

• ProxySQL: A database proxy that sits in front of MySQL servers. It handles connection management, caching, and, crucially, intelligent routing of client requests to the appropriate database backend.
• GTID (Global Transaction Identifier): MySQL’s monotonically increasing identifier for each committed transaction. GTID is fundamental for robust replication, allowing replicas to track their position relative to the master and ensure all changes are applied.

The Migration Setup (Step-by-Step)

1. Snapshot Data: A snapshot of all gist tables is taken from Cluster A.

2. Seed Cluster B: This snapshot is loaded into the primary and replicas of Cluster B. At this point, no traffic is directed to Cluster B.

3. Set Up Replication (A to B): Cluster B’s primary is configured to replicate from Cluster A’s primary. This ensures that any changes (writes) happening on Cluster A for gist data are continuously propagated to Cluster B. Cluster B’s replicas continue to replicate from Cluster B’s primary.

4. ProxySQL Configuration: ProxySQL instances are set up for both Cluster A and Cluster B. All client applications connect to these ProxySQL instances, which then route requests to the appropriate MySQL servers.

5. Redirect gist Traffic (Initial Phase): The main API server is updated to direct all gist-related requests to ProxySQL B. However, since Cluster B is still catching up, ProxySQL B is initially configured to redirect these gist requests to ProxySQL A.

   • Current State: Read and write requests for gist data flow from the client -> ProxySQL B -> ProxySQL A -> Cluster A. Any writes on Cluster A are replicated to Cluster B, ensuring eventual consistency.

The Cut-Over Process (Zero-Downtime Switch)

The cut-over is the critical phase where traffic is switched from Cluster A to Cluster B. This process is designed to be extremely fast, minimizing any impact on users.

1. Monitor Replica Lag: The migration team continuously monitors the replica lag between Cluster A and Cluster B. The cut-over is only initiated when this lag is minimal, typically less than one second (or even half a second).
2. Enable Read-Only Mode on Cluster A: The primary of Cluster A is put into read-only mode specifically for the gist tables. This prevents any new writes to gist data on Cluster A. During this brief period, any write requests for gist data will fail with a 5xx error.
3. Measure GTID Difference: The GTID difference between Cluster A and Cluster B is measured to determine how far behind Cluster B is.
4. Wait for Catch-Up: Since no new writes are occurring on Cluster A for gist data, Cluster B will quickly catch up. The process waits until the GTID difference becomes zero, indicating Cluster B has all changes from Cluster A.
5. Stop Replication: Once Cluster B has fully caught up, the replication from Cluster A to Cluster B is stopped.
6. Update ProxySQL B Configuration: ProxySQL B’s configuration is updated to now route gist traffic directly to Cluster B’s primary, instead of redirecting to ProxySQL A.
7. Disable Read-Only Mode (if applicable): If the read-only mode was applied broadly, it can now be disabled on Cluster A.

This entire six-step cut-over process typically takes less than 100 milliseconds. While some gist write requests might fail during the brief read-only window, the overall impact on availability is negligible, as reads continue to be served, and writes resume almost instantly on the new cluster.

Conclusion

GitHub successfully repeated this process for various logical schema domains, gradually migrating them to their own dedicated clusters. This methodical, two-tiered approach allowed them to break down their monolithic database, improve scalability, reduce the noisy neighbor problem, and enhance overall system resilience—all without significant downtime. The strategy highlights the importance of strong logical boundaries and a carefully orchestrated migration plan when dealing with large-scale database refactoring.