一种数据库持久化组织优化方法

key2；如果维护是数据更新，则将该内部键值key2更新为本次更新的内部键值key3，并将内部键值key3在磁盘中指向的数据存储为输入的更新数据；如果维护是数据删除，则将其对应的内部键值key3更新为空；当用户对该数据库中的数据进行读取时，首先根据该用户读取的用户键值与ali中的内部键值进行映射，如果找到匹配的内部键值，则以该匹配的内部键值在缓存中进行查找，如果命中则返回对应的数据，如果未命中则以该匹配的内部键值为键在kvssd中的数据文件中查找对应的数据。
9.进一步的，所述追加日志索引结构ali包括一树形结构，其根节点、中间节点中以多个用户键值有序地划分区间，并存储相应多个用户键值范围区间指向的下一层节点的指针，每一叶子节点中存储的键为用户键值、数据为内部键值。
10.进一步的，所述追加日志索引结构ali中维护一节点日志，记录了每个叶子节点中存储的映射关系；对每一叶子节点设置一个编号以及一个计数器，所述计数器用于记录叶子节点的更新次数，节点日志的键为一个8字节的数值，其中前四字节为叶子节点编号，后四字节为该叶子节点的计数器的值，存储的值是该叶子节点上本次写入或更新的数据键值到内部键值的映射关系。
11.进一步的，当ali中的节点日志数达到阈值或事务提交时，对ali进行更新，并在kvssd中对实际数据进行操作。
12.进一步的，所述内部键值为一个8字节的编号，其中前4字节为用户的提交编号，后4字节为序列号；所述提交编号为一递增的数值，标识每次用户事务提交的编号；所述事务包括数据的写入、删除、更新、查询。
13.进一步的，当事务回滚时，将该事务的提交编号与ali中的内部键值进行匹配，以匹配的内部键值为键在该数据库查找对应的数据进行删除，并同步删除该事务回滚前更新的节点日志。
14.进一步的，在事务提交后需要建立快照时，将当前ali中每个叶子节点保存的映射关系全部存入一个数据结构中进行保存，并将此数据结构中的各内部键值设为不可变版本；然后将所得快照中的内部键值对应的数据一直保留在所述kvssd中。
15.进一步的，所述kvssd封装了键值对插入接口、更新接口、删除接口以及根据键进行查询的查询接口。
16.一种服务器，其特征在于，包括存储器和处理器，所述存储器存储计算机程序，所述计算机程序被配置为由所述处理器执行，所述计算机程序包括用于执行上述方法中各步骤的指令。
17.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现上述方法的步骤。
18.本发明的优点如下：相对传统基于数据块磁盘的b+树结构，本发明的索引结构减少了磁盘io次数，并在数据插入及更新中大幅提升了插入效率。
19.相对直接使用kvssd的数据库，本发明提供了快照机制以及数据库事务的功能实现。
附图说明
20.图1为ali索引结构。
21.图2为ali持久化结构。
22.图3为向数据库插入数据时的流程图。
23.图4为本发明据库持久化组织优化方法流程图。
具体实施方式
24.下面结合附图对本发明进行进一步详细描述，所举实例只用于解释本发明，并非用于限定本发明的范围。
25.本发明提出一种追加日志索引结构，为类b+树的优化方式。以此为基础实现整体数据库存储系统架构。本发明提出的索引结构以及存储系统的具体实施方式是基于新硬件kvssd所提供的固件接口进行设计的，在其基础上实现了数据库快照机制、范围查询、事务支持等相关功能。
26.在数据库设计中将整体设计为两个部分，一部分是追加日志索引结构ali，其存储了用户键值到内部键值一对一的映射关系，在内存中建立索引结构，并将映射关系以节点日志的形式追加存储在键值固态硬盘（kvssd）硬件中，其中kvssd硬件封装了键值对的相关接口，包括键值对插入、更新、删除以及根据键进行查询的功能。另一部分为实际数据存储系统部分，以内部键值为主键建立了存储结构，使用lru等缓存机制进行缓存优化，并利用kvssd的键值存储特性将数据与内部键值进行了数据持久化。
27.如图3所示，本发明的整体过程为当用户向数据库插入数据时，会将用户键值以及实际数据作为系统输入，首先在ali结构中将用户键值与内部键值进行映射，并将映射关系进行磁盘文件上的持久化。其次将实际数据持久化，在kvssd中以内部键值为主键进行索引。
28.追加日志索引结构（append log index-ali）：在通用的数据库索引b+树结构中，由于没有kvssd的特性可以使用，b+树以用户键值为判断的依据，在最后一层也就是叶子节点中存储了指向数据块存储位置的偏移。同时，为保证用户事务acid的特性，传统基于数据块磁盘的b+树优化方式为在数据写入时需要将节点进行复制，或在节点更新完成后再对树结构进行逐层的整理，前者会将需要更新的数据节点全部读入内存进行更新，增加磁盘io，后者会增加节点调整的额外计算量。
29.如图1所示，在本发明提出的追加日志索引结构（ali）中，根节点、内部节点与b+树相同，每个节点上以多个用户键值有序地划分区间，并存储了相应多个用户键值范围区间指向的下一层节点的指针。在叶子节点上不同于基于块存储硬件的b+树的是，ali叶子节点的键为用户键值，存储的数据是内部键值，通过内部键值使用kvssd硬件提供的接口可以直接的访问数据的实际存储位置。在数据写入时，直接更新内存中叶子节点映射到的内部键值，不需要像传统b+树一样读取目标数据块中的数据进行复制或再对结构进行整理，同时追加一条更新的日志记录用于索引结构的持久化存储。
30.其中内部键值为一个8字节的编号，其中前4字节为提交编号，后4字节为序列号，其中提交编号为一递增的数值，标识每次用户事务提交的编号。每次事务提交会将事务中修改的多条用户数据进行持久化，因此需要后四字节的序列号标识本条用户数据在本次提
交中的编号，将此两者拼接得到8字节的内部键值。
31.同步的，如图2所示，在ali结构中维护了一个节点日志，记录了每个叶子节点中由用户键值到内部键值的映射关系。对于节点日志记录，也以键值对的形式进行存储。对ali中的每一个叶子节点设置一个编号以及一个计数器，计数器记录的是此节点更新的次数，节点日志的键为一个8字节的数值，其中前四字节为节点编号，后四字节为此节点计数器的值，存储的值是此节点上本次写入或更新的数据键值到内部键值的映射关系。如图中4.0的记录表示存储的是节点4在第0次更新时存储的值，值为用户键值a指向内部键值ink0的映射关系，映射关系的表示可以使用字符串”a-》ink0”或者其他数据结构进行表示。
32.本发明提出的ali索引结构若使用传统基于块的ssd进行实现，则从内部键值寻找实际存储位置还需要额外的索引结构进行映射关系的存储，会增加大量的磁盘以及内存使用空间，并且由于多次映射也会降低数据操作的效率，因此只适合提供了键值接口的kvssd新硬件进行底层支持。
33.以图1为例，ali索引结构中共有0至5六个节点，有a、b、c三个用户键值，设最初a映射的内部键值为ink0，在一次更新中映射的键值更新为ink1，因此在内存中将数据直接更新，在节点日志以及持久化中以追加的方式将a、b、c三个数据键的内部键值数据映射关系进行了存储。针对图1中节点3，其在kvssd中已经存储了d用户键值到ink5的映射关系，而在内存中没有进行缓存，在更新时并不需要强制将节点3中的数据读入内存，而是直接在节点日志中添加一条新的记录即可。
34.针对以上提及的类似节点3的更新的情况，由于b+树在数据增加时需要考虑平衡以及节点拆分，而ali索引结构在写入时并不能确定其是插入操作（数据数量增加）还是更新操作（数据数量不变），因此针对两种操作均以插入进行计算，在内存中对所有已创建的节点建立计数器，并在每次插入时将计数器加一。如果节点一直未装载到内存中，则当计数器的计数值达到拆分阈值时，将节点装载到内存中，并将此节点计数器的值更新为此节点中实际记录数。如果更新后仍然超过拆分阈值，则继续进行节点的拆分操作以维持ali类b+树的结构平衡。
35.此时新旧数据都会在磁盘中保存，在保证事务acid特性的同时大幅减少计算量以及多余的文件读取工作，提高数据写入的效率。在达到预先设定的数据更新数量阈值时将更新的节点日志数据统一更新到磁盘上，以批量写入的模式提高了磁盘的写入效率。
36.在上述索引架构中，如果用户不进行清理，所有数据库更新的历史数据都会保存在磁盘中，因此针对每一次提交，都留存了数据快照，可以基于提交设置快照，将某次提交时最新的数据进行保留，以备后续进行快速数据库恢复。同时针对此索引结构，设置每个节点日志的最大数量阈值，当节点的日志数量达到阈值后会进行日志的合并，将已经过期的日志合并删除，保留最新一次的映射关系。在存储系统中存储的数据版本与ali索引结构中保存的一致，也就是在ali索引结构进行数据合并时，数据合并为将节点日志中最新的一条日志记录的内部键值更新到ali索引结构相应的节点中，并舍弃之前版本的映射关系，同时将舍弃的内部键值对应的实际数据也从kvssd硬盘中进行删除。
37.在数据读取时，如果某一节点不在内存中，将以节点编号为键，使用kvssd提供的接口在硬盘中进行查询，将此节点中的全部日志读取，并在内存中进行合并，合并时将最新一次的映射关系全部保留在内存中的ali索引结构中。
38.本发明据库持久化组织优化方法流程如图4所示，具体包括如下内容：数据写入：首先由本次的提交请求获取需要写入或更新的用户键值，以及实际写入的数据。根据提交等信息计算每条涉及的数据的内部键值，提交编号以及序列号的计算方式见事务支持步骤。当写入操作时将用户键值作为键插入到ali索引结构中，当为更新操作时现在ali索引结构中搜索相应需要更新的用户键值。将内部键值插入或更新到相应位置。然后以内部键值为键，实际数据为值调用kvssd的写入接口进行数据持久化操作。此时原始版本数据与本次提交数据都在磁盘中留存。
39.当ali索引结构中的节点日志数达到阈值或事务提交时，对索引结构进行更新，首先在内存中对索引结构中的原始对应关系进行更新，在叶子节点中将本次更新的用户键值对应的内部键值更新为上次提交中的内部键值，并同步追加结点更新日志。在更新达到阈值后将更新的叶子节点日志刷入到磁盘中。
40.数据维护：数据维护包括数据更新以及删除，均为将已有的用户键值与新的内部键值进行映射。首先根据用户需要更新的用户键值在ali结构中查询到相应的节点，根据提交编号以及序列号生成本条数据的内部键值，数据删除时内部键值为空。最后根据更新的内部键值在kvssd中将实际数据写入相应的位置。
41.数据读取：首先针对用户访问的某用户键值在ali索引结构中进行查询，如果在ali的内存中命中，则直接使用其映射的内部键值在存储系统中进行查询。在存储系统中也可以建立内存缓冲机制，如lru等相关缓存机制，进行键值对的存储。如果内部键值在缓存中命中，则可以将实际数据返回给用户。如果没有在缓存中，再使用内部键值在kvssd中进行获取，以尽可能减少磁盘io次数。
42.事务支持：在基于ali索引结构的存储系统中，由于内部键值的引入，对用户事务的支持也会比较简单。在用户开启事务后，首先将之前保存的提交编号加一作为当前的提交编号，在事务中存在多条数据操作，包括数据的增删改查，其中查询不对数据库内容进行更改，在插入、删除、更新操作时，针对每条更改的数据进行编号为序列号，由此得到本条记录的8字节内部键值。将输入的用户键值在ali结构中与得到的内部键值进行映射，并将修改添加到节点日志中。并直接根据内部键值通过kvssd的插入、删除、更新接口将数据进行相应修改。当用户进行事务提交时会主动地对ali索引结构中的节点日志进行持久化，表示本次事务已经完成提交。
43.当事务回滚时，将本次提交编号n作为前四字节，在内部键值中直接使用位与进行匹配，忽略后四字节的序列号，将匹配到的内部键值对应的实际数据进行删除，并在ali结构中同步删除本次事务回滚前事务中的全部节点日志。表示事务已经完成回滚。
44.数据快照与恢复：在某次事务提交后，用户可以手动进行快照的建立，由于ali索引结构中针对每个用户键值都保存了其最新的内部键值的映射关系，并且全部版本的实际数据在kvssd中都进行了持久化存储，可以快速的根据ali索引结构将全部当前最新数据进行快照，即将当前
ali索引中每个叶子节点保存的用户键值与内部键值的映射关系全部存入一个数据结构中进行保存，常见或可以简单实现的数据结构包括数组、链表等。并将此数据结构中的各内部键值设为不可变版本，在每次节点数据合并以及数据删除时进行检查，将此快照中的内部键值对应的数据一直保留在kvssd中。
45.尽管为说明目的公开了本发明的具体实施例，其目的在于帮助理解本发明的内容并据以实施，本领域的技术人员可以理解：在不脱离本发明及所附的权利要求的精神和范围内，各种替换、变化和修改都是可能的。因此，本发明不应局限于最佳实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。

