Distributed lock manager: Difference between revisions

Revision as of 14:22, 6 October 2017

Latest revision as of 19:10, 9 August 2025

(28 intermediate revisions by 23 users not shown)

Line 1:

{{refimprovemore citations needed|date=October 2010}}

Operating Systems use lock managers to organise and serialise the access to resources. A '''distributed lock manager''' (DLM) runs in every machine in a cluster, with an identical copy of a cluster-wide lock database. In this way a DLM provides [[software application]]s which are [[distributed programming|distributed]] across a cluster on multiple machines with a means to synchronize their accesses to [[shared resource]]s.

Operating Systems use lock managers to organise and serialise the access to resources. A '''distributed lock manager''' ('''DLM''') runs in every machine in a cluster, with an identical copy of a cluster-wide lock database. [[Operating system]]s use lock managers to organise and serialise the access to resources. In this way a DLM provides [[software application]]s which are [[distributed programming|distributed]] across a cluster on multiple machines with a means to synchronize their accesses to [[shared resource]]s.

DLMs have been used as the foundation for several successful [[clustered file system]]s, in which the machines in a [[computer cluster|cluster]] can use each other's storage via a unified [[file system]], with significant advantages for performance and [[high-availability|availability]]. The main performance benefit comes from solving the problem of [[cache coherency|disk cache coherency]] between participating computers. The DLM is used not only for [[file locking]] but also for coordination of all [[disk (storage device)|disk]] access. [[VMScluster]], the first clustering system to come into widespread use, relies on the [[OpenVMS]] DLM in just this way.

DLMs have been used as the foundation for several successful [[clustered file system]]s, in which the machines in a [[computer cluster|cluster]] can use each other's storage via a unified [[file system]], with significant advantages for performance and [[high-availability|availability]]. The main performance benefit comes from solving the problem of [[cache coherency|disk cache coherency]] between participating computers. The DLM is used not only for [[file locking]] but also for coordination of all [[disk (storage device)|disk]] access. [[VMScluster]], the first clustering system to come into widespread use, reliesrelied on the [[OpenVMS]] DLM in just this way.

==VMS implementation==

=== Resources= ==

[[Digital Equipment Corporation|DEC]]'s [[OpenVMS|VMS]] (virtual memory system) was the first widely available operating system to implement a DLM. This became available in Version 4, although the user interface was the same as the single-processor lock manager that was first implemented in Version 3.

The DLM uses a generalized concept of a '''resource''', which is some entity to which shared access must be controlled. This can relate to a file, a record, an area of [[shared memory]], or anything else that the [[application software|application]] designer chooses. A hierarchy of resources may be defined, so that a number of levels of locking can be implemented. For instance, a hypothetical [[database]] might define a resource hierarchy as follows:

===Resources===

The DLM uses a generalized concept of a '''resource''', which is some entity to which shared access must be controlled. This can relate to a file, a record, an area of shared memory, or anything else that the [[application software|application]] designer chooses. A hierarchy of resources may be defined, so that a number of levels of locking can be implemented. For instance, a hypothetical [[database]] might define a resource hierarchy as follows:

* Database

* Table

Line 18 ⟶ 15:

A [[process (computing)|process]] can then acquire locks on the database as a whole, and then on particular parts of the database. A lock must be obtained on a parent resource before a subordinate resource can be locked.

=== Lock modes= ==

A process running within a VMSCluster may obtain a lock on a resource. There are six lock modes that can be granted, and these determine the level of exclusivity being granted, it is possible to convert the lock to a higher or lower level of lock mode. When all processes have unlocked a resource, the system's information about the resource is destroyed.

Line 53 ⟶ 50:

|}

=== Obtaining a lock= ==

A process can obtain a lock on a resource by ''enqueueing'' a lock request. This is similar to the [[QIO]] technique that is used to perform I/O. The enqueue lock request can either complete synchronously, in which case the process waits until the lock is granted, or asynchronously, in which case an [[Asynchronous System Trap|AST]] occurs when the lock has been obtained.

Line 59 ⟶ 56:

It is also possible to establish a ''blocking AST'', which is triggered when a process has obtained a lock that is preventing access to the resource by another process. The original process can then optionally take action to allow the other access (e.g. by demoting or releasing the lock).

=== Lock value block= ==

A lock value block is associated with each resource. This can be read by any process that has obtained a lock on the resource (other than a null lock) and can be updated by a process that has obtained a protected update or exclusive lock on it.

