一種基于時(shí)間戳的高擴(kuò)展性的持久性軟件事務(wù)內(nèi)存

劉超杰 王 芳 鄒曉敏 馮 丹

(華中科技大學(xué)武漢光電國家研究中心 武漢 430074)

傳統(tǒng)的單核處理器受限于功耗和散熱問題，難以進(jìn)一步提升運(yùn)行頻率[1-2].因而多核處理器成為了處理器設(shè)計(jì)的主流方向[3].為了充分發(fā)揮多核處理器的性能，必須編寫并發(fā)的程序.然而，編寫正確并且高效的并發(fā)程序往往是一件比較困難的事.這是因?yàn)樵诙嗑€程同步方面，目前往往是基于傳統(tǒng)的鎖來實(shí)現(xiàn)，比如互斥鎖、自旋鎖和讀寫鎖.粗粒度鎖編程簡(jiǎn)單、易實(shí)現(xiàn)，但是擴(kuò)展性不好，無法充分利用多核的性能；細(xì)粒度鎖擴(kuò)展性好，但是往往更難實(shí)現(xiàn)，編程時(shí)容易出錯(cuò)且難以調(diào)試，并且可能會(huì)由于鎖定順序的不同而導(dǎo)致死鎖、優(yōu)先級(jí)反轉(zhuǎn)以及鎖護(hù)送等問題.

為了降低在多核處理器上并發(fā)編程的難度，Herlihy和Moss[4]提出了事務(wù)內(nèi)存(transactional memory, TM).事務(wù)內(nèi)存是一種輕量級(jí)的多線程同步機(jī)制，類似于數(shù)據(jù)庫中的事務(wù)，可以提供原子性、一致性和隔離性的特性.事務(wù)內(nèi)存按照實(shí)現(xiàn)方法分為2種：一種是軟件事務(wù)內(nèi)存(software transactional memory, STM)，其完全由軟件來實(shí)現(xiàn)[5-7]；另一種是硬件事務(wù)內(nèi)存(hardware transactional memory, HTM)，其在CPU緩存層實(shí)現(xiàn)[8-9].當(dāng)然，把這2種方法混合在一起便是混合事務(wù)內(nèi)存[10-11](hybrid transactional memory, HyTM).鑒于軟件事務(wù)內(nèi)存具有的良好兼容性和可移植性，本文主要研究軟件事務(wù)內(nèi)存.

與此同時(shí)，內(nèi)存技術(shù)也在快速發(fā)展，非易失性內(nèi)存(non volatile memory, NVM)成為了當(dāng)今工業(yè)界以及學(xué)術(shù)界研究的熱點(diǎn)，比如3D Xpoint[12]、相變存儲(chǔ)器[13](phase-change memory, PCM)、自旋轉(zhuǎn)移力矩隨機(jī)存儲(chǔ)器[14](spin-transfer torque random access memory, STT-RAM)和可變電阻式存儲(chǔ)器[15](resistive random access memory, ReRAM)等.NVM具有許多優(yōu)點(diǎn)，比如容量大、非易失、能耗低，并且支持CPU的load/store指令.但NVM也有一些缺陷，比如其讀寫延遲仍然比DRAM要高，并且讀寫不對(duì)稱，以及有限的寫次數(shù)等[16-18].總體來說，NVM的出現(xiàn)將可能會(huì)改變計(jì)算機(jī)體系結(jié)構(gòu)，為程序性能的提升帶來了機(jī)遇.

基于NVM的應(yīng)用程序需要自己保證數(shù)據(jù)的崩潰一致性.這是因?yàn)樵跈C(jī)器掉電或者系統(tǒng)崩潰后，可能存在部分更新的數(shù)據(jù)，從而導(dǎo)致了數(shù)據(jù)不一致的問題.為了保障崩潰一致性，數(shù)據(jù)需要按照特定的順序持久化到NVM.英特爾x86架構(gòu)提供了內(nèi)存屏障(MFENCE)以及緩存刷回指令(CLFLUSH)來保證數(shù)據(jù)持久化的順序性[19-20].除此之外，還需要用戶編寫特定的崩潰恢復(fù)程序，從而在系統(tǒng)崩潰后將數(shù)據(jù)恢復(fù)到一個(gè)一致性的狀態(tài)，這增加了在NVM上編程的難度.另外，如果想要充分發(fā)揮多核處理器的性能，用戶既要保證并發(fā)正確性又要保證崩潰一致性，這進(jìn)一步增加了用戶的編程負(fù)擔(dān)，降低了用戶的開發(fā)效率.

為了降低在NVM上編寫并發(fā)程序的難度，研究人員提出了持久性事務(wù)內(nèi)存(durable transactional memory, DTM)[21-22]，通過擴(kuò)展傳統(tǒng)事務(wù)內(nèi)存，即增加持久性的特性，在保證并發(fā)正確性的同時(shí)又能保證數(shù)據(jù)的崩潰一致性.目前，針對(duì)持久性事務(wù)內(nèi)存已經(jīng)有很多相關(guān)的工作，但是這些工作普遍存在擴(kuò)展性較差的問題，即隨著線程數(shù)量的增加，DTM的性能無法繼續(xù)提升甚至?xí)焖傧陆礫22-23].測(cè)試發(fā)現(xiàn)，導(dǎo)致擴(kuò)展性差的原因主要有2個(gè)：1)中心化的全局邏輯時(shí)鐘；2)大量冗余的NVM寫操作.

大多數(shù)事務(wù)內(nèi)存的實(shí)現(xiàn)都是基于時(shí)間戳的(或者稱為基于時(shí)間的)[24-25].通過全局邏輯時(shí)鐘，事務(wù)內(nèi)存以較低的代價(jià)來檢驗(yàn)在一個(gè)事務(wù)中操作的數(shù)據(jù)是否是一致的，從而保證并發(fā)訪問的正確性.然而，全局邏輯時(shí)鐘一般是通過一個(gè)全局的整型變量來實(shí)現(xiàn)的，并通過原子指令或者鎖來保證多線程同時(shí)修改的正確性.在持久性事務(wù)內(nèi)存中，每個(gè)更新的事務(wù)都需要向全局邏輯時(shí)鐘申請(qǐng)一個(gè)時(shí)間戳.當(dāng)運(yùn)行線程數(shù)量增加時(shí)，多個(gè)線程同時(shí)更新全局變量會(huì)引起大量的緩存爭(zhēng)用，特別是跨NUMA(non-uniform memory access)節(jié)點(diǎn)時(shí)，這種緩存爭(zhēng)用的開銷更大.因此，全局邏輯時(shí)鐘在多線程環(huán)境下有較差的擴(kuò)展性，從而限制了持久性事務(wù)內(nèi)存的擴(kuò)展性.

另外，為了保障數(shù)據(jù)的崩潰一致性，在更新數(shù)據(jù)時(shí)，往往不能直接原地修改，這是因?yàn)槿绻藭r(shí)發(fā)生系統(tǒng)崩潰或者機(jī)器掉電，NVM中將會(huì)存在部分更新的數(shù)據(jù)，進(jìn)而導(dǎo)致數(shù)據(jù)不一致.通常的做法是先將數(shù)據(jù)在異地持久化之后再進(jìn)行修改，由此便引入了大量冗余的NVM寫操作[19,22].由于NVM的寫延遲較高，冗余的寫操作將導(dǎo)致事務(wù)的執(zhí)行時(shí)間變長(zhǎng)，在事務(wù)內(nèi)存中，更新事務(wù)在完成前會(huì)一直持有所要修改的數(shù)據(jù)的鎖，其他訪問該數(shù)據(jù)的事務(wù)因無法獲得鎖而處于等待的狀態(tài)，從而造成持久性事務(wù)內(nèi)存較差的擴(kuò)展性.

本文主要針對(duì)持久性事務(wù)內(nèi)存中的全局邏輯時(shí)鐘和大量冗余的NVM寫操作問題，設(shè)計(jì)了高擴(kuò)展性的線程邏輯時(shí)鐘以及緩存行感知的雙版本方法，并實(shí)現(xiàn)了一個(gè)高性能且高擴(kuò)展性的持久性軟件事務(wù)內(nèi)存.

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

1) 針對(duì)全局邏輯時(shí)鐘的擴(kuò)展性較差，本文提出線程邏輯時(shí)鐘，允許每個(gè)線程都擁有一個(gè)獨(dú)立時(shí)鐘，并采用了基于數(shù)據(jù)驅(qū)動(dòng)的時(shí)鐘獲取方法，完全消除了中心化問題，為用戶提供了一個(gè)高擴(kuò)展性的時(shí)鐘原語；

2) 現(xiàn)有崩潰一致性保障方法引入了大量NVM寫操作，本文提出了緩存行感知的雙版本方法，利用NVM緩存行特性，通過在NVM上連續(xù)存儲(chǔ)2個(gè)版本以及輪流更新來保證崩潰一致性，從而消除了冗余的NVM寫操作；

3) 基于線程邏輯時(shí)鐘和緩存行感知的雙版本實(shí)現(xiàn)了一個(gè)高擴(kuò)展性的持久性軟件事務(wù)內(nèi)存(scalable durable transactional memory, SDTM)，并在真實(shí)NVM器件上進(jìn)行了充分的測(cè)試.測(cè)試結(jié)果顯示，在真實(shí)負(fù)載下，SDTM相比于DudeTM和PMDK，其性能最高分別提升了2.8倍和29倍.

1 相關(guān)工作

目前，針對(duì)持久性事務(wù)內(nèi)存已經(jīng)有很多相關(guān)的研究，為了提升其性能以及擴(kuò)展性，各種各樣的優(yōu)化被應(yīng)用到持久性事務(wù)內(nèi)存上.表1展示了最新的研究中所使用的優(yōu)化方法，這些優(yōu)化可以分為2類：1)基于硬件輔助的優(yōu)化；2)基于多版本或者多副本的優(yōu)化.基于硬件輔助的方法主要使用硬件時(shí)鐘以及硬件事務(wù)內(nèi)存來提升性能，這種基于硬件輔助的方法雖然能夠在一定程度上提升持久性事務(wù)內(nèi)存的擴(kuò)展性，但是存在兼容性以及可移植性的問題.多版本和多副本的方法分別主要用來提升只讀事務(wù)性能和降低崩潰一致性保障開銷，不過，這些方法浪費(fèi)了一定的存儲(chǔ)空間，是對(duì)性能和存儲(chǔ)的折衷.

