VIRTUALIZED DATA STORAGE SYSTEM CACHE MANAGEMENT

• US 20100241807A1
• Filed: 03/23/2010
• Published: 09/23/2010
• Est. Priority Date: 03/23/2009
• Status: Abandoned Application

• Current Assignee: Riverbed Technology Incorporated
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Wu, David Tze-Si, Gupta, Nitin, McCanne, Steven, Demmer, Michael J.
• Application Number:
  US12/730,192
• Publication Number:
  US 20100241807A1
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Virtual storage arrays consolidate branch data storage at data centers connected via wide area networks. Virtual storage arrays appear to storage clients as local data storage; however, virtual storage arrays actually store data at the data center. The virtual storage arrays overcomes bandwidth and latency limitations of the wide area network by predicting and prefetching storage blocks, which are then cached at the branch location. Virtual storage arrays leverage an understanding of the semantics and structure of high-level data structures associated with storage blocks to predict which storage blocks are likely to be requested by a storage client in the near future. Virtual storage arrays determine the association between requested storage blocks and corresponding high-level data structure entities to predict additional high-level data structure entities that are likely to be accessed. From this, the virtual storage array identifies the additional storage blocks for prefetching.

Claims

1. A method of optimizing a block storage protocol access to a block storage device via a wide area network, the method comprising:

receiving a first storage block for storage in a storage block cache at a first network location;

determining if the storage block cache has sufficient capacity to store the first storage block; and

in response to the determination that the storage block cache does not have sufficient capacity for the first storage block;

selecting a first high-level data structure entity;

identifying at least a second storage block associated with the high-level data structure entity and stored in the storage block cache; and

removing at least the second storage block from the storage block cache.

2. The method of claim 1, wherein selecting a first high-level data structure entity comprises:

selecting the first high-level data structure entity based on its infrequent access by a storage client.

3. The method of claim 1, wherein selecting a first high-level data structure entity comprises:

selecting a third storage block stored in the storage block cache; and

selecting the first high-level data structure entity based on its correspondence with the third storage block.

4. The method of claim 3, wherein the third storage block is selected based on its infrequent access by a storage client.

5. The method of claim 4, comprising:

removing the third storage block from the storage block cache.

6. The method of claim 1, wherein the second storage block is identified as an infrequently accessed portion of the first high-level data structure entity.

8. The method of claim 1, wherein the first storage block is received from a storage client in association with a storage write operation.

9. The method of claim 1, wherein the first storage block is received from a data storage is association with a storage block prefetching operation.

10. The method of claim 9, wherein the data storage is connected with a wide-area network at a first network location and the storage block cache is connected with the wide-area network location at a second network location.

7. The method of claim 7, wherein the second storage block does not include metadata of the first high-level data structure entity.

11. A method of optimizing a block storage protocol access to a block storage device via a wide area network, the method comprising:

receiving a storage block cache replacement policy;

selecting at least a portion of a first high-level data structure entity identified by the storage block cache replacement policy;

identifying at least a first storage block associated with the selected portion of the first high-level data structure entity; and

selecting the first storage block for retention in a storage block cache connected with a wide-area network at a first network location.

12. The method of claim 11, wherein a copy of the first storage block is stored in the storage block cache.

13. The method of claim 11, wherein a copy of the first storage block is not stored in the storage block cache, the method comprising:

retrieving the first storage block from a data storage connected with the wide area network at a second network location.

14. The method of claim 11, wherein the selected portion of the first high-level data structure entity is identified as a frequently accessed portion of the first high-level data structure entity by the storage block cache replacement policy.

15. The method of claim 14, wherein the second storage block includes metadata of the first high-level data structure entity.

16. A method of optimizing a block storage protocol write access to a block storage device via a wide area network, the method comprising:

receiving a sequence of storage block write operations;

selecting a first storage block write operation included in the sequence of storage block write operations, wherein the first storage block operation includes a first version of a storage block;

determining if the sequence of storage block write operations includes a second storage block write operation including a second version of the storage block, wherein the second storage block write operation is more recent than the first storage block write operation;

in response to the determination that the sequence of storage block write operations does not include the second storage block write operation including the second version of the storage block, communicating the first version of the storage block via a wide area network to a data storage connected with the wide area network at a first network location; and

in response to the determination that the sequence of storage block write operations includes the second storage block write operation including the second version of the storage block, communicating the second version of the storage block via the wide area network to the data storage.

17. The method of claim 16, comprising:

in response to receiving the sequence of storage block requests, caching the sequence of storage block requests in a storage block cache; and

following the communication of the second version of the storage block to the data storage, removing the first storage block write operation and the first version of the storage block from the storage block cache.

18. The method of claim 17, wherein the storage block cache is connected with the wide-area network at a second network location, the method comprising:

following the communication of the second version of the storage block to the data storage, retaining the first version of the storage block in the storage block cache for read access by a storage client connected with the wide-area network at the second location.

19. The method of claim 16, wherein determining if the sequence of storage block write operations includes the second storage block write operation including the second version of the storage block comprises:

searching the sequence of storage block write operations from a time associated with the first storage block write operation up to a snapshot time.

20. The method of claim 16, wherein determining if the sequence of storage block write operations includes the second storage block write operation including the second version of the storage block comprises:

searching the sequence of storage block write operations from a time associated with the first storage block write operation up to an end of the sequence of storage block write operations.