Data backup management on distributed storage systems

A portion of the disclosure of this patent document may contain command formats and other computer language listings, all of which are subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

This Application claims priority from U.S. Provisional Patent Application Ser. Nos. 61/988,603 entitled “DISTRIBUTED DATA STORAGE MANAGEMENT” and 61/988,796 entitled “ZONE CONSISTENCY” filed on May 5, 2014 the content and teachings of which are hereby incorporated by reference in their entirety.

This Application is related to U.S. patent application Ser. No. 14/319,349 entitled “DISTRIBUTED DATA STORAGE MANAGEMENT”, Ser. No. 14/319,360 entitled “DISTRIBUTED METADATA MANAGEMENT”, Ser. No. 14/319,368 entitled “SCALABLE DISTRIBUTED STORAGE SYSTEM INFRASTRUCTURE”, Ser. No. 14/319,378 entitled “DISTRIBUTED DATA STORAGE MANAGEMENT”, Ser. No. 14/319,113 entitled “ZONE CONSISTENCY”, and Ser. No. 14/319,117 entitled “ZONE CONSISTENCY” filed on even date herewith, the teachings of which applications are hereby incorporated herein by reference in their entirety.

This invention relates to data storage.

Computer systems are constantly improving in terms of speed, reliability, and processing capability. As is known in the art, computer systems which process and store large amounts of data typically include a one or more processors in communication with a shared data storage system in which the data is stored. The data storage system may include one or more storage devices, usually of a fairly robust nature and useful for storage spanning various temporal requirements, e.g., disk drives. The one or more processors perform their respective operations using the storage system. Mass storage systems (MSS) typically include an array of a plurality of disks with on-board intelligent and communications electronics and software for making the data on the disks available.

Companies that sell data storage systems and the like are very concerned with providing customers with an efficient data storage solution that minimizes cost while meeting customer data storage needs. It would be beneficial for such companies to have a way for reducing the complexity of implementing data storage.

A computer-executable method, computer program product, and system for managing backups in a distributed data storage system including a first zone, a second zone, and a third zone, the computer-executable method, computer program product, and system comprising processing, at the third zone, a first portion of data of the first zone and a second portion of data of the second zone to create a combined portion of data, and removing the first portion and second portion from the third zone.

Objects, features, and advantages of embodiments disclosed herein may be better understood by referring to the following description in conjunction with the accompanying drawings. The drawings are not meant to limit the scope of the claims included herewith. For clarity, not every element may be labeled in every figure. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments, principles, and concepts. Thus, features and advantages of the present disclosure will become more apparent from the following detailed description of exemplary embodiments thereof taken in conjunction with the accompanying drawings in which:

FIG. 1 is a simplified illustration of a distributed data storage system, in accordance with an embodiment of the present disclosure;

FIG. 2 is a simplified illustration of a distributed data storage system, in accordance with an embodiment of the present disclosure;

FIG. 3 is a simplified illustration of a distributed data storage system backing up portions of data, in accordance with an embodiment of the present disclosure;

FIG. 4 is a simplified illustration of a distributed data storage system reducing the amount of backup data stored, in accordance with an embodiment of the present disclosure;

FIG. 5 is a simplified illustration of a distributed data storage system reducing the amount of backup data stored, in accordance with an embodiment of the present disclosure;

FIG. 6 is a simplified flowchart of a method of reducing used storage space for backups in the distributed data storage system of FIG. 4 , in accordance with an embodiment of the present disclosure;

FIG. 7 is a simplified illustration of a distributed data storage system, in accordance with an embodiment of the present disclosure;

FIG. 8 is a simplified illustration of a Zone failure in a distributed data storage system, in accordance with an embodiment of the present disclosure;

FIG. 9 is a simplified illustration of failover processing in a distributed data storage system, in accordance with an embodiment of the present disclosure;

FIG. 10 is a simplified illustration of a distributed data storage system recovering backup data during failover processing, in accordance with an embodiment of the present disclosure;

