CN1975684A - 一种支持边服务边恢复的分布式实时数据库故障恢复方法 - Google Patents

Abstract

一种支持边服务边恢复的分布式实时数据库故障恢复方法。本发明提供的支持边服务边恢复的基于日志的“识时”动态故障恢复方法(TCDCRS)采用了集成分区日志和短暂日志特性的实时日志模式，同时使用非易失性高速存储设备作为日志存储区，以尽可能地降低系统正常运行时日志代价；在站点发生故障后的恢复策略上，TCDCRS给出了基于分类恢复思想的动态恢复策略，来支持系统边服务边恢复，从而尽可能减少故障站点停止服务的时间。本发明适用于工业过程控制、电网调度、军事作战指挥系统等，需要分布式实时数据库支持的领域。

Description

一种支持边服务边恢复的分布式实时数据库故障恢复方法

【技术领域】：本发明属于分布式实时数据库故障恢复领域。当站点故障发生，借助于系统正常运行时记录的日志信息将分布式实时数据库恢复到最近的一致性状态。

【背景技术】：一类应用，如工业过程控制、电网调度、军事作战指挥系统等，需要分布式实时数据库的支持。分布式实时数据库是分布式数据库和实时数据库相结合的产物，是事务和数据都可以具有定时限制的分布式数据库。在分布式实时数据库中，事务的定时限制典型地表现为事务有截止期。一个实时事务若在规定的截止期后(超截止期)完成，结果将变得毫无价值(对固实时事务)，甚至还可能带来灾难性的后果(对硬实时事务)。分布式实时数据库中数据的定时限制表现为实时数据的有效期，实时数据仅在其有效期内有效，过期的实时数据将变得毫无意义。为了更好地满足事务和数据的定时限制，分布式实时数据库通常需要内存数据库技术提供支持。内存数据库(MMDB)要求数据库工作版本(MDB)常驻内存，外存版本(SDB)作为内存版本的备份。MMDB确保事务执行过程中的所有读、写操作都是针对内存版本，即事务执行过程中无数据I/O。

分布式环境本身的复杂性加上内存的易失性和脆弱性，使得相对于基于磁盘的集中式数据库而言，分布式实时数据库发生故障的可能性更大。当系统故障发生，在恢复正常服务前，许多实时事务可能错过它们的截止期，大量实时数据将变得无效。因此故障发生后，能迅速而有效的恢复对分布式实时数据库而言有至关重要的意义，是其具有实用价值、能够可靠地工作的基础和必备条件，也是其能真正进入市场、推广应用的关键。

现有的数据库故障恢复方法通常基于传统的“静态”恢复的思想，它要求在整个故障恢复处理过程中停止系统服务，这显然不能满足分布式实时数据库中事务和数据有定时限制的需求。此外，传统的数据库故障恢复方法采用的是顺序持久日志模式，顺序持久日志模式将日志记录存储在单一的日志文件中，单一的日志文件会因为严重的访问竞争而成为系统性能的瓶颈，同时，日志持久存放也导致存储空间的浪费与日志处理时间的增加。因此，现有的数据库故障恢复方法已经不能满足分布式实时数据库高性能的需求。

【发明内容】：本发明的目的是解决现有数据库故障恢复方法的低效问题，提供一种适合分布式实时数据库的、支持边服务边恢复的动态恢复方法。

本发明提供的支持边服务边恢复的分布式实时数据库故障恢复方法，方法包括：

1)采用集成分区日志和短暂日志特性的实时日志模式：即根据事务类的划分策略，将日志存储区分成对应的不同分区，属于不同类别的事务的日志记录被分别存储在不同的日志分区。同时日志记录并不持久保存，在本地模糊检验点执行过程中，一些无用的日志记录被删除。

2)存储介质的组织：每个站点的存储介质分为三层：磁盘存储器、非易失RAM、易失RAM(主存)；本地外存数据库(LSDB)被存储在磁盘存储器中；非易失RAM作为日志存储区，对应于规范化分划σ(σ定义在后文中具体给出)，整个日志存储区被划分成四个独立的子日志区；本地内存数据库(LMDB)被存储在易失性主存中，并且被分成两个独立的分区：关键数据分区和一般数据分区，用来分别存储关键数据类和一般数据类；

3)执行频率动态可调的模糊检验点模式：采用模糊检验点模式，在检验点触发时机上，不是采用固定时间间隔的周期性触发策略，而是根据日志存储区空间使用率(简记为R_LU)是否到达设定的阈值α来决定是否触发检验点。当R_LU大于α，检验点被触发执行。α的初始值可根据应用的要求预先设定，在系统运行过程中可通过修改α的值来动态调整检验点执行的频率。

4)动态恢复策略：在站点发生故障后的恢复处理过程中，采用了基于分类恢复思想的动态恢复处理策略，其关键特征是：关键数据类被首先恢复，在恢复一般数据类前恢复站点服务，然后边服务边恢复一般数据类，以最大限度地降低故障站点停止服务的时间。动态恢复策略的具体包括如下步骤：

①从本地外存数据库(LSDB)中将关键数据类装入主存相应数据分区，本地内存数据库(LMDB)；

②消除属于关键事务类的夭折的控制事务导致的对外部世界改变，并将关键数据类恢复到最近一致性状态；

③恢复故障站点的服务；

④从本地外存数据库(LSDB)中将一般数据类装入主存相应数据分区；

