7 ms·

Show HN: A strongly-typed document DB that runs on any transactional KV store

113 points by losfair 5y ago

guywhocodes 5y ago
Love the concept, I'm targeting foundationDB for a project but i don't want to use it for local development and some deployments. I'll explore targeting this with my repository implementation to save some complexity.
lewisjoe 5y ago
Great work! The ideas are intriguing. I want to know more about the quering approach. How is it better than SQL or other document quering representations? What is a concurrent data flow virtual machine ? What is the contract to make this layer talk with the underlying stores (say, POSTGRES)? Just want to pick your brain on these topics. Thanks :)
- losfair 5y ago
  Thanks for the questions! > How is it better than SQL or other document querying representations? SQL is a nice language for querying relational data, but RefineDB deals with nested documents. I think translation from SQL is possible for the subset of RefineDB schemas where documents are not nested though. And RefineDB has types, and I’m not aware of any other query language that deal with types (let me know if I'm wrong). > What is a concurrent data flow virtual machine? The query language (RefineAsm) is a functional language with immutable semantics where values cannot be modified after construction. So a RefineAsm program can be encoded as a data flow graph where nodes are instructions and edges are data dependencies, and instructions that don’t depend on each other can be evaluated concurrently. Read accesses to a distributed key-value store usually incur at least a few hundred microseconds of latency, so by evaluating instructions concurrently the total latency can be minimized. Somewhat similar to what a SQL query planner does. > What is the contract to make this layer talk with the underlying stores A storage plan is generated from the schema (the schema is the type of the storage plan). The storage plan describes how paths of document accesses should map to the underlying key-value space. There are detailed description and examples of how this mapping is done at https://github.com/losfair/RefineDB/blob/main/design/storage.md https://github.com/losfair/RefineDB/blob/main/design/storage....
  - unraveller 5y ago
    >other query language that deal with types EdgeDB has a similar strongly typed schema [1], see their edgeQL/graphQL ability. Their typed schema also facilitates computed references and computed anything, which is crucial for nested items as it keeps your DB calls much simpler. They make SQL style queries for nested data easy. On the topic of great QL i really love what deeprQL[2] brought to the table but it's JS only. [1] https://www.edgedb.com/docs/edgeql/index https://www.edgedb.com/docs/edgeql/index [2] https://github.com/deeprjs/deepr https://github.com/deeprjs/deepr
    - cormacrelf 5y ago
      This is a bit off-topic, but I would really like to see a good query optimiser for GraphQL. Last I checked the industry standard solution to the "N+1 selects" problem that nested queries trigger was to add a delay and attempt to batch those N calls into one. I expect EdgeDB's GraphQL implementation just translates to EdgeQL/SQL and can simply optimise that. (Probably Hasura does this too.) But I have yet to see anything near that in a GraphQL server implementation for any programming language. From the GraphQL FAQ: > Accessing and manipulating data is performed with arbitrary functions called resolvers. ... Generally, these resolver functions should delegate to a business logic layer responsible for communicating with the various underlying data sources. These data sources could be remote APIs, databases, local cache, and nearly anything else your programming language can access. Somehow the lets-implement-this-syntax-in-100-popular-languages part of being a new language means these GraphQL server libraries just give you bare bones "get by id", "get all" interfaces to implement, and you're stuck with their dumb processing. This looks like a pretty standard experience of implementing GraphQL, and having to clear out a dozen jaw-droppingly dumb bugs introduced because the libraries do literally nothing for you: https://www.toptal.com/graphql/graphql-internal-api-optimization https://www.toptal.com/graphql/graphql-internal-api-optimiza.... Being a language, of course it must describe what the queries actually do in abstract, naive terms. Just like a programming language standard. But undefined behaviours are meant to be exploited, not used as a prototype for every implementation on Earth. I don't think GraphQL implementations are doing this nearly enough, considering that the goal is to build an SQL-like for arbitrary data backends. SQL databases ALL have optimisers. It's simply non-negotiable. For GraphQL, do whatever you need -- ask me which collections are available as tables in the same database so you can reorganise a query and send them as one "codegen unit", ask me to estimate the cost of using a resolver, ask me to build and keep indexes. That's the job, right?
tluyben2 5y ago
Nice work! Been playing with this idea for a while to write something like this (in Rust); now you did a lot of the heavy lifting for what I would need already.
- losfair 5y ago
  Thanks :)
