Repository: petermattis/pebble
Pull request #249 (2019-08-28 13:27:55)

Implement SingleDelete
Informs #222.

In Pebble SingleDelete combined with Delete/Merge, it is converted to Delete. But, since SingleDelete is only suitable for special workloads, comment not mention it. If we commenting on them, someone will try to use that unusual behavior.

ajkr: > Requiring SINGLEDEL to cover exactly one SET and misbehaving badly when that requirement is violated (i.e. accumulating SINGLEDEL records at the bottom level) feels like poor API design.

This doesn't make sense to me. The whole SingleDelete optimization is to drop a SINGLEDEL when it encounters the SET it covers. What about if the SINGLEDEL covers two SETs? The outcome is non-deterministic (which IMO is a worse outcome than tombstone stuck in bottom level). What if the SINGLEDEL covers a MERGE or DELETE? According to this PR it transforms the SINGLEDEL into a DELETE even if it's writing to bottom level, which is the same bad behavior you're asking to avoid.

> Yeah, we're requiring the lot from the user to use SINGLEDEL correctly, but might as well prevent more badness when possible. Not allowing a RANGEDEL to lie between a SINGLEDEL and a SET further burdens the user. Perhaps I'm misjudging how much effort this will be.

I don't think I'm arguing for burdening the user. I'm arguing that if our requirement for SingleDelete is that it deletes "at most one key" rather than "exactly one key", we should clarify that and do all the work to make it happen. I do not understand how not half-supporting an explicitly unsupported use case (SINGLEDEL covering zero keys) is "poor API design".
petermattis: > > Requiring SINGLEDEL to cover exactly one SET and misbehaving badly when that requirement is violated (i.e. accumulating SINGLEDEL records at the bottom level) feels like poor API design.
> 
> This doesn't make sense to me. The whole SingleDelete optimization is to drop a SINGLEDEL when it encounters the SET it covers. What about if the SINGLEDEL covers two SETs? The outcome is non-deterministic (which IMO is a worse outcome than tombstone stuck in bottom level). What if the SINGLEDEL covers a MERGE or DELETE? According to this PR it transforms the SINGLEDEL into a DELETE even if it's writing to bottom level, which is the same bad behavior you're asking to avoid.

Heh, I suppose referring to good API design anywhere near SINGLEDEL is problematic as the API is fundamentally fragile.

Let me take a step back. I'd like to have SINGLEDEL provide reasonable behavior when possible. A SINGLEDEL covering two SETs is going to be non-deterministic as that is fundamental to the SINGLEDEL operation. But what about a SINGELDEL covering 0 records? Or one covering a MERGE or a DELETE? I think we can define reasonable semantics for all of these cases **and** I think those semantics are not onerous to implement. I don't believe we (CRDB) need those semantics, but I think we (Pebble) should implement something to cover those cases, whether it be a fatal error, a panic, or something.

The semantics I'm arguing for is that a SINGLEDEL acts like DEL except that when it is compacted with a SET (in the same snapshot stripe) it is elided from the output. A SINGLEDEL at the bottom level of the tree should be elided. SINGEDEL covering a MERGE/DELETE should be transformed into a DEL. My intuition is that implementing these semantics will be as much work as implementing and testing any other semantics (including crashing). 

> I don't think I'm arguing for burdening the user. I'm arguing that if our requirement for SingleDelete is that it deletes "at most one SET" rather than "exactly one SET", we should clarify that and do all the work to make it happen. 

Ack, I think we should clarify the semantics, and I think they should be "SingleDelete deletes at most one SET", though the phrasing on that is slightly problematic. SINGLEDEL might delete more that one SET (depending on the order of compactions). Perhaps, "SINGLEDEL can delete zero or one SET records. If there are two or more SET records (i.e. a record was overwritten), the behavior of SINGLEDEL is non-deterministic."

> We should consider whether general API misuse should cause the DB to go into read-only mode or crash, but that's separate from the question of whether SINGLEDEL covering zero SETs should be supported or not.

