Method and system for multi-dimensional raid
First Claim
1. A non-transitory computer readable medium comprising instructions, which when executed perform a method for storing data, the method comprising:
- receiving a request to write data;
in response the request, selecting, a Redundant Array of Independent Disks (RAID) grid location in a RAID grid to write the data;
writing the data to memory, wherein the data is temporarily stored in the memory;
updating a data structure to indicate that the RAID grid location is filled;
determining, using the data structure, whether a data grid in the RAID grid is filled, wherein the RAID grid location is in the data grid;
based on a determination that the data grid is filled;
calculating parity values for the RAID grid using the data, wherein the RAID grid comprises a Row Q Parity Group, a Row P Parity Group, a Column Q Parity Group, a Column P Parity Group, and an Intersection Parity Group, wherein each of the parity values is associated with one selected from a group consisting of the Row Q Parity Group, the Row P Parity Group, the Column Q Parity Group, the Column P Parity Group, and the Intersection Parity Group, and wherein parity values associated with the Intersection Parity Group are calculated using the parity values from at least one selected from a group consisting of the Row Q Parity Group, the Row P Parity Group, the Column Q Parity Group, and the Column P Parity Group;
determining a physical address in persistent storage corresponding to the RAID grid location;
writing the data to a physical location in persistent storage corresponding to the physical address; and
writing the parity values to the persistent storage.
10 Assignments
0 Petitions
Accused Products
Abstract
A method for storing data. The method including receiving a request to write data. In response the request, selecting, a RAID grid location in a RAID grid to write the data, writing the data to memory, updating a data structure to indicate that the RAID grid location is filled. The method further includes determining, using the data structure, whether a data grid in the RAID grid is filled, where the RAID grid location is in the data grid and based on a determination that the data grid is filled: calculating parity values for the RAID grid using the data, determining a physical address in persistent storage corresponding to the RAID grid location, writing the data to a physical location in persistent storage corresponding to the physical address, and writing the parity values to the persistent storage.
-
Citations
29 Claims
-
1. A non-transitory computer readable medium comprising instructions, which when executed perform a method for storing data, the method comprising:
-
receiving a request to write data; in response the request, selecting, a Redundant Array of Independent Disks (RAID) grid location in a RAID grid to write the data; writing the data to memory, wherein the data is temporarily stored in the memory; updating a data structure to indicate that the RAID grid location is filled; determining, using the data structure, whether a data grid in the RAID grid is filled, wherein the RAID grid location is in the data grid; based on a determination that the data grid is filled; calculating parity values for the RAID grid using the data, wherein the RAID grid comprises a Row Q Parity Group, a Row P Parity Group, a Column Q Parity Group, a Column P Parity Group, and an Intersection Parity Group, wherein each of the parity values is associated with one selected from a group consisting of the Row Q Parity Group, the Row P Parity Group, the Column Q Parity Group, the Column P Parity Group, and the Intersection Parity Group, and wherein parity values associated with the Intersection Parity Group are calculated using the parity values from at least one selected from a group consisting of the Row Q Parity Group, the Row P Parity Group, the Column Q Parity Group, and the Column P Parity Group; determining a physical address in persistent storage corresponding to the RAID grid location; writing the data to a physical location in persistent storage corresponding to the physical address; and writing the parity values to the persistent storage. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A non-transitory computer readable medium comprising instructions, which when executed perform a method for reconstructing data, the method comprising:
-
receiving a request for first data; obtaining the first data, wherein the first data is obtained from a first physical location in persistent storage and wherein the first physical location is associated with a first physical address; making a first determination that the first data is one selected from a group consisting of corrupted and not obtained; based on the first determination; identifying a first RAID grid location corresponding to the first physical address; identifying that a first RAID grid is associated with the first Redundant Array of Independent Disks (RAID) grid location; identifying a RAID cube associated with the first RAID grid, wherein the RAID cube comprises the first RAID grid and a second RAID grid; making a first attempt to reconstruct the first data using at least one value in the first RAID grid, wherein the first attempt fails; making a second attempt, after the first attempt fails, to reconstruct the first data using at least one value in the second RAID grid, wherein the second attempt is successful; and providing the reconstructed first data to the client. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
-
19. A non-transitory computer readable medium comprising instructions, which when executed perform a method for reconstructing data, the method comprising:
-
receiving a request for data; obtaining the data, wherein the data is obtained from a physical location in persistent storage and wherein the physical location is associated with a physical address; making a first determination that the data is one selected from a group consisting of corrupted and not obtained, based on the first determination; identifying a first Redundant Array of Independent Disks (RAID) grid location corresponding to the physical address; identifying that a RAID grid is associated with the first RAID grid location; making a first attempt to reconstruct the data using a first value in a second RAID grid location, wherein the second RAID grid location is located in at least one selected from a group consisting of a first row and a first column in the RAID grid, wherein the first RAID grid location is part of the first row and the first column, wherein the first attempt fails; making a second attempt, after the first attempt fails, to reconstruct the data, wherein the second attempt is successful and wherein the second attempt comprises; reconstructing at least one selected from a group consisting of a second row and a second column in the RAID grid to obtain a reconstructed portion of the RAID gird, wherein the reconstructed portion of the RAID grid intersects at least one selected from a group consisting of the first row and the first column; reconstructing the data using a second value in a third RAID grid location, wherein the third RAID grid location is part of the reconstructed portion of the RAID grid, and wherein the third RAID grid location is located in one selected from a group consisting of the first row and first column; and providing the reconstructed data to the client.
-
-
20. A non-transitory computer readable medium comprising instructions, which when executed perform a method for reconstructing data, the method comprising:
-
receiving a request for data; attempting to obtain the data from a physical location in persistent storage, wherein the physical location is associated with a physical address; making a determination that the data is one selected from a group consisting of corrupted and unavailable; based on the determination; reconstructing a first Redundant Array of Independent Disks (RAID) grid location corresponding to a second physical address using a parity value to obtain a first value, reconstructing a second RAID grid location corresponding to a third physical address using the parity value to obtain a second value, reconstructing a third RAID grid location corresponding to a fourth physical address using the first value to obtain a third value, and reconstructing the data using the second value and the third value, wherein the first RAID grid location is in a first stripe in a RAID grid, wherein the second RAID grid location is in a second stripe in the RAID grid; wherein the parity value is located in a fourth RAID grid location in the RAID grid, and wherein in the fourth RAID grid location is part of the first stripe and the second stripe; and providing the reconstructed data to the client. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29)
-
Specification