面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展

面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第1頁。摘要：面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第1頁。關(guān)鍵詞：大數(shù)據(jù);并發(fā)索引結(jié)構(gòu);新型硬件1引言隨著互聯(lián)網(wǎng)技術(shù)和相關(guān)應用的蓬勃發(fā)展，全球已進入大數(shù)據(jù)時代。國際數(shù)據(jù)公司（InternationalDataCorporation，IDC）在2018年的調(diào)研報告中指出，全球數(shù)據(jù)正在以指數(shù)級的速率增長，如圖1所示，2019年全球產(chǎn)生的數(shù)據(jù)約為40ZB，到2025年全球?qū)a(chǎn)生175ZB的數(shù)據(jù)。在大數(shù)據(jù)時代，利用大數(shù)據(jù)進行處理與預測的應用變得越來越普遍，這些應用在人們生活中占有舉足輕重的地位，比如人們可以基于大數(shù)據(jù)對城市交通擁堵情況進行有效的判斷和防治。然而，大數(shù)據(jù)應用也正面臨著數(shù)據(jù)爆炸帶來的挑戰(zhàn)，Netflix公司2018年的報告顯示，該公司每天處理的數(shù)據(jù)量已達到12PB，這對于其流處理系統(tǒng)而言是一個極大的挑戰(zhàn)。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第2頁。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第2頁。圖1

每年全球數(shù)據(jù)量的增長

由于數(shù)據(jù)的爆發(fā)式增長會顯著影響大數(shù)據(jù)應用的檢索和處理效率，因此該問題得到了學術(shù)界和工業(yè)界的廣泛關(guān)注。在大數(shù)據(jù)領(lǐng)域，基于高效的索引結(jié)構(gòu)保證數(shù)據(jù)處理和檢索的效率是一種通用的解決方案，如MySQL聚簇索引和輔助索引均使用B+tree索引結(jié)構(gòu)保證數(shù)據(jù)庫條目訪問的效率，并基于該結(jié)構(gòu)提供順序遍歷等高效的操作；Microsoft公司的SQLServer數(shù)據(jù)庫將Hash表作為數(shù)據(jù)表的縮影，從而加快處理速度。除了數(shù)據(jù)量的增長外，大數(shù)據(jù)系統(tǒng)面臨著大量用戶同時訪問系統(tǒng)的情況。例如，在2017年的阿里巴巴“天貓雙十一”活動中，阿里云系統(tǒng)每秒需要處理數(shù)百萬次的交易操作。為了更好地支持并發(fā)訪問，索引結(jié)構(gòu)往往需要一定的機制保護其數(shù)據(jù)結(jié)構(gòu)的正確性，即支持高并發(fā)訪問，該種結(jié)構(gòu)被稱為并發(fā)索引結(jié)構(gòu)。并發(fā)索引結(jié)構(gòu)在各類大數(shù)據(jù)系統(tǒng)中被廣泛使用，已成為各種大數(shù)據(jù)系統(tǒng)的核心模塊，因此系統(tǒng)中的并發(fā)索引結(jié)構(gòu)性能的優(yōu)劣將直接影響這些系統(tǒng)的效率。隨著數(shù)據(jù)量的激增和并發(fā)訪問量的增多，并發(fā)索引結(jié)構(gòu)正面臨著諸多挑戰(zhàn)。這些挑戰(zhàn)可以被分為兩方面：其一，用于保護索引結(jié)構(gòu)的并發(fā)控制機制是決定索引數(shù)據(jù)結(jié)構(gòu)正確性和處理效率的關(guān)鍵因素，經(jīng)典的保護機制已經(jīng)無法滿足編程人員對易用性和用戶對性能的要求，因此設(shè)計更為高效的并發(fā)控制機制變得越來越重要；其二，傳統(tǒng)基于CPU的大數(shù)據(jù)系統(tǒng)由于計算能力的限制已經(jīng)無法滿足用戶對高性能處理的需求，層出不窮的新硬件技術(shù)為并發(fā)索引結(jié)面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第3頁。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第3頁。本文結(jié)合并發(fā)索引數(shù)據(jù)結(jié)構(gòu)面臨的各項挑戰(zhàn)，針對大數(shù)據(jù)時代對并發(fā)性能的要求，從并發(fā)控制技術(shù)和基于新型硬件的性能優(yōu)化兩個方面對現(xiàn)有的工作進行了總結(jié)與討論。

