一種基于時間戳的高擴展性的持久性軟件事務內存

劉超杰 王 芳 鄒曉敏 馮 丹

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

傳統的單核處理器受限于功耗和散熱問題，難以進一步提升運行頻率[1-2].因而多核處理器成為了處理器設計的主流方向[3].為了充分發揮多核處理器的性能，必須編寫并發的程序.然而，編寫正確并且高效的并發程序往往是一件比較困難的事.這是因為在多線程同步方面，目前往往是基于傳統的鎖來實現，比如互斥鎖、自旋鎖和讀寫鎖.粗粒度鎖編程簡單、易實現，但是擴展性不好，無法充分利用多核的性能；細粒度鎖擴展性好，但是往往更難實現，編程時容易出錯且難以調試，并且可能會由于鎖定順序的不同而導致死鎖、優先級反轉以及鎖護送等問題.

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

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

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

為了降低在NVM上編寫并發程序的難度，研究人員提出了持久性事務內存(durable transactional memory, DTM)[21-22]，通過擴展傳統事務內存，即增加持久性的特性，在保證并發正確性的同時又能保證數據的崩潰一致性.目前，針對持久性事務內存已經有很多相關的工作，但是這些工作普遍存在擴展性較差的問題，即隨著線程數量的增加，DTM的性能無法繼續提升甚至會快速下降[22-23].測試發現，導致擴展性差的原因主要有2個：1)中心化的全局邏輯時鐘；2)大量冗余的NVM寫操作.

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

另外，為了保障數據的崩潰一致性，在更新數據時，往往不能直接原地修改，這是因為如果此時發生系統崩潰或者機器掉電，NVM中將會存在部分更新的數據，進而導致數據不一致.通常的做法是先將數據在異地持久化之后再進行修改，由此便引入了大量冗余的NVM寫操作[19,22].由于NVM的寫延遲較高，冗余的寫操作將導致事務的執行時間變長，在事務內存中，更新事務在完成前會一直持有所要修改的數據的鎖，其他訪問該數據的事務因無法獲得鎖而處于等待的狀態，從而造成持久性事務內存較差的擴展性.

本文主要針對持久性事務內存中的全局邏輯時鐘和大量冗余的NVM寫操作問題，設計了高擴展性的線程邏輯時鐘以及緩存行感知的雙版本方法，并實現了一個高性能且高擴展性的持久性軟件事務內存.

本文工作的主要貢獻有3個方面：

1) 針對全局邏輯時鐘的擴展性較差，本文提出線程邏輯時鐘，允許每個線程都擁有一個獨立時鐘，并采用了基于數據驅動的時鐘獲取方法，完全消除了中心化問題，為用戶提供了一個高擴展性的時鐘原語；

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

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

1 相關工作

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

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

Table 1 Optimizations of Durable Transactional Memory表1 不同的持久性事務內存采用的優化方法

1.1 基于硬件輔助的持久性事務內存

為了提升持久性事務內存的性能，可以采用一些硬件輔助的方法，這主要體現在2個方面：1)硬件時鐘；2)硬件事務內存.基于時間戳的持久性事務內存需要一個統一的時鐘來產生獨一無二的時間戳，該時間戳被用作數據的版本號，當執行事務時，可以用該版本號來校驗數據的一致性[25].因此，需要為每個更新事務分配一個時間戳，當更新事務較多時，時間戳的產生速度很可能會成為性能的瓶頸.按照實現方法的不同，時鐘可以分為2種：1)邏輯時鐘[25,30];2)硬件時鐘[31-32].

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

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

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

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

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

1.2 基于單版本/多版本/多副本的持久性事務內存

1) 基于單版本的持久性事務內存

為了保證數據的崩潰一致性，往往不能對數據進行就地更新，這是因為在更新時如果發生系統崩潰或者掉電，將會導致部分更新，并且在系統重啟后也無法恢復到一個一致性的狀態[40-41].為了解決這個問題，之前的工作通常會采用寫前日志的方法來保證數據的崩潰一致性.日志主要分為undo日志和redo日志.

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

2) 基于多版本的持久性事務內存

