一種多核友好的持久性?xún)?nèi)存鍵值系統(tǒng)

汪 慶 朱博弘 舒繼武

(清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 北京 100084)(q-wang18@mails.tsinghua.edu.cn)

新型的持久性?xún)?nèi)存(persistent memory, PM)通過(guò)內(nèi)存總線與CPU相連，因此應(yīng)用程序能夠直接使用CPU的load和store指令對(duì)其訪問(wèn).此外，它具有和DRAM相近的性能，以及和磁盤(pán)一樣的持久化存儲(chǔ)數(shù)據(jù)的功能.英特爾公司2019年正式發(fā)布了Optane DC持久性?xún)?nèi)存[1]，將基于持久性?xún)?nèi)存的軟件研究從模擬器時(shí)代帶到了真實(shí)硬件平臺(tái)時(shí)代，其具有百納秒級(jí)的訪問(wèn)延遲以及最高512 GB的單條容量，為設(shè)計(jì)高速的鍵值存儲(chǔ)系統(tǒng)提供了新的機(jī)遇.

然而，構(gòu)建這樣的持久性?xún)?nèi)存鍵值系統(tǒng)存在著諸多挑戰(zhàn)，尤其是在現(xiàn)代基于多核架構(gòu)的服務(wù)器中.具體而言，現(xiàn)有用于持久性?xún)?nèi)存鍵值系統(tǒng)的并發(fā)控制的方法會(huì)帶來(lái)CPU緩存的抖動(dòng)；同時(shí)，將鎖資源嵌入到索引的傳統(tǒng)設(shè)計(jì)會(huì)導(dǎo)致額外的持久性?xún)?nèi)存寫(xiě)帶寬的消耗.除此之外，為保障崩潰一致性而使用的日志等機(jī)制也嚴(yán)重消耗著持久性?xún)?nèi)存有限的寫(xiě)帶寬；當(dāng)多個(gè)線程同時(shí)向持久性?xún)?nèi)存寫(xiě)數(shù)據(jù)時(shí)，會(huì)造成內(nèi)存控制器和持久性?xún)?nèi)存芯片內(nèi)部硬件資源的競(jìng)爭(zhēng)，從而影響鍵值系統(tǒng)的整體性能.最后，由于存在持久化延遲，互斥臨界區(qū)的時(shí)間被拉長(zhǎng)，加劇了線程之間的沖突.

本文提出一種多核友好的持久性?xún)?nèi)存鍵值系統(tǒng)(multicore-friendly persistent memory key-value store, MPKV)，通過(guò)設(shè)計(jì)高效并發(fā)控制方法和減少持久性?xún)?nèi)存的寫(xiě)操作提高多核并發(fā)性能.MPKV使用桶式散列索引管理鍵(key)到值(value)的映射，并在此基礎(chǔ)上提出了3個(gè)針對(duì)多核優(yōu)化的機(jī)制：易失性鎖管理、2階段原子寫(xiě)以及并發(fā)寫(xiě)消除機(jī)制.具體地，在易失性鎖管理機(jī)制中，MPKV將寫(xiě)鎖資源從索引中分離，在DRAM中單獨(dú)維護(hù)它們，以避免鎖操作消耗持久性?xún)?nèi)存的寫(xiě)帶寬；MPKV為DRAM中的鎖表設(shè)計(jì)了緊湊的格式，以減少鎖資源分離結(jié)構(gòu)導(dǎo)致的CPU緩存以及TLB(translation lookaside buffer) 的缺失.在2階段原子寫(xiě)機(jī)制中，MPKV將key的指紋、鍵值數(shù)據(jù)的地址以及持久化標(biāo)志包裝在64 b字段中，并利用CPU提供的原子寫(xiě)操作指令將系統(tǒng)從一個(gè)一致性狀態(tài)原子地切換到另一個(gè)一致性狀態(tài)；基于2階段原子寫(xiě)機(jī)制，MPKV將查詢(xún)操作完全無(wú)鎖化，消除了查詢(xún)操作路徑上對(duì)持久性?xún)?nèi)存的寫(xiě)，并避免了查詢(xún)和更新操作之間的沖突競(jìng)爭(zhēng).在并發(fā)寫(xiě)消除機(jī)制中，MPKV引入了基于序列號(hào)的低開(kāi)銷(xiāo)沖突檢測(cè)方法；當(dāng)出現(xiàn)2個(gè)沖突的更新操作時(shí)，并發(fā)寫(xiě)消除機(jī)制讓其中一個(gè)操作直接返回，不做任何持久性?xún)?nèi)存的分配與修改，有效節(jié)省了持久性?xún)?nèi)存有限的寫(xiě)帶寬.

本文的主要貢獻(xiàn)有3個(gè)方面：

1) 分析了持久性?xún)?nèi)存鍵值系統(tǒng)在多核架構(gòu)下的性能問(wèn)題.

2) 提出了一種多核友好的持久性?xún)?nèi)存鍵值系統(tǒng)MPKV，并引入了易失性鎖管理、2階段原子寫(xiě)以及并發(fā)寫(xiě)消除3個(gè)機(jī)制，提升了并發(fā)控制效率，同時(shí)節(jié)省了持久性?xún)?nèi)存寫(xiě)帶寬.

3) 通過(guò)實(shí)驗(yàn)分析，MPKV相比于pmemkv具有更良好的性能以及多核擴(kuò)展性.其中，在18線程環(huán)境下，MPKV的吞吐達(dá)到pmemkv的1.7～6.2倍.

1 背景介紹與研究動(dòng)機(jī)

在本節(jié)中，主要介紹Optane DC持久性?xún)?nèi)存的基本特性，并分析多核架構(gòu)下持久性?xún)?nèi)存鍵值系統(tǒng)設(shè)計(jì)的挑戰(zhàn).

1.1 Optane DC持久性?xún)?nèi)存

