Storage Performance & Big-O

This page is for app builders making data-modeling decisions. It explains what each collection actually costs — in CPU and, more importantly, in disk reads — so you can choose a shape that stays fast as your state grows.

Throughout, n is the number of entries in the collection you are operating on, k is the number of results a query returns, and K is the number of siblings under one parent (for a top-level collection, K is that collection’s own entry count).

How storage actually works (and why it matters for perf)

Calimero state is not an in-memory HashMap. It is a content-addressed tree of storage entities, and three properties of that tree drive every number below:

1. Each logical entry is its own storage entity. A map with n keys is n separate records on disk, each addressed by a content id. The parent collection stores only the set of child ids, not the values.

2. There is no value index. Nothing maps a value (or a key’s position) to where it lives, beyond the parent’s child-id set. So to read every entry, you must do n point reads — one round-trip to the backend per entry. Iteration is inherently O(n) reads; there is no cheaper path.

3. Every write re-hashes its siblings. When you insert or remove an entry, the parent re-sorts and SHA-256s all K of its children to recompute its Merkle hash (index.rs, calculate_full_hash_for_children), then walks the ancestor chain to the root doing the same at each level. A write is therefore O(K log K) in the size of its parent — not O(1).

The upside of property 3 is that reading the current root / scope hash is O(1): it is kept current incrementally by every write, so the cost is paid at write time, never at read time.

Gotcha: writes are not O(1)

Inserting or removing one entry costs O(K log K), where K is the number of siblings under the same parent, because the parent rehashes its entire child set on every write. A collection with one enormous parent makes every single write to it slow. Keep K bounded — partition large collections (e.g. shard by key prefix or by time bucket) so no single parent holds the whole dataset.

Shared primitives

Every collection is built from the same handful of operations. Their costs compose into the per-collection table further down.

Primitive	Cost	Why
Derive an entry id	O(1)	one SHA-256 over parent + key
Point read (get / contains)	O(1) in n	~3 backend reads + a borsh decode; independent of collection size
Load the child-id set	O(n) cold, O(1) warm	read the parent’s child-id list once, then cache it in memory for the rest of the call
len	O(1)	an open collection reads its child trie’s count; a guarded one (Authored*, WriteOnce, Moderated, UserStorage, anything nested in an owned entry or a cell) reads a node-local count of the entries it admits, which the node’s first count loads once in O(n)
Iterate all entries	O(n) reads	one point read per entry; there is no value index to shortcut it
insert / remove (any write)	O(K log K) + ancestor walk	parent re-sorts and SHA-256s all K siblings, then re-hashes each ancestor up to the root
Read root / scope hash	O(1)	kept current incrementally by every write

Note

“Warm” vs “cold” refers to whether the child-id set has already been loaded into the in-memory cache during the current execution. The first access that needs it pays one O(n)-sized read; subsequent accesses in the same call are free. Neither len nor contains needs it. A guarded collection cannot count from its child trie, which also holds entries a patched peer linked that the collection does not admit, so it keeps a count of the ones it does admit beside the ordered index: node-local, never synced or hashed, carried forward by every link and unlink, local or from a peer, and trusted only at the trie root it was taken at. A node counts a guarded collection by loading its children once, the first time it counts it, and in constant reads after that.

Per-collection complexity

Collection	get / contains	insert / remove	len	Iterate all	Ordered access (range / prefix / page)
UnorderedMap / UnorderedSet	O(1)	O(K log K)	O(1) warm	O(n) reads	none — hashed ids have no key order
SortedMap / SortedSet	O(1)	O(K log K) + index write	O(1) warm	see gotcha below	range/prefix O(log n + k); first/last O(log n)
IndexedMap	O(1)	O(K log K) + one index write per changed index row	O(1) warm	O(n) reads	by field value: query(..).eq/range O(log n + k); desc().limit(k) O(k log n); count reads index rows only
Vector	get(i) is O(i) reads	push O(K log K); update(i) O(1)	O(1) warm	O(n) reads	positional only — see gotcha
ReplicatedGrowableArray (RGA)	get_text O(n log n)	single-char insert O(n log n); insert_str is bulk	O(n log n)	O(n log n)	n/a
FugueText	get_text / char_at O(b) in blocks	writes each touched block once; insert_str and apply_delta are bulk	O(b)	O(b)	n/a
Counter / PNCounter	value() O(actors) reads	increment O(K log K)	n/a	n/a	n/a
LwwRegister	O(1)	O(K log K)	n/a	n/a	n/a
Authored* (map / vector)	same as the underlying collection, plus a per-entry owner-stamp read		O(1), from the node-local count (see the note above)

