← Back
Home › Systems › Communication and media

mail-store

Stores every message a person has received, lets mail clients list and move them, and finds words across years of mail quickly.

Gmail backend, Dovecot

Open the mail-store pagemail-store Dictionary compressioncompression: Prime the compressor with shared, pre-trained content so small messages can reference it; often 2-5x better ratio on sub-KB records.›Roaring bitmapscompression: Compressed set of 32-bit integers in 64K-value chunks, each a sorted array, bitmap or run list; fast intersections, the standard for bitmap indexes.›Zstandard (zstd)compression: LZ77 plus Huffman and FSE entropy coding, with levels from LZ4-like speed to xz-like ratio, all decoding at about 1-2 GB/s.›Consistent hashingdistributed: Hash nodes and keys onto a ring; each key belongs to the next node clockwise, so membership changes move only about 1/n of keys.›Incremental sync cursorsdistributed: The client keeps one opaque token; each pull returns only the changes after it plus the next token, so sync cost scales with what changed, not with the dataset.›Quorum replicationdistributed: Leaderless replication: write to W of N replicas, read from R; overlap (R + W > N) makes reads see the latest completed write.›CRC32C checksumshardware-os: The Castagnoli CRC-32 with dedicated instructions on x86 (SSE4.2) and ARMv8. It is the standard fast integrity check for storage blocks, logs and network frames.›BM25 rankingsearch-sort: The standard lexical relevance score: IDF-weighted term frequency with saturation (k1) and length normalization (b); default in Lucene, Elasticsearch and SQLite FTS5.›Unicode text tokenization forsearchsearch-sort: Turn multilingual text into index terms: segment words (UAX 29 style, CJK bigrams), normalize, case-fold and accent-fold, identically at index and query time.›AEAD (AES-GCM,ChaCha20-Poly1305)security: Authenticated encryption that encrypts and detects tampering in one call; the only kind of symmetric encryption you should use.›Envelope encryptionsecurity: Encrypt each object with its own data key and wrap that key under a KMS-held key, so rotation re-wraps 60 bytes and deleting a key shreds data.›Content-addressed storagestorage: Store each blob under the hash of its bytes: immutable, deduplicated by construction, self-verifying on every read, and composable into Merkle trees.›Erasure codingstorage: Reed-Solomon k+m coding to survive m lost shards at lower overhead than replicationInverted indexstorage: Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.›LSM-treestorage: Buffer writes in memory, flush them as immutable sorted files and merge in the background; turns random writes into sequential I/O.›Mime parsingstorage: RFC 5322/2045 headers, multipart bodies and transfer encodingsWrite-ahead logstorage: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.›LZ77compression: Replace repeated byte strings with (distance, length) back-references into a sliding window; the parsing stage of gzip, LZ4, zstd, Brotli and xz.›Message sequence numbersdistributed: A per-stream counter on every message lets the receiver detect loss, duplicates and reordering, ack cheaply and resume after reconnect with "send from N".›Cursor paginationnetworking: Keyset/opaque-cursor pagination for stable incremental reads from APIs and tablesAnti-entropy repairdistributed: Replicas compare hash trees of a key range, descend only into differing subtrees and stream just those ranges, healing silent divergence in the background.›Hinted handoffdistributed: Park a write meant for a down replica as a tagged hint on a healthy node, replay it when the replica returns, and count it toward the write quorum only if availability matters more than consistency.›Vector clocksdistributed: One counter per node; comparing two vectors tells whether events are ordered or concurrent, which is exactly what conflict detection needs.›Top-k selectionsearch-sort: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.›Text normalizationmachine-learning: Rewrite messy text into one canonical form for matchers and models, or into spoken words for speech output (and back), keeping a map to the original offsets.›SIMD programminghardware-os: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›Constant time codesecurity: Writing secret-dependent code without branches or memory lookups on secrets; constant-time compare and selectCsprngsecurity: OS-backed cryptographically secure random numbers (getrandom), and when a fast PRNG is not enoughAes key wrapsecurity: AES Key Wrap (RFC 3394/5649) and AES-GCM-SIV for deterministic, authenticated wrapping of key material+ 10 moreFast hash functionsdata-structures: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.›Merkle treedata-structures: Hash tree for verifying and diffing large datasets with logarithmic proofsRange partitioningdistributed: Cut the sorted key space into contiguous half-open ranges kept in a boundary map; split hot or big ranges, merge small ones, move ranges between nodes.›Token bucketsystems: A bucket of up to b tokens refilled at rate r; requests spend tokens, enforcing an average rate while allowing bursts of b.›Phi accrual failure detectordistributed: Instead of a fixed heartbeat timeout, output a continuous suspicion level φ from the observed heartbeat interval distribution; adapts to each link's jitter.›d-ary heapdata-structures: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›

