# Postmortem: Distributed Key-Value Store Write Outage

**Date:** 2026-07-09  
**Duration:** 47 minutes  
**Severity:** SEV-1  
**Status:** Resolved  
**Services affected:** `kv-store`, session cache, feature flag service, rate limiter

## Summary

On 2026-07-09, the distributed key-value store experienced elevated write failures across three production regions. Reads remained mostly available, but writes to replicated keyspaces failed or timed out for many customers.

The incident was caused by a bad rollout of a new membership reconciliation path. Under node churn, the new logic incorrectly marked healthy replicas as stale, causing shard ownership to flap. This triggered repeated leader elections and write quorum failures.

The issue was mitigated by rolling back the deployment and forcing shard ownership reconciliation from the last known stable cluster state.

## Customer Impact

From 14:08 to 14:55 UTC:

- Approximately 38% of write requests failed or timed out.
- Read availability remained above 99.7%, but some reads returned stale values for up to 90 seconds.
- Customers using the session cache saw intermittent logouts.
- Customers using feature flags saw delayed flag updates.
- Rate limiting behavior was degraded for a subset of tenants, causing both under-limiting and over-limiting.
- No confirmed data loss occurred.

## Timeline

All times are UTC.

| Time | Event |
|---|---|
| 13:42 | Version `2026.07.09.3` began rolling out to production region `us-east-1`. |
| 13:58 | Rollout reached 50% of `us-east-1` storage nodes. No alerts fired. |
| 14:04 | Deployment advanced to `us-west-2` and `eu-west-1`. |
| 14:08 | Write latency exceeded SLO in `us-east-1`; first automated alert fired. |
| 14:10 | On-call engineer acknowledged the page and began investigation. |
| 14:14 | Error rate for write quorum failures exceeded 20% across replicated keyspaces. |
| 14:18 | Rollout was paused. Initial suspicion focused on network packet loss due to increased gossip retries. |
| 14:24 | Logs showed repeated shard leadership changes for otherwise healthy replica sets. |
| 14:29 | Engineers identified the new membership reconciliation path as the common factor. |
| 14:31 | Rollback to version `2026.07.08.9` was initiated. |
| 14:39 | Rollback completed in `us-east-1`; write success rate began recovering. |
| 14:46 | Rollback completed in all affected regions. |
| 14:50 | Manual shard ownership reconciliation was started using the last stable cluster state. |
| 14:55 | Write error rate returned to baseline. Incident was marked mitigated. |
| 15:18 | Verification completed that hinted handoff queues had drained and no data loss was detected. |

## Root Cause

The outage was caused by a bug in the new membership reconciliation logic introduced in version `2026.07.09.3`.

The change was intended to reduce recovery time after node restarts by more aggressively removing stale node membership records. However, the implementation used the local node’s last gossip timestamp instead of the cluster-agreed heartbeat timestamp when evaluating replica freshness.

During normal node churn, this caused healthy replicas to be incorrectly classified as stale. The cluster repeatedly removed and re-added replicas from shard ownership metadata, which caused leader elections to occur in rapid succession. While leadership was unstable, many write requests could not reach quorum before timing out.

## Contributing Factors

- The rollout moved to multiple regions before the first region had completed a full shard rebalance cycle.
- Existing canary checks measured node health and read/write availability, but did not detect excessive leadership churn.
- The membership reconciliation path had unit tests for stale nodes, but lacked integration tests covering transient gossip delay.
- Alerting focused on customer-visible write latency and error rate, so engineers were paged after impact had already started.

## What Went Well

- The deployment system allowed the rollout to be paused quickly.
- Rollback was clean and completed without manual package intervention.
- Existing repair and hinted handoff mechanisms prevented confirmed data loss.
- Cross-region ownership metrics helped narrow the investigation to the membership layer.

## What Went Wrong

- The canary was not representative of real production churn.
- Leadership churn was visible in metrics but did not have an alert.
- The new reconciliation behavior was enabled by default rather than guarded behind a runtime flag.
- The deployment advanced too quickly for a storage-layer change with quorum semantics.

## Action Items

| Action | Owner | Due Date |
|---|---|---|
| Add integration tests for membership reconciliation under gossip delay and node restart scenarios. | Storage Platform | 2026-07-17 |
| Add alerting for abnormal shard leadership churn. | Observability | 2026-07-18 |
| Require storage-layer rollouts to complete one full rebalance cycle in a single region before global rollout. | Release Engineering | 2026-07-19 |
| Put membership reconciliation changes behind a runtime feature flag. | Storage Platform | 2026-07-22 |
| Add a canary workload that performs quorum writes during simulated node churn. | Reliability Engineering | 2026-07-24 |
| Update incident runbook with shard ownership reconciliation steps. | On-call Rotation Lead | 2026-07-16 |

## Prevention

We will treat membership, replication, and quorum-related changes as high-risk storage changes. These changes will require slower regional rollout, stronger canary validation, and explicit rollback controls before reaching broad production exposure.