這篇paper中提到的lock與lock manager專指database的lock，尤其被廣泛運用在分散式雲端系統
Abstract
- 傳統的centralized lock manager雖對policy的支持較為彈性，但會面臨效能問題
- decentralized lock manager則與上述centralized lock manager的特性完全相反
- 上述兩者的效能皆受限於server的capability
- 本篇paper試圖改良傳統的lock manager所擁有的缺點
1 Introduction
- 現在有許多企業使用雲端服務，尤其是由雲端服務商提供的database服務
- 由於要面對許多要access shared resources的concurrent transaction，lock manager就變得極為重要
- lock manager分為以下兩種 (前人的方法)
- centralized lock manger
- 由server grant lock給client
- 優點：
- 這方法會使用一個或多個對於所有lock operation有global view的server作為central point來grant lock
- 由於對所有lock operation有global view，所以可以輕易的支援多樣的policy，像是starvation freedom & fairness, service differentiation, and performance isolation
- 缺點：
- 當transcation throughput增加，server的CPU成為該方法最大的bottleneck
- decentralized lock manager
- client透過RDMA自己去server的memory做acquire & release的資訊
- 優點：
- 為了解決上述提到的CPU造成的bottleneck，採用RDMA技術，不經server的CPU和OS直接access server的memory
- 缺點：
- 由於這方法的lock是各個client自己去server的memory做acquire & release，所以很難支援也很難強制所有client使用太豐富的policy
- centralized lock manger
- NetLock團隊所改善的點
- 團隊注意到lock資訊其實只是一些需要高速且concurrent access的metadata所組成，且這些metadata遠小於database中所存的資料
- 利用switch處理大部分popular lock來加快速度並降低latency，改善centralized lock manager的缺點
- 另外，NetLock所採用的是centralized技術，所以也能夠支援較為豐富的policy，避免了decentralized lock manager的缺點
- 要想同時達成快速、低latency、支援豐富的policy至少須面對下列2項問題
- memory問題
- 即便lock資料遠小於database所存之資料，但要處理所有cloud database的lock info還是可能塞爆switch的memory
- 有前人提出用server的memory去擴充switch的memory，但該方法並未對memory的管理提出穩定的解法
- sol：NetLock只將popular lock給switch處理，剩下的仍交由server負責
- switch功能不多的問題
- 在data plane的部分，switch功能並不多，不一定能處理好lock request
- 有前人示範了如何在switch上存key-value類型的資料且解決了容錯的問題，但完整的lock manager只有key-value是不夠的
- sol：使用新興的programmable switch來實作lock manager所需之功能
- memory問題
- 要最大化memory使用率並避免memory的碎片化，他們設計了shared queue將多個data plane stages的register arrays集中並分配給lock，使得每個lock都有自己的連續空間
- 因為switch的register array並不支援enqueue跟dequeue所以該shared queue採用circular queue的結構
- 另設計match-action table來支援使用common policy的shared & exclusive lock
- NetLock的實現不必重新架構整個網路，只需增加幾台設計過的ToR switch
2 Background and Motivation
2.1 Background on Lock Management
- Centralized lock management
- can be distributed，但仍由server運算並決定lock的grant
- lock manager可與storage server放在同一台server，也可以將多個storage server的lock manager合併到一個專用的server，需注意的是前者會佔用storage server的運算資源
- Decentralized lock management
- decentralized lock manager還是有專責的server在維護每個lock所需的info，但不參與lock的grant，而是由client們自己follow RDMA所支援的protocol (如：SEND、RECV、READ、WRITE等指令)來搶lock
- 無法像centralized lock manager一樣可以強制套用指定的locking protocol
2.2 Exploiting Programmable Switches
- 利用programmable switch達成high proformance和policy support
- 也可使用programmable NIC，但本paper著重在switch上
3 NetLock Architecher
3.1 Design Goals
- High throughput
- Low latency
- Policy support
3.2 System Overview
- 採用NetLock架構的機櫃中會有1台ToR switch和多個server
- 不同的database rack會有自己的NetLock instance
- client送出lock request後，NetLock中的switch會檢查自己是否應對該request負責
- 若是，則調用已編譯好的data plane module處理該request
- 若否，則將該request forward給server
- switch只負責儲存並處理popular lock，而lock server則必須負責unpopular lock
- 當switch的buffer滿了，lock server還需幫忙暫存要給switch處理的popular lock request (注意只負責暫存，不負責處理)
4 NetLock Design
4.1 Lock Request Handling
- 1 RTT transaction
- 有些distributed transaction system，像是DrTM、FARM、FaSST將lock acquisition和data fetching結合在一起，以達到在1 RTT中完成整個transaction
- NetLock效法這種想法，提出以下做法
- lock由switch負責
- 由switch檢查是否grant lock，當lock granted，NetLock不會回傳封包給client告訴他們lock granted，而是直接forward client的request封包給database server，如此一來也能達到在1 RTT中完成整個transaction
- 當payload有write的行為，如果lock能grant，switch會forward封包，如果不能grant會直接drop
- lock由lock server負責
- lock server跟database server合體，當lock granted，便可以直接給database server處理達成1 RTT中完成整個transaction
- lock由switch負責
- 但像是read-modify-write這類操作就不能在1 RTT中完成 (因為client讀完值必須做些計算後再寫值，但NetLock系統並不支援在server端幫client計算)
4.2 Switch Data Plane
- 使用circular queue，所以有pointer紀錄head & tail
- 保留額外的register來存head跟tail的pointer
- pointer碰到array end的時候會loop back到beginning
- Optimize switch memory layout
- 由於switch的memory在程式compile完成並部署到switch上後便不可再更改，故採用shared queue，即Queue A有可能同時橫跨多個register array
- 採用shared queue必須保留額外的register來存每個queue的boundary，這也使得boundary可在runtime動態調整
- Handle shared and exclusive locks
- 當1個packet被送進switch時，switch的data plane只能對register array做1次read or write，這會造成2個問題
- 當switch收到lock release訊息時必須執行dequeue the head和read the new head這2個動作
- 當switch收到share lock請求，且queue中的下個請求也是shared lock則必須一起grant lock，這需要執行複數的read (直到read到exclusive lock request或是queue tail)
- sol：使用programmable switch中的resubmit功能將封包送至packet processing pipeline的開頭，從頭做process
- 當1個packet被送進switch時，switch的data plane只能對register array做1次read or write，這會造成2個問題
- 用resubmit check new head
- Shared $\to$ Shared：stop processing
- Shared $\to$ Exclusive：grant 1 lock給該request並停止resubmit，switch會送notification給client告知lock granted
- Exclusive $\to$ Shared：重複resubmit並grant lock直到遇到exclusive lock或queue end
- Exclusive $\to$ Exclusive：grant 1 lock給該request並停止resubmit，switch會送notification給client告知lock granted
- Pipeline layout
- lock table和他們的register array會放在連接到lock server的egress pipe以避免不必要的pipeline之間的recirculation
4.3 Switch-Server Memory Management
- Memory allocation mechanism
- 名詞解釋
- $r_i$：obj $i$每秒收到的lock request數量
- $c_i$：obj $i$最多會收到的concurrent request數量
- $s_i$：obj $i$在switch裡的queue size
- $S$：switch的memory size
- NetLock試圖最佳化以下問題
- $maximize \sum_{i}^{}r_is_i/c_i$
- $\sum_{i}^{}r_is_i/c_i$是switch所保證能夠process的request rate
- 最大化switch所保證能夠process的request rate
- $\sum_{i}^{}r_i/c_i$是該obj平均的request rate
- 又可解釋為讓平均request rate最高的obj在switch中獲得最多的memory
- $s.t. \sum_{i}^{}s_i \le S$
- 所有obj在switch中分到的queue size和一定小於等於switch的總memory size
- $s_i \le c_i$
- 沒必要給某obj分配超過”最多會收到的concurrent request數量”的queue size
- $maximize \sum_{i}^{}r_is_i/c_i$
- 名詞解釋
- Performance guarantee
- 名詞解釋
- $r_s$：switch所能支持的request rate
- $r_e$：server所能支持的request rate
- 假設switch不是bottleneck
- $r_s \ge \sum_{i}^{}r_i$
- 此假設有依據：若switch是bottleneck則switch已開始壅塞，會導致並非所有lock request都能好好被grant，則整個workload都是無意義的
- switch可以process $\sum_{i}^{}r_is_i/c_i$的request rate
- 且需要$\lceil(\sum_{i}^{}r_i-\sum_{i}^{}r_is_i/c_i)/r_e\rceil$台server來服務剩下的request rate
- 名詞解釋
- Handling overflowed requests
- overflow發生於switch不能allocate足夠的memory給他所handle的最後一個obj或是錯估了obj的maximum contention
- 在lock server開一個queue去存從switch overflow的request (注意只存不處理)
- switch會對封包放個mark以區別暫存在server的request跟原本就給lock server處理的request
- 只有在switch queue中的request會被grant並dequeue
- 當switch中的queue終於被清完時 (過程中新的request會被送到server暫存)，switch會通知server，server會放行一些request給switch (放行數量不超過switch的available slot數量)
- Moving locks between the switch and lock servers
- 要move lock時，NetLock會暫停該lock的新request被enqueue，直到該queue被清空
- switch中的memory layout會定期調整以避免lock移動中造成的memory碎片化
4.4 Policy Support
- Starvation freedom
- 使用FCFS policy (亦即queue是FIFO的queue)即可避免starvation
- 但deadlock造成transaction的未完成也可能導致starvation
- Service differentiation with priorities
- switch有很多stage，每個stage中都allocate 1個queue來表示priority
- 因為封包的處裡是stage by stage所以高priority的request會在早期的stage就被grant
- priority queue也可以橫跨多個stage來擴充queue size
- 此方法會被switch所支援的stage數量限制
- sol：將一些相近的priority合併或是把低priority的request當成unpopular lock通通丟到lock server處理
- Performance isolation with per-tenant quota
- rate limiter可用自動限制tenant的meter或自動計算tenant的request數並和quota做比較的counter來實做
4.5 Practical Issues
- Switch memory size
- NetLock使用optimal knapsack algorithm來有效地allocate memory
- think time會決定memory slot的maximum turnover rate
- 會跟著影響switch所能support的maximum throughput
- Scability
- 因為是ToR switch所以極易設置，當機櫃增加時只要連上具有NetLock架構的switch跟lock server即可
- Failure handling
- 離不開lease (租約)這個概念
- Transaction failure
- 當network loss、application crash或client failure造成transaction fail且未release他拿到的lock，讓後面的人都等不到lock
- sol：每個lock都會被記錄timestamp，當租約到期transaction就會過期，switch的control plane會定期去data plane清理過期的transaction
- Deadlock
- lock設計不良導致大家互相等對方release lock
- sol：一樣靠租約到期來清理陷入deadlock的transaction；另外良好的priority設計可以避免deadlock
- NetLock failure
- lock server死掉
- sol：由備用的lock server接手死掉的lock server所經手的lock，client resubmit他們的request給備用server，備用server如果因為有transaction卡住沒辦法馬上grant lock也可以等卡住的transaction租約到期
- switch死掉
- sol：解法跟lock server相同，當壞掉的switch重新上線會先跟lock server sync獲取被暫存的overflowed request，client送的request會被送到重新上線的switch，但不會馬上被處理，會等到備用switch的queue被清空以及lock server中暫存的overflowed request被清空才開始處裡
5 Implementation
- 提到用多少行code、甚麼程式語言、switch的牌子來實作
6 Evaluation
- 比較對象
- decentralized lock manager (use RDMA)
- DSLR、DrTM
- switch-based lock manager (only support exclusive lock)
- NetChain
- decentralized lock manager (use RDMA)
- 測試方法
- 只產生lock request，對於lock processing的basic performance的測量很有用
- 產生base on TPC-C且包含lock request的transaction，對於測量application-level的performance很有用
- 結果
- NetLock在throughput、latency通通屌打對手
- 實驗中也證明了
- 採用knapsack algorithm來allocate memory能得到更好的throughput
- think time越短在同樣的memory size下throughput越高