32/5c8a34519a53a9b6cc78c7e614a2cbc0a0cbcd

   1 Return-Path: <amdragon@mit.edu>\r
   2 X-Original-To: notmuch@notmuchmail.org\r
   3 Delivered-To: notmuch@notmuchmail.org\r
   4 Received: from localhost (localhost [127.0.0.1])\r
   5         by olra.theworths.org (Postfix) with ESMTP id 224D0431FD0\r
   6         for <notmuch@notmuchmail.org>; Mon, 19 Dec 2011 11:47:13 -0800 (PST)\r
   7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: -0.7\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5\r
  12         tests=[RCVD_IN_DNSWL_LOW=-0.7] autolearn=disabled\r
  13 Received: from olra.theworths.org ([127.0.0.1])\r
  14         by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)\r
  15         with ESMTP id A6HwCmjIIPXK for <notmuch@notmuchmail.org>;\r
  16         Mon, 19 Dec 2011 11:47:12 -0800 (PST)\r
  17 Received: from dmz-mailsec-scanner-2.mit.edu (DMZ-MAILSEC-SCANNER-2.MIT.EDU\r
  18         [18.9.25.13])\r
  19         by olra.theworths.org (Postfix) with ESMTP id 544F0431FB6\r
  20         for <notmuch@notmuchmail.org>; Mon, 19 Dec 2011 11:47:12 -0800 (PST)\r
  21 X-AuditID: 1209190d-b7f576d0000008c4-a6-4eef94bfcc1c\r
  22 Received: from mailhub-auth-4.mit.edu ( [18.7.62.39])\r
  23         by dmz-mailsec-scanner-2.mit.edu (Symantec Messaging Gateway) with SMTP\r
  24         id BD.1B.02244.FB49FEE4; Mon, 19 Dec 2011 14:47:11 -0500 (EST)\r
  25 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103])\r
  26         by mailhub-auth-4.mit.edu (8.13.8/8.9.2) with ESMTP id pBJJlAF1017294; \r
  27         Mon, 19 Dec 2011 14:47:11 -0500\r
  28 Received: from awakening.csail.mit.edu (awakening.csail.mit.edu [18.26.4.91])\r
  29         (authenticated bits=0)\r
  30         (User authenticated as amdragon@ATHENA.MIT.EDU)\r
  31         by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id pBJJl8hV010252\r
  32         (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT);\r
  33         Mon, 19 Dec 2011 14:47:08 -0500 (EST)\r
  34 Received: from amthrax by awakening.csail.mit.edu with local (Exim 4.77)\r
  35         (envelope-from <amdragon@mit.edu>)\r
  36         id 1RcjC9-0002t5-QF; Mon, 19 Dec 2011 14:48:21 -0500\r
  37 Date: Mon, 19 Dec 2011 14:48:21 -0500\r
  38 From: Austin Clements <amdragon@MIT.EDU>\r
  39 To: David Edmondson <dme@dme.org>\r
  40 Subject: Re: [PATCH 0/5] Store message modification times in the DB\r
  41 Message-ID: <20111219194821.GA10376@mit.edu>\r
  42 References: <1323796305-28789-1-git-send-email-schnouki@schnouki.net>\r
  43         <cunk45szfiu.fsf@hotblack-desiato.hh.sledj.net>\r
  44 MIME-Version: 1.0\r
  45 Content-Type: text/plain; charset=us-ascii\r
  46 Content-Disposition: inline\r
  47 In-Reply-To: <cunk45szfiu.fsf@hotblack-desiato.hh.sledj.net>\r
  48 User-Agent: Mutt/1.5.21 (2010-09-15)\r
  49 X-Brightmail-Tracker:\r
  50  H4sIAAAAAAAAA+NgFprCKsWRmVeSWpSXmKPExsUixG6nrrt/yns/g58z9Cz23dnCZHH95kxm\r
  51         i339/g7MHrue/2XyeLbqFrPHlFlz2QOYo7hsUlJzMstSi/TtErgyGhdeYCr4J11x67hUA+Nc\r
  52         sS5GTg4JAROJBxtPs0DYYhIX7q1n62Lk4hAS2McocW1WA1hCSGADo8T+KWUQiZNMEpv3nGOC\r
  53         SCxhlLhzxBTEZhFQlfi4YiIriM0moCGxbf9yRhBbREBR4v+3FewgNrOAg8TKk71gtrCAs8Tm\r
  54         nzuB6jk4eAV0JF70SECMLJfY/akDrIRXQFDi5MwnLBCtWhI3/r1kAilnFpCWWP6PA8TkFLCR\r
  55         WLXdE6RCVEBFYsrJbWwTGIVmIWmehaR5FkLzAkbmVYyyKblVurmJmTnFqcm6xcmJeXmpRbpG\r
  56         ermZJXqpKaWbGEEBzinJu4Px3UGlQ4wCHIxKPLwrm977CbEmlhVX5h5ilORgUhLltZoMFOJL\r
  57         yk+pzEgszogvKs1JLT7EKMHBrCTC++PFWz8h3pTEyqrUonyYlDQHi5I4r6rWOz8hgfTEktTs\r
  58         1NSC1CKYrAwHh5IEry4wkoUEi1LTUyvSMnNKENJMHJwgw3mAhmuC1PAWFyTmFmemQ+RPMepy\r
  59         7P38/QyjEEtefl6qlDivKUiRAEhRRmke3BxYYnrFKA70ljDEOh5gUoOb9ApoCRPQkr7ANyBL\r
  60         ShIRUsDkk/ntnM+KLRMeB/14seG+UOpUhVU/tif9vqpl7WU3PaE2u2KpdYnH3Q+Jj3Qeal3X\r
  61         SJNTSlAzb7D97hOd9vzeGn35U3tzn4es32BT/LHyoKLk5zqbdSrFKj9iNQNe3LSeLtAWUPUx\r
  62         oeKbt4jp36kVP6wUjt/1yAm/pqdpc2hFiWT8QrU18kHnlFiKMxINtZiLihMBGxHPVicDAAA=\r
  63 Cc: notmuch@notmuchmail.org\r
  64 X-BeenThere: notmuch@notmuchmail.org\r
  65 X-Mailman-Version: 2.1.13\r
  66 Precedence: list\r
  67 List-Id: "Use and development of the notmuch mail system."\r
  68         <notmuch.notmuchmail.org>\r
  69 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  70         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  71 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  72 List-Post: <mailto:notmuch@notmuchmail.org>\r
  73 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  74 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  75         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  76 X-List-Received-Date: Mon, 19 Dec 2011 19:47:13 -0000\r
  77 \r
  78 Quoth David Edmondson on Dec 19 at  4:34 pm:\r
  79 > On Tue, 13 Dec 2011 18:11:40 +0100, Thomas Jost <schnouki@schnouki.net> wrote:\r
  80 > > This is a patch series I've been working on for some time in order to be\r
  81 > > able to sync my tags on several computers. I'm posting it now, but\r
  82 > > please consider it as a RFC rather than something that is ready to be\r
  83 > > pushed.\r
  84 > > \r
  85 > > The basic idea is to the last time each message was modified, i.e. "the\r
  86 > > message was added to the DB", "a tag was added" or "a tag was removed".\r
  87 > \r
  88 > Thomas, this is interesting. Do you have a (back of the envelope?)\r
  89 > design for how you will use this information to implement tag sync?\r
  90 > \r
  91 > My gut feeling is that we need a log of when a change occurred rather\r
  92 > than the last modification time, but I haven't really thought that all\r
  93 > through properly.\r
  94 \r
  95 Here are sketches for two sync algorithms with different properties.\r
  96 I haven't proven these to be correct, but I believe they are.  In\r
  97 both, R is the remote host and L is the local host.  They're both\r
  98 one-way (they only update tags on L), but should be symmetrically\r
  99 stable.\r
 100 \r
 101 \r
 102 == Two-way "merge" from host R to host L ==\r
 103 \r
 104 Per-host state:\r
 105 - last_mtime: Map from remote hosts to last sync mtime\r
 106 \r
 107 new_mtime = last_mtime[R]\r
 108 For msgid, mtime, tags in messages on host R with mtime >= last_mtime[R]:\r
 109   If mtime > local mtime of msgid:\r
 110     Set local tags of msgid to tags\r
 111   new_mtime = max(new_mtime, mtime)\r
 112 last_mtime[R] = new_mtime\r
 113 \r
 114 This has the advantage of keeping very little state, but the\r
 115 synchronization is also quite primitive.  If two hosts change a\r
 116 message's tags in different ways between synchronizations, the more\r
 117 recent of the two will override the full set of tags on that message.\r
 118 This does not strictly require tombstones, though if you make a tag\r
 119 change and then delete the message before a sync, the tag change will\r
 120 be lost without some record of that state.  Also, this obviously\r
 121 depends heavily on synchronized clocks.\r
 122 \r
 123 \r
 124 == Three-way merge from host R to host L ==\r
 125 \r
 126 Per-host state:\r
 127 - last_mtime: Map from remote hosts to last sync mtime\r
 128 - last_sync: Map from remote hosts to the tag database as of the last sync\r
 129 \r
 130 new_mtime = last_mtime[R]\r
 131 for msgid, mtime, r_tags in messages on host R with mtime >= last_mtime[R]:\r
 132   my_tags = local tags of msgid\r
 133   last_tags = last_sync[R][msgid]\r
 134   for each tag that differs between my_tags and r_tags:\r
 135     if tag is in last_tags: remove tag locally\r
 136     else: add tag locally\r
 137   last_sync[R][msgid] = tags\r
 138   new_mtime = max(new_mtime, mtime)\r
 139 Delete stale messages from last_sync[R] (using tombstones or something)\r
 140 last_mtime[R] = new_mtime\r
 141 \r
 142 This protocol requires significantly more state, but can also\r
 143 reconstruct per-tag changes.  Conflict resolution is equivalent to\r
 144 what git would do and is based solely on the current local and remote\r
 145 state and the common ancestor state.  This can lead to unintuitive\r
 146 results if a tag on a message has gone through multiple changes on\r
 147 both hosts since the last sync (though, I argue, there are no\r
 148 intuitive results in such situations).  Tombstones are only required\r
 149 to garbage collect sync state (and other techniques could be used for\r
 150 that).  This also does not depend on time synchronization (though,\r
 151 like any mtime solution, it does depend on mtime monotonicity).  The\r
 152 algorithm would work equally well with sequence numbers.\r
 153 \r
 154 \r
 155 I tried coming up with a third algorithm that used mtimes to resolve\r
 156 tagging conflicts, but without per-tag mtimes it degenerated into the\r
 157 first algorithm.\r