[HN Gopher] Clocks and Causality - Ordering Events in Distribute...
___________________________________________________________________
Clocks and Causality - Ordering Events in Distributed Systems
(2022)
Author : alexzeitler
Score : 281 points
Date : 2023-04-01 12:11 UTC (10 hours ago)
(HTM) web link (www.exhypothesi.com)
(TXT) w3m dump (www.exhypothesi.com)
| vrglvrglvrgl wrote:
| [dead]
| imoe wrote:
| [flagged]
| noiv wrote:
| Given Einstein proved time is relative and not absolute I wonder
| at what time resolution all attempts to assume time as an
| absolute fall apart? The maximum distance of two surface nodes on
| this planet is about 20_000 km translating to about 67 milli
| seconds as speed of information.
|
| All discussion here assumes 17th century Newton's physics.
| hinkley wrote:
| Much of the rule of law is based on cause and effect. Most of
| the people who get hung up on time stamps are trying to
| reconstruct a chain of events over time. And like a lot of
| concurrency problems, the solution seems to be to solve a
| different problem instead. Such as causal chaining.
|
| We made an error here because we were aware of three facts but
| not aware of a fourth. The answer is wrong but the data is
| consistent. That's important for finding bugs. It's also
| important for establishing intent.
|
| If I bonk you with a bat, it might be an accident. If I had
| just found out you've been sleeping with my wife, people should
| be asking a lot more questions. If I don't know that, then
| there's no causal link between these events.
| noiv wrote:
| > Such as causal chaining.
|
| Doesn't that imply knowing which of two events happened
| first? Imagine, after your bat accident I took liberties with
| your wife as a revenge?
|
| Please pardon my 17th century's line of thought :)
| hinkley wrote:
| Which happened first can be in the eye of a third party
| observer versus a first party. it doesn't matter which
| happened first, it matters what the observers saw and
| whether they can agree. The relativistic example here says
| that observers will never agree.
|
| If an event that I didn't observe happened first, it didn't
| influence my decisions. It might influence yours though,
| but when things get grey we give benefit of the doubt.
| Rhapso wrote:
| It really depends on how fast both of you are going
| relatively to each other and who is asking the questions
| (and how fast they are going...)
| threatofrain wrote:
| If I communicate with you then that's enough to determine
| data causality, which is a weaker version of scientific
| causality. That does not mean that you necessarily shall do
| something as a result of my communication, so we shouldn't be
| talking in terms of you bonking someone with a bat as a
| result of receiving a communication.
|
| In scientific causality, A shall cause B to the degree to
| which A is explanatory for B.
| NHQ wrote:
| Time is not real, it is a measurement. Space is real.
| Einstein's times is a quantum model of change over space, but
| really only proves that where you stand is relative to where I
| stand, and our relativity changes if we move through space.
|
| As I have just proven, Einstein's relativity is really a
| confabulation of what is obvious, resulting in people getting
| lost in that model universe. It is only useful for taking
| measurements within that model, everything else is worshiping
| light, the speed of.
| noiv wrote:
| If time isn't real, but space is - how real is spacetime?
| NHQ wrote:
| Spacetime is a colloquial term for a derivative calculation
| or projection which only applies within the model. It has
| also not proven very germane as a unit, or it would be used
| more like a unit, rather than as description of a picture.
| The term seems to relate to the rendering of space in the
| model via geometry, where the model is based on
| singularities, which are the antithesis of space, and so is
| the model. We experience space, but we only find
| singularities from within a model.
|
| That we pretend the relative speed of light is constant,
| and this proves black holes and big bangs, that is pseudo
| science taking a model beyond it's working boundaries,
| where it's calculation have no meaning; to wit, this is a
| physical analogue in optical aberration, where the rim of
| the lens is asymptotic refraction to the point of
| unreliable measurement (not a singularity, unless of course
| you model it as such, in the abstract).
|
| The real question is why so much energy is used staring at
| model aberration. The "Uncertainty paradox" has everyone
| believe the model is real, and even ask the question "at
| what point does the model become real". The model is never
| real, and never becomes real, it stays a model forever.
| Whether the cat is dead or not is simply a measurement
| where, if you mistake the paradox for theory, you don't
| realize the probability of dead or alive given decay is
| nothing more than a measurement taken ex post facto, and
| not proof that the real world accord to the model.
| LegionMammal978 wrote:
| > Time is not real, it is a measurement. Space is real.
|
| In what particular way is space real that time is not?
|
| > Einstein's times is a quantum model of change over space,
| but really only proves that where you stand is relative to
| where I stand, and our relativity changes if we move through
| space.
|
| I think you might have misinterpreted the vocabulary: in the
| "principle of relativity", the word "relativity" refers to
| the relation between two coordinate systems, not the relation
| between two points in space.
|
| > As I have just proven, Einstein's relativity is really a
| confabulation of what is obvious, resulting in people getting
| lost in that model universe.
|
| All you have done is made assertions, without evidence or
| reasoning. You can certainly do that, but how is it supposed
| to prove anything? What is the argument?
| NHQ wrote:
| 1: The clock is real, the minute is abstract. The real and
| abstract are the essence of mathematical relativity, which
| is how we derive "irrational constants" like the relative
| measurement of one thing (radius) to another
| (circumference) making a ratio (PI). PI can never truly be
| defined, because it's not real: it can only be measured
| more or less accurately. This alone should disprove
| singularities, but instead we mistake abstract precision as
| proof of infinity. If time and the clock were both same
| with regard to being real, there would be nothing to
| measure, or no reason to measure: time would be the clock.
| But we know a clock tells time, which is a measurement:
| days into hours into minutes into seconds. If a day is
| time, and so is an hour, time is no more real than PI,
| which describes all radii to arbitrary precision.
|
| 2: More than one point in space makes a coordinate system,
| and more than one point is a prerequisite of relativity.
| Plus, within the questionable physics models which allow
| for singularities, the notional difference between a
| coordinate system and a point is conspicuously broken in
| order to explain other things. But that's how we get vague
| terms like spacetime, descriptions for weird parts of the
| model.
|
| 3: I did prove it, and you can reproduce it yourself by
| going to the nearest mountain range and yodel. In other
| words, I don't need math proofs from within abstruse models
| to prove my point, so my argument is more sound
| scientifically. I proved "relativity" is nothing more than
| understanding the difference in change over space, a
| confabulation which has yielded fiction in place of real
| science at a university near you. You are lost in the
| measurement of the duration of time to go from one space to
| another, and the paradoxes that happen when you go to
| infinity.
|
| Time measures change over space, a thing you witness
| firsthand when your yodel returns in echo from the
| mountain. If space did not change from point A to point B,
| there would be no distance, no coordinate system, and our
| yodel would not echo from anywhere. Without change over
| space there is no time, so that tells you which one is
| primary. The measurement of the echo, taken in time units,
| aka intervals, gives useful information. It does not
| however indicate anything of some model's out-of-bounds
| parameters, like what if the mountain had infinite gravity?
|
| The measure of an echo could not prove a black hole, even
| by the very definition of a black hole, for an echo would
| not return (infinite inches of time til return). Ergo no
| measurement can prove a black hole. Only a model taken to
| mathematical infinity "proves" a black hole, and that is
| not real science, it's just math. Math proofs and
| scientific falsity are not the same side of a single coin.
| The observation yields math, not the other way around, or
| else I could say look here in my notebook, it's a real
| black hole!
| hinkley wrote:
| I've been wondering off and on if the end game for borrow
| checkers is a language that can mode causality in data
| operations.
|
| This withdrawal was predicated on checking records A and B at
| point X in the timeline and approving it. Meanwhile auto
| withdrawal happened 20 ms later and that's why we let him
| overdraft.
| HyperSane wrote:
| Active Directory is the most wildly used multi-master distributed
| database in the world and it uses update sequence numbers.
|
| 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.
| [deleted]
| vlovich123 wrote:
| > However, because of clock drifts and/or assumptions around
| network time delays, timestamps from conventional clocks are not
| always mutually comparable, and therefore events cannot be
| reliably ordered using timestamps from conventional clocks.
|
| This isn't quite right. CockroachDB and Yuggabyte both use
| conventional clocks to reliably order events. Spanner uses GPS to
| do so (conventional time stamp but maybe not technically a
| conventional clock).
| ketzu wrote:
| Your post made me read this:
| https://www.cockroachlabs.com/blog/living-without-atomic-clo...
| on how spanner and cockroadDB do this. And the answes are
| surprisingly simple, but with consequences attached.
|
| * Spanner creates very tight bounds on the clock
| synchronization (through atomic clocks/GPS) and ... just waits
| out the length of the bound.
|
| * CockroachDB seems to do lamport-clocks-with-real-timestamps
| for linearizability (track the highest seen timestamp for
| causality chains). For preventing consistency violations with
| reads, they also track the bounds on the clock and potentially
| attempt to read again.
|
| So they approve of the overall message (of not just comparing
| conventional timestamps) but work around those using the
| uncertainty of the clocks they have available.
|
| My professor used to introduce logical clocks with "as we
| usually can't use atomic clocks on all nodes" because of that.
| photochemsyn wrote:
| That's an interesting link, it leads to a this 1991 Liskov
| paper, which might seem out-of-date, but apparently was very
| foundational to the whole concept. A little searching turned
| up this modern discussion of it:
|
| https://muratbuffalo.blogspot.com/2022/11/practical-uses-
| of-...
|
| Seems the bottom line is: "Since clock synchronization can
| fail occasionally, it is most desirable for algorithms to
| depend on synchronization for performance but not for
| correctness."
| jasonwatkinspdx wrote:
| FYI the general technique Cockroach is using is commonly
| called Hybrid Logical Clocks, though Cloudera call their very
| similar idea Virtual Time as I recall.
|
| Anyhow, here's a nice summary:
| http://muratbuffalo.blogspot.com/2014/07/hybrid-logical-
| cloc...
| preseinger wrote:
| https://www.cockroachlabs.com/blog/living-without-atomic-
| clo...
|
| > perfectly synchronized clocks are a holy grail of sorts for
| distributed systems research. They provide, in essence, a
| means to absolutely order events, regardless of which node an
| event originated at
|
| two events that occur on two physically discrete nodes at
| _exactly_ the same time have no well-defined order, even if
| their clocks are synchronized
|
| > before a node is allowed to report that a transaction has
| committed, it must wait 7ms. Because all clocks in the system
| are within 7ms of each other, waiting 7ms means that no
| subsequent transaction may commit at an earlier timestamp,
| even if the earlier transaction was committed on a node with
| a clock which was fast by the maximum 7ms. Pretty clever.
|
| so sending information between two antipodes on earth takes
| 66ms in one direction, 132ms round-trip, minimum. the speed
| of light dictates this lower limit
|
| if two transactions are made on those two nodes at exactly
| the same time, there is no objective order between the two.
| you can _choose_ an order, but only with knowledge of both
| transactions, and that information physically cannot traverse
| space-time in 7ms
|
| so it's really not clear to me how this works. as an
| optimization, sure -- maybe there is some optimistic
| concurrency control that will fail transactions that conflict
| in the way i've described?
| layer8 wrote:
| "Exactly the same time" isn't even physically well-defined,
| due to relativity.
| thfuran wrote:
| Well, we can make some pretty accurate guesses about the
| frame of reference if we know the nodes' geographic
| positions and ban airplanes.
| preseinger wrote:
| yes but those guesses have "smudge windows" which are
| functions of the physical distance between relevant nodes
|
| if you want to make assertions about order between events
| from a set of nodes, and you want to use per-node
| physical clocks to determine that order, then even if
| those clocks are perfectly synchronized, order can only
| be decided when the light-cones of all nodes intersect,
| which is the maximum distance between any two nodes times
| the speed of light
|
| 7ms works for up to 2098km, that's in the best case
| hansvm wrote:
| The "as we usually can't use atomic clocks on all nodes"
| constraint is more common than you might think. Even code as
| simple as
|
| ts = get_atomic_time_with_no_delay_because_this_node_has_an_a
| tomic_clock();
|
| do_stuff_with_time(ts);
|
| is really broken if you have to wait for garbage collection,
| wait for your process/thread/coroutine/... to be scheduled,
| wait for a nearly invisible pause as a cache line is
| refreshed, .... The time you're using the atomic timestamp is
| at some future moment, and if that delay matters for your
| algorithm you need to track your uncertainty just like
| Spanner/Cockroach do (you just get significant benefits
| because the uncertainty is low).
| kurthr wrote:
| If your get_atomic() isn't also capturing or resetting an
| internal hardware timer atomically it's kinda broken code
| anyway. It's important to remember that you're getting data
| from the firmware of an atomic clock (or GPS receiver) and
| that they will go to great lengths to compensate for
| latency variations so not doing it in the sampling code
| would be nuts (or just not using isochronous coms). Then
| the local clock/timer can be calibrated from the that and
| you can have near clock-cycle correct timing. Typically
| they only send out 1 pulse per second so anything finer
| than that is locally interpolated. We used 1ms internal
| intervals with an accuracy of ~1ppm.
|
| Last time I worked on something like this was 20 years ago,
| but it was a Pentium box. The clock firmware to converted a
| 5MHz sinewave output to 1Pps, but could also output a
| synthetic UTC through LAN in cases where there was no other
| connectivity. I guess I'm saying this is really specialized
| code for whatever hardware/OS you're using.
|
| (edit) Here's some documentation for a very similar box: ht
| tps://www.manualslib.com/manual/1281621/Symmetricom-5071a..
| ..
| jrockway wrote:
| The GPS clock is really used to provide long-term
| stability for the computer's internal oscillator, which
| provides fine short-term stability. Your calls to
| gettimeofday() are handled by the internal oscillator,
| not by asking the GPS unit directly. Additionally, NTP
| daemons are impressive in their ability to get the "right
| answer" on current internal oscillator frequency as
| affected by the entire system. With 86400 very accurate
| data samples per day, you can do a lot!
|
| In a distributed system, the absolute value of the time
| is important, since that's what your transaction
| timestamps are based on. There is a lot to do to ensure
| that your time offset from UTC ends up being correct;
| antenna cable length compensation, oscillator
| quantization compensation, etc. These are not strictly
| necessary for Spanner but can make microsecond-level
| differences which are quite noticeable.
|
| "The API directly exposes clock uncertainty, and the
| guarantees on Spanner's timestamps depend on the bounds
| that the implementation provides. If the uncertainty is
| large, Spanner slows down to wait out that uncertainty.
| Google's cluster-management software provides an
| implementation of the TrueTime API. This implementation
| keeps uncertainty small (generally less than 10ms) by
| using multiple modern clock references (GPS and atomic
| clocks)."
|
| Basically, there is some tradeoff between clock
| synchronization perfection and transaction processing
| speed that can be made. You can build dedicated hardware
| that's clocked by a GPSDO and provide an API to get
| hardware timestamps, and maybe process transactions a
| little faster. Your good old C++ program running on Linux
| with an internal oscillator adjusted by NTP with a GPS
| PPS input still beats communicating between datacenters
| to agree on event ordering, though. Light is slow!
| eternalban wrote:
| > In a distributed system, the absolute value of the time
| is important
|
| Only for a co-variant data cohort is total temporal order
| necessary for correctness. It doesn't need to be system
| wide. Distinct (data independent) process groups can be
| partially ordered.
|
| There really is no such thing as "now" outside of a
| shared frame (or intersecting frames) of observation.
| hansvm wrote:
| All I was pointing out is that worst-case latency on a
| throughput-optimized OS can be unbounded, and it's not
| totally unexpected to see 1ms+ delays between those two
| lines of code, even if the clock implementation is
| flawless. Even in a RTOS you have jitter from cache
| misses and whatnot, just to a lesser degree. Code
| sensitive to clocks not being correct is often sensitive
| no matter how small the deviance is, and smaller
| deviations simply make bugs less frequent. Treating that
| point-in-time estimate as anything other than an estimate
| from the recent past can lead to code that looks flawless
| but occasionally breaks.
| layer8 wrote:
| Strictly speaking, atomic clocks by themselves wouldn't fully
| solve the problem either, because they tick at slightly
| different rates in different locations, due to variations in
| the gravitational field.
| pookah wrote:
| When a system overheats the CPU can speed up and the clocks
| drift and if you're producing volumes of events you will get
| corruption. Wouldn't ever use a system clock... You can write a
| hybrid logical clock in about forty lines of code that can
| scale as much as these wildly expensive appliances that these
| big tech companies shill.
| lanstin wrote:
| This is why reading the original Lamport paper is useful. This
| distributed nature of things isn't due to bad clocks or
| software or anything. It is an irreducible part of the physics
| of our world, with relativity. Perfect clocks won't help with
| space like separations and different velocities or
| gravitational force. You have to build communication into it.
| The causality relationship is inherently a partial order.
| libraryofbabel wrote:
| This isn't really true: it's not got anything to do with
| relatively _specifically_ , it's just because of the finite
| and varying time for messages to travel between points in a
| distributed system. So it's about physics but not about
| relativistic physics. A Newtonian universe with finite speed
| of light would have the same phenomenon.
|
| That said, the _analogy_ with causality in relativity and
| light cones etc is useful, and it's no coincidence that
| Lamport wrote a book on general relativity before he turned
| to distributed systems.
| lanstin wrote:
| there is no sense of simultaneity that crosses coordinate
| systems. there are three relationships between events a and
| b. a is before b, b is before a, and neither. to get the
| total ordering, you have to arbitrary and non physically
| pick a or b.
|
| in that Newtonian universe, good enough clocks and time
| stamps could be used to break the tie. good enough clocks
| will never be enough in our universe, there is no canonical
| way to say of two events separated in a space like way is
| first. in a newtonian universe you can.
| magicalhippo wrote:
| > A Newtonian universe with finite speed of light would
| have the same phenomenon.
|
| Isn't the whole point of special relativity that a
| Newtonian universe with a finite speed of light isn't
| Newtonian?
| libraryofbabel wrote:
| No, a Newtonian universe with finite speed of light is
| consistent. People were able to do physics in that model
| for two centuries. Special relativity flows from the much
| stronger and more radical assumption that the speed of
| light is constant _in all frames of reference_ , which is
| what the Michelson-Morley experiment showed to be true in
| our universe.
| magicalhippo wrote:
| Right, I was implicitly assuming the universe should obey
| Maxwell's equations.
| crdrost wrote:
| Physics nut reporting for duty!
|
| What makes relativity special is that everybody agrees on
| the speed of light. So Alice is passing Bob at say 0.1%
| of _c_ , she detonates a big firecracker or other bright
| sudden event, the light from that event forms a big
| bubble that expands away from her in all directions at
| speed _c_.
|
| If you imagine that light is like sound, that it
| propagates through a medium called the lumineiferous
| ether, then maybe Bob is at rest relative to the
| luminiferous ether. If so, he thinks that the bubble is
| centered on a fixed point in space, and Alice is just a
| smidge closer to one of the sides of the bubble than she
| is to the other. Alice, on this account, sees the center
| of the bubble drifting "backwards" relative to her motion
| and agrees that she is closer to one edge than the other.
| If they were right next to each other when the light
| burst went off, Alice agrees that Bob is the true center
| of the light bubble.
|
| Special relativity says that there is no ether: Bob
| thinks that this expanding light bubble is indeed
| expanding from a fixed point and that Alice is closer to
| this side than that, and he's right... but Alice thinks
| that this bubble is expanding out uniformly with herself
| at the center, and she is also 100% right. According to
| her, Bob is closer to one side of the bubble than the
| other, and Alice is the true center.
|
| This has a bunch of consequences. The first one is that
| it makes the Zeno paradox into a real life thing. To
| outrun a light beam, you first have to accelerate to half
| the speed of the light beam, at which point if you look
| to see how fast it's going away from you, it is receding
| at speed _c_ still, so you accelerate again to half the
| speed of the light beam and it is still moving at speed
| _c_ away from you, and you can never catch up to it. Bob
| watching this must agree that Alice never catches up to
| the leading edge, even though he sees her dumping
| tremendous amounts of energy into her motion. So nobody
| can accelerate faster than the speed of light, it takes
| infinite energy to get there. (The converse of this has
| now become engineering reality, all of our particle
| accelerators dump huge amounts of energy into small
| particles and operate under the simplifying assumption
| that they all max out at speed _c_.)
|
| The Newtonian universe with finite speed of light is the
| first situation, the relativistic universe is the second.
| cleansingfire wrote:
| Original Lamport paper here
| https://lamport.azurewebsites.net/pubs/time-clocks.pdf
| lanstin wrote:
| thanks. this is a profoundly useful paper to help one being
| able to think about distributed systems.
| amelius wrote:
| I suppose you can always order events by the time it takes for
| light to (physically or hypothetically) travel to a central
| server plus the server's local time.
| diarrhea wrote:
| Network uncertainties like splits and delays will render that
| impossible.
| dikei wrote:
| It really depends on how you define "reliability".
|
| If a system never orders events wrong but will immediately
| stops processing events when enough number of nodes have their
| clocks out-of-synced, which is the case with all systems using
| conventional clocks, can it still be considered reliable?
| lanstin wrote:
| only if you have a good ops team on 24x7 pager duty
| withinboredom wrote:
| Things like this are interesting for a couple of reasons.
| Synchronizing clocks in the network and even attaching the
| current time to packets is supported with the correct hardware
| (PPS). This is extremely reliable (when ordering is important,
| not necessarily for keeping time).
|
| What makes solutions like this article interesting is that this
| is at the application level, while there are synchronization
| problems you can solve at the hardware level when you control the
| hardware. Since moving things to the cloud, it's as though we've
| forgotten about these technologies that have been around for over
| 20 years.
| [deleted]
| MPSimmons wrote:
| > However, because of clock drifts and/or assumptions around
| network time delays, timestamps from conventional clocks are not
| always mutually comparable, and therefore events cannot be
| reliably ordered using timestamps from conventional clocks.
|
| I don't think that this distributed logical clock solution isn't
| worth working on, but some combination of a low-stratum NTP
| server combined with PTP is good enough for most people, I would
| think, but cloud solutions are mixed.
|
| - Azure Time Sync uses PTP - https://learn.microsoft.com/en-
| us/azure/virtual-machines/lin... - AWS time sync uses NTP -
| https://aws.amazon.com/about-aws/whats-new/2017/11/introduci... -
| Google Cloud also uses NTP -
| https://developers.google.com/time/faq
| thoughtlede wrote:
| Author here. Pleasantly surprised to see the article here.
|
| Some context behind the article. I studied CRDTs for a few
| months, and noticed that different CRDT designs use logical
| clocks in different and clever ways. And I haven't seen anyone
| narrate all those ways of use in one article. My attempt with
| this article was to dredge up those flavors of logical clocks
| into one article and give them names for future reference.
|
| (To respond to a couple of other comments, I ignored atomic (and
| gps-based) clocks in this discussion, as indicated in my footnote
| 3).
| riemannzeta wrote:
| Curious to know whether, in your opinion, the use of verifiable
| delay functions and proof of history represents a more reliable
| and scalable approach to decentralized time-ordering.
|
| https://solana.com/news/proof-of-history---a-clock-for-block...
| lostcolony wrote:
| Can't speak for op, but can speak as just an observer -
| probably not. Blockchains are ultimately CP systems, not AP.
| From that link - "Data can be inserted into the sequence by
| appending the data to the previous generated state. The
| state, input data, and count are all published. Appending the
| input causes all future output to change unpredictably."
|
| Meaning there is a single source of truth. That single source
| is decentralized (because blockchain), but it still requires
| a quorum to agree to accept a bit of data, and to treat the
| new state as the valid state. I.e., multiple competing
| parallel writes must be serialized across a network of
| computers, which is always more expensive than if they
| multiple competing parallel writes can be done in parallel.
|
| Lamport clocks and etc are AP. It fully expects nodes to make
| decisions autonomously, and to synchronize after the fact.
| And data can be lost without realizing it.
|
| (The above is all a bit of a simplification, but
| fundamentally, they're solving different problems)
| thoughtlede wrote:
| Need more time to think this through. A few comments:
|
| 1. The problem space being solved in proof-of-history needs
| special mention. It assumes byzantine faults. (My article
| does not).
|
| 2. If I understood it correctly, the idea behind proof-of-
| history is that you perceive the flow of time in "windows".
| Each window is linked to the state of the previous window
| (ala blockchain) and has enough randomness built into it that
| predicting window attributes is a very-low-probability case.
| When a new event is generated you declare that event to be
| part of a certain window. You could not have fraudulently
| backdated your event because the future windows already
| considered the original future window state (i.e., the state
| before you inserted your event). You cannot future-date your
| event because you cannot predict the randomness.
|
| 3. At the outset, this is a clever idea. But you mentioned
| "scalable", I wonder how you would deal with the order of
| events that are rightfully binned to the same window.
| Wouldn't you end up with "concurrent events" and find
| yourself back at square one?
|
| 4. At some level, this design can be classified as a causal
| consistent system. In a non-byzantine world, causal
| consistent systems can afford network partitions. But in this
| world, you assume the systems have access to the window-ing
| system of time flow.
|
| Apologies if I grossly misinterpreted the article.
| yonz wrote:
| Nice write up, have you looked at Conflict free replicated
| relations?
|
| We have been discussing Lamport clocks and CRDTs in the context
| of building local-first applications in our LocalFirstWeb
| discord https://lfw.dev.
|
| Causality approximated with temporal proximity is a nice way of
| putting it. I've been trying to wrap my mind around an append
| only DAG to represent user actions so that multi account,
| multiuser and multi device experiences can run offline and get
| to eventually consist state when synced.
| MuffinFlavored wrote:
| > CRDTs
|
| > Conflict-free Replicated Data Types
| ketzu wrote:
| 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 wrote:
| 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.
| HyperSane wrote:
| 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.
| thoughtlede wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| > For example, a Set's add and delete operations.
|
| set add (union) is commutative, set delete is not. so a
| set with only the add (union) operation is a CRDT, but a
| set in general, with all of the typical set operations,
| is not a CRDT
|
| > you can create a CRDT Set
|
| not really
|
| you can create an add-only set, or an add-remove set, or
| a variety of other restricted versions of sets that
| support specific operations. but you can't create a set
| that is a fully-fledged set, with all the operations that
| sets generally provide.
|
| > 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.
|
| so this is the crux of the issue, I think -- "having the
| instances always process [ops] in the same order" is
| basically not possible in any real-world network
|
| first, because it's not possible to decide what the
| "correct" set of ops actually is, nodes are always
| subject to partitions, faults, etc. which prevent
| reliable dissemination of knowledge, and plus all the
| stuff about light cones and etc.
|
| second, because "the same order" implies a specific total
| ordering of events is unknowable (see prior comments)
|
| > you are "ensuring" ops are behaving like they are
| commutative and not "requiring" them to be so
|
| converting a non-commutative operation to a commutative
| operation in a distributed system requires reliable
| delivery, which no network provides
|
| the whole point of CRDTs is that they give you a formally
| strong version of eventual consistency that holds even in
| the face of (unavoidably) unreliable delivery
|
| > 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.
|
| this is true in the abstract, but the issue is that "what
| is communicated" is not a given, it's subject to the
| choices you make when you encounter a network fault -- or
| in the CAP model, a partition
|
| CRDTs are tools for eventually consistent (AP) systems,
| which means that you have to keep making forward progress
| if there are partitions, which means that message
| delivery between nodes is not reliable, it can always
| fail
|
| for state-based CRDTs if you fail to deliver a message
| it's fine, the information in that message is not lost
| forever, it will be included in the next message, and (if
| the partition is eventually healed) the ultimate state
| will converge. this is also true for delta states
|
| but for op-based CRDTs if you fail to deliver a message
| it's not fine, the information in that message is lost
| forever, it won't be included in the next message, and
| (even if the partition is eventually healed) the ultimate
| state will not converge
___________________________________________________________________
(page generated 2023-04-01 23:00 UTC)