8 ms·

A Gentle Introduction to CRDTs

278 points by tantaman 4y ago

deleted 4y ago
[deleted]
sunk1st 4y ago
When you bump your clock forward do you also bump your time stamp forward by the same amount?
- tectec 4y ago
  I think you use the clock instead of the timestamp. You could keep the timestamp for business purposes but that would be the same as without CRDT
- LAC-Tech 4y ago
  No. It's kind of a mindset shift, but with logical clocks you kind have to let go of the concept of ordering with one global universal time - it's just not feasible to do accurately with clock skew. They're purely used to provide a partial order of events - partial because the system cannot say for sure whether some events happened before or after each other.
  - convolvatron 4y ago
    you can also just assume that it is a total ordering, and ignore the entire notion of a canonical non-relativistic clock which would find you out
  - CGamesPlay 4y ago
    > ordering with one global universal time - it's just not feasible to do accurately with clock skew. Even more fundamentally, it’s not possible because of physics. The passage of time is relative! Not as important for terrestrial applications, but useful to consider as a theoretical limitation.
    - LAC-Tech 4y ago
      Even with terrestrial applications that have very low clock skew, it can be very helpful to have a notion of which events could be effected by previous events and which couldn't have. But you're bang on the money with the physics analogy. Lamport himself says that his knowledge of special relativity helped him come up with the concept. https://www.youtube.com/watch?v=nfRouGH0oMg https://www.youtube.com/watch?v=nfRouGH0oMg
    - bmacho 4y ago
      I believe that a global time is possible, indeed, because of physics, causality and information paradoxes. I don't have a proof for it, just a hunch.
      - bmacho 4y ago
        What about: you place a clock somewhere in the universe that emits its value with light, then you define time for a given event as this vale? This seems to be defined, and having the property that if t(B) >= t(A) then B can't happen before A, and conversely, if AB is timelike, then T(B) > t(A). This seems to be such a nice construction, but I don't know its name.
        withinboredom 4y ago
        If it is emitting its value by light, as you move away or closer to it, it's value will shift up/down (red/blue shift), and it's rate of 'ticking' will change up/down. You can't prove that something far away happened in the past or the future using your construction.
        bmacho 4y ago
        It's value won't shift down. Yes, you don't measure it with a wristwatch, but you measure it with a device that receives the value on the clock, and display it. Just like any other physical measures. You don't measure nearly any of them with a wristwatch (only proper time/aging) but with a device that is constructed according to the definition of that physical measure.
- moremetadata 4y ago
  [dead]
- plq 4y ago
  Think of it this way: If we say that we perceive the world in 3D space and 1D time (x,y,z,t), the t dimension is special: You can't change x,y,z if you don't advance t. Inversely, if x,y,z is constant, t doesn't need to advance. That's why it's enough for the logical clocks to count the number of committed transactions. This said, in a truly decentralized setting, where CRDTs make most sense, logical clocks are not useful as they are not not byzantine fault tolerant. You need merkle trees.
  - preseinger 4y ago
    decentralized != untrusted byzantine fault tolerance is fun and all but it's a niche use case
    - plq 4y ago
      > decentralized != untrusted You can only trust the nodes that you control. That's not what I'd call a decentralized system.
      - preseinger 4y ago
        you don't need to control a node to trust it, like tcp isn't byzantine fault tolerant and yet here we are
  - kaoD 4y ago
    Not sure if understand what you mean. If we see every field as f(x,y,z,t) what do you mean you can't "change" x,y,z without changing t? If you mean changing the x,y,z argument values, you can (you're just evaluating a different point in space). If you mean changing the evaluated function value at a given x,y,z it's kinda tautological that it stays constant for a constant x,y,z,t.
    - plq 4y ago
      I'll try to explain with an example: If you have an object at position (x1,y1,z1), at some time t1, and you want to move this object to a different position so that at time t2, it's at position (x2,y2,z2), you must have t2>t1. If t2==t1 then (x1,y1,z1)==(x2,y2,z2). So when time stops, everything else stops. It is tautological when you think about it, but I find that it's an easy way to explain why logical clocks work. Am I wrong to reason this way?
