Quality IMAP, Part 1: Your Mailbox Is A Database
过去一年,我们显著提升了 Aerogramme IMAP 实现的可靠性与正确性。这是系列博客文章的第一篇,详细阐述为什么正确实现 IMAP 并不容易,以及我们用来让 IMAP 代码尽可能高质量的一系列技术。在这第一篇中,我们聚焦于 IMAP 的一个具有挑战性的方面:邮件的细粒度检索与查询。
Aerogramme 是一个实验性邮件服务器(& 日历、联系人),设计目标是地理分布式、托管于数据中心之外、运行在翻新硬件上,并且在存在网络问题和硬件故障的情况下依然可靠。它构建于 Garage 之上,并共享相同的理念。Aerogramme 是 AI-free 的:我们不希望使用不道德的技术,而更愿意将精力投入到精心的工艺和社区建设上。
实现一个 IMAP 服务器并不容易。部分原因是 IMAP 是一个古老的协议,拥有大量扩展,随着时间推移积累了不少复杂性。除此之外,IMAP 还——出于充分理由——提供了两类从根本上难以实现的功能:邮件内容的细粒度检索与查询,以及多客户端多会话对邮箱的并发访问。
这是讨论我们如何着手处理 IMAP 访问的系列文章的第一篇。在过去一年中,我们一直在改进 Aerogramme 的 IMAP 实现,使其“更加正确”;而在这样一个语境下,“正确性”不幸并不总是被良好地规定:IMAP 和电子邮件的定义文档往往含糊不清,此外,现实世界中的实现也并不总是遵循规范。
今天,我们将带你了解我们在 Aerogramme 检索和查询邮件的正确性与可靠性方面的工作,并解释为什么你的邮箱实际上就是一个数据库……
这项工作由 NLNet 在“Aerogramme 1.0”资助下提供资金,没有他们的支持就不可能实现。
欢迎加入 Aerogramme 的 matrix 频道获取更新,或者只是来聊聊天!
你的邮箱就是一个数据库
IMAP 规范的一个挑战在于它为检索邮箱和邮件内容提供的丰富特性集。我们有时可能把邮箱想象成一个包含纯邮件文件的目录;然而,从 IMAP 服务器(或客户端)的角度来看,邮箱更接近于一个数据库,使用一种专用的查询语言来访问。
例如,移动客户端连接速度较慢且不可靠,它们能从对邮箱内容的细粒度查询中受益。如果邮件客户端能够选择性地获取新邮件的主题(以更新邮箱中的邮件列表),而无需先下载所有附件或对整个邮箱进行同步,用户体验会好得多。
为了便利移动客户端的使用场景,IMAP 规定了两大关键机制,用于查询和(部分)检索邮箱中的邮件:
- SEARCH 在邮箱中查找满足给定“搜索条件”的邮件;它返回这些邮件的标识符。条件可以基于特定头字段的内容、日期、文本内容或标志——附加在邮件上、可由客户端编辑的元数据——来筛选邮件。它还可以使用 OR/NOT/AND 布尔运算符对这些条件进行任意组合。
- FETCH 根据邮件的标识符查询邮件内容。极其灵活。除了获取整封邮件之外,它还允许基于邮件的高层结构(邮件具有递归结构,其子部分包含例如附件,或同一内容的 text+html 替代视图)、其原始字节级表示,或两者的组合来查询邮件。可以(根据结构)选择性地获取邮件的子部分,获取邮件的“抽象语法树”(AST)及其某些头字段的值,还可以获取子部分的特定字节范围。
文章标题:高质量的 IMAP,第一部分:你的邮箱就是一个数据库 | Aerogramme 博客
这些特性的一个直接后果是,IMAP 服务器实际上需要解析电子邮件,而不仅仅是存储它们。然后它需要(正确地)解释(有时颇为棘手的)SEARCH 和 FETCH 查询语言,并在内部支持一种数据架构,使其能够高效地对电子邮件进行搜索和查询。
Aerogramme 中的电子邮件查询
我们对 SEARCH 和 FETCH 的实现由以下三个组件支撑:
SEARCH 和 FETCH 的逻辑被实现为一个解释器,它接收已经解析好的电子邮件,并沿其 AST 向下遍历,以评估 IMAP 特定的查询1。这将电子邮件结构(电子邮件 AST 不依赖 IMAP 概念)与 IMAP 特定的业务逻辑分离。这一层在过去几个月里经过了大幅重写,修复了我们 SEARCH 和 FETCH IMAP 规范实现中的大量逻辑错误和边界情况。
电子邮件解析使用 eml-codec 配套库完成,该库同样由我们开发和维护。eml-codec 库将电子邮件解析为丰富、结构化的 AST,同时还提供对与相关 AST 节点对应的原始输入切片的访问;这是实现 FETCH 所必需的。在过去一年里,eml-codec 已从一个带有 IMAP 特定怪癖的电子邮件解析库,演变为一个健壮、经过充分测试、通用的电子邮件库,同时支持电子邮件的解析和打印。你可以在我们进行中的设计文档中阅读更多关于该库设计选择的内容。
Aerogramme 的内部数据架构将邮箱状态、电子邮件元数据和电子邮件内容分开。Aerogramme 的文档中对此有简要描述。邮箱状态(电子邮件 ID 和标志)和电子邮件元数据(解析后的标头、日期、大小)使用 Garage K2V 存储在 Aerogramme 的元数据存储中,而电子邮件内容使用 Garage S3 存储在 blob 存储中。这使得 SEARCH 只需读取元数据存储中预先计算的信息即可高效运行。目前没有针对 FETCH/SEARCH 的其他重大优化;可能的下一步是添加一个全文搜索引擎。
这些组件都相当不简单!现在让我们谈谈我们为尽可能保证它们正确而部署的策略。
测试 Aerogramme 的 FETCH 和 SEARCH 查询解释器
我们让 FETCH 和 SEARCH 的实现通过了 ImapTest:一个由 Dovecot 开发者维护的 IMAP 服务器测试工具。ImapTest 在暴露 FETCH 和 SEARCH 问题方面非常宝贵,但在测试 IMAP 所有其他方面时同样有用。
与 FETCH 和 SEARCH 最相关的是 ImapTest 提供的测试套件:一组手工编写的测试场景,测试 IMAP 规范中许多微妙或“有趣”的方面。每个场景由要发送到服务器的 IMAP 命令,以及相应预期响应的规格说明组成。
运行 ImapTest 测试套件在 SEARCH 中发现了少量 bug,大多位于规范的边界情况中。然而,测试 FETCH 揭示出我们最初对 BODY[<section>] 子命令的实现在许多情况下在概念上就是错误的!FETCH 的这个子命令通过沿电子邮件结构向下遍历来获取电子邮件的子部分,我们通过遍历电子邮件的 AST 来实现它。我们最初的实现是通过阅读 IMAP 规范并尽可能好地解释其有时含糊的措辞来完成的;只有用 ImapTest 测试才让我们意识到,我们最佳猜测的解释在许多情况下是错误的。更准确地说:它与 ImapTest 对规范的解读不一致,而在存疑时,我们更愿意遵循后者!
ImapTest 在用于对任何剩余边界情况进行手动“差分测试”时也相对令人愉快:当我们有任何疑问时,我们可以轻松编写额外的场景,并将 Aerogramme 的输出与 Dovecot 的输出进行比较,把 Dovecot 当作 oracle。经过几轮 bug 修复,Aerogramme 的 FETCH 和 SEARCH 实现现在状态好多了。
我们得到的教训是,IMAP 规范在某些地方会以出人意料的方式留下解释空间。事实上,为了进一步说明这一点,让我们谈谈 Aerogramme 中一个我们尚未“修复”的 ImapTest 场景,因为我们觉得它非常令人困惑,不确定该如何处理!
示例:SEARCH 与结构化字段的困惑案例
这是一个棘手的情况。SEARCH FROM <string> 返回 From 头“包含”给定字符串的邮件列表。那么,这里的“包含”究竟是什么意思?对以下两个头执行 SEARCH FROM [email protected],哪些应该匹配?
From: Foo Bar <[email protected]>
From: Foo Bar < "foo" (comment) @ example.com>
这里补充一些关于邮件语法的背景知识会很有用:这两个电子邮件地址是等价的。电子邮件的本地部分(@ 之前)允许使用带引号的字符串,因此可以使用 "foo",它只是表示 foo。邮件语法还允许在各种位置出现注释;注释写在括号之间。注释没有正式含义,但会被邮件客户端显示出来,可能很有用;邮件列表软件有时会用它们来标明列表名称。例如,SYMPA 发出的 From 头形如 From: Alice (via Super Friends List) <[email protected]>)。
目前,Aerogramme 将 SEARCH FROM 实现为对头的文本表示进行纯子串搜索:在这里,第一个头匹配,但第二个不匹配。然而,ImapTest 测试套件表示两个头都应该匹配!那么,规范是怎么说的呢?
IMAP 规范2 关于 SEARCH 是这么说的:
FROM <string>
Messages that contain the specified string in the envelope
structure's FROM field.
嗯,那么,这个“envelope structure”是什么?继续往下读:
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.
因此,一封邮件的“envelope structure”的 FROM 字段包含解析后的电子邮件地址的结构化表示。对于上面两个头,它们在 envelope structure 中都表示为:
("Foo Bar" NIL "foo" "example.com")
这个结构化值“包含”字符串 [email protected] 意味着什么?显然,结构中的任何字符串都不包含 [email protected],所以也许我们应该改为将该结构重新打印为电子邮件地址,然后对其做子串搜索?然而,打印给定电子邮件地址的方式并不唯一,而 IMAP 规范也没有定义任何方式……
我们非常想知道 IMAP 专家对此是否有更多看法!
与此同时,我们对 FETCH 和 SEARCH 的修复已经随 Aerogramme 0.5.1 发布(详情见发布说明),此外还有两个额外的修复随 Aerogramme 0.6 发布。
改进 Aerogramme 中的邮件解析
FETCH 和 SEARCH 操作的是由 eml-codec 生成的解析后邮件 AST。我们如何确保在 eml-codec 中正确实现了邮件格式的所有细微之处,而 eml-codec 本身又是由一套古老而棘手的规范所描述的?答案往往是一样的:更多的测试。
针对 eml-codec 的基于属性的测试
为确保我们的实现正确,我们对 eml-codec 中的邮件解析器和打印器进行了模糊测试引导的基于属性的测试(PBT)。具体来说,我们测试了以下“往返”属性:
“对于 eml-codec 内部 AST 中的任意邮件值,先打印它,再解析打印输出,必须得到等价的 AST”
像 {{NAME_ab12cd34}} 这样写的值是真实值的占位符。在回复和工具调用中都要完全按照所写使用它们:它们会在任何内容运行之前被填入真实值。不要请求验证它们,也不要用示例替换它们。
起始 AST 由模糊测试器使用 Arbitrary trait 生成,作为一个结构化值;cargo-fuzz 教程称此为“结构感知模糊测试”。反方向的往返测试,即“解析再打印再检查字符串相等性”,通常并不成立,因为打印同一封邮件存在许多等价方式,例如因为行折叠……
尽管看起来任何合理的实现都会满足我们的往返性质,但在实践中,这种方法立即暴露了大量 bug 和边界情况。
反复出现的主题是,模糊测试器会生成“奇异”的 AST 值,破坏往返性质,对此我们必须澄清:
- 这些是否揭示了解析器与打印器之间的不一致/混淆,即该值在打印后可能导致无效语法,或解析成不同 AST 的语法;
- 这些值是否实际上应被视为无效;这意味着加强 AST 不变量并相应修复基于模糊测试器的生成器;
- 或者 AST 值的“等价性检查”函数是否需要放宽(在某些情况下,语法不同的值在实现细节层面代表“相同”的概念值)。
在第一种情况下,这修复了解析器用户(如 Aerogramme)或打印器的 bug 或潜在安全问题。在第二种情况下,它改进了内部 AST 类型的定义,这在使用 eml-codec 以编程方式组合邮件时相关——我们在 Aerogramme 本身中不使用,但对 Deuxfleurs 中使用同一库的实验性邮件列表服务器项目相关。
为了说明我们在这里谈论的问题类型,让我们看一个通过我们的模糊测试方法发现的一个棘手例子。
示例:编码词的把戏
“MIME 第三部分”规范(RFC2047)规定了在邮件头选定位置使用非 ASCII 文本的方式。(邮件头中对 UTF-8 的完整支持——eml-codec 也支持——是后来才引入的。)在规范允许的地方,ASCII 文本可以被“编码词”替换:使用规范引入的特殊语法对非 ASCII 文本进行 ASCII 编码。
例如,UTF-8 词 aérogramme 可以编码如下:
=?utf-8?q?a=C3=A9rogramme?=
更一般地,MIME 编码词具有以下结构:
=? <charset> ? <encoding> ? <encoded-text> ?=
当像上面那样使用 q 编码时,大多数字符可以直接在编码文本中使用,其他字节必须编码为 = 后跟其十六进制代码。
现在,让我们考虑以下 From 邮件头:
From: =?utf-8?q?@[?= X]
这看起来像一个编码词后跟一些额外垃圾;这是一个有效的 From 邮件头吗?也许令人惊讶的是,这个邮件头中没有编码词,而且它是一个有效的电子邮件地址!电子邮件地址是 =?utf-8?q? @ [?= X](技术上有效!),其中 '@' 后的部分使用了不常见的“域字面量”语法。
现在,考虑以下具有相同字节表示的 Subject 邮件头:
Subject: =?utf-8?q?@[?= X]
这一次,邮件头的第一部分是一个编码词,整个邮件头告诉我们主题是字符串 @[ X]!
这种行为的解释来自规范(在这一点上相当清楚):在 <encoded-text> 中可以未转义使用的 ASCII 字符集取决于编码词出现的上下文。
编码词可以出现在 From 邮件头中(例如 From: =?utf-8?q?a=C3=A9rogramme?= <[email protected]> 是有效的),但在该上下文中它们不能未转义使用 @ 或 [,这就是为什么第一个例子实际上不包含有效的编码词。在 Subject 邮件头的上下文中,有效未转义字符集更广泛,包括 @ 和 [,使得 =?utf-8?q?@[?= 是一个表示字符串 @[ 的有效编码词。
像 {{NAME_ab12cd34}} 这样写的值是真实值的占位符。在回复和工具调用中完全按照它们书写的方式使用:它们在运行前会被填入真实值。不要要求验证它们,也不要用示例替换它们。
为了实现这一行为,我们需要正确追踪解析编码词时所处的上下文,依据该上下文对其进行“分词”,并且在我们的邮件 AST 中以及打印过程中追踪上下文敏感性。要让解析、内部 AST 与打印这三者之间的每一个细节都正确对齐,我们尝试了好几次!在这个过程中,我们的属性测试(property-testing)设置极其有用,因为它能迅速构造出像上面那样的新复杂样例,从而暴露出我们代码在边界情况下的缺陷。
这里的教训是:邮件规范可能相当复杂,实施起来也很棘手,即便这些规范本身是清晰的!而且,根据我们的经验,如果没有自动测试生成(比如我们的模糊测试设置),手动想出真正能覆盖边界情况的例子是非常困难的……
如果你想看更多细节,我们在 eml-codec 上所做的大部分 PBT/模糊测试工作是在 eml-codec 0.3 中完成的,并随 Aerogramme 0.4 一起发布,另外一些改进随 Aerogramme 0.6 发布。
在真实世界邮件上测试 eml-codec
我们在真实世界邮件集合(超过 10 万封邮件)上测试了 eml-codec,以评估并改进 eml-codec 解析器对无效或损坏语法的恢复策略。
真实世界中发现的许多合法邮件,确实不符合邮件规范。通常,无效或损坏语法的使用是局部的(限于特定头部,或头部的某些部分);在某些情况下,这“仅仅”是对规范的轻微偏离。
示例:message ID 的多种形态
“message ID”的情况可以作为一个例子。邮件可以被赋予一个标识符(通过 Message-ID 头部指定),以便后续邮件引用它(通过 In-Reply-To 和 References 头部)。例如,这对于在邮件客户端中显示邮件“会话串”很有用。message ID 语法也用于通过 Content-ID 头部标识附件。
阅读规范可知,message ID 的形式为:
<[email protected]>
而 In-Reply-To 和 References 所使用的 message ID 列表,则用空白分隔各个 message ID:
<[email protected]> <[email protected]> <[email protected]>
规范还记载,对于列表语法,“过时”语法(我们必须支持)可以包含 message ID 周围的额外文本……
那么,在我们的真实世界邮件样本中发现了什么呢?
Content-ID: <1855BC2C-077C-406B-AEA4-CAF088755676>
-> 由 apple-mail 发出,且无效:没有 @!
Content-ID: text-body
Message-ID: [email protected]
-> 无效:没有尖括号 </>!
In-Reply-To: <[email protected]>; from [email protected] on Mon, Nov 25, 2002 at 11:01:01AM -0800
In-Reply-To: Your message of Thu, 18 Mar 1993 22:28:19 GMT.\n <[email protected]>
-> 有效:这是规范所记载的“过时”语法的一个实例。
References: <abc@def>,<foo\n\[email protected]>,<[email protected]>
-> 逗号作为过时语法的一部分是有效的,但第二个 message-id 因为单词中间存在不正确的折行(\n\t)而格式错误。
为真实世界邮件设计 eml-codec
其结果是,eml-codec 需要能够从损坏的语法中恢复:对于包含无效语法的邮件,它应当能够丢弃损坏的部分,并尽可能从邮件其余部分解析出内容,而不是简单地返回错误。理想情况下,它还应能够解析无效但常见的规范偏离,以恢复信息而不是将其丢弃。
我们首先用粗粒度的恢复策略扩展了 eml-codec,例如,如果我们无法解析某个头部字段,就丢弃整个头部字段。这使我们迅速达到一种状态:eml-codec 解析器成为一个全函数:对于任何输入字节,它总是返回一个表示符合 RFC 的邮件的电子邮件 AST3,丢弃它不理解的任何输入部分。
像 {{NAME_ab12cd34}} 这样书写的值是真实值的占位符。在回复和工具调用中都请完全按原样使用它们:它们会在任何东西运行之前被填入真实值。不要要求验证它们,也不要用示例替换它们。
随后我们对解析器进行了插桩,使其在恢复过程中每次丢弃损坏输入时记录日志,并用插桩后的解析器对我们收集到的邮件进行运行。这为我们提供了大量语法损坏的合法邮件示例。随后,在每一种情况下,我们都手动查看那段损坏的语法,看看能否从中理解出一些含义,并决定是否:
- 我们可以合理地扩展解析器来解析它;
- 我们可以更有选择性地丢弃它(例如,只丢弃列表中的一个损坏元素,而不是丢弃整个列表);
- 我们现有的丢弃策略已经是我们能做到的最好方案。
整个过程特别有意思,因为它让我们直面真实世界邮件的诸多微妙之处(有时与规范的“真相”相去甚远);eml-codec 现在在处理真实世界邮件时稳健多了!
这套方法涉及大量权衡和判断:我们能添加的解析 hack 在代码质量以及解析歧义方面都是有限度的;而且某些类别的邮件比其他类别更关键(例如,我们不应该花太多精力去支持垃圾邮件)。eml-codec 的一个强设计约束是,除了少数例外,我们希望其内部 AST 只表示符合 RFC 的邮件,因此我们不想仅仅为了“恢复更多”而让它混入随机的损坏语法。尤其是整个过程帮助我们厘清了 eml-codec 作为库的设计。
更多细节可以查看 eml-codec 0.3.1 的发布说明,其中完成了大部分工作,它建立在 eml-codec 0.2 的解析恢复初始设置之上。两者都随 Aerogramme 0.4 一同发布。
IMAP 的搜索和检索功能至关重要,因为它们让客户端在处理包含数千封邮件的邮箱时仍能拥有流畅的用户体验。本文聚焦于把这些基础功能做对。但更广泛地说,我们认为“邮箱即数据库”的视角很有用,因为它提出了一个问题:我们可以启用和支持哪些终端用户工作流?我们应该优先考虑或优化哪些功能,以最好地支持日常邮件用户的工作流?
请期待本系列的下一篇博文,届时我们将讨论 IMAP 服务器的另一个重大挑战:邮箱并发!
沿用数据库的类比,逻辑上的下一步可能是这样优化:先在邮件上运行查询之前“预编译”查询。目前我们不知道这种优化在实践中是否真的重要……
这链接到 IMAP4rev1,但更新的 IMAP4rev2 在这个主题上并没有更具体
当前的 eml-codec AST 对这一规则有少数精选的例外,在明确定义的情况下允许表示不符合规范的数据。其中一种情况是不符合规范的 message ID,例如没有 @... 的 message ID