Oracle RAC的dlm以及OCFS2和GFS2的dlm的设计来自于本篇文章。
背景
Oracle RAC的cache fusion在多个实例节点操作相关联page时，需要对page上锁，因此就需要有一个高性能的分布式锁的组件了，同时这个分布式锁提供global directory service。
一般所说的分布式锁etcd，zookeeper这种是基于复制协议协议实现的分布式锁，主要使用场景是配置管理，集群拓扑变更管理，事件监听等，是控制面的；复制协议运行过程中，会对log进行落盘；
而Oracle RAC cache fusion是内存的，允许节点上锁信息丢失。负责实例运行期间的多个节点之间的协调，因此：
- 数据面的，要求高性能；
- 锁的信息无需落盘；
Oracle RAC的分布式锁，OCFS2中的dlm，以及GFS2中的dlm都参考了80年代DEC公司的VAX/VMS分布式操作系统中锁的设计。
dlm是Distribute Lock Manager的简称，个人理解也是decentralized lock manager的简称。这几个
系统使用的dlm是去中心化的设计，所有的节点是对等的，每个节点都只存储了一部分的锁信息。
一个锁涉及到3个角色：
- requester node：发起上锁的节点；
- directory node：这个锁的目录节点；
- master node：这个锁内容的维护节点；
在dlm中，一个锁的信息有2个副本：
1. master：这个锁的真正管理者，维护该锁的2个队列，以及状态；
2. shadown：存在requester的本地的一个结构，维护当前节点已经上了哪些锁，以及锁的模式等；
通过一个例子来说明上锁的数据流。3个节点，A，B，C，
1. A计划对资源R1上锁，先在本地构造该锁local的结构，也称为锁的shadow；
2. 节点A，通过R1的id以及一个hash函数，计算出这个R1所对应的目录在B上；
3. 节点A请求节点B，得到R1的目录信息，目录信息很简短，只是记录了R1的锁的master在C上；
4. 节点A向节点C发射对R1上锁的请求；
5. 节点C维护R1的锁请求队列，如果允许A上锁，则返回成功；
6. A更新本地R1锁shadow相关信息，上锁成功；
整个过程中需要2次网络的roundtrip，大部分场景可以优化到1个或者0个。
Lock Manager Description
unique lock id
每个需要锁保护的资源都要有唯一的id，id本身只是一个符号，和资源本身没有任何关系。比如，可以用namespaceid + relationid + pageid来做为page的id。
因此可以把需要保护的资源组织成树状的形式，比如文件系统本身就是一个树状结构，可以用路径做为一个文件的id，通过树状的父子继承关系上锁可以在不同的level上优化锁的粒度。
由于锁并不要求一定要有一个实体的resource与之对应，因此dlm不仅可以保护资源，还可以用来在不同节点间对某个事件同步，以及事件通知。
lock model
dlm抽象出了6种锁模式，严格度高的锁可以向严格度低的锁模式转换。下面是6种模式以及每种模式使用场景。
ast
dlm锁的api提供异步接口，以执行回到函数，当上锁成功后就会被触发，称为ast: asynchronous system trap；
bast
场景：对于竞争比较低的资源，进程A得到锁之后，可以一直访问资源而不用都每次上锁（或者释放锁），直到，进程B偶尔也需要访问该资源，尝试上锁。
dlm提供了bast，使得进程A在持有锁时，进程B也要上锁，此时进程A可以得到通知，并且主动释放该资源，这样进程B有机会得到锁（Oracle RAC的优化）。
可以在bast模式和request-release之间切换。
door bell
door bell功能：进程A指定了bast，进程B可以上非兼容锁，进程A通过bast得到通知。
value block
每个锁可以关联value block：16字节，可以选择性的返回，在释放EX和PW时被更新，可以存储一个资源的最新的版本号。比如：当更新一个数据块时，先上PW锁，然后更新，然后释放锁，此时可以把data的最新版本号存入value block，以便其他读者可以比对，如果相等就说明local的buffer是新的可以直接使用。
也可以在本地用来缓存资源id对应的小对象。
Connection Manager
dlm只负责完成锁相关的语义，集群的membership和上下线由connection manager组件负责。当发生网络分区，connection manager通过voting算法负责选举出一个最大的联通的节点集合，然后由dlm完成memship的变更。
connection manager的另一个作用是：提供dlm各个节点间的虚拟网络链路。
猜测是connection manager的实现：在每个运行dlm进程的机器上，运行一个connection manager进程，负责监控dlm进程状态，网络分区情况，同时dlm的网络转发功能（类似DTL），保证消息的按序达到，减少总的连接数。
DLM内核
Initial Lock On Root Resource
节点A对资源上锁步骤：
1. 在本地构建root-lock相关结构：resource block和lock block；
2. 对id进行hashed，找到directory node B；
3. 向节点B询问该资源的lock的master是哪个节点，3种情况：
a. B上没有该资源的记录，说明第一次对该资源上锁，采用先到先得，节点A成为该资源的master；
b. B上记录该资源的master是其他节点；
c. B上记录该资源的master是节点A（节点A之前并不知晓，可能是因为锁的migration导致A成为了该资源新的master）；
4. 节点B上新增记录：该资源的master是A（由于本小节讨论的是第一次上锁，因此节点上没有出现过该资源的记录）；
5. 节点B告知节点A为master，并上锁成功；
Sublock on resource manager
节点A后续对该root-lock的子节点上锁时，可以直接本地操作，而不同询问其master在哪个节点上。
root-lock成功之后，后续的subblock的请求如果是第一次发生，则直接在本地处理，并且挂在rootblock的下面做为子节点；
Rootlock on other node
节点A在后续请求root-lock时，可以直接操作本地，因为它获取到了master。
节点C在第一次请求root-lock时，需要请求一次directory node，因为它并不知晓该root-lock的master（可能是第一次上锁，也可能是已经被别人上锁成功）。
Subsequent root-lock
对sub resource上锁，根据父节点直接给master节点发送上锁请求，无需请求目录节点。
Release Lock Requests
master节点释放锁
如果是最后一个锁的owner释放锁，则需要给目录节点发送消息，以便它可以删除这个id在目录中的槽位。
这样允许后续的上锁者成为新的master。但是这个消息不需要directory node回复response，因为connection manager保证了消息的到达。
非master节点释放锁
如果最后一个释放锁的并非master，直接给master发送释放锁消息，然后节点A发现是最后一个锁，则给directory node节点B发送释放目录id的消息。
Resource Contention
当master发现锁冲突时：
1. 通知所有该锁holder的bast回调（对于一个holder仅仅通知一次，即使有后续他请求者诞生，因为锁只能一个人获取到，通知一次后holder可以自主退出，当前请求才会成功，因此只需通知一次）；
2. 告知正在请求者被block住了；
当锁被释放后（自然释放，或者上锁者主动释放），给所有符合条件（都上read锁）请求者发送消息。
dlm消息数目总结
可以看到最多只需要4个消息，2个roundtrip，大部分产经需要2个以下就可以了。
membership change
connection manger 触发membership变更：所有的节点自发的选出一个leader做为协调者，来驱动其他节点一起完成状态变更。任何运行dlm的进程都可以成为leader。
变更包含两个部分内容：
1. 节点拓扑的变更，所有节点需要对拓扑的变化达成一致（否则会有正确性问题）；
2. dlm的变更；
成员拓扑的变更
为了保障拓扑的变更是一致性的，变更是个2PC过程：leader给所有其他节点发送proposed，如果都接收才进入commit。
leader发送的拓扑关系图也可能被其他节点拒绝：该节点发现了更加优的拓扑。最终要求拓扑是全联通的，而且是最大的一个；如果被拒绝，leader回退，等待随机时间，再次发起选举；
如果所有节点接受新的拓扑，则发送commit消息。
2PC保证所有节点对membership是一致的，包括目录的hash结构也是一致的。
dlm rebuild
节点拓扑变更之后，leader协调所有其他节点进行dlm lock database的重构：过程拆分成多个step，每完成一个step，leader就通知其他所有节点一起进入下一个step；
单node重构
一个节点超时，会优先尝试恢复这个节点，而不是移除这个节点，这样会导致集群拓扑变化rebuild过程很漫长。
该过程，dlm集群仍然继续提供服务，发往该节点的dlm请求会先在本地缓存住，等恢复之后再重新发送给该节点。
过程中只有涉及到重启节点为master的锁相关信息丢失了（一部分），其他节点无感知：
重启节点后，它上面的master锁只丢失了一部分，仍然能恢复出大部分，重启之前它上面的master锁分为：
- local locking：发起者正好是重启节点，那么其他节点可能不知道该锁的存在，因此无法恢复，也无需恢复；
- remoting locking：发起者是其他节点，存储了shdow信息，那么可以通过这些shadow信息可以恢复出重启前的锁状态；
因此，** 单节点重启可以做到无感知。**
单个节点重启恢复（重建目录，重建master，清除local），恢复骤：
1. 重建目录，从其他节点上扫描master，并hash，如果命中了重启节点，则在重启节点的目录结构中重新插入一遍；
2. master资源的构建，可用从其他节点shadow查找，并重新构建锁队列；
3. 清除local资源：从其他节点扫描master，如果发现锁的持有者是重启节点，则清理掉；
集群重构
当节点加入或者剔除时，拓扑发生了变化，directory的hash函数变化，此时需要所有dlm暂停服务。
1. 所有节点清空目录和master锁；
2. 使用存活节点本地的lock和resource块重新走一遍上锁（并发执行，一定能成功），这样就能把新的目录建立起来了。排队中的锁仍然按照序列号插入到master的队列中，已经获得锁的仍然获得锁；
3. 最后每个节点需要把等待锁的尝试走一遍grant逻辑，因为节点退出后，可能会导致资源可用；
dead-lock
dlm中存在两种类型的死锁：
1. 相同资源上：lock convert。比如同时对资源R1从CR到EX。因为是单个资源，因此单机上可以处理；
2. 跨机死锁：不同资源上锁，最终导致出现循环；
死锁检测的算法就是在多个节点上搜索是否wait-for图中出现了环。
从超时锁的进程开始触发死锁检测算法，搜索是否能back to当前进程（存在环）。
在寻找环时，发现目标资源对应的owner不在本地，则向目标发节点送消息，内容是：
1. 发起死锁检测的节点id；
2. 下一步要寻找的资源R集合；
相邻节点收到消息后，则继续递归查找，判断死锁的条件：能否找到回到节点的环。
每次发送的目的地是：依赖锁的的master节点，因为它上面记录了哪些进程持有了该锁。以及他们进一步又持有了哪些锁；
为了避免死循环和加速查找：每个节点上通过bitmap记录是否曾经参与过搜索，后续忽略这类消息。带来的问题是：无法确认这个bitmap何时要被清理，因为最终没有死锁时，算法是不会有output的，也就无法清空bitmap；如果发现了死锁，算法可以结束，同时清空bitmap。
解决的方法：
1. 选出一个node提供timestamp服务；
2. 每次开始deadlock检测记录时间；
3. 下一次记录时需要超过租约；
总结
Oracle RAC在dlm上的积累了很多优化的方法（dlm层面和业务层面）；
dlm是一个去中心化的设计，recovery流程很复杂也很难实现对；
dlm在节点数目变更时使用了remaster的方法，可以考虑一致性hash来优化；
通过RDMA的CAS原语来实现去中心化的锁，也值得关注。
