10 The Plan 9 email system, Upas, uses traditional methods of delivery to
12 mail boxes while using a user-level file system, Upas/fs, to
13 translate mail boxes of various formats into a single, convenient format for access.
14 Unfortunately, it does not do so efficiently. Upas/fs
15 reads entire folders into core. When deleting email from mail boxes,
16 the entire mail box is rewritten. I describe how Upas/fs has been
17 adapted to use caching, indexing and a new mail box format (mdir) to
18 limit I/O, reduce core size and eliminate the need to rewrite mail
25 Chained at his root two scion demons dwell
27 – Erasmus Darwin, The Botanic Garden
30 At Coraid, email is the largest resource user in the system by orders
31 of magnitude. As of July, 2007, rewriting mail boxes was using
32 300MB/day on the WORM and several users required more than 400MB of
33 core. As of July, 2008, rewriting mail boxes was using 800MB/day on
34 the WORM and several users required more than 1.2GB of core to read
35 email. Clearly these are difficult to sustain levels of growth, even
36 without growth of the company. We needed to limit the amount of disk
37 space used and, more urgently, reduce Upas/fs' core size.
39 The techniques employed are simple. Mail is now stored in a directory
40 with one message per file. This eliminates the need to rewrite mail
41 boxes. Upas/fs now maintains an index which allows it to present
42 complete message summaries without reading indexed messages.
43 Combining the two techniques allows Upas/fs to read only new or
44 referenced messages. Finally, caching limits both the total number of
45 in-core messages and their total size.
49 In addition to meeting our urgent operational requirements of reducing
50 memory and disk footprint, to meet the expectations of our users we
51 require a solution that is able to handle folders up to ten thousand
52 messages, open folders quickly, list the contents of folders quickly
53 and support the current set of mail readers.
55 There are several potential styles of mail boxes. The maildir[1] format
56 has some attractive properties. Mail can be delivered to or deleted
57 from a mail box without locking. New mail or deleted mail may be
58 detected with a directory scan. When used with WORM storage, the
59 amount of storage required is no more than the size of new mail
60 received. Mbox format can require that a new copy of the inbox be
61 stored every day. Even with storage that coalesces duplicate blocks
62 such as Venti, deleting a message will generally require new storage
63 since messages are not disk-block aligned. Maildir does not reduce
64 the cost of the common task of a summary listing of mail such as
65 generated by acme Mail.
67 The mails[2] format proposes a directory per mail. A copy of
68 the mail as delivered is stored and each mime part is decoded
69 in such a way that a mail reader could display the file directly.
70 Command line tools in the style of MH[3] are used to display and
71 process mail. Upas/fs is not necessary for reading local mail.
72 Mails has the potential to reduce memory footprint below that
73 offered by mdirs for native email reading. However all of the
74 largest mail boxes at our site are served exclusively through IMAP.
75 The preformatting by mails would be unnecessary for such accounts.
77 Other mail servers such as Lotus Notes[4] store email in a custom
78 database format which allows for fielded and full-text searching
79 of mail folders. Such a format provides very quick mail
80 listings and good search capabilities. Such a solution would not
81 lend itself well to a tool-based environment, nor would it be simple.
83 Maildir format seemed the best basic format but its particulars are
86 environment; mdir is a descendant. A mdir folder
87 is a directory with the name of the folder. Messages in the mdir
88 folder are stored in a file named
91 is defined as the decimal
93 seconds when the message was added to
94 the folder. For the inbox, this time will correspond to the
98 is a two-digit sequence number starting with
100 The lowest available sequence number is used to store the message.
101 Thus, the first email possible would be named
103 To prevent accidents, message files are stored with
104 the append-only and exclusive-access bits turned on.
105 The message is stored in the same format it would be in mbox
106 format; each message is a valid mbox folder with a single message.
110 When upas/fs finds an unindexed message, it is added to the index.
111 The index is a file named
113 and consists a signature and one line per MIME part. Each line
114 contains the SHA1 checksum of the message (or a place holder for
115 subparts), one field per entry in the
117 file, flags and the number of subparts. The flags are currently a
118 superset of the standard IMAP flags. They provide the similar
119 functionality to maildir's modified file names. Thus the `S'
120 (answered) flag remains set between invocations of mail readers.
121 Other mutable information about a message may be stored in a similar
126 file is read by all the mail readers to produce mail listings,
127 mail boxes may be listed without opening any mail files when no new
128 mail has arrived. Similarly, opening a new mail box requires reading
129 the index and checking new mail. Index files are typically between
130 0.5% and 5% the size of the full mail box. Each time the index is
131 generated, it is fully rewritten.
135 Upas/fs stores each message in a
137 structure. To enable caching, this structure was split
140 (or index), message subparts, information on the cache state of the
141 message and a set of pointers into the processed header and body.
142 Only the pointers to the processed header and body are subject to
143 caching. The available cache states are
149 When the header and body are not present, the average message with
150 subparts takes roughly 3KB of memory. Thus a 10,000 message mail box
151 would require roughly 30MB of core in addition to any cached
152 messages. Reads of the
156 files can be satisfied from the information in the
160 Since there are a fair number of very large messages, requests that
161 can be satisfied by reading the message headers do not result in the
162 full message being read. Reads of the
166 files of top-level messages are satisfied in this way. Reading the
167 same files for subparts, however, results in the entire message being
168 read. Caching the header results in the
172 Similarly, reading the
174 requires the body to be read, processed and results in
177 cache state. Reading from MIME subparts also results
182 The cache has a simple LRU replacement policy. Each time a cached
183 member of a message is accessed, it is moved to the head of the list.
184 The cache contains a maximum number of messages and a maximum size.
185 While the maximum number of messages may not be exceeded, the maximum
186 cache size may be exceeded if the sum of all the currently referenced
187 messages is greater than the size of the cache. In this case all
188 unreferenced messages will be freed. When removing a message
189 from the cache all of the cacheable information is freed.
194 Each new user of a new system uncovers a new class of bugs.
199 In addition to upas/fs, programs that have assumptions about how
200 mail boxes are structured needed to be modified. Programs which
201 deliver mail to mail boxes (deliver, marshal, ml, smtp) and append messages to
202 folders were given a common (nedmail) function to call. Since this
203 was done by modifying functions in the Upas common library, this
204 presented a problem for programs not traditionally part of Upas
205 such as acme Mail and imap4d. Rather than fold these programs
206 into Upas, a new program, mbappend, was added to Upas.
208 Imap4d also requires the ability to rename and remove folders.
209 While an external program would work for this as well, that
210 approach has some drawbacks. Most importantly, IMAP folders
211 can't be moved or renamed in the same way without reimplementing
212 functionality that is already in upas/fs. It also emphasises the
213 asymmetry between reading and deleting email and other folder
214 actions. Folder renaming and removal were added to upas/fs.
215 It is intended that mbappend will be removed soon
216 and replaced with equivalent upas/fs functionality —
217 at least for non-delivery programs.
219 Mdirs also expose an oddity about file permissions. An append-only
222 may be appended to by anyone, but is readable only by the owner.
223 With a directory, such a setup is not directly possible as write permission
224 to a directory implies permission to remove. There are a number of
225 solutions to this problem. Delivery could be made asymmetrical—incoming
226 files could be written to a mbox. Or, following the example of the outbound
227 mail queue, each user could deliver to a directory owned by that user.
230 systems, the “sticky bit” on directories is used to modify
233 bit for users matching only the other bits. For them, the
235 bit gives permission to create but not to remove.
237 While this is somewhat of a one-off situation, I chose to implement
238 a version of the “sticky bit” using the existing append-only bit on our
239 file server. This was implemented as an extra permission check when
240 removing files. Fewer than 10 lines of code were required.
244 A representative local mail box was used to generate some rough
245 performance numbers. The mail box is 110MB and contains 868 messages.
246 These figures are shown in table 1. In the worse case—an unindexed
247 mail box—the new upas/fs uses 18% of the memory of the original while
248 using 13% more cpu. In the best case, it uses only 5% of the memory
249 while using only 13% of the cpu. Clearly, a larger mail box will make
250 these ratios more attractive. In the two months since the snapshot was
251 taken, that same mail box has grown to 220MB and contains 1814
260 Table 1 – Performance
262 action:user:system:real:core size:
265 old fs read:1.69:0.84:6.07:135
267 initial read:1.65:0.90:6.90:25
269 indexed read:0.64:0.03:0.77:6.5
276 While Upas' memory usage has been drastically reduced,
277 it is still a work-in-progress. Caching and indexing are
278 adequate but primitive. Upas/fs is still inconsistently
279 bypassed for appending messages to mail boxes. There
280 are also some features which remain incomplete. Finally,
281 the small increase in scale brings some new questions about
282 the organization of email.
284 It may be useful for mail boxes with very large numbers
285 of messages to divide the index into fixed-size chunks.
286 Then messages could be read into a fixed-sized pool of
287 structures as needed. However it is currently hard to
288 see how clients could easily interface a mail box large
289 enough for this technique to be useful. Currently, all
290 clients assume that it is reasonable to allocate an
291 in-core data structure for each message in a mail box.
292 To take advantage of a chunked index, clients (or the
293 server) would need a way of limiting the number of
294 messages considered at a time. Also, for such large
295 mail boxes, it would be important to separate the
296 incoming messages from older messages to limit the work
297 required to scan for new messages.
299 Caching is particularly unsatisfactory. Files should
300 be read in fixed-sized buffers so maximum memory usage
301 does not depend on the size of the largest file in the
302 mail box. Unfortunately, current data structures do not readily
303 support this. In practice, this limitation has not yet
306 There are also a few features that need to be completed.
307 Tracking of references has been added to marshal and
308 upas/fs. In addition, the index provides a place to store
309 mutable information about a message. These capabilities
310 should be built upon to provide general threading and
311 tagging capabilities.
315 Freed from the limitation that all messages in a
316 mail box must be read and stored in memory before a
317 single message may be accessed, it is interesting to
318 speculate on a few further possibilites.
320 For example, it may be
321 useful to replace separate mail boxes with a single
322 collection of messages assigned to one or more virtual
323 mail boxes. The association between a message and a
324 mail box would be a “tag.” A message could be added to
325 or removed from one or more mail boxes without modifying
326 the mdir file. If threads were implemented by tagging
327 each message with its references, it would be possible
328 to follow threads across mail boxes, even to messages
329 removed from all mail boxes, provided the underlying
330 file were not also removed. If a facility for adding
331 arbitrary, automatic tags were enabled, it would be
332 possible to tag messages with the email address in
337 D. Bernstein, “Using maildir format”,
340 http://cr.yp.to/proto/maildir.html
345 http://lsub.org/magic/man2html/1/mails
348 http://en.wikipedia.org/wiki/MH_Message_Handling_System
350 Lotus Notes Wikipedia entry,
351 http://en.wikipedia.org/wiki/Lotus_Notes
353 D. Presotto, “Upas—a Simpler Approach to Network Mail”,
354 Proceedings of the 10th Usenix conference, 1985.
projects / plan9front.git / blob