⑤消除属于一般事务类的夭折的控制事务导致的对外部世界改变，并将一般数据类恢复到最近一致性状态。

——上述方法1)中的日志存储区的分划方法如下：

1)首先将事务集合ST按事务优先级划分成两个子集：ST_＞p＝{T_i|Pr(T_i)＞p，T_i∈ST}和ST_＜＝p＝{T_i|Pr(T_i)≤p，T_i∈ST}，这里，Pr(T_i)表示事务T_i的优先级；显然，{ST_＞p，ST_＜＝p}为ST的一分划；

2)通过适当的调整p值，使得DS(ST_＞p)∩DS(ST_＜＝p)＝，即{ST_＞p，ST_＜＝p}为ST的一正交分划；其中，DS(ST_＞p)为属于ST_＞p中的高优先级事务所存取的数据对象的集合，称DS(ST_＞p)为关键数据类，称ST_＞p为关键事务类；DS(ST_＜＝p)为属于ST_＜＝p中的低优先级事务所存取的数据对象的集合，称其为一般数据类，称ST_＜＝p为一般事务类；

3)进一步，将ST_＞p划分成两个或两个以上子集：ST_＞p，＞f＝{T_i|Fr(T_i)＞f，T_i∈ST_＞p}和ST_{＞p，＜＝f}＝{T_i|Fr(T_i)≤f，T_i∈ST_＞p}，这里，Fr(T_i)代表T_i的估计执行频率，f为一设定的频率值，显然，{ST_＞p，＞f，ST_{＞p，＜＝f}}是ST_＞p的一个分划；类似地，将ST_＜＝p划分成两个或两个以上子集：ST_{＜＝p，＞f}＝{T_i|Fr(T_i)＞f，T_i∈ST_＜＝p}和ST_{＜＝p，＜＝f}＝{T_i|Fr(T_i)≤f，T_i∈ST_＜＝p}，显然，{ST_{＜＝p，＞f}，ST_{＜＝p，＜＝f}}是ST_＞p的一个分划；

4)令σ＝{ST_＞p，＞f，ST_{＞p，＜＝f}，ST_{＜＝p，＞f}，ST_{＜＝p，＜＝f}}，则(根据定理1)σ是一个规范化分划。

5)对应于规范化分划σ，将整个日志存储区被划分成四个独立的子日志区：关键高频事务类子日志区、关键低频事务类子日志区、一般高频事务类子日志区和一般低频事务类子日志区，分别简记为：LS_ch、LS_cl、LS_gh和LS_gl，它们分别用来对应地存储ST_＞p，＞f、ST_{＞p，＜＝f}、ST_{＜＝p，＞f}和ST_{＜＝p，＞＝f}事务类的日志记录，即{LS_ch，LS_cl，LS_gh，LS_gl}是关联规范化分划σ的日志存储区的一个分区；将LS_ch和LS_cl统称为关键日志区；LS_gh和LS_gl统称为一般日志区。

——其中实时日志记录的类型与结构如图1所示，含义如下：

1)结合实时提交协议1PRCP，设计五种日志记录类型：Begin，Redo，Compensate，Ready和Commit，分别用“B”，“D”，“CP”，“R”和“C”来表示，其中，P-TID表示分布式事务(全局事务)标识，定义为：P-TID::＝<Cor_Addr，N>，这里，Cor_Addr表示分布式事务的协调者的网络地址；N代表分布式事务的序号，在每个协调者站点，N是单调递增的；

2)对于本地事务，P-TID被置为NULL；TID为本地事务或子事务标识，定义为：TID::＝<Addr，SN>，这里，Addr表示本地事务或子事务所在站点的网络地址；SN表示本地事务或子事务的序号，在每个站点SN是单调递增；

3)用TS表示Redo或Compensate或Commit类型日志记录创建时刻的逻辑时标；在每个站点，逻辑时标的初始值置为0，每当一条Redo或Compensate或Commit日志记录或检验点日志记录被创建，逻辑时标的值增加1；

4)用RID代表被更新数据对象的标识，BN表示与本地外存数据库(LSDB)中数据页相对应的LSDB中数据块的逻辑块号；AI表示被更新数据对象的后映像；VTI表示实时数据对象的最大有效时刻，即VTI＝ST(X)+VI(X)，这里ST(X)表示采样时标，即采样X对应的外部世界对象的时间，VI(X)表示X的有效期，即自ST(X)算起V(X)具有有效性的时间长度；CA表示控制事务所对应的补偿活动。

——执行频率动态可调的模糊检验点模式

每个站点独立地执行本地模糊检验点；在检验点执行过程中，LMDB的更新被写出到LSDB，同时，删除无用的日志记录；在检验点触发时机上，根据日志存储区空间使用率(R_LE)是否到达设定的阈值α来决定是否触发检验点；当R_LE大于α，检验点被触发执行。

当检验点执行时，检验点日志记录被写入系统在非易失性RAM中为检验点日志记录分配的独立存储空间；检验点日志记录包括五个部分：检验点位域(CKB)、关键事务类恢复起始时标(CTRST)、一般事务类恢复起始时标(GTRST)、检验点时标(CKT)和更新页域(UPF)；检验点位域(CKB)用来表示本次检验点是否成功完成，其取值为1表示成功完成，为0表示检验点执行过程中发生系统故障；关键事务类恢复起始时标(CTRST)表示故障后需要执行REDO恢复操作的关键事务类的最小逻辑时标值，而一般事务类恢复起始时标(GTRST)表示故障后需要执行REDO恢复操作的一般事务类的最小逻辑时标值；检验点时标(CKT)表示检验点被触发时的逻辑时标；更新页域(UPF)为LMDB中的每一数据页设置一更新位(updating bit)来记录该页的更新状态，该位为0表示自上次检验点后该页还未被更新；该位为1表示自上次检验点后该页已被更新。