由于持久性?xún)?nèi)存的非易失、可字節(jié)尋址以及性能高等優(yōu)點(diǎn)，研究者們從體系結(jié)構(gòu)和系統(tǒng)軟件等多方面對(duì)其進(jìn)行了深入的探索.然而，因?yàn)闆](méi)有真實(shí)商用的持久性?xún)?nèi)存產(chǎn)品，之前的研究多基于模擬器或者DRAM.幸運(yùn)的是，英特爾公司在2019年4月發(fā)布了全球首款可大規(guī)模商用的持久性?xún)?nèi)存產(chǎn)品：Optane DC持久性?xún)?nèi)存.Optane DC持久性?xún)?nèi)存基于3DXPoint技術(shù)，它以?xún)?nèi)存條的形式插在標(biāo)準(zhǔn)的DDR4接口上，單條容量可以為128 GB，256 GB，512 GB.Optane DC持久性?xún)?nèi)存支持2種配置模式：內(nèi)存模式(memory mode)和應(yīng)用直訪模式(app direct mode).在內(nèi)存模式下，DRAM作為Optane DC持久性?xún)?nèi)存的緩存；應(yīng)用程序無(wú)需修改就能夠利用到持久性?xún)?nèi)存大容量的特點(diǎn)，但此種模式下Optane DC持久性?xún)?nèi)存無(wú)法被用于數(shù)據(jù)持久存儲(chǔ).在應(yīng)用直訪模式下，Optane DC持久性?xún)?nèi)存作為特殊的存儲(chǔ)設(shè)備可直接通過(guò)CPU的load和store指令訪問(wèn)；通常情況下，應(yīng)用程序利用文件系統(tǒng)或持久性堆來(lái)管理持久性?xún)?nèi)存的名字空間.在MPKV中，Optane DC持久性?xún)?nèi)存被配置成應(yīng)用直訪模式.

Optane DC持久性?xún)?nèi)存的獨(dú)特硬件特性影響著上層軟件的設(shè)計(jì)：1)讀寫(xiě)不對(duì)稱(chēng)性[2]，單條的Optane DC持久性?xún)?nèi)存的讀帶寬為6.6 GBps，而寫(xiě)帶寬只有2.3 GBps.2)硬件內(nèi)部的最小訪問(wèn)粒度是256 B.除此之外，由于CPU緩存的存在，數(shù)據(jù)持久化操作需要顯式地調(diào)用CPU硬件指令，將數(shù)據(jù)從CPU緩存刷寫(xiě)至持久性?xún)?nèi)存.為了提高持久化效率，英特爾公司提出2個(gè)新指令：clwb和clflushopt；相比于傳統(tǒng)clflush指令，新指令支持亂序執(zhí)行，且clwb不會(huì)將CPU緩存無(wú)效化，以更好地利用CPU緩存.CPU持久化指令會(huì)帶來(lái)高昂的性能開(kāi)銷(xiāo)，因此如何在減少使用持久化指令的同時(shí)保證系統(tǒng)的崩潰一致性是設(shè)計(jì)的難點(diǎn).

由于持久性?xún)?nèi)存的性能與DRAM相比仍有差距，現(xiàn)有的系統(tǒng)多采用混合架構(gòu)[3]，即同時(shí)使用DRAM和持久性?xún)?nèi)存.在混合架構(gòu)中，DRAM用于暫存可丟失的數(shù)據(jù)，而持久性?xún)?nèi)存用于存儲(chǔ)核心數(shù)據(jù).

1.2 持久性?xún)?nèi)存鍵值系統(tǒng)的多核挑戰(zhàn)

隨著摩爾定律逐漸走向終結(jié)，CPU單個(gè)核心的性能上升緩慢.因此，處理器生產(chǎn)商通過(guò)在單個(gè)CPU中添加更多的核心來(lái)提高處理器整體性能.在這種多核架構(gòu)下，如何設(shè)計(jì)高效的軟件一直是活躍的研究領(lǐng)域.同時(shí)，持久性?xún)?nèi)存的出現(xiàn)將存儲(chǔ)帶到了內(nèi)存級(jí)，為構(gòu)建高性能的鍵值存儲(chǔ)系統(tǒng)帶來(lái)了機(jī)遇.設(shè)計(jì)多核友好的持久性?xún)?nèi)存鍵值系統(tǒng)存在著3方面的挑戰(zhàn)：

1) CPU緩存的抖動(dòng).為了保證多線程并發(fā)的正確性，鍵值系統(tǒng)使用并發(fā)原語(yǔ)(如讀寫(xiě)鎖)協(xié)調(diào)線程之間的同步互斥.然而，這些并發(fā)原語(yǔ)的使用導(dǎo)致對(duì)應(yīng)數(shù)據(jù)在不同CPU核心的緩存之間來(lái)回抖動(dòng)，頻繁觸發(fā)高昂開(kāi)銷(xiāo)的CPU緩存一致性協(xié)議[4]，造成了CPU性能的急劇下降.

2) 有限的持久性?xún)?nèi)存寫(xiě)帶寬.持久性?xún)?nèi)存的寫(xiě)帶寬遠(yuǎn)遠(yuǎn)低于DRAM的寫(xiě)帶寬.除了存儲(chǔ)鍵值數(shù)據(jù)，系統(tǒng)為保證崩潰一致性而采用的日志等一致性機(jī)制也會(huì)帶來(lái)對(duì)持久性?xún)?nèi)存寫(xiě)帶寬的額外消耗.此外，當(dāng)多個(gè)線程同時(shí)對(duì)持久性?xún)?nèi)存進(jìn)行寫(xiě)操作時(shí)，內(nèi)存控制器中會(huì)產(chǎn)生隊(duì)列競(jìng)爭(zhēng)，同時(shí)持久性?xún)?nèi)存芯片內(nèi)的緩沖區(qū)也會(huì)發(fā)生沖突.

