Object storage system for an unreliable storage medium

• US 9,135,136 B2
• Filed: 01/14/2014
• Issued: 09/15/2015
• Est. Priority Date: 12/27/2010
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Amplidata N.V. (Western Digital Corporation)
• Inventors: De Schrijver, Frederik, Slootmaekers, Romain Raymond Agnes, Stougie, Bastiaan, Damad, Joost Yervante, De Wispelaere, Wim, Van Eetvelde, Wouter, De Vylder, Bart
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US14/154,442
• Publication Number:
  US 20140129881A1
• Time in Patent Office: 609 Days
• Field of Search: 707/652
• US Class Current: 1/1
• 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/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method and computer device for storage and retrieval of a data object on a storage medium. The method includes steps of disassembling the data object into a predetermined number of redundant sub blocks, storing the redundant sub blocks on the storage medium, retrieving at least a predetermined multiple of a minimal spreading requirement of the redundant sub blocks from the storage medium, and assembling the data object from any combination of a particular number of the redundant sub blocks, the particular number corresponding to a predetermined multiple of a minimal spreading requirement. The computer device includes modules for performing the steps.

Claims

1. A computer device for storage and retrieval of a data object on a storage medium, the computer device having a processor and memory and comprising:

an encoding module configured to disassemble a data object into a predetermined number of redundant sub blocks, the data object comprising a data object identifier in form of the predetermined number of redundant sub blocks comprising the data object identifier, the predetermined number of redundant sub blocks corresponding to a predetermined multiple of a desired spreading width, the desired spreading width consisting of the sum of;

(a) a minimal spreading requirement that when multiplied with the predetermined multiple corresponds to a minimal number of sub blocks of the data object which are not allowed to fail; and

(b) a maximal concurrent failures tolerance that when multiplied with the predetermined multiple corresponds to a number of sub blocks of the data object which are allowed to fail concurrently;

each one of the redundant sub blocks comprising;

(a) encoded data of equal size of the data object divided by a factor equal to the predetermined multiple of the minimal spreading requirement; and

(b) decoding data, enabling the data object to be decoded from any combination of a particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement;

a spreading module configured to store the predetermined number of the redundant sub blocks on the storage medium;

a clustering module configured to retrieve at least the predetermined multiple of the minimal spreading requirement of the redundant sub blocks from the storage medium; and

a decoding module configured to assemble the data object from any combination of the particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement.

2. The computer device according to claim 1, wherein the storage medium is segmented into at least the desired spreading width of different sections, the spreading module further being configured to store the predetermined number of the redundant sub blocks on a number of the sections of the storage medium that is larger or equal to the desired spreading width, the clustering module further being configured to retrieve at least the predetermined multiple of the minimal spreading requirement of the redundant sub blocks from the sections of the storage medium.

3. The computer device according to claim 2, wherein the storage medium is a storage medium selected from the group consisting of:

a magnetic storage medium;

a flash drive;

an optical storage medium;

a holographic storage medium; and

a quantum information storage medium.

4. The computer device according to claim 3, wherein the magnetic storage medium is a magnetic tape or disk drive.

5. The computer device according to claim 1, wherein the storage medium is a storage medium selected from the group consisting of:

a magnetic storage medium;

a flash drive;

an optical storage medium;

a holographic storage medium; and

a quantum information storage medium.

6. The computer device according to claim 5, wherein the magnetic storage medium is a magnetic tape or disk drive.

7. A method for storage and retrieval of a data object on a storage medium, the data object having a size, the method comprising:

disassembling the data object into a predetermined number of redundant sub blocks, the predetermined number of redundant sub blocks corresponding to a predetermined multiple of a desired spreading width, the desired spreading width consisting of the sum of;

(a) a minimal spreading requirement that when multiplied with the predetermined multiple corresponds to a minimal number of sub blocks of the data object which are not allowed to fail, and (b) a maximal concurrent failures tolerance that when multiplied with the predetermined multiple corresponds to a number of sub blocks of the data object which are allowed to fail concurrently;

each one of the redundant sub blocks comprising;

(a) encoded data of equal size of the data object divided by a factor equal to the predetermined multiple of the minimal spreading requirement; and

(b) decoding data, enabling the data object to be decoded from any combination of a particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement;

storing the predetermined number of redundant sub blocks on the storage medium;

retrieving at least the predetermined multiple of the minimal spreading requirement of the redundant sub blocks from the storage medium; and

assembling the data object from any combination of the particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement.

8. The method recited in claim 7, wherein

disassembling the data object into the predetermined number of redundant sub blocks comprises:

calculating each redundant sub block by means of a predetermined combination of XOR operations on intermediate data blocks;

generating a Cyclic Redundancy Check (CRC) for each of the intermediate data blocks;

calculating a predetermined number of CRCs of the redundant sub blocks by applying the predetermined combination of XOR operations to the respective CRCs of the intermediate data blocks; and

storing the predetermined number of redundant sub blocks on the storage medium comprises storing the predetermined number of CRCs together with their corresponding redundant sub blocks on the storage medium.

9. The method recited in claim 8, wherein

retrieving at least the predetermined multiple of the minimal spreading requirement of the redundant sub blocks comprises retrieving the respective CRCs of the redundant sub blocks;

and

assembling the data object from any combination of the particular number of the redundant sub blocks comprises;

assembling the data object from intermediate data blocks which are generated from the redundant sub blocks by means of the predetermined combination of XOR operations; and

calculating the CRCs of the intermediate data blocks by applying the predetermined combination of XOR operations to the respective CRCs of the redundant sub blocks.

10. The method recited in claim 8, wherein assembling the data object from any combination of the particular number of the redundant sub blocks comprises:

forming the data object from a concatenation of a plurality of the intermediate data blocks; and

calculating a CRC of the data object from the CRCs of the respective intermediate data blocks.

11. A computer device configured to be used for storage and retrieval of a data object, the computer device comprising:

a processor; and

memory having stored thereon instructions that when processed by the processor cause a method for storage and retrieval of a data object on an unreliable electronic storage medium to be performed, the method comprising;

disassembling the data object into a predetermined number of redundant sub blocks, the predetermined number of redundant sub blocks corresponding to a predetermined multiple of a desired spreading width, the desired spreading width consisting of the sum of;

(a) a minimal spreading requirement that when multiplied with the predetermined multiple corresponds to a minimal number of sub blocks of the data object which are not allowed to fail, and (b) a maximal concurrent failures tolerance that when multiplied with the predetermined multiple corresponds to a number of sub blocks of the data object which are allowed to fail concurrently;

each one of the redundant sub blocks comprising;

(a) encoded data of equal size of the data object divided by a factor equal to the predetermined multiple of the minimal spreading requirement; and

(b) decoding data, enabling the data object to be decoded from any combination of a particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement;

storing the predetermined number of redundant sub blocks on the storage medium;

retrieving at least the predetermined multiple of the minimal spreading requirement of the redundant sub blocks from the storage medium; and

assembling the data object from any combination of the particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement.