Version Vectors(III)

In my last article, we looked at one of the techniques of identifying concurrent updates/conflicts by leveraging Server(Replica) as an Actor & the advantages and disadvantages of doing so. If we went with the approach to include siblings in our Version Vectors to resolve conflicts, we still don’t have a way to track causality in the merged state. If we don’t include siblings in our Version Vectors, we can have data loss/updates. In this article, we’ll look at another approach for identifying concurrent updates/conflicts.

Dotted Version Vectors

Dotted Version Vectors solve the problems we saw with using ServerId. Let’s go over the problem with using ServerId -

Using ServerId for Conflict Resolution

Let’s try to understand what’s happening in the above diagram -

  1. Let’s assume we have a key K, with value U. We’re assuming that we have an empty version vector, to begin with. Client’s C2 and C3 sync the same state from the Replica(Assuming all clients are interacting with the same replica) that’s implementing Version Vectors.
  2. C2 updates the value to W & sends a PUT command, with the local state of Version Vector it has(empty VV).
  3. C3 updates the value to V & sends a PUT command, with the local state of Version Vector it has(empty VV).
  4. Replica A receives the request from C3 first(C2’s request might be delayed because of network latency). Replica A compares the Version Vector it received with its local state & sees that they match. So it increments the counter to 1 & updates the value to V. It also sends back the state to C3.
  5. The request from C2 finally arrives at Replica A. Replica A compares the Version Vector it received with its local state & sees that the vector it received does not match its state. So it increments its counter to 2, and adds the value from C2 as a sibling to V. It also sends back the state to C2.
  6. C2 updates the value to Z & sends a PUT command, with the local state of Version Vector it has which is (A, 1).
  7. Replica A receives the request from C3, compares the Version Vector it received with its local state & sees that they do not match. So it increments its counter to 3, and adds the value Z from C3 as a sibling to V,W.

Problem with Step 7 -

--

--

Pratik Pandey - https://pratikpandey.substack.com

Senior Engineer with experience in designing and architecting large scale distributed systems.