FIG. 11 is a simplified flowchart of a method of recovering data during a failover event as shown in FIG. 10 , in accordance with an embodiment of the present disclosure;

FIG. 12 is an example of an embodiment of an apparatus that may utilize the techniques described herein, in accordance with an embodiment of the present disclosure; and

FIG. 13 is an example of a method embodied on a computer readable storage medium that may utilize the techniques described herein, in accordance with an embodiment of the present disclosure.

Like reference symbols in the various drawings indicate like elements.

Traditionally, distributed data storage systems are managed by a single node and/or module within the distributed data storage system. Conventionally, control by a single node makes a distributed data storage system vulnerable to downtime due to node failure. Typically, control by a single node makes a distributed data storage system constrained by an ability of a single node to manage data I/O requests made within the distributed data storage system. Conventionally, improving the ability to manage data I/O requests within a distributed data storage system would be beneficial to the data storage system industry.

In many embodiments, the current disclose may enable a distributed data storage system to create redundant backups within the distributed data storage system. In various embodiments, the current disclosure may enable creation of redundant backups while minimizing use of data storage space within a distributed data storage system. In certain embodiments, the current disclosure may enable a distributed data storage system to recover data from failure of one or more portions of a distributed data storage system. In other embodiments, the current disclosure may enable a distributed data storage system to recover data from a failure of one or more nodes in the distributed data storage system. In most embodiments, the current disclosure may enable a distributed data storage system to recover data from a failure of a zone and/or cluster in a distributed data storage system.

In many embodiments, a distributed data storage system may include one or more zones and/or clusters. In various embodiments, a zone and/or cluster may include one or more compute nodes and one or more data storage arrays. In certain embodiments, a zone and/or cluster may be enabled to communicate with one or more zones and/or clusters in the distributed data storage systems. In most embodiments, a zone and/or cluster may be enabled to manage and/or store data chunk format. In various embodiments, chunk format may include file and object storage formats. In other embodiments, chunk format may be portions of data storage of a specified size (i.e. 64 MB/125 MB).

In many embodiments, a compute node in a distributed data storage system may include a storage engine. In some embodiments, a storage engine may enable communication between one or more compute nodes in a distributed data storage system. In certain embodiments, a storage engine may enable a distributed data storage system to conduct cluster-wide and/or zone-wide activities, such as creating backups and/or redundancies in a zone. In other embodiments, a storage engine may enable a distributed data storage system to conduct system-wide activities which may enable creation of redundancies and/or backups to handle one or more zones and/or clusters to fail while maintaining data integrity across the entire system. In most embodiments, a storage engine may include one or more layers. In various embodiments, layers within a storage engine may include a transaction layer, index layer, chunk management layer, storage server management layer, partitions record layer, and/or a storage server (Chunk I/O) layer. In certain embodiments, a transaction layer may parse received object request from applications within a distributed data storage system. In most embodiments, a transaction layer may be enable to read and/or write object data to the distributed data storage system. In many embodiments, an index layer may be enabled to map file-name/data-range to data stored within the distributed data storage system. In various embodiments, an index layer may be enabled to manage secondary indices which may be used to manage data stored on the distributed data storage system.

In many embodiments, a chunk management layer may manage chunk information, such as, but not limited to, location and/or management of chunk metadata. In various embodiments, a chunk management layer may be enabled to execute per chunk operations. In certain embodiments, a storage server management layer may monitor the storage server and associated disks. In most embodiments, a storage server management layer may be enabled to detect hardware failures and notify other management services of failures within the distributed data storage system. In some embodiments, a partitions record layer may record an owner node of a partition of a distributed data storage system. In many embodiments, a partitions record layer may record metadata of partitions, which may be in a B+tree and journal format. In most embodiments, a storage server layer may be enabled to direct I/O operations to one or more data storage arrays within the distributed data storage system.

