Nonrepeating identifiers in an address space of a non-volatile solid-state storage

• US 8,868,825 B1
• Filed: 07/02/2014
• Issued: 10/21/2014
• Est. Priority Date: 07/02/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Hayes, John, Davis, John, Gupta, Shantanu, Gold, Brian, Tan, Zhangxi
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): KWONG, EDMUND H
• Application Number:
  US14/322,893
• Time in Patent Office: 111 Days
• Field of Search: 711/103
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 16/16 for erasing blocks, e.g. arrays, words, groups

Abstract

A method of applying an address space to data storage in a non-volatile solid-state storage is provided. The method includes receiving a plurality of portions of user data for storage in the non-volatile solid-state storage and assigning to each successive one of the plurality of portions of user data one of a plurality of sequential, nonrepeating addresses of an address space. The address range of the address space exceeds a maximum number of addresses expected to be applied during a lifespan of the non-volatile solid-state storage. The method includes writing each of the plurality of portions of user data to the non-volatile solid-state storage such that each of the plurality of portions of user data is identified and locatable for reading via the one of the plurality of sequential, nonrepeating addresses of the address space.

Claims

1. A method of applying an address space in a non-volatile solid-state storage, comprising:

receiving user data for storage in the non-volatile solid-state storage;

translating a first address of a portion of the user data in a first address space, to a second address of the portion of the user data in a second address space, wherein addresses in the second address space have a range and a sequence, each address in the second address space applied in keeping with the sequence to a portion of the user data in the non-volatile solid-state storage is different at a time of application from all addresses in the second address space previously applied in keeping with the sequence in the non-volatile solid-state storage to portions of the user data, and the range of the addresses in the second address space is greater than a maximum number of addresses in the second address space expected to be applied during a lifespan of the non-volatile solid-state storage; and

storing the portion of the user data in the non-volatile solid-state storage, with the portion of the user data associated with both the first address and the second address, wherein the second address space is one of a logical address space or a virtual address space, and wherein at least one method operation is performed by a processor.

2. The method of claim 1, wherein storing the portion of the user data in the non-volatile solid-state storage includes:

writing the portion of the user data to non-volatile random access memory (NVRAM) of the non-volatile solid-state storage; and

transferring the portion of the user data from the NVRAM to flash memory of the non-volatile solid-state storage.

3. The method of claim 1, further comprising:

tracking the first address and the second address in an address translation table of the non-volatile solid-state storage.

4. The method of claim 1, further comprising:

assigning a non-overlapping range of the second address space to each of a plurality of non-volatile solid-state storages.

5. The method of claim 1, further comprising:

allocating a range of addresses of the second address space in the non-volatile solid-state storage without synchronization with other non-volatile solid-state storages in a storage cluster that includes the non-volatile solid-state storage.

6. The method of claim 1, further comprising:

writing information relating to the second address to a header of a flash page in a flash memory of the non-volatile solid-state storage, wherein storing the portion of the user data in the non-volatile solid-state storage includes storing the portion of the user data in the flash page.

7. The method of claim 1, further comprising:

separating the user data into a plurality of data segments;

separating each of the plurality of data segments into a plurality of data shards; and

assigning to each of the plurality of data shards a virtual allocation unit as the second address of the portion of the user data, wherein the first address includes an inode number.

8. A method of applying an address space to data storage, comprising:

distributing user data throughout a plurality of storage nodes through erasure coding, wherein the plurality of storage nodes are housed within a chassis that couples the storage nodes as a cluster, each of the plurality of storage nodes having non-volatile solid-state memory for user data storage;

receiving a plurality of portions of user data for storage in the non-volatile solid-state memory;

assigning to each successive one of the plurality of portions of user data one of a plurality of sequential, nonrepeating addresses of an address space, the sequential, nonrepeating addresses having a range that exceeds application of the sequential, nonrepeating addresses in a lifespan of the non-volatile solid-state memory; and