3) 持久化操作加劇線程沖突.在被并發(fā)原語(yǔ)保護(hù)的系統(tǒng)臨界區(qū)中，線程進(jìn)行持久性?xún)?nèi)存的讀以及持久化操作.由于持久性?xún)?nèi)存較高的讀延遲和持久化延遲，臨界區(qū)的時(shí)間被拉長(zhǎng)，導(dǎo)致不同線程間沖突的操作被嚴(yán)重阻塞.

2 MPKV架構(gòu)設(shè)計(jì)

本文提出一種多核友好的持久性?xún)?nèi)存鍵值系統(tǒng).圖1描述MPKV的總體架構(gòu).應(yīng)用程序通過(guò)GET(查詢(xún))、PUT(更新)和DEL(刪除)3個(gè)接口操作鍵值系統(tǒng).MPKV同時(shí)使用DRAM和持久性?xún)?nèi)存.在持久性?xún)?nèi)存中，MPKV維護(hù)著散列索引和鍵值數(shù)據(jù).其中散列索引用于索引key對(duì)應(yīng)的鍵值數(shù)據(jù)，而鍵值數(shù)據(jù)存儲(chǔ)著應(yīng)用程序?qū)懭氲恼嬲龜?shù)據(jù).

Fig. 1 Overall architecture of MPKV圖1 MPKV總體架構(gòu)

MPKV采用基于日志結(jié)構(gòu)的策略分配內(nèi)存[5].持久性?xún)?nèi)存作為存儲(chǔ)設(shè)備以Ext4-DAX文件系統(tǒng)[6]的形式被掛載到特定目錄.每個(gè)線程通過(guò)創(chuàng)建文件并使用mmap(內(nèi)存映射文件)系統(tǒng)調(diào)用獲得持久性?xún)?nèi)存的字節(jié)可尋址空間.每個(gè)線程將各自的持久性?xún)?nèi)存空間組織成日志形式：每次服務(wù)持久性?xún)?nèi)存分配請(qǐng)求時(shí)，直接從日志尾部分配相應(yīng)的空間；后臺(tái)線程周期性回收日志空間的垃圾數(shù)據(jù).該基于日志結(jié)構(gòu)的分配器避免了持久性?xún)?nèi)存碎片的產(chǎn)生，同時(shí)由于不同線程獨(dú)立管理持久性?xún)?nèi)存，分配器具有極好的多核擴(kuò)展性.

為保證崩潰一致性，MPKV需要顯式地將數(shù)據(jù)從CPU緩存刷寫(xiě)至持久性?xún)?nèi)存.MPKV選擇使用clwb指令持久化數(shù)據(jù)，并在一組clwb指令之后通過(guò)加入sfence指令保證持久化順序.相比其他持久化指令，clwb具有2點(diǎn)優(yōu)勢(shì)：首先，多個(gè)clwb可以亂序執(zhí)行，不阻塞CPU的流水線；其次，clwb不會(huì)無(wú)效化CPU緩存中的數(shù)據(jù)，避免后續(xù)訪問(wèn)遇到CPU緩存缺失.

持久性?xún)?nèi)存中的散列索引為桶式散列表結(jié)構(gòu).一個(gè)桶中包含8個(gè)槽；每個(gè)槽存儲(chǔ)著key的信息以及鍵值數(shù)據(jù)的地址.當(dāng)輸入1個(gè)key時(shí)，MPKV通過(guò)散列函數(shù)將key計(jì)算成一個(gè)64 b的散列值：其中高48 b通過(guò)取余操作定位到某一個(gè)桶；低16 b用于定位桶中的槽，稱(chēng)為該key的指紋(fingerprint).當(dāng)一個(gè)桶中的槽被用完時(shí)，系統(tǒng)分配新的桶，安裝在原來(lái)的桶之后，形成鏈表結(jié)構(gòu).桶式散列表具有極好的空間局部性和緊湊的布局格式.

為解決研究動(dòng)機(jī)中提到的3個(gè)挑戰(zhàn)，MPKV引入了易失性鎖管理、2階段原子寫(xiě)以及并發(fā)寫(xiě)消除機(jī)制.易失性鎖管理機(jī)制在DRAM中統(tǒng)一管理系統(tǒng)鎖資源，以減少對(duì)持久性?xún)?nèi)存的寫(xiě)操作.2階段原子寫(xiě)機(jī)制通過(guò)原子指令保證系統(tǒng)崩潰一致性，并支持了無(wú)鎖查詢(xún)操作.進(jìn)一步地，MPKV設(shè)計(jì)了并發(fā)寫(xiě)消除機(jī)制，在存在更新沖突時(shí)減少對(duì)持久性?xún)?nèi)存的寫(xiě).

3 關(guān)鍵技術(shù)

本節(jié)逐一介紹MPKV的3個(gè)關(guān)鍵技術(shù)，包括易失性鎖管理機(jī)制、2階段原子寫(xiě)機(jī)制以及并發(fā)寫(xiě)消除機(jī)制.

3.1 易失性鎖管理機(jī)制

易失性鎖管理旨在通過(guò)利用DRAM管理鎖資源，以減少對(duì)持久性?xún)?nèi)存的寫(xiě)開(kāi)銷(xiāo).

散列索引使用鎖保證對(duì)同一個(gè)桶并發(fā)操作的正確性.鎖本質(zhì)上通過(guò)CPU提供的原子指令如比較并交換(compare and swap, CAS)實(shí)現(xiàn)，包含對(duì)地址空間的寫(xiě).傳統(tǒng)的持久性索引將鎖嵌入到數(shù)據(jù)結(jié)構(gòu)內(nèi)部，如散列表的桶中.由于鎖和索引的部分?jǐn)?shù)據(jù)在同一個(gè)緩存行中，這種設(shè)計(jì)能夠帶來(lái)比較好的空間局部性.但這種設(shè)計(jì)存在3方面問(wèn)題：首先，鎖的操作會(huì)帶來(lái)對(duì)持久性?xún)?nèi)存的寫(xiě)，并消耗持久性?xún)?nèi)存的有限的帶寬；其次，在Optane DC持久性?xún)?nèi)存中，由于內(nèi)存內(nèi)部最小更新粒度是256 B，鎖操作會(huì)帶來(lái)嚴(yán)重的寫(xiě)放大；最后，當(dāng)崩潰重啟時(shí)，系統(tǒng)需要掃描整個(gè)索引，清空所有的鎖字段，帶來(lái)了較高的恢復(fù)開(kāi)銷(xiāo).

