Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Check on Access Via Hierarchical Block Validation

IP.com Disclosure Number: IPCOM000044329D
Original Publication Date: 1984-Dec-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 3 page(s) / 19K

Publishing Venue

IBM

Related People

Bennett, BT: AUTHOR [+4]

Abstract

A data-block validation technique is described which reduces message and data traffic in a multiprocessor system. The procedure is based on a hierarchical data structure for keeping track of valid data. A transaction processing system is set forth with N processors, each with its own main memory data buffers, and a shared secondary store. Data is moved between the secondary store and data buffers in units of physical transfer, called blocks . However, data is logically grouped into units, called records . In general, multiple logical records are stored in a single block. In this case no distinction will be made between logical and physical records.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 25% of the total text.

Page 1 of 3

Check on Access Via Hierarchical Block Validation

A data-block validation technique is described which reduces message and data traffic in a multiprocessor system. The procedure is based on a hierarchical data structure for keeping track of valid data. A transaction processing system is set forth with N processors, each with its own main memory data buffers, and a shared secondary store. Data is moved between the secondary store and data buffers in units of physical transfer, called blocks . However, data is logically grouped into units, called records . In general, multiple logical records are stored in a single block. In this case no distinction will be made between logical and physical records. In the case that a single logical record is stored in B blocks, B > 1, the logical record will be considered to be stored as B physical records, where each physical record is that part of the logical record stored in a particular block. It is assumed that the system contains a utility termed the lock manager whose purpose is to support data integrity by processing global lock requests made on behalf of transactions. It is further assumed that the lock manager is used essentially as follows: (1) transactions acquire write locks on records that will be updated; (2) transactions are protected from concurrent updates to records they read by acquiring read locks on such records; (3) concurrent updates to the same block from different processors are prevented by acquiring exclusive locks on blocks that will be updated; and (4) after a transaction commits its updates, all locks acquired on behalf of that transaction are released. With respect to the locking protocol it is assumed that (1) the protocol is correct in the case that each block is read from the secondary store on the first access to each record in that block by a transaction, and (2) other than preventing concurrent updates to the same block from different processors, concurrency is controlled at record granularity. The basic problem solved is to weaken condition
(1) by allowing transactions to access records that are currently in the buffer of the processor executing the transaction. A known technique for solving this problem is to broadcast invalidate messages to each of the other processors in the system at the completion of each transaction. These messages contain the IDs of blocks updated by the transaction. The buffer manager of each processor receiving an invalidate message is required to mark as invalid or cast out any blocks in its buffer referred to in the message, and to acknowledge the message. After receiving all acknowledgments, the transaction may commit. Since the transaction holds write locks on records it updates until all acknowledgments are received, transactions on other systems are protected from accessing invalid data found in their buffers. For large N, this scheme may become unacceptable due to the large number of messages required (if the throughput is prop...