Browse Prior Art Database

Shared Buffer Management Method Based on Sharing and Access Statistics

IP.com Disclosure Number: IPCOM000116940D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 129K

Publishing Venue

IBM

Related People

Dan, A: AUTHOR [+2]

Abstract

Disclosed is a buffer management method for a shared buffer in a data sharing environment that uses the history of sharing and access to manage the shared buffer.

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

Shared Buffer Management Method Based on Sharing and Access Statistics

      Disclosed is a buffer management method for a shared buffer in
a data sharing environment that uses the history of sharing and
access to manage the shared buffer.

      In a data sharing environment, where a number of closely
coupled computing nodes share a common database, the effectiveness of
a private database buffer at each node is limited due to multi-system
invalidations caused by updates at remote nodes.  A global shared
buffer can be introduced to alleviate this problem.  In (1) various
Shared Buffer Management Policies (SBMP) are proposed.  One such
scheme that was found to perform well for a strongly shared
environment is to propagate an updated page to the shared buffer
since old copies of this page in remote private buffers are
invalidated.

      In a general environment, however, not all pages are strongly
shared.  More specifically, in an environment where transaction types
(or sub-types) exhibit affinity to accessing a subset of the
database, affinity based routing can be used not only to increase
locality of data access, but also to reduce the invalidation across
systems.  In such an environment simply propagating all updated pages
to the shared buffer, will duplicate the contents of the local and
shared buffers.  That is, if a page is not strongly shared, it will
not be required by remote nodes.  In this disclosure, a scheme is
disclosed by which pages are ranked according to their sharing
statistics.  This ranking is used to give priority to the strongly
shared and updated pages over the remaining pages, leading to better
shared buffer hit probability.

      The basic idea is to keep a count of the number of nodes that
access a particular page between successive invalidations.  This
statistic can be maintained as follows.  For each page a bit vector,
with one bit per node, is maintained.  The bit corresponding to a
node is set when the page is read by that node.  The invalidation
count for a page after an update is the number of bits set to one in
the corresponding bit-vector, less one (i.e., number of remote nodes
that may have the page in their local buffers).  After gathering the
invalidation count, the bit-vector is set to zero except for the
updating node (that still holds the valid page in its local buffer).

      In order to maintain stable statistics, exponential averaging
of the invalidation count will be used.  Let x sub n  and x sub n-1
be the current and previous values of the invalidation count.  Then k
% x sub n + (1-k) % x sub n-1  is used in ranking of pages, where 0
lt k lt 1.

      The basic scheme uses the ceiling of the  exponential average
of the invalidation count for page replacement in the shared buffer.
The rationale is as follows.  A large (exponential averaged)
invalidation count implies that the page is accessed by many systems
before an update and is, therefore, a prime ca...