When possible I think we should provide guard rails. Crashing is reasonable in some cases, or returning an error. For example, Pebble returns an error if you close a DB with open iterators as this is indicative of an iterator leak. And operations on a closed DB return an error. Unfortunately, with SINGLEDEL there is a misuse (SINGLEDEL covering 2 or more SETs) which we can't efficiently detect. 

Patch:
diff --git a/batch.go b/batch.go
index 4d4334c..3e89d81 100644
--- a/batch.go
+++ b/batch.go
@@ -526,6 +526,59 @@ func (b *Batch) DeleteDeferred(keyLen int, _ *WriteOptions) (*DeferredBatchOp, e
 	return &b.deferredOp, nil
 }
 
+// SingleDelete adds an action to the batch that single deletes the entry for key.
+// See Writer.SingleDelete for more details on the semantics of SingleDelete.
+//
+// It is safe to modify the contents of the arguments after SingleDelete returns.
+func (b *Batch) SingleDelete(key []byte, _ *WriteOptions) error {
+	deferredOp, err := b.SingleDeleteDeferred(len(key), nil)
+	if err != nil {
+		return err
+	}
+	copy(deferredOp.Key, key)
+	// TODO(peter): Manually inline DeferredBatchOp.Finish(). Mid-stack inlining
+	// in go1.13 will remove the need for this.
+	if b.index != nil {
+		if err := b.index.Add(deferredOp.offset); err != nil {
+			// We never add duplicate entries, so an error should never occur.
+			panic(err)
+		}
+	}
+	return nil
+}
+
+// SingleDeleteDeferred is similar to SingleDelete in that it adds a single delete
+// operation to the batch, except it only takes in key/value lengths instead of
+// complete slices, letting the caller encode into those objects and then call
+// Finish() on the returned object.
+func (b *Batch) SingleDeleteDeferred(keyLen int, _ *WriteOptions) (*DeferredBatchOp, error) {
+	// Code duplication with Delete is so that the Delete case (where byte
+	// slices are provided) can preserve the fast path.
+	if len(b.storage.data) == 0 {
+		b.init(keyLen + binary.MaxVarintLen64 + batchHeaderLen)
+	}
+	if !b.increment() {
+		return nil, ErrInvalidBatch
+	}
+
+	b.memTableSize += memTableEntrySize(keyLen, 0)
+
+	pos := len(b.storage.data)
+	b.deferredOp.offset = uint32(pos)
+	b.grow(1 + maxVarintLen32 + keyLen)
+	b.storage.data[pos] = byte(InternalKeyKindSingleDelete)
+	pos++
+	varlen1 := putUvarint32(b.storage.data[pos:], uint32(keyLen))
+	pos += varlen1
+	b.deferredOp.Key = b.storage.data[pos : pos+keyLen]
+	b.deferredOp.Value = nil
+
+	b.storage.data = b.storage.data[:len(b.storage.data)-(maxVarintLen32-varlen1)]
+
+	b.deferredOp.index = b.index
+	return &b.deferredOp, nil
+}
+
 // DeleteRange deletes all of the keys (and values) in the range [start,end)
 // (inclusive on start, exclusive on end).
 //
