背景

RDMA

提到現(xiàn)成的 RNIC（例如，從 Mellanox Connect-IB 到 NVIDIA ConnectX-7）也支持掩碼原子 verbs，其性能類似于標準原子 verbs，但有更大的靈活性。

對于 masked-CAS，用戶需要提供一個比較位掩碼和一個交換位掩碼。比較和交換步驟均針對相應的位掩碼執(zhí)行。 屏蔽掉的位將不會被比較或交換。

對于 masked-FAA，用戶需要提供一個將 8 個字節(jié)拆分為不同字段的位掩碼。位掩碼中的每個設置位表示字段的左邊界，F(xiàn)AA 在每個字段內單獨執(zhí)行。邊界可以出現(xiàn)在任何位置；允許非字節(jié)對齊的字段。

Distributed Range Lock Management

CPU-based centralized solutions. 如 Figure 1（a）所示，現(xiàn)有的多數(shù)的 DRLM 都極度的依賴服務端的 CPU，范圍鎖操作通過 RPC 接口，基本上都由服務端的 CPU 執(zhí)行，這可能會限制吞吐并存在較高的排隊延遲了。用有限的 CPU 資源執(zhí)行復雜的范圍鎖操作不僅會成為吞吐量的瓶頸，而且會對 CPU 需求高的其他服務造成損害；使用 RPC 范例，服務端 CPU 從 RNIC 端隊列中獲取并處理 RPC 請求，在高并發(fā)情況下，請求會在 RNIC 中排隊，導致排隊延遲高，并且 CPU 不能處理同一隊列中的其他范圍鎖請求，即使它們在邏輯上不沖突。

Figure 1（c）是在測試平臺上運行 eRPC 來證明高延遲的實驗結果，客戶端同步向一臺服務器發(fā)送 RPC，RPC 處理程序運行 100 ns，測量服務器端排隊延遲，即 RPC 到達 NIC 和 CPU 處理 RPC 之間的時間。對于 32 個客戶端，平均排隊時延為 5.4 μs，比 RDMA 往返時間 (RTT) 的 2 倍還要多。p99 時延甚至達到 9.8 μs（4-5 RTT）。

Mutex-based decentralized solutions. ?將范圍劃分為多個段并將每個段與互斥體相關聯(lián)是分散的范圍鎖管理的一個想當然的解決方案，該方案只在訪問粒度是靜態(tài)且事先已知的情況下才有效。在未對齊或動態(tài)大?。╱naligned or dynamically-sized）范圍的情況下，該解決方案的吞吐可能會下降 92%，尾時延提高 5.65 倍。

設計

如 Figure 1（b）所示，基于單邊 RDMA 的 DRLM 可以消除排隊延遲并通過將所有鎖操作卸載到 RNIC 的定制 ASIC 來提供更高的吞吐量，充分發(fā)揮 RNIC 的性能潛力。

Challenges and Design Principles

Challenge 1. 需要一個單邊 RDMA 感知的數(shù)據(jù)結構，能夠有效地管理動態(tài)定位和大小的范圍鎖，并解決它們之間的沖突。

--> Static tree structure for dynamic ranges. ?Citron 將每個請求范圍（requested range）盡可能精確地映射到靜態(tài)數(shù)據(jù)結構線段樹（segment tree）上恒定數(shù)量的節(jié)點，以有效地管理動態(tài)范圍鎖條目。

Challenge 2. 為了實現(xiàn)低時延和高吞吐，必須根據(jù)復雜的范圍鎖語義調整鎖協(xié)議，以縮短關鍵路徑長度。

--> Minimized synchronization overhead. ?Citron 協(xié)議與 RDMA 語義以及線段樹的布局緊密耦合，使同步成本最小化接近常數(shù)。獲取鎖最少僅需要兩個往返。

Challenge 3. 真實的存儲資源不總是固定大小的，因此還必須有效地處理可能動態(tài)增長的存儲大小。

