面向區塊鏈的高效物化視圖維護和可信查詢

人工智能技術與咨詢?

來源：《軟件學報》?，作者蔡 磊等

摘 要:區塊鏈具有去中心化、不可篡改和可追溯等特性,可應用于金融、物流等諸多行業.由于所有交易數據按照交易時間順序存儲在各個區塊,相同類型的交易數據通常會散布在諸多區塊之中,降低了面向歷史區塊的追溯查詢的處理效率.索引構建和物化視圖是提升查詢性能的兩種典型方法,但當待處理數據分布于多個區塊時,使用索引無法改善I/O 訪問效率,而物化視圖可有效應對這個問題.然而,由于區塊鏈系統的特點明顯區別于關系數據庫,傳統的面向關系數據庫的物化視圖技術無法被直接應用到區塊鏈之中.鑒于此,首次提出一種面向區塊鏈的高效物化視圖機制,具有如下特征:(1)將視圖維護操作與共識過程同時執行,降低該操作對系統性能的影響;(2)使用字典樹加快以區塊為單位的多物化視圖維護進程;(3)以默克爾驗證的方式確保物化結果不被惡意篡改,進而確保查詢結果可信.所提出的物化視圖維護機制已經被集成到一個區塊鏈系統中,并通過實驗來驗證該機制的高效性.

關鍵詞:物化視圖;區塊鏈;增量更新;視圖維護;默克爾樹

作為一種在不可信環境中由多方共同維護的分布式賬本,區塊鏈已被應用在金融、物流等領域.然而,當前的區塊鏈技術在數據管理方面存在著無法支持復雜查詢、查詢接口單一和響應太慢等局限性.

為了彌補現有區塊鏈平臺在數據管理性能方面的不足,一些課題組嘗試融合數據管理和區塊鏈技術,例如ChainSQL[1],BigchainDB[2],FlureeDB[3],SEBDB[4]等.ChainSQL 將關系數據庫和Ripple 區塊鏈網絡相結合,借助關系數據庫的訪問接口為鏈上數據訪問提供便利,并使用區塊鏈技術來提升數據異地多活的容錯能力.BigchainDB 是一種添加了區塊鏈特征的數據庫,它集成了MongoDB 和Tendermint 區塊鏈網絡.FlureeDB 將區塊鏈技術中不可篡改和高容錯特性集成到圖形數據庫.以上工作盡管提供了更豐富的查詢功能,但是并未聚焦查詢性能優化.SEBDB[4]在面向傳統行業的聯盟鏈背景下,為區塊數據添加了關系語義,將每種交易類型轉化為一張關系表,將該交易類型的參數轉化為相應關系表的列,從而有效融合關系語義和區塊數據.

在區塊鏈中,區塊包括區塊頭(block header)和區塊體(block body),如圖1(a)所示:區塊頭由前一個區塊的哈希值、區塊ID、區塊生成時間、交易默克爾樹根、簽名和本區塊的哈希值組成;區塊體包含多個交易,每個交易由交易ID(TxID)、交易簽名(TxSig)、智能合約調用者(TxCaller)、交易時間(TxTime)、交易表名(TxName)和表數據(TxData)組成.圖1(b)為一個交易示例,表示用戶Alice 調用智能合約中的donate 函數向教育基金項目Edu Fund 捐助了100 元.在SEBDB[4]中,交易表名相當于關系數據庫中的表名,表數據包含若干列,相當于關系數據庫中的一行記錄.

Fig.1 Structure of block and transaction
圖1 區塊和交易結構

由于交易數據在區塊中以交易提交的時間順序依次存儲,屬于同一關系表的交易數據往往會分散在不連續的多個區塊中,這會降低針對區塊數據的查詢的執行效率.SEBDB[4]通過在區塊鏈上建立B+樹、位圖等索引提高查詢性能,但是當查詢涉及到多個區塊時,使用索引無法持續降低I/O 訪問開銷,因而無法進一步改善查詢處理效率.在數據庫中,建立物化視圖是另一種提高查詢效率的方法,物化視圖通過物化查詢結果來提高特定查詢的處理效率.因此,如何在區塊鏈中使用物化視圖也值得思考.