How it is built

Architecture overview

A mail store keeps every message a person has received, lets any mail client list, read, flag and move them, and finds a word in ten years of mail in under a second. A message is written once and almost never changed; what changes constantly is the small state around it (flags, folder membership, read position), and what is asked of it most is "what changed since I last looked". The design that follows from this is a split in three: an immutable blob store for message bodies, a mutable metadata store for per-message state, and a derived search index that can always be rebuilt from the other two.

The idea that makes it scale is the cursor: the server numbers every change inside a mailbox, and a client keeps one token telling it where it stopped, so a sync costs what changed, not what exists. IMAP's unique identifiers and modification sequences are that cursor (RFC 9051 and RFC 7162), and JMAP makes it explicit with a state string and a changes method (RFC 8620). Everything else is a choice about where the blobs live (one file per message, packed files, or object storage), how the index is kept, and how copies survive a failed machine. Hosted providers' backends (Gmail is the usual example) are proprietary, so this page describes the design space and the open-source systems that occupy it, such as Dovecot, Cyrus and Stalwart.

Parts:

 SMTP / LMTP in ─► parse (MIME) ─► spam / rules ─► deliver
                                        │
                  ┌─────────────────────┼──────────────────────┐
                  ▼                     ▼                      ▼
        blob store (immutable)   metadata store (UID, flags)   indexer (tokenise)
        file / packed / object   WAL + sorted files            inverted index segments
                  ▲                     │  change log: modseq / state
                  │                     ▼
       IMAP / JMAP front end ◄── sync cursor ── client (phone, laptop, web)
                  │  search ► index ► candidate UIDs ► fetch from blob store
                  └── replication: quorum writes, hints, anti-entropy between nodes

How the parts fit together

Blob store: the message is the unit that never changes

A message is bytes in the RFC 5322 format, with MIME structure from RFC 2045. Nothing in the server needs to rewrite them after delivery, so the cheapest store is an append-only one. Three layouts are in use, and Dovecot documents all of them:

  1. One file per message (Maildir). D. J. Bernstein's specification calls the point "no locks": each message is a separate file written first to tmp and then moved to new, so a reader never sees a partly delivered message and the format works even over NFS (source: Maildir specification). Dovecot adds a dovecot-uidlist file that maps message file names to IMAP UIDs, and notes that it must be replaced only with rename() (source: Dovecot Maildir docs). The price is one inode and one directory entry per message, which hurts at tens of millions of small files.
  2. Packed files (dbox). Dovecot's single-dbox keeps one message per file and multi-dbox packs many messages into a file that is rotated at a size; the default rotate size is 10 MB, and the docs say new files are preallocated at that size on some Linux filesystems (source: Dovecot dbox docs). Fewer files make backup and delete cheaper, at the cost of a compaction step when messages are expunged.
  3. Object storage. For large installations Dovecot's documentation recommends object storage and names its obox format for it as part of Dovecot Pro, the commercial edition (source: Dovecot mailbox formats overview). Stalwart lists RocksDB, FoundationDB, PostgreSQL, MySQL, SQLite, S3-compatible and Azure storage backends (source: Stalwart README).

On top of the layout, Content-addressed storage stores each blob under the hash of its bytes (SHA-2 and BLAKE3 hashes), so the same attachment sent to a hundred recipients is stored once and every read can verify itself. Deletion then needs reference counts. Compression is Zstandard with a trained dictionary (Dictionary compression) for the small, repetitive headers, and the plain LZ77 family underneath it. Compression must run before encryption, because ciphertext does not compress.

erasure-coding (no page yet) offers durability at lower overhead than three replicas: split a blob into k data and m parity shards and survive m losses, using Reed-Solomon codes over finite-field-arithmetic (no page yet) with SIMD programming for speed. It suits large, cold blobs; replicas suit small hot metadata, where a read should touch one machine.

Metadata store: small, hot, and the source of truth for sync

Flags, folder membership, thread links and the UID sequence are small records that change often. A LSM tree is a good fit because it turns random flag updates into sequential writes, with a Write-ahead log in front for crash safety; the alternative is a B+ tree, which reads faster but writes in place. A set of messages matching a flag (unread, flagged, in this folder) is a set of integers, which Roaring bitmaps store compactly and intersect quickly, so "unread in Inbox" is an AND of two bitmaps. Fast hash functions build in-memory lookup tables from message ID to location.

