CN114816258A - Nvm的外部排序方法、装置和nvm存储器 - Google Patents

Abstract

本申请涉及一种NVM的外部排序方法、装置和计算机存储介质。方法包括：获取读取至内存的输入缓存中的小文件的有序区间，并且将输入缓存中的无序数据排序，得到第一有序中间结果，将第一有序中间结果写回NVM；小文件是对大数据文件进行切分得到的；获取有序区间在NVM上的位置信息，根据位置信息建立索引表，并且将索引表存储至内存；在进行数据归并时，根据败者树、索引表以及第一有序中间结果，进行数据归并。采用本方法能够解决传统外部归并排序的I/O负载问题，延长外存设备的使用寿命。

Description

NVM的外部排序方法、装置和NVM存储器

技术领域

本申请涉及新型非易失性存储技术领域，特别是涉及一种NVM的外部排序方法、装置和NVM存储器。

背景技术

新型非易失性存储技术的兴起和发展，新型非易失性存储器有着接近动态随机存取存储器(Dynamic Random Access Memory，DRAM)的读写性能，同时提供高密度，大容量的数据存储，而且又可以像机械硬盘(Hard Disk Drive，HDD)和固态硬盘(Solid StateDisk，SSD)一样具有非易失性，可以持久性保存数据。随着数据量爆炸式增长，高性能计算和数据库管理系统对新型非易失性存储的需求急剧增加。在数据库系统中，比较常见的场景是，原本有序的数据因为数据的局部更新导致数据乱序，如果每次局部更新数据后，都重新对全部数据进行排序，开销比较大。特别是在大规模数据量的情况下，执行外排序过程中内存和外存会频繁进行数据交换，产生大量I/O操作，影响算法性能和外存设备的使用寿命。NVM(Non-Volatile memory)有接近DRAM的读写速度，又像HDD和SSD一样可以持久化保存数据，Optane DC PMM是Intel公司推出的真实的NVM产品，Optane DC PMM是字节寻址的非易失存储器，可以充分利用Optane DC PMM的性能优势，设计和优化外排序算法，随着新型非易失性存储器的发展和兴起，基于NVM的外部排序方法研究也成为了当前的热点问题。

目前，NVM有着强大的功能，但也存在以下两个方面的问题。一是写操作的开销比读开销大，而且可随机访问，所以在算法设计过程中，可以增加额外的读操作，减少写操作；二是使用寿命有限，频繁的写入操作会影响NVM的使用寿命。

发明内容

基于此，有必要针对上述技术问题，提供一种能够解决外部排序的大量I/O负载问题的NVM的外部排序方法、装置和NVM存储器。

一种NVM的外部排序方法，所述方法包括：

获取读取至内存的输入缓存中的小文件的有序区间，并且将所述输入缓存中的无序数据排序，得到第一有序中间结果，将所述第一有序中间结果写回NVM；所述小文件是对大数据文件进行切分得到的；

获取所述有序区间在NVM上的位置信息，根据所述位置信息建立索引表，并且将所述索引表存储至内存；

在进行数据归并时，根据败者树、索引表以及所述第一有序中间结果，进行数据归并。

在其中一个实施例中，还包括：获取待检测的读取至内存的输入缓存中的小文件；遍历所述输入缓存中的数据，当连续有序数据的数目超过阈值时，得到所述小文件的有序区间。

在其中一个实施例中，还包括：当连续有序数据数目小于阈值时，将所述连续有序数据存储于内存的无序数据桶中。

在其中一个实施例中，还包括：当无序数据桶中的数据数目超过阈值时，对无序数据桶中的数据排序，得到有序数据的第二有序中间结果。

在其中一个实施例中，还包括：将所述第二有序中间结果写回NVM，记录所述第二有序中间结果重新写回NVM上的位置信息，并添加所述位置信息于索引表中。

在其中一个实施例中，还包括：将输入缓存中的无序数据存储在无序区间数组，当所述无序区间数组中的数据数量达到阈值时，对所述无序区间数组中的数据进行排序。

