一种基于日志方式的存储空间管理方法和装置

本发明涉及存储技术领域，尤其涉及一种基于日志方式的存储空间管理 方法和装置。

无论是基于文件系统还是基于其它块设备的应用，都有两个基本的要求： 1、记录数据存储在块设备的哪些块上；2、块设备的哪些块是空闲状态。

从原则上来说，可以不用记录块设备的哪些块是空闲的，而只记录数据 存储在哪些块上即可。因为块的状态只有两种：使用状态或者空闲状态。所 以，可以通过已使用的块来推算出哪些块是空闲的。但是，这又意味着需要 遍历所有已使用的块。为了使申请空闲块的效率更高，绝大多数块设备都会 记录哪些块是空闲的。

目前记录块是空闲状态还是已使用状态主要有两种方法，一是bitmap的 方式，一是b-tree的方式。当然，最常用的还是bitmap的方式。bitmap是用 一段连续空间的第N个比特位来表述块设备的第N个块是空闲的还是被占用 的。相对而言，bitmap的资源消耗比较小，对于4KB的块大小，其资源消耗 仅为1/(4096*8)＝0.003％(其8代表一个字节8个比特位)。对于1GB大小 的文件系统而言，bitmap所需要的空间大小为32KB；而对于1TB大小的文 件系统而言，则需要的空间大小为2MB。这个大小对于系统的内存来说，还 是可以接受的，但是从查效率的角度来说，相对就比较低了。而如果对于 1PB的文件系统而言，bitmap需要的大小则变为32GB，这个大小对于大多 数设备的内存来说都是不可以接受的。这就意味着每次需要获取块状态时， 都需要从磁盘读取，这将严重影响文件系统的性能。

针对上述问题，一个比较容易想到的方法是：将bitmap分为多个小的 bitmap，再用bitmap来映射划分后的小的bitmap，请参图1所示。这样就可 以通过最顶层的bitmap来出哪些小的bitmap是有空闲块的；如果小的 bitmap不在内存中，则将小的bitmap从磁盘中读取出来。

但是，这样仍会存在如下问题：不论是申请还是释放块资源，bitmap都 需要更新。对于申请块资源的操作，可以对bitmap的更新进行控制，但是对 于释放块资源的操作则很难进行控制，因为释放操作是上层应用触发的。频 繁进行块资源的释放，就意味着频繁更新bitmap，就意味着有很多的读写IO。 更甚，若bitmap的更新涉及到很多小的bitmap，即bitmap的更新具有很大 的随机性时，系统将不堪重负。

B-tree则是采用extent(一段连续的存储空间)的方式来管理连续的块 (block)。Extent的方式采用偏移加长度的方法来管理空闲的块空间。但是 b-tree与bitmap存在上述同样的问题。

有鉴于此，本发明提供一种基于日志方式的存储空间管理方法。

该方法应用于存储设备，包括：在申请存储空间或释放存储空间的时候， 在预设大小的第二映射区域SMR中记录对应的申请或者释放日志，该申请 或者释放日志记录申请或者释放存储空间的起始位置以及大小信息；按照一 定的策略，顺序对所述申请或释放日志，以及上一次的合并日志执行存储空 间合并的操作，并在所述SMR中记录本次产生的合并日志，所述合并日志 记录了空闲的存储空间的起始位置以及大小。

优选地，日志在SMR中的记录采用循环覆盖的方式进行；所述按照一 定的策略，顺序对所述申请或释放日志，以及上一次的合并日志执行存储空 间合并的操作包括：当上一次合并产生的合并日志以及当前未被合并的申请 或释放日志总数量占SMR内容区域日志总容纳量的比值达到预设阈值时， 顺序对所述申请或释放日志，以及上一次的合并日志执行存储空间合并的操 作；或者，在申请存储空间且没有满足该申请所需大小的存储空间时，顺序 对所述申请或释放日志，以及上一次的合并日志执行存储空间合并的操作。

