alcinnz
Since yesterday I saw (from @bean ) chatter about designing a version control system for a broader audience.
So today's algorithm for discussion is a relatively recent one: CRDTs (Conflict-free Replicated DataTypes)!
In very brief if you model data as an inversely-linked tree, with deterministic if often arbitrary sorting, then you can merge changes into this document however frequently you like.
For the scheme to work there must never be any hard-conflicts!
1/2
alcinnz
The goal is to guarantee that no matter in which order the edits are received, all participants still end up with the exact same document onscreen. We've mathematically proven it, & ran simulations to double-check our work!
CRDTs not only gives us collaboration but also infinite undo & auto-save! As someone who enjoys writing about hypothetical new computing systems, I'd be foolish in the 2020's to not include CRDTs in my hypothetical editors!
Then there's the performance concern...
2/3!
alcinnz
CRDTs decomposes your document into tiny pieces to obfuscate the difference between data & edits. If not addressed this can easily introduce performance issues!
To ease processing we want to store the data sorted in document-order, avoiding the O(n*log n) cost of sorting.
And to avoid the storage overhead of all the metadata attached to each miniscule edit Ink&Switch has found columnar-compression all but removes the extra storage space required!
3/3! Unless... Lamport Timestamps?
alcinnz
Addendum: I see that discussing Lamport Timestamps would help replies.
This comes down to CRDTs need for there to be a deterministic, if often arbitrary, order to the edits/nodes making up the document.
If the edit is commutative CRDTs work fine! Otherwise Lampart Timestamps are *one* strategy for prioritizing edits. When time's sync'd imperfectly.
Each node tracks its understanding of all their peers' latest timestamp, to attach to their edits. That's a Lampart Timestamp!
4/3!
d.rift
@alcinnz And yet somehow we are stuck with context unaware git merge. 🤷♂️ What would developer expectations of minimum software capability look like if our own tooling wasn't conceptually decades out of date...
alcinnz
@feonixrift Its hard to imagine, but I try to!
GNU social JP is a social network, courtesy of GNU social JP管理人. It runs on GNU social, version 2.0.2-dev, available under the GNU Affero General Public License.
All GNU social JP content and data are available under the Creative Commons Attribution 3.0 license.