format_version=8 with ReverseBytewiseComparator: a data block holding k + "\x01" before k stores a common prefix longer than k, so Get/MultiGet/Seek of k skip its newest version (stale value, deleted value back, or NotFound) #15439

Expected behavior

With BlockBasedTableOptions::format_version = 8 (every other option at its default, so
optimize_key_common_prefix = kIfFastSeek) and ReverseBytewiseComparator(), point reads and seeks
return the newest version of a key, the same as with format_version = 7.

Actual behavior

When a flushed data block contains a key k and a neighbour k + c, where c is the first byte of
k's internal-key footer (its value type: 0x01 for a Put, 0x00 for a Delete, ...), Get,
MultiGet and Seek(k) do not see k's entry in that block and continue to older files. Every call
returns OK. Output of the program below (three cases, format_version 7 and 8):

== update: Put(user1,100), flush, Put(user1,250), Put(user1\x01), flush, reopen
format_version=7  Get=balance=250  MultiGet=balance=250  Seek(user1)=user1=balance=250   (expected balance=250)
format_version=8  Get=balance=100  MultiGet=balance=100  Seek(user1)=user1=balance=100   (expected balance=250)   <- WRONG
== delete: Put(user1,100), flush, Delete(user1), Put(user1\x00), flush, reopen
format_version=7  Get=<NotFound>  MultiGet=<NotFound>  Seek(user1)=<end>   (expected <NotFound>)
format_version=8  Get=balance=100  MultiGet=balance=100  Seek(user1)=user1=balance=100   (expected <NotFound>)   <- WRONG
== new key: Put(user1,250), Put(user1\x01), flush, reopen
format_version=7  Get=balance=250  MultiGet=balance=250  Seek(user1)=user1=balance=250   (expected balance=250)
format_version=8  Get=<NotFound>  MultiGet=<NotFound>  Seek(user1)=<end>   (expected balance=250)   <- WRONG

So an update is invisible, a deleted value comes back, and a new key cannot be found. A full scan
(SeekToFirst + Next) returns the right data, so flush and compaction copy the block faithfully,
and the wrong prefix is written again: a forced full compaction
(bottommost_level_compaction = kForce) does not repair the reads (Get(user1) then returns NotFound
while the scan shows user1=balance=250). The reopen in the program shows that the
state is persistent. A custom comparator with the same reverse order is not affected (the
optimization is off for it by default, and with kEnabled it reads through full-key
reconstruction), nor is BytewiseComparator().

Likely cause

