diff options
author | EuAndreh <eu@euandre.org> | 2024-11-18 08:21:58 -0300 |
---|---|---|
committer | EuAndreh <eu@euandre.org> | 2024-11-18 08:44:57 -0300 |
commit | 960e4410f76801356ebd42801c914b2910a302a7 (patch) | |
tree | 615d379416f72956d0c1666c63ce062859041fbe /src/content/blog/2020/11/12 | |
parent | Remove jekyll infrastructure setup (diff) | |
download | euandre.org-960e4410f76801356ebd42801c914b2910a302a7.tar.gz euandre.org-960e4410f76801356ebd42801c914b2910a302a7.tar.xz |
v0 migration to mkwb
Diffstat (limited to '')
-rw-r--r-- | src/content/blog/2020/11/12/database-parsers-trees.adoc (renamed from _articles/2020-11-12-durable-persistent-trees-and-parser-combinators-building-a-database.md) | 20 |
1 files changed, 9 insertions, 11 deletions
diff --git a/_articles/2020-11-12-durable-persistent-trees-and-parser-combinators-building-a-database.md b/src/content/blog/2020/11/12/database-parsers-trees.adoc index 05e800e..1870fad 100644 --- a/_articles/2020-11-12-durable-persistent-trees-and-parser-combinators-building-a-database.md +++ b/src/content/blog/2020/11/12/database-parsers-trees.adoc @@ -1,6 +1,4 @@ ---- - -title: Durable persistent trees and parser combinators - building a database += Durable persistent trees and parser combinators - building a database date: 2020-11-12 @@ -22,7 +20,7 @@ I've made any progress on the database project There are a few areas where I've made progress, and here's a public post on it. -## Proof-of-concept: DAG log +== Proof-of-concept: DAG log The main thing I wanted to validate with a concrete implementation was the concept of modeling a DAG on a sequence of datoms. @@ -80,7 +78,7 @@ This code [already exists][clj-poc], but is yet fairly incomplete: [clj-poc-o2-1]: https://euandre.org/git/mediator/tree/src/core/clojure/src/mediator.clj?id=db4a727bc24b54b50158827b34502de21dbf8948#n146 [clj-poc-o2-2]: https://euandre.org/git/mediator/tree/src/core/clojure/src/mediator.clj?id=db4a727bc24b54b50158827b34502de21dbf8948#n253 -## Top-down *and* bottom-up +== Top-down *and* bottom-up However, as time passed and I started looking at what the final implementation would look like, I started to consider keeping the PoC around. @@ -94,7 +92,7 @@ The good thing about a reference implementation is that it has no performance of resources boundary, so if it ends up being 1000x slower and using 500× more memory, it should be find. The code can be also 10x or 100x simpler, too. -## Top-down: durable persistent trees +== Top-down: durable persistent trees In promoting the PoC into a reference implementation, this top-down approach now needs to go beyond doing everything in memory, and the index data structure now @@ -120,15 +118,15 @@ what it will look like: building a new path from root to the leaf. The upside is that writes a lock free, and no coordination is needed between readers and writers, ever; -1. the downside is that a single leaf update means at least `H` new nodes that +2. the downside is that a single leaf update means at least `H` new nodes that will have to be flushed to disk, where `H` is the height of the tree. To avoid that, the writer creates these nodes exclusively on the in-memory memtable, to avoid flushing to disk on every leaf update; -1. a background job will consolidate the memtable data every time it hits X MB, +3. a background job will consolidate the memtable data every time it hits X MB, and persist it to disk, amortizing the cost of the Copy-on-Write B-Tree; -1. readers than will have the extra job of getting the latest relevant +4. readers than will have the extra job of getting the latest relevant disk-resident value and merge it with the memtable data. The key difference to existing Copy-on-Write B-Trees is that the new trees @@ -155,7 +153,7 @@ more[^learn-more-db] and mature it more. "[Intro to Database Systems](https://www.youtube.com/playlist?list=PLSE8ODhjZXjbohkNBWQs_otTrBTrjyohi)" course and Alex Petrov's "[Database Internals](https://www.databass.dev/)" book. -## Bottom-up: parser combinators and FFI +== Bottom-up: parser combinators and FFI I chose Rust as it has the best WebAssembly tooling support. @@ -226,7 +224,7 @@ and property-based testing for libedn. [rust-ffi]: https://blog.eqrion.net/future-directions-for-cbindgen/ [libedn-repo]: https://euandre.org/git/libedn/ -## Conclusion +== Conclusion I've learned a lot already, and I feel the journey I'm on is worth going through. |