Apparatus, system, and method for data block usage information synchronization for a non-volatile storage volume

• US 8,935,302 B2
• Filed: 02/23/2010
• Issued: 01/13/2015
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Flynn, David, Atkisson, David, Dixon, Drex, Flynn, Jonathan, Hansen, Brandon
• Primary Examiner(s): Yen, Syling
• Application Number:
  US12/711,113
• Publication Number:
  US 20100211737A1
• Time in Patent Office: 1,785 Days
• Field of Search: 707/813, 707/610, 707/661, 707/674, 707/814, 707/816, 707/817, 707/818, 707/819, 707/820, 707/999.206, 707/999.204, 711/111, 709/227
• US Class Current: 707/813
• 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 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 21/78 to assure secure storage of data address-based protection against unauthorised use of memory G06F12/14; record carriers for use with machines and with at least a part designed to carry digital markings G06K19/00
• CPC Class Codes: G06F 2206/1014 One time programmable [OTP] memory, e.g. PROM, WORM
• CPC Class Codes: G06F 2211/103 Hybrid, i.e. RAID systems with parity comprising a mix of RAID types
• 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/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• 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/0665 at area level, e.g. provisioning of virtual or logical volumes
• 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/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 12/403 with centralised control, e.g. polling
• 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]

Abstract

An apparatus, system, and method are disclosed for data block usage information synchronization for a non-volatile storage volume. The method includes referencing first data block usage information for data blocks of a non-volatile storage volume managed by a storage manager. The first data block usage information is maintained by the storage manager. The method also includes synchronizing second data block usage information managed by a storage controller with the first data block usage information maintained by the storage manager. The storage manager maintains the first data block usage information separate from second data block usage information managed by the storage controller.

Claims

1. A method, comprising:

referencing logical block usage information of a storage manager in response to one or more of a trigger condition and a pre-determined schedule, wherein the logical block usage information is maintained by the storage manager and is configured to associate objects managed by the storage manager with respective logical block addresses corresponding to a non-volatile storage volume managed by a storage controller, wherein data of the objects are stored on the non-volatile storage volume, and wherein the storage controller is configured to maintain logical-to-physical block usage information that translates logical block addresses to corresponding physical storage locations within the non-volatile storage volume; and

synchronizing the logical-to-physical block usage information maintained by the storage controller in response to the referenced logical block usage information maintained by the storage manager, wherein the logical-to-physical block usage information is maintained by the storage controller separate from the logical block usage information maintained by the storage manager, and

wherein synchronizing the logical-to-physical block usage information comprises identifying a logical block address that was previously associated with an object managed by the storage manager, such that the identified logical block address translates to a physical storage location in the logical-to-physical block usage information maintained by the storage controller, and issuing a message to the storage controller indicating that the identified logical block address no longer references object data.

2. The method of claim 1, wherein synchronizing the logical-to-physical block usage information further comprises,

determining that one or more logical block addresses not in use to reference object data based on the referenced logical block usage information;

and

sending a message directly to the storage controller that indicates the one or more determined logical block addresses.

3. The method of claim 1, wherein synchronizing the logical-to-physical block usage information further comprises removing a mapping between a physical storage location and a logical block address.

4. The method of claim 1, wherein synchronizing the logical-to-physical block usage information further comprises removing an entry from an index maintained by the storage controller that associates an unused logical block address with a physical address within the non-volatile storage volume.

5. The method of claim 1, further comprising updating an in-flight index in response to storage operations executed by the storage controller subsequent to referencing the logical block usage information and executed by the storage controller prior to synchronizing the logical-to-physical block usage information in response to the referenced logical block usage information.

6. The method of claim 1, wherein referencing the logical block usage information comprises referencing the logical block usage information by way of a storage Application Programming Interface (“

API”

) of the storage manager.

7. The method of claim 1, wherein the non-volatile storage volume comprises a live volume actively servicing storage requests.

8. The method of claim 1, wherein the storage controller comprises a redundant array of independent drives (“

RAID”

) controller configured to store data in a RAID configuration on two or more storage devices, and wherein synchronizing the logical-to-physical block usage information comprises synchronizing logical-to-physical block usage information of the two or more storage devices in response to the referenced logical block usage information, the two or more storage devices managed by the RAID controller.

