事務(wù)存儲結(jié)構(gòu)的實(shí)現(xiàn)

1、事務(wù)存儲構(gòu)造的實(shí)現(xiàn)摘要多核處理技術(shù)將成為計(jì)算機(jī)的主流技術(shù)，基于多核開發(fā)線程級并行已至關(guān)重要，事務(wù)的引入可以解決目前線程所不能完成的功能，同時(shí)可以簡化編程模型，事務(wù)存儲能很好地實(shí)現(xiàn)事務(wù)特性。本文首先介紹了T的根本原理，接著分析了目前主流T系統(tǒng)LgT，著重于數(shù)據(jù)版本管理和沖突管理機(jī)制的實(shí)現(xiàn)，進(jìn)而將此系統(tǒng)的優(yōu)越性展現(xiàn)出來。最后對本文進(jìn)展了總結(jié)和展望。關(guān)鍵詞事務(wù)存儲；日志事務(wù)存儲；體系構(gòu)造；操作系統(tǒng)隨著多核處理器技術(shù)的不斷更新和開展，傳統(tǒng)的串行程序不管在效率上還是性能上都已經(jīng)跟不上信息高速開展的腳步了，程序員不得不開發(fā)線程級并行以進(jìn)步片上計(jì)算資源的使用效率，但也帶來了新的挑戰(zhàn)和問題。目前不同線程間的同

2、步、對共享資源的訪問等都是通過鎖和信號量機(jī)制完成的。然而，這種傳統(tǒng)的基于鎖和信號量的并發(fā)系統(tǒng)存在明顯的局限性。粗粒度的鎖對大量的共享數(shù)據(jù)做了保護(hù)，但是可擴(kuò)展性不好，因?yàn)榧词乖诰€程間不存在對共享數(shù)據(jù)的訪問的情況下也可能會出現(xiàn)沖突阻塞現(xiàn)象；細(xì)粒度的鎖雖然比粗粒度的鎖擴(kuò)展性能好，但由于算法設(shè)計(jì)的復(fù)雜性，普通程序員很難借助細(xì)力度的鎖實(shí)現(xiàn)高效的應(yīng)用。同時(shí)使用鎖機(jī)制還會帶來諸多問題，比方：死鎖、優(yōu)先級反轉(zhuǎn)等，極大地影響了并行應(yīng)用的效率和性能。事務(wù)存儲(Transatinalery，T)的使用是解決上述存在問題一個(gè)很好的方法1。通過將不同并行執(zhí)行的線程事務(wù)化，用事務(wù)操作來代替鎖機(jī)制能降低編程的復(fù)雜性。事務(wù)是

3、被單線程執(zhí)行的對內(nèi)存進(jìn)展讀寫的有序操作序列，其特性包括：原子性、隔離性、一致性和持久性。通常事務(wù)的執(zhí)行過程為：調(diào)用事務(wù)入口函數(shù)(begin_transatin)開場執(zhí)行事務(wù)，當(dāng)事務(wù)執(zhí)行完畢后調(diào)用提交函數(shù)(it_transatin)開場提交工作，提交過程分為三個(gè)階段(懇求提交、開場提交和完成提交)，執(zhí)行完提交后此事務(wù)也就執(zhí)行完畢，從而繼續(xù)執(zhí)行下面的事務(wù)。但假如事務(wù)在執(zhí)行或提交過程中發(fā)生沖突或者錯(cuò)誤，那么通過其特有的回滾機(jī)制(rllbak)返回到此事務(wù)入口繼續(xù)執(zhí)行。事務(wù)的執(zhí)行流程圖如圖1所示。圖1事務(wù)執(zhí)行流程為了實(shí)現(xiàn)事務(wù)的這些特性，需有一個(gè)很好的T系統(tǒng)來支持事務(wù)數(shù)據(jù)的版本管理(Versinanag

4、eent)和事務(wù)的沖突管理(ntentinanageent)。版本管理同時(shí)對新值(事務(wù)提交后可見)和原始的舊值(事務(wù)執(zhí)行過程中發(fā)生了回滾的恢復(fù)數(shù)據(jù))進(jìn)展管理。根據(jù)數(shù)據(jù)存放方式的不同T系統(tǒng)區(qū)分版本管理為：積極版本管理(EagerVersinanageent)和懶惰版本管理(LazyVersinanageent)。積極版本管理是將新值置于目的存儲區(qū)中，這樣在提交時(shí)新值可以很快的得到執(zhí)行，極大地降低了提交的時(shí)延；而懶惰版本管理是將原始的舊值置于目的存儲區(qū)，雖然會增加提交的延時(shí)但是降低了當(dāng)事務(wù)發(fā)生回滾后執(zhí)行的延時(shí)。沖突管理是不同事務(wù)執(zhí)行過程中對共享資源訪問引發(fā)沖突而進(jìn)展的沖突檢測以及管理的機(jī)制。沖突管

