# bion-kv 🗃️

Magasin clé-valeur durable, **std-only, zéro dépendance**, style
[Bitcask](https://riak.com/assets/bitcask-intro.pdf) : 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

```rust
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](https://github.com/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.