BlockBuilder::AddWithLastKeyImpl tracks the block's common user-key prefix incrementally
(block_builder.cc#L337-L370).
For a non-restart entry it only shrinks the prefix when shared < first_key_prefix_.size(), where
shared is the number of bytes the entry's persisted key shares with the previous one
(L367-L369).
In a data block the persisted keys are internal keys, so shared can run past the end of the current
key's user key into its 8-byte footer. Under the reverse order the longer key comes first:
"user1\x01" + footer followed by "user1" + footer(seq, kTypeValue = 0x01) share 6 bytes, so the
prefix stays "user1\x01", which "user1" does not start with. (Under the bytewise order the shorter
key always comes first, so this cannot happen there.)

On the read side DataBlockIter::SeekImpl strips the prefix from the target for (reverse-)bytewise
comparators
(block.cc#L188-L212).
StripSeekTargetPrefix sees a target user key ("user1") shorter than the prefix, compares it with
the prefix, and under the reverse comparator concludes that the target sorts after every key in the
block (before_all = false,
block.cc#L1004-L1005),
so the iterator is positioned at the end of the block and the entry is skipped.

The optimization is enabled by default at format_version >= 8 exactly for the built-in bytewise and
reverse-bytewise comparators
(block_based_table_builder.cc#L165-L185).

Possible fix (builder): cap shared at the current entry's user-key length before comparing it with
the prefix. With this change applied to block_builder.cc, all three cases above return the expected
results with format_version = 8:

    } else {
      // `shared` may extend past this key's user key into its footer.
      const size_t uk_size = is_user_key_ ? key_to_persist.size()
                                          : ExtractUserKey(key_to_persist).size();
      const size_t shared_uk = std::min<size_t>(shared, uk_size);
      if (shared_uk < first_key_prefix_.size()) {
        first_key_prefix_.resize(shared_uk);
      }
    }

Files already written with the over-long prefix would still read wrong; a reader-side guard (treat the
block as unstripped / fall back to full-key comparison when a key is shorter than the stored prefix)
or a rewrite of the affected files would be needed for those.

Steps to reproduce the behavior

Tested on main 54732b0 (2026-10-16, version 11.13.0), RelWithDebInfo static library, Linux x86-64.
format_version = 8 / optimize_key_common_prefix were released in 11.10.0.

// g++ -std=c++20 repro.cc -Iinclude build/librocksdb.a -lpthread -ldl -lz -lbz2 -llz4 -lzstd -lsnappy
// usage: repro DBDIR FORMAT_VERSION MODE   (MODE 0: update, 1: delete, 2: new key)
#include <rocksdb/db.h>
#include <rocksdb/table.h>
#include <rocksdb/comparator.h>
#include <iostream>
using namespace rocksdb;
#define CK(x) do { Status _s = (x); if (!_s.ok()) { std::cerr << __LINE__ << " " << _s.ToString() << "\n"; return 2; } } while (0)
int main(int argc, char** argv) {
  std::string p = argv[1]; int fv = atoi(argv[2]), mode = atoi(argv[3]);
  Options o; o.create_if_missing = true; o.comparator = ReverseBytewiseComparator();
  BlockBasedTableOptions t; t.format_version = fv;  // optimize_key_common_prefix left at its default
  o.table_factory.reset(NewBlockBasedTableFactory(t));
  DestroyDB(p, o);
  std::unique_ptr<DB> db; CK(DB::Open(o, p, &db));
  const std::string k = "user1";
  // the neighbour extends the key by the type byte of the key's own newest entry (0x01 Put, 0x00 Delete)
  const std::string neighbour = mode == 1 ? std::string("user1\x00", 6) : std::string("user1\x01", 6);
  std::string expect;
  if (mode != 2) { CK(db->Put(WriteOptions(), k, "balance=100")); CK(db->Flush(FlushOptions())); }
  if (mode == 0) { CK(db->Put(WriteOptions(), k, "balance=250")); expect = "balance=250"; }
  if (mode == 1) { CK(db->Delete(WriteOptions(), k)); expect = "<NotFound>"; }
  if (mode == 2) { CK(db->Put(WriteOptions(), k, "balance=250")); expect = "balance=250"; }
  CK(db->Put(WriteOptions(), neighbour, "another row"));  // the neighbouring key, same memtable
  CK(db->Flush(FlushOptions()));
  CK(db->Close()); db.reset(); CK(DB::Open(o, p, &db));
  std::string v; Status s = db->Get(ReadOptions(), k, &v); std::string got = s.ok() ? v : s.IsNotFound() ? "<NotFound>" : s.ToString();
  std::unique_ptr<Iterator> it(db->NewIterator(ReadOptions())); it->Seek(k);
  std::string seek = it->Valid() ? it->key().ToString() + "=" + it->value().ToString() : "<end>";
  std::string seek_exp = expect == "<NotFound>" ? "<end>" : k + "=" + expect;
  std::vector<Slice> ks{Slice(k)}; std::vector<std::string> vs; auto st = db->MultiGet(ReadOptions(), ks, &vs);
  std::string mg = st[0].ok() ? vs[0] : st[0].IsNotFound() ? "<NotFound>" : st[0].ToString();
  it.reset();
  bool ok = got == expect && mg == expect && seek == seek_exp;
  std::cout << "format_version=" << fv << "  Get=" << got << "  MultiGet=" << mg << "  Seek(user1)=" << seek << "   (expected " << expect << ")" << (ok ? "" : "   <- WRONG") << "\n";
  return ok ? 0 : 1;
}

for mode in 0 1 2; do for fv in 7 8; do ./repro /tmp/fv8db $fv $mode; done; done

Impact

Any column family that uses ReverseBytewiseComparator() and opts into format_version = 8 gets these
blocks without setting anything else. Binary keys (composite keys, length-prefixed or zero-terminated
encodings) produce such neighbours naturally: the neighbour only has to extend the key by its value
type byte (0x01 Put, 0x00 Delete, 0x02 Merge, 0x07 SingleDelete, ...); longer extensions that
also match the low bytes of the sequence number widen the window. A read-modify-write on top of such a
read stores a value computed from the stale version.