盡管物化視圖已被研究多年,如何維護物化視圖仍舊是一個開放問題.在關系數據庫中,增量刷新的物化視圖維護策略可劃分為立即維護[5]和延遲維護[6]兩大類.立即維護策略的優點是實現較為簡單,在單數據源下不存在一致性問題;然而該策略將物化視圖維護過程嵌入到更新事務之中,延長了更新事務的提交時間,這在高并發的情況下易發生死鎖.延遲維護策略解耦合視圖維護和更新事務,在OLTP 場景下,可以通過合并無關更新[6]的方法縮短視圖維護時間;但是此策略存在一致性問題,若視圖未更新完畢則不可使用.在延遲維護策略的諸多實現方法中,按需維護[7]較為常見,即:等待查詢到來之后,只維護與查詢相關的物化視圖.由此可見,各種策略的優缺點顯著,如何合理選擇視圖維護策略非常重要.

面對被賦予了關系語義的區塊數據,采用關系數據庫中普遍使用的建立物化視圖的方式來提升查詢性能是一種可行的方法.在區塊鏈中,系統查找某張表的數據需要掃描所有的區塊,當數據量龐大時,即使掃描索引也會產生非常大的開銷.鑒于此,如果將物化視圖運用于區塊鏈,將會優化查詢的處理效率.

然而,關系數據庫與區塊鏈系統在存儲模型和更新操作上有顯著不同,區塊鏈系統以區塊為單位進行更新,單個區塊包含多條交易,并且區塊鏈系統中的交易需要通過共識來完成.區塊鏈系統和關系數據庫相比,在區塊鏈上建立、維護物化視圖將面臨以下3 個挑戰.

(1)如何選擇物化視圖的寫入時機.區塊鏈的寫入性能受到分布式共識、智能合約執行限制,而物化視圖的維護開銷對系統的性能帶來額外影響.因此,如何合理選擇視圖維護的時機來降低視圖維護對系統整體性能的影響,是一個需要考慮的問題;

(2)如何以區塊為單位維護視圖.區塊是區塊鏈的基本數據追加單位,各區塊包含多種類型的交易,對于一個區塊可能需要同時維護多個視圖.因此,設計的方案必須支持批量的物化視圖維護,并且使得物化視圖維護的開銷盡可能小;

(3)如何確保查詢結果的可信性.由于數據上鏈需要經過較為昂貴的共識過程,為了提升查詢效率,物化視圖并不保存在區塊鏈上.與此同時,將物化視圖保存在本地會面臨數據被篡改的風險,需要實施相應措施來確保查詢結果可信.

針對以上挑戰,本文的主要貢獻包括:首次將物化視圖運用于區塊鏈,提出了一種視圖維護和共識過程并行的方法,降低物化視圖的維護開銷.區塊鏈的共識過程主要消耗網絡帶寬,在此期間,CPU 和I/O 資源消耗相對較少,而視圖維護過程卻主要消耗CPU 和I/O 資源.因此,將視圖維護和共識過程并行執行可減少視圖維護對寫入性能的影響.提出了基于字典樹的方法,以區塊為單位批量維護視圖,并且支持多種維護策略.本文使用字典樹作為索引加快查找不同表名的更新記錄,可對相同表名的更新記錄只進行一次視圖維護操作.并且本文支持閑時維護和按需維護的維護策略.提出了基于默克爾樹的查詢結果驗證方法,確保結果可信.為物化視圖構造默克爾樹.當查詢使用物化視圖時,系統掃描物化視圖建立默克爾樹,并與預先保存的默克爾樹根進行比較,以此確保物化視圖的正確性與完整性.

本文第1 節說明本文的系統架構.第2 節闡述物化視圖的維護時機.第3 節描述物化視圖維護的具體過程.第4 節詳述基于默克爾樹的查詢驗證方法.第5 節展示實驗結果.第6 節回顧與本文相關的研究工作.最后,第7節給出簡短總結.

1 系統架構

本文原型系統架構如圖2 所示,包括應用層、查詢層、存儲層、共識層和網絡層:應用層包括查詢API、訪問控制和智能合約;查詢層具有查詢引擎,負責對查詢的解析、優化、執行,包括物化視圖的維護;存儲層包括區塊鏈和鏈下數據(物化視圖、索引等);共識層負責交易的共識,運用的協議為PBFT[8];最后,網絡層采用Gossip協議.本文專注于查詢層、存儲層和共識層:物化視圖的更新記錄來自于共識返回的結果,查詢層負責物化視圖的維護工作,并將更新后的物化視圖存于存儲層.此外,查詢的結果來源于存儲層的區塊數據或物化視圖.

Fig.2 System architecture
圖2 系統架構

