IEEE TPDS'22：基于对象级协调的分布式I/O干扰排除系统
I/O干扰是造成分布式文件系统I/O性能下降的主要因素之一。纵观文件系统的架构，I/O干扰可以发生在应用层、中间件层、以及服务端等多个层级，最终表现为对底层存储设备的资源竞争。在去中心化的分布式对象文件系统中，我们发现对象请求调度之间的干扰是造成存储设备资源竞争的根本原因。因此，本工作针对分布式对象文件中各分布式OSD(Object Storage Device)对对象请求的独立调度造成的I/O干扰问题，提出了对象级协调系统LoomIO，以协调各OSD的IO调度过程。为保证细粒度协调带来的开销不影响协调带来的性能提升，LoomIO采用了wait-free的设计思想保证各对象请求在有限时间内能得到较优的调度结果。LoomIO系统由通信模块、调度模块、决策接收/发送模块组成，分别负责发现及组织互相干扰的请求、对已组织的干扰请求进行用户自定义的调度以及减少及选择不一致的调度请求。目前我们实现了LoomIO的整套协调机制并将其嵌入到Ceph文件系统中，对于聚合带宽、资源利用率以及尾延迟都有显著的性能提升。
该成果“LoomIO: Object-Level Coordination in Distributed File Systems”收录于IEEE Transactions on Parallel and Distributed Systems（TPDS）期刊。TPDS是计算机系统领域最权威的国际学术期刊之一，每月出版一期，每期录用论文20篇左右，影响因子为2.6，主要关注并行与分布式架构、并行与分布式算法、并行与分布式计算应用、及并行与分布式系统软件等方面的研究。
- 论文链接：
- https://doi.org/10.1109/TPDS.2021.3126260
背景与动机
图1 分布式OSD(Object Storage Device)对对象请求的独立调度造成的I/O干扰
在分布式对象文件系统中，文件以固定粒度被分割成多个对象并分布在多个OSD中。同时，为防止设备故障等因素造成的数据丢失，对象文件系统通常对对象采用多副本或纠删码策略以达到容错的目的。以纠删码策略为例，RS(k,m)表示每个对象被分割成k个数据块，并计算出m个校验块，这k+m个块分布在k+m个不同的存储设备上。因此，存储设备的资源竞争最终来源于多个并发的数据块I/O。然而，由于去中心化分布式文件系统的特性，决定数据块I/O目的地的对象请求调度是在各个OSD上独立进行的，这些独立的调度之间存在严重的I/O干扰问题。如图1所示，A对象请求的三个分块分别存放于0、1、2三个OSD上，B对象请求的三个分块分别存放于1、2、3三个OSD上。并发访问时，当A和B都选择直接读取数据块，1号OSD将会产生资源竞争。
图2 I/O干扰造成的动态负载不均
在使用常见I/O负载对Ceph集群进行测试后，如图2所示，我们发现动态的负载不均系数可以达到静态的8倍以上，意味着任意时刻某个OSD上的资源竞争情况比其他OSD上的严重得多。这主要是因为去中心化分布式文件系统采用的一致性哈希算法（如Crush）通常是为均衡各OSD上的存储空间而设计的，没有也无法顾及到运行时的I/O访问模式。为了解决这个问题，在不影响数据分布的前提下，我们设计了象级协调系统LoomIO，以在运行时动态地协调各对象的调度过程。以图1为例，在LoomIO的协调下，B可以选择从2、3两个OSD读取一个数据块和一个校验块恢复原始数据，从而达到了负载均衡，减少了资源竞争。
设计与实现
图3 LoomIO整体设计
LoomIO的协调功能由四个模块共同完成，分别是通信模块、决策接收模块、调度模块以及决策接收模块。
1. 通信模块。通信模块的主要任务为发现并组织不同OSD上互相干扰的对象请求。为了控制开销，我们为每个请求分配了一个限时窗口。如图4所示，整个窗口包含两个阶段：广播和监听。在广播阶段，每个对象请求将自己的存储布局发送给其他OSD。在接收接收，每个OSD监听其他OSD的广播。我们将通信窗口相重叠的对象请求定义为互相干扰的对象，即如果A与B互相干扰，则A或B必有一方收到另一方的广播信息。通过通信窗口的重合情况，我们可以确定一组互相干扰的对象请求之间的关系。我们定义一个对象请求为leader，如果它接收到了其他对象请求的存储布局，反之，它将成为一个follower。在LoomIO中，一个leader可以有多个follower，一个follower也可以有多个leader。同时，由于所有的对象请求拥有相同大小的时间窗口，我们保证了一个对象请求不可能既是另一个对象请求的follower或者leader。
图4 通信模块
2. 调度模块。得益于通信模块已经将互相干扰的对象组织完毕，调度模块的设计可以像单机调度一样简单。在LoomIO中，由于我们主要解决的是I/O干扰问题，调度算法只需要简单地将k个分片请求发送到k个负载最少的OSD上即可。对于每个对象请求，它除了需要调度自己之外，还需要调度follower。所有需要调度的存储布局都存放在调度列表，调度模块只需要依次执行即可。作为调度依据，负载表也是很重要的一个数据结构，它需要真实的反应当前各个OSD上的负载情况以更好的指导调度过程。我们使用了低频的全局更新+本地实时累积来构成负载表。使用低频的全局更新是因为高频的监控通常会带来较大的开销。一般情况下，集群监控间隔会被设置成秒级，无法为对象请求的毫秒级调度提供准确实时的支持。在监控信息更新的真空期，基于通信模块提供的全局视野，我们可以得到一个近实时的负载分布。
3. 决策接收/发送模块。决策接收及发送模块主要负责follower如何接收与处理leader的决策以及leader如何发送决策。如图5所示，主要有两条规则：1，一个leader只有在它的决策表不为空并且存在follower的决策时才需要发送决策；2，一个follower需要检查接收到的决策并且从他的调度表中去除重复的条目以防止重复调度。通过这两条规则，我们防止了一个对象请求被多个leader调度并且减少了通信开销。在实际环境中，由于网络延迟的原因，决策发送可能会有失败的情况。具体地，一个follower可能在进行调度前∂都没有收到leader的决策，导致存在不一致的调度结果。但这样的情况占比很少，根据我们的测试，只有不到5%，对于性能的影响几乎可以忽略不计。
图5 决策接收/发送模块
目前我们使用Redis实现了LoomIO的整套协调机制并将其嵌入到Ceph文件系统中。实验结果如图6所示，相比于baseline和现有的两种调度策略Late-binding及K-optimal，LoomIO在资源利用率、聚合带宽、以及尾延迟上分别达到了最高35%、31%、54%的提升。
图6 LoomIO对I/O资源利用率、带宽及尾延迟有显著提升
详细内容请参见：
Yusheng Hua, Xuanhua Shi, Kang He, Hai Jin, Wei Xie, Ligang He, and Yong Chen. "LoomIO: Object-Level Coordination in Distributed File Systems." IEEE Transactions on Parallel and Distributed Systems 33, no. 8 (2022): 1799-1810. DOI: 10.1109/TPDS.2021.3126260
