CN104123304B - 数据驱动的并行排序系统和方法 - Google Patents

Abstract

本发明涉及数据驱动的并行排序系统和方法。提供了一种数据驱动的并行排序方法，包括：循环地将输入的数据记录逐个地分配给n（n>1）个分区，每个分区对应于所述并行排序中并行的一个排序处理并且分配有一个用于存储所分配的数据记录的内存块，所述内存块能够存储m（m>0）个数据记录；在各个分区中并行地对各自的内存块中的当前数据记录进行排序；响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，并清空该内存块；以及响应于所有数据记录完成分配，将各内存块中的已排序数据记录写入大容量存储器，并对大容量存储器中的所有有序数据块应用合并排序。

Description

数据驱动的并行排序系统和方法

技术领域

本发明涉及并行计算领域，更具体地说，本发明涉及一种数据驱动的并行排序系统和方法。

背景技术

并行排序算法是计算机并行计算能力大大发展之后，为了提高排序效率而提出的算法。并行排序是数据库、数据抽取转换装载（Extraction-Transformation-Loading，ETL）等领域中广泛使用的技术。并行排序算法是采用分治法（Divide and Conquer）的一个非常典型的应用，其原理是把待排序序列分为若干个子序列，使每个子序列有序，然后将已有序的子序列合并，得到完全有序的序列。

在并行排序中，数据被分配到多个分区中，每个分区对应于一个排序处理，该排序处理例如是一个进程或者线程。对于每个分区，排序处理对分配给该分区的数据进行排序，各个分区中的这种排序是并行进行的，然后对所有分区中的有序数据应用合并排序，从而完成了对所有数据的排序。所述合并排序可以是任何公知的合并排序算法，只要其能够实现把多个有序序列合并成一个有序序列即可。

并行排序现在常常应用于数据仓库中，例如可以对来自数据仓库中的多个数据库的输入的流式的数据进行排序。该输入的流式的数据由数据记录构成，可以依据数据记录中的特定字段对数据记录进行排序。在这种应用中，数据量往往非常大，没有办法在内存中一次容纳所有的数据记录以供排序。

图2是示出了一种现有技术的用于数据量大的情况的并行排序方法的流程图。首先，在数据分配步骤（210）中，连续输入的流式的数据被均匀地分配到多个分区中，每个分区分配有一个特定大小的内存块，该内存块用于存储所分配的数据，以便进行排序。所述数据分配是持续进行的，当数据来到时，就进行分配（除非被阻塞），并且该数据分配处理独立于与各个分区对应的排序处理。在分区内排序步骤（220）中，在每个分区内，通过与该分区对应的排序处理对自身的内存块中的数据进行排序，各个分区中的排序是并行进行的。在数据转储步骤（230）中，每当一个分区中的内存块已满并且该内存块中的数据已完成排序时，使得该内存块中的当前有序数据块被临时写入大容量存储器（例如，硬盘）中，并清空这个内存块。也就是说，在同一分区内，通过使用同一（此时已清空的）内存块继续处理接下来的输入数据，并且当排序完成时再将有序数据块临时写入硬盘。对于每个分区，循环地执行排序和转储，直至所有的数据被排序成有序数据块并被写入硬盘。在合并排序步骤（240）中，响应于所有数据记录完成分配，将各个内存块中的有序数据块写入硬盘，并对硬盘中的所有有序数据块应用合并排序。利用简单的合并排序算法，对所有分区的所有这些（在硬盘上的）有序数据块进行合并排序，将这些有序数据块合并在一起并使其中的数据保持有序，从而得到最终的有序序列。这是广泛使用的针对大数据量的并行排序方法，其中各个分区并行地执行步骤220和步骤230。

然而，采用这种技术，由于每个分区中的排序处理都几乎在同时竞争CPU资源，从而会导致CPU的利用率大幅波动并且使整体吞吐量降低。