在此架構下,面向添加了關系語義的聯盟鏈,我們首次提出一種高效的物化視圖維護方法以提高查詢的效率,并且提出一種驗證方法來確保查詢結果的正確性.當系統應用層接收到客戶端發來的智能合約調用請求時,查詢層處理請求,然后調用智能合約產生一條新的交易,交易通過共識后被打包進區塊保存在區塊鏈中.另一方面,查詢層獲取共識成功的交易進行視圖維護,視圖維護完畢后,將更新后的物化視圖存于存儲層的磁盤中.而當系統接收到客戶端的查詢請求時,查詢層判斷該請求是否可以運用物化視圖:若可以,則獲取物化視圖數據返回給應用層;若不能使用物化視圖,則需掃描區塊鏈查找結果.接下來我們將回答3 個問題:何時進行物化視圖的維護、如何進行物化視圖的維護以及如何保證物化視圖結果的正確性.

2 物化時機的選擇

在區塊鏈中,交易在系統中達成共識需要在各節點之間進行網絡通信.比如,廣泛應用于聯盟鏈的協議PBFT 需要進行3 輪網絡交互,耗費時間較長.在共識階段主要消耗網絡資源,而CPU 和I/O 資源相對空閑.因此,視圖維護與共識階段可以并行執行.當上一輪共識的數據已經有效時,系統在執行新一輪交易共識的過程中對上一輪產生的數據進行物化操作.這樣,物化視圖維護和共識過程同時進行,互不干擾,從而大幅度減少視圖維護對系統整體性能的影響.

該方案需考慮兩種情況:一是視圖的維護時間相對于共識時間比較少;二是視圖的維護時間大于共識時間,即上輪共識通過的交易相關視圖不能在此輪共識時間內完成.假設每個區塊中的交易平均屬于k?張表,每張表的視圖個數為n,每張表的的平均視圖維護時間為tmvi(i∈[1,n]),共識的時間為T,那么需要考慮:

或

如果維護時間滿足公式(1),如圖3 所示,系統直接對上一輪共識通過的數據進行視圖維護;如果滿足公式(2),則將剩余未維護的記錄暫存在緩沖區中,等待CPU 空閑進行閑時維護.以上方法中,正在進行維護更新的物化視圖暫時不可用,因為最新的數據還未更新,查詢得到的結果不完整.因此,當有可以引用物化視圖的查詢到來時,系統采用按需維護策略,優先維護查詢相關的物化視圖以快速響應查詢.對于視圖維護中的一致性保證,我們將在第4.2 節詳細敘述.

Fig.3 Maintenance timing of materialized views
圖3 物化視圖的維護時機

3 視圖維護過程

3.1 維護視圖的基本步驟

在維護物化視圖時,查詢層的查詢引擎獲取共識成功的交易的表名、表數據、所屬區塊ID 進行增量維護.系統創建的物化視圖與基本表類似,只是在類型上加以區別.圖4 展示了物化視圖維護的整體流程,該流程包括4 個步驟:①從共識模塊獲取已完成共識的多個交易,創建增量記錄;② 查詢層將增量記錄按照表名分組,并存儲在增量記錄緩沖區中;③根據增量記錄創建視圖維護任務,當查詢到來時,進行視圖維護任務的調度;④ 根據物化視圖的查詢表達式計算更新的視圖行集,再將新增的視圖行集添加到視圖中.

Fig.4 Maintenance process of materialized views
圖4 物化視圖的維護過程

以下詳細介紹相關步驟.

·首先,在第①步驟中,需要創建增量記錄.

增量記錄是一個用于存儲記錄更新信息的三元組DeltaRecord(Row,TableName,BlockID),其中,Row?是交易的表數據部分,TableName?是交易的表名,BlockID?是當前交易所在區塊的區塊高度.在針對交易進行新一輪共識時,系統獲取上一輪各交易的表名和表數據字段,結合新區塊的ID 創建增量記錄.該步驟可以線性復雜度執行完畢.

·其次,為了提升數據檢索效率,步驟②將增量數據分組后存放在增量數據緩沖區之中.

由于增量記錄數目較多,可將其按照表名進行分組,分別構建增量記錄集(DeltaRecords),并暫存于一個常駐內存的增量記錄緩沖區(DeltaRecordsCache).為了提升增量記錄的檢索效率,采用字典樹[9]對表名進行索引.換言之,該字典樹包含了所有表名以及這些表名的部分前綴字符串.若字典樹中某節點(包括葉節點和非葉節點)對應一個表名,則有一個指針指向與該表名相對應的增量記錄集.圖5 顯示了一個采用字典樹索引增量記錄的案例.在增量記錄緩沖區中共有3 個增量記錄集,其中,視圖維護任務Task1維護表名為donate?的增量記錄d1,d2,d3,Task2維護表名為transfer?的增量記錄t1,t2,t3.當一個新的增量記錄被添加到增量緩沖區時,我們在字典樹上查找該增量記錄的表名:若此增量記錄表名不存在,則系統為該表名創建新的節點;若存在,則將此增量記錄插入到葉子節點所指向的增量記錄集.如果某個增量記錄相關的所有視圖維護完畢,則刪除該增量記錄.