本发明的优点和积极效果：本发明提供的支持边服务边恢复的基于日志的“识时”动态故障恢复方法(TCDCRS)采用集成分区日志和短暂日志特性的实时日志模式，同时使用非易失性高速存储设备作为日志存储区，以尽可能地降低系统正常运行时日志代价；在站点发生故障后的恢复策略上，TCDCRS给出了基于分类恢复思想的动态恢复策略，来支持系统边服务边恢复，从而尽可能减少故障站点停止服务的时间(T_DT)。本发明与现有技术相比，具有以下优点：

(1)基于“动态”恢复的思想，支持边服务边恢复，从而极大地缩短了系统故障后停止服务的时间，有利于实时事务截止期的满足。

(2)采用集成分区和短暂日志特性的、基于非易失性RAM的实时日志技术和与之相适应的本地模糊检验点模式，大大地降低了系统正常运行时的日志和检验点代价，显著地提高了系统运行时的性能。

【附图说明】：

图1是单个站点存储介质的组织结构示意图；

图2是实时日志记录类型与结构示意图；

图3是四种日志模式的效果比较图。

【具体实施方式】：

实施例1

本发明提供的支持边服务边恢复的基于日志的“识时”动态故障恢复方法(TCDCRS)采用了集成分区日志和短暂日志特性的实时日志模式，同时使用非易失性高速存储设备作为日志存储区，以尽可能地降低系统正常运行时日志代价；在站点发生故障后的恢复策略上，TCDCRS给出了基于分类恢复思想的动态恢复策略，来支持系统边服务边恢复，从而尽可能减少故障站点停止服务的时间。具体包括：

集成分区日志和短暂日志特性的、基于非易失性RAM实时日志技术

——采用了日志存储区分区的思想，即根据事务类的划分策略，将日志存储区分成对应的不同分区，属于不同类别的事务的日志记录被分别存储在不同的日志分区，从而可以避免单一日志文件导致的系统性能瓶颈。下面给出TCDCRS日志分区的原则。

文中相关符号的含义说明如下：

参数	含义	参数	含义
				ST	系统中所有可能事务的集合	LS	日志存储区
STi	ST的一个子集	DS(T)	事务T存取的数据对象的集合
				DS(STi)	STi中所有事务存取的数据对象的集合的并集	SA(T)	事务T的日志记录的存储区域
n	表示一正整数

定义1.假定ST₁，ST₂ST，若ST₁∩ST₂＝，则称ST₁和ST₂互斥。记为：ST₁⊥ST₂。

定义2.假定ST₁，ST₂，…，ST_nST，若对任意的ST_i，ST_j，1≤i≤n，1≤j≤n，有ST_i⊥ST_j，则称集合{ST₁，ST₂，…，ST_n}为ST的互斥集。

定义3.假定{ST₁，ST₂，…，ST_n}为一互斥集，若有ST₁∪ST₂∪…∪ST_n＝ST，则称{ST₁，ST₂，…，ST_n}为ST的一个分划(分类)。其中，ST_i，1≤i≤n，称为一个事务类。

定义4.假定LS₁，LS₂，…，LS_nLS，若对任意的LS_i，LS_j，1≤i≤n，有LS_i∩LS_j＝，则称集合{LS₁，LS₂，…，LS_n}为LS的互斥集。

定义5.假定π＝{ST₁，ST₂，…，ST_n}为ST的一个分划，μ＝{LS₁，LS₂，…，LS_n}为LS的一互斥集，若存在双射(——映射)f：π→μ，则称μ为关联分划π的LS的一个分区，LS_i(1≤i≤n)称为一个子日志区。其中，f表示ST_i∈π有且只有一个LS_i∈μ使得T∈ST_i都有SA(T)LS_i，且反之也成立。

定义6.{ST₁，ST₂，…，ST_n}被称为ST的一个正交分划，若{ST₁，ST₂，…，ST_n}为ST的一个分划且ST_i，ST_j∈{ST₁，ST₂，…，ST_n}有DS(ST_i)∩DS(ST_j)＝。

原则1.为了确保故障后能将数据库恢复到正确、一致性状态，TCDCRS要求日志分区所关联的ST的分划π＝{ST₁，ST₂，…，ST_n}满足条件：{ST_k1，ST_k2，…，ST_kj}π，(DS(π₁)∩DS(π₂))＝。这里，π₁＝ST_k1∪ST_k2∪…∪ST_kj，π₂＝ST-π₁。我们称满足原则1中条件的分划为规范化分划。

我们证明了如下定理：

定理1.若{π₁，π₂}是ST的一个正交分划，{ST_k1，ST_k2，…，ST_kj}是π₁的一个分划，{ST_m1，ST_m2，…，ST_mi}是π₂的一个分划，则{ST_k1 ST_k2，…，ST_kj，ST_m1 ST_m2，…，ST_mi}为一规范化分划。

