15章-內(nèi)存數(shù)據(jù)庫系統(tǒng)-數(shù)據(jù)庫系統(tǒng)概論第五版

1、第15章內(nèi)存數(shù)據(jù)庫系統(tǒng)內(nèi)存數(shù)據(jù)庫(MainMemoryDataBase,MMDB)系統(tǒng)是指將數(shù)據(jù)庫的全部或大部分?jǐn)?shù)據(jù)放在內(nèi)存中的數(shù)據(jù)庫系統(tǒng)1。其實(shí)現(xiàn)技術(shù)的研究始于20世紀(jì)80年代，目的是有效利用內(nèi)存的優(yōu)勢，提高數(shù)據(jù)庫的性能。隨著計(jì)算機(jī)硬件技術(shù)的發(fā)展和高性能數(shù)據(jù)處理需求的推動(dòng)，特別是大數(shù)據(jù)時(shí)代的到來，內(nèi)存數(shù)據(jù)庫系統(tǒng)己經(jīng)成為數(shù)據(jù)庫系統(tǒng)的一個(gè)新方向。2013年Gartner發(fā)布前10大戰(zhàn)略性技術(shù)趨勢，將內(nèi)存計(jì)算列入重要的發(fā)展趨勢之一。本章介紹內(nèi)存數(shù)據(jù)庫的基本知識(shí)及其相關(guān)技術(shù)。15.1概述內(nèi)存數(shù)據(jù)庫是將內(nèi)存作為主存儲(chǔ)設(shè)備的數(shù)據(jù)庫系統(tǒng)。內(nèi)存數(shù)據(jù)庫有時(shí)也稱主存數(shù)據(jù)庫，In-MemoryDataBase等。

2、與內(nèi)存數(shù)據(jù)庫相對(duì)的磁盤數(shù)據(jù)庫(DiskResidentDataBase,DRDB是使用磁盤作為常規(guī)數(shù)據(jù)存儲(chǔ)設(shè)備，使用內(nèi)存作為工作數(shù)據(jù)緩沖區(qū)的數(shù)據(jù)庫系統(tǒng)。在磁盤數(shù)據(jù)庫中，磁盤是常規(guī)的數(shù)據(jù)存儲(chǔ)設(shè)備，磁盤陣列或磁帶機(jī)是數(shù)據(jù)的后備存儲(chǔ)設(shè)備，內(nèi)存作為磁盤數(shù)據(jù)庫的緩存使用。磁盤數(shù)據(jù)庫的數(shù)據(jù)組織、存儲(chǔ)訪問模型及處理模型都是面向磁盤訪問特性而設(shè)計(jì)的，磁盤數(shù)據(jù)通過緩沖區(qū)被處理器間接訪問，查詢優(yōu)化的核心是減少磁盤的輸入/輸出。在內(nèi)存數(shù)據(jù)庫中，內(nèi)存作為常規(guī)的數(shù)據(jù)存儲(chǔ)設(shè)備，磁盤是數(shù)據(jù)的永久存儲(chǔ)及后備存儲(chǔ)設(shè)備。內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)組織、存儲(chǔ)訪問模型和查詢處理模型都針對(duì)內(nèi)存特性進(jìn)行了優(yōu)化設(shè)計(jì)，內(nèi)存數(shù)據(jù)被處理器直接訪問。內(nèi)存數(shù)

3、據(jù)庫與磁盤數(shù)據(jù)庫的區(qū)別如圖15.1所示。處理界卷內(nèi)存內(nèi)存收鬻庫表和索弓1索引*W二彩時(shí)文好W后ftfrtt圖15.1內(nèi)存數(shù)據(jù)序和磁盤數(shù)據(jù)庫對(duì)比示意圖內(nèi)存數(shù)據(jù)庫中的數(shù)據(jù)常駐內(nèi)存，消除了磁盤數(shù)據(jù)庫中巨大的輸入/輸出代價(jià)。同時(shí)，數(shù)據(jù)的存儲(chǔ)和訪問算法以內(nèi)存訪問特性為基礎(chǔ)，實(shí)現(xiàn)處理器對(duì)數(shù)據(jù)的直接訪問，在算法和代碼效率上高于以磁盤輸入/輸出為基礎(chǔ)的磁盤數(shù)據(jù)庫。在內(nèi)存數(shù)據(jù)庫中，使用針對(duì)內(nèi)存特性進(jìn)行優(yōu)化的存儲(chǔ)結(jié)構(gòu)、索引結(jié)構(gòu)和操作算法進(jìn)一步優(yōu)化了內(nèi)存數(shù)據(jù)庫的性能，因此與數(shù)據(jù)全部緩存到內(nèi)存的磁盤數(shù)據(jù)庫相比，內(nèi)存數(shù)據(jù)庫的性能仍然高出數(shù)倍。15.2 內(nèi)存數(shù)據(jù)庫的發(fā)展歷程內(nèi)存數(shù)據(jù)庫的研究起步較早，20世紀(jì)60年代末就出

4、現(xiàn)了內(nèi)存數(shù)據(jù)庫的雛形。由于當(dāng)時(shí)內(nèi)存容量較小、成本較高，內(nèi)存數(shù)據(jù)庫主要作為嵌入式系統(tǒng)或者磁盤數(shù)據(jù)庫輔助的存儲(chǔ)與加速引擎存在。其主要目標(biāo)是把磁盤數(shù)據(jù)庫中使用頻繁的“熱”數(shù)據(jù)集中存放在內(nèi)存中，提高這些關(guān)鍵數(shù)據(jù)的查詢和處理效率。隨著內(nèi)存的價(jià)格不斷下降、容量不斷增大，內(nèi)存數(shù)據(jù)庫的實(shí)用性得到顯著提高，從而促進(jìn)了內(nèi)存數(shù)據(jù)庫技術(shù)的研究與發(fā)展。1 .內(nèi)存數(shù)據(jù)庫的雛形期1969年，舊M公司研制了國際上最早的層次數(shù)據(jù)庫管理系統(tǒng)IMSoIMS在一個(gè)系統(tǒng)中提供了兩種數(shù)據(jù)管理方法，一種是采用內(nèi)存存儲(chǔ)的FastPath,另一種是支持磁盤存儲(chǔ)的IMS。FastPath支持內(nèi)存駐留數(shù)據(jù)，是內(nèi)存數(shù)據(jù)庫的雛形。它體現(xiàn)了內(nèi)存數(shù)據(jù)庫的

5、主要設(shè)計(jì)思想，也就是將需要頻繁訪問，要求高響應(yīng)速度的數(shù)據(jù)直接存放在物理內(nèi)存中訪問和管理。內(nèi)存數(shù)據(jù)庫起步于層次型數(shù)據(jù)庫，其后的發(fā)展逐漸轉(zhuǎn)向關(guān)系型內(nèi)存數(shù)據(jù)庫。2 .內(nèi)存數(shù)據(jù)庫的研究發(fā)展期1984年，D.J.DeW廿等人發(fā)表了“內(nèi)存數(shù)據(jù)庫系統(tǒng)的實(shí)現(xiàn)技術(shù)”一文，第一次提出了MainMemoryDataBase的概念。專家預(yù)言異常昂貴的計(jì)算機(jī)內(nèi)存價(jià)格一定會(huì)逐漸下降，大容量的數(shù)據(jù)有可能全部存儲(chǔ)在內(nèi)存中，因此開展了對(duì)內(nèi)存數(shù)據(jù)庫關(guān)鍵技術(shù)的研究，包括內(nèi)存計(jì)算的AVL樹、hash算法、使用非易失內(nèi)存或預(yù)提交和成組提交技術(shù)解決內(nèi)存易失性問題、內(nèi)存數(shù)據(jù)庫恢復(fù)機(jī)制等。1985年，IBM推出了在舊M370上運(yùn)行的OBE內(nèi)

