U64 allowing endianness template parameter is very misleading

[eliphatfs]

Heed Version: 0.22

The heed::types::U64 structure in heed allows to define an endianness. However, since MDB_INTEGER_KEY only works on u32, for U64 the default comparator uses a lexical byte sort order, which leads to surprises for range and ordered listing queries when the data exceeds 256. This surprising behavior is not documented in the U64 struct either. In heed::Database documentation there is an example using BigEndian, but does not explicitly tell us that BigEndian is the only option that actually works as expected.

Proposed mitigation: Disallow nativeendian or littleendian on integer types completely, or at least make clear in documentation about this behavior.

Example:

// Minimal reproduction: LMDB orders keys by memcmp (byte order), NOT numeric
// order. `U64<NativeEndian>` = little-endian on x86, so numeric ordering breaks
// at indices that cross a 256 boundary (where a higher byte first becomes
// non-zero). This is the root cause of the `LogIndex(290)` reapply panic.
//
// Run: cargo run --example probe_bytesort
use byteorder::{ByteOrder, NativeEndian};
use heed::types::{Bytes, SerdeJson, U64};
use heed::{Database, EnvOpenOptions};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let dir = "/tmp/km-bytesort-test";
    let _ = std::fs::remove_dir_all(dir);
    std::fs::create_dir_all(dir)?;
    let env = unsafe { EnvOpenOptions::new().map_size(1 << 24).max_dbs(4).open(dir)? };
    let mut w = env.write_txn()?;
    let db: Database<U64<NativeEndian>, SerdeJson<serde_json::Value>> =
        env.create_database(&mut w, Some("t"))?;
    // Insert the SAME range present in production raft_logs: 32..=290, in
    // strictly increasing numeric order. Nothing here touches the incident.
    for i in 32u64..=290 {
        db.put(&mut w, &i, &serde_json::json!({"i": i}))?;
    }
    w.commit()?;

    let t = env.read_txn()?;
    let dbb: Database<Bytes, Bytes> = env.open_database(&t, Some("t"))?.unwrap();

    // 1) Does sequential iteration come back in numeric order?
    let mut order = Vec::new();
    for res in dbb.iter(&t)? {
        let (k, _) = res?;
        order.push(NativeEndian::read_u64(k));
    }
    let sorted = order.windows(2).all(|w| w[0] < w[1]);
    println!("inserted 32..=290; iteration-order numeric-sorted? {sorted}");
    println!("first: {:?} last: {:?}", order.first(), order.last());
    for (p, w) in order.windows(2).enumerate() {
        if w[0] > w[1] {
            println!("  order break pos{p}: {} then {}", w[0], w[1]);
        }
    }

    // 2) get_log_state() in log_store.rs uses rev_range(..).next() to find the
    //    last log id. Under memcmp ordering that returns the byte-largest key,
    //    which is NOT the numerically-largest index.
    let last = dbb
        .rev_range(&t, &(..))?
        .next()
        .transpose()?
        .map(|(k, _)| NativeEndian::read_u64(k));
    println!("rev_range(..).next() -> {last:?}  (expect 290)");

    // 3) And this is the killer: reapply_committed() reads a RANGE [start..end)
    //    with a forward cursor. Once the cursor seeks into the mis-ordered
    //    region, it yields misplaced indices and the defensive check fails.
    let mut r: Vec<u64> = Vec::new();
    let start = 289u64.to_ne_bytes();
    let end = 291u64.to_ne_bytes();
    let rng = (
        std::ops::Bound::Included(start.as_slice()),
        std::ops::Bound::Excluded(end.as_slice()),
    );
    for res in dbb.range(&t, &rng)? {
        let (k, _) = res?;
        r.push(NativeEndian::read_u64(k));
    }
    println!("range bytes[289..291) -> {r:?}  (expects first=289 last=290)");

    Ok(())
}

inserted 32..=290; iteration-order numeric-sorted? false
first: Some(256) last: Some(255)
  order break pos31: 287 then 32
  order break pos33: 288 then 33
  order break pos35: 289 then 34
  order break pos37: 290 then 35
rev_range(..).next() -> Some(255)  (expect 290)
range bytes[289..291) -> [289, 34, 290, 35]  (expects first=289 last=290)