根据定理1，下面具体给出一种构造方法。首先将ST按事务优先级划分成两个子集：ST_＞p＝{T_i|Pr(T_i)＞p，T_i∈ST}和ST_＜＝p＝{T_i|Pr(T_i)≤p，T_i∈ST}，这里，Pr(T_i)表示事务T_i的优先级。显然，{ST_＞p，ST_＜＝p}为ST的一分划。通过适当地调整p的值，可使得DS(ST_＞p)∩DS(ST_＜＝p)＝(最坏的情况ST_＞p和ST_＜＝p中有一个为)，即{ST_＞p，ST_＜＝p}为ST的一正交分划。DS(ST_＞p)为属于ST_＞p中的高优先级事务所存取的数据对象的集合，我们称DS(ST_＞p)为关键数据类，称ST_＞p为关键事务类；DS(ST_＜＝p)为属于ST_＜＝p中的低优先级事务所存取的数据对象的集合，我们称其为一般数据类，称ST_＜＝p为一般事务类。进一步，我们将ST_＞p划分成两个(也可为多个)子集：ST_＞p，＞f＝{T_i|Fr(T_i)＞f，T_i∈ST_＞p}和ST_{＞p，＜＝f}＝{T_i|Fr(T_i)≤f，T_i∈ST_＞p}，这里，Fr(T_i)代表T_i的估计执行频率，f为一设定的频率值。显然，{ST_＞p，＞f，ST_{＞p，＜＝f}}是ST_＞p的一个分划。类似地，可将ST_＜＝p划分成两个(也可为多个)子集：ST_{＜＝p，＞f}＝{T_i|Fr(T_i)＞f，T_i∈ST_＜＝p}和ST_{＜＝p，＜＝f}＝{T_i|Fr(T_i)≤f，T_i∈ST_＜＝p}。显然，{ST_{＜＝p，＜f}，ST_{＜＝p，＜＝f}}是ST_＜＝p的一个分划。令σ＝{S_T＞p，＞f，ST_{＞p，＜＝f}，ST_{＜＝p，＞f}，ST_{＜＝p，＜＝f}}，则根据定理1，σ是一个规范化分划。

——存储介质的组织

如图1所示，每个站点的存储介质分为三层：磁盘存储器、非易失RAM、易失RAM(主存)。本地外存数据库(LSDB)被存储在磁盘存储器中。非易失RAM作为日志存储区，对应于规范化分划σ，整个日志存储区被划分成四个独立的子日志区：关键高频事务类子日志区、关键低频事务类子日志区、一般高频事务类子日志区和一般低频事务类子日志区，分别简记为：LS_ch、LS_cl、LS_gh和LS_gl，它们分别用来对应地存储ST_＞p，＞f、ST_{＞p，＜＝f}、ST_{＜＝p，＞f}和ST_{＜＝p，＜＝f}事务类的日志记录，即{LS_ch，LS_cl，LS_gh，LS_gl}是关联规范化分划σ的日志存储区的一个分区。我们将LS_ch和LS_cl统称为关键日志区；LS_gh和LS_gl统称为一般日志区。本地内存数据库(LMDB)被存储在易失性主存中，并且被分成两个独立的分区：关键数据分区和一般数据分区，用来分别存储关键数据类和一般数据类。

——实时日志记录的类型与结构

结合实时提交协议1PRCP，我们设计五种日志记录类型：Begin，Redo，Compensate，Ready和Commit，如图2所示。其中，P-TID表示分布式事务(全局事务)标识，定义为：P-TID::＝<Cor_Addr，N>，这里，Cor_Addr表示分布式事务的协调者的网络地址；N代表分布式事务的序号，在每个协调者站点，N是单调递增的。对于本地事务，P-TID被置为NULL。TID为本地事务或子事务标识，定义为：TID::＝<Addr，SN>，这里，Addr表示本地事务或子事务所在站点的网络地址；SN表示本地事务或子事务的序号，在每个站点SN是单调递增。“B”，“D”，“CP”，“R”和“C”用来分别表示Begin，Redo，Compensate，Ready和Commit五种日志记录类型。TS表示Redo或Compensate或Commit类型日志记录创建时刻的逻辑时标。在每个站点，逻辑时标的初始值置为0，每当一条Redo或Compensate或Commit日志记录或后文介绍的检验点日志记录被创建，逻辑时标的值增加1。RID代表被更新数据对象的标识。BN表示与LMDB中数据页相对应的LSDB中数据块的逻辑块号。AI表示被更新数据对象的后映像。VTI表示实时数据对象的最大有效时刻，即VTI＝ST(X)+VI(X)，这里ST(X)表示采样时标，即采样X对应的外部世界对象的时间，VI(X)表示X的有效期，即自ST(X)算起V(X)具有有效性的时间长度。对持久数据对象而言，其VTI置为无限大。CA表示控制事务所对应的补偿活动。

◆本地模糊检验点模式

在TCDCRS中，每个站点独立地执行本地模糊检验点。在检验点执行过程中，LMDB的更新被写出到LSDB，同时，一些无用的日志记录被删除以释放相应的日志存储空间。在检验点触发时机上，TCDCRS不是采用固定时间间隔的周期性触发策略，而是根据日志存储区空间使用率(简记为R_LU)是否到达设定的阈值α来决定是否触发检验点。当R_LU大于α，检验点被触发执行。α的初始值可根据应用的要求预先设定，在系统运行过程中可通过修改α的值来动态调整检验点执行的频率。