6、存數(shù)據(jù)庫，OBE在關(guān)系存儲(chǔ)和索引上大量使用指針，連接操作使用嵌套循環(huán)算法，查詢優(yōu)化的重點(diǎn)是內(nèi)存的處理代價(jià)。1986年，R.B.Hagman提出了使用檢查點(diǎn)技術(shù)實(shí)現(xiàn)內(nèi)存數(shù)據(jù)庫的恢復(fù)機(jī)制；威斯康星大學(xué)提出了按區(qū)雙向鎖定模式解決內(nèi)存數(shù)據(jù)庫中的并發(fā)控制問題，并設(shè)計(jì)出MM-DBMS內(nèi)存數(shù)據(jù)庫；貝爾實(shí)驗(yàn)室推出了DALI內(nèi)存數(shù)據(jù)庫模型，其重要特點(diǎn)是使用內(nèi)存映射體系，采用分區(qū)技術(shù)把數(shù)據(jù)庫的數(shù)據(jù)文件映射到共享內(nèi)存，處理器可以直接通過指針訪問儲(chǔ)存在內(nèi)存數(shù)據(jù)庫中的信息，而且數(shù)據(jù)庫的并發(fā)控制和日志機(jī)制可以根據(jù)需要來打開或關(guān)閉。1987年，ACMSIGMOD會(huì)議中有論文提出了以堆文件(heapfile)作為內(nèi)存數(shù)據(jù)庫的

7、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。SouthernMethodist大學(xué)設(shè)計(jì)出MARS內(nèi)存數(shù)據(jù)庫模型，該模型采用雙處理器分別用于數(shù)據(jù)庫和恢復(fù)處理，事務(wù)提交點(diǎn)之前的任務(wù)由數(shù)據(jù)庫處理器負(fù)責(zé)：恢復(fù)處理器負(fù)責(zé)事務(wù)提交，將日志和更新的數(shù)據(jù)寫到磁盤數(shù)據(jù)庫中，周期性的檢查點(diǎn)同樣由恢復(fù)處理器負(fù)責(zé)。MARS采用雙處理器、易失性內(nèi)存和非易失性內(nèi)存存儲(chǔ)設(shè)備將事務(wù)處理劃分為兩個(gè)獨(dú)立的階段，獨(dú)立加速各自階段的處理性能。1988年，普林斯頓大學(xué)設(shè)計(jì)出TPK內(nèi)存數(shù)據(jù)庫。TPK提供了一種多處理器架構(gòu)下的多線程處理模式，包括輸入、執(zhí)行、輸出、檢查點(diǎn)4類線程，通常配置為單查詢執(zhí)行線程和單檢查點(diǎn)線程。單查詢執(zhí)行線程設(shè)計(jì)不需要并發(fā)控制機(jī)制，而輸入和輸出

8、線程數(shù)量可以為多個(gè)，并使用隊(duì)列結(jié)構(gòu)與其他線程連接。TPK的多線程內(nèi)存數(shù)據(jù)庫技術(shù)實(shí)現(xiàn)了一種多階段的查詢處理技術(shù)。1990年，普林斯頓大學(xué)又設(shè)計(jì)出SystemM內(nèi)存數(shù)據(jù)庫。SystemM由一系列操作服務(wù)線程構(gòu)成，包括消息服務(wù)線程、事務(wù)服務(wù)線程、日志服務(wù)線程和檢查點(diǎn)服務(wù)線程等。SystemM可以支持并發(fā)查詢服務(wù)線程，但仍然要控制活動(dòng)事務(wù)服務(wù)線程的數(shù)量。3 .內(nèi)存數(shù)據(jù)庫的產(chǎn)品成長期隨著互聯(lián)網(wǎng)的發(fā)展，越來越多的網(wǎng)絡(luò)應(yīng)用需要高性能、高并發(fā)的數(shù)據(jù)庫系統(tǒng)支撐，傳統(tǒng)企業(yè)級(jí)的數(shù)據(jù)庫應(yīng)用，如電信、金融等領(lǐng)域同樣需要高性能的實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)。應(yīng)用需求催生了內(nèi)存數(shù)據(jù)庫市場。在硬件方面，半導(dǎo)體技術(shù)快速發(fā)展，內(nèi)存存儲(chǔ)密度不斷

9、提高，動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(DRAM)的容量越來越大、價(jià)格越來越低，這些無疑為計(jì)算機(jī)內(nèi)存的不斷擴(kuò)大提供了硬件基礎(chǔ)，使得內(nèi)存數(shù)據(jù)庫的技術(shù)在可行性和成本的合理化方面逐步成熟。一些公司陸續(xù)推出了不同的內(nèi)存數(shù)據(jù)庫產(chǎn)品。1994年，美國OSE公司推出了第一個(gè)商業(yè)化的、開始實(shí)際應(yīng)用的內(nèi)存數(shù)據(jù)庫產(chǎn)品Polyhedra。1996年，TimesTen公司成立并推出第一個(gè)商業(yè)版內(nèi)存數(shù)據(jù)庫TimesTen2.0,2005年該公司被Oracle公司收購。1998年，德國SoftwareAG公司推出了內(nèi)存數(shù)據(jù)庫TaminoDatabase。1999年，日本UBIT會(huì)社開發(fā)出了內(nèi)存數(shù)據(jù)庫產(chǎn)品XDB韓國Altibase公司推

10、出了內(nèi)存數(shù)據(jù)庫Altibase。2000年，奧地利QuiLogic公司推出了內(nèi)存數(shù)據(jù)庫SQL-IMDR2001年，美國McObject推出了內(nèi)存數(shù)據(jù)庫eXtremeDB;加拿大Empress公司推出了內(nèi)存數(shù)據(jù)庫EmpressDR2003年，荷蘭CWI研究院研制了基于列存儲(chǔ)模型的內(nèi)存數(shù)據(jù)庫MonetDB34,其后又研制了基于向量處理技術(shù)的MonetDB/X100系統(tǒng)，2008年推出其商業(yè)化版本Vectorwise。2010年Ingres公司和CW1研究院合作推出了VectorWise1.0版。2011年3月VectorWise1.5版獲得了TPC-H100GB數(shù)據(jù)量測試的第一名，當(dāng)前仍然是TPC

11、-H性能最高的數(shù)據(jù)庫。2008年，IBM收購Solid公司的內(nèi)存數(shù)據(jù)庫SolidDB,成為舊M家族的一個(gè)產(chǎn)品。舊M提出BlinkBI(商業(yè)智能)內(nèi)存查詢處理引擎，并為Informix提供內(nèi)存加速包IWA(InformixWarehouseAccelerator)。2011年，SAP公司推出SAPHANA(High-PerformanceAnalyticAppliance)5高性能分析應(yīng)用系統(tǒng)，是面向企業(yè)分析型應(yīng)用的內(nèi)存計(jì)算技術(shù)的產(chǎn)品。Oracle公司于2008年推出軟硬件集成設(shè)計(jì)的OracleExadata數(shù)據(jù)庫服務(wù)器。OracleExadata是由DatabaseMachine(數(shù)據(jù)庫服務(wù)器

12、)與ExadataStorageServer存儲(chǔ)服務(wù)器)組成的一體機(jī)平臺(tái)。2012推出OracleExadataX3DatabaseIn-MemoryMachine,大幅增加了內(nèi)存配置，實(shí)現(xiàn)將全部數(shù)據(jù)加載到內(nèi)存，將所有的數(shù)據(jù)庫I/O全部轉(zhuǎn)移到閃存，以提供高性能的數(shù)據(jù)訪問和查詢處理，成為Oracle新一代的內(nèi)存數(shù)據(jù)庫一體機(jī)平臺(tái)。綜上所述，可以發(fā)現(xiàn)最初的內(nèi)存數(shù)據(jù)庫僅僅是針對(duì)特定的應(yīng)用需求定制的內(nèi)存數(shù)據(jù)處理系統(tǒng)，如要求高實(shí)時(shí)響應(yīng)的電信應(yīng)用。這類系統(tǒng)通過應(yīng)用程序來管理內(nèi)存和數(shù)據(jù)，不支持SQL語句，不提供本地存儲(chǔ)，沒有數(shù)據(jù)庫恢復(fù)技術(shù)，性能好但不是通用平臺(tái)，難以維護(hù)和推廣。后來，內(nèi)存數(shù)據(jù)庫系統(tǒng)能支持部分的

