etcd-io / etcd-io/etcd

mvcc: lock-order inversion in progressIfSync can deadlock the apply loop

Open
#22,184 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
52.3k
Forks
10.5k
Avg merge
2d 21h
Merged PRs (30d)
43

Description

### What happened

`progressIfSync` acquires the watchable store's `mu` before the MVCC store's `mu`, which is the exact ordering the code comments forbid. Combined with a concurrent `KV().Commit()` (which the snapshot-send path performs) and any in-flight write transaction, this closes a three-goroutine lock cycle that wedges the apply loop permanently.

The invariant, from `server/storage/mvcc/watchable_store.go`:

```go
// mu protects watcher groups and batches. It should never be locked
// before locking store.mu to avoid deadlock.
mu sync.RWMutex
```

`progressIfSync` violates it (`watchable_store.go`):

```go
s.mu.RLock() // watchable.mu
defer s.mu.RUnlock()
rev := s.rev() // -> store.Read() -> store.mu.RLock()
```

The write path takes the locks in the opposite order: `store.Write()` holds `store.mu.RLock` for the txn lifetime and releases it *inside* `watchableStoreTxnWrite.End()`, which runs under `watchable.mu.Lock()` (`watchable_store_txn.go`). So a writer holds `store.mu.RLock` and wants `watchable.mu.Lock`, while `progressIfSync` holds `watchable.mu.RLock` and wants `store.mu.RLock`.

Two read locks don't conflict on their own — the deadlock needs a third party queuing a **write** lock on `store.mu`. `createMergedSnapshotMessage` provides it: it calls `s.KV().Commit()` → `store.mu.Lock()` **on the snapshot-send goroutine**, not the apply loop. Go's `sync.RWMutex` blocks new readers once a writer is queued, so `progressIfSync`'s `store.mu.RLock()` then blocks behind the queued `Commit`.

The cycle:
- **W** (write txn) holds `store.mu.RLock`, waits on `watchable.mu.Lock` (in `End`)
- **P** (`progressIfSync`) holds `watchable.mu.RLock`, waits on `store.mu.RLock` (behind C)
- **C** (`Commit`) waits on `store.mu.Lock` (behind W)

Nothing makes progress; the apply loop is stuck.

### Reproduction

Deterministic, three goroutines forcing the cycle (drop-in test in package `mvcc`):

```go
func TestProgressIfSyncDeadlock(t *testing.T) {
b, _ := betesting.NewDefaultTmpBackend(t)
s := newWatchableStore(zaptest.NewLogger(t), b, &lease.FakeLessor{}, StoreConfig{})
defer func() { _ = s.store.Close() }()

tw := s.Write(traceutil.TODO()) // W holds store.mu.RLock
tw.Put([]byte("k"), []byte("v"), lease.NoLease)

go func() { s.Commit() }() // C queues store.mu.Lock behind W
time.Sleep(100 * time.Millisecond)

go func() { s.progressAll(map[WatchID]*watcher{}) }() // P: watchable.mu.RLock, blocks on store.mu.RLock
time.Sleep(100 * time.Millisecond)

done := make(chan struct{})
go func() { tw.End(); close(done) }() // W wants watchable.mu.Lock, held by P

select {
case <-done:
case <-time.After(3 * time.Second):
t.Fatal("deadlock: End() blocked on watchable.mu while progressIfSync holds it and waits on store.mu")
}
}
```

On current `main` this fails at the 3s deadline.

### Suggested fix

Read the revision under `revMu` instead of via a full read transaction, matching the `watchable.mu → revMu` order already used by `watch()`, `syncWatchers()`, and `moveVictims()` (none of which touch `store.mu`):

```go
s.mu.RLock()
defer s.mu.RUnlock()

s.store.revMu.RLock()
rev := s.store.currentRev
s.store.revMu.RUnlock()
```

With this change the reproduction passes and the existing watch/sync tests stay green. Happy to open a PR with the fix and the regression test.

### Environment

Reproduced on `main` (`cb846f6d2`). The inverted lock order in `progressIfSync` is long-standing.

Contributor guide

Open the contributing guide

Research direction

Start in server/storage/mvcc/watchable_store.go, then read the lock handling in watchable_store_txn.go and the progressIfSync path. Add the regression test described in the issue, verify it no longer deadlocks, and run the existing watch and sync tests to confirm they remain green.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
databases, distributed-systems
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.