9. The method of claim 8, further comprising,

determining a RAID configuration of the RAID controller;

and

synchronizing logical-to-physical block usage information managed for the two or more storage devices in response to the referenced logical block usage information based on the determined RAID configuration.

10. The method of claim 8, wherein the RAID controller manages one or more sub-controllers, each sub-controller storing data on the two or more storage devices.

11. The method of claim 8, wherein the RAID configuration comprises a RAID 0 configuration that stores data as a stripe across the two or more storage devices, wherein synchronizing the logical-to-physical block usage information comprises,

identifying a first portion of the referenced logical block usage information corresponding to data blocks stored on a first storage device;

identifying a second portion of the referenced logical block usage information corresponding to data blocks stored on a second storage device;

synchronizing logical-to-physical block usage information managed for the first storage device with the first portion of the referenced logical block usage information; and

synchronizing logical-to-physical block usage information managed for the second storage device with the second portion of the referenced logical block usage information.

12. The method of claim 8, wherein the RAID configuration comprises a RAID 1 configuration that mirrors data stored on a first storage device to a second storage device, wherein synchronizing the logical-to-physical block usage information comprises,

synchronizing logical-to-physical block usage information managed for the first storage device with the referenced logical block usage information;

and

synchronizing logical-to-physical block usage information managed for the second storage device with the referenced logical block usage information.

13. The method of claim 8, wherein the RAID configuration comprises a RAID 5 configuration that stores data as a stripe across three or more storage devices, the stripe comprising two or more data strides and a distributed parity data stride, each data stride stored on a storage device and each data stride comprising one or more data blocks, wherein synchronizing the logical-to-physical block usage information comprises,

determining that each data stride in the stripe comprises no object data based on the referenced logical block usage information;

and

synchronizing logical-to-physical block usage information managed by the RAID controller for the stripe by designating data blocks of the second data block usage information corresponding to the stripe as unused.

14. The method of claim 8, wherein the RAID configuration comprises a RAID 10 configuration that mirrors a stride of data between two or more storage devices using a RAID 1 configuration and that stores stripes of data across two or more storage device sets using a RAID 0 configuration, wherein synchronizing logical-to-physical block usage information comprises,

identifying a first portion of the referenced logical block usage information corresponding to data blocks stored in a first stride managed by the RAID controller;

identifying a second portion of the referenced logical block usage information corresponding to data blocks stored in a second stride managed by the RAID controller;

synchronizing logical-to-physical block usage information managed for the first stride with the first portion of the referenced logical block usage information; and

synchronizing logical-to-physical block usage information managed for the second stride with the second portion of the referenced logical block usage information.

15. A computer program product comprising a non-transitory computer readable storage medium having computer usable program code executable to perform operations, comprising:

referencing a block map defining logical block usage information pertaining to logical data blocks corresponding to a non-volatile storage medium in response to one or more of a trigger condition and a pre-determined schedule, the block map maintained by a storage manager to associate file data managed by the storage manager with respective logical data blocks, wherein the non-volatile storage medium is managed by a storage controller, and wherein the storage controller is configured to map logical data blocks to physical blocks on the non-volatile storage medium;

identifying a set of one or more logical data blocks that are not associated with file data managed by the storage manager by use of the referenced block map, wherein one or more of the identified logical data blocks are associated with respective physical blocks on the non-volatile storage medium by the storage controller; and

sending a message to the storage controller managing the non-volatile storage medium, the message indicating the identified set of logical data blocks that are not associated with file data managed by the storage manager.

16. The computer program product of claim 15, the operations further comprising invalidating data stored on one or more physical blocks on the non-volatile storage medium that are mapped to logical data blocks indicated in the message.

17. The computer program product of claim 15, the operations further comprising removing an entry corresponding to the set of logical data blocks that are not associated with file data managed by the storage manager from a logical-to-physical map maintained by the storage controller.

18. The computer program product of claim 15, wherein the file data comprises one of:

data of a file, a file object, a directory, and file system metadata.