优选地，顺序对所述申请或释放日志，以及上一次的合并日志执行存储 空间合并的操作包括：顺序针对当前每条未被合并的申请或释放日志，按照 日志中记录的起始位置和大小，判断是否可以和红黑树中当前的节点进行合 并，如果可以则进行合并；合并后将新生成的节点插入到红黑树中，并删除 被合并的节点；该新生成的节点的内容为：本次合并后空闲存储空间的起始 位置和大小。

优选地，所述SMR中记录的日志包括：表示是释放空间操作还是申请 空间操作的信息；表示是真实申请释放操作的日志还是合并操作的日志的信 息；日志的编号Cur_journal_id，该编号随着日志的增加依次增加；所述顺序 对所述申请或释放日志，以及上一次的合并日志执行存储空间合并的操作为 按照日志编号递增的顺序依次执行所述合并的操作。

优选地，磁盘存储空间被划分为若干个区域region，每个region包括数 据区域DR和映射区域MR；其中MR包括主映射区域PMR和第二映射区域 SMR；PMR包括头部区域和记录了属于该PMR管理的各SMR的位置以及 下一个PMR位置的内容区域；SMR包括头部区域和记录所述日志的内容区 域。

优选地，存储设备启动工作后，将从磁盘中读取PMR信息、SMR信息 到内存中，并基于内存中的PMR信息和SMR信息进行存储空间的管理。

优选地，若从磁盘中读取到内存中的SMR内容区域中的编号最大的日 志是合并日志，在需要进一步进行合并操作时，需要重新将所述合并日志之 前的上一次合并日志、上一次合并日志之后的申请日志、释放日志重新进行 一次合并操作。

优选地，在申请存储空间时，如果SMR管理的DR中存在若干个满足申 请条件的连续可用的空间，则选择逻辑块地址lba小的所述可用空间。

相较于现有技术，本发明的技术方案解决了现有存储空间管理中大量随 机存储空间释放导致的设备性能降低的问题，并且对存储设备的内存容量要 求不高。

图1是一种多层bitmap映射示意图。

图2是本发明实施例流程图。

图3是本发明实施例存储空间的划分结构图。

图4是本发明实施例日志内容图。

图5是本发明实施例日志合并示例图。

图6(a)～图6(b)是本发明实施例另一日志合并示例图。

针对背景技术中提到的技术问题，本发明主要提供一种基于日志方式进 行存储空间管理的技术方案。该技术方案解决了现有存储空间管理中大量随 机存储空间释放导致的设备性能降低的问题。以下通过具体实施例详细说明。

请参图2所示的本发明实施例流程图。

S21、在申请存储空间或释放存储空间的时候，在预设大小的第二映射 区域SMR中记录对应的申请或者释放日志，该申请或者释放日志记录申请 或者释放存储空间的起始位置以及大小信息。

S22、按照一定的策略，顺序对所述申请或释放日志，以及上一次的合 并日志执行存储空间合并的操作，并在所述SMR中记录本次产生的合并日 志，所述合并日志记录了空闲的存储空间的起始位置以及大小。

上述方法在进行存储空间申请或释放的时候，仅是记录对应的申请或释 放操作日志；当满足一定的条件之后，再对上述申请或释放日志进行合并操 作(合并操作的本质是：统计出存储空间中哪些空间已被释放，将连续已被 释放的空间，即extent，进行合并，并且将该合并操作结果作为合并日志追 加到SMR区域中作为一新的日志进行记录)。这样就避免了频繁的进行存 储空间的管理，提升了存储设备的性能。另，该合并日志记录了空闲存储空 间的起始位置和大小，新的存储空间的申请操作可以根据该起始位置和大小 判断是否满足申请需求，如果满足，则直接申请该存储空间。

请进一步参图3，作为一个例子，可以针对存储设备的存储空间按照图3 的方式进行分割。存储空间被划分为若干个区域region，每个region包括数 据区域DR(data region)和映射区域MR(map region)；其中MR包括主映 射区域PMR和映射区域SMR；PMR包括头部区域(map region head)和记 录了属于该PMR管理的各SMR的位置(SMR Entry)以及下一个PMR位置 (Next PMR Entry)的内容区域；SMR包括头部区域(Map Region Head)和 记录所述日志(Map Region Journal)的内容区域。

