Techniques for managing parity information for data stored on a storage device

Patent metadata

Field	Value
Publication number	US-10379949-B2
Application number	US-201715721267-A
Country	US
Kind code	B2
Filing date	Sep 29, 2017
Priority date	Sep 29, 2017
Publication date	Aug 13, 2019
Grant date	Aug 13, 2019

Abstract

Disclosed herein are techniques for managing parity information for data stored on a storage device. According to some embodiments, the method includes the steps of (1) receiving a request to store data into the storage device, (2) writing respective portions of the data into a plurality of data pages included in a first stripe of the storage device, where each data page is stored on a respective different die of the storage device, (3) calculating primary parity information for the first stripe, (4) writing the primary parity information into a primary parity page included in a second stripe of the storage device, (5) calculating secondary parity information for the second stripe, and (6) writing the secondary parity information into a secondary parity page included in a third stripe of the storage device. Additionally, a copy of the secondary parity information can be established to further-enhance redundancy.

First claim

What is claimed is:

1. A method for managing parity information for data stored on a storage device, the method comprising, at a computing device that has access to the storage device:
receiving a request to store data onto the storage device;
writing respective portions of the data into a plurality of data pages included in a first stripe of the storage device, wherein each data page of the plurality of data pages is disposed on a different die of the storage device;
calculating primary parity information for the first stripe;
writing the primary parity information into a primary parity page included in a second stripe of the storage device;
calculating secondary parity information for the second stripe;
writing the secondary parity information into a secondary parity page included in a third stripe of the storage device; and
writing a copy of the secondary parity page into a different secondary parity page included in the third stripe, wherein the different secondary parity page is disposed on a different die than the die on which the secondary parity page is disposed.

2. The method of claim 1 , wherein the second stripe includes a plurality of primary parity pages in which the primary parity page is included, and each primary parity page of the plurality of primary parity pages is disposed on a respective different die of the storage device.

3. The method of claim 1 , wherein the third stripe includes a plurality of secondary parity pages in which the secondary parity page is included, and each secondary parity page of the plurality of secondary parity pages is disposed on a respective different die of the storage device.

4. The method of claim 3 , wherein the different secondary parity page is included in the plurality of secondary parity pages.

5. The method of claim 3 , wherein the third stripe further includes at least one primary parity page that is disposed among the plurality of secondary parity pages.

6. The method of claim 1 , wherein:
(i) the first stripe is logically disposed within a first band, and
(ii) the second and third stripes are logically disposed in a second band that is distinct from the first band.

7. The method of claim 1 , wherein writing the data into the plurality of data pages included in the first stripe comprises:
attempting to write a respective portion of the data into a particular data page of the plurality of data pages;
identifying that an underlying portion of a first die to which the particular data page corresponds is inaccessible;
identifying a next data page having a corresponding underlying portion of a second die that is accessible; and
writing the respective portion of the data into the next data page.

8. The method of claim 7 , wherein the next data page is included in a subsequent stripe that is distinct from the first stripe.

9. At least one non-transitory computer readable storage medium configured to store instructions that, when executed by at least one processor included in a computing device, cause the computing device to manage parity information for data stored on a storage device that is accessible to the computing device, by carrying out steps that include:
receiving a request to store data onto the storage device;
writing respective portions of the data into a plurality of data pages included in a first stripe of the storage device, wherein each data page of the plurality of data pages is disposed on a different die of the storage device;
calculating primary parity information for the first stripe;
writing the primary parity information into a primary parity page included in a second stripe of the storage device;
calculating secondary parity information for the second stripe;
writing the secondary parity information into a secondary parity page included in a third stripe of the storage device; and
writing a copy of the secondary parity page into a different secondary parity page included in the third stripe, wherein the different secondary parity page is disposed on a different die than the die on which the secondary parity page is disposed.

10. The at least one non-transitory computer readable storage medium of claim 9 , wherein the second stripe includes a plurality of primary parity pages in which the primary parity page is included, and each primary parity page of the plurality of primary parity pages is disposed on a respective different die of the storage device.

11. The at least one non-transitory computer readable storage medium of claim 9 , wherein the third stripe includes a plurality of secondary parity pages in which the secondary parity page is included, and each secondary parity page of the plurality of secondary parity pages is disposed on a respective different die of the storage device.

12. The at least one non-transitory computer readable storage medium of claim 11 , wherein the different secondary parity page is included in the plurality of secondary parity pages.

13. The at least one non-transitory computer readable storage medium of claim 11 , wherein the third stripe further includes at least one primary parity page that is disposed among the plurality of secondary parity pages.

14. The at least one non-transitory computer readable storage medium of claim 9 , wherein:
(i) the first stripe is logically disposed within a first band, and
(ii) the second and third stripes are logically disposed in a second band that is distinct from the first band.

15. The at least one non-transitory computer readable storage medium of claim 9 , wherein writing the data into the plurality of data pages included in the first stripe comprises:
attempting to write a respective portion of the data into a particular data page of the plurality of data pages;
identifying that an underlying portion of a first die to which the particular data page corresponds is inaccessible;
identifying a next data page having a corresponding underlying portion of a second die that is accessible; and
writing the respective portion of the data into the next data page.

16. The at least one non-transitory computer readable storage medium of claim 15 , wherein the next data page is included in a subsequent stripe that is distinct from the first stripe.

17. A computing device configured to manage partial parity information for data stored on a storage device that is accessible to the computing device, the computing device comprising:
at least one processor; and
at least one memory storing instructions that, when executed by the at least one processor, cause the computing device to:
receive a request to store data onto the storage device;
write respective portions of the data into a plurality of data pages included in a first stripe of the storage device, wherein each data page of the plurality of data pages is disposed on a different die of the storage device;
identify that the first stripe is incompletely written;
calculate partial parity information for the first stripe;
write the partial parity information into a first partial parity page included in a second stripe of the storage device; and
write a copy of the partial parity information into a second partial parity page included in the second stripe of the storage device.

18. The computing device of claim 17 , wherein the first partial parity page is disposed on a first die of the storage device, and the second partial parity page is disposed on a second die of the storage device.

19. The computing device of claim 17 , wherein the second stripe includes at least one log page.

20. The com

Assignees

• Apple Inc

Inventors

• Televitckiy Evgeny
• Paley Alexander
• Vogan Andrew W

Classifications

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F3/0644

  Management of space entities, e.g. partitions, extents, pools · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title