存储效率优化实战：从50PB到32PB

↑↑↑

当你决定关注「日志君」，你已然超越了99%的程序员

日志君导读：

春节假期回来就处于昏昏沉沉状态，因为感冒了，大家也要注意身体哈：）

今天给大家推送的是俄罗斯最受欢迎的邮件服务商之一Mail.Ru自行设计实现的一套邮件存储去重系统的实现在不影响性能的前提下，将包含120亿个邮件内嵌文件的存储系统占用量从原本的50PB缩减至32PB。一起来看看他们的这套系统是如何实现的。

来源：InfoQ，作者：Dmitriy Kalugin-Balashov，点击原文阅读查看原文。

对电子邮件服务的用户来说，邮箱容量早已不是值得关心的问题，几乎所有主流邮件服务商都提供了容量大到很少有人能用完的服务。然而对服务商来说，尽可能降低成本，提升系统，尤其是存储系统的使用效率总是很好的。考虑到很多用户会收到大量包含相同内容的邮件，如相同的邮件附件，或邮件内相同的图片，一些邮件服务商开始考虑采用去重技术将相同文件只保存一份，借此提高存储效率。

俄罗斯最受欢迎的邮件服务商之一Mail.Ru，自行设计实现了一套邮件存储去重系统，在不影响性能的前提下，将包含120亿个邮件内嵌文件的存储系统占用量从原本的50PB缩减至32PB。一起来看看他们的这套系统是如何实现的。

索引和正文只占到总存储量的15%，另外85%都是各种文件。因此有必要对文件（其实也就是邮件附件）进行进一步分析，并找出优化的方法。当时我们并没有使用文件去重技术，但是估计这种技术可将存储总量减少36%，因为很多用户会收到相同的邮件，如网店的报价单，包含图像等内容的社交网络新闻邮件等。本文将介绍我们在Albert Galimov的监管下实现去重系统的方法。两年前，随着俄罗斯卢布汇率下跌，我们开始考虑缩减Mail.Ru邮件服务的硬件和托管成本。为了设法省钱，先来看看我们的邮件是由什么组成的。

文件总量越来越多，我们需要能快速识别重复内容。一种简单的做法是根据内容为文件生成名称。为此我们使用了SHA-1算法，文件的原始名称存储在邮件内容中，因此无须担心原始名称的问题。

收到新邮件后，系统会先获取该文件，计算出哈希值，然后将结果加入到邮件信息中。这是为了在发送邮件时轻松确定以后的存储系统中，每个文件对应着具体哪封邮件而必须采取的步骤。

试试看上传一个文件到存储系统，然后看看相同哈希值的文件是否已经存在。这就意味着我们必须将所有文件哈希都存储起来。就把这个存储叫做哈希FileDB吧。

同样的文件可以附加到不同邮件中，因此我们需要通过计数器记录包含同一份文件的邮件数量。

每当上传新文件，该计数器的数字会递增。所有文件中约有40%的文件会被删除，因此如果用户删除的邮件中包含已经上传至云端的文件，计数器的数字还必须递减。如果计数器归零，对应的文件才会被真正删除。

接下来我们遇到了第一个问题：有关邮件的信息（索引）存储在一个系统中，有关文件的信息则存储在另一个系统中。这可能会造成一个问题，例如请考虑下面的流程：

1. 系统接到删除某封邮件的请求；

2. 系统检查邮件索引；

3. 系统容可以看到邮件有一个附件（SHA-1）；

4. 系统发送删除该文件的请求；

5. 因为程序崩溃，这封邮件并未实际删除。

此时邮件依然位于系统中，但计数器的数字已经减小了“1”。当系统收到删除该邮件的第二个请求，计数器的数字继续减小，因此可能面临这样的局面：文件依然附加在某封邮件中，但计数器已经归零了。

