cockroachdb / cockroachdb/cockroach
kvcoord: txnWriteBuffer reverse-scan merge can split a multi-column-family row across paginated responses
- 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
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