由表1可以發(fā)現(xiàn)，目前大部分持久性事務(wù)內(nèi)存都是基于軟件事務(wù)內(nèi)存的，和硬件事務(wù)內(nèi)存相比，軟件事務(wù)內(nèi)存不依賴于特定的硬件，具有更好的實(shí)用性.DudeTM[25]既支持軟件事務(wù)內(nèi)存又支持硬件事務(wù)內(nèi)存，后面將進(jìn)行詳細(xì)的說明.需要指出的是，PMDK[26]僅僅支持單線程，為了使其支持多線程，按照通用的方法，對(duì)其增加了讀寫鎖.KaminoTX[27]和Romulus[28]采用的也是基于鎖的并發(fā)控制，和基于時(shí)間戳的并發(fā)控制相比，其對(duì)每個(gè)數(shù)據(jù)的訪問都要獲得鎖，由此帶來了大量的加鎖開銷.本文將主要研究基于時(shí)間戳的并發(fā)控制[29]，基于鎖的并發(fā)控制不再做過多的討論.

Table 1 Optimizations of Durable Transactional Memory表1 不同的持久性事務(wù)內(nèi)存采用的優(yōu)化方法

1.1 基于硬件輔助的持久性事務(wù)內(nèi)存

為了提升持久性事務(wù)內(nèi)存的性能，可以采用一些硬件輔助的方法，這主要體現(xiàn)在2個(gè)方面：1)硬件時(shí)鐘；2)硬件事務(wù)內(nèi)存.基于時(shí)間戳的持久性事務(wù)內(nèi)存需要一個(gè)統(tǒng)一的時(shí)鐘來產(chǎn)生獨(dú)一無二的時(shí)間戳，該時(shí)間戳被用作數(shù)據(jù)的版本號(hào)，當(dāng)執(zhí)行事務(wù)時(shí)，可以用該版本號(hào)來校驗(yàn)數(shù)據(jù)的一致性[25].因此，需要為每個(gè)更新事務(wù)分配一個(gè)時(shí)間戳，當(dāng)更新事務(wù)較多時(shí)，時(shí)間戳的產(chǎn)生速度很可能會(huì)成為性能的瓶頸.按照實(shí)現(xiàn)方法的不同，時(shí)鐘可以分為2種：1)邏輯時(shí)鐘[25,30];2)硬件時(shí)鐘[31-32].

邏輯時(shí)鐘通常使用一個(gè)全局的整型變量來實(shí)現(xiàn)，每次分配時(shí)將其值加1.為了保證多線程更新的正確性，可以使用鎖或者原子指令來對(duì)其進(jìn)行保護(hù)，但是，當(dāng)線程數(shù)量增加時(shí)，特別是超線程或者跨NUMA[33]節(jié)點(diǎn)時(shí)，這種方法會(huì)引入大量的緩存爭(zhēng)用，導(dǎo)致時(shí)間戳的產(chǎn)生速度急劇下降，進(jìn)而成為了整個(gè)系統(tǒng)擴(kuò)展性的瓶頸[34-35].為了解決這個(gè)問題，一些研究直接使用處理器自帶的時(shí)鐘，即硬件時(shí)鐘.處理器時(shí)鐘的值可以使用特定的指令來獲得，由于時(shí)鐘的值是單調(diào)遞增的，因此其產(chǎn)生的時(shí)間戳也是獨(dú)一無二的.在NUMA架構(gòu)下，每個(gè)處理器都擁有一個(gè)自己的時(shí)鐘，因此多個(gè)硬件時(shí)鐘需要進(jìn)行同步.然而，幾乎所有類型的處理器都無法提供一個(gè)全局同步且高分辨率的時(shí)鐘，這是因?yàn)樘峁┻@種時(shí)鐘的開銷較大，在硬件上很難實(shí)現(xiàn)[31].

目前，一些主流的處理器開始提供一種不變硬件時(shí)鐘(invariant hardware clocks)，該時(shí)鐘擁有一個(gè)重要的特性，即其頻率不隨處理器的頻率改變，始終以固定的頻率運(yùn)行[36-37].根據(jù)這個(gè)特性可以發(fā)現(xiàn)，雖然多個(gè)處理器無法提供全局同步的時(shí)鐘，但是它們之間的時(shí)鐘僅僅存在一個(gè)固定的偏差.因此，Kashyap等人[31]利用不變時(shí)鐘提供了一個(gè)全局同步的時(shí)鐘，即ORDO，并提供了一套相應(yīng)的接口，用戶可以使用這些接口直接將邏輯時(shí)鐘替換成ORDO.TimeStone[26]直接使用了ORDO，從而消除由于邏輯時(shí)鐘而導(dǎo)致的性能瓶頸.但是，ORDO也存在一些問題，比如并不是所有的處理器都支持硬件時(shí)鐘，因此，和邏輯時(shí)鐘相比，其兼容性和可移植性較差.

除了使用硬件時(shí)鐘來消除邏輯時(shí)鐘擴(kuò)展性的瓶頸外，還可以使用硬件事務(wù)內(nèi)存來降低事務(wù)內(nèi)存的開銷[38].相比于軟件事務(wù)內(nèi)存，硬件事務(wù)內(nèi)存直接在緩存一致性協(xié)議中檢查數(shù)據(jù)的一致性，因此具有更低的開銷.目前，英特爾公司的Haswell架構(gòu)處理器已經(jīng)支持了硬件事務(wù)內(nèi)存，即受限事務(wù)內(nèi)存(restricted transactional memory, RTM)[39].除此之外，ARM和IBM的Power架構(gòu)也提供了對(duì)硬件事務(wù)內(nèi)存的支持.另外，硬件事務(wù)內(nèi)存提供了和軟件事務(wù)內(nèi)存類似的接口，因此在持久性事務(wù)內(nèi)存中，將軟件事務(wù)內(nèi)存替換成硬件事務(wù)內(nèi)存是十分簡(jiǎn)單的.

如表1所示，DudeTM的實(shí)現(xiàn)既可以使用基于時(shí)間戳的軟件事務(wù)內(nèi)存，又可以使用硬件事務(wù)內(nèi)存.當(dāng)使用硬件事務(wù)內(nèi)存時(shí)，所有的事務(wù)內(nèi)存功能都在硬件層實(shí)現(xiàn)，可避免時(shí)鐘的使用.現(xiàn)有的持久性事務(wù)內(nèi)存大多采用日志保障崩潰一致性，日志和數(shù)據(jù)之間嚴(yán)格的持久化順序約束引起了很大的開銷.為了降低此開銷，DudeTM解耦了持久性內(nèi)存在關(guān)鍵路徑上的操作.其在DRAM中維護(hù)了一個(gè)非持久性的數(shù)據(jù)副本，所有的事務(wù)操作均在此副本上執(zhí)行.對(duì)于更新操作，當(dāng)事務(wù)完成后，再按照事務(wù)執(zhí)行的順序異步(或同步)寫回到NVM上的持久性副本中.

盡管硬件事務(wù)內(nèi)存可大大提升持久性事務(wù)內(nèi)存的性能，但是其也存在3個(gè)問題：1)硬件事務(wù)內(nèi)存受限于CPU緩存的容量限制，只能有效支持小事務(wù)；2)有些架構(gòu)的處理器不支持硬件事務(wù)內(nèi)存，如MIPS和alpha架構(gòu)；3)對(duì)于同一架構(gòu)，不同的版本對(duì)硬件事務(wù)內(nèi)存的支持也有區(qū)別，比如IBM的POWER9支持硬件事務(wù)內(nèi)存，但在POWER10中又刪除了硬件事務(wù)內(nèi)存.因此，基于硬件輔助的持久性事務(wù)內(nèi)存雖然可以消除時(shí)鐘的瓶頸以及提升事務(wù)內(nèi)存的性能，但是有限的容量和較差的可移植性導(dǎo)致其實(shí)用性較低.

1.2 基于單版本/多版本/多副本的持久性事務(wù)內(nèi)存

1) 基于單版本的持久性事務(wù)內(nèi)存

為了保證數(shù)據(jù)的崩潰一致性，往往不能對(duì)數(shù)據(jù)進(jìn)行就地更新，這是因?yàn)樵诟聲r(shí)如果發(fā)生系統(tǒng)崩潰或者掉電，將會(huì)導(dǎo)致部分更新，并且在系統(tǒng)重啟后也無法恢復(fù)到一個(gè)一致性的狀態(tài)[40-41].為了解決這個(gè)問題，之前的工作通常會(huì)采用寫前日志的方法來保證數(shù)據(jù)的崩潰一致性.日志主要分為undo日志和redo日志.

PMDK[23]采用了undo日志，即在修改數(shù)據(jù)之前，將原始數(shù)據(jù)持久化到日志中，如果發(fā)生崩潰，可以借助日志將數(shù)據(jù)恢復(fù)到修改前的狀態(tài).該方法存在一個(gè)很大的問題，即針對(duì)每一個(gè)更新，都必須等到日志持久化之后才可以進(jìn)行修改，即將事務(wù)分割成多個(gè)交替的日志和數(shù)據(jù)，這增加了順序化的約束且位于關(guān)鍵路徑上，影響了持久性事務(wù)內(nèi)存的性能.和PMDK不同，Mnemosyne[19]采用了redo日志的方法，其將更新的數(shù)據(jù)存儲(chǔ)在日志中，因此允許事務(wù)內(nèi)存將一個(gè)事務(wù)涉及的所有日志一起持久化到NVM，再進(jìn)行數(shù)據(jù)更新.相比于undo日志減少了順序化約束的開銷，但是對(duì)更新數(shù)據(jù)的讀要重定向到日志中，增加了地址重映射的開銷，并且也存在至少1倍的寫放大問題.另外，在并發(fā)控制上，Mnemosyne采用的是全局邏輯時(shí)鐘，其擴(kuò)展性被嚴(yán)重制約.

2) 基于多版本的持久性事務(wù)內(nèi)存