该算法很简单。除了文件哈希，我们还会在邮件中存储一个随机生成的数字。所有上传湖哦删除文件的请求都需要考虑这个随机数：对于上传请求，会将该数字添加至Magic数的当前值中；对于删除请求，则会从Magic数的当前值中减去这个随机数。避免数据丢失是最基本的要求。我们不能让用户打开一封邮件后发现自己的附件丢了。也就是说，在磁盘上存储一些冗余的文件也没什么大不了的。我们只需要一种算法，能够明确地决定计数器的“归零”是否为正确的结果。所以我们额外建立了一个名为Magic的字段。

因此如果所有邮件增加或减少计数器数值的操作次数是正确的，Magic数将等于“零”。否则文件不会被删除。

用一个例子来看看。有个名为sha1的文件，被上传了一次，邮件生成了一个随机（Magic）数，假设等于345。

随后收到一封包含相同文件的新邮件。该邮件生成了自己的Magic数（123）并上传了文件。新的Magic数会与Magic数的当前值（345）相加，计数器的数字增加1。因此现在FileDB中的Magic数值为468，计数器数字为2。

用户删除第二封邮件后，将从Magic数的当前值（468）中减去第二封邮件的Magic数，计数器数字也减1。

先看看正常过程。用户删除了第一封邮件，Magic数和计数器数字都归零。这意味着数据是一致的，可以删除文件。

接下来，假设出错了：第二封邮件发送了两个删除请求。计数器归零意味着已经没有邮件链接至该文件，但Magic数此时等于222，意味着出问题了：数据变得一致之前，文件不会被删除。

把这种情况进一步延展一下。假设第一封邮件也被删除了，此时Magic数（-123）依然意味着不一致。

作为一项安全措施，一旦计数器归零但Magic数没有归零（本例中计数器归零时Magic数值为222），文件将会添加“不要删除”标签。通过这种方法，就算在处理了一系列删除和上传操作，Magic数和计数器都归零后，我们依然可以知道该文件有问题，不应删除。

重新回到FileDB。每个项都有一组标志。无论用户是否主动使用，实际上都用得上（例如要将文件标记为不可删除）。

除了物理位置外，我们可以掌握文件的所有特性。物理位置是由服务器（IP）和磁盘决定的。服务器和磁盘可能个有两组。

但每块磁盘会存储大量文件（我们的实例中，大约存储了1,000,000个文件），这也意味着这些记录可以通过FileDB中同一个磁盘对加以区分，那么也就没必要将其存储在FileDB中了。可以把它们放在一个单独的表：PairDB中，随后通过磁盘对ID链接至FileDB。

不言而喻，除了磁盘对ID，我们还需要一个标志字段。先提起说一下，这个字段意味着磁盘是否被锁定（例如一个磁盘崩溃，需要从另一个进行复制，这样新数据才不会写入到这两个磁盘中）。

此外还需要知道每个磁盘有多少可用空间，因此也需要相应的字段。

为了让一切尽可能快速运行，FileDB和PairDB都必须位于内存中。我们原本使用了Tarantool 1.5，但现在应该已经在使用最新版了。FileDB有五个字段（长度分别为20、4、4、4、4字节），总长度36字节。此外每条记录都有一个16字节的头部，外加每字段1字节长度的指针，因此每条记录的总长度为57字节。

Tarantool允许指定最小分配大小，因此与内存有关的开销可以接近于零。我们会为每条记录严格分配刚好够用的内存数量。我们共有12,000,000,000个文件，因此：

(57 * 12 * 10) / (1024) = 637 GB

但这还没完，还需要为sha1字段提供索引，因此每条记录的总长度需要额外增加12字节，因此：

(12 * 12 * 10) / (1024) = 179 GB

所以我们一共需要800GB内存。但是别忘了还要复制，因此所需内存数量需要翻倍。

如果使用装备256GB内存的服务器，这样的机器一共需要八台。

我们还可以评估PairDB的大小。文件的平均大小为1MB，磁盘容量平均为1TB，因此一块硬盘平均可存储大约1,000,000个文件，那么我们需要28,000块硬盘。每条PairDB记录描述了两块磁盘，因此PairDB包含14,000条记录，相比FileDB实在是微不足道。

