技术文章:把IMAP邮箱当作数据库来用(第一部分)
来源标题:Quality IMAP, part 1: your mailbox is a database
一篇技术文章提出把IMAP邮箱当作数据库使用,并发布第一部分内容。文章围绕IMAP的质量问题展开,讨论如何以数据库的视角来使用邮箱。
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
During the past year, we have significantly improved the reliability and correctness of Aerogramme's IMAP implementation. This is the first part in a series of blog posts elaborating on why implementing IMAP correctly is not so easy, and the set of techniques we have been using to make our IMAP code as high-quality as we can. In this first part, we focus on one challenging aspect of IMAP: fine-grained retrieval and querying of emails.
Aerogramme is an experimental email server (& calendar, contacts), designed to be geo-distributed, hosted outside of datacenters, on refurbished hardware, and reliable even in presence of network issues and hardware failures. It is built on top of Garage and shares the same philosophy. Aerogramme is AI-free: we do not wish to use unethical technology and prefer to spend effort on careful craftmanship and community-building.
Implementing an IMAP server is not easy. Partly because IMAP is an old protocol, with a good number of extensions that has accumulated quite a bit of complexity over time. On top of that IMAP provides - for good reasons - two classes of features that are fundamentally challenging to implement: fine-grained retrieval and querying of email contents and concurrent multi-client multi-session access to mailboxes.
This is the first part in a series of posts discussing how we have been approaching IMAP access. In the past year, we have been refining Aerogramme's IMAP implementation to be "more correct", in a context where "correctness" is unfortunately not always well specified: IMAP and email are defined in documents that are often vague, and furthermore, real-world implementations do not always follow specifications.
Today, we'll walk you though our work on the correctness and reliability of Aerogramme for retrieving and querying emails, and explain why your mailbox is, in fact, a database...
This work was funded by NLNet under the "Aerogramme 1.0" grant, and could not have been possible without their support.
Feel free to join the Aerogramme matrix channel for updates or if you just want to chat!
One challenge of the IMAP specification is the rich feature-set it provides for retrieving mailbox and email contents. We may sometimes think of a mailbox as a directory containing plain email files; however, from the point of view of an IMAP server (or client), a mailbox is closer to a database, accessed using a dedicated query language.
For instance, mobile clients, which have slower and unreliable connectivity, benefit from fine-grained querying of a mailbox contents. User experience is much better if an email client can selectively fetch the subject of new emails (to update the list of emails in the mailbox) without having to first download all of their attachments or doing a sync of the entire mailbox.
To facilitate the mobile client use-case, IMAP specifies two key mechanisms for querying and (partial) retrieval of emails in a mailbox:
A direct consequence of these features is that an IMAP server actually needs to parse the emails, not just store them. It then needs to (correctly) interpret the (sometimes tricky) query language of SEARCH and FETCH, and internally support a data architecture that enable efficiently searching and querying over the emails.
Our implementation of SEARCH and FETCH is backed by the three following components:
The logic for SEARCH and FETCH is implemented as an interpreter that takes already parsed emails and walks down their AST to evaluate IMAP-specific queries1. This separates email structure (email ASTs do not depend on IMAP concepts) from IMAP-specific business logic. This layer has been significantly reworked in the last months, fixing a good number of logic bugs and edge cases in our implementation of the SEARCH and FETCH IMAP specification.
Aerogramme's internal data architecture splits mailbox state, email metadata, and email contents. It is briefly described in Aerogramme's documentation. Mailbox state (emails IDs and flags) and email metadata (parsed headers, date, size) are stored in Aerogramme's metadata storage using Garage K2V, while email contents are stored in blob storage using Garage S3. This allows SEARCH to be efficient by only reading pre-computed information in metadata storage. At the moment there are no other significant optimizations for FETCH/SEARCH; the likely next step would be to add a full-text search engine.
These components are all quite non-trivial! Let's now talk about the strategies we've deployed to make them as correct as we could.
We ran our implementation of FETCH and SEARCH through ImapTest: a testing tool for IMAP servers maintained by the Dovecot developers. ImapTest was invaluable in surfacing issues with FETCH and SEARCH, but is equally useful to test all other aspects of IMAP.
Most relevant for FETCH and SEARCH was the test suite provided with ImapTest: a collection of hand-crafted test scenarios testing many subtle or "interesting" aspects of the IMAP specification. Each scenario consists of IMAP commands to send to the server, and a specification of the corresponding expected responses.
Running the ImapTest test suite found a small number of bugs in SEARCH, mostly in edge-cases of the specification. However, testing FETCH revealed that our initial implementation of the BODY[<section>] subcommand was conceptually wrong in many cases! This subcommand of FETCH retrieves a sub-part of an email by following its structure, which we implement by walking down the email's AST. Our initial implementation was done by reading the IMAP specification and interpreting its sometimes vague wording as best as we could; only testing with ImapTest made us realize that our best-guess interpretation was wrong in many cases. More precisely: it did not match ImapTest's reading of the spec, which, in doubt, is what we prefer to follow!
ImapTest was also relatively pleasant to use to do manual "differential testing" for any remaining edge-cases: when we had any doubt, we could easily write additional scenarios and compare Aerogramme's output with Dovecot's; treating Dovecot as an oracle. After a few rounds of bugfixing, Aerogramme's implementation of FETCH and SEARCH is now in much better shape.
The lesson we learned is that the IMAP specification can leave room for interpretation in surprising ways. In fact, to further illustrate this point, let's talk about one ImapTest scenario that we haven't "fixed" yet in Aerogramme because we just found it very confusing, and we are not sure what to do!
He's a tricky case. SEARCH FROM <string> returns the list of emails whose From header "contains" the given string. Now, what does "contains" mean here, exactly? When running SEARCH FROM foo@example.com on the two following headers, which ones should match?
From: Foo Bar foo@example.com From: Foo Bar < "foo" (comment) @ example.com>
Some additional context on email syntax is useful here: these two email addresses are equivalent. The local-part of the email (before the @) allows quoted strings, so "foo" can be used and simply denotes foo. Email syntax also allows comments in various places; they are written between parentheses. Comments have no formal meaning but are shown by email clients and can be useful; they are sometimes used by mailing-list software to indicate the name of the list. As an example SYMPA emits From headers of the form From: Alice (via Super Friends List) list-address@server.org).
At the moment, Aerogramme implements SEARCH FROM as plain substring search on the text representation of the header: here, the first header matches, but not the second. However, the ImapTest test suite says that both headers should match! So, what does the specification says?
FROM <string> Messages that contain the specified string in the envelope structure's FROM field.
Hmm, so, what is this "envelope structure"? Reading further:
An envelope structure is a parsed representation of the [RFC5322] header of the message. [...] The from, sender, reply-to, to, cc, and bcc fields are parenthesized lists of address structures. [...] An address structure is a parenthesized list that describes an electronic mail address. The fields of an address structure are in the following order: display name, [SMTP] at-domain-list [...], mailbox name (local-part ABNF production from [RFC5322]), and hostname.
So the FROM field of an email's "envelope structure" contains a structured representation of parsed email addresses. Regarding our two headers above, they are both represented in the envelope structure as:
("Foo Bar" NIL "foo" "example.com")
What does it mean for this structured value to "contain" the string foo@example.com? Clearly none of the strings in the structure contain foo@example.com, so perhaps instead we should re-print the structure as an email address and do a substring search on that? However, there is not a unique way of printing a given email address, and the IMAP specification does not define any...
We are quite curious to know if IMAP experts have more to say on this point!
In the meantime, our bugfixes for FETCH and SEARCH have been shipped in Aerogramme 0.5.1 (see the release notes for more details), with the exception of two extra fixes shipped in Aerogramme 0.6.
FETCH and SEARCH operate on the parsed email ASTs produced by eml-codec. How do we ensure that we have correctly implemented all the subtleties of the email format in eml-codec, which is itself described in an old and tricky set of specifications? As often, the answer is: more testing.
To ensure our implementation is correct, we performed fuzzer-guided Property-Based Testing (PBT) of the email parser and printer in eml-codec. Specifically, we tested the following "roundtrip" property:
“for an arbitrary email value in eml-codec's internal AST, printing it then parsing the printed output must yield an equivalent AST”
The starting AST is generated by a fuzzer as a structured value using the Arbitrary trait; the cargo-fuzz tutorial calls this "Structure-Aware Fuzzing". A roundtrip in the other direction, i.e. "parse then print then test for string equality" would not generally hold, as there are many equivalent ways of printing the same email, for instance because of line folding...
While it may seem that any reasonable implementation would satisfy our roundtrip property, in practice, this methodology immediately surfaced a lot of bugs and edge cases.
The recurring theme was that the fuzzer would generate "exotic" AST values breaking the roundtrip property, for which we had to clarify:
In the first case, this fixed bugs or potential security issues for users of the parser (like Aerogramme) or printer. In the second case, it improved the definition of internal AST types, which is relevant when using eml-codec to programatically compose emails, not something we use in Aerogramme itself, but relevant for an experimental mailing-list server project in Deuxfleurs using the same library.
To illustrate the kind of issues that we are talking about here, let's look at an tricky example that was found using our fuzzing methodology.
The "MIME Part Three" specification (RFC2047) specifies a way of using non-ASCII text in selected places of email headers. (Full support for UTF-8 in headers, which eml-codec also supports, was only introduced later.) Where allowed by the specification, ASCII text can be replaced by an "encoded word": an ASCII encoding of non-ASCII text using special syntax introduced by the specification.
As an example, the UTF-8 word aérogramme can be encoded as follows:
=?utf-8?q?a=C3=A9rogramme?=
More generally, a MIME encoded word has the following structure:
=? <charset> ? <encoding> ? <encoded-text> ?=
When using the q encoding like above, most ASCII characters can be used directly in the encoded text, and other bytes must be encoded as = followed by their hexadecimal code.
Now, let us consider the following From header:
From: =?utf-8?q?@[?= X]
This looks like an encoded
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。