danr4 5y ago
Looks very very interesting. Nice work. Plans to support more DBs? do you intend for the OS community to build the translation layers?
- losfair 5y ago
  Thanks! > Plans to support more DBs? RocksDB and TiKV backends are planned: https://github.com/losfair/RefineDB/issues/3 https://github.com/losfair/RefineDB/issues/3 > do you intend for the OS community to build the translation layers? What do you mean by "translation layers" here?
  - tluyben2 5y ago
    I really like TiKV: can you explain what the issue is with it? And do what are ways to resolve it if TiKV does not resolve it themselves? Did you do any profiling on your in memory store? I am looking, working on a toy project, for something like this that has 3 layers: local mem, distributed memory and distributed persistence with the same api and, more specifically, query engine. There are kv stores for these (TiKV and Foundation for the last category), Rondb maybe for the in distributed in memory but locally, it should be capable of very high volume (evmap doing a billion/minute but that would not work as not transactional). I bet it is too early to worry about perf for you but it seems you can leave most of that to the kv store which I like.
    - losfair 5y ago
      > can you explain what the issue is with it? And do what are ways to resolve it if TiKV does not resolve it themselves? TiKV is based on multi-raft + Percolator where there is no way to coordinate a consistent range operation across regions (key ranges) and therefore does not support range deletion. RefineDB uses range deletion to delete non-primitive types that contain multiple members, e.g. tables and sets. To support TiKV, RefineDB needs to support asynchronous range deletion - mark a range as deleted, and never use it again. This requires some work on the storage mapping layer, to map ABA accesses to a recreated-after-deleted range to a different keyspace. > Did you do any profiling on your in memory store? Not yet, actually the in-memory store is just for use in tests and the web playground where performance isn't important. For a better in-memory store, I think it's better to use the SQLite backend with an in-memory database.
voidmain 5y ago
This looks really cool! Perhaps you should show some nontrivial examples of (read) queries in RefineASM. Also, what are your plans (if any) for non primary indexing? Storage plans seem like a good fit, but will you transform RefineASM to maintain the indexes or what? What about using the indexes?
- losfair 5y ago
  There are some non-trivial examples of read and update queries in the test: https://github.com/losfair/RefineDB/blob/main/rdb-analyzer/src/data/treewalker/asm/asm_test.rs https://github.com/losfair/RefineDB/blob/main/rdb-analyzer/s... For example, here's a test that generates a list of integers, inserts the list into the database as set members, computes the sum and verifies it, and reads back the list: https://github.com/losfair/RefineDB/blob/ddac0d35b16c01105ddbe65f2b3605713fde4be4/rdb-analyzer/src/data/treewalker/asm/asm_test.rs#L392 https://github.com/losfair/RefineDB/blob/ddac0d35b16c01105dd... . The read-back part looks like: // Schema /* type Store { collection_a: set<Number>, collection_b: set<Number>, } type Number { @primary value: int64, } export Store store; */ graph main(root: schema): map { list1: list<int64>, list2: list<int64>, } { list1 = reduce(decompose_numbers) create_map create_list(int64) root.store.collection_a; list2 = reduce(decompose_numbers) create_map create_list(int64) root.store.collection_b; return m_insert(list1) list1 $ m_insert(list2) list2 create_map; } graph decompose_numbers(_unused: map{}, current: list<int64>, v: Number): list<int64> { return v.value : current; } And it's trivial to modify the reduce function `decompose_numbers` to return a more interesting aggregated value, e.g. the sum. The syntax is not yet very optimized for humans though (hence the name RefineAsm).
- losfair 5y ago
  On non-primary indexing: It's a nice thing to have but I haven't decided on the design yet. My current preference is to implement the non-primary index feature as a library once the human-friendly higher layer of RefineAsm (RefineQL) is built.
  - voidmain 5y ago
