Haystack

Time: 一月 30, 2013
Category: storage

文献原址:Finding a needle in Haystack: Facebook's photo storage 

一:简介:

  1. 2600亿照片,20PB数据量
  2. 每周60TB,10亿照片
  3. 每秒100w张图片的检索速度
  4. 对象存储,我们的图片只写,不修改,很少删除
  5. 传统POSIX文件系统成为瓶颈

论文中提到瓶颈是由于传统的POSIX文件系统是基于目录和metadata来管理文件的,通常取一张图片都会涉及好几个IO操作:

  1. 从文件名得到inode号
  2. 将inode信息从磁盘读取出来
  3. 读取文件。

对于一些稍微复杂的架构,1步骤可能会更频繁些。
Haystack设计的目标:

  1. 高吞吐量和低延迟
  2. 分区容忍性
  3. 低成本。通过两个维度来控制,每TB可用数据的利用率和每TB可用数据的读速率(这里的可用考虑到底层文件系统,磁盘阵列,冗余等各种因素)
  4. 简单。

二、背景

  1. 典型设计,存储集群 + cdn
  2. NFS文件系统

 

CDN通常是用来缓存热数据的,但是对于像facebook这样的互联网站,通常需要产生大量的非热数据内容,而恰恰是这些不太热的数据内容,大量地升高了CDN回源的压力,facebook引用了长尾理论来解析这一效应。在NFS卷里,facebook最初默认是每个目录存储上千个文件,但是由于NAS设备对目录metadata的管理方式,导致在一个目录里存放上千个文件相当困难,因为目录的blockmap太大了。这种情况下读1张图片最少也要10个IO,就算让目录存放的文件数降低到100,也仍然会有3个IO才能读到一张图片。
为了减少磁盘操作的次数,facebook还在Photo Store servers上缓存NAS设备返回的file handle,这个是通过增加内核API(open_by_filehandle)来实现的。facebook从NAS上学到的经验就是:通过缓存来降低磁盘IO的操作是很有限的。
也许有人会说,可以使用memcache来缓存所有的file handles。对此facebook坦言,也许这是一个解决方案,但是只能解决这里部分的问题,因为这么做的话需要NAS设备缓存所有的inodes信息,只不过是一种昂贵的传统存储方案罢了。 

三、设计与实现 

方案:CDN解决热数据问题,Haystack解决长尾效应。
Haystack的主要目的就是为了解决NFS存储方案中高磁盘IO的问题。Haystack的做法是:降低文件系统的metadata的内存占用,因此尽可能的将所有的metadata放在内存里,例如它将多个小文件存在一个大文件里。

1)三个核心组建:Haystack Directory, Haystack cache, Haystack store 

 

Store是由物理卷组成的,容量由物理卷的数量来控制,100个物理卷可提供10TB的存储空间。物理卷还会组合成一个逻辑卷,单个逻辑卷中的所有物理卷数据是相同的,冗余。Directory主要保存应用方面的数据信息,例如每张图片存放在哪个逻辑卷上,还有逻辑卷到物理卷的映射以及逻辑卷的剩余空间。Cache相当于一个内部的CDN。 

2)URL规格

  http://CDN/Cache/Machine-id/<Logical-volume,Photo> 

3)读取图片

(如上) 

4)上传图片 

5)Directory

  1. 逻辑卷到物理卷的映射
  2. 写逻辑卷和读物理卷的负载均衡
  3. 决定一个请求该由CDN来处理还是由Cache来处理
  4. 标志逻辑卷的读写属性

6)Cache 

分布式hash表用图片id作为key定位cache数据。Cache只会在下面两种情况下都吻合的情况下才进行缓存:

  1. 请求来自用户而不是CDN
  2. 从可写的Store机器上读取的数据

对1:CDN和cache其实是一样的。
对2:为了保护可写Store机器,有两点,其一,通常新数据都会有较大的访问,其二,我们设计的filesystem在只读或者只写的时候会有更好的性能。
到这里,Directory的调度就很有趣了。 

7)Store

Store:物理卷组成,hay/haystack_<logical valume id>
每个物理卷的file handle保存在内存里。所以从Store上面检索filename/offset/size不需要磁盘IO。 

cache到store读:
请求数据:logical volume id, key, alternate key, cookie
cache到store写:
上述 + data。数据是ppend-only的,对于某些修改,比如旋转,允许在原needle上修改,否则其余所有的修改都会以相同的key和alternate key追加一个needle,如果新的needle被追加到别的逻辑卷里,这些信息会被Directory感知,旧卷上的needle永远都不会被访问到了。
cache到store删除:
设置flags标志。 

8)索引

为了加快系统启动速度,store机器对每个卷都维护一个index文件。实际上是内存索引某个时刻的checkpoint。

会引入问题:index文件可能是旧的。比如当delete照片时,是设置flag而没有升级index,index的升级是异步的,这样可以让写请求快速返回。 

要解决两个副作用:needles可能存在但没有对应的index记录,或者index记录没有反映出delete标志。
解决办法:

  1. 对于第一个副作用,系统启动时,从卷尾部往头部扫描,补充index。因为没有index的needles肯定是在最后追加的。
  2. 对于第二个副作用,延迟处理,也就是说没人读的话就不管它,有人读时再判断并更新index。

9)文件系统 

根据Haystack的设计,对文件系统的需求是:不需要太多内存(例如保存文件的filemeta数据),在大文件里快速的随机seek。
XFS,好处:

  1. blockmaps很小
  2. 预分配,减少碎片等等。

10)容灾 

故障检测:监控网络链接,检查卷文件是否可用,和尝试读数据。一旦检测存在异常,标志read-only
故障恢复:这个时候基本就是借助副本来进行恢复了。

Leave a Comment