确定了数据库结构后，需要考虑与系统交互的API了。首先，我们需要确定Upload和Delete方法。但是别忘了还要去重：有一定概率打算上传的文件已经位于存储系统中，此时就没必要重新上传了。因此需要具备下列方法：

1. inc(sha1, magic) 负责计数器的递增。如果文件不存在则返回错误。别忘了我们还需要一个防止文件被错误删除的Magic数。

2. upload(sha1, magic) 将可在inc返回错误后调用。意味着该文件不存在，需要上传。

3. dec(sha1, magic) 将在用户删除一封邮件后调用，并首先减小计数器的数字。

4. GET /sha1 通过HTTP下载文件。

一起来深入看看上传过程中会发生什么事。在实现该接口的守护进程中，我们选择了IProto协议。守护进程必须能灵活缩放至任意数量的服务器，因此不能存储状态。假设通过Socket收到了一个请求：

通过命令名称可以了解头部的长度，因此我们首先读取头部。随后我们需要知道origin-len文件的长度，并据此选择要将文件上传到的服务器。通过PairDB获取所有记录（几千条）并使用标准算法查找需要的对：选择长度与所有对的可用空间总量相等的片段，在这个片段中随机选取一点，并选择该点所属的对。

然而用这种方式选择对有一定的风险。假设所有磁盘均90%满载，随后添加了几块新磁盘。有很大可能性所有新文件会被上传至新增的磁盘。为避免这种情况，我们不应计算磁盘对的可用空间总和，而要计算该可用空间的方根。

至此已经选择了一个对，但我们的守护进程是流式的，如果开始将文件上传至存储，将没有回头路。也就是说，在实际开始上传文件之前，我们会首先上传一个很小的测试文件。如果测试文件成功上传，则会从Socket中读取文件内容，并将其上传至存储。否则会选择另一个对。SHA-1哈希可以即时读取，因此可在上传的同时进行计算。

再看看从加载程序（Loader）将文件上传至所选磁盘对的情况。在包含该这些磁盘的机器上，我们设置了Nginx并使用了WebDAV协议。邮件抵达后，FileDB还没有相应的文件，因此需要通过加载程序上传至磁盘对。

但这并不会妨碍到其他用户收到相同邮件：假设有两个收件人，需要注意，此时FileDB还没有拿到这个文件，因此将由另一个加载程序上传这个文件，并可能选择上传至同一个磁盘对。

Nginx通常会正确解决这种问题，但我们需要对整个过程进行控制，因此使用一个复杂的名称保存该文件。

文件名中红色部分是每个加载程序放入的随机数。借此可确保两个PUT方法不会重叠，进而导致上传两个不同的文件。一旦Nginx响应了201 (OK)信息，第一个加载程序会执行一个原子级的MOVE操作，并指定文件的最终名称。

第二个加载程序完成文件上传操作并执行MOVE后，文件会被覆写，但这算不得什么大问题，因为文件始终都是那一个。文件位于磁盘上之后，会向FileDB加入一条新记录。我们所用的Tarantool版本被分为两个空间，我们目前只使用了space0。

然而我们并不是简单地向FileDB新增一条记录，而是会使用存储过程让文件计数器数字增加，或向FileDB添加新记录。为什么这样做？当加载程序确定FileDB中不存在该文件，随后上传文件内容并通过处理给FileDB中新增加一条记录的全过程中，其他人可能已经上传了该文件并添加了对应的记录。上文的例子曾经考虑过这种问题：两个收件人收到了同一封邮件，因此两个加载程序开始上传文件，一旦第二个加载程序先行上传完成，将会通过处理向FileDB中添加新记录。

此时第二个加载程序会让文件计数器的数字增加。

然后再来看看dec方法。我们的系统有两个高优先级任务：可靠地将文件写入磁盘，以及从磁盘快速交付给客户端。文件的物理删除会产生一定的工作负载，导致这两个任务变慢。因此删除操作实际上是脱机进行的。Dec方法本身可以让计数器减小。如果随后计数器和Magic数都归零，意味着已经没人需要该文件了，因此我们会在Tarantool中将相应的记录从space0移动至space1。