13、SQL語句和簡單的系統(tǒng)恢復(fù)，能夠快速處理簡單事務(wù)，主要針對(duì)功能簡單的事務(wù)處理應(yīng)用，例如交換機(jī)，移動(dòng)通信等應(yīng)用領(lǐng)域。隨后，針對(duì)傳統(tǒng)數(shù)據(jù)庫商業(yè)應(yīng)用領(lǐng)域研制了通用的內(nèi)存數(shù)據(jù)庫系統(tǒng)。它們具備了高性能、高通用性以及高穩(wěn)定性，能處理復(fù)雜的SQL語句，其應(yīng)用幾乎包括磁盤數(shù)據(jù)庫的所有應(yīng)用領(lǐng)域。近年來，針對(duì)大內(nèi)存上的大數(shù)據(jù)實(shí)時(shí)分析處理任務(wù)，又研制了分析型內(nèi)存數(shù)據(jù)庫。主要面向只讀(read-most)查詢處理或append-only類型的更新任務(wù)，以列存儲(chǔ)與混合存儲(chǔ)、多核并行處理、復(fù)雜分析查詢處理為特點(diǎn)，為用戶提供秒級(jí)甚至亞秒級(jí)分析處理能力。隨著未來眾核協(xié)處理器、通用計(jì)算圖形處理器(GeneralPurposeG

14、raphicUnit,GPGPU年新的高性能計(jì)算平臺(tái)進(jìn)入數(shù)據(jù)庫領(lǐng)域，內(nèi)存數(shù)據(jù)庫將成為大數(shù)據(jù)實(shí)時(shí)分析處理平臺(tái)。15.3 內(nèi)存數(shù)據(jù)庫的特性內(nèi)存是計(jì)算機(jī)存儲(chǔ)體系結(jié)構(gòu)中能夠被程序可控訪問(相對(duì)于硬件控制的cache)的最高層次，是能夠提供大量數(shù)據(jù)存儲(chǔ)的最快的存儲(chǔ)層。內(nèi)存數(shù)據(jù)庫具有優(yōu)異的數(shù)據(jù)存儲(chǔ)訪問性能、較高的數(shù)據(jù)訪問帶寬和數(shù)據(jù)并行訪問能力等特性。(1)高吞吐率和低訪問延遲數(shù)據(jù)庫的查詢處理性能主要取決于數(shù)據(jù)的存儲(chǔ)訪問性能。內(nèi)存數(shù)據(jù)庫不需要磁盤數(shù)據(jù)庫的緩沖區(qū)機(jī)制，數(shù)據(jù)能夠被處理器直接訪問。內(nèi)存的高帶寬和低訪問延遲保證了內(nèi)存數(shù)據(jù)庫具有較高的事務(wù)吞吐率和較低的查詢處理延遲，能夠支持高實(shí)時(shí)響應(yīng)的應(yīng)用需求，在金融

15、、電信、電子商務(wù)平臺(tái)等查詢負(fù)載重，且查詢響應(yīng)時(shí)間要求高的應(yīng)用環(huán)境中得到了廣泛的應(yīng)用。(2)并行處理能力內(nèi)存具有良好的并行數(shù)據(jù)訪問能力(當(dāng)前為四通道內(nèi)存訪問機(jī)制)和隨機(jī)訪問性能，因此內(nèi)存數(shù)據(jù)庫的查詢處理技術(shù)帶有天然的并行性，并且可以充分利用隨機(jī)訪問能力提高查詢的數(shù)據(jù)訪問效率和CPU指令效率。多核處理器(multicorecpu)技術(shù)和多路服務(wù)器平臺(tái)已成為當(dāng)前數(shù)據(jù)庫標(biāo)準(zhǔn)的硬件平臺(tái)。以磁盤為中心的磁盤數(shù)據(jù)庫難以充分利用當(dāng)前新硬件帶來的高度并行計(jì)算能力，而內(nèi)存數(shù)據(jù)庫在查詢處理模型中可以充分考慮并行計(jì)算能力。因此在內(nèi)存數(shù)據(jù)庫的查詢處理設(shè)計(jì)上，既要研究與開發(fā)面向內(nèi)存特性的查詢處理優(yōu)化技術(shù)，又要研究并行處理

16、優(yōu)化技術(shù)。（3）硬件相關(guān)性內(nèi)存數(shù)據(jù)庫的性能受硬件特性的直接影響。計(jì)算機(jī)硬件技術(shù)的發(fā)展主要體現(xiàn)在高端計(jì)算設(shè)備和存儲(chǔ)設(shè)備上，如多核處理器、眾核協(xié)處理器（ManyIntegratedCore,MIC）、通用GPU、PCM存儲(chǔ)（PhaseChangeMemory,相變存儲(chǔ)）、固態(tài)硬盤（SolidStateDisk,SSD存儲(chǔ)等。這些計(jì)算能力和存儲(chǔ)性能的提升有助于內(nèi)存吞吐率需求的提升（眾核技術(shù)）、提高內(nèi)存持久存儲(chǔ)能力（PCM技術(shù)）或?yàn)閮?nèi)存提供二級(jí)存儲(chǔ)（SSD技術(shù)）。硬件技術(shù)在多核及眾核處理器、高性能存儲(chǔ)和高速網(wǎng)絡(luò)等方面的發(fā)展為內(nèi)存數(shù)據(jù)庫提供了高并行處理、高性能存儲(chǔ)訪問以及高速連通的硬件平臺(tái)。內(nèi)存數(shù)據(jù)庫的

17、設(shè)計(jì)應(yīng)該充分考慮并有效利用由新硬件技術(shù)帶來的功能擴(kuò)展和性能提高。15.4 內(nèi)存數(shù)據(jù)庫的關(guān)鍵技術(shù)由于內(nèi)存數(shù)據(jù)庫上述的特點(diǎn)，磁盤數(shù)據(jù)庫實(shí)現(xiàn)中的相關(guān)技術(shù)在內(nèi)存數(shù)據(jù)庫中不能照搬使用。通用的內(nèi)存數(shù)據(jù)庫管理系統(tǒng)要為用戶提供SQL接口，具有內(nèi)存存儲(chǔ)管理、面向內(nèi)存的查詢處理和優(yōu)化等基本模塊，還應(yīng)提供多用戶的并發(fā)控制、事務(wù)管理和訪問控制，能夠保證數(shù)據(jù)庫的完整性和安全性，在內(nèi)存數(shù)據(jù)庫出現(xiàn)故障時(shí)能夠?qū)ο到y(tǒng)進(jìn)行恢復(fù)。內(nèi)存數(shù)據(jù)庫作為處理器直接訪問的數(shù)據(jù)管理系統(tǒng)，需要研究自底向上的面向內(nèi)存和多核并行處理的系統(tǒng)框架和新的實(shí)現(xiàn)技術(shù)。下面簡要介紹內(nèi)存數(shù)據(jù)庫中的若干關(guān)鍵技術(shù)。15.4.1 數(shù)據(jù)存儲(chǔ)數(shù)據(jù)庫的數(shù)據(jù)存儲(chǔ)一般有行存儲(chǔ)模型

18、、列存儲(chǔ)模型和混合模型等。在行存儲(chǔ)模型中元組是連續(xù)存放的，適合事務(wù)處理中一次更新多個(gè)屬性的操作，能夠保證對(duì)多個(gè)屬性的操作產(chǎn)生最小的內(nèi)存訪問；但對(duì)于只涉及表中相對(duì)較少屬性的分析處理時(shí)，即使該查詢僅涉及元組的某個(gè)或某些屬性，其他屬性也會(huì)被同時(shí)從內(nèi)存讀入到緩存，降低了緩存利用率。列存儲(chǔ)模型將關(guān)系按列進(jìn)行垂直劃分，相同屬性的數(shù)據(jù)連續(xù)存儲(chǔ)。當(dāng)訪問特定屬性時(shí)只讀入所需要的屬性所在的分片，所以節(jié)省內(nèi)存帶寬，并且具有較高的數(shù)據(jù)訪問局部性，可減少緩存失效，提高數(shù)據(jù)訪問效率；同時(shí)列存儲(chǔ)將相同類型的數(shù)據(jù)集中存儲(chǔ)，能夠更好地對(duì)數(shù)據(jù)進(jìn)行壓縮以減少內(nèi)存帶寬消耗，利用SIMD（單指令多數(shù)據(jù)流）技術(shù)提高并行處理效率，通過列存

19、儲(chǔ)的數(shù)據(jù)定長化處理支持對(duì)數(shù)據(jù)按偏移位置的訪問。但是，如果查詢所需要的屬性較多，列存儲(chǔ)需要連接多個(gè)劃分來滿足查詢要求，則會(huì)導(dǎo)致性能下降。特別是元組重構(gòu)時(shí)需要進(jìn)行較多的連接操作，代價(jià)較高。針對(duì)行存儲(chǔ)模型和列存儲(chǔ)模型各自的不足，A.Ailamaki等提出了一種混合存儲(chǔ)模型PAX（PartitionAttributesAcross）7。該模型把同一元組的所有屬性值存儲(chǔ)在一頁內(nèi)，在頁內(nèi)對(duì)元組進(jìn)行垂直劃分。根據(jù)關(guān)系的屬性個(gè)數(shù)m將每一頁劃分為個(gè)m個(gè)MiniPage,每個(gè)MiniPage對(duì)應(yīng)一個(gè)屬性，連續(xù)存放每一頁中所有元組的該屬性的值。由于元組在頁內(nèi)進(jìn)行垂直劃分，所以該模型具有較好的數(shù)據(jù)空間局部性，可優(yōu)化緩

