5 ms·

Huh, this is a really nice writeup of the logical time part of the foundations of distributed systems lecture I used to assist in. I always wondered how much th

by ketzu 4y ago

Huh, this is a really nice writeup of the logical time part of the foundations of distributed systems lecture I used to assist in. I always wondered how much they are actually used in real systems.

dboreham 4y ago
I haven't seen basic Lamport Clocks used much but sequence numbers and various kinds of vector clock are widely used in eventually consistent systems (fashionable to call this CRDT nowadays). Edit: perhaps git uses a kind of lamport clock, but with linked lists of hashes not numbers as the values.
- thoughtlede 4y ago
  Right. The flavors of Lamport clocks I stated in the article are used in CRDTs designs I studied. While CRDTs are eventually consistent, I wouldn't dismiss them as such without qualification. They are causal-consistent when offline and sequential-consistent when online. (This duality is why CRDTs have been hard for me to wrap my head around them).
  - preseinger 4y ago
    the properties of CRDTs are invariant to the concept of "online" or "offline" i think you may be making things harder for yourself by thinking in these terms
    - thoughtlede 4y ago
      Indeed, certain properties of CRDT are invariable to network state. However, it is worth pointing out that in ops-based CRDT “implementations”, you deal with local ops case differently from remote ops case. That is, while the properties are invariant, how you produce them are different. So I was on a my quest to understand the “essence” of CRDTs, not just understand them to be able to practically use them. Atomic broadcast and Raft were easy enough for me to wrap my head around (although quite challenging to implement). But not CRDTs. I found common statements about CRDTs that they ensure ops to be commutative to be superficial. A slightly deeper characteristic was that ops-based CRDTs are just causally-linked ops (aka causal tree). But what about state-based? Finally, when I realized CRDTs are dual-consistent and that’s what makes any data structure a CRDT, that was a moment of epiphany for me.
      - preseinger 4y ago
        so an important "eureka" observation about CRDTs is that the op-based model is theoretical, useful for proofs insofar as any op-based CRDT can be translated to a state-based CRDT, but not something that can actually exist in practice all practical CRDTs are state-based CRDTs that's because it's not possible to assert a causal order for arbitrary operations on arbitrary data structures (in useful contexts) CRDTs don't _ensure_ ops are commutative (and associative, and idempotent) but rather they _require_ that ops are commutative (and associative, and idempotent) and it's definitely not the case that any data structure is a CRDT, it's possible to translate many data structures to CRDTs, but that translation rarely preserves the operations in full fidelity
        thoughtlede 4y ago
        > CRDTs don't _ensure_ ops are commutative (and associative, and idempotent) but rather they _require_ that ops are commutative (and associative, and idempotent) I disagree. You can create a CRDT flavor of data structure whose ops are not commutative. For example, a Set's add and delete operations. These are not commutative. You cannot switch the order of the ops for meaningfully processing them. However, you can create a CRDT Set. You do that by adding metadata to the ops, and having the instances always process them in the only order that makes sense even if such instances receive the ops in a different order. In that sense, you are "ensuring" ops are behaving like they are commutative and not "requiring" them to be so. > it's definitely not the case that any data structure is a CRDT I could have worded my statement better. I meant any data structure that has the aforementioned duality property is a CRDT. Not that any data structure unconditionally can be translated into a CRDT. > an important "eureka" observation about CRDTs is that the op-based model is theoretical, I do not understand your statement. Perhaps you could elaborate. My understanding is that a CRDT is op-based or state-based depending on what is "communicated" between the instances. If ops are communicated, then it is op-based CRDT, whereas if states (or delta-states) are communicated, then it is state-based. At least in that sense, op-based model is NOT theoretical. Perhaps you have a different point in mind that I fail to observe.
        preseinger 4y ago
- HyperSane 4y ago
  An update sequence number (USN) is a 64-bit number in Active Directory that increases as changes occur. Local counters on every domain controller assign USNs. Whenever an object is changed, its USN is incremented. When replication occurs, only the version of the object with the greatest USN is retained. Local counters for USNs are considered reliable because they never decrease or "run backward." USNs are also always unique, making it easier for domain controllers to never use the same USNS at the same time.
  - preseinger 4y ago
    this approach does not provide any reasonable level of consistency https://news.ycombinator.com/item?id=35405055 https://news.ycombinator.com/item?id=35405055 copy/pasting text from a basic google search is pretty weak https://i.imgur.com/lkH9hp0.png https://i.imgur.com/lkH9hp0.png