·然后,步驟③基于增量記錄集來維護視圖.

由于各視圖之間相互獨立,而且整體維護開銷較大,可分別為各個視圖分配一個維護任務,并由調度器進行調度.在此基礎之上,可以動態設置維護任務的優先級,并且根據場景需求實時切換各維護任務的執行次序.比如說,假設包含相同基表的待維護視圖包括v1和v2,而新來的查詢想要處理視圖v1,則可以提升v1的處理優先級,從而提升整體效率.各視圖維護任務需要指定待維護的視圖名稱(ViewName)、維護任務優先級(Priority,默認為1)和增量記錄集.系統維護一個針對所有維護任務的優先級隊列(即視圖維護任務隊列,TaskQueue),以確保高優先級的任務被優先執行.

·最后,步驟④執行步驟③所創建的任務,計算需要更新到物化視圖中的行集.

在物化視圖創建時,為各視圖創建一個數據結構,該數據結構保存視圖的名稱(ViewName)、視圖的基表名稱(TableName)、視圖的查詢執行時的算子(Operators)和當前已維護到的?BlockID.本文將其命名為視圖信息(ViewInfo).系統重新執行視圖的查詢算子,便能很快計算出結果.然后將行集寫入物化視圖中,至此,物化視圖已被更新.

Fig.5 Storage of?DeltaRecord
圖5 增量記錄的存儲

接下來具體描述算法步驟,包括算法1 和算法2.

算法1.創建視圖維護任務.

算法2.物化視圖維護.

算法1 描述了創建視圖維護任務的過程,其輸入參數為:字典樹TrieTree,增量記錄表名TableName,物化視圖信息ViewInfo?和視圖維護隊列TaskQueue.算法1 第1 行根據增量記錄表名TableName?查找字典樹TrieTree,得到增量記錄集DeltaRecords.這里省略了如何在字典樹中查找增量記錄集的過程.第2 行～第4 行表示創建一個新的視圖維護任務Task,并對其增量記錄集和視圖名稱賦值.該算法最后將此任務加入到視圖維護任務隊列中.

調度器周期性評測當前系統的負載,一旦發現當前系統處于非忙碌狀態(CPU 占用資源低于某一閾值),則從TaskQueue?中依次調取優先級高的若干任務來執行;在執行過程之中,系統仍舊可以檢測系統的資源占用情況,當系統過于忙碌時,則暫時退出物化視圖維護過程,留待下一周期執行.算法2 描述了在非忙碌階段調度器執行部分視圖維護任務的過程,其輸入參數為:待維護物化視圖集合V,待維護視圖信息集合ViewInfoSet,視圖維護隊列TaskQueue.算法的第2 行、第3 行取出視圖維護隊列頭部的視圖維護任務.第4 行根據視圖維護任務包含的視圖名稱查找視圖集合V?中相應的視圖.第5 行表示根據視圖維護任務包含的視圖名稱查找視圖信息集合ViewInfoSet?中相應的視圖信息.第6 行表示針對維護任務的增量記錄集執行視圖信息中的算子獲得新增行集Rows.第7 行將第6 行中產生的行集添加到視圖v?中.算法最后判斷系統狀態,若當前系統繁忙,則退出算法.

例1:假設系統中存在兩張物化視圖Vd?和Vt,其中,物化視圖Vd?的基表為donate,Vt?的基表為transfer.系統中增量記錄緩沖區的增量記錄如圖5 所示,此時,視圖維護任務隊列含有4 個視圖維護任務.其中,Task1負責維護基表為donate?的物化視圖,Task2維護基表為transfer?的物化視圖.當系統收到查詢物化視圖Vt?的請求,則提高視圖維護任務Task2的優先級,那么視圖維護任務隊列中視圖維護任務執行的順序變為Task2,Task1.當執行視圖維護任務時,系統從視圖維護任務隊列頭取出Task2,然后根據物化視圖Vt?的查詢執行算子計算視圖新增的行集并添加到Vt?中,最后刪除已維護完畢的維護任務Task2和增量記錄t1,t2,t3.

視圖維護時,增量記錄的BlockID?提供了一致性保證.我們為每個物化視圖存儲已維護記錄的最新BlockID,如果該BlockID?為查詢到來時最新的區塊號,則說明物化視圖已經更新到最新狀態.

