System and method for implementing a hierarchical data storage system

• US 9,189,421 B2
• Filed: 09/11/2012
• Issued: 11/17/2015
• Est. Priority Date: 01/06/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: StorSimple, Inc. (Microsoft Corporation)
• Inventors: Testardi, Richard, Cometto, Maurilio, Kulangara, Kuriakose George
• Primary Examiner(s): Patel, Kaushikkumar
• Application Number:
  US13/610,567
• Publication Number:
  US 20130246711A1
• Time in Patent Office: 1,162 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A system and method for efficiently storing data both on-site and off-site in a cloud storage system. Data read and write requests are received by a cloud data storage system. The cloud storage system has at least three data storage layers. A first high-speed layer, a second efficient storage layer, and a third off-site storage layer. The first high-speed layer stores data in raw data blocks. The second efficient storage layer divides data blocks from the first layer into data slices and eliminates duplicate data slices. The third layer stores data slices at an off-site location.

Claims

1. A data storage system, comprising:

a first data storage layer, the first data storage layer comprising data that can be accessed at a high data rate with a low latency;

a second data storage layer, said second data storage layer comprising de-duplicated data evicted from the first data storage layer, wherein the second storage layer has a higher retrieval latency than the first data storage layer;

a barrier storage area, the barrier storage area comprising a subset of the de-duplicated data that is stored for a settlement period, wherein the settlement period represents a time after which the de-duplicated data is made accessible; and

a third data storage layer coupled to the barrier storage area and configured to receive the subset of the de-duplicated data, said third data storage layer having a higher retrieval latency than said second data storage layer;

wherein a first data item is stored in said first, second, or third data storage layer based upon frequency of use of said first data item.

2. The data storage system of claim 1, wherein said third data storage layer comprises a remote cloud storage service.

3. The data storage system of claim 1, wherein said data storage system further comprises:

a first background process associated with said first data storage layer, said first background process evicting data from said first data storage layer when an amount of free space in said first storage layer is less than a first threshold level.

4. The data storage system for of claim 3, wherein said data storage system further comprises:

a second background process associated with said second data storage layer, said second background process evicting data from said second data storage layer when an amount of free storage space in said second storage layer is less than a second threshold level.

5. The data storage system of claim 3, wherein said first background process evicts data from said first storage layer using a least recently used heuristic.

6. The data storage system of claim 3, wherein said first background process evicts data from said first storage layer using a least recently allocated heuristic.

7. The data storage system of claim 1, wherein the de-duplicated data comprises data slices that are subsets of said data blocks with duplicate data slices eliminated.

8. The data storage system of claim 7, wherein the subset of the de-duplicated data comprises data slices from said second data layer that have been compressed.

9. The data storage system of claim 1, wherein a second data item may be marked as high-priority such that said second data item is kept in said first data storage layer, regardless of the amount of free space in said first storage layer.

10. The data storage system of claim 8, wherein said third data storage layer comprises a remote cloud storage system.

11. The data storage system of claim 7, wherein said data slices are each assigned a statistically unique identifier.

12. A system, comprising:

a first data storage layer in a memory, the first data storage layer comprising data blocks;

a second data storage layer in the memory, the second data storage layer comprising de-duplicated data evicted from the first data storage layer, wherein the second storage layer has a higher retrieval latency than the first data storage layer; and

a barrier storage area in the memory, the barrier storage area comprising a subset of the de-duplicated data that is stored for a settlement period before being deleted, wherein the subset of the de-duplicated data is selected for transfer to a third storage layer operated by a cloud storage provider, wherein the third data storage layer has a higher retrieval latency than the second data storage layer.

13. The system of claim 12, further comprising:

a third data storage layer coupled to the barrier storage area and configured to receive the subset of the de-duplicated data, said third storage layer having a higher retrieval latency and data compression ratio than said second data storage layer;

wherein a first data item is stored in said first, second, or third data storage layer based upon frequency of use of said first data item.

14. The system of claim 13, wherein the settlement period is configurable dependent upon a cloud storage provider being used, wherein the settlement period represents a time after which the de-duplicated data stored by the cloud storage provider is made accessible, and wherein a given data item is stored in the first, second, or third data storage layer based upon frequency of use of the given data item.

15. The system of claim 12, further comprising:

a first background process associated with said first data storage layer, said first background process evicting data from said first data storage layer when an amount of free space in said first storage layer is less than a first threshold level.

16. The system of claim 15, further comprising:

a second background process associated with said second data storage layer, said second background process evicting data from said second data storage layer when an amount of free storage space in said second storage layer is less than a second threshold level.

17. The system of claim 15, wherein said first background process evicts data from said first storage layer using a least recently used heuristic.

18. The system of claim 15, wherein said first background process evicts data from said first storage layer using a least recently allocated heuristic.

19. The system of claim 18, wherein the subset of the de-duplicated said third data format comprises data slices from said second data layer that have been compressed.

20. A memory device having program instructions stored thereon that, upon execution by a computer system, cause the computer system to provide:

a first data storage layer comprising data blocks;

a second data storage layer comprising de-duplicated data evicted from the first data storage layer, wherein the second storage layer has a higher retrieval latency first data storage layer; and

a barrier storage area comprising a subset of the de-duplicated data that is stored for a settlement period after which the subset of the de-duplicated data is deleted, wherein the subset of the de-duplicated data is selected for transfer to a third storage layer operated by a cloud storage provider via a network, wherein the third data storage layer has a higher retrieval latency than the second data storage layer, wherein the settlement period is configurable dependent upon the cloud storage provider being used, wherein the settlement period represents a time after which the de-duplicated data stored by the cloud storage provider is made accessible, and wherein a given data item is stored in the first, second, or third data storage layer based upon frequency of use of the given data item.