在其中一个实施例中，还包括：根据索引表查找有序区间在NVM上的位置信息；将所述有序区间和第一有序中间结果的头部读取至内存中，并作为败者树的叶子结点，得到所述头部中的最小值，将所述最小值写到输出缓存；依次迭代检索有序区间和第一有序中间结果剩余数据中的最小值，将检索结果写到输出缓存；输出缓存中的数据满后，将输出缓存中的数据写回NVM，在NVM中得到有序数据文件。

在其中一个实施例中，还包括：当有序区间的最大值小于另一有序区间的最小值时；合并所述两个有序区间，得到合并有序区间；根据合并有序区间的位置信息更新索引表。

一种NVM的外部排序装置，所述装置包括：

有序区间检索模块，用于获取读取至内存的输入缓存中的小文件的有序区间，并且将所述输入缓存中的无序数据排序，得到第一有序中间结果，将所述第一有序中间结果写回NVM；所述小文件是对大数据文件进行切分得到的；

索引表构建模块，用于获取所述有序区间在NVM上的位置信息，根据所述位置信息建立索引表，并且将所述索引表存储至内存；

数据归并模块，用于在进行数据归并时，根据败者树、索引表以及所述第一有序中间结果，进行数据归并。

一种NVM存储器，其上存储有计算机程序，所述计算机程序被处理器执行时实现以下步骤：

获取读取至内存的输入缓存中的小文件的有序区间，并且将所述输入缓存中的无序数据排序，得到第一有序中间结果，将所述第一有序中间结果写回NVM；所述小文件是对大数据文件进行切分得到的；

获取所述有序区间在NVM上的位置信息，根据所述位置信息建立索引表，并且将所述索引表存储至内存；

在进行数据归并时，根据败者树、索引表以及所述第一有序中间结果，进行数据归并。

上述NVM的外部排序方法、装置和NVM存储器，通过把大的输入文件切分为多个内存空间可容纳的小文件，依次把每个小文件读到内存的输入缓存中，检索小文件中的有序区间，对内存中的无序数据进行排序，并把排序后的数据写回外存设备NVM，写回外存设备的有序数据称为第一有序中间结果，记录有序区间在NVM上的位置信息于内存中的索引表中，根据败者树、索引表和第一有序中间结果，进行多次归并迭代，得到有序的输出文件。能够充分利用NVM的存储特质，重新设计外排序算法，减少对外存的写操作次数，加快外排序的执行，解决传统外部归并排序的I/O负载问题，延长外存设备的使用寿命。

附图说明

图1为一个实施例中NVM的外部排序方法的流程图；

图2为一个实施例中数据归并步骤的示意性流程图；

图3为一个实施例中RunMerge优化策略示意图；

图4为一个实施例中大规模数据下无序比例对NVMSort的性能影响示意图；

图5为另一个实施例中大规模数据下不同数据总量的NVMSort性能比较示意图；

图6为一个实施例中一种不同连续有序阈值对算法的性能影响示意图；

图7为一个实施例中NVM的外部排序装置的结构框图。

具体实施方式

为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。下文中为方便说明将一种基于NVM的外部排序方法称为NVMSort，下文中提到的测试是本发明基于Intel公司推出的真实的NVM产品Optane DC PMM上实现的。

在一个实施例中，如图1所示，提供了一种NVM的外部排序方法，包括以下步骤：

步骤102，获取读取至内存的输入缓存中的小文件的有序区间，并且将输入缓存中的无序数据排序，得到第一有序中间结果，将第一有序中间结果写回NVM。

小文件是对大数据文件进行切分得到的，小文件的大小不超过内存的大小，当输入数据文件比较大时，由于内存空间有限，无法一次性把所有数据读到内存中，需要把大数据文件切分为多个内存可容纳下的小文件；有序区间指的是升序排序的连续有序数据，头部为有序区间的最小值，尾部为有序区间的最大值，是大数据文件中原本有序的数据；无序数据指的是不按照升序规律排序的数据段，是大数据文件中原本无序的数据，无序的数据存放在内存中的无序区间数组中，当无序数组的数据量到达一个设定的阈值，便把该部分无序数据进行排序处理，得到第一有序中间结果，排序处理包括快速排序或其他内存排序算法，把第一有序中间结果写回NVM。第一有序中间结果将与有序数据一起进行归并，得到有序的大数据文件。