In many embodiments, a zone may be enabled to create efficient backups for other zones in a distributed data storage system. In various embodiments, a zone may be enabled to combine backups from multiple zones to create a single backup of combined data that may take the same, or less, space as the backups being combined. In certain embodiments, an XOR operation may be used to combine two or more backups into a single backup. In most embodiments, once a combined backup has been created, a distributed data storage system may remove the unneeded uncombined backups. In some embodiments, a zone and a cluster may equate to the same constructs in a distributed data storage system. In most embodiments, combined XOR data blocks may be created by encoding data from two or more zones. In various embodiments, a system including N zones (where N>=3), an XOR combined block may include N−1 portions of data from the N zones which may enable more data storage to be conserved as the number of zones increases.

Refer to the example embodiment of FIG. 1 . FIG. 1 is a simplified illustration of a distributed data storage system, in accordance with an embodiment of the present disclosure. As shown, distributed data storage system 100 includes cluster 120 which includes Node ( 105 A-C, 105 Generally), and Data Storage Arrays ( 115 A-B, 115 Generally). Node 105 A is in communication with data storage array 115 A and Data storage Array 115 B. Node 105 B is in communication with data storage array 115 A and 115 B. Node 105 C is in communication with data storage array 115 A and Data storage Array 115 B. In FIG. 1 , storage engine 110 is executed on each node 105 . storage engine 110 enables Applications 107 A, 109 A, 107 B, 109 B, 107 C, 109 C to execute data I/O requests to and from distributed data storage system 100 . In various embodiments, a distributed data storage system may include one or more clusters which may be located in one or more locations.

Refer to the example embodiment of FIG. 2 . FIG. 2 is a simplified illustration of a distributed data storage system, in accordance with an embodiment of the present disclosure. As shown, distributed data storage system 200 includes zones ( 205 A-C, 205 Generally). Zones 205 include one or more clusters which contain one or more nodes enabled to manage data storage on data storage arrays. Zone 205 A is managing chunk 210 A and chunk 210 B stored on data storage arrays within zone 205 A. Zone 205 B is managing chunk 210 E and chunk 210 F stored on data storage arrays within zone 205 B. Zone 205 C is managing chunk 210 C and chunk 210 D stored on data storage arrays within zone 205 C. Zone 205 A is in communication with zone 205 B and zone 205 C. Zone 205 B is in communication with Zone 205 A and zone 205 C. Zone 205 C is in communication with Zone 205 A and zone 205 B. In many embodiments, each zone may manage backups and/or redundant storage within their own zone.

Refer to the example embodiment of FIG. 3 . FIG. 3 is a simplified illustration of a distributed data storage system backing up portions of data, in accordance with an embodiment of the present disclosure. As shown, Zone 205 A sends message 330 to zone 205 C to backup chunk 210 A at zone 205 C as backup chunk 315 A. Backup chunk 315 A has the same identifier as chunk 210 A. Zone 205 A sends message 320 to zone 205 B to backup chunk 210 B as backup chunk 315 B. backup chunk 315 B has the same identifier as chunk 210 B As shown, Zone 205 B sends message 345 to zone 205 C to backup chunk 210 F at zone 205 C as backup chunk 315 F. Backup chunk 315 F has the same identifier as chunk 210 F. In many embodiments, chunks and backup chunks may have the same identifier to identify each respective chunk as being associated with another chunk with the same identifier. Zone 205 B sends message 325 to zone 205 A to backup chunk 210 E as backup chunk 315 E. Backup chunk 315 E has the same identifier as chunk 210 E. As shown, Zone 205 C sends message 335 to zone 205 A to backup chunk 210 C at zone 205 A as backup chunk 315 C. Backup chunk 315 C has the same identifier as chunk 210 C. Zone 205 C sends message 340 to zone 205 B to backup chunk 210 D as backup chunk 315 D. Backup chunk 315 D has the same identifier as chunk 210 D