5、理有積極的(Eager)和懶惰的(Lazy)兩種策略，假如沖突在讀數(shù)據(jù)或?qū)憯?shù)據(jù)時(shí)立即被發(fā)現(xiàn)而進(jìn)展仲裁，這種沖突檢測是積極的；假如沖突是在事務(wù)進(jìn)展提交時(shí)才發(fā)現(xiàn)并仲裁的，這種沖突檢測那么是懶惰的。目前，基于T的硬件構(gòu)造有很多種，圖2中列出了目前幾種流行的硬件構(gòu)造根據(jù)版本管理和沖突管理而進(jìn)展的分類。本文將介紹其中的一種構(gòu)造LgT(日志事務(wù)存儲)，通過對其硬件構(gòu)造參見圖3、版本管理、沖突管理的實(shí)現(xiàn)，展現(xiàn)了此構(gòu)造的優(yōu)越性，并給后續(xù)研究提供參考和幫助。圖2T系統(tǒng)分類LgT是建立在多機(jī)系統(tǒng)中基于日志的T實(shí)現(xiàn)，每個(gè)核都有單獨(dú)的私有ahe，并通過目錄協(xié)議來維持?jǐn)?shù)據(jù)的一致性。它采用的是積極的版本管理策略和積極的沖

6、突管理策略。圖3給出了LgT的硬件構(gòu)造，它通過增加一些存放器和ahe中的讀/寫位很好地完成了對事務(wù)的操作。圖3LgT的硬件構(gòu)造(圖中黑框中為其特有構(gòu)造)2.1版本管理(Versinanageent)LgT使用積極的版本管理，將新的執(zhí)行數(shù)據(jù)存儲在目的區(qū)域(目的地址)中，而將舊的數(shù)據(jù)存儲在其它緩沖區(qū)。它通過在內(nèi)存中開拓一塊事務(wù)日志區(qū)域存儲事務(wù)執(zhí)行過程中被修改的數(shù)據(jù)(上文中提到的原始數(shù)據(jù))和這些數(shù)據(jù)所對應(yīng)的地址，新的執(zhí)行數(shù)據(jù)那么被保存在目的存儲區(qū)(目的地址)，當(dāng)執(zhí)行完成提交時(shí)，這些新數(shù)據(jù)將會立即生效；當(dāng)事務(wù)執(zhí)行過程中或提交時(shí)發(fā)生沖突或錯(cuò)誤需要回滾時(shí)，那么通過事務(wù)日志中記錄的信息恢復(fù)出事務(wù)執(zhí)行前的初始

7、狀態(tài)。剛開場創(chuàng)立線程時(shí)，每一個(gè)線程對應(yīng)著一個(gè)日志而且為日志分配一塊虛擬存儲區(qū)域，并將該日志基地址寫入LgBase存放器，當(dāng)舊數(shù)據(jù)需要存儲到日志時(shí)，LgT通過LgBase存放器中的值定位到日志的入口然后將舊數(shù)據(jù)的虛擬地址和值一同保存在日志中以便恢復(fù)時(shí)使用。為了減少冗余日志，LgT為每一個(gè)ahe塊添加了對應(yīng)的寫()位，用此來標(biāo)識該ahe塊在日志中的記錄情況。當(dāng)事務(wù)提交成功后，LgT將對應(yīng)ahe塊的寫()標(biāo)志位清0并將LgPinter(日志指針)重新指向日志的入口處，以便處理后續(xù)事務(wù)。LgT也為每個(gè)ahe塊設(shè)置了一個(gè)讀(R)標(biāo)志位，就像上面我們討論的寫()標(biāo)志位一樣。在每個(gè)事務(wù)操作過程中LgT同樣將

