面向數(shù)據(jù)庫的持久化事務(wù)內(nèi)存

Hillel Avni王 鵬

(華為技術(shù)有限公司 廣東深圳 518129)(hillel.avni@huawei.com)

非易失性內(nèi)存(nonvolatile memory, NVM)是一種新興的技術(shù)，有望在計(jì)算機(jī)內(nèi)存領(lǐng)域掀起一場變革.

研究人員剛剛開始了解如何在配置了非易失性內(nèi)存的機(jī)器上進(jìn)行編程.非易失性內(nèi)存的編程模型仍然在不斷變化中，但當(dāng)前下列模型處于領(lǐng)先地位.系統(tǒng)可以僅使用NVM，也可以將DRAM和NVM組合使用.在任何時(shí)候數(shù)據(jù)都會異步刷新到NVM，該過程對程序員透明.程序員也可以通過顯式調(diào)用刷新原語(Flush)將數(shù)據(jù)刷新到NVM.而持久化屏障(persistence barrier)原語允許阻塞進(jìn)程，直到已將數(shù)據(jù)刷新到NVM.

處理器的緩存和寄存器將滿足易失性還是非易失性仍存在重大爭議.一些研究人員正在研究如何在意外掉電時(shí)提供足夠的電能將這些數(shù)據(jù)刷新到非易失性內(nèi)存中[1].這種方法使應(yīng)用程序無需為持久化增加任何運(yùn)行開銷，因?yàn)檎麄€(gè)處理器的狀態(tài)是持久的.但是，硬件設(shè)計(jì)人員對其可行性持懷疑態(tài)度，他們擔(dān)心將處理器緩存刷新到NVM需要消耗很多電能，因?yàn)榫彺嫒萘糠浅４?，處理器非常?fù)雜而耗電.他們表示未來的硬件只能使用余電保存NVM控制器的易失性緩沖區(qū)中的數(shù)據(jù).英特爾目前正在基于這個(gè)假設(shè)并考慮了NVM而設(shè)計(jì)新的高效的Flush指令CLWB和CLFLUSHOPT[2].這些新指令假設(shè)緩存為易失性，并允許刷新的數(shù)據(jù)保存在緩存中，以避免緩存缺頁.這些指令也將加速刷新到NVM.

我們考慮處理器緩存和寄存器不具備非易失性的系統(tǒng).在這樣的系統(tǒng)中，關(guān)鍵挑戰(zhàn)是發(fā)生掉電并且緩存和寄存器被清除時(shí)仍能確保NVM總是處于一致的狀態(tài).

另一個(gè)被稱為硬件事務(wù)內(nèi)存(hardware trans-actional memory, HTM)的新技術(shù)最近在英特爾處理器中得以實(shí)現(xiàn)，該技術(shù)將數(shù)據(jù)庫中的事務(wù)概念引入共享內(nèi)存(HTM也在IBM的生產(chǎn)系統(tǒng)和各種研究系統(tǒng)中得以實(shí)現(xiàn)，本文僅考慮英特爾的實(shí)現(xiàn)).HTM允許程序員在事務(wù)中執(zhí)行任意代碼塊，這些代碼塊將以原子方式完成提交，或中止而不影響內(nèi)存中原有的內(nèi)容.英特爾的HTM實(shí)現(xiàn)采用盡力提交的方式，這意味著沒有事務(wù)可以保證提交.因此，當(dāng)一個(gè)事務(wù)中止足夠多次后，必須由程序員指定并執(zhí)行其非事務(wù)的回退路徑.最簡單的回退路徑是全局鎖定(即阻止其他進(jìn)程執(zhí)行事務(wù))并重新執(zhí)行事務(wù).但是，這種方法不適用于NVM，因?yàn)槿魏涡薷暮蟮臄?shù)據(jù)都會異步地刷新到NVM(可能會違反原子性).

HTM的實(shí)現(xiàn)和NVM方案之間的相互作用特別復(fù)雜，因?yàn)槭聞?wù)必須是原子的，但是在回退路徑上執(zhí)行的寫入可以在任何時(shí)間異步刷新到NVM.因此，必須仔細(xì)設(shè)計(jì)回退路徑，以避免在發(fā)生掉電故障時(shí)將正在進(jìn)行的事務(wù)的部分結(jié)果暴露給其他進(jìn)程.另一個(gè)復(fù)雜之處在于HTM不能直接修改主存，這樣事務(wù)對共享內(nèi)存的任何修改都是在執(zhí)行該事務(wù)的處理器核的本地緩存中的數(shù)據(jù)副本上執(zhí)行的.這樣，在事務(wù)提交與從緩存刷新到NVM之間存在一個(gè)時(shí)間窗.在此時(shí)間窗內(nèi)發(fā)生電源故障可能會導(dǎo)致部分或全部已提交事務(wù)的結(jié)果丟失.

Avni等人在最近的工作[3]中引入了PHTM算法，該算法允許硬件事務(wù)在包含NVM的系統(tǒng)中運(yùn)行.必須修改現(xiàn)有的HTM實(shí)現(xiàn)以支持NVM，因?yàn)橹辽傩枰黾右粋€(gè)用于標(biāo)記事務(wù)是否已提交的比特位作為HTM提交的一部分，與HTM一起原子性地刷新到NVM，否則，掉電故障可能導(dǎo)致已提交的事務(wù)丟失.Avni等人建議修改英特爾的HTM實(shí)現(xiàn)，允許將單個(gè)比特位作為事務(wù)提交的一部分原子性地刷新到NVM.PHTM使用此功能來維護(hù)重演日志(redo log)，以確保已提交的事務(wù)不會丟失.具體來說，允許PHTM同時(shí)提交一個(gè)事務(wù)，并將NVM中的重演日志標(biāo)記為已完成(completed)，以便在掉電后當(dāng)且僅當(dāng)事務(wù)已提交時(shí)才進(jìn)行重演.PHTM中的回退路徑是面向NVM設(shè)計(jì)的持久化軟件事務(wù)內(nèi)存(persistent software transactional memory, PSTM)，這是一種軟件事務(wù)內(nèi)存.不幸的是，PSTM順序執(zhí)行所有事務(wù)，并且該算法不支持硬件事務(wù)和軟件事務(wù)之間的并發(fā).這消除了在回退路徑上執(zhí)行時(shí)的所有并發(fā)性，并且使得該算法無法隨著HTM系統(tǒng)中處理器核數(shù)的增加而擴(kuò)展.

事務(wù)內(nèi)存(transactional memory, TM)的相關(guān)文獻(xiàn)引入了混合事務(wù)內(nèi)存(hybrid transactional memory, Hybrid TM)以解決此類性能問題.混合事務(wù)內(nèi)存通過使用在回退路徑上允許并發(fā)的軟件事務(wù)內(nèi)存算法來提高性能，并設(shè)計(jì)快速路徑算法，以便硬件和軟件事務(wù)可以同時(shí)運(yùn)行.然而，現(xiàn)有的混合事務(wù)內(nèi)存算法不適用于NVM，所以需要新的算法.

本文介紹了第一種面向NVM的混合事務(wù)內(nèi)存系統(tǒng)——PHyTM.與PHTM一樣，PHyTM通過重演日志進(jìn)行掉電后的恢復(fù).PHyTM提供了無死鎖、無活鎖的原子事務(wù).它有3種執(zhí)行路徑：1)快速HTM(fast HTM)，具有不插樁的硬件讀取速度；2)慢速HTM(slow HTM)，可以進(jìn)行插樁的讀、寫；3)軟件事務(wù)內(nèi)存，鎖定讀集合和寫集合，并緩沖所有的寫操作，直到事務(wù)提交時(shí)的寫回(write-back)階段.為了避免在極少數(shù)情況下發(fā)生活鎖，STM路徑上的事務(wù)可能會使用一個(gè)粗粒度的鎖排除STM路徑上的其他事務(wù)，但允許硬件事務(wù)繼續(xù).