Refer to the example embodiment of FIG. 4 . FIG. 4 is a simplified illustration of a distributed data storage system reducing the amount of backup data stored, in accordance with an embodiment of the present disclosure. In this embodiment, distributed data storage system 200 includes zone 205 A, 205 B, 205 C. Zone 205 A executes an XOR operation on backup chunk 315 C and backup chunk 315 E to create XOR chunk 420 G. Zone 205 B executes an XOR on backup chunk 315 B and backup chunk 315 D to create XOR chunk 420 I. Zone 205 C executes an XOR on backup chunk 315 A and backup chunk 315 F to create XOR chunk 420 H. In this embodiment, XOR chunk 420 G is the same size as backup chunk 315 C and backup chunk 315 E. XOR chunk 420 H is the same size as backup chunk 315 A and backup chunk 315 F. XOR chunk 420 I is the same size as backup chunk 315 B and backup chunk 315 D. In many embodiments, an XOR chunk may enable a distributed data storage system to reproduce one of the input chunks given availability of the remaining input chunks used to create the XOR chunk.

Refer to the example embodiment of FIG. 5 . FIG. 5 is a simplified illustration of a distributed data storage system reducing the amount of backup data stored, in accordance with an embodiment of the present disclosure. As shown, zones 205 remove extraneous backup chunks. XOR chunks 420 G, 420 H, 420 I enable distributed data storage system 200 to recover one or more chunks within distributed data storage system 200 if one of zones 205 A, 205 B, 205 C fails.

Refer to the example embodiment of FIGS. 4 and 6 . FIG. 6 is a simplified flowchart of a method of reducing used storage space for backups in the distributed data storage system of FIG. 4 , in accordance with an embodiment of the present disclosure. As shown, distributed data storage system 200 includes zone 205 A, zone 205 C, and zone 205 B. Zone 205 A is in communication with Zone 205 B and Zone 205 C. Zone 205 B is in communication with Zone 205 A and Zone 205 C. Zone 205 C is in communication with zone 205 A and Zone 205 B. Zone 205 A has received backup chunk 315 C from zone 205 C and received backup chunk 315 E from Zone 205 B (Step 600 ). Zone 205 A processes backup chunk 315 C and backup chunk 315 E to create XOR chunk 420 G (Step 610 ). Zone 205 A removes backup chunk 315 C and backup chunk 315 E (Step 620 ).

Refer to the example embodiment of FIG. 7 . FIG. 7 is a simplified illustration of a distributed data storage system, in accordance with an embodiment of the present disclosure. As shown, distributed data storage system (DDSS) 700 includes zones 705 A, 705 B, 705 C. Zone 705 A includes chunk 710 A, 710 B, and XOR chunk 720 G. Zone B includes chunk 710 E, 710 F and XOR chunk 720 I. Zone 705 C includes chunks 710 C, 710 D, and XOR chunk 720 H. In this embodiment, Zone 705 A is in communication with Zone 705 C and Zone 705 B. Zone 705 B is in communication with Zone 705 A and Zone 705 C. Zone 705 C is in communication with Zone 705 A and Zone 705 B.

Refer to the example embodiment of FIG. 8 . FIG. 8 is a simplified illustration of a Zone failure in a distributed data storage system, in accordance with an embodiment of the present disclosure. As shown, Distributed Data Storage System 700 includes zone 705 A, 705 C, 705 B. In this embodiment, zone 705 A has failed and zones 705 B, 705 C no longer have access to data on zone 705 A.

Refer to the example embodiment of FIG. 9 . FIG. 9 is a simplified illustration of failover processing in a distributed data storage system, in accordance with an embodiment of the present disclosure. As shown, Distributed Data Storage System 700 has received a request to reproduce chunk 710 A, however, zone 705 A has failed and is unable to be queried for data. Distributed data storage system 700 determines that Chunk 710 A is enabled to be reproduced at zone 705 C using XOR chunk 720 H and Chunk 710 F. Distributed data storage system 700 directs Zone 705 B to sends chunk 710 F to zone 705 C using message 945 .

