Contact the author.
WHATIS-OpenDLM Copyright 2003 The OpenDLM Project Author: Ben Cahill (bc), firstname.lastname@example.org 1.0 Introduction ----------------- This document contains an overview of the OpenDLM Distributed Lock Manager. This document is aimed at developers, potential developers, students, and anyone who wants to know about the details of distributed lock management under OpenDLM. This document is not intended as a user guide to the OpenDLM API, although this document should serve as a good introduction to OpenDLM functionality. For a discussion of the API, as well as complementary discussion of the OpenDLM locking model, and configuration info, see "Programming Locking Applications" (dlmbook_final.pdf). Several topics are discussed in depth in that document; the author has kept discussion of those topics in this document complementary in nature. Much of this document is based on a one-hour interview session with Peter Badovinatz in October, 2003. Peter was the lead of a porting effort of IBM's DLM from the AIX operating system to Linux, before the project was dropped by IBM. Peter assisted with getting the current OpenDLM project going on Sourceforge, at http://opendlm.sourceforge.net, but is now stretched pretty thin as chair of the Carrier Grade Linux (CGL) specification committee, sponsored by the Open Source Development Lab (OSDL). The author is grateful for the time Peter spent describing the "big picture" of OpenDLM operation. This document may contain inaccurate statements, based on the author's limited understanding. In particular, the author has not studied any OpenDLM code (I'm trying to write up what Peter told me before it drops out of my head)! Please contact the author (bc) if you see anything wrong or unclear. 1.1 Terminology --------------- "Hold" and "Own" may be used interchangeably, to indicate that the lock holding/ owning compute node has been granted a lock, and therefore may access the entity protected by the lock. 2.0. Overview ------------------------------ OpenDLM is a true distributed lock manager. Knowledge of each lock is distributed among "interested" compute nodes within a cluster of computers, and each compute node contains and executes a complete set of logic for requesting and granting locks among the nodes. With OpenDLM, there is no single central lock server (i.e. a single computer that executes logic for managing locks for all nodes in the cluster), nor is there even a single central lock *storage* server (storing lock data, but not executing lock logic). Therefore, there is no single point of failure (SPOF) for OpenDLM. OpenDLM is efficient in terms of inter-node messaging. It uses a query/request/grant messaging scheme, described a bit later. This is much more efficient than a load/store polling protocol that repeatedly polls a central lock storage server. Such a scheme is used with the "memexp" lock module in the OpenGFS shared filesystem project. Polling can generate a *great deal* of internode LAN traffic when a lock is not immediately available. OpenDLM simply waits for a grant message, thus avoiding the repeated polling. Much of the incentive for developing OpenDLM is for using it with OpenGFS, a clustered/shared filesystem (http://opengfs.sourceforge.net). However, OpenDLM is a general purpose inter-node locking system that can be used at the application level as well, or for other kernel level uses beyond OpenGFS. See "Programming Locking Applications" (dlmbook-final.pdf) for a discussion of the user-level API. The kernel level API is more or less a subset of the user-level API. 3.0 Requesting and Obtaining a Lock ------------------------------------ Knowledge about a lock is divided into 3 different realms: -- Directory (node queried as first stop) -- Master (node containing lock state info) -- Requestor/Grantee (node that holds or wants to hold the lock) When a node needs a lock, it first queries the "directory" node. Each node in the cluster serves as a directory node for a range of lock names. The mapping of name ranges to nodes is well known across the cluster, so each requesting node knows which directory node to query, even for never-before- requested lock names. The well-known algorithm is based on a simple function of the lock name (e.g. the first character in the name). The directory node knows: -- whether a lock has ever been requested -- which node is the lock's master node When a directory node is queried about a never-before-requested lock name, the directory assigns the querying node to be the "master" for the lock, and creates a new directory entry for the new lock. The directory entry simply shows which node is the master; the directory contains no lock state information. Normally, the master will persist as the master of the lock forever, and the directory entry will not need to change. Since the new master had queried the directory because it was interested in obtaining the lock, the new master grants itself ownership of the lock. When a directory node is queried about a previously-requested lock name, the directory tells the requestor which node is the master. The requestor then requests the lock from the master. The master stores the state of the lock (which nodes hold the lock, and in which states), and is the single management server for the lock. With our earlier talk about SPOFs, you may be wondering about this a bit. We'll discuss it later under "Node Death". Note that the query/request/grant protocol efficiently overlaps message functionality between the directory, mastership, and ownership functions. The first node to request a lock handles only these two messages: -- the directory query (outbound) -- the response (inbound), which tells it to be the master (and grant itself the lock) Note also that a single node might be the directory, master, and owner of a lock. In this case, there would be no network traffic for this lock until another node requests it. 4.0 Lock Modes --------------- OpenDLM supports 6 lock modes. Some of these make sense only when you realize that they were intended for use in a hierarchical (parent/child) lock scheme: -- EX, exclusive mode, traditional write lock -- PW, protected write, traditional update lock -- PR, protected read, traditional shared read lock -- CW, concurrent write, see below -- CR, concurrent read, see below -- NL, null, unlocked placeholder, see below The EX mode is the most restrictive, and the NL is the least restrictive. If a lock is requested for a restrictive mode, it will not be granted until all holders of less restrictive modes (or, for some states, equally restrictive states) have given up their lock ownership. The NL state means that the lock is totally unlocked, but some node wants to keep the lock from being garbage collected. That is, the state is unlocked, but there is a lock usage count applied by at least one node, so the master and directory nodes maintain knowledge of the lock. The CR and CW modes are intended for use with a parent/child hierarchy, in which a relatively large area of memory, a directory, or other large entity is protected by a CR or CW lock. The following paragraph describes how this could be used, but please note that current OpenDLM implementation does *not* support this operation, because (in part) it does not support parent/child relationships (no parent is included as a parameter in the lock request call): While the CW lock would presumably allow concurrent writes of a large area by multiple nodes, it really should not directly write-protect the entire large area. Instead, finer grained, more restrictive locks (PW or EX) should be obtained to write into smaller areas contained within the larger area. These finer-grained locks would be requested as "children" of the larger CW lock (with the parent lock included as a parameter in the lock request call). The all-encompassing CW lock, when released, would in turn cause the release of all of the child locks, providing easy management of the large area and all of the small areas that it contains. There is more information on modes in the "Programming Locking Applications" document. 5.0 Lock States ---------------- A "lock resource" is the object contained in the master's memory, indicating the cluster-wide state of the locks associated with a given lock name. A given lock resource protects a single entity (e.g. file, data structure, etc.), and is identified by a unique name. Note that several locks may exist on a given lock name/resource, since many of the lock modes are sharable; several nodes or processes may simultaneously hold locks on the same lock resource. Locks may be in one of 3 states: -- Granted, lock is now in the mode requested -- Converting, waiting for grant to more restrictive mode -- Blocked, waiting for grant For each of these states, there exists a queue attached to the lock resource containing identities of the processes/nodes that hold locks in each of those states (only for this lock resource, of course). There is much more information on states in the "Programming Locking Applications" document. 6.0 Node Death, Lock Recovery, Orphan Locks -------------------------------------------- OpenDLM relies on a (separate) cluster manager to determine which nodes are active members of the cluster. When the cluster manager detects that a node has died, the rest of the cluster must recover the locks that were: -- held by the dead node -- mastered by the dead node -- contained in the dead node's directory A lot of the recovery process depends on whether any other node is interested in the locks held/mastered/directoried by the dead node. If no other node was interested in a particular lock at the time of death, the lock can be safely forgotten. If another node later becomes interested (i.e. requests the lock) the lock can be treated as a never-before-requested lock, thus creating a new directory entry, and assigning a new master. Actually, the recovery process works just like requesting a never-before- requested lock! 6.1 Directory recovery ----------------------- Directory support can migrate from node to node, and the distribution of directory responsibility (range of lock resource names) is based on the number of nodes in the cluster. When OpenDLM (that is, each computer still in the cluster) finds out that a node has entered or left the cluster, it redistributes the directories across the new inventory of nodes. This may mean copying directory information from node to node (if possible), or it may mean simply assuming responsibility for a range of names that was previously handled by a node that just died. In this case, the directory entries must be rebuilt, and new masters assigned, as surviving nodes query the directory (just like a never-before-requested lock). 6.2 Master recovery -------------------- It's important to realize that often, more than one node knows about a lock resource. If a master node for a particular lock resource dies, any other node that holds a lock on the resource, or is blocked waiting for a lock, knows who the master is, and also knows (by means of the cluster manager) that the master node has died. When a master node dies, holders/requestors query the lock's directory node. The directory node will assign the first such querying node to be the new master, and direct other requestors to the new node (just like a never-before- requested lock). 6.3 Owner recovery ------------------- If a lock owner dies, the master node treats the situation as if the dead node had just released the lock. Based on that, it may grant locks to other requesting nodes. "Orphan" locks do not behave that way; the master does *not* treat the dead node's lock as if it were released, and thus may not be able to grant locks to other requestors. See section 2.3.6 "Leaving the Grant Queue" in the "Programming Locking Applications" doc for more info. 6.4 Multiple recovery ---------------------- There are many cases in which a single node may be various combinations of directory/master/holder/requestor. 7.0 Message Ordering --------------------- OpenDLM does not assume that the communications protocol between nodes guarantees proper ordering of messages. OpenDLM has a significant amount of logic dedicated to remembering and re-ordering messages that arrive out of logical sequence. Even if the comm protocol guaranteed message order, the fact that the various nodes operate somewhat independently means that some crazy ordering can occur. For example, when a lock resource's master node dies, several nodes may query its directory node. The first will be assigned to be the new master. Others will request locks from the new master. Lock requests *could* arrive at the new master, before the new master gets the message that it is the new master! In such a case, the new master would need to remember these incoming lock requests, assuming that it *might* be becoming the new master. Logic for remembering and re-sequencing messages is split between the CCCP communication module and the lock management module. Peter suggested that the logic is not very clean (i.e. fairly intertwined and interdependent), and could benefit from some re-design. References: ----------- OpenDLM web site: http://opendlm.sourceforge.net (see especially "Docs/Info" page, via menu) OpenGFS CVS (browsable/downloadable via OpenGFS website): opengfs/docs/* Many docs are also mirrored to http://opengfs.sourceforge.net/docs.php Short descriptions of DLM and DLM API within HP OpenVMS: http://h71000.www7.hp.com/doc/731FINAL/5841/5841pro_021.html#145_conceptslocks http://h71000.www7.hp.com/doc/731FINAL/4527/4527pro_045.html