Browse Prior Art Database

Caching Objects in a Data Space

IP.com Disclosure Number: IPCOM000112804D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 149K

Publishing Venue

IBM

Related People

Morey II, GE: AUTHOR

Abstract

Applications exist that require two retrieves of data from auxilliary devices. One retrieve is required to view the data and another to print the data. What follows is a proposal that will result in improving response time by eliminating the need for the second I/O.

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

Caching Objects in a Data Space

      Applications exist that require two retrieves of data from
auxilliary devices.  One retrieve is required to view the data and
another to print the data.  What follows is a proposal that will
result in improving response time by eliminating the need for the
second I/O.

      A solution for caching retrieved data in a data space requires
management of allocated and unallocated space.

Managing allocated space requires:

o   a directory,

a technique for aging data space resident objects.

Managing unallocated space requires:

o   a technique to ensure all free space fragments represent the
    largest contiguous area of free space possible,

o   a technique for ordering free space fragments by size for
    efficient allocations.

Directory - The main criterion for a directory is it must be
efficient, not necessarily optimal.

      Efficiency of a directory is inversely proportional to the
amount of time required to arrive at a decision via directory access.
When talking of a directory that maps a dynamic data space, a
'decision' can be defined as the determination of whether an object
is resident in a data space (allowing immediate access) or is not
resident (requiring I/O).

      The primary contributor of directory access cost is the
overhead associated with paging.  Paging overhead can be reduced by
taking steps to minimize the size of the directory page set.  One
possible solution is the allocation of four kilobyte directory blocks
from which directory nodes are allocated, rather than allocating
storage for individual directory nodes.  One might also consider
allocating directory storage space from a fixed subpool (eliminating
paging overhead entirely).  When limiting cost consideration to node
accesses, the use of a binary search tree to organize a collection of
objects in a data space provides reasonable performance (efficiency)
without a complicated algorithm.

      A balanced binary search tree mapping 130,000 objects will
require a worst case of 17 node accesses to arrive at a decision.  In
addition, a binary search tree provides additional flexibility that
lends itself to a solution for aging objects in a data space.

      Aging Data Space Resident Objects - When dealing with a finite
amount of space and a set of potential object residents with
virtually unlimited space requirements, a point can be reached where
the data space becomes full and object replacement is necessary.
Criteria are needed to decide which object or set of objects will be
replaced.

      One criterion is the amount of time objects go unreferenced.
Unreferenced age or time would not represent some absolute
quantifiable period but would be relative to other objects'
unreferenced age or time.

      A rather simple solution for tracking unreferenced time of
objects is to maintain a list (linked list).  The list would order
objects based on their relative unreferenced age and wo...