2背景數(shù)據(jù)存儲體量指數(shù)式的增長給大數(shù)據(jù)系統(tǒng)帶來了挑戰(zhàn)，如何高效地檢索和處理數(shù)據(jù)以滿足用戶的需求，成為大數(shù)據(jù)系統(tǒng)領(lǐng)域的一個關(guān)鍵問題。并發(fā)索引數(shù)據(jù)結(jié)構(gòu)作為一種能夠有效組織底層數(shù)據(jù)以提供高效操作的方案，為解決該問題提供了可能。2.1正確性與易用性數(shù)據(jù)的爆發(fā)同時也帶來了用戶數(shù)量的飛速增長。據(jù)GlobalDigital公司的數(shù)據(jù)統(tǒng)計，2018年已經(jīng)有超過40億的用戶使用互聯(lián)網(wǎng)，越來越多的人依賴于從大數(shù)據(jù)應用中得到個性化信息，方便自己的生活。隨著在線用戶的持續(xù)增加，大數(shù)據(jù)系統(tǒng)不僅要面對底層數(shù)據(jù)體量持續(xù)增大的挑戰(zhàn)，同時也要面對用戶的日益增長對并發(fā)訪問效率造成的挑戰(zhàn)。因此，日益增加的數(shù)據(jù)存儲量和并發(fā)訪問量給并發(fā)索引結(jié)構(gòu)帶來了嚴峻的挑戰(zhàn)。在高并發(fā)訪問操作中保證結(jié)果的正確性和不同并發(fā)操作的可串行性是高并發(fā)大數(shù)據(jù)系統(tǒng)中至關(guān)重要的問題。傳統(tǒng)的基于鎖的并發(fā)保護策略在同步時可能存在死鎖、活鎖、優(yōu)先級反轉(zhuǎn)和并行度不足等潛在問題。另外，為實現(xiàn)一個高效且正確的鎖控制策略，需要大量富有經(jīng)驗面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第4頁。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第4頁。2.2各類新型硬件基于經(jīng)典硬件的并發(fā)索引結(jié)構(gòu)系統(tǒng)提供的處理效率和并發(fā)能力有限，這成為限制大數(shù)據(jù)系統(tǒng)提供高效服務(wù)的瓶頸。隨著新型硬件技術(shù)的快速發(fā)展，各種新型硬件層出不窮，如硬件事務(wù)性內(nèi)存（hardwaretransactionalmemory，HTM）、遠程直接內(nèi)存訪問（remotedirectmemoryaccess，RDMA）、圖形處理器（graphicsprocessingunit，GPU）和現(xiàn)場可編程門陣列（field-programmablegatearray，F(xiàn)PGA）等。這些新型硬件為解決該問題提供了潛在可行的處理方案。這些新型硬件具有各不相同的用途及特點。充分地理解和利用這些特點，從而對并發(fā)索引結(jié)構(gòu)進行優(yōu)化，才能取得理想的性能。如在GPU中，雖然存在大量的并發(fā)線程，但是由于其體系結(jié)構(gòu)與CPU差異較大，因此在數(shù)據(jù)結(jié)構(gòu)訪問時需要避免亂序的訪存或執(zhí)行分歧等問題，這樣才能獲得理想的加速效果。再如HTM，它能夠為程序提供堪比細粒度鎖的高效硬件同步機制，減少不必要的鎖開銷，并簡化用戶的編程復雜度。然而，英特爾公司設(shè)計的RTM（一種HTM的具體實現(xiàn)）中存在許多限制條件，如事務(wù)內(nèi)存（transactionalmemory，TM）中處理的工作集大小是有限的，TM中無法支持I/O操作等。這些問題對并發(fā)索引結(jié)構(gòu)的設(shè)計提出了更高的要求?；趥鹘y(tǒng)的并發(fā)索引結(jié)構(gòu)經(jīng)過多年的發(fā)展，已經(jīng)與傳統(tǒng)硬件耦合嚴重，僅僅將傳統(tǒng)的并發(fā)索引結(jié)構(gòu)移植到新型硬件平臺上是難以獲得理想的處理效果的。因此，如何基于新型硬件的特面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第5頁。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第5頁。2.3各類應用場景針對并發(fā)索引結(jié)構(gòu)對數(shù)據(jù)更新實時性的要求，可將其應用場景分為兩大類：支持并發(fā)操作的場景和支持批更新處理的場景。并發(fā)索引數(shù)據(jù)結(jié)構(gòu)應用場景的不同導致其設(shè)計的側(cè)重點存在一定的差異。在支持并發(fā)操作的應用場景中，大量用戶并發(fā)地訪問和更新底層數(shù)據(jù)，用戶對數(shù)據(jù)的操作需要及時地更新在底層的數(shù)據(jù)結(jié)構(gòu)上。為了支持該應用場景的需求，并發(fā)索引數(shù)據(jù)結(jié)構(gòu)需要使用并發(fā)控制策略（如各種同步機制）來協(xié)調(diào)同時執(zhí)行的數(shù)據(jù)讀取操作和數(shù)據(jù)更新操作。這些同步機制給并發(fā)索引結(jié)構(gòu)的執(zhí)行帶來了顯著的開銷，也影響著整體系統(tǒng)的性能和復雜度。因此，在支持并發(fā)操作的應用場景中，編程者將設(shè)計的重點聚焦于兩方面：其一，如何設(shè)計一種完善的并發(fā)控制策略以保證并發(fā)訪問的正確性，如常見的鎖機制、無鎖機制和事務(wù)內(nèi)存機制等；其二，如何設(shè)計一些策略保證并發(fā)索引結(jié)構(gòu)在復雜的高并發(fā)環(huán)境下的性能。對于一些對數(shù)據(jù)更新實時性不是十分敏感的應用場景而言，如搜索引擎中的后端網(wǎng)頁庫，批處理更新是一種高效的處理方式。在該場景中用戶對索引結(jié)構(gòu)的更新操作可以被延遲至一定的階段統(tǒng)一處理，并且可以將讀取與更新操作相互分離，以簡化兩者之間的同步帶來的額外開銷，該應用場景主要應用于在線分析處理（on-lineanalyticalprocessing，OLAP）、決策和數(shù)據(jù)挖掘等系統(tǒng)中。在此類應用場景中，用戶對于查詢的性能更為敏感，因此該場景下設(shè)計的側(cè)重點主要是如何提升并發(fā)索引結(jié)構(gòu)的查詢效率。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第6頁。3面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第6頁。并發(fā)索引結(jié)構(gòu)可以對系統(tǒng)底層數(shù)據(jù)進行有效的組織，以提供高效的處理操作，它能夠有效地應對數(shù)據(jù)量和用戶數(shù)量的增長帶來的挑戰(zhàn)，并且在不同的索引結(jié)構(gòu)應用場景和不同的硬件平臺上均被廣泛使用。然而，為了更好地服務(wù)用戶（編程人員和系統(tǒng)使用者），提供簡單且高效的并發(fā)控制技術(shù)存在一定的必要性。為了應對大數(shù)據(jù)時代的挑戰(zhàn)，設(shè)計一種高效且簡單的并發(fā)控制策略來保證并發(fā)執(zhí)行的正確性，成為一個普遍熱門的問題。針對不同并發(fā)的應用場景，可將并發(fā)控制策略研究與實踐的成果分為三大類：基于鎖的并發(fā)策略、基于無鎖的并發(fā)策略、基于事務(wù)內(nèi)存的并發(fā)策略。另外，還有一些專門針對批更新處理場景的并發(fā)控制策略。這些不同的并發(fā)策略具有不同的特點，不同的應用場景和硬件平臺需要結(jié)合其自身特點選擇合適的策略。本節(jié)將依次介紹這4種更新策略的研究現(xiàn)狀。3.1基于鎖的并發(fā)策略使用基于鎖的并發(fā)控制策略保證系統(tǒng)執(zhí)行的正確性是較常見且較直觀的方式。早在1977年Bayer等人就提出了針對B-tree索引結(jié)構(gòu)的鎖策略優(yōu)化方案，以提高索引的并發(fā)度，其后又有大量的研究成果相繼發(fā)表。經(jīng)典的并發(fā)鎖策略在查詢時首先要鎖定父節(jié)點，然后查找并獲取子節(jié)點的鎖，接著釋放父節(jié)點，重復這個過程依次向下，直到到達葉節(jié)點。這種方式會導致并發(fā)索引結(jié)構(gòu)中過多的數(shù)據(jù)被鎖定，算法整體的并行度較差。為了提高并行度，當前Blink-tree和Masstree是較經(jīng)典且在當前各類大數(shù)據(jù)系統(tǒng)中應用較廣泛的兩種設(shè)計方案。圖2為Blink-tree的示意圖，其中，上半部分為樹的組織結(jié)構(gòu)示意，下半部分為具體節(jié)點的面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第7頁。組織方式示意。Blink-tree對經(jīng)典的B+tree索引結(jié)構(gòu)進行了修改，在每個樹節(jié)點中新增了一個最大鍵值（high-key）和指向同層右兄弟節(jié)點的指針（具體信息存在于節(jié)點的Link區(qū)域中）。該設(shè)計通過節(jié)點的讀寫鎖和兄弟指針，降低并發(fā)操作過程中各個線程之間的相互影響的程度。當在Blink-tree上執(zhí)行查詢時，遍歷樹的過程首先比較當前節(jié)點的最大鍵值是否小于目標鍵值，如果小于目標鍵值，則目標鍵值是本節(jié)點的右兄弟節(jié)點，因此可通過右兄弟節(jié)點指針進行跳轉(zhuǎn)，整個查詢過程不會持有相應樹節(jié)點的鎖，這有效地提升了讀并行度。當執(zhí)行插入操作導致內(nèi)部節(jié)點分裂時，在經(jīng)典B+tree結(jié)構(gòu)中往往整個樹節(jié)點和新增的樹節(jié)點將被鎖住，無法執(zhí)行查詢等任務(wù)，但是基于Blink-tree面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第7頁。圖2

