aboutsummaryrefslogtreecommitdiff
path: root/src/content/blog/2020/11/12
diff options
context:
space:
mode:
authorEuAndreh <eu@euandre.org>2024-11-18 08:21:58 -0300
committerEuAndreh <eu@euandre.org>2024-11-18 08:44:57 -0300
commit960e4410f76801356ebd42801c914b2910a302a7 (patch)
tree615d379416f72956d0c1666c63ce062859041fbe /src/content/blog/2020/11/12
parentRemove jekyll infrastructure setup (diff)
downloadeuandre.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.