Item deletion doesn't work when deleting during iteration

What version of Go are you using (go version)?

$ go version
go version go1.15.5 windows/amd64

What operating system are you using?

Windows 10 Pro, Version 20.04

What version of Badger are you using?

require github.com/dgraph-io/badger/v2 v2.2007.2

Does this issue reproduce with the latest master?

go get github.com/dgraph-io/badger/v2@master gave me github.com/dgraph-io/badger/v2 v2.0.1-rc1.0.20210105060133-d6666aecfdc3, which is not the latest v2 commit ( 38eb5a1 is the latest v2 commit, before the import path changed to v3), but I gave it a try anyway.

It lead to an error when running the app for a second time though (which my reproduction requires):

panic: while opening memtables error: while opening fid: 1 error: Create a new file
        C:/path/to/go/pkg/mod/github.com/dgraph-io/ristretto@v0.0.4-0.20201224172411-e860a6c48e8a/z/file.go:36

Steps to Reproduce the issue

Run this app two times. The first time with no DB files, so a DB is created. The second time point it to the same DB, so the existing one is used.

go.mod:

module repro/badger-iterator-delete

go 1.15

require github.com/dgraph-io/badger/v2 v2.2007.2

main.go:

package main

import (
	"errors"
	"flag"
	"fmt"
	"os"
	"strconv"
	"sync"
	"time"

	"github.com/dgraph-io/badger/v2"
)

var (
	dbPath  = flag.String("dbPath", "", "Path for BadgerDB files")
	isReset = flag.Bool("reset", false, "Flag for resetting DB (delete and then seed entries)")
)

func main() {
	flag.Parse()

	options := badger.DefaultOptions(*dbPath).WithSyncWrites(true)
	db, err := badger.Open(options)
	if err != nil {
		panic(err)
	}
	defer db.Close()

	// "Reset" if flag is set.
	if *isReset {
		if err = reset(db); err != nil {
			fmt.Println("Error:", err)
			db.Close()
			os.Exit(1)
		}
	}

	wg := sync.WaitGroup{}
	wg.Add(2)

	// Check a bar in a separate goroutine, as it would be in a web service
	go func() {
		// Check if we have a bar
		var bar string
		err = db.View(func(txn *badger.Txn) error {
			key := "bar_123"
			item, err := txn.Get([]byte(key))
			if err != nil {
				return err
			}
			if item.IsDeletedOrExpired() {
				return errors.New("bar was deleted from DB")
			}
			barBytes, err := item.ValueCopy(nil)
			if err != nil {
				return err
			}
			bar = string(barBytes)
			return nil
		})
		if err == badger.ErrKeyNotFound {
			fmt.Println("bar_123 not found")
			wg.Done()
			return
		}
		if err != nil {
			fmt.Println("Error:", err)
			db.Close()
			os.Exit(1)
		}
		fmt.Println("bar_123:", bar)
		wg.Done()
	}()

	// Add a bar in a separate goroutine, as it would be in a web service
	// But make sure it runs after the GET above was already done
	go func() {
		time.Sleep(2 * time.Second)

		err = db.Update(func(txn *badger.Txn) error {
			key := "bar_123"
			return txn.Set([]byte(key), []byte("some value"))
		})
		if err != nil {
			fmt.Println("Error:", err)
			db.Close()
			os.Exit(1)
		}
		fmt.Println("Stored bar_123")
		wg.Done()
	}()

	wg.Wait()
}

func reset(db *badger.DB) error {
	// Delete all foos
	count, err := deleteAll(db, "foo_")
	if err != nil {
		return err
	}
	fmt.Println("Deleted all foos. Count:", count)

	// Delete all bars
	count, err = deleteAll(db, "bar_")
	if err != nil {
		return err
	}
	fmt.Println("Deleted all bars. Count:", count)

	// Store some foos
	err = db.Update(func(txn *badger.Txn) error {
		for i := 1; i <= 500; i++ {
			k := []byte("foo_" + strconv.Itoa(i))
			err := txn.Set(k, []byte("some val"))
			if err != nil {
				return err
			}
		}
		return nil
	})
	if err != nil {
		return err
	}
	fmt.Println("Stored all foos to DB")
	return nil
}

func deleteAll(db *badger.DB, prefix string) (int, error) {
	count := 0
	err := db.Update(func(txn *badger.Txn) error {
		it := txn.NewIterator(badger.DefaultIteratorOptions)
		defer it.Close()

		prefix := []byte(prefix)
		for it.Seek(prefix); it.ValidForPrefix(prefix); it.Next() {
			k := it.Item().Key()
			// This won't disrupt the iterator, as the iterator keeps its view from when the tx began
			if err := txn.Delete(k); err != nil {
				return err
			}
			count++
		}
		return nil
	})
	return count, err
}

What Badger options were set?

See code above:

	options := badger.DefaultOptions(*dbPath).WithSyncWrites(true)
	db, err := badger.Open(options)

What did you do?

Run it two times, like this:

  1. go run . -dbPath "/path/to/db" -reset
  2. go run . -dbPath "/path/to/db" -reset

What did you expect to see?

For the second run, I expected:

Deleted all foos. Count: 500
Deleted all bars. Count: 1
Stored all foos to DB
bar_123 not found
Stored bar_123

So in essence, I expected bar_123 to be deleted by the “reset” which iterates through all bar_-prefixed items and deletes them.

What did you see instead?

For the second run, I got:

Deleted all foos. Count: 500
Deleted all bars. Count: 1
Stored all foos to DB
bar_123: some value
Stored bar_123

So in essence, bar_123 didn’t get deleted in the initial “reset” despite iterating through all bar_-prefixed items and seemingly deleting them (but without effect).

Hey @golfer20, thanks for reaching out.

Please check badger/iterator.go at 88bf5aab9f502198ee9d7079241e34e1279e8d58 · dgraph-io/badger · GitHub. it.Item().Key() is valid as long as item is valid. It gets invalidated as soon as you call next on iterator.

If you use KeyCopy(nil), then it will work for you.

k := it.Item().Key()

Feel free to ask follow up questions.

Hi Naman,

Thanks for the quick reply! And indeed it works when changing Key() to KeyCopy(nil). But I don’t fully understand why, because in the code example don’t I use the key only while it’s valid?
The docs for Key() say:

Key is only valid as long as item is valid, or transaction is valid.

And for item:

This item is only valid until it.Next() gets called.

So looking at the code:

for it.Seek(prefix); it.ValidForPrefix(prefix); it.Next() {
	k := it.Item().Key()
	if err := txn.Delete(k); err != nil {
		return err
	}
}

It’s all in one tx, so the key isn’t invalidated from the end of the tx. And the call to Item() and Key() and the use of the key are all done before the call to it.Next(), so the item should also be valid, no?

Sorry if I’m just not seeing it :see_no_evil:

Ah, I think the answer lies in the Delete() method’s docs:

// The current transaction keeps a reference to the key byte slice argument.
// Users must not modify the key until the end of the transaction.

So due to the it.Next() call the previous item is not valid anymore, thus the key is not valid anymore and thus with the key probably being changed, the deletion has an issue. Got it!

1 Like