Blink-tree結(jié)構(gòu)

Masstree于2012年被提出，其設(shè)計參考了以前的多種索引樹結(jié)構(gòu)，包括Blink-tree和OLFIT-tree。它采用了B+tree索引結(jié)構(gòu)和Trie樹結(jié)構(gòu)相互融合的方式，如圖3所示，將樹中的不面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第8頁。同層次及同層次的不同節(jié)點按一定的規(guī)則劃分成若干個不同區(qū)域，各區(qū)域之間按傳統(tǒng)的B+tree的方式組織，而每個區(qū)域內(nèi)部的節(jié)點按Trie樹的方式組織。它使用版本驗證（versionverification）的方式代替讀鎖，并且配合細粒度鎖實現(xiàn)更新與查詢的并發(fā)執(zhí)行。其中，并發(fā)控制策略的設(shè)計使用了讀復制更新（read-copy-update，RCU面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第8頁。圖3

Masstree結(jié)構(gòu)

基于鎖機制的并發(fā)控制雖然容易設(shè)計，且經(jīng)典結(jié)構(gòu)較好地解決了訪問并發(fā)度的問題，但是由于其需要頻繁地訪問鎖，因此鎖的開銷隨著并發(fā)度的提升也逐漸不可被忽略，成為鎖機制的并發(fā)控制的性能問題之一。另外，使用鎖的開發(fā)過程會引入很多潛在的漏洞，如死鎖或活鎖，基于鎖的并發(fā)控制策略對編程人員的能力要求也較高。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第9頁。3.2基于無鎖的并發(fā)策略為了應對基于鎖的并發(fā)策略中存在的問題（如死鎖、鎖同步開銷過大等），基于無鎖的并發(fā)策略逐漸得到了研究人員的重視。Levandoski等人設(shè)計的Bw-tree是當前主要的無鎖樹形結(jié)構(gòu)。該數(shù)據(jù)結(jié)構(gòu)通過對所有狀態(tài)更改使用原子操作（CAS指令，即CompareandSwap指令）來避免不必要的開銷，并提高并行效率，該設(shè)計已經(jīng)被應用于微軟公司的DocumentDB和AzureCosmosDB中。Bw-tree結(jié)構(gòu)主要圍繞映射表（mappingtable）構(gòu)建，通過該表有效地虛擬化索引頁表的位置和頁面大小，這為Bw-tree中基于主存的無鎖策略提供了保證。在更新過程中，Bw-tree沒有使用重寫或者鎖機制，使用CAS指令實現(xiàn)對樹結(jié)構(gòu)的更新操作。Sewall等人設(shè)計了被稱為PALM的B+tree，該樹也可以通過無鎖機制保證并發(fā)查詢和更新操作的順利執(zhí)行?；跓o鎖結(jié)構(gòu)的并發(fā)控制策略有效地規(guī)避了鎖同步的開銷，從而能夠有效地提升性能，但是由于其設(shè)計與實現(xiàn)難度較大，在實際應用中的廣度仍不及基于鎖的并發(fā)策略。3.3基于事務(wù)內(nèi)存的并發(fā)策略為了提升索引結(jié)構(gòu)的并發(fā)度，基于事務(wù)內(nèi)存的并發(fā)訪問策略應運而生。事務(wù)內(nèi)存將傳統(tǒng)數(shù)據(jù)庫中常用的事務(wù)與計算機的內(nèi)存結(jié)合，保證不同的并發(fā)處理之間具有原子性、一致性、隔離性的特點?；谑聞?wù)的并發(fā)索引設(shè)計根據(jù)其實現(xiàn)方式的不同可分為兩大類：軟件事務(wù)內(nèi)存（softwaretransactionalmemory，STM）設(shè)計和HTM設(shè)計。這兩類方案均可以在索引結(jié)構(gòu)上實現(xiàn)簡面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第10頁。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第10頁。Wang等人使用HTM實現(xiàn)了多種并發(fā)數(shù)據(jù)結(jié)構(gòu)，該系統(tǒng)（DBX系統(tǒng)）利用英特爾公司提供的硬件限制事物內(nèi)存（restrictedtransactionalmemory，RTX）實現(xiàn)基于B+tree和Hash表的鍵值存儲（key-valuestore）系統(tǒng)。這些并發(fā)數(shù)據(jù)結(jié)構(gòu)在RTM的保護下保證了多線程訪問的正確性和可串行性。另外，為了使新型硬件支持事務(wù)內(nèi)存的并發(fā)處理方式，Chen等人在GPU上實現(xiàn)了高效的HTM，以支持此并發(fā)策略的廣泛應用。Herliy等人較早使用STM策略實現(xiàn)了高效的無鎖并發(fā)數(shù)據(jù)結(jié)構(gòu)。為了使不具備事務(wù)內(nèi)存的硬件使用該特性，有許多研究使用軟件的策略實現(xiàn)了事務(wù)內(nèi)存策略。其中，Xu等人在GPU上實現(xiàn)了STM策略，使得事務(wù)性內(nèi)存策略在新型硬件上得以應用?；谑聞?wù)內(nèi)存設(shè)計的并發(fā)控制策略能夠較好地解決并發(fā)度的問題，并且可以降低編寫并發(fā)程序的難度，縮短開發(fā)周期。基于此策略能夠方便地對并發(fā)操作進行抽象和控制。3.4基于批處理更新的并發(fā)策略為了實現(xiàn)批處理場景下索引數(shù)據(jù)結(jié)構(gòu)的高效性，Pollari-Malmi等人和Shneiderman等人認為更新操作可以延遲，從而提高并發(fā)查詢的執(zhí)行效率。該設(shè)計模式將查詢與并發(fā)更新按階段依次執(zhí)行，減少了查詢與并發(fā)更新之間不必要的同步開銷。Arge等人和Graefe等人提出了緩存寫操作的更新策略，以避免不必要的I/O操作。批更新的并發(fā)處理策略在PALM和HB+tree中都得到了使用。其中，PALM是基于無鎖索引結(jié)構(gòu)和批處理策略實現(xiàn)的索引結(jié)構(gòu)，其使用了大量的預取操作和內(nèi)核SIMD指令級并行來提供并發(fā)查詢的吞吐量。HB+tree同樣采用了批處理策略，在CPU端進行索引結(jié)構(gòu)的批處理更新操作，在GPU端進行并發(fā)查詢操作。為了更高效地使用CPU和GPU資源，HB+tree基于緩存行長度對B+tree結(jié)構(gòu)進行面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第11頁。了設(shè)計，有效地提高了整體的訪存性能。最后，為了提高GPU與CPU的協(xié)作效率，HB+tree還提出了多種異構(gòu)計算合作模式，比如CPU-GPU流水線的模式、雙流模式（doublebuffering）等。批處理更新在Harmonia和GPUB-tree面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第11頁?；谂幚淼牟l(fā)控制策略針對更新非實時性特點，簡化了并發(fā)處理策略的復雜度，提高了特定場景的檢索效率。4針對新硬件特性的優(yōu)化隨著半導體技術(shù)的飛速發(fā)展，各種新型硬件不斷涌現(xiàn)，其中較為熱門的是多核CPU、異構(gòu)芯片、與分布式網(wǎng)絡(luò)相關(guān)的硬件以及新型存儲部件。它們針對傳統(tǒng)硬件的某一方面進行了增強，以應對不同場景下不同計算的需求。高效使用新硬件特性優(yōu)化并發(fā)索引結(jié)構(gòu)，成為用戶提高大數(shù)據(jù)系統(tǒng)質(zhì)量的潛在途徑之一。4.1基于多核CPU的優(yōu)化在并發(fā)索引結(jié)構(gòu)優(yōu)化領(lǐng)域，多核CPU的優(yōu)化一直是學術(shù)界和工業(yè)界關(guān)心的問題。從基于多核CPU的體系結(jié)構(gòu)可知，多核CPU間存在多個處理器核共享的緩存（L3緩存）和每個處理器核獨享的緩存（L1、L2緩存）。因此，當前各類研究成果均期望充分利用緩存和多核CPU的各個計算核心，提高并發(fā)索引結(jié)構(gòu)的處理效率。Rao等人、Hankins等人也在設(shè)計中得到了一致的結(jié)論，B-tree索引結(jié)構(gòu)中樹節(jié)點大小的設(shè)計會顯著地影響并發(fā)索引結(jié)構(gòu)在CPU上的性能。FAST是這些研究成果的集大成者，它采用靈活的配置方式，基于CPU的緩存行大小、內(nèi)存頁大小和向量指令的寬度進行配置，并面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第12頁。且盡最大能力減少存儲器時延，充分利用線程級并行和數(shù)據(jù)級并行，提高索引結(jié)構(gòu)在CPU端和GPU面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第12頁。除了基于多核CPU存儲器結(jié)構(gòu)的設(shè)計之外，隨著HTM新型硬件的出現(xiàn)和廣泛使用，利用HTM優(yōu)化索引結(jié)構(gòu)也逐漸成為研究的熱點。由于并發(fā)索引結(jié)構(gòu)需要動態(tài)地更新數(shù)據(jù)結(jié)構(gòu)，因此利用HTM能夠?qū)崿F(xiàn)易用的設(shè)計和高吞吐、低時延的事務(wù)處理。Wang等人提出的Eunomia針對CPU端索引結(jié)構(gòu)在高競爭場景中的并發(fā)索引結(jié)構(gòu)面臨的可拓展性問題，進行了詳細的討論與優(yōu)化設(shè)計。作者分析了索引結(jié)構(gòu)在高競爭場景中性能嚴重下降的問題（如數(shù)據(jù)沖突的可能性增大、重試的開銷較大、假沖突的比例較多等），通過將原本粗粒度的HTM事務(wù)區(qū)間劃分為兩部分來減少沖突的概率和重試的開銷，并提出了并發(fā)索引樹在高競爭場景下的設(shè)計原則：分割事務(wù)區(qū)間減少事務(wù)重試開銷，分段存儲數(shù)據(jù)減少假沖突，檢測消除真沖突和自適應的沖突控制策略。另外，作者還設(shè)計了基于版本號的一致性驗證策略，以期解決HTM帶來的整體一致性問題?；谝陨显瓌t重新設(shè)計并實現(xiàn)了并發(fā)B+tree，取得了在高競爭場景下高性能的處理效率和較好的可拓展性。4.2基于異構(gòu)芯片的優(yōu)化GPU和FPGA是當下主流的異構(gòu)計算硬件，GPU因其更好的可編程性，被使用得更為廣泛。GPU具有豐富的硬件資源，并廣泛應用于各大數(shù)據(jù)中心。如何利用GPU實現(xiàn)高效的索引結(jié)構(gòu)得到了越來越多的關(guān)注。目前已有許多關(guān)于使用GPU加速索引結(jié)構(gòu)的工作相繼被發(fā)表，它們均期望在GPU上提升經(jīng)典的B+tree結(jié)構(gòu)的性能。當前學術(shù)界較新的研究成果為Yan等人提出的Harmonia和Awad等人提出的與B-tree更新相關(guān)的優(yōu)化方案。研究成果性能分布如圖4所示，將HB+tree（CPU）作為性能比較基面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第13頁。準，更新吞吐率和查詢吞吐率的值越高表示性能越好。從圖4可以看出，3種基于GPU的B+tree的設(shè)計（HB+tree（GPU）、GPUB-tree和Harmonia）在查詢性能或更新性能方面優(yōu)于HB+tree（CPU）的性能。GPUB-tree針對更新操作進行了優(yōu)化，Harmonia面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第13頁。圖4

