關(guān)于Disaggregating Persistent Memory and Controlling Them Remotely: An Exploration of Passive Disaggregated Key-Value Stores這篇論文的筆記

原文鏈接

提出背景

傳統(tǒng)的分布式存儲(chǔ)系統(tǒng)中，每個(gè)節(jié)點(diǎn)都會(huì)包含計(jì)算和存儲(chǔ)兩個(gè)部分，一個(gè)節(jié)點(diǎn)既可以訪問本地的存儲(chǔ)部分也可以訪問遠(yuǎn)端的存儲(chǔ)部分。傳統(tǒng)的存儲(chǔ)部分是由SSD或者HDD組成，但隨著非易失性內(nèi)存（PM：persistent memory）的提出，越來越多的存儲(chǔ)系統(tǒng)采用了這種存儲(chǔ)介質(zhì)。形成的組織架構(gòu)如下圖所示：

存在的問題

• 在單個(gè)節(jié)點(diǎn)中，計(jì)算和存儲(chǔ)之間存在著處理速度方面的差異，無法發(fā)揮最佳的性能

• 可擴(kuò)展性差

• 存在數(shù)據(jù)一致性與可靠性方面的問題

分離模式

針對(duì)傳統(tǒng)分布式存儲(chǔ)系統(tǒng)存在的問題，人們提出了將計(jì)算和存儲(chǔ)分離的模式，這種模式相比于傳統(tǒng)的模式在資源管理、可擴(kuò)展性等方面表現(xiàn)得更好，現(xiàn)在的許多數(shù)據(jù)中心和云服務(wù)平臺(tái)都正在采用這種模式。

此外，有一種稱為RDMA（Remote Direct Memory Acces）的網(wǎng)絡(luò)技術(shù)正在應(yīng)用于分布式系統(tǒng)中，這種技術(shù)能夠允許跨過CPU直接訪問遠(yuǎn)端節(jié)點(diǎn)的內(nèi)存，因此具有低延遲和低CPU利用率的特點(diǎn)，采用這種技術(shù)能夠大大提高分布式系統(tǒng)的性能。

既然分離出了計(jì)算和存儲(chǔ)節(jié)點(diǎn)，那么就需要在其中一種節(jié)點(diǎn)上安裝管理程序以維護(hù)這個(gè)系統(tǒng)，根據(jù)管理程序所在的節(jié)點(diǎn)，結(jié)合PM存儲(chǔ)介質(zhì)和RDMA傳輸技術(shù)，提出了兩類模型：aDPM(active disaggregated PM)和pDPM(passive disaggregated PM)。其中，主動(dòng)(active)和被動(dòng)(passive)是指對(duì)數(shù)據(jù)的管理模式。

aDPM

aDPM的架構(gòu)如下圖所示

可以看到，在aDPM中，將管理程序安裝在存儲(chǔ)節(jié)點(diǎn)，采用這種方式可以降低延遲，但是為了維持較大的網(wǎng)絡(luò)帶寬，在存儲(chǔ)節(jié)點(diǎn)需要有較高的處理能力，由此會(huì)產(chǎn)生較大能耗。此外，如果該系統(tǒng)采用了RDMA技術(shù)，那么在這種情況下，需要事先通過管理層才能到達(dá)內(nèi)存，并沒有發(fā)揮RDMA直達(dá)內(nèi)存的優(yōu)點(diǎn)。

pDPM

由于aDPM還存在著一些不足，于是考慮將管理程序放在計(jì)算節(jié)點(diǎn)，從而組成了pDPM模型。pDPM的架構(gòu)如下圖所示：

采用這種模式有效地解決了aDPM中RDMA無法發(fā)揮作用的不足，在這種模式下，只需要在存儲(chǔ)節(jié)點(diǎn)安裝支持RDMA的智能網(wǎng)卡，就能實(shí)現(xiàn)對(duì)存儲(chǔ)節(jié)點(diǎn)內(nèi)存的直接訪問。但在這種模式下，存儲(chǔ)節(jié)點(diǎn)失去了處理能力，接下來的問題就是在哪里處理與管理數(shù)據(jù)。從這點(diǎn)出發(fā)，提出了三種模式：pDPM-Direct，pDPM-Central和Clover

pDPM-Direct

直觀的想法是在計(jì)算節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的管理，計(jì)算節(jié)點(diǎn)通過單向的RDMA對(duì)存儲(chǔ)節(jié)點(diǎn)進(jìn)行讀寫操作，它的架構(gòu)如下所示：

