3.3.4.6.2 Processing Updates

  • Article

DFS-R ensures convergence by imposing a total ordering on updates. A total ordering is obtained from the fields (fence, attributes, createTime, clock, uidDbGuid, uidVersion, gvsnDbGuid, and gvsnVersion).

An update with a higher value of fence supersedes updates with lower fence values; otherwise, the fence values are equal.

An update with the directory attribute set in the attributes field supersedes updates that do not have the directory attribute set; otherwise, these attributes coincide.

An update with a higher value of the createTime supersedes updates with lower values;<37> otherwise, the create times are the same.

An update with a higher value of the clock field supersedes updates with a lower value; otherwise, the clock fields are the same.

An update with the lexicographically highest uidDbGuid supersedes one with a lower value. GUIDs are compared using a lexicographic left-to-right comparison of each byte, where each byte is treated as an unsigned 8-bit number. The C-standard routine, memcmp, can for instance be used to realize this ordering as a positive return value from this routine stipulates that a GUID is lexicographically largest. If the uidDbGuid coincide, comparison proceeds to version numbers.

An update with the largest value of uidVersion supersedes an update with a lower value of uidVersion. Recall that VSNs are unsigned 64-bit numbers. Otherwise, if the versions are the same.

An update with the lexicographically largest gvsnDbGuid supersedes one with a lower value; otherwise, if the GUIDs are the same.

An update with the largest gvsnVersion supersedes an update with a lower gvsnVersion; otherwise, the two updates have the same GVSN, which a well-behaved implementation of DFS-R would allow only if the updates are in fact identical. That is, a well-behaved implementation of DFS-R treats the fields, except for the file hashes, of an update as immutable after it is created. Furthermore, at most one machine creates an update with a given GVSN.

To ensure convergence, a replicating member (DFS-R) MUST store one update per UID that is maximal with respect to the previously mentioned lexicographic ordering. A replicating member MUST implement a conflict resolution strategy according to standard File Replication Store semantics of updates. The minimal set of File Replication Store conflicts follow.

Dangling child conflict: An update is a dangling child if its present field is nonzero; it is not a replicated folder root; and its parent present field is 0.

A well-formed set of updates does not contain any of the previously mentioned conflicts and such that whenever update1.parentDbGuid = update2.uidDbGuid, update1.parentVersion = update2.uidVersion and update1.present, then update2.attributes contains the 0x00000010 bit. That is, the bitwise-and with the attribute and the mask 0x00000010 equals 0x00000010. A client MUST maintain a well-formed set of updates.

A dangling-child conflict MUST be resolved by ensuring that parents are saved in persistent storage prior to their children. Absence of dangling children is then enforced as a protocol invariant.

In addition to dangling-child conflicts, a client MAY also resolve cycle and name conflicts.

Cycle conflict: An update update1 introduces a directory cycle if there is a sequence update1, update2 ,…, . updatek such update1.present is nonzero and updatei.parentDbGuid = update(i+1).uidDbGuid, updatei.parentVersion = update(i+1).uidVersion, for I = 1…k, and update1 = updatek.

A cycle conflict MAY be resolved by creating an update with a fresh GVSN and a higher clock value that retains the old parent. To ensure convergence using this scheme in the presence of cycle conflicts, a client MUST process received updates in ancestral order—parents before children.<38>

File name conflict: Two file updates, update1 and update2, are in name conflict if their parentDbGuid and parentVersion field values are the same, they both have the present field set to a nonzero value, and their name fields are equal according to an implementation-specific string comparison, but their uidDbGuid or uidDbVersion values are different.

If a client decides to resolve a file name conflict, it MUST generate a new update for the conflict loser with a fresh GVSN, a clock value that is higher than the name conflict loser, set the present field set to 0 and the nameConflict field set to 1. To guarantee convergence, a client MUST NOT supersede any update with nameConflict set to 1 by any update that sets present to 1. Name conflicts are resolved. File names are compared using case-insensitive string comparison. Language-specific collation policies are not used when comparing file names.

Directory name conflict: Two directory updates, update1 and update2, are in name conflict if their parentDbGuid and parentVersion field values are the same, they both have the present field set to a nonzero value, and their name fields are equal according to an implementation-specific string comparison, but their uidDbGuid or uidDbVersion values are different.<39>

If a client decides to resolve a directory name conflict, it MUST set the conflict loser's createTime, uidDbGuid, and uidDbVersion values equal to the corresponding conflict winner field values. The conflict loser's uidVisible field MUST be set to 1. All files and directories whose parent was the conflict loser MUST be updated such that their parentDbGuid and parentVersion fields are set to the uidDbGuid and uidDbVersion values of the conflict winner.

Reserved UIDs: DFS-R reserves a number of UIDs for designated resources.

The UID of replicated folder roots: The UID of replicated folder roots is fixed by using version 1 and the GUID of the replicated folder, that is:

  • uidDbGuid = {GUID Replicated Folder}

  • uidVersion = 1

The GUID of the replicated folder is present in the configuration for DFS-R.

The UID of version vector tombstones: DFS-R allows members to garbage collect entries in their version vectors. When a member determines that a GUID m1, which is in the domain of a version chain vector, is stale, it MAY generate an update whose UID consists of the following:

  • uidDbGuid = bitwise XOR({GUID of Replicated Folder}, m1)

  • uidVersion = 2

The update's present field is set to 0, and the update is broadcast to replication partners. If a replication partner determines that m1 is not stale, it MAY<40> generate an update that subsumes the broadcasted update with the present field set to 1 (a nonzero value). If a member is not originating updates for a long period and wants to ensure that replication partners do not erroneously determine that it is stale, it SHOULD<41> periodically generate this update, with the present field set to 1, for each of its own replicated folders.

VSNs 0–8 are reserved; therefore, the versions of all other UIDs that correspond to replicated files MUST start with at least version 9.