From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by olra.theworths.org (Postfix) with ESMTP id 4E0DB431FD0 for ; Tue, 20 Dec 2011 00:32:46 -0800 (PST) X-Virus-Scanned: Debian amavisd-new at olra.theworths.org X-Spam-Flag: NO X-Spam-Score: -0.7 X-Spam-Level: X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5 tests=[RCVD_IN_DNSWL_LOW=-0.7] autolearn=disabled Received: from olra.theworths.org ([127.0.0.1]) by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ThBFch3YK+Id for ; Tue, 20 Dec 2011 00:32:45 -0800 (PST) Received: from mail-we0-f181.google.com (mail-we0-f181.google.com [74.125.82.181]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by olra.theworths.org (Postfix) with ESMTPS id 7C00C431FB6 for ; Tue, 20 Dec 2011 00:32:45 -0800 (PST) Received: by werm12 with SMTP id m12so2338992wer.26 for ; Tue, 20 Dec 2011 00:32:44 -0800 (PST) Received: by 10.216.135.75 with SMTP id t53mr618962wei.2.1324369963697; Tue, 20 Dec 2011 00:32:43 -0800 (PST) Received: from hotblack-desiato.hh.sledj.net (host81-149-164-25.in-addr.btopenworld.com. [81.149.164.25]) by mx.google.com with ESMTPS id cy8sm2493372wib.2.2011.12.20.00.32.41 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 20 Dec 2011 00:32:42 -0800 (PST) Received: by hotblack-desiato.hh.sledj.net (Postfix, from userid 30000) id CB728A029E; Tue, 20 Dec 2011 08:32:40 +0000 (GMT) To: Austin Clements Subject: Re: [PATCH 0/5] Store message modification times in the DB In-Reply-To: <20111219194821.GA10376@mit.edu> References: <1323796305-28789-1-git-send-email-schnouki@schnouki.net> <20111219194821.GA10376@mit.edu> User-Agent: Notmuch/0.10.2+107~ga2d0215 (http://notmuchmail.org) Emacs/24.0.92.1 (x86_64-pc-linux-gnu) From: David Edmondson Date: Tue, 20 Dec 2011 08:32:40 +0000 Message-ID: MIME-Version: 1.0 Content-Type: text/plain Cc: notmuch@notmuchmail.org X-BeenThere: notmuch@notmuchmail.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: "Use and development of the notmuch mail system." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 20 Dec 2011 08:32:46 -0000 On Mon, 19 Dec 2011 14:48:21 -0500, Austin Clements wrote: > Here are sketches for two sync algorithms with different properties. > I haven't proven these to be correct, but I believe they are. In > both, R is the remote host and L is the local host. They're both > one-way (they only update tags on L), but should be symmetrically > stable. Thanks for these. > == Two-way "merge" from host R to host L == > > Per-host state: > - last_mtime: Map from remote hosts to last sync mtime With the proposed changes it seems that the state required on each host would live within the Xapian database (to be extracted with 'dump'). > new_mtime = last_mtime[R] > For msgid, mtime, tags in messages on host R with mtime >= last_mtime[R]: > If mtime > local mtime of msgid: > Set local tags of msgid to tags > new_mtime = max(new_mtime, mtime) > last_mtime[R] = new_mtime > > This has the advantage of keeping very little state, but the > synchronization is also quite primitive. If two hosts change a > message's tags in different ways between synchronizations, the more > recent of the two will override the full set of tags on that message. > This does not strictly require tombstones, though if you make a tag > change and then delete the message before a sync, the tag change will > be lost without some record of that state. Does this matter? If the tag on a deleted message is changed, does anyone care? > Also, this obviously depends heavily on synchronized clocks. > > > == Three-way merge from host R to host L == > > Per-host state: > - last_mtime: Map from remote hosts to last sync mtime > - last_sync: Map from remote hosts to the tag database as of the last sync Any ideas where this state might be kept? > new_mtime = last_mtime[R] > for msgid, mtime, r_tags in messages on host R with mtime >= last_mtime[R]: > my_tags = local tags of msgid > last_tags = last_sync[R][msgid] > for each tag that differs between my_tags and r_tags: > if tag is in last_tags: remove tag locally > else: add tag locally > last_sync[R][msgid] = tags > new_mtime = max(new_mtime, mtime) > Delete stale messages from last_sync[R] (using tombstones or something) > last_mtime[R] = new_mtime > > This protocol requires significantly more state, but can also > reconstruct per-tag changes. Conflict resolution is equivalent to > what git would do and is based solely on the current local and remote > state and the common ancestor state. This can lead to unintuitive > results if a tag on a message has gone through multiple changes on > both hosts since the last sync (though, I argue, there are no > intuitive results in such situations). Tombstones are only required > to garbage collect sync state (and other techniques could be used for > that). This also does not depend on time synchronization (though, > like any mtime solution, it does depend on mtime monotonicity). The > algorithm would work equally well with sequence numbers. > > I tried coming up with a third algorithm that used mtimes to resolve > tagging conflicts, but without per-tag mtimes it degenerated into the > first algorithm. dme. -- David Edmondson, http://dme.org