在事務內存中，多版本的方法經常用來降低更新事務對只讀事務的阻塞，提升其性能.當更新事務正在更新某個數據時，只讀事務是無法對該數據進行讀取的，只能等待或者重試.這是因為更新事務還沒有提交，數據處于一種中間狀態，此時讀取數據將破壞事務的隔離性與原子性.因此，更新事務會阻塞只讀事務的執行，造成只讀事務產生較大的延遲.特別是對于執行時間較長的只讀事務，比如遍歷所有數據的操作，在最壞的情況下，該操作可能一直在重試，從而永遠無法完成.

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

3) 基于多副本的持久性事務內存

經過分析可以發現，無論是undo日志還是redo日志，都存在一些問題.首先，它們都會導致冗余的NVM寫操作.其次，undo日志會引入較多的持久化順序約束；而redo日志由于將數據寫到了異地，在事務中訪問這些未提交的數據時，將會引入數據重定向的問題[22].這些問題都會影響持久性事務內存的性能以及擴展性，為了解決這些問題，一些研究開始使用多副本的方法對其進行優化.

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

2 持久性事務內存擴展性測試

本節通過測試來分析制約基于時間戳的持久性事務內存擴展性的因素.其中，2.1節測試了全局邏輯時鐘的擴展性；2.2節分析了在崩潰一致性保障機制中，冗余的NVM寫操作對持久性事務內存擴展性的制約.

2.1 全局邏輯時鐘

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

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

Fig. 1 The scalability of global logical clock圖1 全局邏輯時鐘的擴展性

TL2是經典的基于全局時間戳的軟件事務內存，借助于TL2算法，本文實現了一個并發的鏈式散列表，并用鏈表來解決沖突.圖2展示了在不同數量的線程下執行插入操作時的吞吐量以及時鐘操作所占的開銷.從中可以發現，隨著線程數量的增加，散列表的吞吐量在達到8個線程便開始緩慢增加(32～40線程出現下降，是因為跨域了NUMA節點)，而全局邏輯時鐘所占的開銷也是越來越大，最高達到了79%.

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

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

2.2 冗余的NVM寫操作

為了保證數據一致性，持久性事務內存通常采用undo日志或redo日志.顯然，兩者都存在大量冗余的NVM寫操作，這主要體現在：為了使數據在崩潰后可以恢復一致性的狀態，需要將數據在異地進行持久化，這種異地的持久化至少增加了1倍的寫操作(對于redo是2倍，因為還要將數據寫回到本地).圖3展示了在使用undo或者redo日志的情況下，基于時間戳的持久性事務內存的吞吐量.這里使用持久性事務內存實現了一個并發且持久性的二叉搜索樹，并用讀寫混合負載(50%讀，50%更新)對其進行測試.由圖3可以發現，不管使用哪種日志，持久性事務內存的擴展性都不是很好，在超過16個線程后，吞吐量便不再有明顯的提升.并且，在達到40個線程時，吞吐量有明顯的下降，這是因為跨越了NUMA節點，導致了遠程內存訪問.

Fig. 3 The throughputs of transactional memory with different logs圖3 不同的日志方法下事務內存的吞吐量

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

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

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

3 高擴展性的線程邏輯時鐘

本文提出了一種線程邏輯時鐘方案：通過允許每個線程都擁有自己的時鐘，消除了全局邏輯時鐘中心化問題；采用數據驅動的時鐘獲取方法，完全消除了緩存爭用的開銷；通過動態擴展起始時鐘，大大降低了事務的終止率.基于這些優化，線程邏輯時鐘擁有了近似于硬件時鐘的性能以及擴展性.

3.1 時間戳的構成

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

Fig. 5 The composition of timestamp under thread logical clock圖5 線程邏輯時鐘下時間戳的構成

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

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

3.2 基于數據驅動的時鐘獲取方法

雖然每個線程的邏輯時鐘只有該線程自己可以修改，但是多個線程的讀操作也會帶來大量的緩存爭用開銷.這是因為根據緩存一致性協議，當一個線程讀取一個變量后，便在自己的緩存里增加了該變量的一個副本，如果有其他線程對該變量進行了修改，那么這個線程里的副本便需要被同步，通常的做法是置為無效狀態.當線程數量增加，這種同步的操作便會帶來大量的開銷.特別是在跨NUMA節點時，這種開銷就會更大，由此嚴重影響了線程邏輯時鐘的擴展性.

