Apparatus and method for managing storage of data blocks

• US 8,812,454 B2
• Filed: 01/12/2012
• Issued: 08/19/2014
• Est. Priority Date: 01/12/2012
• Status: Active Grant

• Current Assignee: Proven Networks, LLC
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Nandagopal, Thyagarajan, Puttaswamy Naga, Krishna P., Kodialam, Muralidharan S.
• Primary Examiner(s): HARRINGTON, MICHAEL P
• Application Number:
  US13/348,754
• Publication Number:
  US 20130185229A1
• Time in Patent Office: 950 Days
• Field of Search: 707/609, 707/604, 707/661, 707/662, 707/663, 707/665, 707/668, 707/827, 711/100, 711/154, 711/161, 711/162
• US Class Current: 707/661
• 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 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 data block eviction time elapses without a subsequent access to the data block.

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

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

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

4. The apparatus of claim 1, wherein, to compute 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 a current time as T log [(e−

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

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

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

7. The apparatus of claim 1, wherein the memory is a memory of an end user computer.

8. A method, comprising:

determining, by a processor, 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 data block eviction time elapses without a subsequent access to the data block.

9. The method of claim 8, wherein the data block eviction time is computed when the data block is stored in the memory or accessed from the memory.

10. The method of claim 8, further comprising:

computing the probability density function as;

11. The method of claim 8, wherein computing the data block eviction time comprises:

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

1]; and

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

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

12. The method of claim 8, wherein determining the storage duration for the data block comprises:

computing the storage duration for the data block using cost information associated with each of a plurality of memories available for storing the data block.

13. The method of claim 8, wherein the memory is configured to host a storage volume of a cloud storage service.

14. The method of claim 8, wherein the memory is a memory of an end user computer.

15. A non-transitory computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method, the method comprising:

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 data block eviction time elapses without a subsequent access to the data block.

16. The non-transitory computer-readable storage medium of claim 15, wherein the data block eviction time is computed when the data block is stored in the memory or accessed from the memory.

17. The non-transitory computer-readable storage medium of claim 15, the method further comprising:

computing the probability density function as;

18. The non-transitory computer-readable storage medium of claim 15, wherein computing the data block eviction time comprises:

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

1]; and

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

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

19. The non-transitory computer-readable storage medium of claim 15, wherein determining the storage duration for the data block comprises:

computing the storage duration for the data block using cost information associated with each of a plurality of memories available for storing the data block.

20. The non-transitory computer-readable storage medium of claim 15, wherein the memory is configured to host a storage volume of a cloud storage service.

21. The non-transitory computer-readable storage medium of claim 15, wherein the memory is a memory of an end user computer.