20、存性能；同時(shí)，同一元組的值存儲(chǔ)在同一頁內(nèi)，所以元組的重構(gòu)代價(jià)比較少。DataMorphing8也是一種混合存儲(chǔ)技術(shù)，它在頁內(nèi)按屬性訪問特征劃分為屬性組，將屬性訪問關(guān)聯(lián)度高的屬性組合存儲(chǔ)，在一次cacheline訪問時(shí)獲得盡可能多的屬性值，提高這些屬性訪問時(shí)的緩存效率。圖15.2展示了行存儲(chǔ)（a）、PAX存儲(chǔ)（b）、屬性組存儲(chǔ)（c）的頁內(nèi)物理數(shù)據(jù)分布。內(nèi)存數(shù)據(jù)庫系統(tǒng)既有聯(lián)機(jī)事務(wù)處理（On-LineTransactionProcessing,OLTP更新密集型應(yīng)用，也有聯(lián)機(jī)分析處理（On-LineAnalyticalProcessing,OLAP）M雜分析型應(yīng)用，因此行存儲(chǔ)和列存儲(chǔ)這兩種存儲(chǔ)模型被

21、不同的內(nèi)存數(shù)據(jù)庫系統(tǒng)所采用。例如，Timesten,soIidDB等事務(wù)型內(nèi)存數(shù)據(jù)庫采用的是行存儲(chǔ)模型；MonetDB、HANA,Vectorwise等分析型內(nèi)存數(shù)據(jù)庫采用的是列存儲(chǔ)模型。Brighthouse、OracleExadata等采用混合存儲(chǔ)模型。(b)PAX(/tt1CacheLine-32bytes圖15.2行存儲(chǔ)、PAX存儲(chǔ)和屬性組存儲(chǔ)Brighthouse在PAX存儲(chǔ)模型基礎(chǔ)上實(shí)現(xiàn)了DataPack存儲(chǔ)機(jī)制9,如圖15.3所示。它首先將記錄水平分片為行組（rowgroup）,216行為一個(gè)行組，每個(gè)行組以列方式存儲(chǔ)在DataPack數(shù)據(jù)單元內(nèi)。Brighthouse在Data

22、Pack上建立一張表（粗糙屬性信息表），用來記錄DataPack內(nèi)每列數(shù)據(jù)的最大值和最小值等信息。因此，在對(duì)列數(shù)據(jù)過濾操作時(shí)（如weight>30），可以通過與粗糙屬性信息表中DataPack最大值（如25）和最小值（如15）的比較直接跳過對(duì)不滿足過濾條件的DataPack的訪問，從而提高了列數(shù)據(jù)訪問效率。OutlookTtffipUwmdWwiTSumyHE2IMl而*H他Sroqf153Hol“岫Weak134RamMild3255RataCdMHofmlWnk116lUunCMNamai217OcrtMColdMohmIWind*Ml屆W3n9SumyColdNonnJWHk211

23、0RuiMildN«bbLWeik1511SvnqyMildNanml號(hào)Eje19OcmsMildS1ZK»£341)35cmalHusNohihlIW'nk14RunMildHiKbimEPtaklMin»7MoM5圖15.3DataPack存儲(chǔ)機(jī)制OracleExadata采用了一種CompressionUnit的混合列壓縮技術(shù)，簡稱為CU。CU對(duì)列存儲(chǔ)進(jìn)行分段,并在分段內(nèi)通過壓縮技術(shù)組織不同列的混合數(shù)據(jù)塊存儲(chǔ)，如圖15.4所示。CompressionUnit圖15.4CompressionUnit存儲(chǔ)機(jī)制在結(jié)構(gòu)化內(nèi)存數(shù)據(jù)庫技術(shù)發(fā)展的同時(shí)，基

24、于key/value的內(nèi)存存儲(chǔ)模型也逐漸成為滿足高實(shí)時(shí)響應(yīng)應(yīng)用的解決方案。這種NoSQL的內(nèi)存存儲(chǔ)技術(shù)具有良好的擴(kuò)展性，在很多大型社會(huì)網(wǎng)絡(luò)應(yīng)用中使用。與磁盤數(shù)據(jù)庫相比，內(nèi)存在訪問模式和訪問速度上的優(yōu)勢為內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)組織和存儲(chǔ)方式提供了更大的靈活性和多樣性。15.4.2 查詢處理及優(yōu)化內(nèi)存數(shù)據(jù)庫的查詢處理性能主要由兩個(gè)因素決定：內(nèi)存數(shù)據(jù)訪問性能和內(nèi)存數(shù)據(jù)處理性能。內(nèi)存數(shù)據(jù)訪問性能由內(nèi)存帶寬和內(nèi)存訪問延遲決定。相對(duì)于CPU,內(nèi)存數(shù)據(jù)訪問性能的增長速度與CPU性能增長速度之間的差距越來越大，如圖15.5所示。內(nèi)存訪問的巨大延遲(memorywall)是內(nèi)存數(shù)據(jù)庫的性能瓶頸。內(nèi)存數(shù)據(jù)庫查詢優(yōu)化的關(guān)

25、鍵技術(shù)是通過現(xiàn)代CPU的多級(jí)緩存結(jié)構(gòu)(LI、L2、L3cache)減少內(nèi)存數(shù)據(jù)訪問延遲，提高數(shù)據(jù)訪問性能。摩爾定律的影喻圖15.5CPU和內(nèi)存訪問延遲內(nèi)存數(shù)據(jù)庫的處理性能主要受處理器性能影響。CPU的發(fā)展已經(jīng)進(jìn)入多核時(shí)代，不再單一依靠CPU主頻的提高，更多的處理核心提高了多核CPU的并行計(jì)算能力，因此內(nèi)存數(shù)據(jù)庫的查詢優(yōu)化技術(shù)也進(jìn)入多核并行時(shí)代，需要將內(nèi)存數(shù)據(jù)庫的查詢處理技術(shù)全面升級(jí)為多核CPU并行查詢處理技術(shù)，并根據(jù)多核CPU的硬件特性進(jìn)行算法優(yōu)化，提高內(nèi)存數(shù)據(jù)庫整體性能。同時(shí)，隨著協(xié)處理器走向通用計(jì)算領(lǐng)域，由于其計(jì)算內(nèi)核密度、并行計(jì)算能力等方面超過多核CPU,逐漸成為高性能計(jì)算的新平臺(tái)，也成

26、為內(nèi)存數(shù)據(jù)庫的擴(kuò)展技術(shù)。內(nèi)存數(shù)據(jù)庫，尤其是分析型內(nèi)存數(shù)據(jù)庫既有數(shù)據(jù)密集型處理的特點(diǎn)，又因其復(fù)雜的查詢而具有計(jì)算密集型處理的特點(diǎn)，內(nèi)存數(shù)據(jù)庫查詢優(yōu)化的重點(diǎn)既包括面向cache特性的查詢處理與優(yōu)化技術(shù)，又包括面向多核及協(xié)處理器的并行查詢處理技術(shù)。1.面向cache特性的查詢處理與優(yōu)化技術(shù)內(nèi)存數(shù)據(jù)庫的基礎(chǔ)假設(shè)是數(shù)據(jù)庫的工作數(shù)據(jù)集常駐于內(nèi)存中(memoryresident),從而消除了傳統(tǒng)磁盤數(shù)據(jù)庫的I/O代價(jià)，內(nèi)存數(shù)據(jù)庫的性能較磁盤數(shù)據(jù)庫有數(shù)十倍甚至數(shù)百倍的提升。但相對(duì)CPU速度的提升，內(nèi)存訪問需要上百個(gè)CPU時(shí)鐘周期的訪問延遲，因而成為內(nèi)存數(shù)據(jù)庫新的瓶頸。磁盤數(shù)據(jù)庫使用內(nèi)存緩沖區(qū)(buffer)來