HB+tree、Harmonia與GPUB-tree的性能分布

Yan等人提出的Harmonia將B+tree索引結(jié)構(gòu)進行了重新設(shè)計，以期能夠在GPU的硬件體系結(jié)構(gòu)上達到理想的加速效果，如圖5所示。他們將樹結(jié)構(gòu)劃分為鍵區(qū)域和孩子節(jié)點信息區(qū)域，其中鍵值區(qū)域（鍵數(shù)組）存儲原有樹形結(jié)構(gòu)節(jié)點中的鍵值信息，孩子節(jié)點信息區(qū)域存儲每個節(jié)點的前綴和的信息，每個節(jié)點第一個孩子前的總節(jié)點數(shù)目被稱為該節(jié)點的前綴和。通過前綴和可以很容易地計算出該節(jié)點第一個孩子節(jié)點的位置以及該節(jié)點包含的孩子節(jié)點的數(shù)目。相比于傳統(tǒng)的樹結(jié)構(gòu)的存儲方式，這種基于前綴的樹形結(jié)構(gòu)組織方式雖然引入了一定的額外計算，但卻不需要存儲所有孩子節(jié)點的指針信息，從而節(jié)省樹形結(jié)構(gòu)的存儲開銷。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第14頁。這種設(shè)計方式能夠有效地減少B+tree結(jié)構(gòu)的體積，并充分地利用GPU上不同類型的存儲器緩存高時延的全局存儲器訪問。另外，Harmonia還基于B+tree數(shù)據(jù)結(jié)構(gòu)設(shè)計了兩種搜索優(yōu)化訪問：基于預排序的搜索優(yōu)化和基于窄線程組的搜索優(yōu)化策略，以期減少GPU上B+tree檢索的內(nèi)存訪問分歧、執(zhí)行分歧，并提高計算硬件的使用率。Awad等人提出的GPUB-tree針對B-tree索引結(jié)構(gòu)在GPU的更新及查詢操作進行設(shè)計并實現(xiàn)。在該研究成果中，他們針對GPU的緩存行，對Blink-tree數(shù)據(jù)結(jié)構(gòu)進行了特別的設(shè)計，以期獲得更好的緩存效果。另外，他們采用了線程束配合工作的策略，將任務(wù)以線程束的線程為粒度分發(fā)，執(zhí)行的過程則采用整個線程束合作完成的策略，以期在工作量和執(zhí)行分歧之間達到一定的平衡。在GPUB-tree上，作者還將傳統(tǒng)的B-tree索引結(jié)構(gòu)的鎖策略應用到了GPU上，如預分類機制、重啟機制等。面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第14頁。圖5

