path: root/docs/architecture.org

#+TITLE: Sakura Architecture

* Module Organization

The codebase is organized into focused modules, each with a single
responsibility. This separation enables independent testing, clearer
dependencies, and easier reasoning about the system.

** Core Types

- =Schema=: Defines the structure of relations. A schema maps
  attribute names to domain names (types), capturing both the shape
  and the semantic meaning of each attribute.

- =Relation=: A relation combines a name, schema, optional merkle tree
  of tuple hashes, constraints, cardinality, and metadata for
  provenance tracking. The schema is part of the relation's
  identity—it's hashed into the relation hash and persisted to
  storage.

- =Tuple=: A tuple is a mapping from attribute names to values. Tuples
  can be materialized (concrete values in memory) or non-materialized
  (references to be resolved).

** Computation Modules

- =Hashing=: Content-addressable hash computation for tuples and
  relations. Tuple hashes are computed from sorted attribute
  name-value pairs. Relation hashes incorporate the name, schema, and
  merkle tree root.

- =Storable=: Serialization formats for persistence. Each entity type
  (tuple, relation, database) has a storable representation that
  captures exactly the data needed for reconstruction.

** Management Layer

- =Management.Physical=: A functor-based storage abstraction. Any
  backend implementing the signature (get, put, exists, transactions)
  can be plugged in. The in-memory backend serves development and
  testing.

- =Management.Database=: Database state management. A database holds
  its relations directly—not just their hashes—providing an integrated
  cache. Mutations produce new database states with updated hashes and
  history tracking.

** Manipulation

- =Manipulation=: CRUD operations over the storage layer. This module
  is a functor parameterized by a storage backend. It handles the
  interplay between in-memory relation objects and their persisted
  representations, ensuring consistency between the two.

* Storage Model

Sakura uses an append-only, content-addressed storage model. Every
object in the database is identified by its cryptographic hash
(SHA-256), and data is never overwritten—only new versions are
appended. This design provides natural deduplication, complete history
preservation, and integrity verification at every level.

** Content Addressing

Every entity in Sakura is stored and retrieved by its hash:

- An *attribute* is a value with its hash. The same value appearing in
  multiple tuples is stored once and referenced by hash everywhere
  else.

- A *tuple* is a set of attribute hashes. Its own hash is derived from
  the hashes of its constituent attributes.

- A *relation* maintains a set of tuple hashes. The relation's hash
  represents the current state of that set.

- A *database* holds a map of relation names to their current hashes.
  The database hash is computed from this map, forming the root of a
  Merkle tree.

This hierarchical hashing means that any change modifying an
attribute, inserting a tuple, or altering a relation—propagates
upward, producing a new database hash. The chain of database hashes
over time constitutes the complete history of the database.

** Schema Persistence

A relation's schema is not merely metadata—it is part of the
relation's identity. The schema is included in the relation hash
computation and persisted alongside the tuple hashes and cardinality.

When a relation is stored:

#+begin_example
StoredRelation = {
  name: string,
  schema: (attribute_name, domain_name) list,
  tree_keys: hash list,
  cardinality: cardinality
}
#+end_example

When the relation is loaded from storage, the schema is reconstructed
exactly. This enables:

- *Schema validation*: Tuples can be validated against the relation's
  schema at load time, not just at insertion time.

- *Query planning*: The schema is available for type checking and
  optimization without requiring a separate schema registry.

- *Time-travel consistency*: Loading a historical relation state
  retrieves the schema as it existed at that point in time.

** Integrated Relation Cache

The database maintains actual =Relation.t= objects, not just their
hashes. This eliminates the need for a separate cache and ensures
consistency between the database's view of its relations and the
relations themselves.

When a relation is created or updated:

1. The =Relation.t= object is constructed with its computed hash
2. The database stores the relation directly in its =relations= map
3. The relation hash is inserted into the database's merkle tree
4. Both the relation and database states are persisted to storage

Retrieving a relation is a direct map lookup:

#+begin_src ocaml
let get_relation db name = RelationMap.find_opt name db.relations
#+end_src

When loading a database from storage, all its relations are loaded
and reconstructed in memory as part of the database load. This
ensures that =load_database= returns a fully operational database
with all relations ready for use.

** Append-Only Semantics

Nothing is deleted or modified in place. When a tuple is "updated,"
the new version is appended and the relation's hash set is updated to
reference it. The old tuple remains in storage, reachable through
historical database hashes.

