Durable data structures: mutate in memory, and it’s on disk. A cross-language file format and durability protocol with crash-safety guarantees, and libraries for building durable data types on top of it.
Founded and currently maintained by Robert Bamler. Source on GitHub; all of these pages also as one PDF.
Kladde is becoming a system for durable data structures: containers (strings, vectors, hash maps, trees, …) and user-defined types that behave like their ordinary in-memory counterparts, but whose every mutation is durably recorded to a file as it happens, in a way that is optimized for disk I/O. Unlike serialization formats like JSON or XML, there is no save step and no serialization pass. Unlike sqlite, there is no SQL and no object-relational layer. You open a kladde file containing some value (typically in some complex nested application-defined data type), you mutate some parts of the value in (almost) the same way you would mutate any other value, and each one of your changes is immediately and efficiently applied to the file.
The idea is known as orthogonal persistence: a program works with persistent data exactly as it works with transient data, and data persists by being reachable from a persistent root. Kladde brings it to existing languages as libraries, as far as each language allows.
Reads never touch the file. A durable data structure keeps a full, natively-typed in-memory representation, so reading a field or iterating a map costs what it costs in the host language, not what it costs in a database. Writes go two places at once: into that in-memory representation, and into an append-only on-disk journal that is durable by the time the mutating call returns. Whenever the journal reaches a threshold size, it is folded into the bulk part of the file, in a way that minimizes I/O and guarantees durability under application crashes and consistency even under power outages.
The bulk part holds the root value’s encoding as one byte sequence, kept on copy-on-write pages as a chain of spans that each show a run of its bytes and name the span that follows. An edit anywhere — a keystroke in a long text, a shape moved to another group — restates the few spans where it cuts the chain and nothing behind them, so the file stays within a constant factor of its content at a constant cost per edit, however large it grows.
The name is German: a Kladde is a merchant’s rough day-book, where transactions are scribbled down in order as they happen and later transcribed into the clean Hauptbuch. The file format has exactly that shape.
Project status
The project is still very young and under active development. At the current stage, the main products are
There are two reference implementations, kladde-rs in Rust and kladde-cpp in C++, and neither is production ready. Their purpose at the moment is to allow rapid experimentation on new policies (non-normative decisions that an implementation may make without breaking interoperability), and to test that the specification is precise enough for two independent implementations to read each other’s files. This is why the reference implementations are currently limited to these two languages and why they are currently fully auto-generated from the specification.
Contributions are welcome. While this includes code contributions in principle, at the current stage, the most valuable contributions are not in the form of code but instead in the form of well-motivated opinions and proposals of what should be added or changed in the specification. If you have a potential use case for a system like kladde and you think that something in its currently stated design would hold you back, then I want to hear your opinion. Please feel free to describe your situation in a new issue.
The ambition
Kladde is meant to be a cross-language system, not a library for one language.
At the centre sits a language-independent specification of the file format and the schema description — everything all implementations must agree on.
Around it sit implementations for individual languages: kladde-rs first and kladde-cpp second, with kladde-python, kladde-java and others intended to follow.
The contract between them is deliberately narrow and deliberately strict:
A file written by any conforming implementation can be opened by any other conforming implementation, with no conversion step and no special treatment, as long as the opening application implements equivalent data structures.
Everything the specification does not pin down is free to vary, and implementations are expected to differ substantially beyond the normative part (e.g., how aggressively they consolidate free space).
Each language should get an API that is idiomatic for that language rather than a transliteration of the Rust one.
For example, the Rust implementation of kladde needs an explicit Mut type to intercept field assignments; by contrast, a Python implementation of kladde should intercept field assignments via property hooks so that doc.title = "..." simply persists.
Language-independent tooling
A file format that several languages can read is also a file format that tools can read, without knowing anything about the application that wrote it. A kladde file’s content is one byte sequence, the encoding of the application’s root value with every value inline in its parent, and the file carries the descriptors of its types. So a generic tool can measure the file’s garbage and compact it without interpreting a byte of application data, report what types the file contains, and decode its whole content from those descriptors to render it as text. See Tooling for how far each of those goes.
The sections
| section | what it holds | who it is for |
|---|---|---|
| Specification | the normative, language-independent description: what a kladde file is, what invariants it must uphold, and what guarantees an implementation must provide | implementers porting kladde to a new language; tool authors |
| Drafts | half-baked ideas in progress, not yet held to the separation the other sections observe | the authors |
| Evaluation | measurements of kladde-rs on realistic workloads, what they say about the design, and what porting it to C++ found | anyone judging the design or choosing its constants |
| Related work | what applications use in kladde’s place today, where the design comes from, and where it parts company | potential users exploring whether kladde is the right choice; contributors researching where ideas came from |
| Implementation | the reference algorithms and data structures — what must be maintained in memory to satisfy the spec, and how — stated in language-agnostic pseudocode | anyone building an implementation in any language |
| kladde-rs | everything specific to the Rust implementation: crate layout, traits, Mut handles, macros, and the Rust-specific half of the algorithms | Rust users, and Rust contributors |
| kladde-cpp | everything specific to the C++ implementation: its layers, which C++ types are durable, its handles and its error handling | C++ users, and C++ contributors |
| Superseded | designs that were worked out and then rejected, kept for the reasoning | anyone tempted to re-propose one of them |
The three-way split between spec, impl, and rust is the organising idea, and the test for which one a statement belongs in is:
- Could two implementations disagree about it and still read each other’s files? If no, it is spec.
- Would a Python or C++ implementation make substantially the same choice? If yes, it is impl.
- Otherwise it is rust.
License
Everything here — text, figures, and data — is available under your choice of CC BY 4.0, MIT, Apache 2.0, or the Boost Software License 1.0; the repository has the details.
Patent pledge. I, Robert Bamler, will not assert any patent I own or control against any implementation of the kladde specification.