為了解決如上問(wèn)題，MPKV引入了易失性鎖管理機(jī)制.MPKV將鎖資源從散列索引中分離，在DRAM中單獨(dú)維護(hù)它們.具體地，DRAM中存有一個(gè)鎖表結(jié)構(gòu)，它的輸入是散列桶的地址，輸出是對(duì)應(yīng)的鎖字段.由于鎖表會(huì)帶來(lái)額外的一次查詢(xún)，它的性能對(duì)MPKV至關(guān)重要.由此，MPKV將鎖表實(shí)現(xiàn)成4 096個(gè)64 b鎖字段的數(shù)組；系統(tǒng)通過(guò)對(duì)散列桶的地址散列取余后得到對(duì)應(yīng)的鎖字段，用于并發(fā)控制.由于鎖表只占32 KB的空間，它能夠緩存在高速的CPU第2級(jí)緩存中(現(xiàn)有服務(wù)器CPU 的第2級(jí)緩存大小在256 KB左右)，且?guī)缀醪粫?huì)引入TLB缺失.需要注意的是，這種空間占用極小的鎖表結(jié)構(gòu)會(huì)帶來(lái)偽沖突，即不同的散列桶同時(shí)爭(zhēng)搶一個(gè)鎖字段.但在真實(shí)測(cè)試和負(fù)載中，2個(gè)原因?qū)е聜螞_突的概率很低：首先，在一次鍵值操作中，一個(gè)線程最多持有1把鎖，所以整個(gè)系統(tǒng)同一個(gè)時(shí)刻總持鎖量的上限為線程數(shù)，它的值遠(yuǎn)遠(yuǎn)小于鎖表的大小(4 096)；其次，真實(shí)負(fù)載多為讀密集的，而在MPKV中，易失性鎖管理機(jī)制只用于管理散列桶的寫(xiě)鎖，而MPKV的查詢(xún)操作是無(wú)鎖的(3.2節(jié)).

3.2 2階段原子寫(xiě)

MPKV設(shè)計(jì)了2階段原子寫(xiě)機(jī)制，在保障系統(tǒng)崩潰一致性的同時(shí)，減少對(duì)持久性?xún)?nèi)存不必要的讀開(kāi)銷(xiāo)，以及支持無(wú)鎖的查詢(xún)操作.

具體地，MPKV利用了CPU提供的64 b原子寫(xiě)操作將系統(tǒng)原子地從一個(gè)一致性狀態(tài)切換到另一個(gè)一致性狀態(tài).在MPKV的散列桶中，每個(gè)槽的內(nèi)容為對(duì)齊的64 b字段，如圖2所示.槽的最高16 b存著key的指紋，用于快速檢測(cè)，以減少對(duì)鍵值數(shù)據(jù)的讀取和比較；中間47 b存著鍵值數(shù)據(jù)地址；最低位(persist)標(biāo)記著該槽的內(nèi)容是否已經(jīng)被成功持久化.高16 b和最低位可以用于存儲(chǔ)額外信息的原因在于2點(diǎn)：首先，現(xiàn)在的英特爾處理器的虛擬地址空間只有48 b；其次，在MPKV中，分配的持久性?xún)?nèi)存地址8 B對(duì)齊，即地址最低3 b為0.

Fig. 2 Format of hash index slot圖2 散列索引槽的格式

MPKV的更新操作流程如下：1)定位到對(duì)應(yīng)的散列桶以及其中的槽，并成功持有易失性鎖表內(nèi)的對(duì)應(yīng)鎖；2)從持久性?xún)?nèi)存中分配鍵值數(shù)據(jù)的空間，將鍵值數(shù)據(jù)寫(xiě)入其中，并通過(guò)調(diào)用CPU持久化指令將其持久化；3)根據(jù)散列槽的格式槽，生成指紋，鍵值數(shù)據(jù)地址，0三元組(64 b)；4)進(jìn)行2階段原子寫(xiě)，在第1階段中，將64 b三元組原子地寫(xiě)入對(duì)應(yīng)的散列槽，并調(diào)用CPU持久化指令將其從CPU緩存刷寫(xiě)至持久性?xún)?nèi)存；在第2階段中，將散列槽的最低位(即persist位)置成1，標(biāo)志散列槽已成功被持久化.

2階段原子寫(xiě)機(jī)制的引入使得MPKV的查詢(xún)操作可以完全無(wú)鎖化.具體地，查詢(xún)操作的流程如下：1)定位到對(duì)應(yīng)的散列桶；2)依次遍歷其中的散列槽(通過(guò)64 b原子讀)，若某一個(gè)槽中的指紋與key的指紋匹配，且對(duì)應(yīng)鍵值數(shù)據(jù)中的key也相同，則定位到該槽；如果該槽的persist位為1，則直接讀取鍵值數(shù)據(jù)中的value；如果該槽的persist位為0，則協(xié)助完成2階段原子寫(xiě)：調(diào)用CPU持久化指令使槽的內(nèi)容持久性，最后調(diào)用CAS指令原子地更新persist值為1，若CAS成功，讀取鍵值數(shù)據(jù)中的value，否則，從該槽開(kāi)始繼續(xù)向后遍歷散列槽.值得注意的是，persist位用于保證查詢(xún)操作不會(huì)讀到未被成功持久化記錄到散列索引的鍵值數(shù)據(jù)，以達(dá)到正確的語(yǔ)義.此外，查詢(xún)操作協(xié)助完成2階段原子寫(xiě)，這是為了系統(tǒng)崩潰重啟后無(wú)需遍歷所有的散列槽并將persist置位為1；同時(shí)，該協(xié)助過(guò)程未引入不一致的問(wèn)題，這是因?yàn)樵诖酥皩?duì)應(yīng)寫(xiě)操作的數(shù)據(jù)已成功被持久化.

