How an ALTER TABLE Caused a Massive GitHub Outage

On November 27, 2020, GitHub suffered a critical, widespread outage. Core services including GitHub Actions, API requests, Codespaces, Git operations, Issues, Packages, and Pull Requests experienced severe degradation.

The incident was initiated not by a hardware failure or network partition, but by an ALTER TABLE command executed on a massive MySQL table. While schema migrations are routine operations, performing them at hyperscale introduces subtle distributed locking dynamics, replication nuances, and cascading failure modes.

Here is a technical dissection of what went wrong, the anatomy of database replication deadlocks, why early mitigations failed, and the architectural principles applied to recover and build long-term resilience.

---

1. Why ALTER TABLE is Perilous on Giant Tables

In relational databases like MySQL, executing an ALTER TABLE statement (such as adding a column, modifying a column type, or creating indexes) on a table containing hundreds of millions or billions of rows is computationally and I/O intensive.

Historically, MySQL provides two built-in algorithms for DDL operations:

1. ALGORITHM = COPY: MySQL creates a temporary table with the new schema, copies all rows from the original table row-by-row, builds the indexes, and swaps the tables. This requires an exclusive lock (LOCK TABLES), blocking all concurrent writes and sometimes reads.
2. ALGORITHM = INPLACE: Introduced via MySQL Online DDL to avoid full table copying. However, many in-place operations still require rebuilding the clustered index (B+ Tree reorganizations), row-by-row data modifications, and recording concurrent writes into an online alter log. During the preparation and final commit phases, brief exclusive metadata locks (MDL) are still required.

Because modifying a massive table directly causes extreme lock contention, IOPS saturation, and hours (or weeks) of operational latency, production engineering teams do not fire raw ALTER TABLE queries on critical monolithic databases.

---

2. Online Schema Migrations and the Ghost Table Pattern

To alter tables without locking live production traffic, organizations use online schema change tools (such as GitHub’s open-source tool gh-ost or Percona’s pt-online-schema-change).

+-----------------------+           +-------------------------+
| Original Table        |           | Ghost Table             |
| (e.g., repositories)  |           | (e.g., _repositories_gho)|
|                       |           |                         |
| [Live Traffic Reads]  |           | [New Schema Applied]    |
| [Live Traffic Writes] |           |                         |
+-----------+-----------+           +------------+------------+
            |                                    ^
            |         1. Backfill Rows           |
            +------------------------------------+
            |                                    |
            |         2. Stream Binlog Events    |
            +------------------------------------+

The Lifecycle of an Online Migration:

1. Create a Ghost Table: An empty clone of the target table is created with the desired new schema applied (e.g., _repositories_gho).
2. Backfill Existing Data: Rows are copied in small, rate-limited chunks from the original table to the ghost table.
3. Stream Concurrent Writes: Continuous insert, update, and delete events occurring on the original table are captured via MySQL’s binary log (binlog) and replayed on the ghost table to keep both tables in near real-time sync.
4. The Final Cutover (The Table Rename): Once the tables are in sync, the tool performs an atomic rename:

   RENAME TABLE repositories TO repositories_old, _repositories_gho TO repositories;

This atomic rename is designed to be sub-second. However, executing RENAME TABLE requires an Exclusive Metadata Lock (MDL). If long-running reads or writes are executing concurrently, this cutover can become a catastrophic bottleneck.

---

3. The Failure Mechanism: Semaphore Deadlocks on Read Replicas

During the final cutover step of the migration, a significant portion of GitHub’s MySQL read replicas entered a semaphore deadlock state.

Why Do Read Replicas Deadlock?

A common misconception is that read replicas only read data and therefore cannot encounter write deadlocks. In MySQL replication, the primary processes user writes and records them into the binary log. The read replica’s internal replication thread (specifically the SQL coordination and worker threads) continuously consumes the binlog and applies those write/DDL events locally.

[Client Read Traffic] ───Shared Read Locks (MDL/Pages)───┐
                                                         ▼
                                            [MySQL Read Replica Storage Engine]
                                                         ▲
[Replication Worker]  ───Exclusive Lock (RENAME TABLE)───┘

When the atomic RENAME TABLE binlog event arrived at the read replicas:

