APPARATUS AND METHOD FOR MANAGING STORAGE OF DATA BLOCKS

• US 20130185229A1
• Filed: 01/12/2012
• Published: 07/18/2013
• Est. Priority Date: 01/12/2012
• Status: Active Grant

• Current Assignee: Proven Networks, LLC
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Nandagopal, Thyagarajan, Kodialam, Muralidharan S., Naga, Krishna P. Puttaswamy
• Granted Patent: US 8,812,454 B2
• Time in Patent Office: Days
• US Class Current: 705/418
• 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 2212/622 State-only directory, i.e. not recording identity of sharing or owning nodes
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• 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

A data block storage management capability is presented. A cloud file system management capability manages storage of data blocks of a file system across multiple cloud storage services (e.g., including determining, for each data block to be stored, a storage location and a storage duration for the data block). A cloud file system management capability manages movement of data blocks of a file system between storage volumes of cloud storage services. A cloud file system management capability provides a probabilistic eviction scheme for evicting data blocks from storage volumes of cloud storage services in advance of storage deadlines by which the data blocks are to be removed from the storage volumes. A cloud file system management capability enables dynamic adaptation of the storage volume sizes of the storage volumes of the cloud storage services.

Claims

1. An apparatus, comprising:

a processor and a memory, the processor configured to;

determine a storage location and a storage duration for a data block using cost information associated with a plurality of cloud storage services available for storing data blocks of a file system, the storage location specifying one of the cloud storage services in which the data block is to be stored, the storage duration specifying a length of time for which the data block is to be stored in the storage location; and

analyze storage of the data block at the storage location, based on an access pattern of the data block and the storage duration determined for the data block, to determine whether to remove the data block from the storage location.

2. The apparatus of claim 1, wherein the cost information for a cloud storage service comprises at least one of a storage cost associated with the cloud storage service, an access cost associated with the cloud storage service, and a bandwidth cost associated with the cloud storage service.

3. The apparatus of claim 1, wherein, for at least one of the cloud storage services, the cost information associated with the cloud storage service is determined using at least one of a fixed pricing model and a dynamic pricing model.

4. The apparatus of claim 1, wherein the cloud storage services include a first cloud storage service and a second cloud storage service, wherein the first cloud storage service has a lower storage cost and a higher access cost than the second cloud storage service, wherein the storage location specifies the second cloud storage service.

5. The apparatus of claim 4, wherein the processor is configured to:

determine a cost of accessing data from the first cloud storage service (f₁);

determine a cost of storing data in the second cloud storage service (m₂); and

compute the storage duration T for the data block using T=(f₁)/(m₂).

6. The apparatus of claim 1, wherein, to analyze storage of the data block at the storage location for determining whether to transfer the data block from the storage location, the processor is configured to:

monitor access requests for the data block; and

when an amount of time equal to the storage duration has elapsed without an intervening access request for the data block, initiate removal of the data block from the storage location.

7. The apparatus of claim 1, wherein, to analyze storage of the data block at the storage location for determining whether to transfer the data block from the storage location, the processor is further configured to:

determine, for the data block, whether to evict the data block from the storage location prior to removal of the data block from the storage location based on the storage duration.

8. The apparatus of claim 1, wherein, to analyze storage of the data block at the storage location for determining whether to transfer the data block from the storage location, the processor is further configured to:

when a data block is stored in the storage location or accessed from the storage location, compute a data block eviction time for the data block using a probability distribution; and

initiate eviction of the data block from the storage location when the data block eviction time elapses without a subsequence access to the data block.

9. The apparatus of claim 1, wherein the file is stored in a storage volume of the one of the cloud file services indicated by the file storage location, wherein the processor is configured to:

periodically initiate resizing events for resizing the storage volume.

10. The apparatus of claim 9, wherein the size of the storage volume at a current resizing event is S, wherein the processor is configured to:

after the current resizing event, monitor a number of data blocks replaced in S before their respective block eviction times (B_replace) and monitor a number of blocks evicted from S (B_evict); and

at a next resizing event, determine a new size of the storage volume using S+B_replace−

B_evict.

11. The apparatus of claim 10, wherein the processor is configured to:

determine a resizing granularity of the one of the cloud storage services indicated by the file storage location; and

round the determined new size of the storage volume to the nearest multiple of the resizing granularity.

12. The apparatus of claim 9, wherein the resizing events comprise:

increase resizing events configured for attempting to increase the size of the storage volume; and

decrease resizing events configured for attempting to decrease the size of the storage volume.

13. The apparatus of claim 12, wherein a periodic interval associated with the increase resizing events is less than a periodic interval associated with the decrease resizing events.

14. The apparatus of claim 13, wherein the periodic interval associated with the decrease resizing events is determined based on a minimum storage time for which a customer may pay for storage of data in the one of the cloud storage services.

15. The apparatus of claim 1, wherein the processor is configured to:

when a determination is made to remove or evict the data block from the storage location, determine a new file storage location for the data block.

16. A method, comprising:

using a processor and a memory for;

determining a storage location and a storage duration for a data block using cost information associated with a plurality of cloud storage services available for storing data blocks of a file system, the storage location specifying one of the cloud storage services in which the data block is to be stored, the storage duration specifying a length of time for which the data block is to be stored in the storage location; and

analyzing storage of the data block at the storage location, based on an access pattern of the data block and the storage duration determined for the data block, for determining whether to remove the data block from the storage location.

17. An apparatus, comprising:

a processor configured to;

determine a storage duration for storage of a data block in a memory, the storage duration configured to indicate a time at which the data block is scheduled to be removed from the memory;

compute a data block eviction time for the data block based on a probability density function configured to describe a probability of removing the data block from the memory at a time, within a range of time from an initial time to the time at which the data block is scheduled to be removed from the memory, since a last access time of the data block; and

evict the data block from the memory when the block eviction time elapses without a subsequence access to the data block.

18. The apparatus of claim 17, wherein the processor is configured to:

compute the block eviction time when the data block is stored in the memory or accessed from the memory.

19. The apparatus of claim 17, wherein the processor is configured to compute the probability density function as:

20. The apparatus of claim 17, wherein, to generate the data block eviction time, the processor is configured to:

generate a uniformly distributed random variable U in the range [0;

1]; and

compute the data block eviction time from the current time as T log [(e−

1)U+1], wherein T is the storage duration for the data block.

21. The apparatus of claim 17, wherein the processor is configured to determine the storage duration for the data block by computing the storage duration for the data block, wherein the storage duration is computed using cost information associated with each of a plurality of memories available for storing the data block.

22. The apparatus of claim 17, wherein the memory is configured to host a storage volume of a cloud storage service.

23. The apparatus of claim 17, wherein the memory is a memory of an end user computer.

24. A method, comprising:

using a processor for;

determining a storage duration for storage of a data block in a memory, the storage duration configured to indicate a time at which the data block is scheduled to be removed from the memory;

computing a data block eviction time for the data block based on a probability density function configured to describe a probability of removing the data block from the memory at a time, within a range of time from an initial time to the time at which the data block is scheduled to be removed from the memory, since a last access time of the data block; and

evicting the data block from the memory when the block eviction time elapses without a subsequence access to the data block.