Version Vectors are not Vector Clocks

Most people still confuse Version Vectors and Vector Clocks. Well, I did confuse them for several years. In fact they look the same and the update rules are almost the same.

Both of these mechanisms are practical ways of capturing causality in distributed systems. Causality (in distributed systems) is an abstract concept, can was formalized in 1978 by Leslie Lamport in one of the most cited  articles in computer science. In 1983 Version Vectors are developed to track the causal relations among data items that can be concurrently updated. Some years later, around 1988, Vector Clocks are developed to track the causality between events in a distributed computation. In both cases a vector of integers, one per source of concurrency, is used. There is, however, a fundamental difference.

First, in order to simplify a little bit, lets consider that we have a fixed number of processes and a fixed number of replicas. 

  • Vector Clocks need to establish a partial order among a, potentially ever growing, set of events occurring in the processes. The set of events that are generated in the distributed computation. Naturally since the set can grow unbounded, the tracking mechanism also needs to grow unbounded. Vectors of integers are fine since, at least in theory we don’t run out of integers. In 1991, Charron-Bost showed in this article that Vector Clocks are the smaller mechanism that can track causality among distributed events.
  • Version Vectors need to establish a partial order (more precisely a pre-order) among the replicas in the distributed system. Notice that although the state in these replicas changes as consequence of ever growing sets of update events, here we want to relate the replica states and not the update events. Using vectors of integers is over-expressive in this setting. In 2004, we noticed this and constructed Bounded Version Vectors, where integers are substituted by a limited set of symbols, depending on the number of replicas. Naturally, Charron-Bost result does not apply to Version Vectors.

Lets consider a simple example, thats shows that vectors of integers are over-expressive . One has two recently synchronized replicas A and B with identical state and vectors A[2,3] and B[2,3]. Now, replica A suffers an update and its new vector is A[3,3]. We now see that A is more updated than B, since [3,3] > [2,3] (here each integer in the left is greater or equal than its counterpart in the same position). Now replica A suffers 7 more updates, A[10,3]. Still we have [10,3] > [2,3], and this increase in the integer does not convey more information to the task of tracking the causal order among the two replicas. The number of individual updates is typically not important, specially in systems where you can change either a lot or a little in a single update. What is important is how they change the causal order relation among the replicas.

In the example, at this point, we can compare A[10,3] and B[2,3] and notice that they are easy to synchronize since A has the most updated state and it can be simply copied into B. However, if B issues an update and we now have a system with A[10,3] and B[2,4]. Now the replicas are divergent and a synchronization will typically have to look at the state (often with user assistance)  to figure the correct synchronized state that can be tagged with [10,4].

The message is, use the right tools and know the differences. Vector Clocks are great to implement causal delivery middleware, consistent snapshots, and the like. But for replicated data, Version Vectors are the right concept, and several mechanisms can make use of the subtle differences. Our own work on Dotted Version Vectors explores this and a specific system interaction that occurs in present data-stores. We also point out to Concise Version Vectors that explores the synchronization of multiple replicas  and early work on dynamic version vector maintenance

 

 

Advertisements

5 responses to “Version Vectors are not Vector Clocks

  1. I have always thought that vector clock and version clock were the same thing before reading this article. It is the theorem of Charron-Bost that reminds me that they are actually different: otherwise your dotted version clock cannot be right. I am wondering whether there is some theorem on version clock, analogous to the Charron-Bost theorem on vector clock.

  2. In the “simple example”, you have commented that “The number of individual updates is typically not important, specially in systems where you can change either a lot or a little in a single update.” Does the “individual updates” mean the updates made by a single process? What do you mean by “you can change either a lot or a little in a single update”? Could you give some examples?

  3. Carlos Baquero

    Hi, on the “change either a lot or a little in a single update” means to say that small changes or big changes to a replica can both be detected by advancing a clock entry by 1. The magnitude of the change is not important, so if you change a word or a whole paragraph, its the same. Its a bit like doing copy-on-write on memory pages, it doesn’t mater how much you changed.

  4. Is my understanding right: For a distributed storage system, what the dotted version clock is tracking is the causality among *replica states* instead of among the *update events* modifying the states. In vector clock with one entry per client, the causal history is a set of *events*. However, in dotted version clock, the causal history is now a set of *replica states*, from which we cannot restore the origin *update events* which bring the initial state to the current one.

    I have read your paper “Dotted Version Vectors: Logical Clocks for Optimistic Replication” which takes the typical key-value store as example. In particular, dotted version vector is used for eventual consistency. My questions are
    (1) Can DVV be used for causal consistency?
    (2) How to capture causality among replica states over different keys?
    (3) Is DVV suitable for the conversation scenario in social network in which people can reply to a post and also to another reply. The replies are causally organized in the natural way.

    I am still quite confused about (dotted) version clock. May I have your comments on these questions? Great thanks.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s