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原語來實作去中心化的鎖，也值得關注。