--> Runtime capacity expansion. ?雖然線段樹是靜態(tài)的，但較小的樹可以被視為較大樹的子樹，Citron 利用這個特性，使用少量的服務端 CPU 周期在運行時擴展樹的容量。

Basic Assumptions

Address space. Citron 在抽象地址空間 [0, ∞) 內維護范圍鎖。

Cluster infrastructure. 除了一個在 DRAM 中托管 Citron 組件的 lock server，Citron 需要有一個集群管理器（cluster manager，CM）和一個元數(shù)據(jù)服務器（metadata server，MDS）。CM 協(xié)調配置更改并檢測 client 故障。MDS 維護 Citron 組件的地址，以便使用單邊 RDMA。CM 和 MDS 不必在獨立的機器上運行：它們可以在 RPC 接口后面的 lock server 上運行。

Clock well-behavedness. ?Citron 假定所有 client 的時鐘都表現(xiàn)良好，即它們以幾乎相同的速度前進。Citron 不要求時鐘同步（synchronized）。

Components of Citron

Citron 使用 lock tree 和 spillover mutex 來維護范圍鎖。lock tree 負責 [0,N) 內的鎖，spillover mutex 體負責 [N,∞)，其中 N 在初始化時指定。Citron 還包括一個最大化器（maximizer），使 client 能夠擴展 lock tree，即增加 N。

Lock tree. Lock tree 是一個完美平衡的線段樹，其中每個節(jié)點代表一個連續(xù)的范圍。根（root）代表整個范圍[0,N)；對于每個非根節(jié)點，它和它的兄弟節(jié)點每個都接收到由其父節(jié)點表示的范圍的相等且連續(xù)的份額（均分）。這樣的結構決定了任何一個節(jié)點所代表的范圍都只與它的祖先和它的后代相交。正統(tǒng)的線段樹是二叉樹，該文將 Citron 中的 lock tree 定義為四元線段樹，即所有內部節(jié)點的度（即子節(jié)點數(shù)）均為 4，且葉節(jié)點表示的范圍大小為 64 。這些設計旨在限制樹的高度，從而限制每個鎖請求發(fā)布的需要的 RDMA verbs 的數(shù)量。

因為所有內部節(jié)點都具有相同的度，所以 lock tree 中不需要指針，所有節(jié)點都按級別順序放置在一個連續(xù)的平面數(shù)組中，并由正整數(shù)索引。 樹導航（tree navigation）只是簡單的節(jié)點索引算法。如 Figure 2 顯示了 lock tree 的前三個層和節(jié)點索引，其中節(jié)點的寬度對應于它們表示的范圍，可以很容易地得到對于索引為 x 的節(jié)點，

Spillover mutex. 溢出互斥量表示 [N,∞)，即 lock tree 處理范圍鎖請求的越界部分。它可以采用任何對單邊RDMA 友好的設計，該文使用 DSLR （SIGMOD 18 的一篇文章） 來實現(xiàn)這個互斥量。

Maximizer. 最大化器是一個初始為零的 8 字節(jié)變量，可由單邊 RDMA 訪問。當 client 鎖定不包含在 [0,N) 內的范圍時，client 會修改此變量。

Formats of Lock Tree Nodes

Lock tree 中的所有節(jié)點都是 8 字節(jié)的變量，可由各種 RDMA 單邊原語訪問。內部節(jié)點（Internal nodes）和葉節(jié)點（Leaf nodes）具有不同的格式，并由不同的 RDMA 原子動詞操作，如 figure 3 所示。

Leaf nodes. 葉節(jié)點是 8 字節(jié)位圖（bitmap），其中每個位都與一個共享存儲單元相關聯(lián)。位圖中設置位表示某個 client 占用資源的對應單位，反之亦然。client 使用 RDMA masked-CAS 來設置和清除 64 位中的每一位。