步骤104，获取有序区间在NVM上的位置信息，根据位置信息建立索引表，并且将索引表存储至内存。

索引表的主要作用是根据有序区间的起始偏移和结束偏移记录所有有序数据区间在外存文件中的起始位置和结束位置，便于归并阶段时读取数据，以ITable的形式表述索引表，ITable的作用是记录有序区间的位置索引信息，通过记录有序区间的位置信息，可以在数据归并阶段根据索引表信息，把相应的数据读取到内存中，进行归并比较。

步骤106，在进行数据归并时，根据败者树、索引表以及第一有序中间结果，进行数据归并。

数据归并主要采用败者树完成，败者树是一颗完全二叉树，败者树的查找效率比较高，可以在log(n)的时间复杂度内检索到最值，败者树相当于通过多轮的比赛，筛选出最终的胜利者，也就是数值中的最小值，在败者树中，把两个数中数值较大的定义为败者，数值较小的定义为胜者；根据索引表的位置索引信息，将有序区间相应的数据读取到内存的输入缓存中，与第一有序中间结果通过败者树排序，得到有序的大数据文件，因为NVM可以字节寻址，所以检测到的有序区间可以是变长的，归并阶段可以按照细粒度从NVM读到DRAM，读取数据的最小单位是4KB，因此可以减少读放大问题，而且在细粒度的数据读取中，采用NVMSort可以检测原数据中部分有序的区间，可以大大减少写回NVM的数据量，提高算法执行性能，加快外排序处理和响应时间。

上述NVM的外部排序方法中，把大的输入文件切分为多个内存空间可容纳的小文件，依次把每个小文件读到内存的输入缓存中，检索小文件中的有序区间，对内存中的无序数据进行排序，并把排序后的数据写回外存设备NVM，写回外存设备的有序数据称为第一有序中间结果，记录有序区间在NVM上的位置信息于内存中的索引表中，根据败者树、索引表和第一有序中间结果，进行多次归并迭代，得到有序的输出文件。本发明实施例，能够充分利用NVM的存储特质，重新设计外排序算法，减少对外存的写操作次数，加快外排序的执行，解决传统外部归并排序的I/O负载问题，延长外存设备的使用寿命。

在其中一个实施例中，获取读取至内存的输入缓存中的小文件的有序区间包括：获取待检测的读取至内存的输入缓存中的小文件；遍历输入缓存中的数据，当连续有序数据的数目超过阈值时，得到小文件的有序区间。

在本实施例中，数据数目超过阈值的有序区间不需要重新进行排序，也不需要重新写回外存设备，这样可以避免对有序数据的重新排序和写回外存，减少写回的数据量；如果检测到的有序区间数目比较多，在数据归并时，需要在内存中为每个有序区间预留输入缓存，这导致内存占用开销相对比较大，设置连续有序数据的有序阈值划分有序区间，可以减少有序区间的数目，从而减少归并阶段的输入缓存开销。因为DRAM空间有限，输入缓存需要为每个有序区间预留数据空间，用于参与数据归并，所以通过减少有序区间的数目，可以提高内存利用率，输入缓存可以为每个有序区间预留更大的空间，从而提高归并阶段的读写粒度，提高算法执行效率。

在其中一个实施例中，还包括：当连续有序数据数目小于阈值时，将连续有序数据存储于内存的无序数据桶中。在本实施例中，如果检测到的有序数据区间的总数目小于阈值，那么把该区间里的数据存储于内存的无序数据桶中，需要排序后再写回外存，无序数据桶用于存储数据数目低于阈值的有序区间，这一步骤主要是为了控制检索到有序区间的数目，应该尽可能记录长度较长的连续有序数据区间，而不是记录大量短的有序数据区间。

