[BUG]: 4.3.0 breaks reverse iterators with prefix

[sveeig]

What version of Badger are you using?

4.3.0

What version of Go are you using?

1.23.1

Have you tried reproducing the issue with the latest release?

None

What is the hardware spec (RAM, CPU, OS)?

GOARCH='amd64'
GOHOSTARCH='amd64'
GOHOSTOS='linux'

What steps will reproduce the bug?

	db.Update(func(txn *badger.Txn) error {
		key := make([]byte, 6)
		binary.BigEndian.PutUint16(key, 5)
		binary.BigEndian.PutUint32(key[2:], 1)
		txn.Set(key, []byte("value1"))

		binary.BigEndian.PutUint32(key[2:], 2)
		txn.Set(key, []byte("value2"))
		return nil
	})

	db.View(func(txn *badger.Txn) error {
		searchBuffer := make([]byte, 3)
		binary.BigEndian.PutUint16(searchBuffer, 5)
		searchBuffer[2] = 0xFF

		iteratorOptions := badger.DefaultIteratorOptions
		iteratorOptions.Reverse = true
		iteratorOptions.PrefetchValues = false
		iteratorOptions.Prefix = searchBuffer
		it := txn.NewIterator(iteratorOptions)
		defer it.Close()

		it.Rewind()
		fmt.Println(it.Item().Key()) // causes panic with 4.3.0, prints [0 5 0 0 0 2] with 4.2.0
		return nil
	})

Expected behavior and actual result.

prefixes for reverse iterators need to be appended with an 0xFF byte, to make badger seek to the correct starting point.
The change in #2077 compares all key candidates with the prefix, including the extra byte, and therefore nothing is found. Expected is that items are found like before.

Additional information

I am not sure if the "trick" with appending the 0xFF is officially part of the iterator APIs. But for projects that use it, the last release is a regression. Unless there is a different, officially supported way to seek to the end of a prefix range for reverse traversal, this should be fixed.

@rompetroll Could you tell me more about 0xFF thing? I have not heard it ever, is there any documentation / discuss post for it?

[sveeig]

@rompetroll Could you tell me more about 0xFF thing? I have not heard it ever, is there any documentation / discuss post for it?

It was suggested in dgraph forum discussions in the past. I can't seem to find the exact place we found it previously, but there are some github issues mentioning it as well. e.g. #347

Yeah I found it. I used to be in README, but was removed sometime before. TBH I still don't understand why it happens, but I have made the fix to the code. I am just not doing this check if the iterator is reverse. That should work right?

[sveeig]

I agree, sounds like a reasonable fix 👍