Line 65 ⟶ 62:

It can be used to hold any information about the resource that the application designer chooses. A typical use is to hold a ''version number'' of the resource. Each time the associated entity (e.g. a database record) is updated, the holder of the lock increments the lock value block. When another process wishes to read the resource, it obtains the appropriate lock and compares the current lock value with the value it had last time the process locked the resource. If the value is the same, the process knows that the associated entity has not been updated since last time it read it, and therefore it is unnecessary to read it again. Hence, this technique can be used to implement various types of [[cache (computing)|cache]] in a database or similar application.

=== Deadlock detection= ==

When one or more processes have obtained locks on resources, it is possible to produce a situation where each is preventing another from obtaining a lock, and none of them can proceed. This is known as a [[Deadlock (computer science)|deadlock]] ([[E. W. Dijkstra]] originally called it a [[Deadlock (computer science)|deadly embrace]]).<ref>{{cite book|page=105|url=https://books.google.com/books?id=E6wOK8OYBG4C&pg=PA105|title=Ada: Concurrent Programming|isbn=9780929306087|author1last1=Gehani|first1=Narain|year=1991| publisher=Silicon Press }}</ref>

A simple example is when Process 1 has obtained an exclusive lock on Resource A, and Process 2 has obtained an exclusive lock on Resource B. If Process 1 then tries to lock Resource B, it will have to wait for Process 2 to release it. But if Process 2 then tries to lock Resource A, both processes will wait forever for each other.

Line 77 ⟶ 74:

Both [[Red Hat]] and [[Oracle Corporation|Oracle]] have developed clustering software for [[Linux]].

[[OCFS2]], the Oracle Cluster File System was added<ref>[https://www.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=29552b1462799afbe02af035b243e97579d63350 kernel/git/torvalds/linux.git - Linux kernel source tree]{{Dead link|date=July 2019 |bot=InternetArchiveBot |fix-attempted=yes }}. Kernel.org. Retrieved on 2013-09-18.</ref> to the official [[Linux kernel]] with version 2.6.16, in January 2006. The alpha-quality code warning on OCFS2 was removed in 2.6.19.

Red Hat's cluster software, including their DLM and [[GFS2]] was officially added to the Linux kernel <ref>[https://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=1c1afa3c053d4ccdf44e5a4e159005cdfd48bfc6 kernel/git/torvalds/linux.git - Linux kernel source tree] {{Webarchive|url=https://archive.today/20120718045424/http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=1c1afa3c053d4ccdf44e5a4e159005cdfd48bfc6 |date=2012-07-18 }}. Git.kernel.org (2006-12-07). Retrieved on 2013-09-18.</ref> with version 2.6.19, in November 2006.

Both systems use a DLM modeled on the venerable VMS DLM.<ref>[https://lwn.net/Articles/137278/ The OCFS2 filesystem]. Lwn.net (2005-05-24). Retrieved on 2013-09-18.</ref> Oracle's DLM has a simpler API. (the core function, <code>dlmlock()</code>, has eight parameters, whereas the VMS <small><code>SYS$ENQ</code></small> service and Red Hat's <ttcode>dlm_lock</ttcode> both have 11.)

==Other implementations==

==Google's Chubby lock service==

[[Google]] has developed ''Chubby'', a lock service for loosely coupled distributed systems.<ref name="chubby">[http://research.google.com/archive/chubby.html Google Research Publication: Chubby Distributed Lock Service]. Research.google.com. Retrieved on 2013-09-18.</ref> It is designed for coarse-grained locking and also provides a limited but reliable distributed file system. Key parts of Google's infrastructure, including [[Google File System]], [[Bigtable]], and [[MapReduce]], use Chubby to synchronize accesses to shared resources. Though Chubby was designed as a lock service, it is now heavily used inside Google as a [[name server]], supplanting [[Domain name system|DNS]].<ref name="chubby" />

Other DLM implementations include the following:

==ZooKeeper==

* [[Google]] has developed ''Chubby'', a lock service for loosely coupled distributed systems.<ref name="chubby">[http://research.google.com/archive/chubby.html Google Research Publication: Chubby Distributed Lock Service]. Research.google.com. Retrieved on 2013-09-18.</ref> It is designed for coarse-grained locking and also provides a limited but reliable distributed file system. Key parts of Google's infrastructure, including [[Google File System]], [[Bigtable]], and [[MapReduce]], use Chubby to synchronize accesses to shared resources. Though Chubby was designed as a lock service, it is now heavily used inside Google as a [[name server]], supplanting [[Domain name system|DNS]].<ref name="chubby" />

* [[Apache ZooKeeper]], which was created at [[Yahoo]], is [[open-source software]] and can be used to perform distributed locks<ref name="zookeeper">[httphttps://zookeeper.apache.org/doc/trunkr3.1.2/recipes.html#sc_recipes_Locks ZooKeeper Recipes and Solutions]. Zookeeper.apache.org. Retrieved on 2013-09-18.</ref> as well.

* [[Etcd]] is open-source software, developed at [[CoreOS]] under the [[Apache License]].<ref name="CoreOS">{{cite web|url=https://coreos.com/|title=CoreOS|website=coreos.com}}</ref> It can be used to perform distributed locks as well.<ref name="etcd">{{Citation|title=etcd: Distributed reliable key-value store for the most critical data of a distributed system|date=2018-01-16|url=https://github.com/coreos/etcd|publisher=CoreOS|accessdate=2016-09-20}}</ref>

* [[Redis]] is an open source, BSDRedis Source Available License licensed, advanced key-value cache and store.<ref name="redis">{{cite web |url=http://redis.io/ Retrieved|title= on|website=redis.io |access-date=2015-04-14}}{{title missing|date=May 2022}}</ref> Redis can be used to implement the [https://redis.io/topics/distlock Redlock Algorithm] for distributed lock management.<ref name="redlock">{{Cite web|url=http://redis.io/topics/distlock|title=Distributed Retrievedlocks onwith Redis – Redis|website=redis.io|access-date=2015-04-14}}</ref>

* HashiCorp's [[Consul (software)|Consul]],<ref name="consul">[https://consul.io/ Consul Overview]. Retrieved on 2015-02-19.</ref> which was created by [[HashiCorp]], is open-source software and can be used to perform distributed locks as well.

The* Taooka distributed lock manager Taooka<ref name="taooka">[http://taooka.com/ Taooka Description] {{Webarchive|url=https://web.archive.org/web/20170503112902/http://taooka.com/ |date=2017-05-03 }} Retrieved on 2017-05-04.</ref> uses the "try lock" methods to avoid [[Deadlock (computer science)|deadlock]]s. It can also specify a TTL for each lock with nanosecond precision.

* A DLM is also a key component of more ambitious [[Single-system image|single system image]] (SSI) projects such as [[OpenSSI]].

==etcdReferences==

etcd, is an open-source software, Apache Licensed developed at [[CoreOS]] <ref name="CoreOS">https://coreos.com/</ref> and can be used to perform distributed locks<ref name="etcd">[https://github.com/coreos/etcd/blob/master/Documentation/demo.md#distributed-locks]. Retrieved on 2016-09-20.</ref> as well.

==Redis Redlock Algorithm==

[[Redis]] is an open source, BSD licensed, advanced key-value cache and store.<ref name="redis">http://redis.io/ Retrieved on 2015-04-14</ref> Redis can be used to implement the [https://redis.io/topics/distlock Redlock Algorithm] for distributed lock management.<ref name="redlock">http://redis.io/topics/distlock Retrieved on 2015-04-14</ref>

==HashiCorp's Consul==

Consul,<ref name="consul">[https://consul.io/ Consul Overview]. Retrieved on 2015-02-19.</ref> which was created by [[HashiCorp]], is open-source software and can be used to perform distributed locks as well.

==Taooka==

The distributed lock manager Taooka<ref name="taooka">[http://taooka.com/ Taooka Description] Retrieved on 2017-05-04.</ref> uses the "try lock" methods to avoid [[deadlock]]s. It can also specify a TTL for each lock with nanosecond precision.

==SSI Systems==

A DLM is also a key component of more ambitious [[Single-system image|single system image]] projects such as [[OpenSSI]].

==References==

{{Reflist}}

{{Refbegin}}

* [https://web.archive.org/web/20101219074254/http://h71000.www7.hp.com/doc/82FINAL82final/4527/4527pro_044.html#jun_227 HP OpenVMS Systems Services Reference Manual – $ENQ]

* [https://github.com/chadrem/officer Officer - A simple distributed lock manager written in Ruby]

* [httphttps://sourceforge.net/projects/flom/ FLoM - A free open source distributed lock manager that can be used to synchronize shell commands, scripts and custom developed C, C++, Java, PHP and Python software]

{{Refend}}