近年來,電子信息數據在企業的運營中越來越重要,企業需要對電子信息數據進行高效、及時、精確的分析。傳統的數據倉庫通常只支持歷史數據的分析與查詢,不能實時捕獲數據源中的變化,因為它們采用ETL工具周期性地從數據源中抽取數據,對其處理后加載到數據倉庫,而數據抽取的頻率通常為一個月一次、一周一次或者一天一次[1]。在實時數據倉庫中,實時數據導入與實時數據查詢的沖突將嚴重影響聯機在線分析(On-Line Analysis Processing,OLAP)的精度和效率。
當前解決這個問題的方法有很多,包括提高數據庫的性能、增加外部實時數據緩存[8]、即時(just in time)合并外部數據緩存信息、反向即時數據合并、實時分區、主動分區等等。但是上述方法在查詢結果的精度和效率上不能兼顧。
為解決查詢競爭并提高查詢結果精度,本文提出一種動態鏡像技術。動態鏡像技術是在實時數據倉庫的外部創建一個動態存儲區域,源系統中數據導入數據倉庫時,先在動態存儲區域創建一個分區并在其中創建一個節點,同時將數據存入節點。當這部分數據同時有更新需求和查詢需求時,則利用復制機制新建一個與存儲該數據的節點物理結構、邏輯結構都相同的節點。新數據存入新的節點,當新數據導入完成后,再次進行查詢,保證了查詢結果的精度,且避免了查詢競爭。
改進的實時數據倉庫架構與傳統數據倉庫不同的是,改進架構的ETL[2]過程被分割為定期ETL與實時ETL兩個部分。定期ETL是將數據源中的數據定期以批處理方式直接導入數據倉庫,而實時ETL則運用改變數據捕獲(CDC)[3]技術將源系統中變化數據加載到動態存儲區域。經過查詢、更新和刪除等操作,當滿足系統的觸發條件后,這些數據才會以批處理方式載入數據倉庫。
數據倉庫的存儲區域被分為實時數據存儲區和歷史數據存儲區,實時數據查詢和存儲在實時數據存儲區實現。實時數據倉庫的更新查詢調度模塊能夠根據用戶的需要決定查詢和更新等操作序列;數據質量模塊在展示數據查詢結果時生成一份報告,以便用戶知道這些數據內容和新鮮度;查詢控制模塊實現在動態存儲區域進行實時數據查詢操作。對于歷史數據查詢,動態存儲區域與數據倉庫需要無縫連接,以保證查詢結果的精度。
為了克服實時OLAP(Real-Time OLAP,RTOLAP)查詢中的多表連接和分組聚集的性能瓶頸,采用物化策略可以減少RTOLAP在動態存儲區域中表連接操作訪問基表和中間數據結構的次數。首先,RTOLAP將查詢分解為作用在維表和事實表上的子查詢,子查詢將生成〈key,value〉二元組;然后,掃描事實表一趟,利用事實表的外鍵映射直接定位相應二元組,完成多表連接或聚集操作。為了提高RTOLAP多表連接或聚集性能,本文提出蠅量級物化下的表連接算法FWMJoin(Fly-Weight Materialization Join)。
本文采用的基于動態鏡像的實時數據存取技術在不同的事務更新頻率下,查詢效率可靠,如果給予動態存儲區域更大的內存空間則性能會更好。
本文采用基于TPC-H的實時數據倉庫測試系統,從OLAP響應時間、查詢精度方面對動態鏡像技術、單鏡像、無鏡像方案進行比較與分析。實驗結果表明,基于動態鏡像的實時數據存取技術能有效解決查詢競爭問題,提高數據存取效率和查詢結果的精度。
動態鏡像是一種實時數據倉庫存儲預處理技術,主要用于解決數據倉庫的查詢競爭問題[9]。面對實時數據倉庫中的查詢與插入的競爭問題,近年來開展了許多研究工作,包括提高數據庫的性能、增加外部實時數據緩存、即時(just in time)合并外部數據緩存信息、反向即時數據合并、實時分區、主動分區等。
(1)單獨實時數據緩存方法是使用一種與數據倉庫分離的外部緩存。外部數據緩存持續更新,數據倉庫使用ETL工具以批處理模式進行數據更新,所有的實時數據或準實時數據的查詢直接定位到外部的數據緩存,從而避免了在數據倉庫中的查詢競爭問題[7],但如果數量巨大的復雜查詢分析運行在外部實時數據緩存,則同樣會發生在數據倉庫中出現的查詢競爭問題。
(2)簡化和限制實時報表方法,需要實時數據的用戶只能發出簡單的查詢要求,限制復雜查詢語句。這種方法可以消除查詢競爭,但是無法滿足用戶對復雜查詢的要求。
(3)升級硬件,可以為高端的SMP數據庫系統增加更多的節點或者為數據倉庫配備更快的處理器和更大的內存。這種方法能在短期內解決問題,但是增加了成本并且可擴展性低。
(4)反向即時數據合并[4],就是把所需要的歷史數據臨時地反向加載到實時數據緩存中,查詢在緩存中進行。這種方法可以有效解決查詢競爭,但是查詢結果的精度卻不盡理想。
(5)實時分區[5]是將實時數據進行數據量均衡的分區,然后分別對各分區數據進行查詢導入操作。這種方法有效緩解了查詢競爭,但是關于分區的個數和數據量的均衡算法的研究一直未成熟,分區算法隨著分區個數增加,其時間復雜度也線性增加,海量數據環境下給系統帶來沉重的負擔,難以滿足實時性的要求[11]。還有主動分區[6]等技術,它們都難以滿足用戶的需要。
當連續實時地導入數據時,用戶的查詢操作受到嚴重影響,包括查詢結果的精度和查詢效率。因此,實時數據倉庫面臨實時數據導入和實時數據查詢相沖突的問題,即當ETL在向實時存儲區加載數據時,用戶如果正在對實時存儲區進行多次查詢,這幾次查詢都將納入同一個統計結果,那么就要考慮是否將新到來的數據納入結果中。如果不做任何處理,OLAP查詢結果的精度往往難以滿足要求,需要設計一種新的結構來解決此問題。
本文設計一種基于動態鏡像的實時數據倉庫預存取技術,系統結構如圖1所示。其包括3個部分:
(1)實時數據倉庫改進,包括分類ETL結構和將數據倉庫存儲區域分為實時數據存儲區和歷史數據存儲區。
(2)在數據倉庫外部構建動態存儲區域,動態存儲區域由多個數據鏡像與基于雙重鏈接的鏡像索引組成。
(3)動態鏡像管理,包括鏡像創建與回收、基于雙重鏈接的鏡像索引維護。
首先是ETL分類。對于實時數據,數據在時間有效性范圍之外(即失效)將成為歷史數據。因此,我們對于實時數據的ETL處理同樣是分為歷史ETL和實時ETL。實時ETL通過CDC技術捕獲OLTP系統中查詢任務提交時間之后更新的數據并加載到動態存儲區域,在動態存儲區域對數據進行查詢、更新、刪除,當滿足系統觸發條件后再以批處理方式存入到數據倉庫中的實時數據存儲區;歷史ETL將OLTP系統中查詢任務提交時間之前存在的數據以批處理方式存入數據倉庫的歷史數據存儲區域。
其次是數據倉庫存儲區域分為實時數據存儲區和歷史數據存儲區。歷史數據是指由歷史ETL將OLTP系統中的數據處理并存入數據倉庫的歷史數據存儲區的數據;實時數據是指先由實時ETL將OLTP系統中的數據處理并存入動態存儲區域,然后根據觸發條件由動態存儲區域存入數據倉庫的實時數據存儲區的數據。
動態存儲區域由多個數據鏡像與基于雙重鏈接的鏡像索引組成。鏡像是具有相同的邏輯結構和物理結構的數據存儲區域,并根據數據查詢任務的需求,在動態存儲區中動態創建;系統可以將OLTP中的實時數據加載至鏡像中。
當創建一個鏡像時,系統在動態存儲區中保存一個相應的鏡像文件,用四元組表示:
其中,image_address表示鏡像在動態存儲區中的首地址,image_size表示鏡像分配的存儲空間大小,data_id表示鏡像存儲的數據源,timestamp表示數據的時間戳。
根據每個鏡像文件中的data_id,將所有data_id相同的鏡像構建成一個鏡像鏈表Link_img,如圖2所示。鏡像鏈表Link_img由鏈表頭節點img_head和鏈表節點img_node組成,鏈表頭節點img_head由鏡像數據源data_id與指向鏈表第一個節點的地址head_next組成。在一個鏡像鏈表中,所有鏡像的數據源來自同一數據源,數據源data_id相同。指向鏈表第一個節點的地址head_next存放第一個鏡像首地址image_address。根據鏡像文件內容,鏈表節點img_node由鏡像大小image_size、鏡像數據時間戳timestamp、操作標識符tag,及指向下一個鏈表節點的地址img_next組成。操作標識符tag用于記錄當前鏡像數據的操作類型,其初始值為0;若當前鏡像內容節點的數據是從源數據庫系統OLTP導入至動態存儲區,則此鏡像內容節點的操作標識符置為0;若當前鏡像內容節點的數據需要從動態存儲區批量加載至數據倉庫的實時數據存儲區,則操作標識符置為1;對于當前鏡像而言,若在動態存儲區中,不存在來自同一數據源的鏡像,則img_next設為空;否則,img_next存放下一個來自同一數據源的鏡像的首地址image_address。
同一個鏡像鏈表中存儲了來自同一數據源但是更新時間不同的數據鏡像信息;隨著系統運行,最近更新數據的時間戳一定大于較早更新數據的時間戳,所以,鏡像鏈表中的節點按其數據時間戳倒序(從大至小)排序。
所有來自同一數據源的鏡像構成一個鏡像鏈表,稱之為一個鏡像桶bucket,如圖3所示。其中鏡像桶的首地址bucket_address為鏈表頭節點地址。
在動態存儲區中,若存儲了n個數據源的數據,就有n個鏡像桶。為了加快鏡像數據的查找與定位,將對多個鏡像桶采用鏈表結構,構成一個鏡像桶鏈表Link_bucket。鏡像桶鏈表Link_bucket是一個無鏈表頭節點的鏈表,僅僅由鏡像桶鏈表節點bucket_node構成。
每個鏡像桶鏈表節點bucket_node由數據源data_id、鏡像桶的首地址bucket_address與指向下一個鏡像桶鏈表節點的地址bucket_next組成。其中,數據源data_id存放對應的鏡像鏈表的數據源data_id;鏡像桶的首地址bucket_address存放對應鏡像鏈表頭節點地址;向下一個鏡像桶鏈表節點的地址bucket_next存放下一個鏡像桶的地址bucket_address;若動態存儲區中不存在任何數據,即不存在任何數據源的鏡像桶,則不存在鏡像桶鏈表;在動態存儲區中,若只有一個鏡像桶,則其bucket_next為空;否則,bucket_next存放下一個bucket_address。
通過鏡像管理模塊可以得知在動態存儲區域中哪些鏡像用于查詢而哪些鏡像用于ETL的更新數據,這樣由多個鏡像構成的動態存儲區域就可以實現持續數據的實時裝載。這種動態鏡像的方法不但有效地解決了查詢競爭問題,同時也提高了實時數據的查詢精度。傳統的數據倉庫在更新的過程中進行“批”加載[8],本文通過建立由動態鏡像組成的實時存儲區使新鮮的數據不斷載入,以達到數據的持續更新,從而大大提高了查詢結果的精度。
動態鏡像管理包括鏡像創建與回收,及基于雙重鏈接的鏡像索引維護。首先動態存儲區域空間有限,其次從源系統載入數據到動態存儲區域中的鏡像,其物理地址不一定是連續的,所以需要有效地分配、收回管理才能保證動態存儲區域中數據的查詢和導入有條不紊地進行。
鏡像的創建過程就是將實時數據存入實時存儲區域的過程。算法步驟如圖4所示。
該算法的具體操作流程如下。
(1)當有新的數據需要從OLTP系統加載至動態存儲區時,動態鏡像管理模塊在動態存儲區中分配一塊存儲空間,創建一個鏡像,用于存儲新數據;同時,系統在動態存儲區中保存一個相應的鏡像文件。
(2)動態鏡像管理模塊采用順序查找方式,遍歷鏡像桶鏈表中的每個鏡像鏈表節點,檢查新數據的數據源是否與鏡像鏈表節點的數據源相同,即檢查動態存儲區中是否存在與新數據屬于同一數據源的數據。若存在,則轉入(3);否則轉入(9)。
(3)根據鏡像桶鏈表節點的桶鏡像首地址,可以查找到來自同一數據源的鏡像鏈表的頭節點。
(4)為新創建的鏡像,在對應的鏡像鏈表中創建一個新的鏡像鏈表節點,操作標識符tag設為0,指向下一個鏈表節點的地址設為空。
(5)根據新節點時間戳,將新鏡像鏈表節點插入至相應的鏡像鏈表。在鏡像鏈表中,鏡像節點按其數據更新時間戳倒序(從大至小)排序,所以,新鏡像鏈表節點n的時間戳最大,將其插入在鏈表頭節點之后。
(6)對于鏡像M而言,若鏡像的數據滿足查詢條件,或者接收到系統操作指令,需要將數據批量地從動態存儲區導入數據倉庫的實時數據存儲區時,將鏡像鏈表節點的操作標識符tag設為1,同時,相應的數據批量地寫入數據倉庫的實時數據存儲區。
(7)對于鏡像M而言,若系統接收到數據更新指令,此時,動態鏡像管理負責檢查同一數據源的鏡像數據是否正在從動態存儲區導入數據倉庫的實時數據存儲區。
若存在,正在導入數據的鏡像內容節點無法進行更新操作,則動態鏡像管理在動態存儲區采用步驟(1),分配存儲空間,創建鏡像,更新所屬同一數據源的鏡像鏈表,并接收來自OLTP的更新數據。以此類推,若需要將不斷更新的數據導入動態存儲區,系統不斷分配存儲空間,創建后續鏡像,更新鏡像鏈表,轉入(11)。若不存在,則轉入步驟(8)。
(8)動態鏡像管理模塊在動態存儲區中分配存儲空間,創建鏡像,用于存儲新數據。同時,系統在動態存儲區中保存相應的鏡像文件。
(9)為新數據源的鏡像創建一個新的鏡像鏈表。鏈表頭節點的數據源ID存放鏡像文件四元組的數據源;指向鏈表第一個節點的地址存放新創建的鏡像首地址。鏡像節點的操作標識符tag設為0,鏡像節點的指向下一個鏈表節點的地址設為空。
(10)根據新創建的鏡像鏈表更新鏡像桶鏈表。在原鏡像桶鏈表的尾部增加一個新鏡像桶鏈表節點。鏡像桶鏈表節點的數據源存放新數據源ID,鏡像桶鏈表節點的首地址存放新創建的鏡像鏈表的首地址,鏡像桶鏈表節點的指向下一個鏡像桶鏈表節點的地址設為空。
(11)動態鏡像創建完畢,基于雙重鏈表的鏡像索引也完成相應的更新。
(1)對于鏡像M而言,當系統將鏡像的數據批量地從動態存儲區導入數據倉庫的實時數據存儲區完成后,實時數據倉庫系統將發送反饋信息至動態鏡像管理模塊。
(2)動態鏡像管理模塊根據收到的反饋信息,釋放導入鏡像數據所占用的存儲空間。
(3)動態鏡像管理模塊根據鏡像的數據源ID和鏡像桶鏈表節點的首地址,定位到同一數據源的鏡像鏈表中對應的鏡像鏈表節點,將其節點從鏡像鏈表中刪除。
(4)若刪除鏡像鏈表節點后,其所屬鏡像鏈表的節點個數為0,僅存在鏈表頭節點時,則動態鏡像管理塊將此鏡像鏈表所對應的鏡像桶鏈表節點從鏡像桶鏈表中刪除,并釋放其占用的存儲空間。
本文采用時間戳匹配法處理實時數據倉庫查詢請求,請求過程如下:
(1)若實時數據倉庫系統已運行,根據用戶發出的查詢請求,鏡像管理模塊首先獲取請求的時間戳和data_id。
(2)然后根據data_id在動態存儲區中查找相應的鏡像,如果沒有,則返回空值,并將查詢請求發送至數據倉庫處理;否則,在對應data_id的鏡像鏈表中順序查找,轉(3)。
(3)在相應的data_id鏡像鏈表中,按時間戳從大到小查找。若時間戳失效,則返回空值,并將查詢請求發送至數據倉庫處理;否則,讀取與請求最匹配的鏡像節點數據,并將結果返回至用戶。
鏡像鏈表中鏡像按時間戳從大到小有序存儲。若存在某一節點的時間戳小于或等于請求的時間戳,且其前一個節點的時間戳大于請求的時間戳,則說明此節點數據按時間戳匹配原則,最佳滿足用戶請求,所以,返回此節點的數據至用戶。圖5顯示了在鏡像鏈表中處理用戶查詢請求的實例。
從分析可知,查詢競爭嚴重影響查詢效率和查詢結果的精度,動態鏡像是一種實時數據倉庫存儲預處理技術,用于解決數據倉庫的查詢競爭問題[9]。當一條數據載入數據倉庫后,首先判斷數據是否為實時數據,如果是,則被實時ETL捕獲,經過一系列清洗、過濾操作后載入動態存儲區域。為了說明動態鏡像技術是如何解決查詢競爭問題的,本文假設所有新捕獲的數據都是同源數據,即數據具有相同data_id,且動態存儲區域已經存在該數據的同源鏡像鏈表。當數據第一次加載至動態存儲區時,為其建立相應的數據鏡像,命名為M1,同時插入相應的鏡像鏈表中。當鏡像M1中的數據時間戳失效時,將其導入數據倉庫中。后續同源的數據再加載至動態存儲區時,系統也建立相應的數據鏡像,命名M2、M3,并插入鏡像鏈表中,以此類推。鏡像M1數據由于實時性失效,被載入數據倉庫后,為用戶提供歷史數據的查詢分析,而存放于鏡像M2、鏡像M3中的實時數據加載至動態存儲區后,為用戶提供實時數據查詢分析功能。通過時間戳比較匹配方法,來滿足用戶實時性要求,提高查詢結果的精度。通過合理、高效的數據分配和管理,基于動態鏡像的數據存取技術可以有效地解決查詢競爭問題。
對于傳統關系數據倉庫而言,在數據更新階段,實時數據以批處理模式加載至存儲區時,由于查詢競爭,會導致數據更新丟失,影響數據查詢精度[10]。本文提出的動態存儲區可以動態地為實時數據分配鏡像存儲空間,緩解查詢競爭壓力。時間復雜度作為衡量算法質量的重要指標,關系到算法的執行效率。下面對動態鏡像創建、回收過程進行時間復雜度分析。
(1)動態鏡像創建的時間復雜度是由數據導入的頻率決定的。最壞情況為數據查詢過程中不斷有更新數據導入,則時間復雜度為O(n2);最好情況為數據查詢操作恰好在數據導入完成后進行,則時間復雜度為O(n)。
(2)動態鏡像回收過程是在操作完成后,回收數據所在的鏡像桶空間,時間復雜度為O(n2)。
本文利用空間換取時間思想,以內存空間為代價,減少數據I/O開銷,提高查詢效率和查詢結果的精度。
OLAP上的查詢分析操作一般表現為在事實表和維表之間連接操作的基礎上對結果集進行分組聚集等操作。因此,表連接和分組聚集操作是關系聯機分析處理(Relational OLAP,ROLAP)性能的兩個重要決定因素。為了提高實時OLAP進行基于多表連接查詢的數據分析性能,期望查詢執行算法能夠采用一趟掃描機制完成表連接、過濾與聚集等操作。下面給出本文提出的蠅量級物化下的表連接算法FWMJoin(Fly-Weight Materialization Join)。本文提出的蠅量級物化連接算法FWMJoin是LWMJoin[13]算法的改進。LWMJoin是針對星型模型的數據倉庫,基于輕量級物化而提出來的表連接算法,它分為3個階段:首先,將維表上的謂詞條件作用在相應維表上,產生三元組〈surrogate,key,value〉,抽取符合過濾條件的元組構建哈希表;然后,順序掃描事實表,利用事實表外鍵映射函數定位相應維表的三元組;最后,根據過濾三元組確定是否訪問事實表相應位置上的元組構建結果集。如果三元組中的key值存在為false,那么該元組應舍棄;否則,將key值與事實表度量屬性拼接成一條元組,并將該元組以流水線方式輸入到下一個操作。
FWMJoin對LWMJoin的改進如下:將invisible join中由元組關鍵字構建的哈希表替換為Chord環。通過結合DHT(Distributed Hash Table)技術,將維表中符合過濾條件的元組的關鍵字所在的內存地址的哈希值作為節點標識符(Node ID),并對元組的關鍵字進行散列運算,產生一個唯一的資源標識符(Object ID),且該資源將存儲在節點標識符與之相等或相近的節點上。使用事實表外鍵作為關鍵字(key)進行查找。Chord與其他結構相比較,具有負載均衡、魯棒性高、可擴展和命名靈活等特點。
作為一種優化實時數據倉庫性能的手段,動態存儲區域下的動態鏡像實時數據倉庫的存取預處理技術必須與實時數據倉庫結合使用。本文實驗部分將動態鏡像技術與基于多級緩存(multi-cache)的實時數據倉庫結合。
影響計算機系統性能的因素是多種多樣的,加上其應用環境也特別復雜,基本不可能使用一個準確、固定的公式來表達,常用衡量的方式是指通用的基準程序。TPC-H是一種基準,用來衡量數據庫系統在硬件、軟件方面聯機分析處理的性能以及對DSS支持的能力[12]。這一基準是由事務處理性能委員會(TPC)在1999年公布的。通過測量給定的數據庫單位時間內能夠處理事務的數量來測試數據庫性能。
本文選用來自Sean Lahman[14]網站的結構化數據。Sean Lahman網站詳細記載了從1871年到2014年美國職棒大聯盟(Major League Baseball)各支球隊和各個運動員的比賽數據。本文在Hive中建立16GB空間的實時數據倉庫,約350萬條記錄。
(1)統一設置動態存儲區域大小為128MB,無鏡像方案沒有動態存儲區域,不設置。從圖6中可以看出,使用動態鏡像技術在事務更新頻率為1.0s/次的情況下,這是測試基準最低開銷,響應時間增長率都趨于0。當事務更新頻率設置為最高值時,每次間隔0.1s需處理一個事務,OLAP響應時間也達到最大,動態鏡像技術相比于單鏡像提升約1倍,與不采用鏡像技術相比,性能提升接近3倍。隨著事務發生頻率增大,本文提出的動態鏡像技術響應時間變長,但即使在事務成倍增加的情況下,使用動態鏡像技術的響應時間的增長還是可以控制在50%以內。這種效率是完全可以接受的,同時也在用戶滿意的范圍。
(2)統一設置事務更新頻率為0.5s/次。如圖7所示,在條件相同的情況下,動態存儲區域的空間越小,OLAP的響應時間則越長。當動態存儲區域為32MB時,對于OLAP查詢操作,單鏡像與動態鏡像方案響應時間相當,動態鏡像方案略占優勢。但是,當存儲空間較大時,對于OLAP操作,動態鏡像和單鏡像方案的查詢響應時間明顯占優。動態鏡像方案的查詢響應時間比無鏡像方案快1.8倍,比單鏡像方案提升約16%。
(3)設置事務更新頻率為0.5s/次,動態存儲區域統一為128MB空間。從圖8中可以看出動態鏡像技術、單鏡像技術及無鏡像3種情況在不同的事務更新頻率下的實時數據查詢結果精度。當事務更新頻率較低時,3種方案的查詢精度較為接近;當事務更新頻率設置為0.1s/次的最高頻率時,動態鏡像技術的查詢結果精度達到85%,單鏡像技術的精度為73%,而不采用鏡像技術的精度為48%。本文提出的體系結構隨著事務發生頻率增大,平均精度達到89.3%。
實驗結果表明,當實時數據被不斷加載時,本文采用的基于動態鏡像的實時數據存取技術在不同的事務更新頻率下,查詢效率可靠,如果給予動態存儲區域更大的內存空間則性能會更好。
結束語本文提出的基于動態鏡像的實時數據倉庫預存取技術是一種空間換時間的技術。通過在實時數據倉庫外部創建一個由多個鏡像組成的實時存儲區域,有效地解決了實時數據倉庫的查詢競爭問題,并且提升了實時數據查詢結果的精度。另一方面,在海量數據的背景下,如何進一步提高實時數據查詢的精度,以及保證實時數據新鮮度,將在后續的研究中展開。
標簽:
上一篇: 自動化立體倉庫在備件存儲方面的應用
下一篇: 海外代購中保稅倉庫問題研究