Method and system for storing data in raid memory devices
A redundant array of independent disk (RAID) memory storage system comprising data storage blocks arranged in a first plurality of data rows and a second plurality of data columns, wherein parity data is stored in additionally defined parity blocks, and wherein numbers of data blocks in respective columns are different, to accommodate the additional diagonal parity data block that the geometry of the system requires. The system is suitable for an SSD array in which sequential disk readout is not required.
1. A redundant array of independent disk (RAID) memory storage system comprising data storage blocks arranged in said array in a first plurality of data rows and a second plurality of data columns, wherein parity data is stored in additionally defined parity blocks, and wherein numbers of blocks in respective columns are different;
wherein at least some of said parity data is row parity data placed in a plurality of columns of row parity data wherein at least some of said parity data is diagonal parity data placed in diagonal parity blocks in a diagonal parity column, wherein the number of said data blocks comprising each row parity set is larger than the number of said data blocks comprising each diagonal parity set.
2. The RAID memory storage system of claim 1 , wherein the said data storage blocks are arranged in at least two independent parity groups, wherein each said parity group has a plurality of said parity blocks and an equal number of parity sets comprising a subset of the said data storage blocks.
3. The RAID memory storage system of claim 1 , wherein each said data block is present in exactly two said parity blocks.
4. The RAID memory storage system of claim 1 , wherein at least some of said parity blocks are arranged in parity columns other than those containing respective data blocks, and wherein each remaining said parity block is placed in a column containing data blocks other than a column which contains respective data blocks of the respective parity block.
5. The RAID memory storage system of claim 1 , wherein at least some of said parity data is row parity data placed in row parity blocks in at least one row parity column.
6. The RAID memory storage system of claim 1 , wherein at least some of said parity data is diagonal parity data placed in diagonal parity blocks in a diagonal parity column.
7. The RAID memory storage system of claim 1 , wherein at least some of said parity data is diagonal parity data placed in a column of diagonal parity data, said diagonal parity column comprising one more block than a number of said first plurality of data rows.
8. The RAID memory storage system of claim 1 , wherein at least some of said parity data is row parity data placed in row parity blocks in at least one row parity column wherein at least some of said parity data is diagonal parity data placed in diagonal parity blocks in a diagonal parity column, wherein said data storage blocks are arranged with a blank diagonal, such that each data column sharing said blank diagonal has one less block than a number of said plurality of rows and said diagonal parity column has a number of blocks equal to said number of said first plurality of data rows.
9. The RAID memory storage system of claim 1 , wherein said array comprises a plurality of solid state drives (SSD).
10. The RAID memory storage system of claim 1 , wherein said second plurality of data columns equals a prime number and said first plurality of data rows is less than said second plurality of data columns.
11. The RAID memory storage system of claim 10 , wherein said second plurality of data columns is equal to a number of disks allowed in said array, wherein at any given time an actual number of disks present is less than or equal to said allowed number of disks.
12. The RAID storage system of claim 10 , further comprising a disk addition unit for adding a new disk to the array and maintaining a balance of parity blocks over said array, the disk addition unit being configured to migrate a selected row parity block to said new disk by retaining said row parity block at an original disk position and defining a zeroed block of data to receive future parity updates for said selected row parity block, said disk addition unit further configured to calculate a new diagonal parity block on said new disk.
13. The RAID storage system of claim 1 , further comprising a single disk failure recovery unit configured to use row parity to recover a first plurality of lost data blocks and to use diagonal parity to recover remaining data blocks, thereby to use data blocks already read from said row parity recovery to calculate said diagonal parity recovery.
14. The RAID storage system of claim 1 , further comprising a double disk failure recover unit, configured to recover a first block of a first lost disk in a first, and then succeeding ones, of said rows using diagonal parity and then to recover a first block of a second lost disk in said first row, and then succeeding rows using row parity data of said first row and then succeeding rows respectively.
15. The RAID storage system of claim 1 , further comprising a data update unit for writing a new data block over an old data block, the data update unit configured to read said old data block, and existing parity data, write said new data block and XOR data of said old block with data of said new data block and said existing parity data to form new parity data.
16. A redundant array of independent disk (RAID) memory storage method comprising storing data storage blocks arranged in a first plurality of data rows and a second plurality of data columns, and storing parity data in additionally defined parity blocks, said columns being arranged such that numbers of blocks in respective columns are different;
wherein at least some of said parity data is row parity data placed in row parity blocks in a row parity column wherein at least some of said parity data is diagonal parity data placed in diagonal parity blocks in a diagonal parity column, the method comprising arranging said data storage blocks with a blank diagonal, such that each data column sharing said blank diagonal has one less block than a number of said plurality of rows and said diagonal parity column has a number of blocks equal to said number of said first plurality of data rows.
17. The RAID memory storage method of claim 16 , wherein at least some of said parity data is row parity data placed in row parity blocks in a row parity column.
18. The RAID memory storage method of claim 16 , wherein at least some of said parity data is diagonal parity data placed in diagonal parity blocks in a diagonal parity column.
19. The RAID memory storage method of claim 16 , wherein at least some of said parity data is diagonal parity data placed in a column of diagonal parity data, said diagonal parity column comprising one more block than a number of said first plurality of data rows.
20. The RAID memory storage method of claim 16 , wherein said array comprises a plurality of solid state drives (SSD).
21. The RAID memory storage method of claim 16 , wherein said second plurality of data columns equals a prime number and said first plurality of data rows is one less than said second plurality of data columns.
22. The RAID memory storage method of claim 21 , wherein said second plurality of data columns is equal to a number of disks allowed in said array, and providing, at any given time, an actual number of disks which is less than or equal to said allowed number of disks.
23. The RAID storage method of claim 21 , further comprising adding a new disk to the array and maintaining a balance of parity blocks over said array, the method comprising migrating a selected row parity block to said new disk by retaining said row parity block at an original disk position and defining a zeroed block of data to receive future parity updates for said selected row parity block, and calculating a new diagonal parity block on said new disk.
24. The RAID storage method of claim 16 , further comprising, in the event of single disk failure, using row parity to recover a first plurality of lost data blocks and to use diagonal parity to recover remaining data blocks, thereby to use data blocks already read from said row parity recover to calculate said diagonal parity recovery.
25. The RAID storage method of claim 16 , further comprising, in the event of double disk failure, recovering a first block of a first lost disk in a first, and then succeeding ones, of said rows using diagonal parity and then to recover a first block of a second lost disk in a said first row, and then succeeding rows using row parity data of said first row and then succeeding rows respectively.
26. The RAID storage method of claim 16 , further comprising writing a new data block over an old data block, by reading said old data block and existing parity data, writing said new data block and XORing data of said old data block with data of said new data block and said existing parity data to form new parity data.