19. The computer program product of claim 18, wherein identifying the set of logical data blocks that are not associated with the file data managed by the storage manager further comprises,

monitoring storage operations pertaining to the logical data blocks subsequent to referencing the block map and prior to sending the message to the storage controller;

and

updating the set of logical data blocks that are not associated with the file data managed by the storage manager in response to the monitored storage operations, such that the message sent to the storage controller indicates the updated set of logical data blocks that are not associated with the file data.

20. The computer program product of claim 19, the operations further comprising recording logical block usage information corresponding to the monitored storage operations in an in-flight block map, wherein updating the set of logical data blocks that are not associated with the file data managed by the storage manager comprises combining the referenced block map and the in-flight block map.

21. The computer program product of claim 15, the operations further comprising:

obtaining a lock on a logical-to-physical map maintained by the storage controller to associate logical data blocks with physical blocks on the non-volatile storage medium prior to identifying the set of logical data blocks that are not associated with file data managed by the storage manager; and

releasing the lock on the logical-to-physical map subsequent to the storage controller deallocating one or more mappings between physical blocks on the non-volatile storage medium and logical data blocks that are not associated with file data managed by the storage manager.

22. The computer program product of claim 15, wherein the message complies with an interface that communicates notifications to the storage controller, the notifications identifying logical data blocks that are not associated with file data managed by the storage manager, wherein the notifications comprise no requirement for action by the storage controller in accordance with the interface.

23. The computer program product of claim 15, wherein the message complies with an interface for communicating directives to the storage controller, the directives identifying logical data blocks, wherein the directives require the storage controller to erase physical blocks on the non-volatile storage medium that comprise data associated with logical data blocks specified in the directives in accordance with the interface.

24. The computer program product of claim 15, wherein the message complies with an interface to communicate information pertaining to the logical data blocks to the storage controller, the message comprising a purge instruction that requires the storage controller to erase data associated with the set of logical data blocks indicated in the message from the non-volatile storage medium in accordance with the interface.

25. The computer program product of claim 15, wherein the storage controller comprises a redundant array of independent drives (“

RAID”

) controller storing data in a RAID configuration on two or more storage devices managed by the RAID controller.

26. The computer program product of claim 25, wherein sending the message to the storage controller comprises sending one or more messages communicating the set of logical data blocks that are not associated with the file data managed by the storage manager to one or more sub-controllers.

27. The computer program product of claim 25, wherein the RAID configuration comprises a RAID 0 configuration that stores data as a stripe across the two or more storage devices, the operations further comprising,

identifying a first portion of the referenced block map corresponding to logical data blocks associated with physical blocks of a first storage device managed by the RAID controller;

identifying a second portion of the referenced block map corresponding to logical data blocks associated with physical blocks of a second storage device managed by the RAID controller; and

wherein sending the message to the storage controller comprises,

sending a first message to the RAID controller, the first message identifying one or more logical data blocks that are not associated with file data managed by the storage manager and are identified by the first portion of the referenced block map,

and sending a second message to the RAID controller, the second message identifying one or more logical data blocks that are not associated with file data managed by the storage manager and are identified by the second portion of the referenced block map.

28. The computer program product of claim 25, wherein the RAID configuration comprises a RAID 1 configuration that mirrors data stored on a first storage device to a second storage device, wherein sending the message to the storage controller comprises,

sending a first message to the RAID controller managing the first storage device, the first message identifying the set of logical data blocks that are not associated with file data managed by the storage manager and are associated with physical blocks of the first storage device;

and

sending a second message to the RAID controller managing the second storage device, the second message identifying the set of logical data blocks that are not associated with file data managed by the storage manager and are associated with physical blocks of the second storage device.

29. The computer program product of claim 25, wherein the RAID configuration comprises a RAID 5 configuration that stores data as a stripe across three or more storage devices, the stripe comprising two or more data strides and a distributed parity data stride, each data stride stored on a storage device and each data stride comprising one or more data blocks, the operations further comprising,

determining that each data stride in the stripe comprises no logical data blocks in use to reference file data managed by the storage manager based on the referenced block map;

and