A few rows deserve their own warnings.

Vector

Vector keeps insertion order, but it is backed by the same child-id set as every other collection — it is not an array you can index into in constant time.

• push mints a random element id (so it skips the per-key id hash), but it is still a write, so it pays the O(K log K) parent rehash like everything else.
• update(i) is O(1): it looks the id up by position in the cached child-id set, then does one point write.
• get(i) is O(i) reads: it iterates entries from the start and loads each one until it reaches index i, discarding the rest.

Gotcha: Vector::get(i) is O(index), not O(1)

Reading vec.get(i) loads and decodes i + 1 entries to return one. A loop of for i in 0..len { vec.get(i) } is therefore O(n^2) reads. To read a vector in order, iterate it (vec.iter(), a single O(n) pass) instead of indexing by position.

SortedMap / SortedSet

SortedMap adds a node-local ordered index so range and prefix queries can seek instead of scan. But not every read uses it:

• range, prefix, first, last, and page go through the index: O(log n + k) (seeks, then loads only the k matches).
• entries(), keys(), and values() ignore the index and sort all entries in memory: O(n log n), after an O(n)-read full materialization.
• page(offset, limit) walks and discards offset rows before returning limit — so deep pagination (page(100000, 20)) is O(offset + limit), not O(limit). Prefer a range keyed on the last item you saw (“seek pagination”) over large offsets.

Use SortedMap only when you genuinely need key order. It costs an extra index write on every insert/remove plus extra disk per key; if you only ever point-access by key, use UnorderedMap.

IndexedMap

IndexedMap is an UnorderedMap whose value type declares secondary indexes (#[derive(app::Indexed)]), so a read by field value — “the open issues”, “the notes of deal 7”, “the newest twenty posts” — seeks instead of scanning the whole map.

• query(index).eq(v) / .range(a..b) seek to the matching rows: O(log n + k). On a compound index, eq on the leading fields leaves the rest to order the result, so “status = open, newest first” is one seek.
• .desc().limit(k) walks back with one bounded reverse seek per row: O(k log n), however large the index.
• .count() reads index rows only and loads no entry.
• Each insert / update / remove writes only the index rows that changed. Measured by the cost gate: per insert, identical state writes to an UnorderedMap, plus 2 state reads, 1 index read and 3 index writes.
• entries() ignores the indexes: O(n) like any map.

Its stored bytes are exactly an UnorderedMap’s, so switching an existing field to IndexedMap needs no migration. Change an indexed field with update(key, |v| ...), not by reinserting through a raw guard, or the next query pays a rebuild.

ReplicatedGrowableArray (RGA)

Each RGA operation re-materializes the whole document — a depth-first walk plus a sort over all visible characters (O(n log n)) — to resolve the current text order. That cost is per call, not per character.

Gotcha: single-char insert re-materializes the whole document

rga.insert(pos, ch) rebuilds the entire ordered document (O(n log n)) on every call, so typing m characters one at a time is O(m * n log n). To add a string, call insert_str once: it materializes the order a single time and then appends each character. Same applies to reading — call get_text() once and slice the result rather than calling it in a loop.

Collaborative text

FugueText stores text as blocks of up to 256 consecutive characters, and a read rebuilds the order from those blocks, so it costs O(b) in blocks rather than in characters. Text typed or pasted in one place fills a block before opening the next; text inserted in many scattered places makes more, smaller blocks, up to one per character in the worst case. A write stores each block it touches once, so one apply_delta for a whole editor change costs one write per touched block rather than one per character. RichText adds one row per formatting mark and nothing for a mark already in effect, and RichDocument writes a constant number of rows to insert or move a block however long the document is. The measured rows for every text workload, RGA included, are pinned in tools/storage-cost/storage-costs.json; see benchmarking to rerun them.

Counter

A counter stores one slot per executor that has touched it. value() reads every slot and sums them, so it is O(actors) reads — cheap while a handful of nodes write to it, linear in the number of distinct writers over the counter’s lifetime.

Merge cost

Sync applies remote changes through the same write path, so the costs above also govern reconciliation:

• Merging one entry costs the same as inserting it: O(K log K).
• A full root merge touches up to N entries (where N is total state size), each paying its parent’s sibling rehash — roughly O(N * K). When everything hangs off one parent (K ≈ N), that degrades toward O(N^2). This is the same “keep K bounded” lesson as for local writes, now applied to whole-state convergence.

The ordered index and sync

SortedMap’s ordered index is node-local, derived, and not synced. A remote sync writes entries directly, bypassing insert, so it never updates the index. The next ordered read notices the mismatch (a full_hash marker no longer matches the entry set) and rebuilds the index once — an O(n)-reads pass — then resumes seeking. Under PrivateStorage (which has no ordered backing store), ordered reads fall back to an in-memory sort, O(n log n) per read, with no seek advantage. See CRDT internals for the merge model behind this.

IndexedMap’s secondary indexes follow the same rules and live in the same node-local column: never synced, never in the root hash. Their marker also fingerprints the index declarations, so adding or renaming an index rebuilds on the next query too. The first query after a remote change is therefore O(n) reads (it re-derives every entry’s keys, writing only the rows that changed); every query after it seeks again. A rebuild whose writes do not land (an execution with node-local writes suppressed, such as the migration check) answers that query by scanning rather than from the unbuilt index; SortedMap and SortedSet do the same.

Blobs

Large binary payloads use the blob store, which is separate from the collection tree:

• Content is split into fixed 1 MiB chunks.
• A multi-chunk blob’s BlobId is SHA-256 over its child chunk ids, not over the raw content.
• Reading a blob is O(chunks) — it streams chunk by chunk.

Blobs are the right home for anything large or opaque (files, media, serialized snapshots). Storing big values as collection entries instead forces that data through the per-entry read and sibling-rehash machinery above.

Worked example: a chat that doesn’t shard

Make the write-cost cliff concrete. A chat app stores every message as a direct child of one map:

// All messages under a single parent — K grows without bound.
messages: UnorderedMap<u64, LwwRegister<String>>,

By message 100,000, K ≈ 100_000. Each new message is an insert, and every insert re-sorts and SHA-256s all of the parent’s children to recompute its Merkle hash — O(K log K). So the 100,000th message hashes ~100k siblings, the room gets slower the more it is used, and a full sync that replays the room degrades toward O(N^2) because K ≈ N. This is a write/merge cliff, not a read problem — point reads stay O(1).

The fix is to bound K: shard the messages so no single parent holds the whole history. Bucketing by UTC day keeps each parent at one day’s traffic, and the inner SortedMap still gives ordered reads within a day:

// "room:2026-06-25" -> that day's messages, time-ordered. Each parent's K is
// one day of traffic (thousands), not the lifetime total (hundreds of thousands).
messages: UnorderedMap<String, SortedMap<[u8; 8], LwwRegister<String>>>,

	One flat map	Sharded by day
Parent size K at 100k messages	~100,000	~one day’s count
Cost of the next insert	O(100k · log 100k)	O(day · log day)
Full-room merge	toward O(N^2)	O(N · day)

The shard key is whatever bounds growth for your access pattern — a time bucket, a room id, a key prefix, or an owner. The only requirement is that no single parent grows unbounded.

Practical guidance

• Use the right collection for the access pattern. Point lookups → UnorderedMap. Ordered scans, ranges, or pagination → SortedMap. Append-log with in-order reads → Vector (iterate, don’t index). Collaborative text → FugueText with one apply_delta per editor change. A running total across writers → Counter.
• Reach for SortedMap only when you need order. It is the BTreeMap to UnorderedMap’s HashMap: more write and disk cost, paid back only if you actually range/prefix/paginate.
• Build RGA text with insert_str, never a per-character loop. One bulk call materializes the document order once instead of once per character.
• Don’t iterate to compute what you can track incrementally. Iterating to count, sum, or find a max is O(n) reads every time. If you need a running aggregate, maintain it as you write (e.g. a Counter or a dedicated field) rather than recomputing it on read.
• Iterate vectors; never index them in a loop. vec.iter() is one O(n) pass; for i in 0..len { vec.get(i) } is O(n^2) reads.
• Watch write cost on large parents. Because every write rehashes its siblings, a single collection holding tens of thousands of entries makes every write to it slow and every full merge expensive. Partition large datasets (shard by key prefix, time bucket, or owner) so no single parent grows unbounded.

For the merge semantics that sit underneath these costs, see Collections and CRDT internals.

Next steps

CollectionsThe merge semantics of each collection these costs come from.

CRDT internalsThe storage tree and merge model underneath the Big-O.

Gotchas & sharp edgesSharp edges around writes, iteration, and large parents.