1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
#pragma once
#include "IStorageBackend.h"
#include <array>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <vector>
/**
* @file Merkle.h
* @brief Generic sorted content-addressed B-tree over a templated key type.
*
* Maps `Key → Hash32 payload` with `Key` totally ordered. Each tree node is
* stored as an immutable blob in IStorageBackend via Put/Get. All operations
* load only the nodes on the path from root to the target leaf — O(log_B(n))
* nodes in memory at once, never the whole tree.
*
* Instantiated three times in RNT:
*
* | Level | Key | Payload (Hash32) |
* |---------------|----------------|-------------------------|
* | Branch tree | `std::string` | multigroup snapshot hash|
* | Multigroup | `std::string` | relation merkle root |
* | Relation | `nt::Hash32` | tuple hash (key=payload)|
*
* **Branching factor B = 64**. At 64 children per node and a billion leaves the
* tree is at most 5 levels deep (~20 KB peak working set).
*
* **Immutability**: nodes are never overwritten once written (content-addressed).
* Insert / Remove produce new nodes only along the modified path; old nodes
* remain valid for any snapshot that still holds their root hash.
*
* **Leaf node** stores a sorted-by-key list of `(Key, Hash32 payload)` pairs,
* length ≤ B. For the relation level the key and payload happen to carry the
* same value (the tuple hash); callers pass it twice. Storing both keeps the
* tree shape uniform across the three levels.
*
* **Internal node entry** layout (`leaf_count | min_key | child_hash`):
* - `leaf_count` enables O(log_B(n) + limit) offset navigation for Page()
* without loading sibling subtrees.
* - `min_key` is the smallest key in the subtree — the routing key.
* - `child_hash` is the content-addressed hash of the child node blob.
*
* **Invariants** (asserted in debug builds):
* - No leaf or internal node is ever empty.
* - Leaf entries are sorted ascending by key.
* - Internal entries are sorted ascending by min_key.
*
* **Wire format**: tagged 1-byte node kind ('L' or 'I'), then big-endian u32
* count, then count repetitions of either a leaf entry or a child entry.
* Key encoding is per-specialisation: `Hash32` is 32 raw bytes; `std::string`
* is `u32_be length | bytes`. Wire format is content-addressed — any change
* here invalidates every existing stored snapshot.
*/
namespace nt {
/** @brief 32-byte hash, the universal payload type for all merkle levels. */
using Hash32 = std::array<uint8_t, 32>;
/** @brief Decode a 64-character lowercase-hex SHA256 string into raw bytes.
* Throws std::invalid_argument when the string is not exactly 64 hex chars. */
Hash32 hex_to_bin(const std::string& hex);
/** @brief Encode raw 32 bytes back into a 64-character lowercase-hex string. */
std::string bin_to_hex(const Hash32& bin);
template<typename Key>
class Merkle {
public:
static constexpr size_t B = 64;
/**
* @brief Insert or overwrite a `(key, payload)` mapping.
* @param store KV backend for node serialisation.
* @param root_hex Current root hash (empty string = empty tree).
* @param key Routing/identity key.
* @param payload Hash this key maps to (child root one level down, or
* the key itself at the relation level).
* @return New root hash. Equal to root_hex when an insertion of an
* identical (key, payload) pair would be a no-op.
*/
static std::string Insert(IStorageBackend& store,
const std::string& root_hex,
const Key& key,
const Hash32& payload);
/**
* @brief Remove a key from the tree.
* @return New root hash. Empty string when the tree becomes empty.
* Equal to root_hex when the key is absent.
*/
static std::string Remove(IStorageBackend& store,
const std::string& root_hex,
const Key& key);
/**
* @brief Look up the payload for a key.
* @return The payload when present, std::nullopt when absent.
*/
static std::optional<Hash32> Get(IStorageBackend& store,
const std::string& root_hex,
const Key& key);
/** @brief One (key, payload) pair returned by Page(). */
struct Entry {
Key key;
Hash32 payload;
};
/**
* @brief Page through entries in key-sorted order.
*
* Descends to the leaf at logical position @p offset using cumulative
* leaf_counts stored in internal nodes, then walks forward collecting at
* most @p limit entries. Only the nodes on the active path are loaded;
* sibling subtrees are never touched.
*/
static std::vector<Entry> Page(IStorageBackend& store,
const std::string& root_hex,
size_t offset,
size_t limit);
private:
struct LeafEntry {
Key key;
Hash32 payload;
};
struct LeafNode {
std::vector<LeafEntry> entries;
};
struct ChildEntry {
uint64_t leaf_count;
Key min_key;
Hash32 child_hash;
};
struct InternalNode {
std::vector<ChildEntry> entries;
};
// Wire format
static std::vector<uint8_t> encode_leaf(const LeafNode& n);
static std::vector<uint8_t> encode_internal(const InternalNode& n);
static LeafNode decode_leaf(const std::vector<uint8_t>& bytes);
static InternalNode decode_internal(const std::vector<uint8_t>& bytes);
static bool is_leaf_bytes(const std::vector<uint8_t>& bytes);
// Storage helpers
static std::vector<uint8_t> load_node(IStorageBackend& store,
const std::string& hash_hex);
static std::string store_leaf(IStorageBackend& store, const LeafNode& n);
static std::string store_internal(IStorageBackend& store, const InternalNode& n);
/** @brief Returns the smallest key in the subtree rooted at @p node_hex. */
static Key subtree_min_key(IStorageBackend& store, const std::string& node_hex);
/** @brief Routes a key to the rightmost child whose min_key ≤ target. */
static size_t route(const InternalNode& node, const Key& target);
struct InsertResult {
std::string new_hash;
uint64_t leaf_count = 0;
bool did_split = false;
uint64_t split_leaf_count = 0;
Key split_min_key{};
std::string split_hash;
};
static InsertResult insert_into(IStorageBackend& store,
const std::string& node_hex,
const Key& key,
const Hash32& payload);
struct RemoveResult {
std::string new_hash;
uint64_t leaf_count = 0;
};
static RemoveResult remove_from(IStorageBackend& store,
const std::string& node_hex,
const Key& key);
static void page_from(IStorageBackend& store,
const std::string& node_hex,
size_t& offset,
size_t limit,
std::vector<Entry>& out);
static std::optional<Hash32> get_from(IStorageBackend& store,
const std::string& node_hex,
const Key& key);
};
} // namespace nt
|
