cockroachdb / cockroachdb/cockroach

kvcoord: txnWriteBuffer reverse-scan merge can split a multi-column-family row across paginated responses

Open
#172,400 1 comment 0 reactions 0 assignees View on GitHub
A-buffered-writes A-kv-transactions branch-master branch-release-25.2 branch-release-25.3 branch-release-25.4 branch-release-26.1 branch-release-26.2 branch-release-26.3 C-bug O-agent P-3 T-kv
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

**Describe the problem**

This is a **latent defect**: it violates a documented KV response contract, but as far as we can trace, no current SQL path converts it into wrong results (analysis below).

When the txnWriteBuffer merges buffered writes into a paginated ReverseScan response, the merge window is `[ResumeSpan.EndKey, req.EndKey)` ([`respIter.startKey`](https://github.com/cockroachdb/cockroach/blob/0935372badc46f73ac2660752b8a966edb31ba88/pkg/kv/kvclient/kvcoord/txn_interceptor_write_buffer.go#L2683), used by [`mergeWithReverseScanResp`](https://github.com/cockroachdb/cockroach/blob/0935372badc46f73ac2660752b8a966edb31ba88/pkg/kv/kvclient/kvcoord/txn_interceptor_write_buffer.go#L1220)). The server's reverse resume boundary is row-aligned only with respect to **live** keys: after whole-row trimming, `ResumeSpan.EndKey` is `(highest live key of the next row to scan).Next()` ([`pebble_mvcc_scanner.go#L727`](https://github.com/cockroachdb/cockroach/blob/0935372badc46f73ac2660752b8a966edb31ba88/pkg/storage/pebble_mvcc_scanner.go#L727)).

Only column family 0 is guaranteed to exist in KV. If the transaction has a buffered write to a column family **above** the boundary row's highest live family (e.g. an UPDATE that sets a previously-NULL column stored in a higher family), that key sorts above `ResumeSpan.EndKey`, so the merge injects it into the tail of the **current** page while the rest of the row is only returned on the **next** page. This violates `WholeRowsOfSize` semantics and the kvstreamer `Result` contract, which promises "*ScanResp never contains partial rows (i.e. a single row is never split into different Results)*" ([`streamer.go#L116`](https://github.com/cockroachdb/cockroach/blob/0935372badc46f73ac2660752b8a966edb31ba88/pkg/kv/kvclient/kvstreamer/streamer.go#L116)); the streamer sets `WholeRowsOfSize` on all its batches ([`streamer.go#L1431`](https://github.com/cockroachdb/cockroach/blob/0935372badc46f73ac2660752b8a966edb31ba88/pkg/kv/kvclient/kvstreamer/streamer.go#L1431)).

Forward scans are structurally safe: the forward resume boundary is the boundary row's lowest live key, which is the always-present family-0 key -- a lower bound on every buffered key of the row -- so the whole row defers to the next page naturally.

**To Reproduce**

Unit test against the interceptor (fails on master @ 0935372bad); it mocks the server's documented reverse resume-boundary behavior and asserts (1) no page contains a partial row and (2) every key appears exactly once across pages. It currently fails with `page 1 contains a partial row "b": expected 2, actual 1`.

TestTxnWriteBufferReverseScanPaginationSplitsRow

```go
// TestTxnWriteBufferReverseScanPaginationSplitsRow demonstrates that the
// reverse-scan merge can split a multi-column-family SQL row across two
// paginated responses when the transaction has a buffered write to a column
// family above the row's highest live (committed) family.
//
// The server's reverse-scan resume boundary is row-aligned only with respect
// to live keys: after whole-row trimming, ResumeSpan.EndKey is set to
// (highest live key of the next row to scan).Next() (see
// pebbleMVCCScanner.afterScan). A buffered write to a higher column family of
// that row sorts above ResumeSpan.EndKey, so the merge injects it into the
// tail of the current page while the row's live keys arrive only on the next
// page. Consumers of WholeRowsOfSize (the kvstreamer) assume a response never
// contains a partial row; in the streamer's OutOfOrder mode the two fragments
// arrive in separate Results, with other Results potentially interleaved, and
// the cFetcher emits the same PK twice as two partial rows.
//
// Keys are of the form /. Rows "b", "c", and "d" exist with only
// family 0 live; the transaction buffers a write to "b"'s family 2.
//
// TODO(ssd): This test demonstrates an open bug and currently fails: page 1
// contains only the buffered fragment of row "b". Note that the fix cannot
// simply exclude the buffered key from page 1: the returned resume span must
// also be extended to cover it, or the second check below (no lost writes)
// fails instead.
func TestTxnWriteBufferReverseScanPaginationSplitsRow(t *testing.T) {
defer leaktest.AfterTest(t)()
defer log.Scope(t).Close(t)
ctx := context.Background()
twb, mockSender, _ := makeMockTxnWriteBuffer(ctx)

txn := makeTxnProto()
txn.Sequence = 1
keyA, keyE := roachpb.Key("a"), roachpb.Key("e")
bCF0, bCF2 := roachpb.Key("b/0"), roachpb.Key("b/2")
cCF0 := roachpb.Key("c/0")
dCF0 := roachpb.Key("d/0")

// The full contents of each row in the transaction's view: committed
// family-0 keys plus the buffered write to b's family 2 below.
rowKeys := map[string][]roachpb.Key{
"b": {bCF0, bCF2},
"c": {cCF0},
"d": {dCF0},
}
rowOf := func(k roachpb.Key) string { return string(k[:1]) }

// The transaction writes to a previously-nonexistent column family of row
// "b". The write is buffered.
ba := &kvpb.BatchRequest{}
ba.Header = kvpb.Header{Txn: &txn}
ba.Add(putArgs(bCF2, "b2", txn.Sequence))
br, pErr := twb.SendLocked(ctx, ba)
require.Nil(t, pErr)
require.NotNil(t, br)

// Page 1: reverse scan [a, e) with a key limit. The server returns rows
// "d" and "c" and, after whole-row trimming, a resume span whose EndKey
// is bCF0.Next(): the next key the reverse scan will read is row "b"'s
// highest live key, bCF0. WholeRowsOfSize is set, as the streamer sets
// it; the txnWriteBuffer ignores it.
txn.Sequence = 2
ba = &kvpb.BatchRequest{}
ba.Header = kvpb.Header{Txn: &txn, MaxSpanRequestKeys: 2, WholeRowsOfSize: 2}
ba.Add(&kvpb.ReverseScanRequest{
RequestHeader: kvpb.RequestHeader{Key: keyA, EndKey: keyE, Sequence: txn.Sequence},
})

mockSender.MockSend(func(ba *kvpb.BatchRequest) (*kvpb.BatchResponse, *kvpb.Error) {
require.Len(t, ba.Requests, 1)
require.IsType(t, &kvpb.ReverseScanRequest{}, ba.Requests[0].GetInner())

resp := ba.CreateReply()
resp.Txn = ba.Txn
resp.Responses[0].MustSetInner(&kvpb.ReverseScanResponse{
ResponseHeader: kvpb.ResponseHeader{
NumKeys: 2,
ResumeSpan: &roachpb.Span{Key: keyA, EndKey: bCF0.Next()},
ResumeReason: kvpb.RESUME_KEY_LIMIT,
},
Rows: []roachpb.KeyValue{
{Key: dCF0, Value: roachpb.MakeValueFromString("d0")},
{Key: cCF0, Value: roachpb.MakeValueFromString("c0")},
},
})
return resp, nil
})

br, pErr = twb.SendLocked(ctx, ba)
require.Nil(t, pErr)
require.NotNil(t, br)
page1 := br.Responses[0].GetInner().(*kvpb.ReverseScanResponse)
require.NotNil(t, page1.ResumeSpan)

// Page 2: continue the scan using the resume span returned to the client.
ba = &kvpb.BatchRequest{}
ba.Header = kvpb.Header{Txn: &txn, MaxSpanRequestKeys: 2, WholeRowsOfSize: 2}
ba.Add(&kvpb.ReverseScanRequest{
RequestHeader: kvpb.RequestHeader{
Key: page1.ResumeSpan.Key,
EndKey: page1.ResumeSpan.EndKey,
Sequence: txn.Sequence,
},
})

mockSender.MockSend(func(ba *kvpb.BatchRequest) (*kvpb.BatchResponse, *kvpb.Error) {
require.Len(t, ba.Requests, 1)
req := ba.Requests[0].GetInner().(*kvpb.ReverseScanRequest)

// bCF0 is the only live key below bCF0.Next() in [a, e), regardless
// of how far the first page's resume span extends.
require.True(t, req.EndKey.Compare(bCF0) > 0)
resp := ba.CreateReply()
resp.Txn = ba.Txn
resp.Responses[0].MustSetInner(&kvpb.ReverseScanResponse{
ResponseHeader: kvpb.ResponseHeader{NumKeys: 1},
Rows: []roachpb.KeyValue{
{Key: bCF0, Value: roachpb.MakeValueFromString("b0")},
},
})
return resp, nil
})

br, pErr = twb.SendLocked(ctx, ba)
require.Nil(t, pErr)
require.NotNil(t, br)
page2 := br.Responses[0].GetInner().(*kvpb.ReverseScanResponse)

pages := [][]roachpb.KeyValue{page1.Rows, page2.Rows}

// No response may contain a partial row: WholeRowsOfSize promises that if
// any key of a row is present in a response, all of the row's keys are.
for i, page := range pages {
present := make(map[string]int)
for _, kv := range page {
present[rowOf(kv.Key)]++
}
for row, count := range present {
require.Equal(t, len(rowKeys[row]), count,
"page %d contains a partial row %q", i+1, row)
}
}

// Every key in the transaction's view of [a, e) must appear exactly once
// across the two pages: the buffered write must be neither lost nor
// duplicated.
seen := make(map[string]int)
for _, page := range pages {
for _, kv := range page {
seen[string(kv.Key)]++
}
}
for _, keys := range rowKeys {
for _, k := range keys {
require.Equal(t, 1, seen[string(k)], "key %s", k)
}
}
}
```

**Expected behavior**

A paginated response never contains a partial row (with respect to the transaction's own view, i.e. committed data merged with buffered writes), and each buffered key is returned exactly once across pages.

**Why it is latent (reachability analysis)**

Turning the split row into wrong results requires the streamer's OutOfOrder mode with reverse scans, which is unreachable today:

- the columnar index join hardcodes `reverse=false`;
- the rowexec joinReader sets `reverse` from `spec.ReverseScans`, which execbuilder produces only when the required ordering appends lookup-index columns in reverse direction -- and that same condition sets `MaintainLookupOrdering`, forcing the streamer into InOrder mode;
- InOrder mode delivers a truncated scan's continuation Results adjacently in key order, and the cFetcher already assembles rows spanning adjacent Results (required for `SplitFamilyIDs > 1`, see [`joinreader.go#L548`](https://github.com/cockroachdb/cockroach/blob/0935372badc46f73ac2660752b8a966edb31ba88/pkg/sql/rowexec/joinreader.go#L548) and #113013);
- non-streamer paths (the classic `txnKVFetcher`) preserve contiguity across pages, which the row parsers tolerate.

The safety therefore rests on a stack of incidental invariants in three different layers. Any one change -- reverse support in the columnar index join, reverse OutOfOrder lookup joins, or a consumer that starts relying on the documented "never split" contract -- turns this into silent row corruption (duplicate/partial rows) with no test coverage.

**Proposed fix**

In `mergeWithReverseScanResp`, when the response is paginated and the batch set `WholeRowsOfSize`: defer buffered keys whose row prefix (via `keys.GetRowPrefixLength`, the same decoding the server's whole-row trimming uses) begins below `ResumeSpan.EndKey`, and extend the returned `ResumeSpan.EndKey` to the boundary row's `PrefixEnd()` so the next page picks them up. Excluding without extending would lose the write -- the next page's window doesn't contain the deferred keys otherwise. A test-build assertion on the forward path would enforce the symmetric invariant that today holds structurally.

**Environment**

- master @ 0935372bad (`kv.transaction.write_buffering.enabled = true`, the default)

Jira issue: CRDB-65636

Contributor guide

Open the contributing guide

Research direction

Start in pkg/kv/kvclient/kvcoord/txn_interceptor_write_buffer.go at mergeWithReverseScanResp, then run TestTxnWriteBufferReverseScanPaginationSplitsRow and inspect the referenced reverse-resume boundary behavior. Done means paginated reverse responses preserve WholeRowsOfSize semantics and every buffered key appears exactly once across pages.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
databases
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.