Warning, /pim/trojita/docs/masters/imap-protocol.tex is written in an unsupported language. File is not indexed.

0001 % vim: spelllang=en spell textwidth=120
0002 \documentclass[trojita]{subfiles}
0003 
0004 \begin{document}
0005 
0006 \chapter{IMAP Protocol Essentials}
0007 \label{sec:imap-protocol}
0008 
0009 This chapter provides a gentle introduction to peculiarities of the IMAP protocol and presents an analysis of how its
0010 users can benefit from the unique protocol features.
0011 
0012 \section{IMAP}
0013 
0014 The IMAP protocol, as defined by RFC~3501~\cite{rfc3501}, is an internet protocol suitable for managing e-mail folders
0015 and individual messages stored on a remote mail server.  In contrast to the older POP3 protocol~\cite{rfc1939}, IMAP is
0016 actually intended to serve as an {\em access} protocol.  Where a POP3 client would happily download a full message from
0017 the mail server, store it into a local mailbox and perform all further processing locally, the IMAP mode of operation is
0018 much more complicated.  These complications, however, bring a whole slew of new features and interesting applications
0019 along.
0020 
0021 For one thing, IMAP presents a single authoritative place storing messages --- that feature alone is a must in today's world
0022 where everyone expects to be able to access mail from their cell phones.  Furthermore, given that all messages
0023 are located on a single place, it is possible to perform efficient server-side operations like searching or sorting over
0024 the whole mail store.  IMAP also makes it possible to access individual message parts like attachments separately,
0025 eliminating the need to download a huge message before reading a short accompanying textual information.  Finally,
0026 advanced servers can recognize clients with limited resources and only present a subset of messages to them.
0027 
0028 At the same time, IMAP is an old protocol burdened with many compatibility warts.  Its designers were struggling with
0029 people objecting to novel ideas due to legacy code in their mail implementations.  Over the years, though, various
0030 protocol extensions appeared.  Some of them are extremely useful for contemporary clients, yet cannot be relied upon
0031 as there is no general agreement on what extensions are really crucial, and hence available on most IMAP servers.
0032 
0033 The rest of this chapter provides a quick overview of the basic IMAP concepts and how they relate to the usual client's
0034 workflow.  A detailed introduction to the basic IMAP concepts can be found in my bachelor thesis on this topic
0035 \cite[p. 9 - 19]{jkt-bc-thesis}.
0036 
0037 \subsection{Basic Features}
0038 
0039 An IMAP server exports a set of {\em mailboxes}, folders which contain individual messages (and further mailboxes, if
0040 the server allows that).  Each message can be identified either by its {\em sequence number}, an order in which it
0041 appears in mailbox, or by its {\em UID}.  Sequence numbers are by definition very volatile (deleting the first message
0042 in a mailbox changes sequence numbers of all subsequent messages, for example) while the UIDs provide better chances of
0043 persistence across reconnects.~\footnote{It shall be noted that IMAP does {\em not} guarantee UIDs to be persistent at
0044 all.  The reason behind this decision was to allow IMAP to publish messages from obsolete mail stores which could not
0045 have been extended to support UIDs at all.  Even today, UID changes have to be expected when signalled through {\tt
0046 UIDVALIDITY}.} When the UIDs have to be invalidated for some reason, a per-mailbox integer property {\tt UIDVALIDITY}
0047 is incremented to signal all clients that previously used UIDs are no longer valid.
0048 
0049 \subsection{Cache Filing Protocol}
0050 
0051 As Mark Crispin, the principal author of the IMAP standard, has to
0052 say~\cite{crispin-imap-cache-filing-1}~\cite{crispin-imap-cache-filing-2}, IMAP is a {\em cache filing protocol}.  That
0053 means that whatever the server thinks about a mailbox state is {\em the truth}, and any state stored on the clients can
0054 be invalidated by the server at any time.  This critical design choice has impact on all further operations.  IMAP
0055 clients which do not anticipate such a behavior~\footnote{Such clients are usually called ``POP3 clients converted to
0056 speak IMAP'' on various IMAP-related mailing
0057 lists.~\cite{shannon-imap-clients-glorified-pop}~\cite{crispin-imap-clients-glorified-pop}} are bound to operate in an
0058 inefficient manner or fail in unexpected scenarios.
0059 
0060 The first issue which typically comes up on the {\tt imap-protocol} mailing list is treating UIDs as a persistent
0061 identifier of some kind.  In fact, IMAP guarantees that a triple of (mailbox name, {\tt UIDVALIDITY}, {\tt UID}) will
0062 not refer to {\em any other} message at any time, but there's no guarantee that the very same message, quite possibly in
0063 the same mailbox, will not get another UID in future.~\footnote{People have been trying to solve this issue for quite
0064 some time, but no standardized solution is ready yet.  The recent iterations of these proposals concentrate on providing
0065 a cryptographic hash of a message body, but is far from clear whether doing so would get any traction.  Furthermore, the
0066 hashes are typically too long to serve as the only identifier of a message, so UIDs will definitely be around in
0067 future.}  That said, on reasonable server implementations, the UIDs should not get invalidated too often under normal
0068 circumstances.  Given the IMAP protocol doesn't offer anything else, they are widely used (along with the {\tt
0069 UIDVALIDITY} and when limited to the scope of a single mailbox) as a semi-persistent identification of a message.
0070 
0071 UIDs are assigned to the messages in a strictly monotonic sense, i.e. if message $A$ has a sequence number $seq_A$ and
0072 message $B$ has sequence number $seq_B$ such as $seq_A < seq_B$, it is true that $UID_A < UID_B$.  UID numbers are also
0073 guaranteed to never be reused in the same mailbox, unless the {\tt UIDVALIDITY} changes.
0074 
0075 Due to the facts described above, virtually any IMAP client which maintains a persistent cache of the downloaded data
0076 uses UIDs to assign the cached data to individual messages.  Such an approach leads to a need to maintain a mapping
0077 between the sequence numbers and the UID numbers of all messages in the mailbox --- upon reconnect, clients have to
0078 recognize whether any messages previously available in the mailbox disappeared, and if they did, the clients should
0079 remove the cached data for these messages.~\footnote{The reader shall be reminded that IMAP is a {\em cache filing
0080 protocol}, i.e. the server is always right about what messages ``are'' in a mailbox and what messages are gone.}  This
0081 is in a strong contrast to the usual POP3 mode of operation where the clients are expected to prune their cache only
0082 based on their local policy, perhaps moving older messages to a designated archive, but definitely not discarding the
0083 retrieved data as soon as the server doesn't present the message any longer.
0084 
0085 Furthermore, even during an established session the IMAP server informs about messages being permanently deleted through
0086 the {\tt EXPUNGED} response which contains sequence number only.  Given that the cache is usually addressed by UID, a
0087 caching client shall maintain full UID mapping at any time.
0088 
0089 \section{Mailbox Synchronization}
0090 \label{sec:imap-mailbox-sync}
0091 
0092 When an IMAP client opens a mailbox, the server provides it with a few data points about the state of the mail store.
0093 Among these data, there's a number representing the total amount of messages in the mailbox through the {\tt EXISTS}
0094 response, the current {\tt UIDVALIDITY} value and, finally, the {\tt UIDNEXT} which represents the lowest UID which the
0095 next arriving message could possibly get assigned.  Please note that the {\tt UIDNEXT} is merely a lower bound of the
0096 future UID; there is no guarantee that a message with such UID would ever exist in the mailbox in future.
0097 
0098 Having obtained these three values, the client can perform a few optimizations before it proceeds to fetch an updated
0099 UID mapping from the IMAP server:
0100 
0101 \begin{itemize}
0102   \item If the {\tt UIDVALIDITY} has changed, the client is obliged to completely purge any data which it might have
0103     accumulated in its local persistent cache.  This is a hard requirement allowing the server to inform the client that
0104     no state whatsoever can be reused from the previous connections.  In the real world, this situation shall be only
0105     reached under exceptional circumstances (like when migrating to a completely different server implementation, or
0106     after having to restore the data after an inadvertent damage caused by a reckless system
0107     administrator.~\footnote{The IMAP standard nevertheless allows servers to increment the {\tt UIDVALIDITY} upon each
0108     reconnect to accommodate server implementations which are unable to assign persistent UIDs at all.  It shall be
0109     noted that although such servers are {\em compliant} with the IMAP specification, they offer severely limited user
0110     experience and little room for further optimization --- the clients cannot reuse any data from previous connections,
0111     so the overall efficiency is similar to accessing e-mail through the POP3 protocol.}
0112   \item If {\tt UIDNEXT} is not available, the client has to resort to asking for the whole UID mapping from scratch.
0113   \item If the {\tt UIDNEXT} has decreased, the IMAP server exhibits a bug.  This situation is explicitly forbidden by
0114     the IMAP standard.  Trojitá will, nevertheless, try to work in this scenario by purging its cache and continuing as
0115     if no state was cached locally.
0116   \item If the {\tt UIDNEXT} has not changed since the last time the client has opened the mailbox, the IMAP protocol
0117     says that no messages could have been delivered to the mailbox at all.
0118     \begin{itemize}
0119       \item If the {\tt EXISTS} remains constant as well, it is clear that no deletions have taken place. This means
0120         that the cached sequence $\rightarrow$ UID mapping from the last time is directly usable, and the UID syncing
0121         phase of the mailbox synchronization is concluded.
0122       \item Otherwise, if the {\tt EXISTS} has grown, the client is talking to a non-compliant IMAP server which failed
0123         to adjust either {\tt UIDNEXT} or {\tt UIDVALIDITY}, and cannot assume anything about the server's behavior.
0124         Trojitá will gracefully degrade to a complete UID mapping resynchronization.
0125       \item If the {\tt EXISTS} has decreased, one can be sure that some messages have been deleted.  In this situation,
0126         the client has two possible options on how to proceed:
0127         \begin{itemize}
0128           \item One can try to perform a binary search in the list of messages to find the first deleted message and ask
0129             for UIDs of all messages at the subsequent positions.  This is a heuristics which relies on an observation
0130             that it is more likely for users working with big mailboxes to delete messages at the end of the mailbox.
0131             However, each step in this incremental search requires a complete round trip to the IMAP server over a
0132             network; with a mailbox with tens of thousands of messages, this could lead to 17 round trips.  Given that
0133             real-world cellular networks like the GPRS/EDGE infrastructure, unfortunately still common in the Czech
0134             Republic, exhibit the RTT latencies which can often be larger than one second~\cite{gprs-rtt-report}, such
0135             an approach to incremental synchronization of the UID mapping will have severe impact on the total
0136             synchronization time.
0137           \item Another way is to give up on possible bandwidth reduction possibility and to fetch the complete UID
0138             mapping.
0139         \end{itemize}
0140     \end{itemize}
0141   \item If the {\tt UIDNEXT} has grown, some messages might have arrived into the mailbox.  There's no guarantee that
0142     any of them are still present, though, so the clients could use another set of heuristics:
0143     \begin{itemize}
0144       \item If the increase in {\tt EXISTS} is exactly the same as the growth of the {\tt UIDNEXT}, all of the new
0145         arrivals are still present in the mailbox and no message have been expunged since the last time.  The client can
0146         ask only for UIDs of the new arrivals.
0147       \item In any other case, the situation is very similar to a changed {\tt EXISTS} with constant {\tt UIDNEXT} and
0148         the same possible optimization about the binary search might apply.  Alternatively, clients could fetch a
0149         complete UID mapping.
0150     \end{itemize}
0151 \end{itemize}
0152 
0153 If the decisions described above suggest that at least a part of the UID mapping shall be updated, an IMAP client can
0154 --- in absence of the optional extensions --- use one of the following ways to update the map.  The first one is through
0155 the generic {\tt FETCH} command:
0156 
0157 \begin{minted}{text}
0158   C: y1 UID FETCH 1:* (UID)
0159   S: * 1 FETCH (UID 123)
0160   S: * 2 FETCH (UID 125)
0161   S: * 4 FETCH (UID 127)
0162   S: * 3 FETCH (UID 126)
0163   S: y1 OK Fetched
0164 \end{minted}
0165 
0166 This command simply requests the {\tt FETCH} response containing UID for each and every message in the mailbox.  The
0167 sample results show that the received data are in no particular order and demonstrate that the UID range is not
0168 necessarily continuous.  If the heuristics shows that there is just a subset of messages with unknown UIDs, the sequence
0169 range (the {\tt "1:*"} string in the example above) shall be changed to only refer to the relevant subset, like the {\tt
0170 "last\_uidnext:*"}.  It is also possible to request {\tt FLAGS} (which will be described later on) at this point.
0171 
0172 Alternatively, the {\tt UID SEARCH} command can be used as follows:
0173 
0174 \begin{minted}{text}
0175     C: y1 UID SEARCH UID ALL
0176     S: * SEARCH 123 125 127 126
0177     S: y1 OK search completed
0178 \end{minted}
0179 
0180 As one can see, the {\tt SEARCH} response is much more compact.  In practice, the bandwidth saving is slightly lower as
0181 the UID discovery and {\tt FLAGS} synchronization can be merged into a single {\tt FETCH} command, but the overhead is
0182 still at least four bytes for each message in the mailbox,~\footnote{If the {\tt FLAGS} are fetched as well, the real
0183 overhead is just the {\tt "UID<space>"} string --- the number and its trailing space is present in the {\tt SEARCH}
0184 response as well and the overhead of the {\tt FETCH} response format is required for the updated flags anyway.} which
0185 leads to at least 200~kB of useless data on a mailbox with fifty thousands of messages.
0186 
0187 \subsection{Message Flags}
0188 
0189 I have mentioned message flags when describing the mailbox synchronization.  These flags allow the system and the mail
0190 user to attach a certain state to the messages --- information like whether the message has been read or replied to is
0191 tracked at this level.  Further applications include user-level arbitrary tagging of messages with flags like
0192 ``important'' or ``todo''.
0193 
0194 Strictly speaking, asking for message flags of all messages in a mailbox is not necessary, provided the program is
0195 capable of lazy-loading --- flags could, for example, only be fetched for those messages which are immediately visible on
0196 screen (probably with some intelligent preload of items which will likely get to the viewport in near future), avoiding
0197 a potentially expensive operation.  On the other hand, contemporary user agents typically have to display an aggregated
0198 statistics like ``$X$ unread messages, $Y$ total'' to the user.  IMAP certainly has methods for delivering such
0199 statistics, however, the baseline specification's only two ways of conveying that information are through the {\tt
0200 STATUS} command or via an explicit {\tt SEARCH}.  In practice, this design leads to a pressing need to load {\em all}
0201 flags for all messages at the start of the session.
0202 
0203 The problem with the {\tt STATUS} command is that it is unfortunately forbidden from being used on an actively selected
0204 mailbox~\cite[p. 43]{rfc3501}.  That makes this command usable for an initial estimate, but prevents further updates --- consider
0205 that an IMAP client has opened a big mailbox and scrolled to the end of the message listing.  Suddenly, an {\tt *
0206 EXPUNGE 3} arrives, informing the client that the third message in the mailbox is now gone.  Because the flags of those
0207 ``older'' messages haven't been loaded in this scenario, the client has no way of knowing whether the number of unread
0208 messages shall be updated.  At this point, the client has no choice but to explicitly ask for message flags of all
0209 messages or conduct a special {\tt SEARCH}.  The {\tt SEARCH} command looking for unread messages (or for any set of
0210 messages tagged with a certain flag, for that matter) can surely be constructed, even the baseline IMAP4rev1 provides a
0211 way of requesting that information.  However, each {\tt SEARCH} only provides the client with an information about one
0212 kind of a particular flag.  It is not an unreasonable idea to design a client with further development in mind, most
0213 notably it might make a lot of sense not to special-case the {\tt {\textbackslash}UnSeen} message flag --- after all, certain
0214 applications will benefit from having access to all messages matching the {\tt \$SubmitPending} flag or those which were
0215 marked as a ``Draft'' by the user, for example.  Unfortunately, statistics about these user-defined flags cannot be
0216 determined via the {\tt STATUS} command and have to be discovered explicitly, either through a lot of separate {\tt
0217 SEARCH} commands, one for each ``interesting'' flag, or via an explicit synchronization through the {\tt FETCH (FLAGS)}
0218 command.
0219 
0220 In short, deferring the flag synchronization certainly has some merit, but at the same time, special-casing the {\tt
0221 {\textbackslash}UnSeen} flag for unread messages is not a viable long-term solution.  Given that extensions designed for
0222 speeding up the flags resynchronization exist, Trojitá will always ask for a full flags mapping when synchronizing
0223 through the baseline IMAP profile.
0224 
0225 \subsection{Immutable Data}
0226 \label{sec:imap-immutable-data}
0227 
0228 In the previous sections, I have spoken about data which have to be resynchronized during each reconnect to the mailbox,
0229 be it message flags or the UIDs.  Other data available through IMAP are, however, immutable by nature.  Examples of
0230 these data are message headers or the individual body parts.
0231 
0232 IMAP is pretty unique in allowing its implementors to dissect a MIME message~\cite{rfc2045} into individual body parts.
0233 In practice, this is a very useful feature --- clients can read a short textual body of a message before deciding whether
0234 to download a big binary attachment etc.  On the other hand, it requires servers to include a full MIME parser.  Some of
0235 them, notably the Google's GImap, have been struggling with this requirement for many
0236 years~\cite{gmail-bodystructure-sucks}.
0237 
0238 IMAP defines a data structure called {\tt ENVELOPE} containing some of the most interesting headers from the
0239 RFC~2822~\cite{rfc2822} message.  Among them, the {\tt Subject}, {\tt Date}, {\tt From}, {\tt Sender}, {\tt Reply-To},
0240 {\tt To}, {\tt Cc}, {\tt Bcc}, {\tt In-Reply-To} and {\tt Message-Id} are included.  Unfortunately, the {\tt References}
0241 header is missing.~\footnote{The {\tt References} header is useful when the client wants to be as compatible as possible
0242 with the other agents that deal with message threading.  Strictly speaking, the {\tt Message-Id} and {\tt In-Reply-To}
0243 headers are sufficient for some forms of threading, but MUAs should strive to be ``good citizens'' and support the {\tt
0244 References} header as well.}  Even with this omission, the {\tt ENVELOPE} is useful for clients which do not necessarily
0245 have to include RFC~2822-style header parsing code.  However, this usefulness is unfortunately further limited by not
0246 including an RFC~2047~\cite{rfc2047} decoder, so non-ASCII data in fields like senders' human readable names or in the
0247 subject field have to be decoded by the clients.
0248 
0249 \section{Protocol Design}
0250 
0251 The baseline version of IMAP, as defined in RFC~3501~\cite{rfc3501}, contains a few features which limit its performance
0252 by a fair amount.  One example of these features are IMAP's {\em synchronizing literals}.
0253 
0254 Before the client is allowed to send a big amount of data to the server, it has to ask for its explicit permission via a
0255 continuation request.  While such an idea is good on paper (and is probably intended to {\em save bandwidth} by allowing
0256 the server to refuse huge uploads before the client sends them), in reality this leads to rather slow operation because
0257 each transmission requires a full roundtrip over the network.  Fortunately, extensions like the {\tt LITERAL+} (see
0258 \secref{sec:imap-literalplus}) have eliminated this bottleneck.
0259 
0260 Another manifestation of a situation which could potentially use an improvement is the protocol's requirement on clients
0261 to accept any response at any time,~\footnote{{\tt ``The client MUST be prepared to accept any response at all
0262 times.''}~\cite[p. 61]{rfc3501}} which is not applied consistently --- the same RFC also mandates that the servers
0263 cannot send {\tt EXPUNGE} when no command is in progress~\cite[p. 72]{rfc3501}.  This particular wording certainly has
0264 merits (it encourages client implementors to {\em really} accept anything at any time) and is required for proper
0265 synchronization --- if {\tt EXPUNGE}s were allowed when no command was in progress and a client issued a {\tt STORE}
0266 command referencing a message through its sequence number, that action could affect a completely different message.
0267 This design is probably required due to the old decision to support addressing through both sequence numbers and UIDs,
0268 but has a side effect of requiring constant polling for mailbox updates.  Again, extensions have emerged (see
0269 \secref{sec:imap-idle}) which try to eliminate this drawback through a special mode.
0270 
0271 \subsection{Additional Server-Side Features}
0272 
0273 Having all messages available without much effort (or, certainly with much less effort than a client), servers are in a
0274 unique position to make certain operations smoother, faster and more efficient than performing on the client side.
0275 
0276 The baseline IMAP specification contains provisions for server-side searching.  Features notably missing, however, are
0277 server-side sorting and conveying information about message threading~\footnote{Message {\em threading} refers to a
0278 mechanism which allows graphical user agents to present related messages together.  Recently re-branded as
0279 ``conversations'', threading is in fact a pretty old idea which builds on the {\tt Message-Id}, {\tt References} and
0280 {\tt In-Reply-To} headers, or, in its crudest form, just on similarity of message subjects.  Threading presents the
0281 human with a tree of messages where each immediate child of a particular node represents a reply to the parent message.}
0282 which are available through optional extensions.
0283 
0284 Certain scenarios (like having a cell phone with severely limited resources) could benefit from server-side content
0285 conversion, similar to how the Opera Mobile browser converts images to low-resolution versions for display on the
0286 phone's screen.  An extension for just that exists, but its support is rather scarce among the IMAP servers --- in fact,
0287 the author of this thesis was not able to find a single reasonably-deployed server which would offer such a feature.
0288 
0289 At the same time, the overall design of the IMAP protocol is rather promising; it allows executing commands in
0290 parallel through pipelining and even the most basic profile provides enough features to implement a reasonably efficient
0291 client which can maintain its state over reconnects.  It is therefore reasonable to start with the existing state and
0292 try to build upon its solid foundation, improving the whole experience in the process.
0293 
0294 \end{document}