APPARATUS, SYSTEM, AND METHOD FOR STORAGE SPACE RECOVERY IN SOLID-STATE STORAGE

• US 20080183953A1
• Filed: 12/06/2007
• Published: 07/31/2008
• 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, Thatcher, Jonathan, Zappe, Michael, Lagerstedt, Bert, Strasser, John, Walker, John
• Granted Patent: US 8,402,201 B2
• Time in Patent Office: Days
• 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. An apparatus for storage recovery, the apparatus comprising:

a sequential storage module that sequentially writes data packets in a storage division, the storage division comprising a portion of a solid-state storage in a solid-state storage device, the data packets derived from an object, the data packets sequentially stored by order of processing;

a storage division selection module that selects a storage division for recovery;

a data recovery module that reads valid data packets from the storage division selected for recovery, queues the valid data packets with other data packets to be written sequentially by the sequential storage module, and updates an index with a new physical address of the valid data written by the sequential storage module, the index comprising a mapping of physical addresses of data packets stored in the solid-state storage to object identifiers corresponding to the data packets; and

a storage division recovery module that marks the storage division selected for recovery as available to the sequential storage module for sequentially writing data packets, the storage division marked for recovery in response to the data recovery module completing copying valid data from the storage division.

2. The apparatus of claim 1, wherein the sequential storage module, the storage division selection module, the data recovery module, and the storage division recovery module are in a solid-state storage device controller within the solid-state storage device and the object index is located in the solid-state storage device and created and maintained by the solid-state storage device controller.

3. The apparatus of claim 1, wherein the storage division comprises an erase block and further comprising an erase module that erases an erase block selected for recovery prior to the storage division recovery module marking the erase block available for recovery, erasing an erase block selected for recovery in response to the data recovery module copying valid data packets from the selected erase block.

4. The apparatus of claim 3, wherein the solid-state storage is arranged in two or more banks and the erase module erases an erase block in a first bank while the sequential storage module writes data packets to a storage division in a second bank.

5. The apparatus of claim 3, wherein the solid-state storage is arranged in two or more banks and the erase module erases an erase block in a first bank while data is read from a storage division in a second bank.

6. The apparatus of claim 1, wherein the storage division selection module, the data recovery module, and the storage division recovery module operate autonomously.

7. The apparatus of claim 1, further comprising a garbage marking module that identifies a data packet in a storage division as invalid in response to an operation indicating that the data packet is no longer valid.

8. The apparatus of claim 7, wherein the data packet in the storage division is a first data packet and an operation indicating that the first data packet is no longer valid comprises writing a second data packet to the solid-state storage device that the first data packet is invalid.

9. The apparatus of claim 7, wherein an operation indicating that the data packet is no longer valid comprises one of a delete operation and a read-modify-write operation, the delete operation signifying that the data packet is to be deleted and the read-modify-write operation comprising reading the data packet, modifying the data packet, and writing the modified data packet to another location, the modified data packet written to another location by the sequential storage module.

10. The apparatus of claim 7, wherein identifying a data packet as invalid comprises modifying an entry in the object index to indicate that the data packet is invalid.

11. The apparatus of claim 1, wherein the storage division selection module selects a storage division for recovery by identifying a storage division with a low amount of wear.

12. The apparatus of claim 11, wherein identifying a storage division with a low amount of wear comprises identifying a storage division with a low amount of invalid data.

13. The apparatus of claim 11, wherein identifying a storage division with a low amount of wear comprises identifying a storage division with a low number of erase cycles.

14. The apparatus of claim 11, wherein identifying a storage division with a low amount of wear comprises identifying a storage division with a low program count, wherein a program comprises writing data packets to a designated page within the storage division.

15. The apparatus of claim 11, wherein identifying a storage division with a low amount of wear comprises identifying a storage division with a low bit error rate.

16. The apparatus of claim 1, wherein the storage division selection module selects a storage division for recovery by identifying a storage division with a high amount of wear.

21. The apparatus of claim 1, wherein the storage division selection module selects a storage division for recovery by identifying a storage division with a high amount of invalid data.

22. The apparatus of claim 1, wherein the storage division selection module selects a storage division for recovery by identifying a storage division using a combination of two or more of program count, erase cycle count, bit error rate, amount of invalid data, erase cycles, and a non-recoverable ECC block.

23. The apparatus of claim 1, wherein the solid-state storage is arranged in an array of storage elements and a storage division comprises a virtual storage division that includes a storage division within each storage element in a row of storage elements accessed together.

17. The apparatus of claim 17, wherein identifying a storage division with a high amount of wear comprises identifying a storage division with a high number of erase cycles.

18. The apparatus of claim 17, wherein the storage division recovery module marks the storage division selected for recovery as unavailable for storing data.

19. The apparatus of claim 17, wherein identifying a storage division with a high amount of wear comprises identifying a storage division with a high bit error rate.

20. The apparatus of claim 19, wherein identifying a storage division with a high bit error rate comprises identifying a storage division with a non-recoverable error-correcting code (“

ECC”

) block.

24. A system for storage recovery, the system comprising:

a solid-state storage device comprising a solid-state storage, the solid-state storage comprising one or more storage divisions, each storage division comprising a portion of the solid-state storage in a solid-state storage device, the solid-state storage device comprising

a sequential storage module that sequentially writes data packets in a storage division, the data packets derived from an object, the data packets sequentially stored by order of processing;

a storage division selection module that selects a storage division for recovery;

a data recovery module that reads valid data packets from the storage division selected for recovery, queues the valid data packets with other data packets to be written sequentially by the sequential storage module, and updates an index with a new physical address of the valid data written by the sequential storage module, the index comprising a mapping of physical addresses of data packets stored in the solid-state storage to object identifiers corresponding to the data packets; and

a storage division recovery module that marks the storage division selected for recovery as available to the sequential storage module for sequentially writing data packets, the storage division marked for recovery in response to the data recovery module completing copying valid data from the storage division.

25. A computer program product comprising a computer readable medium having computer usable program code executable to perform operations for storage recovery, the operations of the computer program product comprising:

sequentially writing data packets in a storage division, the storage division comprising a portion of a solid-state storage in a solid-state storage device, the data packets derived from an object, the data packets sequentially stored by order of processing;

selecting a storage division for recovery;

reading valid data packets from the storage division selected for recovery;

queuing the valid data packets with other data packets queued to be written sequentially;

updating an index with a new physical address of the valid data written by the sequential storage module, the index comprising a mapping of physical addresses of data packets stored in the solid-state storage to object identifiers corresponding to the data packets; and

marking the storage division selected for recovery as available for sequentially writing data packets, the storage division marked for recovery in response to completing copying valid data from the storage division.

26. The computer program product of claim 25, wherein the storage division comprises an erase block and further comprising

erasing an erase block selected for recovery prior to the storage division recovery module marking the erase block available for recovery, erasing an erase block selected for recovery in response to copying valid data packets from the selected erase block;

and

identifying a data packet in a storage division as invalid in response to an operation indicating that the data packet is no longer valid.