Repository: cockroachdb/pebble
Pull request #1922 (2022-08-22 18:41:48)

metamorphic: increase probability of valid SeekPrefixGE calls
This pr increases the probablity of SeekPrefixGE calls which are in
range, and also makes it likely that the key passed to the
SeekPrefixGE function is readable by the iterator.

Currently, we only increase the probablity of valid SeekPrefixGE
calls for iterators created on the DB.

cockroach-teamcity: 

<!-- Reviewable:start -->
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/cockroachdb/pebble/1922)
<!-- Reviewable:end -->

bananabrick: Increase in valid calls after this change:

```
These are valid:
arjunnair@crlMBP-C02FR0UTMD6TMjA4 metamorphic % grep 'SeekPrefixGE.*true' test | wc -l
    7680

These return false:
arjunnair@crlMBP-C02FR0UTMD6TMjA4 metamorphic % grep 'SeekPrefixGE.*false' test | wc -l
   10224

This is the valid + invalid:
arjunnair@crlMBP-C02FR0UTMD6TMjA4 metamorphic % grep 'SeekPrefixGE.*//' test | wc -l   
   17904
arjunnair@crlMBP-C02FR0UTMD6TMjA4 metamorphic % 
```
bananabrick: Open to other approaches too.
bananabrick: Another method would be to generate keys which can't be deleted with some probability on key generation. Then, we can use those for SeekPrefixGE calls.