8、讀標(biāo)志位設(shè)置用于表示讀操作的執(zhí)行(如圖4所示)，而且在事務(wù)完畢后，讀標(biāo)志位也清0。這種積極的版本管理形式的缺點(diǎn)就是在事務(wù)發(fā)生沖突或錯(cuò)誤需要回滾時(shí)執(zhí)行比擬慢，在回滾時(shí)，LgT為了完成恢復(fù)必須將原始數(shù)據(jù)從日志中讀到適宜的目的地址中然后重置寫()位，同時(shí)因?yàn)橛泻芏鄶?shù)據(jù)記錄在日志中，所以恢復(fù)過程必須按照由后向前(后進(jìn)先出)的順序進(jìn)展。但在事務(wù)沖突比擬少的情況下，這種形式可以帶來高效的執(zhí)行效率。為了能更好的理解LgT版本管理過程，圖4通過一個(gè)例子進(jìn)展了很好的分析。(1)事務(wù)執(zhí)行開場前的狀態(tài)ahe數(shù)據(jù)塊中存放著原始數(shù)據(jù)，每塊的讀(R)、寫()位置0，LgBase(日志基址存放器)指向日志入口地址，LgPt

9、r(日志偏移指針)指向日志入口地址同時(shí)Tunt(事務(wù)計(jì)數(shù)器)置1代表正準(zhǔn)備執(zhí)行一個(gè)事務(wù)。(2)讀00地址(十六進(jìn)制地址)中的數(shù)據(jù)到存放器r1中，00地址對應(yīng)數(shù)據(jù)塊的讀(R)標(biāo)志位置1表示此數(shù)據(jù)被讀。(3)將存放器r2中數(shù)據(jù)(這里假設(shè)為56)存入0地址中，由于0地址中存在原始數(shù)據(jù)34，將0地址和該原始數(shù)據(jù)一起根據(jù)LgBase中的日志入口地址存入日志中，并將LgPtr指針后移，指向用于存放下個(gè)數(shù)據(jù)的地址位，同時(shí)將0地址對應(yīng)塊的寫()標(biāo)志位置1，代表一次寫操作的完成，其他的狀態(tài)不變。(4)讀取40地址中數(shù)據(jù)到存放器r3中，然后r3中數(shù)據(jù)加1，并將執(zhí)行后的r3數(shù)據(jù)存回40地址中，該操作對40地址對應(yīng)塊

10、執(zhí)行了一次讀操作和一次寫操作，將讀(R)和寫()標(biāo)志位置1，然后將原始40地址對應(yīng)塊中數(shù)據(jù)存入日志中，存入LgPtr指向的地址中，同時(shí)將LgPtr指針后移。(5)事務(wù)提交后狀態(tài)將與本領(lǐng)務(wù)相關(guān)的各個(gè)數(shù)據(jù)塊對應(yīng)讀寫標(biāo)志位清0，將LgPtr置位到LgBase，Tunt置0。(本例僅針對單事務(wù)執(zhí)行，假如是嵌套事務(wù)的執(zhí)行，LgT構(gòu)造會更加復(fù)雜，詳細(xì)支持嵌套事務(wù)的LgT實(shí)現(xiàn)，請參考2)(6)事務(wù)回滾后狀態(tài)事務(wù)在執(zhí)行或提交過程中假如出錯(cuò)需要回滾，那么將日志中記錄的原始數(shù)據(jù)按照地址映射關(guān)系重新加載到對應(yīng)ahe數(shù)據(jù)塊中，同時(shí)將各個(gè)塊對應(yīng)讀寫標(biāo)志位清0，LgPtr重置并且Tunt置0。圖4事務(wù)版本管理過程成功提交