快速HTM和慢速HTM可以同時(shí)運(yùn)行(因?yàn)閮烧叨际褂肏TM，因此硬件可以解決數(shù)據(jù)沖突)，慢速HTM和STM也可以同時(shí)運(yùn)行(因?yàn)槁貶TM像STM一樣獲取鎖).但是，由于快速HTM支持不插樁讀，因此不能在沒有額外機(jī)制能夠確定STM是否使存儲器處于不一致狀態(tài)的情況下與STM同時(shí)運(yùn)行.因此，快速HTM上的每個(gè)事務(wù)T都需要訂閱一個(gè)計(jì)數(shù)器，該計(jì)數(shù)器記錄了STM路徑上處于寫回階段的事務(wù)數(shù).如果在T執(zhí)行期間計(jì)數(shù)器非零，那么T可能看到不滿足一致性要求的狀態(tài)，所以需要中止T的執(zhí)行；如果T的中止次數(shù)過多，T將切換到STM路徑以保證得到處理.

諸如HANA(SAP)，Hekaton(微軟)，TimesTen(Oracle)，MemSQL和VoltDB等內(nèi)存數(shù)據(jù)庫(in-memory databases, IMDB)經(jīng)常應(yīng)用在單節(jié)點(diǎn)配置的數(shù)據(jù)分析系統(tǒng)中，以及響應(yīng)時(shí)間至關(guān)重要的應(yīng)用程序中，如電信網(wǎng)絡(luò)和實(shí)時(shí)金融服務(wù).在此類實(shí)現(xiàn)中，內(nèi)存數(shù)據(jù)庫使用同步機(jī)制的一部分來協(xié)調(diào)進(jìn)程對內(nèi)部數(shù)據(jù)結(jié)構(gòu)的訪問.常見的同步機(jī)制包括兩階段鎖(2-phase locking, 2PL)：樂觀并發(fā)控制(optimistic concurrency control, OCC)和多版本并發(fā)控制(multi-version concurrency control, MVCC).最近的研究表明，SAP HANA可以從當(dāng)前的HTM實(shí)現(xiàn)[4]中獲得顯著的性能提升，并且聲稱通過NVM的實(shí)現(xiàn)[5]提升了容錯(cuò)能力.因此，本文的一個(gè)有價(jià)值的應(yīng)用方向就是將PHyTM作為內(nèi)存數(shù)據(jù)庫新的同步機(jī)制，利用HTM的能力減少傳統(tǒng)方法的同步開銷，同時(shí)增加對NVM的支持.

為了證明這種方法的潛力，我們在支持HTM的英特爾系統(tǒng)上通過模擬NVM進(jìn)行了實(shí)驗(yàn).本文使用Yahoo!的云服務(wù)基準(zhǔn)測試(Yahoo! cloud serving benchmark，YCSB)和TPC-C進(jìn)行基準(zhǔn)測試，比較了使用4種不同的同步機(jī)制實(shí)現(xiàn)的簡單內(nèi)存數(shù)據(jù)庫的性能：2PL，OCC，PHTM和PHyTM.結(jié)果表明，PHyTM效率高并且可擴(kuò)展，往往明顯優(yōu)于其他機(jī)制.

我們預(yù)測非易失性內(nèi)存將成為標(biāo)準(zhǔn)，并可以適應(yīng)通用應(yīng)用程序.這些從未使用ACID事務(wù)的程序?qū)⒈仨氃贜VM中保持一致性，以保持系統(tǒng)的可恢復(fù)性.那時(shí)，PHTM和PHyTM可以用來維護(hù)數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫上下文.

作為正在進(jìn)行的和將來的工作，我們討論了分離事務(wù)執(zhí)行(split transactions execution, STE)算法，本文在數(shù)據(jù)庫特定的同步協(xié)議內(nèi)使用PHTM；本文也展示了在多數(shù)事務(wù)對PHTM而言過大的情況下，如何通過STE幫助PHTM獲得更簡單和更快速的解決方案.

1 模 型

本文考慮使用了HTM和NVM的多進(jìn)程異步共享內(nèi)存系統(tǒng).

1.1 內(nèi) 存

本文所考慮的內(nèi)存體系結(jié)構(gòu)在最底層由全NVM內(nèi)存作為主存(如果系統(tǒng)中也包含了DRAM，邏輯內(nèi)存空間一般被分割成持久化和非持久化地址空間，為了簡化問題，本文僅考慮無DRAM的情況).不失一般性，將緩存行定義為數(shù)據(jù)的最小粒度.最底層之上是緩存，包含了主存中緩存行的副本.緩存一致性協(xié)議確保了無論有多少個(gè)緩存副本各處理器都能獲得一致的主存數(shù)據(jù).最高層為寄存器，即每個(gè)處理器內(nèi)部用于暫存數(shù)據(jù)的特殊存儲.

一般而言，在內(nèi)存系統(tǒng)低層中進(jìn)行的操作比高層慢幾個(gè)數(shù)量級.NVM的寫操作比DRAM慢，讀操作速度則至少持平.

數(shù)據(jù)從緩存異步刷新到NVM，這一過程程序員無法感知.數(shù)據(jù)也可以通過硬件原語FLUSH，參數(shù)是內(nèi)存地址，顯式刷新到NVM.FLUSH(addr)操作利用緩存一致性協(xié)議將最新的緩存行副本刷新到主存地址addr.

1.2 故 障

本文將考慮系統(tǒng)掉電后所有易失性內(nèi)存的內(nèi)容丟失的情況，而不考慮其他類型的故障，如進(jìn)程崩潰或拜占庭式故障.所有的緩存和寄存器都是易失性存儲，掉電后僅NVM仍保存著數(shù)據(jù).

掉電后系統(tǒng)通過單個(gè)恢復(fù)進(jìn)程執(zhí)行一系列特殊的恢復(fù)流程.這個(gè)恢復(fù)流程在其他進(jìn)程恢復(fù)運(yùn)行前修復(fù)數(shù)據(jù).由于恢復(fù)進(jìn)程單獨(dú)運(yùn)行，因此具有相當(dāng)大的自由度，可以進(jìn)行危險(xiǎn)操作，例如強(qiáng)制釋放其他進(jìn)程在掉電前已持有的鎖.

1.3 硬件事務(wù)內(nèi)存

考慮英特爾HTM的實(shí)現(xiàn)，進(jìn)程p通過調(diào)用xbegin啟動事務(wù)，若處理器進(jìn)入事務(wù)執(zhí)行模式則xbegin返回OK，否則返回退出原因.在事務(wù)模式下，每一次p對某一地址進(jìn)行讀或?qū)懖僮鲿r(shí)，將該地址加入到該事務(wù)的讀地址集合(read-set)或?qū)懙刂芳?write-set).該事務(wù)的讀地址集合和寫地址集合的并集稱為數(shù)據(jù)地址集合(data-set).若一個(gè)事務(wù)的數(shù)據(jù)地址集合與其他并發(fā)事務(wù)的寫地址集合相交則存在數(shù)據(jù)沖突.HTM系統(tǒng)將中止相互沖突的至少一個(gè)事務(wù).進(jìn)程p也可以通過調(diào)用xabort主動退出當(dāng)前事務(wù)的執(zhí)行.

事務(wù)也會因其他原因而退出執(zhí)行，例如系統(tǒng)調(diào)用、中斷，缺頁中斷或內(nèi)部緩沖區(qū)溢出.特別地，由于事務(wù)存在可訪問內(nèi)存地址數(shù)的限制，超過這一限制將因容量超限而退出.容量超限無法預(yù)測，而且硬件事務(wù)由于數(shù)據(jù)地址集合持續(xù)增長而更容易出現(xiàn)容量超限問題.為避免容量超限而退出事務(wù)執(zhí)行，事務(wù)的數(shù)據(jù)地址集合必須最少滿足如下條件：適合L1緩存的大小、避免緩存的關(guān)聯(lián)沖突、避免將事務(wù)載入的緩存行換出.另外，當(dāng)2個(gè)超線程在同一個(gè)核上運(yùn)行時(shí)，該核的本地緩存由這2個(gè)超線程共享，這使得每一個(gè)線程的L1 緩存容量減半，容量超限退出問題也更嚴(yán)重.

無論何時(shí)進(jìn)程p的事務(wù)T退出時(shí)，p停止該事務(wù)，控制流返回到調(diào)用xbegin之前(事務(wù)啟動前).因此p下一步是調(diào)用xbegin，這一次調(diào)用將返回退出的原因(如沖突、容量超限).這樣xbegin的典型調(diào)用模式為“ifxbegin()=OK then {transaction body} else {abort handler}”.

1.4 增加對NVM的支持