Patch:
diff --git a/internal/metamorphic/generator.go b/internal/metamorphic/generator.go
index 692732e1..cbc6426c 100644
--- a/internal/metamorphic/generator.go
+++ b/internal/metamorphic/generator.go
@@ -84,21 +84,27 @@ type generator struct {
 	// snapshotID -> snapshot iters: used to keep track of the open iterators on
 	// a snapshot. The iter set value will also be indexed by the readers map.
 	snapshots map[objID]objIDSet
+	// iterSequenceNumber is the metaTimestamp at which the iter was created.
+	iterCreationTimestamp map[objID]int
+	// iterReaderID is a map from an iterID to a readerID.
+	iterReaderID map[objID]objID
 }
 
 func newGenerator(rng *rand.Rand, cfg config, km *keyManager) *generator {
 	g := &generator{
-		cfg:           cfg,
-		rng:           rng,
-		init:          &initOp{},
-		keyManager:    km,
-		liveReaders:   objIDSlice{makeObjID(dbTag, 0)},
-		liveWriters:   objIDSlice{makeObjID(dbTag, 0)},
-		batches:       make(map[objID]objIDSet),
-		iters:         make(map[objID]objIDSet),
-		readers:       make(map[objID]objIDSet),
-		snapshots:     make(map[objID]objIDSet),
-		itersLastOpts: make(map[objID]iterOpts),
+		cfg:                   cfg,
+		rng:                   rng,
+		init:                  &initOp{},
+		keyManager:            km,
+		liveReaders:           objIDSlice{makeObjID(dbTag, 0)},
+		liveWriters:           objIDSlice{makeObjID(dbTag, 0)},
+		batches:               make(map[objID]objIDSet),
+		iters:                 make(map[objID]objIDSet),
+		readers:               make(map[objID]objIDSet),
+		snapshots:             make(map[objID]objIDSet),
+		itersLastOpts:         make(map[objID]iterOpts),
+		iterCreationTimestamp: make(map[objID]int),
+		iterReaderID:          make(map[objID]objID),
 	}
 	// Note that the initOp fields are populated during generation.
 	g.ops = append(g.ops, g.init)
@@ -535,6 +541,8 @@ func (g *generator) newIter() {
 	}
 
 	g.itersLastOpts[iterID] = opts
+	g.iterCreationTimestamp[iterID] = g.keyManager.nextMetaTimestamp()
+	g.iterReaderID[iterID] = readerID
 	g.add(&newIterOp{
 		readerID: readerID,
 		iterID:   iterID,
@@ -585,6 +593,8 @@ func (g *generator) newIterUsingClone() {
 		g.itersLastOpts[iterID] = g.itersLastOpts[existingIterID]
 	}
 
+	g.iterCreationTimestamp[iterID] = g.keyManager.nextMetaTimestamp()
+	g.iterReaderID[iterID] = g.iterReaderID[existingIterID]
 	g.add(&newIterUsingCloneOp{
 		existingIterID: existingIterID,
 		iterID:         iterID,
@@ -755,10 +765,69 @@ func (g *generator) iterSeekGEWithLimit(iterID objID) {
 	})
 }
 
+func (g *generator) randKeyToReadWithinBounds(lower, upper []byte, readerID objID) []*keyMeta {
+	var inRangeKeys []*keyMeta
+	for _, keyMeta := range g.keyManager.byObj[readerID] {
+		posKey := keyMeta.key
+		if g.cmp(posKey, lower) < 0 || g.cmp(posKey, upper) >= 0 {
+			continue
+		}
+		inRangeKeys = append(inRangeKeys, keyMeta)
+	}
+	return inRangeKeys
+}
+
 func (g *generator) iterSeekPrefixGE(iterID objID) {
+	lower := g.itersLastOpts[iterID].lower
+	upper := g.itersLastOpts[iterID].upper
+	iterCreationTimestamp := g.iterCreationTimestamp[iterID]
+	var key []byte
+
+	// We try to make sure that the SeekPrefixGE key is within the iter bounds,
+	// and that the iter can read the key. If the key was created on a batch
+	// which deleted the key, then the key will still be considered visible
+	// by the current logic. We're also not accounting for keys written to
+	// batches which haven't been presisted to the DB. But we're only picking
+	// keys in a best effort manner, and the logic is better than picking a
+	// random key.
+	if g.rng.Intn(10) >= 1 {
+		possibleKeys := make([][]byte, 0, 100)
+		inRangeKeys := g.randKeyToReadWithinBounds(lower, upper, dbObjID)
+		for _, keyMeta := range inRangeKeys {
+			posKey := keyMeta.key
+			var foundWriteWithoutDelete bool
+			for _, update := range keyMeta.updateOps {
+				if update.metaTimestamp > iterCreationTimestamp {
+					break
+				}
+
+				if update.deleted {
+					foundWriteWithoutDelete = false
+				} else {
+					foundWriteWithoutDelete = true
+				}
+			}
+			if foundWriteWithoutDelete {
+				possibleKeys = append(possibleKeys, posKey)
+			}
+		}
+
+		if len(possibleKeys) > 0 {
+			key = []byte(possibleKeys[g.rng.Int31n(int32(len(possibleKeys)))])
+		}
+	}
+
+	if key == nil {
+		// TODO(bananabrick): We should try and use keys within the bounds,
+		// even if we couldn't find any keys visible to the iterator. However,
+		// doing this in experiments didn't really increase the valid
+		// SeekPrefixGE calls by much.
+		key = g.randKeyToRead(0) // 0% new keys
+	}
+
 	g.add(&iterSeekPrefixGEOp{
 		iterID: iterID,
-		key:    g.randKeyToRead(0), // 0% new keys
+		key:    key,
 	})
 }
 
diff --git a/internal/metamorphic/key_manager.go b/internal/metamorphic/key_manager.go
index 6a094d81..33e4a455 100644
--- a/internal/metamorphic/key_manager.go
+++ b/internal/metamorphic/key_manager.go
@@ -32,6 +32,12 @@ func (o objKey) String() string {
 	return fmt.Sprintf("%s:%s", o.id, o.key)
 }
 
+type keyUpdate struct {
+	deleted bool
+	// metaTimestamp at which the write or delete op occurred.
+	metaTimestamp int
+}
+
 // keyMeta is metadata associated with an (objID, key) pair, where objID is
 // a writer containing the key.
 type keyMeta struct {
@@ -49,6 +55,12 @@ type keyMeta struct {
 	// del can be true only if a Delete was added to this writer after the
 	// Sets and Merges counted above.
 	del bool
+
+	// updateOps should always be ordered by non-decreasing metaTimestamp.
+	// updateOps will not be updated if the key is range deleted. Therefore, it
+	// is a best effort sequence of updates to the key. updateOps is used to
+	// determine if an iterator created on the DB can read a certain key.
+	updateOps []keyUpdate
 }
 
 func (m *keyMeta) clear() {
@@ -57,10 +69,11 @@ func (m *keyMeta) clear() {
 	m.singleDel = false
 	m.del = false
 	m.dels = 0
+	m.updateOps = nil
 }
 
 // mergeInto merges this metadata this into the metadata for other.
-func (m *keyMeta) mergeInto(other *keyMeta) {
+func (m *keyMeta) mergeInto(keyManager *keyManager, other *keyMeta) {
 	if other.del && !m.del {
 		// m's Sets and Merges are later.
 		if m.sets > 0 || m.merges > 0 {
@@ -78,7 +91,7 @@ func (m *keyMeta) mergeInto(other *keyMeta) {
 	// maintaining a global invariant that SingleDelete will only be added for
 	// a key that has no inflight Sets or Merges (Sets have made their way to
 	// the DB), and no subsequent Sets or Merges will happen until the
-	// SingleDelete makes its way to th DB.
+	// SingleDelete makes its way to the DB.
 	other.singleDel = other.singleDel || m.singleDel
 	if other.singleDel {
 		if other.sets > 1 || other.merges > 0 || other.dels > 0 {
@@ -86,6 +99,21 @@ func (m *keyMeta) mergeInto(other *keyMeta) {
 				other.sets, other.merges, other.dels))
 		}
 	}
+
+	// Determine if the key is visible or not after the keyMetas are merged.
+	// TODO(bananabrick): We currently only care about key updates which make it
+	// to the DB, since we only use key updates to determine if an iterator
+	// can read a key in the DB. We could extend the timestamp system to add
+	// support for iterators created on batches.
+	if other.del || other.singleDel {
+		other.updateOps = append(
+			other.updateOps, keyUpdate{true, keyManager.nextMetaTimestamp()},
+		)
+	} else {
+		other.updateOps = append(
+			other.updateOps, keyUpdate{false, keyManager.nextMetaTimestamp()},
+		)
+	}
 }
 
 // keyManager tracks the write operations performed on keys in the generation
@@ -102,6 +130,12 @@ func (m *keyMeta) mergeInto(other *keyMeta) {
 type keyManager struct {
 	comparer *base.Comparer
 
+	// metaTimestamp is used to provide a ordering over certain operations like
+	// iter creation, updates to keys. Keeping track of the timestamp allows us
+	// to make determinations such as whether a key will be visible to an
+	// iterator.
+	metaTimestamp int
+
 	// byObjKey tracks the state for each (writer, key) pair. It refers to the
 	// same *keyMeta as in the byObj slices. Using a map allows for fast state
 	// lookups when changing the state based on a writer operation on the key.
@@ -166,6 +200,12 @@ type keyManager struct {
 	//   others.
 }
 
+func (k *keyManager) nextMetaTimestamp() int {
+	ret := k.metaTimestamp
+	k.metaTimestamp++
+	return ret
+}
+
 var dbObjID objID = makeObjID(dbTag, 0)
 
 // newKeyManager returns a pointer to a new keyManager. Callers should
@@ -265,7 +305,7 @@ func (k *keyManager) mergeKeysInto(from, to objID) {
 			k.byObjKey[mTo.String()] = mTo
 		}
 
-		m.mergeInto(mTo)
+		m.mergeInto(k, mTo)
 		msNew = append(msNew, mTo)
 
 		delete(k.byObjKey, m.String()) // Unlink "from".
@@ -322,6 +362,7 @@ func (k *keyManager) update(o op) {
 		meta.sets++ // Update the set count on this specific (id, key) pair.
 		meta.del = false
 		globalMeta.sets++
+		meta.updateOps = append(meta.updateOps, keyUpdate{false, k.nextMetaTimestamp()})
 		if meta.singleDel || globalMeta.singleDel {
 			panic("setting a key that has in-flight SingleDelete")
 		}
@@ -331,6 +372,7 @@ func (k *keyManager) update(o op) {
 		meta.merges++
 		meta.del = false
 		globalMeta.merges++
+		meta.updateOps = append(meta.updateOps, keyUpdate{false, k.nextMetaTimestamp()})
 		if meta.singleDel || globalMeta.singleDel {
 			panic("merging a key that has in-flight SingleDelete")
 		}
@@ -341,6 +383,7 @@ func (k *keyManager) update(o op) {
 		globalMeta.del = true
 		meta.dels++
 		globalMeta.dels++
+		meta.updateOps = append(meta.updateOps, keyUpdate{true, k.nextMetaTimestamp()})
 		if s.writerID == dbObjID {
 			k.checkForDelOrSingleDelTransition(meta, globalMeta)
 		}
@@ -352,6 +395,7 @@ func (k *keyManager) update(o op) {
 		globalMeta := k.globalKeysMap[string(s.key)]
 		meta.singleDel = true
 		globalMeta.singleDel = true
+		meta.updateOps = append(meta.updateOps, keyUpdate{true, k.nextMetaTimestamp()})
 		if s.writerID == dbObjID {
 			k.checkForDelOrSingleDelTransition(meta, globalMeta)
 		}


Test patch:
diff --git a/internal/metamorphic/key_manager_test.go b/internal/metamorphic/key_manager_test.go
index bace751d..97fe25ac 100644
--- a/internal/metamorphic/key_manager_test.go
+++ b/internal/metamorphic/key_manager_test.go
@@ -112,6 +112,9 @@ func TestKeyMeta_MergeInto(t *testing.T) {
 				sets:      1,
 				merges:    0,
 				singleDel: true,
+				updateOps: []keyUpdate{
+					{deleted: true, metaTimestamp: 0},
+				},
 			},
 		},
 		{
@@ -131,6 +134,9 @@ func TestKeyMeta_MergeInto(t *testing.T) {
 				merges: 3,
 				dels:   15,
 				del:    true,
+				updateOps: []keyUpdate{
+					{deleted: true, metaTimestamp: 1},
+				},
 			},
 		},
 		{
@@ -151,13 +157,17 @@ func TestKeyMeta_MergeInto(t *testing.T) {
 				merges: 1,
 				dels:   15,
 				del:    false,
+				updateOps: []keyUpdate{
+					{deleted: false, metaTimestamp: 2},
+				},
 			},
 		},
 	}
 
+	keyManager := newKeyManager()
 	for _, tc := range testCases {
 		t.Run("", func(t *testing.T) {
-			tc.toMerge.mergeInto(&tc.existing)
+			tc.toMerge.mergeInto(keyManager, &tc.existing)
 			require.Equal(t, tc.expected, tc.existing)
 		})
 	}