一种元数据存储方法、系统、设备及存储介质

1.本发明涉及存储技术领域，特别是涉及一种元数据存储方法、系统、设备及存储介质。


背景技术：

2.全闪存阵列是完全由ssd(solid state disk，固态硬盘)构成的存储阵列，具有高性能、低功耗和高容量的优势。全闪存阵列正迅速取代基于磁盘的存储集群，成为存储的首选产品。目前。1pb的全闪存阵列地址映射产生的元数据将达到tb级别，元数据由卷的lba(logical block address，逻辑块地址)到存盘的pba(physical block address，物理块地址)的正向、反向映射，以及重删/压缩hash指纹和pba的映射关系构成。全闪存阵列上的元数据具有规模达千亿级、小尺寸键值对、读写性能要求均高等特点，位于阵列系统的关键路径，对整体性能有较大影响，因此设计高效的元数据存储引擎至关重要。
3.目前进行元数据存储时，通常采用的是多级树合并的方案，可参阅图1，为目前采用的多级树合并的原理示意图，图1中存在四颗b+树，分别称为树a、树b、树c以及树d。完成一次合并刷盘的步骤如下：首先是元数据的更新请求写入内存中的树b中，当树b的大小达到一定阈值后，树b将不再接收更新请求，并启动刷盘准备写入ssd。与此同时，新建树a，使得新的更新请求写入树a，当树b完成刷盘后释放的内存将分配给树a。树b的叶子节点刷盘后需要与上一次合并刷盘所生成的树c进行合并，得到树d。然后删除树b和树c，本轮的树d在下一轮合并中作为树c使用。对于元数据的读请求，则按次序查找树a，树b和树c即可。
4.目前的这种方案保证了大块连续写入，避免频繁修改ssd中的元数据。同时，读请求最多只需查询一次闪存中的b+树，保证了较高的读性能。该方案的问题在于，树b和树c合并必然带来写性能抖动。特别是随着大量请求的写入，树c的体量会持续增大，导致性能抖动的问题将加重，io资源利用率下降幅度可到达50％。此外，内存空间的释放也必然是突然大量释放，不能做到及时释放。
5.综上所述，如何有效地进行元数据存储，避免写性能抖动，是目前本领域技术人员急需解决的技术问题。


技术实现要素：