turnsout 4y ago
The linked projects (https://vlcn.io https://vlcn.io and https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite) are both extremely impressive, and open up the possibility of adding "multiplayer" to apps that rely on SQLite for local storage—including web apps, via a WASM build of SQLite.
- hummus_bae 4y ago
  Could you elaborate? What problem would using CRDTs solve in the context of a web-based app, especially one built with WASM? I've heard of offline-first web apps but am not aware of much use cases for CRDTs there.
  - AlexErrant 4y ago
    I'm using cr-sqlite right now in my Anki clone: https://github.com/AlexErrant/Pentive https://github.com/AlexErrant/Pentive It's basically an offline-first flashcard webapp. CR-Sqlite allows for incremental syncing. With Anki (the app from which I'm taking my inspiration), syncing is _not_ incremental - basically it just copies SQLite files around. So for example, the app could be on an iPhone with cards a card `A` reviewed, but the app on an iPad could make changes to the template on which card `A` is based, and that's enough to cause a conflict - you must take changes from only the iPad or only the iPhone. (To be clear - Anki does have some incremental syncing capabilities - I'm picking an intentionally pathological example.) CR-SQLite will mean that everything is incremental, however. Basically makes 3 way merges a breeze (or n-way merges, really).
- brunoqc 4y ago
  That could be nice with D1.
  - 5Qn8mNbc2FNCiVV 4y ago
    D1 is eventually consistent so better not use it with that. I'd rather use Durable Objects
VirusNewbie 4y ago
How do you handle gc of deletes?
- tantaman 4y ago
  In a client-server sync setup you can drop a client's deletes (for certain crdts like observed-remove sets) once they send their changes to the server. The server, of course, needs to retain them. Other GC research unrelated to this project but something I've been following: https://braid.org/antimatter https://braid.org/antimatter
rvbissell 4y ago
What a gorgeous webpage -- and it even renders well with SingleFile!
- deleted 4y ago
  [deleted]
- jiehong 4y ago
  On mobile, not so much…
  - tantaman 4y ago
    :( I'll try to get to that.
- alpaca128 4y ago
  At my current window size the table of contents on the side overlaps with the text. Otherwise really nice and readable, I agree. I especially like the font.
quantum_state 4y ago
wonder if there is an estimate to quantify what “eventual” means as a function of the variables of a peer ecosystem … e.g., the number of nodes, the frequency of updates, etc. …
- tantaman 4y ago
  It'd depend on the network topology and rate of syncing. For a simple case of two nodes, they'll be divergent until each node sends the other their current state. For client-server, the "whole system" wouldn't be in the same state until all clients report all their changes to the server and the server re-broadcasts all those changes to all clients. A pathological case (but happens when people leave an ipad in a drawer or something) -- a node could be offline for 6 months and the rest of the system never gets those changes until that node comes back online. There's technically some divergence: the other nodes are missing whatever state the ipad had, but does it really matter if that node was unimportant enough to be left offline? Depends on use case for sure.
foruhar 4y ago
Very cool. CRDTs seem to be in the air. I was searching for something unrelated and bumped into https://mycelial.com/ https://mycelial.com/ which is also doing CRDTs with sqlite. Very helpful intro to CRDTs video on their youtube channel.
- call-me-al 4y ago
  I guess this is the mentioned video: https://www.youtube.com/watch?v=gZP2VUmH05A https://www.youtube.com/watch?v=gZP2VUmH05A
mixmastamyk 4y ago
Interesting that is uses sqlite as a file format as an example for rich documents. Probably would work reasonably well, but hadn't thought to do that until now. Have tables for pages and items on the page? Would that make document search more robust? Wonder if/how it would combine with the distributed litestream stuff recently touted on fly.io? I love postgres but have to admit these features are tempting.

278 points by tantaman 4y ago

deleted 4y ago

[deleted]

sunk1st 4y ago

When you bump your clock forward do you also bump your time stamp forward by the same amount?

tectec 4y ago
I think you use the clock instead of the timestamp. You could keep the timestamp for business purposes but that would be the same as without CRDT
LAC-Tech 4y ago
No. It's kind of a mindset shift, but with logical clocks you kind have to let go of the concept of ordering with one global universal time - it's just not feasible to do accurately with clock skew. They're purely used to provide a partial order of events - partial because the system cannot say for sure whether some events happened before or after each other.
- convolvatron 4y ago
  you can also just assume that it is a total ordering, and ignore the entire notion of a canonical non-relativistic clock which would find you out
- CGamesPlay 4y ago
  > ordering with one global universal time - it's just not feasible to do accurately with clock skew. Even more fundamentally, it’s not possible because of physics. The passage of time is relative! Not as important for terrestrial applications, but useful to consider as a theoretical limitation.
  - LAC-Tech 4y ago
    Even with terrestrial applications that have very low clock skew, it can be very helpful to have a notion of which events could be effected by previous events and which couldn't have. But you're bang on the money with the physics analogy. Lamport himself says that his knowledge of special relativity helped him come up with the concept. https://www.youtube.com/watch?v=nfRouGH0oMg https://www.youtube.com/watch?v=nfRouGH0oMg
  - bmacho 4y ago
    I believe that a global time is possible, indeed, because of physics, causality and information paradoxes. I don't have a proof for it, just a hunch.
    - bmacho 4y ago
      What about: you place a clock somewhere in the universe that emits its value with light, then you define time for a given event as this vale? This seems to be defined, and having the property that if t(B) >= t(A) then B can't happen before A, and conversely, if AB is timelike, then T(B) > t(A). This seems to be such a nice construction, but I don't know its name.
      - withinboredom 4y ago
        If it is emitting its value by light, as you move away or closer to it, it's value will shift up/down (red/blue shift), and it's rate of 'ticking' will change up/down. You can't prove that something far away happened in the past or the future using your construction.
        bmacho 4y ago
        It's value won't shift down. Yes, you don't measure it with a wristwatch, but you measure it with a device that receives the value on the clock, and display it. Just like any other physical measures. You don't measure nearly any of them with a wristwatch (only proper time/aging) but with a device that is constructed according to the definition of that physical measure.
moremetadata 4y ago
[dead]
plq 4y ago
Think of it this way: If we say that we perceive the world in 3D space and 1D time (x,y,z,t), the t dimension is special: You can't change x,y,z if you don't advance t. Inversely, if x,y,z is constant, t doesn't need to advance. That's why it's enough for the logical clocks to count the number of committed transactions. This said, in a truly decentralized setting, where CRDTs make most sense, logical clocks are not useful as they are not not byzantine fault tolerant. You need merkle trees.
- preseinger 4y ago
  decentralized != untrusted byzantine fault tolerance is fun and all but it's a niche use case
  - plq 4y ago
    > decentralized != untrusted You can only trust the nodes that you control. That's not what I'd call a decentralized system.
    - preseinger 4y ago
      you don't need to control a node to trust it, like tcp isn't byzantine fault tolerant and yet here we are
- kaoD 4y ago
  Not sure if understand what you mean. If we see every field as f(x,y,z,t) what do you mean you can't "change" x,y,z without changing t? If you mean changing the x,y,z argument values, you can (you're just evaluating a different point in space). If you mean changing the evaluated function value at a given x,y,z it's kinda tautological that it stays constant for a constant x,y,z,t.
  - plq 4y ago
    I'll try to explain with an example: If you have an object at position (x1,y1,z1), at some time t1, and you want to move this object to a different position so that at time t2, it's at position (x2,y2,z2), you must have t2>t1. If t2==t1 then (x1,y1,z1)==(x2,y2,z2). So when time stops, everything else stops. It is tautological when you think about it, but I find that it's an easy way to explain why logical clocks work. Am I wrong to reason this way?

turnsout 4y ago

The linked projects (https://vlcn.io https://vlcn.io and https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite) are both extremely impressive, and open up the possibility of adding "multiplayer" to apps that rely on SQLite for local storage—including web apps, via a WASM build of SQLite.

hummus_bae 4y ago
Could you elaborate? What problem would using CRDTs solve in the context of a web-based app, especially one built with WASM? I've heard of offline-first web apps but am not aware of much use cases for CRDTs there.
- AlexErrant 4y ago
  I'm using cr-sqlite right now in my Anki clone: https://github.com/AlexErrant/Pentive https://github.com/AlexErrant/Pentive It's basically an offline-first flashcard webapp. CR-Sqlite allows for incremental syncing. With Anki (the app from which I'm taking my inspiration), syncing is _not_ incremental - basically it just copies SQLite files around. So for example, the app could be on an iPhone with cards a card `A` reviewed, but the app on an iPad could make changes to the template on which card `A` is based, and that's enough to cause a conflict - you must take changes from only the iPad or only the iPhone. (To be clear - Anki does have some incremental syncing capabilities - I'm picking an intentionally pathological example.) CR-SQLite will mean that everything is incremental, however. Basically makes 3 way merges a breeze (or n-way merges, really).
brunoqc 4y ago
That could be nice with D1.
- 5Qn8mNbc2FNCiVV 4y ago
  D1 is eventually consistent so better not use it with that. I'd rather use Durable Objects

VirusNewbie 4y ago

How do you handle gc of deletes?

tantaman 4y ago
In a client-server sync setup you can drop a client's deletes (for certain crdts like observed-remove sets) once they send their changes to the server. The server, of course, needs to retain them. Other GC research unrelated to this project but something I've been following: https://braid.org/antimatter https://braid.org/antimatter

rvbissell 4y ago

What a gorgeous webpage -- and it even renders well with SingleFile!

deleted 4y ago
[deleted]
jiehong 4y ago
On mobile, not so much…
- tantaman 4y ago
  :( I'll try to get to that.
alpaca128 4y ago
At my current window size the table of contents on the side overlaps with the text. Otherwise really nice and readable, I agree. I especially like the font.

quantum_state 4y ago

wonder if there is an estimate to quantify what “eventual” means as a function of the variables of a peer ecosystem … e.g., the number of nodes, the frequency of updates, etc. …

tantaman 4y ago
It'd depend on the network topology and rate of syncing. For a simple case of two nodes, they'll be divergent until each node sends the other their current state. For client-server, the "whole system" wouldn't be in the same state until all clients report all their changes to the server and the server re-broadcasts all those changes to all clients. A pathological case (but happens when people leave an ipad in a drawer or something) -- a node could be offline for 6 months and the rest of the system never gets those changes until that node comes back online. There's technically some divergence: the other nodes are missing whatever state the ipad had, but does it really matter if that node was unimportant enough to be left offline? Depends on use case for sure.

foruhar 4y ago

Very cool. CRDTs seem to be in the air. I was searching for something unrelated and bumped into https://mycelial.com/ https://mycelial.com/ which is also doing CRDTs with sqlite. Very helpful intro to CRDTs video on their youtube channel.

call-me-al 4y ago
I guess this is the mentioned video: https://www.youtube.com/watch?v=gZP2VUmH05A https://www.youtube.com/watch?v=gZP2VUmH05A

mixmastamyk 4y ago

Interesting that is uses sqlite as a file format as an example for rich documents. Probably would work reasonably well, but hadn't thought to do that until now. Have tables for pages and items on the page? Would that make document search more robust? Wonder if/how it would combine with the distributed litestream stuff recently touted on fly.io? I love postgres but have to admit these features are tempting.