1、計(jì)算機(jī)硬件性能的提升正在推動著內(nèi)存計(jì)算的發(fā)展:一方面，內(nèi)存容量的不斷增長使得傳統(tǒng)應(yīng)用可以將數(shù)據(jù)存儲在內(nèi)存中進(jìn)行處理，從而顯著地提高了系統(tǒng)性能;另一方面，多核平臺中處理器核數(shù)量的不斷增長為內(nèi)存計(jì)算提供了強(qiáng)大的處理能力。然而，內(nèi)存計(jì)算也面臨著新的挑戰(zhàn):一方面，由于系統(tǒng)瓶頸從I/O向CPU與內(nèi)存轉(zhuǎn)變，如何設(shè)計(jì)高可擴(kuò)展的內(nèi)存計(jì)算系統(tǒng)以充分利用大規(guī)模內(nèi)存與處理器核，成為內(nèi)存計(jì)算的一個重要問題;另一方面，內(nèi)存的易失性也使得如何提供高效的系統(tǒng)可靠性變

2、得更加重要。
　　實(shí)現(xiàn)高可擴(kuò)展內(nèi)存計(jì)算系統(tǒng)的難點(diǎn)在于提供共享資源的并發(fā)訪問。傳統(tǒng)的優(yōu)化方法主要使用基于細(xì)粒度鎖或原子指令等方式實(shí)現(xiàn)對共享資源并發(fā)訪問的保護(hù)，但是這種方法一方面增加了系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的復(fù)雜度，使得系統(tǒng)的正確性難以保證，另一方面過于保守的同步策略也限制了可能的并行性。此外，在內(nèi)存計(jì)算系統(tǒng)中增加高可靠性的需求進(jìn)一步限制了系統(tǒng)的性能與可擴(kuò)展性。
　　硬件事務(wù)內(nèi)存(Hardware Transactional Memor

3、y，HTM)的出現(xiàn)與商用化為構(gòu)建高可擴(kuò)展、高可靠內(nèi)存計(jì)算系統(tǒng)提供了新的思路。然而，硬件事務(wù)內(nèi)存由于工藝設(shè)計(jì)的限制，存在較多的受限性，因而被稱為受限事務(wù)內(nèi)存(RestrictedTransactional Memory，RTM)。典型的受限性包括可容納的工作集較小從而不能容納內(nèi)存計(jì)算中的大數(shù)據(jù)集、硬件事務(wù)執(zhí)行中不能發(fā)生中斷從而不能支持較長時間的內(nèi)存計(jì)算事務(wù)等。此外，硬件事務(wù)內(nèi)存還缺乏持久化存儲的支持，因而宕機(jī)時不能保證系統(tǒng)狀態(tài)的一致性。<

4、br>　　本文圍繞如何基于硬件事務(wù)內(nèi)存設(shè)計(jì)高可擴(kuò)展的內(nèi)存計(jì)算系統(tǒng)開展研究，系統(tǒng)地研究了當(dāng)前商用硬件事務(wù)內(nèi)存的特征，并在此基礎(chǔ)上從多個層面對內(nèi)存計(jì)算系統(tǒng)的可擴(kuò)展性展開研究:1）數(shù)據(jù)存儲層:基于RTM構(gòu)建高可擴(kuò)展內(nèi)存鍵值存儲系統(tǒng)，提供對非結(jié)構(gòu)化數(shù)據(jù)的高效存儲和訪問;2）數(shù)據(jù)庫層:基于RTM構(gòu)建高可擴(kuò)展內(nèi)存數(shù)據(jù)庫管理系統(tǒng)，提供結(jié)構(gòu)化數(shù)據(jù)的存儲和事務(wù)性處理;3）并發(fā)控制層:提出基于事務(wù)切分和RTM的并發(fā)控制機(jī)制，用于保證并行事務(wù)計(jì)算的正確性和可

5、擴(kuò)展性;4）硬件層:提出基于非易失性存儲器的可持久化硬件事務(wù)內(nèi)存技術(shù)，為內(nèi)存計(jì)算存儲系統(tǒng)提供高可靠性支持。
　　具體而言，本文的具體貢獻(xiàn)如下:
　　1.提出基于RTM構(gòu)造可擴(kuò)展并行數(shù)據(jù)結(jié)構(gòu)的方法，在此基礎(chǔ)上構(gòu)造高可擴(kuò)展內(nèi)存鍵值存儲系統(tǒng)。針對RTM硬件限制和特性，使用內(nèi)存預(yù)分配、編譯調(diào)優(yōu)和緩存行對齊等技術(shù)構(gòu)建多種高可擴(kuò)展并行數(shù)據(jù)結(jié)構(gòu)（B+樹、跳表、散列表和布谷鳥散列表），以支持對鍵值存儲的有序/無序訪問。實(shí)驗(yàn)顯示，基于RTM構(gòu)

6、建的有序鍵值存儲系統(tǒng)相比已知最快有序鍵值存儲系統(tǒng)Masstree有10％的性能提升。
　　2.提出基于RTM的樂觀并發(fā)控制(Optimistic Concurrency Control)算法，在此基礎(chǔ)上構(gòu)造高可擴(kuò)展內(nèi)存數(shù)據(jù)庫。針對RTM的硬件限制和特性，使用基于序列號的沖突檢測、待更新數(shù)據(jù)預(yù)查找以及基于內(nèi)存引用置換的事務(wù)提交等方法設(shè)計(jì)并實(shí)現(xiàn)高可擴(kuò)展的樂觀并發(fā)控制機(jī)制，在此基礎(chǔ)上構(gòu)建了高可擴(kuò)展內(nèi)存數(shù)據(jù)庫管理系統(tǒng)。該系統(tǒng)還提供了基于R

7、TM的數(shù)據(jù)庫快照機(jī)制、基于重做日志的可擴(kuò)展持久化機(jī)制以及基于靜息狀態(tài)(quiescentstate)的垃圾回收機(jī)制等。實(shí)驗(yàn)顯示，該系統(tǒng)在具有四個處理核的測試平臺上可以達(dá)到每秒處理50萬個事務(wù)請求的吞吐量，比已知最快內(nèi)存數(shù)據(jù)庫Silo有60％的性能提升。
　　3.提出基于交錯限制(Interleaving Constrained)的事務(wù)切分(TransactionChoping)算法，結(jié)合事務(wù)切分和RTM構(gòu)建高可擴(kuò)展并發(fā)控制機(jī)制。通

8、過限制事務(wù)并行執(zhí)行時的交錯順序，支持對事務(wù)的任意粒度切分并保證事務(wù)執(zhí)行的可串行性(Serializability)語義。使用RTM對關(guān)鍵事務(wù)片段的保護(hù)，保證事務(wù)的原子性和一致性語義。實(shí)驗(yàn)表明，相比于傳統(tǒng)樂觀并發(fā)控制機(jī)制和階段鎖(2-Phase Locking)并發(fā)控制機(jī)制，該機(jī)制有30％以上性能提升;即使在并行訪問沖突嚴(yán)重的情況下，該并發(fā)控制機(jī)制仍具有高可擴(kuò)展性。
　　4.提出基于非易失性存儲器的可持久化硬件事務(wù)內(nèi)存技術(shù)，為內(nèi)存計(jì)