diff options
Diffstat (limited to 'include/Merkle.h')
| -rw-r--r-- | include/Merkle.h | 162 |
1 files changed, 99 insertions, 63 deletions
diff --git a/include/Merkle.h b/include/Merkle.h index 8380093..ba8018a 100644 --- a/include/Merkle.h +++ b/include/Merkle.h @@ -5,105 +5,143 @@ #include <array> #include <cstddef> #include <cstdint> +#include <optional> #include <string> #include <vector> /** * @file Merkle.h - * @brief Sorted content-addressed B-tree over SHA-256 tuple hash hex strings. + * @brief Generic sorted content-addressed B-tree over a templated key type. * - * Each node is stored as an immutable blob in IStorageBackend via Put/Get. - * All three 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. + * 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. * - * **Branching factor B = 64**: leaves hold up to 64 hashes; internal nodes hold - * up to 64 child entries. At B=64 and 1 billion tuples the tree is at most - * 5 levels deep (~20 KB peak working set). + * 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 and Remove produce new nodes only along the modified path; old nodes + * Insert / Remove produce new nodes only along the modified path; old nodes * remain valid for any snapshot that still holds their root hash. * - * **Internal node entry layout** (leaf_count | min_hash | child_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_hash` (smallest tuple hash in the subtree) is the routing key. + * - `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. - * - Internal node entries are sorted ascending by min_hash. - * - All public entry points that accept a hex hash throw `std::invalid_argument` - * when the string is not exactly 64 lowercase hex characters. + * - Leaf entries are sorted ascending by key. + * - Internal entries are sorted ascending by min_key. * - * @todo Add bounds checking in decode_leaf / decode_internal: validate that the - * reported entry count does not exceed the actual blob size before reading. - * Currently a truncated or corrupt blob causes out-of-bounds reads. + * **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 a tuple hash into the tree. - * @param store KV backend for node serialization. + * @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 hash_hex 64-char hex SHA-256 of the tuple to insert. - * @return New root hash. Equal to root_hex when the hash was already present. + * @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 std::string& hash_hex); + const std::string& root_hex, + const Key& key, + const Hash32& payload); /** - * @brief Remove a tuple hash from the tree. - * @param store KV backend. - * @param root_hex Current root hash. - * @param hash_hex 64-char hex SHA-256 of the tuple to remove. - * @return New root hash. Empty string when the tree becomes empty. + * @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 std::string& hash_hex); + 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 tuple hashes in sorted order. + * @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 hashes. Only the nodes on the active path are loaded; + * most @p limit entries. Only the nodes on the active path are loaded; * sibling subtrees are never touched. - * - * @param store KV backend. - * @param root_hex Current root hash. - * @param offset Zero-based logical tuple offset. - * @param limit Maximum number of hashes to return. - * @return Hex hash strings in sorted order. Empty when past the end. */ - static std::vector<std::string> Page(IStorageBackend& store, - const std::string& root_hex, - size_t offset, - size_t limit); + static std::vector<Entry> Page(IStorageBackend& store, + const std::string& root_hex, + size_t offset, + size_t limit); private: - using Hash32 = std::array<uint8_t, 32>; + struct LeafEntry { + Key key; + Hash32 payload; + }; struct LeafNode { - std::vector<Hash32> hashes; // sorted ascending, len ≤ B + std::vector<LeafEntry> entries; }; - // Wire: 8-byte leaf_count | 32-byte min_hash | 32-byte child_hash struct ChildEntry { - uint64_t leaf_count; // number of tuple hashes in this subtree - Hash32 min_hash; // smallest tuple hash in the subtree - Hash32 child_hash; // content-addressed hash of the child node + uint64_t leaf_count; + Key min_key; + Hash32 child_hash; }; struct InternalNode { - std::vector<ChildEntry> entries; // sorted by min_hash, len ≤ B + std::vector<ChildEntry> entries; }; // Wire format @@ -113,34 +151,32 @@ private: static InternalNode decode_internal(const std::vector<uint8_t>& bytes); static bool is_leaf_bytes(const std::vector<uint8_t>& bytes); - // Hex / binary - static Hash32 hex_to_bin(const std::string& hex); - static std::string bin_to_hex(const Hash32& bin); - // 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); - // Returns the minimum hash of the subtree rooted at node_hex. - static Hash32 subtree_min(IStorageBackend& store, const std::string& node_hex); + /** @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); - // Recursive insert result: new node hash, subtree leaf count, optional split. struct InsertResult { std::string new_hash; uint64_t leaf_count = 0; bool did_split = false; uint64_t split_leaf_count = 0; - Hash32 split_min_hash = {}; + Key split_min_key{}; std::string split_hash; }; static InsertResult insert_into(IStorageBackend& store, const std::string& node_hex, - const Hash32& tuple_hash); + const Key& key, + const Hash32& payload); - // Recursive remove result: new node hash (empty = node gone), leaf count. struct RemoveResult { std::string new_hash; uint64_t leaf_count = 0; @@ -148,17 +184,17 @@ private: static RemoveResult remove_from(IStorageBackend& store, const std::string& node_hex, - const Hash32& tuple_hash); + const Key& key); - // Page collection — offset consumed as we descend. static void page_from(IStorageBackend& store, const std::string& node_hex, size_t& offset, size_t limit, - std::vector<Hash32>& out); + std::vector<Entry>& out); - // Find which child to route into (rightmost whose min_hash ≤ target). - static size_t route(const InternalNode& node, const Hash32& target); + static std::optional<Hash32> get_from(IStorageBackend& store, + const std::string& node_hex, + const Key& key); }; } // namespace nt |