当检验点执行时，检验点日志记录被写入系统在非易失性RAM中为检验点日志记录分配的独立存储空间。检验点日志记录包括五个部分：检验点位域(CKB)、关键事务类恢复起始时标(CTRST)、一般事务类恢复起始时际(GTRST)、检验点时标(CKT)和更新页域(UPF)。CKB用来表示本次检验点是否成功完成。CKB取值为1表示成功完成，为0表示检验点执行过程中发生系统故障。CTRST表示故障后需要执行REDO恢复操作的关键事务类的最小逻辑时标值，而GTRST表示故障后需要执行REDO恢复操作的一般事务类的最小逻辑时标值。CKT表示检验点被触发时的逻辑时标。UPF为LMDB中的每一数据页设置一更新位(updating bit)来记录该页的更新状态，该位为0表示自上次检验点后该页还未被更新；该位为1表示自上次检验点后该页已被更新。检验点执行过程可描述如下：

Procedure LocalCheckpoint()1：CKB＝0；2：CKT＝TCounter++；3：Write data pages updated by committed transaction out to LSDB；4：Set UPF according to updating state of data page；5：Write the data pages whose upadting bits are 1 out to LSDB；6：Delete useless log records，i.e.the log records of aborted transactions or whose logic timestampin Commit log records is not larger than CKT，and free the corresponding logging store spaces；7：Get the minimal logging timestamp of critical transaction class，set the value of CTRST；8：Get the minimal logging timestamp of ordinary transaction class，set the value of GTRST；9：CKB＝1；

上述算法的中文描述：

Procedure LocalCheckpoint()  /*本地检验点执行算法*/1：CKB＝0；2：CKT＝TCounter++；3：将已提交事务更新了的数据页写出到LSDB；4：根据数据页的更新状态设置UPF；5：将UPF中更新位为1的数据页写出到LSDB；6：删除夭折事务和提交记录中逻辑时标大于CKT的事务的日志记录，释放日志存储空间；7：获取关键事务类日志中最小逻辑时标，并将其赋给CTRST；8：获取一般事务类日志中最小逻辑时标，并将其赋给GTRST；9：CKR＝1；

在上面的描述中及后面的恢复处理的算法描述中，TCounter用来表示逻辑时标计数器，其初始值置为0，每当一条Redo或Compensate或Commit或检验点日志记录被创建，其值加1。系统在非易失性RAM中为TCounter分配相应的存储空间。

◆动态恢复处理方法

在站点故障后的恢复处理过程中，首先，LSDB被装入主存并重建LMDB；然后，恢复子系统负责将LMDB恢复到最近的一致性状态。为了提高系统性能，TCDCRS给出了基于分类恢复思想的动态恢复处理策略，动态恢复处理策略是以前面提出实时日志模式为基础，其关键特征是：关键数据类被首先恢复，在恢复一般数据类前恢复站点服务，然后边服务边恢复一般数据类，以最大限度地降低故障站点停止服务的时间。结合实时提交协议1PRCP，动态恢复策略能确保分布式事务故障的原子性。动态恢复策略的具体包括如下步骤：

(1)从LSDB中将关键数据类装入主存相应数据分区，重建LMDB；

(2)消除属于关键事务类的夭折的控制事务导致的对外部世界改变，并将关键数据类恢复到最近一致性状态；

(3)恢复故障站点的服务；

(4)从LSDB中将一般数据类装入主存相应数据分区；

(5)消除属于一般事务类的夭折的控制事务导致的对外部世界改变，并将一般数据类恢复到最近一致性状态。

在上面步骤中，(2)和(5)的实现算法可统一描述如下：

Procedure CrashRecovery(char dc)

  Input：dc denotes data class asking to be recovered and dc＝”C”stands for critical data class，

         while dc＝”G”stands for general data class.

1：FT＝TCounter

2：if(dc＝”C”)then

3：  RST＝CTRST；

4：  Scan critical logging partition(including CALP and CDLP)to look for all Compensate log reords

      CPLog_Ti，which satisfy the following conditions：the corresponding Commit log records

      CommitLog_Ti don’t exist，i.e.the corresponding transactions don’t commit successfully，

      and timestamp of CPLog_Ti is smaller than FT.At the same time insert these CPLog_Ti into

      compensating activity recovery list(CARL)in order of their timestamp；

5：else

6：  RST＝GTRST；

7：  Scan ordinary logging partition(including OALP and ODLP)to look for all Compensate log reords

      CPLog_Ti，which satisfy the following conditions：the corresponding Commit log records

      CommitLog_Ti don’t exist，i.e.the corresponding transactions don’t commit successfully，

      and timestamp of CPLog_Ti is smaller than FT.At the same time insert these CPLog_Ti into

      compensating activity recovery list(CARL)in order of their timestamp；

8：Scan reversely CARL until the head of CARL and for each CPLog_Ti，execute the corresponding

  compensating activity CPLog_Ti.CA；

9：while(RST≤FT)

10：  if(dc＝”C”)then

11：    Scan critical logging partition to look for the Redo log record RedoLog_Ti，k whose timestamp

        is RST；

12.   else

13：    Scan ordinary logging partition to look for the Redo log record RedoLog_Ti，k whose timestamp

        is RST；

14：  if(find the Redo log record RedoLog_Ti，k)then

15：    if(find the corresponding Commit log record CommitLog_Ti)then