在其中一个实施例中，还包括：当无序数据桶中的数据数目超过阈值时，对无序数据桶中的数据排序，得到有序数据的第二有序中间结果。在本实施例中，阈值指的是对无序数据桶中数据数目的限定参数，无序数据桶中的数据即数据数目小于有序阈值的有序区间，属于大数据文件的部分有序数据，对无序数据桶中的数据排序能够减少长度较短的有序区间数量，可以减少归并数据时的输入缓存开销，生成的第二有序中间结果写回NVM上，重新写回的位置信息将被记录于索引表中，本实施例还能够减少索引表的内存开销，因为索引表的内存开销和有序区间数目成正比。

在其中一个实施例中，还包括：将第二有序中间结果写回NVM，记录第二有序中间结果重新写回NVM上的位置信息，并添加位置信息于索引表中。

在其中一个实施例中，还包括：将输入缓存中的无序数据存储在无序区间数组，当无序区间数组中的数据数量达到阈值时，对无序区间数组中的数据进行排序。在本实施例中，阈值指的是对无序区间数组中无序数据数量的限定参数，无序区间数组存储在内存中，对无序数组中无序数据排序后的结果是第一有序中间结果，将写回至NVM中。

在其中一个实施例中，在进行数据归并时，根据败者树、索引表以及有序中间结果，进行数据归并包括：根据索引表查找有序区间在NVM上的位置信息；将有序区间和第一有序中间结果的头部读取至内存中，并作为败者树的叶子结点，得到头部中的最小值，将最小值写到输出缓存；依次迭代检索有序区间和第一有序中间结果剩余数据中的最小值，将检索结果写到输出缓存；输出缓存中的数据满后，将输出缓存中的数据写回NVM，在NVM中得到有序数据文件。

在本实施例中，通过败者树对数据迭代检索最小值，得到有序数据文件，败者树的每个叶子结点记录一个数值，每个中间结点相当于一场比赛，比较中间结点的两个子节点的数值。败者树中每一层相当于一轮比赛，中间结点记录这场比赛中的败者，也就是数值较大的结点的下标，在败者树中，用父结点记录其左右子节点比赛的败者，也就是参与比较的两个数中更大的数值，而数值较小的数据，即胜利者继续参加下一轮比赛，败者树的根结点记录最后一轮比赛的较大值，还需要一个额外的结点，用来记录整场比赛的最小值，也是最终的胜利者。败者树的查找效率比较好，可以在log(n)时间复杂度内找到最值，所以，在更新叶子结点时，也可以在比较快的时间内重构败者树，维护树的结构。

在一个具体实施例中，如图2所示，提供一种数据归并步骤的示意性流程图，(5，7，8，10，12，15)和(6，9，10)为原本有序的数据区间，NVM中还存储着第一有序中间结果(12，12，18，20)和(7，8，10，10)。在图2中，将上述四组有序数据归并为一个有序数据文件，归并过程使用败者树来实现。依次把每组有序数据的头部，读到内存中并作为败者树的叶子结点，胜者记录在内部节点ls[·]中，第一批最小值为(12，7，5，6)，败者树的叶子结点两两比较，其中12比7大，12为败者，父节点记录败者的位置b1，7为胜者继续往上进行比较，6比5大，6为败者，父节点记录败者的位置b4，5为胜者继续往上比较。最后一轮比较中，7比5大，那么7为败者，5为最后的胜者，所以得到这一轮比较的最小值为5，把最小值写到输出缓存中，当输出缓存中的数据满后，将输出缓存中的数据写回NVM，每一轮比赛都可以检索到败者树中的最小值，添加下一个数值进来，继续调整败者树的结构，维持败者树的性质，继续迭代检索最小值，直到所有数据处理完毕，得到一个完整的有序数据文件。

在其中一个实施例中，还包括：当有序区间的最大值小于另一有序区间的最小值时；合并两个有序区间，得到合并有序区间；根据合并有序区间的位置信息更新索引表。