1. The replication applier thread attempted to acquire an Exclusive Metadata Lock (MDL_EXCLUSIVE) to rename the ghost table.
2. Concurrently, dozens of high-throughput application threads were reading from the table, holding Shared Metadata Locks (MDL_SHARED_READ).
3. The applier thread blocked waiting for active read queries to finish.
4. Subsequent incoming read queries lined up behind the exclusive lock request (since MySQL prioritizes exclusive lock requests in its wait queue to prevent writer starvation).
5. Under heavy memory pressure, mutexes, and thread contention within InnoDB, this lock-dependency inversion mutated into an unrecoverable semaphore deadlock (internal InnoDB sync semaphores waiting beyond thresholds), causing the MySQL daemon on the replicas to crash.

---

4. Architecture Context: Dual Read Replica Fleets

GitHub leverages a segregated replica topology to isolate divergent workloads:

                              +------------------+
                              |  MySQL Primary   |
                              |   (All Writes)   |
                              +--------+---------+
                                       |
                   +-------------------+-------------------+
                   | Replication                           | Replication
                   v                                       v
       +-----------------------+               +-----------------------+
       | Production Read Fleet |               |  Internal Read Fleet  |
       +-----------------------+               +-----------------------+
       | Replica 1             |               | Analytics Replica     |
       | Replica 2             |               | Backup Replica        |
       | Replica 3             |               | Internal Ops Replica  |
       +-----------------------+               +-----------------------+
       (Handles user traffic,                  (Handles large reporting
        web requests, APIs)                     queries, ETL, backups)

• Production Fleet: Serves low-latency, user-facing reads (rendering PRs, serving Git data, responding to API requests).
• Internal Fleet: Serves heavy reporting, backup generation, and business intelligence queries. Separating this fleet prevents internal analytical queries from degrading customer-facing latencies.

---

5. Cascading Failures and the Crash-Recovery Loop

When the semaphore deadlocks hit, a subset of production read replicas crashed simultaneously. This triggered a classic distributed cascading failure.

The Mathematical Saturation Problem

Assume a cluster of 3 production replicas handling 3,000 requests/second (RPS) distributed evenly:

• Nominal State: Each replica handles 1,000 RPS (33.3% of total traffic).
• Failure 1: Replica 3 deadlocks and crashes. Total capacity falls by 33%.
• Load Redistribution: The remaining 2 replicas now receive 1,500 RPS each (a 50% traffic increase).
• Failure 2: Without over-provisioned CPU and memory headroom, Replica 2 saturates, exhausts connection pools, hits mutex timeouts, and crashes.
• Complete Fleet Outage: All 3,000 RPS now slam into the sole surviving replica, instantly collapsing it.

+-------------+        +-------------+        +-------------+
|  Replica 1  |        |  Replica 2  |        |  Replica 3  |
|  1,000 RPS  |        |  1,000 RPS  |        |  1,000 RPS  |
+------+------+        +------+------+        +------+------+
       |                      |                      |
       |                      |                      x [DEADLOCK CRASH]
       v                      v
+-------------+        +-------------+
|  Replica 1  |        |  Replica 2  |
|  1,500 RPS  |        |  1,500 RPS  |  <-- Overloaded: memory & thread exhaustion
+------+------+        +------+------+
       |                      |
       |                      x [SATURATION CRASH]
       v
+-------------+
|  Replica 1  |  <-- Absorbs 3,000 RPS (3.0x load) -> Immediate Collapse
+-------------+

The Crash-Recovery Loop

Once a MySQL instance crashes, it restarts and undergoes InnoDB Crash Recovery (replaying the redo log to make data pages consistent and rolling back uncommitted transactions from the undo log).

During this phase, the database is resource-starved. As soon as a replica finished crash recovery and announced itself healthy, incoming production load flooded it while replication caught up. This immediate stampede caused the replica to exhaust its thread pool or hit another semaphore deadlock, sending it right back into a crash loop.

---

6. The Tactical Response: Why Hack Fixes Failed

Attempted Mitigation: Promoting Internal Replicas

Provisioning brand-new MySQL replicas at scale takes significant time because multi-terabyte data snapshots must be restored and replication must catch up.

To restore capacity rapidly, GitHub’s SREs executed an emergency routing change: They promoted healthy nodes from the internal replica fleet into the production read pool.

