Apparatus, system, and method for storage space recovery in solid-state storage

• US 8,402,201 B2
• Filed: 12/06/2007
• Issued: 03/19/2013
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Lagerstedt, Bert, Strasser, John, Thatcher, Jonathan, Walker, John, Zappe, Michael
• Primary Examiner(s): Dudek, Jr., Edward
• Assistant Examiner(s): DARE, RYAN A
• Application Number:
  US11/952,101
• Publication Number:
  US 20080183953A1
• Time in Patent Office: 1,930 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 1/183 Internal mounting support structures, e.g. for printed circuit boards, internal connecting means for buses G06F13/409
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 13/426 using an embedded synchronisation, e.g. Firewire bus, Fibre Channel bus, SSA bus
• CPC Class Codes: G06F 2211/002 Bus
• CPC Class Codes: G06F 2211/103 Hybrid, i.e. RAID systems with parity comprising a mix of RAID types
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/70 Details relating to dynamic memory management
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 : Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0604 : Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 : Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 : in relation to throughput
• CPC Class Codes: G06F 3/0619 : in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 : Management of files
• CPC Class Codes: G06F 3/065 : Replication mechanisms
• CPC Class Codes: G06F 3/0652 : Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0656 : Data buffering arrangements
• CPC Class Codes: G06F 3/0659 : Command handling arrangements, e.g. command buffers, queues, command scheduling
• 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/0685 : Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0688 : Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 9/52 : Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/54 : Interprogram communication
• CPC Class Codes: H04L 67/02 : based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 : Complex or three-dimensional-arrangements; Stepped or dual mother boards
• CPC Class Codes: H05K 7/1487 : Blade assemblies, e.g. blade cases or inner arrangements within a blade
• CPC Class Codes: Y02D 10/00 : Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

An apparatus, system, and method are disclosed for storage space recovery in solid-state storage. A sequential storage module sequentially writes data packets in a storage division. The storage division includes a portion of a solid-state storage. The data packets are derived from an object. The data packets are sequentially stored by order of processing. A storage division selection module selects a storage division for recovery. A data recovery module reads valid data packets from the storage division selected for recovery, queues the valid data packets with other data packets to be written sequentially, and updates an index with a new physical address of the valid data. The index includes a mapping of physical addresses of data packets to object identifiers. A storage division recovery module marks the storage division selected for recovery as available for sequentially writing data packets in response to completing copying valid data from the storage division.

Claims

1. A method for managing a solid-state storage device, the method comprising:

configuring a storage controller to;

write data to sequential storage locations by order of processing within sequentially ordered storage divisions of a solid-state storage device,

select one of the storage divisions for recovery,

write valid data from the selected storage division on a different storage division that is available for storing data, and

recover the selected storage division by erasing the selected storage division and marking the selected storage division with a sequence indicator, wherein sequence indicators of the storage divisions determine an ordered sequence of the storage divisions, and wherein a sequential order of data storage locations within the storage divisions determines an ordered sequence of storage operations.

2. The method of claim 1, further comprising configuring the storage controller to:

receive a storage request identifying a data operation on the solid-state storage device; and

read the valid data from the selected storage division, wherein the storage controller is configured to select the storage division for recovery and read the valid data from the selected storage division autonomously with servicing the storage request.

3. The method of claim 1, wherein the storage controller receives a storage request identifying data to store on the solid-state storage device, and wherein the method further comprises configuring the storage controller to write the valid data from the selected storage division sequentially on the different storage division together with at least a portion of the data identified in the storage request.

4. The method of claim 1, further comprising configuring the storage controller to mark the selected storage division in response to erasing the selected storage division.

5. The method of claim 1, further comprising reconstructing an index of data stored on the solid-state storage device based on the sequential order of data storage locations within the storage divisions.

6. The method of claim 1, wherein the solid-state storage device comprises a plurality of solid-state storage elements, each solid-state storage element comprising a plurality of storage divisions, the method further comprising configuring the storage controller to write the valid data on two or more of the solid-state storage elements in parallel.

7. The method of claim 1, further comprising configuring the storage controller to:

include at least a portion of the valid data in an error-correcting code (ECC) block, the ECC block comprising an error-correcting code configured to correct an error in the ECC block,

