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

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

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

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

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

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

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

8、線程數量可以為多個，并使用隊列結構與其他線程連接。TPK的多線程內存數據庫技術實現了一種多階段的查詢處理技術。1990年，普林斯頓大學又設計出SystemM內存數據庫。SystemM由一系列操作服務線程構成，包括消息服務線程、事務服務線程、日志服務線程和檢查點服務線程等。SystemM可以支持并發查詢服務線程，但仍然要控制活動事務服務線程的數量。3 .內存數據庫的產品成長期隨著互聯網的發展，越來越多的網絡應用需要高性能、高并發的數據庫系統支撐，傳統企業級的數據庫應用，如電信、金融等領域同樣需要高性能的實時數據庫系統。應用需求催生了內存數據庫市場。在硬件方面，半導體技術快速發展，內存存儲密度不斷

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

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

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

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

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

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

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

16、優化技術。（3）硬件相關性內存數據庫的性能受硬件特性的直接影響。計算機硬件技術的發展主要體現在高端計算設備和存儲設備上，如多核處理器、眾核協處理器（ManyIntegratedCore,MIC）、通用GPU、PCM存儲（PhaseChangeMemory,相變存儲）、固態硬盤（SolidStateDisk,SSD存儲等。這些計算能力和存儲性能的提升有助于內存吞吐率需求的提升（眾核技術）、提高內存持久存儲能力（PCM技術）或為內存提供二級存儲（SSD技術）。硬件技術在多核及眾核處理器、高性能存儲和高速網絡等方面的發展為內存數據庫提供了高并行處理、高性能存儲訪問以及高速連通的硬件平臺。內存數據庫的

17、設計應該充分考慮并有效利用由新硬件技術帶來的功能擴展和性能提高。15.4 內存數據庫的關鍵技術由于內存數據庫上述的特點，磁盤數據庫實現中的相關技術在內存數據庫中不能照搬使用。通用的內存數據庫管理系統要為用戶提供SQL接口，具有內存存儲管理、面向內存的查詢處理和優化等基本模塊，還應提供多用戶的并發控制、事務管理和訪問控制，能夠保證數據庫的完整性和安全性，在內存數據庫出現故障時能夠對系統進行恢復。內存數據庫作為處理器直接訪問的數據管理系統，需要研究自底向上的面向內存和多核并行處理的系統框架和新的實現技術。下面簡要介紹內存數據庫中的若干關鍵技術。15.4.1 數據存儲數據庫的數據存儲一般有行存儲模型

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

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

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

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

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

23、0RuiMildN«bbLWeik1511SvnqyMildNanml號Eje19OcmsMildS1ZK»£341)35cmalHusNohihlIW'nk14RunMildHiKbimEPtaklMin»7MoM5圖15.3DataPack存儲機制OracleExadata采用了一種CompressionUnit的混合列壓縮技術，簡稱為CU。CU對列存儲進行分段,并在分段內通過壓縮技術組織不同列的混合數據塊存儲，如圖15.4所示。CompressionUnit圖15.4CompressionUnit存儲機制在結構化內存數據庫技術發展的同時，基

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

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

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

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

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

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

30、究的重要課題。另一個與內存訪問延遲密切相關的硬件是TLB(TranslationLookasideBuffer)旁路轉換緩沖，或稱為頁表緩沖)。TLB是硬件級緩存，與CPU的cache類似，主要用來存放內存頁表。在內存的頁表區里，記錄虛擬頁面和物理頁框對應關系的記錄稱為一個頁表條目(entry)。在TLB里緩存了一些頁表條目。當CPU執行機構收到應用程序發來的虛擬地址后，首先到TLB中查找相應的頁表數據，如果TLB中正好存放著所需的頁表，則稱為TLB命中(TLBhit)。接下來CPU依次查看TLB中頁表所對應的物理內存地址中的數據是不是已經在一級、二級緩存里了，如果不存在則為TLBmiss,需

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

32、優化技術主要包括以下幾類。(1) cache-conscious優化技術cache-conscious優化技術以hash連接優化為代表。在hash連接中，內層的hash表大小決定了hash探測過程中能否盡可能多地從高速cache中訪問hash表。為提高hash探測時的cache命中率，需要將hash表劃分為小于cache容量的較小的分區，從而使hash探測時的cache命中率提高。基于分區的hash連接算法需要將連接表L和R根據連接屬性的取值，按相同的hash函數進行hash分區，當連接表L和R較大時，關系表需要劃分為數量較多的分區以保證每個分區的數據量小于cache容量，而較多的分區導致數據

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

34、sh連接時的cache性能。基于分區的兩削基數分區(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)針對列存儲的內存數據庫需要物化大量中間結果，代價較大，MonetDB/X100采用了向量執行(vectoriz

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

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

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

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

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

40、che敏感性數據結構，其中使用了兩種數據存放技術：聚類（clustering）和染色（coloring）,優化了cache性能。cache優化技術是內存數據庫重要但難以觸及的研究領域。主要因為cache管理是硬件級的技術。因此，數據庫領域內cache優化技術主要通過對數據在內存中的存儲布局、訪問模式、數據結構等方面的優化來提高查詢處理過程中數據的cache命中率。對于涉及操作系統及處理器硬件方面的cache優化技術的研究，需要數據庫、操作系統和硬件多個領域的同步發展才能取得預期效果。硬件平臺和硬件參數的不斷升級，與硬件結構緊密綁定的hardware-conscious優化技術也面臨很多優化障礙

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

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

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

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

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

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

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

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

49、儲和計算代價。(2)基于分區(partitioned)的hash連接算法。該算法對R表和S表按相同的hash函數進行分區，R表的每個分區創建獨立的hash表，S表選擇對應的分區與R表白hhash表進行連接操作。3 3)radixhash連接算法。該算法通過radix分區技術減少R表和S表在分區過程中所產生的cache失效和TLB失效，通過radix多趟劃分創建分區，然后創建獨立的hash表，完成基于R表和S表分區的并行hash連接操作。基于分區的hash連接操作在分區階段需要較大的空間和時間代價，但分區后的hash連接能夠滿足hash表小于cache容量的要求，使得在hash探測階段獲得較好的

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

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

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

53、術開始支持協處理器核心與CPU核心訪問相同的內存地址空間，將減少數據傳輸瓶頸，為強大的眾核并行計算核心提供充足的數據供給。數據庫采用以存儲為中心的設計思想，內存數據庫的優化技術也一直以內存數據訪問優化為核心。現代多核處理器和協處理器能夠提供強大的并行計算能力，多通道內存數據訪問技術和多核并行查詢處理技術推動內存數據庫進入并行計算時代，內存數據庫的存儲訪問優化及查詢優化需要面向新的高并行計算平臺進行全面的優化設計，以多核/眾核計算為核心的內存數據庫設計思想將成為數據庫發展的新趨勢。15.4.3并發與恢復1 .并發控制內存數據庫與磁盤數據庫的并發控制機制類似，細節上存在一定差異。由于數據存儲在內存

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

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

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