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

Abstract

本发明提供一种基于日志方式的存储空间管理方法，该方法应用于存储设备，该方法包括：在申请存储空间或释放存储空间的时候，在预设大小的第二映射区域SMR中记录对应的申请或者释放日志，该申请或者释放日志记录申请或者释放存储空间的起始位置以及大小信息；按照一定的策略，顺序对所述申请或释放日志，以及上一次的合并日志执行存储空间合并的操作，并在所述SMR中记录本次产生的合并日志，所述合并日志记录了空闲的存储空间的起始位置以及大小。本发明的技术方案解决了现有存储空间管理中大量随机存储空间释放导致的设备性能降低的问题，并且对存储设备的内存容量要求不高。

Description

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

技术领域

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

背景技术

无论是基于文件系统还是基于其它块设备的应用，都有两个基本的要求：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)。

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

Claims (8)

1.一种基于日志方式的存储空间管理方法，该方法应用于存储设备，其特征在于，该方法包括：

在申请存储空间或释放存储空间的时候，在预设大小的第二映射区域SMR中记录对应的申请或者释放日志，该申请或者释放日志记录申请或者释放存储空间的起始位置以及大小信息，存储设备的存储空间被划分为若干个区域region，每个region包括数据区域DR和映射区域MR；其中MR包括主映射区域PMR和所述第二映射区域SMR；

当上一次合并产生的合并日志以及当前未被合并的申请或释放日志总数量占SMR内容区域日志总容纳量的比值达到预设阈值时，或者在申请存储空间且没有满足该申请所需大小的存储空间时，顺序对所述申请或释放日志，以及上一次的合并日志执行存储空间合并的操作，并在所述SMR中记录本次产生的合并日志，所述合并日志记录了空闲的存储空间的起始位置以及大小。

2.如权利要求1所述的方法，其特征在于，日志在SMR中的记录采用循环覆盖的方式进行。

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

4.如权利要求1所述的方法，其特征在于，所述SMR中记录的日志包括：表示是释放空间操作还是申请空间操作的信息；表示是真实申请释放操作的日志还是合并操作的日志的信息；日志的编号Cur_journal_id，该编号随着日志的增加依次增加；

所述顺序对所述申请或释放日志，以及上一次的合并日志执行存储空间合并的操作为按照日志编号递增的顺序依次执行所述合并的操作。

5.如权利要求1所述的方法，其特征在于，所述PMR包括头部区域和记录了属于该PMR管理的各SMR的位置以及下一个PMR位置的内容区域；SMR包括头部区域和记录所述日志的内容区域。

6.如权利要求5所述的方法，其特征在于，所述存储设备启动工作后，将从磁盘中读取PMR信息、SMR信息到内存中，并基于内存中的PMR信息和SMR信息进行存储空间的管理。

7.如权利要求6所述的方法，其特征在于，若从磁盘中读取到内存中的SMR内容区域中的编号最大的日志是合并日志，在需要进一步进行合并操作时，需要重新将所述合并日志之前的上一次合并日志、上一次合并日志之后的申请日志、释放日志重新进行一次合并操作。

8.如权利要求1所述的方法，其特征在于，在申请存储空间时，如果SMR管理的DR中存在若干个满足申请条件的连续可用的空间，则选择逻辑块地址lba小的所述可用空间。