Internal nodes. ?每個內部節(jié)點分為六個字段。Exp 和 Occ 是標志位，其余四個是計數(shù)器。client 使用 RDMA masked-FAA 來修改這些字段。{TCnt,TMax} 和 {DCnt,DMax} 是遵循 Lamport 面包店算法思想的兩個計數(shù)器對。具體來說，在每個計數(shù)器對中，Max 是下一個可用的“票號”，Cnt 是當前持有鎖的票號。client 通過在 Max 字段上執(zhí)行 FAA 獲得票證，輪詢 Cnt 字段直到匹配票證，進入臨界區(qū)，最后 client 完成操作后在 Cnt 字段上執(zhí)行 FAA。{TCnt,TMax} 計算“本節(jié)點”（this node）的鎖請求，而 {DCnt,DMax} 計算后代的鎖請求。

Exp（代表擴展）通知 client lock tree 擴展事件。Occ（代表已占用）如果已設置，則會阻止后代的沖突的鎖請求。設置了 Occ 標志的節(jié)點將稱為占用節(jié)點（occupied node）。

Lock Acquisition

下面是該文主要的鎖策略。后面基本是圍繞下面的算法展開的。

算法 2 中的 k 和 m，先提前提一嘴，之后還會講，k 大致就是將實際要鎖的范圍劃分為 k 個 lock tree 中的節(jié)點，m 和鎖沖突通知的深度有關。TCnt 和 DCnt 在算法 3 釋放鎖的過程中更改。

算法 1 顯示了 client 如何獲取范圍 [l, r) 上的鎖，主要就是在判斷了要上鎖的范圍是不是在當前的 lock tree 中。 文章表示 spillover mutex 已經得到充分研究，所以該文省略了有關 spillover mutex 的詳細信息并專注于 lock tree。 現(xiàn)在假設 [l, r) 完全包含在 [0, N) 中，算法 2 顯示了整個鎖獲取過程，包括兩個步驟：

1. 將要鎖的范圍適當?shù)胤殖勺臃秶?，使得每個子范圍對應于單個樹節(jié)點；

2. 按升序獲取每個子范圍的鎖。

對于每個子范圍對應的節(jié)點，上面的步驟 2 進一步分解為四個階段：

2(a). ?如果是內部節(jié)點（internal node），則鎖定節(jié)點；

2(b). ?等待直到該節(jié)點所有的祖先節(jié)點的鎖都被釋放；

2(c). ?如果該節(jié)點是葉子節(jié)點則鎖定節(jié)點，否則占據(jù)（occupy）它；

2(d). ?通知該節(jié)點的祖先并等待其后代節(jié)點。

低（low）和高（high）描述遠離和靠近根的樹節(jié)點；范圍小的鎖請求具有更高的優(yōu)先級。

步驟 1：分割范圍

對應算法 2 代碼的 4-7 行

這一步不需要網絡的交互，因為 client 事先知道 lock tree 的結構并且可以在本地進行所有計算。使用線段樹，任何連續(xù)范圍都可以表示為 O(logN) 個樹節(jié)點的聚合，在最壞的情況下，必須鎖定 Θ(logN) 個節(jié)點以精確鎖定范圍 [l, r)，但是這可能會導致較高的時延，因為必須按順序鎖定節(jié)點以防止死鎖。一個想當然的方法是簡單地鎖定完全覆蓋 [l, r) 的最低節(jié)點，但是這可能會導致嚴重的沖突，如覆蓋 [N/2?1,N/2+1] 范圍的最低節(jié)點就是根節(jié)點，與所有其他鎖定請求沖突。

Citron 允許 client 最多鎖 k 個節(jié)點來達到平衡。為了減少錯誤的鎖沖突，Citron 嘗試最小化覆蓋但未請求（unrequested）的范圍。 該優(yōu)化目標可以表述為樹背包問題（tree knapsack problem）并通過現(xiàn)有算法解決。Citron 背包算法的時間復雜度為O(k的2次方 logN)，如果經過適當優(yōu)化，通常可以在 0.5 μs 內完成（沒提具體的算法，就這么提了一句）。 增加 k 以時延換取更少的錯誤沖突，反之亦然。Citron 為了低時延，將 k 固定為 2。

