13

I've started looking at approaches to data synchronisation among a set of peers. The peers must be able to work in a disconnected way and then synchronise together to merge their local changes.

Peers should be able to merge local updates with a "three way merge". So, at synchronisation peers should know which facts are more recent, but where there is no strict ordering, they should be able to merge together the facts based on the common root.

When independent peers make changes, they can "time stamp" them with a "clock". I use the term "clock" and "time stamp" but I'm not meaning a wall time clock. I mean some kind of partial ordering of events which makes causality clear. It's the "happened before" relationship among events that forms a directed acyclic graph (DAG).

It seems like the "usual" way to do build this partial ordering is by using a vector clock. These can become very large, however. More recent developments such as interval tree clocks provide more compact storage of time stamps.

What I'm not at all clear about is why synchronisation protocols apparently don't "simply" store the DAG explicitly. (Or do they?)

Peers can independently create a time stamp by randomly generating a UUID (or by other means, such as <peer-name> + <local-monotonically-increasing-counter>). The ordering of this time stamp is entirely clear to that peer.

When 2 peers sync to each other, they can agree on a new time stamp. Again, the ordering of this time stamp is clear to both peers.

There is now a requirement to pass the happened before DAG between peers, but the storage and bandwidth requirements of this are small. Time points are graph vertexes. As such they have 1 or 2 incoming edges (1 for an event on a client and 2 for a sync between clients). This is bounded and independent of the number of peers in the network.

To use an individual time point, you require the graph of time points that lead in to this. However, as far as I can see, any peer that is able to know of a time point (it has generated it itself, or generated it with another peer, or has been told it by another peer when synchronising with it) has also had an opportunity to know about the history leading up to that time point. I think there's probably an inductive proof for this.

Given that storing and synching the DAG explicitly seems simple: is this used in practice? If not, why are vector clocks preferred?


Notes

Peer to peer

I'd prefer to a peer to peer solution over a client server solution.

The likely end topology will be many clients connecting to a much smaller group of servers that replicate among themselves. However, it'd be nice to have a general solution that supported this particular topology rather than a solution that requires this specific topology.

  • I may be misunderstanding what you're saying, but it's unclear how a graph of all events leading to a state could be smaller than a vector of counters. Unless you're in a system that has an extremely large number of nodes and an extremely small number of changes. – kdgregory Jun 10 '15 at 10:50
  • Thanks @kdgregory – good point. To be able to compute a three way merge in the future, you need to know the past (and be able to determine the DAG of the past time points). So, if you are storing those past time points then explicitly storing the DAG is cheaper. If you are not storing those past time points then you can't compute a three way merge of data anyway. – I wonder if this three way requirement might be the thing? If you don't want 3-way, perhaps vector clocks better than explicit DAG? – Benjohn Jun 10 '15 at 11:02
  • I reckon this could be the crucial point @kdgregory, so I've added a bit about that to the question. I am assuming it be possible to perform a 3-way-merge, which also implies that all of history is known. If all history is known then (I reckon) an explicit DAG is cheaper. If history is truncated, then vector clocks are probably the less costly approach. – Benjohn Jun 10 '15 at 11:12
  • 1
    Yeah, my understanding of vector clocks is that they're intended simply for an accept/reject decision: "node C is trying to update this piece of data, but it isn't aware of node B's update". – kdgregory Jun 10 '15 at 11:16
1

As far as I can tell, version control systems like Git and Mercurial use the DAG approach rather than vector clocks.

  • 1
    Without an explanation, this answer may become useless in case if someone else posts an opposite opinion. For example, if someone posts a claim like "Propversion control systems like Git and Mercurial use vector clocks rather than the DAG approach", how would this answer help reader to pick of two opposing opinions? Consider editing it into a better shape, to meet How to Answer quality standards. – gnat Aug 12 '16 at 21:30
  • 2
    The way I understood the question, they were asking if there are any real world examples of where DAG is used rather than vector clocks. – bikeman868 Aug 13 '16 at 21:27
  • 1
    Both Git and Mecurial are real world examples of peer to peer change synchronization using DAG, and I hope that benjohn will find my answer helpful even though you voted it down. – bikeman868 Aug 13 '16 at 21:30
  • Hi @bikeman868 I've voted you up for a net 0 (sorry). Your answer is helpful, even if couched with uncertainty! While references or authoritative answers are always nice, stack exchanges don't mandate that! Your suggestion makes good sense with points in comments on the question. It seems like when you want to store history and be able to merge histories, then a DAG is appropriate. When you don't store history and want synchronisation and consensus on the current state, then vector clocks are what you need. – Benjohn Aug 21 '16 at 11:31
1

Take a look on the consensus problem. Depending on your task requirements (as to how much data do you have, how many syncing nodes, how often etc.) existing solutions to that problem (like "Raft") might be suitable for your case.

Another (maybe tangential) approach to this problem is designing a CRDT.

  • Braid HTTP is attempting to create a CRDT-based state sync protocol via augmenting HTTP. They have a great visualization of a Time DAG and Space DAG, and how these two concepts inter-relate to arrive at eventual consistency. – Duane J Oct 25 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.