在本实施例中，提供了一种RunMerge的优化策略，可以用于步骤102中，把数值不交叉重叠的有序中间结果合并为一个有序区间，可以减少内存占用空间，记录合并后每个有序区间里面的若干个有序区间的起始偏移和结束偏移，从而更新索引表，逻辑上把多个不交叉重叠的有序区间合并成一个有序区间。如图3所示，以6个有序区间为例进行优化，run表示有序区间，ID表示有序区间的编号，其中run 2，run 3和run 6可以进行合并，因为run 2的最大值(Run_max)是43，小于run 3的最小值(Run_min)48，同时run 3的最大值是94，小于run 6的最小值200，根据RunMerge优化策略将这三个run合并为一个run，run 4和run 5合并为一个run，因为这两个有序区间的数值没有出现交错重叠的情况，初始的6个run，经过RunMerge优化后，合并为3个run，合并之后，需要更新索引表ITabel。

在一个具体实施例中，编程过程中采用了持久存储器开发套件(PMDK)，PMDK是一个不断增长的库和工具集合，这些库建立在操作系统的DAX功能上，允许应用程序将永久内存映射文件进行访问，实现中采用了PMDK的Libpmem库，Libpmem库是一个低层次持久化内存的库，调用pmem_map_file(·)函数，可以创建持久化内存文件，并将文件映射，得到指向文件的指针，如果地址是指向持久化内存的单一变量，调用pmem_persist(·)函数可以进行持久化操作，调用pmem_unmap(·)函数可以解除映射关系，由于DRAM内存有限，需要把大数据文件分成多个小文件，分批次从persistent memory中读取数据到DRAM中。

在本实施例中，首先遍历输入缓存中的数据，用一个数组存放读取进来的数据，记录开始遍历的位置和数值大小，如果相邻两个数值中，后面的数值不小于前面的数值，那么继续往后遍历，如果相邻两个数值中，后面的数值小于前面的数值，则停下来判断当前连续有序区间的长度是否超过阈值，如果连续有序区间的数据长度超过阈值，则记录这段有序区间的位置信息，并把位置信息添加到索引表中，如果该长度不超过阈值，则将这部分数据复制到无序数据桶中，每次检索到无序数据，则复制到无序区间数组unorderData中，给无序数据桶和unorderData设置固定的长度，当数据存满后，对存储的数据进行排序操作，并在Optane DC上创建新文件，得到第一有序中间结果和第二有序中间结果，记录第二有序中间结果的索引信息，包括最小值，位置偏移信息，在归并数据时，首先创建和初始化败者树，败者树本质上采用数组来实现，初始化败者树时需调整败者树的结构，在内存中为每个有序区间和第一有序中间结果预留数据缓存区，将每个有序数据段的头部读到缓存中，将缓存区的最小值添加到败者树里进行比较，每轮比较得到一个最小值，将最小值添加到输出缓存后，需要更新数据，并调整败者树的结构，维护败者树的特性，当输入缓存的数据处理完毕，继续从NVM上读取下一批数据进行比较，直到所有数据都处理完毕，得到一个完整的有序数据文件。

在另一个实施例中，如图4所示，提供一种大规模数据下无序比例对NVMSort的性能影响示意图，本发明测试了100GB数据在不同无序比例下的算法处理时间对比，传统的外部归并排序算法用Baseline表示，当100GB测试数据无序比例为1％时，Baseline算法需要花费266分钟，对100GB部分有序的数据进行排序大约需要4.43小时，NVMSort可以充分利用测试数据的局部有序分布特点，在无序比例为1％时，对100GB数据进行排序只需要花费18分钟。这是因为测试数据中无序数据占比为1％时，NVMSort通过检索测试数据中部分有序的区间，可以有效减少写回的数据总量，提高算法执行性能，特别是在更大规模的测试数据中，NVMSort可以体现出更明显的性能优势。