算法 2 中的過程 AcquireLockOnTree 顯示了此步驟的工作原理。首先運行背包算法來找到要鎖定的節(jié)點的最佳組合（第 5 行）。 然后，按順序鎖定節(jié)點（第 6-7 行）。

步驟 2：獲取鎖

a. 鎖定內部節(jié)點

對應算法 2 代碼的 9-11 行，主要是為了解決不同 client 對同一內部節(jié)點訪問的沖突，保證同一時刻只能有一個 client 對該內部節(jié)點進行操作。

工作流程遵循 Lamport 的面包店算法。 具體來說， client 首先增加節(jié)點的 TMax 字段以獲得“票”， 之后輪詢 TCnt 字段，直到它與“票”的 TMax 字段相匹配（第 10-11 行）。

b. 等待節(jié)點的祖先節(jié)點

對應算法 2 代碼的 12-19 行，主要是為了避免與祖先節(jié)點的沖突，如果祖先節(jié)點正被鎖住或者先發(fā)出鎖定請求，則等待祖先節(jié)點執(zhí)行操作。

從這個階段開始，Citron 開始解決不同節(jié)點之間的沖突，主要原則是在多個并發(fā)的鎖請求中，Citron 優(yōu)先考慮范圍最小的節(jié)點，因為它通常對時延最敏感。（但是暫時看下來該算法貌似只是優(yōu)先考慮小的節(jié)點，但是小的節(jié)點不一定是小的鎖范圍的，可能是大范圍剛好拆成一個大節(jié)點和小節(jié)點）

該節(jié)點的所有祖先都與該節(jié)點沖突，如果該節(jié)點的一個祖先持有鎖，client 必須等到它被釋放。代碼 15 行表示，如果根節(jié)點標記了拓展，則鎖操作直接中斷。

此階段由多次迭代組成，在每次迭代中，client 先讀取節(jié)點的祖先節(jié)點（第 14 行），然后查看祖先節(jié)點的 Occ 標志以確認是否存在被占用的節(jié)點。如果沒有 next 應該等于 nil，然后 17 行直接 break 退出迭代。如果有，則選擇最低的一個節(jié)點（最近的一個祖先節(jié)點）賦值給 next（第 16 行），之后 client 一直等到 next 節(jié)點的鎖被釋放（第 18 行），第 19 行以剛剛的節(jié)點為對象，重復新的一次迭代。因為節(jié)點是從低到高檢查的，且越高的節(jié)點和其他節(jié)點沖突的概率越大，祖先節(jié)點被占用的情況下，他的后代節(jié)點一定不會被鎖，所以迭代完成的瞬間，能保證這一刻該節(jié)點的祖先節(jié)點沒有被占用，沒有沖突。

c. 占用或鎖定節(jié)點

對應算法 2 代碼的 20-28 行，對于葉子節(jié)點直接用原子操作 CAS 去加鎖，內部節(jié)點用 FAA 將 Occ 加一表示搶占。

Client 目前可以確保節(jié)點的祖先沒有持有鎖（內部節(jié)點僅僅 Occ 位被標記不代表加鎖，但是不加鎖 Occ 位一定不被標記）。

如果節(jié)點是內部節(jié)點，client 使用 MaskedFAA 設置其 Occ 標志（階段 a 保證了同一時刻只會有一個 client 占用該節(jié)點，所以直接加一就行）。通過設置節(jié)點的 Occ 標志，新到達的節(jié)點后代的鎖請求將在步驟 2(b) 中檢測并等待 ，這確保了內部節(jié)點有限的等待時間。