While conceptually sound, this tactical fix failed. The incoming production traffic volume was so disproportionately high that the promoted internal nodes were immediately overwhelmed. They too entered the crash-recovery loop alongside the existing production replicas.

The Turning Point: Prioritizing Integrity Over Availability

Confronted with an unstable crash-recovery loop across both fleets, GitHub made a foundational systems design trade-off:

Prioritize Data Integrity Over Immediate Site Availability.

When database nodes continuously crash while replication processes writes, the risk of table corruption, invalid secondary index pointers, or divergent replication positions increases exponentially. If persistent corruption occurs across replicas, rebuilding the cluster from cold storage backups takes days rather than hours.

The Recovery Protocol:

1. Sever All Read Traffic: Production routing layers proactively stopped routing user traffic to the crashing replicas.
2. Provide Quiescent Breathing Room: Completely isolated from client read traffic, the replicas were allowed to complete their InnoDB crash recovery quietly.
3. Apply the Migration Uncontended: With zero competing shared metadata locks from user queries, the replication thread applied the atomic RENAME TABLE operation instantly without deadlocking.
4. Catch Up Replication: The replicas replayed lagging binlogs to reach parity with the primary.
5. Controlled Re-Introduction: Once confirmed healthy and free of corruption, the replicas were gradually re-introduced to production traffic behind load balancers.

The entire incident lasted 2 hours and 50 minutes. Throughout the duration, the MySQL primary (the write path) remained healthy and unaffected.

---

7. Long-Term Architectural Solutions

To prevent this class of failure from recurring, GitHub accelerated two major infrastructure shifts:

1. Functional Partitioning (Vertical Domain Sharding)

Prior to this evolution, multiple high-traffic domains (Pull Requests, Issues, Repositories, Webhooks) shared large monolithic database clusters. An issue affecting a table in one domain caused collateral damage across all services.

Before: Monolithic Cluster             After: Functionally Partitioned Clusters
+---------------------------+          +---------------+  +---------------+  +---------------+
| MySQL Cluster             |          | PR Database   |  | Issue Database|  | Repo Database |
| - Repositories Table      |   ===>   | - PR Table    |  | - Issue Table |  | - Repo Table  |
| - Pull Requests Table     |          | - Review Table|  | - Label Table |  | - Org Table   |
| - Issues Table            |          +---------------+  +---------------+  +---------------+
+---------------------------+             Blast Radius:      Blast Radius:      Blast Radius:   
                                            Isolated           Isolated           Isolated      

• Blast Radius Reduction: A failed migration on the Pull Requests schema affects only the PR database; Issues, Actions, and Git operations remain fully operational.
• Canary Migrations: Functional partitioning allows running schema alterations on a canary shard or isolated domain before rolling them out broadly.

2. Strategic Cluster Over-Provisioning

Databases cannot be provisioned purely for steady-state average loads. GitHub updated cluster provisioning standards to ensure replicas maintain sufficient CPU, RAM, and IOPS headroom to sustain $N - 1$ or $N - 2$ failover scenarios.

If a cluster requires 3 nodes to handle 3,000 RPS, provisioning each node with enough capacity to handle 1,500–2,000 RPS ensures that the sudden loss of one node does not push the surviving members over their saturation thresholds.

3. Automated Circuit Breaking

Implementing adaptive circuit breakers at the client/proxy layer (e.g., stopping queries to replicas whose replication lag or thread concurrency exceeds safety thresholds) prevents failing databases from entering cascading crash-recovery spirals.

---

8. Summary of Key Architectural Insights

Concept	Takeaway
Online Migrations	Even ghost table tools (gh-ost) require an atomic RENAME TABLE that demands an exclusive metadata lock. It is not zero-risk.
Replica Concurrency	Read replicas process writes via replication appliers. High-concurrency reads can deadlock with incoming replication DDL/writes.
Cascading Collapse	Any system operating near resource capacity without buffer headroom is mathematically vulnerable to cascading failure when a single node drops.
Integrity vs. Availability	When systems flap uncontrollably, proactively degrading availability to eliminate contention prevents catastrophic, irrecoverable data corruption.
Functional Partitioning	Splitting monolithic storage into domain-bounded databases isolates failure blast radiuses and enables safe canary schema rollouts.