Refer to the example embodiment of FIG. 10 . FIG. 10 is a simplified illustration of a distributed data storage system recovering backup data during failover processing, in accordance with an embodiment of the present disclosure. As shown, zone 705 C received chunk 710 F from zone 705 B. Zone 705 C processes XOR chunk 720 H and chunk 710 F to produce chunk 930 A which is chunk 710 A.

Refer to the example embodiments of FIGS. 10 and 11 . FIG. 11 is a simplified flowchart of a method of recovering data during a failover event as shown in FIG. 10 , in accordance with an embodiment of the present disclosure. In this embodiment, distributed data storage system 700 includes Zone 705 A, Zone 705 B, and Zone 705 C. A failure in distributed data storage system 700 has occurred and Zone 705 A has experienced a permanent failure. Upon receiving a notification of zone failure 710 A (Step 1100 ), distributed data storage system 700 determines the status of chunk 710 A (Step 1110 ) located on failed zone 705 A. Distributed data storage system 700 determines that XOR Chunk 720 H is enabled to support retrieving chunk 710 A. To process future data I/O requests, Zone 705 C retrieves Chunk 710 F from Zone 705 B (Step 1120 ). Zone 705 C processes XOR Chunk 720 H and retrieved chunk 710 F to produce Chunk 930 A, which is chunk 710 A (Step 1130 ). Zone 705 C responds is enabled to respond to data I/O requests for Chunk 710 A with chunk 930 A. Similarly, XOR Chunk 720 I is enabled to be used to retrieve Chunk 710 B in a similar manner.

The methods and apparatus of this invention may take the form, at least partially, of program code (i.e., instructions) embodied in tangible non-transitory media, such as floppy diskettes, CD-ROMs, hard drives, random access or read only-memory, or any other machine-readable storage medium.

FIG. 12 is a block diagram illustrating an apparatus, such as a computer 1210 in a network 1200 , which may utilize the techniques described herein according to an example embodiment of the present invention. The computer 1210 may include one or more I/O ports 1202 , a processor 1203 , and memory 1204 , all of which may be connected by an interconnect 1225 , such as a bus. Processor 1203 may include program logic 1205 . The I/O port 1202 may provide connectivity to memory media 1283 , I/O devices 1285 , and drives 1287 , such as magnetic or optical drives. When the program code is loaded into memory 704 and executed by the computer 1210 , the machine becomes an apparatus for practicing the invention. When implemented on one or more general-purpose processors 1203 , the program code combines with such a processor to provide a unique apparatus that operates analogously to specific logic circuits. As such, a general purpose digital machine can be transformed into a special purpose digital machine.

FIG. 13 is a block diagram illustrating a method embodied on a computer readable storage medium 1360 that may utilize the techniques described herein according to an example embodiment of the present invention. FIG. 13 shows Program Logic 1355 embodied on a computer-readable medium 1360 as shown, and wherein the Logic is encoded in computer-executable code configured for carrying out the methods of this invention and thereby forming a Computer Program Product 1300 . Program Logic 1355 may be the same logic 1205 on memory 1204 loaded on processor 1203 in FIG. 12 . The program logic may be embodied in software modules, as modules, as hardware modules, or on virtual machines.

The logic for carrying out the method may be embodied as part of the aforementioned system, which is useful for carrying out a method described with reference to embodiments shown in, for example, FIGS. 1-13 . For purposes of illustrating the present invention, the invention is described as embodied in a specific configuration and using special logical arrangements, but one skilled in the art will appreciate that the device is not limited to the specific configuration but rather only by the claims included with this specification.

Although the foregoing invention has been described in some detail for purposes of clarity of understanding, it will be apparent that certain changes and modifications may be practiced within the scope of the appended claims. Accordingly, the present implementations are to be considered as illustrative and not restrictive, and the invention is not to be limited to the details given herein, but may be modified within the scope and equivalents of the appended claims.