基於列存儲的多核並行哈希分區優化方法
2023-08-09 02:48:11 2
基於列存儲的多核並行哈希分區優化方法
【專利摘要】本發明公開了一種基於列存儲的多核並行哈希分區優化方法，主要解決現有並行哈希分區算法不能高效利用多核處理器資源的問題。其實現方案是：首先，利用映射-化簡併行編程模型將數據分區任務動態分配到各個核來執行，根據列存儲數據集存儲結構的不同，選擇相應的避免寫衝突策略；然後，用映射線程進行第一次哈希劃分，並將所得到的第一次哈希分區結果經過數據傾斜優化後交給化簡進程進行第二次哈希分區；最後，返回最終的哈希分區結果。本發明很好的利用了在多核處理器上任務可並行執行的特性，並能夠適應各種分布的輸入數據，提高了高速緩存效率和多核處理器的整體性能，可用於列存儲數據集的多核並行多步哈希分區。
【專利說明】基於列存儲的多核並行哈希分區優化方法
【技術領域】
[0001]本發明屬於數據處理【技術領域】，特別涉及一種多核並行哈希分區優化方法，可用於列存儲資料庫的數據分區。
【背景技術】
[0002]分區是資料庫中的重要操作，同時也是其他資料庫操作的基本操作，例如:連接、聚集、排序等操作。分區是將一個較大的任務分成若干個較小的子任務。處理若干個子任務所用的總時間常常小於處理一個較大任務所用的時間，這是因為較小的任務能夠高效的利用緩存和內存。分區操作在不同的應用中已經有了大量的研究，這些研究主要是針對資料庫操作。在連接操作和聚集操作中，分區能夠明顯的提升其性能；在並行排序操作中，分區也是其中重要的一步。Manegold等人提出的Radix_cluster分區算法通過減少緩存丟失和快表丟失獲得了較好的效果。Cieslewicz等人提出了在多核處理器中並行分區的方法，在處理均勻分布的輸入數據時取得了較好的效果。
[0003]HASH分區主要用來分散熱點讀，確保數據在預先確定個數的分區中儘可能平均分布。傳統HASH分區方式通過取模的方式使數據儘可能平均分布在每個分區中，讓每個分區管理的數據都減少，提高查詢的效率；可是當需要增加分區或者合併分區的時候，就會出現問題。假設原來是5個常規HASH分區，現在需要新增一個常規HASH分區，原來的取模算法是M0D(eXpr，5)，根據餘數O?4分布在5個分區中，現在新增一個分區後，取模算法變成M0D(expr, 6)，根據餘數O?5分區在6個分區中，原來5個分區中的數據大部分都需要通過重新計算重新分區。
[0004]伴隨當今的硬體發展十分迅速，CPU擁有更多的核心，每個核心擁有更多的線程。常見的CPU擁有4個或者更多的核心，每個核心擁有2個或者更多的線程。最近，IBM推出了新一代的P0WER8處理器，支持12核心96線程，共享96MB的三級緩存，這說明多核CPU有廣闊的應用前景。面對新型的硬體架構，傳統的並行哈希分區算法不能高效地利用多核處理器的並行資源，且不能較好地處理有傾斜的輸入數據。
【發明內容】
[0005]鑑於現有技術的不足，本發明的目的是克服上述傳統哈希分區方法的兩個缺陷，採用多核處理器，利用線性哈希分區技術和基於映射-化簡模型的單CPU多核處理器並行技術，動態地將要分區的列存儲數據集加載到內存，並使用映射-化簡模型將分區操作分配到處理器的多個核上並行運行，以縮短大數據集分區結果的返回時間，提高數據分區的效率，並較好地處理了有傾斜的輸入數據。
[0006]實現本發明目的的技術思路是:採用映射-化簡框架在多核處理器環境下對列存儲數據集進行哈希分區，並在映射-化簡執行時將列存儲數據集均勻分為若干塊，通過映射-化簡模型將各個塊分配給不同的映射線程並行執行，通過選擇合適的策略避免寫衝突，進行第一次映射線程哈希分區，再將所得到的中間結果集進行數據傾斜優化後作為輸入進行第二次化簡線程哈希分區，以實現列存儲數據集的多核並行哈希分區。
[0007]根據上述思路本發明的實現步驟包括如下:
[0008](I)讀取用戶輸入的列存儲數據集，該列存儲數據集的數據格式為(Key，Value)形式的鍵值對，其中Key表示鍵值對所對應的編號，Value表示鍵值對所存儲的值；
[0009](2)將用戶輸入的列存儲數據集分割為若干大小相同的塊，並將每一塊數據交給一個映射線程進行第一次哈希分區；
[0010](3)對於列存儲數據集不同的哈希存儲結構，選擇相應的避免寫衝突策略，以確保第一次哈希分區時映射線程的並行執行；
[0011](4)通過映射線程並行執行第一次哈希分區，產生m個一次哈希分區結果:
HashBi ts
[0012](4a)設映射線程的映射哈希函數為' (Key) =Key mod T一^一其中HashBits
是用戶自定義的哈希參數，其取值範圍為[2，+⑴)，mod為模運算，L I為向下取整運算；
[0013](4b)每個映射線程依據映射哈希函數(Key),對於列存儲數據集(Key, Value)鍵值對中的Key值進行哈希運算，將運算結果相同的鍵值對分到同一個分區中，共產生m個一次哈希分區，其大小分別為D1, D2,...，Di,..., Dm, i e I, 2，…，m，m彡2 ;
[0014](5)將產生的m個分區結果通過化簡進程進行第二次哈希分區:
H<ishBi ts
[0015](5a)設化簡線程的化簡哈希函數為:& (Key)= Key mod 2，其中「I為向上取整運算；
[0016](5b)通過數據傾斜優化方法優化m個一次哈希分區結果，將數據傾斜優化後的分區結果交給m個化簡線程進行分區，即由化簡線程依據化簡哈希函數f2 (Key)，對每個分區結果(Key，Value)鍵值對中的Key值進行哈希運算，再將運算結果相同的鍵值對分到同一個分區中，分別產生η個分區結果，η彡2,共產生mXn個二次哈希分區，mXn ^ 4 ；
[0017](6)將最終的mXη個分區結果輸出給用戶。
[0018]本發明具有如下優點:
[0019]1.本發明基於多核處理器可並行執行的特性，利用映射-化簡模型，將列存儲數據集分為若干塊交給線程進行並行處理，實現多步並行的哈希分區，提高了高速緩存效率，從而使多核處理器的整體性能得到提升；
[0020]2.本發明根據列存儲數據集兩種的不同存儲結構，選擇四種避免線程寫衝突策略，解決了各線程之間並行寫入數據集到同一分區位置時的寫衝突；
[0021]3.本發明對有數據傾斜的列存儲數據集提出數據傾斜優化方法，實現了對各種分布的輸入數據集的哈希分區。
【專利附圖】
【附圖說明】
[0022]圖1為本發明的運行流程示意圖；
[0023]圖2為本發明利用映射-化簡模型執行多步哈希分區示意圖；
[0024]圖3為傳統的哈希存儲結構圖；
[0025]圖4為本發明優化的哈希存儲結構圖；
[0026]圖5為本發明進行第二次哈希分區前使用數據傾斜優化方法的流程示意圖；
[0027]圖6為用本發明在無鎖策略下分別進行單步分區與多步分區的效率對比圖；
[0028]圖7為用本發明在四種不同策略下分別進行單步分區的效率對比圖；
[0029]圖8為用本發明在兩次遍歷策略下使用數據傾斜優化與未使用數據傾斜優化分別進行分區的效率對比圖。
【具體實施方式】
[0030]為了更好的理解本發明，下面將結合附圖對本發明進行詳細的說明。
[0031]參照圖1，本發明的實現步驟如下:
[0032]步驟1，讀取列存儲數據集。
[0033]將用戶所輸入的列存儲數據集保存在一個txt的文本文件中，每個鍵值對佔txt文本文件的一行；
[0034]通過讀取txt文件每一行讀取用戶輸入的列存儲數據集，該列存儲數據集數的數據格式為(Key，Value)形式的鍵值對，其中每對鍵值對大小16位元組，含有8位元組的編號Key和8位元組存儲的值Value ；
[0035]對讀取的列存儲數據集選擇傳統的哈希存儲結構或者優化的哈希存儲結構進行存儲。
[0036]步驟2，分割用戶輸入的列存儲數據集。
[0037]將用戶輸入的列存儲數據集分割為t個大小相同的塊，如圖2中的分塊所示，數據集分塊數目t應當等於映射線程的數目，其中t e 2，3,4,…；
[0038]依據用戶輸入數據集大小C和數據集分塊數目t計算每一塊數據集的大小f，映射線程依據每塊數據集的大小從總的數據集中取出數據。
[0039]步驟3，選擇並行分區時的避免寫衝突策略。
[0040]依據存儲用戶輸入數據集時所選擇的哈希存儲結構，對列存儲數據集不同的哈希存儲結構，選擇相應的避免寫衝突策略，以確保第一次哈希分區時映射線程的並行執行，其選擇原則如下:
[0041]原則一，對於存儲數據集採用傳統的哈希存儲結構，即用一個容器或者數組存儲鍵值對，則選擇使用兩次遍歷策略或並行緩存策略，以避免寫衝突；
[0042]原則二，對於列存儲數據集採用優化的哈希存儲結構，則選擇使用加鎖策略或無鎖策略，以避免寫衝突。
[0043]所述傳統的哈希存儲結構，是用一個容器或者數組存儲鍵值對；當用一個容器存儲某一個分區中的鍵值對時，由於用容器存儲鍵值對時只能通過順序遍歷找到該容器空閒的存儲位置，然後進行寫入操作，隨著鍵值對數目的增加，鍵值對的存儲效率會明顯降低；當用一個數組存儲某一個分區中的鍵值對時，其結構如圖3所示，哈希存儲結構由一個指針數組組成，該指針數組中的每一個指針指向一個新的數組，用於存儲鍵值對，由於數組可以通過下標進行定位，數組存儲鍵值對的存儲效率較高且存儲效率不會隨著存儲鍵值對的數目的增加而降低，但初始化一個容量較大的數組所需時間較長。
[0044]所述優化的哈希存儲結構，其結構如圖4所示，用一個連續的數組表示，數組的每一位表示一個哈希桶，每一個哈希桶存儲結果集中某一個分區中的鍵值對。每一個哈希桶由空閒指針(free指針)，後繼指針(next指針)和一段連續的存儲空間組成,其中連續的存儲空間用於存儲鍵值對，free指針指向該連續存儲空間中下一個空閒位置，next指針指向新的哈希桶位置，這樣的設計既保證了鍵值對存儲效率又降低了初始化存儲結構時的花銷；
[0045]所述的兩次遍歷策略，是指先通過線程進行第一次遍歷，將每個線程分區所產生的各分區中鍵值對個數存儲到二維數組Km，其中q表示線程的編號，P表示該線程分區所產生的分區編號；然後通過公式=計算出第q個線程的第P個分區中鍵值對寫入
J=I 克=1
存儲結構的位置；最後進行第二次遍歷，將鍵值對並行寫入分區區域存儲結構；該策略最終的分區結果存儲在一段連續的存儲空間，提高了程序的局部空間利用率，但該策略對輸入的數據集要進行兩次遍歷；
[0046]所述的並行緩存策略，是指每個線程有大小一定的獨立存儲空間，將鍵值對寫入線程自己的存儲空間時不需要進行加鎖解鎖操作，但當該存儲空間耗盡時，需要通過加鎖解鎖操作獲取新的存儲空間；
[0047]所述的加鎖策略，是指所有線程共享一個鍵值對存儲結構，每一個分區區域是一個連續的存儲空間，每個線程並行地將鍵值對寫入分區區域，當不同線程寫入同一分區區域時，需要先對該分區區域進行加鎖操作，然後加鎖線程進行寫入；加鎖線程將鍵值對寫入完畢後需要進行解鎖操作，並由另一個線程加鎖該分區區域進行寫入，直至所有線程執行完畢，使用該策略進行哈希分區時內存消耗較小，且內存消耗不會隨著線程數目的增加而增加，但頻繁的加鎖解鎖操作影響了哈希分區的整體效率；
[0048]所述的無鎖策略，是指每個線程有一個獨立的鍵值對存儲結構，每個線程只將數據寫入自己的存儲結構中，避免頻繁的加鎖解鎖操作，但該策略需要額外的操作將所有線程分區所產生的存儲結構進行合併，同時進行哈希分區時的內存消耗會隨著線程數目的增加而增加。
[0049]步驟4，映射線程進行第一次哈希分區。
[0050]映射線程依據所選擇的避免寫衝突策略利用映射哈希函數並行執行第一次哈希分區，產生m個分區結果:
I HashBi ts
[0051](4a)設映射線程的映射哈希函數為:士' (Key) =Key mod 一2一其中HashBits
是用戶自定義的哈希參數，其取值範圍為[2，+⑴)，mod為模運算，L」為向下取整運算；
[0052](4b)每個映射線程依據映射哈希函數(Key),對於列存儲數據集(Key, Value)鍵值對中的Key值進行哈希運算，將運算結果相同的鍵值對分到同一個分區中，共產生m個一次哈希分區，其大小分別SD11Df1Df1Dm, i e l，2^"，m，m>2。
[0053]步驟5，將產生的m個分區結果交給化簡線程，進行數據傾斜優化和第二次哈希分區。
[0054](5a)設化簡線程的化簡哈希函數為:& (Key)= Key fflod 2，其中「]為向上取整運算；
[0055](5b)通過數據傾斜優化方法優化m個一次哈希分區結果:
[0056]參照圖5，本步驟的具體實現如下:
[0057](5bl)設定一個閾值T=2 X -；
Hl
[0058](5b2)將m個一次哈希分區D1, D2,...，Di,...，Dm依次與閾值T進行比較:
[0059]若Di < T，則將該哈希分區直接交給化簡線程；
[0060]若DiXT,則將該哈希分區暫時保存到隊列D中，直至所有一次哈希分區全部比較完畢，再將隊列D中的每一個哈希分區平均分為m份，將每一份分別交給一個化簡線程。
[0061](5c)化簡線程依據化簡哈希函數對優化後的分區結果進行第二次哈希分區，即依據化簡哈希函數(Key),對每個分區結果(Key, Value)鍵值對中的Key值進行哈希運算，再將運算結果相同的鍵值對分到同一個分區中，分別產生η個分區結果，η >2，共產生mXn個二次哈希分區，mXn彡4。
[0062]步驟6，將最終的mX η個分區結果輸出給用戶。
[0063]最終的mXn個分區結果通過txt文件形式輸出給用戶，同時進行本次哈希分區所用的初始化時間、第一次分區時間、第二次分區時間以及總時間均將輸出給用戶，用戶依據上述時間參數對哈希分區的效率進行評定。
[0064]下面將結合具體實驗對本發明的效果作進一步描述。
[0065]一、實驗環境
[0066]在Linux系統中用C++程式語言,基於英特爾新型Sandy Bridge架構的Xeon8核處理器(E5-26702.6GHZ)共用4個8GB DDR3內存進行分區，每核包含兩個線程、擁有3個級別的緩存，其中I級緩存為獨立的32KB，2級緩存為獨立的256KB，3級緩存為共享的20M。
[0067]二、實驗內容
[0068]實驗1，在無鎖策略下比較單步分區與多步分區的效率。
[0069]本實驗中，用戶輸入的列存儲數據集為16M，共16384對鍵值對，對輸入數據集採用優化的哈希存儲結構進行存儲，映射線程的線程數為16，即將輸入數據集均分為16個含有1024對鍵值對的數據集，取多個哈希函數參數HashBit，在無鎖策略下分別進行單步哈希分區與多步哈希分區，結果如圖6所示。
[0070]從圖6可見，當HashBits較小時，由於分區結果中鍵值對較少，能夠較好地利用高速緩存和快表，而多步分區相比單步分區要多進行一次分區，因此單步分區的效率比多步分區要高。
[0071]當HashBits較大時，由於分區結果中鍵值對較多，高速緩存和快表未命中的機率增加，多步分區能夠將分區結果中較多的鍵值對通過第一次分區使得分區結果中鍵值對數目減少，因此多步分區比單步分區效率更高，當多步分區中第一次分區數目等於第二次分區數目時，多步分區效果最好。
[0072]實驗2，比較四種不同策略的下單步分區的效率。
[0073]本實驗中，用戶輸入的列存儲數據集為16M，共16384對鍵值對，使用加鎖策略和無鎖策略進行分區時，輸入數據集採用優化的哈希存儲結構進行存儲，使用兩次遍歷策略和並行緩存策略進行分區時，輸入數據集採用傳統的哈希存儲結構進行存儲，映射線程的線程數為16，即將輸入數據集均分為16個含有1024對鍵值對的數據集，取多個哈希函數參數HashBit，通過映射線程進行單步哈希分區，結果如圖7所示。
[0074]從圖7可見，在加鎖策略中，當HashBits較小時，每一個分區結果有較多的鍵值對，頻繁加鎖解鎖操作會影響整體性能。隨著HashBits的增加，每一個分區結果的鍵值對數目減少，線程之間的衝突減少，整體性能提升。當HashBits繼續增加，高速緩存和快表的未命中會影響程序效率。
[0075]在無鎖策略中，由於沒有加鎖解鎖操作，在HashBits較小時程序性能大大優於加鎖策略，但程序需要許多額外的變量記錄當前寫入位置、分區大小等信息，而這些變量的數目隨著線程數目的增加而增加，所以隨著HashBits的增加，無鎖策略承擔的內存壓力增力口，再考慮到高速緩存和快表未命中的影響，隨著HashBits的增加，程序整體效率明顯下降。
[0076]在兩次遍歷策略中，受限於第一次遍歷計算分區鍵值對寫入位置的操作，當HashBits增加時，分區數目增多，第一次遍歷需要計算的寫入位置數目也隨著增加，該策略的整體效率就降低。
[0077]在並行緩存策略中，隨著HashBits的增加，考慮到高速緩存和快表未命中的影響，程序整體效率明顯下降。
[0078]實驗3，對含有數據傾斜的輸入數據集在兩次遍歷策略下比較使用數據傾斜優化與未使用數據傾斜優化進行分區的效率。
[0079]本實驗中，用戶輸入的列存儲數據集為16M，共16384對鍵值對，用戶輸入的數據集是有數據傾斜的數據集，其傾斜度的齊夫值為1.15，對輸入數據集採用傳統的哈希存儲結構進行存儲，映射線程的線程數為16，取多個哈希函數參數HashBit，比較在兩次遍歷策略避免下使用數據傾斜優化數據集與不使用數據傾斜優化數據集進行分區的效率，其結果如圖8所示。
[0080]從圖8可知，在多步分區處理有數據傾斜的輸入數據時，使用本發明提出的優化方法比未使用優化方法的性能有了明顯的提高。這是因為本發明提出的優化方法將較大的數據集暫時保存延後進行處理，先並行分區較小的數據集避免多個空閒線程等待一個工作線程的情況，對較大的數據集進行均分後再由線程進行並行分區，因此在有數據傾斜的輸入數據情況下，可以有效的提高整體分區性能。
【權利要求】
1.一種基於列存儲的多核並行哈希分區優化方法，其特徵在於，包括以下步驟: (1)讀取用戶輸入的列存儲數據集，該列存儲數據集的數據格式為(Key，Value)形式的鍵值對，其中Key表示鍵值對所對應的編號，Value表示鍵值對所存儲的值； (2)將用戶輸入的列存儲數據集分割為若干大小相同的塊，並將每一塊數據交給一個映射線程進行第一次哈希分區； (3)對於列存儲數據集不同的哈希存儲結構，選擇相應的避免寫衝突策略，以確保第一次哈希分區時映射線程的並行執行； (4)通過映射線程並行執行第一次哈希分區，產生m個一次哈希分區結果:
MashBi ts.(4a)設映射線程的映射哈希函數為..a (Key) =Key mod 一_2一其中HashBits是用戶自定義的哈希參數，其取值範圍為[2，+⑴)，mod為模運算，L I為向下取整運算； (4b)每個映射線程依據映射哈希函數(Key),對於列存儲數據集(Key, Value)鍵值對中的Key值進行哈希運算，將運算結果相同的鍵值對分到同一個分區中，共產生m個一次哈希分區，其大小分別為D1, D2, - ,Di, - ,Dm, i e 1，2，彡2 ; (5)將產生的m個分區結果通過化簡進程進行第二次哈希分區: (5a)設化簡線程的化簡哈希函數為:^ (Key)= Rey mod 2?^^其中「I為向上取整運算； (5b)通過數據傾斜優化方法優化m個一次哈希分區結果，將數據傾斜優化後的分區結果交給m個化簡線程進行劃分，即由化簡線程依據化簡哈希函數f2 (Key)，對每個分區結果(Key, Value)鍵值對中的Key值進行哈希運算,再將運算結果相同的鍵值對分到同一個分區中，分別產生η個分區結果，η彡2,共產生mXn個二次哈希分區，mXn彡4 ； (6)將最終的mXn個分區結果輸出給用戶。
2.根據權利要求1所述的基於列存儲的多核並行哈希分區優化方法，其特徵在於，步驟(3)所述對於列存儲數據集不同的哈希存儲結構，選擇相應的避免寫衝突策略，按如下原則選擇: 若列存儲數據集採用傳統的哈希存儲結構，即用一個容器或者數組存儲鍵值對，則選擇使用兩次遍歷策略或並行緩存策略，以避免寫衝突； 若列存儲數據集採用優化的哈希存儲結構，則選擇使用加鎖策略或無鎖策略，以避免與衝突； 所述優化的哈希存儲結構，是用一個連續的數組表示，數組中的每一位表示一個哈希桶，每一個哈希桶由free指針，next指針和一段連續的存儲空間組成,其中連續的存儲空間用於存儲鍵值對，free指針指向該連續存儲空間中下一個空閒位置，next指針指向新的哈希桶位置。
3.根據權利要求2所述基於列存儲的多核並行哈希分區優化方法，其中所述的兩次遍歷策略，是指先通過線程進行第一次遍歷，將每個線程分區所產生的各分區中鍵值對個數存儲到二維數組Km，其中q表示線程的編號，P表示該線程分區所產生的分區編號；然後通過公式￡ ?晃k計算出第q個線程的第P個分區中鍵值對寫入存儲結構的位置；最後
^/=1 k =1進行第二次遍歷，將鍵值對並行寫入分區區域存儲結構。
4.根據權利要求2所述基於列存儲的多核並行哈希分區優化方法，其中所述的並行緩存策略，是指每個線程有大小一定的獨立存儲空間，將鍵值對寫入線程自己的存儲空間時不需要進行加鎖解鎖操作，但當該存儲空間耗盡時，需要通過加鎖解鎖操作獲取新的存儲空間。
5.根據權利要求2所述基於列存儲的多核並行哈希分區優化方法，其中所述的加鎖策略，是指每個線程並行地將鍵值對寫入分區區域，當不同線程寫入同一分區區域時，需要先對該分區區域進行加鎖操作，然後加鎖線程進行寫入；加鎖線程將鍵值對寫入完畢後需要進行解鎖操作，並由另一個線程加鎖該分區區域進行寫入，直至所有線程執行完畢。
6.根據權利要求2所述基於列存儲的多核並行哈希分區優化方法，其中所述的無鎖策略，是指每個線程有一個獨立的鍵值對存儲結構，每個線程只將數據寫入自己的存儲結構中，避免頻繁的加鎖解鎖操作。
7.根據權利要求1所述的基於列存儲的多核並行哈希分區優化方法，其特徵在於，步驟(5b)所述通過數據傾斜優化方法優化m個一次哈希分區結果，按如下步驟進行: (5bl)設定一個閾值T=2 X 一，其中C表不輸入列存儲數據集的大小；
m (5b2)將m個一次哈希分區D1, D2,...，Di,...，Dm依次與閾值T進行比較: 若Di < T，則將該哈希分區直接交給化簡線程； 若DiXT,則將該哈希分區暫時保存到隊列D中，直至所有一次哈希分區全部比較完畢，執行步驟(5b3)；(5b3)將隊列D中的每一個哈希分區平均分為m份，將每一份分別交給一個化簡線程。
【文檔編號】G06F17/30GK104133661SQ201410369674
【公開日】2014年11月5日 申請日期:2014年7月30日 優先權日:2014年7月30日
【發明者】黃鑫, 劉志鏡, 袁通, 劉慧 , 王梓, 徐曾, 強波, 李宗利, 邱龍濱, 王鵬 申請人:西安電子科技大學