Granted Patent B2

US 10,379,948 · App. 15/722,685 · Granted Aug 13, 2019

Abstract

Claims (71)

1. A system comprising:

a plurality of non-volatile storage devices, wherein each non-volatile storage device comprises:

a device controller; and

a plurality of non-volatile memory cells configured with internal addresses;

non-transitory storage;

a data collecting module configured to collect, for each chunk of a redundancy coding stripe, data for the chunk;

a command module configured to issue a command to write the data for the chunk of the redundancy coding stripe to a selected non-volatile storage device of the plurality of non-volatile storage devices using a virtual block address;

an interface configured to receive, for each chunk of the redundancy coding stripe, an internal address of the chunk in the selected non-volatile storage device from the selected non-volatile storage device; and

a redundancy coding module configured to store into the non-transitory storage a redundancy stripe map having a redundancy stripe identifier and the internal addresses in the non-volatile storage devices for the chunks of the redundancy coding stripe.

2. The system of claim 1 , further comprising a data recovery module configured to:

send a request to a first non-volatile memory device of the plurality of non-volatile storage devices for a chunk of the redundancy coding stripe, wherein the request specifies the internal address of the chunk.

3. The system of claim 1 , further comprising logic configured to instruct at least one non-volatile storage device of the plurality of non-volatile storage devices to store, into non-volatile storage in the at least one non-volatile storage device, a forward map that maps from virtual block addresses to redundancy stripe identifiers.

4. The system of claim 3 , further comprising a data recovery module configured to:

read the forward map from the non-volatile storage in a non-volatile storage device to retrieve a redundancy stripe identifier for a target virtual block address;

use the retrieved redundancy stripe identifier to retrieve internal addresses for target chunks in the plurality of non-volatile storage devices from the redundancy stripe map; and

request target chunks of data from the plurality of non-volatile storage devices, the requests for the target chunks specifying the retrieved internal addresses.

5. The system of claim 1 , wherein:

each of the chunks of data comprises a plurality of blocks of random data, wherein each of the plurality of blocks has an external logical address; and

a first of the plurality of non-volatile storage devices further comprises:

an address mapping module configured to:

map the external logical addresses associated with a chunk of data to sequential internal addresses in the first non-volatile storage device; and

store the mapping in non-transitory storage in the first non-volatile storage device.

6. The system of claim 1 , wherein a first non-volatile storage device of the plurality of non-volatile storage devices comprises:

writing logic configured to write the entire chunk of the redundancy coding stripe to a contiguous region of the plurality of non-volatile memory cells in the first non-volatile storage device; and

address providing logic configured to provide, to the interface, the internal address at which the chunk was written in the first non-volatile storage device.

7. The system of claim 1 , wherein the internal address that a first non-volatile storage device of the plurality of non-volatile storage devices provides for a first chunk in the redundancy coding stripe is a first internal logical address.

8. The system of claim 7 , wherein the first non-volatile storage device further comprises:

non-transitory storage;

writing logic configured to move the first chunk that is stored in a first contiguous region of the plurality of non-volatile memory cells in the first non-volatile storage device to a second contiguous region of the plurality of non-volatile memory cells in the first non-volatile storage device; and

an address mapping module configured to update, in the non-transitory storage of the first non-volatile storage device, a mapping of the first internal logical address from the first contiguous region to the second contiguous region.

9. The system of claim 8 , wherein:

the first contiguous region is all or a portion of a first erase block in the first non-volatile storage device; and

the second contiguous region is all or a portion of a second erase block in the first non-volatile storage device.

10. The system of claim 1 , wherein each of the chunks of data comprises a plurality of blocks of random data each with an external logical block address, and further comprising drive virtualization logic configured to:

for each virtual block address associated with one of the external logical block addresses sent in a write request to one of the plurality of non-volatile storage devices, convert the virtual block address to one of the external logical block addresses and an identifier of one of the plurality of non-volatile storage devices.