27、優(yōu)化I/O代價(jià)，現(xiàn)代CPU使用硬件級(jí)的多級(jí)cache機(jī)制優(yōu)化cache機(jī)制來完成，采用類LRU(最近最少訪問)替內(nèi)存訪問，內(nèi)存數(shù)據(jù)庫的內(nèi)存訪問優(yōu)化由硬件級(jí)的換算法實(shí)現(xiàn)cache中的數(shù)據(jù)管理。圖15.6顯示了當(dāng)前多核CPU中的多級(jí)cache機(jī)制，每個(gè)核心擁有32KB的L1數(shù)據(jù)cache和32KB的L1指令cache,256KB的L2cache和共享L3cache。多核處理器的性能與內(nèi)核數(shù)量和共享L3cache容量密切相關(guān)。圖15.6(a)為6核CPU結(jié)構(gòu)，具有15MB的L3共享cache;圖15.6(b)為10核CPU結(jié)構(gòu)，具有25MB的L3共享cache;圖15.6(c)為最新的15核CPU結(jié)

28、構(gòu)，具有37.5MB的L3共享cache。MemoryControlJcr(0QPI為快速通道互聯(lián)。向注：PCIe為PCI-Express接口，圖15.6多核CPU中的多級(jí)cache機(jī)制多核CPU的發(fā)展趨勢是最后一級(jí)cache(LastLevelCache,LLC海量隨核數(shù)增加而增大，LLC大小是cache性能的一個(gè)重要指標(biāo)。CPU處理的是cache中的數(shù)據(jù)，若CPU需要的數(shù)據(jù)不在cache中，會(huì)導(dǎo)致cache失效，此時(shí)CPU需要等待數(shù)據(jù)從內(nèi)存中讀取，因此會(huì)延長數(shù)據(jù)的處理時(shí)間。研究表明數(shù)據(jù)庫在現(xiàn)代處理器中進(jìn)行查詢處理時(shí)，有大約一半的時(shí)間花費(fèi)在各種延遲上。其中大約20%的延遲是由于一些實(shí)現(xiàn)細(xì)節(jié)(

29、如分支誤判)引起的，內(nèi)存延遲中大部分延遲是由于一級(jí)指令cache失效和LLC失效引起的。cache失效可以分為強(qiáng)制(compulsory)失效、容量(capacity)失效和沖突(conflict)失效等類型。強(qiáng)制失效是數(shù)據(jù)首次訪問時(shí)在cache中所產(chǎn)生的失效，是內(nèi)存數(shù)據(jù)訪問不可避免的；容量失效是由于工作數(shù)據(jù)集超過cache容量大小而導(dǎo)致的數(shù)據(jù)訪問時(shí)在cache中的失效；沖突失效則是在cache容量充足時(shí)由于大量弱局部性數(shù)據(jù)(一次性訪問數(shù)據(jù)或復(fù)用周期很長的數(shù)據(jù))將強(qiáng)局部性數(shù)據(jù)(頻繁使用的數(shù)據(jù)集)驅(qū)逐出cache而在對(duì)強(qiáng)局部性數(shù)據(jù)重復(fù)訪問時(shí)產(chǎn)生的cache失效，沖突失效是現(xiàn)代內(nèi)存數(shù)據(jù)庫查詢優(yōu)化研

30、究的重要課題。另一個(gè)與內(nèi)存訪問延遲密切相關(guān)的硬件是TLB(TranslationLookasideBuffer)旁路轉(zhuǎn)換緩沖，或稱為頁表緩沖)。TLB是硬件級(jí)緩存，與CPU的cache類似，主要用來存放內(nèi)存頁表。在內(nèi)存的頁表區(qū)里，記錄虛擬頁面和物理頁框?qū)?yīng)關(guān)系的記錄稱為一個(gè)頁表?xiàng)l目(entry)。在TLB里緩存了一些頁表?xiàng)l目。當(dāng)CPU執(zhí)行機(jī)構(gòu)收到應(yīng)用程序發(fā)來的虛擬地址后，首先到TLB中查找相應(yīng)的頁表數(shù)據(jù)，如果TLB中正好存放著所需的頁表，則稱為TLB命中(TLBhit)。接下來CPU依次查看TLB中頁表所對(duì)應(yīng)的物理內(nèi)存地址中的數(shù)據(jù)是不是已經(jīng)在一級(jí)、二級(jí)緩存里了，如果不存在則為TLBmiss,需

31、要到頁表區(qū)進(jìn)行尋址，把這個(gè)映射關(guān)系更新到TLB中以備下次使用。由于TLB大小有限，而一旦出現(xiàn)TLBmiss其查詢的代價(jià)很高，所以現(xiàn)代CPU架構(gòu)基本都進(jìn)行了一些優(yōu)化以提高地址映射的效率。例如線性地址到物理地址轉(zhuǎn)換一開始就選擇同時(shí)在TLB和內(nèi)存頁表區(qū)進(jìn)行查詢，而不是在TLBmiss后再啟動(dòng)內(nèi)存頁表的查詢；使用多級(jí)TLB以及軟TLB在CPU內(nèi)容切換(contextswitch)時(shí)不清空(flush)TLB。cache性能優(yōu)化算法是一類通過提高cache數(shù)據(jù)的空間局部性和時(shí)間局部性，從而減少cache失效、優(yōu)化cache性能的算法。人們從不同角度研究cache性能的優(yōu)化算法，在數(shù)據(jù)訪問方面的cache

32、優(yōu)化技術(shù)主要包括以下幾類。(1) cache-conscious優(yōu)化技術(shù)cache-conscious優(yōu)化技術(shù)以hash連接優(yōu)化為代表。在hash連接中，內(nèi)層的hash表大小決定了hash探測過程中能否盡可能多地從高速cache中訪問hash表。為提高h(yuǎn)ash探測時(shí)的cache命中率，需要將hash表劃分為小于cache容量的較小的分區(qū)，從而使hash探測時(shí)的cache命中率提高?；诜謪^(qū)的hash連接算法需要將連接表L和R根據(jù)連接屬性的取值，按相同的hash函數(shù)進(jìn)行hash分區(qū)，當(dāng)連接表L和R較大時(shí)，關(guān)系表需要?jiǎng)澐譃閿?shù)量較多的分區(qū)以保證每個(gè)分區(qū)的數(shù)據(jù)量小于cache容量，而較多的分區(qū)導(dǎo)致數(shù)據(jù)

33、在分區(qū)時(shí)需要訪問數(shù)量眾多的地址，產(chǎn)生較大的TLB失效影響。Radix-Cluster是一種面向cache和TLB優(yōu)化的分區(qū)技術(shù)，它采用基數(shù)位hash分區(qū)技術(shù)，即使用數(shù)據(jù)的最低B個(gè)二進(jìn)制位將數(shù)據(jù)劃分為2B個(gè)分區(qū)，通過多趟基數(shù)分區(qū)控制每一趟分區(qū)的數(shù)量，降低TLB失效的影響。如圖15.7所示，表L和R以最后三個(gè)二進(jìn)位為基數(shù)劃分為8個(gè)分區(qū)，這個(gè)劃分過程分兩趟完成，第一趟使用后三位中的前二位將L和R表各自劃分為4個(gè)分區(qū)，然后在每個(gè)分區(qū)中再按最低位劃分為兩個(gè)分區(qū)。完成兩趟radix劃分后，在對(duì)應(yīng)的L表和R表分區(qū)上執(zhí)行hash連接操作。多趟radix分區(qū)保證了TLB性能，基于分區(qū)的hash連接操作提高了ha

