6 ms·
So far this is probably the best "intro to CRDTs for a developer" I've read. I built a product around CRDTs, essentially, and my god was it painful trying to en
by insanitybit 3y ago
So far this is probably the best "intro to CRDTs for a developer" I've read. I built a product around CRDTs, essentially, and my god was it painful trying to engage with. Showing actual code, explaining that `merge` is the fundamental operation, etc, is really all a developer needs to know IMO.
Also, the fact that we always use text editing as the de-facto solution is so weird to me since that problem is both niche and extremely complex. IMO a better example would be something like "Can this person drink alcohol?". Age moves in one direction so it has a simple merge function:
def set_age(self, new_age: int):
self.age = max(self.age, new_age)
A property of this is that if I query your age and if you're 21 I can cache that age forever. You'll only ever be >= 21, after all. If I add new queries that care about you being 25 (for a hotel) I can satisfy the "drinking age" queries from a stale cache and then retrieve the true value (<25) when I need to check if you can book a hotel.
This means you can have distributed caches without invalidation logic. A pretty amazing property since cache invalidation is a hugely complex problem and has seriously negative performance/ storage implications.
It also means you can drop writes. If my system gets information that a person was 18, but that information is out of date, I can drop that write, and I can do so by examining the cache and viewing stale information, only checking the real value if the cache value is < 18.
This whole thing lets you push computation to the edge, drop expensive writes, ignore any cache invalidation logic, cache values forever, potentially answer queries from stale cache values, etc.
Anyway, kudos for the writeup. I skimmed the second half but the first half was great and the second half looked legit.
- hmottestad 3y agoI really like this somewhat old video by Microsoft https://www.youtube.com/watch?v=oyUHd894w18 https://www.youtube.com/watch?v=oyUHd894w18 it was my first intro to CRDTs.
- whalesalad 3y agoI realize this is a straw man argument/example - but it feels hairy to me. So much fuss about age and cache invalidation ... age should not be persisted anywhere. When you make age a calculated property from birthday it is never inaccurate or stale or wrong. "set age" should not be a possible operation in any system imho.
- insanitybit 3y agoEven if you persist a timestamp like 'birth date' into a database it doesn't matter - you can still cache the resulting 'age' calculations as CRDTs. But yes, it is a made up example. Another might be 'first/last observed time' for an IP address.
- rahkiin 3y agoFor GDPR it is better to store ‘is legal drinking age’ instead of age or forbid even the birthdate
- neilellis 3y agoUntil the legal drinking age changes :-)
- actionfromafar 3y agoThat’s why you need the SAAS, for compliance and i18n!
- rahkiin 3y agoIdeally you only verify at time of purchase and do not care afterwards until next purchase. Bare minimum to hold to laws
- jcrites 3y agoIdeally you also don't need to verify it more than once, though. Otherwise, it will be friction that detracts from the user experience.
- yard2010 3y agoFun fact: in some places in Canada the legal drinking age is 19
- 3y ago
- alephnan 3y ago> text editing as the de-facto solution is so weird to me since that problem is both niche and extremely complex. My first foray into collaborative editing was for my text editor. Indeed, things get super linearly harder as you add basic functionality of editors such as deleting and replacing, especially when those space multiple lines. Instead, I reached for Fraser’s differential syncing. https://neil.fraser.name/writing/sync/ https://neil.fraser.name/writing/sync/. There’s a lot of ambiguity and nuances in various versions of the prose and white paper that I could never really flesh out. I think anyone attempting to relay a collaborative editing algorithm needs to do is start with the simplest scenarios: append only / monotonically increasing data.
- steve_adams_86 3y agoThe way you describe that makes me wonder if state machines would be natural tools to express CRDT “states”.
- insanitybit 3y agoThe important this is that, as mentioned in the article, you need to have a way to converge states in a way that obeys certain properties.
- steve_adams_86 3y agoYeah, as I’m reading this more thoroughly I see that there wouldn’t be many states to express, and the merging itself isn’t something you’d express in states. I initially thought more of the inner workings could be managed this way, but it seems better implemented as it is in the article.
- insanitybit 3y agoYou should check out the P language and consider the implications of CRDTs on the `machine` constructs :)
- steve_adams_86 3y agoThis turned out to be super interesting. Thanks!
- richardwhiuk 3y agoSomebody typos there age to be too high, and then you cache it forever. You have to be careful here.
- insanitybit 3y agoOf course. All things require care. Not all problems fit into CRDTs either.
- LtdJorge 3y agoAnd of course you typoed there instead of their :D
- kevincox 3y ago> the fact that we always use text editing as the de-facto solution is so weird to me since that problem is both niche and extremely complex The reason we use that is because it is complex enough to show the problems that CRDTs solve. I would argue that this painting example is too simple. The core merge loop is: if pixel.created_at < newPixel.created_at { pixel = newPixel; } this is maybe good as a first step, but I don't think it is enough to even really called an "Intro". A last-write-wins register is trivial. Simple text inserts with a simple "insert after" CRDTs is not much more complicated but involves things like generated unique IDs without communication and how to resolve conflicts with some sort of globally consistent ordering.
- jakelazaroff 3y agoI agree that it's simple, but that's exactly what makes it so powerful — it's easy to understand and yet you can do a ton with it. I've been working on a vector editor as well that's also built with just registers and maps. That one is a bit long for a blog post (although I might do a high level overview of some techniques like fractional indexing). But the point I'm trying to drive at here is that you can get really far just by combining simple CRDTs.
- insanitybit 3y agoI think the problem is that CRDTs don't solve the text editing problem as far as I know. They can solve a constrained version of it and they have to be sorta mixed up with other algorithms and approaches. It's like a worst case scenario for distributed systems that requires tons of complex solutions. It's something to build up to maybe, not to start with.
- cabalamat 3y ago> Age moves in one direction so it has a simple merge function: Better to use date of birth as that doesn't change at all.
- angry_octet 3y agoIt can though. Some people have different DOB on different identity documents.
- matheusmoreira 3y agoI regularly deal with people older than the my country's identity documents. Their "official" dates of birth are frequently off by several years and have to be manually corrected in all databases and systems.
- Racing0461 3y agoWhat if i set the wrong dob and i need to change it?