Harmonia樹結(jié)構(gòu)

面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第15頁。FPGA由于其電路芯片邏輯的可修改性和靈活性受到了各類優(yōu)化方案的青睞。Yang等人、Heinrich等人、Qu等人均使用該芯片對索引樹結(jié)構(gòu)進行了優(yōu)化。其中Heinrich等人基于FPGA提出了混合的索引結(jié)構(gòu)，它支持CPU與FPGA端異構(gòu)協(xié)同工作。該混合索引以B+tree為基礎(chǔ)，在CPU端存儲葉子節(jié)點或者多層底層節(jié)點，在FPGA端存儲內(nèi)部節(jié)點或者多層的高層節(jié)點。通過FPGA的并行加速提升了混合索引上層的搜索速度，以此提升索引結(jié)構(gòu)的整體處理效率。4.3基于分布式的優(yōu)化RDMA硬件目前已廣泛應用于各種數(shù)據(jù)中心，可以顯著提升網(wǎng)絡(luò)的通信性能，為分布式并發(fā)索引結(jié)構(gòu)的性能優(yōu)化提供了可能。RDMA作為一種新型的網(wǎng)絡(luò)硬件，可以減少傳統(tǒng)遠程過程調(diào)用帶來的時延，有效地提高了分布式索引結(jié)構(gòu)總事務(wù)的執(zhí)行速度，使得原來受限于網(wǎng)絡(luò)速率的分布式并發(fā)索引在性能上得到了有效的提升。DrTM的工作中將RDMA與HTM硬件的特性進行融合，使得分布式事務(wù)同步能夠降低時延，并且使用這兩種硬件技術(shù)可使跨機器的并發(fā)事務(wù)保持順序性。DrTM以Hash表索引結(jié)構(gòu)為基礎(chǔ)，使用以HTM為單機的事務(wù)提供事務(wù)保護，在多機之間則采用類兩段鎖的方式配合HTM來保證事務(wù)的正確性，其中在遠程訪問內(nèi)存時使用單邊的RDMA提高訪問的效率。DrTM+R在DrTM的基礎(chǔ)上，引入了樂觀控制策略，進一步提升整體性能，并為系統(tǒng)高可用性提供更好的支持。由Mitchell等人提出的Cell（一種分布式B樹存儲）可基于RDMA的特性解決傳統(tǒng)分布式存儲中服務(wù)器端負載過高時客戶端請求無法高效處理的問題。如圖6所示，其中R為根節(jié)面向大數(shù)據(jù)的索引結(jié)構(gòu)研究進展全文共18頁，當前為第16頁。點，L為葉子節(jié)點。在該設(shè)計中，當客戶端請求發(fā)送到服務(wù)器時，并發(fā)樹結(jié)構(gòu)的一個超級節(jié)點（64MB）將會通過RDMA傳輸?shù)娇蛻舳诉M行處理。這種方式避免了所