Many systems keep this state in separate index files next to the messages rather than in a database; Dovecot stores them in the Maildir by default and lets the index path move to other storage (source: Dovecot Maildir docs). Whatever form, the contract is the same: the store assigns a UID in strictly ascending order within a mailbox, and keeps a validity value that changes if UIDs are ever reassigned (source: RFC 9051, section 2.3.1.1).

Search index: derived, rebuildable, and allowed to lag

The index is an Inverted index: for each term, a sorted list of message identifiers. Lists are stored as Delta encoding of the gaps, then Bit-packing and PFOR or Varints for the small numbers; a multi-term query is a Posting-list intersection that starts with the shortest list. Terms come from text that went through Text normalisation and Unicode text tokenisation; the same pipeline must run on the query or "résumé" and "resume" never meet. BM25 ranking orders results by relevance when the client asks for it, and Top-k selection keeps only the best page of hits.

Two design points matter. First, the index is derived: it can be wrong or empty without losing mail, so it can be built lazily. Dovecot's full-text plugin can index mail on delivery, skip mailboxes such as Junk, and still index a skipped mailbox when a search hits it (source: Dovecot fts docs). Second, attachments need extraction before indexing; the same plugin can use an external decoder service for this. Dovecot's plugin supports Apache Solr as a backend (source: Dovecot documentation), Stalwart ships a built-in engine covering 17 languages and can also use Meilisearch, ElasticSearch, OpenSearch, PostgreSQL or MySQL (source: Stalwart README), and notmuch builds on Xapian (source: notmuch repository).

Sync: the cursor is the interface

Incremental sync cursors are the contract between the server and every client. IMAP gives two of them. The UID plus a UIDVALIDITY value identify a message forever within a mailbox (source: RFC 9051, section 2.3.1.1). CONDSTORE adds a modification sequence per message that is increased whenever a flag changes, so a client can ask only for flags changed since a known value (source: RFC 7162, sections 1 and 3.1); QRESYNC lets a reconnecting client resynchronise a mailbox in one step (same RFC). Message sequence numbers in general give loss and duplicate detection. JMAP puts it in the open: every object type has a state string and a /changes method that returns what was created, updated or destroyed since a given state (source: RFC 8620, section 5.2), and JMAP for Mail defines Email, Thread and the matching changes and query-changes methods (source: RFC 8621). cursor-pagination (no page yet) is the same idea for long lists: an opaque keyset token rather than an offset, so inserts during paging do not shift the window.

Replication and placement: where machines fail

One mailbox belongs to one user, so the natural shard key is the user: Consistent hashing or Range partitioning assign users to nodes, and moving a user is a bounded copy. A user's mailbox then needs copies. Quorum replication writes to W of N replicas and reads from R with R + W > N, which tolerates a failed node without a leader; Hinted handoff parks writes for a node that is down and replays them later, and Anti-entropy repair compares merkle-tree (no page yet) hashes of ranges to find silent divergence. Vector clocks tell whether two updates were ordered or concurrent, which is what conflict detection needs. The alternative is a single primary per user with a standby (primary-backup replication), which is simpler and gives the strong ordering that UIDs need; for mail it is often the better choice, because UID assignment must be a single sequence per mailbox.

Token bucket limits per-user rates for delivery and IMAP commands so one runaway client does not saturate a shard.

Durability and encryption

A message should be acknowledged to the sending server only after it is durably stored; fsync and direct I/O says exactly what a fsync guarantees, and Dovecot exposes a mail_fsync setting with an "optimized" mode and a way to disable it for POP3 (source: Dovecot mailbox formats overview). CRC32C checksums detect corruption in blocks and logs, and atomic-file-replacement (no page yet) (write a temporary file, sync it, rename it over the old one, sync the directory) updates small whole files such as an index safely.

For privacy, Envelope encryption encrypts each message with its own data key and wraps that key with a user key held elsewhere, using AEAD ciphers for the data and aes-key-wrap (no page yet) for the key, with randomness from a csprng (no page yet). Deleting the user's key then shreds everything. Server-side search then needs an index that is itself protected. Dovecot ships a mail-crypt plugin for encrypting stored mail (source: Dovecot documentation).

Data and control flow

One incoming message:

  1. The SMTP or LMTP server hands over the raw message and the recipient.
  2. The parser reads headers and MIME parts; spam and rule filters run; the result may be a folder choice.
  3. The blob is compressed, checksummed and written; the write is synced before acknowledgement.
  4. The metadata store assigns the next UID in the target mailbox and a new modification sequence, and appends to the log.
  5. The indexer is told about the new message, tokenises headers and text, and adds postings in a small in-memory or on-disk segment.
  6. Connected clients get a notification; sleeping clients find the change at their next sync.

