Browse Prior Art Database

Efficient, Approximate Cache Invalidation for an Object Server

IP.com Disclosure Number: IPCOM000110864D
Original Publication Date: 1994-Jan-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 124K

Publishing Venue

IBM

Related People

Luniewski, A: AUTHOR [+2]

Abstract

An object server stores and fetches object instances on disk. Clients of the object server establish a communication session with the server, possibly from different machines, for the purpose of fetching and storing objects from the server. On current workstation hardware, it may take from 1 to 6 milliseconds for the client to send a request to the server and receive a response. Therefore, if the client anticipates a need to possibly re-examine objects it has fetched recently, it will want to retain those objects in a client cache. The client cache may be particularly advantageous when the client is made up of several processes, all of which share access to the client cache.

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

Efficient, Approximate Cache Invalidation for an Object Server

      An object server stores and fetches object instances on disk.
Clients of the object server establish a communication session with
the server, possibly from different machines, for the purpose of
fetching and storing objects from the server.  On current workstation
hardware, it may take from 1 to 6 milliseconds for the client to send
a request to the server and receive a response.  Therefore, if the
client anticipates a need to possibly re-examine objects it has
fetched recently, it will want to retain those objects in a client
cache.  The client cache may be particularly advantageous when the
client is made up of several processes, all of which share access to
the client cache.

      Objects retained in the client cache must be discarded (or
"invalidated") when the corresponding object is updated or deleted at
the server.  It is likely to be just as costly to verify the currency
of a cached object by sending a message to the server as it is to
simply refetch the object.  Therefore, a more efficient means of
invalidating client cache entries is required.  In the intended
environment of this technique, absolute client cache consistency is
not essential.  Rather, there are identifiable points in a client's
execution at which stale objects should be deleted from the cache.

      Our basic technique is to maintain an array of version numbers.
The array is designed to be large enough for fine granularity, while
small enough to fit in an efficient inter-system message.
Practically, the size will be on the order of 350 entries to fit in a
1500-byte Ethernet packet.  This array is called the version vector.
Each object known to the server has an object identifier associated
with it.  Object identifiers are used by clients to request objects
from the server.  The server hashes each object identifier into an
entry in the version vector.  When an object is fetched from the
server, the server includes the version vector value with the object
in the response message to the client.  The client stores both the
object and its version value in the client cache.  When the client
wishes to make sure it is up to date with the server, it requests the
latest value of the version vector from the server.  Due to the
limited size of the version vector, it can be fetched with a single
message pair.  Whenever a client finds an object in its cache, it
compares the retained object version number to the corresponding
entry in the latest version vector fetched from the server.  If the
values do not match, the cached object is invalid, and is replaced by
the current object value fetched from the server.  Whenever an object
is updated or deleted, the server increments the corresponding
version vector entry.

      The advantages of this scheme are: 1) clients can fetch the
current contents of the version vector, effectively giving them a
completely consistent cache view, i...