Managing parity information for data stored on a storage device

Patent metadata

Field	Value
Publication number	US-11494107-B2
Application number	US-201916381969-A
Country	US
Kind code	B2
Filing date	Apr 11, 2019
Priority date	Apr 11, 2019
Publication date	Nov 8, 2022
Grant date	Nov 8, 2022

Abstract

Disclosed herein are techniques for managing parity information for data stored on a storage device. A method includes (1) receiving a request to store data into the storage device, (2) storing portions of the data in data pages included in stripes in a band of the storage device, where a respective data page is stored on a respective different die of a respective stripe, (3) determining primary parity information for a first stripe including a subset of the data pages, (4) storing the primary parity information in a primary parity page included in a second stripe in the stripes in the band, where the primary parity page is disposed on a next available die relative to dies storing the data pages, (5) determining secondary parity information for the second stripe, and (6) storing the secondary parity information in a secondary parity page included in the stripes in the band.

First claim

What is claimed is:

1. A method for managing parity information for data stored on a non-volatile storage device, the method comprising, at a computing device that has access to the non-volatile storage device:
receiving a request to store the data into the non-volatile storage device;
storing respective portions of the data in a plurality of data pages included in a plurality of stripes in a band of the non-volatile storage device, wherein a respective data page is stored on a respective different die of a respective stripe of the plurality of stripes;
determining primary parity information for a first stripe including a subset of the plurality of data pages;
storing the primary parity information for the first stripe in a primary parity page included in a second stripe in the plurality of stripes in the band, the primary parity page being stored on a die that is a next available die in the band, the next available die being relative to dies storing the plurality of data pages in the plurality of stripes in the band, and the first and second stripes are distinct from one another;
determining secondary parity information for the second stripe including the primary parity page storing the primary parity information;
storing the secondary parity information in a secondary parity page included in the plurality of stripes in the band;
determining second primary parity information for a third stripe of the plurality of stripes, wherein the third stripe includes a second subset of the plurality of data pages; and
storing the second primary parity information in a second primary parity page included in the plurality of stripes in the band, wherein the second primary parity page is stored on another next available die relative to the next available die storing the primary parity page in the plurality of stripes.

2. The method of claim 1 , wherein the second stripe includes a second subset of the plurality of data pages and the primary parity page, and each of the second subset of the plurality of data pages and the primary parity page is stored on another respective different die of the non-volatile storage device.

3. The method of claim 1 , wherein the secondary parity page is stored on another next available die relative to the next available die storing the primary parity page in the plurality of stripes.

4. The method of claim 3 , comprising storing a copy of the secondary parity page in a different secondary parity page included in the plurality of stripes in the band.

5. The method of claim 4 , wherein the different secondary parity page is stored on a different die than the another next available die on which the secondary parity page is stored.

6. The method of claim 4 , wherein the secondary parity page and the different secondary parity page are stored in a third stripe of the plurality of stripes in the band.

7. The method of claim 1 , comprising determining the next available die at which to store the primary parity page based on a number of the plurality of data pages that are storing the respective portions of the data.

8. The method of claim 1 , further comprising:
receiving a second request to store second data into the non-volatile storage device;
determining a data storage size for second data pages for the second data, second primary parity pages for the second data pages, and second secondary parity pages for the second primary parity pages, and second secondary parity page copies for the second secondary parity pages;
determining a second size of available space in the band of the non-volatile storage device;
responsive to determining that the data storage size is less than or equal to the second size, storing the second data pages, the second primary parity pages, the second secondary parity pages, and the second secondary parity page copies in the band; and
responsive to determining that the data storage size exceeds the second size, storing the second data pages, the second primary parity pages, the second secondary parity pages, and the second secondary parity page copies in a second band of the non-volatile storage device.

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 non-volatile storage device that is accessible to the computing device, by carrying out steps that include:
receiving a request to store the data into the non-volatile storage device;
storing respective portions of the data in a plurality of data pages included in a plurality of stripes in a band of the non-volatile storage device, wherein a respective data page is stored on a respective different die of a respective stripe of the plurality of stripes;
determining primary parity information for a first stripe including a subset of the plurality of data pages;
storing the primary parity information for the first stripe in a primary parity page included in a second stripe in the plurality of stripes in the band, the primary parity page being stored on a die that is a next available die in the band, the next available die being relative to dies storing the plurality of data pages in the plurality of stripes in the band, and the first and second stripes are distinct from one another;
determining secondary parity information for the second stripe including the primary parity page storing the primary parity information;
storing the secondary parity information in a secondary parity page included in the plurality of stripes in the band;
determining second primary parity information for a third stripe of the plurality of stripes, wherein the third stripe includes a second subset of the plurality of data pages; and
storing the second primary parity information in a second primary parity page included in the plurality of stripes in the band, wherein the second primary parity page is stored on another next available die relative to the next available die storing the primary parity page in the plurality of stripes.

10. The at least one non-transitory computer readable storage medium of claim 9 , wherein the second stripe includes a third subset of the plurality of data pages and the primary parity page, and each of the third subset of the plurality of data pages and the primary parity page is stored on another respective different die of the non-volatile storage device.

11. The at least one non-transitory computer readable storage medium of claim 9 , wherein the steps further include:
storing a copy of the secondary parity page in a different secondary parity page included in the plurality of stripes in the band.

12. The at least one non-transitory computer readable storage medium of claim 11 , wherein the different secondary parity page is stored on a different die than the another next available die on which the secondary parity page is stored.

13. The at least one non-transitory computer readable storage medium of claim 11 , wherein the secondary parity page and the different secondary parity page are stored in the third stripe of the plurality of stripes in the band.

14. The at least one non-transitory computer readable storage medium of claim 13 , 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 stored on a respective different die of the non-volatile storage device.

15. A computing device configured to manage managing parity information for data stored on a non-volatile storage

Assignees

• Apple Inc

Inventors

• Paley Alexander
• Vogan Andrew W
• Televitckiy Evgeny

Classifications

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F3/065 Primary

  Replication mechanisms · CPC title

• G06F11/108 Primary

  Parity data distribution in semiconductor storages, e.g. in SSD · CPC title

• G06F11/0793

  Remedial or corrective actions (recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40) · CPC title