3.2 多種維護策略的支持

許多數據庫都采用單一的物化視圖維護策略,例如:文獻[6]采用閑時維護的策略,文獻[7]采用按需維護的策略.閑時維護存在不能及時響應查詢的情況,而按需維護可能存在一些物化視圖累積增量記錄過多、導致一次維護的執行時間長的問題.為了避免上述情況,本方法同時支持閑時維護和按需維護的策略:當CPU 空閑時,查詢引擎檢查視圖維護隊列是否存在未執行的視圖維護任務,若存在,則依次執行;如果查詢到來,維護策略切換為按需維護.

當查詢到來時,我們從共識層可以知道當前最新的BlockID,而我們預先為每個視圖維護一個最近更新的BlockID.首先將兩個BlockID?比較,如果相等,則說明該物化視圖已維護到最新狀態;如果不等,則需要訪問增量記錄緩沖區和視圖維護任務隊列.此時,根據查詢語句中的表名查找字典樹,便可獲取到與查詢相關的增量記錄,如果存在,則建立視圖維護任務.如果視圖維護任務隊列中存在查詢相關視圖的維護任務,則系統將會提升這些視圖維護任務的優先級,從而查詢引擎優先維護查詢相關的物化視圖以快速響應查詢.通過將多種維護策略相互協調,系統可以最大限度地降低查詢的延遲時間.

4 可信任的物化視圖

借助物化視圖固然可顯著提高區塊鏈中查詢的效率,但是當物化結果被存儲于本地時,一旦本地節點被攻擊,物化結果就有可能被惡意篡改,進而影響查詢結果的正確性.鑒于此,本文利用默克爾樹來確?；谖锘晥D的查詢結果的正確性.

默克爾樹[10]是基于哈希值的二叉樹,其葉子節點是數據的哈希值,非葉子節點是對子節點哈希值進行串接之后再進行散列所獲得的哈希值.因此,默克爾樹具有防篡改特性.本方法預先為每個視圖構建一棵默克爾樹,并保存在內存中.在查詢過程中,系統讀取物化視圖重新構建默克爾根,并與之前保存的默克爾根進行比對,以驗證查詢結果的正確性.每當物化視圖更新時,均會針對所更新的數據產生一個哈希值,該哈希值將被添加到默克爾樹的最右側子節點,并向上更新默克爾樹直至根節點.以圖6 為例,假定物化視圖每次更新一行,則所生成的默克爾樹共有8 個葉子節點,其中,Hi即為Rowi的哈希值.由于新增的交易總是更新默克爾樹的最右節點,所以當默克爾樹增長到超出可使用的內存大小時,系統可以只將默克爾樹的最右路徑上的節點保存在內存中,以便更新默克爾樹.

Fig.6 Structure of Merkle-tree
圖6 默克爾樹結構

算法3 描述了如何使用默克爾樹驗證基于物化視圖的查詢結果,輸入參數為物化視圖MV、視圖每次更新的數據長度數組sArray?和預先建立的默克爾樹的樹根Root,輸出為驗證標志Proofs.算法第1 行創建一個空數組ViewHashs?以保存哈希值.第2 行初始化視圖MV?的偏移位置.算法的第3 行～第8 行表示對于每次維護的記錄行集Rows?進行哈希操作,其中:第4 行表示每次從視圖的偏移位置讀取長度為sArray[i]的數據rows;第5 行、第6 行表示將每次讀取的數據rows?進行哈希,并把得到的哈希值保存在ViewHashs?中;第7 行更新視圖MV?的偏移位置.算法的第9 行使用ViewHashs?建立默克爾樹得到默克爾樹根RowsRoot.第10 行驗證新計算的默克爾樹根RowsRoot?是否與Root?相同:若相同,則驗證成功,算法返回驗證結果Proofs?為true;反之驗證失敗,返回false.由此,本方法保證了物化視圖物化結果的正確性,從而保證基于視圖的查詢的結果也是正確的.

算法3.默克爾樹查詢驗證.

例2:以圖6 為例,查詢獲取視圖結果時,系統按照每次視圖寫入的終止位置不斷讀取物化視圖中的記錄并進行散列,然后根據散列后的哈希值建立圖6 所示的默克爾樹,如此得到默克爾樹根H15.算法3 將它與預先保存的默克爾樹根Root?比對:若相同,則驗證成功,表示物化結果沒有被惡意篡改.

