一种基于PageRank的数据块预缓存方法

摘要

一种基于PageRank的数据块预缓存方法；其包括统计记录数据块调度情况；模型的构建；模型的更新；模型的保存；模型的加载；模型保存周期H的设定；基于PageRank算法的排序；缺块中断；数据块的预调入等。本发明是一种针对大数据处理过程中数据块频繁磁盘IO而造成的服务性能下降和数据块缓存命中率不高问题提出的解决方案，可广泛应用到大数据处理过程中，通过实时的统计记录数据块调度情况，再根据空间局部性、时间局部性和通过PageRank算法计算出来的数据块之间的紧密关系，采用预调入的方式，将要数据块主动的推送到缓存中，从而提高数据块缓存的命中率，大幅度的提高服务的性能。

说明书

技术领域

本发明属于服务器数据缓存技术领域，特别是涉及一种基于PageRank的数据块预缓存方法。

背景技术

随着互联网和移动互联网的发展，大量的互联网应用都依赖于处理海量数据以提供服务。新兴的互联网应用展示了与传统应用不同的数据存储和访问特征。目前一些大的互联网公司的数据的存储大多采用将很多文件合并成固定大小的数据块存储到磁盘上，这样的存储方式方面了企业对数据的管理，然而面临海量数据块处理的时候，常常因为数据块缓存策略的影响，造成数据块缓存命中率不高，而造成的多次的磁盘IO，从而严重减低了服务的性能。目前，大多数解决该问题的方法，不断增大物理内存、采用多级缓存、增加固态磁盘等，而这些方法基本上是通过物理的方式提高性能，对于内存、缓存、固态硬盘等，这些设备的价格比较昂贵，这会造成很大物理硬件的开支。目前尚未发现针对数据块预缓存或主动缓存的基于PageRank算法的方法。

发明内容

为了解决上述问题，本发明的目的在于提供一种基于PageRank的数据块预缓存方法。

一种基于PageRank的数据块预缓存方法，其特征在于：包括如下步骤：

步骤一、判断系统是否存在数据模型，若是存在数据模型将在指定的目录下加载数据模型；否则进入步骤二；

步骤二、初始化数据模型所需要的各个参数；

步骤三、统计数据块在Δt时间内使用的情况，生成数据块之间的关系 矩阵A；

步骤四、通过上述关系矩阵A，生成概率转移矩阵M，根据PageRank公式V’，计算出每个数据块的PageRank值，模型构造完成；根据每个数据块的PageRank值，进行模拟，具体的模拟过程为：将PageRank值高的N个数据块标识出来，将PageRank值调入内存，统计Δt1内，被标记的N个数据块使用次数n1以及计算机使用的总数据块数n2，则Δt1内命中率p＝n1/n2；

步骤五、判断上述命中率p是否大于预设的命中率P，若是大于，将模型投入实际生产中；否则执行步骤三；

步骤六、将PageRank值高的N个数据块调入缓存；

步骤七、统计数据块的使用情况，更新关系矩阵A；

步骤八、在数据处理过程中，读取数据时判断数据是否在缓存中，若在缓存中，计算机就从缓存的数据块中读取数据；否则发生却块中断，执行步骤十一；

步骤九、判断是否到了保存模型的时间，若时间到了，保存或更新模型；否则继续进行数据处理；

步骤十、将此时刻的数据模型保存或更新到磁盘上，以便计算机重启的时候直接加载模型；

步骤十一、判断缺块中断的次数MBIs是否大于初始化设定的值M，若是大于，首先将CulBlock数据块调入内存，同一时刻进行模型更新；否则，将CulBlock数据块调入到内存，记录调入缓存的数据块，同时将缺块中断次数MIBs加1。

进一步：在步骤三中，所述的关系矩阵A的表达式为:

其中，i＝j＝n，a_k,q表示当数据块k被访问时，下一时刻访问数据块q的次数，且k＝q时a_k,q＝0，a_k,q为数据块k与数据块q的关系度。

更进一步：在步骤四中，所述的PageRank公式V’的表达式为：

V'＝αMV+(1-α)e，其中，α表示计算机直接在内存中使用数据块的概率，1-α表示计算机发生缺块中断从磁盘中使用数据块的概率，M表示关系矩阵A的概率转移矩阵，V表示每次迭代中的PageRank值，且

本发明提供的基于PageRank的数据块预缓存方法的特征如下：

1.该发明是通过一种主动软策略的方式将数据块提前放到数据块缓存中，从而避免了数据块处理过程中磁盘的IO，提高缓存的命中率。

2.该发明主要是针对多数数据文件合并成固定大小的数据块而提出的，是用来解决企业对海量大数据块的快速处理，对传统的操作系统级别的缓存不适用。

3.该发明主要是通过统计几率实时环境下的数据块调度情况，根据空间局部性和时间局部性，再加上优化好的PageRank算法排序，将多个将要处理的且还没处理的数据块提前调入到缓存中，并且在实时环境下不断的更新 数据模型，具有良好的动态性。

本发明具有的优点和积极效果：

基于PageRank的数据块预缓存方法是一种针对大数据处理过程中数据块频繁磁盘IO而造成的服务性能下降和数据块缓存命中率不高问题提出的解决方案，可广泛应用到大数据处理过程中，通过实时的统计记录数据块调度情况，再根据空间局部性、时间局部性和通过PageRank算法计算出来的数据块之间的紧密关系，采用预调入的方式，将要数据块主动的推送到缓存中，从而提高数据块缓存的命中率，大幅度的提高服务的性能。

