LRU-based replication strategies in a LAN remote caching architecture

Abstract

The possibility of quick access to main memory of remote sites has been advanced as a potential performance improvement in modern distributed systems. Even if objects are not available in local memory, sites need not do a disk access. Instead, sites can use efficient mechanisms that support rapid request/response exchanges in order to access objects that reside in the memory of remote sites. However, hardware and software support in such a remote memory architecture must also include algorithms that determine which objects should be cached at the different sites in the system. When each site uses the classic LRU replacement algorithm, performance can be much worse than optimal for a realistic choice of parameters. Because sites cannot coordinate individual decisions, overall sy$tem caching decisions yield very inefficient global configurations. This paper proposes, for LAN environments, a simple modification of the LRU replacement algorithm. By limiting the number of object replicas, the algorithm can substantially improve LRU performance over a wide range of parameters. The relatively simple LAN topology implies that much less state information need be available for good replacement decisions, compared to general network topologies.