This has practical consequences:

- *Deduplication*: Identical attribute values share storage. If a
  million tuples contain the string "active", that string exists once,
  referenced a million times by its hash.

- *Immutable History*: Any past database state can be reconstructed by
  following the Merkle tree from a historical root hash.

- *Integrity*: Corruption or tampering is detectable—if a stored
  object doesn't match its hash, something is wrong.

** Merkle Tree Structure

The database forms a Merkle tree where:

- Leaf nodes are attribute values
- Interior nodes are tuples (referencing attributes) and relations
  (referencing tuples)
- The root is the database hash

This structure enables efficient verification. To prove a tuple
belongs to a relation at a given database state, one needs only the
tuple, its sibling hashes up to the relation, and the path to the
database root—not the entire database.

* Physical Layer Abstraction

The physical storage layer is designed as a functor: a module that
accepts any storage backend implementing a common signature. This
means the same relational engine can run against different storage
systems without modification.

** Backend Requirements

A storage backend must provide:

- Key-value storage where keys are hashes and values are serialized objects
- Read operations (potentially with consistency options)
- Write operations (append new objects)
- Transaction support with isolation guarantees

The abstraction handles the difference between backends that offer
strong consistency (like etcd) and those with eventual consistency
(like DynamoDB), exposing appropriate primitives for dirty reads
versus transactional reads.

** Pluggable Backends

Potential backends include:

- *etcd*: For distributed coordination and strong consistency
- *Redis*: For in-memory speed with optional persistence
- *DynamoDB*: For cloud-native scalability
- *PostgreSQL*: For leveraging existing infrastructure (using it purely as a key-value store)
- *Local filesystem*: For embedded or development use
- *Any key-value store*: The interface is minimal enough to adapt to most systems

The choice of backend affects performance characteristics and
operational concerns, but not the correctness of the relational
algebra or the integrity guarantees provided by the Merkle structure.

** Transaction Semantics

The physical layer must abstract over:

- *Dirty reads*: Reading potentially uncommitted or stale data, useful
  when eventual consistency is acceptable

- *Transactional reads*: Reading a consistent snapshot, necessary when
  operations depend on multiple related values

- *Atomic writes*: Ensuring that a set of objects is either fully
  written or not written at all

Different backends implement these guarantees differently. The functor
interface normalizes them into a common vocabulary so the relational
engine above can reason about consistency without knowing which
backend is in use.

* Ephemeral Relations and Generators

Not all relations are stored. Some are computed on demand.

** Generator Functions

An ephemeral relation has a generator: a function that produces tuples
lazily. The relation =less_than_natural=, for instance, generates
pairs (n, m) where n < m from the natural numbers. This relation is
infinite—it cannot be stored—but it can be queried.

The generator maintains no external state. Given a position (an
integer index into the enumeration), it deterministically produces the
corresponding tuple. This makes ephemeral relations reproducible:
running the same query twice yields the same results.

** Membership Criteria

Every relation, stored or ephemeral, has a membership criterion: a
predicate that determines whether a tuple belongs to the relation.
For stored relations, this is typically derived from constraints. For
ephemeral relations, it's the intensional definition—the rule that
characterizes membership rather than an enumeration of members.

* Provenance and Updatable Views

When relations are combined through algebraic operations (join,
project, select), the result is an ephemeral relation that tracks
where its attributes came from.

** Provenance

Provenance records the source relation of each attribute. If a join
combines =orders= and =customers= on =customer_id=, the resulting
ephemeral relation knows that =order_date= came from =orders= and
=customer_name= came from =customers=.

This enables updatable views: an update to an attribute in a derived
relation can be traced back to the base relation that owns it and
applied there. The derived relation reflects the change automatically
on next evaluation.

** Lineage

Lineage records the operations that produced a relation. It's a tree
describing the algebraic derivation: this relation is a selection over
a projection of a join of these two base relations.

Lineage enables query optimization (rewriting equivalent expressions)
and provenance queries (understanding how a result was derived).

* References

- Codd, E. F. (1979), "Extending the Database Relational Model to Capture More Meaning"
- Merkle, R. (1987), "A Digital Signature Based on a Conventional Encryption Function"
- Buneman, P., Khanna, S., Tan, W. (2001), "Why and Where: A Characterization of Data Provenance"