0%

MapperX: 基于DM-Cache混合存储设备的自适应元数据维护,实现快速故障恢复

MapperX: 基于DM-Cache混合存储设备的自适应元数据维护,实现快速故障恢复

背景

混合存储设备

  • 固态硬盘相比于传统的机械硬盘,在处理随机小I/O时具有更出色的表现
  • 但是现在固态硬盘的价格依然比机械硬盘昂贵得多
  • 近些年,提出了混合存储设备的概念,例如SSHD技术,将SSD作为HHD的高速缓存,以低成本的方式提供更快速的读写

DM-Cache 概览

  • DM-Cache是Linux内核设备映射器的一个组件,实现了物理块设备到虚拟块设备的映射,其将SSDs和HHDs映射到虚拟块设备,SSD作为HHD的高速缓存
  • Linux中I/O设备分为两类:块设备和字符设备,SSD和HHD都属于块设备

img

  • 虚拟块设备是一种抽象,应用程序将数据写入虚拟块设备、获得ACK确认,从虚拟块设备读取数据,底层的SSD、HHD操作对应用程序是透明的
  • DM-Cache元数据(metadata)存储:SSD块和对应HHD块之间的映射关系、“脏”位、当前采用策略相关的元数据
  • 若采用写回法(writeback)的模式,有两种可能的情况:

(1) 被修改的块在缓存中:

不需要更新元数据中SSD块和对应HHD块之间的映射关系,但是要在将“脏”位信息放到内存中后向调用方发送ACK确认,之后由异步任务将“脏”位信息持久化到元数据驱动器上

(2) 被修改的块不在缓存中:

需要将HHD块加载到SSD缓存中,同步修改元数据中SSD块和对应HHD块之间的映射关系,之后的步骤和情况(1)中一样

  • 如果写局部性较高,则缓存命中率高,不需要频繁修改元数据中的映射关系,这样“脏”位的同步会造成更大的影响
  • MapperX使用ABT(adaptive bit-tree)数据结构同步地以层次结构的形式维护”脏”位元数据;ABT用一个比特位表示某个连续范围内的数据块

DM-Cache 的缺陷

  • DM-Cache默认在发生写操作时先将“脏”位信息放入内存中,之后再由异步任务写入元数据驱动器,因为内存是易失性设备,断电后数据消失,这样当系统崩溃时,无法得知SSD缓存中哪些是“脏”数据,只好假定SSD缓存中全部都是“脏”数据(即使大部分数据块是一致的),全都要写入HHD,导致崩溃恢复时间长、系统可用性差

MapperX

CBT

  • 有1个在内存中的位图,记录着全部数据块的状态(1个bit代表对应数据块是否为“脏”,即不一致),首先把这个位图展开成度为d的树,称为CBT(Complete bit-tree)
  • 展开方式:数据块的个数最好为d的幂次,刚开始一分为d,分为d个子树,然后递归划分下去,最后叶子结点就代表位图中的某个bit

ABT

  • MapperX在元数据存储器中维护着CBT的摘要,称之为ABT(Adaptive bit-tree)
  • 对于每次写操作,ABT同步更新
  • ABT的结点表示某个连续范围内的数据块状态,初始状态是只有一个“干净”的根结点,表示SSD缓存和HHD数据完全一致

自适应算法

BitTreeUpdate

  1. 更新内存中的位图(每一bit表示某个数据块,0代表数据一致,1代表存在“脏”数据)
  2. 更新CBT:当某个结点任何一个子孙结点状态为“脏”,置这个结点状态为脏;如果所有子孙结点都“干净”,这个结点状态也为“干净”
  3. 如果写操作导致ABT的某个叶子结点变“脏”,根据CBT修改磁盘上的ABT

PeriodicAdjust

  • 参数列表:
参数 类型 含义
p 时间 异步任务执行周期(采样间隔,默认为1s)
n 整数 SLA(Service-Level Agreement)
abt 自适应树ABT
  • 算法:
  1. 置W为客户端在异步任务执行周期p内的写入操作次数
  2. 置N为元数据驱动器被写入的次数
  3. 如果 N/W ≥ 1/(10^n),认定元数据写入频率太高了,因为元数据修改是同步的,这会降低写操作的性能,在ABT中找到所有叶子结点的直接父结点,在这个范围内寻找在周期p中导致最多元数据写操作的结点,在ABT中将它的子结点移除
  4. 如果 N/W < 1/(10^n),认定还可以接受更高一点频率的元数据写入,于是在ABT中找到周期p内最少元数据写入的叶子结点,在它的下方生成d个子结点,状态根据CBT设置

快速崩溃恢复策略

  • 因为元数据是在每次写操作发生时同步更新的,所以在ABT中的叶子结点对“脏”状态的判断不存在假阴性,也就是说,如果一个叶子结点的状态不为“脏”,那么它所表示的连续数据块也就没有“脏”数据,在数据恢复时可以安全地跳过这些块
  • 对于ABT中每个状态为“脏”的叶子结点,其所表示范围的SSD缓存块全都写回HHD

实现

  • 重用DM-Cache原有的4字节元数据类型,最后两位分别是“脏”位和有效位,将所有4字节元数据的前30位组织成一个位数组,每一bit表示1个结点,以宽度优先的方式表示
  • V-ABT和CBT具有相同的层数和叶子结点数,但是只要状态为“脏”的叶子结点标记为1,其余结点标记为0
  • 例如:

img

上图是1个V-ABT,度为2,层数为4,有两个“脏”状态的叶子结点被标记为1,根据宽度优先,可以将这个V-ABT表示成1个15个bit的位数组:001010000000000

评估

写入时延

  • 根据实验数据,使用MapperX后,写入时延相比于原有的DM-Cache略微高一些,但是远低于使用同步写“脏”位元数据的策略
  • MapperX本质上也是同步写“脏”位元数据,但是利用了客户端写操作的局部性原理,减少了对元数据的写入次数
  • 随着预期β值(写元数据次数占所有客户端写操作次数的比例)的增加,客户端写入时延增加

IOPS(writes per sec)

  • 根据实验数据,使用MapperX后,IOPS低于原有的DM-Cache,远高于使用同步写“脏”位元数据的策略

恢复时间

  • 根据实验数据,使用MapperX后,崩溃恢复时间相比于原有的DM-Cache显著减少
  • 随着预期β值(写元数据次数占所有客户端写操作次数的比例)的增加,恢复时间减少,这是因为在PeriodicAdjust过程中,当N/W小于β时会在ABT中增加叶子结点,从而叶子结点表示范围粒度更细,在崩溃恢复的时候,需要写回HHD的缓存块个数更少