6.本发明的目的是提供一种元数据存储方法、系统、设备及存储介质，以有效地进行元数据存储，避免写性能抖动。
7.为解决上述技术问题，本发明提供如下技术方案：
8.一种元数据存储方法，包括：
9.接收一个批次的元数据请求并为该批次的所述元数据请求分配线程；
10.基于元数据索引树的路径，确定出各个所述元数据请求各自指向的叶子节点；
11.进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行；
12.基于该批次的所述元数据请求，更新所述元数据索引树；
13.利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果。
14.优选的，在接收一个批次的元数据请求之后，在为该批次的所述元数据请求分配线程之前，还包括：
15.按照键从小到大的顺序，对该批次的元数据请求进行重新排序；
16.其中，当存在键相同的2个或者多个元数据请求时，在重新排序之后，键相同的各个元数据请求的先后顺序，符合重新排序之前的先后顺序。
17.优选的，所述基于该批次的所述元数据请求，更新所述元数据索引树，包括：
18.基于该批次的所述元数据请求，按照自底层向上的顺序逐层更新所述元数据索引树；
19.在进行所述元数据索引树的任意1层的更新时，对该层的节点进行增删，并在增删之后，当存在上溢时，进行该层节点的分裂并传递指针，当存在下溢时，删除下溢的子树并将残留的键值重新插回所述元数据索引树。
20.优选的，所述进行该层节点的分裂并传递指针，包括：
21.通过分裂生成该层各个新的子节点之后，将各个新的子节点的指针一次性插入相应父节点中。
22.优选的，所述接收一个批次的元数据请求，包括：
23.每当一个批次的队列被元数据请求填满时，接收一个批次的元数据请求；
24.每当一个批次的队列未被元数据请求填满，并且计时时长达到第一时长时，接收一个批次的元数据请求，并将所述计时时长清零。
25.优选的，在硬盘中，每个叶子节点具有对应于该叶子节点的1个组，且该组中包括基本页和更新页，所述基本页用于记录下在创建该组时的该叶子节点的各个键值对，所述更新页用于以日志的形式记录下对于该叶子节点的键值对的更新；
26.相应的，所述利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果，包括：
27.对于各个元数据请求中的任意1个读请求，由相应线程查找该读请求所指向的叶子节点所对应的组，并将从该组中读取出的结果进行反馈；
28.对于各个元数据请求中的任意1个非读请求，由相应线程判断该非读请求所指向的叶子节点所对应的组中，更新页是否存在足够的剩余空间；
29.如果是，则利用该组的更新页对该非读请求进行记录；
30.如果否，则将该组的全部数据读入内存并释放该组的空间，将读入内存的数据与暂未插入的更新内容进行合并去重之后，确定出新生成的组的数量，再按照新生成的组的数量，获取相应数量的组的地址，并进行新生成的各组的创建。
31.优选的，所述按照新生成的组的数量，获取相应数量的组的地址，包括：
32.按照新生成的组的数量，通过索引位图获取相应数量的组的地址，并进行所述索引位图的更新；
33.其中，所述索引位图的最底层为位图，在所述位图中，1个bit位表示的是k个连续页的使用状态，k为正整数，且1个组中包括k页，所述，索引位图最底层之外的层由与运算进
行构建以进行空闲空间的查找。
34.优选的，还包括：
35.每当进行所述索引位图的更新时，以增量日志的形式进行索引位图的更新记录；
36.每隔第一时长，进行所述索引位图的副本的更新，并进行持久化保存；
37.当所述索引位图崩溃时，通过持久化保存的所述索引位图的副本以及所述索引位图的更新记录，进行所述索引位图的恢复。
38.优选的，还包括：
39.将每一组内的最小键的数值存储在该组中；
40.当所述元数据索引树崩溃时，从所有有效的组中读取所保存的该组的最小键的数值，并通过重建索引的中间节点，进行所述元数据索引树的恢复。
41.优选的，在每一组中还包括定位页，以通过所述定位页定位出组内的键值对的最新位置。
42.一种元数据存储系统，包括：
43.线程分配模块，用于接收一个批次的元数据请求并为该批次的所述元数据请求分配线程；
44.遍历模块，用于基于元数据索引树的路径，确定出各个所述元数据请求各自指向的叶子节点；
45.节点重分配模块，用于进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行；
46.元数据索引树更新模块，用于基于该批次的所述元数据请求，更新所述元数据索引树；
47.执行模块，用于利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果。
48.一种元数据存储设备，包括：
49.存储器，用于存储计算机程序；
50.处理器，用于执行所述计算机程序以实现如上述所述的元数据存储方法的步骤。
51.一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如上述所述的元数据存储方法的步骤。
52.应用本发明实施例所提供的技术方案，每当接收一个批次的元数据请求之后，便可以据此进行元数据的存储，因此不会出现传统方案中导致性能抖动的情况。具体的，接收一个批次的元数据请求之后，便可以为该批次的元数据请求分配线程，多线程的方式有利于提高并发度。之后，需要基于元数据索引树的路径，确定出各个元数据请求各自指向的叶子节点，然后本技术会进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行。可以看出，由于节点重分配之后，1个叶子节点的各个请求，均是由1个线程来执行，因此不会出现多个线程共同访问1个叶子节点的情况，使得可以进行无锁的元数据索引树的设计，即本技术的方案可以去除多个线程因同步竞争而导致的额外cpu开销，有利于提高并发性。进行了节点重分配之后，可以基于该批次的元数据请求，更新元数据索引树，并且利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果。综上所述，本技术的方案可以有效地进行元数据存储，避免了写性能抖动，
并且元数据索引树可以采用设计，有利于提高并发性，即提高了系统性能。
附图说明
53.为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
54.图1为传统方案中采用的多级树合并的原理示意图；
55.图2为本发明中一种元数据存储方法的实施流程图。
56.图3a为本发明一种具体实施方式中为元数据请求分配线程的示意图；
57.图3b为本发明一种具体实施方式中确定出各个元数据请求各自指向的叶子节点的示意图；
58.图3c为本发明一种具体实施方式中进行节点重分配之后的示意图；
59.图3d为本发明一种具体实施方式中更新元数据索引树中的叶子结点的示意图；
60.图3e为本发明一种具体实施方式中更新元数据索引树中的中间节点的示意图；
61.图3f为本发明一种具体实施方式中更新元数据索引树中的根节点的示意图；
62.图4a为本发明一种具体实施方式中的1个组中的页的构成示意图；
63.图4b为本发明一种具体实施方式中利用更新页对非读请求进行记录的示意图；
64.图4c为本发明一种具体实施方式中触发合并的过程的示意图；
65.图5为本发明一种具体实施方式中的索引位图的结构示意图；
66.图6为本发明一种具体实施方式中采用三层架构的元数据存储引擎的结构示意图；
67.图7为本发明中一种元数据存储系统的结构示意图；
68.图8为本发明中一种元数据存储设备的结构示意图；
69.图9为本发明中一种计算机可读存储介质的结构示意图。
具体实施方式
70.本发明的核心是提供一种元数据存储方法，可以有效地进行元数据存储，避免了写性能抖动，并且元数据索引树可以采用设计，有利于提高并发性，即提高了系统性能。
71.为了使本技术领域的人员更好地理解本发明方案，下面结合附图和具体实施方式对本发明作进一步的详细说明。显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
72.请参考图2，图2为本发明中一种元数据存储方法的实施流程图，该元数据存储方法可以包括以下步骤：
73.步骤s201：接收一个批次的元数据请求并为该批次的元数据请求分配线程。
74.请求队列通常可以存放于保电dram中，可以把请求队列中一定批量的数据打包成一个批，作为b+树的输入，也即作为接收到的一个批次的元数据请求。
75.当然，一个批次最多可以包括多少元数据请求，可以根据需要进行设定和调整，并
不影响本发明的实施。。
76.在实际应用中，通常是在一个批次满时，接收该批次的元数据请求进而进行后续的处理，进一步的，考虑到在部分场合中，如果一个批次长时间未满，则内部的操作可能会被长时间阻塞。为了避免延时过高，则每一个批可以设置有一个相应的定时器，如果定时器超时，则即便该批次未满，也可以接收该批次的元数据请求进而执行。
77.即在本发明的一种具体实施方式中，步骤s201描述的接收一个批次的元数据请求，可以具体包括：
78.每当一个批次的队列被元数据请求填满时，接收一个批次的元数据请求；
79.每当一个批次的队列未被元数据请求填满，并且计时时长达到第一时长时，接收一个批次的元数据请求，并将计时时长清零。
80.在通常情况下，一个批次的队列会很快被元数据请求填满，则此时可以接收一个批次的元数据请求，而部分场合中，如果一个批次的队列未被元数据请求填满，并且计时时长达到了第一时长，为了避免操作被长时间阻塞，则也可以接收该批次的元数据请求，并将计时时长清零。这样的实施方式可以有效地避免性能抖动问题。
81.此外，系统中可以仅设置有1个批处理队列，可以同时设置有多个批处理队列，并不影响本发明的实施。同样的，每个批处理队列的队列大小，第一时长的取值，也均可以根据实际情况进行设定和调整，以使得系统能够在性能和稳定性之间取得一个较好的平衡。
82.在接收一个批次的元数据请求之后，便需要为该批次的元数据请求分配线程。通常是每x个元数据请求分配1个线程，此处的x为正整数，具体取值也可以根据需要进行设定和调整。
83.图3a为一种具体实施方式中为元数据请求分配线程的示意图，在图3的实施方式中为了便于描述以x＝2为例进行说明，图3中的一个批次的元数据请求可以表示为：r(2)，r(19)，r(17)，r(22)，d(18)，i(3)，r(29)，i(35)。括号中的数值为key的数值，即键的数值，r表示读，即该元数据请求具体为读请求，非读请求则有删除，插入，修改这3种，图3a的d表示删除，i表示插入。在图3中，该批次的前2个元数据请求为r(2)和r(19)，分配给了线程1，第3个和第4个元数据请求为r(17)和r(22)，分配给了线程2，相应的，d(18)和i(3)分配给线程3，r(29)和i(35)分配给线程4。
84.步骤s202：基于元数据索引树的路径，确定出各个元数据请求各自指向的叶子节点。
85.进行了线程的分配之后，便可以基于元数据索引树的路径，查询出各个元数据请求各自指向的叶子节点。本技术描述的元数据索引树通常采用的是b+树的结构。
86.由于该步骤只是纯读操作，因此该步骤的过程中无需加锁。
87.可参阅图3b，为一种具体实施方式中确定出各个元数据请求各自指向的叶子节点的示意图，步骤s202的操作也就是将所有的操作请求，根据元数据索引树的路径，遍历至相应的叶子结点，也即构建操作请求到叶子结点的映射。以r(2)这一操作请求为例，该操作请求所映射的叶子节点便是图3b中最左侧的叶子节点，例如该叶子节点的编号为1。同样的，该例子中，i(3)这一操作请求所指向的叶子节点也是叶子节点1。而r(17)和d(18)这2个操作请求所指向的叶子节点均是图3b中的叶子节点2。
88.步骤s203：进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应
的1个线程进行请求的执行。
89.确定出各个元数据请求各自指向的叶子节点之后，本技术需要进行节点重分配，目的是保障每个叶子节点只由一个线程操作。也就是说，在进行了节点重分配之后，要求指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行。
90.例如，用li表示线程i所持有的b+树的叶子节点列表，也即线程i的待处理键值对所属的叶子节点列表。此时，由于键值对的分散，导致一个叶子结点可能被多个线程持有。因此需要进行节点重分配，以重新确定每个结点的归属权，保证一个结点在一个批次的处理过程中，指向该叶子节点的请求只会由一个线程处理。
91.实现节点重分配的具体方式可以有多种，例如可以遍历各个线程的叶子节点列表，以线程i为例，对于线程i的叶子节点列表li中的某个叶子节点λ，如果其在比自己id小的线程j的叶子节点列表中存在，那么就可以把它剔除掉，因为这个叶子节点λ已经对应了一个标识更小的线程j，这样便实现了本技术所需要的节点重分配，即该例子中，实现了每个叶子节点的分配，且只分配给对应id最小的线程。
92.可参阅图3c，为一种具体实施方式中进行节点重分配之后的示意图，可以看出，节点重分配之后，每个叶子节点只由一个线程操作。这样的设计，使得后续不会出现多个线程共同访问1个叶子节点的情况，使得可以进行无锁的元数据索引树的设计，即可以去除多个线程因同步竞争而导致的额外cpu开销，有利于提高并发性。
93.进一步的，在本发明的一种具体实施方式中，在接收一个批次的元数据请求之后，在为该批次的元数据请求分配线程之前，还可以包括：
94.按照键从小到大的顺序，对该批次的元数据请求进行重新排序；
95.其中，当存在键相同的2个或者多个元数据请求时，在重新排序之后，键相同的各个元数据请求的先后顺序，符合重新排序之前的先后顺序。
96.该种实施方式的重新排序也可以称为预排序。通常可以选择归并排序算法先进行多线程排序，即各个线程对获取到的对应的请求进行排序，然后进行单线程归并，即由其中一个线程将多个有序段进行合并。归并排序算法是一个稳定的排序算法，可以保证键的相对顺序稳定。
97.该种实施方式考虑到，本技术的方案需要进行节点重分配，如上文的描述，进行节点重分配时，为了确定某个线程i应当分配给哪个叶子节点，需要遍历各个线程的叶子节点列表，这种通过遍历多次列表，对叶子结点逐一比较的方式，对cpu开销较大，而如果在接收一个批次的元数据请求之后，对该批次的元数据请求进行了预排序，这样使得每个线程的叶子节点列表内部的各个键也是有序的，且相邻的结点列表之间也是有序的，这样使得后续在进行重分配时，可以有效地降低cpu开销。
98.仍然用li表示线程i所持有的b+树的叶子节点列表，对于线程i的叶子节点列表li中的某个叶子节点λ，如果其存在于左边更小的线程的叶子节点列表之中，则可以直接丢弃。对于叶子节点列表中最后一个叶子节点，如果其存在于右边更大的线程的叶子节点列表中，则将这些结点都移动到本线程i的叶子节点列表之中。可以看出，由于节点的有序性，无论是向左还是向右扫描时，当遇到第一个不等于λ的结点时，即可提前终止。
99.上文的例子中，一个批次的元数据请求表示为：r(2)，r(19)，r(17)，r(22)，d(18)，i(3)，r(29)，i(35)。则进行了重新排序之后，得到的该批次的元数据请求表示为：r(2)，i
(3)，r(17)，d(18)，r(19)，r(22)，r(29)，i(35)。还需要说明的是，如果存在键相同的2个或者多个元数据请求时，对于这些元数据请求，重新排序之后的先后顺序符合重新排序之前的先后顺序。例如上述例子中，在i(35)之后还跟着有i(19)和d(2)，则在进行重新排序之后，得到的该批次的元数据请求表示为：r(2)，d(2)，i(3)，r(17)，d(18)，r(19)，d(19)，r(22)，r(29)，i(35)。可以看出，由于重新排序之前，是r(2)在先，d(2)在后，因此重新排序之后，d(2)在r(2)之后，重新排序之前，是r(19)在先，d(19)在后，因此重新排序之后，d(19)在r(19)之后。
100.步骤s204：基于该批次的元数据请求，更新元数据索引树。
101.可以理解的是，由于元数据请求包括读请求和非读请求，对于读请求而言，由于不会改变索引结构，因此具体是基于该批次的全部的元数据请求中的非读请求，更新元数据索引树。而对于读请求，则可以执行获取读请求的执行结果。
102.在更新元数据索引树时，先从叶子节点进行更新，再自底向上逐层更新中间结点，直至根结点。可参阅图3d，图3e以及图3f，分别为一种具体实施方式中更新元数据索引树中的叶子结点的示意图，更新元数据索引树中的中间节点的示意图，以及更新元数据索引树中的根节点的示意图。
103.在图3d中，如上文的描述，对于该例子中的读请求r(2)，r(17)，r(19)等，可以直接反馈执行结果。而对于非读请求，按照图3d至图3f的过程，自底向上逐层更新元数据索引树。
104.在本发明的一种具体实施方式中，步骤s204可以具体包括：
105.基于该批次的元数据请求，按照自底层向上的顺序逐层更新元数据索引树；
106.在进行元数据索引树的任意1层的更新时，对该层的节点进行增删，并在增删之后，当存在上溢时，进行该层节点的分裂并传递指针，当存在下溢时，删除下溢的子树并将残留的键值重新插回元数据索引树。
107.该种实施方式考虑到，无论是修改叶子结点还是中间结点，逻辑是一样的，即均是先对元数据索引树的节点中的键值对进行增删，增删之后，则可以根据节点大小判断是否上溢或者下溢。
108.如果上溢，则需要等分成若干个新的结点，即进行big split操作，进而将指针传递到上层插入父结点。如果下溢，则需要把该子树删除，如果该子树中有残留的kv(orphaned keys)，则在更新元数据索引树之后，要重新按插入操作的流程插回去。
109.进一步的，在本发明的一种具体实施方式中，进行该层节点的分裂并传递指针，可以具体包括：
110.通过分裂生成该层各个新的子节点之后，将各个新的子节点的指针一次性插入相应父节点中。
111.该种实施方式考虑到，当操作请求队列的负载不均衡时，会出现一个线程负责绝大部分请求的情况。一个极端的例子为：当所有的请求均为插入新的键值对时，这些请求会落到同一个结点。
112.针对这种倾斜负载场景下，涉及中间结点多次分裂的情况，本发明的该种实施方式中，可以缓解其对性能的影响。具体的，是在分裂时，先只生成各个新的子节点，而不是直接修改父节点，之后，再将这些新的子节点的指针一次性插入父节点，避免逐个插入导致需
要父节点多次分裂的情况，也就有效地缓解了多次分裂所导致的对性能的影响，使得即使在倾斜负载上，本技术方案也有着可观的性能提高。
113.步骤s205：利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果。
114.在进行了节点重分配之后，便可以利用进行了节点重分配之后的各个线程执行相应的元数据请求，进而反馈执行结果。
115.在本发明的一种具体实施方式中，可以设置有内存索引层，缓存合并层以及闪存管理层的三层结构，内存索引层可以位于内存中，实现b+树的索引优化，即步骤s201至步骤s204的过程可以位于内存索引层。而具体执行请求时，可以由缓存合并层和闪存管理层实现，缓存合并层和闪存管理层均位于ssd中。其中的缓存合并层可以完成键值对的落盘操作，对于刷新落盘的b+树叶子节点起到合并缓冲的作用，从而可以提升元数据落盘的io资源利用率，减少落盘时的写放大，同时保证较高的读取性能。闪存管理层则可以负责落盘地址选择、空闲块管理等机制。可以为缓存合并层提供高效的落盘所需的存储空间资源，尽可能地高效分配连续的空闲空间，也就是说，当大量节点落盘到ssd上时，闪存管理层可以分配对应大小的空闲空间。
116.可参阅图6，为一种具体实施方式中采用三层架构的元数据存储引擎的结构示意图，图6中便示出了内存索引层，缓存合并层以及闪存管理层的三层结构。
117.在本发明的一种具体实施方式中，在硬盘中，每个叶子节点具有对应于该叶子节点的1个组，且该组中包括基本页和更新页，基本页用于记录下在创建该组时的该叶子节点的各个键值对，更新页用于以日志的形式记录下对于该叶子节点的键值对的更新；
118.相应的，利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果，包括：
119.对于各个元数据请求中的任意1个读请求，由相应线程查找该读请求所指向的叶子节点所对应的组，并将从该组中读取出的结果进行反馈；
120.对于各个元数据请求中的任意1个非读请求，由相应线程判断该非读请求所指向的叶子节点所对应的组中，更新页是否存在足够的剩余空间；
121.如果是，则利用该组的更新页对该非读请求进行记录；
122.如果否，则将该组的全部数据读入内存并释放该组的空间，将读入内存的数据与暂未插入的更新内容进行合并去重之后，确定出新生成的组的数量，再按照新生成的组的数量，获取相应数量的组的地址，并进行新生成的各组的创建。
123.该种实施方式中，将分组统一更新的方式，与增量追加日志记录的方式进行了结合。分组统一更新的方式有利于提升落盘数据的聚合度，保证大块连续写，减少空间碎片化程度。而采用增量追加日志记录的方式，有利于降低写放大倍数以及垃圾回收频率。
124.具体的，当内存中的叶子结点进行了修改操作后，需要发起合并下刷。本技术的该种实施方式中，每个叶子节点具有对应于该叶子节点的1个组，即1个叶子节点具有相对应的1个group，而1个组则包括多个页，即多个page组合成1组。page可以划分为基本页和更新页，即划分为base page和delta page。可参阅图4a，为一种具体实施方式中的1个组中的页的构成示意图。图4a中的group1中，包括了n页基本页，即base page1至base pagen，还包括了若干更新页，其中的free page表示的是该更新页中，当前还未记录有数据。
125.基本页用于记录下在创建该组时的该叶子节点的各个键值对，也就是说，基本页中的数据，是在该组被创建时写入的，后续进行该组的更新时，不会对该组的基本页进行新的插入、删除、修改操作。基本页中可以以键值对形式进行数据存放。
126.而更新页用于以日志的形式记录下对于该叶子节点的键值对的更新，也就是说，后续需要执行插入、删除、修改等请求时，是以日志形式逐条将更新记录追加写入delta page中。更新记录在delta page中同样以键值对形式存放，对于插入和修改操作，其值就是更新的值，而删除操作的值则可以标记为无效。
127.此外需要说明的是，base page和delta page的比例根据可以闪存块大小以及其他因素确定。在实际应用中，通常可以选取意多个base page对应多个delta page的方案，如此设计的原因在于平衡空间放大和写放大。具体的，在一组内，如果一个base page对应多个delta page，则会造成超过一倍的空间浪费。如果多个base page对应一个delta page，则少量的delta也会触发频繁的合并，导致base page被重复写，造成写放大，因此可以采用多对多的设计方案，也即base page和delta page的数量相同，并且对于base page的任意更新，delta page的任意剩余空间均可以用于记录该更新。
128.在执行元数据请求时，可以分为读盘和刷盘。
129.对于读盘而言，即对于各个元数据请求中的任意1个读请求而言，是由相应线程查找该读请求所指向的叶子节点所对应的组，并将从该组中读取出的结果进行反馈，也即查找该组，得到读请求所需要的键值对，进而进行反馈。
130.可以理解的是，由于本技术的基本页和更新页的设计，在查找时，应该是先查找叶子节点所在组的delta page，从新至旧依次查找，若找到该键值对则返回结果，若没有找到，说明该键值对没有进行过更新，则可以在base page中查找该键值对并返回结果。
131.对于刷盘而言，即对于各个元数据请求中的任意1个非读请求而言，非读请求需要对内存索引层的叶子结点进行修改操作，并且由缓存层负责刷盘操作，此时可能发生两种情况，一种是组内有空的delta page，则可以直接将更新内容以日志的形式记录到delta page中。即，判断该组中的更新页是否存在足够的剩余空间，如果存在的话，则可以利用该组的更新页对该非读请求进行记录。可参阅图4b，为一种具体实施方式中利用更新页对非读请求进行记录的示意图，图4b中，例如a，b，c，d分别表示4条日志，则这4条日志对应的是4个非读请求。
132.此外需要说明的是，在实际应用中，将更新内容以日志的形式记录到delta page中时，可以是每产生1个批次的请求，便直接将该批次的相应更新内容进行刷盘，也可以是进行缓存之后，再进行刷盘，均不影响本发明的实施。例如一种场合中，对于部分组，设置有该组的写缓存，用于存储针对该组的更新。例如一种场合中，该组的写缓存大小设置为1页page的大小，则如果针对该组的更新内容达到1页page大小时，说明该组的写缓存用尽，则可以将该组的写缓存中的这1页page大小的更新内容，写入至该组的delta page中，这样的操作方式有利于提升大块连续写入的能力。
133.刷盘操作时，另一种可能发生的情况是组内没有空的delta page，也即更新页中不存在足够的剩余空间，此时便会触发合并的过程。
134.具体是先将该组的全部数据读入内存，并且释放该组的空间。然后，需要将读入内存的数据与暂未插入的更新内容进行合并去重，也即排序去重，对于相同的键，仅需要保留
一条最新记录。之后，确定出新生成的组的数量，即根据合并去重结果，计算新生成的组的数量。再按照新生成的组的数量，从闪存管理层获取相应数量的组的地址，可以理解的是，获取的应当是空闲地址，从而可以新生成的各组的创建，进而将新的组刷盘到空闲地址对应的空间上。
135.可以理解的是。若产生大于一个空闲组，意味着叶子节点发生了分裂，为这些组创建相应的叶子节点时，需要通知内存索引层修改中间节点。旧组占用的空间在释放之后，可以被ssd内部的垃圾回收机制重新利用。
136.参阅图4c，为一种具体实施方式中触发合并的过程的示意图，可以看出，由于该例子中，更新页不存在足够的剩余空间，因此将该组的全部数据读入内存并释放该组的空间，与暂未插入的更新内容进行合并去重之后，重新生成新的组。之后按照新生成的组的数量，获取相应的空闲地址，进而将新的组刷盘到空闲地址对应的空间上，可以理解的是，此时，刷盘到空闲地址上是新生成的组各个base page。
137.在本发明的一种具体实施方式中，按照新生成的组的数量，获取相应数量的组的地址，可以具体包括：
138.按照新生成的组的数量，通过索引位图获取相应数量的组的地址，并进行索引位图的更新；
139.其中，索引位图的最底层为位图，在位图中，1个bit位表示的是k个连续页的使用状态，k为正整数，且1个组中包括k页，索引位图最底层之外的层由与运算进行构建以进行空闲空间的查找。
140.按照新生成的组的数量，获取相应数量的组的地址时，需要获取空闲地址，该种实施方式中，可以通过闪存管理层，以索引位图的方式获取空闲地址。
141.可参阅图5，为一种具体实施方式中的索引位图的结构示意图，索引位图的最底层为位图，以k＝8为例，即1个组中包括8页，在位图中，1个bit位表示的是8个连续页的使用状态，例如，用bit为0表示对应的8个连续page全为空闲，bit为1表示对应的8个连续page全被占用。
142.在位图之上可以构建多叉的索引树，构成完整的索引位图，以加速空间分配。在一种具体实施方式中，最底层为位图，倒数第二层往上可以使用与运算来构建，直至构建完整的索引位图。高层使用与运算构建加速查找，分配时则从索引位图的根结点开始向下查找。在索引位图中，只有bit为0的节点向下查找才能找到目标连续空闲空间，从而避免了高额的横向遍历开销。即，由于该种实施方式中的索引位图的索引树是数组式的，不同层之间的结点并没有指针连接，父节点到子节点之间的定位是通过下标按一定规则计算得到的，因此有利于避免高额的横向遍历开销。
143.在本发明的一种具体实施方式中，还可以包括：
144.每当进行索引位图的更新时，以增量日志的形式进行索引位图的更新记录；
145.每隔第一时长，进行索引位图的副本的更新，并进行持久化保存；
146.当索引位图崩溃时，通过持久化保存的索引位图的副本以及索引位图的更新记录，进行索引位图的恢复。
147.该种实施方式中，考虑到可以维护一份位图的副本，以实现崩溃恢复。具体的，每隔第一时长，即每个持久化时间点到来时，可以进行索引位图的副本的更新，也就是将索引
位图的增量日志与当前的索引位图副本进行合并，得到更新之后的索引位图的副本。
148.而每当进行索引位图的更新时，需要以增量日志的形式进行索引位图的更新记录，即对于索引位图的更新，需要在保电内存的增量日志中增加相应记录。
149.而当索引位图崩溃时，通过持久化保存的索引位图的副本，以及索引位图的更新记录，便可以进行索引位图的恢复，也就找到了所有叶子结点的数据。
150.此外，由于位图和日志占用空间较小，通常不超过100mb，因此可以将它们完全放入保电内存，减少位图导致的写放大。
151.在本发明的一种具体实施方式中，还可以包括：
152.将每一组内的最小键的数值存储在该组中；
153.当元数据索引树崩溃时，从所有有效的组中读取所保存的该组的最小键的数值，并通过重建索引的中间节点，进行元数据索引树的恢复。
154.该种实施方式中，可以将每一组内的最小键的数值存储在该组中，例如，将每组的min_key存放到第一个page中，这样有利于减少读取开销。
155.当元数据索引树崩溃时，可以通过位图找到所有有效的组，进而读取每一组的第一个page，获得这组中的min_key，即，从所有有效的组中读取所保存的该组的最小键的数值，进而便可以根据每组的min_key，重建元数据索引树的中间节点，也即进行元数据索引树的恢复。在恢复时，是根据min_key自底向上逐层重建索引的中间节点。
156.在本发明的一种具体实施方式中，在每一组中还包括定位页，以通过定位页定位出组内的键值对的最新位置。
157.在实际应用中，如果某个查询定位到了一个叶子节点，如上文的描述，是通过先查询更新页，确定出本次查询数据的最新数据内容，如果更新页中不存在则查询基本页。也就是说，是先对delta page进行遍历操作，再对base page进行遍历操作。该种实施方式中，可以专门设计一个定位页，称为index page。在加入index page之后，访问组内一个键值对只需要进行两次ssd的读取，极大减少了访问ssd的数据量，增加了读性能。这是因为，通过定位页，可以定位出组内的键值对的最新位置，也即如果某个查询定位到了一个叶子节点，先通过定位页确定出本次查询数据的最新数据内容在delta page的哪页或者是在base page的哪页，进而直接从该页中读取所需要的键值对，无需进行整个group的遍历，极大减少了访问ssd的数据量，增加了读性能。
158.应用本发明实施例所提供的技术方案，每当接收一个批次的元数据请求之后，便可以据此进行元数据的存储，因此不会出现传统方案中导致性能抖动的情况。具体的，接收一个批次的元数据请求之后，便可以为该批次的元数据请求分配线程，多线程的方式有利于提高并发度。之后，需要基于元数据索引树的路径，确定出各个元数据请求各自指向的叶子节点，然后本技术会进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行。可以看出，由于节点重分配之后，1个叶子节点的各个请求，均是由1个线程来执行，因此不会出现多个线程共同访问1个叶子节点的情况，使得可以进行无锁的元数据索引树的设计，即本技术的方案可以去除多个线程因同步竞争而导致的额外cpu开销，有利于提高并发性。进行了节点重分配之后，可以基于该批次的元数据请求，更新元数据索引树，并且利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果。综上所述，本技术的方案可以有效地进行元数据存储，避免了写性能抖动，
并且元数据索引树可以采用设计，有利于提高并发性，即提高了系统性能。
159.相应于上面的方法实施例，本发明实施例还提供了一种元数据存储系统，可与上文相互对应参照。
160.参见图7所示，为本发明中一种元数据存储系统的结构示意图，包括：
161.线程分配模块701，用于接收一个批次的元数据请求并为该批次的元数据请求分配线程；
162.遍历模块702，用于基于元数据索引树的路径，确定出各个元数据请求各自指向的叶子节点；
163.节点重分配模块703，用于进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行；
164.元数据索引树更新模块704，用于基于该批次的元数据请求，更新元数据索引树；
165.执行模块705，用于利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果。
166.实际应用中，线程分配模块701，遍历模块702，节点重分配模块703，以及元数据索引树更新模块704通常可以在内存索引层实现，而执行模块705则可以包括缓存合并层和闪存管理层。
167.在本发明的一种具体实施方式中，线程分配模块701还用于：在接收一个批次的元数据请求之后，在为该批次的元数据请求分配线程之前，按照键从小到大的顺序，对该批次的元数据请求进行重新排序；
168.其中，当存在键相同的2个或者多个元数据请求时，在重新排序之后，键相同的各个元数据请求的先后顺序，符合重新排序之前的先后顺序。
169.在本发明的一种具体实施方式中，元数据索引树更新模块704，具体用于：
170.基于该批次的元数据请求，按照自底层向上的顺序逐层更新元数据索引树；
171.在进行元数据索引树的任意1层的更新时，对该层的节点进行增删，并在增删之后，当存在上溢时，进行该层节点的分裂并传递指针，当存在下溢时，删除下溢的子树并将残留的键值重新插回元数据索引树。
172.在本发明的一种具体实施方式中，进行该层节点的分裂并传递指针，包括：
173.通过分裂生成该层各个新的子节点之后，将各个新的子节点的指针一次性插入相应父节点中。
174.在本发明的一种具体实施方式中，线程分配模块701接收一个批次的元数据请求，包括：
175.每当一个批次的队列被元数据请求填满时，接收一个批次的元数据请求；
176.每当一个批次的队列未被元数据请求填满，并且计时时长达到第一时长时，接收一个批次的元数据请求，并将计时时长清零。
177.在本发明的一种具体实施方式中，在硬盘中，每个叶子节点具有对应于该叶子节点的1个组，且该组中包括基本页和更新页，基本页用于记录下在创建该组时的该叶子节点的各个键值对，更新页用于以日志的形式记录下对于该叶子节点的键值对的更新；
178.相应的，执行模块705，具体用于：
179.对于各个元数据请求中的任意1个读请求，由相应线程查找该读请求所指向的叶
子节点所对应的组，并将从该组中读取出的结果进行反馈；
180.对于各个元数据请求中的任意1个非读请求，由相应线程判断该非读请求所指向的叶子节点所对应的组中，更新页是否存在足够的剩余空间；
181.如果是，则利用该组的更新页对该非读请求进行记录；
182.如果否，则将该组的全部数据读入内存并释放该组的空间，将读入内存的数据与暂未插入的更新内容进行合并去重之后，确定出新生成的组的数量，再按照新生成的组的数量，获取相应数量的组的地址，并进行新生成的各组的创建。
183.在本发明的一种具体实施方式中，按照新生成的组的数量，获取相应数量的组的地址，包括：
184.按照新生成的组的数量，通过索引位图获取相应数量的组的地址，并进行索引位图的更新；
185.其中，索引位图的最底层为位图，在位图中，1个bit位表示的是k个连续页的使用状态，k为正整数，且1个组中包括k页，，索引位图最底层之外的层由与运算进行构建以进行空闲空间的查找。
186.在本发明的一种具体实施方式中，还包括：
187.每当进行索引位图的更新时，以增量日志的形式进行索引位图的更新记录；
188.每隔第一时长，进行索引位图的副本的更新，并进行持久化保存；
189.当索引位图崩溃时，通过持久化保存的索引位图的副本以及索引位图的更新记录，进行索引位图的恢复。
190.在本发明的一种具体实施方式中，还包括：
191.将每一组内的最小键的数值存储在该组中；
192.当元数据索引树崩溃时，从所有有效的组中读取所保存的该组的最小键的数值，并通过重建索引的中间节点，进行元数据索引树的恢复。
193.在本发明的一种具体实施方式中，在每一组中还包括定位页，以通过定位页定位出组内的键值对的最新位置。
194.相应于上面的方法和系统实施例，本发明实施例还提供了一种元数据存储设备以及一种计算机可读存储介质，可与上文相互对应参照。
195.可参阅图8，该元数据存储设备可以包括：
196.存储器801，用于存储计算机程序；
197.处理器802，用于执行计算机程序以实现如上述任一实施例中的元数据存储方法的步骤。
198.该计算机可读存储介质90上存储有计算机程序91，计算机程序91被处理器执行时实现如上述任一实施例中的元数据存储方法的步骤。这里所说的计算机可读存储介质90包括随机存储器(ram)、内存、只读存储器(rom)、电可编程rom、电可擦除可编程rom、寄存器、硬盘、可移动磁盘、cd-rom、或技术领域内所公知的任意其它形式的存储介质。
199.还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要
素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
200.专业人员还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。
201.本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的技术方案及其核心思想。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明的保护范围内。

