Systems and methods for persistent deallocation

• US 8,762,658 B2
• Filed: 08/03/2012
• Issued: 06/24/2014
• 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
• Primary Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US13/566,471
• Publication Number:
  US 20120331206A1
• Time in Patent Office: 690 Days
• Field of Search: 711/154, 711/E12.002, 707/692
• US Class Current: 711/154
• 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 managing data with an empty data segment directive at the storage device. The apparatus, system, and method for managing data include a write request receiver module and a data segment token storage module. The write request receiver module receives a storage request from a requesting device. The storage request includes a request to store a data segment in a storage device. The data segment includes a series of repeated, identical characters or a series of repeated, identical character strings. The data segment token storage module stores a data segment token in the storage device. The data segment token includes at least a data segment identifier and a data segment length. The data segment token is substantially free of data from the data segment.

Claims

1. An apparatus for managing data stored on a non-volatile storage medium, comprising:

a non-volatile storage medium;

a request receiver module configured to receive a message comprising a logical identifier, the message indicating that data associated with the logical identifier has been erased, wherein the logical identifier is mapped to a physical storage location of the non-volatile storage medium; and

a storage module configured to store persistent data on the non-volatile storage medium in response to the indication, wherein the persistent data is configured to indicate that the data associated with the logical identifier is erased.

2. The apparatus of claim 1, further comprising an index reconstruction module configured to reconstruct mappings between logical identifiers and physical storage locations of the non-volatile storage medium from contents of the non-volatile storage medium, wherein the reconstruction module is configured indicate that data of the logical identifier are erased based on the persistent data stored on the non-volatile storage medium.

3. The apparatus of claim 1, further comprising:

an index comprising mappings between logical identifiers and physical storage locations of the non-volatile storage medium; and

an index reconstruction module configured to reconstruct the mappings using contents of the non-volatile storage medium, wherein the index reconstruction module is configured to indicate that data associated with the logical identifier are erased based on the persistent data stored on the non-volatile storage medium.

4. The apparatus of claim 1, further comprising:

an index comprising a plurality of index entries comprising mappings between logical identifiers and physical storage locations of the non-volatile storage medium; and

an index reconstruction module configured to reconstruct the index entries from data stored on the non-volatile storage medium, wherein the index reconstruction module is configured to record an indication that data associated with the logical identifier are erased based on the persistent data stored on the non-volatile storage medium.

5. The apparatus of claim 4, wherein the index reconstruction module is configured to update the index to indicate that the data associated with the logical identifier are erased.

6. The apparatus of claim 4, wherein the indication comprises an index entry.

7. The apparatus of claim 4, wherein the indication comprises removing an entry from the index.

8. The apparatus of claim 1, further comprising a read request module configured to return an indication that the data of the logical identifier are erased in response a request pertaining to the logical identifier received while the data associated with the logical identifier remains on the physical storage location of the non-volatile storage medium.

9. The apparatus of claim 1, further comprising a marking module configured to record that contents of the physical storage location associated with the logical identifier no longer need to be retained on a non-volatile storage medium in response to the indication.

10. The apparatus of claim 1, further comprising a marking module configured to invalidate an index entry configured to associate the logical identifier with the physical storage location in response to the indication.

11. The apparatus of claim 1, further comprising a storage recovery module configured to recover a storage division comprising the physical storage location in response to the indication.

12. The apparatus of claim 1, further comprising an erase module configured to erase the physical storage location in response to the indication.

13. A system, comprising:

a processor;

an index module configured for operation on the processor, wherein the index module is configured to maintain an index comprising associations between logical identifiers and physical storage locations used to store data corresponding to the logical identifiers on a non-volatile storage medium;

a request receiver module configured to receive a hint comprising a logical identifier, wherein the hint is configured to indicate that data of the logical identifier associated with a physical storage location in the index has been deleted; and

a storage module configured to store a packet on the non-volatile storage medium configured to indicate that contents of the physical storage location have been deleted in response to the hint.

14. The system of claim 13, further comprising an index module configured to update the index to invalidate the association between the logical identifier and the physical storage location in response to the hint.

15. The system of claim 14, wherein the index module is configured to remove an entry that maps the logical identifier to the physical storage location from the index in response to the hint.

16. The system of claim 13, further comprising an index reconstruction module configured to reconstruct the associations between the logical identifiers and the physical storage locations, wherein the index reconstruction module is configured to record that data associated with the logical identifier has been deleted based on the packet.

17. The system of claim 13, wherein the packet comprises one of an erase packet and a data segment token.

18. The system of claim 13, wherein the packet indicates that data of a plurality of logical identifiers have been deleted.

19. The system of claim 13, further comprising a storage controller, wherein the storage controller comprises the processor.

20. The system of claim 13, wherein the non-volatile storage medium comprises a flash storage medium.

21. The system of claim 13, wherein the non-volatile storage medium comprises a NAND flash storage medium.

22. A non-transitory computer-readable storage medium comprising instructions configured to cause a computing device to perform a method, comprising:

maintaining an index comprising mappings between logical identifiers and physical storage locations of a non-volatile storage device;

receiving an indication, comprising a logical identifier, that the logical identifier mapped to a physical storage location comprising data associated with the logical identifier in the index is empty; and

recording persistent data on the non-volatile storage device in response the indication, wherein the persistent data is configured to indicate that the logical identifier is empty.

23. The non-transitory computer-readable storage medium of claim 22, the method further comprising invalidating a data packet in response to the indication.

24. The non-transitory computer-readable storage medium of claim 22, the method further comprising removing the mapping between the logical identifier and the physical storage location from the index in response to the indication.

25. The non-transitory computer-readable storage medium of claim 22, the method further comprising reconstructing the index based on the contents of the non-volatile storage medium, wherein reconstructing comprises determining that the logical identifier is empty in response to the persistent data recorded on the non-volatile storage device while the data associated with the logical identifier remains on the physical storage location.

26. The non-transitory computer-readable storage medium of claim 22, further comprising responding to a request pertaining to the logical identifier with an indication the logical identifier is empty while the data associated with the logical identifier remains on the physical storage location.