Multiple granularity locking

Last updated

In computer science, multiple granularity locking (MGL) is a locking method used in database management systems (DBMS) and relational databases.

Contents

In multiple granularity locking, locks are set on objects that contain other objects. MGL exploits the hierarchical nature of the contains relationship. For example, a database may have files, which contain pages, which contain records. This can be thought of as a tree of objects, where each node contains its children. A lock on this structure (such as a shared or exclusive lock) locks the targeted node as well as all of its descendants. [1]

Multiple granularity locking is usually used with non-strict two-phase locking to guarantee serializability.

Lock modes

In addition to shared (S) locks and exclusive (X) locks from other locking schemes, like strict two-phase locking, MGL also uses intentional "locks", which do not directly lock a node, but instead denote the existence, or intent to add, a lock of the specified type lower in the node hierarchy. Intentional locks include "intention shared" (IS), "intention exclusive" (IX), and the combined "shared and intention exclusive" (SIX) locks. IS locks conflict with X locks, while IX locks conflict with S and X locks. The null lock (NL) is compatible with everything.

To lock a node in S (or X), MGL has the transaction lock on all of its ancestors with IS (or IX), so if a transaction locks a node in S (or X), no other transaction can access its ancestors in X (or S and X). This protocol is shown in the following table:

To GetMust have on all ancestors
IS or SIS or IX
IX, SIX or XIX or SIX

Determining what level of granularity to use for locking is done by locking the finest level possible (i.e., at the lowest leaf), and then escalating these locks to higher levels in the file hierarchy to cover more records or file elements as needed in a process known as "lock escalation". MGL locking modes are compatible with each other as defined in the following matrix.

ModeNLISIXSSIXX
NLYesYesYesYesYesYes
ISYesYesYesYesYesNo
IXYesYesYesNoNoNo
SYesYesNoYesNoNo
SIXYesYesNoNoNoNo
XYesNoNoNoNoNo

Following the locking protocol and the compatibility matrix, if one transaction holds a node in S mode, no other transactions can have locked any ancestor in X mode.

See also

Related Research Articles

Transaction Processing Facility IBM mainframe operating system used for transaction processing

Transaction Processing Facility (TPF) is an IBM real-time operating system for mainframe computers descended from the IBM System/360 family, including zSeries and System z9.

Cache coherence Property of shared data being read as the same value across different execution units, without data races

In computer architecture, cache coherence is the uniformity of shared resource data that ends up stored in multiple local caches. When clients in a system maintain caches of a common memory resource, problems may arise with incoherent data, which is particularly the case with CPUs in a multiprocessing system.

In computer science, a lock or mutex is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy.

In databases and transaction processing, two-phase locking (2PL) is a concurrency control method that guarantees serializability. It is also the name of the resulting set of database transaction schedules (histories). The protocol utilizes locks, applied by a transaction to data, which may block other transactions from accessing the same data during the transaction's life.

In computer networking, Server Message Block (SMB), one version of which was also known as Common Internet File System, is a communication protocol for providing shared access to files, printers, and serial ports between nodes on a network. It also provides an authenticated inter-process communication mechanism. Most usage of SMB involves computers running Microsoft Windows, where it was known as "Microsoft Windows Network" before the introduction of Active Directory. Corresponding Windows services are LAN Manager Server for the server component, and LAN Manager Workstation for the client component.

Record locking is the technique of preventing simultaneous access to data in a database, to prevent inconsistent results.

File system concrete format or program for storing files and directories on a data storage device

In computing, a file system or filesystem controls how data is stored and retrieved. Without a file system, data placed in a storage medium would be one large body of data with no way to tell where one piece of data stops and the next begins. By separating the data into pieces and giving each piece a name, the data is easily isolated and identified. Taking its name from the way paper-based data management system is named, each group of data is called a "file." The structure and logic rules used to manage the groups of data and their names is called a "file system."

File locking is a mechanism that restricts access to a computer file, or to a region of a file, by allowing only one user or process to modify or delete it in a specific time and to prevent reading of the file while it's being modified or deleted.

In databases an index is a data structure, part of the database, used by a database system to efficiently navigate access to user data. Index data are system data distinct from user data, and consist primarily of pointers. Changes in a database, may require indexes to be updated to maintain accurate user data accesses. Index locking is a technique used to maintain index integrity. A portion of an index is locked during a database transaction when this portion is being accessed by the transaction as a result of attempt to access related user data. Additionally, special database system transactions may be invoked to maintain and modify an index, as part of a system's self-maintenance activities. When a portion of an index is locked by a transaction, other transactions may be blocked from accessing this index portion. Index Locking Protocol guarantees that phantom read phenomenon won't occur. Index locking protocol states:

