一种在固态硬盘上进行海量数据并行扫描的调度方法

摘要

本发明公开了一种在固态硬盘上进行海量数据并行扫描的调度方法。在查询开始时估算其扫描速度，根据速度相近的匹配原则为该扫描选择一个最优的扫描组。在进行扫描时，以扫描组为单位发送正向的公共数据请求，所读取的数据被组内的所有扫描共享。当同组内速度较快的扫描当领先较慢的扫描超过一定距离时，发送反向的补偿数据请求。所有的数据请求被集中处理，其中，正向的公共请求优先级较高，而反向的补偿请求优先级较低。在扫描开始和结束时，计算它对系统总体的影响并调节所有组以达到最优性能。本发明充分发挥了固态硬盘高速随机读的能力，提高了查询的平均响应时间，适合在大规模高并发的数据环境中使用。

权利要求

1.一种在固态硬盘上进行海量数据并行扫描的调度方法，其特征在于：

扫描被分成多个扫描组，对于每个扫描组，在计算机内存中分配一个固定大小的窗口用于缓存从固态硬盘上读进的数据页面，同组中的扫描共享该窗口中的数据页面；同时扫描组维护本组的统计信息，包括本扫描组的窗口大小，本扫描组的扫描数目，本扫描组的平均速度，本扫描组平均还未扫描的页面数目；

当扫描开始时，挑选一个扫描组加入，如果当前没有扫描组则创建一个，加入扫描组后，检查并在需要时对该组进行分裂，新加入的扫描以扫描组当前扫描窗口的中间页面作为自己的起始位置，并更新本组的统计信息；

当窗口中的某一数据页面被所有扫描处理过后，扫描组发起正向的公共页面请求，读取下一个页面来代换掉前一个数据页面，而当组中较快的扫描领先本组最慢的扫描超过扫描组窗口长度时，先检查自己起始位置的前一个页面在不在缓存中，如果在，则直接处理前一页面上的数据，否则发送反向的补偿页面请求到请求分发区中，所述反向的补偿页面请求是指自己起始位置反方向的前一个页面请求，唤醒请求分发进程，自己进入睡眠，直至被请求分发进程唤醒；各扫描之间通过临界区交换信息；

当一个扫描所在组的公共正向页面和它的起始位置交汇时，这个扫描已经扫描完所有的数据页面，此时扫描结束，退出该组并更新统计信息，如果自己是本组内最后一个扫描则删除扫描组，并释放出自己原来占据的公共带宽需求，同时需要对其它扫描组进行扫描，并计算状态以决定是否分裂；

所有的页面请求被一个请求分发进程统一处理，当有新的页面请求产生时，扫描或扫描组唤醒请求分发进程，正向的公共页面请求具有较高的优先级，被优先处理，反向的补偿页面请求在有足够系统资源的情况下才被处理；当一个正向的公共页面请求被处理后，发起正向的公共页面请求的扫描组内的所有成员都被请求分发进程唤醒，包括已经发送了反向的补偿页面请求的扫描，当一个反向的补偿页面请求被完成后，发起反向的补偿页面请求的扫描被请求分发进程唤醒。

2.根据权利要求1所述的一种在固态硬盘上进行海量数据并行扫描的调度方法，其特征在于：所述分成多个扫描组的方法根据系统的信息和各扫描的统计信息决定，每个扫描在开始时根据贪心算法检查各个现有扫描组以决定加入哪一个可使系统的负荷增加最小；

在加入扫描组后，同样根据贪心算法检查按照何种分裂策略可使系统的负荷降低最多。

3.根据权利要求1所述的一种在固态硬盘上进行海量数据并行扫描的调度方法，其特征在于：所述各扫描组的内存窗口大小随着组数目的增减和计算机内存的可用情况动态调整。

4.根据权利要求1所述的一种在固态硬盘上进行海量数据并行扫描的调度方法，其特征在于：所述公共页面请求和补偿页面请求被一个请求分发进程统一处理，公共页面请求和补偿页面请求分别加入各自的队列，请求分发进程被唤醒后，首先服务正向的公共请求队列，当请求被完成时唤醒发起请求的该组所有扫描；当正向公共请求队列为空时服务反向补偿请求队列并处理，当请求被完成时唤醒发起反向补偿请求的扫描。

5.根据权利要求1所述的一种在固态硬盘上进行海量数据并行扫描的调度方法，其特征在于：所述扫描与扫描之间依靠临界区进行信息交换，而扫描与请求分发进程之间依靠信号量进行唤醒。

说明书

一种在固态硬盘上进行海量数据并行扫描的调度方法

技术领域

