Cook Computing

Replication and Conflict Detection in SSE

November 26, 2005 Written by Charles Cook

I use Lotus Notes daily to access a development group bug database and Lotus Domino server is one of the mail server backends supported by the product I work on, so the first thing that caught my attention in Ray Ozzie's announcement of Simple Sharing Extensions (SSE) was the point that the SSE's replication mechanism is based on that used by Notes:

Ray OzzieThis got me to thinking about simplicity. Notes had just about the simplest possible replication mechanism imaginable. After all, we built it at Iris in 1985 for use on a 6Mhz 286-based IBM PC/AT with incredibly slow-seeking 20MB drives. We were struggling with LIM EMS trying to make effective use of more than 1MB of memory. Everything about the design was about implementation simplicity and efficiency. So if simple is the goal, why not just adapt the Notes replication algorithm to this need? Notes "notefiles" could be analogous to RSS "feeds"; and Notes "notes" could be analogous to RSS "items"; and Notes "items" could be analogous to XML "elements".

Notefiles replicate by using a very simple mechanism based on GUID assignment, with clocks and tie-breakers to detect and deterministically propagate modifications. Something like this could easily be represented in XML. Notefiles replicate with one another in a decentralized, masterless manner; feeds could be "cross-subscribed" in a similar manner. There's no magic to it once you know specifically what you're trying to accomplish, but it certainly helped to have an existence proof.

So I studied the spec last night to find out how this works, in particular conflict detection.

Each version of an item in a feed is identified by a version number, and either or both of the time when the version was created (the when attribute) and the identifier for the endpoint that created the version (the by attribute).

Using the example from the draft spec, the first version of an item will look like this:


<item>
  <description>This is a test item</description>
  <sx:sync id="0a7903db47fb0ae8" version="1">
    <sx:history when="Sat, 21 May 2005 09:43:33 GMT" by="REO1750"/>
  </sx:sync>
</item>

When subsequent versions are created locally the information about previous versions is stored in <update> elements:


<item>
  <description>This is a test item</description>
  <sx:sync id="0a7903db47fb0ae8" version="4">
    <sx:history when="Tue, 24 May 2005 09:43:33 GMT" by="REO1750">
      <sx:update when="Mon, 23 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Sun, 22 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Sat, 21 May 2005 09:43:33 GMT"
          by="REO1750" />
    </sx:history>
  </sx:sync>
</item>

Note that the <update> elements are ordered most recent first and although they do not have a version attribute this can be deduced from the version attribute of the <sync> element. If this is n then the implicit version numbers of the <update> elements are n-1, n-2, n-3, and so on. So the versioning information in the previous example above can be represented as:


(4, Tue, 24 May 2005 09:43:33 GMT, REO1750)
(3, Mon, 23 May 2005 09:43:33 GMT, REO1750)
(2, Sun, 22 May 2005 09:43:33 GMT, REO1750)
(1, Sat, 21 May 2005 09:43:33 GMT, REO1750)

When a subscriber reads a feed and the feed contains items with the same id as items held locally, the subscriber must use a globally consistent algorithm to decide which instance of the item is the "winner" which will be included in the local copy of the feed. The spec define this as follows:

a. When comparing the incoming item to its corresponding local item, the "winner" is determined by a collation using comparison of these four keys, in order:

1. the version attribute of the sx:sync element (larger version number wins)

2. the when attribute of the sx:history element (later date/time wins; if it is present on one and not present on the other, present wins)

3. the by attribute of the sx:history element ("greater" normalized text wins; if it is present on one and not present on the other, present wins)

b. If the collation results in equality on all tests, the two items are deemed to be identical and no action is required on this item.

Continuing with the same example, say the item downloaded from the remote server looks like this:


<item>
  <description>This is a test item</description>
  <sx:sync id="0a7903db47fb0ae8" version="5">
    <sx:history when="Wed, 25 May 2005 09:43:33 GMT" by="JIM234">
      <sx:update when="Tues, 24 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Mon, 23 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Sun, 22 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Sat, 21 May 2005 09:43:33 GMT"
          by="REO1750" />
    </sx:history>
  </sx:sync>
</item>

In this case a new version of the item has been created by JIM234 on the remote feed. The test on version number indicates the remote item is the winner and the local item should be replaced. If it turns out that there is no winner we assume that the items are equal and no action is required. Otherwise:

