论文笔记:[OSDI'10] Finding a needle in Haystack: Facebook's photo storage

Haystack 是 Facebook 为了其图片存储场景进行特殊优化的热存储系统,系统接口是简单 Key-Value 存储。论文主要描述了其单机存储引擎的构建,针对一次写入多次读取从不修改的场景进行优化。本笔记只涉及到论文中单机存储引擎的部分

Facebook 图片存储场景有这样的一些特点:

  1. 新写入的图片会很快变得很热,并且随着时间推迟慢慢变冷(feed 流场景)

  2. 写入的 1 个图片会产生 4 种不同的大小(Thumbnails,Small,Medium,Large),大部分的读请求是 Small 大小的

  3. 读请求远大于写请求,并且一旦写入就不会进行修改,很少进行删除

  4. 对于热点请求在系统外部已经有了 SDN,因此大部分 Cache 方案效果都不会太好

  5. 主要处理长尾请求或还没来得及推给 SDN 的请求

  6. 平均对象大小为 64KB ~ 85KB(根据 §1 给出的数据)

在 Haystack 之前,Facebook 采用 NFS + NAS 的方式来进行服务。有一些 NAS 服务器提供存储服务,一张图片一个文件。WebServer 通过 NFS 协议挂载这些 NAS。这样遇到的问题是读一张图片需要 3 次磁盘随机访问:

  1. 读文件系统索引,从而找到 inode

  2. 读 inode 从而找到实际数据所在的位置

  3. 读实际数据

尽管做了不少尝试,但是由于用户请求大多数是长尾请求,因此通过 cache 来减少这一流程的尝试基本上都失败了。在这种情况下,最好的选择是减少 Metadata 的大小,然后将所有的 Metadata 都装入内存。注意这种方式是可行的,因为

  1. 数据是一次写入,多次读取,从不修改,很少删除

  2. 不需要任何访存控制

  3. 不需要任何结构

Haystack 的结构比较简单,分为三部分:Haystack Store,Haystack Directory and Haystack Cache。论文中着重描述了 Store 部分的构造,而对后两者描述较少。这是可以理解的,因为这一问题主要是单机 Key-Value 存储引擎如何对这一特殊场景进行优化的问题。

Haystack Store 的结构自顶向下是这样的:

  1. Hashtable(虽然文中没有直接说,但是在 §3.6.2 中提到了)

  2. Index File(用于快速重建 Hashtable,§3.4.4)

  3. Physical File(约 100GB 大小,存放实际数据,§3.4)

  4. XFS(1GB extents,§3.4.5)

  5. RAID-6 (256KB stripe size,§3.4.5,§4.4.6)

一个写请求的流程大概是这样的(有自行脑补部分,因为有些细节原论文没写):

  1. 根据 Logical Volumn ID 查内存表直接找到文件句柄

  2. 如果文件不够大的话,进行 pre-allocate

  3. 在文件末尾顺序写入内容(此处不确定是如何处理并发的)

  4. 更新内存中的 Hashtable 并向客户端响应成功

  5. 异步更新 Index File(此处不确定是如何处理并发的,因为第 3 步很有可能是更小的 object 先完成,这样的话如何保证 Index File 中 needle 的顺序和 Physical File 中 needle 的顺序一致?)

对于并发处理有两个可能的猜测:

  1. 在写入请求中已经知道 data 的大小,进而可以推算出 needle 的大小。只需维护写入位置的 offset 即可并发写入多个 needle

  2. 并发写入顺序化后再进行处理(这样对 HDD 写操作比较友好?)

一个删除请求只设置数据区的删除标记并调整内存中的数据结构,不管 Index File。读取时如果发现某一对象已经被删除,则再次调整内存中的映射。最终通过 stop and copy 的方式完成 GC。在论文 [2] 中提到,删除操作已经不依赖于 Physical File 和 Index File 的 delete 标记了,转而直接操作 Journal File 和 Hashtable。

其他疑问

  • 为什么非得保证 Index File 中 needle 的顺序和 Physical File 中一致?难道不是只记录最后一个 needle 的位置就行了吗?这样也许并发的处理会简单一些。

  • needle 结构中的 Header 和 Footer 是怎么起到 recovery 的作用的?为什么需要两个一样作用的东西?

  • Superblock 是什么?

  • 与其他单机引擎的比较?(InnoDB,BerkeleyDB,LevelDB)尤其是与 LSM 类引擎的比较。(LSM-trie: an LSM-tree-based ultra-large key-value store for small data;LSM-tree managed storage for large-scale key-value store;Ceph: a scalable, high-performance distributed file system ;Atlas: Baidu’s key-value storage system for cloud data)

    • 其他引擎并不对读场景特别优化,而是支持读写平衡的

    • 有些引擎还支持快速 scan 等功能,Haystack 中 value 不是有序组织的,可能 scan 起来性能会降低

    • LSM 引擎的写放大可能会是个问题,见论文 [3]

References

  • [1] Beaver, D., Kumar, S., Li, H. C., Sobel, J., Vajgel, P., & Facebook, I. (2010). Finding a Needle in Haystack: Facebook’s Photo Storage. In Proc. USENIX Symp. Operating Systems Design and Implementations (OSDI’10) (pp. 1–14).

  • [2] Subramanian Muralidhar, Wyatt Lloyd, Southern California, Sabyasachi Roy, Cory Hill, Ernest Lin, Weiwen Liu, Satadru Pan, Shiva Shankar, Viswanath Sivakumar, Linpeng Tang, and Sanjeev Kumar. 2014. f4: Facebook’s Warm BLOB Storage System. Osdi’14 (2014), 383—​398. Retrieved from https://www.usenix.org/conference/osdi14/technical-sessions/presentation/muralidhar

  • [3] Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees. In Proceedings of the 26th Symposium on Operating Systems Principles - SOSP ’17, 497–514. DOI:https://doi.org/10.1145/3132747.3132765