在事務(wù)內(nèi)存中，多版本的方法經(jīng)常用來降低更新事務(wù)對(duì)只讀事務(wù)的阻塞，提升其性能.當(dāng)更新事務(wù)正在更新某個(gè)數(shù)據(jù)時(shí)，只讀事務(wù)是無法對(duì)該數(shù)據(jù)進(jìn)行讀取的，只能等待或者重試.這是因?yàn)楦率聞?wù)還沒有提交，數(shù)據(jù)處于一種中間狀態(tài)，此時(shí)讀取數(shù)據(jù)將破壞事務(wù)的隔離性與原子性.因此，更新事務(wù)會(huì)阻塞只讀事務(wù)的執(zhí)行，造成只讀事務(wù)產(chǎn)生較大的延遲.特別是對(duì)于執(zhí)行時(shí)間較長(zhǎng)的只讀事務(wù)，比如遍歷所有數(shù)據(jù)的操作，在最壞的情況下，該操作可能一直在重試，從而永遠(yuǎn)無法完成.

Pisces[20]使用了雙版本來提升讀操作的性能，其將redo日志作為一個(gè)新的版本來為讀操作服務(wù).具體來說，在更新數(shù)據(jù)時(shí)，Pisces[20]先把更新寫入日志，此時(shí)日志中便存儲(chǔ)了該數(shù)據(jù)的第2個(gè)版本中.當(dāng)有其他事務(wù)讀取該數(shù)據(jù)時(shí)，便可以利用這個(gè)較新的版本為讀操作服務(wù).然而，Pisces[20]放松了對(duì)一致性的約束，僅僅提供了快照隔離級(jí)[42]，將會(huì)導(dǎo)致用戶編程復(fù)雜.另外，日志仍然需要寫回到本地，依舊存在寫放大的問題.TimeStone[26]使用多版本來實(shí)現(xiàn)了更高的擴(kuò)展性和支持不同的隔離級(jí)，其通過操作日志來保證持久性，并在DRAM中維護(hù)了多個(gè)版本來提升持久性事務(wù)內(nèi)存的性能.然而，TimeStone依賴于硬件時(shí)鐘，并且操作日志和redo日志類似，仍然存在寫放大的問題.

3) 基于多副本的持久性事務(wù)內(nèi)存

經(jīng)過分析可以發(fā)現(xiàn)，無論是undo日志還是redo日志，都存在一些問題.首先，它們都會(huì)導(dǎo)致冗余的NVM寫操作.其次，undo日志會(huì)引入較多的持久化順序約束；而redo日志由于將數(shù)據(jù)寫到了異地，在事務(wù)中訪問這些未提交的數(shù)據(jù)時(shí)，將會(huì)引入數(shù)據(jù)重定向的問題[22].這些問題都會(huì)影響持久性事務(wù)內(nèi)存的性能以及擴(kuò)展性，為了解決這些問題，一些研究開始使用多副本的方法對(duì)其進(jìn)行優(yōu)化.

DudeTM[22]通過非持久性副本和持久性副本來解耦更新事務(wù)在關(guān)鍵路徑上的操作，并通過重做日志的方法將事務(wù)持久化.但是為了保證數(shù)據(jù)的一致性，DudeTM僅使用一個(gè)線程來重做日志，因此，其擴(kuò)展性較差.KaminoTX[27]和Romulus[28]為數(shù)據(jù)維護(hù)了2個(gè)持久性副本，稱為主副本和從副本，所有的更新操作直接在主副本中進(jìn)行，等到主副本持久化之后，再異步寫回到從副本中.如果發(fā)生崩潰，可以使用從副本(或主副本)來恢復(fù)，因此消除了關(guān)鍵路徑上的阻塞.同樣，這2種方法都存在寫放大的問題.和DudeTM類似，Romulus使用單線程來將數(shù)據(jù)寫回到從副本，因此擴(kuò)展性較差.而KaminoTX在將數(shù)據(jù)持久化到從副本的過程中都需要持有鎖，阻礙了其他事務(wù)的執(zhí)行，影響了擴(kuò)展性.另外，基于多副本的方法由于需要額外的存儲(chǔ)數(shù)據(jù)，因此對(duì)NVM的空間造成了浪費(fèi).

2 持久性事務(wù)內(nèi)存擴(kuò)展性測(cè)試

本節(jié)通過測(cè)試來分析制約基于時(shí)間戳的持久性事務(wù)內(nèi)存擴(kuò)展性的因素.其中，2.1節(jié)測(cè)試了全局邏輯時(shí)鐘的擴(kuò)展性；2.2節(jié)分析了在崩潰一致性保障機(jī)制中，冗余的NVM寫操作對(duì)持久性事務(wù)內(nèi)存擴(kuò)展性的制約.

2.1 全局邏輯時(shí)鐘

在基于時(shí)間戳的事務(wù)內(nèi)存中，有3個(gè)操作涉及時(shí)鐘：1)事務(wù)開始時(shí)，讀取時(shí)鐘的值，稱為起始時(shí)鐘，并記錄在局部變量sc(start clock)中；2)讀取數(shù)據(jù)時(shí)，通過sc和數(shù)據(jù)的時(shí)間戳來檢驗(yàn)數(shù)據(jù)的一致性；3)提交事務(wù)時(shí)，將時(shí)鐘的值加1并返回，該返回值即是提交時(shí)間戳ct(commit timestamp).這3個(gè)操作封裝成3個(gè)API，即get_time，cmp_time，new_time.

目前，使用最廣泛的是全局邏輯時(shí)鐘，其實(shí)現(xiàn)方式簡(jiǎn)單并且不依賴于特定硬件.該時(shí)鐘可以是一個(gè)全局整型變量，其初始值為0，并使用鎖或者原子指令來保證并發(fā)的正確性.圖1展示了在不同的并發(fā)保護(hù)方法下，全局邏輯時(shí)鐘的擴(kuò)展性.基于C++ mutex的方法在修改全局邏輯時(shí)鐘前，需先獲取互斥鎖，然后再進(jìn)行修改；基于add_and_fetch或compare_and_swap(CAS)指令的方法可以對(duì)全局邏輯時(shí)鐘直接進(jìn)行更新.測(cè)試所用的機(jī)器有2個(gè)NUMA節(jié)點(diǎn)，每個(gè)NUMA節(jié)點(diǎn)有36個(gè)核，這里使用了1～64個(gè)線程進(jìn)行測(cè)試.從圖1中可以發(fā)現(xiàn)，無論是基于哪種并發(fā)控制的時(shí)鐘，其擴(kuò)展性都很差.當(dāng)線程數(shù)量為1時(shí)，其性能是最好的，這是因?yàn)樵谥挥幸粋€(gè)線程的情況下，不會(huì)產(chǎn)生任何緩存競(jìng)爭(zhēng)的開銷.隨著線程數(shù)量的增加，便有更多的緩存需要同步，維護(hù)緩存一致性的開銷也就越大.

Fig. 1 The scalability of global logical clock圖1 全局邏輯時(shí)鐘的擴(kuò)展性

TL2是經(jīng)典的基于全局時(shí)間戳的軟件事務(wù)內(nèi)存，借助于TL2算法，本文實(shí)現(xiàn)了一個(gè)并發(fā)的鏈?zhǔn)缴⒘斜?，并用鏈表來解決沖突.圖2展示了在不同數(shù)量的線程下執(zhí)行插入操作時(shí)的吞吐量以及時(shí)鐘操作所占的開銷.從中可以發(fā)現(xiàn)，隨著線程數(shù)量的增加，散列表的吞吐量在達(dá)到8個(gè)線程便開始緩慢增加(32～40線程出現(xiàn)下降，是因?yàn)榭缬蛄薔UMA節(jié)點(diǎn))，而全局邏輯時(shí)鐘所占的開銷也是越來越大，最高達(dá)到了79%.

Fig. 2 The throughput of Hash table and the overhead of clock圖2 散列表的吞吐量以及時(shí)鐘開銷

基于圖1與圖2的分析可以發(fā)現(xiàn)，全局邏輯時(shí)鐘的擴(kuò)展性較差，嚴(yán)重制約了事務(wù)內(nèi)存的擴(kuò)展性，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)低開銷且高擴(kuò)展性時(shí)鐘成為提升持久性事務(wù)內(nèi)存擴(kuò)展性的重要途徑.雖然目前已經(jīng)有一些方法對(duì)邏輯時(shí)鐘進(jìn)行了研究，但是這些方法僅僅緩解了時(shí)鐘擴(kuò)展性問題，而沒有真正的解決.Silo[43]使用了批量的原子修改，根據(jù)DBX1000[44]測(cè)試，當(dāng)存在較多沖突時(shí)，該方法的擴(kuò)展性較差；TicToc[45]消除了全局時(shí)鐘，但是這種方法并不保證事務(wù)的Opacity[46]特性；Zhang等人[47]試圖通過優(yōu)化事務(wù)的提交階段來減少對(duì)時(shí)鐘不必要的更新，僅僅緩解了時(shí)鐘的問題.

2.2 冗余的NVM寫操作

為了保證數(shù)據(jù)一致性，持久性事務(wù)內(nèi)存通常采用undo日志或redo日志.顯然，兩者都存在大量冗余的NVM寫操作，這主要體現(xiàn)在：為了使數(shù)據(jù)在崩潰后可以恢復(fù)一致性的狀態(tài)，需要將數(shù)據(jù)在異地進(jìn)行持久化，這種異地的持久化至少增加了1倍的寫操作(對(duì)于redo是2倍，因?yàn)檫€要將數(shù)據(jù)寫回到本地).圖3展示了在使用undo或者redo日志的情況下，基于時(shí)間戳的持久性事務(wù)內(nèi)存的吞吐量.這里使用持久性事務(wù)內(nèi)存實(shí)現(xiàn)了一個(gè)并發(fā)且持久性的二叉搜索樹，并用讀寫混合負(fù)載(50%讀，50%更新)對(duì)其進(jìn)行測(cè)試.由圖3可以發(fā)現(xiàn)，不管使用哪種日志，持久性事務(wù)內(nèi)存的擴(kuò)展性都不是很好，在超過16個(gè)線程后，吞吐量便不再有明顯的提升.并且，在達(dá)到40個(gè)線程時(shí)，吞吐量有明顯的下降，這是因?yàn)榭缭搅薔UMA節(jié)點(diǎn)，導(dǎo)致了遠(yuǎn)程內(nèi)存訪問.

Fig. 3 The throughputs of transactional memory with different logs圖3 不同的日志方法下事務(wù)內(nèi)存的吞吐量

