Expanding upon the previous blog post regarding Capturing the happens before relationship, the scenario that is described only uses a single replica…

The question is, how does the algorithm change when there are multiple replicas but no leader? (leaderless replication)

• Using a single version number is not enough
  • Why?
    • There are multiple replicas accepting writes concurrently!
  • What do we do?
    • Instead we need to use a version number per replica as well as per key
  • How?
    • Each replica increments its own version number when processing a write.
    • It also keeps track of the version number it has seen from each of the other replicas
    • This info, indicates:
      • which value to overwrite
      • which value to keep as siblings

A collection of version numbers from all the replicas is called the version vector

Martin Kleppman

To note, there are many variations of version vectors… although as Martin Kleppman highlights dotted version vector is potentially one of the most interesting.

Dotted Version Vectors

For instance, Riak 2.0 actually uses this. Similar to the previous post for the shopping cart example:

• Vectors are sent from the database replicas to clients when values are read
• And these need to be sent back to the database when a value is subsequently written
• Riak encodes the version vector as a string, which it labels as casual context
• The version vector allows the database to distinguish between overwrites and concurrent writes

Moreover, like in the single replica example:

• The application may require the need to merge siblings
• The version vector structure ensures that it is safe to read from one replica
  • And then subsequently write back to another replica
  • Doing so, may result in the siblings being created, but no data is lossed as long as siblings are merged correctly

To Note…

A version vector is sometimes referred to as a vector clog (even though they are not quite the same). The difference is subtle… but in brief when comparing the state of replicas, the version vectors are the right data structure to use.