APPARATUS, SYSTEM, AND METHOD FOR DATA BLOCK USAGE INFORMATION SYNCHRONIZATION FOR A NON-VOLATILE STORAGE VOLUME

• US 20100211737A1
• Filed: 02/23/2010
• Published: 08/19/2010
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Longitude Enterprise Flash S.à r.l. (Vector Capital Corporation)
• Inventors: Flynn, Jonathan, Hansen, Brandon, Dixon, Drex, Flynn, David, Atkisson, David
• Granted Patent: US 8,935,302 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• 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 for data block usage information synchronization for a non-volatile storage volume, the method comprising:

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 maintained by the storage manager;

synchronizing second data block usage information managed by a storage controller with the first data block usage information maintained by the storage manager; and

wherein the storage manager maintains the first data block usage information separate from the second data block usage information managed by the storage controller.

2. The method of claim 1, wherein synchronizing data block usage information further comprises,

determining one or more unused blocks from the first data block usage information;

and

sending a message directly to the storage controller managing the non-volatile storage volume, the message indicating to the storage controller unused blocks identified by the storage manager, the storage controller deallocating the unused blocks identified by the storage manager in response to the message.

3. The method of claim 1, wherein synchronizing second data block usage information further comprises deallocating blocks identified by the storage controller as used blocks corresponding to one or more unused blocks identified by the storage manager based on the first data block usage information.

4. The method of claim 1, wherein synchronizing data block usage information further comprises determining that the storage controller identifies one or more used blocks indicated by the first data block usage information as unused blocks and deallocating the used blocks identified by the storage controller corresponding to the one or more unused blocks.

5. The method of claim 1, further comprising updating the first data block usage information based on storage operations that modify the first data block usage information, the storage operations executed by the storage controller subsequent to referencing the first data block usage information and executed by the storage controller prior to synchronizing the second data block usage information to the first data block usage information.

6. The method of claim 1, wherein referencing the first data block usage information further comprises referencing the first data 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 storing data in a RAID configuration on two or more storage devices and synchronizing second data block usage information synchronizes second data block usage information managed for the two or more storage devices with the first data 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 second data block usage information managed for the two or more storage devices with the first data 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 second data block usage information comprises,

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

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

synchronizing second data block usage information managed for the first storage device with the first portion of the first data block usage information; and

synchronizing second data block usage information managed for the second storage device with the second portion of the first data block usage information.

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

synchronizing second data block usage information managed for the first storage device with the first data block usage information;

and

synchronizing second data block usage information managed for the second storage device with the first data 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 second data block usage information comprises,

determining that each data stride in the stripe comprises no used blocks based on the first data block usage information;

and

synchronizing second data 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 minors 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 second data block usage information comprises,

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

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

synchronizing second data block usage information managed for the first stride with the first portion of the first data block usage information; and

synchronizing second data block usage information managed for the second stride with the second portion of the first data block usage information.

15. A computer program product comprising a computer readable storage medium having computer usable program code executable to perform operations for data management on non-volatile storage media managed by a storage manager, the operations of the computer program product comprising:

referencing a block map defining data block usage information for data blocks of non-volatile storage media managed by a storage manager, the block map maintained by the storage manager; and

sending a message to a storage controller managing the non-volatile storage media, the message identifying to the storage controller one or more unused blocks identified by the block map.

16. The computer program product of claim 15, further comprising deallocating used blocks identified by the storage controller corresponding to the one or more unused blocks identified by the storage manager in response to the message.

17. The computer program product of claim 15, further comprising determining that the storage controller identifies the one or more unused blocks from the block map as used blocks and deallocating the used blocks identified by the storage controller corresponding to the one or more unused blocks in the block map in response to the message.

18. The computer program product of claim 15, further comprising determining one or more unused blocks from the block map.

19. The computer program product of claim 18, wherein determining one or more unused blocks from the block map comprises,

monitoring storage operations on data blocks represented by the block map, the storage operations executed by the storage controller subsequent to referencing the block map and executed by the storage controller prior to deallocating the one or more unused blocks in response to the message;

and

recording data block usage information for the storage operations that change unused blocks of the block map to used blocks.

20. The computer program product of claim 19, wherein recording data block usage information for the storage operations further comprises recording the data block usage information in an in-flight block map, the computer program product further comprising combining the block map and the in-flight block map to identify the one or more unused blocks of the data blocks.

21. The computer program product of claim 15, further comprising obtaining a lock on a logical-to-physical map managed by the storage controller prior to determining one or more unused blocks from the block map and releasing the lock on the logical-to-physical map subsequent to the storage controller deallocating the unused blocks, the storage controller configured to store data on the non-volatile storage media using an append-only writing process and configured to recover storage space on the non-volatile storage media using a storage space recovery process that re-uses non-volatile storage media storing blocks that have become unused blocks.

