Levy's ink.
Doodles, whimsy & life.
About
Blog
Mess
Catalog

[教程向] 从零开始造个云存储系统

据说现在云计算越来越火了,为了赶上这一波潮流,我们也打算从零开始老司机网盘云存储系统,提供像Dropbox、百度网盘在任何地方任何设备都能通过网页/客户端访问的存储服务。

云存储系统1.0:服务基础架构

首先,我们需要一台服务器。嗯,不用太好,找个地方随便攒个台式机凑合吧,将其插上不断电电源,就勉强算个能用的机器了。当然了,因为我们要做网盘,所以这台机器的硬盘得大,先上个2TB的吧。

于是我们在这台台式机上装了一个操作系统,并在上面装了一个NodeJS顺带用npm装了一个Express(Python党请自动替换为(Python, pip, Django/Flask)套装)。为了简单起见,我们暂时不管客户端的开发,做一个可以在任何平台通过浏览器访问的网页版先。

由于网页前端和后端通过HTTP协议通讯,自然地,文件的下载/上传分别通过GET/POST协议。于是我们用Express实现了如下几个接入点:(灵魂画师上线)

当然,为了简单起见,我们并没有打算在我们的网盘上提供文件夹结构(毕竟都在一个大目录下也可以用嘛是吧 )。具体地说,我们在本地维护了一个文件夹用来容纳用户上传的文件,而后分别用NodeJS文件系统包提供的API操作该目录,在其中保存、读取文件以及获得整个目录的文件列表。文件在其中的保存名与上传时指定的名字相同,这样在下载时只需要简单地做路径join就能直接读取到该文件了。

好了,我们实现了一个云存储系统。本文结束.....................了么?

并没有。

云存储系统2.0:单机可扩展性

因为,随着我们在里面存的东西越来越多,我们发现用来存储文件的台式机硬盘满了

解决方式简单粗暴——换个更大的硬盘!然而不久之后我们发现,某宝上能买到的最大的硬盘也已经装不下这个硕大的文件夹了(暂不考虑文件系统能不能容纳如此大尺寸的单目录),所以我们决定在这台台式机上挂载足够多的硬盘,当空间不足时再加挂新硬盘即可。新的问题又来了:由于我们的所有文件都在一个目录下,而其他硬盘无法将容量提供给该目录(Unix系系统可以挂载给该目录的子目录,但仍然不能让同一个目录挂载多个硬盘),故我们还是不能将装上的硬盘都用于扩充我们的云存储系统

这可是一个很糟糕的问题。在这种情况下,最直观的解决方式是RAID-0(定义见英文维基),不过我们暂时不考虑RAID这样硬件层面的解决方式,而是自己实现系统解决。解决方式很简单,维护位于不同磁盘上的若干目录,并将文件分散在这些目录中。

新的问题是,当用户决定下载一个文件时,NodeJS实现的网站后台如何知道这个文件在哪一个目录中呢?其答案有如下两种:

  • 维护一个数据库,当写入该文件时,顺便在数据库中记录每个文件所在的目录。这样一来,读取文件时就可以通过查询数据库得知该文件的存储位置。
  • 借鉴哈希表(散列表)的方式,通过文件名计算哈希值确定该文件的存储位置。当哈希值足够随机时,被存储的文件会在分布的目录间均匀分布。

考虑到第一个方法还要再给我们的台式机上装一个数据库,而且数据库本身太大了的话还不知道往哪里放,我们采用第二种方法:当用户访问文件时,我们计算文件名的MD5值,并将其对磁盘个数取模来确定其所在的磁盘编号:

int location = Calc_MD5(filename) % NUM_OF_DISKS;

至此,我们成功地做好了一个可以支持超多硬盘扩展的云存储系统,从而提供几百TB的存储空间了!

还能不能更给力一点?

云存储系统3.0:集群可扩展性

随着我们的容量增大,周围的小伙伴也开始使用我们的网盘服务了,于是系统中存储的内容迎来了一次井喷,最火爆的时候甚至每秒钟都有成百上千个连接连上Web后台上传/下载文件。问题随之而来:这一台台式机的CPU、内存似乎已经不能够很好的应付这大量的并发请求,用户经常要等很久服务器才能响应,有时候Web后台甚至会因为内存不足挂掉;另外,增长的越来越快的存储空间需求让挂载了10个硬盘的台式机也再也腾不出可用空间了。

于是乎,现在是时候引入更多的机器了。在不同机器间分配文件,我们也面临着类似的策略选择:是专门维护一个服务器记录不同文件所在服务器,还是使用哈希的方式自行确定?前者是大名鼎鼎的Google File System以及Hadoop Distributed File System使用的方式,然而我们为了系统能够进一步扩展,仍然选择了后者。

新架构如上,我们将计算哈希值确定文件所在位置的操作放在了前端,而服务器仅仅提供存储在该目录上文件的读取接口。这样一来,我们成功地将整个系统扩展到机器集群上,从而能给大家提供无限量的网盘,走向人生巅峰了。