為了解決這個問題，需要避免使用全局變量.本文提出的基于數據驅動的時鐘獲取方法源自于一種簡單的觀察：數據的時間戳存儲著線程邏輯時鐘的歷史值.根據3.1節的介紹，時間戳由2部分組成：線程ID和該線程的邏輯時鐘值.當更新事務在提交時，會通過函數new_time獲得獨一無二的時間戳，即提交時間戳，并且該提交時間戳會被寫入到被更新的數據的時間戳屬性中.因此，在數據的時間戳屬性中存儲著所有線程的邏輯時鐘的歷史值.

這里使用了歷史值，是因為并不是所有數據的時間戳都存儲著邏輯時鐘的最新值，根據線程邏輯時鐘的執行流程，只有少量數據存儲著最新值，大部分數據存儲的是時鐘的舊值，即比真正的邏輯時鐘的值要小.使用這些較舊的時鐘值來檢驗數據的一致性是完全可行的，這是因為時鐘值總是單調遞增的，如果事務開始后，其訪問的數據被其他更新事務修改，那么被修改后的數據，其時間戳一定大于任何一個之前產生的舊的時間戳.和TicToc[45]相比，盡管都使用了基于數據驅動的方法，但是本文是為了獲取起始時鐘，而TicToc是通過數據的時間戳信息來計算得到提交時間戳.

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

由更新事務的執行流程來看，基于數據驅動的方法直接從數據的時間戳中獲取起始時鐘，從而避免了訪問全局變量，完全消除了緩存一致性的開銷.但是，從圖6的例子中也可以發現，該方法增加了事務的終止率.可以優化的一點是，當事務完成后，該事務記錄的起始時鐘可以存儲下來，這樣下個事務便可以直接使用上個事務的起始時鐘，從而降低事務的終止率.即使通過這種方法優化后，事務的終止率仍然很高，這是因為基于數據驅動的方法獲取的時鐘值比當前的時鐘值更舊，這意味著在進行數據校驗時更容易失敗.盡管較高的終止率會影響事務的性能，但是和全局邏輯時鐘相比，基于數據驅動的線程邏輯時鐘仍然擁有更好的擴展性.

3.3 動態擴展起始時鐘

基于數據驅動的時鐘獲取方法雖然能夠消除緩存同步的開銷，但所獲取的時鐘值往往偏舊.盡管使用這些偏舊的時鐘值來校驗數據的一致性是完全可行的，但是往往會帶來較高的事務終止率，進而影響事務性能.這是因為事務終止的處理是使用函數sigsetjmp來實現的，在事務開始前，首先調用函數sigsetjmp來保存目前的堆棧環境，如果事務終止，便調用函數siglongjmp跳轉到由前面保存的位置，繼續該事務的執行.這種指令的跳轉不利于CPU流水線的執行，并且對CPU的緩存也不友好，進而影響事務的性能以及擴展性.

為了解決這個問題，本文提出了一種動態擴展起始時鐘的方法.傳統的基于時間戳的事務內存，在事務開始時首先獲得起始時鐘，如果事務不發生終止，那么該時鐘的值在該事務的執行過程中便不會再發生改變.然而，本文發現起始時鐘在一定條件下是可以改變的，該條件是該事務所訪問的數據在事務開始后沒有被其他線程修改.這是因為如果滿足該條件，那么和事務終止后再重新執行所達到的狀態時完全相同的.因此當該條件成立時，將對應的起始時鐘修改為一個更大的值仍然能夠保證數據的一致性，同時避免了事務終止的發生.由于被更新的數據在訪問時都會獲取鎖，所以一定不會被其他事務修改，因此不需要校驗那些更新的數據，只需要對只讀的數據(只讀的數據會保存在集合中，稱為read-set)進行校驗.

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

3.4 線程邏輯時鐘的實現

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