22. The computer program product of claim 15, wherein the message complies with an interface operable to communicate storage information between the storage manager and the storage controller, the message comprising a notification passing the unused blocks identified by the storage manager to the storage controller, the notification comprising 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 operable to communicate storage information between the storage manager and the storage controller, the message comprising a directive passing the unused blocks identified by the storage manager to the storage controller, the directive requiring the storage controller to erase the non-volatile storage media comprising the unused blocks in accordance with the interface.

24. The computer program product of claim 15, wherein the message complies with an interface operable to communicate storage information between the storage manager and the storage controller, the message comprising a purge instruction passing the unused blocks identified by the storage manager to the storage controller, the purge instruction requiring the storage controller to erase the non-volatile storage media comprising the unused blocks and to overwrite the unused blocks 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 a message to the storage controller comprises sending one or more messages communicating the unused blocks identified 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 computer program product further comprising,

identifying a first portion of the block map corresponding to data blocks stored on a first storage device managed by the RAID controller;

identifying a second portion of the block map corresponding to data blocks stored on a second storage device managed by the RAID controller; and

wherein sending a message to the storage controller comprises sending a first message to the RAID controller, the first message identifying one or more unused blocks on the first storage device identified by the first portion of the block map and sending a second message to the RAID controller, the second message identifying one or more unused blocks on the second storage device identified by the second portion of the block map.

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

sending a first message to the RAID controller managing the first storage device, the first message identifying one or more unused blocks on the first storage device identified by the block map;

and

sending a second message to the RAID controller managing the second storage device, the second message identifying one or more unused blocks on the second storage device identified by the block map.

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 computer program product further comprising,

determining that each data stride in the stripe comprises no used blocks based on the block map;

and

wherein sending a message to the storage controller comprises sending a message to the RAID controller, the message designating 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 computer program product further comprising

identifying a first portion of the block map corresponding to data blocks stored in a first stride managed by the RAID controller;

identifying a second portion of the block map corresponding to data blocks stored in a second stride managed by the RAID controller;

wherein sending a message to the storage controller comprises sending a first message to the RAID controller managing the first stride, the message identifying one or more unused blocks in the first stride identified by the first portion of the block map; and

sending a second message to the RAID controller managing the second stride, the second message identifying one or more unused blocks in the second stride identified by the second portion of the block map.

31. A system for data block usage information synchronization for a non-volatile storage volume managed by a storage manager, the system comprising:

a processor;

a memory in communication with the processor;

a block-oriented volume comprising non-volatile storage media configured to store a plurality of data blocks, the block-oriented volume in communication with the memory;

a storage controller configured to store data on the block-oriented volume using an append-only writing process and configured to recover storage space on the block-oriented volume using a storage space recovery process that re-uses data blocks storing previously used data blocks;

a storage manager configured to maintain a block map defining data block usage information for data blocks of the block-oriented volume; and

a block usage synchronizer configured to synchronize data block usage information of the block map with data block usage information maintained by the storage controller.

32. The system of claim 31, wherein the system further comprises an interface operable to communicate storage information between the storage manager and the storage controller, the block usage synchronizer configured to send a message complying with the interface, the message prompting the storage controller to synchronize data block usage information managed by the storage controller.

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. A method for data block usage information synchronization for a non-volatile storage volume managed by a storage manager, the method comprising:

calling a function of a storage Application Programming Interface (“

API”

) to reference a block map defining data block usage information for a set of data blocks of a non-volatile storage volume, the block map maintained by a storage manager, the non-volatile storage volume exclusively managed by a storage controller configured to use a logical-to-physical address translation layer configured to translate logical block addresses received from a storage client to physical block addresses on the non-volatile storage volume;

determining one or more unused blocks from the data block usage information defined by the block map and updates to the data block usage information of the block map caused by storage operations that modify the data block usage information subsequent to referencing the block map; and

sending a message directly to a storage controller directly managing the non-volatile storage volume, the message comprising unused block information indicating to the storage controller the unused blocks identified by the storage manager.

36. The method of claim 35, further comprising deallocating used blocks identified by the storage controller corresponding to the one or more unused blocks identified by the storage manager in response to the message.

37. The method of claim 35, wherein the storage API comprises a defragmentation API for block-oriented storage devices.

38. The method of claim 35, wherein determining one or more unused blocks further comprises,

monitoring storage operations on data blocks represented by the block map, the storage operations executed by the storage controller subsequent to referencing the block map and prior to deallocating the one or more unused blocks in response to the message;

recording data block usage information for the storage operations that change unused blocks of the block map to used blocks, the data block usage information recorded in an in-flight block map; and

combining the block map and the in-flight block map into a combined block map that identifies the one or more unused blocks of the data blocks.