Skip to content

Commit 95b836d

Browse files
sumeerbholasumeerbhola
committed
storage: implement iterator to interleave separated intents
intentInterleavingIter allows for both physically separate and physically interleaved intents, and makes both look like interleaved intents. It uses two underlying iterators, a MVCCIterator and an EngineIterator, that are kept synchronized. Informs cockroachdb#41720 Release note: None
1 parent ec6cdbc commit 95b836d

11 files changed

Lines changed: 1496 additions & 17 deletions

File tree

‎pkg/keys/keys.go‎

Lines changed: 20 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -393,22 +393,28 @@ func QueueLastProcessedKey(key roachpb.RKey, queue string) roachpb.Key {
393393
}
394394

395395
// LockTableSingleKey creates a key under which all single-key locks for the
396-
// given key can be found. Note that there can be multiple locks for the given
397-
// key, but those are distinguished using the "version" which is not in scope
398-
// of the keys package.
396+
// given key can be found. buf is used as scratch-space to avoid allocations
397+
// -- its contents will be overwritten and not appended to.
398+
// Note that there can be multiple locks for the given key, but those are
399+
// distinguished using the "version" which is not in scope of the keys
400+
// package.
399401
// For a scan [start, end) the corresponding lock table scan is
400402
// [LTSK(start), LTSK(end)).
401-
func LockTableSingleKey(key roachpb.Key) roachpb.Key {
403+
func LockTableSingleKey(key roachpb.Key, buf []byte) (roachpb.Key, []byte) {
404+
// The +3 accounts for the bytesMarker and terminator.
405+
keyLen := len(LocalRangeLockTablePrefix) + len(LockTableSingleKeyInfix) + len(key) + 3
406+
if cap(buf) < keyLen {
407+
buf = make([]byte, 0, keyLen)
408+
} else {
409+
buf = buf[:0]
410+
}
402411
// Don't unwrap any local prefix on key using Addr(key). This allow for
403412
// doubly-local lock table keys. For example, local range descriptor keys can
404413
// be locked during split and merge transactions.
405-
// The +3 account for the bytesMarker and terminator.
406-
buf := make(roachpb.Key, 0,
407-
len(LocalRangeLockTablePrefix)+len(LockTableSingleKeyInfix)+len(key)+3)
408414
buf = append(buf, LocalRangeLockTablePrefix...)
409415
buf = append(buf, LockTableSingleKeyInfix...)
410416
buf = encoding.EncodeBytesAscending(buf, key)
411-
return buf
417+
return buf, buf
412418
}
413419

414420
// DecodeLockTableSingleKey decodes the single-key lock table key to return the key
@@ -448,6 +454,12 @@ func IsLocal(k roachpb.Key) bool {
448454
return bytes.HasPrefix(k, localPrefix)
449455
}
450456

457+
// IsLocalStoreKey performs a cheap check that returns true iff the parameter
458+
// is a local store key.
459+
func IsLocalStoreKey(k roachpb.Key) bool {
460+
return bytes.HasPrefix(k, localStorePrefix)
461+
}
462+
451463
// Addr returns the address for the key, used to lookup the range containing the
452464
// key. In the normal case, this is simply the key's value. However, for local
453465
// keys, such as transaction records, the address is the inner encoded key, with

‎pkg/keys/keys_test.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -718,7 +718,7 @@ func TestLockTableKeyEncodeDecode(t *testing.T) {
718718
}
719719
for _, test := range testCases {
720720
t.Run("", func(t *testing.T) {
721-
ltKey := LockTableSingleKey(test.key)
721+
ltKey, _ := LockTableSingleKey(test.key, nil)
722722
require.True(t, bytes.HasPrefix(ltKey, expectedPrefix))
723723
k, err := DecodeLockTableSingleKey(ltKey)
724724
require.NoError(t, err)

‎pkg/storage/BUILD.bazel‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ go_library(
1414
"error.go",
1515
"file_util.go",
1616
"in_mem.go",
17+
"intent_interleaving_iter.go",
1718
"multi_iterator.go",
1819
"mvcc.go",
1920
"mvcc_incremental_iterator.go",
@@ -81,6 +82,7 @@ go_library(
8182
"//pkg/settings/cluster",
8283
"//pkg/storage/enginepb",
8384
"//pkg/storage/fs",
85+
"//pkg/util",
8486
"//pkg/util/bufalloc",
8587
"//pkg/util/encoding",
8688
"//pkg/util/envutil",
@@ -116,6 +118,7 @@ go_test(
116118
"disk_map_test.go",
117119
"engine_key_test.go",
118120
"engine_test.go",
121+
"intent_interleaving_iter_test.go",
119122
"main_test.go",
120123
"multi_iterator_test.go",
121124
"mvcc_history_test.go",
@@ -147,6 +150,7 @@ go_test(
147150
"//pkg/testutils",
148151
"//pkg/testutils/skip",
149152
"//pkg/testutils/zerofields",
153+
"//pkg/util",
150154
"//pkg/util/caller",
151155
"//pkg/util/encoding",
152156
"//pkg/util/fileutil",

‎pkg/storage/engine.go‎

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -60,7 +60,8 @@ type SimpleMVCCIterator interface {
6060
// NextKey advances the iterator to the next MVCC key. This operation is
6161
// distinct from Next which advances to the next version of the current key
6262
// or the next key if the iterator is currently located at the last version
63-
// for a key.
63+
// for a key. NextKey must not be used to switch iteration direction from
64+
// reverse iteration to forward iteration.
6465
NextKey()
6566
// UnsafeKey returns the same value as Key, but the memory is invalidated on
6667
// the next call to {Next,NextKey,Prev,SeekGE,SeekLT,Close}.
@@ -125,7 +126,8 @@ type MVCCIterator interface {
125126
// and the encoded SST data specified, within the provided key range. Returns
126127
// stats on skipped KVs, or an error if a collision is found.
127128
CheckForKeyCollisions(sstData []byte, start, end roachpb.Key) (enginepb.MVCCStats, error)
128-
// SetUpperBound installs a new upper bound for this iterator.
129+
// SetUpperBound installs a new upper bound for this iterator. The caller can modify
130+
// the parameter after this function returns.
129131
SetUpperBound(roachpb.Key)
130132
// Stats returns statistics about the iterator.
131133
Stats() IteratorStats
@@ -294,7 +296,8 @@ type Reader interface {
294296
NewMVCCIterator(iterKind MVCCIterKind, opts IterOptions) MVCCIterator
295297
// NewEngineIterator returns a new instance of an EngineIterator over this
296298
// engine. The caller must invoke EngineIterator.Close() when finished
297-
// with the iterator to free resources.
299+
// with the iterator to free resources. The caller can change IterOptions
300+
// after this function returns.
298301
NewEngineIterator(opts IterOptions) EngineIterator
299302
}
300303

‎pkg/storage/engine_key.go‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -251,8 +251,9 @@ func (lk LockTableKey) ToEngineKey() EngineKey {
251251
if lk.Strength != lock.Exclusive {
252252
panic("unsupported lock strength")
253253
}
254+
ltKey, _ := keys.LockTableSingleKey(lk.Key, nil)
254255
k := EngineKey{
255-
Key: keys.LockTableSingleKey(lk.Key),
256+
Key: ltKey,
256257
Version: make([]byte, engineKeyVersionLockTableLen),
257258
}
258259
k.Version[0] = byte(lk.Strength)

0 commit comments

Comments
 (0)