需要指出硬件事務(wù)并不直接修改主存，相反，所有的事務(wù)寫是在緩存中實(shí)施的，所有相關(guān)的緩存行在事務(wù)提交后一個(gè)接一個(gè)地刷入主存.緩存一致性協(xié)議確保了受影響的緩存行將在事務(wù)提交后原子性地刷入主存.但是若在刷入主存過程中發(fā)生了掉電故障，緩存的信息可能會喪失原子性.

避免這種問題的方法之一就是讓每個(gè)事務(wù)在提交前以日志記錄寫操作并刷新到NVM中，以便在恢復(fù)過程中有足夠的信息完成掉電前的任何事務(wù).當(dāng)然，這種方法要求已實(shí)現(xiàn)事務(wù)處理過程中的FLUSH(不中止事務(wù)).在接下來的Avni等人的研究中[3]，我們假定透明刷新(TFLUSH)不會中止事務(wù).此外，既然日志在事務(wù)提交前已刷新到NVM，恢復(fù)進(jìn)程一定能夠檢查掉電前事務(wù)是否已提交.同樣地，類似文獻(xiàn)[3]，我們假定xend通過擴(kuò)展指令在NVM中設(shè)置一個(gè)標(biāo)記位，可以在事務(wù)提交到緩存時(shí)原子性地設(shè)置該比特位并刷新到NVM中.在事務(wù)提交時(shí)原子性地將標(biāo)記位刷新到NVM是對當(dāng)前HTM協(xié)議的最小化修改.

2 持久化HTM

Herlihy和Moss定義了硬件事務(wù)內(nèi)存(HTM)[6]，用于充分利用硬件緩存一致性機(jī)制在多核芯片的可緩存共享內(nèi)存中執(zhí)行原子事務(wù).其基本思想是每一個(gè)事務(wù)都在當(dāng)前核的本地L1緩存中隔離.“原子性”是從數(shù)據(jù)庫系統(tǒng)中借用的概念[7],但是，數(shù)據(jù)庫的事務(wù)與HTM事務(wù)不同，數(shù)據(jù)庫的事務(wù)是持久化的，例如當(dāng)一個(gè)事務(wù)成功提交后也將備份到持久化存儲中.

由于HTM發(fā)展緩慢，大量的相關(guān)研究集中在STM以獲得低開銷和無需硬件輔助的可擴(kuò)展同步事務(wù)內(nèi)存.英特爾公司最早的HTM實(shí)現(xiàn)在2013年上市，同時(shí)STM也已整合進(jìn)GCC編譯器中[8-9].

內(nèi)存技術(shù)的最新進(jìn)展(如PCM，STT-RAM和憶阻器)展示了NVM設(shè)備可以如DRAM一樣高速進(jìn)行字節(jié)尋址，比DRAM節(jié)能，還具有非易失性，并且和HDD一樣便宜.本節(jié)將提出一種通過利用NVM進(jìn)行持久化存儲而非(補(bǔ)充)DRAM的HTM事務(wù)的方法，同時(shí)還能夠保持易失性緩存結(jié)構(gòu).

2.1 相關(guān)研究

Coburn等人[10]提出了一種可與NVM正確工作的軟件事務(wù)內(nèi)存——NV-Heaps.其基本思想遵循DSTM[11]，即事務(wù)對象存儲在NVM中，可以在寫入時(shí)打開，然后STM事務(wù)T將它復(fù)制到撤銷日志(undo log)中并鎖定.T為每個(gè)事務(wù)維護(hù)一個(gè)易失性讀日志和一個(gè)非易失性撤消日志.如果發(fā)生系統(tǒng)故障，則中止T并使用持久化的撤消日志來復(fù)原T所做的改變.

NV-Heaps是基于對象的，而同時(shí)發(fā)表的源自TinySTM[12]的Mnemosyne STM[13]是基于字的，但是這些算法背后的思想都是非易失性撤消日志和易失性讀日志，這是相同的.

雖然正確并且可行，但由于維護(hù)記錄的開銷和鎖的序列化，基于軟件的方法性能較弱.因此，雖然有些數(shù)據(jù)庫實(shí)現(xiàn)使用了HTM進(jìn)行同步[14-15]，但是，這些數(shù)據(jù)庫仍然使用硬盤進(jìn)行持久化.

PMFS[16]使用NVM作為文件系統(tǒng)存儲，文獻(xiàn)[17]使用NVM在OLTP數(shù)據(jù)庫中進(jìn)行持久化. PMFS確實(shí)使用了HTM，但僅用于管理文件系統(tǒng)元數(shù)據(jù)這一特定目的.

2.2 術(shù) 語

非易失性內(nèi)存技術(shù)的已日趨成熟，這必將改變事務(wù)系統(tǒng)的構(gòu)建方式.NVM設(shè)備如DRAM一樣快，同樣可以進(jìn)行字節(jié)尋址，比DRAM更加節(jié)能，還具有非易失性，并且和HDD一樣便宜.因此，非易失性內(nèi)存將消除傳統(tǒng)的多層內(nèi)存體系的分層，這種分層是ACID事務(wù)持久性的保證.在主存中維持失效狀態(tài)可導(dǎo)致系統(tǒng)故障后無法恢復(fù).因此，設(shè)計(jì)故障恢復(fù)(重啟)時(shí)的持久化方案需要一種全新設(shè)計(jì)的、并且考慮周全的方法，這將從NVM中受益.后續(xù)我們將使用如下術(shù)語.

1) HTM.原子性地提交事務(wù)的同步機(jī)制，并保持隔離性.一旦HTM事務(wù)T提交，所有新修改的數(shù)據(jù)都在易失性緩存中.

2) HTM事務(wù)TK.由處理器的核心Pk執(zhí)行的事務(wù).

3) NVM.非易失性，可字節(jié)尋址、可寫的內(nèi)存.

4) 重啟.重新啟動的任務(wù)是使數(shù)據(jù)處于一致性狀態(tài)，消除未提交事務(wù)的影響，并恢復(fù)丟失的已提交事務(wù).

這里考察的硬件模型包括無限的NVM，多核處理器并且無硬盤.所有的NVM都是可緩存的，緩存是易失的并且是一致的.該系統(tǒng)包括有限容量的DRAM.最后，我們使用術(shù)語持久化硬件事務(wù)內(nèi)存(persistent HTM, PHTM)來指代現(xiàn)有HTM實(shí)現(xiàn)的概念，并納入NVM所需的最少硬件和軟件調(diào)整.PHTM系統(tǒng)包括軟件和硬件.

2.3 問題定義

隨著現(xiàn)代硬件中處理器核心數(shù)越來越多，NVM就會越來越難以滿足持久化要求. 一方面，由于數(shù)據(jù)在NVM中，因此不需要為其另外分配一個(gè)持久化存儲器，這減少了持久化的開銷. 但另一方面，向某一地址寫入時(shí)，新值必須以新的、一致的并且持久化的狀態(tài)原子性地對外暴露.保證這種原子性的一個(gè)方案是通過鎖.隨著核心數(shù)量的不斷增加，鎖必將成為瓶頸.實(shí)現(xiàn)免鎖原子性的一種方法是HTM，但HTM無法訪問物理內(nèi)存.這樣，當(dāng)前面臨的主要問題就是填補(bǔ)HTM與NVM之間的差距，并允許應(yīng)用程序在NVM中保持一致和持久的狀態(tài)，而且不加鎖，不復(fù)制數(shù)據(jù).

2.4 數(shù)據(jù)存儲流程

由HTM事務(wù)T寫入的數(shù)據(jù)項(xiàng)x(可尋址的字)的狀態(tài)如圖1所示.請注意，x可能緩存在易失性緩存中，或者只駐留在NVM中(就像任何其他可尋址的字一樣)：

1) PrivateShared.Private表示x只在一個(gè)線程的L1緩存中，對其他線程不可見.當(dāng)x是Shared時(shí)，緩存一致性使其新值對其他線程可見.

2) PersistentVolatile.Persistent意味著x最后寫入的值在NVM中，Volatile表示x的新值在緩存中，并且掉電時(shí)會消失.

3) LoggedClear.當(dāng)x是Logged時(shí)，重啟將從非易失性日志中恢復(fù)x.如果x是Clear，重啟將不會對x執(zhí)行任何操作，因?yàn)椴淮嬖谙嚓P(guān)的記錄.這可能在事務(wù)提交或中止之后發(fā)生.

Fig. 1 State machine for a persistent transactional variable圖1 持久化事務(wù)的狀態(tài)機(jī)

