Browse Prior Art Database

Least-Recently-Used-Based Replication Scheme for a LAN Remote Caching Architecture

IP.com Disclosure Number: IPCOM000105036D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 93K

Publishing Venue

IBM

Related People

Leff, A: AUTHOR [+3]

Abstract

The problem is to find an optimal set of caching decisions in a local area network implementation of a remote caching architecture.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 48% of the total text.

Least-Recently-Used-Based Replication Scheme for a LAN Remote Caching Architecture

      The problem is to find an optimal set of caching decisions in a
local area network implementation of a remote caching architecture.

      The availability of high speed LAN technology facilitates
efficient transmission of data between sites.  Remote memory
architectures (RCAs) are distributed systems that utilize the large
bandwidth and low latency of modern networked systems to support
efficient request/response exchanges for objects that reside in
remote memory [*].  This ability to access objects cached at remote
sites introduces a new level in the classic memory hierarchy -- main
memory accessed through the network -- whose access time may be
significantly faster than that of local disks.  Distributed
replacement algorithms must solve the task of coordinating caching
decisions in order to achieve good performance.  The basic problem is
that, while sites should normally cache locally valuable objects in
local memory, the actual benefit of this decision depends on the
caching decisions made by other sites in the system.

      The proposed One-Copy-Heuristic (1CH) algorithm contains two
components.  The first component does a dynamic and efficient
estimation of object access rates and site activity.  This is
accomplished through (1) each site independently applying the classic
LRU algorithm -- yielding an object's LRU stack position -- and (2)
each site estimating its own "busyness" by tracking the number of
object accesses generated by transactions running at its site.  The
second component uses these estimates to make cache replacement
decisions without requiring sites to constantly exchange information
about their cache decisions.  This is accomplished by (1) maintaining
the one copy invariant and (2) occasionally volunteering to be a
"buddy" and cache an object for another site.  The one copy invariant
requires that at most one copy of any object be resident in RCA
memory at any time.  If a site needs to access an object it applies
the following steps.

      1.  If the object is available in local cache, then the LRU
          stack is updated in the usual fashion.

      2.  If the object must be fetched from remote memory, then the
          object is not cached locally.  This reduces the number of
          replicas in the system.  One of two actions can be taken at
          this point:

          a.  Remote sites do not update their LRU stack despite the
              remote memory reference.  The idea is that sites
              operate autonomously, and maintain full control of
              their cache -- subject to the one-copy criterion.  This
              variant of 1CH is denoted 1CH sub l, (for "local").

          b.  Any remote site with a copy of the object in main
             ...