在其中一个实施例中，如图5所示，提供一种大规模数据下不同数据总量的NVMSort性能比较示意图，本发明主要测试在更大规模的数据集下两个算法的性能比较，传统的外部归并排序算法用Baseline表示，分别测试了10GB、50GB、100GB、150GB和180GB数据集，在无序数据占比为1％的情况下，NVMSort算法和传统外部归并排序算法的执行时间，可以看到，当测试数据大小为150GB时，Baseline算法需要花费6.63小时，但NVMSort算法只需要花费29分钟；当测试数据大小为180GB时，Baseline算法的执行时间为472分钟，即7.87小时，但是NVMSort算法只需要花费35分钟。在数据无序比例为1％的情况下，对于不同数据总量的大规模测试数据集NVMSort算法的性能都提升92％以上，NVMSort算法在大规模局部有序的数据中可以发挥更好的性能。100GB的测试数据原来是完全有序的，因为局部更新数据导致部分数据乱序，但是测试数据整体还是呈现局部有序的分布特点，在无序比例为1％的情况下，100GB测试数据中约有1GB的数据被随机更新，导致原数据变得乱序，NVMSort算法通过检索测试数据部分有序的区间，减少中间结果的生成，从而提高算法的执行效率，只需要花费18.4分钟可以使得100GB测试数据变为完全有序。

在其中一个实施例中，如图6所示，提供一种不同连续有序阈值对算法的性能影响示意图，连续有序阈值的设置是为了控制检索到有序区间的数目，应该尽可能记录长度较长的连续有序数据区间，而不是记录大量短的有序数据区间。连续有序阈值的大小对NVMSort的影响比较重要，本发明设置了实验对比NVMSort和传统外部归并排序的算法处理时间，包括读写文件的时间，传统的外部归并排序算法用Baseline表示，总测试数据量是100M部分有序的数据，数据无序比例设置为1％，分别设置连续有序阈值为2KB、4KB、6KB、8KB、12KB、14KB以及16KB，其他参数都设置一致。随着有序阈值的增加，NVMSort算法的处理时间逐渐增加，在有序阈值设置比较小的情况下，对有序区间的长度要求没那么严格，所以在有序区间检测阶段可以检测到比较多的连续有序数据区间，这样可以减少数据写回的操作数，但是同时也增加记录索引的内存消耗，不过记录索引内存开销占比较少；随着有序阈值增大，检测有序区间时，只记录比较长的超过阈值的连续有序区间，不会记录低于阈值的较短的有序区间，那么检测到的有序区间减少，有序数据数目减少，导致增加了NVMSort写回NVM的数据量，延长了算法的处理时间。

应该理解的是，虽然图1-2的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图1-2中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。

在一个实施例中，如图7所示，提供了一种NVM的外部排序装置，包括：有序区间检索模块702、索引表构建模块704和数据归并模块706，其中：

有序区间检索模块702，用于获取读取至内存的输入缓存中的小文件的有序区间，并且将输入缓存中的无序数据排序，得到第一有序中间结果，将第一有序中间结果写回NVM；小文件是对大数据文件进行切分得到的。

索引表构建模块704，用于获取有序区间在NVM上位置信息，根据位置信息建立索引表，并且将索引表存储至内存。

数据归并模块706，用于在进行数据归并时，根据败者树、索引表以及第一有序中间结果，进行数据归并。

在其中一个实施例中，有序区间检索模块702还用于获取待检测的读取至内存的输入缓存中的小文件；遍历输入缓存中的数据，当连续有序数据的数目超过阈值时，得到小文件的有序区间。

在其中一个实施例中，有序区间检索模块702还用于当连续有序数据数目小于阈值时，将连续有序数据存储于内存的无序数据桶中。

在其中一个实施例中，有序区间检索模块702还用于当无序数据桶中的数据数目超过阈值时，对无序数据桶中的数据排序，得到有序数据的第二有序中间结果。

在其中一个实施例中，有序区间检索模块702还用于在将输入缓存中的无序数据排序之前，将输入缓存中的无序数据存储在无序区间数组，当无序区间数组中的数据数量达到阈值时，对无序区间数组中的数据进行排序。

在其中一个实施例中，索引表构建模块704还用于将第二有序中间结果写回NVM，记录第二有序中间结果重新写回NVM上的位置信息，并添加位置信息于索引表中。

