Otara

A distributed, replicated database based on Mergeable Replicated Data Types (MRDTs)

Otara is a cross-platform database for building offline-first applications with automatic synchronization. Unlike CRDT-based solutions, Otara uses MRDTs with characteristic relations for composable three-way merging.

Key Features

• Composable 3-way merge — Merge functions compose naturally via Galois connections
• k²-tree storage — Succinct, compressed storage with efficient set operations
• Linearizable backend — Simplifies non-monotonic operations, bounded metadata growth
• GraphQL SDL schemas — Define your data model with familiar GraphQL syntax
• Cross-platform — iOS (Swift), Android (Kotlin), Web (TypeScript/WASM)

How It Works

Operations → WAL → Apply to k²-trees → Sync with Backend
                                              ↓
Query → γ (concretization) ← Three-way Merge (◇)

1. Write path: Operations logged in WAL, applied to characteristic relations stored in k²-trees
2. Sync: Compute delta from LCA (last synced server TID), send to backend
3. Merge: Three-way merge using k²-tree set operations (union, intersection, difference)
4. Read path: γ functions reconstruct concrete views from relations

Why k²-trees?

k²-trees are succinct data structures that excel at:

• Set operations on compressed form — Union/intersection/difference without decompression
• Sparse data compression — Characteristic relations are typically sparse
• Range queries — Z-order (Morton) curve enables efficient 2D queries
• Simple persistence — Just bit arrays, mmap and go

Why a Linearizable Backend?

Non-monotonic operations (decrements, dequeues) require causality tracking. In pure P2P systems, this metadata grows unboundedly. Otara assumes a linearizable backend that:

• Provides total ordering of updates
• Makes causality implicit in log order
• Enables bounded metadata growth
• Scales to datacenter-wide with modern approaches (CORFU, Scalog)

Documentation

• Design Document — Comprehensive architecture and design decisions

Based On

• Mergeable Replicated Data Types (Kaki et al., OOPSLA 2019)
• Efficient Set Operations over k²-trees (Brisaboa et al., DCC 2015)
• tdb-succinct — Succinct data structures from TerminusDB

Status

🚧 Early Development — Design phase

License

TBD