16：      if(RedoLog_Ti，k.VTI＞T_c)then

17：        REDO(RedoLog_Ti，k)

18：        RST++；continue；

19：      else

20：     RST++；

21：     Triggeer the corresponding sample transaction to update overdue data；

22：  if(find the corresponding Ready log record ReadyLog_Ti)then

23：    if(receive Commit message)then

24：      REDO(RedoLog_Ti，k)；

25：      Add CommitLog_Ti to the corresponding logging partition；

26：      RST++；

27：    if(receive Abort message)then

28：      RST++；

29：  else

30：   RST++；

31：else

32：   RST++；

33：endwhile

上述算法的中文描述：

Procedure CrashRecovery(char dc)

输入：dc表示要求恢复的数据类别，dc＝”C”代表关键数据类，而dc＝”G”代表一般数据类

1：FT＝TCounter

2：if(dc＝”C”)then

3：  RST＝CTRST；

4：  扫描关键日志分区，寻找满足如下条件的Compensate日志记录CPLog_Ti，：该事务的提交日志记录不存

    在且CPLog_Ti，的逻辑时标比FT更小。将找到的CPLog_Ti，按它们逻辑时标值从小到大依次插入到补偿恢

    复活动表CARL中。

5：else

6：  RST＝GTRST；

7：  扫描一般日志分区，寻找满足如下条件的Compensate日志记录CPLog_Ti，：该事务的提交日志记录不存

     在且CPLog_Ti，的逻辑时标比FT更小。将找到的CPLog_Ti，按它们逻辑时标值从小到大依次插入到补偿恢

     复活动表CARL中。

8：反向扫描CARL表直到表头，对每一CPLog_Ti，执行相应的补充活动CPLog_Ti.CA；

9：while(RST≤FT)

10：  if(dc＝”C”)then

11：    扫描关键日志分区找逻辑时标等于RST的Redo日志记录RedoLog_Ti，k；

12.   else

13：    扫描一般日志分区找逻辑时标等于RST的Redo日志记录RedoLog_Ti，k；

14：  if(找到RedoLog_Ti，k)then

15：    if(存在相应的Commit日志记录CommitLog_Ti)then

16：      if(RedoLog_Ti，k.VTI＞T_c)then

17：        REDO(RedoLog_Ti，k)

18：        RST++；continue；

19：      else

20：     RST++；

21：     触发对应的采样事务更新过期数据对象；

22：  if(找到相应的Ready日志记录ReadyLog_Ti)then

23：   if(收到了协调者的提交消息)then

24：     REDO(RedoLog_Ti，k)；

25：     增加CommitLog_Ti到对应的日志分区；

26：     RST++；

27：    if(收到了协调者的夭折消息)then

28：     RST++；

29：  else

30：   RST++；

31：else

32：   RST++；

33：endwhile

在上面的算法描述中，RedoLog_Ti，k表示事务T_i的第k条Redo日志记录；过程REDO(RedoLog_Ti，k)负责将RedoLog_Ti，k记录的数据对象在LMDB中的值用其后映像覆盖；RedoLog_Ti，k.VTI表示RedoLog_Ti，k记录的数据对象的有效时刻。由于实时数据对象一旦过期其值即变得无意义，因此，在上述动态恢复处理策略中，对过期的实时数据对象并不执行REDO操作，还是采取触发相应的采样事务来更新过期数据对象的值。

实施例2

【具体性能比较】：

我们将TCDCRS与其它恢复方法进行了运行时日志的代价的比较，测试了不同日志模式对系统性能的影响。性能测试的主要参数设置如表1所示，其中U[i，j]表示服从区间[i，j]上的均匀分布的随机变量。在我们的实验中，全局内存数据库(GMDB)为由50000个数据页组成的集合，这些数据页被分配到5个站点形成相应的本地内存数据库(LMDB)，对数据的访问和并发控制都发生在页级，并发控制策略采用分布式高优先级两段锁协议(DHP-2PL)，事务优先级分派采用最早截上期优先策略(EDF)。事务T的截止期按如下公式计算：Deadline(T)＝AT(T)+Slack×ET(T)。这里，Deadline(T)表示T的截止期；AT(T)表示T到达系统的时间；Slack表示松弛因子，通常为一个满足均匀分布的随机变量；ET(T)表示T的估计执行时间。ET(T)按如下公式估算：ET(T)＝OpN×AET，其中OpN和AET的含义如表1所述。我们以实时事务错过截止期的比率MDR为主要性能指标，其定义如下：MDR＝(错过截止期事务的数目)/(进入系统事务的总数)。显然，MDR越小，系统实时性能越好。

                    Table 1.Experiment parameters

                            表1.实验参数

参数	取值(单位)	意义
			NS	5	分布式实时主存数据库系统包含的站点数目
SLMDB	10000(Page)	每个站点LMDB的大小
			RCD	0.4	关键数据类数据占总数据的比例
RTD	0.8	实时数据占总数据的比例
			NP	4	日志存储区分区数目
SL	8(MB)	每个站点日志存储区的大小
			AET	0.4(ms)	事务操作的平均执行时间
PU	0.4	事务操作是更新操作的概率
			Slack	U[2.0，6.0]	松弛因子
NTO	U[4，8]	事务包含的操作的数目
			α	0.8	日志存储区空间使用率阈值

