Method for distributed storage of data

• US 7,734,643 B1
• Filed: 06/30/2004
• Issued: 06/08/2010
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Werner, Jeremy, Botros, Sherif M., Arnoud, Sacha, Gates, Patrick, Manczak, Olaf, Waterhouse, Steven Richard
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): LIN, SHEW FEN
• Application Number:
  US10/883,325
• Time in Patent Office: 2,169 Days
• Field of Search: 707101-102, 707/10
• US Class Current: 707/770
• CPC Class Codes: G06F 16/10 File systems; File servers

Abstract

A method for distributively storing a data object on a data storage system includes determining a layout map ID and associating the layout map ID with the data object. The layout map ID is used in determining a layout map, and the layout map is used in determining a layout given a current configuration of the data storage system. The data object is fragmented into data fragments and parity fragments, and the data fragments and parity fragments are distributively stored on data storage system in accordance with the layout.

Claims

1. A method for distributively storing a data object on a data storage system, said method comprising:

providing a data storage system, the data storage system including two or more nodes, each of the two or more nodes being assigned a different IP address, each of the two or more nodes including one or more data structures, each of the two or more nodes including a symmetric storage system application such that each of the two or more nodes is a complete compute and storage unit that includes all software required to run the data storage system;

determining a layout map identifier (ID) for said data object;

determining a layout map utilizing said layout map ID, wherein said determining a layout map utilizing said layout map ID comprises generating a layout map associated with said layout map ID based upon the number of said two or more nodes, the number of said one or more data storage structures, the number of “

N”

data fragments per data object and the number of “

M”

parity fragments per data object, wherein said “

N”

number of data fragments is a number of portions in to which said data object is divided, and further wherein said “

M”

parity fragments is a number of parity fragments generated by application of an erasure coding algorithm to said data fragments;

wherein said data storage system has a configured number of “

N”

data fragments per data object and “

M”

parity fragments per data object; and

further wherein said layout map is a matrix comprising;

one or more columns equal to (N+M); and

one or more rows equal to a total number of said one or more data storage structures divided by (N+M), wherein each intersection of said one or more columns and said one or more rows comprises an identifier of a particular one of said one or more data storage structures;

determining a layout utilizing said layout map;

wherein determining a layout utilizing said layout map comprises;

obtaining a current disk mask, said disk mask indicating at least which data storage structures are operational; and

applying said disk mask to said layout map to determine said layout;

fragmenting said data object; and

distributively storing said data object on one or more of said one or more data storage structures in accordance with said layout.

2. The method of claim 1, wherein said fragmenting said data object comprises:

receiving said data object;

dividing said data object into one or more data blocks;

dividing each of said one or more data blocks into one or more data fragments; and

applying the erasure coding algorithm to said one or more data fragments to generate one or more parity fragments; and

further wherein said distributively storing said data object on one or more of said one or more data storage structures in accordance with said layout comprises;

distributively storing said one or more data fragments and said one or more parity fragments on said one or more of said one or more data storage structures in accordance with said layout.

3. The method of claim 2, wherein said erasure coding algorithm is a Reed-Solomon erasure coding algorithm.

4. The method of claim 2, wherein said erasure coding algorithm generates said one or more parity fragments based on one or more external criteria.

5. The method of claim 2, wherein said erasure coding algorithm generates said one or more parity fragments based on a specified level of reliability of storage of said data object on said data storage system.

6. The method of claim 2, wherein said erasure coding algorithm generates said one or more parity fragments based on a configured number of “

N”

data fragments per data object and “

M”

parity fragments per data object.

7. The method of claim 2, further comprising:

generating a unique identifier of said data object based on an intrinsic property of said data object.

8. The method of claim 7, further comprising:

generating metadata associated with said data object.

9. The method of claim 8, further comprising:

storing at least a portion of said metadata with each of said one or more data fragments and each of said one or more parity fragments.

10. The method of claim 1, wherein said determining a layout map ID comprises:

randomly selecting a value within a specified range of values.

11. A data storage system comprising:

two or more nodes, each of said two or more nodes being assigned a different IP address, each of the two or more nodes including one or more data structures, each of the two or more nodes including a symmetric storage system application such that each of the two or more nodes is a complete compute and storage unit that includes all software required to run the data storage system, each of the two of more nodes further including;

a processor; and

a memory coupled to said processor, and having stored therein computer readable instructions for a method for distributively storing a data object on a data storage system, wherein upon execution of said computer readable instructions on said processor, said method comprises;

determining a layout map identifier (ID) for a said data object;

determining a layout map utilizing said layout map ID, wherein said determining a layout map utilizing said layout map ID comprises generating a layout map associated with said layout map ID based upon the number of said two or more nodes, the number of said one or more data storage structures, the number of “

N”

data fragments per data object and the number of “

M”

parity fragments per data object, wherein said “

N”

number of data fragments is a number of portions into which said data object is divided, and further wherein said “

M”

parity fragments is a number of parity fragments generated by application of an erasure coding algorithm to said data fragments;

wherein said data storage system has a configured number of “

N”

data fragments per data object and “

M”

parity fragments per data object; and

further wherein said layout map is a matrix comprising;

one or more columns equal to (N+M); and

one or more rows equal to a total number of said one or more data storage structures divided by (N+M), wherein each intersection of said one or more columns and said one or more rows comprises an identifier of a particular one of said one or more data storage structures;

determining a layout utilizing said layout map;

wherein determining a layout utilizing said layout map comprises;

obtaining a current disk mask, said disk mask indicating at least which data storage structures are operational; and

applying said disk mask to said layout map to determine said layout;

fragmenting said data object; and

distributively storing said data object on one or more of said one or more data storage structures in accordance with said layout.

12. The data storage system of claim 11, wherein said determining a layout map identifier (ID) comprises:

randomly selecting a value within a specified range of values.