ac/9742f2b8a9d96a1b02a4ebdf27fbe769216b84

   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 5AD0B431FD0\r
   6         for <notmuch@notmuchmail.org>; Tue, 20 Dec 2011 07:03:57 -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 r-2MZINkMl77 for <notmuch@notmuchmail.org>;\r
  16         Tue, 20 Dec 2011 07:03:56 -0800 (PST)\r
  17 Received: from dmz-mailsec-scanner-5.mit.edu (DMZ-MAILSEC-SCANNER-5.MIT.EDU\r
  18         [18.7.68.34])\r
  19         by olra.theworths.org (Postfix) with ESMTP id 99C8A431FB6\r
  20         for <notmuch@notmuchmail.org>; Tue, 20 Dec 2011 07:03:56 -0800 (PST)\r
  21 X-AuditID: 12074422-b7fd66d0000008f9-fd-4ef0a3db0c27\r
  22 Received: from mailhub-auth-2.mit.edu ( [18.7.62.36])\r
  23         by dmz-mailsec-scanner-5.mit.edu (Symantec Messaging Gateway) with SMTP\r
  24         id C8.D7.02297.BD3A0FE4; Tue, 20 Dec 2011 10:03:56 -0500 (EST)\r
  25 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103])\r
  26         by mailhub-auth-2.mit.edu (8.13.8/8.9.2) with ESMTP id pBKF3swd018335; \r
  27         Tue, 20 Dec 2011 10:03:55 -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 pBKF3q2n025101\r
  32         (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT);\r
  33         Tue, 20 Dec 2011 10:03:53 -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 1Rd1FX-0004bN-Vv; Tue, 20 Dec 2011 10:05:04 -0500\r
  37 Date: Tue, 20 Dec 2011 10:05:03 -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: <20111220150503.GE10376@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         <20111219194821.GA10376@mit.edu>\r
  45         <cun8vm7zlqv.fsf@hotblack-desiato.hh.sledj.net>\r
  46 MIME-Version: 1.0\r
  47 Content-Type: text/plain; charset=us-ascii\r
  48 Content-Disposition: inline\r
  49 In-Reply-To: <cun8vm7zlqv.fsf@hotblack-desiato.hh.sledj.net>\r
  50 User-Agent: Mutt/1.5.21 (2010-09-15)\r
  51 X-Brightmail-Tracker:\r
  52  H4sIAAAAAAAAA+NgFuphleLIzCtJLcpLzFFi42IRYrdT0b2z+IOfwYqdTBb77mxhsrh+cyaz\r
  53         xb5+fwdmj13P/zJ5PFt1i9ljyqy57AHMUVw2Kak5mWWpRfp2CVwZ8ye9ZCr4oVjx7j97A+N1\r
  54         qS5GTg4JAROJy5uXM0LYYhIX7q1n62Lk4hAS2McoMX/5T3YIZwOjxIM7O5khnJNMEoduLWIH\r
  55         aRESWMIosXJHEYjNIqAq0TDjBROIzSagIbFtP8RYEQFFif/fVoDVMws4SKw82QtmCws4S2z+\r
  56         uZMVxOYV0JHovPKaCWLBGUaJOds/M0MkBCVOznzCAtGsJXHj30ugIg4gW1pi+T8OkDCngI3E\r
  57         yqeTwfaKCqhITDm5jW0Co9AsJN2zkHTPQuhewMi8ilE2JbdKNzcxM6c4NVm3ODkxLy+1SNdU\r
  58         LzezRC81pXQTIzjQXZR2MP48qHSIUYCDUYmHd2XTez8h1sSy4srcQ4ySHExKorwnF37wE+JL\r
  59         yk+pzEgszogvKs1JLT7EKMHBrCTCe6wFKMebklhZlVqUD5OS5mBREudV13rnJySQnliSmp2a\r
  60         WpBaBJOV4eBQkuCVAUa0kGBRanpqRVpmTglCmomDE2Q4D9Bwf5Aa3uKCxNzizHSI/ClGRSlx\r
  61         XieQhABIIqM0D64XloheMYoDvSLM6wNSxQNMYnDdr4AGMwEN3uYMNrgkESEl1cDIO79h5fP3\r
  62         O+/9lcuTZJVq71GfNr/PuqBswV+HM6qX7rSfa1zvdvx8wqmn/at+r1nNcT3Ny2zWW8/25fOW\r
  63         OxpIb3iVI2r6TqdToPBRhWuKa9CDSyWK/YvFNk768vz6XBfO7+1zzi/caaY3h3Gny7kH0kdr\r
  64         jYJ7drK1tBzY9eod327RLwudz/gkKrEUZyQaajEXFScCAH+5yf8fAwAA\r
  65 Cc: notmuch@notmuchmail.org\r
  66 X-BeenThere: notmuch@notmuchmail.org\r
  67 X-Mailman-Version: 2.1.13\r
  68 Precedence: list\r
  69 List-Id: "Use and development of the notmuch mail system."\r
  70         <notmuch.notmuchmail.org>\r
  71 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  72         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  73 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  74 List-Post: <mailto:notmuch@notmuchmail.org>\r
  75 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  76 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  77         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  78 X-List-Received-Date: Tue, 20 Dec 2011 15:03:57 -0000\r
  79 \r
  80 Quoth David Edmondson on Dec 20 at  8:32 am:\r
  81 > > == Two-way "merge" from host R to host L ==\r
  82 > > \r
  83 > > Per-host state:\r
  84 > > - last_mtime: Map from remote hosts to last sync mtime\r
  85 > \r
  86 > With the proposed changes it seems that the state required on each host\r
  87 > would live within the Xapian database (to be extracted with 'dump').\r
  88 \r
  89 It certainly could.  I haven't thought about how any of this would\r
  90 integrate with dump, or if it necessarily should.  A related question\r
  91 is how bootstrap should work.  For example, if you add another host,\r
  92 what's the best way to bring it up to speed without, say, overwriting\r
  93 your tags everywhere with your initial tags?  In general, when a new\r
  94 message arrives, how do you get the hosts to agree on its tags and\r
  95 what happens if one host tags it before another host sees it?\r
  96 \r
  97 > > new_mtime = last_mtime[R]\r
  98 > > For msgid, mtime, tags in messages on host R with mtime >= last_mtime[R]:\r
  99 > >   If mtime > local mtime of msgid:\r
 100 > >     Set local tags of msgid to tags\r
 101 > >   new_mtime = max(new_mtime, mtime)\r
 102 > > last_mtime[R] = new_mtime\r
 103 > > \r
 104 > > This has the advantage of keeping very little state, but the\r
 105 > > synchronization is also quite primitive.  If two hosts change a\r
 106 > > message's tags in different ways between synchronizations, the more\r
 107 > > recent of the two will override the full set of tags on that message.\r
 108 > > This does not strictly require tombstones, though if you make a tag\r
 109 > > change and then delete the message before a sync, the tag change will\r
 110 > > be lost without some record of that state.\r
 111 > \r
 112 > Does this matter? If the tag on a deleted message is changed, does\r
 113 > anyone care?\r
 114 \r
 115 That depends on what sort of synchronization model you're expecting.\r
 116 If you're expecting git-style synchronization where all that matters\r
 117 is the state and not the order things happened in, then this is\r
 118 exactly what you'd expect.  If you're expecting something more nuanced\r
 119 that knows about the order you did things in across hosts between\r
 120 synchronizations (which I think can only lead to more unintuitive\r
 121 corner-cases, but some people seem to expect), then this could be\r
 122 surprising.\r
 123 \r
 124 > > Also, this obviously depends heavily on synchronized clocks.\r
 125 > > \r
 126 > > \r
 127 > > == Three-way merge from host R to host L ==\r
 128 > > \r
 129 > > Per-host state:\r
 130 > > - last_mtime: Map from remote hosts to last sync mtime\r
 131 > > - last_sync: Map from remote hosts to the tag database as of the last sync\r
 132 > \r
 133 > Any ideas where this state might be kept?\r
 134 \r
 135 It could also be stored in Xapian (in user keys or as additional\r
 136 message metadata).  That would certainly be simplest and would avoid\r
 137 hairy atomicity issues.  OTOH, it's not the end of the world if\r
 138 last_sync doesn't get updated atomically, especially if we can at\r
 139 least guarantee last_sync is fully updated and on disk before we\r
 140 update last_mtime.\r
 141 \r
 142 > > new_mtime = last_mtime[R]\r
 143 > > for msgid, mtime, r_tags in messages on host R with mtime >= last_mtime[R]:\r
 144 > >   my_tags = local tags of msgid\r
 145 > >   last_tags = last_sync[R][msgid]\r
 146 > >   for each tag that differs between my_tags and r_tags:\r
 147 > >     if tag is in last_tags: remove tag locally\r
 148 > >     else: add tag locally\r
 149 > >   last_sync[R][msgid] = tags\r
 150 > >   new_mtime = max(new_mtime, mtime)\r
 151 > > Delete stale messages from last_sync[R] (using tombstones or something)\r
 152 > > last_mtime[R] = new_mtime\r
 153 > > \r
 154 > > This protocol requires significantly more state, but can also\r
 155 > > reconstruct per-tag changes.  Conflict resolution is equivalent to\r
 156 > > what git would do and is based solely on the current local and remote\r
 157 > > state and the common ancestor state.  This can lead to unintuitive\r
 158 > > results if a tag on a message has gone through multiple changes on\r
 159 > > both hosts since the last sync (though, I argue, there are no\r
 160 > > intuitive results in such situations).  Tombstones are only required\r
 161 > > to garbage collect sync state (and other techniques could be used for\r
 162 > > that).  This also does not depend on time synchronization (though,\r
 163 > > like any mtime solution, it does depend on mtime monotonicity).  The\r
 164 > > algorithm would work equally well with sequence numbers.\r
 165 > > \r
 166 > > I tried coming up with a third algorithm that used mtimes to resolve\r
 167 > > tagging conflicts, but without per-tag mtimes it degenerated into the\r
 168 > > first algorithm.\r
 169 > \r
 170 > dme.\r