無(wú)鎖查詢(xún)操作帶來(lái)了內(nèi)存釋放的問(wèn)題，因?yàn)槠渌僮鳠o(wú)法感知并發(fā)的查詢(xún)操作.MPKV引入了一種基于epoch的內(nèi)存回收方法[7]；該方法將時(shí)間劃分為連續(xù)的周期(epoch).具體地，MPKV維護(hù)一個(gè)全局epoch計(jì)數(shù)器，同時(shí)每個(gè)線程維護(hù)一個(gè)本地epoch計(jì)數(shù)器.每個(gè)鍵值操作開(kāi)始時(shí)，將本地計(jì)數(shù)器的值更新成全計(jì)數(shù)器的值.當(dāng)更新和刪除操作需要釋放持久性?xún)?nèi)存空間時(shí)，將該內(nèi)存空間以本地計(jì)數(shù)器的值，內(nèi)存空間地址格式記錄到本地回收鏈表中.MPKV使用一個(gè)后臺(tái)線程周期性地將全局計(jì)數(shù)器加1并安全回收內(nèi)存：該線程收集所有其他線程的本地計(jì)數(shù)器，并計(jì)算出其中的最小值，稱(chēng)作最大安全epoch，此時(shí)，所有本地回收鏈表中小于最大安全epoch的內(nèi)存可以被安全回收.

2階段原子寫(xiě)機(jī)制帶了3方面的性能優(yōu)勢(shì)：1)最小化崩潰一致性的開(kāi)銷(xiāo).在更新操作的過(guò)程中，無(wú)需記錄日志；2)最小化系統(tǒng)恢復(fù)的開(kāi)銷(xiāo).在系統(tǒng)恢復(fù)的過(guò)程中，無(wú)需遍歷散列索引或者日志內(nèi)容；3)多核并發(fā).查詢(xún)操作完全無(wú)鎖，避免了傳統(tǒng)的讀寫(xiě)鎖造成的持久性?xún)?nèi)存寫(xiě)開(kāi)銷(xiāo)以及緩存抖動(dòng)的問(wèn)題，同時(shí)將更新操作的鍵值數(shù)據(jù)持久化過(guò)程排除至并發(fā)查詢(xún)操作的關(guān)鍵路徑之外.

3.3 并發(fā)寫(xiě)消除機(jī)制

鍵值存儲(chǔ)系統(tǒng)面臨著嚴(yán)重的并發(fā)問(wèn)題.易失性鎖管理和2階段原子寫(xiě)機(jī)制通過(guò)優(yōu)化并發(fā)控制機(jī)制來(lái)加速并發(fā)訪問(wèn).與這兩者不同，并發(fā)寫(xiě)消除機(jī)制利用并發(fā)沖突帶來(lái)的機(jī)遇，來(lái)減少對(duì)持久性?xún)?nèi)存的寫(xiě)，提高并發(fā)效率.

如圖3所示，當(dāng)出現(xiàn)2個(gè)沖突的更新操作時(shí)，并發(fā)寫(xiě)消除機(jī)制讓其中一個(gè)操作直接返回，不做任何持久性?xún)?nèi)存的分配與修改，并標(biāo)記為完成.該機(jī)制未違反線性化(linearizable)的并發(fā)語(yǔ)義[8]：2個(gè)在時(shí)間上重疊的操作執(zhí)行完之后，等價(jià)于某一種串行順序.

Fig. 3 Concurrent write elimination圖3 并發(fā)寫(xiě)消除

具體地，在MPKV引入了一種基于序列號(hào)的低開(kāi)銷(xiāo)方法，用以支持并發(fā)寫(xiě)消除.每個(gè)更新操作被賦予一個(gè)獨(dú)一無(wú)二的序列號(hào)：該序列號(hào)所占空間為64 b，其中高8 b是執(zhí)行該更新操作的線程號(hào)，低56 b在每次更新操作之時(shí)加1.利用序列號(hào)，并發(fā)沖突的更新操作可以被檢測(cè)，進(jìn)而被消除.在更新操作的執(zhí)行過(guò)程中，線程將序列號(hào)寫(xiě)入易失性鎖表的對(duì)應(yīng)鎖字段，并在鍵值數(shù)據(jù)中記錄該序列號(hào).當(dāng)一個(gè)線程發(fā)現(xiàn)存在沖突，即鎖已經(jīng)被其他線程獲得時(shí)，它讀取鎖字段中對(duì)應(yīng)的序列號(hào)，記作沖突序列號(hào)cseq；該線程持鎖成功之后，遍歷散列桶中的槽；當(dāng)需要更新的鍵值數(shù)據(jù)的序列號(hào)等于cseq時(shí)，該線程取消持久性?xún)?nèi)存分配和持久化操作，即寫(xiě)操作被消除.

當(dāng)多個(gè)線程對(duì)同一個(gè)鍵值數(shù)據(jù)并發(fā)進(jìn)行更新時(shí)，并發(fā)寫(xiě)消除機(jī)制能有效地減少對(duì)持久性?xún)?nèi)存的寫(xiě)帶寬的消耗，提高了系統(tǒng)整體吞吐.同時(shí)，針對(duì)非沖突的更新操作，由于該機(jī)制使用基于序列號(hào)的輕量級(jí)方法，沖突檢測(cè)的開(kāi)銷(xiāo)極低.

3.4 討 論