我们将TCDCRS的集成分区日志和短暂日志特性的实时日志模式PERT-NVRAM与另外三种日志模式：无日志模式(NLS)、基于磁盘的分区日志模式(PLSD)和基于磁盘的顺序日志模式(SLSD)进行比较。NLS表示系统运行过程中不记录事务日志，显然这不能满足恢复的要求，这里将它作为不同模式代价比较的基准。测试结果如图3所示，当事务的到达率提高时，四种日志模式所对应的MDR都相应增大，而PERT-NVRAM最接近NLS的效果，它的MDR明显的小于其它两种日志模式。

故障发生后系统停止服务的时间T_DT是衡量恢复性能的另一重要指标。对分布式实时数据库系统而言，T_DT主要包括：将数据从LSDB装入内存重建LMDB所需的时间T₁和将LMDB恢复到一致性状态所需的时间T₂。由于TCDCRS采用了基于分类恢复思想的动态恢复策略(关键类数据被首先装入、恢复，在一般类数据装入内存前恢复了系统服务)，因此对TCDCRS而言，T_DT等于将关键数据类装入内存所需时间与在内存中将它们恢复一致性状态所需时间的总和，T_DT可估算如下：

T_DT＝T₁+T₂≈S_LMDB×R_CD×T_L0+(SL×R_CL×α)÷S_LR×T_rp    (1)

(1)式中，T_L0表示从外存读入一数据块到内存平均所需时间；R_CL表示关键日志区占整个可用日志区的比率；S_LR代表一条日志记录的平均大小；T_rp代表恢复时一条日志记录的平均处理时间；S_LMDB、R_CD、SL及α的含义如表1所描述。由于关键数据类通常只占全部数据的小部分，因此相比于将全部数据装入、恢复后再提供系统服务的静态恢复策略而言，TCDCRS能明显地降低系统停止服务的时间T_DT。

Claims (5)

1、一种支持边服务边恢复的分布式实时数据库故障恢复方法，其特征是该方法包括：

1)采用集成分区日志和短暂日志特性的实时日志模式：即根据事务类的划分策略，将日志存储区分成对应的不同分区，属于不同类别的事务的日志记录被分别存储在不同的日志分区；同时日志记录并不持久保存，在本地模糊检验点执行过程中，一些无用的日志记录被删除；

2)存储介质的组织：每个站点的存储介质分为三层：磁盘存储器、非易失RAM、易失RAM(主存)；本地外存数据库(LSDB)被存储在磁盘存储器中；非易失RAM作为日志存储区，对应于规范化分划σ，整个日志存储区被划分成四个独立的子日志区；本地内存数据库(LMDB)被存储在易失性主存中，并且被分成两个独立的分区：关键数据分区和一般数据分区，用来分别存储关键数据类和一般数据类；

3)执行频率动态可调的模糊检验点模式：采用模糊检验点模式，在检验点触发时机上，不是采用固定时间间隔的周期性触发策略，而是根据日志存储区空间使用率(简记为R_LU)是否到达设定的阈值α来决定是否触发检验点。当R_LU大于α，检验点被触发执行；α的初始值可根据应用的要求预先设定，在系统运行过程中可通过修改α的值来动态调整检验点执行的频率；

4)在站点发生故障后的恢复处理过程中，采用了基于分类恢复思想的动态恢复处理策略，其关键特征是：关键数据类被首先恢复，在恢复一般数据类前恢复站点服务，然后边服务边恢复一般数据类，以最大限度地降低故障站点停止服务的时间；动态恢复策略的具体包括如下步骤：

(1)从本地外存数据库(LSDB)中将关键数据类装入主存相应数据分区，重建本地内存数据库(LMDB)；

(2)消除属于关键事务类的夭折的控制事务导致的对外部世界改变，并将关键数据类恢复到最近一致性状态；

(3)恢复故障站点的服务；

(4)从本地外存数据库(LSDB)中将一般数据类装入主存相应数据分区；

(5)消除属于一般事务类的夭折的控制事务导致的对外部世界改变，并将一般数据类恢复到最近一致性状态。

2、根据权利要求1所述的支持边服务边恢复的分布式实时数据库故障恢复方法，其特征是1)中的日志存储区的分划方法如下：

(1)首先将事务集合ST按事务优先级划分成两个子集：ST_＞p＝{T_i|Pr(T_i)＞p，T∈ST}和ST_＜＝p＝{T_i|Pr(T_i)≤p，T_i∈ST}，这里，Pr(T_i)表示事务T_i的优先级；显然，{ST_＞p，ST_＜＝p}为ST的一分划；

(2)通过适当的调整p值，使得DS(ST_＞p)∩DS(ST_＜＝p)＝，即{ST_＞p，ST_＜＝p}为ST的一正交分划；其中，DS(ST_＞p)为属于ST_＞p中的高优先级事务所存取的数据对象的集合，称DS(ST_＞p)为关键数据类，称ST_＞p为关键事务类；DS(ST_＜＝p)为属于ST_＜＝p中的低优先级事务所存取的数据对象的集合，称其为一般数据类，称ST_＜＝p为一般事务类；