diff --git a/compaction_iter.go b/compaction_iter.go
index f3aa040..3ddf14f 100644
--- a/compaction_iter.go
+++ b/compaction_iter.go
@@ -207,7 +207,7 @@ func (i *compactionIter) Next() (*InternalKey, []byte) {
 	for i.iterKey != nil {
 		i.key = *i.iterKey
 		switch i.key.Kind() {
-		case InternalKeyKindDelete:
+		case InternalKeyKindDelete, InternalKeyKindSingleDelete:
 			// If we're at the last snapshot stripe and the tombstone can be elided
 			// skip to the next stripe (which will be the next user key).
 			if i.curSnapshotIdx == 0 && i.elideTombstone(i.key.UserKey) {
@@ -216,11 +216,21 @@ func (i *compactionIter) Next() (*InternalKey, []byte) {
 				continue
 			}
 
-			i.saveKey()
-			i.value = i.iterValue
-			i.valid = true
-			i.skip = true
-			return &i.key, i.value
+			switch i.key.Kind() {
+			case InternalKeyKindDelete:
+				i.saveKey()
+				i.value = i.iterValue
+				i.valid = true
+				i.skip = true
+				return &i.key, i.value
+
+			case InternalKeyKindSingleDelete:
+				if i.singleDeleteNext() {
+					return &i.key, i.value
+				}
+
+				continue
+			}
 
 		case InternalKeyKindRangeDelete:
 			i.key = i.cloneKey(i.key)
@@ -384,6 +394,45 @@ func (i *compactionIter) mergeNext() (*InternalKey, []byte) {
 	}
 }
 
+func (i *compactionIter) singleDeleteNext() bool {
+	// Save the current key.
+	i.saveKey()
+	i.valid = true
+
+	// Loop until finds a key to be passed to the next level.
+	for {
+		if !i.nextInStripe() {
+			i.skip = false
+			return true
+		}
+
+		key := i.iterKey
+		switch key.Kind() {
+		case InternalKeyKindDelete, InternalKeyKindMerge:
+			// We've hit a Delete or Merge, transform the SingleDelete into a full Delete.
+			i.key.SetKind(InternalKeyKindDelete)
+			i.skip = true
+			return true
+
+		case InternalKeyKindSet:
+			i.nextInStripe()
+			i.valid = false
+			return false
+
+		case InternalKeyKindSingleDelete:
+			continue
+
+		case InternalKeyKindRangeDelete:
+			i.valid = false
+			return false
+
+		default:
+			i.err = fmt.Errorf("invalid internal key kind: %d", i.iterKey.Kind())
+			return false
+		}
+	}
+}
+
 func (i *compactionIter) saveKey() {
 	i.keyBuf = append(i.keyBuf[:0], i.iterKey.UserKey...)
 	i.key.UserKey = i.keyBuf
diff --git a/db.go b/db.go
index bce86fd..9be4d86 100644
--- a/db.go
+++ b/db.go
@@ -89,6 +89,26 @@ type Writer interface {
 	// It is safe to modify the contents of the arguments after Delete returns.
 	Delete(key []byte, o *WriteOptions) error
 
+	// SingleDelete is similar to Delete in that it deletes the value for the given key. Like Delete,
+	// it is a blind operation that will succeed even if the given key does not exist.
+	//
+	// WARNING: Undefined (non-deterministic) behavior will result if a key is overwritten and
+	// then deleted using SingleDelete. The record may appear deleted immediately, but be
+	// resurrected at a later time after compactions have been performed. Or the record may
+	// be deleted permanently. A Delete operation lays down a "tombstone" which shadows all
+	// previous versions of a key. The SingleDelete operation is akin to "anti-matter" and will
+	// only delete the most recently written version for a key. These different semantics allow
+	// the DB to avoid propagating a SingleDelete operation during a compaction as soon as the
+	// corresponding Set operation is encountered. These semantics require extreme care to handle
+	// properly. Only use if you have a workload where the performance gain is critical and you
+	// can guarantee that a record is written once and then deleted once.
+	//
+	// SingleDelete is internally transformed into a Delete if the most recent record for a key is either
+	// a Merge or Delete record.
+	//
+	// It is safe to modify the contents of the arguments after SingleDelete returns.
+	SingleDelete(key []byte, o *WriteOptions) error
+
 	// DeleteRange deletes all of the keys (and values) in the range [start,end)
 	// (inclusive on start, exclusive on end).
 	//
@@ -328,6 +348,17 @@ func (d *DB) Delete(key []byte, opts *WriteOptions) error {
 	return d.Apply(b, opts)
 }
 
+// SingleDelete adds an action to the batch that single deletes the entry for key.
+// See Writer.SingleDelete for more details on the semantics of SingleDelete.
+//
+// It is safe to modify the contents of the arguments after SingleDelete returns.
+func (d *DB) SingleDelete(key []byte, opts *WriteOptions) error {
+	b := newBatch(d)
+	defer b.release()
+	_ = b.SingleDelete(key, opts)
+	return d.Apply(b, opts)
+}
+
 // DeleteRange deletes all of the keys (and values) in the range [start,end)
 // (inclusive on start, exclusive on end).
 //
diff --git a/internal.go b/internal.go
index f8c017d..82338e9 100644
--- a/internal.go
+++ b/internal.go
@@ -17,6 +17,7 @@ const (
 	InternalKeyKindSet             = base.InternalKeyKindSet
 	InternalKeyKindMerge           = base.InternalKeyKindMerge
 	InternalKeyKindLogData         = base.InternalKeyKindLogData
+	InternalKeyKindSingleDelete    = base.InternalKeyKindSingleDelete
 	InternalKeyKindRangeDelete     = base.InternalKeyKindRangeDelete
 	InternalKeyKindMax             = base.InternalKeyKindMax
 	InternalKeyKindInvalid         = base.InternalKeyKindInvalid
diff --git a/internal/base/internal.go b/internal/base/internal.go
index bc62b6a..0c1b7f9 100644
--- a/internal/base/internal.go
+++ b/internal/base/internal.go
@@ -25,7 +25,7 @@ const (
 	// InternalKeyKindColumnFamilyDeletion                     = 4
 	// InternalKeyKindColumnFamilyValue                        = 5
 	// InternalKeyKindColumnFamilyMerge                        = 6
-	// InternalKeyKindSingleDelete                             = 7
+	InternalKeyKindSingleDelete = 7
 	// InternalKeyKindColumnFamilySingleDelete                 = 8
 	// InternalKeyKindBeginPrepareXID                          = 9
 	// InternalKeyKindEndPrepareXID                            = 10
@@ -67,13 +67,14 @@ const (
 )
 
 var internalKeyKindNames = []string{
-	InternalKeyKindDelete:      "DEL",
-	InternalKeyKindSet:         "SET",
-	InternalKeyKindMerge:       "MERGE",
-	InternalKeyKindLogData:     "LOGDATA",
-	InternalKeyKindRangeDelete: "RANGEDEL",
-	InternalKeyKindMax:         "MAX",
-	InternalKeyKindInvalid:     "INVALID",
+	InternalKeyKindDelete:       "DEL",
+	InternalKeyKindSet:          "SET",
+	InternalKeyKindMerge:        "MERGE",
+	InternalKeyKindLogData:      "LOGDATA",
+	InternalKeyKindSingleDelete: "SINGLEDEL",
+	InternalKeyKindRangeDelete:  "RANGEDEL",
+	InternalKeyKindMax:          "MAX",
+	InternalKeyKindInvalid:      "INVALID",
 }
 
 func (k InternalKeyKind) String() string {
@@ -130,12 +131,13 @@ func MakeRangeDeleteSentinelKey(userKey []byte) InternalKey {
 }
 
 var kindsMap = map[string]InternalKeyKind{
-	"DEL":      InternalKeyKindDelete,
-	"RANGEDEL": InternalKeyKindRangeDelete,
-	"SET":      InternalKeyKindSet,
-	"MERGE":    InternalKeyKindMerge,
-	"INVALID":  InternalKeyKindInvalid,
-	"MAX":      InternalKeyKindMax,
+	"DEL":       InternalKeyKindDelete,
+	"SINGLEDEL": InternalKeyKindSingleDelete,
+	"RANGEDEL":  InternalKeyKindRangeDelete,
+	"SET":       InternalKeyKindSet,
+	"MERGE":     InternalKeyKindMerge,
+	"INVALID":   InternalKeyKindInvalid,
+	"MAX":       InternalKeyKindMax,
 }
 
 // ParseInternalKey parses the string representation of an internal key. The
diff --git a/iterator.go b/iterator.go
index 1ebcffd..0059353 100644
--- a/iterator.go
+++ b/iterator.go
@@ -59,7 +59,7 @@ func (i *Iterator) findNextEntry() bool {
 	for i.iterKey != nil {
 		key := *i.iterKey
 		switch key.Kind() {
-		case InternalKeyKindDelete:
+		case InternalKeyKindDelete, InternalKeyKindSingleDelete:
 			i.nextUserKey()
 			continue
 
@@ -127,7 +127,7 @@ func (i *Iterator) findPrevEntry() bool {
 		}
 
 		switch key.Kind() {
-		case InternalKeyKindDelete:
+		case InternalKeyKindDelete, InternalKeyKindSingleDelete:
 			i.value = nil
 			i.valid = false
 			i.iterKey, i.iterValue = i.iter.Prev()
@@ -226,7 +226,7 @@ func (i *Iterator) mergeNext(key InternalKey) bool {
 			return true
 		}
 		switch key.Kind() {
-		case InternalKeyKindDelete:
+		case InternalKeyKindDelete, InternalKeyKindSingleDelete:
 			// We've hit a deletion tombstone. Return everything up to this
 			// point.
 			return true
diff --git a/mem_table.go b/mem_table.go
index 5cdf439..48a03ec 100644
--- a/mem_table.go
+++ b/mem_table.go
@@ -112,10 +112,12 @@ func (m *memTable) get(key []byte) (value []byte, err error) {
 	if !m.equal(key, ikey.UserKey) {
 		return nil, ErrNotFound
 	}
-	if ikey.Kind() == InternalKeyKindDelete {
+	switch ikey.Kind() {
+	case InternalKeyKindDelete, InternalKeyKindSingleDelete:
 		return nil, ErrNotFound
+	default:
+		return val, nil
 	}
-	return val, nil
 }
 
 // Prepare reserves space for the batch in the memtable and references the
diff --git a/tool/wal.go b/tool/wal.go
index 437730f..2cea021 100644
--- a/tool/wal.go
+++ b/tool/wal.go
@@ -127,6 +127,8 @@ func (w *walT) runDump(cmd *cobra.Command, args []string) {
 						w.fmtValue.fn(stdout, value)
 					case base.InternalKeyKindLogData:
 						w.fmtValue.fn(stdout, ukey)
+					case base.InternalKeyKindSingleDelete:
+						w.fmtKey.fn(stdout, ukey)
 					case base.InternalKeyKindRangeDelete:
 						w.fmtKey.fn(stdout, ukey)
 						stdout.Write([]byte{','})


Test patch:
diff --git a/batch_test.go b/batch_test.go
index 83cc543..acb98a3 100644
--- a/batch_test.go
+++ b/batch_test.go
@@ -47,13 +47,16 @@ func TestBatch(t *testing.T) {
 		{InternalKeyKindSet, "roses", "red"},
 		{InternalKeyKindSet, "violets", "blue"},
 		{InternalKeyKindDelete, "roses", ""},
+		{InternalKeyKindSingleDelete, "roses", ""},
 		{InternalKeyKindSet, "", ""},
 		{InternalKeyKindSet, "", "non-empty"},
 		{InternalKeyKindDelete, "", ""},
+		{InternalKeyKindSingleDelete, "", ""},
 		{InternalKeyKindSet, "grass", "green"},
 		{InternalKeyKindSet, "grass", "greener"},
 		{InternalKeyKindSet, "eleventy", strings.Repeat("!!11!", 100)},
 		{InternalKeyKindDelete, "nosuchkey", ""},
+		{InternalKeyKindSingleDelete, "nosuchkey", ""},
 		{InternalKeyKindSet, "binarydata", "\x00"},
 		{InternalKeyKindSet, "binarydata", "\xff"},
 		{InternalKeyKindMerge, "merge", "mergedata"},
@@ -73,6 +76,8 @@ func TestBatch(t *testing.T) {
 			_ = b.Merge([]byte(tc.key), []byte(tc.value), nil)
 		case InternalKeyKindDelete:
 			_ = b.Delete([]byte(tc.key), nil)
+		case InternalKeyKindSingleDelete:
+			_ = b.SingleDelete([]byte(tc.key), nil)
 		case InternalKeyKindRangeDelete:
 			_ = b.DeleteRange([]byte(tc.key), []byte(tc.value), nil)
 		case InternalKeyKindLogData:
@@ -103,6 +108,11 @@ func TestBatch(t *testing.T) {
 			copy(d.Key, key)
 			copy(d.Value, value)
 			d.Finish()
+		case InternalKeyKindSingleDelete:
+			d, _ := b.SingleDeleteDeferred(len(key), nil)
+			copy(d.Key, key)
+			copy(d.Value, value)
+			d.Finish()
 		case InternalKeyKindRangeDelete:
 			d, _ := b.DeleteRangeDeferred(len(key), len(value), nil)
 			copy(d.Key, key)
diff --git a/db_test.go b/db_test.go
index 52b0ae9..103b3d4 100644
--- a/db_test.go
+++ b/db_test.go
@@ -506,6 +506,109 @@ func TestGetMerge(t *testing.T) {
 	}
 }
 
+func TestSingleDeleteGet(t *testing.T) {
+	d, err := Open("", &Options{
+		FS: vfs.NewMem(),
+	})
+	if err != nil {
+		t.Fatal(err)
+	}
+	defer func() {
+		if err := d.Close(); err != nil {
+			t.Fatal(err)
+		}
+	}()
+
+	key := []byte("key")
+	val := []byte("val")
+
+	d.Set(key, val, nil)
+	verifyGet(t, d, key, val)
+
+	key2 := []byte("key2")
+	val2 := []byte("val2")
+
+	d.Set(key2, val2, nil)
+	verifyGet(t, d, key2, val2)
+
+	d.SingleDelete(key2, nil)
+	verifyGetNotFound(t, d, key2)
+}
+
+func TestSingleDeleteFlush(t *testing.T) {
+	d, err := Open("", &Options{
+		FS: vfs.NewMem(),
+	})
+	if err != nil {
+		t.Fatal(err)
+	}
+	defer func() {
+		if err := d.Close(); err != nil {
+			t.Fatal(err)
+		}
+	}()
+
+	key := []byte("key")
+	valFirst := []byte("first")
+	valSecond := []byte("second")
+	key2 := []byte("key2")
+	val2 := []byte("val2")
+
+	d.Set(key, valFirst, nil)
+	d.Set(key2, val2, nil)
+	d.Flush()
+
+	d.SingleDelete(key, nil)
+	d.Set(key, valSecond, nil)
+	d.Delete(key2, nil)
+	d.Set(key2, val2, nil)
+	d.Flush()
+
+	d.SingleDelete(key, nil)
+	d.Delete(key2, nil)
+	d.Flush()
+
+	verifyGetNotFound(t, d, key)
+	verifyGetNotFound(t, d, key2)
+}
+
+func TestUnremovableSingleDelete(t *testing.T) {
+	d, err := Open("", &Options{
+		FS: vfs.NewMem(),
+	})
+	if err != nil {
+		t.Fatal(err)
+	}
+	defer func() {
+		if err := d.Close(); err != nil {
+			t.Fatal(err)
+		}
+	}()
+
+	key := []byte("key")
+	valFirst := []byte("valFirst")
+	valSecond := []byte("valSecond")
+
+	d.Set(key, valFirst, nil)
+	ss := d.NewSnapshot()
+	d.SingleDelete(key, nil)
+	d.Set(key, valSecond, nil)
+	d.Flush()
+
+	verifyGetSnapshot(t, ss, key, valFirst)
+	verifyGet(t, d, key, valSecond)
+
+	d.SingleDelete(key, nil)
+
+	verifyGetSnapshot(t, ss, key, valFirst)
+	verifyGetNotFound(t, d, key)
+
+	d.Flush()
+
+	verifyGetSnapshot(t, ss, key, valFirst)
+	verifyGetNotFound(t, d, key)
+}
+
 func TestIterLeak(t *testing.T) {
 	for _, leak := range []bool{true, false} {
 		t.Run(fmt.Sprintf("leak=%t", leak), func(t *testing.T) {
@@ -771,3 +874,87 @@ func TestDBConcurrentCommitCompactFlush(t *testing.T) {
 		t.Fatal(err)
 	}
 }
+
+func BenchmarkDelete(b *testing.B) {
+	rng := rand.New(rand.NewSource(uint64(time.Now().UnixNano())))
+	const keyCount = 10000
+	var keys [keyCount][]byte
+	for i := 0; i < keyCount; i++ {
+		keys[i] = []byte(strconv.Itoa(rng.Int()))
+	}
+	val := bytes.Repeat([]byte("x"), 10)
+
+	benchmark := func(b *testing.B, useSingleDelete bool) {
+		d, err := Open(
+			"",
+			&Options{
+				FS: vfs.NewMem(),
+			})
+		if err != nil {
+			b.Fatal(err)
+		}
+		defer func() {
+			if err := d.Close(); err != nil {
+				b.Fatal(err)
+			}
+		}()
+
+		b.StartTimer()
+		for _, key := range keys {
+			d.Set(key, val, nil)
+			if useSingleDelete {
+				d.SingleDelete(key, nil)
+			} else {
+				d.Delete(key, nil)
+			}
+		}
+		// Manually flush as it is flushing/compaction where SingleDelete
+		// performance shows up. With SingleDelete, we can elide all of the
+		// SingleDelete and Set records.
+		if err := d.Flush(); err != nil {
+			b.Fatal(err)
+		}
+		b.StopTimer()
+	}
+
+	b.Run("delete", func(b *testing.B) {
+		for i := 0; i < b.N; i++ {
+			benchmark(b, false)
+		}
+	})
+
+	b.Run("single-delete", func(b *testing.B) {
+		for i := 0; i < b.N; i++ {
+			benchmark(b, true)
+		}
+	})
+}
+
+func verifyGet(t *testing.T, d *DB, key, expected []byte) {
+	val, err := d.Get(key)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if !bytes.Equal(expected, val) {
+		t.Fatalf("expected %s, but got %s", expected, val)
+	}
+}
+
+func verifyGetNotFound(t *testing.T, d *DB, key []byte) {
+	val, err := d.Get(key)
+	if err != base.ErrNotFound {
+		t.Fatalf("expected nil, but got %s", val)
+	}
+}
+
+func verifyGetSnapshot(t *testing.T, ss *Snapshot, key, expected []byte) {
+	val, err := ss.Get(key)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if !bytes.Equal(expected, val) {
+		t.Fatalf("expected %s, but got %s", expected, val)
+	}
+}
diff --git a/testdata/compaction_iter b/testdata/compaction_iter
index 0f549ca..488b451 100644
--- a/testdata/compaction_iter
+++ b/testdata/compaction_iter
@@ -561,3 +561,254 @@ a#2,1:a
 b#2,1:b
 c#2,1:c
 .
+
+define
+a.SINGLEDEL.1:
+----
+
+iter
+first
+next
+----
+a#1,7:
+.
+
+iter elide-tombstones=true
+first
+----
+.
+
+define
+a.SINGLEDEL.2:
+a.SINGLEDEL.1:
+----
+
+iter
+first
+next
+----
+a#2,7:
+.
+
+define
+a.SINGLEDEL.3:
+a.SINGLEDEL.2:
+a.SET.1:a
+----
+
+iter
+first
+----
+.
+
+define
+a.SINGLEDEL.2:
+a.DEL.1:
+----
+
+iter
+first
+next
+----
+a#2,0:
+.
+
+iter elide-tombstones=true
+first
+----
+.
+
+define
+a.SINGLEDEL.2:
+a.MERGE.1:
+----
+
+iter
+first
+next
+----
+a#2,0:
+.
+
+iter elide-tombstones=true
+first
+----
+.
+
+define
+a.SINGLEDEL.2:
+a.SET.1:b
+----
+
+iter
+first
+----
+.
+
+define
+a.SET.2:b
+a.SINGLEDEL.1:
+----
+
+iter
+first
+next
+----
+a#2,1:b
+.
+
+define
+a.SINGLEDEL.2:
+a.SET.1:b
+b.SET.3:c
+----
+
+iter
+first
+next
+----
+b#3,1:c
+.
+
+define
+a.SINGLEDEL.3:
+a.SET.2:b
+a.SET.1:a
+----
+
+iter
+first
+next
+----
+a#1,1:a
+.
+
+define
+a.SINGLEDEL.3:
+a.MERGE.2:b
+a.MERGE.1:a
+----
+
+iter
+first
+next
+----
+a#3,0:
+.
+
+define
+a.SINGLEDEL.4:
+a.SET.3:val
+a.SINGLEDEL.2:
+a.SET.1:val
+----
+
+iter
+first
+----
+.
+
+iter snapshots=2
+first
+next
+next
+----
+a#2,7:
+a#1,1:val
+.
+
+define
+a.SINGLEDEL.4:
+a.SET.3:val
+a.DEL.2:
+a.SET.1:val
+----
+
+iter
+first
+next
+----
+a#2,0:
+.
+
+iter snapshots=2
+first
+next
+next
+----
+a#2,0:
+a#1,1:val
+.
+
+iter snapshots=3
+first
+next
+----
+a#2,0:
+.
+
+iter snapshots=(2,3)
+first
+next
+next
+----
+a#2,0:
+a#1,1:val
+.
+
+define
+a.SINGLEDEL.4:
+a.SET.3:c
+a.MERGE.2:b
+a.SET.1:a
+----
+
+iter
+first
+next
+----
+a#2,1:ba
+.
+
+iter snapshots=2
+first
+next
+next
+----
+a#2,2:b
+a#1,1:a
+.
+
+iter snapshots=3
+first
+next
+----
+a#2,1:ba
+.
+
+iter snapshots=(2,3,4)
+first
+next
+next
+next
+next
+----
+a#4,7:
+a#3,1:c
+a#2,2:b
+a#1,1:a
+.
+
+define
+a.SINGLEDEL.3:
+a.RANGEDEL.2:c
+a.SET.1:val
+----
+
+iter
+first
+tombstones
+----
+.
+a-c#2
+.
diff --git a/testdata/iterator b/testdata/iterator
index 3b13ea6..43f939d 100644
--- a/testdata/iterator
+++ b/testdata/iterator
@@ -1190,3 +1190,146 @@ next
 a:a
 b:b
 .
+
+define
+a.SINGLEDEL.1:
+----
+
+iter seq=2
+first
+----
+.
+
+define
+a.SINGLEDEL.2:
+a.SINGLEDEL.1:
+----
+
+iter seq=3
+first
+----
+.
+
+define
+a.SINGLEDEL.2:
+a.DEL.1:
+----
+
+iter seq=3
+first
+----
+.
+
+define
+a.SINGLEDEL.2:
+a.MERGE.1:
+----
+
+iter seq=3
+first
+----
+.
+
+define
+a.SINGLEDEL.2:
+a.SET.1:b
+----
+
+iter seq=3
+first
+----
+.
+
+define
+a.SET.2:b
+a.SINGLEDEL.1:
+----
+
+iter seq=3
+first
+next
+----
+a:b
+.
+
+define
+a.SINGLEDEL.2:
+a.SET.1:b
+b.SET.3:c
+----
+
+iter seq=4
+first
+next
+----
+b:c
+.
+
+define
+a.SINGLEDEL.3:
+a.SET.2:b
+a.SET.1:a
+----
+
+iter
+first
+----
+.
+
+define
+a.SINGLEDEL.3:
+a.MERGE.2:b
+a.MERGE.1:a
+----
+
+iter seq=4
+first
+----
+.
+
+define
+a.SINGLEDEL.4:
+a.SET.3:val
+a.SINGLEDEL.2:
+a.SET.1:val
+----
+
+iter seq=5
+first
+----
+.
+
+define
+a.SINGLEDEL.4:
+a.SET.3:val
+a.DEL.2:
+a.SET.1:val
+----
+
+iter seq=5
+first
+----
+.
+
+define
+a.SINGLEDEL.4:
+a.SET.3:c
+a.MERGE.2:b
+a.SET.1:a
+----
+
+iter seq=5
+first
+----
+.
+
+define
+a.SINGLEDEL.3:
+a.RANGEDEL.2:c
+a.SET.1:val
+----
+
+iter seq=4
+first
+----
+.