smoyer 5y ago
If a document DB is strongly typed, if should be possible to implement SQL to return results right?
rmorey 5y ago
I love this - a KV store is such a powerful primitive, I've wondered why we don't see more projects like this
- bognition 5y ago
  There is https://www.foundationdb.org/ https://www.foundationdb.org/ Which is incredible.
  - nkohari 5y ago
    This runs on FoundationDB.
monstrado 5y ago
This looks really promising! Could you provide at a high-level what this aims to offer over FoundationDB's RecordLayer[1]? [1] https://github.com/FoundationDB/fdb-record-layer https://github.com/FoundationDB/fdb-record-layer
- losfair 5y ago
  - Both FDB record layer and RefineDB support complex types and indexes (with the details differing a lot); FDB record layer's index support is more complete for now. - FDB record layer is more mature and well-tested. - RefineDB supports KV backends other than FoundationDB. - RefineDB can run either as a server or an embedded library in user applications; FDB record layer is a Java-only library. - RefineDB has a functional query language for complex queries; FDB record layer does not and provides a query API instead that allows to scan, filter and sort across records.
zackmorris 5y ago
This is great! Can you implement a data-changed event stream like the RethinkDB changefeed and Firebase triggers? https://rethinkdb.com/docs/changefeeds/javascript/ https://rethinkdb.com/docs/changefeeds/javascript/ https://firebase.google.com/docs/functions/database-events https://firebase.google.com/docs/functions/database-events This functionality is critical for writing web apps that reflect the current state when multiple users are collaborating on the same data. I've been down the road many times of starting with a POST-style request/response website, only to find that it inevitably needs a realtime event feed over WebSocket to show notifications or otherwise update the view when another user changes some data. I can't stress this enough, but, IMHO a database that doesn't have this doesn't really have anything. And most databases don't have this. If that's too ambitious, another option would be filters and/or callback hooks on the server. That way a process would be notified when something was trying to be changed, or had been changed. Then the user could append events containing the data identifier/path onto their own WebSocket manually. Apologies if you've already implemented this and I just haven't read the documentation. Another rather selfish ask for myself would be a transpiler from SQL to your RefineASM DSL. Being able to go the other way would be pretty awesome too. I'd love to design queries using sets and be able to generate the SQL without having to deal with SQL's quirks since it's so old.

113 points by losfair 5y ago

Love the concept, I'm targeting foundationDB for a project but i don't want to use it for local development and some deployments. I'll explore targeting this with my repository implementation to save some complexity.

lewisjoe 5y ago

Great work! The ideas are intriguing. I want to know more about the quering approach. How is it better than SQL or other document quering representations? What is a concurrent data flow virtual machine ? What is the contract to make this layer talk with the underlying stores (say, POSTGRES)? Just want to pick your brain on these topics. Thanks :)