為了進(jìn)一步探究NVM的寫操作對(duì)持久性事務(wù)內(nèi)存擴(kuò)展性的影響，本文測(cè)試了在不同的訪問粒度下隨機(jī)寫操作的延遲，如圖4所示.從圖4中可以發(fā)現(xiàn)，針對(duì)DRAM的隨機(jī)寫延遲最低，而針對(duì)NVM的隨機(jī)寫，其延遲大概是DRAM的3倍.另外，為了將數(shù)據(jù)進(jìn)行持久化，需要調(diào)用緩存寫回指令(CLFLUSH或CLWB)將數(shù)據(jù)從CPU緩存寫回NVM中，從圖4可以看出，緩存寫回指令也會(huì)帶來較多延遲.另外，為了保證持久化的順序，需要調(diào)用內(nèi)存屏障指令(MFENCE)確保前面指令完成再執(zhí)行后面指令.基于undo日志的持久性事務(wù)內(nèi)存需要使用大量的內(nèi)存屏障，這是因?yàn)楫?dāng)更新數(shù)據(jù)時(shí)，必須等待針對(duì)該數(shù)據(jù)的日志持久化到NVM后才可以更新，這引入了大量的等待，且都位于關(guān)鍵路徑.而redo日志只需要在數(shù)據(jù)寫回時(shí)調(diào)用一次內(nèi)存屏障指令，因此redo日志的擴(kuò)展性以及性能要明顯優(yōu)于undo日志.

Fig. 4 The latency of NVM and DRAM under random write圖4 NVM和DRAM隨機(jī)寫操作的延遲

盡管基于redo日志不需要使用大量的內(nèi)存屏障指令，但是帶來了更多的NVM寫操作，并且引入了數(shù)據(jù)重定向的開銷，即在訪問數(shù)據(jù)時(shí)必須重定向到日志中，這增加了一次緩存缺失的開銷.大量冗余的NVM寫操作是這樣影響持久性事務(wù)內(nèi)存的擴(kuò)展性的：由圖4可知，NVM上的寫操作延遲較高，會(huì)導(dǎo)致事務(wù)執(zhí)行時(shí)間更長(zhǎng)；而在持久性事務(wù)內(nèi)存中，更新事務(wù)在完成前會(huì)一直持有所要修改的數(shù)據(jù)的鎖，這會(huì)導(dǎo)致其他需要訪問該數(shù)據(jù)的事務(wù)由于無法獲取鎖而處于等待的狀態(tài)，從而嚴(yán)重影響了事務(wù)內(nèi)存的擴(kuò)展性.因此，提升擴(kuò)展性的核心在于減少單個(gè)事務(wù)的執(zhí)行時(shí)間，從而降低不同事務(wù)之間由于鎖的爭(zhēng)用而導(dǎo)致的阻塞，undo日志和redo日志顯然都沒有很好地解決這個(gè)問題.

3 高擴(kuò)展性的線程邏輯時(shí)鐘

本文提出了一種線程邏輯時(shí)鐘方案：通過允許每個(gè)線程都擁有自己的時(shí)鐘，消除了全局邏輯時(shí)鐘中心化問題；采用數(shù)據(jù)驅(qū)動(dòng)的時(shí)鐘獲取方法，完全消除了緩存爭(zhēng)用的開銷；通過動(dòng)態(tài)擴(kuò)展起始時(shí)鐘，大大降低了事務(wù)的終止率.基于這些優(yōu)化，線程邏輯時(shí)鐘擁有了近似于硬件時(shí)鐘的性能以及擴(kuò)展性.

3.1 時(shí)間戳的構(gòu)成

線程邏輯時(shí)鐘和全局邏輯時(shí)鐘最大的區(qū)別在于其允許每個(gè)線程都擁有一個(gè)自己的邏輯時(shí)鐘，并且每個(gè)線程只能修改自己的邏輯時(shí)鐘，而不能修改其他線程的.為了生成獨(dú)一無二的時(shí)間戳，使用線程ID和此線程的時(shí)鐘值共同構(gòu)成時(shí)間戳.由于所有線程的ID是不同的且每個(gè)線程的時(shí)鐘都是單調(diào)遞增的，因此，使用這種方法構(gòu)成的時(shí)間戳是一定不會(huì)重復(fù)的.圖5展示了時(shí)間戳的結(jié)構(gòu)，大小是64 b，其中前n位存儲(chǔ)線程ID，后64-n位用來存儲(chǔ)邏輯時(shí)鐘的值.n的大小由線程數(shù)量決定，須滿足2n大于或等于線程數(shù).

Fig. 5 The composition of timestamp under thread logical clock圖5 線程邏輯時(shí)鐘下時(shí)間戳的構(gòu)成

和全局邏輯時(shí)鐘一樣，線程邏輯時(shí)鐘使用整型變量實(shí)現(xiàn)，只是不再是全局變量，而是線程局部變量(thread-local variables)，從C++11開始已經(jīng)支持該類型.對(duì)于線程ID，操作系統(tǒng)通常會(huì)為每個(gè)線程分配單獨(dú)的值.但是系統(tǒng)提供的線程ID值一般較大，這會(huì)導(dǎo)致存儲(chǔ)線程邏輯時(shí)鐘值的空間變小，進(jìn)而容易引起時(shí)鐘的溢出.并且，當(dāng)線程運(yùn)行結(jié)束后，其ID不會(huì)立即被回收，而是等達(dá)到最大值的時(shí)候再回收.那么隨著線程的創(chuàng)建與銷毀，在運(yùn)行時(shí)系統(tǒng)中便需要維護(hù)大量的線程ID，這會(huì)帶來一定的存儲(chǔ)開銷.因此，線程邏輯時(shí)鐘不使用操作系統(tǒng)提供的線程ID，而是自己為線程分配.

為了對(duì)線程ID進(jìn)行管理，設(shè)計(jì)了一個(gè)線程ID分配器.由于線程ID的分配與回收僅僅在線程創(chuàng)建和銷毀時(shí)被調(diào)用，其性能不會(huì)成為系統(tǒng)的瓶頸，因此設(shè)計(jì)了一個(gè)全局的ID分配器，并用C++中的互斥鎖來保證并發(fā)的正確性.線程ID是從0開始分配的，和線程ID綁定的還有其對(duì)應(yīng)的邏輯時(shí)鐘，其初始值也是0.當(dāng)新的線程被創(chuàng)建時(shí)，便會(huì)從分配器中搜索一個(gè)空閑的ID分配給它，相應(yīng)的也將該ID對(duì)應(yīng)的邏輯時(shí)鐘交給該線程使用.當(dāng)線程被銷毀時(shí)，該線程ID和該線程的邏輯時(shí)鐘被一起回收，但時(shí)鐘的值不會(huì)被重置，這樣當(dāng)再次分配后，便不會(huì)出現(xiàn)重復(fù)的時(shí)間戳.

3.2 基于數(shù)據(jù)驅(qū)動(dòng)的時(shí)鐘獲取方法

雖然每個(gè)線程的邏輯時(shí)鐘只有該線程自己可以修改，但是多個(gè)線程的讀操作也會(huì)帶來大量的緩存爭(zhēng)用開銷.這是因?yàn)楦鶕?jù)緩存一致性協(xié)議，當(dāng)一個(gè)線程讀取一個(gè)變量后，便在自己的緩存里增加了該變量的一個(gè)副本，如果有其他線程對(duì)該變量進(jìn)行了修改，那么這個(gè)線程里的副本便需要被同步，通常的做法是置為無效狀態(tài).當(dāng)線程數(shù)量增加，這種同步的操作便會(huì)帶來大量的開銷.特別是在跨NUMA節(jié)點(diǎn)時(shí)，這種開銷就會(huì)更大，由此嚴(yán)重影響了線程邏輯時(shí)鐘的擴(kuò)展性.

為了解決這個(gè)問題，需要避免使用全局變量.本文提出的基于數(shù)據(jù)驅(qū)動(dòng)的時(shí)鐘獲取方法源自于一種簡(jiǎn)單的觀察：數(shù)據(jù)的時(shí)間戳存儲(chǔ)著線程邏輯時(shí)鐘的歷史值.根據(jù)3.1節(jié)的介紹，時(shí)間戳由2部分組成：線程ID和該線程的邏輯時(shí)鐘值.當(dāng)更新事務(wù)在提交時(shí)，會(huì)通過函數(shù)new_time獲得獨(dú)一無二的時(shí)間戳，即提交時(shí)間戳，并且該提交時(shí)間戳?xí)粚懭氲奖桓碌臄?shù)據(jù)的時(shí)間戳屬性中.因此，在數(shù)據(jù)的時(shí)間戳屬性中存儲(chǔ)著所有線程的邏輯時(shí)鐘的歷史值.

這里使用了歷史值，是因?yàn)椴⒉皇撬袛?shù)據(jù)的時(shí)間戳都存儲(chǔ)著邏輯時(shí)鐘的最新值，根據(jù)線程邏輯時(shí)鐘的執(zhí)行流程，只有少量數(shù)據(jù)存儲(chǔ)著最新值，大部分?jǐn)?shù)據(jù)存儲(chǔ)的是時(shí)鐘的舊值，即比真正的邏輯時(shí)鐘的值要小.使用這些較舊的時(shí)鐘值來檢驗(yàn)數(shù)據(jù)的一致性是完全可行的，這是因?yàn)闀r(shí)鐘值總是單調(diào)遞增的，如果事務(wù)開始后，其訪問的數(shù)據(jù)被其他更新事務(wù)修改，那么被修改后的數(shù)據(jù)，其時(shí)間戳一定大于任何一個(gè)之前產(chǎn)生的舊的時(shí)間戳.和TicToc[45]相比，盡管都使用了基于數(shù)據(jù)驅(qū)動(dòng)的方法，但是本文是為了獲取起始時(shí)鐘，而TicToc是通過數(shù)據(jù)的時(shí)間戳信息來計(jì)算得到提交時(shí)間戳.