write a first portion of the ECC block on a first one of a plurality of solid-state storage elements of the solid-state storage device; and

write a second portion of the ECC block on a second one of the solid-state storage elements.

8. The method of claim 1, wherein the solid-state storage device comprises a write data buffer configured to store data of a plurality of virtual storage locations of the solid-state storage device, the virtual storage locations comprising storage locations on each of a plurality of parallel solid-state storage elements, the method further comprising configuring the storage controller to:

fill out the write data buffer with a portion of the valid data such that the write data buffer comprises data that fills a selected one of the virtual storage locations; and

write contents of the write data buffer to the selected virtual storage location on the solid-state storage device.

9. The method of claim 1, further comprising configuring the storage controller to select the storage division for recovery by one of identifying a storage division comprising a threshold of invalid data, identifying a storage division comprising data satisfying a refresh threshold, identifying a storage division with a low amount of wear, identifying a storage division with a high amount of wear, and identifying an unreliable storage division.

10. The method of claim 1, further comprising configuring the storage controller to select the storage division for recovery by identifying a storage division with a low amount of wear by one of identifying a storage division with a low amount of invalid data, identifying a storage division with a short erase time, identifying a storage division with a short program time, identifying a storage division with a low program count, and identifying a storage division with a low error rate.

11. The method of claim 1, further comprising configuring the storage controller to select the storage division for recovery by identifying a storage division with a high amount of wear by one of identifying a storage division with a high number of erase cycles, identifying a storage division with a high error rate, and identifying a storage division with a non-recoverable error-correcting code (ECC) block.

12. The method of claim 1, further comprising configuring the storage controller to select the storage division for recovery by identifying an unreliable storage division based on one of a storage division error rate, a storage division erase count, a non-recoverable error-correcting code (ECC) block, and a storage division failure.

13. The method of claim 1, wherein the solid-state storage device comprises a plurality of solid-state storage elements configured in parallel to form a plurality of virtual storage divisions, each virtual storage division comprising a storage division of each of the solid-state storage elements, the method further comprising configuring the storage controller to remap a new storage division to replace a particular storage division in a first one of the virtual storage divisions.

14. The method of claim 13, further comprising configuring the storage controller to replace the particular storage division from a plurality of storage divisions of a second one of the virtual storage divisions.

15. The method of claim 1, wherein the solid-state storage device comprises a write data pipeline to process data to store on the solid-state storage device through a plurality of stages, the method further comprising configuring the storage controller to:

bypass at least one of the write data pipeline stages with the valid data from the selected storage division, and

write the valid data sequentially on the different storage division of the solid-state storage device with other data processed by the write data pipeline.

16. The method of claim 1, further comprising configuring the storage controller to distinguish a valid data segment stored on a first storage division from one or more invalid data segments of the specified logical identifier stored on the first storage division based upon a sequential order of data segment storage locations within the first storage division.

17. The method of claim 1, further comprising configuring the storage controller to distinguish a valid data segment of a specified logical identifier from one or more invalid data segments of the specified logical identifier by use of the sequence identifiers of the storage divisions and the sequential order of data storage locations within the storage divisions.

18. The method of claim 1, wherein the selected storage division is a virtual storage division that comprises storage divisions of each of a plurality of solid-state storage elements.

19. A computer program product comprising a non-transitory computer readable storage medium having computer usable program code executable to perform operations for managing a solid-state storage device, the operations of the computer program product comprising:

writing data to sequential storage locations by order of processing within sequentially ordered storage divisions of a solid-state storage device;

selecting one of a plurality of storage divisions of the solid-state storage device for recovery;

writing valid data of the selected solid-state storage division to sequential storage locations of a different storage division of the solid-state storage device that is available for storing data; and

recovering the selected storage division by erasing the selected storage division and marking the selected storage division with a sequence indicator, wherein sequence indicators of the storage divisions determine an ordered sequence of the storage divisions, and wherein a sequential order of data storage locations within the storage divisions determines an ordered sequence of storage operations.

20. The computer program product of claim 19, wherein writing the valid data comprises sequentially writing the valid data on the different storage division of the solid-state storage device with the data identified in the storage request to store data on the solid-state storage device such that an ordered sequence of storage operations completed on the solid-state storage media is preserved on the solid-state storage media.