losfair 5y ago
Thanks for the questions! > How is it better than SQL or other document querying representations? SQL is a nice language for querying relational data, but RefineDB deals with nested documents. I think translation from SQL is possible for the subset of RefineDB schemas where documents are not nested though. And RefineDB has types, and I’m not aware of any other query language that deal with types (let me know if I'm wrong). > What is a concurrent data flow virtual machine? The query language (RefineAsm) is a functional language with immutable semantics where values cannot be modified after construction. So a RefineAsm program can be encoded as a data flow graph where nodes are instructions and edges are data dependencies, and instructions that don’t depend on each other can be evaluated concurrently. Read accesses to a distributed key-value store usually incur at least a few hundred microseconds of latency, so by evaluating instructions concurrently the total latency can be minimized. Somewhat similar to what a SQL query planner does. > What is the contract to make this layer talk with the underlying stores A storage plan is generated from the schema (the schema is the type of the storage plan). The storage plan describes how paths of document accesses should map to the underlying key-value space. There are detailed description and examples of how this mapping is done at https://github.com/losfair/RefineDB/blob/main/design/storage.md https://github.com/losfair/RefineDB/blob/main/design/storage....
- unraveller 5y ago
  >other query language that deal with types EdgeDB has a similar strongly typed schema [1], see their edgeQL/graphQL ability. Their typed schema also facilitates computed references and computed anything, which is crucial for nested items as it keeps your DB calls much simpler. They make SQL style queries for nested data easy. On the topic of great QL i really love what deeprQL[2] brought to the table but it's JS only. [1] https://www.edgedb.com/docs/edgeql/index https://www.edgedb.com/docs/edgeql/index [2] https://github.com/deeprjs/deepr https://github.com/deeprjs/deepr
  - cormacrelf 5y ago
    This is a bit off-topic, but I would really like to see a good query optimiser for GraphQL. Last I checked the industry standard solution to the "N+1 selects" problem that nested queries trigger was to add a delay and attempt to batch those N calls into one. I expect EdgeDB's GraphQL implementation just translates to EdgeQL/SQL and can simply optimise that. (Probably Hasura does this too.) But I have yet to see anything near that in a GraphQL server implementation for any programming language. From the GraphQL FAQ: > Accessing and manipulating data is performed with arbitrary functions called resolvers. ... Generally, these resolver functions should delegate to a business logic layer responsible for communicating with the various underlying data sources. These data sources could be remote APIs, databases, local cache, and nearly anything else your programming language can access. Somehow the lets-implement-this-syntax-in-100-popular-languages part of being a new language means these GraphQL server libraries just give you bare bones "get by id", "get all" interfaces to implement, and you're stuck with their dumb processing. This looks like a pretty standard experience of implementing GraphQL, and having to clear out a dozen jaw-droppingly dumb bugs introduced because the libraries do literally nothing for you: https://www.toptal.com/graphql/graphql-internal-api-optimization https://www.toptal.com/graphql/graphql-internal-api-optimiza.... Being a language, of course it must describe what the queries actually do in abstract, naive terms. Just like a programming language standard. But undefined behaviours are meant to be exploited, not used as a prototype for every implementation on Earth. I don't think GraphQL implementations are doing this nearly enough, considering that the goal is to build an SQL-like for arbitrary data backends. SQL databases ALL have optimisers. It's simply non-negotiable. For GraphQL, do whatever you need -- ask me which collections are available as tables in the same database so you can reorganise a query and send them as one "codegen unit", ask me to estimate the cost of using a resolver, ask me to build and keep indexes. That's the job, right?

tluyben2 5y ago

Nice work! Been playing with this idea for a while to write something like this (in Rust); now you did a lot of the heavy lifting for what I would need already.

losfair 5y ago
Thanks :)

danr4 5y ago

Looks very very interesting. Nice work. Plans to support more DBs? do you intend for the OS community to build the translation layers?

losfair 5y ago
Thanks! > Plans to support more DBs? RocksDB and TiKV backends are planned: https://github.com/losfair/RefineDB/issues/3 https://github.com/losfair/RefineDB/issues/3 > do you intend for the OS community to build the translation layers? What do you mean by "translation layers" here?
- tluyben2 5y ago
  I really like TiKV: can you explain what the issue is with it? And do what are ways to resolve it if TiKV does not resolve it themselves? Did you do any profiling on your in memory store? I am looking, working on a toy project, for something like this that has 3 layers: local mem, distributed memory and distributed persistence with the same api and, more specifically, query engine. There are kv stores for these (TiKV and Foundation for the last category), Rondb maybe for the in distributed in memory but locally, it should be capable of very high volume (evmap doing a billion/minute but that would not work as not transactional). I bet it is too early to worry about perf for you but it seems you can leave most of that to the kv store which I like.
  - losfair 5y ago
    > can you explain what the issue is with it? And do what are ways to resolve it if TiKV does not resolve it themselves? TiKV is based on multi-raft + Percolator where there is no way to coordinate a consistent range operation across regions (key ranges) and therefore does not support range deletion. RefineDB uses range deletion to delete non-primitive types that contain multiple members, e.g. tables and sets. To support TiKV, RefineDB needs to support asynchronous range deletion - mark a range as deleted, and never use it again. This requires some work on the storage mapping layer, to map ABA accesses to a recreated-after-deleted range to a different keyspace. > Did you do any profiling on your in memory store? Not yet, actually the in-memory store is just for use in tests and the web playground where performance isn't important. For a better in-memory store, I think it's better to use the SQLite backend with an in-memory database.

voidmain 5y ago

