Browse Prior Art Database

Elimination of Serialized Synchronous I/O During Concurrent Index Searches

IP.com Disclosure Number: IPCOM000101543D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 62K

Publishing Venue

IBM

Related People

Ricard, GR: AUTHOR [+3]

Abstract

Random searching of index trees (such as B-trees) can be very I/O-intensive operations as a new page at each level of the tree must be read from disk storage as it is encountered. When many processes are contending for access to the same tree, this I/O can severely degrade throughput of the system when a tree-level locking mechanism is used. Page-level locking will help in this case but will add excessive processor overhead for situations where there is little contention for the index tree and many of the desired index pages are already in storage.

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

Elimination of Serialized Synchronous I/O During Concurrent Index Searches

       Random searching of index trees (such as B-trees) can be
very I/O-intensive operations as a new page at each level of the tree
must be read from disk storage as it is encountered.  When many
processes are contending for access to the same tree, this I/O can
severely degrade throughput of the system when a tree-level locking
mechanism is used. Page-level locking will help in this case but will
add excessive processor overhead for situations where there is little
contention for the index tree and many of the desired index pages are
already in storage.

      The method introduced below uses a single lock at the tree
level, but has the means of releasing the lock if the current process
is incurring an I/O and if other processes are waiting to use the
index.  This method is described in terms of indexes but will work
with many other types of object data.

      An application-specific page fault handler is used by this
method.  When a holder of the index lock page faults, a check is made
to see if another process is waiting for the lock.  If no process is
waiting, the lock is retained, but if another process is waiting, an
unlock is done so that another process may run during the I/O.  Upon
completion of the I/O, the index is locked again, and check counts
are sampled to determine if any changes were made to the index which
would affect the process incurring the I/O.

      I...