全剧终。 (当然不是真的了...)

云存储系统4.0:副本存储和可靠性

云存储系统3.0顺利运行了很长一段时间,直到有一天,机房中的2号机器硬盘因为常年读写报废了,这对于硬盘是非常正常的事,尤其当硬盘数目增加后发生的几率会陡增。

这一报废,在这个硬盘上存储的所有文件全部丢了。由于这个硬盘存储了哈希值取模后结果为2的全部文件,所以这一部分文件也就再也不能找回来了。我们因此蒙受了巨大的损失,于是决定再次升级我们的系统,使其尽量减少数据丢失的可能。

既然硬盘损坏不可避免,我们能够将文件多保存几份呀!本着这样的思路,我们设计了冗余存储的策略:每当用户上传文件时,用户不仅需要在通过哈希值算出的服务器上存储该文件,还要将该文件上传到该服务器编号之后的另外n台上作为副本;下载文件时,用户试图从哈希值算出的服务器开始读取该文件,若发现该文件在当前服务器已经损坏,则试图在下一个服务器上读取其副本,流程简图如下:

当发现硬盘损坏后,我们能够及时利用副本恢复存储的内容。这样一来,只要不发生大规模损坏,我们便不会担心数据真的丢失了。

总之,通过上线更可靠的云存储系统4.0,我们迎来的老司机们的如潮好评,直到...

云存储系统5.0:动态扩展和一致性哈希

这次问题的提出,与其说是源于老司机们的不满,不如说是来自于运维人员的吐槽。由于数据量不断增大,业务不断拓宽,我们也不停通过增加新服务器的方式来扩充整个系统的容量。然而由于整个文件到服务器的分配方式是通过散列取模的方式实现的,服务器增加后导致整个系统中存储的所有文件都需要重算哈希,而且其中大部分文件都需要迁移去另外的服务器。运维人员在执行若干次机房扩充操作后,实在受不了扩充涉及的巨大计算量、网络流量和因此带来的整个服务在一段时间的完全停运,强烈要求我们采取新的算法降低系统扩充成本。

因此,我们引入了一致性哈希(Consistent Hash)来解决这个问题。(如果要系统的了解该算请直接参考维基百科,在这里我们只是对其做粗略的介绍)

普通哈希函数通过对MD5取模的方式简单地将文件分配给不同服务器,从而导致被除数改变时整个分配规则发生巨大的变动;一致性哈希则正是针对这一点,建立连续变动的分配规则,防止结点数导致的分配规则大变。

具体实现上,一致性哈希首先对每一个容纳结点(也就是服务器)计算MD5值,并将其排列在MD5函数的值域上,如下图。

这样排布之后,对于值域上每个结点,从该点的哈希值开始直到下个结点哈希值前的部分为该结点的“辖域”(上图中与结点颜色相对的大括号部分),而最末尾结点的辖域则包含其之后的以及第一个结点之前的部分。为了更直观表达辖域和结点的关系,我们索性将MD5函数值域首尾相连,形成一个哈希环,并将环上不同结点的辖域涂色,效果如下:

哈希环构建完成后,轮到被分配的文件本身出场了:对于每一个文件,我们在计算其MD5值后确定其在哈希环上的位置,而后看看该位置是哪个结点的辖域,就将该文件分配给哪个结点。假如结点和文件均能够大致均匀分布在哈希环上,则文件能被很好的均分到各个结点中。

完美!

那么接下来,我们要增加新的存储结点了。如下图所示,新增加的蓝色结点加入哈希环并从已有的红色结点的辖域中“抢夺”了一部分。我们需要做的也就显而易见了:在红色结点对应的服务器将哈希值处于由红转蓝这一范围的文件全部转移到新结点中。

这样一来,如果分布理想,每次增删结点带来的文件转移成本仅为总文件数的 1/NN为存储结点总数),当存储结点量大时该成本几乎可以忽略。另外更重要的一点在于,文件转移时影响到服务质量的结点仅有被波及的两个,其余结点可以毫无影响地继续提供存于其上文件的读取服务,从而使结点增删操作完全不影响整个系统对外的服务质量。

那么,这样做会不会让哈希表的效率大幅降低呢?哈希表最引以为傲的就是其 O(1)的访问时间,我们不能接受遍历哈希环上的结点来寻找文件所属辖域带来的 O(N)的遍历开销。

事实上,给定一个文件的MD5,我们要做的是寻找比该值大的结点中MD5最小的一个。所以,我们不难想到使用平衡树来加速该操作。通过在平衡树上检索,我们能将该操作开销减少至 O(logN),考虑到服务器的数目 N并不大(我们没有这么多钱买几百万台服务器),我们能忍受这样的效率损失。

DONE? NOT YET.

云存储系统6.0:跨机房备份和加速

