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}