SECURE DATA STORAGE IN RAID MEMORY DEVICES

• US 20130124776A1
• Filed: 11/15/2011
• Published: 05/16/2013
• Est. Priority Date: 11/15/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: XtremlO Ltd. (Dell Technologies Inc.)
• Inventors: HALLAK, Renen, Segev, Yaron
• Granted Patent: US 8,990,495 B2
• Time in Patent Office: Days
• US Class Current: 711/102
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

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.

Claims

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.

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 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 smaller than the number of said data blocks comprising each diagonal parity set.

10. The RAID memory storage system of claim 1, wherein said array comprises a plurality of solid state drives (SSD).

11. 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.

12. The RAID memory storage system of claim 11, 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.

13. The RAID storage system of claim 11, 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.

14. 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.

15. The RAID storage system of claim 1, further comprising a double disk failure recovery 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.

16. 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 data block with data of said new data block and said existing parity data to form new parity data.

17. 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.

18. The RAID memory storage method of claim 17, wherein at least some of said parity data is row parity data placed in row parity blocks in a row parity column.

19. The RAID memory storage method of claim 17, wherein at least some of said parity data is diagonal parity data placed in diagonal parity blocks in a diagonal parity column.

20. The RAID memory storage method of claim 17, 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.

21. The RAID memory storage method of claim 17, 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.

22. The RAID memory storage method of claim 17, wherein said array comprises a plurality of solid state drives (SSD).

23. The RAID memory storage method of claim 17, 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.

24. The RAID memory storage method of claim 23, 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.

25. The RAID storage method of claim 23, 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.

26. The RAID storage method of claim 17, 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.

27. The RAID storage method of claim 17, 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 said first row, and then succeeding rows using row parity data of said first row and then succeeding rows respectively.

28. The RAID storage method of claim 17, 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.