基于非易失性内存的文件系统新型索引方法及系统

1.本发明涉及文件系统索引方法技术领域，具体地，涉及基于非易失性内存的文件系统新型索引方法及系统。


背景技术：

2.非易失性内存是一种同时拥有传统内存的低延迟、高吞吐特征和传统存储设备的断电后内容不易失特征的新型存储介质。并且它可以以字节粒度寻址，从而允许处理器像操作传统内存一样通过load/store指令直接访问非易失内存中的内容
3.当前的文件系统通常采用层级结构进行组织，对文件进行读写需要先根据该文件路径定位文件，若使用绝对路径则是从文件系统根目录进行层层索引：文件系统需要首先定位根目录，并根据第一级目录名在根目录的索引结构中找到对应的目录，并根据第二级目录名在该目录的索引结构中找到下一级目录，以此类推。
4.由于非易失性内存相较于传统块存储设备(机械硬盘、固态硬盘)读写性能极高，因此对于文件数据读写操作而言，性能瓶颈由数据读写转向元数据操作。尤其地，对于目录层次深的小文件读取操作而言，以根目录为起点进行的层级索引相较与文件实际的数据读写来说时间开销占比可观。而许多社交网络平台系统中需要存储大量用户的头像等占用空间小的文件，并且需要在需要时快速索引，而目前的索引性能受制于从根目录起始的索引设计，无法充分利用非易失性内存的高性能。
5.专利文献cn110413724b(申请号：201910527961.0)公开了一种数据检索方法与装置，包括：将检索引擎中的映射表和高频文档同步到非易失性内存储器，响应于接收到不同检索条件，通过映射表在易失性内存储器中执行反向索引，以获得不同被检索文档，根据不同被检索文档的各自的被检索频率重新确定高频文档，获取新增索引文档并写入非易失性内存储器，并在非易失性内存储器中根据新增索引文档更新映射表，将重新确定的高频文档、新增索引文档、和更新的映射表反馈到检索引擎。
6.因此我们需要基于为非易失性内存的文件系统设计新型的索引系统来消除目录深的小文件的索引开销，从而充分利用非易失性内存的高性能。


技术实现要素：

