Reverse Iterator does not seem to be working

Users Badger
1

I want to provide a “tail” function for my eventstore I’m building on top of Badger, so that any query microservices can detect if there are changes since the last time it looked. The events are stored with a concatenated key in the format:

aggregate|key|eventId

The eventIds are order dependent, so when I do a normal iteration over the prefix for a record (aggregate|key) I get the events in the order that they happened.

The following works, but it will take longer depending on how many records are in badger:

var lastKey string
prefix := strings.Join([]string{aggregate, key}, separator)
err = db.View(func(txn *badger.Txn) error {
	opts := badger.DefaultIteratorOptions
	opts.PrefetchValues = false // keys only
	opts.Prefix = []byte(prefix)
	opts.Reverse = true

	it := txn.NewIterator(opts)
	defer it.Close()

	for it.Rewind(); it.Valid(); it.Next(){
		key := string(it.Item().Key())
		split := strings.Split(key, separator)
		lastKey = split[len(split)-1]
	}

	return nil
})

Instead, I would prefer to change the iterator options to iterate in reverse and I only get the last item:

opts := badger.DefaultIteratorOptions
opts.PrefetchValues = false // keys only
opts.Prefix = []byte(prefix)

it := txn.NewIterator(opts)
defer it.Close()
it.Rewind()
if it.Valid() {
	key := string(it.Item().Key())
	split := strings.Split(key, separator)
	lastKey = split[len(split)-1]
}

However, when I do that, the iterator is never valid. I have to always iterate forward or I won’t get a result. For the types of records I’m dealing with right now, it’s a low number of events per entity (aggregate|key).

Other relevant information: Windows, go 1.16, badger v3.2011.1, CGO_ENABLED=0

I am aware that Windows is not fully supported, but outside of timing issues on that platform, it seems like the rest of the functionality still works. Windows is the dev platform, not the deployment platform

2

Duplicate of Reverse Seek(prefix) not working as expected.
Please mark this as solved if it answers yoursquery.

3

Sort of? So here’s the thing with the iterator as it stands now. It fails to function like just about any other iterator I know, forward or reverse.

Specifically this does not work because Rewind() doesn’t append the magic character:

opts := badger.DefaultIteratorOptions
opts.PrefetchValues = false // keys only
opts.Prefix = []byte(prefix)
opts.Reverse = true

it := txn.NewIterator(opts)
defer it.Close()
it.Rewind()
if it.Valid() {
	key := string(it.Item().Key())
	split := strings.Split(key, separator)
	lastKey = split[len(split)-1]
}

This is due to the way the iterator works behind the scenes. Nor does this work:

opts := badger.DefaultIteratorOptions
opts.PrefetchValues = false // keys only
opts.Prefix = []byte(prefix)
opts.Prefix = append(opts.Prefix, 0xff)
opts.Reverse = true

it := txn.NewIterator(opts)
defer it.Close()
it.Rewind()
if it.Valid() {
	key := string(it.Item().Key())
	split := strings.Split(key, separator)
	lastKey = split[len(split)-1]
}

That passes the it.Rewind() call, but fails the it.Valid() call because the current key does not begin with the prefix + 0xff. The only way to make reverse iteration work is to provide two different values, and use Seek() and ValidForPrefix():

opts := badger.DefaultIteratorOptions
opts.PrefetchValues = false // keys only
opts.Reverse = true

it := txn.NewIterator(opts)
defer it.Close()

p := []byte(prefix)

it.Seek(append(p, 0xff))
if it.ValidForPrefix(p) {
	key := string(it.Item().Key())
	split := strings.Split(key, separator)
	lastKey = split[len(split)-1]
}

To me, the fact I have to not only know to append 0xff to the it.Seek() call, but leave that off for the it.ValidForPrefix() call is a bug. Perhaps if your it.Rewind() and it.Seek() handled appending the 0xff internally if the code is iterating in reverse, and then simply used the prefix as is for the it.Valid() function this would work as expected in all cases.