11、和回滾2.2沖突管理(ntentinanageent)LgT采用積極的沖突管理形式，而沖突管理中的一個(gè)重要概念目錄，就是在內(nèi)存中開拓的一片用來記錄共享數(shù)據(jù)索引和相關(guān)狀態(tài)信息的區(qū)域，也稱為目錄表。此沖突管理以目錄為橋梁，通過目錄的分析和消息轉(zhuǎn)發(fā)機(jī)制來完成多處理機(jī)間的沖突檢測。詳細(xì)的實(shí)現(xiàn)步驟概括起來為：懇求操作的處理機(jī)發(fā)出一致性懇求到目錄；目錄響應(yīng)懇求并可能將懇求轉(zhuǎn)發(fā)到其他一個(gè)或多個(gè)處理機(jī)上；每個(gè)響應(yīng)懇求的處理機(jī)檢查自身狀態(tài)看是否發(fā)生沖突；每個(gè)響應(yīng)懇求的處理機(jī)給出應(yīng)答信號，包括沖突應(yīng)答(nak)和非沖突應(yīng)答(ak)；發(fā)出懇求的處理機(jī)解決沖突。事務(wù)發(fā)生沖突后的交換行為須根據(jù)目錄中有效的ESI狀態(tài)(E

12、SI狀態(tài)：dified()，ned()，Exlusive(E)，Shared(S)rInvalidate(I)而定。下面結(jié)合圖5中的沖突檢測實(shí)例對沖突管理的詳細(xì)行為進(jìn)展說明。圖5LgT沖突檢測實(shí)例(1)事務(wù)開場處理機(jī)P開場執(zhí)行事務(wù)，Tunt增1；此時(shí)僅目錄中存放的ahe塊信息有效。(2)處理機(jī)P向目錄懇求數(shù)據(jù)信息步驟：P在自身的ahe中找不到某數(shù)據(jù)，馬上發(fā)送獨(dú)占懇求(GETX)到目錄。步驟：目錄收到懇求后根據(jù)相應(yīng)數(shù)據(jù)的索引找到“老版本數(shù)據(jù)傳給處理機(jī)P，當(dāng)“老版本數(shù)據(jù)到達(dá)P時(shí)，P將此數(shù)據(jù)更為“新版本數(shù)據(jù)同時(shí)將本機(jī)此數(shù)據(jù)塊對應(yīng)讀/寫標(biāo)志位置1。步驟：P承受數(shù)據(jù)完畢后，發(fā)送應(yīng)答信號給目錄表示已經(jīng)成功

13、承受數(shù)據(jù)。與此同時(shí)目錄中的狀態(tài)信息為P(difiedbyP)，表示此數(shù)據(jù)正在被處理機(jī)P更改。(3)檢測到事務(wù)沖突步驟：處理機(jī)Q發(fā)出懇求某共享數(shù)據(jù)的信號(GETS)給目錄。步驟：由于目錄中此數(shù)據(jù)的狀態(tài)為P，目錄那么根據(jù)懇求轉(zhuǎn)發(fā)給處理機(jī)P。步驟：P承受到懇求后檢查自己的狀態(tài)，由于P中相應(yīng)數(shù)據(jù)塊的寫標(biāo)志位已置，說明P正在修改此數(shù)據(jù)，不能滿足Q的懇求，發(fā)生沖突。這時(shí)處理機(jī)P直接發(fā)送沖突信號給Q，當(dāng)Q承受到?jīng)_突信號后進(jìn)展沖突處理。步驟：處理機(jī)Q同時(shí)將沖突信號發(fā)送給目錄，說明此次懇求失敗。(4)事務(wù)溢出的處理處理機(jī)P通知目錄要將修改后的數(shù)據(jù)存到內(nèi)存中(目前，內(nèi)存中存在的是對應(yīng)數(shù)據(jù)修改前的“臟數(shù)據(jù))。步驟：

