diff options
Diffstat (limited to '')
| -rw-r--r-- | include/CursorManager.h | 85 | ||||
| -rw-r--r-- | include/IStorageBackend.h | 76 | ||||
| -rw-r--r-- | include/InMemoryBackend.h | 43 | ||||
| -rw-r--r-- | include/SqliteBackend.h | 60 | ||||
| -rw-r--r-- | include/TupleCodec.h | 52 |
5 files changed, 269 insertions, 47 deletions
diff --git a/include/CursorManager.h b/include/CursorManager.h index 78ea24c..5636d8d 100644 --- a/include/CursorManager.h +++ b/include/CursorManager.h @@ -2,10 +2,10 @@ #include "Api.h" #include "HandlerManager.h" +#include "IStorageBackend.h" #include "Types.h" -#include <string> -#include <unordered_map> +#include <cstddef> #include <vector> /** @@ -17,55 +17,54 @@ namespace nt { /** * @class CursorManager - * @brief Orchestrates data pagination from storage backends to the query executor. + * @brief Orchestrates paginated data retrieval from a storage backend. * - * The cursor manager is the glue between registry objects and the - * Volcano-style iterator model. It translates high-level plan requests into - * low-level backend operations such as LMDB or etcd reads. + * CursorManager depends only on IStorageBackend. The concrete backend + * (SqliteBackend, InMemoryBackend, …) is injected at construction time. * - * Responsibilities: - * - Snapshot anchoring and pins: bind retrieval to a multigroup snapshot. - * The snapshot object should hold the reference to the tree containing - * all relations and tuples. - * - * - State maintenance: track the current iterator or offset inside a - * relation to support sequential Next() calls from the algebra engine. - * - * - Prefetching and buffering: abstract backend paging. For remote - * backends like etcd, manage local buffers to hide latency from the - * executor. Think of this as a database equivalent of an operating-system - * driver. - * - * - Boundary enforcement: ensure scans do not cross commit boundaries or - * logical branch definitions unless explicitly requested by the plan. + * Tuples are never loaded all at once. Open() fetches the first page; + * each subsequent Next() call transparently fetches the next page from + * the backend once the current page is exhausted. */ class NT_API CursorManager { public: - /** @brief Active scan state for a single relation. */ + static constexpr std::size_t PAGE_SIZE = 1; + + /** @brief Constructs a CursorManager that reads from the given backend. */ + explicit CursorManager(IStorageBackend& backend); + + /** + * @brief Active scan state for a single relation. + * + * Holds one page of deserialized tuples at a time. When page_position + * reaches the end of the page, Next() discards the page and fetches + * the next one from the backend. + * + * The pointer returned by Next() is valid only until the next Next() + * or Close() call — a page replacement invalidates all prior pointers. + */ struct cursor { - /** Handle that authorized this cursor. */ - HandlerManager::handle* handle; - // TODO: Replace with a lazy iterator into the physical storage backend. - // Pre-loading all tuples on Open() is a mock simplification. - std::vector<Tuple> tuples; - size_t position = 0; + HandlerManager::handle* handle = nullptr; + std::vector<Tuple> page; + std::size_t page_position = 0; + std::size_t fetch_offset = 0; // next TupleHashes() call starts here + bool exhausted = false; }; /** * @brief Opens a cursor on the relation referenced by the handle. - * @param handle Authorized handle to a RELATION object. - * @return A new cursor, or nullptr if the object is not a RELATION. + * + * Fetches the first page immediately. Returns nullptr if the relation + * has no tuples or the handle does not refer to a RELATION. */ cursor* Open(HandlerManager::handle* handle); /** * @brief Pulls the next tuple from the cursor. * - * The returned pointer is valid until the next Next() or Close() call. - * - * @param cursor Active cursor. - * @return Pointer to the next tuple, or nullptr when exhausted. + * Fetches the next page from the backend transparently when the + * current page is exhausted. Returns nullptr when all pages are done. */ Tuple* Next(cursor* cursor); @@ -75,19 +74,11 @@ namespace nt */ void Close(cursor* cursor); - /** - * @brief Inserts one tuple into the mock store for a given relation path. - * - * TODO: Replace with physical storage writes when the backend is wired up. - * - * @param path Logical path of the relation. - * @param tuple Attribute values for the tuple to insert. - */ - void MockInsert(std::vector<std::string> path, std::vector<Attribute> tuple); - private: - // TODO: Replace with physical storage backend access. - // Keyed by the relation path joined as "seg/seg/...". - std::unordered_map<std::string, std::vector<std::vector<Attribute>>> mock_store_; + IStorageBackend& backend_; + + /** Fetches a page of hashes, resolves each from the KV store, and + * deserializes them into cursor->page. Clears the existing page. */ + void LoadPage(cursor* c, const std::vector<std::string>& path); }; } diff --git a/include/IStorageBackend.h b/include/IStorageBackend.h new file mode 100644 index 0000000..884af2d --- /dev/null +++ b/include/IStorageBackend.h @@ -0,0 +1,76 @@ +#pragma once + +#include <cstdint> +#include <optional> +#include <string> +#include <vector> + +/** + * @file IStorageBackend.h + * @brief Abstract KV storage backend consumed by CursorManager. + * + * Storage is strictly content-addressed: every value is stored under its + * SHA256 hex digest. This mirrors the Sakura physical layer in which the + * key is always `Sha256.to_hex (Sha256.string serialized_bytes)` and the + * value is the raw serialized bytes. + * + * Relation membership (which tuple hashes belong to a given relation) is + * tracked via a separate index managed by LinkTuple / TupleHashes. This + * corresponds to Sakura's B+ tree of tuple hashes stored under each relation. + */ + +namespace nt +{ + /** + * @interface IStorageBackend + * @brief Contract between CursorManager and a physical (or mock) storage engine. + * + * Storage is strictly content-addressed: every value lives under its own + * SHA256 digest. Relation membership is tracked separately via + * LinkTuple / TupleHashes, mirroring Sakura's per-relation B+ tree. + */ + class IStorageBackend + { + public: + virtual ~IStorageBackend() = default; + + /** + * @brief Stores a serialized value and returns its SHA256 hex hash. + * + * Idempotent: storing the same bytes twice does not create a duplicate. + * The hash is the only valid key for subsequent Get calls. + */ + virtual std::string Put(std::vector<uint8_t> value) = 0; + + /** + * @brief Retrieves bytes by their SHA256 hex hash. + * @return The stored bytes, or std::nullopt when the hash is unknown. + */ + virtual std::optional<std::vector<uint8_t>> Get(const std::string& hash) = 0; + + /** + * @brief Records that a tuple (by hash) belongs to a relation (by path). + * + * Idempotent. Corresponds to appending a tuple hash to a relation's + * B+ tree in Sakura's physical layer. + */ + virtual void LinkTuple(const std::vector<std::string>& relation_path, + const std::string& tuple_hash) = 0; + + /** + * @brief Returns a page of tuple hashes for a relation. + * + * Pagination is tuple-level: @p offset and @p limit count whole tuples. + * Hashes are returned in insertion order. + * + * @param relation_path Logical relation path. + * @param offset Zero-based index of the first tuple to return. + * @param limit Maximum number of tuple hashes to return. + * @return Ordered list of SHA256 hex hashes. Empty when past the end. + */ + virtual std::vector<std::string> TupleHashes( + const std::vector<std::string>& relation_path, + std::size_t offset, + std::size_t limit) = 0; + }; +} diff --git a/include/InMemoryBackend.h b/include/InMemoryBackend.h new file mode 100644 index 0000000..8f7f50a --- /dev/null +++ b/include/InMemoryBackend.h @@ -0,0 +1,43 @@ +#pragma once + +#include "Api.h" +#include "IStorageBackend.h" + +#include <cstdint> +#include <optional> +#include <string> +#include <unordered_map> +#include <vector> + +/** + * @file InMemoryBackend.h + * @brief In-process KV storage backend backed by unordered_maps. + */ + +namespace nt +{ + /** + * @interface InMemoryBackend + * @brief IStorageBackend implementation that keeps all data in process memory. + * + * Intended for unit tests where SQLite is not appropriate. Data does not + * survive process exit and is not thread-safe. + */ + class NT_API InMemoryBackend : public IStorageBackend + { + public: + std::string Put(std::vector<uint8_t> value) override; + std::optional<std::vector<uint8_t>> Get(const std::string& hash) override; + void LinkTuple(const std::vector<std::string>& relation_path, + const std::string& tuple_hash) override; + std::vector<std::string> TupleHashes(const std::vector<std::string>& relation_path, + std::size_t offset, + std::size_t limit) override; + + private: + std::unordered_map<std::string, std::vector<uint8_t>> kv_; + std::unordered_map<std::string, std::vector<std::string>> index_; + + static std::string PathKey(const std::vector<std::string>& path); + }; +} diff --git a/include/SqliteBackend.h b/include/SqliteBackend.h new file mode 100644 index 0000000..0b21925 --- /dev/null +++ b/include/SqliteBackend.h @@ -0,0 +1,60 @@ +#pragma once + +#include "Api.h" +#include "IStorageBackend.h" + +#include <sqlite3.h> +#include <string> +#include <vector> + +/** + * @file SqliteBackend.h + * @brief IStorageBackend implementation backed by an in-process SQLite database. + * + * SQLite schema: + * + * kv(hash TEXT PRIMARY KEY, value BLOB NOT NULL) + * — content-addressed store; key is the SHA256 hex digest of value. + * + * relation_index(path TEXT NOT NULL, tuple_hash TEXT NOT NULL, + * UNIQUE(path, tuple_hash)) + * — maps a relation's logical path to the ordered set of tuple hashes + * it contains. Corresponds to Sakura's per-relation B+ tree of + * tuple hashes stored in the physical layer. + */ + +namespace nt +{ + /** + * @class SqliteBackend + * @brief IStorageBackend that persists data in a SQLite database. + * + * Constructed with a file path or ":memory:" for an in-process database. + * All KV values are opaque blobs; callers are responsible for serialization + * (see TupleCodec). + */ + class NT_API SqliteBackend : public IStorageBackend + { + public: + /** + * @brief Opens (or creates) a SQLite database at @p path. + * @param path File path, or ":memory:" for an in-process database. + * @throws std::runtime_error if the database cannot be opened. + */ + explicit SqliteBackend(const std::string& path = ":memory:"); + ~SqliteBackend() override; + + std::string Put(std::vector<uint8_t> value) override; + std::optional<std::vector<uint8_t>> Get(const std::string& hash) override; + void LinkTuple(const std::vector<std::string>& relation_path, + const std::string& tuple_hash) override; + std::vector<std::string> TupleHashes(const std::vector<std::string>& relation_path, + std::size_t offset, + std::size_t limit) override; + + private: + sqlite3* db_ = nullptr; + + static std::string PathKey(const std::vector<std::string>& path); + }; +} diff --git a/include/TupleCodec.h b/include/TupleCodec.h new file mode 100644 index 0000000..18294d4 --- /dev/null +++ b/include/TupleCodec.h @@ -0,0 +1,52 @@ +#pragma once + +#include "Types.h" + +#include <cstdint> +#include <string> +#include <vector> + +/** + * @file TupleCodec.h + * @brief Content-addressing utilities for tuples. + * + * Mirrors Sakura's hashing.ml and physical.ml: + * - Hash() ≈ hash_tuple: deterministic SHA256 over sorted attribute content + * - Serialize() ≈ Marshal.to_bytes: raw bytes stored as the KV value + * - Deserialize() ≈ Marshal.from_bytes: reconstruct attributes from raw bytes + * + * The hash input format is: + * "path_seg1/path_seg2/..|name1:value1;name2:value2;" + * where attributes are sorted by name for determinism. + * + * The serialization format is a sequence of length-prefixed UTF-8 pairs: + * [uint32_le name_len][name bytes][uint32_le value_len][value bytes] ... + */ + +namespace nt::TupleCodec +{ + /** + * @brief Computes the SHA256 hex digest of the serialized tuple. + * + * Equivalent to SHA256(Serialize(attrs)), so the value returned here + * matches the key returned by IStorageBackend::Put(Serialize(attrs)). + * + * @param attrs Attribute set. Need not be pre-sorted. + * @return 64-character lowercase hex string. + */ + std::string Hash(const std::vector<Attribute>& attrs); + + /** + * @brief Serializes a tuple's attributes to raw bytes for KV storage. + * @param attrs Attribute set. Need not be pre-sorted. + * @return Serialized bytes. + */ + std::vector<uint8_t> Serialize(const std::vector<Attribute>& attrs); + + /** + * @brief Reconstructs attributes from the bytes returned by Serialize(). + * @param bytes Bytes produced by Serialize(). + * @return Reconstructed attribute list in serialization order. + */ + std::vector<Attribute> Deserialize(const std::vector<uint8_t>& bytes); +} |