多核結(jié)構(gòu)上軟件事務(wù)存儲的研究.pdf

1、針對計算資源日益增加的需求，單純提高處理器主頻的方式，已經(jīng)不再能夠提升計算機(jī)的性能了。因此，工業(yè)界引入了“多核”的概念，即在一個芯片上集成兩個或多個獨立的處理器，處理器之間共享內(nèi)存。在多核系統(tǒng)中，同樣的時鐘頻率，由于片上處理器個數(shù)的增加，每秒鐘執(zhí)行的指令數(shù)也隨著翻倍，這為解決處理器性能的瓶頸問題提供了新的思路。與此同時，多核系統(tǒng)也給并行處理提出了新的問題，如何能夠更好地利用多核的資源對程序進(jìn)行并行處理，成為當(dāng)今并行處理方面研究的一個熱點

2、方向。
　　事務(wù)的概念來源于數(shù)據(jù)庫，實踐證明了其是一種有效的并發(fā)控制手段。因此，將事務(wù)引入并行程序設(shè)計領(lǐng)域，形成了事務(wù)存儲的理論。事務(wù)存儲中的事務(wù)，指的是被某個線程執(zhí)行的對內(nèi)存的一系列有序讀寫操作序列。這些序列或者全部被執(zhí)行并提交，或者一個也不執(zhí)行并恢復(fù)到執(zhí)行該序列之前的狀態(tài)。本文首先對現(xiàn)有的各類事務(wù)存儲系統(tǒng)進(jìn)行了分析，重點研究了基于Signature數(shù)據(jù)結(jié)構(gòu)的軟件事務(wù)存儲系統(tǒng)。然后針對軟件事務(wù)存儲系統(tǒng)中的三大基本功能分別進(jìn)行了研

3、究，提出了新的優(yōu)化方案，并對這些方案進(jìn)行了仿真實驗。最后，將改進(jìn)后的功能整合起來構(gòu)成一個基于Signature的軟件事務(wù)存儲系統(tǒng)。本文的主要研究成果如下：
　　(1)在研究了沖突檢測算法VHB的基礎(chǔ)之上，提出了一種基于Signature的新的沖突檢測算法VHTB。該算法不但對Signature的行與行之間進(jìn)行動態(tài)變換，而且對地址數(shù)據(jù)相對較少的情況采用了尚未使用的存儲空間來存儲哈希函數(shù)的True Bloom映射信息。這種并行實現(xiàn)的方

4、式既可以對塊內(nèi)的行與行之間進(jìn)行并行搜索，降低延時，同時也可以降低誤判率。經(jīng)實驗測試VHTB算法的誤判率和中止率較VHB算法有了明顯的降低。
　　(2) True Bloom和Hash Bloom是事務(wù)存儲中常用的沖突檢測算法，而這兩種算法各有其特點，在此基礎(chǔ)之上將Signature區(qū)域劃分為兩個區(qū)域，對其中一個區(qū)域進(jìn)行TrueBloom映射，對另一個區(qū)域進(jìn)行Hash Bloom映射，由此提出了一種沖突檢測算法MixBloom。實驗

5、證明該算法較Hash Bloom算法有著較低的誤判率和中止率。
　　(3)針對軟件事務(wù)存儲中數(shù)據(jù)版本管理的問題，提出了一種結(jié)合急切版本管理和惰性版本管理于一身的混合數(shù)據(jù)版本管理機(jī)制。在該機(jī)制中，混合數(shù)據(jù)版本管理器能夠根據(jù)沖突的數(shù)量進(jìn)行動態(tài)地雙向切換，從而選取最適合當(dāng)前狀態(tài)的數(shù)據(jù)版本管理策略。實驗證明混合數(shù)據(jù)版本管理策略在整體上取得了較好的性能，達(dá)到了預(yù)期的效果。
　　(4)在現(xiàn)有的沖突解決策略的基礎(chǔ)上，結(jié)合各個沖突解決策略的

6、優(yōu)點，提出了一種沖突解決策略Synthesized。該策略綜合了若干因素，包括Polite的隨機(jī)指數(shù)回退、Karma的優(yōu)先級、Eruption的繼承優(yōu)先級以及Justice的權(quán)重等，形成一個綜合的沖突解決策略。實驗證明了該沖突解決策略與現(xiàn)有策略相比，有較高的事務(wù)提交數(shù)量。
　　(5) Rochester STM是一種常用的軟件事務(wù)存儲系統(tǒng)，該系統(tǒng)僅采用單一沖突解決策略來處理沖突。為解決這一問題，提出了一種復(fù)合型沖突解決策略Comp

7、rehensive。該策略在兩個事務(wù)發(fā)生沖突時根據(jù)兩個事務(wù)的丟棄成本、嘗試次數(shù)以及起始時間等因素來決定丟棄哪個事務(wù)。實驗證明了該沖突解決策略性能較其他沖突解決策略有顯著的提高。
　　(6)設(shè)計并實現(xiàn)了一個支持多種基于Signature的沖突檢測算法的事務(wù)存儲系統(tǒng)RingSS(Ring Support Signature)，并在RingSS中對本文中提出的改進(jìn)策略進(jìn)行了評測。結(jié)果表明，在該事務(wù)存儲系統(tǒng)中，通過使用新的策略，使系統(tǒng)的性