盡管圖1說明了PHTM事務(wù)中單次寫入的狀態(tài)機(jī)，Logged狀態(tài)應(yīng)該是針對整個(gè)事務(wù)的.也就是說，將單個(gè)事務(wù)的所有寫入從Clear轉(zhuǎn)變?yōu)長ogged需要唯一的持久化寫.在PHTM提交中，所有寫入都由HTM暴露，并同時(shí)被記錄下來.每次寫入都必須生成一個(gè)持久化的日志記錄，但是直到成功提交之前，寫入操作不會被重啟進(jìn)程重演.

當(dāng)HTM事務(wù)Tk寫入變量x時(shí)，x在Pk的L1緩存中被標(biāo)記為事務(wù)性的，并且是私有的(Private)，即僅存儲在Pk的緩存中.它是易失(Volatile)的，因?yàn)樗辉诰彺嬷?，而且是未記?Clear)的，即未記錄到日志中，因?yàn)槭聞?wù)還沒有被提交.在中止或掉電故障時(shí)，x的易失(Volatile)私有(Private)值將被丟棄，并將恢復(fù)到先前共享(Shared)和持久(Persistent)值.

在PHTM提交中，x的狀態(tài)改變了2次.首先變成共享的(Shared)，即可見的，同時(shí)也被記錄(Logged)下來.這2次狀態(tài)改變都必須原子性地提交成功.成功提交后，PHTM將x的新值透明刷新到NVM，并清除x.如果系統(tǒng)發(fā)生故障并在x記錄時(shí)重新啟動，則恢復(fù)過程使用x的日志記錄來寫入提交的x值，然后清除x.

NVM中的日志不是典型的順序日志,相反，它僅保留無序的日志記錄，這些日志記錄僅用于正在運(yùn)行的或已提交的事務(wù)，而且尚未回收其日志記錄.

有關(guān)PHTM實(shí)現(xiàn)的詳細(xì)信息，包括衍生硬件以及正確性證明，請參閱Avni等人的文獻(xiàn)[3].

2.5 評 估

本節(jié)使用紅黑樹的數(shù)據(jù)結(jié)構(gòu)和復(fù)合基準(zhǔn)程序測試PHTM的性能.該復(fù)合基準(zhǔn)程序測試PHTM的開銷，以及PHTM和HTM大小限制的相關(guān)性.

測試在英特爾core i7-4770 3.4 GHz Haswell CPU上進(jìn)行測試，共有4個(gè)核心，每核2個(gè)超線程，每個(gè)核心擁有本地L1和L2緩存，大小分別為32 KB 和256 KB，同時(shí)所有核心共享8 MB L3緩存.

2.5.1 硬件仿真

英特爾的Haswell處理器具備用于實(shí)驗(yàn)的HTM特性.但是，NVM和PHTM仍未能在硬件上實(shí)現(xiàn)，所以需要仿真以進(jìn)行評估.我們通過將電源開啟并僅將易失性區(qū)域(如日志標(biāo)記)置零來模擬PHTM中掉電故障的影響.為了模擬tx_end_log，提交記錄在事務(wù)中寫入.由于這是事務(wù)的一部分，所以HTM本身使提交記錄在成功提交的同時(shí)可見.在TF仿真中，根據(jù)預(yù)期的NVM性能，通過加入100 ns的延遲來模擬NVM訪問時(shí)間.本文并未仿真互連流量，因?yàn)檫@個(gè)流量與解決方案中的互連流量(即持久化STM)相同.

2.5.2 對比算法

PHTM與標(biāo)準(zhǔn)HTM、模擬持久化的STM(per-sistent software transactional memory, PSTM)、無持久化的標(biāo)準(zhǔn)STM進(jìn)行了比較.STM來自GCC[8-9]，并使用最低優(yōu)化級別.這是為了使所有4種算法能夠進(jìn)行公平的比較，避免了用以減少訪問次數(shù)的編譯器優(yōu)化.

與PHTM一樣，PSTM在持久化存儲中實(shí)現(xiàn)重演日志.在PSTM中寫入的開銷是提交之前的日志條目的一次刷新和提交之后的一次刷新，因此它與PHTM相當(dāng).PSTM基于Mnemosyne[13]，但有少量修改.本文選擇實(shí)現(xiàn)重演日志和本地?cái)?shù)據(jù)更新，以避免寫懲罰后巨大的讀操作.PHTM相對于STM的優(yōu)勢在于以處理器的速度加載.為了公平比較，PSTM應(yīng)該盡可能快地加載以挑戰(zhàn)PHTM.

PSTM的缺點(diǎn)源自STM，即與指令插樁、鎖和版本相關(guān)的開銷.PHTM的缺點(diǎn)源自HTM，即有限的事務(wù)大小.

2.5.3 性能基準(zhǔn)

本文將在復(fù)合數(shù)組基準(zhǔn)測試中對無爭用條件下的PHTM進(jìn)行性能測試，然后在紅黑樹上測試爭用條件下的性能.檢查的算法包括HTM，PHTM，STM和PSTM.在圖2中，增加了HTM-CAP和PHTM-CAP行來統(tǒng)計(jì)HTM容量超限中止次數(shù)，并增加了HTM-CON以及HTM-CON和PHTM-CON行用以表示一些圖中因沖突而終止的次數(shù).中止次數(shù)通過每秒中止的操作數(shù)進(jìn)行統(tǒng)計(jì).因沖突而中止并在加全局鎖之前需重新嘗試20次，但容量超限中止不會重試并立即加鎖，因?yàn)橹卦嚦晒Φ目赡苄苑浅Ｐ?

2.5.3.1 數(shù)組負(fù)載

在這個(gè)負(fù)載中，所有的事務(wù)都具有相同的訪問次數(shù)以使其執(zhí)行時(shí)間相當(dāng).該測試訪問一組連續(xù)的內(nèi)存地址，所以緩存中無碎片.每個(gè)待訪問地址都在單獨(dú)的緩存行中.

1) 只讀(read-only)

Fig. 2 Synthetic array and a red-black tree benchmarks圖2 數(shù)組和紅黑樹復(fù)合性能結(jié)果

首先觀察PHTM在只讀工作負(fù)載上的性能.這對于PHTM而言是最好的情況，因?yàn)镻HTM以處理器的速度加載.在圖2(a)中，每個(gè)事務(wù)循環(huán)地執(zhí)行512次加載指令到不同數(shù)量的連續(xù)緩存行.可以看到，只要避免HTM容量限制，PHTM和HTM的性能相同，并且比STM和PSTM高一個(gè)數(shù)量級.圖2(a)中的所有測試都在所有8個(gè)硬件線程上執(zhí)行.由于存在超線程，每個(gè)線程的緩存大小是其核心緩存大小的一半，即16 KB或256個(gè)緩存行(每個(gè)緩存行64 B)，所以當(dāng)訪問集大小為512時(shí)，所有的HTM和PHTM事務(wù)都將觸及容量上限并中止退出.在這一點(diǎn)上，HTM和PHTM的性能等同于STM，因?yàn)樗褂昧顺坊?如預(yù)期的那樣，STM和PSTM表現(xiàn)相當(dāng).

2) 只寫(write-only)

這個(gè)測試檢驗(yàn)PHTM的寫入性能.圖2(c)中的性能結(jié)果與圖2(a)中的性能結(jié)果非常接近.每個(gè)事務(wù)循環(huán)地執(zhí)行512次存儲指令到不同數(shù)量的連續(xù)緩存行.

可以看到，HTM性能未受到待訪問緩存行數(shù)量增加的影響，但PHTM接近PSTM的性能，因?yàn)樗⑿碌絅VM的速度決定了性能.必須強(qiáng)調(diào)的是，即使多次寫入緩存行，PHTM和PSTM也只能在事務(wù)中刷新一次緩存行.因此，如果事務(wù)只訪問一個(gè)緩存行，則它將512次寫入相同的緩存行，但僅刷新2次，一次在提交之后刷新數(shù)據(jù)，另一次在提交之前刷新日志.如果將TF置為非阻塞可以減小開銷.

當(dāng)HTM和PHTM事務(wù)開始接近容量上限時(shí)，它們會加全局鎖，雖大大降低性能但可防止事務(wù)繼續(xù)擴(kuò)大.PHTM在標(biāo)準(zhǔn)HTM之前達(dá)到容量限制.這是因?yàn)镻HTM的每次寫入都要寫入一個(gè)日志條目，所以它可以訪問更多的內(nèi)存.此外，日志條目不在連續(xù)內(nèi)存中，所以即使在緩存已滿之前，它們也可能違反緩存關(guān)聯(lián)性.請注意，在一個(gè)真正的實(shí)現(xiàn)中，非事務(wù)性的存儲指令可以被用于日志，并且避免增加事務(wù)占用的空間.

