# US 2014/0156777 A1 · Dynamic caching technique for adaptively controlling data block copies in a distributed data processing system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0156777 A1
- Document ID: US20140156777A1
- Status: Published application
- Kind: A1
- Application number: 13/690,158
- Filed: 2012-11-30
- Published: 2014-06-05
- Earliest claimed: 2012-11-30
- Assignees: NetApp, Inc.
- Inventors: Sethuraman Subbiah; Gokul Soundararajan; Tanya Shastri; Lakshmi Narayanan Bairavasundaram
- Web page: https://patentgrep.com/patent/US20140156777A1

## CPC

- H04L 67/1001: for accessing one among a plurality of replicated servers
- 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]
- H04L 67/563: Data redirection of data network streams
- H04L 67/568: Storing data temporarily at an intermediate stage, e.g. caching
- H04L 67/5682: Policies or rules for updating, deleting or replacing the stored data
- H04L 69/02: {Protocol performance}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A dynamic caching technique adaptively controls copies of data blocks stored within caches (“cached copies”) of a caching layer distributed among servers of a distributed data processing system. A cache coordinator of the distributed system implements the dynamic caching technique to increase the cached copies of the data blocks to improve processing performance of the servers. Alternatively, the technique may decrease the cached copies to reduce storage capacity of the servers. The technique may increase the cached copies when it detects local and/or remote cache bottleneck conditions at the servers, a data popularity condition at the servers, or a shared storage bottleneck condition at the storage system. Otherwise, the technique may decrease the cached copies at the servers.

## Claims

### Claim 1

A system comprising:
a plurality of servers including storage devices, each server embodied as a computer having a processor;
a statistics manager configured to maintain statistics pertaining to data blocks stored on the storage devices of the servers; and
a cache coordinator configured to utilize the statistics to implement one of a replication phase and a consolidation phase of a dynamic caching technique that adaptively controls a number of copies of a data block stored on one or more of the storage devices, the cache coordinator further configured to cooperate with the processor to execute the replication phase of the dynamic caching technique to increase the number of copies of the data block stored on the one or more storage devices, the replication phase when executed operable to:
determine that a number of data block requests assigned to a source server of the plurality of servers exceeds a total number of data block requests that can be processed by the source server, the number of data block requests assigned to the source server including one or more data block requests directed to the data block;
determine that a number of data block requests assigned to a target server of the plurality of servers is less than or equal to a total number of data block requests that can be processed by the target server;
copy the data block to the storage device of the target server; and
redirect the one or more data block requests directed to the copied data block at the source server to the target server to alleviate congestion in the system.

### Claim 2 (depends on 1)

The system of claim 1 wherein the storage devices are embodied as caches configured to provide a caching layer of the system.

### Claim 3 (depends on 2)

The system of claim 2 further comprising a storage system connected to the servers, the storage system configured to cooperate with the caches of the servers to provide a shared storage infrastructure of the system.

### Claim 4 (depends on 3)

The system of claim 3 wherein the storage system is configured to store a dataset that is partitioned into blocks of data, including the data block, for storage on the one or more caches of the caching layer.

### Claim 5 (depends on 4)

The system of claim 4 further including one or more data analytic modules configured to track locations of the partitioned blocks of data stored on the one or more caches.

### Claim 6 (depends on 5)

The system of claim 5 wherein the one or more data analytic modules includes a metadata coordinator module configured to perform operations that control access to the dataset and/or partitioned blocks.

### Claim 7 (depends on 3)

The system of claim 3 wherein the statistics manager is embodied as a tree data structure to maintain the statistics pertaining to the data block located on the storage system and one or more caches of the servers.

### Claim 8 (depends on 1)

The system of claim 1 wherein the cache coordinator is further configured to execute the consolidation phase of the dynamic caching technique to decrease the number of copies of the data block, the consolidation phase when executed operable to:
determine that the number of copies of the data block is greater than a minimum number of replicas in the system;
determine that the number of data block requests assigned to the target server is less than or equal to the total number of data block requests that can be processed by the target server, the number of data block requests assigned to the target server including one or more data block requests directed to the data block at the source server;
remove the data block from the source server; and
redirect the one or more data block requests directed to the removed data block at the source server to the target server to improve storage efficiency in the system.

### Claim 9 (depends on 8)

The system of claim 8 wherein the minimum number of replicas is specified by a replication factor.

### Claim 10

