分布式順序表片內二級索引方法及系統的製作方法
2023-05-30 00:09:06 1
分布式順序表片內二級索引方法及系統的製作方法
【專利摘要】本發明公開了一種分布式順序表片內二級索引方法及系統，其中系統包括，索引布局管理模塊，為每個數據存儲文件創建對應的索引存儲文件；一致性更新模塊，寫入數據時，先將該數據寫入預寫日誌中，再寫入內存存儲中，若該內存存儲中該數據部分丟失，將該預寫入日誌中未成功寫入磁碟上的該數據重新寫入該內存存儲中；內存存儲刷寫模塊，若該內存存儲存量達到某閾值，先生成該內存存儲中類型不為「刪除」的數據記錄對應的索引記錄，並刷寫該索引記錄到該磁碟上生成該索引存儲文件，再生成數據存儲文件；合併和分裂模塊，索引存儲文件隨著數據存儲文件一起合併和分裂，保證兩者的一致性；多維區間查詢模塊，對每個數據分片單獨查詢，一次查詢可使用多列索引。
【專利說明】分布式順序表片內二級索引方法及系統
【技術領域】
[0001]本發明涉及分布式順序表信息處理技術，特別涉及一種分布式順序表片內二級索引方法及系統。
【背景技術】
[0002]分布式順序表(Distributed Ordered Table簡稱DOT)是一種最適用於海量數據下多維區間查詢的資料庫系統，與本專利相關的現有技術是一個名為「一種對分布式順序表進行多維區間查詢的方法及其系統」的專利，專利號為201210517589.3，其實現方案包括，分別為所述分布式順序表的每個索引列創建一張對應的二級索引表，各索引列對應的二級索引表的主鍵為該列值、所述分布式順序表的主鍵值和該列值的長度三者的拼接值；當接收到區間查詢請求時，依據所述查詢請求的欄位名稱，從各所述二級索引表中查找所述欄位名稱對應的二級索引表，依據所述查詢請求的欄位值，從所述對應的二級索引表中查找所述查詢請求欄位值對應的記錄位置，直接從所述分布式順序表中的該記錄位置讀取相應的數據。該現有技術的缺點和不足包括如下幾個方面:
[0003](I)需要更改原來機制或增加新的機制來保證數據和索引的一致性。因為分布式順序表缺少跨表、跨行的事務支持，所以必須要更改原有的預寫日誌機制或者額外添加一致性保證機制來保證索引和數據的一致性。
[0004](2)數據寫入性能下降嚴重。由於額外的索引操作開銷，在對表進行寫入操作的時候的性能將會有很大下降，而且索引越多，寫入性能下降也越多。
[0005](3)查詢性能不好，僅對較小的查詢有加速效果。對於大多數多維區間查詢，這種索引帶來的速度提升很有限，因為數據表數據讀取速度慢，客戶端和服務端的來回網絡開銷大，只有在查詢很小的時候才相對於全表掃描有速度上的優勢。
[0006](4)索引帶來的額外存儲開銷較大。直接使用存儲數據的數據結構來存儲索引，沒有針對索引存儲的特點進行優化，會存儲一些無用的數據，存儲開銷較大。
[0007](5) 一次查詢不能使用多列索引。在一次多維區間查詢中，因為索引的讀取和對數據表的讀取都在客戶端完成，客戶端資源有限，在面對存儲海量數據的分布式順序表的時候，客戶端難以完成多個索引數據合併的任務。索引不能用於帶聚集函數的服務端計算。服務端計算是單獨處理每個數據分片，對局部數據進行計算，該索引是一種全局的索引，無法對索引進行劃分獲得局部數據對應的索引。
[0008]發明人在進行分布式順序表索引及多維區間查詢技術研究時，發現現有技術中的缺陷是因為在較高的存儲層級，即表級維護索引，沒有針對索引存儲、使用特點，以及分布式順序表設計原理、內部結構特點來設計和優化索引導致的，發明人經過對索引和分布式順序表的特點進行深入研究發現，解決該項缺陷可以通過在更低的存儲級別，即存儲文件級來維護索引，重新設計專用的索引存儲結構，充分利用分布式順序表的框架來維護和管理索引的方法來實現。
【發明內容】
[0009]為解決上述問題，本發明提出了一種分布式順序表片內二級索引方法及系統，本發明通過對索引和分布式順序表的特點進行深入研究，重新設計索引存儲結構，來減小索引存儲開銷，提高索引查詢性能，解決了一次查詢不能使用多列索引，索引不能用於服務端計算等問題，通過一致性更新模塊、合併和分裂模塊保證索引和數據的一致性，通過內存存儲刷與1旲塊提聞數據與入性能。
[0010]為了達到本發明的目的，本發明提供了一種分布式順序表片內二級索引方法，包括如下步驟:
[0011]SI索引布局管理步驟，為分布式順序表的每個數據分片中的每個數據存儲文件創建對應的索引存儲文件，該索引存儲文件存儲列名、列值、主鍵；
[0012]S2 一致性更新步驟，向該分布式順序表寫入數據時，先將該數據寫入預寫日誌中，再寫入內存存儲中，若該內存存儲中該數據部分丟失，將該預寫入日誌中未成功寫入磁碟上的該數據重新寫入該內存存儲中；
[0013]S3內存存儲刷寫步驟，若該內存存儲存量達到某閾值，先生成該內存存儲中類型不為「刪除」的數據記錄對應的索引記錄，並刷寫該索引記錄到該磁碟上生成該索引存儲文件，再刷寫數據記錄到磁碟上生成該數據存儲文件；
[0014]S4合併和分裂步驟，在數據分片合併時，先將多個索引存儲文件合併成一個新的索引存儲文件，再將對應的多個數據存儲文件合併成一個新的數據存儲文件；以及
[0015]在該數據片按照某主鍵分裂成兩個新數據分片時，首先將該數據分片內的每個索引存儲文件按照該主鍵分裂成兩個新索引存儲文件後分別加入到所述兩個新數據分片中，然後再把該數據分片內的每個數據存儲文件按照該主鍵分裂成兩個新數據存儲文件後分別加入到所述的兩個新的數據分片中；
[0016]S5多維區間查詢步驟，對該分布式順序表進行多維區間查詢時，按照查詢條件對每個數據分片單獨查詢，查詢時對該查詢條件進行預處理得到索引查詢條件，再依次單獨查詢每列索引、合併多列索引查詢結果、讀取滿足該索引查詢條件的該些數據作為最終查詢結果。
[0017]所述一種分布式順序表片內二級索引方法，該索引存儲文件結構包括:多個記錄塊，記錄塊索引，文件信息和結尾，每個記錄塊存儲多條索引記錄，保存每個記錄塊中第一條索引記錄作為記錄塊索引。
[0018]所述分布式順序表片內二級索引方法，該索引記錄結構使用鍵值對結構存儲，鍵主要包括列值和列名，值主要包括主鍵，鍵長度、值長度和列名長度都是用於快速讀取索引記錄的某部分。
[0019]所述一種分布式順序表片內二級索引方法，該多維區間查詢步驟S5還包括:
[0020]在查詢每個索引存儲文件時，直接二分查找該塊索引，快速查找開始、結束記錄塊的偏移位置，然後直接讀取中間所有的記錄塊以獲取滿足該索引查詢條件的主鍵集合。
[0021]所述一種分布式順序表片內二級索引方法，該多維區間查詢步驟S5還包括:
[0022]S51預處理步驟，用戶對該分布式順序表進行多維區間查詢時，將查詢條件發送到每個數據分片後預處理該查詢條件，獲得索引查詢條件；
[0023]S52讀取主鍵步驟，分別從該索引存儲文件和該內存存儲中查找滿足該索引查詢條件的索引記錄和數據記錄，並分別讀取該索引記錄和該數據記錄的主鍵，得到主鍵集合；
[0024]S53合併主鍵步驟，按照該索引查詢條件間關係和該查詢規模大小次序合併該主鍵集合，按主鍵排序後得到最終主鍵集合；
[0025]S54結果集生成步驟，依據最終主鍵集合查詢該數據分片中數據，並把滿足該索引查詢條件的數據放入結果集中；
[0026]S55合併結果集步驟，合併每個數據分片的結果集得到最終的查詢結果集，並把該最終的查詢結果集返回給該用戶。
[0027]本發明還涉及一種分布式順序表片內二級索引系統，包括:
[0028]索引布局管理模塊，用於為所述分布式順序表的每個數據分片中的每個數據存儲文件創建對應的索引存儲文件，該索引存儲文件存儲列名、列值、主鍵；
[0029]一致性更新模塊，向該分布式順序表寫入數據時，先將該數據寫入預寫日誌中，再寫入內存存儲中，若該內存存儲中該數據部分丟失，將該預寫入日誌中部分未成功寫入磁碟上的該數據重新寫入該內存存儲中；
[0030]內存存儲刷寫模塊，若該內存存儲存量達到某閾值，先生成該內存存儲中類型不為「刪除」的數據記錄對應的索引記錄，並刷寫該索引記錄到該磁碟上生成該索引存儲文件，再刷寫數據記錄到磁碟上生成該數據存儲文件；
[0031]合併和分裂模塊，在數據分片合併時，先將多個索引存儲文件合併成一個新的索引存儲文件，再將對應的多個數據存儲文件合併成一個新的數據存儲文件；以及
[0032]在該數據分片按照某主鍵分裂成兩個數據分片時，首先將該數據分片內的每個索引存儲文件按照該主鍵分裂成兩個索引存儲文件後分別加入到所述兩個新的數據分片中，然後再把該數據分片內的每個數據存儲文件按照所述主鍵分裂成兩個數據存儲文件後分別加入到所述的兩個新的數據分片中；
[0033]多維區間查詢模塊，用於該分布式順序表接收多維區間查詢條件，按照該查詢條件對每個數據分片單獨查詢，查詢時對該查詢條件進行預處理得到索引查詢條件，再依次單獨查詢每列索引、合併多列索引查詢結果、讀取滿足該列索引查詢條件的該些數據作為最終查詢結果。
[0034]所述一種分布式順序表片內二級索引系統，該索引存儲文件結構包括:多個記錄塊，記錄塊索引，文件信息和結尾，每個記錄塊存儲多條索引記錄，保存每個記錄塊中第一條索引記錄作為記錄塊索引。
[0035]所述一種分布式順序表片內二級索引系統，該多維區間查詢模塊還包括:
[0036]在查詢每個索引存儲文件時，直接二分查找塊索引，快速查找開始、結束記錄塊的偏移位置，然後直接讀取中間所有的記錄塊以獲取滿足該索引查詢條件的主鍵集合。
[0037]所述分布式順序表片內二級索引系統，該索引記錄結構使用鍵值對結構存儲，鍵主要包括列值和列名，值主要包括主鍵，鍵長度、值長度和列名長度都是用於快速讀取索引記錄的某部分。
[0038]所述一種分布式順序表片內二級索引系統，該多維區間查詢模塊還包括:
[0039]預處理模塊，用於用戶對該分布式順序表進行多維區間查詢時，將查詢條件發送到每個數據分片後預處理該查詢條件，獲得索引查詢條件；
[0040]讀取主鍵模塊，用於分別從索引存儲文件和內存存儲中查找滿足該索引查詢條件的索引記錄和數據記錄，並分別讀取該索引記錄和該數據記錄的主鍵，得到主鍵集合；
[0041]合併主鍵模塊，用於按照該索引查詢條件間關係和該查詢規模大小次序合併該主鍵集合，按主鍵排序後得到最終主鍵集合；
[0042]結果集生成模塊，用於依據最終主鍵集合查詢該數據分片中數據，並把滿足該索引查詢條件的數據放入結果集中；
[0043]合併結果集模塊，用於合併每個數據分片的結果集得到最終的查詢結果集，並把該查詢結果集返回給該用戶。
[0044]由以上方案可知，本發明的優點在於:
[0045](I)通過改變內存存儲刷寫過程即可保證數據記錄和索引記錄的一致性。僅在內存存儲刷寫的時候生成索引記錄，不需要對原有的數據恢復機製做任何的更改即可保證該內存存儲中數據對應的索引不丟失，索引存儲文件隨著數據存儲文件一起變遷，保證該索引存儲文件中的索引不丟失，因此可以保證整個系統中索引和數據的一致性。
[0046](2)數據寫入性能下降較小。由於沒有在寫入過程中沒有為索引引入額外的開銷，特別是為了保證一致性的額外開銷，僅在內存存儲刷寫時生成索引記錄，寫入性能增加。
[0047](3)查詢性能好。索引記錄和數據記錄讀取都在數據分片內，避免了大量的來回網絡時間開銷，經過查詢條件預處理、去掉較大查詢規模的索引查詢條件、按照查詢規模從小到大合併主鍵集合、最終主鍵集合排序等優化技術，查詢性能有大幅度提升。
[0048](4)索引帶來的額外存儲開銷較小。使用重新設計的專用數據結構來存儲索引可以把索引的存儲開銷壓縮到最小。
[0049](5) 一次查詢能使用多列索引。查詢是對每個數據分片單獨進行，絕大多數情況下每個數據分片內的數據量不會太大，可以使用內存對多個索引的查詢結果進行合併，故一次查詢可以使用多列索引。
[0050](6)索引能用於帶聚集函數的服務端計算。索引的使用是在數據分片內，對服務端計算完全透明，服務端計算可以使用索引查詢數據。
【專利附圖】
【附圖說明】
[0051]圖1為分布式順序表片內二級索引布局示意圖；
[0052]圖2為分布式順序表片內二級索引記錄結構圖；
[0053]圖3為分布式順序表片內二級索引存儲文件結構圖；
[0054]圖4為分布式順序表片內二級索引組織示意圖；
[0055]圖5為分布式順序表片內二級索引多維區間查詢流程圖；
[0056]其中附圖標記為:分布式順序表片內二級索引多維區間查詢步驟:
[0057]S51, S52, S53, S54, S55
【具體實施方式】
[0058]下面給出【具體實施方式】，結合附圖對本發明做出詳細的描述，但不作為對本發明的限定。
[0059]本發明提出了一種分布式順序表片內二級索引方法及系統。具體而言，本發明將使用重新設計的專用數據結構來存儲索引，可以把索引的存儲開銷壓縮到最小，同時索引的讀寫性能更好，本發明通過更改內存存儲的刷寫過程，不需要對原有的數據恢復機製做任何的更改即可保證內存存儲中數據對應的索引不丟失，保證了內存存儲中索引和數據的一致性，本發明通過更改合併和分裂流程，保證了存儲文件中索引和數據的一致性，本發明是對每個數據分片單獨進行查詢，絕大多數情況下每個數據分片內的數據量不會太大，可以使用內存對多個索引的查詢結果進行合併，故一次查詢可以使用多列索引。同時，索引的使用是在數據分片內，對服務端計算完全透明，服務端計算可以使用索引查詢數據。另外，索引和數據讀取都在數據分片內，避免了大量的來回網絡時間開銷，查詢性能大幅提升，經過查詢條件預處理、去掉較大查詢規模的索引查詢條件、按照查詢規模從小到大合併主鍵集合、最終主鍵集合排序等優化技術，查詢性能有進一步地大幅度提升。
[0060]為了完成上述過程，本發明提供一種分布式順序表片內二級索引方法，所述方法包括:
[0061]SI索引布局管理步驟，如圖1所示，為所述分布式順序表的每個數據分片中的每個數據存儲文件創建對應的索引存儲文件，該索引存儲文件存儲列名、列值、主鍵；
[0062]S2 一致性更新步驟，向該分布式順序表寫入數據時，先將該數據寫入預寫日誌中，再寫入內存存儲中，若該內存存儲中該數據部分丟失，將該預寫入日誌中部分未成功寫入磁碟上的該數據重新寫入該內存存儲中；
[0063]S3內存存儲刷寫步驟，若該內存存儲存量達到某閾值，先生成該內存存儲中類型不為「刪除」的數據記錄對應的索引記錄，並刷寫該索引記錄到該磁碟上生成該索引存儲文件，再刷寫數據記錄到磁碟上生成該數據存儲文件；
[0064]S4合併和分裂步驟，在數據分片合併時，先將多個索引存儲文件合併成一個新的索引存儲文件，再將對應的多個數據存儲文件合併成一個新的數據存儲文件；以及
[0065]在該數據分片按照某主鍵分裂成兩個數據片時，首先將該數據分片內的每個索引存儲文件按照該主鍵分裂成兩個索引存儲文件後分別加入到所述兩個新的數據分片中，然後再把該數據分片內的每個數據存儲文件按照所述主鍵分裂成兩個數據存儲文件後分別加入到所述的兩個新的數據分片中；
[0066]S5多維區間查詢步驟，該分布式順序表接收多維區間查詢條件，按照該查詢條件對每個數據分片單獨查詢，查詢時對該查詢條件進行預處理得到索引查詢條件，再依次單獨查詢每列索引、合併多列索引查詢結果、讀取數據作為最終查詢結果。
[0067]如圖2所示，該索引記錄結構使用鍵值對數據結構存儲，「鍵」包括列名和列值，「值」包括包括主鍵，鍵長度、值長度和列名長度都是用於快速讀取索引記錄的某個部分。索弓I記錄依次按照列名、列值、主鍵來排序。
[0068]如圖3所示，該索引存儲文件結構包括:多個記錄塊，記錄塊索引，文件信息和結尾，每個記錄塊存儲多條索引記錄，保存每個記錄塊中第一條索引記錄作為記錄塊索引，在查詢每個索引存儲文件時，直接二分查找塊索引，快速查找開始、結束記錄塊的偏移位置，然後直接讀取中間所有的記錄塊以獲取滿足該索引查詢條件的主鍵集合。該文件信息中存儲的是文件的幾個統計數據，大小不是固定的，該結尾的大小是固定的，存儲各部分的偏移和一些其他文件統計信息。
[0069]如圖4所示，本發明具體實施所述的面向分布式順序表的片內二級索引的索引組織示例。所述分布式順序表共有三列，即Cl，c2和c3。為其中兩列Cl和c2分別添加片內二級索引，系統會為每個數據存儲文件維護對應的索引存儲文件，並且把該數據存儲文件中Cl和c2兩列的類型不為「刪除」的數據記錄寫入到該索引存儲文件中，cl、c2為索引列，c3為非索引列。該數據存儲文件中每條數據記錄有五個屬性:主鍵、列名、時間戳、類型和列值，並依次按照主鍵、列名、時間戳和類型排序，該索引存儲文件中每條索引記錄有三個屬性:列名、列值和主鍵，並依次按照列名、列值、主鍵排序。
[0070]所述一種分布式順序表片內二級索引方法，該多維區間查詢步驟S5還包括:
[0071]S51預處理步驟，用戶對該分布式順序表進行多維區間查詢時，將查詢條件發送到每個數據分片後預處理該查詢條件，獲得索引查詢條件；進一步地說，當接收到區間查詢請求時，把查詢請求分別送到每個數據分片，在數據分片內，首先對所述查詢請求中的查詢條件進行條件合併和去重、索引條件篩選和較大查詢規模的索引條件去除等預處理步驟，得到最終的索引查詢條件。
[0072]S52讀取主鍵步驟，分別從索引存儲文件和內存存儲中查找滿足該索引查詢條件的索引記錄和數據記錄，並分別讀取該索引記錄和該數據記錄的主鍵，得到主鍵集合；
[0073]S53合併主鍵步驟，按照該索引查詢條件間關係和該查詢規模大小次序合併該主鍵集合，按主鍵排序後得到最終主鍵集合；進一步說，按照索引查詢條件間的「與」或者「或」關係合併各自的主鍵集合，合併時按照查詢規模從小到大的順序進行，最後得到一個合併後的主鍵集合，對其按照主鍵進行排序，得到最終主鍵集合；
[0074]S54結果集生成步驟，依據最終主鍵集合查詢該數據分片中的數據，並把滿足該索引查詢條件的數據放入結果集中；進一步說，依據所述最終主鍵值集合，從該數據分片的所有數據存儲文件和內存存儲中讀取相應的數據，並用查詢條件對該數據進行篩選，把滿足該查詢條件的數據記錄放入查詢結果集中；
[0075]S55合併結果集步驟，合併每個數據分片的結果集得到最終的查詢結果集，並把該最終的查詢結果集返回給該用戶。
[0076]現在列舉本發明的一個實施例，下面的實施例基於Apache HBase來創建本發明所述的片內二級索引方法及系統，HBase是一種典型的分布式順序表,構建於ApacheHadoop (用於構建大規模共享存儲和計算設施的軟體)之上。一個HBase (分布式順序表)系統包括一個HMaster (主服務節點)和多個HReg1nServer (數據服務節點)。
[0077]本發明所述的片內二級索引採用HBase-0.94.16作為代碼基礎，採用Java語言實現。在HBase中為每個HReg1n (數據分片)中的每個HFile (數據存儲文件)維護一個對應的IndexFile (索引存儲文件)。與HFile存儲KeyValue (數據記錄)類似，IndexFile存儲IndexKeyValue (索引記錄)。IndexKeyValue是一種類似KeyValue的存儲結構，與KeyValue在存儲內容上的主要區別在於不存儲列名、時間戳和類型。KeyValue結構按照主鍵、列名、時間戳、類型、列值進行排序，而IndexKeyValue結構按照列名、列值、主鍵進行排序。另外，MemStore (內存存儲)中的數據不維護索引，在MemStore刷寫生成HFile的之前先生成對應的IndexFile。
[0078]在進行Minor (次)合併時，將多個小HFile合併成一個較大HFile的之前先將對應的多個IndexFile合併成一個大的IndexFile。在進行Major (主)合併時,在多個HFile合併成一個大的HFile之後，從新生成的HFile中生成IndexKeyValue列表後還需要在內存中進行排序，為了控制內存的使用，設置一個可以使用的最大內存量，在內存裝滿後，將排序好的IndexKeyValue刷寫到磁碟上生成臨時的IndexFile,最後再將多個臨時IndexFile合併成一個最終的IndexFile。
[0079]在HReg1n分裂時，父HReg1n中的HFile並沒有立即分裂，子HReg1n只是對父HReg1n中所有的HFile創建了一個對應的ReferenceFile (應用文件),在子HReg1n做合併的時候才會真正生成存有實際數據的HFile，合併之前都是通過讀取父HReg1n中被引用的HFile。基於這個原理,可以對HReg1n分裂過程不做任何更改,而是在HReg1n上線時，如果發現有ReferenceFile,就同時讀取被引用的HFile對應的IndexFile,在HReg1n合併之後真正生成自己的IndexFile。
[0080]在對數據表進行多維區間查詢時，把查詢請求分別送到每個HReg1n中單獨查詢。在每個HReg1n內查詢時，首先對查詢條件進行預處理，得到索引查詢條件，再查詢IndexFile中的索引和MemStore中的數據，得到滿足索引查詢條件的主鍵集合，然後對多個索引查詢條件的查詢結果進行合併，根據他們之間的關係和查詢規模大小次序合併各自得到主鍵集合，並對合併後的主鍵集合按照主鍵排序得到最終的主鍵集合，最後根據最終主鍵集合中的主鍵在HReg1n中的HFile和MemStore中讀出整行數據，並使用該查詢條件進一步判斷，把滿足該查詢條件的數據放入查詢結果集中。最後把每個HReg1n的查詢結果集進行合併，得到最終的查詢結果集。
[0081]本發明還涉及一種分布式順序表片內二級索引系統，包括:
[0082]索引布局管理模塊，用於為所述分布式順序表的每個數據分片中的每個數據存儲文件創建對應的索引存儲文件，該索引存儲文件存儲列名、列值、主鍵；
[0083]一致性更新模塊，向該分布式順序表寫入數據時，先將該數據寫入預寫日誌中，再寫入內存存儲中，若該內存存儲中該數據部分丟失，將該預寫入日誌中部分未成功寫入磁碟上的該數據重新寫入該內存存儲中；
[0084]內存存儲刷寫模塊，若該內存存儲存量達到某閾值，先生成該內存存儲中類型不為「刪除」的數據記錄對應的索引記錄，並刷寫該索引記錄到該磁碟上生成該索引存儲文件，再刷寫數據記錄到磁碟上生成該數據存儲文件；
[0085]合併和分裂模塊，在數據片合併時，先將多個索引存儲文件合併成一個新的索引存儲文件，再將對應的多個數據存儲文件合併成一個新的數據存儲文件；以及
[0086]在該數據片按照某主鍵分裂成兩個數據片時，首先將該數據分片內的每個索引存儲文件按照該主鍵分裂成兩個索引存儲文件後分別加入到所述兩個新的數據分片中，然後再把該數據分片內的每個數據存儲文件按照所述主鍵分裂成兩個數據存儲文件後分別加入到所述的兩個新的數據分片中；
[0087]多維區間查詢模塊，用於該分布式順序表接收多維區間查詢條件，按照該查詢條件對每個數據分片單獨查詢，查詢時對該查詢條件進行預處理得到索引查詢條件，再依次單獨查詢每列索引、合併多列索引查詢結果、讀取數據作為最終查詢結果。
[0088]所述一種分布式順序表片內二級索引系統，該索引存儲文件結構包括:多個記錄塊，記錄塊索引，文件信息和結尾，每個記錄塊存儲多條索引記錄，保存每個記錄塊中第一條索引記錄作為記錄塊索引。
[0089]所述一種分布式順序表片內二級索引系統，該索引記錄結構使用鍵值對數據結構存儲，「鍵」包括列名和列值，「值」包括包括主鍵，鍵長度、值長度和列名長度都是用於快速讀取索引記錄的某個部分。索引記錄依次按照列名、列值、主鍵來排序。
[0090]所述一種分布式順序表片內二級索引系統，該多維區間查詢模塊還包括:
[0091]在查詢每個索引存儲文件時，直接二分查找塊索引，快速查找開始、結束記錄塊的偏移位置，然後直接讀取中間所有的記錄塊以獲取滿足該索引查詢條件的主鍵集合。
[0092]所述一種分布式順序表片內二級索引系統，該多維區間查詢模塊還包括:
[0093]預處理模塊，用於用戶對該分布式順序表進行多維區間查詢時，將查詢條件發送到每個數據分片後預處理該查詢條件，獲得索引查詢條件；
[0094]讀取主鍵模塊，用於分別從索引存儲文件和內存存儲中查找滿足該索引查詢條件的索引記錄和數據記錄，並分別讀取該索引記錄和該數據記錄的主鍵，得到主鍵集合；
[0095]合併主鍵模塊，用於按照該索引查詢條件間關係和該查詢規模大小次序合併該主鍵集合，按主鍵排序後得到最終主鍵集合；
[0096]結果集生成模塊，用於依據最終主鍵集合查詢該數據分片中數據，並把滿足該索引查詢條件的數據放入結果集中；
[0097]合併結果集模塊，用於合併每個數據分片的結果集得到最終的查詢結果集，並把該最終的查詢結果集返回給該用戶。
【權利要求】
1.一種分布式順序表片內二級索引方法，其特徵在於，包括如下步驟: Si索引布局管理步驟，為分布式順序表的每個數據分片中的每個數據存儲文件創建對應的索引存儲文件，該索引存儲文件存儲列名、列值、主鍵； S2 一致性更新步驟，向該分布式順序表寫入數據時，先將該數據寫入預寫日誌中，再寫入內存存儲中，若該內存存儲中該數據部分丟失，將該預寫入日誌中未成功寫入磁碟上的該數據重新寫入該內存存儲中； S3內存存儲刷寫步驟，若該內存存儲存量達到某閾值，先生成該內存存儲中類型不為「刪除」的數據記錄對應的索引記錄，並刷寫該索引記錄到該磁碟上生成該索引存儲文件，再刷寫該數據記錄到磁碟上生成該數據存儲文件； S4合併和分裂步驟，在數據分片合併時，先將多個索引存儲文件合併成一個新的索引存儲文件，再將對應的多個數據存儲文件合併成一個新的數據存儲文件；以及 在該數據片按照某主鍵分裂成兩個新數據分片時，首先將該數據分片內的每個索引存儲文件按照該主鍵分裂成兩個新索引存儲文件後分別加入到所述兩個新數據分片中，然後再把該數據分片內的每個數據存儲文件按照該主鍵分裂成兩個新數據存儲文件後分別加入到所述的兩個新的數據分片中； S5多維區間查詢步驟，對該分布式順序表進行多維區間查詢時，按照查詢條件對每個數據分片單獨查詢，查詢時對該查詢條件進行預處理得到索引查詢條件，再依次單獨查詢每列索引、合併多列索引查詢結果、讀取滿足該索引查詢條件的該些數據作為最終查詢結果O
2.如權利要求1所述分布式順序表片內二級索引方法，其特徵在於，該索引存儲文件結構包括:多個記錄塊，記錄塊索引，文件信息和結尾，每個記錄塊存儲多條索引記錄，保存每個記錄塊中第一條索引記錄作為記錄塊索引。
3.如權利要求1所述分布式順序表片內二級索引方法，其特徵在於，該索引記錄結構使用鍵值對結構存儲，鍵主要包括列值和列名，值主要包括主鍵，鍵長度、值長度和列名長度都是用於快速讀取索引記錄的某部分。
4.如權利要求1所述一種分布式順序表片內二級索引方法，其特徵在於，該多維區間查詢步驟S5還包括: 查詢每個索引存儲文件時，直接二分查找該塊索引，快速查找開始、結束記錄塊的偏移位置，然後直接讀取中間所有的記錄塊以獲取滿足該索引查詢條件的主鍵集合。
5.如權利要求1所述分布式順序表片內二級索引方法，其特徵在於，該多維區間查詢步驟S5還包括: S51，用戶對該分布式順序表進行多維區間查詢時，將查詢條件發送到每個數據分片後預處理該查詢條件，獲得索引查詢條件； S52,分別從該索弓I存儲文件和該內存存儲中查找滿足該索弓I查詢條件的索引記錄和數據記錄，並分別讀取該索引記錄和該數據記錄的主鍵，得到主鍵集合； S53，按照該索引查詢條件間關係和該查詢規模大小次序合併該主鍵集合，按主鍵排序後得到最終主鍵集合； S54，依據最終主鍵集合查詢該數據分片中數據，並把滿足該索引查詢條件的數據放入結果集中； S55，合併每個數據分片的結果集得到最終的查詢結果集，並把該最終的查詢結果集返回給該用戶。
6.一種分布式順序表片內二級索引系統，其特徵在於，包括: 索引布局管理模塊，用於為所述分布式順序表的每個數據分片中的每個數據存儲文件創建對應的索引存儲文件，該索引存儲文件存儲列名、列值、主鍵； 一致性更新模塊，向該分布式順序表寫入數據時，先將該數據寫入預寫日誌中，再寫入內存存儲中，若該內存存儲中該數據部分丟失，將該預寫入日誌中部分未成功寫入磁碟上的該數據重新寫入該內存存儲中； 內存存儲刷寫模塊，若該內存存儲存量達到某閾值，先生成該內存存儲中類型不為「刪除」的數據記錄對應的索引記錄，並刷寫該索引記錄到該磁碟上生成該索引存儲文件，再刷寫數據記錄到磁碟上生成該數據存儲文件； 合併和分裂模塊，在數據分片合併時，先將多個索引存儲文件合併成一個新的索引存儲文件，再將對應的多個數據存儲文件合併成一個新的數據存儲文件；以及 在該數據分片按照某主鍵分裂成兩個數據片時，首先將該數據分片內的每個索引存儲文件按照該主鍵分裂成兩個索引存儲文件後分別加入到所述兩個新的數據分片中，然後再把該數據分片內的每個數據存儲文件按照所述主鍵分裂成兩個數據存儲文件後分別加入到所述的兩個新的數據分片中； 多維區間查詢模塊，用於該分布式順序表接收多維區間查詢條件，按照該查詢條件對每個數據分片單獨查詢，查詢時對該查詢條件進行預處理得到索引查詢條件，再依次單獨查詢每列索引、合併多列索引查詢結果、讀取滿足該列索引查詢條件的該些數據作為最終查詢結果。
7.如權利要求6所述分布式順序表片內二級索引系統，其特徵在於，該索引存儲文件結構包括:多個記錄塊，記錄塊索引，文件信息和結尾，每個記錄塊存儲多條索引記錄，保存每個記錄塊中第一條索引記錄作為記錄塊索引。
8.如權利要求6所述分布式順序表片內二級索引系統，其特徵在於，該多維區間查詢模塊還包括:在查詢每個索引存儲文件時，直接二分查找塊索引，快速查找開始、結束記錄塊的偏移位置，然後直接讀取中間所有的記錄塊以獲取滿足該索引查詢條件的主鍵集合。
9.如權利要求6所述分布式順序表片內二級索引系統，其特徵在於，該索引記錄結構使用鍵值對結構存儲，鍵主要包括列值和列名，值主要包括主鍵，鍵長度、值長度和列名長度都是用於快速讀取索引記錄的某部分。
10.如權利要求6所述分布式順序表片內二級索引系統，其特徵在於，該多維區間查詢模塊還包括: 預處理模塊，用於用戶對該分布式順序表進行多維區間查詢時，將查詢條件發送到每個數據分片後預處理該查詢條件，獲得索引查詢條件； 讀取主鍵模塊，用於分別從索引存儲文件和內存存儲中查找滿足該索引查詢條件的索引記錄和數據記錄，並分別讀取該索引記錄和該數據記錄的主鍵，得到主鍵集合； 合併主鍵模塊，用於按照該索引查詢條件間關係和該查詢規模大小次序合併該主鍵集合，按主鍵排序後得到最終主鍵集合； 結果集生成模塊，用於依據最終主鍵集合查詢該數據分片中數據，並把滿足該索引查詢條件的數據放入結果集中； 合併結果集模塊，用於合併每個數據分片的結果集得到最終的查詢結果集，並把該查詢結果集返回給該用戶。
【文檔編號】G06F17/30GK104133867SQ201410345063
【公開日】2014年11月5日 申請日期:2014年7月18日 優先權日:2014年7月18日
【發明者】查禮, 萬浩, 程學旗 申請人:中國科學院計算技術研究所