What's special about caches?

Caches are used in distributed request/response systems for a variety of purposes, and in a variety of ways. They are used at the small scale of processor-memory interaction, and at the large scale of file and web server interaction, with largely similar techniques. Here we discuss some general properties of caches and how that relates to the LSAM system.

Caches are provide two distinct benefits in distributed request/response systems:

By keeping a copy of data near the client, the cache reduced response time, whether due to propagation delay, transmission delay, or transaction processing overhead.

Caches also reduce server load by keeping requests local to the client/cache pair. This can also reduce network load across the long link between client and server.

Ways of finding locality in the request stream

A cache exploits locality of reference of the data, by reacting to patterns in the request stream. In particular, a cache is looking for repeating requests, which exploit the locality of its storage. Caches are typically placed near the client (the low response-time path) and far from the server (the high response-time path).


There are two types of locality:

Temporal locality is a property of a single client over time; the same client requests the same response repeatedly over a period of time. This kind of locality is best served by per-client caches, which are already incorporated into most commercial clients (browsers, file system clients, etc.).

Spatial locality is a property of a group of clients over time; one client requests what another has requested earlier. This kind of locality is best served by shared caches, known as proxy caches in web systems. They require that the cache be placed central and near to the set of clients, and far from the server.

The problem occurs when spatial locality dictates a single proxy cache, but no central location exists where the cache can be placed near to all the clients.

The LSAM Proxy cache deploys separate local caches, like in the temporal cache case, but integrates their operation to provide the benefits of a single, spatial proxy cache, even where no central cache could exist.

LSAM home ISI home
Page maintainer: the LSAM project

Last modified: Thu Feb 18 12:49:23 PST 1999
Copyright © 1996 by USC/ISI