IBM Spectrum Scale, formerly theGeneral Parallel File System(GPFS) is high-performance clustered file system software developed by IBM. It can be deployed in shared-disk or shared-nothing distributed parallel modes, or a combination of these. It is used by many of the world's largest commercial companies, as well as some of the supercomputers on the Top 500 List. For example, it is the filesystem of the Summit Supercomputer at Oak Ridge National Laboratory which was the #1 fastest supercomputer in the world in the November 2019 top500 list of supercomputers . Summit is a 200 Petaflops system composed of more than 9,000 IBM POWER processors and 27,000 NVIDIA Volta GPUs. The storage filesystem called Alpine has 250 PB of storage using Spectrum Scale on IBM ESS storage hardware, capable of approximately 2.5TB/s of sequential I/O and 2.2TB/s of random I/O.

In computer science and engineering, transactional memory attempts to simplify concurrent programming by allowing a group of load and store instructions to execute in an atomic way. It is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. Transactional memory systems provide high-level abstraction as an alternative to low-level thread synchronization. This abstraction allows for coordination between concurrent reads and writes of shared data in parallel systems.

Commitment ordering (CO) is a class of interoperable serializability techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic (non-blocking) implementations. With the proliferation of multi-core processors, CO has been also increasingly utilized in concurrent programming, transactional memory, and especially in software transactional memory (STM) for achieving serializability optimistically. CO is also the name of the resulting transaction schedule (history) property, which was originally defined in 1988 with the name dynamic atomicity. In a CO compliant schedule the chronological order of commitment events of transactions is compatible with the precedence order of the respective transactions. CO is a broad special case of conflict serializability, and effective means to achieve global serializability across any collection of database systems that possibly use different concurrency control mechanisms.

Virtuoso Universal Server

Virtuoso Universal Server is a middleware and database engine hybrid that combines the functionality of a traditional Relational database management system (RDBMS), Object-relational database (ORDBMS), virtual database, RDF, XML, free-text, web application server and file server functionality in a single system. Rather than have dedicated servers for each of the aforementioned functionality realms, Virtuoso is a "universal server"; it enables a single multithreaded server process that implements multiple protocols. The free and open source edition of Virtuoso Universal Server is also known as OpenLink Virtuoso. The software has been developed by OpenLink Software with Kingsley Uyi Idehen and Orri Erling as the chief software architects.

Microsoft SQL Server is a relational database management system developed by Microsoft. As a database server, it is a software product with the primary function of storing and retrieving data as requested by other software applications—which may run either on the same computer or on another computer across a network. Microsoft markets at least a dozen different editions of Microsoft SQL Server, aimed at different audiences and for workloads ranging from small single-machine applications to large Internet-facing applications with many concurrent users.

OS 2200 is the operating system for the Unisys ClearPath Dorado family of mainframe systems. The operating system kernel of OS 2200 is a lineal descendant of Exec 8 for the UNIVAC 1108. Documentation and other information on current and past Unisys systems can be found on the Unisys public support website.

Apache ZooKeeper System for distributed coordination

Apache ZooKeeper is a software project of the Apache Software Foundation. It is essentially a service for distributed systems offering a hierarchical key-value store, which is used to provide a distributed configuration service, synchronization service, and naming registry for large distributed systems. ZooKeeper was a sub-project of Hadoop but is now a top-level Apache project in its own right.

Versant Object Database (VOD) is an object database software product developed by Versant Corporation.

Distributed Data Management Architecture

Distributed Data Management Architecture (DDM) is IBM's open, published software architecture for creating, managing and accessing data on a remote computer. DDM was initially designed to support record-oriented files; it was extended to support hierarchical directories, stream-oriented files, queues, and system command processing; it was further extended to be the base of IBM's Distributed Relational Database Architecture (DRDA); and finally, it was extended to support data description and conversion. Defined in the period from 1980 to 1993, DDM specifies necessary components, messages, and protocols, all based on the principles of object-orientation. DDM is not, in itself, a piece of software; the implementation of DDM takes the form of client and server products. As an open architecture, products can implement subsets of DDM architecture and products can extend DDM to meet additional requirements. Taken together, DDM products implement a distributed file system.

Database scalability is the ability of a database to handle changing demands by adding/removing resources. Databases have adopted a host of techniques to cope.

References

  1. Jim Gray; Raymond A. Lorie; G. R. Putzolu; Iriving L. Traiger (1976). "Granularity of locks and degrees of consistency in a shared data base". IBM Technical Report. IBM. CiteSeerX   10.1.1.92.8248 .