算法3 的時間開銷由內存中的計算時間和物化視圖的讀取時間組成.其中,內存計算的時間主要取決于哈希運算的次數.在算法3 中的循環體中,哈希運算被運行n?次(n?為物化視圖維護的次數),循環體外建立默克爾樹哈希運算需要運行n?1 次,則哈希運算一共被運行2×n?1 次,因此算法3 內存中的時間復雜度為O(n).而對于視圖的讀取,設磁盤帶寬為x(MB/s),物化視圖的大小為y(MB),則視圖的讀取時間為y/x(s).

5 實 驗

5.1 實驗環境

本文將提出的物化視圖機制實現在區塊鏈系統SEBDB[4]中,以驗證所提出方法的有效性.實驗在4 臺機器組成的集群上進行,其中,每臺機器配備Intel Xeon(R)2.10GHz 的CPU,96G 的RAM 和3TB 的硬盤.區塊鏈系統運行在CentOS 7 上,區塊鏈采用Tendermint 共識,共識時間設置為1s.

此外,我們采用了SEBDB[4]中的模式,如圖7 所示,此模式的鏈上表由捐贈系統中的donate,transfer?和distribute?這3 張表組成.其中,donate?表記錄捐助者的捐款信息,transfer?記錄捐贈組織間的資產轉移信息,distribute?記錄捐助組織給予受助者的援助信息.由于系統原型的局限性,原型暫不支持多表連接和聚集查詢,因此,這里工作負載僅涉及單張表的查詢或者兩張表的連接,形式如Q1,Q2 和Q3 所示.本文實驗的數據由SEBDB中的數據生成器生成,系統中各表的交易均勻地分布在區塊鏈中.

Fig.7 Database schema
圖7 數據庫模式

5.2 物化視圖維護性能

我們通過創建Q1,Q2 形式的物化視圖來比較單表與等值連接視圖維護所需要的時間.本實驗設置區塊個數2 000～4 000,其中每個區塊包含5 條需要視圖維護的交易,每條交易大小為300 字節.圖8 顯示了物化視圖規模在1 萬～2 萬條記錄之間情況下的維護時間.對于Q1 形式的單表查詢視圖,維護開銷緩慢增長,即使系統一次維護2 萬條數據,也僅需要200ms 的時間.這種情況下,視圖維護過程完全可以與共識過程并發處理中,視圖維護對系統的影響非常小.Q2 形式的等值連接視圖維護過程中依然要掃描區塊以獲取另一張表的數據進行連接,所以相對單表視圖的維護時間增長許多,對于2 萬條記錄的維護已經超過共識設定的時間.這種情況下,系統采用閑時維護的策略.對于現階段的區塊鏈,交易的吞吐量最高為上千級別,并且現實情況中系統每張表的物化視圖數量比較少,因此我們的方法完全可行.

圖9 具體分析了Q2 形式的等值連接視圖在視圖維護過程中,存儲視圖和除存儲視圖以外其他階段消耗的時間,圖中顯示:存儲物化視圖的時間是短暫的,其余階段的執行占據了視圖維護的主要部分.這是因為在連接的另一張表不存在視圖的情況下連接查詢仍然需要掃描區塊,但這可以通過使用索引的方法來避免.

Fig.8 Cost to maintain views
圖8 視圖維護開銷

Fig.9 Storage time and other time
圖9 存儲時間與其他時間

除此之外,我們測試了使用字典樹和線性掃描兩種方法查找增量記錄的物化視圖維護性能.為了更好地體現字典樹的性能,實驗中模擬加入了其他表名的增量記錄,并且固定每個表名的增量記錄為100 個.如圖10 所示:使用字典樹的視圖維護方法的維護性能總是優于線性掃描增量記錄緩沖區的維護方法,當維護的增量記錄的表名越多、增量記錄越多時,兩者的差距則越大.這是因為字典樹只需要一次字符串比較便可得到增量記錄集的位置,而不使用字典樹的情況下,系統每次獲取增量記錄集都需要遍歷整個增量記錄緩沖區.

Fig.10 Using trie tree
圖10 使用字典樹

5.3 使用物化視圖減少查詢的延遲

本節我們對比查詢使用視圖和查詢掃描區塊所需的響應時間.對于Q1 查詢,本實驗固定區塊個數為1 000,每個區塊中的交易數量為200.圖11 顯示:使用物化視圖的查詢響應時間增長緩慢,而掃描區塊方式的查詢時間快速增長.這是因為隨著區塊的增多,掃描區塊的時間快速增長,而掃描物化視圖需要更少的I/O.圖12 顯示Q2的查詢響應時間,結果集固定為20 000 行,區塊個數從1 000～5 000 增長,使用物化視圖的查詢響應時間遠少于掃描區塊的查詢響應時間.而掃描區塊的查詢響應時間快速增長,這是因為Q2 查詢需要兩次掃描區塊,并且需要進行復雜的連接操作.