3) 讀寫混合(read-write mix)

在不存在容量超限中止問題的情況下，即在小事務(wù)中，該測試檢查事務(wù)性加載指令與事務(wù)性存儲指令的數(shù)量如何影響PHTM，以及與STM和PSTM相比的性能.

在圖2(e)中，每個(gè)事務(wù)對10個(gè)相互獨(dú)立的緩存行訪問10次，并執(zhí)行不同數(shù)量的寫操作.HTM并未在圖2中展示，因?yàn)樗源笾孪嗤乃俣冗M(jìn)行讀寫.圖2(e)表明直到只讀部分達(dá)到70%，STM都比PHTM快.但是當(dāng)只讀部分達(dá)到90%時(shí)，PHTM已經(jīng)是STM性能的2倍.如圖2(a)所示，當(dāng)只讀部分達(dá)到100%時(shí)，PHTM比STM快12倍.

2.5.3.2 紅黑樹(RB-Tree)負(fù)載

為了評估爭用條件下的PHTM性能，本文使用了一種紅黑樹進(jìn)行基準(zhǔn)測試，所有事務(wù)都使用隨機(jī)鍵值訪問樹進(jìn)行插入、刪除或查找操作.所執(zhí)行的工作負(fù)載運(yùn)行在8個(gè)核上，具有固定的鍵值范圍大小，更新的比例范圍從10%到100%.每棵樹從半滿開始，插入的數(shù)量等于刪除的數(shù)量以維持樹的大小.

第1組測試是在一個(gè)小的1 K個(gè)節(jié)點(diǎn)的樹上執(zhí)行的.如圖2(b)所示，HTM和PHTM沒有因容量超限中止，出現(xiàn)了沖突退出，但可擴(kuò)展性與STM相當(dāng).在這個(gè)測試中，PHTM比PSTM快大約6倍.圖2(d)中的第2組測試是在1 M個(gè)節(jié)點(diǎn)的樹上進(jìn)行的，可以看到出現(xiàn)了容量超限中止，但仍較少.因此，PHTM只比PSTM快40%.盡管沖突中止率很高，但可擴(kuò)展性仍然相同，這表明中止率與STM接近.為了進(jìn)一步增加容量帶來的挑戰(zhàn)，我們原子性地在2個(gè)1 M個(gè)節(jié)點(diǎn)的樹上執(zhí)行相同操作的事務(wù).如圖2(f)所示，容量超限中止數(shù)上升，PHTM的性能下降到和PSTM相當(dāng).

正如預(yù)期的那樣，容量限制是HTM最大的問題，因?yàn)樗鼤仁故聞?wù)序列化，而PHTM性能的最大障礙是它從HTM繼承的容量超限中止.在每個(gè)執(zhí)行的測試中，PHTM在所有爭用水平上與HTM和來自STM的PSTM保持恒定的差異.不同之處在于工作負(fù)載中的寫入部分.樹越小，遍歷它的時(shí)間就越少，所以寫入部分相對增加，并且持久化算法的開銷相應(yīng)增加.

3 持久化混合HTM

在PHyTM中，事務(wù)可以以如下3種路徑執(zhí)行：快速HTM、慢速HTM和STM.每種路徑都提供了一個(gè)操作集用于啟動和提交事務(wù)，以及讀寫內(nèi)存位置.這些操作并非直接由用戶代碼調(diào)用，相反，用戶簡單調(diào)用編譯器提供的操作以啟動和提交事務(wù)，編譯器將通過我們在操作集中提供的操作編譯用戶代碼，自動選擇合適的路徑執(zhí)行事務(wù).

3.1 STM路徑

本文所述STM算法通過遭遇時(shí)序(encounter-time order, ETO)實(shí)現(xiàn)了兩階段鎖.每一個(gè)事務(wù)首先鎖住所有它可能訪問的地址(以首次遭遇的順序)，隨后可以在這些地址上進(jìn)行所需操作，最后釋放所有的鎖.為避免死鎖而使用了try-lock，當(dāng)無法獲取到鎖時(shí)立刻返回false，而非一般的阻塞.當(dāng)一個(gè)進(jìn)程獲取try-lock鎖失敗時(shí)，將釋放其持有的所有鎖并再次嘗試.存在一種罕見的情況；若一個(gè)進(jìn)程獲取鎖時(shí)持續(xù)失敗，該進(jìn)程將鎖住整個(gè)STM路徑.作為try-lock的備選方案，可以使用標(biāo)準(zhǔn)的死鎖檢查算法，但這樣會降低效率，尤其是在非常高競爭的場景下.

2PL和ETO的應(yīng)用使得正確性的條件——不透明性[18]非常容易得以證明，不透明性可直觀表述為進(jìn)程無法觀察到事務(wù)的部分結(jié)果.考慮一個(gè)要寫入一些地址的事務(wù)T，2PL和ETO要求T在訪問地址前鎖住所有這些地址，并持有鎖直到完成寫入.另外，其他任何嘗試讀取這些地址的事務(wù)T′均無法在T解鎖前操作.因此T′無法看到T的任何寫入，直到T的所有操作均已經(jīng)完成.

STM將鎖住事務(wù)欲訪問的所有地址，完成讀操作并將寫操作記錄到日志中，隨后進(jìn)入寫回階段.在寫回階段，事務(wù)將日志刷入NVM，完成所有的寫入操作，隨后將寫入結(jié)果刷入NVM.這種實(shí)現(xiàn)機(jī)制確保了日志刷入NVM的原子性，這使得恢復(fù)進(jìn)程可以在提交時(shí)訪問日志(否則，已提交的事務(wù)可能丟失，未提交的事務(wù)也可能由恢復(fù)進(jìn)程重演).

STM路徑提供了4種操作：用于啟動事務(wù)的STMBegin、用于替換標(biāo)準(zhǔn)內(nèi)存讀的STMRead、用于替換標(biāo)準(zhǔn)寫的STMWrite、用于提交事務(wù)的STMFinalize.

STMBegin操作作為讀者獲取stmLock(若該事務(wù)嘗試次數(shù)未超限)或者作為寫者獲取(如果超限).作為寫者獲取stmLock將阻止其他事務(wù)在STM路徑上運(yùn)行.

STMRead操作首先調(diào)用GetLockAddr(addr)來確定locks中的哪一個(gè)保護(hù)addr；然后調(diào)用TryReadLock(lock)以獲取讀鎖，讀取該地址，并將該地址(addr)保存在它的讀地址集合中.STMWrite操作也需要首先通過調(diào)用GetLockAddr(addr)來確定合適的lock，隨后調(diào)用TryWriteLock以獲取寫鎖.這樣做有2個(gè)目的：這個(gè)鎖授予待寫入地址的排他訪問權(quán)限，并且獨(dú)占地在寫日志(write-log)中存儲該地址.如果執(zhí)行TryWriteLock的進(jìn)程當(dāng)前作為讀者持有鎖，并且沒有其他讀者，則TryWriteLock將讀鎖升級為寫鎖.接下來，STMWrite將addr和val添加到其寫日志條目中.請注意，STMWrite不會顯式刷新這些修改，但可能異步地寫入NVM.如果STMRead或STMWrite無法獲取鎖，則事務(wù)中止，釋放所有鎖并重試事務(wù).

進(jìn)程需要調(diào)用STMFinalize以提交STM事務(wù).STMFinalize首先將寫日志條目刷新到NVM，然后通過調(diào)用numSTMWriteback上的FetchAnd-Increment表示事務(wù)已進(jìn)入寫回階段(將會在3.3節(jié)中看到如何運(yùn)用numSTMWriteback).然后設(shè)置并刷新日志條目中的logged位，這表示日志條目已準(zhǔn)備好，可以在發(fā)生掉電故障時(shí)由恢復(fù)進(jìn)程重演.當(dāng)logged位刷入NVM時(shí)，事務(wù)為committed狀態(tài).接下來，STMFinalize調(diào)用ReplayLogEntry函數(shù)來重演事務(wù)的日志條目，執(zhí)行所有的寫操作并將其刷新到NVM.ReplayLogEntry也會清除并刷新logged位以表明該日志條目不再需要重演.在事務(wù)的所有寫操作完成并刷新后，STMFinalize將取numSTM-Writeback并進(jìn)行減操作，以表明該事務(wù)不再處于寫回階段.最后，STMFinalize解鎖所有的鎖，并準(zhǔn)備其日志條目以供進(jìn)程的下一個(gè)事務(wù)重用.