[0001] 本发明涉及数据信息处理，特别是涉及一种在固态硬盘上进行海量数据并行扫描的调度方法。

背景技术

[0002] 近年来计算机，尤其是大型服务器的硬盘性能已经远远跟不上CPU性能的飞速提升，因此固态硬盘将取代传统的磁性硬盘已成为共识。固态硬盘的优势在于它克服了随机寻道慢的弱点，目前先进的固态硬盘的随机访问速度可以达到传统磁性硬盘的几百到几千倍。

[0003] 然而我们注意到，大部分现有的大型数据存储系统，以关系数据库为代表，在设计之时都是面对传统磁性硬盘的。因此当这些系统被直接移植到固态硬盘上时，它们的I/O调度方法必然无法充分发挥出固态硬盘的性能优势。

[0004] 海量数据扫描是在决策支持、数据挖掘领域常见的一种操作，当有多个用户并行地对数据库中的某一张表进行全表查询时，他们的扫描会形成对外存设备过多的读取，从而造成I/O通道的严重堵塞，降低查询的性能。目前SQL Server，DB2等工业数据库的解决方法往往是使多个扫描同步，共享从硬盘上读进来的数据页面。然而在实际应用中，不同的查询具有不同的复杂度，从而导致不同扫描的速度差异很大，传统的方法为了避免磁盘的磁针抖动，往往牺牲了速度较快查询的响应时间，使它等待速度较慢的查询。很明显，这些传统的方法并不适用于固态硬盘，因为固态硬盘不存在磁针的寻道问题，在传统的方法下，固态硬盘的高速随机读取能力完全没有发挥出来。

发明内容

[0005] 本发明目的在于提供一种在固态硬盘上进行海量数据并行扫描的调度方法，充分发挥固态硬盘高速随机读的特性，获得相比传统方法更优秀的查询响应时间。

[0006] 为达到上述目标，本发明的技术方案如下：

[0007] 扫描被分成多个扫描组，对于每个扫描组，在计算机内存中分配一个固定大小的窗口用于缓存从固态硬盘上读进的数据页面，同组中的扫描共享该窗口中的数据页面；同时扫描组维护本组的统计信息，包括本扫描组的窗口大小，本扫描组的扫描数目，本扫描组的平均速度，本扫描组平均还未扫描的页面数目；

[0008] 当扫描开始时，挑选一个扫描组加入，如果当前没有扫描组则创建一个，加入扫描组后，检查并在需要时对该组进行分裂，新加入的扫描以扫描组当前扫描窗口的中间页面作为自己的起始位置，并更新本组的统计信息；

[0009] 当窗口中的某一数据页面被所有扫描处理过后，扫描组发起正向的公共页面请求，读取下一个页面来代换掉前一个数据页面，而当组中较快的扫描领先本组最慢的扫描超过扫描组窗口长度时，先检查自己起始位置的前一个页面在不在缓存中，如果在，则直接处理前一页面上的数据，否则发送反向的补偿页面请求到请求分发区中，所述反向的补偿页面请求是指自己起始位置反方向的前一个页面请求，唤醒请求分发进程，自己进入睡眠，直至被请求分发进程唤醒；各扫描之间通过临界区交换信息；

[0010] 当一个扫描所在组的公共正向页面和它的起始位置交汇时，这个扫描已经扫描完所有的数据页面，此时扫描结束，退出该组并更新统计信息，如果自己是本组内最后一个扫描则删除扫描组，并释放出自己原来占据的公共带宽需求，同时需要对其它扫描组进行扫描，并计算状态以决定是否分裂；

[0011] 所有的页面请求被一个请求分发进程统一处理，当有新的页面请求产生时，扫描或扫描组唤醒请求分发进程，正向的公共页面请求具有较高的优先级，被优先处理，反向的补偿页面请求在有足够系统资源的情况下才被处理；当一个正向的公共页面请求被处理后，发起正向的公共页面请求的扫描组内的所有成员都被请求分发进程唤醒，包括已经发送了反向的补偿页面请求的扫描，当一个反向的补偿页面请求被完成后，发起反向的补偿页面请求的扫描被请求分发进程唤醒。

[0012] 所述分成多个扫描组的方法根据系统的信息和各扫描的统计信息决定，每个扫描在开始时根据贪心算法检查各个现有扫描组以决定加入哪一个可使系统的负荷增加最小；在加入扫描组后，同样根据贪心算法检查按照何种分裂策略可使系统的负荷降低最多。

[0013] 所述各扫描组的内存窗口大小随着组数目的增减和计算机内存的可用情况动态调整。