Fig.11 Response time on?Q1
圖11 查詢響應時間(Q1)

Fig.12 Response time on?Q2
圖12 查詢響應時間(Q2)

5.4 使用物化視圖與使用索引的查詢性能對比

本實驗將本文提出的物化視圖方法與SEBDB 中的索引方法進行性能對比,兩者皆采用相同的查詢和數據.本實驗固定區塊個數為1 000,每個區塊有200 條交易,結果集從1 萬～2 萬行增長.由圖13 可知:對于Q1,使用物化視圖的查詢響應時間一直低于使用索引的查詢響應時間;當結果集行數增加時,使用索引的查詢響應時間增長較快,而使用物化視圖的查詢響應時間平緩增長.這是因為當數據均勻分散在各個區塊中時,使用索引會引起更多的磁盤隨機讀取,而使用物化視圖是對文件的順序讀取.

如圖14 所示:對于Q2,使用物化視圖的查詢始終優于使用索引的方式;基于索引的查詢需要隨機讀取數據,并且需要進行連接操作,因此使用索引的查詢響應時間相對使用視圖的方式越來越長.實驗證明,查詢使用物化視圖方法的性能優于使用索引的方法.

Fig.13 Index vs.materialized view on?Q1
圖13 索引和物化視圖性能對比(Q1)

Fig.14 Index vs.materialized view on?Q2
圖14 索引和物化視圖性能對比(Q2)

此外,我們使用Q3 對比在查詢具有選擇條件的情況下,使用物化視圖和索引的性能.本實驗固定區塊個數為2 000,每個區塊的交易為1 000 條,查詢的選擇率從0.1～1 增長.實驗結果如圖15 所示:當選擇率為1 時,使用索引的查詢響應時間比使用物化視圖的方法多40ms;隨著選擇率的下降,物化視圖的優勢越明顯;當選擇率為0.1 時,使用索引的查詢響應時間為使用視圖的方法的2 倍多.

Fig.15 Index vs.materialized view on?Q3
圖15 索引和物化視圖性能對比(Q3)

5.5 可驗證查詢的性能

對于使用物化視圖的查詢請求,我們構建默克爾樹對視圖進行驗證.本實驗采用的視圖為Q1 形式的單表視圖.實驗設置物化視圖維護的總記錄數從5 000 增長到10 000,在掃描視圖時生成默克爾樹,并與內存中保存的默克爾樹根進行比對.驗證查詢的延遲如圖16 所示:NV?表示不加驗證過程的查詢響應時間,YV?表示具有驗證階段的查詢響應時間.圖16 中顯示:結果集為10 000 條記錄時,YV?比NV?多了約100ms.這是可以接受的,因為這仍然比不使用視圖的查詢要快很多.

Fig.16 Verification cost
圖16 驗證開銷

總結以上實驗,本文描述的物化視圖維護方法可以很好地提升查詢的性能;并且通過默克爾驗證,保證了使用視圖的查詢請求結果的正確性.

6 相關工作

以支持智能合約為代表的區塊鏈2.0 平臺的提出,使得區塊鏈技術可以廣泛使用到除電子貨幣以外的傳統行業中.為了應對區塊鏈在傳統行業應用中所面臨的數據管理方面的新需求,來自學術界和工業界的許多工作開始專注于區塊鏈技術與數據管理技術的結合,這將促使區塊鏈技術可以在傳統行業領域有更廣泛的使用.其中,ChainSQL[1]和BigchainDB[2]在數據庫的基礎上使用區塊鏈,使得數據庫具有去中心化、防篡改的特點.FlureeDB[3]是一個結合了區塊鏈技術的可擴展的圖形數據庫,雖然它們豐富了查詢的功能,但未提高查詢的性能.SEBDB[4]為區塊數據添加了關系語義,并且使用索引來提升查詢性能;但對于復雜查詢或均勻分布的數據查詢,響應時間依然較長.