圖6是一個(gè)基于線程邏輯時(shí)鐘的更新事務(wù)執(zhí)行過程的例子，該事務(wù)所作的操作是先讀取對(duì)象A再修改對(duì)象B.該更新事務(wù)是由線程0執(zhí)行的，因此線程0的起始時(shí)鐘可以直接獲得，方法get_time會(huì)把線程0的起始時(shí)鐘設(shè)置為1，線程1的起始時(shí)鐘設(shè)置為0.接著，事務(wù)開始讀寫數(shù)據(jù).對(duì)象A校驗(yàn)通過，當(dāng)使用cmp_time檢驗(yàn)對(duì)象B時(shí)，發(fā)現(xiàn)其時(shí)間戳大于線程1的起始時(shí)鐘，此時(shí)先將線程1的起始時(shí)鐘修改為4，然后終止該事務(wù)并重試.重試的事務(wù)其起始時(shí)鐘分別是1和4，此時(shí)數(shù)據(jù)校驗(yàn)都可以通過.最終該事務(wù)完成.

由更新事務(wù)的執(zhí)行流程來看，基于數(shù)據(jù)驅(qū)動(dòng)的方法直接從數(shù)據(jù)的時(shí)間戳中獲取起始時(shí)鐘，從而避免了訪問全局變量，完全消除了緩存一致性的開銷.但是，從圖6的例子中也可以發(fā)現(xiàn)，該方法增加了事務(wù)的終止率.可以優(yōu)化的一點(diǎn)是，當(dāng)事務(wù)完成后，該事務(wù)記錄的起始時(shí)鐘可以存儲(chǔ)下來，這樣下個(gè)事務(wù)便可以直接使用上個(gè)事務(wù)的起始時(shí)鐘，從而降低事務(wù)的終止率.即使通過這種方法優(yōu)化后，事務(wù)的終止率仍然很高，這是因?yàn)榛跀?shù)據(jù)驅(qū)動(dòng)的方法獲取的時(shí)鐘值比當(dāng)前的時(shí)鐘值更舊，這意味著在進(jìn)行數(shù)據(jù)校驗(yàn)時(shí)更容易失敗.盡管較高的終止率會(huì)影響事務(wù)的性能，但是和全局邏輯時(shí)鐘相比，基于數(shù)據(jù)驅(qū)動(dòng)的線程邏輯時(shí)鐘仍然擁有更好的擴(kuò)展性.

3.3 動(dòng)態(tài)擴(kuò)展起始時(shí)鐘

基于數(shù)據(jù)驅(qū)動(dòng)的時(shí)鐘獲取方法雖然能夠消除緩存同步的開銷，但所獲取的時(shí)鐘值往往偏舊.盡管使用這些偏舊的時(shí)鐘值來校驗(yàn)數(shù)據(jù)的一致性是完全可行的，但是往往會(huì)帶來較高的事務(wù)終止率，進(jìn)而影響事務(wù)性能.這是因?yàn)槭聞?wù)終止的處理是使用函數(shù)sigsetjmp來實(shí)現(xiàn)的，在事務(wù)開始前，首先調(diào)用函數(shù)sigsetjmp來保存目前的堆棧環(huán)境，如果事務(wù)終止，便調(diào)用函數(shù)siglongjmp跳轉(zhuǎn)到由前面保存的位置，繼續(xù)該事務(wù)的執(zhí)行.這種指令的跳轉(zhuǎn)不利于CPU流水線的執(zhí)行，并且對(duì)CPU的緩存也不友好，進(jìn)而影響事務(wù)的性能以及擴(kuò)展性.

為了解決這個(gè)問題，本文提出了一種動(dòng)態(tài)擴(kuò)展起始時(shí)鐘的方法.傳統(tǒng)的基于時(shí)間戳的事務(wù)內(nèi)存，在事務(wù)開始時(shí)首先獲得起始時(shí)鐘，如果事務(wù)不發(fā)生終止，那么該時(shí)鐘的值在該事務(wù)的執(zhí)行過程中便不會(huì)再發(fā)生改變.然而，本文發(fā)現(xiàn)起始時(shí)鐘在一定條件下是可以改變的，該條件是該事務(wù)所訪問的數(shù)據(jù)在事務(wù)開始后沒有被其他線程修改.這是因?yàn)槿绻麧M足該條件，那么和事務(wù)終止后再重新執(zhí)行所達(dá)到的狀態(tài)時(shí)完全相同的.因此當(dāng)該條件成立時(shí)，將對(duì)應(yīng)的起始時(shí)鐘修改為一個(gè)更大的值仍然能夠保證數(shù)據(jù)的一致性，同時(shí)避免了事務(wù)終止的發(fā)生.由于被更新的數(shù)據(jù)在訪問時(shí)都會(huì)獲取鎖，所以一定不會(huì)被其他事務(wù)修改，因此不需要校驗(yàn)?zāi)切└碌臄?shù)據(jù)，只需要對(duì)只讀的數(shù)據(jù)(只讀的數(shù)據(jù)會(huì)保存在集合中，稱為read-set)進(jìn)行校驗(yàn).

盡管采用動(dòng)態(tài)擴(kuò)展起始時(shí)鐘的方法需要遍歷read-set集合以檢驗(yàn)數(shù)據(jù)的一致性，但是該方法總是能夠提升事務(wù)的性能的.這是因?yàn)?，如果不采用該方法，在事?wù)終止并重試時(shí)，需要重新開始執(zhí)行，這種重新執(zhí)行也會(huì)將終止之前的數(shù)據(jù)再訪問一遍.因此，動(dòng)態(tài)擴(kuò)展起始時(shí)鐘的方法總是有效的，它在一定程度上避免了長(zhǎng)指令跳轉(zhuǎn)，有利于CPU流水線的執(zhí)行以及利用CPU的緩存.

3.4 線程邏輯時(shí)鐘的實(shí)現(xiàn)

線程邏輯時(shí)鐘是使用C++來實(shí)現(xiàn)的，其為用戶提供了簡(jiǎn)單易用的API，即get_time，cmp_time，new_time，本節(jié)將主要描述這3個(gè)函數(shù)的實(shí)現(xiàn).在介紹這些函數(shù)的實(shí)現(xiàn)之前，這里先來描述事務(wù)結(jié)構(gòu)體TX，該結(jié)構(gòu)體的主要成員如表2所示.在TX結(jié)構(gòu)體中，因?yàn)槠鹗紩r(shí)鐘不止一個(gè)，這里使用了數(shù)組來存儲(chǔ)起始時(shí)鐘，該數(shù)組的大小即為支持的最大線程數(shù)量.另外，分別使用集合read_set和wrtie_set記錄數(shù)據(jù)讀寫過的數(shù)據(jù)，read_set僅僅記錄數(shù)據(jù)的地址，write_set同時(shí)還保存著數(shù)據(jù)修改后的值.

Table 2 Data Members of Transaction Structure表2 事務(wù)結(jié)構(gòu)體的主要數(shù)據(jù)成員

每個(gè)線程單獨(dú)擁有一個(gè)TX結(jié)構(gòu)體實(shí)例，在線程剛被創(chuàng)建時(shí)，需要對(duì)該實(shí)例進(jìn)行初始化.首先從線程ID管理器中獲得一個(gè)空閑的線程ID，并對(duì)tid和tc進(jìn)行初始化，然后將數(shù)組scs中的元素全部初始化為0.為了能夠復(fù)用TX結(jié)構(gòu)體實(shí)例，特別是scs成員，避免針對(duì)每個(gè)事務(wù)都創(chuàng)建一個(gè)新的結(jié)構(gòu)體，在事務(wù)開始前，需要對(duì)集合read_set和write_set清0，其他的數(shù)據(jù)成員不需要改動(dòng).

線程邏輯時(shí)鐘為用戶提供了簡(jiǎn)單的API，這些API的形式和全局邏輯時(shí)鐘相似，以方便用戶對(duì)傳統(tǒng)的時(shí)鐘進(jìn)行替換.使用者可以完全不用了解線程邏輯時(shí)鐘的具體實(shí)現(xiàn)方法，只需要調(diào)用這些API即可，下面將分別介紹這3個(gè)API的實(shí)現(xiàn)，如算法1所示：

算法1.線程邏輯時(shí)鐘偽代碼.

① Functionget_time(tx)

②tx.scs[tid]=tx.tc;

③ Functioncmp_time(tx)

④ ifts.tc≤tx.scs[ts.tid] then

⑤ return true;

⑥ else

⑦tx.scs[ts.tid]=ts.tc;

⑧ iftx.read_set是一致的 then

⑨ return true;

⑩ end if

在基于數(shù)據(jù)驅(qū)動(dòng)的時(shí)鐘獲取方法下，get_time方法只需要獲取自己線程的邏輯時(shí)鐘值，并賦值給對(duì)應(yīng)的起始時(shí)鐘.cmp_time首先檢驗(yàn)數(shù)據(jù)的時(shí)間戳ts，如果通過，直接返回true，否則在事務(wù)的數(shù)組scs中更新該時(shí)間戳對(duì)應(yīng)的起始時(shí)鐘.下一步，即算法1的行⑧，檢查集合read_set的一致性，如果檢查通過，返回true，否則返回false.方法new_time為用戶返回一個(gè)獨(dú)一無二的時(shí)間戳，首先將該線程的時(shí)鐘值加1，然后將線程ID和該時(shí)鐘值組合在一起并返回，該返回值即是更新事務(wù)的提交時(shí)間戳.

4 緩存行感知的雙版本方法

為了消除數(shù)據(jù)崩潰一致性保障過程中的冗余NVM寫操作，本文還提出了一種緩存行感知的雙版本方法.該方法利用真實(shí)NVM器件的特性，將2個(gè)版本連續(xù)存儲(chǔ)，并利用混合內(nèi)存的架構(gòu)來提升性能；另外，類似于傳統(tǒng)的多版本，雙版本可以用來提升只讀事務(wù)的性能；給出了2種崩潰一致性恢復(fù)機(jī)制.

4.1 數(shù)據(jù)存儲(chǔ)格式

緩存行感知的雙版本結(jié)合了多副本和多版本的優(yōu)點(diǎn)，既能夠?qū)崿F(xiàn)數(shù)據(jù)的直接更新和避免異地持久化操作，又能夠利用雙版本提升只讀事務(wù)的性能.傳統(tǒng)的多版本方案通常使用鏈表存儲(chǔ)多個(gè)版本，動(dòng)態(tài)地為新的版本分配空間，并且保證最新的版本被最先訪問到.但是由于鏈表指針訪問的緩存局部性不好，NVM的讀寫延遲比DRAM高，其緩存缺失的開銷也更大，因此緩存行感知的雙版本采用了連續(xù)存儲(chǔ)的數(shù)據(jù)布局方案，如圖7所示：

