Apparatus, system, and method for identifying data that is no longer in use

• US 8,533,406 B2
• Filed: 09/07/2012
• Issued: 09/10/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, Thatcher, Jonathan, Zappe, Michael
• Primary Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US13/607,486
• Publication Number:
  US 20130024642A1
• Time in Patent Office: 368 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 a non-volatile storage medium. A storage controller receives a message that identifies data that no longer needs to be retained on the non-volatile storage medium. The data may be identified using a logical identifier. The message may comprise a hint, directive, or other indication that the data has been erased and/or deleted. In response to the message, the storage controller records an indication that the contents of a physical storage location and/or physical address associated with the logical identifier do not need to be preserved on the non-volatile storage medium.

Claims

1. A method for managing data stored on non-volatile storage media, the method comprising:

receiving a message, at a storage controller, comprising a logical identifier, the message indicating that a storage client has deleted a block associated with the logical identifier such that data of the logical identifier does not need to be preserved on a non-volatile storage medium, wherein the logical identifier is associated with a physical storage location on the non-volatile storage medium; and

indicating that contents of the physical storage location do not need to be preserved on the non-volatile storage medium in response to the message.

2. The method of claim 1, wherein indicating comprises deleting an index entry that associates the logical identifier with the physical storage location.

3. The method of claim 1, wherein indicating comprises deleting a mapping between the logical identifier and the physical storage location.

4. The method of claim 1, wherein indicating comprises invalidating an association between the logical identifier and an address of the physical storage location.

5. The method of claim 1, further comprising maintaining an index of mappings between logical identifiers and physical storage locations, wherein indicating comprises removing a mapping between the logical identifier and the physical storage location from the index.

6. The method of claim 1, wherein indicating comprises marking the contents of the physical storage location invalid.

7. The method of claim 1, wherein receiving comprises receiving the message from a block storage client.

8. The method of claim 1, wherein receiving comprises receiving the message through a block storage application programming interface.

9. The method of claim 1, wherein receiving comprises receiving the message via a block storage protocol.

10. The method of claim 1, further comprising erasing the contents of the physical storage location in a storage recovery process.

11. A method, comprising:

receiving, at a storage driver configured to maintain mappings between logical identifiers and physical addresses of a non-volatile storage device, an indication comprising a logical identifier corresponding to data that does not need to be preserved on the non-volatile storage device, wherein the logical identifier is associated with a storage client data identifier, and wherein the logical identifier is mapped to a physical storage location of the data on the non-volatile storage device in an index; and

removing a mapping between the logical identifier and the physical address of the data of the specified logical identifier on the non-volatile storage device in response to the indication comprising the logical identifier, wherein removal of the mapping indicates that the data corresponding to the logical identifier does not need to be preserved on the non-volatile storage device.

12. The method of claim 11, further comprising erasing a storage division comprising the data in a storage recovery process.

13. The method of claim 11, further comprising invalidating a data packet in response to receiving the indication.

14. The method of claim 11, wherein receiving comprises receiving the indication from one of a file system, operating system, storage client, and storage application, and wherein the indication comprises one of a hint, a message, a command, and a directive.

15. An apparatus, comprising:

a non-volatile storage medium;

a request receiver module of a storage layer for the non-volatile storage medium configured to receive an indication that a data structure, corresponding to data stored on the non-volatile storage medium, has been deleted, wherein the indication comprises a logical identifier that is associated with the data structure by a storage client, and wherein the logical identifier is mapped to a physical address of the data on the non-volatile storage medium; and

a marking module configured to record that the data stored at the physical address mapped to the logical identifier can be erased from the non-volatile storage medium in response to receiving the indication.

16. The apparatus of claim 15, wherein the marking module is configured to record that data stored at a physical address on the non-volatile storage medium can be erased from the non-volatile storage medium by invalidating an association between the logical identifier and the physical address.

17. The apparatus of claim 15, wherein the marking module is configured to record that data stored at a physical address on the non-volatile storage medium can be erased from the non-volatile storage medium by deleting a mapping between the logical identifier and the physical address.

18. The apparatus of claim 15, further comprising an index comprising mappings between logical identifiers and physical addresses on the non-volatile storage medium, wherein the marking module is configured to remove a mapping between the logical identifier and the physical addresses of the data from the index.

19. The apparatus of claim 18, wherein the marking module is configured to delete a reference to the physical address from an index entry of the logical identifier.

20. The apparatus of claim 18, wherein removal of the mapping indicates that data stored at the physical address can be erased from the non-volatile storage medium.

21. The apparatus of claim 15, wherein the marking module is configured to mark a data packet at the physical address invalid.

22. The apparatus of claim 15, further comprising a request receiver module configured to receive the hint, wherein the request receiver module comprises a driver.

23. The apparatus of claim 15, further comprising a request receiver module configured to receive the hint from a file system, the file system configured to send the hint in response to deletion of file system data associated with the logical identifier.

24. The apparatus of claim 15, further comprising a request receiver module configured to receive the hint from a file system, the file system configured to issue the hint in response to removal of a file associated with the logical identifier.

25. The apparatus of claim 15, further comprising a request receiver module configured to receive the hint from an application, wherein the application is configured to send the hint in response to determining that data associated with the logical identifier no longer needs to be retained on the non-volatile storage medium.

26. The apparatus of claim 15, wherein the non-volatile storage medium comprises a flash storage medium, the apparatus further comprising:

a storage recovery module configured to recover the physical storage location at the physical address; and

a storage module configured to store data associated with another logical identifier on the physical storage location in response to recovering the physical storage location.

27. A system comprising:

a flash storage medium; and

a storage layer for the flash storage medium, comprising;

an index module configured to maintain an index comprising a plurality of entries, wherein the individual entries associate a logical identifier with a physical storage location of the flash storage medium that comprises data associated with the logical identifier; and

a request receiver module configured to receive an indication comprising a logical identifier that is empty, wherein the logical identifier is associated with a data identifier of a storage client, and wherein the logical identifier is associated with a physical storage location in the index,

wherein the index module is configured to update the index, in response to the indication, to indicate that contents of the physical storage location associated with the logical identifier do not need to be preserved on the flash storage medium, wherein the index module is configured to update the index by one or more of (a) removing an entry from the index that associates the specified logical identifier with the physical storage location, and (b) adding an entry to the index.

28. The system of claim 27, further comprising a storage recovery module configured to erase a storage division comprising the physical storage location in response to removing the entry.

29. The system of claim 27, wherein the indication comprises a command, wherein the request receiver module is configured to receive the command through one of a block device interface and via a block storage protocol, and wherein the system further comprises a storage division recovery module configured to recover physical storage locations comprising invalid data.

30. A system, comprising:

a flash storage medium;

an index module configured to maintain an index comprising a plurality of entries, wherein the individual entries associate a logical identifier with a physical storage location of the flash storage medium that comprises data associated with the logical identifier;

a request receiver module configured to receive an indication that a specified logical identifier is empty, wherein the logical identifier is associated with a data identifier of a storage client, and wherein the logical identifier is associated with a physical storage location in the index,

wherein the index module is configured to update the index, in response to the indication, to indicate that contents of the physical storage location associated with the logical identifier do not need to be preserved on the flash storage medium, wherein the index module is configured to update the index by one or more of (a) removing an entry from the index that associates the specified logical identifier with the physical storage location, and (b) adding an entry to the index; and

a read request response module configured to return an indication that the logical identifier is empty in response to a request to read data of the logical identifier while the data remains on the flash storage medium.