3.2 慢速HTM路徑

與STM路徑一樣，慢速HTM需要在所有待寫入地址上獲取鎖，隨后在日志中記錄所有的寫，這將保證無法對同一地址重復(fù)記錄寫.但是慢速HTM和STM有2處不同:1)慢速HTM實(shí)際上在記錄到日志之后立刻執(zhí)行寫操作(不需要等待日志重演).這在HTM中可以實(shí)現(xiàn)，因?yàn)樗袑懖僮鞫急Ａ粼谔幚砥鞯乃接芯彺嬷兄钡绞聞?wù)提交.2)慢速HTM在讀取地址時(shí)不會獲取任何鎖，相反，它只是簡單地讀取每個(gè)地址的鎖的狀態(tài).如果當(dāng)前已由寫者鎖定(寫鎖)，則事務(wù)將中止.讀取鎖狀態(tài)意味著HTM事務(wù)將訂閱這把鎖.這樣，如果在事務(wù)首次檢查其狀態(tài)時(shí)為未鎖定狀態(tài)，但在事務(wù)提交前的某個(gè)時(shí)間點(diǎn)被其他進(jìn)程鎖定，則事務(wù)將中止.

慢速HTM訂閱它所讀取的地址的鎖，并鎖定它寫入的地址，記錄和執(zhí)行其寫入，因?yàn)樗i定了要寫入的每個(gè)地址.當(dāng)所有的寫入操作完成后，將其日志刷新到NVM并通過xend原子性執(zhí)行如下操作：提交事務(wù)并將其日志標(biāo)記為已完成，以便恢復(fù)進(jìn)程在發(fā)生掉電故障時(shí)進(jìn)行重演.最后，慢速HTM重演其日志條目，將其所有寫入刷新到NVM，然后清除其日志條目.如果一個(gè)事務(wù)在慢速HTM上失敗了很多次，它將切換到STM路徑.

SlowHTMBegin操作調(diào)用xbegin來啟動硬件事務(wù)，然后判斷是否以事務(wù)模式執(zhí)行(即xbegin返回OK).如果不是，那么跳轉(zhuǎn)到先前的慢速HTM事務(wù)中止時(shí)的代碼行.所以，SlowHTMBegin檢查是否已經(jīng)到達(dá)嘗試次數(shù)上限.如果已到達(dá)嘗試次數(shù)上限，該事務(wù)就切換到STM路徑；否則，SlowHTMBegin再次嘗試在硬件中執(zhí)行.

SlowHTMRead操作讀取待讀取地址的鎖的狀態(tài)，若有其他進(jìn)程作為寫入者獲得鎖中止；否則，SlowHTMRead只是簡單地讀取地址并返回結(jié)果.SlowHTMWrite操作嘗試給一個(gè)地址加寫鎖，如果失敗則退出.該鎖授予對正在寫入的地址的獨(dú)占訪問權(quán)，并且獨(dú)占許可將該地址存儲在寫日志中.如果SlowHTMWrite獲取該鎖，則它將要寫入的地址和值添加到事務(wù)的寫日志條目中.最后執(zhí)行實(shí)際的寫入.

為了在慢速HTM中提交一個(gè)事務(wù)，進(jìn)程還需要調(diào)用SlowHTMFinalize.這會將寫日志條目刷新到NVM中，接下來還需要調(diào)用xend.調(diào)用xend將同時(shí)提交事務(wù)，并設(shè)置和刷新日志條目中的記錄位(表示如果發(fā)生電源故障，日志條目已準(zhǔn)備好由恢復(fù)進(jìn)程重演). 在此之后，SlowHTMFinalize調(diào)用ReplayLogEntry重演自己的日志條目，將寫操作刷新到NVM中.ReplayLogEntry也清除并刷新記錄下的比特位，表明該日志條目不再需要重演(與在STMFinalize中調(diào)用ReplayLogEntry不同，這個(gè)ReplayLogEntry的調(diào)用不需要執(zhí)行事務(wù)的寫操作，因?yàn)樗鼈円呀?jīng)作為硬件事務(wù)的一部分執(zhí)行了).最后，SlowHTMFinalize解鎖所有的鎖，并準(zhǔn)備其日志條目以供進(jìn)程的下一個(gè)事務(wù)重用.

3.3 快速HTM路徑

每個(gè)事務(wù)都以快速HTM開始.快速HTM事務(wù)中的寫入和提交與慢速HTM事務(wù)中的寫入和提交相同.快速HTM事務(wù)的讀取效率更高，因?yàn)樗鼈儾恍枰嗛嗘i來保證事務(wù)處理看到一致的狀態(tài)(即它讀取的地址包含在事務(wù)處理過程中某些時(shí)刻看到的值)，有2個(gè)原因：首先，HTM系統(tǒng)保證慢速HTM上的事務(wù)不會導(dǎo)致快速HTM上的事務(wù)看到不一致的狀態(tài)(反之亦然)；其次，每個(gè)快速HTM事務(wù)首先驗(yàn)證numSTMWriteback是否為零，若非零則中止.正如我們在3.1節(jié)看到的那樣，每當(dāng)一個(gè)STM事務(wù)開始寫回，numSTMWriteback就會增加，并且每當(dāng)一個(gè)STM事務(wù)完成寫回時(shí)遞減.因此，如果T在寫回階段與任何STM事務(wù)并行運(yùn)行，它將中止.因此，F(xiàn)astHTMRead被實(shí)現(xiàn)為一個(gè)簡單的讀取，沒有額外的同步.

最后，我們描述FastHTMBegin.FastHTMBegin首先調(diào)用xbegin，然后驗(yàn)證是否以事務(wù)模式執(zhí)行的.若在事務(wù)模式下執(zhí)行，則FastHTMBegin驗(yàn)證numSTMWriteback是否為零，若非零則中止，然后返回.若非事務(wù)模式，則跳轉(zhuǎn)到之前的快速HTM事務(wù)中止時(shí)的代碼行.所以，F(xiàn)astHTMBegin檢查嘗試次數(shù)是否已經(jīng)到了上限.若已到達(dá)上限，則快速HTM切換到慢速HTM；否則，F(xiàn)astHTMBegin再次嘗試在快速HTM上執(zhí)行事務(wù).

3.4 實(shí)驗(yàn)結(jié)果分析

在本節(jié)中，我們將研究如何使用PHyTM降低各種工作負(fù)載下簡單內(nèi)存數(shù)據(jù)庫的同步成本.

1) 工作負(fù)載

我們實(shí)現(xiàn)了一個(gè)非常簡單的內(nèi)存數(shù)據(jù)庫(very simple IMDB, VSDB)，并用它來運(yùn)行Yahoo!云服務(wù)基準(zhǔn)測試(Yahoo! cloud serving benchmark, YCSB)的一個(gè)子集.本文還使用DBx1000(來自文獻(xiàn)[19]的內(nèi)存數(shù)據(jù)庫實(shí)現(xiàn))研究了TPC-C基準(zhǔn).結(jié)果及其分析可以在文獻(xiàn)[20]中找到.我們簡單的YCSB基準(zhǔn)測試證明了PHyTM的低同步成本，而TPC-C基準(zhǔn)測試則以更復(fù)雜的事務(wù)來說明其性能.

2) 同步方法

我們使用不同的同步方法修改每個(gè)內(nèi)存數(shù)據(jù)庫.在內(nèi)存數(shù)據(jù)庫中，我們增加了對PHyTM和PHTM的支持.在VSDB中，我們實(shí)現(xiàn)了一個(gè)簡單的2PL方案，按照遭遇順序?qū)Ω咚倬彺嫘羞M(jìn)行細(xì)粒度的鎖定.由于我們使用的YCSB工作負(fù)載不會導(dǎo)致死鎖，所以并未實(shí)現(xiàn)2PL的死鎖檢測.DBx1000已經(jīng)將2PL和樂觀并發(fā)控制(OCC)作為同步方法.2PL實(shí)現(xiàn)在行上執(zhí)行細(xì)粒度鎖定，并結(jié)合死鎖檢測.已證明該2PL和OCC實(shí)現(xiàn)是可擴(kuò)展的，在模擬器中模擬了超過一千個(gè)處理器[19].