相比于索引技術,物化視圖是提升區塊鏈數據庫查詢性能更直接的辦法,但物化視圖卻會帶來額外的維護開銷.慶幸的是,數據管理領域的研究人員已經對如何降低物化視圖的維護代價做了很多方面的工作.在視圖維護策略方面,文獻[11,12]采用立即維護的視圖維護策略;而文獻[6,7]使用延遲維護策略,使視圖維護不阻塞更新事務.此外,文獻[13,14]分別討論了分布式數據庫系統和NOSQL 數據庫系統中更新物化視圖的問題,它們都支持增量的視圖維護方法.在降低物化視圖更新開銷方面,早期的文獻[5,15?19]提出了優化的物化視圖更新算法,它們主要利用現有的物化視圖和表達式進行增量更新.文獻[6,20?23]提出了異步更新的視圖維護工作,對于需要集成分布式數據源的數據倉庫,這種方法的優勢更加突出.文獻[14,24]將分布式環境下的物化視圖的維護工作分散到多個視圖更新程序中,通過并行維護,提高了物化視圖更新的效率.文獻[25,26]優化了同時更新多個相關的物化視圖的算法,它們考慮多個物化視圖之間的表達式關系,利用多個物化視圖表達式之間的公共子表達式,從而找到維護一組物化視圖的最高效的維護計劃.文獻[27?29]提出了物化附加視圖的方法,其中,文獻[28,29]提出的方法對文獻[27]中的方法做了優化,節省了空間開銷.文獻[30]提出了一種高階形式的增量視圖維護(HIVM)算法,該算法借鑒數學中微分的思想,遞歸地使用離散的前向差異(增量修改)進行視圖更新.文獻[31]提出了在分布式環境中進行批量更新的高效增量視圖處理技術.文獻[32]提出一種新的數據結構,并提出基于此結構的視圖更新算法,該算法具有常量的時間復雜度和空間復雜度.在面向區塊鏈的視圖維護中,這些方法都是可以借鑒的,但它們并不完全適用于區塊鏈的數據模型,比如不支持以區塊為粒度的視圖更新,并且區塊鏈的共識過程使區塊鏈上的視圖維護變得更加復雜.

在可驗證查詢方面,文獻[33]提出了3 種可驗證的連接算法,保證了連接結果的完整性和正確性.Vchain[34]提出了輕量級可驗證查詢框架,并保證查詢結果的正確性和完整性,此外,Vchain 中還提出了基于雙線性配對累加器的驗證數據結構,以降低查詢驗證的代價.它們通過驗證返回的結果來保證查詢的完備和保真.而本文則驗證查詢的數據來源是否正確,使得驗證更輕便、高效.

除了物化視圖相關的工作,關于區塊鏈數據管理方面的研究工作涉及得很廣泛,文獻[35?37]是關于區塊鏈技術和可信數據管理方面的探討.為了提高區塊鏈系統的擴展性和并發性,文獻[39]提出一種智能合約并發執行的方法.

7 結束語

本文針對區塊鏈系統中,面向區塊數據的查詢響應太慢的問題,提出了一套面向區塊鏈中區塊數據查詢的物化視圖構建、維護和訪問機制:首先,本文選擇合適的時機進行視圖維護,使得視圖維護過程隱藏于共識過程中,并以區塊為粒度,采用字典樹的元數據存儲方式加快了視圖維護的過程;其次,本文采用混合式的多種維護策略相結合的視圖維護方式,降低了查詢的延遲;最后,本文提出默克爾樹驗證方法使得本地物化數據不會被惡意篡改,進而保證了查詢結果的有效性.

本文提出的面向區塊鏈中區塊數據查詢的物化視圖機制,實現在一個真實的區塊鏈平臺[4]中.實驗結果表明,本文的方法高效可行.但是和關系模型相比,對于區塊鏈中數據的鏈式存儲模型,針對復雜查詢的物化視圖創建和維護面臨著更多的挑戰.比如:對于復雜的業務場景,為了保證查詢效率,區塊鏈需要創建的物化視圖更多.因此,我們將繼續探究物化視圖的更新、選擇在區塊鏈中與關系數據庫的不同之處,動態地為每個智能合約精準預創建物化視圖,在保證系統查詢性能下的同時,使得物化視圖所占空間盡可能小.我們下一步的工作重點是研究支持復雜查詢,例如多表連接、聚集查詢等的有效物化視圖維護機制,我們也將進一步探討將基于物化視圖的可信查詢與可信硬件SGX 結相合,使得可驗證查詢的響應時間更短.

我們的服務類型

公開課程

人工智能、大數據、嵌入式? ? ? ? ? ? ??? ?? ?

內訓課程

普通內訓、定制內訓? ? ? ? ? ? ? ?? ??? ? ??

項目咨詢

技術路線設計、算法設計與實現（圖像處理、自然語言處理、語音識別）

總結

以上是生活随笔為你收集整理的面向区块链的高效物化视图维护和可信查询的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。