wherein sending the message to the storage controller comprises sending the message to the RAID controller, the message designating physical data blocks corresponding to the stripe as unused.

30. The computer program product of claim 25, wherein the RAID configuration comprises a RAID 10 configuration that mirrors a stride of data between two or more storage devices using a RAID 1 configuration and that stores stripes of data across two or more storage device sets using a RAID 0 configuration, the operations further comprising,

identifying a first portion of the referenced block map corresponding to logical data blocks associated with physical blocks in a first stride managed by the RAID controller;

and

identifying a second portion of the referenced block map corresponding to logical data blocks associated with physical blocks in a second stride managed by the RAID controller;

wherein sending the message to the storage controller comprises,

sending a first message to the RAID controller managing the first stride, the message identifying one or more logical data blocks that are not associated with file data managed by the storage manager and are associated with physical blocks in the first stride, and

sending a second message to the RAID controller managing the second stride, the second message identifying one or more logical data blocks that are not associated with file data managed by the storage manager and are associated with physical blocks in the second stride.

31. A system, comprising:

a processor;

a memory in communication with the processor;

a block-oriented volume comprising a plurality of logical blocks in communication with the memory, wherein the block-oriented volume corresponds to a non-volatile storage device;

a storage controller that stores data corresponding to the logical blocks of the block-oriented volume on the non-volatile storage device, and maintains a logical-to-physical translation layer that associates logical blocks of the block-oriented volume with corresponding physical storage locations of the non-volatile storage device;

a storage manager that maintains a block map defining logical block usage information pertaining to the block-oriented volume, wherein the logical block usage information associates logical blocks of the block-oriented volume with files managed by the storage manager, and wherein the logical-to-physical translation layer maintained by the storage controller associates logical blocks corresponding to the files managed by the storage manager with physical storage locations of the non-volatile storage device storing data of the files; and

a block usage synchronizer that determines logical block usage information pertaining to the block-oriented volume by use of the block map maintained by the storage manager in response to one or more of a trigger condition and a pre-determined schedule, and synchronizes the logical-to-physical translation layer maintained by the storage controller based on the determined logical block usage information by deallocating an association between a physical storage location of the non-volatile storage device and a logical block of the block-oriented volume that the determined logical block usage information indicates is not in use to reference data of a file managed by the storage manager.

32. The system of claim 31, wherein the system further comprises an interface for communicating storage information to the storage controller, and wherein the block usage synchronizer is configured to send a message complying with the interface to the storage controller, the message prompting the storage controller to synchronize logical-to-physical block usage information managed by the storage controller based on the determined logical block usage information.

33. The system of claim 31, wherein the block usage synchronizer is initiated in response to one or more predetermined events.

34. The system of claim 31, wherein the block usage synchronizer is initiated at a predetermined time interval.

35. An apparatus, comprising:

a reference module that references logical block usage information of a storage manager in response to one or more of a trigger condition and a pre-determined schedule, wherein the logical block usage information is maintained by the storage manager and is configured to associate objects managed by the storage manager with respective logical block addresses corresponding to a non-volatile storage volume managed by a storage controller, wherein data of the objects are stored on the non-volatile storage volume, and wherein the storage controller is configured to maintain logical-to-physical block usage information that translates logical block addresses to corresponding physical storage locations within the non-volatile storage volume; and

a block usage synchronizer that synchronizes the logical-to-physical block usage information maintained by the storage controller in response to the referenced logical block usage information maintained by the storage manager, wherein the logical-to-physical block usage information is maintained by the storage controller separate from the logical block usage information maintained by the storage manager, wherein synchronizing the logical-to-physical block usage information comprises identifying a logical block address that was previously associated with an object managed by the storage manager, such that the identified logical block address translates to a physical storage location in the logical-to-physical block usage information maintained by the storage controller, and issuing a message to the storage controller indicating that the identified logical block address no longer references object data.

36. The apparatus of claim 35, wherein the storage manager is configured to deallocate a physical address mapped to the identified logical block address in response to the message.

37. The apparatus of claim 35, wherein the reference module is configured to reference the logical block usage information through a defragmentation interface.