# US 2014/0156910 A1 · Automated Space Management for Server Flash Cache

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

- Number: US 2014/0156910 A1
- Document ID: US20140156910A1
- Status: Published application
- Kind: A1
- Application number: 13/693,976
- Filed: 2012-12-04
- Published: 2014-06-05
- Earliest claimed: 2012-12-04
- Assignees: VMware, Inc.
- Applicants: Vmware, Inc.
- Inventors: Sandeep Uttamchandani; Li Zhou; Fei Meng; Deng Liu
- Web page: https://patentgrep.com/patent/US20140156910A1

## CPC

- G06F 3/061: {Improving I/O performance}
- G06F 3/0667: {at data level, e.g. file, record or object virtualisation}
- G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays}
- G06F 9/5016: {the resource being the memory}
- G06F 12/0873: Mapping of cache memory to specific storage devices or parts thereof
- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 2009/45579: {I/O management, e.g. providing access to device drivers or storage}
- G06F 2212/152: Virtualized environment, e.g. logically partitioned system
- G06F 2212/222: Non-volatile memory
- G06F 2212/6042: Allocation of cache space to multiple users or processors
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques for automatically allocating space in a flash storage-based cache are provided. In one embodiment, a computer system collects I/O trace logs for a plurality of virtual machines or a plurality of virtual disks and determines cache utility models for the plurality of virtual machines or the plurality of virtual disks based on the I/O trace logs. The cache utility model for each virtual machine or each virtual disk defines an expected utility of allocating space in the flash storage-based cache to the virtual machine or the virtual disk over a range of different cache allocation sizes. The computer system then calculates target cache allocation sizes for the plurality of virtual machines or the plurality of virtual disks based on the cache utility models and allocates space in the flash storage-based cache based on the target cache allocation sizes.

## Claims

### Claim 1

A method for automatically allocating space in a flash storage-based cache, the method comprising:
collecting, by a computer system, an input/output (I/O) trace log for each virtual machine in a plurality of virtual machines or each virtual disk in a plurality of virtual disks;
determining, by the computer system, a cache utility model for each virtual machine or each virtual disk based on the I/O trace log for the virtual machine or the virtual disk, the cache utility model defining an expected utility of allocating space in the flash storage-based cache to the virtual machine or the virtual disk over a range of different cache allocation sizes;
calculating, by the computer system, target cache allocation sizes for the plurality of virtual machines or the plurality of virtual disks based on the cache utility models; and
allocating, by the computer system, space in the flash storage-based cache based on the target cache allocation sizes.

### Claim 2 (depends on 1)

The method of claim 1 wherein the cache utility model for each virtual machine or each virtual disk takes into account a spatial locality of I/O operations identified in the I/O trace log for the virtual machine or the virtual disk.

### Claim 3 (depends on 2)

The method of claim 2 wherein the cache utility model for each virtual machine or each virtual disk further takes into account a temporal locality of I/O operations identified in the I/O trace log for the virtual machine or the virtual disk.

### Claim 4 (depends on 3)

The method of claim 3 wherein the temporal locality is based on a user-defined time window.

### Claim 5 (depends on 3)

The method of claim 3 wherein the cache utility model for each virtual machine or each virtual disk includes a spatial locality function and a temporal locality function, the spatial locality function modeling a probability of a cache hit as a function of cache allocation size, the temporal locality function modeling a probability of a cache hit as a function of time.

### Claim 6 (depends on 5)

The method of claim 5 wherein the computer system generates the spatial locality function and the temporal locality function by:
reading log entries in the I/O trace log of the virtual machine or the virtual disk, each log entry identifying a logical block address (LBA);
creating a hashtable based on the log entries, each hashtable entry being keyed by the LBA and including one more log entries from the I/O trace log corresponding to the hashtable entry's LBA key,
creating, based on the hashtable, an array of spatial distances and an array of temporal distances, each entry in the array of spatial distances identifying a number of I/O operations between consecutive read accesses to a single LBA in the I/O trace log, each entry in the array of temporal distances identifying a time interval between consecutive read accesses to a single LBA in the I/O trace log; and
applying a linear regression analysis to the array of spatial distances and the array of temporal distances respectively.

### Claim 7 (depends on 1)

The method of claim 1 further comprising collecting I/O statistics for the plurality of virtual machines or the plurality of virtual disks at predefined time intervals, the I/O statistics including I/O operations per second (IOPS) for each virtual machine or each virtual disk, service times of one or more physical storage devices associated with each virtual machine or each virtual disk, and a read/write ratio for each virtual machine or each virtual disk.

### Claim 8 (depends on 7)

The method of claim 7 wherein determining a cache utility model for each virtual machine or each virtual disk is further based on the service times and the read/write ratio for the virtual machine or the virtual disk.

