Data replication method over a limited bandwidth network by mirroring parities

• US 20060036901A1
• Filed: 12/20/2004
• Published: 02/16/2006
• Est. Priority Date: 08/13/2004
• Status: Active Grant

• Current Assignee: Slater Technology Fund, Inc.
• Original Assignee: Gemini Storage
• Inventors: Yang, Ken Q., DiPippo, John
• Granted Patent: US 7,457,980 B2
• Time in Patent Office: Days
• US Class Current: 714/6
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/2066 Optimisation of the communication load
• CPC Class Codes: G06F 11/2074 Asynchronous techniques
• CPC Class Codes: G06F 2211/1009 Cache, i.e. caches used in RAID system with parity
• CPC Class Codes: G06F 2211/1045 Nested RAID, i.e. implementing a RAID scheme in another RAID scheme
• CPC Class Codes: G06F 2211/1066 Parity-small-writes, i.e. improved small or partial write techniques in RAID systems

Abstract

A method dramatically reduces the amount of data to be stored and transferred in a networked storage system. Preferably, the network storage system provides continued data protection through mirroring/replication, disk-to-disk backup, data archiving for future retrieval, and Information Lifecycle management (ILM). The idea is to leverage the parity computation that exists in RAID systems. By caching, transferring, and storing data parity or delta bytes of changes on a block as opposed to data block itself, substantial data reduction is possible without using sophisticated compression algorithms at the production side to minimize performance impacts upon production servers. Data can be computed using the parity/delta and previously existing data at mirror side, replication side, backup storage, or at retrieval time upon events such as failures or ILM operations.

Claims

1. A storage architecture for mirroring data comprising:

(a) a network;

(b) a primary storage system for serving storage requests, wherein the primary storage system has

i) a central processing unit (CPU),

ii) a random access memory (RAM) operatively connected to the CPU and segmented into a parity cache for storing a difference between an old parity and a new parity of each data block until the difference is mirrored to a remote site,

iii) a log-structured disk as a secondary level mirroring cache, and

iv) a parity computation engine for determining the difference; and

(c) a mirror storage system in communication with the primary storage system via the network, wherein the mirror storage system provides data mirroring storage for the primary storage system for data recovery and business continuity, wherein the mirror storage system stores a mirrored copy of data of the primary storage system that is computed based on the difference transferred from the primary storage system.

2. A storage architecture as recited in claim 1, wherein the primary storage system has the RAM further segmented into a data cache and a mirroring cache.

3. A storage architecture as recited in claim 2, wherein the log-structured disk and the RAM form a two level hierarchical cache that caches data and delta_parity if computed.

4. A storage architecture as recited in claim 3, wherein upon each write operation, the RAM collects written data blocks as well as delta_parities of the written data blocks, if the delta_parities are computed, to form a log to be sequentially written into the log-structured disk.

5. A storage architecture as recited in claim 4, wherein the log-structured disk contains a header with meta-information about the log and a plurality of entries selected from the group consisting of data blocks with associated meta-information and delta_parities of data blocks with associated meta-information, each entry having a flag to indicate whether the entry is a data block or a delta_parity.

6. A storage architecture for data mirroring/replication, disk-to-disk backup, archiving, or ILM (information lifecycle management) comprising:

(a) a network;

(b) a primary storage system for serving storage requests, wherein the primary storage system has

i) a central processing unit (CPU),

ii) a random access memory (RAM) operatively connected to the CPU and segmented into a parity cache for storing a difference between an old parity and a new parity of each data block until the difference is replicated to a remote site, stored in an archiving storage, or moved to an ILM storage, and

iii) a parity computation engine for determining the difference; and

(c) a secondary storage system in communication with the primary storage system via the network, wherein the secondary storage system provides data mirroring storage for the primary storage system for data recovery and business continuity, a backup storage, archiving storage, or ILM storage, wherein the secondary storage system stores mirrored copy of data of the primary storage or the delta-parity of changed data blocks for saving storage space.

7. A storage architecture as recited in claim 6, wherein the secondary storage system is a disk-to-disk backup and data stored thereon is either directly mirrored from the primary storage system or computed based on the difference when transferred from the primary storage system such that the difference can be used to recompute data back upon retrieval using successive EX-OR functions.

8. A storage architecture as recited in claim 6, wherein the primary storage system has the RAM further segmented into a data cache, the primary storage system has the RAM further segmented into a mirroring cache and the primary storage system has a log-structured disk as a secondary level cache for mirroring, replication, disk-to-disk backup, archiving, or ILM.

9. A storage architecture as recited in claim 8, wherein the RAM and the log-structured disk form a two level hierarchical cache that caches data or delta-parity if computed, wherein the cached data and the delta-parity in the two level hierarchical cache are to be replicated, backed up, or archived to the secondary storage system.

10. A storage architecture as recited in claim 8, wherein upon each write operation, the RAM collects a written data block or a delta-parity of the written data block if the delta-parity is computed contemporaeously to form a large log to be sequentially written into the log-structured disk.

11. A storage architecture as recited in claim 10, wherein the large log contains a number of entries, each entry being either a data block with associated meta-information, a delta-parity of a data block with associated meta-information, a flag in each log entry indicating whether the log entry is a data block or a delta-parity and a header with meta-information about the large log.

14. A computer-readable medium as recited in claim 9 with functions for further invocation by performing the steps of computing parity of data based upon the delta_parity at the secondary storage system and deriving new data based upon the computed parity.

12. A computer-readable medium whose contents cause a computer system to perform a method for replicating, mirroring, and archiving data, the computer system having a CPU, a RAM, and a log disk with functions for invocation by performing the steps of:

calculating a delta_parity;

caching the delta-parity and a data block; and

providing the delta_parity or the data block to a secondary storage system.

13. A computer-readable medium as recited in claim 12 with functions for further invocation by performing the step of determining if a cache hit has occurred.

15. A method for asynchronous and real-time remote mirroring/replication of data, data backup, or archiving to a secondary storage through a limited bandwidth network connection comprising the steps of:

calculating a difference between an old parity and a new parity of a data block being changed, wherein calculating the difference is done by performing an EX-OR between the new parity and the old parity of a data stripe containing the data block, and the new parity is created by reading old data and the old parity, and performing an EX-OR with the changed data block; and

transferring the difference to the secondary site whenever bandwidth is available.

16. A system for storing data in a network comprising:

first means for calculating a delta_parity at a primary storage system;

second means for caching the delta_parity and data at the primary storage system; and

third means for transmitting the delta_parity.

17. A system as recited in claim 16, wherein the first means is a parity computation engine, the second means is a two level cache hierarchy, and the third means is limited bandwidth communication line.

18. A system as recited in claim 16, further comprising the step of determining if a cache hit has occurred.

19. A system as recited in claim 16, further comprising the step of applying data compression to the delta_parity.

20. A system as recited in claim 16, further comprising a secondary storage system for receiving the delta_parity, the secondary storage system being operative to perform the following steps:

computing parity based upon the delta_parity at a secondary storage system; and

deriving new data based upon the computed parity and data present at the secondary storage system.

21. A system as recited in claim 20, wherein the secondary storage system is further operative to perform the following steps:

reorganize logs of data and delta_parities in time sequence for each LBA;

store the logs in storage selected from the group consisting of a disk, RAID, and tapes;

use logical block addressing to index a log upon retrieval;

sequentially read the log;

find a location in the log based upon a time entry; and

recompute data based upon the delta_parity and data.