21. The computer program product of claim 19, wherein a portion of the valid data of the selected storage division is written sequentially on the different storage division together with at least a portion of data identified in a storage request to store data on the solid-state storage media.

22. The computer program product of claim 19, the operations further comprising:

reconstructing an index of data stored on the solid-state storage media, wherein reconstructing the index comprises distinguishing a valid data segment of a logical identifier from one or more invalid data segments of the logical identifier by use of the sequence indicators on the storage divisions and the sequential order of data segment storage locations within the storage divisions.

23. The computer program product of claim 19, the operations further comprising:

including at least a portion of the valid data in an error-correcting code (ECC) block, the ECC block comprising an error-correcting code configured to correct an error in the ECC block;

writing a first portion of the ECC block on a first one of a plurality of solid-state storage elements; and

writing a second portion of the ECC block on a second one of the solid-state storage elements.

24. The computer program product of claim 19, wherein the solid-state storage media is communicatively coupled to a write data buffer configured to buffer data to write to one of a plurality of virtual storage locations of the solid-state storage device, the virtual storage locations comprising storage locations on each of a plurality of parallel solid-state storage elements, the operations further comprising:

filling out the write data buffer with a portion of the valid data such that the write data buffer comprises data to fill a selected one of the virtual storage locations; and

writing contents of the write data buffer to the selected virtual storage location on the solid-state storage device responsive to a single programming command.

25. The computer program product of claim 19, wherein the solid-state storage device comprises a plurality of solid-state storage elements configured in parallel to form a plurality of virtual storage divisions, each virtual storage division comprising a storage division of each of the solid-state storage elements, the operations further comprising:

remapping a first storage division of a first virtual storage division to replace a storage division in a second virtual storage division.

26. The computer program product of claim 19, wherein writing the valid data further comprises,

bypassing at least one stage of a write data pipeline with the valid data read from the selected storage division, and

writing the valid data sequentially on the different storage division of the solid-state storage media with data processed by the write data pipeline.

27. An apparatus for managing a solid-state storage device, comprising:

a sequential storage module configured to store data segments in sequential storage locations by order of processing within respective sequentially ordered storage divisions of a solid-state storage medium;

a storage division selection module configured to select one of the storage divisions for recovery, wherein the sequential storage module is configured to write valid data segments of the selected storage division sequentially to a different storage division that is available for storing data; and

an erase module configured to recover the selected storage division by erasing the selected storage division and marking the selected storage division with a sequence indicator,

wherein sequence indicators of the storage divisions determine an ordered sequence of the storage divisions, and wherein a sequential order of data segment storage locations within the respective storage divisions determines an ordered sequence of storage operations, an

wherein the storage division sequence indicators and the sequential order of data segment storage locations within the respective storage divisions distinguish a valid data segment of a specified logical identifier from one or more data segments associated with the specified logical identifier on the solid-state storage medium.

28. The apparatus of claim 27, wherein a portion of the valid data is written sequentially on the different storage division together with at least a portion of the data identified in a storage request.

29. The apparatus of claim 27, further comprising a reconstruction module configured to reconstruct a map of data stored on the solid-state storage medium using the sequence indicators of the storage divisions and the sequential order of data segment storage locations within the storage divisions.

30. The apparatus of claim 27, wherein the sequential order of data segment storage locations on a first one of the storage divisions distinguishes a valid data segment of a specified logical identifier stored on the first storage division from one or more invalid data segments of the specified logical identifier stored on the first storage division.

31. A system for managing a solid-state storage device, comprising:

means for selecting one of a plurality of storage divisions of a solid-state storage medium for recovery;

means for storing data segments sequentially in sequential storage locations within respective storage divisions of the solid-state storage medium, the data segments comprising valid data of the selected storage division; and

means for recovering the selected storage division by erasing the selected storage division and marking the selected storage division with a sequence indicator, wherein sequence indicators of the plurality of storage divisions and a sequential order of data segment storage locations within the respective storage divisions distinguishes a valid data segment of a specified logical identifier from one or more data segments associated with the specified logical identifier on the solid-state storage medium.