Browse Prior Art Database

Original Publication Date: 2004-Feb-18
Included in the Prior Art Database: 2004-Feb-18
Document File: 4 page(s) / 101K

Publishing Venue



The invention described here is a method and a system for maintaining a so-called "value function" which assigns a numercial value to any feasible cache contents with respect to past statistics of data accesses. This function is used for deciding how to dynamically change the cache contents. The value function is aimed at minimizing the expected number of cache misses per time unit. In the past, cache replacement policies and cache pre-fetching policies have been pursued independently. This inventions provides an unfied basis for both replacement and pre-fetching.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 21% of the total text.

Page 1 of 4


The problem of cache management is well-known but is largely unsolved. A modern storage system (for example, IBM's Enterprise Storage Server) or storage controller combines a large number of individual disks, and presents them to the accessing hosts and applications as one or many large logical disks. The main task of the storage system is to respond to read/write requests/commands for data access. A storage system consists of two memory levels--main and auxiliary. The main-level refers to very fast intermediate storage, for example, random access memory (RAM), inside the storage system, while auxiliary-level refers to the individual disks or other storage sub-systems that are attached to the strorage system. The main memory is usually referred to as the cache. The cache is usually at least an order of magnitude faster than the auxiliary-level memory. However, due to cost constraints, the cache is usually only a fraction of the size of the auxiliary storage. For example, IBM's Enterprise Storage Server provides upto 32GB of cache, while supporting upto 11TB of auxiliary storage. Due to this reason, at any time, the cache can contain only a small subset of the data available in the auxiliary storage. If a requested data item resides in cache (this is called a cache hit), then this data can be returned to the system much faster than if it were not in the cache (called a cache miss). The performance of modern storage systems depends largerly on proper management of the cache.

The problem of cache management amounts to dynamically deciding what data should be kept in the cache--at any given time. An algorithm that governs the contents of the cache is known as cache management policy, or simply, caching policy. The cache management problem is complex because future requests for data are not known in advance, but past requests may hint about the likelihood of future ones. Also, due to performance constraints, the contents of the cache cannot be drastically changed from moment-to-moment. Furthermore, the cache policy itself amounts to an overhead on the system.

One of the most popular cache management policies is called "Least Recently Used" (LRU). According to this rule, the items in the cache are linearly ordered in a list from the most recently accessed item to the least recently accessed. This list is known as the LRU stack. Whenever a data item, which is not in the cache, is requested, this item is placed at the top of the LRU stack in anticipation of future requests for it. In order to make room for this new item, the Least Recently Used item (at the bottom of the LRU stack) is discarded from the cache. If the requested item is already in the list, then it is moved to the top of the LRU stack. Another popular cache management policy is called "Least Frequently Used" (LFU). According to this rule, the items in the cache are linearly ordered in a list from the most frequently accessed...