附图说明

图1是本发明优选实施例的实际生产环境的示意图；

图2是本发明优选实施例的数据块淘汰示意图；

图3是本发明优选实施例的流程图。

具体实施方式

下面结合附图和具体实施例对本发明提供的基于PageRank的数据块预缓存方法进行详细说明。

如图1、图2、图3所示，本发明提供的基于PageRank的数据块预缓存方法的核心思想是。

本发明提供的基于PageRank的数据块预缓存方法是在实际生产环境中的实施。如图1所示，所述的实际的生产环境包括：数据处理中心、内存、Disk、模型工厂。

数据处理中心：海量数据的处理中心，也包括模型的计算和每个数据块PageRank值的计算；

内存：缓存PageRank值高的数据块，为数据处理中心提供缓存支持，提高数据处理中心的命中率，减少磁盘IO；

Disk：用来存储海量的数据，采用数据块存储，数据模型的持久化存储 设备；

模型工厂：主要包括四个模块：记录器、计数器、元数据管理器、调度器。记录器主要用来统计记录数据处理中心的数据块使用情况，构建数据块之间的关系矩阵；调度器主要是根据数据模型管控数据块在缓存Cache中的缓存、淘汰，数据模型的构建、数据模型的加载、数据模型的更新和数据模型的保存等，各种参数的初始化、更新等；计数器主要是用来计数数据块中断次数，模型保存周期等；元数据管理器主要是用来管理内存中数据块的元数据。

如图2所示，本发明提供的基于PageRank的数据块预缓存方法的数据块淘汰方式，包括(a)和(b)两种方式：

图(a)表示在图3中的S12和S13阶段发生的缺块中断时的数据块淘汰方式，从磁盘调过来的一块数据将Cache中数据块PageRank值最小的数据块淘汰掉；

图(b)表示使用PageRank算法计算得到的模型进行数据块调入的的淘汰方式，将数据块PageRank值高的N(根据内存允许缓存的数据块数)个数据块调入到缓存中，若是有些将要调入内存的数据块已经在内存中，则不调入，只将其标记一下；只将不在内存中的数据块调入到内存中；

图2说明：每个方格代表一个数据块；CulBlock表示当前正在访问的数据块；StandByBlock表示下一时刻将可能访问的数据块(缓存块)。

如图3所示，本发明提供的基于PageRank的数据块预缓存方法包括按顺序执行的下列步骤：

步骤一、判断系统是否存在数据模型的S1阶段：判断系统是否存在数据模型，若是存在数据模型将在指定的目录下加载数据模型；否则进入下面步骤初始化数据模型；

步骤二、初始化数据参数的S2阶段：初始化数据模型所需要的各个参 数；

步骤三、统计记录Δt时间内的缓存的S3阶段：统计数据块在Δt时间内使用的情况，生成数据块之间的关系矩阵A；

步骤四、构造数据模型，进行模拟内存调入，计算命中率的S4阶段：通过S3阶段生成的关系矩阵A，生成相应的概率转移矩阵M，根据PageRank公式V’，计算出每个数据块的PageRank值，模型构造完成；根据每个数据块的PageRank值，进行模拟(将PageRank值高的N个数据块标识出来，假设将他们调入内存，统计Δt1内，被标记的的N个数据块使用次数n1以及计算机使用的总数据块数n2)，则Δt1内命中率p＝n1/n2；

步骤五、判断命中率是否大于P的S5阶段：判断S4阶段计算的命中率p不是大于我们预设的命中率P，若是大于，将模型投入实际生产中；否则继续完善初始化阶段的模型；

步骤六、根据数据模型将最相关的N个数据块调入缓存的S6阶段：将PageRank值高的N(根据内存允许数据块数)个数据块调入缓存(只将当前缓存中没有的数据块调入)；

步骤七、数据处理的S7阶段：该阶段数据计算机处理阶段，在该阶段中继续统计数据块的使用情况，更新关系矩阵A；

步骤八、判断计算机使用的数据是否在缓存中的S8阶段：计算机在数据处理过程中，读取数据时判断数据是否在缓存中，若在缓存中，计算机就从缓存的数据块中读取数据；否则发生却块中断执行S11阶段；

步骤九、判断是否到保存模型的时间的S9阶段：判断是否到了保存模型的时间，若时间到了，保存或更新模型；否则继续进行数据处理；

步骤十、保存或更新数据模型的S10阶段：将此时刻的数据模型保存或更新到磁盘上，以便计算机重启的时候直接加载模型；

步骤十一、判断却块中断的次数是否大于初始化设定的值的S11阶段： 判断却块中断的次数MBIs是否大于初始化设定的值M，若是大于，首先将CulBlock数据块调入内存，同一时刻进行模型更新；否则，只需将CulBlock数据块调入到内存，记录调入缓存的数据块，同时将缺块中断次数MIBs加1。

以上对本发明的实施例进行了详细说明，但所述内容仅为本发明的较佳实施例，不能被认为用于限定本发明的实施范围。凡依本发明申请范围所作的均等变化与改进等，均应仍归属于本发明的专利涵盖范围之内。