c. Now that a "winner" and a "loser" have been declared, one must detect to see if this was a normal sequence of edits, of if the endpoints separately edited the same version of the same item and "stepped on" each others' changes. This is called conflict detection.

4.4.1 Conflict Detection

In order to detect conflicts, endpoints MUST follow this algorithm on the modification history of two updated items:

1. If there is an sx:history element:

a. Let n equal the version attribute of the winner's sx:sync element.

b. Decrement n by the current version attribute of the loser's sx:sync item.

c. Compare the when and by attributes of the loser's sx:history element with the corresponding attributes of the nth (1-based) sx:update sub-element of the winner. If n is 0, compare against the sx:history element of the winner.

d. If the nth sx:update sub-element does not exist, assume NO CONFLICT; we are done processing conflict detection.

e. If attribute values are equal, there is NO CONFLICT; we are done processing conflict detection.

f. If they are not equal it is a CONFLICT; continue with step 2.

2. If a conflict is detected, the conflict attribute on the sx:sync element should be set to "true"; else if a conflict is not detected, the value of the conflict attribute MUST be preserved.

All this is saying is that when the most recent version of the item for the loser does not have the same when and by attributes as the similarly numbered version of the winner's item, the remote and local versions are out of sync. For example in the example above the versioning information is:


Local - Loser
(4, Tue, 24 May 2005 09:43:33 GMT, REO1750)
(3, Mon, 23 May 2005 09:43:33 GMT, REO1750)
(2, Sun, 22 May 2005 09:43:33 GMT, REO1750)
(1, Sat, 21 May 2005 09:43:33 GMT, REO1750)

Remote - Winner
(5, Wed, 25 May 2005 09:43:33 GMT, JIM234)
(4, Tue, 24 May 2005 09:43:33 GMT, REO1750)
(3, Mon, 23 May 2005 09:43:33 GMT, REO1750)
(2, Sun, 22 May 2005 09:43:33 GMT, REO1750)
(1, Sat, 21 May 2005 09:43:33 GMT, REO1750)

The most recent version for the loser is version 4, and if we compare this with version 4 of the winner we see that they are the same and so there is no conflict. However say the versioning information looked like this:


Local - Loser
(4, Tue, 24 May 2005 09:43:33 GMT, REO1750)
(3, Mon, 23 May 2005 09:43:33 GMT, REO1750)
(2, Sun, 22 May 2005 09:43:33 GMT, REO1750)
(1, Sat, 21 May 2005 09:43:33 GMT, REO1750)

Remote - Winner
(5, Wed, 25 May 2005 09:43:33 GMT, JIM234)
(4, Mon, 23 May 2005 11:01:12 GMT, JIM234)
(3, Mon, 23 May 2005 09:43:33 GMT, REO1750)
(2, Sun, 22 May 2005 09:43:33 GMT, REO1750)
(1, Sat, 21 May 2005 09:43:33 GMT, REO1750)

Now the most recent version for the loser - version 4 - has different attribute values to the winner's version 4 and so there is a conflict. Up to version 3 the two feeds were in sync but the endpoints made their own version 4 changes and conflict was introduced.

The spec specifies how to handle cases where full versioning information is not available. One point to note is that the version number takes precedence over when the version was created which might seem a bit counter-intuitive. In the following example the remote item is the winner even though the local item was updated over two days later:


LOCAL

<item>
  <description>This is a test item</description>
  <sx:sync id="0a7903db47fb0ae8" version="5">
    <sx:history when="Thu, 26 May 2005 20:00:00 GMT" by="REO1750">
      <sx:update when="Tues, 24 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Mon, 23 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Sun, 22 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Sat, 21 May 2005 09:43:33 GMT"
          by="REO1750" />
    </sx:history>
  </sx:sync>
</item>

REMOTE

<item>
  <description>This is a test item</description>
  <sx:sync id="0a7903db47fb0ae8" version="6">
    <sx:history when="Tues, 24 May 2005 13:00:00 GMT" by="JIM234">
      <sx:update when="Tues, 24 May 2005 11:00:00 GMT"
          by="JIM234" />
      <sx:update when="Tues, 24 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Mon, 23 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Sun, 22 May 2005 09:43:33 GMT"
          by="REO1750" />
      <sx:update when="Sat, 21 May 2005 09:43:33 GMT"
          by="REO1750" />
    </sx:history>
  </sx:sync>
</item>