We see this in a modified metamorphic test

iter64 = batch61.NewIter("", "") // <nil> #11982
...
iter64.SetBounds("dsqz", "ewcjnfotphz") // <nil> #12191
iter64.SeekGE("vkqxbbggc") // [false] <nil> #12195
iter64.Prev() // [false] <nil> #12206
iter64.Last() // [true,"eebkemwwnk","jal"] <nil> #12217
batch61.Set("ebflokolqf", "rn") // <nil> #12219
iter64.Next() // [true,"eebkemwwnk","jal"] <nil> #12220

The Next should not have returned the same key-value pair as the preceding call to Last.
iter64.Last ends up with an empty heap when it steps to iterPosPrev in Iterator. The call to iter64.Next is at iterPosPrev and i.iterKey is nil, https://github.com/cockroachdb/pebble/blob/master/iterator.go#L447-L455 so it does a SeekGE on the mergingIter. This exposes the ""ebflokolqf" that was just set in the batch, since it is after the seek position. Since the iterator was at iterPosPrev it then does a call to nextUserKey https://github.com/cockroachdb/pebble/blob/master/iterator.go#L458 which steps from "ebflokolqf" to "eebkemwwnk", which is the result returned above.

A Pebble with a different options setting is lucky in that iter64.Last ends up on a key k such that
"ebflokolqf" < k < "eebkemwwnk"
This happens to be an InternalKeyKindDelete since the last byte is 0 (I'm speculating that different compactions caused this delete to be pushed down to the lowest level in the first case, so it vanished). i.iterKey is at k, so we call i.nextUserKey https://github.com/cockroachdb/pebble/blob/master/iterator.go#L456 instead of mergingIter.SeekGE. This prevents "ebflokolqf" from becoming visible since the iterator is already greater than that key.

This is reproducible by running https://github.com/sumeerbhola/pebble/tree/meta_failure_master (the commit mentions the seed to use).

In general, consider keys k1, k2, k3 that are lexicographically ordered. The Last call, in stepping to iterPosPrev is positioned at k1. The user thinks the iterator is at k3 since that is what was returned by Last. If k2 gets inserted, the code will step twice (thinking k2 is what was returned to the user), and return k3 again. The above example is a special case where this happens when k1 is nil.

I think the fix here is whenever Iterator positions itself at iterPosPrev or iterPosNext it needs to remember the key that it actually returned so it can use that as a constraint when changing direction.

It is possible that this is not sufficient to cover the cases when the direction is not changed. Say the iterator returned k3, and is at iterPosPrev k1. Then k2 is inserted, and then Prev is called. The user expectation is that the Prev should return k2.