图3是示出了利用现有技术的并行排序方法时的CPU利用率的示意图。从图3中可见，CPU的利用率的波动很大，在波峰处CPU利用率接近或达到100%，这使得处理效率降低，而在波谷时CPU利用率低于20%，这造成了处理能力的浪费。造成这种现象的根本原因在于数据分配器采用轮询方式将数据均匀地分配给各个分区。在一轮分配中，向每个分区分配一个数据记录。每个分区接收分配给自己的输入数据。由于一轮分配可能在非常短的时间内完成（几乎同时），这使得各个分区的排序处理几乎在同时处理这个新输入的数据记录，并且还使得每个分区几乎同时需要把有序数据块写入硬盘。也就是说，当各个分区基于新分配给自己的数据记录的驱动而对内存块中的所有数据记录进行排序时，各个分区将同时竞争使用CPU资源，这就造成了图3中的波峰的出现。另外，由于以上原因，当各个分区内的排序完成时，为了把有序数据块写入硬盘，各个分区还会同时竞争输入输出（IO）资源，同样会造成等待和延迟。这使得系统资源的使用效率低下。

已经发现，通常，当内存块的大小较小时，并行排序的系统利用效率的低下就不那么明显。减小内存块的大小会缓解上述问题，但是具有另外的明显缺陷。当数据量非常大时，小的内存块是无益的，因为这将导致在硬盘上产生过多的数据块，从而使得合并排序处理把所有这些数据块合并在一起变得非常慢，最终这将使整个排序过程变得非常慢。因此，减小内存块的大小无法解决上述问题。

发明内容

基于以上的描述，希望提供一种能够优化系统资源（CPU资源和输入输出资源）的利用率的数据驱动的并行排序系统和方法。

根据本发明的一个方面，提供了一种数据驱动的并行排序方法，该方法包括：循环地将输入的数据记录逐个地分配给n个分区，每个分区对应于所述并行排序中并行的一个排序处理并且分配有一个用于存储所分配的数据记录的内存块，所述内存块能够存储m个数据记录，其中n是大于1的整数且m是正整数；在各个分区中并行地对各自的内存块中的当前数据记录进行排序；响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，并清空该内存块，其中表示m/n的商向下取整；以及响应于所有数据记录完成分配，将各内存块中的已排序数据记录写入大容量存储器，并对大容量存储器中的所有有序数据块应用合并排序。

根据本发明的另一个方面，提供了一种数据驱动的并行排序系统，该系统包括：数据分配装置，被配置为循环地将输入的数据记录逐个地分配给n个分区，每个分区对应于所述并行排序中并行的一个排序处理并且分配有一个用于存储所分配的数据记录的内存块，所述内存块能够存储m个数据记录，其中n是大于1的整数且m是正整数；分区内排序装置，被配置为在各个分区中并行地对各自的内存块中的当前数据记录进行排序；受控数据转储装置，被配置为响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，并清空该内存块，其中表示m/n的商向下取整；以及合并排序装置，被配置为响应于所有数据记录完成分配，将各内存块中的已排序数据记录写入大容量存储器，并对大容量存储器中的所有有序数据块应用合并排序。

本发明通过分别控制各个分区使它们分别在计算出的定时（即使内存块并未满）把自身的内存块中的已排序数据块写入到大容量存储器中，在把不同分区的内存块中的数据块写入硬盘的定时之间以及在CPU计算强度大的时间之间产生了时间差，从而避免了各分区对各种系统资源的集中竞争，从而能够优化系统资源的利用率，以提高并行排序的性能。

附图说明

通过结合附图对本公开示例性实施方式进行更详细的描述，本公开的上述以及其它目的、特征和优势将变得更加明显，其中，在本公开示例性实施方式中，相同的参考标号通常代表相同部件。

图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12的框图。

图2是示出了一种现有技术的用于数据量大的情况的并行排序方法的流程图。

图3是示出了利用现有技术的并行排序方法时的CPU利用率的示意图。

图4是示出了根据本发明的一个实施例的数据驱动的并行排序方法的流程图。

图5是示出了反映根据本发明的一个实施例的数据驱动的并行排序方法的原理的示意图。

图6示出了根据本发明的一个实施例的数据驱动的并行排序系统的方框图。

图7和图8是示出了现有技术的并行排序对于CPU的使用情况的示意图、以及根据本发明的实施例的并行排序对于减少CPU竞争的效果的示意图。