通过一致性哈希提供的低成本动态扩展,我们将我们的云存储系统基础设施扩展到了一大个机房。不幸的是,这个机房在某一夜晚因为打雷而停电了,导致我们的整个网盘服务都停摆了好几个小时。尽管对此抱怨的用户并不多,但我们开始和其他机房商量、布置若干个备份机房以防止某一机房的服务器集体停机时造成服务崩溃。这时我们碰到了一些在单一机房没有考虑的问题:

  • 同一机房间服务器处于同一内网,可以很方便、快速而安全地进行内部数据传输;当存储云跨机房时,不同机房间通过公网通讯,拥有很多安全隐患。该问题可以通过涉及更安全的通信协议,或直接搭建vpn解决。
  • 跨机房网络延迟往往远大于单一机房。由于我们利用多机房进行数据备份,故需要用上文所述的写入多份的方式创建文件副本。而原本我们采用的同步写入策略规定,只有当所有副本全部写入成功后用户的存储请求才能成功返回,在跨机房、高延迟环境下,每一个用户存储请求都需要等待跨机房写入请求成功,从而造成用户等待时间大幅上升。

针对第二点,我们采取了异步更新的方式维护副本,如下图:

其中左边是当写入副本数目为3时原本的同步更新流程,右边是该情况下异步更新的流程。可以看到,由于存储请求发起时并不会跨机房访问,故用户依然能在相当短的时间内收到“上传成功!”的提示,只不过这时候跨机房副本并没有做好罢了。

那么跨机房副本什么时候写入呢?

答案是我也不知道... 写入时机的调度在不同云存储系统中有各种实现形式,而我们可以采取一个简单粗暴的方式:定时询问——对于每个机房的服务器,每隔一段时间,便问其他机房有没有需要给交给自己的副本。当然,如果机房数目不多,可以对全体询问;而若机房很多,则需要采用部分询问、通过类似Gossip协议的方式在若干次询问周期后将副本传递给所有应该存储的机房。

说那么复杂,总之在一个机房写入后是需要时间才会将副本同步到其他机房的。

那么这就带来一个不一致(Incosistency)的问题:若一个用户上传文件并提示上传成功,而存储机房偏偏在将该文件副本同步出去前挂了,那该用户将会惊讶地发现,自己上传的文件不见了。

这符不符合预期呢?答案是肯定的。用户能在该机房在恢复运行后看到自己当初上传的文件,而这种策略被起了一个更好听的名字:最终一致。根据CAP定理(先给一个wikipedia的定义,有时间专开博文填坑),最终一致也是在追求分区容忍性和可访问性的情况下一个大家都接受的均衡策略。

跨机房备份还为我们带来了一个额外的惊喜:跨区加速。众所周知,中国国内的国际出口带宽很有限,所以我们托管在国内机房的资源不能被大洋彼岸的友人们很好的访问。由于我们已经设计好了可以跨机房备份的云存储系统,我们只需要在美国找一个机房,便能向美帝提供快速方便的云存储服务了!

当然,这样的加速策略还可以细分:同在国内,我们可以为不同宽带运营商各设置一个机房,从而降低不同运营商用户访问存储服务的网络延迟;我们甚至可以根据中国不同地区设置西南、华南、华中、华东、华北、西北等区域的机房来加速访问。一句话,只要有钱,不愁没速度和存储容量!

总结

再来一遍,只要有钱,不愁没速度和存储容量!

从上面这句理直气壮的加粗的话中(当然,有一定夸张成分),我们已经能很明显的向用户昭示云存储系统的可扩展性了:无论是容量还是访问速度,都可以通过基础设施规模的扩大而轻松优化,而其中容量更是拥有近乎无限的扩展能力——这就是云存储不同于传统分布式存储(如Hadoop)或网络磁盘(如FTP等)之处所在。

后记:OpenStack Swift

如果你听我扯淡了快5000字却能坚持看到了这里,那请受我一拜... 作为后记,就简单上点干货了。

只要和云计算相关领域有所交集的人就不可能没听过OpenStack项目。该项目号称是云计算领域的操作系统,也为现今几乎所有非自行研发系统的云计算服务商提供了技术支持,其流行度可见一斑。OpenStack Swift作为该项目中的一个子项目,被称作Amazon S3的开源版,提供的服务正是文件存储服务,是各大云存储服务如七牛云存储、各大网盘等的底层系统。

在上文的废话中,我简单地勾勒了一个云存储系统,那么这个系统和OpenStack Swift的差距有多远呢?从架构上说,上文所述的云存储系统和OpenStack Swift大体一致并已经实现了其大部分功能(利用一致性哈希进行跨服务器扩展、跨机房异步备份和加速、多副本写入等);然而,Swift是一个成熟的生产环境工程,而我们的系统只是一个粗制滥造的实验品,两者从可用度、稳定性等方面完全不具有可比性。

尽管如此,我们可以管中窥豹,揭下知道业界最流行开源云存储项目的神秘面纱了。如果要系统的了解该系统,就等我再开新坑吧...(啊等不及的小伙伴自行谷歌吧逃)