# Meshanina --- specialized, WORM, content-addressed database

Meshanina is a rather strange key-value database, with three assumptions:

- Once written, a key-value mapping will never be deleted
- Some function `H` maps every value to every key: `H(v) = k`. That is, the same key will never be rebound to a different value.

Meshanina is designed for use as a _content-addressed_ datastore, where keys are typically hashes of values and deletion is ill-defined. It is a purely log-structured, content-addressed database file where we interleave data blocks with 64-ary HAMT nodes. When we insert keys, we just insert gobs of data, then when we flush we make sure metadata is pushed out too.

In-memory, we keep track of an Arc-linked bunch of new nodes before they get flushed out. Everything is managed in a "purely functional" way.

## On-disk format

- 4 KiB: reserved region
  - starting with 10 bytes: `meshanina2`
  - then 16 bytes more of a random, unique, database-specific 128-bit divider
- indefinite number of **records**:
  - (possibly padding to the some nice boundary)
  - 16 bytes: magic divider stored in the reserved region
  - 8 bytes: SipHash 1-3 checksum of the record contents
  - 4 bytes: what kind of record, little endian
    - 0x00000000: data
    - 0x00000001: HAMT _interior_ node
    - 0x00000002: HAMT _root_ node
  - 4 bytes: length of the record
  - n bytes: the content of the record
    - for HAMT nodes, this is:
      - 8 bytes: 64-bit little-endian bitmap
      - n\*8 bytes: 64-bit pointers to absolute offsets
    - for data nodes, this is:
      - 32 bytes: key
      - n bytes: value

## Recovery

On DB open, there is a recovery mechanism. We search backwards, from the end of the file, for instances of the magic divider, then try to decode a record at each instance. When we find the first _validly encoded HAMT root_, we stop. We then scan forwards, reinserting every valid data block after this root into the database.

Assuming that there are no "gaps" in correctly written blocks --- that is, if there's a record that's correctly written, every record before it must be so too --- this defends against arbitrary crashes and power interruptions. Essentially all Unix filesystems do guarantee that interrupted file appends cannot disturb existing data in the file.

## Lookup and insertion

Starting from the latest HAMT root node, do the usual HAMT lookup/insertion, using the 256-bit key value 6 bits at a time.