Browse Prior Art Database

Efficient Representation of Page-Range Tokens in a Binary Tree Data Structure

IP.com Disclosure Number: IPCOM000114165D
Original Publication Date: 1994-Nov-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 108K

Publishing Venue

IBM

Related People

Mohindra, A: AUTHOR

Abstract

Disclosed is a technique for efficiently representing and managing page-range tokens using a binary tree data structure. The technique is used by a file server for maintaining the state information of tokens on individual pages of a file. In such systems, tokens are used to enforce consistency among multiple copies of data.

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

Efficient Representation of Page-Range Tokens in a Binary Tree Data
Structure

      Disclosed is a technique for efficiently representing and
managing page-range tokens using a binary tree data structure.  The
technique is used by a file server for maintaining the  state
information of tokens on individual pages of a file.  In such
systems, tokens are used to enforce consistency among multiple copies
of data.

      In the scheme, each node in a binary tree represents a token
entry for a range of pages of a file, i.e., each node has a starting
page number (st_pno) and an end page number (end_pno) it covers
(st_pno <= end_pno).  The left subtree of a node contains all the
entries that represent page-ranges strictly less than the parent node
while the right subtree contains all the entries that represent
page-ranges strictly greater than the parent node.  Thus, each node
in the tree represents non-overlapping distinct page-ranges.  The
design exploits the property of a file system in which read and write
system calls operate on several bytes (range) of data.  If there are
no mode conflicts, the requested byte range corresponds to exactly
one entry in the server data structure; thereby, reducing the memory
overhead as the state information about several pages is represented
in a single entry.  Fig. 1 shows the structure of a node in the data
structure.  Each node contains the starting page number (st_pno), end
page number (end_pno), mode of the token (mode), and bitmap of all
machines (copyset) that have an outstanding token.  In addition to
these fields, each node also stores the minimum and maximum page
numbers covered by the node's left subtree (lmin, lmax) and right
subtree (rmin, rmax).  The reason for these fields is given below.

      By design, the token management protocol requires that all
outstanding data read tokens be revoked prior to granting a
write-token, and an outstanding data write token must be downgraded
to a read token prior to granting a read-token.  Since the read and
write system calls generate requests for a byte-range, the above
requirement translates to revoking/downgrading all conflicting tokens
for any page in the requested range.  It is, therefore,  necessary to
identify all entries in the binary tree that represent page-ranges
that overlap with the new request.  Such an operation can be quite
expensive to implement for it could require the traversal of the
entire binary tree (an O(n) operation).  To reduce the time
requirement for such an operation, ea...