by ketzu 4y ago

Huh, this is a really nice writeup of the logical time part of the foundations of distributed systems lecture I used to assist in. I always wondered how much they are actually used in real systems.

dboreham 4y ago

I haven't seen basic Lamport Clocks used much but sequence numbers and various kinds of vector clock are widely used in eventually consistent systems (fashionable to call this CRDT nowadays). Edit: perhaps git uses a kind of lamport clock, but with linked lists of hashes not numbers as the values.

thoughtlede 4y ago
Right. The flavors of Lamport clocks I stated in the article are used in CRDTs designs I studied. While CRDTs are eventually consistent, I wouldn't dismiss them as such without qualification. They are causal-consistent when offline and sequential-consistent when online. (This duality is why CRDTs have been hard for me to wrap my head around them).
- preseinger 4y ago
  the properties of CRDTs are invariant to the concept of "online" or "offline" i think you may be making things harder for yourself by thinking in these terms
  - thoughtlede 4y ago
    Indeed, certain properties of CRDT are invariable to network state. However, it is worth pointing out that in ops-based CRDT “implementations”, you deal with local ops case differently from remote ops case. That is, while the properties are invariant, how you produce them are different. So I was on a my quest to understand the “essence” of CRDTs, not just understand them to be able to practically use them. Atomic broadcast and Raft were easy enough for me to wrap my head around (although quite challenging to implement). But not CRDTs. I found common statements about CRDTs that they ensure ops to be commutative to be superficial. A slightly deeper characteristic was that ops-based CRDTs are just causally-linked ops (aka causal tree). But what about state-based? Finally, when I realized CRDTs are dual-consistent and that’s what makes any data structure a CRDT, that was a moment of epiphany for me.
    - preseinger 4y ago
      so an important "eureka" observation about CRDTs is that the op-based model is theoretical, useful for proofs insofar as any op-based CRDT can be translated to a state-based CRDT, but not something that can actually exist in practice all practical CRDTs are state-based CRDTs that's because it's not possible to assert a causal order for arbitrary operations on arbitrary data structures (in useful contexts) CRDTs don't _ensure_ ops are commutative (and associative, and idempotent) but rather they _require_ that ops are commutative (and associative, and idempotent) and it's definitely not the case that any data structure is a CRDT, it's possible to translate many data structures to CRDTs, but that translation rarely preserves the operations in full fidelity
      - thoughtlede 4y ago
        > CRDTs don't _ensure_ ops are commutative (and associative, and idempotent) but rather they _require_ that ops are commutative (and associative, and idempotent) I disagree. You can create a CRDT flavor of data structure whose ops are not commutative. For example, a Set's add and delete operations. These are not commutative. You cannot switch the order of the ops for meaningfully processing them. However, you can create a CRDT Set. You do that by adding metadata to the ops, and having the instances always process them in the only order that makes sense even if such instances receive the ops in a different order. In that sense, you are "ensuring" ops are behaving like they are commutative and not "requiring" them to be so. > it's definitely not the case that any data structure is a CRDT I could have worded my statement better. I meant any data structure that has the aforementioned duality property is a CRDT. Not that any data structure unconditionally can be translated into a CRDT. > an important "eureka" observation about CRDTs is that the op-based model is theoretical, I do not understand your statement. Perhaps you could elaborate. My understanding is that a CRDT is op-based or state-based depending on what is "communicated" between the instances. If ops are communicated, then it is op-based CRDT, whereas if states (or delta-states) are communicated, then it is state-based. At least in that sense, op-based model is NOT theoretical. Perhaps you have a different point in mind that I fail to observe.
        preseinger 4y ago
HyperSane 4y ago
An update sequence number (USN) is a 64-bit number in Active Directory that increases as changes occur. Local counters on every domain controller assign USNs. Whenever an object is changed, its USN is incremented. When replication occurs, only the version of the object with the greatest USN is retained. Local counters for USNs are considered reliable because they never decrease or "run backward." USNs are also always unique, making it easier for domain controllers to never use the same USNS at the same time.
- preseinger 4y ago
  this approach does not provide any reasonable level of consistency https://news.ycombinator.com/item?id=35405055 https://news.ycombinator.com/item?id=35405055 copy/pasting text from a basic google search is pretty weak https://i.imgur.com/lkH9hp0.png https://i.imgur.com/lkH9hp0.png