[0014] 所述公共页面请求和补偿页面请求被一个请求分发进程统一处理，公共页面请求和补偿页面请求分别加入各自的队列，请求分发进程被唤醒后，首先服务正向的公共请求队列，当请求被完成时唤醒发起请求的该组所有扫描；当正向公共请求队列为空时服务反向补偿请求队列并处理，当请求被完成时唤醒发起反向补偿请求的扫描。

[0015] 所述扫描与扫描之间依靠临界区进行信息交换，而扫描与请求分发进程之间依靠信号量进行唤醒。

[0016] 本发明解决了固态硬盘上的海量数据并行扫描问题，具有的有益效果是：

[0017] 1)速度相近的扫描只会占用单个扫描的I/O带宽，有效节省了固态硬盘的带宽资源，使得系统的有效服务能力得到提升。

[0018] 2)速度较快的扫描可以利用固态硬盘快速随机读的性能优势，在与较慢扫描共享I/O带宽的同时自己进行补偿扫描，使得单个查询的响应时间得到明显提升。

[0019] 3)系统根据统计信息来动态调节各扫描组的参数，使得系统的性能随着不同的工作集进行自调节，以达到最优。

[0020] 4)本方法使用标准的同步机制和通用的页面访问机制，可以灵活地被嵌入各主流数据库产品中，也方便在各个操作系统和平台间进行移植；同时本方法基于固态硬盘闪存芯片随机访问快的基本特征，而不依赖于制造工艺，因此适用于现在和将来所有的固态硬盘产品。

附图说明

[0021] 图1是系统整体框架图。

[0022] 图2是各扫描工作流程图。

[0023] 图3是请求分发进程工作流程图。

具体实施方式

[0024] 下面结合附图及具体实施方式对本发明作进一步的描述：

[0025] 如图1所示，给出了整个并行扫描的调度框架示意图。其主要结构包括：扫描组结构，数据页面缓冲区和请求分发区。在各查询进程外还需要启动一个请求分发进程，用于服务在请求分发区的页面请求。

[0026] 扫描组结构在内存中以链表结构存在，对于每个扫描对象(表、索引)，在内存中维护一条扫描组链表。链表中的一个结点是一个单独的扫描组，在链表头上有对象标识和同步锁，对链表的访问和修改在同步锁的保护下进行。

[0027] 在扫描组结点中，维护着本扫描组的统计信息，如本扫描组的窗口大小，本扫描组的扫描数目，本扫描组的平均速度，本扫描组平均还未扫描的页面数目等。属于本扫描组的扫描以子链表的形式挂载在扫描组结点中，扫描结点同样维护了本扫描的统计信息。扫描组和扫描都采用链表形式，是为了便于结点的移动和删除。

[0028] 数据页面缓冲区用于缓存来自固态硬盘的数据。缓冲区的组织可以依赖于成熟的数据库或操作系统产品，在本发明中跳过其细节介绍，而统一归纳为给予每个页面一个权重，当发生替换时替换掉缓冲区内权重最低页面的形式。

[0029] 请求分发区包括两个先入先出队列：公共请求分发队列和补偿请求分发队列，队列头上有同步锁，用来保护对队列的访问和修改。队列中的每个成员代表一个页面请求，公共请求队列成员的结构为(页面标识号，扫描组标识号)，补偿请求队列成员的结构为(页面标识号，扫描标识号)。

[0030] 当系统启动时，后台启动一个请求分发进程来处理加入队列的页面请求。这里的进程与计算机操作系统中的进程概念不完全等价，根据不同的体系结构可以用进程、线程甚至纤程来实现。

[0031] 如图2所示，该图所示为本发明提出的单个查询进行扫描的工作流程。在关系数据库的体系结构中，海量数据扫描的流程以迭代形式分成三步进行：

[0032] 1)开始扫描：注册一个扫描句柄；

[0033] 2)进行扫描：通过句柄调用，逐行返回数据；

[0034] 3)结束扫描：销毁句柄。

[0035] 本发明的查询过程同样基于迭代形式，详细步骤为：

[0036] 1)开始扫描时，首先在扫描组结构中寻找本扫描对象是否存在扫描组，如果不存在，则生成第一个扫描组结点，将自己加入其中；如果已经存在本对象的扫描组，则寻找一个最合适的扫描组加入，并检查扫描组是否需要分裂。加入扫描组后，以扫描组当前扫描窗口的中间页面作为自己的扫描起始位置。

[0037] 201寻找最合适的扫描组。顺序访问扫描组链表中的各个结点，根据扫描组的统计信息和自身的速度，计算本扫描加入各个扫描组后的状态，并选择最优者加入。扫描自身的速度由查询的复杂度决定，现代成熟的数据库中的优化模块都具有准确估算查询复杂度的能力。

