forked from jmapio/jmap
-
Notifications
You must be signed in to change notification settings - Fork 1
/
server.html
387 lines (300 loc) · 21.3 KB
/
server.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<link href='http://fonts.googleapis.com/css?family=Open+Sans:400italic,400,700' rel='stylesheet' type='text/css'>
<link href="main.css" rel="stylesheet" type="text/css">
<title>JSON Mail Access Protocol Specification (JMAP)</title>
</head>
<body>
<header>
<div id="logo">JMAP</div>
<ul id="nav">
<li class="nav-item"><a class="nav-link" href="index.html">Intro</a></li>
<li class="nav-item"><a class="nav-link" href="spec.html">The Spec</a> </li>
<li class="nav-item"><a class="nav-link" href="client.html">Using JMAP</a></li>
<li class="nav-item"><a class="nav-link" href="server.html">Implementing JMAP</a></li>
</ul>
<a id="github" href="https://github.com/neilj/jmap"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_darkblue_121621.png" alt="Fork me on GitHub"></a>
</header>
<article>
<h1>Advice for JMAP implementors</h1>
<p>This document describes a recommended set of data structures and algorithms for efficiently implementing JMAP. It is intended to serve as suggestions only. There may well be better ways of implementing JMAP. The spec is the authoritative guide on what constitutes a conformant JMAP implementation.</p>
<h2>Assigning Message Ids</h2>
<p>A good way of assigning a message id is to sha1 the RFC2822 message and take the first 80 bits (this is sufficient for avoiding collisions in any reasonable sized instance, but the server may choose any length it likes). If this is already in use (i.e. another copy of the message already exists), sha1 the GUID. Repeat until there is no collision. The bytes can be represented in any reasonable encoding for transmission as a <code>String</code> within the API.</p>
<h2>Modification sequences</h2>
<p>A modification sequence, or <strong>modseq</strong>, is a 63-bit monotonically incrementing counter. Each user has their own modseq counter (in IMAP it’s originally per-mailbox, but per user is backwards compatible with this). Every time a change occurs to data within the user, the modseq is incremented by one and the new value is associated with the changes. This is used in a number of data structures and algorithms below to efficiently calculate changes.</p>
<h2>Data structures</h2>
<p>As ever in programming, get your data structures right and the server will practically write itself.</p>
<p>There are three types of data structures suggested in this guide (excluding the email indexing for search, which is more complicated than this guide is prepared to go into):</p>
<ol>
<li>A <strong>Map</strong> (associative array) of id to variable-length data blob:
<ul>
<li>Insert should be O(1).</li>
<li>Lookup should be O(1).</li>
<li>Delete should be O(1).</li>
<li>Not ordered, but we need to be able to iterate over all the values.</li>
</ul>
</li>
<li>An <strong>append-only log</strong> of variable length blobs:
<ul>
<li>Insert is only at tail.</li>
<li>Lookup needs to be able to binary search (based on modseq) to find start location, then read sequentially.</li>
<li>Delete is only at head.</li>
</ul>
</li>
<li>An <strong>Ordered list</strong> of fixed-si** objects:
<ul>
<li>Insert is mainly at or near the head, but can be in a random location.</li>
<li>Want to be able to read sequentially from head (common case), or read whole structure into memory and sort.</li>
<li>Delete is mainly near head, but can be in a random location.</li>
</ul>
</li>
</ol>
<h3>1. User</h3>
<p>This is a simple collection of important top-level values for the user (kept in a <strong>Map</strong>):</p>
<ul>
<li>Highest ModSeq for the user (<code>63 bits</code> for IMAP compat)</li>
<li>Highest ModSeq of any Mailbox.</li>
<li>Low watermark ModSeq for Thread Log <code>63 bits</code> – whenever the thread log (see below) is truncated, the modseq of the new first item in the log is stored here. Any attempt to call <em>getThreadUpdates</em> with a modseq lower than this must be rejected with a <code>cannotCalculateUpdates</code> error.</li>
<li>Low watermark ModSeq for Message Log <code>63 bits</code> – the same, but for the message log.</li>
<li>Quota available in bytes (63 bits. -1 => Don’t care)</li>
<li>Quota used in bytes <code>63 bits</code></li>
<li>List of other users with mailboxes made available to this user (shared mailboxes) (var length).</li>
</ul>
<h3>2. Mailboxes</h3>
<p>A map of Mailbox Id to all of the mailbox object values (as defined in the spec, including the counts). For the purposes of calculating <code>getMailboxUpdates</code>, also include the following for each mailbox:</p>
<ul>
<li><strong>Mailbox ModSeq</strong> <code>63 bits</code> Updated when any of the mailbox properties (as defined in the spec) change – not updated when the mailbox message list changes.</li>
<li><strong>Mailbox Non-Counts ModSeq</strong> <code>63 bits</code> Updated when any of the mailbox properties that are not counts change. When calculating <code>getMailboxUpdates</code>, if this is lower than the previous mod seq, but the Mailbox ModSeq is higher, then only counts have changed.</li>
<li><strong>Message list UID Next</strong> <code>32 bits</code> The next UID (incrementing 32-bit counter) to assign to messages added to the mailbox message list.</li>
<li><strong>Message list highest ModSeq</strong> <code>63 bits</code> The highest ModSeq of a message in the mailbox message list.</li>
<li><strong>Low watermark message list ModSeq</strong> <code>63 bits</code> Whenever a message is undeleted via IMAP (that is the \Deleted flag is removed) or a deleted message is fully expunged from the mailbox message list (see message list data structure below), set this to the ModSeq of that message if higher than the previous value. Any attempt to call <em>getMessageListUpdates</em> with a modseq lower than this must be rejected with a <code>cannotCalculateUpdates</code> error.</li>
</ul>
<p>The suggested way to assign a Mailbox id is to use an incrementing counter. 16 bits should be sufficient, giving support for a maximum of 65536 mailboxes per user. Old ids are reusable without penalty while keeping with the JMAP semantics. Over the wire this would be represented as a prefix plus an encoding of the number, e.g. “m1”, “m2” etc.</p>
<h3>3. Mailbox message list</h3>
<p>One of these should exist for each mailbox. It is an ordered list of fixed size objects. Each object is:</p>
<ul>
<li><strong>UID</strong> <code>32 bits</code> As per IMAP semantics, this increments each time you append a message to the mailbox. The next UID to use is stored in the Mailbox object.</li>
<li><strong>ModSeq</strong> <code>63 bits</code> As per IMAP semantics, this is updated whenever any property of the message changes.</li>
<li><strong>Message Id</strong> <code>80 bits</code> This is the ID always used within JMAP to refer to the message, and does not change as it moves between mailboxes.</li>
<li><strong>Thread Id</strong> <code>64 bits</code></li>
<li><strong>Deleted</strong> <code>64 bits</code> Time stamp from epoch of when the message was removed the mailbox. <code>0</code> means not deleted. See below</li>
<li><strong>Message Date</strong> <code>64 bits</code></li>
</ul>
<p>Given that most message list fetches are of the first section of a single mailbox in date descending order, if we keep it stored in this order on disk we can just read the first few bytes to return the desired information; no sorting required (we don’t even have to look up anything in the message cache). The date is included in each record so we can insert a new one in the correct position without having to reference any other data.</p>
<p>When a message is removed from the mailbox we don’t remove it immediately from the message list. Instead we just set the Deleted field to the time stamp of when it was deleted. This allows the delta update algorithm to work to efficiently update the client to the new list state. At certain intervals (either based on how many deleted nodes there are or how long since they were deleted) this needs to be cleaned up and the deleted objects fully expunged from the message list. At this point the low watermark ModSeq needs to be updated on the Mailbox data structure.</p>
<h3>4. Message cache</h3>
<p>A map of Message Id to flags, mailboxes and common header information for that message (variable length). This lets the server optimise calls to <code>getMessages</code> that only fetch this information (common when fetching the required information for a mailbox listing). It also allows optimisation of <code>getMessageList</code> as most, even quite complex filters will only require checking this cache (which should be relatively fast) rather than looking up and parsing the whole message (which could be quite slow).</p>
<p>For each message, store:</p>
<ul>
<li><strong>isUnread</strong> <code>1 bit</code> (mutable)</li>
<li><strong>isFlagged</strong> <code>1 bit</code> (mutable)</li>
<li><strong>isAnswered</strong> <code>1 bit</code> (mutable)</li>
<li><strong>isDraft</strong> <code>1 bit</code> (mutable by IMAP)</li>
<li>Other flags + labels + annotations as needed for IMAP compat only. (mutable)</li>
<li><strong>Mailboxes</strong> (list of mailbox ids this message belongs to) (mutable)</li>
<li><strong>From</strong> header (either in the JSON used by JMAP, or whatever IMAP needs)</li>
<li><strong>To</strong> header (either in the JSON used by JMAP, or whatever IMAP needs)</li>
<li><strong>Subject</strong> header</li>
<li><strong>Date</strong></li>
<li><strong>Preview</strong> (see spec)</li>
<li><strong>Attachments</strong> (list of file names only; also used for hasAttachments)</li>
<li><strong>GUID</strong> (sha1 of raw email)</li>
</ul>
<h3>5. Message index</h3>
<p>For searching messages at any reasonable speed, an index is required from textual content within the message to the message id. Describing how this should work is beyone the scope of this guide.</p>
<h3>6. Messages</h3>
<p>A map of GUID (sha1 of the message contents) to the raw RFC2822 message itself. This is the bulk of the data to be stored for each user. As this data is immutable and referenced by its sha1, there are many possibilities for how to store it. Each message ould be stored as a separate file using its GUID as the name. Or on a separate networked object store etc. etc.</p>
<h3>7. Message log</h3>
<p>An append only log of changes made to the message cache. Each entry consists of:</p>
<ul>
<li><strong>ModSeq</strong> of change <code>63 bits</code></li>
<li>List of <strong>Message ids</strong> which were affected by the change (to save extra lookups when the client is fetching these changes, should probably include a bit to say whether the message was destroyed by the change or created/modified).</li>
</ul>
<p>Periodically, truncate the log by chopping records off the beginning. At this point you need to update the low watermark ModSeq for the log in the User object (data structure 1).</p>
<h3>8. Threads</h3>
<p>A map of thread id to an object containing information about the thread (variable length). The information stored for each thread is:</p>
<ul>
<li>The <strong>list of messages</strong> belonging to the thread, sorted in date order. For each - message we need to store:
<ul>
<li><strong>Message Id</strong> <code>80 bits</code></li>
<li><strong>Mailboxes</strong> The list of mailboxes the message belongs to. For sorting a message list by thread unread/thread flagged purposes only.</li>
<li><strong>isUnread</strong> <code>1 bit</code> For sorting a message list by thread unread/thread flagged purposes only.</li>
<li><strong>isFlagged</strong> <code>1 bit</code> For sorting a message list by thread unread/thread flagged purposes only.</li>
</ul>
</li>
<li><strong>ModSeq of last change</strong> to isRead/isFlagged for any message in the thread (for sorting a message list by thread unread/thread flagged purposes only).</li>
<li><strong>Sha1 of subject</strong> after stripping Fwd/Re etc. (for checking whether we need to split a new conversation out later; see threading algorithm in data structure 10).</li>
</ul>
<h3>9. Thread log</h3>
<p>An append only log of changes made to the <strong>membership</strong> of threads (in data structure 7; changes to only the isRead/isFlagged/Mailboxes of a message in a thread do not need to go in the log). Each entry consists of:</p>
<ul>
<li><strong>ModSeq</strong> of change</li>
<li><strong>List of thread ids</strong> which were affected by the change (to save extra lookups when the client is fetching these changes, should probably include a bit to say whether the thread was destroyed by the change or created/modified).</li>
</ul>
<p>As with the message log, periodically truncate the log by chopping records off the beginning; at this point you need to update the low watermark ModSeq for the log in the user object.</p>
<h3>10. Refs to ThreadId</h3>
<p>This is solely used to look up the conversation to assign to a message on creation/import/delivery. Maps the RFC2822 Message Id (eughh, so many different types of id!) to the thread id.</p>
<p>The suggested rule for connecting messages into threads is this:</p>
<p>If two messages share a common RFC2822 Message Id in the set of such ids within the <code>Message-Id</code>, <code>References</code> and <code>In-Reply-To</code> headers of each message, and the messages have the same <code>Subject</code> header (after stripping any preceeding Re:/Fwd: and trimmming white space from either end), then they should belong in the same thread. Otherwise they should belong in different threads.</p>
<h2>Message List Algorithms</h2>
<p>The <code>state</code> property to return with getter calls to each type is:</p>
<ul>
<li>Mailbox: Highest ModSeq of any Mailbox (stored in the User object)</li>
<li>MessageList: Message list UID Next + Message list highest ModSeq (as stored on the Mailbox object). For message lists that aren’t just a mailbox, the state string should be the highest message ModSeq (as found at the tail of the Message Log).</li>
<li>Thread: The highest modseq found at the end of the Thread Log.</li>
<li>Message: The highest modseq found at the end of the Message Log.</li>
</ul>
<h3>getMailboxUpdates</h3>
<p>Simply iterate through the set of Mailboxes comparing their current mod seqs to the client mod seq. If higher, the mailbox has changed. If the non-counts is not higher, only counts have changed.</p>
<h3>getMessageList</h3>
<p>First you need to get the complete list. In the common case of…</p>
<pre><code>filter == { inMailboxes: [ 'inboxId' ], notInMailboxes: [ 'trashId' ] }
</code></pre>
<p>…you are simply fetching the list of messages in a mailbox. This list is already pre-calculated for each mailbox and kept on disk (data structure 3). You can simply slurp this into memory and sort if needed (again, in the common case of sorting date-descending, it will be pre-sorted).</p>
<p>If the filter is more complex, you will need to do more work to get the set of matching messages and sort it. If there is a <code>String</code> component to the filter, first use the message index (data structure 5) to get a set of matches. Then iterate through and lookup each match in the message cache (data structure 4) to apply any other components of the filter. Finally sort as specified.</p>
<p>Once you have the complete message list, you can calculate the results to return to the client. Since a client is likely to fetch a different portion of the same message list soon after, it is beneficial if the server can keep the last list requested by the user in a cache for a short time.</p>
<pre><code>let collapseThreads = args.collapseThreads
let position = args.position
let anchor = args.anchor
let anchorOffset = args.anchorOffset
let limit = args.limit
let total = 0
let messageIds = [] # NB Max size of array is limit
let threadIds = [] # NB Max size of array is limit
# If not collapsing threads, we can just jump to the required section
if !collapseThreads {
total = messageList.length
for i = position; i < total; i = i + 1 {
messageIds.push( msg.id )
threadIds.push( msg.threadId )
}
} else {
# Optimisation for the common case
let totalIsKnown = filter is just mailbox
let SeenThread = new Set()
let numFound = 0
foreach msg in sortedFilteredList {
if !SeenThread{ msg.threadId } {
SeenThread.add( msg.threadId )
total += 1
if position >= total && numFound < limit {
messageIds.push( msg.id )
threadIds.push( msg.threadId )
numFound += 1
if numFound == limit && totalIsKnown {
break;
}
}
}
}
if totalIsKnown {
total = getTotal( mailbox, collapseThreads )
}
}
</code></pre>
<h3>getMessageListUpdates</h3>
<p>With the suggested data structures, we can do delta updates for any standard mailbox message list (the common case), but not for a search. The following algorithm correctly calculates the delta update. We’re presuming we already have a <code>messageList</code> (directly read in from data structure 3 and sorted if required):</p>
<pre><code>let index = -1
let added = []
let removed = []
let collapseThreads = args.collapseThreads
let uptoHasBeenFound = false
# A mutable sort is one which sorts by a mutable property, e.g.
# sort flagged messages/threads first.
let isMutable = sort.isMutable()
# An exemplar is the first message in each thread in the list, given the
# sort order that
# The old exemplar is the exemplar in the client's old state.
let SeenExemplar = collapseThreads ? new Set() : null
let SeenOldExemplar = collapseThreads ? new Set() : null
foreach msg in messageList {
let isNewExemplar = false
let isOldExemplar = false
let isNew = ( msg.uid >= mailbox.uidNext )
let isChanged = ( msg.modSeq > args.state )
let isDeleted = ( msg.deletedTimeStamp != 0 )
let wasDeleted = ( isDeleted && !isChanged )
# Is this message the current exemplar?
if !isDeleted && ( !collapseThreads || !SeenExemplar{ msg.threadId } ) {
isNewExemplar = true
index += 1
if collapseThreads {
SeenExemplar.set( msg.threadId )
}
}
# Was this message an old exemplar?
# 1. Must not have arrived after the client's state
# 2. Must have been deleted before the client's state
# 3. Must not have already found the old exemplar
if !isNew && !wasDeleted &&
( !collapseThreads || !SeenOldExemplar{ msg.threadId } ) {
isOldExemplar = true
if collapseThreads {
SeenOldExemplar.set( msg.threadId )
}
}
if isOldExemplar && !isNewExemplar {
removed.push({
messageId: msg.messageId,
threadId: msg.threadId
})
}
else if !isOldExemplar && isNewExemplar {
added.push({
index: index,
messageId: msg.messageId,
threadId: msg.threadId
})
}
# Special case for mutable sorts (based on isFlagged/isUnread). If
# collapseThread == true, the sort is based on the *conversation*
# isFlagged/isUnread status.
if isMutable && isOldExemplar && isNewExemplar {
# Has the isUnread/isFlagged status of the message/thread
# (as appropriate) possibly changed since the client's state?
let modSeq = collapseThreads ?
msg.modSeq :
getThread( msg.threadId ).modSeq
# If so, we need to remove the exemplar from the client view and add
# it back in at the correct position.
if modSeq > args.modSeq {
removed.push({
messageId: msg.messageId,
threadId: msg.threadId
})
added.push({
index: index,
messageId: msg.messageId,
threadId: msg.threadId
})
}
}
# If this is the last message the client cares about, we can stop here
# and just return what we've calculated so far. We already know the total
# count for this message list as we keep it pre calculated and cached in
# the Mailbox object.
#
# However, if the sort is mutable we can't break early, as messages may
# have moved from the region we care about to lower down the list.
if !isMutable && msg.uid == args.upto {
break
}
} # End loop
total = getTotal( mailbox, collapseThreads )
</code></pre>
<p>To implement this algorithm, the server must keep the metadata at least of deleted (expunged) messages for a little while (say 1-2 weeks). This is also very useful for restoring accidentally deleted messages as well. At cleanup time (when actually removing the messages), the server must keep track of the highest modseq of a message it has removed in that mailbox (the modseq would have been set at the original delete time); any requests for updates from a state before this must be rejected, as the results may be incorrect.</p>
<h2>getThreadUpdates</h2>
<p>If the client id is lower than the low watermark ModSeq for the Thread Log (as found in the User object), reject with a <code>cannotCalculateUpdates</code> error. Otherwise, binary search the Thread log looking for the client modseq, then read sequentially from there to get the changes.</p>
<h2>getMessageUpdates</h2>
<p>If the client id is lower than the low watermark ModSeq for the Message Log (as found in the User object), reject with a <code>cannotCalculateUpdates</code> error. Otherwise, binary search the Message log looking for the client modseq, then read sequentially from there to get the changes.</p>
</article>
<aside>
<div class="toc-selected"></div>
<ol class="toc"></ol>
</aside>
<script type="text/javascript" src="toc.js"></script>
</body>
</html>