论文笔记：[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]

参考实现

https://github.com/chrislusf/seaweedfs

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