### Claim 9 (depends on 7)

The method of claim 7 further comprising, prior to determining a cache utility model for each virtual machine or each virtual disk:
detecting that one or more of the I/O statistics have changed beyond a threshold; and
triggering the determining of a cache utility model for each virtual machine or each virtual disk in response to the detecting.

### Claim 10 (depends on 1)

The method of claim 1 further comprising, prior to determining a cache utility model for each virtual machine or each virtual disk:
detecting when a predetermined number of log entries have been collected in the I/O trace log for a virtual machine or a virtual disk; and
in response to the detecting:
calculating, based on the log entries, an actual cache hit rate for the virtual machine or the virtual disk;
calculating, based on a previously determined cache utility model, a predicted cache hit rate for the virtual machine or the virtual disk; and
if the actual cache hit rate deviates from the predicted cache hit rate beyond a threshold, triggering the determining of cache utility models.

### Claim 11 (depends on 1)

The method of claim 1 further comprising receiving one or more VM event notifications.

### Claim 12 (depends on 11)

The method of claim 11 wherein the one or more VM event notifications include a VM power on/off event notification, a VM suspend/resume event notification, or a VM mobility event notification.

### Claim 13 (depends on 12)

The method of claim 12 further comprising triggering the determining of a cache utility model for each virtual machine or each virtual disk or the calculating of target cache allocation sizes based on the one or more VM event notifications.

### Claim 14 (depends on 1)

The method of claim 1 wherein calculating target cache allocation sizes for the plurality of virtual machines or the plurality of virtual disks comprises:
defining an objective function based on the cache utility model for each virtual machine or each virtual disk and a user-defined weight assigned to the virtual machine or the virtual disk; and
optimizing the objective function.

### Claim 15 (depends on 14)

The method of claim 14 wherein the objective function is subject to a constraint indicating that a sum of the target cache allocation sizes cannot exceed a size of the flash storage-based cache.

### Claim 16 (depends on 15)

The method of claim 15 wherein the objective function is subject to a further constraint indicating that the target cache allocation size for each virtual machine or each virtual disk cannot exceed a maximum user-defined cache allocation size for the virtual machine or the virtual disk and cannot go below a minimum user-defined cache allocation size for the virtual machine or the virtual disk.

### Claim 17 (depends on 1)

The method of claim 1 wherein allocating space in the flash-storage based cache based on the target cache allocation sizes comprises:
modifying, for each virtual machine or each virtual disk, a target size parameter based on the target cache allocation size for the virtual machine or the virtual disk; and
upon servicing an I/O request directed to a first virtual machine or a first virtual disk:
determining a current cache allocation size for the first virtual machine or the first virtual disk; and
if the current cache allocation size is less than the target size parameter for the first virtual machine or the first virtual disk:
determining one or more second virtual machines or one or more second virtual disks that has a current cache allocation size that exceeds its target size parameter; and
allocating one or more blocks of cache space from one of the one or more second virtual machines or the one or more second virtual disks to the first virtual machine or the first virtual disk.

### Claim 18 (depends on 17)

The method of claim 17 wherein the one or more of second virtual machines or the one or more second virtual disks are ordered according to user-defined weights, and wherein the one or more blocks are allocated from a virtual machine in the one or more second virtual machines or a virtual disk in the one or more second virtual disks having a lowest user-defined weight.

### Claim 19

A non-transitory computer readable storage medium having stored thereon computer software executable by a processor, the computer software embodying a method for automatically allocating space in a flash storage-based cache, the method comprising:
collecting an I/O trace log for each virtual machine in a plurality of virtual machines or each virtual disk in a plurality of virtual disks;
determining a cache utility model for each virtual machine or each virtual disk based on the I/O trace log for the virtual machine or the virtual disk, the cache utility model defining an expected utility of allocating space in the flash storage-based cache to the virtual machine or the virtual disk over a range of different cache allocation sizes;
calculating target cache allocation sizes for the plurality of virtual machines or the plurality of virtual disks based on the cache utility models; and
allocating space in the flash storage-based cache based on the target cache allocation sizes.

### Claim 20

A system for automatically allocating space in a flash storage-based cache, the system comprising:
a processor configured to:
collect an I/O trace log for each virtual machine in a plurality of virtual machines or each virtual disk in a plurality of virtual disks;
determine a cache utility model for each virtual machine or each virtual disk based on the I/O trace log for the virtual machine or the virtual disk, the cache utility model defining an expected utility of allocating space in the flash storage-based cache to the virtual machine or the virtual disk over a range of different cache allocation sizes;
calculate target cache allocation sizes for the plurality of virtual machines or the plurality of virtual disks based on the cache utility models; and
allocate space in the flash storage-based cache based on the target cache allocation sizes.