3) 系統(tǒng)

我們使用帶有4個(gè)核心的Intel i7-4770 3.4 GHz處理器，每個(gè)處理器有2個(gè)超線程.每個(gè)核心都有專用的L1和L2緩存，大小分別為32 KB和256 KB.還有一個(gè)由所有核心共享的8 MB三級緩存.我們使用由硬件提供的HTM并模擬NVM.實(shí)驗(yàn)中線程是固定的，每個(gè)邏輯處理器上運(yùn)行一個(gè)線程.

4) 仿真

我們使用文獻(xiàn)[3]中采用的方法模擬對NVM的支持.原子性分配和對logged位的刷新是通過避免在HTM提交和設(shè)置該位之間的任何模擬電源故障來模擬的.由于預(yù)計(jì)NVM的寫入速度比寫入DRAM要慢，因此我們插入了延遲以模擬寫入NVM的所有同步方法.

5) YCSB

在我們所有的YCSB實(shí)驗(yàn)中，使用了一個(gè)有2 000萬條記錄和1個(gè)單主鍵列的表.執(zhí)行4種類型的事務(wù)：短距離查詢(short range queries, SRQ)、長距離查詢(long range queries, LRQ)、短距離更新(short range updates, SRU)和長距離更新(long range updates, LRU).短(或長)事務(wù)查找表中的16(或256)個(gè)隨機(jī)的鍵.查(或更新)事務(wù)選擇一個(gè)列(或?qū)懭肓?.這些事務(wù)只是簡單地讀取或?qū)懭肓械膬?nèi)容，而不執(zhí)行任何額外的計(jì)算.例如，查詢事務(wù)的SQL代碼可能是“SELECT name FROM customers WHERE id IN(1350,2107，…，571)”.更新事務(wù)的SQL代碼可能是“UPDATE customers SET orders=7 WHERE id=1350; UPDATE customers SET orders=4 WHERE id=2107; …”.所有事務(wù)都是相互獨(dú)立的.也就是說，事務(wù)的行為不依賴于前一個(gè)事務(wù)的結(jié)果.請注意，由于長事務(wù)訪問相當(dāng)多的行，有可能導(dǎo)致容量超限而退出.

6) 結(jié)果

結(jié)果如圖3所示.一般而言，在終止退出較少時(shí)PHyTM的行為與PHTM相似.這是因?yàn)橹灰猄TM路徑上沒有事務(wù)處理，2種算法都沒有讀操作的開銷，寫入NVM的開銷將導(dǎo)致寫操作較多的工作負(fù)載存在性能差異.在寫操作較多的工作負(fù)載中，2PL的性能同樣由寫入NVM的開銷決定.對于基準(zhǔn)測試中的所有算法而言，NVM的寫入開銷是相同的，因此它們在只寫測試中表現(xiàn)出相似的性能，如圖3(c)所示.然而，圖3(b)顯示PHTM和PHyTM的讀速度比2PL快一個(gè)數(shù)量級.

Fig. 3 YCSB workloads for different transaction mixes圖3 YCSB驗(yàn)證結(jié)果

圖3(d)顯示執(zhí)行50%SRQ和50%SRU的YCSB工作負(fù)載.在這種工作負(fù)載中，寫入NVM的開銷比任何算法相關(guān)的性能差異更顯著，所以2PL的性能與PHTM和PHyTM的性能相當(dāng)接近.

HTM最大的缺點(diǎn)是事務(wù)規(guī)模受容量超限中止的限制.PHTM包含有一個(gè)STM回滾路徑以允許完成大型事務(wù)，但是該STM路徑需要進(jìn)行全局鎖定，所以STM路徑上的事務(wù)被序列化.這是嚴(yán)重的性能瓶頸，特別是當(dāng)HTM支持的系統(tǒng)中并發(fā)度越來越高時(shí)(支持?jǐn)?shù)百個(gè)并發(fā)線程).

為了研究部分事務(wù)在硬件中執(zhí)行失敗，接下來必須在軟件路徑中執(zhí)行時(shí)會發(fā)生什么，我們增加了一個(gè)工作負(fù)載，其中包含有不太可能在硬件中提交的大事務(wù).當(dāng)所有事務(wù)都是LRU時(shí)，如圖3(a)，我們可以看到PHTM根本不可擴(kuò)展，而PHyTM與2PL一樣可擴(kuò)展.PHyTM可擴(kuò)展是因?yàn)镾TM事務(wù)可以與其他硬件事務(wù)同時(shí)運(yùn)行.PHyTM在落入軟件路徑前樂觀地嘗試硬件事務(wù)所帶來的開銷并未使得其性能低于2PL的性能(從不中止退出)，即使在這種包含眾多異常中止的工作負(fù)載下也是如此.我們認(rèn)為這是因?yàn)镻HyTM在提交之前避免了對NVM執(zhí)行許多昂貴的寫入刷新操作.這樣，中止退出的事務(wù)避免了這種開銷.

在完全由LRU組成的工作負(fù)載中，PHyTM和2PL實(shí)現(xiàn)的吞吐量大致相同，并且比PHTM高一個(gè)數(shù)量級.在完全由SRQ組成的工作負(fù)載中，PHTM和PHyTM則實(shí)現(xiàn)了大致相同的吞吐量，并且比2PL高一個(gè)數(shù)量級.

當(dāng)少量線程在STM路徑上運(yùn)行事務(wù)，而大多數(shù)線程在HTM中成功提交事務(wù)時(shí)，PHyTM比PHTM和2PL的優(yōu)勢變得明顯.如圖3(e)所示，其中一個(gè)線程正在執(zhí)行LRQ(不太可能在硬件路徑中成功執(zhí)行，通常需落入軟件路徑運(yùn)行)，其他線程執(zhí)行能夠在硬件路徑上成功提交SRQ.在這種情況下，PHyTM比具有8個(gè)線程的競爭對手快一個(gè)數(shù)量級.PHTM的STM路徑執(zhí)行讀取操作時(shí)沒有額外開銷，因此其在處理次數(shù)較少時(shí)比2PL(其必須獲取到鎖)要快得多.但是，由于PHTM的STM路徑需要獲取到全局鎖，因此無法擴(kuò)展.2PL雖然可以通過將PHTM與8個(gè)并發(fā)線程聯(lián)系起來而在此類工作負(fù)載中擴(kuò)展，但是受制于獲取鎖的高昂成本.只要沒有STM 事務(wù)在其寫回階段，PHyTM事務(wù)就可以在快速HTM上運(yùn)行，這樣它們的讀取操作沒有額外開銷.此外，即使存在處于寫回階段的STM事務(wù)，PHyTM事務(wù)也可以在慢速HTM上運(yùn)行，在這種情況下，讀操作可以簡單地讀取鎖的狀態(tài)而不需要獲取到鎖.

為了說明PHyTM減少了多少HTM的同步鎖成本，我們用PHyTM的3種不同版本運(yùn)行了圖3(b)所示的只讀工作負(fù)載.在第1個(gè)版本(鎖方式)中，讀操作在所有路徑上需要獲取鎖(類似STM路徑)；在第2個(gè)版本(檢查方式)，在所有路徑上的讀操作只需檢查鎖的狀態(tài)(就像慢速HTM路徑一樣)；在第3個(gè)版本(非同步方式)，所有路徑上的讀操作都是簡單的不插樁讀(就像快速HTM路徑一樣).這些算法僅適用于只讀工作負(fù)載，結(jié)果如圖3(f)所示，檢查鎖狀態(tài)方式的速度比獲取鎖方式快5倍以上，而且不插樁讀的速度比檢查鎖狀態(tài)的方式快大約20%.

4 分離事務(wù)執(zhí)行

4.1 相關(guān)工作

PHTM承諾更輕量的同步，但是2個(gè)固有的限制使得在數(shù)據(jù)庫中應(yīng)用PHTM面臨巨大挑戰(zhàn).一個(gè)限制是PHTM事務(wù)處理受到L1緩存大小的限制，對于完整的數(shù)據(jù)庫事務(wù)來說L1緩存大小通常太小.另一個(gè)是對沖突的過度反應(yīng)，即使在低爭用水平下有時(shí)也會導(dǎo)致序列化執(zhí)行.