7.针对现有技术中的缺陷，本发明的目的是提供一种针对基于非易失性内存的文件系统的新型索引方法及系统。
8.根据本发明提供的一种针对基于非易失性内存的文件系统的新型索引方法，包括：同时进行反向索引和常规索引，通过多线程同时检索常规索引和反向索引直至找到对应文件；
9.所述反向索引以文件路径的末端文件名为起点反向遍历文件路径进行目录索引直至获得对应文件；
10.所述常规索引由根目录开始，通过逐级目录名进行索引直至获得对应文件。
11.优选地，所述反向索引包括多级索引，当文件系统使用文件路径进行反向索引时，首先使用路径最末端的文件名在第一级索引中进行检索，若第一级索引所得到的结果包含多个文件，则再次通过路径中次末端的目录名在第二级索引中进行检索，直至找到对应文件。
12.优选地，所述反向索引中每级索引由哈希表构成，第一级索引使用末端文件名进行哈希搜索定位到哈希表项，若哈希表项仅对应一个文件，则指向文件反向索引节点，当前反向索引节点内存储文件的完整路径以及文件索引节点，完整路径用于与搜索路径进行完整匹配，文件索引节点指向文件实际位置；若哈希表项对应多个文件，则指向另一个哈希表作为下一级索引，通过文件名上一级的文件目录进行哈希搜索，以此类推。
13.优选地，所述通过多线程同时检索常规索引和反向索引直至找到对应文件采用：在同时查询常规索引和反向索引时，若任一索引未查询到文件路径所对应文件，则直接返回当前文件不存在；若任一索引根据文件路径查询到对应文件，则直接返回当前文件。
14.优选地，在进行文件系统目录操作时，在修改文件系统常规索引时，需要同时修改反向索引，保证常规索引和反向索引包含相同的文件系统目录信息。
15.根据本发明提供的一种针对基于非易失性内存的文件系统的新型索引系统，包括：同时进行反向索引和常规索引，通过多线程同时检索常规索引和反向索引直至找到对应文件；
16.所述反向索引以文件路径的末端文件名为起点反向遍历文件路径进行目录索引直至获得对应文件；
17.所述常规索引由根目录开始，通过逐级目录名进行索引直至获得对应文件。
18.优选地，所述反向索引包括多级索引，当文件系统使用文件路径进行反向索引时，首先使用路径最末端的文件名在第一级索引中进行检索，若第一级索引所得到的结果包含多个文件，则再次通过路径中次末端的目录名在第二级索引中进行检索，直至找到对应文件。
19.优选地，所述反向索引中每级索引由哈希表构成，第一级索引使用末端文件名进行哈希搜索定位到哈希表项，若哈希表项仅对应一个文件，则指向文件反向索引节点，当前反向索引节点内存储文件的完整路径以及文件索引节点，完整路径用于与搜索路径进行完整匹配，文件索引节点指向文件实际位置；若哈希表项对应多个文件，则指向另一个哈希表作为下一级索引，通过文件名上一级的文件目录进行哈希搜索，以此类推。
20.优选地，所述通过多线程同时检索常规索引和反向索引直至找到对应文件采用：在同时查询常规索引和反向索引时，若任一索引未查询到文件路径所对应文件，则直接返回当前文件不存在；若任一索引根据文件路径查询到对应文件，则直接返回当前文件。
21.优选地，在进行文件系统目录操作时，在修改文件系统常规索引时，需要同时修改反向索引，保证常规索引和反向索引包含相同的文件系统目录信息。
22.与现有技术相比，本发明具有如下的有益效果：
23.1、本发明在进行索引时通过多线程同时检索常规索引以及反向索引以充分利用非易失性内存的性能优势；
24.2、通过多线程同时对两个索引进行检索以降低查询的延迟，提高查询的性能；
25.3、反向索引的好处在于文件系统文件重名情况较少，可以快速缩小搜索文件的范
围；
26.4、并行查询的好处在于在极端情况下，例如所查询文件在文件系统内有大量同名文件，反向索引的查询效率可能低于常规索引，在这种情况下可以保证新型索引方法的性能不低于传统索引(即仅常规索引)，从而充分利用非易失性内存的高性能优势，加速对目录层次深的文件的索引；
27.5、若任意索引返回查询结果(文件存在或不存在)，则直接将结果返回给用户而不需要等待另一索引的查询结果；
28.6、本发明对目录层次深的小文件读写能取得性能上的提升。
附图说明
29.通过阅读参照以下附图对非限制性实施例所作的详细描述，本发明的其它特征、目的和优点将会变得更明显：
30.图1是本发明中对于反向索引具体结构的举例。
31.图2是本发明中对于双重索引设计中的查询方式的举例。
具体实施方式
32.下面结合具体实施例对本发明进行详细说明。以下实施例将有助于本领域的技术人员进一步理解本发明，但不以任何形式限制本发明。应当指出的是，对本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变化和改进。这些都属于本发明的保护范围。
33.针对基于非易失性内存的文件系统下对目录层次深的小文件的快速索引需求，本发明的目的是提供一种针对基于非易失性内存的文件系统下的新型索引方法，其充分考虑非易失性内存的性能优势与特点，结合用户态系统对于目录层次深的小文件的快速索引需求，利用从文件路径末端文件名开始索引的反向索引，并与常规索引并行查询，避免了极端情况下反向索引性能低于常规索引，总体降低索引查询延迟，从而提升文件系统针对目录层次深的小文件的索引性能。
34.实施例1
35.根据本发明提供的一种针对基于非易失性内存的文件系统的新型索引方法，包括：同时进行反向索引和常规索引，通过多线程同时检索常规索引和反向索引直至找到对应文件以充分利用非易失性内存的性能优势；并行查询的好处在于在极端情况下，例如所查询文件在文件系统内有大量同名文件，反向索引的查询效率可能低于常规索引，在这种情况下可以保证新型索引方法的性能不低于传统索引(即仅常规索引)，从而充分利用非易失性内存的高性能以及低延迟访问特性的优势，加速对目录层次深的文件的索引。
36.所述反向索引以文件路径的末端文件名为起点反向遍历文件路径进行目录索引直至获得对应文件；即以文件路径最末端的文件名开始索引，并以逆序遍历文件路径直到找到对应文件。
37.所述常规索引由根目录开始，通过逐级目录名进行索引直至获得对应文件。
38.具体地，所述反向索引由多级索引构成，当文件系统使用文件路径进行反向索引时，首先使用路径最末端的文件名在第一级索引中进行检索，若第一级索引所得到的结果
包含多个文件，则再次通过路径中次末端的目录名在第二级索引中进行检索，以此类推，直至找到对应文件。该项设计的好处在于文件系统文件重名情况较少，可以快速缩小搜索文件的范围，而常规索引受制于文件系统层次结构无法快速定位文件，因此反向索引在通常情况下查询速度快于常规索引。
39.进一步地，所述反向索引中每级索引由哈希表构成，第一级索引使用末端文件名进行哈希搜索定位到哈希表项，若哈希表项仅对应一个文件，则指向文件反向索引节点，当前反向索引节点内存储文件的完整路径以及文件索引节点，完整路径用于与搜索路径进行完整匹配，文件索引节点指向文件实际位置；若哈希表项对应多个文件，则指向另一个哈希表作为下一级索引，通过文件名上一级的文件目录进行哈希搜索，以此类推。
40.具体地，所述通过多线程同时检索常规索引和反向索引直至找到对应文件采用：在同时查询常规索引和反向索引时，若任意索引返回查询结果(文件存在或不存在)，则直接将结果返回给用户而不需要等待另一索引的查询结果。即反向索引与常规索引同样包含文件系统的所有文件信息。
41.具体地，在进行文件系统目录操作(创建、删除文件等)时，在修改文件系统常规索引后需要同时修改反向索引，保证常规索引和反向索引包含相同的文件系统目录信息。
42.文件系统内同时存在常规索引与反向索引，在进行查询时，通过多线程同时对两个索引进行检索以降低查询的延迟，提高查询的性能。
43.根据本发明提供的一种针对基于非易失性内存的文件系统的新型索引系统，包括：同时进行反向索引和常规索引，通过多线程同时检索常规索引和反向索引直至找到对应文件以充分利用非易失性内存的性能优势；并行查询的好处在于在极端情况下，例如所查询文件在文件系统内有大量同名文件，反向索引的查询效率可能低于常规索引，在这种情况下可以保证新型索引方法的性能不低于传统索引(即仅常规索引)，从而充分利用非易失性内存的高性能优势，加速对目录层次深的文件的索引。
44.所述反向索引以文件路径的末端文件名为起点反向遍历文件路径进行目录索引直至获得对应文件；即以文件路径最末端的文件名开始索引，并以逆序遍历文件路径直到找到对应文件。
45.所述常规索引由根目录开始，通过逐级目录名进行索引直至获得对应文件。
46.具体地，所述反向索引由多级索引构成，当文件系统使用文件路径进行反向索引时，首先使用路径最末端的文件名在第一级索引中进行检索，若第一级索引所得到的结果包含多个文件，则再次通过路径中次末端的目录名在第二级索引中进行检索，以此类推，直至找到对应文件。该项设计的好处在于文件系统文件重名情况较少，可以快速缩小搜索文件的范围，而常规索引受制于文件系统层次结构无法快速定位文件，因此反向索引在通常情况下查询速度快于常规索引。
47.进一步地，所述反向索引中每级索引由哈希表构成，第一级索引使用末端文件名进行哈希搜索定位到哈希表项，若哈希表项仅对应一个文件，则指向文件反向索引节点，当前反向索引节点内存储文件的完整路径以及文件索引节点，完整路径用于与搜索路径进行完整匹配，文件索引节点指向文件实际位置；若哈希表项对应多个文件，则指向另一个哈希表作为下一级索引，通过文件名上一级的文件目录进行哈希搜索，以此类推。
48.具体地，所述通过多线程同时检索常规索引和反向索引直至找到对应文件采用：
在同时查询常规索引和反向索引时，若任意索引返回查询结果(文件存在或不存在)，则直接将结果返回给用户而不需要等待另一索引的查询结果。即反向索引与常规索引同样包含文件系统的所有文件信息。
49.具体地，在进行文件系统目录操作(创建、删除文件等)时，在修改文件系统常规索引后需要同时修改反向索引，保证常规索引和反向索引包含相同的文件系统目录信息。
50.文件系统内同时存在常规索引与反向索引，在进行查询时，通过多线程同时对两个索引进行检索以降低查询的延迟，提高查询的性能。
51.本发明所述的“内存”均指“非易失性内存”或称“持久内存”，即能够以内存接口进行访问、并能持久保存数据的内存。
52.实施例2
53.实施例2是实施例1的优选例
54.本发明针对基于非易失性内存的文件系统的新型索引包含以下两个方面，具体实施方法如下：
55.反向索引设计：反向索引由多级索引构成，当文件系统使用文件路径进行反向索引时，首先使用路径最末端的文件名在第一级索引中进行检索，若第一级索引所得到结果包含多个文件，则再次通过路径中次末端的目录名在第二级索引中进行检索，以此类推，直到找到对应文件。
56.反向索引中每级索引由哈希表构成，第一级索引使用末端文件名进行哈希搜索定位到哈希表项，若哈希表项仅对应一个文件，则指向文件反向索引节点，该节点内存储文件的完整路径以及文件索引节点，完整路径用于与搜索路径进行完整匹配，文件索引节点指向文件实际位置，若哈希表项对应多个文件(重名文件或哈希冲突)，则指向另一个哈希表作为下一级索引，通过文件名上一级的文件目录进行哈希搜索，依次类推。如图1所示，文件系统包含四个文件，文件路径分别为/a，/b/b，/c/b以及/d/b/b。由于文件系统中文件名为a的文件仅有一个，因此在第一级索引中文件名a对应的哈希项指向文件/a的反向索引节点，而由于文件名为b的文件有三个，因此在第一级索引中文件名b对应的哈希项指向了新的哈希表作为第二级索引。由于以/c/b结尾的文件仅有一个，因此在第二级索引中c所对应的哈希项指向文件/c/b的反向索引节点，而以/b/b结尾的文件有两个，因此在第二级索引中b所对应的哈希项仍然指向另一个哈希表作为第三级索引。
57.双重索引设计：文件系统常规索引由根目录开始，通过逐级目录名进行索引直到找到对应文件。新型索引同时包含反向索引与常规索引，在进行索引时通过多线程同时检索常规索引以及反向索引以充分利用非易失性内存的性能优势。如图2所示，在使用双重索引查询文件时，首先创建新线程使用常规索引查询文件，随后在当前线程内使用反向索引查询文件。具体地，使用反向索引查询文件包含以下步骤：
58.步骤1：定位第一级索引的哈希表，并以文件路径末端的文件名为哈希表的键。
59.步骤2：根据哈希键定位哈希表中对应的哈希项。
60.步骤3：若哈希项为空，则返回文件不存在结果。
61.步骤4：若哈希项指向下一级索引的哈希表，则将文件路径中上一级的目录名为哈希表的键，并返回步骤2。
62.步骤5：若哈希项指向反向索引节点，则比对反向索引节点中文件路径与查询文件
路径是否一致。
63.步骤6：若一致则返回反向索引节点中的文件索引节点所指向文件。
64.步骤7：若不一致则返回文件不存在结果。
65.若进行到任意一个步骤时常规索引线程已查询到结果，则直接返回查询到的结果(文件不存在或对应文件)。
66.综上所述，本发明提出的针对基于非易失性内存的文件系统的新型索引方法，充分考虑非易失性内存的性能优势与特点，结合用户态系统对于目录层次深的小文件的快速索引需求，利用从文件路径末端文件名开始索引的反向索引，并与常规索引并行查询，避免了极端情况下反向索引性能低于常规索引，总体降低索引查询延迟，从而提升文件系统针对目录层次深的小文件的索引性能。
67.本领域技术人员知道，除了以纯计算机可读程序代码方式实现本发明提供的系统、装置及其各个模块以外，完全可以通过将方法步骤进行逻辑编程来使得本发明提供的系统、装置及其各个模块以逻辑门、开关、专用集成电路、可编程逻辑控制器以及嵌入式微控制器等的形式来实现相同程序。所以，本发明提供的系统、装置及其各个模块可以被认为是一种硬件部件，而对其内包括的用于实现各种程序的模块也可以视为硬件部件内的结构；也可以将用于实现各种功能的模块视为既可以是实现方法的软件程序又可以是硬件部件内的结构。
68.以上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述特定实施方式，本领域技术人员可以在权利要求的范围内做出各种变化或修改，这并不影响本发明的实质内容。在不冲突的情况下，本技术的实施例和实施例中的特征可以任意相互组合。