Table 2 Data Members of Transaction Structure表2 事務結構體的主要數據成員

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

線程邏輯時鐘為用戶提供了簡單的API，這些API的形式和全局邏輯時鐘相似，以方便用戶對傳統的時鐘進行替換.使用者可以完全不用了解線程邏輯時鐘的具體實現方法，只需要調用這些API即可，下面將分別介紹這3個API的實現，如算法1所示：

算法1.線程邏輯時鐘偽代碼.

① 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

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

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

為了消除數據崩潰一致性保障過程中的冗余NVM寫操作，本文還提出了一種緩存行感知的雙版本方法.該方法利用真實NVM器件的特性，將2個版本連續存儲，并利用混合內存的架構來提升性能；另外，類似于傳統的多版本，雙版本可以用來提升只讀事務的性能；給出了2種崩潰一致性恢復機制.

4.1 數據存儲格式

緩存行感知的雙版本結合了多副本和多版本的優點，既能夠實現數據的直接更新和避免異地持久化操作，又能夠利用雙版本提升只讀事務的性能.傳統的多版本方案通常使用鏈表存儲多個版本，動態地為新的版本分配空間，并且保證最新的版本被最先訪問到.但是由于鏈表指針訪問的緩存局部性不好，NVM的讀寫延遲比DRAM高，其緩存缺失的開銷也更大，因此緩存行感知的雙版本采用了連續存儲的數據布局方案，如圖7所示：

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

其中lock是該數據的鎖，這里用CAS指令實現了該鎖.標記位new用來指定哪個版本是最新的，new=0表示V0是最新的，new=1表示V1是最新的.之所以使用new而不是直接比較2個版本的時間戳，是為了和線程邏輯時鐘進行集成，因為線程邏輯時鐘的時間戳是無法直接進行比較的，除非擁有相同的線程ID.緊接著存儲的是數據的2個版本V0和V1，并附帶它們的時間戳ts0和ts1.數據是與NVM的緩存行對齊的，由于現有的NVM器件(Intel Optane DCPMM)的緩存行是256 B[48]，因此對于大部分數據結構來說2個版本可以存儲在同一個緩存行中，從而避免了在訪問第2個版本時所引起的緩存行缺失的開銷.當然，這種提前為多版本分配存儲空間的做法對存儲空間造成了浪費，一種可行的方法是針對那些不經常更新的數據，仍采用單版本方法進行存儲，因為那些只讀的數據是不會從緩存行感知的雙版本中得到性能提升的.

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

為了降低NVM較高的寫延遲對事務內存擴展性的影響，緩存行感知的雙版本還充分利用了混合內存的優勢.目前，NVM的讀寫延遲和DRAM相比仍然有比較大的差距，很難在短時間內取代DRAM，在未來較長時間內，NVM和DRAM共存于計算機系統將成為一種常態.因此，可以利用DRAM來提升持久性事務內存的性能，本文設計了一種基于混合內存的存儲架構，數據完全存儲在NVM中以保證持久性，將事務在執行時臨時產生的數據存儲在DRAM中，因為這些臨時的數據不需要進行持久化，如果發生崩潰，不需要對它們進行恢復.

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

4.2 基于雙版本的只讀事務優化

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

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

4.3 崩潰恢復機制

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

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

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

4.4 緩存行感知的雙版本的實現

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

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

用戶通過OpenWithRead和OpenWithWrite來對數據進行讀寫[5]，本節將重點介紹這2個函數的實現，如算法2所示.

Fig. 8 The architecture of SDTM圖8 SDTM架構圖

算法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在讀取數據時會首先嘗試較新的版本，當較新的版本不滿足條件時再嘗試較舊的，如果仍然不滿足，便會終止并重試.在函數Open-WithRead中，當把數據拷貝到DRAM后，需要對數據的有效性再次進行檢查，如算法2中的⑥所示.這是因為在拷貝數據的過程中，數據可能已經被其他事務修改.和OpenWithRead不同的是，Open-WithWrite需要獲取鎖，這里使用了CAS指令來執行加鎖操作.需要注意的是，在獲取鎖后lock的值應該指向較舊的版本，這是因為根據緩存行感知的雙版本的更新邏輯，較舊的版本會被直接覆蓋.在獲取鎖成功并且時間戳檢查通過后，調用CopyToDram來將較新的版本拷貝到DRAM中，以后在該事務中對于該數據的訪問將直接重定向到DRAM中.