具体实施方式

在图3中所使用的现有技术的并行排序方法中，一个数据记录一被分配到分区中，该分区就对该数据记录和该分区的内存块中已排序的其它数据记录（如果有的话）进行重新排序，并且一旦一个分区的内存块变满，就把该内存块中的数据块写入硬盘。因此，该并行排序方法是一种数据驱动的方法。

本发明的发明人发现，造成系统资源利用率降低主要是由于以下两个原因：

1、各个分区对CPU资源的使用需求的峰值几乎同时出现，该峰值出现在内存块中数据量超过某个阈值直至内存块变满时（因为内存块中的数据越多，排序处理需要进行比较的次数更多，对CPU资源的使用也就越多）。

2、由于轮询式的数据分配，各个分区的内存块会几乎同时变满，需要几乎同时地将内存块中的数据块写入硬盘中，这就造成了对输入输出资源的集中竞争。

基于以上两点观察，为了解决以上技术问题，本发明的发明人发现，需要在把不同分区的内存块中的数据块写入硬盘的定时之间产生时间差。

下面将参照附图更详细地描述本公开的优选实施方式。虽然附图中显示了本公开的优选实施方式，然而应该理解，可以以各种形式实现本公开而不应被这里阐述的实施方式所限制。相反，提供这些实施方式是为了使本公开更加透彻和完整，并且能够将本公开的范围完整地传达给本领域的技术人员。

所属技术领域的技术人员知道，本发明可以实现为系统、方法或计算机程序产品。因此，本公开可以具体实现为以下形式，即：可以是完全的硬件、也可以是完全的软件（包括固件、驻留软件、微代码等），还可以是硬件和软件结合的形式，本文一般称为“电路”、“模块”或“系统”。此外，在一些实施例中，本发明还可以实现为在一个或多个计算机可读介质中的计算机程序产品的形式，该计算机可读介质中包含计算机可读的程序代码。