Fig. 7 Data layout of cache line conscious dual versions圖7 緩存行感知的雙版本的數(shù)據(jù)布局

其中l(wèi)ock是該數(shù)據(jù)的鎖，這里用CAS指令實(shí)現(xiàn)了該鎖.標(biāo)記位new用來指定哪個(gè)版本是最新的，new=0表示V0是最新的，new=1表示V1是最新的.之所以使用new而不是直接比較2個(gè)版本的時(shí)間戳，是為了和線程邏輯時(shí)鐘進(jìn)行集成，因?yàn)榫€程邏輯時(shí)鐘的時(shí)間戳是無法直接進(jìn)行比較的，除非擁有相同的線程ID.緊接著存儲(chǔ)的是數(shù)據(jù)的2個(gè)版本V0和V1，并附帶它們的時(shí)間戳ts0和ts1.數(shù)據(jù)是與NVM的緩存行對(duì)齊的，由于現(xiàn)有的NVM器件(Intel Optane DCPMM)的緩存行是256 B[48]，因此對(duì)于大部分?jǐn)?shù)據(jù)結(jié)構(gòu)來說2個(gè)版本可以存儲(chǔ)在同一個(gè)緩存行中，從而避免了在訪問第2個(gè)版本時(shí)所引起的緩存行缺失的開銷.當(dāng)然，這種提前為多版本分配存儲(chǔ)空間的做法對(duì)存儲(chǔ)空間造成了浪費(fèi)，一種可行的方法是針對(duì)那些不經(jīng)常更新的數(shù)據(jù)，仍采用單版本方法進(jìn)行存儲(chǔ)，因?yàn)槟切┲蛔x的數(shù)據(jù)是不會(huì)從緩存行感知的雙版本中得到性能提升的.

在基于緩存行感知的雙版本方法中，數(shù)據(jù)的2個(gè)版本是循環(huán)被修改的，這樣能保證在任何時(shí)候NVM中都存在一個(gè)一致性的版本，從而在系統(tǒng)崩潰或者掉電后將數(shù)據(jù)恢復(fù)到一致性的狀態(tài).例如，假設(shè)一個(gè)更新事務(wù)要修改數(shù)據(jù)A，當(dāng)前A的V0版本是最新的，在事務(wù)提交時(shí)，便將對(duì)A的修改直接持久化到A的V1版本.如果此時(shí)系統(tǒng)發(fā)生崩潰，在機(jī)器重啟后可以使用A的V0版本將數(shù)據(jù)恢復(fù)到一致的狀態(tài).如果更新事務(wù)成功，那么A的V1成為了最新的版本，下次的修改將直接寫到V0中.因此，緩存行感知的雙版本方法完全消除了日志所引起的冗余NVM寫操作.相比于多副本方法在主副本更新成功后還需將更新同步到備用副本而引起NVM寫放大，緩存行感知的雙版本方法是直接覆蓋較舊的版本，不需要任何同步操作.

為了降低NVM較高的寫延遲對(duì)事務(wù)內(nèi)存擴(kuò)展性的影響，緩存行感知的雙版本還充分利用了混合內(nèi)存的優(yōu)勢(shì).目前，NVM的讀寫延遲和DRAM相比仍然有比較大的差距，很難在短時(shí)間內(nèi)取代DRAM，在未來較長(zhǎng)時(shí)間內(nèi)，NVM和DRAM共存于計(jì)算機(jī)系統(tǒng)將成為一種常態(tài).因此，可以利用DRAM來提升持久性事務(wù)內(nèi)存的性能，本文設(shè)計(jì)了一種基于混合內(nèi)存的存儲(chǔ)架構(gòu)，數(shù)據(jù)完全存儲(chǔ)在NVM中以保證持久性，將事務(wù)在執(zhí)行時(shí)臨時(shí)產(chǎn)生的數(shù)據(jù)存儲(chǔ)在DRAM中，因?yàn)檫@些臨時(shí)的數(shù)據(jù)不需要進(jìn)行持久化，如果發(fā)生崩潰，不需要對(duì)它們進(jìn)行恢復(fù).

臨時(shí)數(shù)據(jù)是在事務(wù)訪問數(shù)據(jù)時(shí)產(chǎn)生的，當(dāng)事務(wù)第1次訪問某個(gè)數(shù)據(jù)時(shí)，會(huì)將該數(shù)據(jù)直接拷貝到DRAM中，再次訪問該數(shù)據(jù)時(shí)，便可直接從快速DRAM中獲取.在事務(wù)提交時(shí)，對(duì)于只讀數(shù)據(jù)，可以直接釋放其在DRAM上分配的空間；對(duì)于更新的數(shù)據(jù)，在釋放DRAM空間前，需先將修改寫回到NVM中.這種方法使得持久性事務(wù)內(nèi)存的大部分時(shí)間都是在DRAM上運(yùn)行的，從而降低了單個(gè)事務(wù)的執(zhí)行時(shí)間，極大地提升了持久性事務(wù)內(nèi)存的性能和擴(kuò)展性.

4.2 基于雙版本的只讀事務(wù)優(yōu)化

緩存行感知的雙版本方法的優(yōu)勢(shì)不僅在于能夠消除冗余的NVM寫操作，同時(shí)還能用來提升只讀事務(wù)的性能.和傳統(tǒng)的多版本的組織方法不同，緩存行感知的雙版本采用的是循環(huán)更新的方法，版本的新舊在每一次更新后都會(huì)發(fā)生變化.因此，對(duì)于一個(gè)只讀事務(wù)來說，在訪問數(shù)據(jù)時(shí)，需要先使用new來定位最新的版本，并優(yōu)先對(duì)其進(jìn)行訪問.如果最新的版本不滿足條件，再去訪問較舊的版本.

在2種場(chǎng)景下，雙版本是可以提升只讀事務(wù)的性能的.1)被訪問的數(shù)據(jù)沒有被其他事務(wù)修改，且對(duì)最新版本的時(shí)間戳檢查沒有通過，這時(shí)訪問較舊的版本能夠降低只讀事務(wù)的終止率.2)被訪問的數(shù)據(jù)正在被其他事務(wù)修改，且對(duì)最新版本的時(shí)間戳檢查沒有通過，此時(shí)只讀事務(wù)會(huì)終止并重試，防止因等待更新事務(wù)的完成而產(chǎn)生阻塞.但是有一點(diǎn)需要注意的是，在函數(shù)cmp_time中，被檢查的時(shí)間戳必須是一個(gè)已經(jīng)提交了事務(wù)的時(shí)間戳.這是因?yàn)?，如果該事?wù)還未完成，那么基于數(shù)據(jù)驅(qū)動(dòng)的時(shí)鐘獲取方法會(huì)得到一個(gè)超前的時(shí)鐘，使用該時(shí)鐘去訪問數(shù)據(jù)將會(huì)讀取到事務(wù)的中間狀態(tài).因此，在檢查數(shù)據(jù)的時(shí)間戳前，首先獲取該版本的時(shí)間戳并記錄，然后通過檢查該版本是否被加鎖來驗(yàn)證時(shí)間戳的有效性.

4.3 崩潰恢復(fù)機(jī)制

系統(tǒng)崩潰可能會(huì)導(dǎo)致系統(tǒng)在重啟后處于不一致的狀態(tài)，比如一個(gè)更新事務(wù)完成了對(duì)部分?jǐn)?shù)據(jù)的修改，如果這時(shí)系統(tǒng)發(fā)生崩潰，在系統(tǒng)重啟后便殘留著這個(gè)沒有完成的事務(wù).緩存行感知的雙版本崩潰恢復(fù)機(jī)制和基于日志的方法有很大不同.在基于日志的方法下，不管是undo日志還是redo日志，它們都將被修改的數(shù)據(jù)的地址在日志中進(jìn)行了持久化.在崩潰后進(jìn)行恢復(fù)時(shí)，便可以按照日志將數(shù)據(jù)恢復(fù)到更新事務(wù)開始前的狀態(tài)或者重做日志以完成更新事務(wù).緩存行感知的雙版本方法沒有使用日志，而是采用循環(huán)更新的方法直接覆蓋較舊的版本，并且保留較新的版本以便在崩潰時(shí)將數(shù)據(jù)恢復(fù)到一致的狀態(tài).這里存在的問題是，在崩潰恢復(fù)時(shí)，將無法知道哪些數(shù)據(jù)在崩潰前被修改，即無法知道哪些數(shù)據(jù)是不一致的.

本文提出了2種緩存行感知的雙版本崩潰恢復(fù)機(jī)制：1)基于全局掃描的方法；2)基于更新地址寫回的方法.在基于全局掃描的方法下，在更新事務(wù)執(zhí)行時(shí)不需要持久化被更新的數(shù)據(jù)的地址.在系統(tǒng)崩潰恢復(fù)時(shí)，由于不知道哪些數(shù)據(jù)是不一致的，因此需要全局掃描所有的數(shù)據(jù).為了能夠檢測(cè)出不一致的數(shù)據(jù)，即那些被中斷的更新事務(wù)修改過的數(shù)據(jù)，在修改數(shù)據(jù)前，需要將提交時(shí)間戳持久化到日志中；在事務(wù)完成后，再將該提交時(shí)間戳從日志中刪除.這樣，在進(jìn)行全局掃面時(shí)，如果數(shù)據(jù)的時(shí)間戳等于日志中的時(shí)間戳，即表示該數(shù)據(jù)是不一致的，便可以使用另一個(gè)版本將其恢復(fù)到更新事務(wù)執(zhí)行前的狀態(tài).該方法的優(yōu)點(diǎn)是不需要持久化更新數(shù)據(jù)的地址，減少了運(yùn)行時(shí)開銷，但是由于需要全局掃描，其恢復(fù)時(shí)間較長(zhǎng).

基于更新地址寫回的方法，在更新事務(wù)修改數(shù)據(jù)前，需要把被修改的數(shù)據(jù)的地址全部持久化到日志中.這樣，在崩潰恢復(fù)時(shí)，通過日志中記錄的地址便可以準(zhǔn)確知道哪些數(shù)據(jù)在崩潰前被修改，從而避免了全局掃描的開銷，做到快速恢復(fù).顯然，這種方法引入了一定的運(yùn)行時(shí)開銷.但是，由于僅僅持久化數(shù)據(jù)的地址，而不是數(shù)據(jù)本身，因此這種開銷和傳統(tǒng)的基于日志的方法相比是比較小的.在具體的應(yīng)用場(chǎng)景下，可以根據(jù)需求的不同選擇不同的崩潰恢復(fù)機(jī)制，默認(rèn)情況下，本文選用了基于更新地址寫回的方法.

