comet.sh
An Elixir implementation of AT Protocol-flavoured Merkle Search Trees (MST)
ovyerus.com
1# elixir-mst
2
3An Elixir implementation of [AT Protocol-flavoured Merkle Search Trees (MST)][spec].
4
5## Overview
6
7A Merkle Search Tree is a content-addressed, ordered key/value structure.
8Every unique set of key/value pairs produces a unique root CID, making it
9suitable for Merkle proofs, efficient diffs, and repository synchronisation.
10This library implements the AT Protocol flavour: nodes are encoded as
11DRISL, keys are arbitrary byte strings, values are `DASL.CID` links, and
12tree depth is derived from the SHA-256 hash of each key.
13
14[spec]: https://atproto.com/specs/repository#mst-structure
15
16## Installation
17
18Get elixir-mst from [hex.pm](https://hex.pm) by adding it to your `mix.exs`:
19
20```elixir
21# mix.exs
22def deps do
23 [
24 {:mst, "~> 0.1"}
25 ]
26end
27```
28
29Documentation can be found on HexDocs at https://hexdocs.pm/mst.
30
31## Quick start
32
33```elixir
34# Build a tree
35tree = MST.new()
36
37val = DASL.CID.compute("my record data")
38{:ok, tree} = MST.put(tree, "app.bsky.feed.post/3jqfcqzm3ft2j", val)
39{:ok, ^val} = MST.get(tree, "app.bsky.feed.post/3jqfcqzm3ft2j")
40
41# Mutate (persistent — the original tree is unchanged)
42{:ok, tree2} = MST.put(tree, "app.bsky.feed.post/3jqfcqzm3fz2j", val)
43{:ok, tree2} = MST.delete(tree2, "app.bsky.feed.post/3jqfcqzm3ft2j")
44
45# Enumerate in sorted order
46{:ok, pairs} = MST.to_list(tree2)
47# => [{"app.bsky.feed.post/3jqfcqzm3fz2j", val}]
48
49# Or stream lazily
50tree2 |> MST.stream() |> Enum.each(fn {key, cid} -> ... end)
51```
52
53## CAR import / export
54
55```elixir
56# Export to a CARv1 binary
57{:ok, car_bytes} = MST.to_car(tree)
58File.write!("repo.car", car_bytes)
59
60# Import from a CARv1 binary
61{:ok, tree} = MST.from_car(File.read!("repo.car"))
62```
63
64## Diffing two trees
65
66```elixir
67{:ok, diff} = MST.diff(tree_a, tree_b)
68
69diff.created_nodes # MapSet of node CIDs added in tree_b
70diff.deleted_nodes # MapSet of node CIDs removed from tree_a
71
72for %MST.Diff.Op{key: key, old_value: old, new_value: new} <- diff.record_ops do
73 case {old, new} do
74 {nil, cid} -> IO.puts("create #{key} → #{cid}")
75 {cid, nil} -> IO.puts("delete #{key} (was #{cid})")
76 {old, new} -> IO.puts("update #{key}: #{old} → #{new}")
77 end
78end
79```
80
81---
82
83This project is licensed under the [MIT License](./LICENSE)