lab notes
In my previous lab note #028, I was worried that Prolly trees were not unicit. When I inserted keys in different orders, there was a small chance that splits would propagate to the end of the dataset. I was mistaken. Prolly Trees are unicit (the same data yields the same
retro review
Compared to 2021, I was much more focused this year. Compared to 2022, I have built more conviction. And starting in September, I started to have full days to work, rather than just the nights and weekends. Unlike 2021, I wasn't trying a lot of different things. I
lab notes
Last time, I found balancing nodes seemed to be in conflict with the property of a unicit tree. A balanced tree is desirable for efficient queries. A unicit tree is desirable for Merkle Trees for fast equality comparisons. Was there a way to get both? I noticed this problem was
lab notes
👉See Lab note #30 for corrections. Prolly Trees are unicit, and don't exhibit the bad behavior I've outlines below. Last week, I was looking at Prolly Trees. A major concern I had was whether the Prolly Tree was unicit [^1], and anhysteretic [^2]. These are desirable
crdt
🔰If CRDTs are new to you, here are some introductory links.  - An interactive intro to CRDTs  - An introduction to state-based CRDTs  - CRDTs for non-academics  - CRDT: The Hard Parts  - Readings in CRDTs  - crdt.tech Last time, I discussed the trade-offs between more traditional CRDTs, such
lab notes
When I found the splitting of nodes for Merkle Search Trees to be problematic, I stumbled upon Prolly Trees. They were first described by the Noms, a git for databases. It's a Merkle Tree that can store a sorted set. [^1] Like a B-Tree, all the data is
crdt
🔰If CRDTs are new to you, here are some introductory links.  - An interactive intro to CRDTs  - An introduction to state-based CRDTs  - CRDTs for non-academics  - CRDT: The Hard Parts  - Readings in CRDTs  - crdt.tech What are the trade-offs between different kinds of CRDTs (Conflict-free Replicated
lab notes
Most desktop, mobile, and web apps use a form-based metaphor to manipulate the state of the digital objects sitting in the database. This is a little odd when you think about it. Most things in the real-world don't work like this, aside from our complex machines. What would
lab notes
I started outlining how to compose different CRDTs together to make an Immutable Conflict-free Resolution Relations [1] construction, based on the Merkle Search Tree. When designing it, I first tried sketching out the entire construction by drawing, but I was left confused. I wasn't sure if all the
lab notes
I been reading various papers on CRDTs to deepen my understanding of them. That's when I happened upon a paper that constructed Merkle-CRDTs from Merkle-DAGs. Surprisingly, the internal merkle data structure of Git is like a vector clock. It establishes causal order of events from disparate parties to
lab notes
A major implication not often included in discussions of local-first software is how to deal with migrations. The degree of the problem depends largely on how you fence the boundaries of your system. If your local-first system allows any number of replicas to come in and out of the network
lab notes
SQL is the new QWERTY. It's a strong enough network effect that we'll have to keep living with it. I don't mind the declarative nature of SQL, but I do wish it was more composable and abstractable. While there is the WITH clause, it&