34、sh連接時(shí)的cache性能?；诜謪^(qū)的兩削基數(shù)分區(qū)(001)81(100)2081756603171026692£06(000)(101)(010)(001)3706472047326621003352047blacktupleshit(lowest3-bitsofvaluesinparenthesis圖15.7Radix-cluster03(OH)17(OOI)66(010)96(000)2(010)32(000)35(Oil)47(111)20(100)10(010)R)針對(duì)列存儲(chǔ)的內(nèi)存數(shù)據(jù)庫需要物化大量中間結(jié)果，代價(jià)較大，MonetDB/X100采用了向量執(zhí)行(vectoriz

35、edexecution)技術(shù)，列存儲(chǔ)的表進(jìn)一步水平劃分為向量(vectors),一系列向量代表一個(gè)記錄組，查詢以向量為單位流水執(zhí)行以減少中間物化數(shù)據(jù)。(2) cache-oblivious優(yōu)化技術(shù)cache-conscious查詢優(yōu)化技術(shù)需要根據(jù)cache層數(shù)、各層cache大小、cacheline長度、TLB條目等硬件參數(shù)來優(yōu)化算法實(shí)現(xiàn)，對(duì)硬件平臺(tái)的特性依賴性較高。隨著硬件平臺(tái)越來越復(fù)雜，算法的性能調(diào)優(yōu)是一個(gè)困難的問題。與cache-conscious查詢優(yōu)化技術(shù)相對(duì)，cache-oblivious算法自動(dòng)優(yōu)化cache性能。cache-oblivious主要采用分而治之(divide-an

36、d-conquer)的方法將一個(gè)任務(wù)遞歸地劃分為一系列子任務(wù)，直到子任務(wù)能夠放入cache(3) page-coloring優(yōu)化技術(shù)page-coloring是一種內(nèi)存虛擬地址向cache地址映射的機(jī)制?，F(xiàn)代多核處理器通常采用多路組關(guān)聯(lián)cache。在這種地址映射機(jī)制下，物理地址被劃分為以page大小(4KB)為單位的地址段，稱為pagecolor。應(yīng)用程序使用的虛擬內(nèi)存地址被操作系統(tǒng)轉(zhuǎn)換為物理內(nèi)存地址，然后按照物理地址中的page-color位將每個(gè)page映射到cache中指定的區(qū)域，通過這種機(jī)制實(shí)現(xiàn)在物理地址與cache地址之間的快速轉(zhuǎn)換。在查詢優(yōu)化中，兩個(gè)具有不同數(shù)據(jù)局部性強(qiáng)度的查詢?nèi)蝿?wù)

37、(如一個(gè)數(shù)據(jù)局部性強(qiáng)度高的hash連接查詢和一個(gè)局部性強(qiáng)度低的索引連接查詢)在爭用共享cache時(shí)，大量的弱局部性數(shù)據(jù)會(huì)將強(qiáng)局部性數(shù)據(jù)驅(qū)逐出有限的caches,從而造成cache與內(nèi)存之間額外的數(shù)據(jù)交換。MCC-DB系統(tǒng)通過page-coloring技術(shù)為具有不同數(shù)據(jù)局部性強(qiáng)度的查詢?nèi)蝿?wù)分配不同的page-color,即對(duì)弱局部性查詢?nèi)蝿?wù)在基于page-c010r的內(nèi)存頁隊(duì)列中分配較少的color,使其查詢?nèi)蝿?wù)對(duì)應(yīng)cache中較少的地址范圍，而對(duì)強(qiáng)局部性查詢?nèi)蝿?wù)分配較多的color,使強(qiáng)局部性查詢?nèi)蝿?wù)能夠使用較大范圍的cache地址范圍，減少不同查詢?nèi)蝿?wù)在共享cache中的沖突。page-co

38、lor的數(shù)量與內(nèi)存地址空間大小具有比例關(guān)系，強(qiáng)局部性數(shù)據(jù)集通常較小但需要較多的page-color,占用較大的內(nèi)存地址范圍，而弱局部性數(shù)據(jù)集通常較大但只能分配較少的page-color,占用較少的內(nèi)存地址范圍。對(duì)于數(shù)據(jù)持久駐留內(nèi)存的內(nèi)存數(shù)據(jù)庫來說，較大的弱局部性數(shù)據(jù)集往往需要預(yù)先分配較大的內(nèi)存地址范圍，而較少的pagecolor對(duì)應(yīng)的地址范圍較小，難以滿足大數(shù)據(jù)集存儲(chǔ)的要求。為此，本章文獻(xiàn)16提出了W-order掃描技術(shù)，如圖15.8所示。該技術(shù)對(duì)于較大的弱局部性數(shù)據(jù)集不是按遞增地址的行式（Z-order）掃描，而是按page-c010r順序的列式掃描（W-order）。在每一個(gè)page-co

39、lor掃描階段，弱局部性數(shù)據(jù)集只與cache中相同page-color的數(shù)據(jù)頁產(chǎn)生cache爭用，與其他page-color的數(shù)據(jù)頁沒有cache沖突，從而降低了查詢處理過程的整體cache沖突。nn(XMX)ouoooo00.0-11.1000000(XJSTFTTTTTTpageculur1minoo,0*11.11000/1IA000001000-ll.J0-iL山"00.叫二11I山"A00(Mlpagecolorpagecolr內(nèi)存圖15.8Z-order掃描與W-order掃描除了對(duì)算法進(jìn)行改進(jìn)之外，T.M.Chilimbi等對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行了改進(jìn)，提出了一種ca

40、che敏感性數(shù)據(jù)結(jié)構(gòu)，其中使用了兩種數(shù)據(jù)存放技術(shù)：聚類（clustering）和染色（coloring）,優(yōu)化了cache性能。cache優(yōu)化技術(shù)是內(nèi)存數(shù)據(jù)庫重要但難以觸及的研究領(lǐng)域。主要因?yàn)閏ache管理是硬件級(jí)的技術(shù)。因此，數(shù)據(jù)庫領(lǐng)域內(nèi)cache優(yōu)化技術(shù)主要通過對(duì)數(shù)據(jù)在內(nèi)存中的存儲(chǔ)布局、訪問模式、數(shù)據(jù)結(jié)構(gòu)等方面的優(yōu)化來提高查詢處理過程中數(shù)據(jù)的cache命中率。對(duì)于涉及操作系統(tǒng)及處理器硬件方面的cache優(yōu)化技術(shù)的研究，需要數(shù)據(jù)庫、操作系統(tǒng)和硬件多個(gè)領(lǐng)域的同步發(fā)展才能取得預(yù)期效果。硬件平臺(tái)和硬件參數(shù)的不斷升級(jí)，與硬件結(jié)構(gòu)緊密綁定的hardware-conscious優(yōu)化技術(shù)也面臨很多優(yōu)化障礙

41、，hardware-oblivious的研究技術(shù)路線也逐漸成為數(shù)據(jù)庫界關(guān)注的問題。2 .索引技術(shù)索引是數(shù)據(jù)庫中提高查詢性能的有效方法，在磁盤數(shù)據(jù)庫中廣泛使用的hash索引、B+樹索引等不適合內(nèi)存數(shù)據(jù)庫的需求，所以一些針對(duì)內(nèi)存數(shù)據(jù)庫特性的索引得到了廣泛的研究。如圖15.9所示，AVL樹是一種內(nèi)存數(shù)據(jù)結(jié)構(gòu)，采用二叉樹搜索，索引性能較高。由于結(jié)點(diǎn)只存儲(chǔ)一個(gè)數(shù)據(jù)，因此存儲(chǔ)效率較低。數(shù)據(jù)庫的索引需要在結(jié)點(diǎn)內(nèi)存儲(chǔ)更多的數(shù)據(jù)以提高索引查找時(shí)的I/O或內(nèi)存訪問效率，典型的索引包括B+樹和T樹。B+樹是一種動(dòng)態(tài)平衡白多路查找樹，B+樹結(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)較多，存儲(chǔ)效率高，更新性能較好；B+樹層次較少，葉結(jié)點(diǎn)存儲(chǔ)實(shí)際數(shù)

42、據(jù)，從根結(jié)點(diǎn)到任意一個(gè)葉結(jié)點(diǎn)具有相同路徑長度。T樹是一種結(jié)點(diǎn)中包括多個(gè)碼值的平衡二叉樹，T樹既具有AVL樹的查找性能，又具有與B+樹相近的存儲(chǔ)效率和更新性能。但是，相對(duì)于B+樹的多路查找特性，T樹的二叉樹結(jié)構(gòu)增加了樹的高度，使查找的次數(shù)相對(duì)B+樹增加。AVI制惴點(diǎn)D*laCoirfinriJTLJDc?adF*nm!PtrRithiChildhrLeftChild%AVI第rw314印餐結(jié)點(diǎn)eoalHhlj/日胭TPw圖15.9AVL樹、B4W和T樹T樹與B樹各有優(yōu)缺點(diǎn)。在無并發(fā)訪問的情況下，T樹的性能優(yōu)于B+樹，主要原因是在不用加鎖解鎖的情況下，查找的主要開銷是碼值比較。B+樹在查找目標(biāo)碼值

43、的過程中需要在每個(gè)結(jié)點(diǎn)內(nèi)做二分查找；而T樹除了最后一個(gè)結(jié)點(diǎn)需要做二分查找外，其他結(jié)點(diǎn)只需要比較最大項(xiàng)和最小項(xiàng)。在有并發(fā)控制的情況下，由于T樹比B+樹高，在更新時(shí)涉及的結(jié)點(diǎn)較多，需要加鎖的結(jié)點(diǎn)也較多，所以并發(fā)的性能沒有樹好。為提高索引訪問時(shí)的cache效率，人們?cè)噲D將一個(gè)cacheline作為一個(gè)索引結(jié)點(diǎn)，提出了CSB樹和CST樹。CSB+W使用數(shù)組存儲(chǔ)子結(jié)點(diǎn)，結(jié)點(diǎn)中只存儲(chǔ)第一個(gè)子結(jié)點(diǎn)的指針，通過指針的偏移地址計(jì)算出其他子節(jié)點(diǎn)的地址，如圖15.10所示。圖15.10CSB+樹CST樹是一種面向cacheline大小而優(yōu)化設(shè)計(jì)的索引結(jié)構(gòu)。圖15.11(a)為原始T樹結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)包含若干數(shù)據(jù)。圖1