11. The system of claim 1 , wherein the command to write the data for the chunk of the redundancy coding stripe in the selected non-volatile storage device instructs the selected non-volatile storage device to write the entire chunk within all or a portion of an erase block.

12. A method comprising:

receiving, at each of a plurality of non-volatile storage devices, a request to write a chunk of a redundancy coding stripe;

writing, by each of the plurality of non-volatile storage devices, the entire chunk to a contiguous region of non-volatile memory cells in the respective non-volatile storage device;

providing, by each of the plurality of non-volatile storage devices, a fixed internal address of the chunk in an internal address space of the respective non-volatile storage device;

sending, by each of the plurality of non-volatile storage devices, the fixed internal address to a manager system including non-transitory storage; and

storing a redundancy stripe map into non-transitory storage, the redundancy stripe map having a redundancy stripe identifier and the fixed internal addresses for the chunks for the redundancy coding stripe.

13. The method of claim 12 , further comprising:

sending, from the manager system, a request to a first non-volatile storage device of the plurality of non-volatile storage devices for a chunk of the redundancy coding stripe, wherein the request specifies the fixed internal address of the chunk.

14. The method of claim 13 , further comprising:

instructing at least one non-volatile storage device of the plurality of non-volatile storage devices to store, into non-volatile storage in the at least one non-volatile storage device, a forward map that maps from virtual block addresses to redundancy stripe identifiers.

15. The method of claim 14 , further comprising:

reading the forward map from the non-volatile storage in the at least one non-volatile storage device to retrieve a redundancy stripe identifier for a virtual block address;

using the retrieved redundancy stripe identifier to retrieve fixed internal addresses in the redundancy stripe map; and

requesting chunks of data from the plurality of non-volatile storage devices, the requests for the chunks specifying the retrieved fixed internal addresses.

16. The method of claim 12 , further comprising:

collecting, by the manager system, random writes for each of the chunks of the redundancy coding stripe; and

sending, by the manager system, commands to write all of the random writes for each of the chunks in a contiguous region on each of the plurality of non-volatile storage devices.

17. The method of claim 16 , wherein the contiguous region is an erase block.

18. A non-volatile storage system comprising:

a plurality of non-volatile storage devices, wherein each non-volatile storage device comprises:

a device controller; and

a plurality of non-volatile memory cells configured with internal addresses;

non-transitory storage;

data collecting means for collecting random writes for each chunk of a redundancy coding stripe;

command means for sending, to each of the plurality of non-volatile storage devices, a command to write one of the chunks of random writes within a contiguous region of the plurality of non-volatile memory cells in each respective non-volatile storage device;

writing means for writing each respective chunk of the redundancy coding stripe in a contiguous region of the plurality of non-volatile memory cells in each respective non-volatile storage device;

address providing means for providing, for each of the chunks, an internal address at which the chunk was written in the respective non-volatile storage device; and

redundancy coding means for storing into the non-transitory storage a redundancy stripe map having a redundancy stripe identifier and the internal addresses for the chunks for the redundancy coding stripe.

19. The non-volatile storage system of claim 18 , wherein the writing means is further for:

writing a forward map to non-volatile memory in a first non-volatile storage device of the plurality of non-volatile storage devices, wherein the forward map translates from virtual block addresses to redundancy stripe identifiers.

20. The non-volatile storage system of claim 19 , further comprising data recovery means for:

reading the forward map from the non-volatile storage in the first non-volatile storage device to retrieve a redundancy stripe identifier for a virtual block address;

using the retrieved redundancy stripe identifier to retrieve internal addresses in the redundancy stripe map;

requesting chunks of data from the plurality of non-volatile storage devices, the requests for the chunks specifying the retrieved internal addresses; and

recovering a chunk of a redundancy coding stripe based on chunks returned from the plurality of non-volatile storage devices in response to the requests specifying the retrieved internal addresses.

Assignments (10)