This looks really cool! Perhaps you should show some nontrivial examples of (read) queries in RefineASM. Also, what are your plans (if any) for non primary indexing? Storage plans seem like a good fit, but will you transform RefineASM to maintain the indexes or what? What about using the indexes?

losfair 5y ago
There are some non-trivial examples of read and update queries in the test: https://github.com/losfair/RefineDB/blob/main/rdb-analyzer/src/data/treewalker/asm/asm_test.rs https://github.com/losfair/RefineDB/blob/main/rdb-analyzer/s... For example, here's a test that generates a list of integers, inserts the list into the database as set members, computes the sum and verifies it, and reads back the list: https://github.com/losfair/RefineDB/blob/ddac0d35b16c01105ddbe65f2b3605713fde4be4/rdb-analyzer/src/data/treewalker/asm/asm_test.rs#L392 https://github.com/losfair/RefineDB/blob/ddac0d35b16c01105dd... . The read-back part looks like: // Schema /* type Store { collection_a: set<Number>, collection_b: set<Number>, } type Number { @primary value: int64, } export Store store; */ graph main(root: schema): map { list1: list<int64>, list2: list<int64>, } { list1 = reduce(decompose_numbers) create_map create_list(int64) root.store.collection_a; list2 = reduce(decompose_numbers) create_map create_list(int64) root.store.collection_b; return m_insert(list1) list1 $ m_insert(list2) list2 create_map; } graph decompose_numbers(_unused: map{}, current: list<int64>, v: Number): list<int64> { return v.value : current; } And it's trivial to modify the reduce function `decompose_numbers` to return a more interesting aggregated value, e.g. the sum. The syntax is not yet very optimized for humans though (hence the name RefineAsm).
losfair 5y ago
On non-primary indexing: It's a nice thing to have but I haven't decided on the design yet. My current preference is to implement the non-primary index feature as a library once the human-friendly higher layer of RefineAsm (RefineQL) is built.
- voidmain 5y ago

smoyer 5y ago

If a document DB is strongly typed, if should be possible to implement SQL to return results right?

rmorey 5y ago

I love this - a KV store is such a powerful primitive, I've wondered why we don't see more projects like this

bognition 5y ago
There is https://www.foundationdb.org/ https://www.foundationdb.org/ Which is incredible.
- nkohari 5y ago
  This runs on FoundationDB.

monstrado 5y ago

This looks really promising! Could you provide at a high-level what this aims to offer over FoundationDB's RecordLayer[1]? [1] https://github.com/FoundationDB/fdb-record-layer https://github.com/FoundationDB/fdb-record-layer

losfair 5y ago
- Both FDB record layer and RefineDB support complex types and indexes (with the details differing a lot); FDB record layer's index support is more complete for now. - FDB record layer is more mature and well-tested. - RefineDB supports KV backends other than FoundationDB. - RefineDB can run either as a server or an embedded library in user applications; FDB record layer is a Java-only library. - RefineDB has a functional query language for complex queries; FDB record layer does not and provides a query API instead that allows to scan, filter and sort across records.

zackmorris 5y ago

This is great! Can you implement a data-changed event stream like the RethinkDB changefeed and Firebase triggers? https://rethinkdb.com/docs/changefeeds/javascript/ https://rethinkdb.com/docs/changefeeds/javascript/ https://firebase.google.com/docs/functions/database-events https://firebase.google.com/docs/functions/database-events This functionality is critical for writing web apps that reflect the current state when multiple users are collaborating on the same data. I've been down the road many times of starting with a POST-style request/response website, only to find that it inevitably needs a realtime event feed over WebSocket to show notifications or otherwise update the view when another user changes some data. I can't stress this enough, but, IMHO a database that doesn't have this doesn't really have anything. And most databases don't have this. If that's too ambitious, another option would be filters and/or callback hooks on the server. That way a process would be notified when something was trying to be changed, or had been changed. Then the user could append events containing the data identifier/path onto their own WebSocket manually. Apologies if you've already implemented this and I just haven't read the documentation. Another rather selfish ask for myself would be a transpiler from SQL to your RefineASM DSL. Being able to go the other way would be pretty awesome too. I'd love to design queries using sets and be able to generate the SQL without having to deal with SQL's quirks since it's so old.