44、5.11(b)為對(duì)T樹創(chuàng)建的二叉搜索樹，搜索樹結(jié)點(diǎn)為T樹結(jié)點(diǎn)的最大值，用于快速檢索碼值所在的結(jié)點(diǎn)位置。圖15.11(c)顯示了CST樹的存儲(chǔ)結(jié)構(gòu)：根據(jù)cacheline大小(本例為32個(gè)字節(jié))確定基于數(shù)組存儲(chǔ)的二叉搜索子樹高度(例如，搜索樹結(jié)點(diǎn)寬度為4字節(jié)，一個(gè)cacheline中最多存儲(chǔ)7個(gè)結(jié)點(diǎn)，構(gòu)成一個(gè)三層二叉樹)：每個(gè)二叉搜索子樹構(gòu)成一個(gè)結(jié)點(diǎn)組，對(duì)應(yīng)7個(gè)T樹結(jié)點(diǎn)；結(jié)點(diǎn)組采用數(shù)組連續(xù)存儲(chǔ)，因此每個(gè)結(jié)點(diǎn)組只需要保存一個(gè)指向下級(jí)結(jié)點(diǎn)組首地址的指針即可。CST樹在查找時(shí)首先在結(jié)點(diǎn)組上進(jìn)行查找，確定查找碼值所在的結(jié)點(diǎn)，然后再訪問數(shù)據(jù)結(jié)點(diǎn)，查找是否存在指定碼值。154)«6nH*2MMS1

45、53IM2J72i924f站點(diǎn)置粉西"修自修15.11CST樹(128b?512玷點(diǎn)期連續(xù)It蛆存儲(chǔ).文結(jié)點(diǎn)只需要一個(gè)指針b)SIMD計(jì)算，因此基于SIMD的位圖連接索引能夠較好地發(fā)揮處理器數(shù)據(jù)并行處理能力和索引訪問性Judy是HP公司實(shí)現(xiàn)的一種專門針對(duì)cache特性而設(shè)計(jì)的內(nèi)存結(jié)構(gòu)，但若將其用作索引結(jié)構(gòu)，則具有不能支持重復(fù)值的存儲(chǔ)、范圍查找速度慢等缺點(diǎn)。欒華博士提出的J21是對(duì)Judy結(jié)構(gòu)的改進(jìn)。J刑使用葉結(jié)點(diǎn)存儲(chǔ)所有的碼值，內(nèi)部結(jié)點(diǎn)使用Judy來存儲(chǔ)。J刑的范圍查找、插入等操作的速度都優(yōu)于Judy且各方面的操作都優(yōu)于B+樹和T樹。cache-conscious索引技術(shù)主要以cac

46、heline大小作為結(jié)點(diǎn)大小的參照，通過數(shù)組連續(xù)存儲(chǔ)來壓縮指針空間，提高索引查找時(shí)cacheline的命中率。但基于數(shù)組連續(xù)存儲(chǔ)的cache-conscious索引結(jié)構(gòu)主要適合于只讀的分析型查詢應(yīng)用場景，當(dāng)有大量更新事務(wù)時(shí)，索引維護(hù)代價(jià)較高。30tHryw1103nm3asi114i帕inn«CW197Ltt2kfi2*7玉謫i)7WW1|fi78I3SL皿擲Ml2920MlJWlXflMS能，提高了連接性能。3 .面向多核的查詢處理技術(shù)在多核平臺(tái)上，查詢算法需要改寫為多核并行算法，將串行操作符并行化。在多核并行優(yōu)化時(shí)需要解決的關(guān)鍵技術(shù)包括并行處理時(shí)的共享cache優(yōu)化，數(shù)據(jù)分區(qū)優(yōu)化

