MBOX-Line: From dave at cridland.net  Fri Jan 21 00:46:45 2011
To: imap-protocol@u.washington.edu
From: Dave Cridland <dave@cridland.net>
Date: Fri Jun  8 12:34:45 2018
Subject: [Imap-protocol] UIDNEXT updates upon new message arrival
In-Reply-To: <4D38DE97.6060509@gentoo.org>
References: <4D385AB5.90208@gentoo.org> <28835.1295567529.285091@puncture>
	<4D38DE97.6060509@gentoo.org>
Message-ID: <28835.1295599605.789384@puncture>

On Fri Jan 21 01:17:11 2011, Jan Kundr?t wrote:
> On 01/21/11 00:52, Dave Cridland wrote:
> > You're describing (a slightly broken version of) Polymer's sync  
> algorithm.
> >
> > See https://github.com/dwd/Polymer/blob/master/infotrope/imap.py  
> around
> > line 3611, and also line 3800.
> 
> Thank you, I've read various docs at your web a few years ago. It's
> possible that the EXISTS/UIDNEXT thing was there back then. I wasn't
> able to find it today, but I'm sure I've read various things which
> aren't there anymore.
> 
> Could you please mention what is broken in what I described,  
> though? It
> isn't obvious from a quick glance at your source code. (I've already
> found that you sort the response to the UID SEARCH command locally,  
> but
> that isn't related to this question. Fixed now, thanks.)
> 
> 
Your technique might not be broken, but it's not clear to me that it  
isn't.


> > No, but that's okay. If N messages arrive, UIDNEXT must increase  
> by a
> > minimum of N. In fact, if N messages arrive, UIDNEXT will in all
> > likelyhood increase by precisely N. I can conceive of edge cases  
> where
> > it increases by more than N in a reasonable implementation, but  
> they're
> > unlikely. So just add one for each new message that you're told  
> about
> > during a session. (ie, each time you're told about an increase to
> > EXISTS, add the difference to your UIDNEXT).
> 
> Yes, but reading threads about people adding a fake EXISTS/EXPUNGE  
> pair
> to the IDLE, just to make Outlook happy, scares me. I can't think  
> of a
> situation where this extra increment would break anything, but  
> maybe I'm
> just missing something -- that's why I'm asking.
> 
> 
In the case where an EXISTS/EXPUNGE pair is done such that no UIDNEXT  
increment occurs, the server is broken. Still, the algorithm works -  
you just find that the UIDNEXT isn't where you expected it to be.


> >> I do not support QRESYNC yet.
> >
> > You should do - it's effectively the same sync algorithm, but  
> changed to
> > take advantage of the server's knowledge instead - so the  
> complicated
> > selection is done by the server.
> 
> Yes, it's just a matter of making sure that I have the basic
> functionality well-tested and covered by test cases before I build a
> more complicated setup on top of it.
> 
> 
Oh, sure. Just build your code with QRESYNC in mind. Or, alternately,  
build QRESYNC with your code in mind, which is what I did.


> > Polymer doesn't do a binary search, by the way - it fetches  
> chunks of
> > 1000 UIDs at once, and has an amusing algorithm to decide how many
> > chunks to fetch, depending on whether ESEARCH is used (which'll  
> help you
> > hugely) and how sparse the UID mapping is. For finding a UID in  
> the
> > mapping, it actually does a successive approximation technique,  
> on the
> > assumption that the map is uniformly sparse, which works pretty  
> well -
> > usually it find the right chunk in its first guess.
> >
> > For resync purposes, if there have been expunges, it discards and
> > refetches just the last block - because generally expunges will  
> happen
> > in the recent portion of the mailbox - and if the beginning of  
> the newly
> > fetched UID block matches the beginning of the one it's  
> replacing, the
> > UID map is now synchronized.
> 
> I'm assuming that these chunks are always 1000 items in length (ie.  
> they
> cover 1000 messages, or 1000 sequence numbers), and therefore your
> blocks start at message #1, #1001, #2001 etc, is that right? That  
> indeed
> looks like a nice optimization, albeit with a similar latency  
> tradeoff.

Yeah, it leans toward saving bandwidth, more than round-trips, but  
ESEARCH means it's fetching multiple blocks at once (typically the  
entire mailbox, since it figures out how many holes are likely to  
exist, and bigger mailboxes have fewer expunges, I find).

Dave.
-- 
Dave Cridland - mailto:dave@cridland.net - xmpp:dwd@dave.cridland.net
  - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
  - http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade

