aboutsummaryrefslogtreecommitdiffstats
path: root/proposals/0000-hyperdb.md
diff options
context:
space:
mode:
authorBryan Newbold <bnewbold@robocracy.org>2018-02-04 19:09:56 -0800
committerBryan Newbold <bnewbold@robocracy.org>2018-02-28 22:02:14 -0800
commit6ca744c8d0f5e5a68123707abb54efa499a633fd (patch)
tree5b72dd58ef3352da519788198b4d550da197a0a1 /proposals/0000-hyperdb.md
parent53b72f01f68ad2c9c10c28ff21f5cda0929832ba (diff)
downloaddat-deps-6ca744c8d0f5e5a68123707abb54efa499a633fd.tar.gz
dat-deps-6ca744c8d0f5e5a68123707abb54efa499a633fd.zip
hyperdb progress
Diffstat (limited to 'proposals/0000-hyperdb.md')
-rw-r--r--proposals/0000-hyperdb.md131
1 files changed, 94 insertions, 37 deletions
diff --git a/proposals/0000-hyperdb.md b/proposals/0000-hyperdb.md
index 05764d1..e81fc59 100644
--- a/proposals/0000-hyperdb.md
+++ b/proposals/0000-hyperdb.md
@@ -5,7 +5,7 @@ Short Name: `0000-hyperdb`
Type: Standard
-Status: Undefined (as of 2018-01-XXX)
+Status: Undefined (as of 2018-02-XX)
Github PR: (add HTTPS link here after PR is opened)
@@ -17,14 +17,14 @@ Authors: noffle (Stephen Whitmore), bnewbold (Bryan Newbold)
HyperDB is a new abstraction layer providing a general purpose distributed
key/value store over the Dat protocol. It is an iteration on the hyperdrive
-directory tree implementation, providing a general purpose key/value store on
-top of the hypercore append-only log abstraction layer. Keys are path-like
-strings (eg, `/food/fruit/kiwi`), and values are arbitrary binary blobs (with
-expected size of under a megabyte).
+directory tree implementation, building top of the hypercore append-only log
+abstraction layer. Keys are path-like strings (eg, `/food/fruit/kiwi`), and
+values are arbitrary binary blobs (generally under a megabyte).
-hyperdrive is expected to be re-implemented on top of HyperDB for improved
-performance with many (millions) of files. The hyperdrive API should be largely
-unchanged, but the `metadata` format will be backwards-incompatible.
+Hyperdrive (used by the Dat application) is expected to be re-implemented on
+top of HyperDB for improved performance with many files (eg, millions). The
+hyperdrive API should be largely unchanged, but the `metadata` format will be
+backwards-incompatible.
# Motivation
@@ -37,44 +37,98 @@ basic local actions such as adding a directory taking an unacceptably long time
to complete.
A secondary benefit is to refactor the trie-structured key/value API out of
-hyperdrive, allowing third party code to build on this abstraction layer.
+hyperdrive, allowing third party code to build applications directly on this
+abstraction layer.
# Usage Documentation
[usage-documentation]: #usage-documentation
+*This section describes HyperDB's interface and behavior in the abstract for
+application programmers. It is not intended to be exact documentation of any
+particular implementation (including the reference Javascript module).*
+
HyperDB is structured to be used much like a traditional hierarchical
filesystem. A value can be written and read at locations like `/foo/bar/baz`,
and the API supports querying or tracking values at subpaths, like how watching
for changes on `/foo/bar` will report both changes to `/foo/bar/baz` and also
`/foo/bar/19`.
-## New API
+Lower-level details of the hypercore append-only log, disk serialization, and
+networked synchronization features that HyperDB builds on top of are not
+described in detail here. Multi-writer hypercore details are also not discussed
+in this DEP. References to formal documentation of these details are TODO.
-`add(key, value)`
+A HyperDB database instance can be represented by a single hypercore feed (or
+several feeds in a multi-writer context), and is named, referenced, and
+discovered using the public and discovery keys of the hypercore feed (or the
+original feed if there are several). In a single-writer configuration, only a
+single node (holding the secret key) can mutate the database (eg, via `put` or
+`delete` actions).
-`get(key)`
+**Keys** can be any UTF-8 string. Path segments are separated by the forward
+slash character (`/`).
-`delete(key)`
+**Values** can be any binary blob, including empty (of zero length). For
+example, values could be UTF-8 encoded strings, JSON encoded objects, protobuf
+messages, or a raw `uint64` integer (of either endian-ness). Length is the only
+form of type or metadata stored about the value; deserialization and validation
+are left to library and application developers.
-# Reference Documentation
-[reference-documentation]: #reference-documentation
+TODO: key corner-cases:
+- `///` same as `//`? `///a` vs. `//a`?
+
+TODO: size limits on keys and values?
+
+TODO: "prefix" end in a trailing slash, or optional?
+
+A leading `/` is optional: `db.get('/hello')` and `db.get('hello')` are
+equivalent.
+
+## Core API Semantics
+
+`db.put(key, value)`: inserts `value` (arbitrary bytes) under the path `key`.
+Returns an error (eg, via callback) if there was a problem.
+
+`db.get(key)`: Reading a non-existant `key` is an error.
+
+`db.delete(key)`: Removes the key from the database. Deleting a non-existant
+key is an error.
+
+`db.list(prefix)`: returns a flat (not nested) list of all keys currently in
+the database.
+
+TODO: in what order?
-## Set of append-only logs (feeds)
+TODO: what if node is a file, not a prefix?
-A HyperDB is fundamentally a set of
-[hypercore](https://github.com/mafintosh/hypercore)s. A *hypercore* is a secure
-append-only log that is identified by a public key, and can only be written to
-by the holder of the corresponding private key.
+An example pseudo-code session working with a database might be:
-Each entry in a hypercore has a *sequence number*, that increments by 1 with
-each write, starting at 0 (`seq=0`).
+TODO:
-HyperDB builds its hierarchical key-value store on top of these hypercore
-feeds, and also provides facilities for authorization, and replication of those
-member hypercores.
+TODO: Read Stream
-## Incremental index
+TODO: Changes Stream
+
+TODO: Diff Stream
+
+
+# Reference Documentation
+[reference-documentation]: #reference-documentation
+
+The new Node protobuf message schema is:
+
+```
+ message Node {
+ optional string key = 1;
+ optional bytes value = 2;
+ repeated uint64 clock = 3;
+ optional bytes trie = 4;
+ optional uint64 feedSeq = 6; // TODO remove and merge into index (trie+feedSeq)
+ }
+```
+
+## Incremental Index
HyperDB builds an *incremental index* with every new key/value pairs ("nodes")
written. This means a separate data structure doesn't need to be maintained
@@ -209,19 +263,22 @@ TODO:
- What parts of the design do you expect to resolve through implementation and code review, or are left to independent library or application developers?
- What related issues do you consider out of scope for this DEP that could be addressed in the future independently of the solution that comes out of this DEP?
-# Migration logistics
+# Dat Migration logistics
[migration]: #migration
-HyperDB is not backwards compatible with the existing hyperdrive
-implementation, meaning dat clients will need to support multiple on-disk
-representations during a transition period.
+HyperDB is not backwards compatible with the existing hyperdrive metadata,
+meaning dat clients may need to support both versions during a transition
+period. This applies both to archives saved to disk (eg, in SLEEP) and to
+archives received and published to peers over the network.
+
+No changes to the Dat network wire protocol itself are necessary, only changes
+to content passed over the protocol. The Dat `content` feed, containing raw
+file data, is not impacted by HyperDB, only the contents of the `metadata`
+feed.
-a new abstraction layer between hypercore (replicated append-only
-logs) and hyperdrive (versioned file system abstraction). HyperDB provides an
-efficient key/value database API, with path-like strings as keys and arbitrary
-binary data (up to a reasonable chunk size) as values. HyperDB will require
-breaking changes to dat clients, but will not require changes to the network
-wire protocol.
+Upgrading a Dat (hyperdrive) archive to HyperDB will necessitate creating a new
+feed from scratch, meaning new public/private key pairs, and that public key
+URL links will need to change.
# Changelog
[changelog]: #changelog
@@ -232,6 +289,6 @@ for this DEP.
- 2017-12-06: @noffle publishes `ARCHITECTURE.md` overview in the
[hyperdb github repo][arch_md]
-- 2018-01-XXX: First complete draft submitted for review
+- 2018-02-XX: First complete draft submitted for review
[arch_md]: https://github.com/mafintosh/hyperdb/blob/master/ARCHITECTURE.md