技术特征：
1.一种针对基于非易失性内存的文件系统的新型索引方法，其特征在于，包括：同时进行反向索引和常规索引，通过多线程同时检索常规索引和反向索引直至找到对应文件；所述反向索引以文件路径的末端文件名为起点反向遍历文件路径进行目录索引直至获得对应文件；所述常规索引由根目录开始，通过逐级目录名进行索引直至获得对应文件。2.根据权利要求1所述的针对基于非易失性内存的文件系统的新型索引方法，其特征在于，所述反向索引包括多级索引，当文件系统使用文件路径进行反向索引时，首先使用路径最末端的文件名在第一级索引中进行检索，若第一级索引所得到的结果包含多个文件，则再次通过路径中次末端的目录名在第二级索引中进行检索，直至找到对应文件。3.根据权利要求2所述的针对基于非易失性内存的文件系统的新型索引方法，其特征在于，所述反向索引中每级索引由哈希表构成，第一级索引使用末端文件名进行哈希搜索定位到哈希表项，若哈希表项仅对应一个文件，则指向文件反向索引节点，当前反向索引节点内存储文件的完整路径以及文件索引节点，完整路径用于与搜索路径进行完整匹配，文件索引节点指向文件实际位置；若哈希表项对应多个文件，则指向另一个哈希表作为下一级索引，通过文件名上一级的文件目录进行哈希搜索，以此类推。4.根据权利要求1所述的针对基于非易失性内存的文件系统的新型索引方法，其特征在于，所述通过多线程同时检索常规索引和反向索引直至找到对应文件采用：在同时查询常规索引和反向索引时，若任一索引未查询到文件路径所对应文件，则直接返回当前文件不存在；若任一索引根据文件路径查询到对应文件，则直接返回当前文件。5.根据权利要求1所述的针对基于非易失性内存的文件系统的新型索引方法，其特征在于，在进行文件系统目录操作时，在修改文件系统常规索引时，需要同时修改反向索引，保证常规索引和反向索引包含相同的文件系统目录信息。6.一种针对基于非易失性内存的文件系统的新型索引系统，其特征在于，包括：同时进行反向索引和常规索引，通过多线程同时检索常规索引和反向索引直至找到对应文件；所述反向索引以文件路径的末端文件名为起点反向遍历文件路径进行目录索引直至获得对应文件；所述常规索引由根目录开始，通过逐级目录名进行索引直至获得对应文件。7.根据权利要求6所述的针对基于非易失性内存的文件系统的新型索引系统，其特征在于，所述反向索引包括多级索引，当文件系统使用文件路径进行反向索引时，首先使用路径最末端的文件名在第一级索引中进行检索，若第一级索引所得到的结果包含多个文件，则再次通过路径中次末端的目录名在第二级索引中进行检索，直至找到对应文件。8.根据权利要求7所述的针对基于非易失性内存的文件系统的新型索引系统，其特征在于，所述反向索引中每级索引由哈希表构成，第一级索引使用末端文件名进行哈希搜索定位到哈希表项，若哈希表项仅对应一个文件，则指向文件反向索引节点，当前反向索引节点内存储文件的完整路径以及文件索引节点，完整路径用于与搜索路径进行完整匹配，文件索引节点指向文件实际位置；若哈希表项对应多个文件，则指向另一个哈希表作为下一级索引，通过文件名上一级的文件目录进行哈希搜索，以此类推。9.根据权利要求6所述的针对基于非易失性内存的文件系统的新型索引系统，其特征在于，所述通过多线程同时检索常规索引和反向索引直至找到对应文件采用：在同时查询
常规索引和反向索引时，若任一索引未查询到文件路径所对应文件，则直接返回当前文件不存在；若任一索引根据文件路径查询到对应文件，则直接返回当前文件。10.根据权利要求6所述的针对基于非易失性内存的文件系统的新型索引系统，其特征在于，在进行文件系统目录操作时，在修改文件系统常规索引时，需要同时修改反向索引，保证常规索引和反向索引包含相同的文件系统目录信息。

技术总结
本发明提供了一种针对基于非易失性内存的文件系统的新型索引方法及系统，包括：同时进行反向索引和常规索引，通过多线程同时检索常规索引和反向索引直至找到对应文件；所述反向索引以文件路径的末端文件名为起点反向遍历文件路径进行目录索引直至获得对应文件；所述常规索引由根目录开始，通过逐级目录名进行索引直至获得对应文件。本发明在进行索引时通过多线程同时检索常规索引以及反向索引以充分利用非易失性内存的性能优势。分利用非易失性内存的性能优势。分利用非易失性内存的性能优势。


技术研发人员：蔡忠玮 董明凯 陈海波
受保护的技术使用者：上海交通大学
技术研发日：2022.03.14
技术公布日：2023/9/23