如果是葉子節(jié)點，因為前面提到過，葉子節(jié)點的大小為 64，內部還可以劃分，所以 21 行首先將需要鎖定的范圍復制給 mask（應該是 64 位中需要的地方為 1 ，其他為 0 這個樣子），然后代碼 22 行 MaskedCAS 檢測需要的位置是否被占用，沒被占用的話應該是 0，如果是 0 的話，改為 1 （就是 mask），返回 true；但是前面的階段 a 和 b 都是針對檢查內部節(jié)點的（b 檢測祖先節(jié)點，祖先節(jié)點只會是內部節(jié)點），無法保證該葉子節(jié)點中被需要的位置沒有被占用或該時刻沒有其他 client 正在鎖定，所以可能會出現(xiàn)沖突，導致 MaskedCAS 失敗（即沒有 swap），之后就需要返回到步驟 2(b) 的開頭（第 26 行），因為其他 client 可能已經設置了該葉子節(jié)點祖先的 Occ 標志。為了避免饑餓，MaskedCAS 失敗多了，Citron 提供了一種變通方法，選擇鎖定該葉子節(jié)點的其父節(jié)點，重新啟動鎖獲取過程，因為上面提了通過設置內部節(jié)點的 Occ 標志，可以避免后代節(jié)點的鎖請求。

d. 通知祖宗節(jié)點，等待子孫節(jié)點

對應算法 2 代碼的 29-37 行，給低的節(jié)點優(yōu)先級，避免上下節(jié)點的沖突。

上面的階段只是勉強知道了那個時刻，節(jié)點的祖先沒有持有鎖，但是無法保證之后的祖先子孫鎖操作不會產生沖突，比如有 a，b，c 3個鎖請求，都是內部節(jié)點，且 a 是 b 的父節(jié)點，b 是 c 的父節(jié)點，同時到達，他們同時執(zhí)行完前面的階段，并將各自的 Occ 位標記，但是他們無法感知各自的存在，但是他們之間會產生沖突。因此需要一種機制來檢測。

有 2 種想當然的方案，第一個解決方案，由子孫節(jié)點去通知所有的祖先節(jié)點，但是這可能會導致小范圍鎖定請求的高延遲（越小的節(jié)點越低，需要通知的祖先越多）；第二種解決方案，由祖先節(jié)點去檢查該節(jié)點的所有后代是否存在可能的沖突，但是這可能會導致網絡流量過大，因為節(jié)點的后代數(shù)量隨著節(jié)點的高度呈指數(shù)增長。

然后 Citron 提出了一種折中的方案，維護一個全局一致的參數(shù) m，從該節(jié)點的父節(jié)點開始，通知到第 m 個祖先，并檢查 m 層內所有該節(jié)點的后代。就是對之前的方案進行了折中。lock tree 的節(jié)點在內存中是按層序排列的，且是連續(xù)的，所以檢測后代時，只需要 RDMA READ m 次。 在 Citron 的實現(xiàn)中 m = 4。

為了確保子孫節(jié)點在祖先節(jié)點檢查前完成了通知，祖宗需要檢查節(jié)點的后代之前等待一段時間 Twait，子孫確保在 Twait 內完成通知，若完不成則終止請求。為了確定 Twait，文章通過計算 RDMA 往返的最大次數(shù)，并為每個往返預留一個時間單位來確實，論文測試 RDMA RTT 約為 2 μs； 保守地為每次往返保留 5 μs，然后需要 3 個 RTT， 因此，Twait = 15 μs（具體的看論文）。

回到算法 2 代碼，首先 29 行獲取當前的時間，之后 30 行獲取需要通知的祖先節(jié)點，然后 31 行為這些祖先節(jié)點的 DMax 位加一，并讀取根節(jié)點的信息，32 行如果通知操作的時間超出了則終止，33 行是檢測是否 lock tree 在拓展，34 行對于內部節(jié)點（葉節(jié)點沒有后代）等待 Twait 時間，之后的代碼通過檢測子孫內部節(jié)點的 Dcnt 和 DMax 值是否相等來判斷子孫節(jié)點是否有沖突，若有則等待，反復檢查。Dcnt 在節(jié)點釋放鎖時改變。若子孫沒有沖突，Dcnt = DMax，返回 Acquired。

步驟 2(d) 依賴于正確選擇的 m 和 Twait 才能表現(xiàn)良好，然后論文還提了一下參數(shù)調整，這里不寫了。

Lock Release