MPKV引入了易失性鎖管理、2階段原子寫(xiě)以及并發(fā)寫(xiě)消除機(jī)制.這些技術(shù)在提高系統(tǒng)性能的同時(shí)也帶來(lái)了額外的空間開(kāi)銷(xiāo).易失性鎖管理機(jī)制需要占用32 KB的DRAM空間.2階段原子寫(xiě)機(jī)制由于將指紋信息和持久化標(biāo)記嵌入到64 b鍵值地址字段中，無(wú)需消耗額外空間.在并發(fā)寫(xiě)消除機(jī)制中，每份鍵值數(shù)據(jù)需要額外64 b空間存儲(chǔ)序列號(hào)；對(duì)于平均鍵值大小為150 B的典型負(fù)載(如Facebook的UDB[9])，并發(fā)寫(xiě)消除機(jī)制會(huì)造成5%左右的空間開(kāi)銷(xiāo).考慮到3個(gè)技術(shù)帶來(lái)的性能優(yōu)勢(shì)，這些較少的空間開(kāi)銷(xiāo)是可以接受的.

4 實(shí) 驗(yàn)

本節(jié)實(shí)驗(yàn)將從3個(gè)方面對(duì)MPKV進(jìn)行測(cè)試，并分析其與現(xiàn)有系統(tǒng)的性能差異：1)對(duì)比測(cè)試不同查詢(xún)操作比例下鍵值系統(tǒng)的性能；2)對(duì)比測(cè)試不同鍵值尺寸下鍵值系統(tǒng)的性能；3)多核擴(kuò)展性對(duì)比測(cè)試.

4.1 實(shí)驗(yàn)平臺(tái)

本實(shí)驗(yàn)使用的實(shí)驗(yàn)平臺(tái)配置信息如表1所示.本實(shí)驗(yàn)使用的持久性?xún)?nèi)存設(shè)備是英特爾2019年推出的Optane DC持久性?xún)?nèi)存.為支持持久性?xún)?nèi)存，實(shí)驗(yàn)平臺(tái)配置了相應(yīng)的CPU和主板.實(shí)驗(yàn)機(jī)器擁有2個(gè)NUMA(non uniform memory access)節(jié)點(diǎn).為避免跨NUMA訪問(wèn)帶來(lái)的性能下降，本實(shí)驗(yàn)只使用單個(gè)NUMA節(jié)點(diǎn)，即只使用一塊CPU(包含18個(gè)核心)和對(duì)應(yīng)NUMA節(jié)點(diǎn)上的持久性?xún)?nèi)存.

本實(shí)驗(yàn)將MPKV與pmemkv[10]進(jìn)行性能對(duì)比.pmemkv是一款持久性?xún)?nèi)存鍵值系統(tǒng)，它基于英特爾的持久性?xún)?nèi)存開(kāi)發(fā)套件(persistent memory development kit, PMDK)[11]實(shí)現(xiàn)，并提供了多種存儲(chǔ)引擎.在本實(shí)驗(yàn)中，為了公平比較，pmemkv選擇了基于并發(fā)散列表的cmap存儲(chǔ)引擎；該存儲(chǔ)引擎采用PMDK進(jìn)行持久性?xún)?nèi)存分配，同時(shí)使用讀寫(xiě)鎖進(jìn)行并發(fā)控制.除此之外，實(shí)驗(yàn)還比較了MPKV的基準(zhǔn)版本，稱(chēng)為Baseline；Baseline的散列索引和內(nèi)存分配部分與MPKV相同，但使用嵌入在散列桶中的讀寫(xiě)鎖進(jìn)行并發(fā)控制.在所有實(shí)驗(yàn)中，負(fù)載生成的key滿足均勻分布.負(fù)載生成的key的空間為1億，即存在1億個(gè)不同key.在默認(rèn)情況下，實(shí)驗(yàn)使用18個(gè)線程，這與單個(gè)NUMA節(jié)點(diǎn)的CPU核心數(shù)目相同，以避免多個(gè)線程爭(zhēng)奪相同CPU核心資源；同時(shí)key和value的尺寸分別為8 B和64 B.

Table 1 Platform Configuration表1 實(shí)驗(yàn)平臺(tái)配置信息

4.2 讀寫(xiě)比例對(duì)比測(cè)試

圖4展示了在不同的查詢(xún)操作比例下，MPKV及其對(duì)比系統(tǒng)的吞吐情況.從圖4可知，當(dāng)查詢(xún)操作的比例上升時(shí)，所有鍵值系統(tǒng)的吞吐隨之上升.這是因?yàn)槌志眯詢(xún)?nèi)存的寫(xiě)帶寬很低，更新操作的效率比查詢(xún)效率低；同時(shí)，沖突的更新操作無(wú)法并行.pmemkv的吞吐在所有查詢(xún)操作比例下均最低，這是因?yàn)椋?)對(duì)于更新操作，pmemkv使用了事務(wù)機(jī)制保證崩潰一致性，帶來(lái)寫(xiě)日志的開(kāi)銷(xiāo)，同時(shí)PMDK的內(nèi)存分配操作需要持久性化元數(shù)據(jù)，擴(kuò)展性也很差；而MPKV和Baseline的更新操作無(wú)需寫(xiě)日志，且它們使用的基于日志結(jié)構(gòu)的分配器開(kāi)銷(xiāo)低、擴(kuò)展性良好.2)對(duì)查詢(xún)操作，pmemkv與其他系統(tǒng)不同，未使用指紋技術(shù)，造成了嚴(yán)重的持久性?xún)?nèi)存讀放大現(xiàn)象.

Fig. 4 Throughput with varying GET ratio圖4 不同查詢(xún)比例下的吞吐量

當(dāng)查詢(xún)操作比例為0，即全為更新操作時(shí)，MPKV的吞吐比Baseline高出了18%.這是因?yàn)镸PKV的易失性鎖管理機(jī)制避免了寫(xiě)鎖帶來(lái)的對(duì)持久性?xún)?nèi)存的寫(xiě)；進(jìn)一步，并發(fā)寫(xiě)消除機(jī)制不僅在一定程度上節(jié)省了持久性?xún)?nèi)存的寫(xiě)入帶寬，還通過(guò)縮短持鎖時(shí)間，提高了沖突的更新操作之間的并發(fā)效率.

