Debian Codegraph @

doc/html/_sources/imap/reference/admin/murder/murder-concepts.rst.txt

raw
1 .. _murder_concepts:
2
3 ======================
4 Cyrus Murder: Concepts
5 ======================
6
7 The Cyrus IMAP Aggregator transparently distributes IMAP and POP
8 mailboxes across multiple servers. Unlike other systems for load
9 balancing IMAP mailboxes, the aggregator allows users to access
10 mailboxes on any of the IMAP servers in the system.
11
12 Note that although this document focuses on IMAP and POP, the same
13 concepts also apply to NNTP and HTTP (CalDAV, CardDAV, RSS).
14
15
16
17 Overview
18 ========
19
20 Scaling a service usually takes one of two paths:
21
22 1. Buy bigger and faster machines
23 This approach is obvious and (hopefully) easy, though at some point
24 software tuning becomes necessary to take advantage of the bigger
25 machines. However, if one of these large machines go down, then your
26 entire system is unavailable.
27 2. Distribute the load across multiple machines.
28 The second approach has the benefit that there is no longer a single
29 point of failure and the aggregate cost of multiple machines may be
30 significantly lower than the cost of a single large machine. However,
31 the system may be harder to implement as well as harder to manage.
32
33 In the IMAP space, the approach of buying a larger machine is pretty
34 obvious. Distributing the load is a bit trickier since there is no
35 concept of mailbox location in IMAP (excluding :rfc:`2193` mailbox
36 referrals, which are not widely implemented by clients). Clients
37 traditionally assume that the server they are talking to is the server
38 with the mailbox they are looking for.
39
40 The approaches to distributing the load among IMAP servers generally
41 sacrifice the unified system image. For pure email, this is an
42 acceptable compromise; however, trying to share mailboxes becomes
43 difficult or even impossible. Specific examples can be found in `Appendix
44 A: DNS Name Load Balancing`_ and `Appendix B: IMAP Multiplexing`_).
45
46 We propose a new approach to overcome these problems. We call it the Cyrus
47 IMAP Aggregator. The Cyrus aggregator takes a :ref:`murder <def_murder>` of IMAP
48 servers and presents a server independent view to the clients. That is,
49 **all the mailboxes across all the IMAP servers are aggregated to a single
50 image**, thereby appearing to be only one IMAP server to the clients.
51
52 Architecture
53 ============
54
55 The Cyrus IMAP Aggregator has three classes of servers:
56 1. IMAP frontend,
57 2. IMAP backend, and
58 3. MUPDATE.
59
60 The frontend servers act as the primary communication point between the
61 end user clients and the backend servers. The frontends use the MUPDATE
62 server as an authoritative source for mailbox names, locations, and
63 permissions. The backend servers store the actual IMAP data (and keep
64 the MUPDATE server appraised as to changes in the Mailbox list).
65
66 Backend Servers
67 ---------------
68
69 The backend servers serve the actual data and are fully functional
70 standalone IMAP servers that serve a set of mailboxes. Each backend
71 server maintains a local mailboxes database that lists what mailboxes
72 are available on that server.
73
74 The imapd processes on a backend server can stand by themselves, so that
75 each backend IMAP server can be used in isolation, without a MUPDATE
76 server or any frontend servers. However, they are configured so that
77 they won't process any mailbox operations (CREATE, DELETE, RENAME,
78 SETACL, etc) unless the master MUPDATE server can be contacted and
79 authorizes the transaction.
80
81 In this mode, the imapd processes update the local mailboxes database
82 themselves. Additionally, on a CREATE they need to reserve a place with
83 the MUPDATE server to insure that other backend servers aren't creating
84 the same mailbox before proceeding. Once the local aspects of mailbox
85 creation are complete, the mailbox is activated on the MUPDATE server,
86 and is considered available to any client through the frontends.
87
88 Frontend Servers
89 -----------------
90
91 The frontend servers, unlike the backend servers, are fully
92 interchangeable with each other and the frontend servers can be
93 considered 'dataless'; any loss of a proxy results in no loss of data.
94 The only persistent data that is needed (the mailbox list) is kept on
95 the MUPDATE master server. This list is synchronized between the
96 frontend and the MUPDATE master when the frontend comes up.
97
98 The list of mailboxes in the murder is maintained by the MUPDATE server.
99 The MUPDATE protocol is described at :rfc:`3656`.
100
101 For IMAP service on a frontend, there are two main types of processes,
102 the proxyd and the mupdate (slave mode) synchronization process. The
103 proxyd handles the IMAP session with clients. It relies on a consistent
104 and complete mailboxes database that reflects the state of the world. It
105 never writes to the mailboxes database. Instead, the mailboxes database
106 is kept in sync with the master by a slave mupdate process.
107
108 Mail Delivery
109 -------------
110
111 The incoming mail messages go to an lmtp proxy (either running on a
112 frontend, a mail exchanger, or any other server). The lmtp proxy running
113 on the frontend server uses the master MUPDATE server to determine the
114 location of the destination folder and then transfers the message to the
115 appropriate backend server via LMTP. If the backend is not up (or
116 otherwise fails to accept the message), then the LMTP proxy returns a
117 failure to the connected MTA.
118
119 If a sieve script is present, the lmtp proxy server must do the
120 processing as the end result of the processing may result in the mail
121 message going to a different backend server than where the user's INBOX
122 is.
123
124 .. note::
125 The current implementation runs SIEVE on the backend servers, and
126 holds the requirement that all of a user's mailboxes live on the
127 same backend.
128
129 Clients
130 -------
131
132 Clients that support :rfc:`2193` IMAP referrals can bypass the
133 aggregator frontend. See `IMAP Referrals`_ for more details.
134
135 Clients are encouraged to bypass the frontends via approved mechanisms.
136 This should result in better performance for the client and less load
137 for the servers.
138
139 .. Note::
140 Sites choosing to locate front ends in a DMZ, or other isolated
141 network segment, should disable IMAP Referrals which might lead
142 clients to attempt impossible actions, such as direct access to
143 back ends which are firewalled. Please consult
144 :cyrusman:`imapd.conf(5)` for details of the
145 ``proxyd_disable_mailbox_referrals`` setting.
146
147 Implementation
148 ==============
149
150 Assumptions
151 -----------
152
153 * Operations that change the mailbox list are (comparatively) rare.
154 The vast majority of IMAP sessions do not manipulate the state of the
155 mailbox list.
156
157 * Read operations on the mailbox list are very frequent.
158
159 * A mailbox name must be unique among all the back end servers.
160
161 * The MUPDATE master server will be able to handle the load from the
162 frontend, backend, and LMTP proxy servers. Currently, the MUPDATE
163 master can be a bottleneck in the throughput of mailbox operations,
164 but as the MUPDATE protocol allows for slave server to act as
165 replicas, it is theoretically possible to reduce the load of read
166 operations against the master to a very low level.
167
168 * IMAP clients are not sensitive to somewhat loose mailbox tree
169 consistency, and some amount of consistency can be sacrificed for
170 speed. As is, IMAP gives no guarantees about the state of the mailbox
171 tree from one command to the next. However, it's important to note
172 that different IMAP sessions do communicate out of band: two sessions
173 for the same client should see sensible results. In the Murder case,
174 this means that the same client talking to two different frontends
175 should see sensible results.
176
177 * A single IMAP connection should see consistent results: once an
178 operation is done, it is done, and needs to be reflected in the
179 current session. The straightforward case that must work correctly is
180 (provided there is no interleaved DELETE in another session)::
181
182 A001 CREATE INBOX.new
183 A002 SELECT INBOX.new
184
185 * Accesses to non-existent mailboxes are rare.
186
187 Authentication
188 --------------
189
190 The user authenticates to the frontend server via any supported SASL
191 mechanism or via plaintext. If authentication is successful, the front
192 end server will authenticate to the backend server using a SASL
193 mechanism (in our case GSSAPI) as a privileged user. This
194 user is able to switch to the authorization of the actual user being
195 proxied for and any authorization checks happen as if the user actually
196 authenticated directly to the backend server. Note this is a native
197 feature of many SASL mechanisms and nothing special with the aggregator.
198
199 To help protect the backends from a compromised frontends, all
200 administrative actions (creating users, top level mailboxes, quota
201 changes, etc) must be done directly from the client to the backend, as
202 administrative permissions are not granted to any of the proxy servers.
203 IMAP Referrals provide a way to accomplish this with minimal client UI
204 changes.
205
206 Subscriptions
207 -------------
208
209 ``[LSUB, SUBSCRIBE, UNSUBSCRIBE]``
210
211 The frontend server directs the LSUB to the backend server that has
212 the user's INBOX. As such, the backend server may have entries in the
213 subscription database that do not exist on that server. The frontend
214 server needs to process the list returned by the backend server and
215 either remove or tag with \\NoSelect the entries which are not currently
216 active within the murder.
217
218 If the user's INBOX server is down and the LSUB fails, then the
219 aggregator replies with NO with an appropriate error message. Clients
220 should not assume that the user has no subscriptions (though apparently
221 some clients do this).
222
223
224
225 Finding a Mailbox
226 -----------------
227
228 ``[SETQUOTA, GETQUOTA, EXAMINE, STATUS]``
229
230 The frontend machine looks up the location of the mailbox, connects
231 via IMAP to the backend server, and issues the equivalent command there.
232 A quota root is not allowed to span across multiple servers.
233 At least, not with the semantics that it will be inclusive across the murder.
234
235 ``[SELECT]``
236
237 To SELECT a mailbox:
238
239 1. proxyd: lookup foo.bar in local mailboxes database
240
241 2. if yes, proxyd -> back end: send SELECT
242
243 3. if no, proxyd -> mupdate slave -> mupdate master: send a ping
244 along the UPDATE channel in order to ensure that we have received
245 the latest data from the MUPDATE master.
246
247 4. if mailbox still doesn't exist, fail operation
248
249 5. if mailbox does exist, and the client supports referrals, refer
250 the client. Otherwise continue as a proxy with a selected mailbox.
251
252 SELECT on mailboxes that do not exist are much more expensive but
253 the assumption is that this does not frequently occur (or if it
254 does, it is just after the mailbox has been created and the
255 frontend hasn't seen the update yet).
256
257 Operations within a Mailbox
258 ---------------------------
259
260 ``[APPEND, CHECK, CLOSE, EXPUNGE, SEARCH, FETCH, STORE, UID]``
261
262 These commands are sent to the appropriate backend server.
263 The aggregator does not need to modify any of these commands
264 before sending them to the backend server.
265
266 COPY
267 ----
268
269 COPY is somewhat special as it acts upon messages in the currently
270 SELECT'd mailbox but then interacts with another mailbox.
271
272 In the case where the destination mailbox is on the same backend server
273 as the source folder, the COPY command is issued to the backend
274 server and the backend server takes care of the command.
275
276 If the destination folder is on a different backend server, the
277 frontend intervenes and does the COPY by FETCHing the messages from the
278 source backend server and then APPENDs the messages to the destination server.
279
280 Operations on the Mailbox List
281 ------------------------------
282
283 ``[CREATE, DELETE, RENAME, SETACL]``
284
285 These commands are all done by the backend server using the MUPDATE
286 server as a lock manager. Changes are then propagated to the frontend
287 via the MUPDATE protocol.
288
289 ``[LIST]``
290
291 LIST is handled by the frontend servers; no interaction is
292 required with the backend server as the front ends have a local
293 database that is never more than a few seconds out of date.
294
295 ``[CREATE]``
296
297 CREATE creates the mailbox on the same backend server as the
298 parent mailbox. If the parent exists but exists on multiple backend
299 servers, if there is no parent folder, a tagged NO response is
300 returned.
301
302 When this happens, the administrator has two choices. He may
303 connect directly to a backend server and issue the CREATE on that
304 server. Alternatively, a second argument can be given to CREATE
305 after the mailbox name. This argument specifies the specific host
306 name on which the mailbox is to be created.
307
308 The following operations occur for CREATE on the frontend:
309
310 * proxyd: verify that mailbox doesn't exist in MUPDATE mailbox list.
311
312 * proxyd: decide where to send CREATE (the server of the parent
313 mailbox, as top level mailboxes cannot be created by the proxies).
314
315 * proxyd -> back end: duplicate CREATE command and verifies that
316 the CREATE does not create an inconsistency in the mailbox list
317 (i.e. the folder name is still unique).
318
319 The following operations occur for CREATE on the backend:
320
321 * imapd: verify ACLs to best of ability (CRASH: aborted)
322
323 * imapd: start mailboxes transaction (CRASH: aborted)
324
325 * imapd may have to open an MUPDATE connection here if one doesn't
326 already exist
327
328 * imapd -> MUPDATE: set foo.bar reserved (CRASH: MUPDATE externally
329 inconsistent)
330
331 * imapd: create foo.bar in spool disk (CRASH: MUPDATE externally
332 inconsistent, back end externally inconsistent, this can be
333 resolved when the backend comes back up by clearing the state from
334 both MUPDATE and the backend)
335
336 * imapd: add foo.bar to mailboxes dataset (CRASH: ditto)
337
338 * imapd: commit transaction (CRASH: ditto, but the recovery can
339 activate the mailbox in mupdate instead)
340
341 * imapd -> MUPDATE: set foo.bar active (CRASH: committed)
342
343 Failure modes: Above, all backend inconsistencies result in the
344 next CREATE attempt failing. The earlier MUPDATE inconsistency
345 results in any attempts to CREATE the mailbox on another backend
346 failing. The latter one makes the mailbox unreachable and
347 un-createable. Though, this is safer than potentially having the
348 mailbox appear in two places when the failed backend comes back
349 up.
350
351 ``[RENAME]``
352
353 RENAME is only interesting in the cross-server case. In this case
354 it issues a (non-standard) XFER command to the backend that
355 currently hosts the mailbox, which performs a binary transfer of
356 the mailbox (and in the case of a user's inbox, their associated
357 seen state and subscription list) to the new backend. During this
358 time the mailbox is marked as RESERVED in mupdate, and when it is
359 complete it is activated on the new server in MUPDATE. The
360 deactivation prevents clients from accessing the mailbox, and
361 causes mail delivery to temporarily fail.
362
363 .. _imap_referrals:
364
365 IMAP Referrals
366 --------------
367
368 If clients support IMAP Mailbox Referrals (:rfc:`2193`), the client can
369 improve performance and reduce the load on the aggregator by using the
370 IMAP referrals that are sent to it and going to the appropriate
371 backend servers.
372
373 The frontend servers will advertise the ``MAILBOX-REFERRALS``
374 capability. The backend servers will also advertise this capability
375 (but only because they need to refer clients while a mailbox is moving
376 between servers).
377
378 Since there is no way for the server to know if a client supports
379 referrals, the Cyrus IMAP Aggregator will assume the clients do not
380 support referrals unless the client issues a RLSUB or a RLIST command.
381
382 Once a client issues one of those commands, then the aggregator will
383 issue referrals for any command for which the client may safely contact
384 the IMAP server directly. Most commands performing operations within
385 a mailbox (cf Section 3.3) fall into this category. Some commands will
386 not be possible without a referrals-capable client (such as most
387 commands done as administrator).
388
389 :rfc:`2193` indicates that the client does not stick the referred
390 server. As such the SELECT will get issued to the frontend server and
391 not the referred server. Additionally, CREATE, RENAME, and DELETE get
392 sent to the frontend which will proxy the command to the correct
393 backend server.
394
395 POP
396 ---
397
398 POP is easy given that POP only allows access to the user's INBOX. When
399 it comes to POP, the IMAP Aggregator acts just like a :ref:`multiplexor
400 <appendix-b-imap-multiplexing>`. The user authenticates to frontend
401 server. The frontend determines where the user's INBOX is located and
402 does a direct pass through of the POP commands from the client to the
403 appropriate backend server.
404
405 MUPDATE
406 -------
407
408 The mupdate (slave) process (one per frontend) holds open a MUPDATE
409 connection and listens for updates from the MUPDATE master server (as
410 backends inform it of updates). The slave makes these modifications on
411 the local copy of the mailboxes database.
412
413 Analysis
414 ========
415
416 Mailboxes Database
417 ------------------
418
419 A benefit of having the mailbox information on the frontend is that
420 LIST is very cheap. The frontend servers can process this request
421 without having to contact each backend server.
422
423 We're also assuming that LIST is a much more frequent operation than any
424 of the mailbox operations and thus should be the case to optimize. (In
425 addition to the fact that any operation that needs to be forwarded to a
426 backend needs to know to which backend it is being forwarded, so lookups
427 in the mailbox list are also quite frequent).
428
429 Failure Mode Analysis
430 ---------------------
431
432 What happens when a backend server comes up?
433 #############################################
434
435 Resynchronization with the MUPDATE server. Any mailboxes that exist
436 locally but are not in MUPDATE are pushed to MUPDATE. Any mailboxes
437 that exist locally but are in MUPDATE as living on a different
438 server are deleted. Any mailboxes that do not exist locally but
439 exist in MUPDATE as living on this server are removed from MUPDATE.
440
441 What happens when a frontend server comes up?
442 ##############################################
443
444 The only thing that needs to happen is for the frontend to connect
445 to the MUPDATE server, issue an UPDATE command, and resynchronize
446 its local database copy with the copy on the master server.
447
448 Where's the true mailboxes file?
449 ################################
450
451 The MUPDATE master contains authoritative information as to the
452 location of any mailbox (in the case of a conflict), but the
453 backends are authoritative as to which mailboxes actually exist.
454
455 Summary of Benefits
456 -------------------
457
458 * **Availability** - By allowing multiple frontends, failures of the
459 frontend only result in a reduction of capacity. Users currently
460 connected still lose their session but can just reconnect to get back
461 online.
462
463 * The failure of the backends will result in the loss of
464 availability. However, given that the data is distributed among
465 multiple servers, the failure of a single server does not result
466 the entire system being down. Our experience with AFS was that
467 this type of partitioned failure was acceptable (if not ideal).
468 * The failure of the mupdate master will cause write operations to
469 the mailbox list to fail, but accesses to mailboxes themselves (as
470 well as read operations to the mailbox list) will continue
471 uninterrupted.
472 * At this point, there may be some ideas but no plans for providing
473 a high availability solution which would allow for backend
474 servers or the MUPDATE server to fail with no availability impact.
475
476 * **Load scalability** - No specific benchmarks have been run to
477 show that this system actually performs better. However, it is clear
478 that it scales to a larger number of users than a single server
479 architecture would. Though, based on the fact that there are no further
480 performance problems beyond when running a single machine,
481 but handling about 20% more concurrent users, this is a success.
482
483 * **Management benefits** - As with AFS, administrators have the
484 flexibility of placement of data on the servers, "live" move of data
485 between servers,
486
487 * **User benefits** - The user only needs to know a single server name
488 for configuration. The same name can be handed out to all users.
489
490 * Users don't lose the ability to share their folders and those
491 folders are visible to other users. A user's INBOX folder
492 hierarchy can also exist across multiple machines.
493
494 Futures
495 =======
496
497 It would be nice to be able to replicate the messages in a mailbox
498 among multiple servers and not just do partitioning for availability.
499
500 We are also evaluating using the aggregator to be able to provide
501 mailboxes to the user with a different backup policy or even different
502 "quality of service." For example, we are looking to give users a
503 larger quota than default but not back up the servers where these
504 mailboxes exist.
505
506 There is possibility that LDAP could be used instead of MUPDATE.
507 However at this time the replication capabilities of LDAP are
508 insufficient for the needs of the Aggregator.
509
510 It would be nice if quotaroots had some better semantics with respect
511 to the murder (either make them first-class entities, or have them
512 apply across servers).
513
514 Appendices
515 ==========
516
517 Appendix A: DNS Name Load Balancing
518 -----------------------------------
519
520 One method of load balancing is to use DNS to spread your users to
521 multiple machines.
522
523 One method is to create a DNS CNAME for each letter of the alphabet.
524 Then, each user sets their IMAP server to be the first letter of their
525 userid. For example, the userid 'tom' would set his IMAP server to be
526 ``T.IMAP.ANDREW.CMU.EDU`` and ``T.IMAP.ANDREW.CMU.EDU`` would resolve to
527 an actual mail server.
528
529 Given that this does not provide a good distribution, another option is
530 to create a DNS CNAME for each user. Using the previous example, the
531 user 'tom' would set his IMAP server to be ``TOM.IMAP.ANDREW.CMU.EDU``
532 which then points to an actual mail server.
533
534 The good part is that you don't have all your users on one machine and
535 growth can be accommodated without any user reconfiguration.
536
537 The drawback is with shared folders. The mail client now must support
538 multiple servers and users must potentially configure a server for each
539 user with a shared folder he wishes to view. Also, the user's INBOX
540 hierarchy must also reside on a single machine.
541
542 .. _appendix-b-imap-multiplexing:
543
544 Appendix B: IMAP Multiplexing
545 -----------------------------
546
547 Another method of spreading out the load is to use IMAP multiplexing.
548 This is very similar to the IMAP Aggregator in that there are frontend
549 and backend servers. The frontend servers do the lookup and then
550 forward the request to the appropriate backend server.
551
552 The multiplexor looks at the user who has authenticated. Once the user
553 has authenticated, the frontend does a lookup for the backend server
554 and then connects the session to a single backend server. This provides
555 the flexibility of balancing the users among any arbitrary server but
556 it creates a problem where a user can not share a folder with a user on
557 a different backend server.
558
559 Multiplexors references:
560
561 * `Netscape Messaging Multiplexor`_
562 * `Paul Fleming's IMAP Proxy`_
563 * `Perdition IMAP Proxy`_
564 * `Mirapoint Message Director`_ - This is a hardware solution that
565 also does content filtering.
566
567 .. _Netscape Messaging Multiplexor: http://docs.oracle.com/cd/E19079-01/nscp.mes.svr40/816-6037-10/
568 .. _Paul Fleming's IMAP Proxy: http://www.siumed.edu/~pfleming/development/email/
569 .. _Perdition IMAP Proxy: http://horms.net/projects/perdition/
570 .. _Mirapoint Message Director: http://owmessaging.com/Mirapoint_Message_Server
571
572 Appendix C: Definitions
573 -----------------------
574
575 IMAP connection
576 A single IMAP TCP/IP session with a single IMAP server is a
577 "connection".
578
579 client
580 A client is a process on a remote computer that communicates with
581 the set of servers distributing mail data, be they ACAP, IMAP,
582 or LDAP servers. A client opens one or more connections to
583 various servers.
584
585 mailbox tree
586 The collection of all mailboxes at a given site in a namespace is
587 called the mailbox tree. Generally, the user Bovik's personal data
588 is found in ``user.bovik``.
589
590 mailboxes database
591 A local database containing a list of mailboxes known to a
592 particular server.
593
594 mailbox dataset
595 The store of mailbox information on the ACAP server is the "mailbox
596 dataset".
597
598 mailbox operation
599 The following IMAP commands are "mailbox operations": CREATE,
600 RENAME, DELETE, and SETACL.
601
602 MTA
603 The mail transport agent (e.g. sendmail, postfix).
604
605 .. _def_murder:
606
607 Murder of IMAP servers
608 A grouping of IMAP servers. It sounded cool for crows so we decided
609 to use it for IMAP servers as well.
610
611 quota operations
612 The quota IMAP commands (GETQUOTA, GETQUOTAROOT, and SETQUOTA)
613 operate on mailbox trees. In future versions of Cyrus, it is
614 expected that a quotaroot will be a subset of a mailbox tree that
615 resides on one partition on one server. For rationale, see section
616 xxx.