该存储空间采用的是两级映射的方式，每个区域region可以按照一定的 大小进行划分，比如说128GB。这样整个存储空间将被分为若干的region， 每个region均包含上述的两级映射结构，单独进行管理。

作为一个例子，SMR的内容区域记录的日志Map Region Journal(MRJ) 请参图4。每条MRJ包括：2bit的Reserved(预留)位。占2bit的Ops_flag， 其中低比特位表示释放空间或申请空间的操作，比如说释放操作为0，申请 操作为1；高比特位表示该日志是真实的申请/释放日志，还是合并生成的日 志，比如说真实的申请/释放日志为0，合并生成的日志为1。分别占28bit 的(也表示DR最大容量为(2^28-1)*4KB≈1TB)Offset及Size，该Offset 表示操作涉及的空间在DR中的偏移(相对位置，以4KB为单位)，Size表 示操作涉及的大小。Cur_journal_id表示当前日志的id，每记一条日志该id 就会自加一次。上文中日志记录的存储空间的起始位置在这个例子中用 Offset来表示。

上述PMR信息、SMR信息被保存在存储设备的内存中；其他信息则记 录在磁盘空间中。由于PMR信息、SMR信息所需占用的空间较少，所以对 内存大小要求较低。当然，内存中还可以进一步保存SMR对应的DR最近一 次被访问的存储空间的信息，这样在后续申请存储空间时，如果该存储空间 满足申请的要求，直接从该其中划取空间即可。

由于用于记录日志的SMR内容区的大小是预先设定的，而申请操作、 释放操作、合并操作对应的日志是不断增加的，所以这里采用循环覆盖的方 式将日志记录在SMR中。

为了准确的对存储空间进行管理，需要对于日志的合并采取一定的策略。 策略一：当上一次合并产生的合并日志以及当前未被合并的申请或释放日志 总数量占SMR内容区域日志总容纳量的比值达到预设阈值时，顺序对所述 申请或释放日志，以及上一次的合并日志执行存储空间合并的操作；策略二： 在申请存储空间且没有满足该申请所需大小的存储空间时，顺序对所述申请 或释放日志，以及上一次的合并日志执行存储空间合并的操作。这里只是举 例两个例子，本实施例不排除其他存储空间管理的策略。

请参图5给出的一个例子，第一行中“MRJ 45”表示第45条日志，第 一行中的“1”表示该第45条日志是合并生成的日志；其他各行相同的释义。 从该例中可以看出，第45条日志之前的日志已经经过合并处理，并且形成了 两条合并日志45和46，该45和46条合并日志是上一次合并产生的合并日 志；之后，又新生成了若干条真实的(非合并的)操作日志：47、48、49、 50、51、52。这样上一次合并产生的合并日志以及当前未被合并的日志即为 以下日志：45～52，共8条，这里的SMR内容区域日志的总容纳量为10，所 以其占比为80％。当上述策略一中的预设阈值为78％时，则当前需要对日志 45～52进行合并操作。该合并策略可以及时避免有效日志未经处理而被覆盖 的情况出现。

策略二在申请存储空间时，若要申请的空间大小大于当前空闲的空间大 小时，则可以采用日志合并的方式看看合并得到的新日志对应的空闲空间的 大小是否满足申请的要求，若是，则申请操作将成功，直接将合并后的空间 的offset值反馈给上层。

本实施例针对日志进行存储空间的合并操作时，可以依赖红黑树进行该 合并操作。比如说针对每条未被合并的申请或者释放日志，按照该申请或者 释放日志记录空间的起始位置和大小，判断是否可以和红黑树中当前的节点 进行合并，如果可以则进行合并；合并后将新生成的节点插入到红黑树中， 并删除被合并的节点。该新生成的节点的内容为：合并后空闲存储空间的起 始位置和大小。红黑树的每个节点均记录空闲空间的起始位置和大小信息， 索引值为所述起始位置。上述可以合并的原则是，红黑树中节点记录的空闲 空间信息和日志中记录的申请/释放空间重合、部分重合、连续。