4.4 緩存行感知的雙版本的實(shí)現(xiàn)

緩存行感知的雙版本也是使用C++實(shí)現(xiàn)的，借助于C++中的抽象類以及類模板，為用戶提供了簡(jiǎn)單的編程接口.首先，緩存行感知的雙版本為用戶提供了AbstractPtmObject抽象類，該類主要定義了2個(gè)接口：CopyToDram和WriteToNvm.其中CopyToDram是將本地的數(shù)據(jù)拷貝到DRAM中；WriteToNvm是把DRAM中的數(shù)據(jù)寫回到NVM中.用戶所有的類都應(yīng)該繼承該抽象類，并實(shí)現(xiàn)這2個(gè)函數(shù).其次，在事務(wù)內(nèi)存中，所有的讀寫操作都應(yīng)該被截獲.緩存行感知的雙版本對(duì)用戶的類進(jìn)行了封裝，提供了一個(gè)類模板PtmObjectWrapper，如表3所示:

Table 3 The Main Members of PtmObjectWrapper表3 PtmObjectWrapper類模板主要成員

用戶通過OpenWithRead和OpenWithWrite來對(duì)數(shù)據(jù)進(jìn)行讀寫[5]，本節(jié)將重點(diǎn)介紹這2個(gè)函數(shù)的實(shí)現(xiàn)，如算法2所示.

Fig. 8 The architecture of SDTM圖8 SDTM架構(gòu)圖

算法2.緩存行感知的雙版本.

① FunctionOpenWithRead(tx)

②saved_new=new;

③saved_ts=saved_new==0?ts0:ts1;

④ iflock≠saved_new&&time_cmp(tx,

saved_ts) then

⑤ret=saved_new==0?V0.CopyToDram

():V1.CopyToDram();

⑥ ifnew==saved_new&&lock≠

saved_new&& (saved_new==

0?ts0:ts1)==saved_tsthen

⑦ returnret;

⑧ end if

⑨ end if

⑩ iftxis not READ_ONLY then

saved_ts) then

==0?ts0:ts1)==saved_tsthen

&&time_cmp(tx,saved_ts) then

==0?ts0:ts1)==saved_tsthen

OpenWithRead在讀取數(shù)據(jù)時(shí)會(huì)首先嘗試較新的版本，當(dāng)較新的版本不滿足條件時(shí)再嘗試較舊的，如果仍然不滿足，便會(huì)終止并重試.在函數(shù)Open-WithRead中，當(dāng)把數(shù)據(jù)拷貝到DRAM后，需要對(duì)數(shù)據(jù)的有效性再次進(jìn)行檢查，如算法2中的⑥所示.這是因?yàn)樵诳截悢?shù)據(jù)的過程中，數(shù)據(jù)可能已經(jīng)被其他事務(wù)修改.和OpenWithRead不同的是，Open-WithWrite需要獲取鎖，這里使用了CAS指令來執(zhí)行加鎖操作.需要注意的是，在獲取鎖后lock的值應(yīng)該指向較舊的版本，這是因?yàn)楦鶕?jù)緩存行感知的雙版本的更新邏輯，較舊的版本會(huì)被直接覆蓋.在獲取鎖成功并且時(shí)間戳檢查通過后，調(diào)用CopyToDram來將較新的版本拷貝到DRAM中，以后在該事務(wù)中對(duì)于該數(shù)據(jù)的訪問將直接重定向到DRAM中.

5 可擴(kuò)展的持久性軟件事務(wù)內(nèi)存SDTM

基于線程邏輯時(shí)鐘和緩存行感知的雙版本方法，我們實(shí)現(xiàn)了一個(gè)可擴(kuò)展性的持久性軟件事務(wù)內(nèi)存SDTM，其架構(gòu)如圖8所示.SDTM的架構(gòu)分為2層：在NVM中持久化數(shù)據(jù)；在DRAM中加速數(shù)據(jù)的訪問，吸收對(duì)數(shù)據(jù)的讀寫操作.圖8也展示了一個(gè)事務(wù)執(zhí)行的過程，該事務(wù)讀取對(duì)象A，并修改對(duì)象B.在讀取數(shù)據(jù)時(shí)，依據(jù)new來判斷哪個(gè)版本是最新的，然后將對(duì)應(yīng)的版本拷貝到DRAM中.由于對(duì)B進(jìn)行了修改，因此，在事務(wù)提交時(shí)需要將其寫回到NVM中.可以發(fā)現(xiàn)，這里采用了就地更新的方法，直接覆蓋了較舊的版本，消除了冗余的NVM寫操作.

SDTM集成了線程邏輯時(shí)鐘和緩存行感知的雙版本方法，并為用戶提供了4個(gè)API：sdtm_start，sdtm_commit，sdtm_read，sdtm_write，如算法3所示.用戶使用sdtm_start開始一個(gè)事務(wù)，使用sdtm_commit來提交事務(wù)，需要注意的是，在函數(shù)sdtm_commit中，只有更新事務(wù)才需要提交，對(duì)于只讀事務(wù)，由于沒有進(jìn)行任何修改，直接返回即可.sdtm_abort用來終止并重試事務(wù)，它釋放write_set的鎖，并跳轉(zhuǎn)到事務(wù)開始的地方進(jìn)行重試，用戶不需要自己調(diào)用該函數(shù).

算法3.SDTM算法.

① Functionsdtm_start(tx)

②get_time(tx);

③ clearread_set;/*清空read_set*/

④ clearwrite_set;/*清空write_set*/

⑤ Functionsdtm_commit(tx)

⑥ iftxis not READ_ONLY then

⑦ iftx.read_setis not valid then

⑧sdtm_abort();

⑨ end if

⑩ct=new_time(tx);

wrapperAddr,ct);

(wrapperAddr))‖(ret=tx.read_

set.Find(wrapperAddr)) then

then

/*用戶不可直接調(diào)用*/

sdtm_read用來讀取數(shù)據(jù)，在真正地訪問數(shù)據(jù)前，首先檢查在write_set和read_set中是否存在該數(shù)據(jù)的拷貝.如果存在，表明在之前訪問過該數(shù)據(jù)，且在DRAM中存在一個(gè)拷貝，這樣可以直接返回該拷貝的地址，避免訪問低速的NVM.這里，首先檢查的是write_set，這是因?yàn)槿绻谶@個(gè)事務(wù)中該數(shù)據(jù)被修改，那么被修改后的數(shù)據(jù)(也即是最新的數(shù)據(jù))一定在write_set中.如果在DRAM中找不到該數(shù)據(jù)，則通過函數(shù)OpenWithRead在DRAM中生成一個(gè)拷貝，并插入到read_set中，然后返回該拷貝的地址.sdtm_write和sdtm_read相似，只是sdtm_write僅僅在write_set中查找是否有該數(shù)據(jù)的拷貝，并且調(diào)用的是函數(shù)OpenWithWrite.

6 實(shí)驗(yàn)與結(jié)果

6.1 實(shí)驗(yàn)環(huán)境與內(nèi)容

本文所做的測(cè)試都是在真實(shí)的NVM硬件環(huán)境下進(jìn)行的，實(shí)驗(yàn)設(shè)備的配置參數(shù)如表4所示.其中，服務(wù)器有2個(gè)NUMA節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有36個(gè)核，并使用了超線程，并裝備了192 GB的DRAM和1.5 TB的Optane DCPMM.Optane DCPMM共有3種配置模式：Memory Mode，App Direct Mode，Mixed Mode.由于Memory Mode不保證持久性，因此這里使用的是App Direct Mode配置，并使用PMDK來對(duì)其空間的分配與回收進(jìn)行管理.本文使用了TINYSTM[24]中的測(cè)試框架，每個(gè)測(cè)試的運(yùn)行時(shí)間為10 s，并連續(xù)運(yùn)行5次然后取平均值.在測(cè)試中發(fā)現(xiàn)，libc自帶的內(nèi)存分配器ptmalloc[49]擴(kuò)展性較差，為了消除內(nèi)存分配器對(duì)測(cè)試的影響，本文使用了在多線程下具有更高性能的jemalloc[50].

Table 4 The Configuration of Server表4 服務(wù)器配置信息

測(cè)試共分為2個(gè)部分，分別是并發(fā)數(shù)據(jù)結(jié)構(gòu)測(cè)試和真實(shí)負(fù)載測(cè)試.在并發(fā)數(shù)據(jù)結(jié)構(gòu)的測(cè)試中，本文基于SDTM實(shí)現(xiàn)了3種并發(fā)且持久性的數(shù)據(jù)結(jié)構(gòu)，包括散列表、二叉搜索樹、有序鏈表，并使用了不同比例的讀寫負(fù)載對(duì)其擴(kuò)展性進(jìn)行了測(cè)試.之所以選擇3種不同的數(shù)據(jù)結(jié)構(gòu)，是因?yàn)檫@些數(shù)據(jù)結(jié)構(gòu)的競(jìng)爭(zhēng)情況不同.散列表的沖突較少，因此競(jìng)爭(zhēng)較?。欢行蜴湵淼臎_突較多，因此競(jìng)爭(zhēng)最大.這樣，可以測(cè)試出SDTM在不同競(jìng)爭(zhēng)情況下的性能與擴(kuò)展性.在真實(shí)負(fù)載的測(cè)試中，本文基于SDTM實(shí)現(xiàn)了一個(gè)B+樹，并使用YSCB[51]提供的典型負(fù)載對(duì)其進(jìn)行了詳細(xì)的測(cè)試，以此來驗(yàn)證SDTM在真實(shí)負(fù)載下的效果.

Fig. 9 The throughput and abort rate of Hash table圖9 散列表的吞吐量以及事務(wù)終止