當(dāng)查詢(xún)操作比例為100%時(shí)，MPKV的吞吐比Baseline高出了99%.這是因?yàn)镸PKV基于2階段原子寫(xiě)機(jī)制設(shè)計(jì)了無(wú)鎖讀.無(wú)鎖讀不僅避免了讀鎖帶來(lái)的持久性?xún)?nèi)存的寫(xiě)，還消除了由于多個(gè)讀者操作讀鎖帶來(lái)的CPU緩存抖動(dòng)的問(wèn)題.為了進(jìn)一步探究MPKV性能優(yōu)勢(shì)的來(lái)源，實(shí)驗(yàn)采集了單個(gè)CPU周期執(zhí)行的指令數(shù)目(instruction per cycle, IPC).在查詢(xún)操作比例為100%時(shí)，Baseline的IPC為0.08，而MPKV的IPC為0.14.這2個(gè)系統(tǒng)的IPC值均很低，這是由于負(fù)載的內(nèi)存占用較大，緩存缺少發(fā)生頻繁.MPKV的IPC是Baseline對(duì)應(yīng)值的1.75倍，這是因?yàn)槿缟衔乃觯瑹o(wú)鎖讀減少了持久性?xún)?nèi)存的寫(xiě)以及緩存抖動(dòng)，由此提高了CPU的執(zhí)行效率.

4.3 鍵值尺寸對(duì)比測(cè)試

圖5展示了在不同的鍵值尺寸下，MPKV及其對(duì)比系統(tǒng)的吞吐情況.此時(shí)查詢(xún)操作比例為50%，同時(shí)key的尺寸固定為8 B，而value的尺寸在變化.從圖5可知，當(dāng)value尺寸增大時(shí)，所有鍵值系統(tǒng)的吞吐隨之下降.這是因?yàn)楦蟮膙alue會(huì)消耗更多的持久性?xún)?nèi)存帶寬和CPU執(zhí)行周期.特別地，當(dāng)value的尺寸為64 B和128 B時(shí)，性能下降幅度很小.這是因?yàn)镺ptane DC持久性?xún)?nèi)存內(nèi)部的最小粒度是256 B，在這2種情況下，持久性?xún)?nèi)存消耗的內(nèi)部帶寬相同.需要注意的是，當(dāng)value尺寸為256 B時(shí)，由于key和其他元數(shù)據(jù)的存在，整個(gè)鍵值數(shù)據(jù)的總尺寸大于256 B.

Fig. 5 Throughput with varying value size圖5 不同值的尺寸下的吞吐量

當(dāng)value尺寸逐漸增大時(shí)，MPKV相對(duì)于Baseline的吞吐提高比例從22%降到了12%.這是因?yàn)槌志没I值數(shù)據(jù)的開(kāi)銷(xiāo)逐漸增大，導(dǎo)致MPKV的優(yōu)化技術(shù)帶來(lái)的相對(duì)收益減小.pmemkv由于冗余復(fù)雜的軟件設(shè)計(jì)，性能遠(yuǎn)低于其他2個(gè)系統(tǒng).

4.4 多核擴(kuò)展性測(cè)試

圖6展示了MPKV及其對(duì)比系統(tǒng)的在寫(xiě)密集負(fù)載下的多核擴(kuò)展性.此時(shí)查詢(xún)操作的比例為50%.從圖6中可以觀察到，MPKV具有最好的多核擴(kuò)展性，而B(niǎo)aseline在使用了12個(gè)線程時(shí)，吞吐接近飽和.這是因?yàn)樵趯?xiě)密集負(fù)載中，會(huì)產(chǎn)生大量的更新與更新、更新與查詢(xún)操作之間的沖突，導(dǎo)致線程經(jīng)常相互阻塞.針對(duì)更新與更新操作之間的沖突，MPKV的并發(fā)寫(xiě)消除機(jī)制減少了沖突操作帶來(lái)的持久性?xún)?nèi)存分配與持久化寫(xiě)，提高了并發(fā)效率； MPKV基于2階段原子寫(xiě)機(jī)制實(shí)現(xiàn)的無(wú)鎖讀，完全消除了更新與查詢(xún)操作之間的沖突.

Fig. 6 Throughput with varying number of threads(write-intensive workload)圖6 不同線程數(shù)目下的吞吐量(寫(xiě)密集負(fù)載)

特別地，當(dāng)線程數(shù)目小于等于4時(shí)，MPKV和Baseline之間的差別并不明顯.這是由于此時(shí)并發(fā)沖突不足，MPKV的設(shè)計(jì)優(yōu)勢(shì)難以充分體現(xiàn).其中MPKV 8%左右的性能提高來(lái)源于易失性鎖管理機(jī)制和無(wú)鎖讀減少了對(duì)持久性?xún)?nèi)存的寫(xiě)，縮短了單個(gè)操作的完成時(shí)間.

Fig. 7 Throughput with varying number of threads(read-intensive workload)圖7 不同線程數(shù)目下的吞吐量(讀密集負(fù)載)

進(jìn)一步，圖7展示了MPKV及其對(duì)比系統(tǒng)的在讀密集負(fù)載下多核擴(kuò)展性.此時(shí)查詢(xún)操作的比例為95%.由于查詢(xún)操作從語(yǔ)義上天生支持并發(fā)，在讀密集負(fù)載下3個(gè)鍵值系統(tǒng)的擴(kuò)展性均表現(xiàn)良好.此時(shí)MPKV的性能優(yōu)勢(shì)主要來(lái)自基于2階段原子寫(xiě)機(jī)制的無(wú)鎖讀：它完全消除了查詢(xún)操作由于讀鎖帶來(lái)的線程之間CPU緩存的競(jìng)爭(zhēng).此外，pmemkv的吞吐最低原因來(lái)源于2點(diǎn)：1)5%的更新操作需要使用基于日志的事務(wù)機(jī)制，軟件開(kāi)銷(xiāo)高；2)95%的查詢(xún)操作由于未利用指紋機(jī)制，造成了額外的持久性?xún)?nèi)存讀，帶來(lái)來(lái)了較高延遲.

