bions-rust/bion-kv/README.md

bion-kv 🗃️

Magasin clé-valeur durable, std-only, zéro dépendance, style Bitcask : un log append-only sur disque + un index en mémoire + une compaction atomique. La brique build-your-own-database du xerboxion — construite une fois, plus jamais rebâtie, seulement optimisée (principe RS-7).

Quoi

• Kv::open(dir) — ouvre/crée le magasin, reconstruit l'index en scannant le log
• put(k, v) — un append séquentiel, O(1)
• get(k) -> Option<Vec<u8>> — un lookup mémoire + au plus un seek/read
• delete(k) — appose un tombstone (on n'efface jamais le passé)
• compact() — réécrit uniquement les données vivantes, bascule atomique par rename
• sync() — fsync explicite quand on veut la garantie coupure-de-courant
• CRC32 (IEEE) implémenté maison (bion_kv::crc32, table const calculée à la compilation)

Pourquoi Bitcask

1. Rapide en écriture : tout est un append séquentiel — le motif d'E/S le plus rapide sur disque comme sur SSD. Pas d'arbre à rééquilibrer, pas de page à réécrire.
2. Robuste : le passé est immuable ; un crash ne peut abîmer que la queue du log. À la réouverture, chaque record est vérifié par CRC32 et la queue malade est tronquée — les données saines survivent toujours.
3. Simple : le format tient en une ligne (crc32 | klen | vlen | clé | valeur, tombstone = vlen == 0xFFFFFFFF), la récupération = relire le log. Tout le moteur tient dans un fichier source lisible en une soirée : c'est aussi un cours.

Le compromis assumé : la RAM porte l'index (proportionnel au nombre de clés, pas au volume des valeurs), et le log grossit avec les versions mortes — d'où compact().

Lien avec le boxion store

Le boxion store (jOSBoxion) expose déjà un KV par-utilisateur aux ploxions. bion-kv en est le moteur côté core Rust : même contrat (put/get/delete durable et réouvrable), mais embarquable partout — dans xerboxion-rt, dans l'OS bare-metal, dans un bion WASM. On ne réinvente pas le KV à chaque étage : on branche ce bloc.

Exemple

let mut kv = bion_kv::Kv::open("/tmp/mon-magasin")?;
kv.put(b"xer", b"renderer")?;
assert_eq!(kv.get(b"xer")?.as_deref(), Some(&b"renderer"[..]));
kv.delete(b"xer")?;                 // tombstone dans le log
assert_eq!(kv.get(b"xer")?, None);
kv.compact()?;                       // le log ne garde que le vivant
# Ok::<(), std::io::Error>(())

Build-your-own-x

Même famille que ces guides du dépôt codecrafters-io/build-your-own-x (section Build your own Database) :

• Build Your Own Fast, Persistent KV Store in Rust — exactement ce crate
• l'article fondateur : Bitcask — A Log-Structured Hash Table for Fast Key/Value Data (Riak)
• cousins de design : les WAL de SQLite/Postgres, les SSTables de LevelDB/RocksDB (Bitcask = le cas dégénéré à un seul niveau)

Comment l'optimiser (l'invitation au fork)

L'API est stable pour toujours ; tout ce qui suit se fait dessous, sans casser un seul appelant :

• Fichiers multiples + hint files (le vrai Bitcask) : fermer le segment actif à N Mo, compacter segment par segment, et écrire un hint file (clé → offset) pour rouvrir sans relire les valeurs.
• Compaction incrémentale : aujourd'hui compact() copie tout le vivant d'un coup ; en segments, on ne compacte que les segments les plus « morts ».
• Batching/put_many : grouper plusieurs records dans un seul write_all
  • un seul fsync.
• CRC matériel : remplacer la table par l'instruction crc32c (SSE4.2) ou du SIMD — le format ne change pas si on garde le polynôme IEEE.
• Index plus dense : HashMap<Vec<u8>, _> → arène de clés + table à adressage ouvert, ou un ART pour les scans par préfixe.
• get sans &mut : pread/read_at (FileExt) pour des lectures concurrentes sans déplacer le curseur.

Tests

cargo test -p bion-kv — 17 tests unitaires + 2 doc-tests : put/get/delete, écrasements, clés/valeurs binaires et vides, persistance après réouverture, tombstones rejoués, compaction (taille réduite, données intactes, réouverture), queue corrompue (bruit, record tronqué, bit-flip détecté par CRC), fichier étranger refusé, brouillon de compaction orphelin ignoré, 500 clés.