以下簡要介紹這種架構(gòu)在讀寫方面的實(shí)現(xiàn)：

對(duì)于一條數(shù)據(jù)，它在存儲(chǔ)節(jié)點(diǎn)中的形式是一個(gè)KV條目，每個(gè)KV條目包含已提交和未提交數(shù)據(jù)，同時(shí)這些數(shù)據(jù)需要有校驗(yàn)碼保證可靠性。

• 當(dāng)進(jìn)行讀操作時(shí)，讀取對(duì)于KV條目中的已提交數(shù)據(jù)，并進(jìn)行校驗(yàn)，如果校驗(yàn)失敗，需要重新讀取。

• 當(dāng)進(jìn)行寫操作時(shí)，首先對(duì)要寫的KV條目加鎖，再先后將數(shù)據(jù)寫入未提交和已提交數(shù)據(jù)中，最后釋放鎖。

可以看到，采取這種方式存在的問題有：

• 寫操作時(shí)較慢

• 一條數(shù)據(jù)需要復(fù)制為兩份保存，會(huì)造成空間的浪費(fèi)。

pDPM-Central

pDPM-Direct采用的方式相當(dāng)于將數(shù)據(jù)的處理分散到每一個(gè)計(jì)算節(jié)點(diǎn)上，那么相對(duì)應(yīng)的另一種思路是將數(shù)據(jù)的處理集中在一個(gè)調(diào)度器，這個(gè)調(diào)度器位于計(jì)算節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)之間，這就是pDPM-Central采用的方法。它的架構(gòu)如下所示：

以下簡要介紹這種架構(gòu)在讀寫方面的實(shí)現(xiàn)：

在調(diào)度器中的PM保存著一張映射表，每個(gè)條目保存的是一條數(shù)據(jù)所在的地址。

• 當(dāng)進(jìn)行讀操作時(shí)，計(jì)算節(jié)點(diǎn)會(huì)向調(diào)度器發(fā)送一個(gè)RPC請(qǐng)求，調(diào)度器會(huì)給對(duì)應(yīng)得映射表?xiàng)l目加鎖，然后調(diào)度器從存儲(chǔ)節(jié)點(diǎn)讀取數(shù)據(jù)并返回給計(jì)算節(jié)點(diǎn)，最后釋放條目上的鎖

• 當(dāng)進(jìn)行寫操作時(shí)，計(jì)算節(jié)點(diǎn)會(huì)向調(diào)度器發(fā)送一個(gè)RPC請(qǐng)求，此時(shí)調(diào)度器需要為這條數(shù)據(jù)在存儲(chǔ)節(jié)點(diǎn)中分配空間，然后調(diào)度器將數(shù)據(jù)寫入分配的空間中，最后更新內(nèi)部的映射表（需要加鎖）

可以看到，采取這種方式存在的問題有：

• 由于中間經(jīng)過調(diào)度器，讀操作的速度下降

• 調(diào)度器本身的CPU使用率非常高，需要處理計(jì)算節(jié)點(diǎn)的RPC請(qǐng)求、分配存儲(chǔ)節(jié)點(diǎn)的空間等

• 調(diào)度器成為了該系統(tǒng)的一個(gè)瓶頸

Clover

Clover采取的模式是對(duì)以上兩種方式的混合，它將數(shù)據(jù)和元數(shù)據(jù)分離，分別采用不同的形式進(jìn)行管理，其中對(duì)于數(shù)據(jù)的管理（稱為數(shù)據(jù)層），采用的是pDPM-Direct中的方式，即將數(shù)據(jù)的讀寫操作分散在每個(gè)計(jì)算節(jié)點(diǎn)中；對(duì)于元數(shù)據(jù)的管理（稱為元數(shù)據(jù)層），采用的是pDPM-Central中的方式，即將數(shù)據(jù)空間分配和垃圾回收等操作集中在一個(gè)元數(shù)據(jù)服務(wù)器(MS)中。它的架構(gòu)如下圖所示：

數(shù)據(jù)層

對(duì)于數(shù)據(jù)層，需要完成的基本操作是數(shù)據(jù)的讀寫操作，這里采用的是一種不需要加鎖的數(shù)據(jù)結(jié)構(gòu)，對(duì)于一條數(shù)據(jù)以鏈表的形式存儲(chǔ)，鏈表的每個(gè)結(jié)點(diǎn)代表的是該數(shù)據(jù)的歷史版本，不難看出，該鏈表的最后一個(gè)結(jié)點(diǎn)就是該數(shù)據(jù)的最新版本。同時(shí)在計(jì)算節(jié)點(diǎn)中保存著一個(gè)游標(biāo)（類似指針），代表的是上一次訪問該條數(shù)據(jù)時(shí)的版本（不一定是最新的）。