writing each of the plurality of portions of user data to the non-volatile solid-state memory such that each of the plurality of portions of user data is identified and locatable for reading via the one of the plurality of sequential, nonrepeating addresses of the address space, wherein the address space is one of a logical address space or a virtual address space.

9. The method of claim 8, further comprising:

translating file paths of the plurality of portions of user data to inode identifiers (IDs) of the plurality of portions of user data; and

translating the inode IDs of the plurality of portions of user data to medium addresses of the plurality of portions of user data in a medium address space, wherein the address space includes the medium address space.

10. The method of claim 8, further comprising:

translating medium addresses of the plurality of portions of user data to segment addresses of the plurality of portions of user data in a segment address space, wherein the address space includes the segment address space.

11. The method of claim 8, further comprising:

translating segment addresses of the plurality of portions of user data into physical flash memory locations in the non-volatile solid-state memory, wherein writing each of the plurality of portions of user data to the non-volatile solid-state memory includes writing the plurality of portions of user data into flash memory according to the physical flash memory locations.

12. The method of claim 8, wherein the range is at least a binary number having 128 bits.

13. The method of claim 8, further comprising:

erasing a block of pages of a flash memory in the non-volatile solid-state memory, wherein the writing each of the plurality of portions of user data includes writing individual pages in sequential order within a single erased block according to the addresses of the address space.

14. The method of claim 8, further comprising:

storing, in the non-volatile solid-state memory, a snapshot of a version of the user data, the snapshot including reference to the addresses of the address space as associated with the version of the user data; and

reading the non-volatile solid-state memory to recover the version of the user data according to the snapshot.

15. A storage cluster, comprising:

a plurality of storage nodes within a single chassis, each of the plurality of storage nodes having non-volatile solid-state memory for storage of user data, the non-volatile solid-state memory comprising;

a flash memory, configured to store user data; and

a controller coupled to the flash memory and configured to perform actions including;

receiving a plurality of portions of user data for storage in the non-volatile solid-state storage;

assigning to the plurality of portions of user data, in sequence, a plurality of virtual allocation units from an address space of sequential non-repeating virtual allocation units, such that each virtual allocation unit upon assignment to a portion of user data in the non-volatile solid-state storage differs from all previously assigned virtual allocation units in the non-volatile solid-state storage; and

storing the plurality of portions of user data in the non-volatile solid-state storage, with each of the plurality of portions of user data stored according to one of the plurality of virtual allocation units as assigned, wherein the address space is one of a logical address space or a virtual address space.

16. The storage cluster of claim 15, further comprising:

the flash memory further configured to store a mapping table that relates the assigned virtual allocation units of the portions of user data to physical storage locations in the flash memory; and

the controller further configured to translate the assigned virtual allocation units of the portions of user data to the physical storage locations in the flash memory via application of the mapping table.

17. The storage cluster of claim 15, wherein:

a range of virtual allocation units in the address space is assigned to the non-volatile solid-state storage;

ranges of virtual allocation units in the address space, as assigned to a plurality of non-volatile solid-state storages, are non-overlapping; and

the non-volatile solid-state storage is configured to allocate virtual allocation units within the range of virtual allocation units assigned to the non-volatile solid-state storage without synchronization with others of the plurality of non-volatile solid-state storages.

18. The storage cluster of claim 15, further comprising:

a non-volatile random-access memory (NVRAM) coupled to the controller and configured to receive the plurality of portions of user data; and

the controller configured to transfer the plurality of portions of user data from the NVRAM to the flash memory.

19. The storage cluster of claim 15, further comprising:

the flash memory further configured to store a header in a flash page, the header having information relating to the one of the plurality of virtual allocation units and a corresponding one of the plurality of portions of user data stored in the flash page.

20. The storage cluster of claim 15, further comprising:

the controller configured to erase blocks of pages in the flash memory and configured to write pages within an erased block in a sequential order according to the virtual allocation units assigned to the portions of user data in the pages being written.