另外，為了驗(yàn)證SDTM的先進(jìn)性，本文將SDTM和最新的研究進(jìn)行了對(duì)比，包括DudeTM和PMDK.在DudeTM的具體實(shí)現(xiàn)中，其既可以基于軟件事務(wù)內(nèi)存，也可以基于硬件事務(wù)內(nèi)存，由于SDTM是完全基于軟件的，這里為了公平性，進(jìn)行對(duì)比的也是基于軟件事務(wù)內(nèi)存的DuteTM.另外，按照對(duì)持久性的要求，DudeTM又分為同步的DudeTM和異步的DudeTM，異步的DudeTM在事務(wù)完成后不會(huì)立即將數(shù)據(jù)寫回到NVM，而是在累積一定數(shù)據(jù)量的日志后再一起寫回，這可以帶來性能的提升，但是放松了對(duì)持久性的要求，本文進(jìn)行對(duì)比測(cè)試的是異步的DudeTM.由于PMDK沒有對(duì)多線程進(jìn)行同步，按照通用的做法，本文使用了讀寫鎖來保證并發(fā)的正確性.

6.2 并發(fā)持久性數(shù)據(jù)結(jié)構(gòu)測(cè)試

在本節(jié)中，基于SDTM，DudeTM，PMDK分別實(shí)現(xiàn)了3種并發(fā)且持久性的數(shù)據(jù)結(jié)構(gòu)：散列表、二叉搜索樹和有序鏈表，并使用讀為主(2%更新)、讀密集(20%更新)和寫密集(80%更新)3種負(fù)載對(duì)這3種數(shù)據(jù)結(jié)構(gòu)進(jìn)行測(cè)試.另外，為了進(jìn)一步對(duì)測(cè)試結(jié)果進(jìn)行分析，本文還統(tǒng)計(jì)了對(duì)應(yīng)的事務(wù)終止率，其中事務(wù)終止率指的是被終止的事務(wù)占提交事務(wù)的比例，由于一個(gè)事務(wù)可能會(huì)被多次終止并重試，因此終止率是可以大于100%的.

1) 散列表

本實(shí)驗(yàn)將散列表的初始大小設(shè)為1萬個(gè)桶，并使用鏈表解決沖突.對(duì)于所有測(cè)試，預(yù)先往散列表中插入1萬個(gè)鍵值對(duì)，再執(zhí)行工作負(fù)載.由于散列表被設(shè)置的較大，并且現(xiàn)有的散列函數(shù)能很好地將數(shù)據(jù)均勻分布，因此發(fā)生沖突的概率很小，具有很好的擴(kuò)展性.

圖9是測(cè)試結(jié)果，圖9(a)～9(c)分別對(duì)應(yīng)讀為主、讀密集和寫密集3種負(fù)載，圖9(d)～9(f)是對(duì)應(yīng)的事務(wù)終止率.可以看到，不管是基于哪種負(fù)載，SDTM都擁有最好的擴(kuò)展性，且隨著更新比例的增加，其他事務(wù)內(nèi)存和SDTM的性能差距越來越大.另外，從事務(wù)的終止率中可以看到，SDTM的終止率一直維持在一個(gè)很低的水平.這主要有2個(gè)原因：①線程邏輯時(shí)鐘和緩存行感知的雙版本方法加速了單個(gè)事務(wù)的執(zhí)行時(shí)間，降低了事務(wù)沖突的概率；②雙版本減少了更新事務(wù)對(duì)只讀事務(wù)的阻塞，降低了只讀事務(wù)的失敗重試次數(shù).由于PMDK使用讀寫鎖來進(jìn)行并發(fā)控制，不會(huì)存在事務(wù)終止的情況，因此圖9中沒有顯示它的終止率.

2) 二叉搜索樹

二叉搜索樹和散列表相比存在較多的競(jìng)爭(zhēng)，這是因?yàn)閷?duì)于樹的訪問，都是從根節(jié)點(diǎn)開始的，如果中間節(jié)點(diǎn)發(fā)生改變，那么路過該中間節(jié)點(diǎn)的事務(wù)都會(huì)受到影響.同樣，在測(cè)試前，在二叉搜索樹中插入1萬個(gè)鍵值對(duì)來進(jìn)行初始化，然后分別運(yùn)行這3種不同類型的負(fù)載，結(jié)果如圖10所示:

Fig. 10 The throughput and abort rate of binary search tree圖10 二叉搜索樹的吞吐量以及事務(wù)終止率

從圖10中可以發(fā)現(xiàn)，不管是在哪種負(fù)載下，SDTM都擁有最好的擴(kuò)展性，DudeTM和PMDK的性能隨著線程數(shù)的增加迅速下降，這主要是受到了全局邏輯時(shí)鐘以及undo日志的影響，而SDTM依然保持著很好的性能.在寫密集型的負(fù)載下，SDTM的吞吐量相對(duì)于DudeTM和PMDK最多可以分別達(dá)到7.6倍和17.5倍.從事務(wù)終止率來看，由于使用了雙版本來提升只讀事務(wù)的性能，即使是在寫密集的負(fù)載下，SDTM依然保持著較低的終止率，而DudeTM的終止率隨著線程數(shù)量的增加會(huì)快速升高.

3) 有序鏈表

在有序鏈表中，對(duì)于數(shù)據(jù)的訪問只能從鏈表的頭部開始，依次向后遍歷，即只有一條訪問路徑.根據(jù)事務(wù)的執(zhí)行過程，這種訪問數(shù)據(jù)的模式存在大量的競(jìng)爭(zhēng)，將會(huì)導(dǎo)致大量的事務(wù)終止并重試.比如，更新事務(wù)在提交時(shí)，需要檢查它所讀取的數(shù)據(jù)是否發(fā)生修改，對(duì)于有序鏈表來說，要校驗(yàn)從鏈表頭到這個(gè)被修改的數(shù)據(jù)之間的節(jié)點(diǎn)是否發(fā)生改變，當(dāng)線程數(shù)量較多時(shí)，這種校驗(yàn)極大可能會(huì)失敗，從而導(dǎo)致事務(wù)終止并重試.因此，有序鏈表本身是一個(gè)擴(kuò)展性較差的數(shù)據(jù)結(jié)構(gòu).為避免因鏈表太長(zhǎng)使得事務(wù)大部分執(zhí)行時(shí)間花費(fèi)在鏈表遍歷上，難以對(duì)不同事務(wù)內(nèi)存的擴(kuò)展性以及性能進(jìn)行比較，此處測(cè)試使用了256個(gè)鍵值對(duì)來初始化有序鏈表.

圖11展示了在不同負(fù)載下不同事務(wù)內(nèi)存的擴(kuò)展性以及終止率的測(cè)試結(jié)果.有意思的是，當(dāng)只有一個(gè)線程時(shí)，PMDK擁有最好的性能.這是因?yàn)镻MDK采用的是undo日志，當(dāng)以只讀的方式訪問有序鏈表中的某個(gè)節(jié)點(diǎn)時(shí)，可以直接對(duì)其進(jìn)行讀取，不需要像SDTM和DudeTM那樣將數(shù)據(jù)拷貝到另一個(gè)地方(DRAM)，這種內(nèi)存拷貝會(huì)占據(jù)大量的開銷.但是，隨著線程數(shù)量的增加，PMDK中的讀寫鎖成為了擴(kuò)展性的瓶頸，因?yàn)榧词箤?duì)于只讀事務(wù)，也需要加鎖.因此，在讀為主和讀密集的負(fù)載下，SDTM總體上保持著最好的擴(kuò)展性，但是在寫密集的負(fù)載下，PMDK展現(xiàn)了最好的性能.這是因?yàn)?，從?duì)應(yīng)的終止率中可以看出，SDTM和DudeTM在寫密集負(fù)載下的終止率較高，這時(shí)采用讀寫鎖來進(jìn)行并發(fā)控制往往能夠收獲更好的性能.

Fig. 11 The throughput and abort rate of sorted list圖11 有序鏈表的吞吐量以及事務(wù)終止率

6.3 真實(shí)負(fù)載測(cè)試

Fig. 12 The throughput of SDTM under YCSB workloads圖12 YCSB負(fù)載下SDTM的吞吐量

為了驗(yàn)證SDTM在真實(shí)負(fù)載下的效果，基于SDTM，本文實(shí)現(xiàn)了一個(gè)并發(fā)且持久性的B+樹，并使用YCSB性能測(cè)試工具集生成A～D共4個(gè)工作負(fù)載，請(qǐng)求的分布模式為傾斜分布.其中，load操作的數(shù)量為100萬，run操作的數(shù)量為1 000萬.圖12展示了4種YCSB負(fù)載下不同持久性事務(wù)內(nèi)存實(shí)現(xiàn)的B+樹的性能.從測(cè)試結(jié)果來看，不管是基于哪種負(fù)載，SDTM都擁有最好的擴(kuò)展性與性能，最高時(shí)SDTM的吞吐量是DudeTM的2.8倍，是PMDK的29倍.注意，在負(fù)載B,C,D中，當(dāng)線程數(shù)由32增加到40時(shí)，可以看到SDTM和DudeTM的性能有明顯的下降，這是因?yàn)榇嬖诳缭絅UMA節(jié)點(diǎn)的訪問，其開銷影響了事務(wù)內(nèi)存的性能.PMDK的性能沒有太大變化，是因?yàn)槠湫阅苤饕艿阶x寫鎖開銷的制約.

7 總 結(jié)

現(xiàn)有的持久性軟件事務(wù)內(nèi)存擴(kuò)展性較差，本文測(cè)試并分析了制約擴(kuò)展性的因素，發(fā)現(xiàn)中心化的全局邏輯時(shí)鐘和冗余的NVM寫操作嚴(yán)重影響了擴(kuò)展性.針對(duì)這2個(gè)問題，分別設(shè)計(jì)并實(shí)現(xiàn)了線程邏輯時(shí)鐘和緩存行感知的雙版本方法，消除了制約擴(kuò)展性的因素.基于這2種方法，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)高擴(kuò)展性的持久性軟件事務(wù)內(nèi)存SDTM，并在真實(shí)的NVM器件上使用YCSB工作負(fù)載進(jìn)行測(cè)試.結(jié)果顯示，相比于現(xiàn)有的持久性事務(wù)內(nèi)存DudeTM和PMDK，SDTM的性能最高分別提升了2.8倍和29倍.

作者貢獻(xiàn)聲明：劉超杰負(fù)責(zé)編寫代碼、做實(shí)驗(yàn)、撰寫論文；王芳負(fù)責(zé)修改和指導(dǎo)論文；鄒曉敏負(fù)責(zé)修改論文；馮丹負(fù)責(zé)指導(dǎo)論文.