1 Multi-party Conflict Detection
2 ==============================
4 The current Magic-Folder remote conflict detection design does not properly detect remote conflicts
5 for groups of three or more parties. This design is specified in the "Fire Dragon" section of this document:
6 https://github.com/tahoe-lafs/tahoe-lafs/blob/2551.wip.2/docs/proposed/magic-folder/remote-to-local-sync.rst#fire-dragons-distinguishing-conflicts-from-overwrites
8 This Tahoe-LAFS trac ticket comment outlines a scenario with
9 three parties in which a remote conflict is falsely detected:
11 .. _`ticket comment`: https://tahoe-lafs.org/trac/tahoe-lafs/ticket/2551#comment:22
14 Summary and definitions
15 =======================
17 Abstract file: a file being shared by a Magic Folder.
19 Local file: a file in a client's local filesystem corresponding to an abstract file.
21 Relative path: the path of an abstract or local file relative to the Magic Folder root.
23 Version: a snapshot of an abstract file, with associated metadata, that is uploaded by a Magic Folder client.
25 A version is associated with the file's relative path, its contents, and
26 mtime and ctime timestamps. Versions also have a unique identity.
29 * If and only if a change to a client's local file at relative path F that results in an upload of version V',
30 was made when the client already had version V of that file, then we say that V' directly follows V.
31 * The follows relation is the irreflexive transitive closure of the "directly follows" relation.
33 The follows relation is transitive and acyclic, and therefore defines a DAG called the
34 Version DAG. Different abstract files correspond to disconnected sets of nodes in the Version DAG
35 (in other words there are no "follows" relations between different files).
37 The DAG is only ever extended, not mutated.
39 The desired behaviour for initially classifying overwrites and conflicts is as follows:
41 * if a client Bob currently has version V of a file at relative path F, and it sees a new version V'
42 of that file in another client Alice's DMD, such that V' follows V, then the write of the new version
43 is initially an overwrite and should be to the same filename.
44 * if, in the same situation, V' does not follow V, then the write of the new version should be
45 classified as a conflict.
47 The existing `Magic Folder design for remote-to-local sync`_ defines when an initial overwrite
48 should be reclassified as a conflict.
50 The above definitions completely specify the desired solution of the false
51 conflict behaviour described in the `ticket comment`_. However, they do not give
52 a concrete algorithm to compute the follows relation, or a representation in the
53 Tahoe-LAFS file store of the metadata needed to compute it.
55 We will consider two alternative designs, proposed by Leif Ryge and
56 Zooko Wilcox-O'Hearn, that aim to fill this gap.
58 .. _`Magic Folder design for remote-to-local sync`: remote-to-local-sync.rst
62 Leif's Proposal: Magic-Folder "single-file" snapshot design
63 ===========================================================
68 We propose a relatively simple modification to the initial Magic Folder design which
69 adds merkle DAGs of immutable historical snapshots for each file. The full history
70 does not necessarily need to be retained, and the choice of how much history to retain
71 can potentially be made on a per-file basis.
79 Additionally, the initial design had two cases of excess authority:
81 1. The magic folder administrator (inviter) has everyone's write-caps and is thus essentially "root"
82 2. Each client shares ambient authority and can delete anything or everything and
83 (assuming there is not a conflict) the data will be deleted from all clients. So, each client
84 is effectively "root" too.
86 Thus, while it is useful for file synchronization, the initial design is a much less safe place
87 to store data than in a single mutable tahoe directory (because more client computers have the
88 possibility to delete it).
94 - merkle DAG: like a merkle tree but with multiple roots, and with each node potentially having multiple parents
95 - magic folder: a logical directory that can be synchronized between many clients
96 (devices, users, ...) using a Tahoe-LAFS storage grid
97 - client: a Magic-Folder-enabled Tahoe-LAFS client instance that has access to a magic folder
98 - DMD: "distributed mutable directory", a physical Tahoe-LAFS mutable directory.
99 Each client has the write cap to their own DMD, and read caps to all other client's DMDs
100 (as in the original Magic Folder design).
101 - snapshot: a reference to a version of a file; represented as an immutable directory containing
102 an entry called "content" (pointing to the immutable file containing the file's contents),
103 and an entry called "parent0" (pointing to a parent snapshot), and optionally parent1 through
104 parentN pointing at other parents. The Magic Folder snapshot object is conceptually very similar
105 to a git commit object, except for that it is created automatically and it records the history of an
106 individual file rather than an entire repository. Also, commits do not need to have authors
107 (although an author field could be easily added later).
108 - deletion snapshot: immutable directory containing no content entry (only one or more parents)
109 - capability: a Tahoe-LAFS diminishable cryptographic capability
110 - cap: short for capability
111 - conflict: the situation when another client's current snapshot for a file is different than our current snapshot, and is not a descendant of ours.
112 - overwrite: the situation when another client's current snapshot for a file is a (not necessarily direct) descendant of our current snapshot.
118 This new design will track the history of each file using "snapshots" which are
119 created at each upload. Each snapshot will specify one or more parent snapshots,
120 forming a directed acyclic graph. A Magic-Folder user's DMD uses a flattened directory
121 hierarchy naming scheme, as in the original design. But, instead of pointing directly
122 at file contents, each file name will link to that user's latest snapshot for that file.
124 Inside the dmd there will also be an immutable directory containing the client's subscriptions
125 (read-caps to other clients' dmds).
127 Clients periodically poll each other's DMDs. When they see the current snapshot for a file is
128 different than their own current snapshot for that file, they immediately begin downloading its
129 contents and then walk backwards through the DAG from the new snapshot until they find their own
130 snapshot or a common ancestor.
132 For the common ancestor search to be efficient, the client will need to keep a local store (in the magic folder db) of all of the snapshots
133 (but not their contents) between the oldest current snapshot of any of their subscriptions and their own current snapshot.
134 See "local cache purging policy" below for more details.
136 If the new snapshot is a descendant of the client's existing snapshot, then this update
137 is an "overwrite" - like a git fast-forward. So, when the download of the new file completes it can overwrite
138 the existing local file with the new contents and update its dmd to point at the new snapshot.
140 If the new snapshot is not a descendant of the client's current snapshot, then the update is a
141 conflict. The new file is downloaded and named $filename.conflict-$user1,$user2 (including a list
142 of other subscriptions who have that version as their current version).
144 Changes to the local .conflict- file are not tracked. When that file disappears
145 (either by deletion, or being renamed) a new snapshot for the conflicting file is
146 created which has two parents - the client's snapshot prior to the conflict, and the
147 new conflicting snapshot. If multiple .conflict files are deleted or renamed in a short
148 period of time, a single conflict-resolving snapshot with more than two parents can be created.
150 ! I think this behavior will confuse users.
152 Tahoe-LAFS snapshot objects
153 ---------------------------
155 These Tahoe-LAFS snapshot objects only track the history of a single file, not a directory hierarchy.
156 Snapshot objects contain only two field types:
157 - ``Content``: an immutable capability of the file contents (omitted if deletion snapshot)
158 - ``Parent0..N``: immutable capabilities representing parent snapshots
160 Therefore in this system an interesting side effect of this Tahoe snapshot object is that there is no
161 snapshot author. The only notion of an identity in the Magic-Folder system is the write capability of the user's DMD.
163 The snapshot object is an immutable directory which looks like this:
164 content -> immutable cap to file content
165 parent0 -> immutable cap to a parent snapshot object
166 parent1..N -> more parent snapshots
169 Snapshot Author Identity
170 ------------------------
172 Snapshot identity might become an important feature so that bad actors
173 can be recognized and other clients can stop "subscribing" to (polling for) updates from them.
175 Perhaps snapshots could be signed by the user's Magic-Folder write key for this purpose? Probably a bad idea to reuse the write-cap key for this. Better to introduce ed25519 identity keys which can (optionally) sign snapshot contents and store the signature as another member of the immutable directory.
181 detection of conflicts
182 ``````````````````````
184 A Magic-Folder client updates a given file's current snapshot link to a snapshot which is a descendent
185 of the previous snapshot. For a given file, let's say "file1", Alice can detect that Bob's DMD has a "file1"
186 that links to a snapshot which conflicts. Two snapshots conflict if one is not an ancestor of the other.
189 a possible UI for resolving conflicts
190 `````````````````````````````````````
192 If Alice links a conflicting snapshot object for a file named "file1",
193 Bob and Carole will see a file in their Magic-Folder called "file1.conflicted.Alice".
194 Alice conversely will see an additional file called "file1.conflicted.previous".
195 If Alice wishes to resolve the conflict with her new version of the file then
196 she simply deletes the file called "file1.conflicted.previous". If she wants to
197 choose the other version then she moves it into place:
199 mv file1.conflicted.previous file1
202 This scheme works for N number of conflicts. Bob for instance could choose
203 the same resolution for the conflict, like this:
208 Deletion propagation and eventual Garbage Collection
209 ----------------------------------------------------
211 When a user deletes a file, this is represented by a link from their DMD file
212 object to a deletion snapshot. Eventually all users will link this deletion
213 snapshot into their DMD. When all users have the link then they locally cache
214 the deletion snapshot and remove the link to that file in their DMD.
215 Deletions can of course be undeleted; this means creating a new snapshot
216 object that specifies itself a descent of the deletion snapshot.
218 Clients periodically renew leases to all capabilities recursively linked
219 to in their DMD. Files which are unlinked by ALL the users of a
220 given Magic-Folder will eventually be garbage collected.
222 Lease expirey duration must be tuned properly by storage servers such that
223 Garbage Collection does not occur too frequently.
227 Performance Considerations
228 --------------------------
233 Our old scheme requires two remote Tahoe-LAFS operations per local file modification:
234 1. upload new file contents (as an immutable file)
235 2. modify mutable directory (DMD) to link to the immutable file cap
237 Our new scheme requires three remote operations:
238 1. upload new file contents (as in immutable file)
239 2. upload immutable directory representing Tahoe-LAFS snapshot object
240 3. modify mutable directory (DMD) to link to the immutable snapshot object
245 Our old scheme requires one remote Tahoe-LAFS operation per remote file modification (not counting the polling of the dmd):
246 1. Download new file content
248 Our new scheme requires a minimum of two remote operations (not counting the polling of the dmd) for conflicting downloads, or three remote operations for overwrite downloads:
249 1. Download new snapshot object
250 2. Download the content it points to
251 3. If the download is an overwrite, modify the DMD to indicate that the downloaded version is their current version.
253 If the new snapshot is not a direct descendant of our current snapshot or the other party's previous snapshot we saw, we will also need to download more snapshots to determine if it is a conflict or an overwrite. However, those can be done in
254 parallel with the content download since we will need to download the content in either case.
256 While the old scheme is obviously more efficient, we think that the properties provided by the new scheme make it worth the additional cost.
258 Physical updates to the DMD overiouslly need to be serialized, so multiple logical updates should be combined when an update is already in progress.
260 conflict detection and local caching
261 ````````````````````````````````````
263 Local caching of snapshots is important for performance.
264 We refer to the client's local snapshot cache as the ``magic-folder db``.
266 Conflict detection can be expensive because it may require the client
267 to download many snapshots from the other user's DMD in order to try
268 and find it's own current snapshot or a descendent. The cost of scanning
269 the remote DMDs should not be very high unless the client conducting the
270 scan has lots of history to download because of being offline for a long
271 time while many new snapshots were distributed.
274 local cache purging policy
275 ``````````````````````````
277 The client's current snapshot for each file should be cached at all times.
278 When all clients' views of a file are synchronized (they all have the same
279 snapshot for that file), no ancestry for that file needs to be cached.
280 When clients' views of a file are *not* synchronized, the most recent
281 common ancestor of all clients' snapshots must be kept cached, as must
282 all intermediate snapshots.
288 Bob can in fact, set a pre-existing directory (with files) as his new Magic-Folder directory, resulting
289 in a merge of the Magic-Folder with Bob's local directory. Filename collisions will result in conflicts
290 because Bob's new snapshots are not descendent's of the existing Magic-Folder file snapshots.
293 Example: simultaneous update with four parties:
295 1. A, B, C, D are in sync for file "foo" at snapshot X
296 2. A and B simultaneously change the file, creating snapshots XA and XB (both descendants of X).
297 3. C hears about XA first, and D hears about XB first. Both accept an overwrite.
298 4. All four parties hear about the other update they hadn't heard about yet.
300 - everyone's local file "foo" has the content pointed to by the snapshot in their DMD's "foo" entry
301 - A and C's DMDs each have the "foo" entry pointing at snapshot XA
302 - B and D's DMDs each have the "foo" entry pointing at snapshot XB
303 - A and C have a local file called foo.conflict-B,D with XB's content
304 - B and D have a local file called foo.conflict-A,C with XA's content
308 - Everyone ignores the conflict, and continue updating their local "foo". but slowly enough that there are no further conflicts, so that A and C remain in sync with eachother, and B and D remain in sync with eachother.
310 - A and C's foo.conflict-B,D file continues to be updated with the latest version of the file B and D are working on, and vice-versa.
312 - A and C edit the file at the same time again, causing a new conflict.
314 - Local files are now:
316 A: "foo", "foo.conflict-B,D", "foo.conflict-C"
318 C: "foo", "foo.conflict-B,D", "foo.conflict-A"
320 B and D: "foo", "foo.conflict-A", "foo.conflict-C"
322 - Finally, D decides to look at "foo.conflict-A" and "foo.conflict-C", and they manually integrate (or decide to ignore) the differences into their own local file "foo".
324 - D deletes their conflict files.
326 - D's DMD now points to a snapshot that is a descendant of everyone else's current snapshot, resolving all conflicts.
328 - The conflict files on A, B, and C disappear, and everyone's local file "foo" contains D's manually-merged content.
331 Daira: I think it is too complicated to include multiple nicknames in the .conflict files
332 (e.g. "foo.conflict-B,D"). It should be sufficient to have one file for each other client,
333 reflecting that client's latest version, regardless of who else it conflicts with.
336 Zooko's Design (as interpreted by Daira)
337 ========================================
339 A version map is a mapping from client nickname to version number.
341 Definition: a version map M' strictly-follows a mapping M iff for every entry c->v
342 in M, there is an entry c->v' in M' such that v' > v.
345 Each client maintains a 'local version map' and a 'conflict version map' for each file
346 in its magic folder db.
347 If it has never written the file, then the entry for its own nickname in the local version
348 map is zero. The conflict version map only contains entries for nicknames B where
349 "$FILENAME.conflict-$B" exists.
351 When a client A uploads a file, it increments the version for its own nickname in its
352 local version map for the file, and includes that map as metadata with its upload.
354 A download by client A from client B is an overwrite iff the downloaded version map
355 strictly-follows A's local version map for that file; in this case A replaces its local
356 version map with the downloaded version map. Otherwise it is a conflict, and the
357 download is put into "$FILENAME.conflict-$B"; in this case A's
358 local version map remains unchanged, and the entry B->v taken from the downloaded
359 version map is added to its conflict version map.
361 If client A deletes or renames a conflict file "$FILENAME.conflict-$B", then A copies
362 the entry for B from its conflict version map to its local version map, deletes
363 the entry for B in its conflict version map, and performs another upload (with
364 incremented version number) of $FILENAME.
368 A, B, C = (10, 20, 30) everyone agrees.
369 A updates: (11, 20, 30)
370 B updates: (10, 21, 30)
372 C will see either A or B first. Both would be an overwrite, if considered alone.