A highly-available move opertaion for replicated trees [pdf]
martin.kleppmann.com
A highly-available move opertaion for replicated trees [pdf]
1–10 of 14 posts
Re: A highly-available move opertaion for replicated trees [pdf]
#2Super cool. Martin Kleppmann, the lead author on this paper, is the author of Designing Data-Intensive Applications, which I haven't read but have heard pretty awesome things about.
What I have done: watched his other talks about CRDTs (conflict-free replicated data types). I'd recommend watching this video [1] for an overview of what CRDTs are, why he cares about them, and open problems (one of which he solves in this paper!).
A (potentially inaccurate) TLDR: local-first collaboration software presents is a compelling alternative to the current way collaboration is implemented in a client-server model. Specifically: if we build tooling that makes it easy to build collaborative experiences into your app without a server, then we'll potentially be able to achieve the goals of 'decentralization' (or, fuck the middleman or whatever you wanna call it) in some real sense. Note that I'm not talking about crypto coins here!
Very cool, very exciting!
Re: A highly-available move opertaion for replicated trees [pdf]
#3Super cool. Martin Kleppmann, the lead author on this paper, is the author of Designing Data-Intensive Applications, which I haven't read but have heard pretty awesome things about. What I have done: watched his other talks about CRDTs (conflict-free replicated data types). I'd recommend watching this video [1] for an overview of what CRDTs are, why he cares about them, and open problems (one of which he solves in th…
Ok, having read through the core of the algorithm, cool! Seems like the main key here is that move operations have timestamps associated with them, and this allows you to effectively linearize the operations (and ignore ones that result in invalid state).
The tradeoff: you need to store all the operations you've ever seen, as you need to be able to detect conflicts between old ones.
Question for the authors (if they are around): any ideas for how we might get to efficient pruning of old operations?
My first thought was that you could have some notion of epoch, and once you move beyond that epoch, you accept no new operations from it. But then you realize that this requires nodes to agree on moving between epochs, which seems like it might require some fancy consensus protocol / a known set of nodes / mad complexity.
I don't have any ideas. Do you all have some idea of how we might be able to prune this old log? Or even sketches of ideas?
Re: A highly-available move opertaion for replicated trees [pdf]
#4I must be missing something. The paper describes the algorithm of the CRDT and mentions that "timestamps ’t need to be globally unique and totally ordered".
Then it mentions multiple times that Lamport clocks/timestamp can be used as the timestamp in their system but as far as I know these only give a partial order of events. How is this reconciled in their system?
Re: A highly-available move opertaion for replicated trees [pdf]
#5I must be missing something. The paper describes the algorithm of the CRDT and mentions that "timestamps ’t need to be globally unique and totally ordered". Then it mentions multiple times that Lamport clocks/timestamp can be used as the timestamp in their system but as far as I know these only give a partial order of events. How is this reconciled in their system?
My understanding[1] is that you would not use only a Lamport timestamp but rather a tuple (Lamport, actor ID), where the actor ID is a globally unique per-node ID (say, a UUID), which would then be used as a tiebreaker in cases where comparing by the Lamport timestamp alone would give an ambiguous ordering.
This should not be problematic, since the Lamport timestamps are only equal in cases where there is guaranteed to be no causal relationship between the events (i.e. the user did not see the effects of one event before submitting the next event), so it's fine to pick the ordering arbitrarily.
[1] Based on reading the Rust implementation (https://docs.rs/crdt_tree/latest/src/crdt_tree/clock.rs.html...), since I had the same question :)
Re: A highly-available move opertaion for replicated trees [pdf]
#6Super cool. Martin Kleppmann, the lead author on this paper, is the author of Designing Data-Intensive Applications, which I haven't read but have heard pretty awesome things about. What I have done: watched his other talks about CRDTs (conflict-free replicated data types). I'd recommend watching this video [1] for an overview of what CRDTs are, why he cares about them, and open problems (one of which he solves in th…
Ok, having read through the core of the algorithm, cool! Seems like the main key here is that move operations have timestamps associated with them, and this allows you to effectively linearize the operations (and ignore ones that result in invalid state). The tradeoff: you need to store all the operations you've ever seen, as you need to be able to detect conflicts between old ones. Question for the authors (if they…
The authors actually do briefly mention this concern in the section titled 3.7 Algorithm extensions (under Log truncation):
> However, in practice it is easy to truncate the log, because apply_op only examines the log prefix of operations whose timestamp is greater than that of the operation being applied. Thus, once it is known that all future operations will have a timestamp greater than t, then operations with timestamp t or less can be discarded from the log.
The main issue seems to be that we need to know about all the replicas that we want to be able to synchronize with - but I guess there isn't really a way around this.
Re: A highly-available move opertaion for replicated trees [pdf]
#7Earlier quoted context omitted.
Ok, having read through the core of the algorithm, cool! Seems like the main key here is that move operations have timestamps associated with them, and this allows you to effectively linearize the operations (and ignore ones that result in invalid state). The tradeoff: you need to store all the operations you've ever seen, as you need to be able to detect conflicts between old ones. Question for the authors (if they…
The authors actually do briefly mention this concern in the section titled 3.7 Algorithm extensions (under Log truncation ): > However, in practice it is easy to truncate the log, because apply_op only examines the log prefix of operations whose timestamp is greater than that of the operation being applied. Thus, once it is known that all future operations will have a timestamp greater than t , then operations with t…
I did miss this section in my skim, but it's also the first place I went as well. It doesn't seem like you could ever be sure that no old messages would be sent with an earlier timestamp if you don't know the set of nodes that are participating in the protocol.
Moreover, if you allow the set of nodes you do know to make operations maliciously (e.g. a single bad node enters the set and tries to cause conflicts), things get much more complicated, and I don't really think you can escape the impossibility results in relation to consensus protocols...
Re: A highly-available move opertaion for replicated trees [pdf]
#8(Someone please fix the typo in the submitted title... @dang?)
Re: A highly-available move opertaion for replicated trees [pdf]
#9Super cool. Martin Kleppmann, the lead author on this paper, is the author of Designing Data-Intensive Applications, which I haven't read but have heard pretty awesome things about. What I have done: watched his other talks about CRDTs (conflict-free replicated data types). I'd recommend watching this video [1] for an overview of what CRDTs are, why he cares about them, and open problems (one of which he solves in th…
This book seems the bible of distributed systems, but I'm still looking for a MOOC that covers Distributed Systems.
Re: A highly-available move opertaion for replicated trees [pdf]
#10Super cool. Martin Kleppmann, the lead author on this paper, is the author of Designing Data-Intensive Applications, which I haven't read but have heard pretty awesome things about. What I have done: watched his other talks about CRDTs (conflict-free replicated data types). I'd recommend watching this video [1] for an overview of what CRDTs are, why he cares about them, and open problems (one of which he solves in th…
Reading through the book right now. It's really illuminating. Highly recommend to anyone trying to plug any of the gaps in their knowledge of system design.