One search from a phone:

  1. The client sends a query ("from:alice invoice"), scoped to a mailbox.
  2. The server tokenises the terms exactly as at index time and looks up each posting list.
  3. Lists are intersected, shortest first; the sender filter comes from the metadata bitmap.
  4. The top results are ranked, their UIDs returned and headers fetched from the blob store.

One reconnect after a day offline:

  1. The client sends its last known UIDVALIDITY and modification sequence.
  2. If UIDVALIDITY changed, the client discards its cache; otherwise the server returns new UIDs, changed flags and expunged UIDs.
  3. The client applies the delta and stores the new token.

Scaling

In the order you hit them:

  1. Metadata I/O. Many small flag updates; keep index and metadata on fast disks and blobs on cheaper ones.
  2. File count. One file per message becomes the limit; pack messages (dbox) or use object storage.
  3. Index size and build time. Index lazily, skip junk, shard the index with the user.
  4. Storage cost. Dedupe attachments, compress, move cold blobs to erasure-coded storage.
  5. Node failure. Replicas and repair; test them by failing nodes on purpose.
  6. Noisy users. Per-user rate and quota limits.

Failure modes

FailureSymptomCauseFix
UID reuseclient shows wrong or duplicate messagesUIDVALIDITY not changed after UIDs were reassignedbump UIDVALIDITY; clients then rebuild their cache (RFC 9051)
Lost flagsread mail turns unreadconcurrent writers overwrote each othermodification sequences and conditional stores (RFC 7162)
Search finds nothing newrecent mail missing from resultsindexer lag or crashedrebuild or catch up; index is derived
Slow listingfolders with 100k files hangone file per message, directory scanspacked format, index files, avoid stat on every entry
Silent corruptionunreadable old messagebit rot, no checksumCRC32C on blocks, background scrub, repair from replica
Duplicate deliverysame mail twiceretry after timeout without idempotencykey deliveries by message ID and recipient
Unreadable after key lossdata permanently gonewrapped key deleted or lostback up key material separately from the data
Replication splittwo nodes accept writes for one userfailover without fencingsingle writer per mailbox, fencing, or quorum
Index poisoningsearch shows other users' hitsshared index without tenant isolationper-user or per-tenant index
Full diskdelivery rejects mailquota or index growthquota accounting, alert before full, move cold blobs

Real implementations

namewhat it isrepolicencenotes
DovecotIMAP and POP3 server with Maildir, dbox and index filesdovecot/coreMIT for some libraries, otherwise LGPL-2.1 (COPYING)object storage format is in the commercial Pro edition
Cyrus IMAPIMAP server (per its README) with its own mailbox storecyrusimap/cyrus-imapdBSD-style, Carnegie Mellon (COPYING)project site cyrusimap.org
Stalwartmail and collaboration server in Rust: JMAP, IMAP4, SMTPstalwartlabs/stalwartAGPL-3.0 (README badge); an enterprise licence is also soldpluggable stores incl. RocksDB, FoundationDB, S3
Apache JamesJava mail server: IMAP, SMTP, JMAP, POP3apache/james-projectApache-2.0 (LICENSE)distributed server uses Cassandra, S3, OpenSearch, RabbitMQ (README)
notmuchtag-based mail indexer on top of Xapiannotmuch/notmuchGPL-3.0-or-later (COPYING)an index over Maildir, not a server
Xapiansearch engine libraryxapian/xapianGPL-2.0 (COPYING)used by notmuch

The alternative: use a hosted mail provider. Running your own mail store only pays when data location, control or cost demand it; the delivery side (reputation, spam, deliverability) is a separate, larger job than the storage.

Sources

  • M. Crispin, Internet Message Access Protocol (IMAP) - Version 4rev2, RFC 9051. RFC; IMAP4rev1, RFC 3501: RFC
  • A. Melnikov, D. Cridland, C. Wilson, IMAP Extensions: Quick Flag Changes Resynchronization (CONDSTORE) and Quick Mailbox Resynchronization (QRESYNC), RFC 7162. RFC
  • N. Jenkins, C. Newman, The JSON Meta Application Protocol (JMAP), RFC 8620, and JMAP for Mail, RFC 8621. RFC 8620, RFC 8621
  • Internet Message Format, RFC 5322. RFC; MIME Part One, RFC 2045. RFC
  • D. J. Bernstein, Using maildir format. spec
  • Dovecot CE 2.4 documentation: mailbox formats, Maildir, dbox, fts plugin, mail-crypt
  • Stalwart: README; Cyrus IMAP: repo

Similar systems

Share the most building blocks with this one.

backup-dr 28 %object-storage 22 %distributed-fs 19 %filesystem 17 %logging 17 %