[0038] 202检查扫描组是否需要分裂。顺序访问本组中扫描子链表中的各个结点，按照扫描速度进行排序，再计算按照各个扫描将扫描组分裂成为两组的状态，选择最优方案进行分裂。

[0039] 在201和202步骤中，对最优状态的计算是根据扫描速度和剩余页面数目两个因素来决定的，根据扫描组的行为逻辑，可以作出如下定义。对于单个扫描，定义它的扫描速度为：单位时间内可处理的页面数。对于单个扫描组，定义它的公共扫描带宽需求为：组内最慢扫描的速度。定义扫描组的补偿扫描带宽需求为：组内所有扫描与最慢扫描的速度差值之和。定义扫描组的总带宽需求为：扫描细的公共扫描带宽需求与补偿扫描带宽需求之和。

[0040] 评价状态的优劣根据以下标准：在公共带宽需求之和不大于系统总带宽能力的前提下，最小化总带宽需求。在201选择扫描组时，剩余页面数目小于一定阈值的扫描组不予考虑，这样做的目的是使扫描组尽快完成以释放带宽。在计算加入或者分裂后状态时，根据扫描组的统计信息，利用贪心算法获得最优解。由于扫描和分裂的算法都只需要扫描一遍链表，其时间复杂度为O(n)。

[0041] 2)进行扫描时，扫描首先判断本扫描是否完成，其判断依据是向前扫描的页面已经到达了自己的起始位置。当扫描越过了表的最后一个数据页面时，从表的第一个数据页面开始循环扫描。

[0042] 203每个扫描在处理过程中，需要将自己当前的统计信息更新到扫描组内的结点中。为了降低对扫描组链表同步的开销，这个更新在每扫描了一定数目的页面后进行。所更新的统计信息包括：当前位置、剩余页面数目等。

[0043] 扫描首先检查自己当前位置正方向的下一个页面是否在页面缓存中，如果在，则直接处理下一页面上的数据。如果不在，则检查自己是否领先本组中最慢的扫描超过本扫描组窗口的长度。

[0044] 204如果自己没有领先本组中最慢的扫描超过扫描组窗口的长度时，发送从自己当前位置正方向的页面请求到请求分发区中，唤醒请求分发进程，自己进入睡眠，直至被请求分发进程唤醒。

[0045] 如果自己领先本组最慢的扫描超过扫描组窗口长度，先检查自己起始位置的前一个页面在不在缓存中，如果在，则直接处理前一页面上的数据。

[0046] 205否则发送从自己起始位置反方向的前一页面请求到请求分发区中，唤醒请求分发进程，自己进入睡眠，直至被请求分发进程唤醒。

[0047] 当扫描在204和205步骤中进入等待被唤醒后，需要重新检查这时自己的状态，即重新检查自己当前位置正方向的页面。

[0048] 206当扫描处理完一个页面上的数据以后，将页面上的权重进行相应设置，以便缓冲区模块将已被所有扫描处理后的页面换出。扫描通过权重设置来控制窗口的大小，而不需要直接干涉页面缓冲区的行为。对于补偿请求获得的页面，将扫描完的页面权重直接设置为最低；对于公共请求获得的页面，扫描组中的最慢扫描负责将页面权重设置为最低。

[0049] 3)结束扫描时，需要检查本组中是否还有其它扫描，如果有，则将自己的扫描结点从扫描子链表里摘除。如果没有，则将整个扫描组结点从扫描组链表里摘除。

[0050] 207当一个扫描组被删除时，会释放出自己原来占据的公共带宽需求。根据我们的分裂原则，此时可能对其它扫描组进行分裂可以优化系统的状态，因此需要对其它扫描组进行扫描，并计算状态以决定是否分裂。

[0051] 如图3所示，该图所示为本发明中的请求分发进程的工作流程。详细步骤如下：

[0052] 301首先检查公共请求队列是否为空。如果不为空，则处理当中的第一个请求；

[0053] 302如果公共请求队列为空，则检查补偿请求队列是否为空。如果不为空，则处理当中的第一个请求；

[0054] 303304每当处理完一个请求之后，将读到缓存中的数据页面设置一个较高的权重，防止页面被过早换出。再唤醒等待在这个页面请求上的所有扫描。对于公共页面请求，唤醒发起该请求的扫描组中的所有扫描，对于补偿页面请求，唤醒发起该请求的扫描。

[0055] 请求分发进程循环进行上述工作，当两个队列都为空时，请求分发进程进入睡眠状态，等待唤醒。