RAID ERASURE CODE APPLIED TO PARTITIONED STRIPE

• US 20140208022A1
• Filed: 01/21/2013
• Published: 07/24/2014
• Est. Priority Date: 01/21/2013
• Status: Active Grant

• Current Assignee: Kaminario Limited
• Original Assignee: Kaminario Limited
• Inventors: GORDON, Eyal
• Granted Patent: US 9,495,246 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

The disclosure presents examples of a RAID storage system, method and computer program product where a stripe is logically partitioned into two or more sub-stripes and at least one RAID erasure code is applied to each sub-stripe independently of any other of the sub-stripe(s). Consequently, in some of these examples, a larger packet size may be used than if the stripe had not been partitioned. A larger packet size may in some cases allow for accelerated encoding and/or decoding.

Claims

1. A system, comprising:

a Redundant Array of Independent Disks, RAID, controller capable of logically partitioning a stripe into two or more sub-stripes, and of applying at least one RAID erasure code to each of said sub-stripes independently of any other of said sub-stripes.

2. The system of claim 1, further comprising:

a plurality of storage devices;

wherein said RAID controller is capable of writing or reading said stripe to or from any of said plurality of storage devices.

3. The system of claim 1, wherein each sub-segment associated with a same sub-stripe has identical size.

4. The system of claim 1, wherein a size of a sub-segment associated with one of said sub-stripes differs from a size of a sub-segment associated with another of said sub-stripes.

5. The system of claim 1, wherein two sub-segments associated with two different sub-stripes have identical size.

6. The system of claim 1, wherein at least one selected from a group comprising:

number of packets or size of packets, differs for different sub-stripes.

7. The system of claim 1, wherein at least one selected from a group comprising:

number of packets or size of packets, is identical for at least two different sub-stripes.

8. The system of claim 1, wherein a size of a sub-segment associated with a sub-stripe does not equal a power of two.

9. The system of claim 1, wherein a size of a sub-segment associated with a sub-stripe equals a power of two.

10. The system of claim 1, wherein said RAID controller is capable of determining values of packet size and number of packets to use per sub-stripe.

11. The system of claim 10, wherein said RAID controller being capable of determining values of packet size and number of packets to use per sub-stripe, includes said RAID controller being capable of selecting from among available sets which each includes values for any of packet size, number of packets, or sub-segment size per sub-stripe, at least partly based on at least one factor selected from a group comprising:

segment size in stripe, type of said at least one RAID erasure code, number of data segments in stripe, testing data relating to acceleration of RAID erasure code application, in-turn selection, or random selection.

12. The system of claim 10, wherein there is available to said RAID controller only one set including values for any of packet size, number of packets, or sub-segment size per sub-stripe, and wherein said RAID controller being capable of determining values of packet size and number of packets to use per sub-stripe, includes said RAID controller being capable of determining to use said set.

13. The system of claim 10, wherein said RAID controller being capable of determining values of packet size and number of packets to use per sub-stripe includes said RAID controller being capable of deriving a value of packet size or sub-segment size to use per sub-stripe from an available set corresponding to a different segment size than segment size of said stripe.

14. The system of claim 10, being capable of determining values of packet size and number of packets to use per sub-stripe, includes said RAID controller being capable of computing a value for packet size or number of packets from an available set which includes values for sub-segment size and number of packets or packet size respectively.

15. The system of claim 10, wherein said RAID controller being capable of determining values of packet size and number of packets to use per sub-stripe includes said RAID controller being capable of determining values to use for decoding at least partly based on values which were used for encoding.

16. The system of claim 1, wherein said RAID controller is capable of determining at least one possible set including values for any of packet size, number of packets, or sub-segment size per sub-stripe which complies with at least one predetermined constraint.

17. The system of claim 16, wherein said at least one predetermined constraint is selected from a group comprising:

number of packets per sub-segment of sub-stripe is greater than or equal to number of data segments, number of packets per sub-segment of sub-stripe is greater than or equal to number of data segments minus 1, number of packets per sub-segment of sub-stripe is equal to a prime number minus 1, packet size per sub-stripe is equal to a power of 2, or sum of sub-stripe sub-segment sizes is equal to stripe segment size.

18. The system of claim 1, wherein said RAID controller being capable of applying at least one RAID erasure code includes said RAID controller being capable of encoding said sub-stripe in order to compute at least one parity sub-segment.

19. The system of claim 1, wherein said RAID controller being capable of applying at least one RAID erasure code includes said RAID controller being capable of decoding at least one parity sub-segment in said sub-stripe.

20. The system of claim 1, wherein said RAID controller being capable of applying at least one RAID erasure code includes said RAID controller being capable of applying different RAID erasure codes to different ones of said sub-stripes.

21. A method performed by a Redundant Array of Independent Disks, RAID, controller, comprising:

logically partitioning a stripe into two or more sub-stripes, and

applying at least one RAID erasure code to each of said sub-stripes independently of any other of said sub-stripes.

22. The method of claim 21, wherein said applying includes encoding said sub-stripe in order to compute at least one parity sub-segment.

23. The method of claim 21, wherein said applying includes decoding at least one parity sub-segment in said sub-stripe.

24. The method of claim 21, further comprising:

determining values of packet size and number of packets to use per sub-stripe.

25. The method of claim 21, further comprising:

determining at least one possible set including values for any of packet size, number of packets or sub-segment size per sub-stripe which complies with at least one predetermined constraint.

26. The method of claim 21, further comprising:

reading said stripe from storage devices prior to said partitioning.

27. The method of claim 21, further comprising:

writing said stripe to storage devices after said applying.

28. A computer program product comprising a non-transitory computer readable medium having Redundant Array of Independent Disks, RAID computer readable program code embodied therein the computer program product comprising:

computer readable program code for causing a computer to logically partition a stripe into two or more sub-stripes, and

computer readable program code for causing a computer to apply at least one RAID erasure code to each of said sub-stripes independently of any other of said sub-stripes.