技术特征：
1.一种元数据存储方法，其特征在于，包括：接收一个批次的元数据请求并为该批次的所述元数据请求分配线程；基于元数据索引树的路径，确定出各个所述元数据请求各自指向的叶子节点；进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行；基于该批次的所述元数据请求，更新所述元数据索引树；利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果。2.根据权利要求1所述的元数据存储方法，其特征在于，在接收一个批次的元数据请求之后，在为该批次的所述元数据请求分配线程之前，还包括：按照键从小到大的顺序，对该批次的元数据请求进行重新排序；其中，当存在键相同的2个或者多个元数据请求时，在重新排序之后，键相同的各个元数据请求的先后顺序，符合重新排序之前的先后顺序。3.根据权利要求1所述的元数据存储方法，其特征在于，所述基于该批次的所述元数据请求，更新所述元数据索引树，包括：基于该批次的所述元数据请求，按照自底层向上的顺序逐层更新所述元数据索引树；在进行所述元数据索引树的任意1层的更新时，对该层的节点进行增删，并在增删之后，当存在上溢时，进行该层节点的分裂并传递指针，当存在下溢时，删除下溢的子树并将残留的键值重新插回所述元数据索引树。4.根据权利要求3所述的元数据存储方法，其特征在于，所述进行该层节点的分裂并传递指针，包括：通过分裂生成该层各个新的子节点之后，将各个新的子节点的指针一次性插入相应父节点中。5.根据权利要求1所述的元数据存储方法，其特征在于，所述接收一个批次的元数据请求，包括：每当一个批次的队列被元数据请求填满时，接收一个批次的元数据请求；每当一个批次的队列未被元数据请求填满，并且计时时长达到第一时长时，接收一个批次的元数据请求，并将所述计时时长清零。6.根据权利要求1至5任一项所述的元数据存储方法，其特征在于，在硬盘中，每个叶子节点具有对应于该叶子节点的1个组，且该组中包括基本页和更新页，所述基本页用于记录下在创建该组时的该叶子节点的各个键值对，所述更新页用于以日志的形式记录下对于该叶子节点的键值对的更新；相应的，所述利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果，包括：对于各个元数据请求中的任意1个读请求，由相应线程查找该读请求所指向的叶子节点所对应的组，并将从该组中读取出的结果进行反馈；对于各个元数据请求中的任意1个非读请求，由相应线程判断该非读请求所指向的叶子节点所对应的组中，更新页是否存在足够的剩余空间；如果是，则利用该组的更新页对该非读请求进行记录；如果否，则将该组的全部数据读入内存并释放该组的空间，将读入内存的数据与暂未
插入的更新内容进行合并去重之后，确定出新生成的组的数量，再按照新生成的组的数量，获取相应数量的组的地址，并进行新生成的各组的创建。7.根据权利要求6所述的元数据存储方法，其特征在于，所述按照新生成的组的数量，获取相应数量的组的地址，包括：按照新生成的组的数量，通过索引位图获取相应数量的组的地址，并进行所述索引位图的更新；其中，所述索引位图的最底层为位图，在所述位图中，1个bit位表示的是k个连续页的使用状态，k为正整数，且1个组中包括k页，所述，索引位图最底层之外的层由与运算进行构建以进行空闲空间的查找。8.根据权利要求7所述的元数据存储方法，其特征在于，还包括：每当进行所述索引位图的更新时，以增量日志的形式进行索引位图的更新记录；每隔第一时长，进行所述索引位图的副本的更新，并进行持久化保存；当所述索引位图崩溃时，通过持久化保存的所述索引位图的副本以及所述索引位图的更新记录，进行所述索引位图的恢复。9.根据权利要求6所述的元数据存储方法，其特征在于，还包括：将每一组内的最小键的数值存储在该组中；当所述元数据索引树崩溃时，从所有有效的组中读取所保存的该组的最小键的数值，并通过重建索引的中间节点，进行所述元数据索引树的恢复。10.根据权利要求6所述的元数据存储方法，其特征在于，在每一组中还包括定位页，以通过所述定位页定位出组内的键值对的最新位置。11.一种元数据存储系统，其特征在于，包括：线程分配模块，用于接收一个批次的元数据请求并为该批次的所述元数据请求分配线程；遍历模块，用于基于元数据索引树的路径，确定出各个所述元数据请求各自指向的叶子节点；节点重分配模块，用于进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行；元数据索引树更新模块，用于基于该批次的所述元数据请求，更新所述元数据索引树；执行模块，用于利用进行了节点重分配之后的各个线程执行相应的元数据请求，并反馈执行结果。12.一种元数据存储设备，其特征在于，包括：存储器，用于存储计算机程序；处理器，用于执行所述计算机程序以实现如权利要求1至10任一项所述的元数据存储方法的步骤。13.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1至10任一项所述的元数据存储方法的步骤。

技术总结
本申请公开了一种元数据存储方法、系统、设备及存储介质，应用于存储技术领域，包括：接收一个批次的元数据请求并为该批次的元数据请求分配线程；基于元数据索引树的路径，确定出各个元数据请求各自指向的叶子节点；进行节点重分配，以使得指向相同叶子节点的各个请求，均由唯一对应的1个线程进行请求的执行；基于该批次的元数据请求，更新元数据索引树；利用进行了节点重分配之后的各个线程执行相应的元数据请求以实现数据读写，并反馈执行结果。应用本申请的方案，可以有效地进行元数据存储，避免了写性能抖动，并且元数据索引树可以采用设计，有利于提高并发性，即提高了系统性能。性能。性能。


技术研发人员：孙斌 苏楠 刘志勇
受保护的技术使用者：华中科技大学
技术研发日：2023.06.09
技术公布日：2023/9/20