hoytech/quadrable

Authenticated multi-version database: sparse binary merkle tree with compact partial-tree proofs

quadrable's Issues

Having some issues building on macOS Catalina/Big Sur

Can't seem to find any docs on building liblmdb-dev for macOS. Any ideas?

ld: library not found for -l:liblmdb.a
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [quadb] Error 1

This seems like a cool project, I'd love to give it a spin

few questions

Fascinating project, really loved the README.
However I am not very familiar with C++ so I thought asking these questions is faster than digging into the code base, and I hope it is useful for others as a FAQ.

1. Can LMDB be swapped with other databases like LevelDB, RocksDB, or IndexedDB? or is there a performance or other reasons to not support such abstraction?
2. If the answer for (1) is no, can Quadrable be used as a lightweight DB in browsers or mobile native apps? any guides for how to do so?
3. Since the merkle tree is a binary tree, I can imagine integer keys trees will have very deep leafs, does that demand O(n) of hashes (where n is the depth) or is there an efficient way to compress that? maybe it is in the README and I missed it.
4. Can you expand on why is Radix tree more complex than binary trees? And what are the optimisations used to approach the same advantages of a more shallow tree?

Thank you very much.

Benchmarks

Out of curiosity I hacked up part of the liburkel benchmark to work with Quadrable.

Inserting 100k records took about 3 times longer with quadrable compared to liburkel. Same with the get. The commit was basically identical (probably since both are basically just an msync).

I'm pretty satisfied with this result. liburkel's backing data-store is more specialised compared to ours which is just vanilla LMDB. If we feel like racing in the future here are some things we could try:

• In the liburkel benchmark the hashing of keys is done once up-front, whereas in Quadrable we are hashing keys again on insertion. We could extend the API to support pre-hashing like in liburkel, which would make the benchmark more equivalent.
• We could use a faster hash function. Right now it's an unoptimized keccak256 function for ethereum compatibility. liburkel uses blake2b which is way faster.
• Reduce dynamic memory allocation and pointer chasing during bulk insertion. There are probably better containers than std::map for this, for example a flatmap of some sort.
• Segregate leaf nodes into their own table to improve locality?