System and Method for Implementing a Hierarchical Data Storage System

• US 20130246711A1
• Filed: 09/11/2012
• Published: 09/19/2013
• 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
• Granted Patent: US 9,189,421 B2
• Time in Patent Office: Days
• US Class Current: 711/135
• 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 for storing large amounts of digital information, said data storage system comprising:

a first data storage layer, said first data storage layer comprising data stored in a low latency first data format of data blocks;

a second data storage layer, said second data storage layer comprising data stored in a second data format with a higher retrieval latency and data compression ratio than said first data format used in said first data storage layeres;

a third data storage layer, said third data storage layer comprising data stored in a third data format with a higher retrieval latency and data compression ratio than said second data format used in 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 for storing large amounts of digital information as set forth in claim 1 wherein said third data storage layer comprises a remote cloud storage service.

3. The data storage system for storing large amounts of digital information as set forth in claim 1 wherein said statistically unique fingerprint comprises a SHA-256 fingerprint 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 storing large amounts of digital information as set forth in 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 for storing large amounts of digital information as set forth in 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 for storing large amounts of digital information as set forth in 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 for storing large amounts of digital information as set forth in claim 1 wherein said second data format comprises data slices that are subsets of said data blocks with duplicate data slices eliminated.

8. The data storage system for storing large amounts of digital information as set forth in claim 7 wherein said third data format comprises data slices from said second data layer that have been compressed.

9. The data storage system for storing large amounts of digital information as set forth in 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.

10. The data storage system for storing large amounts of digital information as set forth in claim 8 wherein said third data storage layer comprises a remote cloud storage system.

11. A method of storing large amounts of digital information in a data storage system, said method comprising:

receiving a data write request having a first data block;

storing said first data block in a first data storage format in a first data storage layer;

evicting said first data block from said first data storage layer in accordance with a first eviction policy;

storing said first data block in a second data format in a second data storage layer, said second data storage layer having a higher retrieval latency and data compression ratio than said first data format;

evicting a subset of said first data block from said second data storage layer in accordance with a second eviction policy; and

storing said subset of said first data block in a third data format in a third data storage layer, said third data storage layer having a higher retrieval latency and data compression ratio than said second data format;

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.

12. The method for storing large amounts of digital information in a data storage system as set forth in claim 11 wherein said third data storage layer comprises a remote cloud storage service.

13. The method for storing large amounts of digital information in a data storage system as set forth in claim 11 wherein evicting said subset of said first data block from said second data storage layer is performed with 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 space in said second storage layer is less than a second threshold level.

14. The method for storing large amounts of digital information in a data storage system as set forth in claim 13 wherein evicting said first data block from said first data storage layer is performed with 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.

15. The method for storing large amounts of digital information as set forth in claim 11 wherein said first eviction policy comprises a least recently used policy.

16. The method for storing large amounts of digital information in a data storage system as set forth in claim 11 wherein said first eviction policy comprises a least recently allocated policy.

17. The method for storing large amounts of digital information in a data storage system as set forth in claim 11 wherein said second data format comprises data slices that are subsets of said data blocks with duplicate data slices eliminated.

18. The method for storing large amounts of digital information in a data storage system as set forth in claim 1711 wherein said third data format comprises data slices from said second data layer that have been compressed.

19. The method for storing large amounts of digital information in a data storage system as set forth in claim 11 wherein a second data block may be marked as high-priority such that said second data block is kept in said first data storage layer.

20. The method for storing large amounts of digital information in a data storage system as set forth in claim 17 wherein said data slices are each assigned a statistically unique identifier.