在其中一个实施例中，数据归并模块706还用于根据索引表查找有序区间在NVM上的位置信息；将有序区间和第一有序中间结果的头部读取至内存中，并作为败者树的叶子结点，得到头部中的最小值，将最小值写到输出缓存；依次迭代检索有序区间和第一有序中间结果剩余数据中的最小值，将检索结果写到输出缓存；输出缓存中的数据满后，将输出缓存中的数据写回NVM，在NVM中得到有序数据文件。

在其中一个实施例中，还用于当有序区间的最大值小于另一有序区间的最小值时；合并两个有序区间，得到合并有序区间；根据合并有序区间的位置信息更新索引表。

关于NVM的外部排序装置的具体限定可以参见上文中对于NVM的外部排序方法的限定，在此不再赘述。上述NVM的外部排序装置中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。

在一个实施例中，提供了一种NVM存储器，其上存储有计算机程序，计算机程序被处理器执行时实现上述实施例中方法的步骤。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所引用的NVM存储器这一非易失性存储器，可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。

以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。

Claims (10)

1.一种NVM的外部排序方法，其特征在于，所述方法包括：

获取读取至内存的输入缓存中的小文件的有序区间，并且将所述输入缓存中的无序数据排序，得到第一有序中间结果，将所述第一有序中间结果写回NVM；所述小文件是对大数据文件进行切分得到的；

获取所述有序区间在NVM上的位置信息，根据所述位置信息建立索引表，并且将所述索引表存储至内存；

在进行数据归并时，根据败者树、索引表以及所述第一有序中间结果，进行数据归并。

2.根据权利要求1所述的方法，其特征在于，所述获取读取至内存的输入缓存中的小文件的有序区间包括：

获取待检测的读取至内存的输入缓存中的小文件；

遍历所述输入缓存中的数据，当连续有序数据的数目超过阈值时，得到所述小文件的有序区间。

3.根据权利要求2所述的方法，其特征在于，所述方法还包括：

当连续有序数据数目小于阈值时，将所述连续有序数据存储于内存的无序数据桶中。

4.根据权利要求3所述的方法，其特征在于，所述方法还包括：

当无序数据桶中的数据数目超过阈值时，对无序数据桶中的数据排序，得到有序数据的第二有序中间结果。

5.根据权利要求4所述的方法，其特征在于，所述方法还包括：

将所述第二有序中间结果写回NVM，记录所述第二有序中间结果重新写回NVM上的位置信息，并添加所述位置信息于索引表中。

6.根据权利要求1至5任一项所述的方法，其特征在于，在将输入缓存中的无序数据排序之前，还包括：

将输入缓存中的无序数据存储在无序区间数组，当所述无序区间数组中的数据数量达到阈值时，对所述无序区间数组中的数据进行排序。

7.根据权利要求1所述的方法，其特征在于，所述在进行数据归并时，根据败者树、索引表以及所述有序中间结果，进行数据归并包括：

根据索引表查找有序区间在NVM上的位置信息；

将所述有序区间和第一有序中间结果的头部读取至内存中，并作为败者树的叶子结点，得到所述头部中的最小值，将所述最小值写到输出缓存；

依次迭代检索有序区间和第一有序中间结果剩余数据中的最小值，将检索结果写到输出缓存；

输出缓存中的数据满后，将输出缓存中的数据写回NVM，在NVM中得到有序数据文件。

8.根据权利要求1至5任一项所述的方法，其特征在于，所述方法还包括：

当有序区间的最大值小于另一有序区间的最小值时；合并所述两个有序区间，得到合并有序区间；

根据合并有序区间的位置信息更新索引表。

9.一种NVM的外部排序装置，其特征在于，所述装置包括：

有序区间检索模块，用于获取读取至内存的输入缓存中的小文件的有序区间，并且将所述输入缓存中的无序数据排序，得到第一有序中间结果，将所述第一有序中间结果写回NVM；所述小文件是对大数据文件进行切分得到的；

索引表构建模块，用于获取所述有序区间在NVM上的位置信息，根据所述位置信息建立索引表，并且将所述索引表存储至内存；

数据归并模块，用于在进行数据归并时，根据败者树、索引表以及所述第一有序中间结果，进行数据归并。

10.一种NVM存储器，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1-7中任一项所述的方法的步骤。

Images