一種分布式b+樹索引系統及構建方法
2023-04-28 06:15:06 2
專利名稱：：一種分布式b+樹索引系統及構建方法
技術領域：
：本發明涉及一種數據索引系統及構建方法，特別是一種用於雲存儲環境下的分布式B+樹索引系統及構建方法。
背景技術：
：隨著網際網路技術的發展和Web2.0時代的到來，由於應用過程中需要對海量數據進行處理和運算，這樣的應用環境對Web應用數據管理系統的可擴展性、可靠性和高效性提出了更高的要求。隨著雲環境技術的日益成熟，雲存儲系統在如今Web數據管理方面體現出越來越明顯的優勢。雲存儲是指通過機群應用、網格技術或分布式文件系統等功能，將網絡中大量各種不同類型的存儲設備通過應用軟體集合起來協同工作，共同對外提供數據存儲和業務訪問功能的一個系統。現有的雲存儲系統如Bigtable、Hbase、PNUTS等，它們在對海量數據的索引方面都存在著一些不足，主要包括1)現有系統都只有對數據的主鍵上的索引，缺乏對數據的其他屬性的有效索引方式；如果客戶端應用伺服器需要依據數據的某些其他屬性上的檢索條件進行查詢時，系統只能通過遍歷所有數據的方式實施查詢，從而使得査詢效率非常低。2)現有系統在索引操作中缺乏有效的並發控制事務機制；這樣的缺陷直接導致客戶端應用伺服器在使用索引接口時必須通過自己的編碼來保證並發環境下的事務一致性，這使得客戶端應用伺服器的開發變得複雜，缺乏對不同索引操作的普適支持。綜上所述，為了在雲存儲系統中提供高效的結構化查詢能力，開發一種有效的雲存儲系統下的索引系統有著重要的意義。
發明內容針對上述問題，本發明的目的是提供一種在雲存儲環境下能夠增強索引操作中的並發控制事務支持的分布式B+樹索引系統及構建方法。為實現上述目的，本發明採取以下技術方案一種分布式B+樹索引系統，其特徵在於它包括主伺服器、事務伺服器機群、索引伺服器機群和版本控制伺服器；所述事務伺服器機群包括多個事務伺服器，所述索引伺服器機群包括多個索引伺服器；所述主伺服器負責管理META數據，並對所述索引伺服器機群進行負載平衡調度；所述事務伺服器機群負責對分布式文件系統中索引數據訪問的事務控制；所述索引伺服器機群負責管理和讀寫所述分布式文件系統中的索引數據；所述版本控制伺服器負責在並發環境下所述索引伺服器機群中的索引數據備份的一致性控制；雲存儲系統通過所述事務伺服器機群向所述索弓I伺服器機群並發起事務基本操作。所述負載平衡調度包括當有新索引數據插入系統時，所述主伺服器調度當前負載較低的所述索弓I伺服器來管理所述新索弓I數據。一種實現如權利要求1或2所述系統的分布式B+樹索引構建方法，其步驟包括1)雲存儲系統發起事務訪問請求，事務伺服器機群將所述事務訪問請求分解為若干事務基本操作，同類事務基本操作組成事務基本操作序列；2)所述索引伺服器根據所述事務基本操作序列中的讀操作，讀取分布式文件系統中的索引數據並進行備份；其餘事務基本操作序列緩存在所述事務伺服器機群中；3)各索引伺服器結合有效性驗證條件對事務基本操作序列進行事務有效性驗證；4)如果所述事務伺服器機群接收到的各個索引伺服器的事務有效性驗證返回結果都為成功，則執行步驟5);否則各個索引伺服器從緩衝區中將所述事務訪問請求的事務基本操作序列刪除，所述事務伺服器機群向所述雲存儲系統發送事務執行結果為失敗；5)所述各索引伺服器執行緩存在所述索引伺服器機群中的除寫操作之外的其餘事務基本操作序列，之後將操作執行結果保存在副本中，執行寫操作，返回提交成功結果給所述事務伺服器機群，如果所述事務伺服器機群收到的所有所述索引伺服器的操作執行結果都為成功，則執行步驟6);如果存在某個索引伺服器的操作執行結果為失敗，各個索引伺服器將所述副本刪除，所述事務伺服器機群向所述雲存儲系統發送事務執行結果為失敗；6)所述各索引伺服器將所述副本標記為已提交版本儲存在所述分布式文件系統中；之後所述事務伺服器機群向所述雲存儲系統發送所述操作執行結果的返回值；7)所述雲存儲系統將所述事務伺服器機群的各個所述事務基本操作執行結果進行歸併，得到滿足所述事務訪問請求的索引數據。所述步驟2)中，主伺服器對具有索引數據備份的索引伺服器進行選擇，選擇相對空閒的索引伺服器響應事務基本操作序列。所述步驟3)中，所述有效性驗證條件根據所述雲存儲系統設定的事務一致性級別定製。所述步驟3)中，所述事務基本操作序列包括當前索引伺服器正在執行的或已執行完成，但執行結束時間晚於當前事務基本操作序列開始時間的事務基本操作序列。所述事務基本操作的類別包括獲取下一個結點操作、讀操作、寫操作、分裂操作和合併操作。本發明由於採取以上技術方案，其具有以下優點1、本發明由於採用主伺服器對各索引伺服器進行負載平衡調度，使得索引結構具有良好的擴展性，支持依據主屬性外的其他屬性上的檢索條件進行査詢，從而提高査詢效率。2、本發明的事務伺服器將客戶端發出的事務訪問請求分解成若干個事物基本操作，再將事物基本操作按照類別組成事物基本操作序列發送到對應的索引伺服器中，使得本發明的系統能夠在雲環境下顯著得提高結構化查詢的效率。3、本發明提出了一種細粒度、小網絡流量的索引上的事務機制，由於本發明的事務基本操作是基於B+樹的鍵值粒度，事務基本操作在執行時只需要傳輸幾十個字節的B+樹索引鍵值對，而現有方法的事務機制是基於B+樹結點粒度，一般以幾K個字節大小的B+樹結點作為基本單位進行傳輸，因此本發明有效地實現了並發環境下索引數據的事務功能。圖1是本發明分布式B+樹索引系統框架示意圖圖2是本發明分布式B+樹索引中事務執行的流程示意圖具體實施例方式下面結合附圖和實施例對本發明進行詳細的描述。本發明提供了一種基於雲存儲環境下的分布式B+樹索引構建方法及系統，可以直接獲取到滿足用戶查詢條件的網頁的存儲位置信息，從而直接獲取網頁數據返回給用戶，而不再需要遍歷整個系統中保存的網頁集合，極大地提高了索引效率。其中，B+樹索引是一種綜合效率較高的用於資料庫索引的數據結構，其特點在於所有的關鍵字都出現在葉子結點的鍊表中，且鍊表中的關鍵字恰好是有序的；搜索只有達到葉子結點才結束；搜索過程等價於在關鍵字全集內做一次二分查找；非葉子結點相當於葉子結點的索引，葉子結點相當於存儲索引數據的數據層。如圖1所示，本發明的分布式B+樹索引系統包括主伺服器1、事務伺服器機群2、索引伺服器機群3和版本控制伺服器4。其中，事務伺服器機群2包括多個事務伺服器21，索引伺服器機群3包括多臺索引伺服器31。主伺服器l負責管理分布式B+樹索引系統中的META數據。當有新的索引伺服器31進入索引伺服器機群3時，由主伺服器1對索引伺服器機群3進行負載平衡調度使得系統具有良好的擴展性。當有新的索引數據插入分布式B+樹索引系統時，主伺服器l調度當前負載較低的索引伺服器31來管理新索引數據。事務伺服器機群2負責對分布式文件系統6中索引數據訪問的事務控制，由事務伺服器21將雲存儲系統5發出的事務訪問請求分解成若干個由同類事務基本操作組成的事物基本操作序列，通過這些事務基本操作序列訪問索弓I伺服器機群3獲得索引數據並返回雲存儲系統5。索引伺服器機群3負責管理和讀寫分布式文件系統6中的索引數據，每臺索引伺服器31管理若干個B+樹結點。版本控制伺服器4負責在並發環境下索引伺服器機群3中索引數據的一致性控制。索引數據存儲在分布式文件系統6中，由索引伺服器機群3通過相應的接口進行訪問。雲存儲系統5不直接連接索引伺服器機群3，而是通過事務伺服器機群2向索引伺服器機群3並發起事務基本操作。本發明採用了數據備份技術來提高分布式B+樹索引系統的訪問效率，即當索引伺服器31執行事務伺服器機群2的讀操作請求，從分布式文件系統6中讀取索引數據後，版本控制伺服器4將每個索引數據進行備份，之後將索引數據備份統一發送到索引伺服器31上，通過版本控制伺服器4來維護索引數據備份在各個索引伺服器31上的一致性。本發明採用異步的方式對索引伺服器機群3進行數據維護，即在創建一個B+樹的結點時，由主伺服器1選擇一臺索引伺服器31作為該結點對應的索引主伺服器；所有對當前結點的更新操作首先發送到其對應的索引主伺服器上執行，當前索引主伺服器執行完畢後通知版本控制伺服器4;由版本控制伺服器4在適當的時候將更新操作發送到存儲當前索引數據備份的索引伺服器31進行更新。當索引伺服器機群3收到事務伺服器機群2發出的事務基本操作序列時，由主伺服器1對備份有相應索引數據備份的索引伺服器31進行選擇，選擇其中相對"空閒"的索引伺服器31來響應事務伺服器機群2發出的事務基本操作序列。如圖2所示，本發明的分布式B+樹索引系統的構建方法包括以下步驟1、雲存儲系統5發起事務訪問請求，事務伺服器機群2根據事務訪問請求的操作內容，將當前事務訪問請求分解為若干事務基本操作，同類事務基本操作組成事務基本操作序列。本發明的實施例中，事務基本操作的種類包括1)獲取下一個結點操作getnext(ts，node,key)，即返回搜索鍵值key時，與當前結點node相適應的下一級結點指針；2)讀操作read(ts，node,keyset),即返回由當前結點node指定的鍵值key所對應的鍵值對keyset;3)寫操作write(ts，node,keyset,valueset，op)，即根據參數叩所指定的操作類型的不同，對當前結點node進行對應的寫操作，寫操作的操作類型包括插入操作、刪除操作和更新操作;4)分裂操作Split(tS，nodel，node2)，即將當前結點node分裂為兩個結點nodel和node2，node2為nodel的右鄰居；5)合併操作Merge(ts，nodel，node2)，即將當前結點nodel和它的右鄰居node2結點合併為一個新結點。2、事務伺服器機群2將事務基本操作序列中的各個讀操作read發送給一個索引伺服器31，將其餘操作緩存在事務伺服器機群2中。索引伺服器31根據讀操作read的請求讀取分布式文件系統6中的索引數據，並通過上述的數據備份技術對索引數據進行備份。同時事務伺服器機群2將雲存儲系統5的其他各類事務基本操作序列分別發送到索引伺服器機群3的索引伺服器31中。主伺服器1對具有相應索引數據備份的索引伺服器31進行選擇，選擇其中相對"空閒"的索引伺服器31來響應這些事務基本操作序列。3、各索引伺服器31將接收到的事務基本操作序列保存在緩衝區中，並根據云存儲系統5設定的事務一致性級別來定製事務有效性驗證條件。結合事務有效性驗證條件，以及當前索引伺服器31正在執行的或已執行完成，但執行結束時間晚於當前事務基本操作序列開始時間的事務基本操作序列進行事務有效性驗證。4、如果事務伺服器機群2接收到的各個索引伺服器31的事務有效性驗證返回結果都為成功，則事務有效性驗證通過，執行步驟5;否則事務有效性驗證返回結果為失敗，事務伺服器機群2向各個索引伺服器31發送回滾請求，各個索引伺服器31從緩衝區中將該事務訪問請求的事務基本操作序列刪除，事務伺服器機群2向對應的雲存儲系統5發送事務執行結果為失敗。5、事務伺服器機群2向各個索引伺服器31發送事務提交請求，索引伺服器31在收到事務提交請求後，執行索引伺服器31的緩衝區中的除寫操作write之外的其餘事務基本操作序列，之後將操作執行結果保存在副本中。執行事務伺服器機群2中的寫操作write，將生成的副本寫入分布式文件系統6中，返回提交成功結果給事務伺服器機群2。如果事務伺服器機群2收到的所有索引伺服器31返回的操作執行結果都為成功，則執行步驟6;如果存在某個索引伺服器31返回的操作執行結果為失敗，事務伺服器機群2向索引伺服器機群3發送提交失敗請求，各個索引伺服器31將生成的副本刪除，事務伺服器機群2向對應的雲存儲系統5發送事務執行結果為失敗。6、事務伺服器機群2向索引伺服器機群3發出提交成功請求，各個索引伺服器31從分布式文件系統6中讀取生成的副本，並將其標記為已提交版本後儲存在分布式文件系統6中，供當雲存儲系統5發起新的事務訪問請求時讀寫。之後事務伺服器機群2向對應的雲存儲系統5發送操作執行結果的返回值以及事務執行結果為成功。7、雲存儲系統5將事務伺服器機群2的各個事務基本操作執行的返回值進行歸併，得到滿足事務訪問請求的索引數據。下面通過一實施例，對本發明的方法和系統進一步說明現有一分布式文件系統6中存儲了從新浪2008年8月至今的新聞網頁集合，數據量約佔400G字節，新聞網頁集合中每個網頁保存的屬性有網頁內容、標題、日期和作者的信息。假設現有用戶請求查詢所有從2008年8月8日到2008年9月1日之間作者為"沈飛"的新浪新聞網頁，如果利用現有技術中的索引系統，雲存儲系統5隻能通過遍歷這400G字節的數據的方式進行査詢；如果利用本發明的分布式B+樹索引系統，雲存儲系統5查詢流程如下i)雲存儲系統5向分布式B+樹索引系統發出事務訪問請求，事務訪問請求的內容為分別查詢日期為2008年8月8日至2008年9月1日間的網頁以及作者索引值為"沈飛"的網頁。ii)分布式B+樹索引系統在事務伺服器機群2中將該事務訪問請求分解為兩類事務基本操作序列，包括若干個獲取下一個結點操作getnext和若干個讀操作read,並發送到相應的索引伺服器31上執行。iii)兩個索引伺服器31將各自收到的事務基本操作序列保存在緩衝區中，然後對事務有效性進行驗證，如果事務有效性驗證通過，則事務伺服器機群2向索引伺服器31發送事務提交請求，執行步驟iv);如果驗證失敗，則執行步驟v)。iv)索引伺服器31執行事務基本操作的序列，將執行結果保存在副本中，並提交執行成功結果給事務伺服器機群2。v)事務伺服器機群2向各個索引伺服器31發送回滾請求，各個索引伺服器31從緩衝區中將該事務訪問請求的事務基本操作序列刪除，事務伺服器21向對應的雲存儲系統5發送事務執行結果為失敗。vi)若所有索引伺服器31都提交成功，則事務伺服器機群2將獲取索引伺服器31返回的索引數據，即存儲日期2008年8月8日至2008年9月1日間的網頁的伺服器及磁碟位置以及作者為"沈飛"的網頁的伺服器及磁碟位置，索引伺服器31將該結果通過事務伺服器21返回給雲存儲系統5，執行步驟vii)。若某個索引伺服器31提交失敗，則事務伺服器機群2向索引伺服器31發送刪除各個副本的請求，並向對應的雲存儲系統5發送事務執行結果為失敗。vii)雲存儲系統5將這兩個結果進行歸併後，得到滿足雲存儲系統5事務訪問請求的索引數據所在分布式文件系統6中的伺服器及磁碟位置列表，即獲取網頁數據的存儲位置，再依據此列表獲取網頁數據並返回給雲存儲系統5。綜上所述，通過本發明的分布式B+樹索引系統，雲存儲系統5可以直接獲取到滿足查詢條件的網頁的存儲位置信息，從而直接從分布式文件系統6中獲取網頁數據返回給用戶，而不再需要遍歷整個分布式文件系統6中保存的網頁集合。本發明的方法是一種細粒度、小網絡流量的事務機制，由於事務基本操作是基於B+樹的鍵值粒度，因此在執行事務基本操作時只需要傳輸幾十個字節的B+樹索引鍵值對，而現有方法的事務機制是基於B+樹結點粒度，一般以幾K個字節大小的B+樹結點作為基本單位進行傳輸，因此本發明有效地實現了並發環境下索引數據的事務功能。權利要求1、一種分布式B+樹索引系統，其特徵在於它包括主伺服器、事務伺服器機群、索引伺服器機群和版本控制伺服器；所述事務伺服器機群包括多個事務伺服器，所述索引伺服器機群包括多個索引伺服器；所述主伺服器負責管理META數據，並對所述索引伺服器機群進行負載平衡調度；所述事務伺服器機群負責對分布式文件系統中索引數據訪問的事務控制；所述索引伺服器機群負責管理和讀寫所述分布式文件系統中的索引數據；所述版本控制伺服器負責在並發環境下所述索引伺服器機群中的索引數據備份的一致性控制；雲存儲系統通過所述事務伺服器機群向所述索引伺服器機群並發起事務基本操作。2、如權利要求l所述的一種分布式B+樹索引系統，其特徵在於所述負載平衡調度包括當有新索引數據插入系統時，所述主伺服器調度當前負載較低的所述索弓I伺服器來管理所述新索弓I數據。3、一種實現如權利要求1或2所述系統的分布式B+樹索引構建方法，其步驟包括1)雲存儲系統發起事務訪問請求，事務伺服器機群將所述事務訪問請求分解為若干事務基本操作，同類事務基本操作組成事務基本操作序列；2)所述索引伺服器根據所述事務基本操作序列中的讀操作，讀取分布式文件系統中的索引數據並進行備份；其餘事務基本操作序列緩存在所述事務伺服器機群中；3)各索引伺服器結合有效性驗證條件對事務基本操作序列進行事務有效性驗證；4)如果所述事務伺服器機群接收到的各個索引伺服器的事務有效性驗證返回結果都為成功，則執行步驟5);否則各個索引伺服器從緩衝區中將所述事務訪問請求的事務基本操作序列刪除，所述事務伺服器機群向所述雲存儲系統發送事務執行結果為失敗；5)所述各索引伺服器執行緩存在所述索引伺服器機群中的除寫操作之外的其餘事務基本操作序列，之後將操作執行結果保存在副本中，執行寫操作，返回提交成功結果給所述事務伺服器機群，如果所述事務伺服器機群收到的所有所述索引伺服器的操作執行結果都為成功，則執行步驟6);如果存在某個索引伺服器的操作執行結果為失敗，各個索引伺服器將所述副本刪除，所述事務伺服器機群向所述雲存儲系統發送事務執行結果為失敗；6)所述各索引伺服器將所述副本標記為已提交版本儲存在所述分布式文件系統中；之後所述事務伺服器機群向所述雲存儲系統發送所述操作執行結果的返回值；7)所述雲存儲系統將所述事務伺服器機群的各個所述事務基本操作執行結果進行歸併，得到滿足所述事務訪問請求的索引數據。4、如權利要求3所述的一種分布式B+樹索引構建方法，其特徵在於所述步驟2)中，主伺服器對具有索引數據備份的索引伺服器進行選擇，選擇相對空閒的索引伺服器響應事務基本操作序列。5、如權利要求3所述的一種分布式B+樹索引構建方法，其特徵在於所述步驟3)中，所述有效性驗證條件根據所述雲存儲系統設定的事務一致性級別定製。6、如權利要求4所述的一種分布式B+樹索引構建方法，其特徵在於所述步驟3)中，所述有效性驗證條件根據所述雲存儲系統設定的事務一致性級別定製。7、如權利要求3或4或5或6所述的一種分布式B+樹索引構建方法，其特徵在於所述步驟3)中，所述事務基本操作序列包括當前索引伺服器正在執行的或已執行完成，但執行結束時間晚於當前事務基本操作序列開始時間的事務基本操作序列。8、如權利要求3或4或5或6所述的一種分布式B+樹索引構建方法，其特徵在於所述事務基本操作的類別包括獲取下一個結點操作、讀操作、寫操作、分裂操作和合併操作。9、如權利要求7所述的一種分布式B+樹索引構建方法，其特徵在於所述事務基本操作的類別包括獲取下一個結點操作、讀操作、寫操作、分裂操作和合併操作。全文摘要本發明涉及一種分布式B+樹索引系統及構建方法，其特徵在於它包括主伺服器、事務伺服器機群、索引伺服器機群和版本控制伺服器；事務伺服器機群包括多個事務伺服器，索引伺服器機群包括多臺索引伺服器；主伺服器負責管理META數據，並對索引伺服器機群進行負載平衡調度；事務伺服器機群負責對分布式文件系統中索引數據訪問的事務控制；索引伺服器機群負責管理和讀寫分布式文件系統中的索引數據。本發明提出了一種細粒度、小網絡流量的索引事務機制，由於本發明的事務基本操作是基於B+樹的鍵值粒度，事務基本操作在執行時只需要傳輸幾十個字節的B+樹索引鍵值對，因此本發明有效地實現了並發環境下索引數據的事務功能。文檔編號G06F17/30GK101576915SQ20091008707公開日2009年11月11日申請日期2009年6月18日優先權日2009年6月18日發明者楊冬青,成湯,王騰蛟,軍高申請人:北京大學