• 當(dāng)進(jìn)行讀操作時(shí)，根據(jù)計(jì)算節(jié)點(diǎn)中的游標(biāo)找到該條數(shù)據(jù)對(duì)應(yīng)鏈表中的位置，從該位置開始遍歷直至找到鏈表末尾，得到該條數(shù)據(jù)的最新版本。

• 當(dāng)進(jìn)行寫操作時(shí)，需要在存儲(chǔ)節(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)條目中添加一個(gè)新的結(jié)點(diǎn)，如果該鏈表只有一個(gè)結(jié)點(diǎn)，說明是新創(chuàng)建的數(shù)據(jù)，只需要在計(jì)算節(jié)點(diǎn)中添加新的指向該結(jié)點(diǎn)的游標(biāo)；如果鏈表有多個(gè)結(jié)點(diǎn)，說明是對(duì)數(shù)據(jù)的更新，將代表上一版本的結(jié)點(diǎn)指向新創(chuàng)建的結(jié)點(diǎn)，最后更新執(zhí)行寫操作的計(jì)算節(jié)點(diǎn)中的游標(biāo)。

可以看到，在讀操作中當(dāng)遇到鏈表很長而游標(biāo)指向的歷史版本過早時(shí)，存在遍歷時(shí)間過長的情況。因此可以采取一種優(yōu)化措施，在存儲(chǔ)節(jié)點(diǎn)內(nèi)部保存一類稱為捷徑(shortcut)的指針，它們會(huì)指向?qū)?yīng)數(shù)據(jù)條目中盡量新的版本結(jié)點(diǎn)。在實(shí)際應(yīng)用時(shí)，會(huì)并行采取遍歷鏈表和使用捷徑指針的方式，直到其中一種方式獲得最新的數(shù)據(jù)。

數(shù)據(jù)層的組織形式如下圖所示：

元數(shù)據(jù)層

對(duì)于元數(shù)據(jù)層，它只與計(jì)算節(jié)點(diǎn)進(jìn)行通信，進(jìn)行空間管理、垃圾回收、負(fù)載均衡等操作。

對(duì)于空間分配的操作，在MS中將空閑空間打包為一個(gè)塊(chunk)，每個(gè)塊的大小和數(shù)據(jù)緩沖區(qū)的大小一致，不同的塊會(huì)有不同的大小，這些塊會(huì)組成一個(gè)空閑隊(duì)列。當(dāng)計(jì)算節(jié)點(diǎn)需要進(jìn)行寫操作時(shí)，會(huì)在后臺(tái)向MS請(qǐng)求分配一個(gè)對(duì)應(yīng)的塊，MS會(huì)在空閑隊(duì)列中將這個(gè)塊發(fā)送給計(jì)算節(jié)點(diǎn)。

對(duì)于垃圾回收操作，在寫完成之后，計(jì)算節(jié)點(diǎn)可能需要淘汰一些歷史版本結(jié)點(diǎn)，因此后臺(tái)會(huì)給MS發(fā)送回收請(qǐng)求，收到回收請(qǐng)求的MS會(huì)將原來分配出去的塊重新放回空閑隊(duì)列中。

以上操作的組織形式如下圖所示：

對(duì)于數(shù)據(jù)可靠性與負(fù)載均衡，一個(gè)數(shù)據(jù)條目的歷史版本的副本可能存在于不同的存儲(chǔ)節(jié)點(diǎn)上，一個(gè)版本結(jié)點(diǎn)可以指向多個(gè)下一版本結(jié)點(diǎn)，盡管它們存在不同的存儲(chǔ)節(jié)點(diǎn)。大致思路如下圖所示：

小結(jié)

在以上三種pDPM模型中，Clover嘗試結(jié)合另外兩種模型的優(yōu)點(diǎn)，經(jīng)過實(shí)驗(yàn)證明Clover的確具有讀寫延遲低、能耗低、成本低等優(yōu)點(diǎn)，但也存在大量寫沖突情況下性能變差的問題?？傊?#xff0c;在設(shè)計(jì)分布式存儲(chǔ)系統(tǒng)時(shí)可以考慮采用pDPM中的Clover模型。