技术特征：
1.一种数据库持久化组织优化方法，其步骤包括：针对待优化的数据库，在内存中为该数据库创建一追加日志索引结构ali，用于存储用户键值到内部键值一对一的映射关系，并将所述映射关系以节点日志的形式追加存储在键值固态硬盘kvssd中；该数据库持久化存储在所述kvssd中，为该数据库中的每一数据生成一内部键值，将数据及其内部键值进行映射及数据持久化并使用缓存机制进行缓存优化；当用户向该数据库插入数据时，将该用户的用户键值与ali中的内部键值进行映射，如果找到匹配的内部键值，则以该匹配的内部键值为键将该用户待插入数据插入到该数据库中；如果未找到匹配的内部键值，则为该用户待插入数据生成一内部键值key1并与该用户的用户键值u建立映射关系i1，然后以该内部键值key1为键将该用户待插入数据插入到该数据库中；当用户对该数据库中的数据进行维护时，首先根据需要更新的用户键值在ali中查询到匹配的用户键值u1，以该匹配的用户键值u1为键在该数据库查找对应的内部键值 key2；如果维护是数据更新，则将该内部键值key2更新为本次更新的内部键值key3，并将内部键值key3在磁盘中指向的数据存储为输入的更新数据；如果维护是数据删除，则将其对应的内部键值key3更新为空；当用户对该数据库中的数据进行读取时，首先根据该用户读取的用户键值与ali中的内部键值进行映射，如果找到匹配的内部键值，则以该匹配的内部键值在缓存中进行查找，如果命中则返回对应的数据，如果未命中则以该匹配的内部键值为键在kvssd中的数据文件中查找对应的数据。2.根据权利要求1所述的方法，其特征在于，所述追加日志索引结构ali包括一树形结构，其根节点、中间节点中以多个用户键值有序地划分区间，并存储相应多个用户键值范围区间指向的下一层节点的指针，每一叶子节点中存储的键为用户键值、数据为内部键值。3.根据权利要求2所述的方法，其特征在于，所述追加日志索引结构ali中维护一节点日志，记录了每个叶子节点中存储的映射关系；对每一叶子节点设置一个编号以及一个计数器，所述计数器用于记录叶子节点的更新次数，节点日志的键为一个8字节的数值，其中前四字节为叶子节点编号，后四字节为该叶子节点的计数器的值，存储的值是该叶子节点上本次写入或更新的数据键值到内部键值的映射关系。4.根据权利要求3所述的方法，其特征在于，当ali中的节点日志数达到阈值或事务提交时，对ali进行更新，并在kvssd中对实际数据进行操作。5.根据权利要求3所述的方法，其特征在于，所述内部键值为一个8字节的编号，其中前4字节为用户的提交编号，后4字节为序列号；所述提交编号为一递增的数值，标识每次用户事务提交的编号；所述事务包括数据的写入、删除、更新、查询。6.根据权利要求5所述的方法，其特征在于，当事务回滚时，将该事务的提交编号与ali中的内部键值进行匹配，以匹配的内部键值为键在该数据库查找对应的数据进行删除，并同步删除该事务回滚前更新的节点日志。7.根据权利要求5所述的方法，其特征在于，在事务提交后需要建立快照时，将当前ali中每个叶子节点保存的映射关系全部存入一个数据结构中进行保存，并将此数据结构中的各内部键值设为不可变版本；然后将所得快照中的内部键值对应的数据一直保留在所述kvssd中。
8.根据权利要求1所述的方法，其特征在于，所述kvssd封装了键值对插入接口、更新接口、删除接口以及根据键进行查询的查询接口。9.一种服务器，其特征在于，包括存储器和处理器，所述存储器存储计算机程序，所述计算机程序被配置为由所述处理器执行，所述计算机程序包括用于执行权利要求1至8任一所述方法中各步骤的指令。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至8任一所述方法的步骤。

技术总结
本发明公开了一种数据库持久化组织优化方法，其步骤包括：针对待优化的数据库，在内存中为该数据库创建一追加日志索引结构ALI，用于存储用户键值到内部键值一对一的映射关系，并将映射关系存储在KVSSD中；该数据库持久化存储在KVSSD中，为该数据库中的每一数据生成一内部键值，将数据及其内部键值进行映射及数据持久化；当用户向该数据库插入数据时，将该用户的用户键值与ALI中的内部键值进行映射，如果找到匹配的内部键值，则以该匹配的内部键值为键将待插入数据插入到数据库中；如果未找到匹配的内部键值，则为待插入数据生成一内部键值并与该用户的用户键值建立映射关系，然后以该内部键值为键将待插入数据插入到该数据库中。库中。库中。


技术研发人员：王潮 刘雨蒙 赵怡婧 徐帆江
受保护的技术使用者：中国科学院软件研究所
技术研发日：2023.08.31
技术公布日：2023/10/11