US 11,144,397 B2 · Data recovery using bitmap data structure

Abstract

Examples of the present disclosure describe implementing bitmap-based data replication when a primary form of data replication between a source device and a target device cannot be used. According to one example, a temporal identifier may be received from the target device. If the source device determines that the primary replication method is unable to be used to replicate data associated with the temporal identifier, a secondary replication method may be initiated. The secondary replication method may utilize a recovery bitmap identifying data blocks that have changed on the source device since a previous event.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims16

Dependent claims

A method comprising:

creating and maintaining at a source device a plurality of target-specific hierarchical bitmap structures for a plurality of target devices, wherein each of the target-specific hierarchical bitmap structures comprises a recovery bitmap, a checkpoint bitmap, and an accumulating bitmap for one of the plurality of target devices, the checkpoint bitmap corresponding to data records in a current virtual log and the accumulating bitmap corresponding to data records in a previous virtual log;
receiving a temporal identifier from a first target device of the plurality of target devices;
determining that a primary replication method is unable to be used to replicate data associated with the temporal identifier for the first target device;
and
initiating replication of data for the first target device using a secondary replication method, wherein the secondary replication method utilizes a recovery bitmap for the first target device that identifies data blocks that have changed on the source device since a previous replication of data to the first target device through a transaction indicated by the temporal identifier.

2 more elements

A data replication system comprising:

a processor;
and
memory storing computer readable instructions that when executed by the processor cause the system to:
create and maintain a plurality of target-specific hierarchical bitmap structures, wherein each of the plurality of target-specific hierarchical bitmap structures comprises a recovery bitmap, a checkpoint bitmap, and an accumulating bitmap for a target device, the checkpoint bitmap corresponding to data records in a current virtual log and the accumulating bitmap corresponding to data records in a previous virtual log;
propagate data from the checkpoint bitmap to the accumulating bitmap when a current virtual log represented by the checkpoint bitmap is full;
receive a first temporal identifier from a first target device;
determine that a primary replication method is unable to be used to replicate data associated with the first temporal identifier;
initiate replication of data to the first target device using a secondary replication method, wherein the secondary replication method utilizes a recovery bitmap for the first target device that identifies data blocks that have changed since the first temporal identifier;
based on the determination that the primary replication method is unable to be used to replicate data associated with the temporal identifier, propagate data from the accumulating bitmap to the recovery bitmap;
receive a second temporal identifier from the first target device;
determine if the accumulating bitmap for the first target device is empty;
when the accumulating bitmap for the first target device is empty, providing replication to the first target device using the primary replication method;
and
when the accumulating bitmap for the first target device is not empty, propagating data from the accumulating bitmap to the recovery bitmap and sending the recovery bitmap to the target device.

11 more elements

A method for data replication from a source device to a plurality of target devices, the method comprising:

maintaining at the source device a target-specific hierarchical bitmap structure for each of the plurality of target devices, wherein the plurality of target devices comprises a first target device and a second target device and each of the target-specific hierarchical bitmap structures comprises a checkpoint bitmap, an accumulating bitmap, and a recovery bitmap;
receiving a first log sequence number (LSN) from the first target device;
determining that a log-based replication method is unable to be used to replicate data associated with the LSN for the first target device;
initiating replication of data to the first target device using a bitmap-based replication method, wherein the bitmap-based replication method utilizes the recovery bitmap to identify data blocks that have changed on the source device since a previous event;
receiving a second log sequence number (LSN) from the second target device;
determining that a log-based replication method may be used to replicate data associated with the second LSN for the second target device;
receiving a third LSN from the first target device;
determining if the accumulating bitmap for the first target device is empty;
and
when the accumulating bitmap for the first target device is not empty, propagating data from the accumulating bitmap to the recovery bitmap and sending the recovery bitmap to the first target device.

7 more elements

Dependencies are inferred from the claim text.

Description8,896 words

Summary701 words

#Systems may utilize log-based replication for replicating data between a source and target. Updates of a source device may be captured in a log, and the log may be sent to one or more target devices for replication. During operation, a log of a target may lose synchronization with a log of a source. It is with respect to this general technical environment that the present application is directed.

#This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

#Examples of the present disclosure describe implementing bitmap-based replication when synchronization is lost between a source device and a target device. According to one example, a temporal identifier may be received from the target device. If the source device determines that a primary replication method is unable to be used to replicate data associated with the temporal identifier, a secondary replication method may be initiated. The secondary replication method may utilize a recovery bitmap identifying data blocks that have changed on the source device since a previous event.

Brief description of the drawings9 figures

#Non-limiting and non-exhaustive examples are described with reference to the following figures.

#FIG. 1A illustrates an overview of a system that may be used to implement examples described herein.

#FIG. 1B illustrates an overview of a system including a source and a target, which may be used to implement examples described herein.

Detailed description8,009 words

#Examples of the present disclosure describe implementing a secondary replication method that utilizes bitmap data structures when synchronization is lost between a source device and a target device.

#Replication systems share log records identified by log sequence numbers LSNs with other replication systems as a part of a replication protocol with the goal of synchronizing source and target data stores. When applications issue updates to data stores, a replication system synchronously records the updates to the replication log and satisfies the application request. The updates to the data store itself may be applied from the replication log when it is convenient for device to process the updates.

#Logging exists to ensure that if a crash occurs, a committed transaction will be correctly reflected in a data store after the crash. It ensures that an uncommitted transaction will be correctly rolled back and not reflected in the data store after the crash. The LSN of a log record is used for constructing the correct restore sequences during a recovery protocol enforced by the replication systems. Log Sequence numbers can be compared when constructing restore sequences in recovery protocols. Further, replication using logs permits a target device to maintain synchronization without requiring large amounts of data to be transmitted to the target device. Rather, upon initialization, the target device receives a full replication of the source device's data store, and thereafter the source device keeps a log of any transactions that affect the source device data store. The log of the transactions is periodically sent to the target device so that such transactions can be replayed at the target device data store to keep the two data stores in synchronization.

Facts

Application

14/484,592Filed 12 Sep 2014

Published

US 2016/0077917 A117 Mar 2016

Granted

12 Oct 2021

Term ends

12 Sep 2034

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification7 codes

G06F 11/1407
At machine instruction level: checkpointing the instruction stream
G06F 11/1451
Management of the data involved in backup or backup restore: by selection of backup contents
G06F 11/2074
Using a plurality of controllers: asynchronous techniques
G06F 11/2082
By mirroring: data synchronisation

Timeline

12 Sep 2014Application filedUS 14/484,592
12 Sep 2014Assigned to Microsoft Corporationassignment of assignor's interest
9 Jan 2015Assigned to Microsoft Technology Licensing, LLCassignment of assignor's interest
17 Mar 2016PublishedUS 2016/0077917 A1
12 Oct 2021GrantedUS 11,144,397 B2
12 Oct 2026TodayWithin its term
12 Sep 2034Term endsEstimated

Data recovery using bitmap data structure

Life of this patent

Data recovery using bitmap data structure

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims16

Description8,896 words

Drawings

Classification7 codes

Life of this patent

Description8,896 words