我們將一個(gè)數(shù)據(jù)庫事務(wù)分離為多個(gè)滿足PHTM容量限制的較小塊，這樣不太容易發(fā)生爭用，隨后將它們重組為單個(gè)原子事務(wù)，以降低額外開銷.本文僅介紹利用PHTM的數(shù)據(jù)庫事務(wù)提交.

我們所在的華為數(shù)據(jù)庫實(shí)驗(yàn)室還為并行數(shù)據(jù)庫的新型光纖解決方案的發(fā)展[21]以及實(shí)時(shí)分析型數(shù)據(jù)庫的發(fā)展作出了貢獻(xiàn)[22].

4.2 STE算法

STE由一組并發(fā)工作線程執(zhí)行.每個(gè)工作線程都有一個(gè)唯一的ID(tid)和一個(gè)單調(diào)遞增的本地版本計(jì)數(shù)器(tv).另外還維護(hù)一個(gè)全局的最后提交版本數(shù)組(lca).數(shù)據(jù)庫事務(wù)由tid和tv唯一標(biāo)識.

每個(gè)線程在lca中有一個(gè)槽位，并且在數(shù)據(jù)庫成功提交時(shí)在lca的槽位中寫入tv，即lca[tid]←tv，然后在本地增加tv.一個(gè)數(shù)據(jù)庫行同樣有屬性rid和rv，其值為最后一個(gè)事務(wù)T寫入的tid和tv.如果T未提交，則該行指向到prev的鏈接，即該行的最后提交版本，包括其rid，rv和數(shù)據(jù).如前所述，prev鏈接僅在事務(wù)正在寫入行時(shí)設(shè)置.總的來說，prev鏈接指向數(shù)據(jù)庫事務(wù)T的回退集.

算法1. 驗(yàn)證以及提交或終止.

我們將數(shù)據(jù)庫事務(wù)分離為訪問行進(jìn)行讀取或?qū)懭氲男⌒蚉HTM事務(wù)，并使用另一個(gè)PHTM事務(wù)來執(zhí)行數(shù)據(jù)庫事務(wù)的驗(yàn)證和提交.最后一個(gè)HTM事務(wù)可能會更大，但它是只讀的，直到它最終寫入lca并立即提交.英特爾的HTM正在使用大型布隆過濾器來檢測沖突，同時(shí)允許從L1緩存中清除讀取設(shè)置的條目，而不中止HTM事務(wù)處理.這樣，HTM事務(wù)可以容納非常大的讀取集，并且可以支持大型只讀前綴.

4.3 生效和提交

為了驗(yàn)證讀者看到滿足一致性的結(jié)果，即最后提交的值，我們進(jìn)行了2步驗(yàn)證.如果讀者記錄的此行所記錄的rv和rid不變，與在行⑤中所驗(yàn)證的相同，則讀者看到最后提交的值.第2種情況下當(dāng)前的rv和rid不同于日志中記錄的，但它們代表一個(gè)進(jìn)行中的事務(wù)記錄，而日志中記錄的rv和rid是從prev鏈接的，所以記錄的數(shù)據(jù)仍然是最后提交的版本，在這種情況下讀仍然是有效的.

5 結(jié) 論

我們預(yù)計(jì)未來的系統(tǒng)將使用數(shù)千個(gè)處理器核心和PB級的NVM. 基于鎖的同步以及傳統(tǒng)的基于日志的持久性將在這些系統(tǒng)中引入不可接受的開銷. PHTM是向ACID事務(wù)邁出的第一步，避免鎖定并以面向NVM的方式提供持久性.

最近，數(shù)據(jù)庫已經(jīng)開始棄用磁盤，成為完全的內(nèi)存數(shù)據(jù)庫.高效持久的混合事務(wù)內(nèi)存將使得內(nèi)存數(shù)據(jù)庫能夠從事務(wù)內(nèi)存相關(guān)文獻(xiàn)中積累的研究中受益. 另一種方法是基于PHTM定制的同步協(xié)議，如STE，利用PHTM加速不受限數(shù)據(jù)庫事務(wù).

[1]Dushyanth N, Orion H. Whole-system persistence[J]. ACM SIGARCH Computer Architecture News, 2012: 40(1): 401-410

[2]Intel Corporation. Intel architecture instruction set extensions programming reference[EB/OL]. (2017-04-28)[2017-10-08]. https://software.intel.com/sites/default/files/managed/c5/15/architecture-instruction-set-extensions-programming-reference.pdf

[3]Avni H, Levy E, Mendelson A. Hardware transactions in nonvolatile memory[C] //Proc of the 29th Int Symp on DISC 2015. Berlin. Springer, 2015: 617-630

[4]Karnagel T, Dementiev R, Rajwar R, et al. Improving in-memory database index performance with Intel?transactional synchronization extensions[C] //Proc of the 20th IEEE Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2014: 476-487

[5]Schwalb D, Faust M, Dreseler M, et al. Leveraging non-volatile memory for instant restarts of in-memory database systems[C] //Proc of the 32nd IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2016: 1386-1389

[6]Herlihy M, Moss J E B. Transactional memory: Architectural support for lock-free data structures[J]. ACM Sigarch Computer Architecture News, 1993, 21(2): 289-300

[7]Bernstein P A, Hadzilacos V, Goodman N. Concurrency Control and Recovery in Database Systems[M]. Boston: Addison-Wesley Longman Publishing Co, Inc, 1987

[8]Torvald Riegel. Tm support in the GNU compiler collection[EB/OL]. (2012-02-06)[ 2017-10-08]. http://gcc.gnu.org/wiki/TransactionalMemory

[9]Riegel T. Software Transactional Memory Building Blocks[D]. Dresden: Technische Universit?t Dresden, 2013

[10]Coburn J, Caulfield A M, Akel A, et al. Nv-heaps: Making persistent objects fast and safe with next-generation, non-volatile memories[C] //Proc of the 16th Int Conf on ASPLOS. New York: ACM, 2011: 105-118

[11]Herlihy M, Luchangco V, Moir M, et al, Software transactional memory for dynamic-sized data structures[C] //Proc of the 22nd Annual Symp on Principles of Distributed Computing. New York: ACM, 1993: 92-101

[12]Felber P, Fetzer C, Riegel T. Dynamic performance tuning of word-based software transactional memory[C] //Proc of the 13th ACM SIGPLAN Sym on Principles and Practice of Parallel Programming. New York: ACM, 2008: 237-246

[13]Volos H, Tack A J, Swift M M. Mnemosyne: Lightweight persistent memory[J].ACM SIGARCH Computer Architecture News, 2011, 39(1): 91-104

[14]Leis V, Kemper A, Neumann T. Exploiting hardware transactional memory in main-memory databases[C] //Proc of the 30th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE 2014: 580-591

[15]Wang Zhaoguo, Qian Hao, Li Jinyang, et al. Using restricted transactional memory to build a scalable in-memory database[C] //Proc of the 9th European Conf on Computer Systems. New York: ACM, 2014: 26

[16]Dulloor S R, Kumar S, Keshavamurthy A, et al. System software for persistent memory[C] //Proc of the 9th European Conf on Computer Systems. New York: ACM, 2014: 15:1-15:15

[17]DeBrabant J, Arulraj J, Pavlo A, et al. A prolegomenon on OLTP database systems for non-volatile memory[EB/OL]. (2017-09-01)[2017-10-08]. http://www.adms-conf.org/adms_2014.html

[18]Guerraoui R, Kapalka M. On the correctness of transactional memory[C] //Proc of the 13th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2008: 175-184

[19]Yu X, Bezerra G, Pavlo A, et al. Staring into the abyss: An evaluation of concurrency control with one thousand cores[J]. Proceedings of the VLDB Endowment, 2014, 8(3): 209-220

[20]Brown T, Avni H. Phytm: Persistent hybrid transactional memory[J]. Proceedings of the VLDB Endowment, 2016, 10(4): 409-420

[21]Gasiunas V, Dominguez-Sal D, Acker R, et al. Fiber-based architecture for NFV cloud databases[J]. Proceedings of the VLDB Endowment, 2017, 10(12): 1682-1693

[22]Braun L, Etter T, Gasparis G, et al. Analytics in motion: High performance event-processing AND real-time analytics in the same database[C] //Proc of the 2015 ACM SIGMOD Int Conf. on Management of Data. New York: ACM: 251-264