算法 3 是鎖釋放過程，對于范圍內的所有節(jié)點，如果節(jié)點是葉子節(jié)點，使用 MaskedCAS 解鎖（第 3-5 行，這次反過來賦值為 0）；對于內部節(jié)點，使用 MaskedFAA 清除 Occ 標志，將 TCnt 計數(shù)器加一（第 7 行）。之后對于在鎖獲取期間已被通知的所有節(jié)點的祖先，使用 MaskedFAA 將他們的 DCnt 計數(shù)器加一（第 8-9 行）。 在后面是拓展時的操作。上面的操作需要的 RDMA verbs 都可以一起批處理以減少延遲。

Proof Sketch of Correctness

Citron 中的范圍鎖由 lock tree 上的節(jié)點和可能的 spillover mutex 組成，所有這些都是單獨和順序獲取的。 spillover mutex 的正確性已經被其他論文證明，只需要證明鎖在單個樹節(jié)點上的正確性即可。

如圖4所示（圖沒啥多的解釋。。），無論沖突什么時候發(fā)生，Citron 都能解決，具體來說，步驟 2(a)+(c) 確保節(jié)點處不存在沖突的 client：2(a) 用于內部節(jié)點，2(c) 用于葉節(jié)點。步驟 2(b) 和 2(c)+(d) 分別確保節(jié)點的祖先和后代不存在持有的鎖。 （具體說步驟2(a)保證了同一內部節(jié)點不會產生沖突，步驟2(c)避免了葉子節(jié)點之間的沖突，步驟2(b)將沖突的節(jié)點拉到了同一起始時間，之后在步驟2(d)中，因為都是先執(zhí)行通知祖先的操作，祖先節(jié)點在子孫節(jié)點執(zhí)行并釋放前被只能等待，最低的節(jié)點最早執(zhí)行，避免了沖突）

Liveness. Liveness 意味著沒有無限長的臨界區(qū)(等待時間)，鎖獲取過程總是在一些有限的時間返回（盡管結果可能是 Aborted）。具體來說，第 1 步是有限的。步驟 2(a) 使用 Lamport 的面包店算法，它是無饑餓的。由于饑餓避免機制，步驟 2(c) 對于內部節(jié)點顯然是有限的，對于葉節(jié)點也是有限的。對于步驟 2(b) 和 2(d)，client 在每個階段只能等待有限數(shù)量的其他 client，因為這些 client 最終會中止或釋放他們的鎖，所以這些階段也是有限的。 綜上所述，鎖獲取需要的時間是有限的。

不過暫時沒有看到對于返回 Aborted 的情況的處理，返回 Aborted 時，可能更改了 TMax，Occ，DMax 等，應該會有相應的處理？

Fast Path Optimization

就是操作的優(yōu)化，減少 RDMA RTT。

當 Citron 未處于嚴重爭用狀態(tài)時，多項優(yōu)化適用于鎖獲取路徑。首先，RDMA 在同一 QP 中對任何單邊 verbs 的保序性，可以將鎖獲取路徑中的 RDMA 動詞一起批處理（具體看論文）。

其次，如果節(jié)點的子節(jié)點都是葉節(jié)點，可以顯式鎖定所有節(jié)點的后代以跳過步驟 2(d) 中的等待時間（具體看論文）。

通過這些優(yōu)化，樂觀地說，獲取鎖只需要兩次 RDMA 往返，確保低延遲。

Scaling the Lock Tree

Scale up

存儲資源的大小可以隨著寫入而增長，可能會出現(xiàn)不包含在 [0,N) 內的越界鎖定請求，并將爭用 spillover mutex。利用線段樹的結構自相似性，即小樹可以看作是大樹的子樹，Citron 提供了在運行時擴展鎖樹的選項。 Citron 使用 MaskedCAS 來決定 lock tree 應該擴展到多大。當比較掩碼為零時，MaskedCAS 提供按位或（OR）語義。出于這個原因，Citron 包含一個最大化器：client 可以使用單邊 MaskedCAS 將越界鎖請求的右邊界與最大化器進行或運算，從而能夠檢測到此類鎖請求。最大化器的值最多是實際最大值的 2 倍。?