5 相關(guān)工作

本節(jié)從持久性?xún)?nèi)存散列索引，持久性?xún)?nèi)存鍵值系統(tǒng)和多核友好的鍵值系統(tǒng)3方面介紹相關(guān)工作.

1) 持久性?xún)?nèi)存散列索引.2018年提出的寫(xiě)優(yōu)化持久性?xún)?nèi)存散列索引level hashing[12]，采用無(wú)日志的方式優(yōu)化更新和刪除操作，并通過(guò)2級(jí)的散列結(jié)構(gòu)減少散列索引擴(kuò)展時(shí)需要的數(shù)據(jù)挪動(dòng)和持久性開(kāi)銷(xiāo).2019年提出的寫(xiě)優(yōu)化動(dòng)態(tài)散列索引CCEH[13]，一方面通過(guò)緩存優(yōu)化，提高查詢(xún)性能；另一方面通過(guò)采用可擴(kuò)展散列結(jié)構(gòu)，避免了散列索引擴(kuò)展時(shí)需要耗時(shí)的散列表重建.2020年提出的Dash[14]采用樂(lè)觀讀處理查詢(xún)操作，并通過(guò)均衡策略提高整個(gè)散列索引的空間利用率.與上述的持久性?xún)?nèi)存散列索引相比，MPKV采用了無(wú)鎖讀并把寫(xiě)鎖放入了DRAM，所以具有更好的多核擴(kuò)展性和更少的持久性?xún)?nèi)存寫(xiě)帶寬消耗.

2) 持久性?xún)?nèi)存鍵值系統(tǒng).2017年提出的持久性?xún)?nèi)存鍵值系統(tǒng)HiKV[15]，采用散列表和B+樹(shù)混合的索引結(jié)構(gòu)，以同時(shí)保證高效的單點(diǎn)查詢(xún)和范圍查詢(xún).HiKV將B+樹(shù)索引維護(hù)在DRAM中，避免對(duì)持久性?xún)?nèi)存額外的讀寫(xiě)，并通過(guò)后臺(tái)線程異步地更新B+樹(shù)索引.2018年提出的NoveLSM[16]利用持久性?xún)?nèi)存優(yōu)化基于日志結(jié)構(gòu)合并樹(shù)(log structured merge tree, LSM Tree)的鍵值系統(tǒng).具體地，NoveLSM在持久性?xún)?nèi)存中構(gòu)造了memtable，這種設(shè)計(jì)不僅降低了序列化和反序列化的開(kāi)銷(xiāo)，也減少了垃圾回收帶來(lái)的前臺(tái)阻塞.與NoveLSM不同，2019年提出的SLM-DB[17]完全改造了LSM樹(shù)的結(jié)構(gòu).SLM-DB采用單層的結(jié)構(gòu)，通過(guò)持久性B+樹(shù)索引鍵值數(shù)據(jù)，并設(shè)計(jì)了選擇性的垃圾回收策略以減少寫(xiě)放大.2020年提出的FlatStore[18]則利用Optane DC持久性?xún)?nèi)存內(nèi)部最小粒度是256 B的特征，設(shè)計(jì)了緊湊的日志格式，通過(guò)高效的CPU核心之間協(xié)同批處理機(jī)制以避免持久性?xún)?nèi)存內(nèi)部的寫(xiě)放大.此外，F(xiàn)latStore利用了高速的遠(yuǎn)程內(nèi)存直接訪問(wèn)(remote direct memory access, RDMA)網(wǎng)絡(luò)技術(shù)，以提供遠(yuǎn)程跨網(wǎng)絡(luò)的鍵值訪問(wèn)接口.與上述持久性?xún)?nèi)存鍵值系統(tǒng)不同，MPKV關(guān)注的是由于多核并發(fā)帶來(lái)的性能問(wèn)題，并通過(guò)一系列技術(shù)解決該問(wèn)題.

3) 多核友好的鍵值系統(tǒng).2017年提出的SLB[19]將熱點(diǎn)數(shù)據(jù)緩存住，以提高并發(fā)查詢(xún)的效率，并在真實(shí)負(fù)載下獲得了73%的性能提高.2020年提出的HotRing[20]，設(shè)計(jì)了環(huán)狀的散列桶結(jié)構(gòu)，通過(guò)在線檢測(cè)數(shù)據(jù)的冷熱程度，將熱點(diǎn)數(shù)據(jù)挪動(dòng)到環(huán)的頭部，以減少內(nèi)存訪問(wèn)次數(shù).上述技術(shù)難以用于持久性鍵值系統(tǒng)，因?yàn)槌志眯枣I值系統(tǒng)需要保證崩潰一致性，數(shù)據(jù)緩存和挪動(dòng)會(huì)帶來(lái)高昂的一致性開(kāi)銷(xiāo).

6 結(jié) 論

構(gòu)建適應(yīng)于持久性?xún)?nèi)存和多核服務(wù)器架構(gòu)的鍵值系統(tǒng)面臨諸多挑戰(zhàn).本文提出一種多核友好的持久性?xún)?nèi)存鍵值系統(tǒng)MPKV，通過(guò)引入易失性鎖管理，2階段原子寫(xiě)以及并發(fā)寫(xiě)消除機(jī)制，有效減少持久性?xún)?nèi)存的寫(xiě)操作，并提升了并發(fā)效率.實(shí)驗(yàn)顯示，相比于其他系統(tǒng)，MPKV具有更良好的吞吐和多核擴(kuò)展性.MPKV目前未針對(duì)NUMA進(jìn)行優(yōu)化，這也是未來(lái)值得探索的方向.