A method comprising:
maintaining statistics pertaining to data blocks stored on servers of a distributed processing system, each server including a processor configured to execute a dynamic caching technique that adaptively controls a number of copies of a data block stored on the servers;
utilizing the statistics to implement one of a replication phase and a consolidation phase of the dynamic caching technique; and
executing the replication phase of the dynamic caching technique to increase the number of copies of the data block, the replication phase when executed operable to:
determine that a number of data block requests assigned to a source server of the distributed processing system exceeds a total number of data block requests that can be processed by the source server, the number of data block requests assigned to the source server including one or more data block requests directed to the data block;
determine that a number of data block requests assigned to a target server of the distributed processing system is less than or equal to a total number of data block requests that can be processed by the target server;
copy the data block to the target server; and
redirect the one or more data block requests directed to the copied data block from the source server to the target server to alleviate congestion in the distributed processing system.

### Claim 11 (depends on 10)

The method of claim 10 further comprising:
storing the data blocks on storage devices of the servers; and
embodying the storage devices as caches of the servers.

### Claim 12 (depends on 11)

The method of claim 11 further comprising:
organizing the caches of the servers to provide a caching layer of the distributed processing system.

### Claim 13 (depends on 12)

The method of claim 12 further comprising:
coupling a storage system to the servers; and
configuring the storage system to cooperate with the caches of the servers to provide a shared storage infrastructure of the system.

### Claim 14 (depends on 13)

The method of claim 13 further comprising:
storing a dataset on the storage system;
partitioning the dataset into blocks of data, including the data block; and
storing the blocks of data on one or more of the caches of the distributed processing system.

### Claim 15 (depends on 14)

The method of claim 14 wherein the maintaining statistics comprises organizing a tree data structure to maintain the statistics pertaining to the data block stored on the storage system and the one or more caches of the servers.

### Claim 16 (depends on 10)

The method of claim 10 further comprising:
executing the consolidation phase of the dynamic caching technique to decrease the number of copies of the data block, the consolidation phase when executed operable to:
determine that the number of copies of the data block is greater than a minimum number of replicas in the distributed system;
determine that the number of data block requests assigned to the target server of the distributed system is less than or equal to the total number of data block requests that can be processed by the target server, the number of data block requests assigned to the target server including one or more data block requests directed to the data block at the source server;
remove the data block from the source server; and
redirect the one or more data block requests directed to the removed data block at the source server to the target server to improve storage efficiency in the distributed system.

### Claim 17 (depends on 16)

The method of claim 16 further comprising:
specifying the minimum number of replicas by a replication factor.

### Claim 18

A distributed data processing system comprising:
a plurality of servers including storage devices embodied as caches configured to provide a caching layer of the distributed data processing system, each server embodied as a computer having a processor;
a storage system connected to the servers and configured to cooperate with the caches of the caching layer to provide a shared storage infrastructure of the distributed data processing system;
a statistics manager configured to maintain statistics pertaining to data blocks stored on the caches of the caching layer; and
a cache coordinator configured to utilize the statistics to implement one of a replication phase and a consolidation phase of a dynamic caching technique that adaptively controls a number of copies of a data block stored on one or more of the caches of the caching layer, the cache coordinator further configured to cooperate with the processor to execute the replication phase of the dynamic caching technique to increase the number of copies of the data block stored on the one or more caches, the replication phase when executed operable to:
determine that a number of data block requests assigned to a source server of the plurality of servers exceeds a total number of data block requests that can be processed by the source server, the number of data block requests assigned to the source server including one or more data block requests directed to the data block;
determine that a number of data block requests assigned to a target server of the plurality of servers is less than or equal to a total number of data block requests that can be processed by the target server;
copy the data block to the cache of the target server; and
redirect the one or more data block requests directed to the copied data block at the source server to the target server to alleviate congestion in the distributed data processing system.

### Claim 19 (depends on 18)

The distributed data processing system of claim 18 wherein the statistics manager is embodied as a tree data structure to maintain the statistics pertaining to the data block located on the storage system and one or more caches of the caching layer.

### Claim 20 (depends on 18)

The distributed data processing system of claim 18 wherein the cache coordinator is further configured to execute the consolidation phase of the dynamic caching technique to decrease the number of copies of the data block, the consolidation phase when executed operable to:
s determine that the number of copies of the data block is greater than a minimum number of replicas in the distributed data processing system;
determine that the number of data block requests assigned to the target server is less than or equal to the total number of data block requests that can be processed by the target server, the number of data block requests assigned to the target server including one or more data block requests directed to the data block at the source server;
remove the data block from the source server; and
redirect the one or more data block requests directed to the removed data block at the source server to the target server to improve storage efficiency in the distributed data processing system.