Browse Prior Art Database

Dynamic Check Count Method for Detection of Concurrent Data Modifications

IP.com Disclosure Number: IPCOM000102347D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 2 page(s) / 71K

Publishing Venue

IBM

Related People

Holm, ML: AUTHOR [+2]

Abstract

This disclosure presents a fast and simple method for detection of concurrent data modifications without the performance degradation incurred when data modifications are restricted through locking.

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

Dynamic Check Count Method for Detection of Concurrent Data Modifications

       This disclosure presents a fast and simple method for
detection of concurrent data modifications without the performance
degradation incurred when data modifications are restricted through
locking.

      Instead of using a lock or similar mechanism to control
concurrency, we introduce the idea of a check count.  A check count
is a piece of storage which is incremented when an associated data
structure is changed -- much like a time stamp.

      In the following example, the data structures used are a binary
tree and a record in a file.  The binary tree is searched with a key
to locate an associated record.

      Instead of locking a key or range of keys, a check count can be
associated with a storage area in the binary tree.  Another check
count can be associated with a row or set of rows in the table.  An
appropriate level of granularity can be chosen based on the data
structure and the likelihood of a check count changing.  In some
cases a system-wide check count table might be sufficient.

      The algorithm shown on the next page will allow binary tree
searches to be performed without locking the index.

      This technique has the following advantages:
      1.  Tasks that change the binary tree (or rows) increment an
associated check count, and the readers of the table sample and check
the associated counts.  The updates and sampling of the check...