47、等技術(shù)。StagedDB數(shù)據(jù)庫系統(tǒng)將數(shù)據(jù)庫的查詢處理過程分解為一系列處理階段，每個(gè)階段有獨(dú)立的任務(wù)隊(duì)列和處理線程，查詢?nèi)蝿?wù)被封裝并依次通過各階段的處理線程。StagedDB從查詢子任務(wù)的層次上對(duì)線程資源進(jìn)行全局優(yōu)化配置。多核并行優(yōu)化更多地采用分區(qū)并行處理技術(shù)，包括基于位置劃分(positionalpartition)的分區(qū)技術(shù)和基于hash劃分的分區(qū)技術(shù)等。圖15.12顯示了當(dāng)前內(nèi)存數(shù)據(jù)庫主要采用的三種多核并行hash連接技術(shù)。huh表(構(gòu)建皿h表2Xh探博I構(gòu)建ha福表2hashffH(a)hash逢接(bj圮分區(qū)bash連接每分區(qū)一個(gè)"h表Ipan2種，huh衣3"sh

48、保律1p*n封基小區(qū)的hi聞1近接修分區(qū)一個(gè)ha&hAE(d)Rddixhn曲連接圖15.12多核并行HAS旌接算法(1)無分區(qū)(nopartitioning)hash連接算法。該算法對(duì)連接表R并行掃描，創(chuàng)建共享的hash表，各個(gè)掃描線程并發(fā)地向共享hash表中插入hash記錄。S表同樣采用并行掃描，每個(gè)掃描線程獨(dú)立地向共享hash表進(jìn)行hash探測，完成hash連接操作。共享hash表在創(chuàng)建階段產(chǎn)生較大的hash表訪問并發(fā)控制代價(jià)，共享的hash表較大時(shí)會(huì)超出cache容量，從而在hash探測階段也會(huì)產(chǎn)生較多的cache失效。但是，R表和S表沒有進(jìn)行物理分區(qū)，因此節(jié)省了分區(qū)所產(chǎn)生的存

49、儲(chǔ)和計(jì)算代價(jià)。(2)基于分區(qū)(partitioned)的hash連接算法。該算法對(duì)R表和S表按相同的hash函數(shù)進(jìn)行分區(qū)，R表的每個(gè)分區(qū)創(chuàng)建獨(dú)立的hash表，S表選擇對(duì)應(yīng)的分區(qū)與R表白hhash表進(jìn)行連接操作。3 3)radixhash連接算法。該算法通過radix分區(qū)技術(shù)減少R表和S表在分區(qū)過程中所產(chǎn)生的cache失效和TLB失效，通過radix多趟劃分創(chuàng)建分區(qū)，然后創(chuàng)建獨(dú)立的hash表，完成基于R表和S表分區(qū)的并行hash連接操作?；诜謪^(qū)的hash連接操作在分區(qū)階段需要較大的空間和時(shí)間代價(jià)，但分區(qū)后的hash連接能夠滿足hash表小于cache容量的要求，使得在hash探測階段獲得較好的

50、性能。當(dāng)前研究表明，當(dāng)R表相對(duì)于S表較小時(shí)，簡單的無分區(qū)hash連接算法在當(dāng)前多核處理器平臺(tái)上能夠獲得較好的性能，而當(dāng)R表和S表較大時(shí)，基于radix分區(qū)的hash連接算法能夠獲得更高的性能。分區(qū)技術(shù)對(duì)于多核并行聚集計(jì)算有類似的結(jié)論。4 .面向眾核的查詢處理技術(shù)多核處理器逐漸進(jìn)入眾核時(shí)代。目前Intel最新的通用處理器集成了15個(gè)核心(core),支持30個(gè)物理線程；眾核架構(gòu)的IntelXeonPhi協(xié)處理器集成了61個(gè)內(nèi)核，244個(gè)物理線程；而NVIDA的TeslaK40集成了2880個(gè)核心。如圖15.13所示，CPU的計(jì)算單元較少，控制單元較多，支持復(fù)雜的預(yù)取、分支預(yù)測、亂序指令執(zhí)行等功能

51、，通過較大的cache容量掩蓋內(nèi)存訪問延遲。而GPU擁有眾多的計(jì)算單元，控制單元較少，功能相對(duì)簡單，主要依賴單指令多線程(SingleInstructionMultipleThread,SIMT)技術(shù)通過零切換代價(jià)的硬件級(jí)線程來掩蓋內(nèi)存訪問延遲。AMD的加速處理器(acceleratedprocessingunits,APU)將CPU和GPU集成在一個(gè)芯片中，實(shí)現(xiàn)GPU和CPU對(duì)整體內(nèi)存空間的相互可見并能同時(shí)訪問。當(dāng)前最新的APU中集成了超過500個(gè)流處理器(如AMD公司的A10-7850K包含4個(gè)CPU核心和8個(gè)GCN圖形單元，512個(gè)流處理器)，將多核平臺(tái)擴(kuò)展為眾核平臺(tái)。CPU圖15.13

52、CPU與GPU吉構(gòu)圖內(nèi)存數(shù)據(jù)庫面臨越來越多的計(jì)算核心，查詢算法需要進(jìn)化為高可擴(kuò)展并行算法，以充分利用先進(jìn)眾核處理器提供的強(qiáng)大并行計(jì)算性能。當(dāng)前眾核平臺(tái)上的數(shù)據(jù)庫研究主要集中在NVIDAGPU平臺(tái)和APU平臺(tái)上，IntelPhi協(xié)處理器平臺(tái)也將成為內(nèi)存數(shù)據(jù)庫新的眾核計(jì)算平臺(tái)。當(dāng)前GPU和APU平臺(tái)上的數(shù)據(jù)庫技術(shù)研究需要解決的關(guān)鍵問題有GPU數(shù)據(jù)庫存儲(chǔ)模型，GPU與內(nèi)存之間的數(shù)據(jù)傳輸優(yōu)化技術(shù)，GPU上的索引技術(shù)，GPU數(shù)據(jù)壓縮技術(shù)，GPU關(guān)系操作算法，GPU和CPU協(xié)同計(jì)算技術(shù)等。相對(duì)于內(nèi)存數(shù)據(jù)庫消除的I/O瓶頸，當(dāng)前GPU數(shù)據(jù)庫面臨PCIe通道新的數(shù)據(jù)傳輸瓶頸。而新一代的APU和Phi協(xié)處理器技

53、術(shù)開始支持協(xié)處理器核心與CPU核心訪問相同的內(nèi)存地址空間，將減少數(shù)據(jù)傳輸瓶頸，為強(qiáng)大的眾核并行計(jì)算核心提供充足的數(shù)據(jù)供給。數(shù)據(jù)庫采用以存儲(chǔ)為中心的設(shè)計(jì)思想，內(nèi)存數(shù)據(jù)庫的優(yōu)化技術(shù)也一直以內(nèi)存數(shù)據(jù)訪問優(yōu)化為核心?，F(xiàn)代多核處理器和協(xié)處理器能夠提供強(qiáng)大的并行計(jì)算能力，多通道內(nèi)存數(shù)據(jù)訪問技術(shù)和多核并行查詢處理技術(shù)推動(dòng)內(nèi)存數(shù)據(jù)庫進(jìn)入并行計(jì)算時(shí)代，內(nèi)存數(shù)據(jù)庫的存儲(chǔ)訪問優(yōu)化及查詢優(yōu)化需要面向新的高并行計(jì)算平臺(tái)進(jìn)行全面的優(yōu)化設(shè)計(jì)，以多核/眾核計(jì)算為核心的內(nèi)存數(shù)據(jù)庫設(shè)計(jì)思想將成為數(shù)據(jù)庫發(fā)展的新趨勢。15.4.3并發(fā)與恢復(fù)1 .并發(fā)控制內(nèi)存數(shù)據(jù)庫與磁盤數(shù)據(jù)庫的并發(fā)控制機(jī)制類似，細(xì)節(jié)上存在一定差異。由于數(shù)據(jù)存儲(chǔ)在內(nèi)存

54、中，內(nèi)存數(shù)據(jù)庫中的事務(wù)執(zhí)行時(shí)間一般較短，因此持鎖時(shí)間也較短，系統(tǒng)中沖突較少，所以可以采用以下方法減少鎖的開銷：采用較大的封鎖粒度（如表級(jí)鎖）：采用樂觀加鎖方式；減少鎖的類型；將鎖信息存儲(chǔ)在數(shù)據(jù)本身。對(duì)于內(nèi)存數(shù)據(jù)來說，封鎖產(chǎn)生的CPU代價(jià)會(huì)對(duì)性能產(chǎn)生嚴(yán)重的影響，特別是對(duì)于工作負(fù)載主要由短小事務(wù)構(gòu)成的OLTP應(yīng)用場合，每個(gè)事務(wù)要求極短的響應(yīng)時(shí)間，在幾十毫秒甚至微秒之內(nèi)完成。針對(duì)此問題，S.Blott等提出了接近串行的并發(fā)控制協(xié)議（almostserialprotocol）o該協(xié)議的特點(diǎn)是，寫事務(wù)在整個(gè)數(shù)據(jù)庫上施加互斥鎖（mutex）,通過時(shí)間戳和互斥鎖在事務(wù)的提交記錄沒有到達(dá)磁盤之前允許新事務(wù)開始

55、，并且保證任何提交的讀事務(wù)不會(huì)讀到未提交的數(shù)據(jù)。并發(fā)控制會(huì)帶來一些系統(tǒng)代價(jià)，如CPU代價(jià)、存儲(chǔ)代價(jià)等，影響系統(tǒng)性能。而內(nèi)存數(shù)據(jù)庫對(duì)性能要求非常高，所以利用內(nèi)存優(yōu)勢，結(jié)合內(nèi)存數(shù)據(jù)庫的應(yīng)用需求，在保證事務(wù)ACID特性的同時(shí)，盡量減少并發(fā)控制對(duì)性能的影響是需要進(jìn)一步研究的問題。內(nèi)存數(shù)據(jù)庫擺脫了I/O延遲之后，內(nèi)存訪問速度得到極大的提升，在新興的非易失性內(nèi)存，如PCM等技術(shù)支持下，內(nèi)存計(jì)算和更新的速度進(jìn)一步提升。事務(wù)型內(nèi)存數(shù)據(jù)庫的一個(gè)技術(shù)發(fā)展趨勢是將事務(wù)串行化，簡化并發(fā)控制機(jī)制，提高內(nèi)存數(shù)據(jù)庫代碼執(zhí)行效率，使串行處理性能能夠滿足高吞吐性能需求。分析型內(nèi)存數(shù)據(jù)庫則將計(jì)算最大化并行，以提高多核處理器的并行

56、計(jì)算效率，提高應(yīng)對(duì)內(nèi)存大數(shù)據(jù)實(shí)時(shí)分析處理的性能需求。對(duì)于事務(wù)型內(nèi)存數(shù)據(jù)庫，全局性資源比分析型內(nèi)存數(shù)據(jù)庫多，全局性資源包括緩沖區(qū)、鎖表和日志等。研究表明，CPU大約花費(fèi)90%的時(shí)間用于處理緩沖區(qū)管理、加鎖、閂鎖（latch）和日志記錄等任務(wù)。在多核處理器平臺(tái)上，內(nèi)存數(shù)據(jù)庫需要對(duì)緩沖區(qū)管理、日志、鎖表等原來串行處理的機(jī)制進(jìn)行并行化改造才能減少對(duì)共享資源的排他性爭用所導(dǎo)致的處理效率降低的問題。多核優(yōu)化技術(shù)包括對(duì)鎖表進(jìn)行分區(qū)、增加并行日志隊(duì)列、緩沖區(qū)多路訪問等。Hyper是一種混合事務(wù)型與分析型負(fù)載的內(nèi)存數(shù)據(jù)庫系統(tǒng)，它采用了串行事務(wù)處理機(jī)制，即將所有的事務(wù)組織為存儲(chǔ)過程序列，借助于內(nèi)存數(shù)據(jù)庫的高性能串行處理，消除對(duì)數(shù)據(jù)對(duì)象加鎖和加閂（lock和latch）的代價(jià)，簡化內(nèi)存數(shù)據(jù)庫查詢處理引擎設(shè)計(jì)。VoltDB（原H-store）數(shù)據(jù)庫由大量分散在多個(gè)結(jié)點(diǎn)（服務(wù)器）上的數(shù)據(jù)分區(qū)組成。每個(gè)站點(diǎn)都