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

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

3、據(jù)庫與磁盤數(shù)據(jù)庫的區(qū)別如圖15.1所示。處理界卷內(nèi)存內(nèi)存收鬻庫表和索弓1索引*W二彩時文好W后ftfrtt圖15.1內(nèi)存數(shù)據(jù)序和磁盤數(shù)據(jù)庫對比示意圖內(nèi)存數(shù)據(jù)庫中的數(shù)據(jù)常駐內(nèi)存，消除了磁盤數(shù)據(jù)庫中巨大的輸入/輸出代價。同時，數(shù)據(jù)的存儲和訪問算法以內(nèi)存訪問特性為基礎，實現(xiàn)處理器對數(shù)據(jù)的直接訪問，在算法和代碼效率上高于以磁盤輸入/輸出為基礎的磁盤數(shù)據(jù)庫。在內(nèi)存數(shù)據(jù)庫中，使用針對內(nèi)存特性進行優(yōu)化的存儲結(jié)構(gòu)、索引結(jié)構(gòu)和操作算法進一步優(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世紀60年代末就出

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

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

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

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

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

9、提高，動態(tài)隨機存取存儲器(DRAM)的容量越來越大、價格越來越低，這些無疑為計算機內(nèi)存的不斷擴大提供了硬件基礎，使得內(nèi)存數(shù)據(jù)庫的技術在可行性和成本的合理化方面逐步成熟。一些公司陸續(xù)推出了不同的內(nèi)存數(shù)據(jù)庫產(chǎn)品。1994年，美國OSE公司推出了第一個商業(yè)化的、開始實際應用的內(nèi)存數(shù)據(jù)庫產(chǎn)品Polyhedra。1996年，TimesTen公司成立并推出第一個商業(yè)版內(nèi)存數(shù)據(jù)庫TimesTen2.0,2005年該公司被Oracle公司收購。1998年，德國SoftwareAG公司推出了內(nèi)存數(shù)據(jù)庫TaminoDatabase。1999年，日本UBIT會社開發(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研究院研制了基于列存儲模型的內(nèi)存數(shù)據(jù)庫MonetDB34,其后又研制了基于向量處理技術的MonetDB/X100系統(tǒng)，2008年推出其商業(yè)化版本Vectorwise。2010年Ingres公司和CW1研究院合作推出了VectorWise1.0版。2011年3月VectorWise1.5版獲得了TPC-H100GB數(shù)據(jù)量測試的第一名，當前仍然是TPC

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、優(yōu)化I/O代價，現(xiàn)代CPU使用硬件級的多級cache機制優(yōu)化cache機制來完成，采用類LRU(最近最少訪問)替內(nèi)存訪問，內(nèi)存數(shù)據(jù)庫的內(nèi)存訪問優(yōu)化由硬件級的換算法實現(xiàn)cache中的數(shù)據(jù)管理。圖15.6顯示了當前多核CPU中的多級cache機制，每個核心擁有32KB的L1數(shù)據(jù)cache和32KB的L1指令cache,256KB的L2cache和共享L3cache。多核處理器的性能與內(nèi)核數(shù)量和共享L3cache容量密切相關。圖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中的多級cache機制多核CPU的發(fā)展趨勢是最后一級cache(LastLevelCache,LLC海量隨核數(shù)增加而增大，LLC大小是cache性能的一個重要指標。CPU處理的是cache中的數(shù)據(jù)，若CPU需要的數(shù)據(jù)不在cache中，會導致cache失效，此時CPU需要等待數(shù)據(jù)從內(nèi)存中讀取，因此會延長數(shù)據(jù)的處理時間。研究表明數(shù)據(jù)庫在現(xiàn)代處理器中進行查詢處理時，有大約一半的時間花費在各種延遲上。其中大約20%的延遲是由于一些實現(xiàn)細節(jié)(

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

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

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

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

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

34、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)針對列存儲的內(nèi)存數(shù)據(jù)庫需要物化大量中間結(jié)果，代價較大，MonetDB/X100采用了向量執(zhí)行(vectoriz

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

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

37、(如一個數(shù)據(jù)局部性強度高的hash連接查詢和一個局部性強度低的索引連接查詢)在爭用共享cache時，大量的弱局部性數(shù)據(jù)會將強局部性數(shù)據(jù)驅(qū)逐出有限的caches,從而造成cache與內(nèi)存之間額外的數(shù)據(jù)交換。MCC-DB系統(tǒng)通過page-coloring技術為具有不同數(shù)據(jù)局部性強度的查詢?nèi)蝿辗峙洳煌膒age-color,即對弱局部性查詢?nèi)蝿赵诨趐age-c010r的內(nèi)存頁隊列中分配較少的color,使其查詢?nèi)蝿諏猚ache中較少的地址范圍，而對強局部性查詢?nèi)蝿辗峙漭^多的color,使強局部性查詢?nèi)蝿漳軌蚴褂幂^大范圍的cache地址范圍，減少不同查詢?nèi)蝿赵诠蚕韈ache中的沖突。page-co

38、lor的數(shù)量與內(nèi)存地址空間大小具有比例關系，強局部性數(shù)據(jù)集通常較小但需要較多的page-color,占用較大的內(nèi)存地址范圍，而弱局部性數(shù)據(jù)集通常較大但只能分配較少的page-color,占用較少的內(nèi)存地址范圍。對于數(shù)據(jù)持久駐留內(nèi)存的內(nèi)存數(shù)據(jù)庫來說，較大的弱局部性數(shù)據(jù)集往往需要預先分配較大的內(nèi)存地址范圍，而較少的pagecolor對應的地址范圍較小，難以滿足大數(shù)據(jù)集存儲的要求。為此，本章文獻16提出了W-order掃描技術，如圖15.8所示。該技術對于較大的弱局部性數(shù)據(jù)集不是按遞增地址的行式（Z-order）掃描，而是按page-c010r順序的列式掃描（W-order）。在每一個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掃描除了對算法進行改進之外，T.M.Chilimbi等對數(shù)據(jù)結(jié)構(gòu)進行了改進，提出了一種ca

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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