14、P發(fā)出PUTX懇求給目錄。步驟：目錄認(rèn)可后發(fā)送應(yīng)答信號給P，通知P可以發(fā)送。步驟：P接收到此信號后將數(shù)據(jù)寫回內(nèi)存(B_XAT)同時(shí)將溢出位置1(說明此數(shù)據(jù)已經(jīng)不在ahe中)。這樣在寫回操作完成后，P中相關(guān)數(shù)據(jù)塊信息已置為無效，但是目錄中仍然保持著原先P持有數(shù)據(jù)時(shí)的狀態(tài)，內(nèi)存中對應(yīng)區(qū)域已為修改后的“干凈數(shù)據(jù)，目錄中該數(shù)據(jù)相應(yīng)的狀態(tài)也由“老變成了“新，說明內(nèi)存中此數(shù)據(jù)已為更新后的數(shù)據(jù)。(5)溢出數(shù)據(jù)的事務(wù)沖突檢測步驟：處理機(jī)Q重新發(fā)出懇求數(shù)據(jù)信號給目錄，由于目錄中的狀態(tài)還沒有改變。步驟：目錄根據(jù)當(dāng)前狀態(tài)再次將懇求轉(zhuǎn)發(fā)給處理機(jī)P，而此時(shí)Q懇求的數(shù)據(jù)塊已經(jīng)寫回內(nèi)存中去了，并不在P的ahe中，P收到懇求

15、信號后檢查到自身的溢出位已經(jīng)置位，它認(rèn)為此數(shù)據(jù)可能由于某種原因不在ahe中，但是仍然與它相關(guān)。比方：由于此數(shù)據(jù)塊大小大于ahe規(guī)定塊大小而不能放下，但仍需操作。步驟：P發(fā)出沖突信號(NAK)給Q，但是這個(gè)沖突并不是真正意義上的沖突，而是P假設(shè)的沖突。步驟：Q收到?jīng)_突信號后處理沖突同時(shí)發(fā)送信號給目錄，說明此次懇求再次失敗。(6)目錄中數(shù)據(jù)狀態(tài)的懶惰(Lazy)更新處理機(jī)P提交事務(wù)后將Tunt減1，將對應(yīng)ahe塊的讀/寫標(biāo)志位和溢出標(biāo)志位清零，但此時(shí)目錄中的狀態(tài)仍然為P。步驟：此時(shí)一旦處理機(jī)Q重新發(fā)出懇求此數(shù)據(jù)信號。步驟：該信號會再一次通過目錄轉(zhuǎn)發(fā)給處理機(jī)P，但此時(shí)P的溢出位已經(jīng)被清空。步驟：P通

16、過發(fā)送去除信息(LEAN)給目錄通知目錄不必再轉(zhuǎn)發(fā)懇求信息，目錄中的數(shù)據(jù)信息有效可以直接發(fā)送給懇求的處理機(jī)Q。步驟：目錄根據(jù)索引關(guān)系找到相關(guān)數(shù)據(jù)發(fā)送給處理機(jī)Q。步驟：Q收到數(shù)據(jù)后進(jìn)展處理同時(shí)將應(yīng)答信號發(fā)送給目錄，說明懇求成功同時(shí)將目錄對應(yīng)數(shù)據(jù)項(xiàng)狀態(tài)置EQ，表示此時(shí)處理機(jī)Q獨(dú)占此數(shù)據(jù)資源。但在執(zhí)行沖突檢測的過程中也會存在錯(cuò)誤的沖突，比方：當(dāng)處理機(jī)Q懇求訪問一個(gè)數(shù)據(jù)塊，該數(shù)據(jù)塊在目錄中的狀態(tài)為P，而處理機(jī)P已經(jīng)執(zhí)行到后續(xù)事務(wù)，同時(shí)也置了溢出位。P發(fā)送沖突信號給Q，但這個(gè)沖突并不是因處理機(jī)Q懇求的數(shù)據(jù)正被其他占有而產(chǎn)生的沖突，是一種無關(guān)的沖突。所以必須采取一種機(jī)制將目錄狀態(tài)及時(shí)更新。2.3操作系統(tǒng)對

