Automated space management for server flash cache

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, 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, and wherein the spatial locality function and the temporal locality function are generated 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;
• 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.

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, 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, and wherein the spatial locality function and the temporal locality function are generated 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;
• 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.