下面举几个例子来说明上述合并操作：

例1：红黑树中已有一代表空闲空间的节点：offset值为32，size值为 16K；假设每4K，offset值增加1。当前需要对offset值为36，size为4K 的释放日志进行合并操作。根据上述offset值和size值，判断当前日志可以 和该节点进行合并，合并后的新节点对应的offset值为32，size值为20。所 以将该新节点根据其索引值32插入到红黑树中，并将原来的offset值为32， size值为16K的节点从红黑树中删除。并在SMR中生成一条合并日志，该 合并日志的内容为：释放操作，offset值为32，size值为20。

例2、红黑树中已有一代表空闲空间的节点：offset值为32，size值为 16K；假设每4K，offset值增加1。当前需要对offset值为31，size值为4KB 的释放日志进行合并操作。根据上述offset值和size值，判断当前日志可以 和该节点进行合并，合并后的新节点对应的offset值为31，size值为20。所 以将该新节点根据其索引值31插入到红黑树中，并将原来的offset值为32， size值为16K的节点从红黑树中删除。并在SMR中生成一条合并日志，该 合并日志的内容为：释放操作，offset值为31，size值为20。

例3、红黑树中已有一代表空闲空间的节点：offset值为32，size值为 16K；假设每4K，offset值增加1。当前需要对offset值为32，size值为16KB 的释放日志进行合并操作。直接忽略该条释放日志，不需作任何处理。

例4、红黑树中已有一代表空闲空间的节点：offset值为32，size值为 16K；假设每4K，offset值增加1。当前需要对offset值为34，size值为4KB， 的申请日志进行合并。此时，需要将原有节点拆分成两个，并将原有的结点 删除。新生成的节点其offset分别为32，35，size值分别为8K，4K。此时 需要进一步在SMR中生成两条合并日志。

例5、红黑树中已有一代表空闲空间的节点：offset值为32，size值为 16K；假设每4K，offset值增加1。当前需要对offset值为35，size值为4KB 的申请日志进行合并。此时，删除原节点，新生成的节点的offset值为32， size值为12K；实际上只需要把原节点的size值直接改为12K即可。进一步 在SMR中生成该新节点对应的合并日志。

例6、红黑树中已有一代表空闲空间的节点：offset值为32，size值为 16K；假设每4K，offset值增加1。当前需要对offset值为32，size值为4KB 的申请日志进行合并。此时，删除原节点，新生成的节点的offset值为33， size值为12K。进一步在SMR中生成该新节点对应的合并日志。

这里有一种情况需要说明，在存储设备启动时，首先需要将磁盘中的 PMR信息、SMR信息读取到内存中。此时可能会出现图6(a)或者图6(b) 所示的情况。在图6(a)中，由于编号journal_id最大的MRJ是真实的申请 或者释放日志，所以此时若要进行合并操作只需要将journal_id为09、10、 11三条MRJ参与日志合并；而图6(b)中，由于编号journal_id最大的MRJ 是合并日志，所以此时若要进行合并操作，则需要将journal_id为06、07、 08、09的这四条日志参与合并即可。其中journal_id为06、07的日志为上一 次产生的合并日志；journal_id为08、09的日志为上一次合并日志产生后新 生成的真实的申请/释放日志。如果合并的结果和当前journal_id为10、11 日志的结果一致，则不需要进行任何操作。若合并的结果除了当前journal_id 为10、11日志的结果外，还包括其他合并结果，则进一步增加该其他合并结 果的日志，这种情况有可能是系统关机或其它情况导致上次的合并未完全完 成。

另外，还有一点需要说明，在申请存储空间时，除了考虑SMR管理的 DR中连续可用空间的大小外，还需要考虑该可用空间尽可能在逻辑块地址 lba小的位置。这主要是因为对于现有硬盘，小的lba对应的磁道在硬盘的外 侧，在硬盘盘片旋转速率为定值时，外侧有更高的线速度，也就意味着更快 的读写速率(外侧磁道与内侧磁道平均速率比为2:1)。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本 发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在 本发明保护的范围之内。