[HN Gopher] CRDTs Turned Inside Out
___________________________________________________________________
CRDTs Turned Inside Out
Author : iamwil
Score : 81 points
Date : 2024-01-25 16:00 UTC (6 hours ago)
(HTM) web link (interjectedfuture.com)
(TXT) w3m dump (interjectedfuture.com)
| taylorius wrote:
| I think the article would benefit from quickly defining what a
| CRDT is - (Conflict free Replicated Data Type). Even just
| expanding the acronym once would give a bit of an idea.
| iamwil wrote:
| Ah, I'll put it in as a note in the beginning. You can see a
| more basic introduction in a previous post I wrote:
|
| https://interjectedfuture.com/trade-offs-between-different-c...
|
| https://news.ycombinator.com/item?id=38916647
|
| Here's some introductory material I found helpful:
|
| - [An interactive intro to
| CRDTs](https://jakelazaroff.com/words/an-interactive-intro-to-
| crdts...)
|
| - [An introduction to state-based
| CRDTs](https://www.bartoszsypytkowski.com/the-state-of-a-state-
| base...)
|
| - [CRDTs for non-
| academics](https://www.youtube.com/watch?v=vBU70EjwGfw)
|
| - [CRDT: The Hard
| Parts](https://www.youtube.com/watch?v=x7drE24geUw)
|
| - [Readings in CRDTs](https://christophermeiklejohn.com/crdt/20
| 14/07/22/readings-i...)
|
| - [crdt.tech](https://crdt.tech)
| h4ch1 wrote:
| I usually just do a quick search on hn.algolia for previous
| discussions regarding a topic since I somehow imbibe
| information faster through reading discourse, where different
| opinions/viewpoints help me wrap my head around a concept
| faster. Also have noticed the same topic is often shared
| through different mediums (videos/articles), that also helps,
| getting curated, diverse content.
|
| May not be the same for you, but just a random observation d:)
| sitkack wrote:
| Mixture of debating armchair experts.
| vacuity wrote:
| Sometimes threads will veer off into opinionated fights,
| but there's something wonderful about the threads where
| people chime in on a topic and keep building on the
| content. I often learn something new from those.
| echelon wrote:
| tl;dr - "multiplayer web apps"
|
| The technical specifics can follow.
| lmm wrote:
| Disagree. CRDT is pretty much a word at this point, searching
| for the acronym will get you more useful results than expanding
| it.
| tadfisher wrote:
| Prolly trees are currently used (and maintained) in Dolt [1, 2],
| who dive a little deeper into the implementation.
|
| [1]: https://www.dolthub.com/blog/2020-04-01-how-dolt-stores-
| tabl... [2]: https://docs.dolthub.com/architecture/storage-
| engine/prolly-...
| zachmu wrote:
| Our implementation of the Merkle DAG data structure is
| optimized for tabular data since Dolt is a SQL database, but a
| lot of it generalizes to other kinds of data. For example, we
| put a lot of work into making sure that chunk sizes had a
| predictable distribution, since very large chunks kill query
| performance:
|
| https://www.dolthub.com/blog/2022-06-27-prolly-chunker/
|
| We also have a lot of work to do with preserving structural
| sharing across schema changes, which we're not great at yet.
|
| https://www.dolthub.com/blog/2024-01-19-structural-sharing-w...
| LAC-Tech wrote:
| _Normally, this is the job of vector clocks in State-based CRDTs_
|
| Is the author mistaking vector clocks for version vectors? If so
| he would not be the first; the famous Amazon Dynamo white paper
| makes the same mistake when discussing their CRDT
| implemenetation. But verson vectors and vector clocks are
| different things.
|
| Alternately, I may be ignorant of a class of CRDTs solved with
| vector clocks.
| macintux wrote:
| At Basho, we also got version vectors and vector clocks
| reversed, probably thanks to the Dynamo paper. As I recall,
| it's a subtle difference.
| LAC-Tech wrote:
| Yeah version vectors were first coined in a very underrated
| paper from 4 decades ago; "Detection of Mutual Inconsistency
| in Distributed Systems" [0].
|
| In it they not only invent version vectors, they also
| perfectly describe what came to be known as the "multi-value
| register CRDT", some three decades before the term was
| coined. (Amazon Dyano paper does the same, but only a few
| years before).
|
| Also, it contains this line which always makes me laugh:
|
| _Network partitioning can completely destroy mutual
| consistency in the worst case, and this fact has led to a
| certain amount of restrictiveness, vagueness, and even
| nervousness in past discussions, of how it may be handled._
|
| [0] https://pages.cs.wisc.edu/~remzi/Classes/739/Fall2018/Pap
| ers...
___________________________________________________________________
(page generated 2024-01-25 23:00 UTC)