client 擴大 lock tree 可以通過 RDMA 讀取最大化器，并在發(fā)現(xiàn)非零值時執(zhí)行擴大。算法 4 顯示了按比例放大的過程。client 首先獲取 spillover mutex（第 2 行）以確保鎖定安全并防止同時進行擴展嘗試。之后 client 向 server 發(fā)送一個 RPC 以分配線段樹的擴展部分（第 3 行）。舊的 lock tree 并沒有移動，它將與新分配的節(jié)點組成一棵新的樹，如圖5。client 然后設置舊樹的前 m 層所有節(jié)點的 Exp 位以讓其他 client 感知放大事件（第 4-5 行）。 之后還需要將這些節(jié)點的 DCnt 和 DMax 計數(shù)器傳播給它們的新祖先（第 7-8 行）。一個被占用的節(jié)點占一個額外的 DMax 單位。最后使用更新的配置更新元數(shù)據(jù)服務，包括 lock tree 的原始部分和擴展部分的地址，清除最大化器，并釋放溢出互斥體以完成鎖樹的擴展（第 9-11 行）。

Handling scale-ups in lock acquisition. 在獲取鎖時（算法 2），另一個 client A 必須考慮到其他的 client 如 B 可以同時擴展 lock tree。具體來說，在步驟 2(b) 中，A 在讀取根節(jié)點時檢查 Exp 標志（第 15 行），在步驟 2(d) 中，A 需要在通知節(jié)點的祖先后讀取根節(jié)點（第 31 行）。如果節(jié)點的需要通知的最高的祖先和根節(jié)點的 Exp 標志都已設置（第 33 行），則此時一定在進行樹的擴展。A 平凡地處理并發(fā)擴展（即 A 中止并重試）。Handling scale-ups in lock release. Lock tree 也可以在 client A 獲得鎖之后和釋放鎖之前按比例放大。執(zhí)行拓展的 client 將代表 A 通知節(jié)點的新祖先。因此，A 還應該添加節(jié)點新祖先的 DCnt 計數(shù)器（算法 3，第 10-12 行）。

Scale down

與 scaling up 不同，scaling down 不能由寫入觸發(fā)，在大多數(shù)情況下本質上是一個阻塞操作。例如，在文件系統(tǒng)中，調用 ftruncate 來縮小文件將獲取其 inode 互斥鎖并阻止所有其他 I/O 嘗試。在阻塞縮小操作期間，Citron 可以通過刪除除子樹之外的所有節(jié)點來安全地縮小其鎖樹。

Handling Client Failures

要啟用恢復，所有 client 必須同意一個租約時間 T_lease，并且必須在 T_lease 內釋放范圍鎖。

Detection. Citron 依靠集群管理器 (cluster manager，CM) 來檢測 client 故障。CM 通知 lock server 銷毀故障 client 連接的 RDMA QP。

Recovery. 如果 client 在鎖定獲取期間在某個地方等待的時間長于 T_lease，則會檢測到失敗，包括算法 2 中的第 11、18 和 36 行，在第 22 行失敗太多次，也會懷疑失敗。（具體看原文）

實驗

搞不動了。。直接放幾張圖吧。

個人看法

這篇文章是第一個使用單邊 RDMA 原語針對分布式范圍鎖管理優(yōu)化的文章。其中關于鎖的部分，不是特別的了解，所以花了不少的時間來看這篇文章。說是 RDMA 的吧，其實感覺也沒有那么深，更像是套個 RDMA 的幌子，感覺最近的很多文章主要集中在單邊 RDMA 原語（基本只用單邊）去適配優(yōu)化某一應用，或者發(fā)掘出一些之前沒被注意到的 RDMA 特性，如這篇文章的 masked-CAS 和 masked-FAA，其他文章中提到的 DTC，網卡內存等。

題外話，寫這個太花時間了，打算先水一水論文（畢不了業(yè)了），之后寫不寫看情況。

如果問題，歡迎指正~~~~~~~~~~~~~~