m4_comment([$Id: page.so,v 10.19 2002/06/01 23:42:12 bostic Exp $])m4_ref_title(Locking Subsystem, Locking granularity,    [page-level @locking, locking granularity], lock/deaddbg, lock/notxn)m4_p([dnlWith the exception of the Queue access method, the m4_db access methodsdo page-level locking.  The size of pages in a database may be set whenthe database is created by calling the m4_refT(dbh_set_pagesize).  Ifnot specified by the application, m4_db selects a page size that willprovide the best I/O performance by setting the page size equal to theblock size of the underlying file system.  Selecting a smaller page sizecan result in increased concurrency for some applications.])m4_p([dnlIn the Btree access method, m4_db uses a technique called lock couplingto improve concurrency.  The traversal of a Btree requires reading apage, searching that page to determine which page to search next, andthen repeating this process on the next page.  Once a page has beensearched, it will never be accessed again for this operation, unless apage split is required.  To improve concurrency in the tree, once thenext page to read/search has been determined, that page is locked andthen the original page lock is released atomically (that is, withoutrelinquishing control of the lock manager).  When page splits becomenecessary, write locks are reacquired.])m4_p([dnlBecause the Recno access method is built upon Btree, it also uses lockcoupling for read operations.  However, because the Recno access methodmust maintain a count of records on its internal pages, it cannotlock-couple during write operations.  Instead, it retains write lockson all internal pages during every update operation.  For this reason,it is not possible to have high concurrency in the Recno access methodin the presence of write operations.])m4_p([dnlThe Queue access method uses only short-term page locks.  That is, a pagelock is released prior to requesting another page lock.  Record locks areused for transaction isolation.  The provides a high degree of concurrencyfor write operations.  A metadata page is used to keep track of the headand tail of the queue.  This page is never locked during other locking orI/O operations.])m4_p([dnlThe Hash access method does not have such traversal issues, but it mustalways refer to its metadata while computing a hash function because itimplements dynamic hashing.  This metadata is stored on a special pagein the hash database.  This page must therefore be read-locked on everyoperation.  Fortunately, it needs to be write-locked only when new pagesare allocated to the file, which happens in three cases:])m4_bulletbeginm4_bullet([a hash bucket becomes full and needs to split])m4_bullet([a key or data item is too large to fit on a normal page])m4_bullet([dnlthe number of duplicate items for a fixed key becomes so large that theyare moved to an auxiliary page])m4_bulletendm4_p([dnlIn this case, the access method must obtain a write lock on the metadatapage, thus requiring that all readers be blocked from entering the treeuntil the update completes.])m4_p([dnlFinally, when traversing duplicate data items for a key, the lock onthe key value also acts as a lock on all duplicates of that key.Therefore, two conflicting threads of control cannot access the sameduplicate set simultaneously.])m4_ignore([dnlAs the Hash access method implements dynamic hashing, it must always referto its metadata while computing a hash function.  This metadata isstored on a special page in the hash database.  The hash access uses asimilar lock coupling technique to coordinate access between its metadatapage and the remaining buckets in the database.  The metadata page isread-locked in order to determine the next bucket to traverse.  Thatbucket is then locked, and the metadata page lock is atomically released.If it is later necessary to write lock the metadata page, the Hash methoduses an algorithm similar to that used for Btree splits.  It releases itsbucket lock, obtains a write lock on the metadata page and thenreacquires the lock on the appropriate bucket (which may have changedwhile the lock was released).  The conditions under which this scenariooccurs are: 1) a hash bucket becomes full and needs to split, 2) a keyor data item is too large to fit on a normal page, and 3) the number ofduplicate items for a fixed key becomes sufficiently large that they aremoved to an auxiliary page.  This algorithm provides much betterconcurrency and fewer deadlocks than previous algorithms, which requiredthat the metadata page remain locked for the duration of every operation.])m4_page_footer