OBFS全称为Object-Based File System，翻译成中文就是基于对象的文件系统。
该论文是Ceph EBOFS的前置研究，发表在MSST’04中，作者来自于加州大学圣克鲁兹分校（UCSC）。
对象存储介绍
在基于对象的存储系统中，文件被条带化（striping）成多个对象，如下图所示：
这些对象分散存储在多个OSD（Object Storage Devices，对象存储设备）中。
作者发现：OSD上的工作负载与通用目的文件系统中的工作负载十分不同。基于该发现，他们提出针对工作负载来优化磁盘布局。
The basic idea of OBFS is to optimize the disk layout based on our knowledge of the workload.
工作负载分析
作者分析了劳伦斯利物莫国家实验室（LLNL）中分布式文件系统的工作负载，统计结果如下图所示：
从图1(a)中可以发现：小于4KB（通用目的文件系统中的典型块大小）的文件只占很小一部分；绝大部分文件在32KB-8MB之间；
从图1(b)中可以发现：小于256KB的文件占用的磁盘空间很小；绝大部分空间被4MB-1GB的文件所占据。虽然大于1GB的文件只占一小部分，但是其占用的总空间超过了15%。
假设系统条带大小为512KB，在LLNL的工作负载中，预计85%的对象为512KB，其余15%的对象则小于512KB。
而OBFS将与系统条带大小相同的对象称为大对象，其他对象称为小对象。也就是说，在其工作负载中，85%的对象都是大对象。
设计与实现
Region和变长块
OBFS将磁盘划分为大小相同的Region，同一Region中的块大小相同，不同Region中的块大小不同。
在实现时，OBFS使用了两种块大小：4KB的小块（Linux中的逻辑块大小）和512KB的大块（系统中的条带大小）。大块用于存储大对象，小块用于存储小对象。
因为大对象的大小与条带化大小相等，所以大对象只占用一个大块；而小对象的大小则不尽相同，可能会存放在多个小块中。
如下图所示，包含大块的Region叫作Large block region（以下简称为大块Region），包含小块的Region叫作Small block region（以下简称为小块Region），没有初始化的Region称为空闲Region。
每个Region都有一个Region头，其存储了Region的一些元数据，如空闲块位图位置（只有小块Region有）、空闲Onode位图位置以及Onode表（只有小块Region有）等。
所有的Region头均会被链接到Region头链表（Region Head List，RHL）中。
此外，OBFS还会将它们组织成三个子链表：大块Region链表、小块Region链表以及空闲Region链表，每个链表都按照Region的地址升序排列。
当小（大）块Region链表中找不到足够的空闲块来存放对象时，OBFS就会从空闲Region链表中分配一个空闲Region，将其中的所有块初始化为需要的块大小（4KB或者512KB）。
对象元数据
下图是OBFS中两种Region的具体结构和对应的数据布局。不难发现，小块Region的磁盘布局与Ext2是非常相似的。
其中，Onode（Object node）表示对象的元数据。每个Onode都有一个32位的ID，高16位为Region ID，低16位为Region内的对象ID，即图中的Onode Index（以下统一采用Onode Index表示）。
在实现时，无论是大对象，还是小对象，其Onode均占用512个字节。Onode中存储了Object ID，可以实现从Onode到Object的反向映射。
对象查询
OBFS使用哈希表（Object Lookup Table，OLT）来管理Object ID和Onode ID的映射，也就是说：
$$
hash(\mathrm{Object\ ID}) \rightarrow \mathrm{Onode\ ID} \tag{1}
$$
在哈希表中，每个项需要8个字节：4个字节用于存储Object ID，4个字节用于存储Onode ID。
在查找某个对象时，需要经过以下三步：
首先，查询哈希表，根据Object ID得到对应的Onode ID，即
然后，根据Onode ID得到对应的Region ID（Onode ID的高16位），搜索Region头链表，找到对应的Region；
最后，根据Onode ID得到对应的Onode Index（Onode ID的低16位）。如果Onode属于大块Region，可以直接计算出数据位置：
$$
(\mathrm{Data\ Block\ Size} + \mathrm{Onode\ Size}) \times \mathrm{Onode\ Index} \tag{2}
$$
如果属于小块Region，则需要先搜索Onode表，找到对应的Onode，再根据Onode得到对象的数据位置。
数据分配策略
OBFS采用了基于Extent的块分配策略，Onode中存储了多个<块地址，对象偏移，长度>三元组，每组占用4个字节。
- 如何判断应该用大块，还是小块来存储对象呢？
如果对象的大小大于使用大块的阈值，则为其分配一个大块；否则，为其分配适当数量的小块。
- 对象应该存放在哪里呢？
1.对于大对象来说，OBFS会从最近的大块Region中寻找空闲块来存放它。如果找不到空闲块，则初始化一个最近的空闲Region来存放它。
2.对于小对象来说，
OBFS会顺序遍历小块Region链表，从上一次访问过的小块Region开始搜索，如果能找到足够大的连续空闲块，则将对象直接存放在其中；
如果找不到足够大的连续空闲块，则将最大的连续空闲块（一个Extent）分配给该对象。然后，从对象大小中减去已分配的空间，重复执行该过程，直到整个对象被存放在Region中为止；
注意：为了避免超出Onode的存储容量（512B），OBFS为对象设置了最大的Extent数量，只有当使用的Extent数量小于该阈值时，才会将对象分配给当前的Region。
如果在当前Region中找不到足够的空间来存放该对象，则继续往后寻找其他的小块Region；
如果仍然找不到足够的空间来存放该对象，则初始化最近的空闲Region（放进小块Region链表中），在新的Region中分配空间来存放该对象。
作者的博士论文还提到：当写负载密集时，直接分配空闲Region要优于先搜索现有的Region。
参考资料
论文, https://www.storageconference.us/2004/Papers/33-Wang-a.pdf
Slides, https://www.storageconference.us/2004/Presentations/33r1.pdf
Ph.D. Thesis “Storage Management in Large Distributed Object-Based Storage Systems”, https://www.ssrc.ucsc.edu/media/pubs/b478452bd61cc3cb3510ed6ea8750d5d93f2affd.pdf