(3)进一步，将ST_＞p划分成两个或两个以上子集：ST_＞p，＞f＝{T_i|Fr(T_i)＞f，T_i∈ST_＞p}和ST_{＞p，＜＝f}＝{T_i|Fr(T_i)≤f，T_i∈ST_＞p}，这里，Fr(T_i)代表T_i的估计执行频率，f为一设定的频率值，显然，{ST_＞p，＞f，ST_{＞p，＜＝f}}是ST_＞p的一个分划；类似地，将ST_＜＝p划分成两个或两个以上子集：ST_{＜＝p，＞f}＝{T_i|Fr(T_i)＞f，T_i∈ST_＜＝p}和ST_{＜＝p，＜＝f}＝{T_i|Fr(T_i)≤f，T_i∈ST_＜＝p}，显然，{ST_{＜＝p，＞f}，ST_{＜＝p，＜＝f}}是ST_＜＝p的一个分划；

(4)令σ＝{ST_＞p，＞f，ST_{＞p，＜＝f}，ST_{＜＝p，＞f}，ST_{＜＝p，＜＝f}}，则(根据定理1)σ是一个规范化分划；

(5)对应于规范化分划σ，将整个日志存储区被划分成四个独立的子日志区：关键高频事务类子日志区、关键低频事务类子日志区、一般高频事务类子日志区和一般低频事务类子日志区，分别简记为：LS_ch、LS_cl、LS_gh和LS_gl，它们分别用来对应地存储ST_＞p，＞f、ST_{＞p，＜＝f}、ST_{＜＝p，＞f}和ST_{＜＝p，＜＝f}事务类的日志记录，即{LS_ch，LS_cl，LS_gh，LS_gl}是关联规范化分划σ的日志存储区的一个分区。

3、根据权利要求1所述的支持边服务边恢复的分布式实时数据库故障恢复方法，其特征是2)中非易失RAM作为日志存储区，对应于规范化分划σ，整个日志存储区被划分成四个独立的子日志区：关键高频事务类子日志区、关键低频事务类子日志区、一般高频事务类子日志区和一般低频事务类子日志区，分别简记为：LS_ch、LS_cl、LS_gh和LS_gl，它们分别用来对应地存储ST_＞p，＞f、ST_{＞p，＜＝f}、ST_{＜＝p，＞f}和ST_{＜＝p，＜＝f}事务类的日志记录，即{LS_ch，LS_cl，LS_gh，LS_gl}是关联规范化分划σ的日志存储区的一个分区；将LS_ch和LS_cl统称为关键日志区；LS_gh和LS_gl统称为一般日志区。

4、根据权利要求1所述的支持边服务边恢复的分布式实时数据库故障恢复方法，其特征是1)、2)、3)、或4)中的实时日志记录的类型与结构及含义如下：

(1)结合实时提交协议1PRCP，设计五种日志记录类型：Begin，Redo，Compensate，Ready和Commit，分别用“B”，“D”，“CP”，“R”和“C”来表示，其中，p-TID表示分布式事务(全局事务)标识，定义为：P-TID::＝<Cor_Addr，N>，这里，Cor_Addr表示分布式事务的协调者的网络地址；N代表分布式事务的序号，在每个协调者站点，N是单调递增的；

(2)对于本地事务，P-TID被置为NULL；TID为本地事务或子事务标识，定义为：TID::＝<Addr，SN>，这里，Addr表示本地事务或子事务所在站点的网络地址；SN表示本地事务或子事务的序号，在每个站点SN是单调递增；

(3)用TS表示Redo或Compensate或Commit类型日志记录创建时刻的逻辑时标；在每个站点，逻辑时标的初始值置为0，每当一条Redo或Compensate或Commit日志记录或检验点日志记录被创建，逻辑时标的值增加1；

(4)用RID代表被更新数据对象的标识，BN表示与本地外存数据库(LSDB)中数据页相对应的LSDB中数据块的逻辑块号；AI表示被更新数据对象的后映像；VTI表示实时数据对象的最大有效时刻，即VTI＝ST(X)+VI(X)，这里ST(X)表示采样时标，即采样X对应的外部世界对象的时间，VI(X)表示X的有效期，即自ST(X)算起V(X)具有有效性的时间长度；CA表示控制事务所对应的补偿活动。

5、根据权利要求1所述的支持边服务边恢复的分布式实时数据库故障恢复方法，其特征是3)中所述执行本地模糊检验点模式；即要求每个站点独立地执行本地模糊检验点；在检验点执行过程中，LMDB的更新被写出到LSDB，同时，删除无用的日志记录；在检验点触发时机上，根据日志存储区空间使用率(R_LU)是否到达设定的阈值α来决定是否触发检验点；当R_LU大于α，检验点被触发执行；

当检验点执行时，检验点日志记录被写入系统在非易失性RAM中为检验点日志记录分配的独立存储空间；检验点日志记录包括五个部分：检验点位域(CKB)、关键事务类恢复起始时标(CTRST)、一般事务类恢复起始时标(GTRST)、检验点时标(CKT)和更新页域(UPF)；检验点位域(CKB)用来表示本次检验点是否成功完成，其取值为1表示成功完成，为0表示检验点执行过程中发生系统故障；关键事务类恢复起始时标(CTRST)表示故障后需要执行REDO恢复操作的关键事务类的最小逻辑时标值，而一般事务类恢复起始时标(GTRST)表示故障后需要执行REDO恢复操作的一般事务类的最小逻辑时标值；检验点时标(CKT)表示检验点被触发时的逻辑时标；更新页域(UPF)为LMDB中的每数据页设置一更新位(updating bit)来记录该页的更新状态，该位为0表示自上次检验点后该页还未被更新；该位为1表示自上次检验点后该页已被更新。

Images