17、LgT的支持由于事務(wù)的引入，傳統(tǒng)操作系統(tǒng)已經(jīng)不能滿足要求，必須更改或擴(kuò)展操作系統(tǒng)使事務(wù)能穩(wěn)定高效的執(zhí)行。首先，基于LgT系統(tǒng)，操作系統(tǒng)負(fù)責(zé)對日志進(jìn)展創(chuàng)立和維護(hù)。它為每一個(gè)執(zhí)行線程開拓一片日志區(qū)域，并將該區(qū)域入口地址寫到LgBase存放器中，同時(shí)當(dāng)某數(shù)據(jù)存入日志后使LgPinter指針后移，用來存放新數(shù)據(jù)。當(dāng)發(fā)生回滾，操作系統(tǒng)根據(jù)目前LgPinter指針從后向前恢復(fù)數(shù)據(jù)直到LgPinter與LgBase指向一樣為止。其次，當(dāng)執(zhí)行事務(wù)發(fā)生切換時(shí)，操作系統(tǒng)可以通過擴(kuò)展目前的TB(線程控制塊)來對事務(wù)相關(guān)存放器內(nèi)容等信息進(jìn)展保存。再次，當(dāng)發(fā)惹事務(wù)級線程切換時(shí)，操作系統(tǒng)判斷切換原因(包括其他線程搶占、時(shí)

18、間片到達(dá)、事務(wù)之間沖突等而執(zhí)行的切換)，通知調(diào)度器采取不同的切換策略或沖突策略來完成切換。最后，由于中斷內(nèi)新創(chuàng)立的事務(wù)和被中斷事務(wù)沖突而導(dǎo)致活鎖(被中斷事務(wù)掛起得不到執(zhí)行，中斷內(nèi)新創(chuàng)立事務(wù)由于沖突策略一直回滾重新執(zhí)行回滾，也得不到執(zhí)行)，操作系統(tǒng)必須可以記錄回滾次數(shù)并設(shè)定一個(gè)門限值，假如同一事務(wù)回滾數(shù)超過此門限，操作系統(tǒng)可以強(qiáng)行中止該事務(wù)而調(diào)度其他事務(wù)。本文介紹T的根本原理，并對當(dāng)前主流T系統(tǒng)LgT進(jìn)展分析實(shí)現(xiàn)，得出以下結(jié)論：要實(shí)現(xiàn)高效的事務(wù)處理必需要有一個(gè)很好的基于事務(wù)模型的硬件構(gòu)造。比方：LgT，硬件專門為T添加了LgBase、LgPinter等存放器并改變了ahe的構(gòu)造，在ahe中參加了

19、讀(R)和寫()標(biāo)志位；這樣對事務(wù)版本管理以及沖突管理都帶來了前所未有的作用，這也是此T構(gòu)造優(yōu)越性的表達(dá)。要高效的進(jìn)展事務(wù)處理必需要有T操作系統(tǒng)的支持，上文中提到了一些操作系統(tǒng)對LgT的相關(guān)支持，但假如要完美的支持事務(wù)還需要不斷更改和優(yōu)化已有的操作系統(tǒng)，最終的目的是將操作系統(tǒng)事務(wù)化，并能很好的處理事務(wù)化的用戶級應(yīng)用。目前T系統(tǒng)(包括LgT)雖然通過一些特有的構(gòu)造和機(jī)制解決了事務(wù)處理的一些問題，但是面對今后的開展，像多級嵌套事務(wù)的復(fù)雜應(yīng)用、中斷事務(wù)化(特別是外部設(shè)備的中斷)、掛起事物與執(zhí)行事務(wù)沖突問題、被切換事務(wù)的執(zhí)行選擇(重新調(diào)度后，被切換事務(wù)可能回滾也可能繼續(xù)接著執(zhí)行)等問題都需要我們不斷的去研究，去尋找最優(yōu)的解決方法一一攻克，所以對T的研究任重而道遠(yuǎn)。1Yen，L.andJ.Bbba，etal.LgT-SE：DeuplingHardareTransatinaleryfrahes.InPr.fThirteenthAnnualInternatinalSyp.nHigh-PerfraneputerArhi