可以采用一个或多个计算机可读的介质的任意组合。计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质。计算机可读存储介质例如可以是——但不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可读存储介质的更具体的例子（非穷举的列表）包括：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机存取存储器（RAM）、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑磁盘只读存储器(CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。在本文件中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。

计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括——但不限于——电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。

计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括——但不限于——无线、电线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言或其组合来编写用于执行本发明操作的计算机程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如Java、Smalltalk、C++，还包括常规的过程式程序设计语言—诸如”C”语言或类似的程序设计语言。程序代码可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机（例如利用因特网服务提供商来通过因特网连接）。

下面将参照本发明实施例的方法、装置（系统）和计算机程序产品的流程图和/或框图描述本发明。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机程序指令实现。这些计算机程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，这些计算机程序指令通过计算机或其它可编程数据处理装置执行，产生了实现流程图和/或框图中的方框中规定的功能/操作的装置。

也可以把这些计算机程序指令存储在能使得计算机或其它可编程数据处理装置以特定方式工作的计算机可读介质中，这样，存储在计算机可读介质中的指令就产生出一个包括实现流程图和/或框图中的方框中规定的功能/操作的指令装置(instructionmeans)的制造品（manufacture）。

也可以把计算机程序指令加载到计算机、其它可编程数据处理装置、或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机或其它可编程装置上执行的指令能够提供实现流程图和/或框图中的方框中规定的功能/操作的过程。

图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12的框图。图1显示的计算机系统/服务器12仅仅是一个示例，不应对本发明实施例的功能和使用范围带来任何限制。

如图1所示，计算机系统/服务器12以通用计算设备的形式表现。计算机系统/服务器12的组件可以包括但不限于：一个或者多个处理器或者处理单元16，系统存储器28，连接不同系统组件（包括系统存储器28和处理单元16）的总线18。

总线18表示几类总线结构中的一种或多种，包括存储器总线或者存储器控制器，外围总线，图形加速端口，处理器或者使用多种总线结构中的任意总线结构的局域总线。举例来说，这些体系结构包括但不限于工业标准体系结构（ISA）总线，微通道体系结构（MAC）总线，增强型ISA总线、视频电子标准协会（VESA）局域总线以及外围组件互连（PCI）总线。

计算机系统/服务器12典型地包括多种计算机系统可读介质。这些介质可以是任何能够被计算机系统/服务器12访问的可用介质，包括易失性和非易失性介质，可移动的和不可移动的介质。

系统存储器28可以包括易失性存储器形式的计算机系统可读介质，例如随机存取存储器（RAM）30和/或高速缓存存储器32。计算机系统/服务器12可以进一步包括其它可移动/不可移动的、易失性/非易失性计算机系统存储介质。仅作为举例，存储系统34可以用于读写不可移动的、非易失性磁介质（图1未显示，通常称为“硬盘驱动器”）。尽管图1中未示出，可以提供用于对可移动非易失性磁盘（例如“软盘”）读写的磁盘驱动器，以及对可移动非易失性光盘（例如CD-ROM,DVD-ROM或者其它光介质）读写的光盘驱动器。在这些情况下，每个驱动器可以通过一个或者多个数据介质接口与总线18相连。存储器28可以包括至少一个程序产品，该程序产品具有一组（例如至少一个）程序模块，这些程序模块被配置以执行本发明各实施例的功能。

具有一组（至少一个）程序模块42的程序/实用工具40，可以存储在例如存储器28中，这样的程序模块42包括——但不限于——操作系统、一个或者多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。程序模块42通常执行本发明所描述的实施例中的功能和/或方法。

计算机系统/服务器12也可以与一个或多个外部设备14（例如键盘、指向设备、显示器24等）通信，还可与一个或者多个使得用户能与该计算机系统/服务器12交互的设备通信，和/或与使得该计算机系统/服务器12能与一个或多个其它计算设备进行通信的任何设备（例如网卡，调制解调器等等）通信。这种通信可以通过输入/输出（I/O）接口22进行。并且，计算机系统/服务器12还可以通过网络适配器20与一个或者多个网络（例如局域网（LAN），广域网（WAN）和/或公共网络，例如因特网）通信。如图所示，网络适配器20通过总线18与计算机系统/服务器12的其它模块通信。应当明白，尽管图中未示出，可以结合计算机系统/服务器12使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、RAID系统、磁带驱动器以及数据备份存储系统等。

现在参看图4，图4是示出了根据本发明的一个实施例的数据驱动的并行排序方法的流程图。根据本发明的实施例的数据数据驱动的并行排序方法例如可应用于数据仓库的数据采集。在这种应用中，输入的数据记录是流式数据，即，数据记录的流。图4中的流程图中的处理包括如下步骤：数据分配步骤410、分区内排序步骤420、受控数据转储步骤430、以及合并排序步骤440。

下面，将详细描述图4中的本发明的数据驱动的并行排序方法中的各个步骤。

在数据分配步骤410中，使用轮询法（round robin），循环地将输入的数据记录逐个地分配给这n分区（假定存在n个分区，n是大于1的整数），每个分区对应于并行排序中并行的一个排序处理并且分配有一个用于存储所分配的数据记录的内存块，所述内存块能够存储m个数据记录（m是正整数）。在一个应用于数据采集的实施例中，m可以达到百万的数量级。

在这里，轮询法指的是循环地将到来的数据记录依次地逐个地分配给n个分区。例如，将（按到来的次序的）第1至第n个数据记录分别分配给第1至第n个分区，然后再循环地将接下来的第n+1至第2n个数据记录（按到来的次序）分别分配给第1至第n个分区，依此类推。

所述排序处理例如是一个进程或者线程，与分区的数量相等的（即n个）排序处理能够并行执行。在一个实施例中，与各个分区对应的排序处理中的至少两个竞争同一处理器资源，从而使用本发明的并行排序方法能够减少对CPU资源的竞争。在另一个实施例中，与各个分区对应的排序处理被分配在不同的处理器或处理器核上执行，从而不存在对CPU的竞争关系，但是在这种情况下，本发明的并行排序方法仍然能够有效地减少对输入输出资源的竞争强度，这将在稍后描述。

所述数据分配是持续进行的，当数据来到时，就进行分配（除非被阻塞），并且该数据分配独立于与各个分区对应的排序处理。

图5是示出了反映根据本发明的一个实施例的数据驱动的并行排序方法的原理的示意图。图5仅仅给出了本发明的数据驱动的并行排序方法的一个示例性实施例，给出图5中的示例是为了便于理解本发明的原理，该示例不应被解释为对本发明的保护范围的限制。在图5中，给出了n个分区，每个分区分配有一个特定大小的内存块，并且每个分区具有一个对应的排序处理器，每个排序处理器是由一个进程或者线程实现的。作为示例，图5中仅仅示出了第1、2、i、n个分区，其余分区用分区间的横向虚线表示。当然，本发明同样适用于仅有2或3个分区的情况。

图5中的分配器是一个单独的进程或线程，专门用于处理把到来的数据分配给n个分区，并且可以向图5中的排序处理器和/或转储发起器发送信号。根据步骤410的操作，图5中的分配器将到来的数据记录按轮询方式逐个地分配给各个分区并存储在相应的内存块中。

在分区内排序步骤420中，在各个分区中并行地对各自的内存块中的当前数据记录进行排序。所述排序可以采用各种已知的排序算法，例如，起泡排序、快速排序、二分法排序等等。再次参照图5，图5中示出的排序处理器1-n（仅例示了排序处理器1、2、i和n，其它的排序处理器被省略）分别对各自的分区中的内存块中的输入的数据记录进行排序。

如上所述，由于数据分配可以在非常短的时间内完成，与数据分配花费的时间相比，各个分区需要长得多的时间进行分区内排序。而由于各分区的分区内排序几乎同时进行，产生了系统资源过度竞争的问题。本发明的发明人因此对现有技术的数据转储步骤进行了如下的改进。

在受控数据转储步骤430中，响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，并清空该内存块，其中表示m/n的商向下取整。这里，所述数据转储指的是把内存块中的数据块（已排序）写入到大容量存储器中并且清空该内容块，所述大容量存储器是诸如磁盘或固态硬盘的存储器。在一轮分配中，向每个分区分配一个数据记录。由于每当分配了轮的数据记录时，就控制n个分区中的一个分区使之执行数据转储，对于所述n个分区，使得首次写入大容量存储器的有序数据块的大小不等，从而使各个分区对系统资源的竞争产生了时间差。

例如，参照图5所见，图5中的每个分区中省略地示出了数据块1、2、…、j、…，这些数据块是进行分区内排序之后被从内存块转储到例如硬盘的有序数据块。其中，由于进行了根据本发明的控制，各个分区中的被转储的第一个数据块的大小不等，但是各个分区中的从第二个数据块起的数据块的大小相等且包含m个数据记录。另外，需要注意的是，各个分区的最后一个数据块（未示出）的大小也很可能不等，这是因为一般不会发生在最后一轮正好把所有内存块充满，对于现有技术中的图2中的并行排序处理也是如此。

在一个实施例中，设定i为分区的编号，1≤i≤n，对于第1个至第n-1个分区，首次写入大容量存储器的有序数据块的大小小于m个数据记录，例如图5中的第1、2、i分区中的数据块1所示（尽管图5只示出了四个分区（1、2、i、n）的情况，第1至n-1分区中的数据块1的大小均小于m）。另外，对于第n个分区，首次写入大容量存储器的有序数据块的大小小于或等于m个数据记录。即，当m/n能够整除时，第n个分区中的数据块1的大小是m个数据记录；当m/n不能够整除时，第n个分区中的数据块1的大小小于m个数据记录。

在一个实施例中，设定i为分区的编号，1≤i≤n，并且，响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区包括：响应于分配了第*k轮的数据记录，控制第i=(k mod n)分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，其中k是正整数，并且(k mod n)表示k模n后的余数。在这里，可以把k看作一个计数器，该计数器被初始值化为0（要注意的是该初始化值并无意义），每当分配了轮的数据记录时，使该计数器的值加1。把该计数器的值模n后得到的余数即为要进行控制的分区的编号。

在一个实施例中，上述计数器可以实现于图5中所示的转储发起器中。在此情况下，每当分配了轮的数据记录时，分配器向图5中的转储发起器发送一个信号，响应于该信号，转储发起器使所述计数器加1，并根据所述计数器的值计算的i=（k mod n）来发起相应的分区i中的数据转储（参见图5中的转储发起器与各分区之间的横向双向箭头）。具体地，在一个实施例中，转储发起器可以针对该分区启动一个写入进程或线程，把该分区的内存块中的已排序的数据块的当前快照写入到例如硬盘，并清空该内存块。在另一个实施例中，转储发起器不必启动专门的写入进程或线程，而是可以通知相应的排序处理器，从而由该排序处理器响应于该通知而自己调用写入指令来完成数据转储。

在一个实施例中，上述计数器可以实现于图5所述中的分配器中。在此情况下，每当分配了轮的数据记录时，分配器使所述计数器加1并根据所述计数器的值计算的i=（k mod n）向相应的排序处理器i发送一个信号。响应于接收到直接来自分配器的该信号，该相应的排序处理器启动专门的写入进程或线程或者调用写入指令来完成数据转储。

在引入了上述的值k的情况下，当k小于或等于n时，写入大容量存储器的有序数据块的大小为*k个数据记录。另一方面，当k大于n并且输入的数据记录充足（即，不是第一个也不是最后一个数据块）时，写入大容量存储器的有序数据块的大小为m个数据记录。

如上所述，可以采用各种方式来实现本发明的发明构思，本发明并不局限于图5中所示的特定结构。

以下给出一个简单的例子来详细说明本发明的并行排序。假定n=4（即，存在4个分区）并且m=16（即，每个分区中的内存块能够存储16个数据记录）。需要注意的是，以上仅仅是为了易于理解而给出的一个简单例子，在现实中，分区的数目可以达到64个以上，而内存块的大小能够存储数百万个数据记录。在n=4且m=16的情况下，。也就是说，每当分配了4轮（即，16个）的数据记录时，循环地控制这4个分区中的一个分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，并清空该内存块。

参考图5中的例子，当k=1（即，分配了4轮的数据记录）时，对分区1（(k mod4)=1）执行数据转储，此时分区1的内存块中仅具有4个已排序数据记录（即1/4满），这样，分区1中的大小为m*1/4的数据块1被写入例如硬盘并且分区1的内存块被清空。

当k=2（即，分配了8轮的数据记录）时，对分区2（(k mod4)=2）执行数据转储，此时分区2的内存块中仅具有8个已排序数据记录（即1/2满），这样，分区2中的大小为m*1/2的数据块1被写入例如硬盘并且分区2的内存块被清空。

当k=3（即，分配了12轮的数据记录）时，对分区3（(k mod4)=3）执行数据转储，此时分区3的内存块中仅具有12个已排序数据记录（即3/4满），这样，分区3中的大小为m*3/4的数据块1被写入例如硬盘并且分区3的内存块被清空。

当k=4（即，分配了16轮的数据记录）时，对分区4（(k mod4)=4）执行数据转储，此时分区4的内存块中具有16个已排序数据记录（即全满），这样，分区4中的大小为m的数据块1被写入例如硬盘并且分区4的内存块被清空。

当k=5（即，分配了20轮的数据记录）时，再次对分区1（(k mod4)=1）执行数据转储，此时分区1的内存块中具有16个已排序数据记录（此时，在第4轮数据分配后清空分区1的内存块后又经过了16轮，使得该内存块变满），这样，分区1中的大小为m的数据块2被写入例如硬盘并且分区1的内存块被清空。

受控数据转储步骤430如上所述地执行并且后续的步骤依此类推。需要注意的是，图5中的纵向箭头代表数据块之间的顺序关系，实线箭头代表相邻，虚线箭头代表在数据块之间存在省略的其它数据块。

下面返回参照图4，在合并排序步骤440中，与图2中的合并排序步骤240类似地，响应于所有数据记录完成分配，将各内存块中的已排序数据记录写入大容量存储器，并对大容量存储器中的所有有序数据块应用合并排序。利用简单的合并排序算法，对所有分区的所有这些（在硬盘上的）有序数据块进行合并排序，将这些有序数据块合并在一起并使其中的数据保持有序，从而得到最终的有序序列（参见图5的下部）。

在一个实施例中，响应于从分配器接收到数据分配完成的信号，转储发起器启动写入进程或线程将各个内存块中的数据块（已排序）写入例如硬盘。在另一个实施例中，分配器直接通知各个排序处理器数据分配已完成，从而由各个排序处理器各自启动写入进程或线程或者调用写入指令来把数据块写入例如硬盘。

在另一个实施例中，当接收到数据分配完成的信号时，对各个分区中的内存块中的当前数据块（即，最后一个数据块）不进行转储，而是直接开始所有有序数据块（包括硬盘中的数据块和内存块中的数据块）的合并排序。这样做，可以避免最后一个数据块写入硬盘后又需要从硬盘取回的冗余的输入输出操作。

本发明通过分别控制各个分区使它们分别在计算出的定时（即使内存块并未满）把自身的内存块中的已排序数据块写入到大容量存储器中，在把不同分区的内存块中的数据块写入硬盘的定时之间以及在CPU计算强度大的时间之间产生了时间差，从而避免了各分区对各种系统资源的集中竞争，从而能够优化系统资源的利用率，以提高并行排序的性能。

图6是示出了根据本发明的实施例的数据驱动的并行排序系统的方框图。图6中的并行排序系统600包括数据分配装置610、分区内排序装置620、受控数据转储装置630以及合并排序装置640。数据分配装置610被配置为循环地将输入的数据记录逐个地分配给n个分区，每个分区对应于所述并行排序中并行的一个排序处理并且分配有一个用于存储所分配的数据记录的内存块，所述内存块能够存储m个数据记录，其中n是大于1的整数且m是正整数。分区内排序装置620被配置为在各个分区中并行地对各自的内存块中的当前数据记录进行排序。受控数据转储装置630被配置为，响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，并清空该内存块，其中表示m/n的商向下取整。合并排序装置640被配置为响应于所有数据记录完成分配，将各内存块中的已排序数据记录写入大容量存储器，并对大容量存储器中的所有有序数据块应用合并排序。

图7和图8是示出了现有技术的并行排序对于CPU的使用情况的示意图、以及根据本发明的实施例的并行排序对于减少CPU竞争的效果的示意图。图7的上部示出了一个分区的排序处理对于CPU的使用情况。在现有技术中，当存在两个分区时，这两个分区的排序处理对于CPU的使用是相似的，例如都如图7的上部所示。这样，这两个分区的排序处理对CPU的利用率产生了如图8的上部所示的叠加情况，即，峰部与峰部重叠且谷部与谷部重叠。与之相对，采用本发明的并行排序，当存在两个分区时，使这两个分区对于CPU使用率高的时段之间产生时间差。例如，图7的上部表示分区1的排序处理对CPU的使用情况，而图7的下部表示分区2的排序处理对CPU的使用情况。图8的下部表示采用本发明的合并排序后这两个分区的排序处理对CPU的利用率产生了的叠加情况。如图可见，与图8的上部相比，CPU不存在利用率接近100%的情况，实现了削峰平谷的作用，从而提高了CPU的响应速度，优化了CPU资源的利用率。

另外，与图7和图8所示的例子类似，在来自各个分区的有序数据块的所述写入竞争同一输入输出资源的情况下，对输入输出资源的集中竞争也因为时间差的引入而被避免，从而也优化了输入输出资源的利用率。另外，即使在多处理器的情况下，例如4处理器的情况下，如果分区的数目超过处理器的数目，那么仍然存在多个分区的排序处理竞争同一个处理器资源的情况。在这种情况下，本发明仍然可以适用以避免处理器的集中竞争。此外，即使分区的数目小于等于处理器的数目，但系统中存在其他形式的CPU资源占用（比如有其它程序正在运行），系统依然有可能将多个分区的排序处理任务调度为竞争同一个处理器资源。在这种情况下，本发明仍然可以适用以减少处理器的集中竞争。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

以上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。

Claims (14)

1.一种数据驱动的并行排序方法，该方法包括：

循环地将输入的数据记录逐个地分配给n个分区，每个分区对应于所述并行排序中并行的一个排序处理并且分配有一个用于存储所分配的数据记录的内存块，所述内存块能够存储m个数据记录，其中n是大于1的整数且m是正整数；

在各个分区中并行地对各自的内存块中的当前数据记录进行排序；

响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区，在计算出的定时里，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，并清空该内存块，其中表示m/n的商向下取整，其中所述计算出的定时使得在所述该分区的内存块中的已排序数据记录写入大容量存储器的时间以及在一个或多个处理器处理至少一个并行的所述排序处理的CPU计算强度大的时间之间产生了时间差；以及

响应于所有数据记录完成分配，将各内存块中的已排序数据记录写入大容量存储器，并对大容量存储器中的所有有序数据块应用合并排序，

其中，设定i为分区的编号，1≤i≤n，并且

其中，响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区包括：响应于分配了第轮的数据记录，控制第i＝(k mod n)分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，其中k是正整数，并且(k modn)表示k模n后的余数。

2.根据权利要求1所述的方法，其中，输入的数据记录是流式数据。

3.根据权利要求1所述的方法，其中，

对于第1个至第n-1个分区，首次写入大容量存储器的有序数据块的大小小于m个数据记录；并且

对于第n个分区，首次写入大容量存储器的有序数据块的大小小于或等于m个数据记录。

4.根据权利要求1所述的方法，其中，当k小于或等于n时，写入大容量存储器的有序数据块的大小为个数据记录。

5.根据权利要求1所述的方法，其中，不把各个分区中的最后一个有序数据块写入大容量存储器。

6.根据权利要求1所述的方法，其中，与各个分区对应的排序处理中的至少两个竞争同一处理器资源。

7.根据权利要求1所述的方法，其中，来自各个分区的有序数据块的所述写入竞争同一输入输出资源。

8.一种数据驱动的并行排序系统，该系统包括：

数据分配装置，被配置为循环地将输入的数据记录逐个地分配给n个分区，每个分区对应于所述并行排序中并行的一个排序处理并且分配有一个用于存储所分配的数据记录的内存块，所述内存块能够存储m个数据记录，其中n是大于1的整数且m是正整数；

分区内排序装置，被配置为在各个分区中并行地对各自的内存块中的当前数据记录进行排序；

受控数据转储装置，被配置为响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区，在计算出的定时里，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，并清空该内存块，其中表示m/n的商向下取整，其中所述计算出的定时使得在所述将该分区的内存块中的已排序数据记录写入大容量存储器的时间以及在一个或多个处理器处理至少一个并行的所述排序处理的CPU计算强度大的时间之间产生了时间差；以及

合并排序装置，被配置为响应于所有数据记录完成分配，将各内存块中的已排序数据记录写入大容量存储器，并对大容量存储器中的所有有序数据块应用合并排序，

其中，设定i为分区的编号，1≤i≤n，并且

其中，响应于分配了轮的数据记录，循环地控制所述n个分区中的一个分区包括：响应于分配了第轮的数据记录，控制第i＝(k mod n)分区，将该分区的内存块中的已排序数据记录写入大容量存储器作为有序数据块，其中k是正整数，并且(k modn)表示k模n后的余数。

9.根据权利要求8所述的系统，其中，输入的数据记录是流式数据。

10.根据权利要求8所述的系统，其中，

对于第1个至第n-1个分区，首次写入大容量存储器的有序数据块的大小小于m个数据记录；并且

对于第n个分区，首次写入大容量存储器的有序数据块的大小小于或等于m个数据记录。

11.根据权利要求8所述的系统，其中，当k小于或等于n时，写入大容量存储器的有序数据块的大小为个数据记录。

12.根据权利要求8所述的系统，其中，不把各个分区中的最后一个有序数据块写入大容量存储器。

13.根据权利要求8所述的系统，其中，与各个分区对应的排序处理中的至少两个竞争同一处理器资源。

14.根据权利要求8所述的系统，其中，来自各个分区的有序数据块的所述写入竞争同一输入输出资源。