5 可擴展的持久性軟件事務內存SDTM

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

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

算法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

/*用戶不可直接調用*/

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

6 實驗與結果

6.1 實驗環境與內容

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

Table 4 The Configuration of Server表4 服務器配置信息

測試共分為2個部分，分別是并發數據結構測試和真實負載測試.在并發數據結構的測試中，本文基于SDTM實現了3種并發且持久性的數據結構，包括散列表、二叉搜索樹、有序鏈表，并使用了不同比例的讀寫負載對其擴展性進行了測試.之所以選擇3種不同的數據結構，是因為這些數據結構的競爭情況不同.散列表的沖突較少，因此競爭較小；而有序鏈表的沖突較多，因此競爭最大.這樣，可以測試出SDTM在不同競爭情況下的性能與擴展性.在真實負載的測試中，本文基于SDTM實現了一個B+樹，并使用YSCB[51]提供的典型負載對其進行了詳細的測試，以此來驗證SDTM在真實負載下的效果.

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

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

6.2 并發持久性數據結構測試

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

1) 散列表

本實驗將散列表的初始大小設為1萬個桶，并使用鏈表解決沖突.對于所有測試，預先往散列表中插入1萬個鍵值對，再執行工作負載.由于散列表被設置的較大，并且現有的散列函數能很好地將數據均勻分布，因此發生沖突的概率很小，具有很好的擴展性.

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

2) 二叉搜索樹

二叉搜索樹和散列表相比存在較多的競爭，這是因為對于樹的訪問，都是從根節點開始的，如果中間節點發生改變，那么路過該中間節點的事務都會受到影響.同樣，在測試前，在二叉搜索樹中插入1萬個鍵值對來進行初始化，然后分別運行這3種不同類型的負載，結果如圖10所示:

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

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

3) 有序鏈表

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

圖11展示了在不同負載下不同事務內存的擴展性以及終止率的測試結果.有意思的是，當只有一個線程時，PMDK擁有最好的性能.這是因為PMDK采用的是undo日志，當以只讀的方式訪問有序鏈表中的某個節點時，可以直接對其進行讀取，不需要像SDTM和DudeTM那樣將數據拷貝到另一個地方(DRAM)，這種內存拷貝會占據大量的開銷.但是，隨著線程數量的增加，PMDK中的讀寫鎖成為了擴展性的瓶頸，因為即使對于只讀事務，也需要加鎖.因此，在讀為主和讀密集的負載下，SDTM總體上保持著最好的擴展性，但是在寫密集的負載下，PMDK展現了最好的性能.這是因為，從對應的終止率中可以看出，SDTM和DudeTM在寫密集負載下的終止率較高，這時采用讀寫鎖來進行并發控制往往能夠收獲更好的性能.

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

6.3 真實負載測試

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

為了驗證SDTM在真實負載下的效果，基于SDTM，本文實現了一個并發且持久性的B+樹，并使用YCSB性能測試工具集生成A～D共4個工作負載，請求的分布模式為傾斜分布.其中，load操作的數量為100萬，run操作的數量為1 000萬.圖12展示了4種YCSB負載下不同持久性事務內存實現的B+樹的性能.從測試結果來看，不管是基于哪種負載，SDTM都擁有最好的擴展性與性能，最高時SDTM的吞吐量是DudeTM的2.8倍，是PMDK的29倍.注意，在負載B,C,D中，當線程數由32增加到40時，可以看到SDTM和DudeTM的性能有明顯的下降，這是因為存在跨越NUMA節點的訪問，其開銷影響了事務內存的性能.PMDK的性能沒有太大變化，是因為其性能主要受到讀寫鎖開銷的制約.

7 總 結

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

作者貢獻聲明：劉超杰負責編寫代碼、做實驗、撰寫論文；王芳負責修改和指導論文；鄒曉敏負責修改論文；馮丹負責指導論文.