# Postmortem: Distributed Key-Value Store Write Unavailability

**Date of incident:** 2026-06-18  
**Duration:** 47 minutes  
**Severity:** SEV-1  
**Status:** Final  
**Services affected:** `kv-store`, `session-api`, `feature-flags`, `checkout-state`

## Summary

On 2026-06-18, the distributed key-value store experienced a partial outage that caused elevated write failures and increased read latency across three production regions. The incident began after a rolling deployment introduced a change to the shard rebalancer. Under a specific cluster topology, the rebalancer repeatedly moved hot shards between nodes, causing quorum instability and compaction backlog.

Approximately 18% of write requests failed during the incident window. Reads remained mostly available, but p99 latency increased from 42 ms to 1.8 seconds for affected tenants.

The issue was mitigated by disabling automatic shard rebalancing, rolling back the deployment, and manually pinning the affected shards.

## Customer Impact

From 14:07 UTC to 14:54 UTC:

- 18% of write requests to the key-value store failed with `503 quorum_unavailable`.
- Read p99 latency increased from 42 ms to 1.8 seconds.
- Session updates intermittently failed, causing some users to be logged out.
- Feature flag updates were delayed for up to 12 minutes.
- Checkout state writes failed for approximately 4.3% of active checkout sessions.

No confirmed data loss occurred. Failed writes were rejected before commit and returned errors to callers.

## Timeline

All times in UTC.

| Time | Event |
|---|---|
| 13:42 | Rolling deployment of `kv-store` version `2026.06.18-rc3` begins in `us-east-1`. |
| 13:58 | Deployment completes in `us-east-1`; no immediate alerts fire. |
| 14:03 | Shard rebalancer begins moving 38 shards from nodes with high disk utilization. |
| 14:07 | First spike in `quorum_unavailable` errors observed. |
| 14:09 | PagerDuty alert fires for elevated write error rate. |
| 14:12 | On-call engineer acknowledges incident and begins investigation. |
| 14:16 | Metrics show repeated leadership changes for several hot shards. |
| 14:21 | Incident escalated to storage team and declared SEV-1. |
| 14:25 | Automatic shard rebalancing is disabled globally. |
| 14:31 | Write error rate stabilizes but remains above baseline. |
| 14:34 | Team identifies version `2026.06.18-rc3` as correlated with rebalancer activity. |
| 14:39 | Rollback to `2026.06.12` begins. |
| 14:47 | Manual shard pinning applied to the five most unstable shards. |
| 14:54 | Write error rate returns to baseline. |
| 15:08 | Read latency returns to normal levels. |
| 15:30 | Incident resolved. |
| 16:20 | Post-incident review begins. |

## Root Cause

The root cause was a bug in the shard rebalancer introduced in `kv-store` version `2026.06.18-rc3`.

The new logic attempted to reduce disk skew by moving shards away from nodes above 78% disk utilization. However, it did not account for pending compaction debt when estimating the destination node’s effective capacity. Several destination nodes appeared healthy based on raw disk usage but were already under heavy compaction load.

As hot shards moved to these nodes, write amplification increased, compactions fell behind, and Raft append latency rose sharply. The rebalancer interpreted the resulting latency as node imbalance and moved the same shards again. This created a feedback loop:

1. Hot shard moved to a node with hidden compaction debt.
2. Write latency increased.
3. Raft followers missed heartbeat deadlines.
4. Leadership changed repeatedly.
5. Quorum became temporarily unavailable.
6. Rebalancer selected the shard for movement again.

The system preserved consistency but sacrificed availability for affected shards.

## Contributing Factors

- Rebalancer tests covered disk utilization but not compaction backlog.
- Staging clusters did not include production-sized hot shards.
- The deployment proceeded region-wide before shard movement metrics were reviewed.
- Alerts detected write failures but did not directly identify rebalancer churn.
- The rebalancer lacked a cooldown period after moving a shard.

## Detection

The incident was detected by automated monitoring on write error rate. The first alert fired two minutes after customer-visible errors began.

Useful signals during investigation:

- `kv_write_errors_total{code="quorum_unavailable"}`
- `raft_leader_changes_total`
- `shard_rebalance_moves_total`
- `compaction_pending_bytes`
- `raft_append_latency_p99`

## Resolution

We mitigated the outage by:

- Disabling automatic shard rebalancing globally.
- Rolling back `kv-store` to version `2026.06.12`.
- Manually pinning unstable hot shards.
- Allowing compaction queues to drain before re-enabling normal traffic patterns.

Automatic rebalancing remains disabled until the remediation work is complete.

## What Went Well

- Write failures were rejected before commit, preventing partial or inconsistent writes.
- On-call escalation happened quickly.
- Existing shard pinning tooling allowed targeted mitigation.
- Rollback completed without requiring data migration.

## What Went Poorly

- The rebalancer made repeated decisions without sufficient dampening.
- Staging did not model production shard heat or compaction behavior.
- The initial alert identified symptoms but not the subsystem causing them.
- The deployment checklist did not require reviewing shard movement rate after rollout.

## Action Items

| Action | Owner | Priority | Due Date |
|---|---|---:|---|
| Add compaction backlog to rebalancer capacity scoring. | Storage Team | P0 | 2026-06-25 |
| Add per-shard movement cooldown with exponential backoff. | Storage Team | P0 | 2026-06-25 |
| Create alert for abnormal shard movement rate. | Observability | P1 | 2026-06-28 |
| Add production-scale hot shard simulation to staging. | Platform Infra | P1 | 2026-07-05 |
| Require post-deploy review of leadership churn and rebalance metrics. | Release Engineering | P1 | 2026-06-30 |
| Add automated rollback trigger for sustained quorum errors after deploy. | SRE | P2 | 2026-07-12 |
| Document manual shard pinning runbook. | Storage Team | P2 | 2026-07-03 |

## Prevention

Before automatic rebalancing is re-enabled, we will require:

- Load testing with production-like shard heat.
- Validation of compaction-aware placement decisions.
- A shard movement cooldown.
- New alerts for rebalance churn and leadership instability.
- A staged rollout with manual approval between regions.

## Follow-Up

A follow-up review will be held on 2026-07-08 to confirm completion of P0 and P1 action items and decide whether automatic shard rebalancing can be safely re-enabled.