[發明專利]一種面向云存儲的分層索引方法與檢索方法

在審

• 申請號: 201610975816.5
• 申請日: 2016-11-07
• 公開（公告）號: CN106599040A
• 公開（公告）日: 2017-04-26
• 發明（設計）人: 郭皓明;王之欣;魏閆艷;龐廓;田霂;焉麗
• 申請（專利權）人: 中國科學院軟件研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙)11200
• 代理人: 邱曉鋒

技術領域

本發明屬于分布式云存儲系統索引技術研究與應用領域，具體涉及一種面向云存儲的分層索引方法與檢索方法。

背景技術

近年來，隨著云計算、物聯網、互聯網等信息技術的快速發展，信息系統的形態發生較大變化，云化服務與全生態圈構建逐漸成為信息系統的發展趨勢。這一趨勢導致云端數據量呈爆發性增長，達到TB、PB級的規模，其增長速度已經遠遠超過傳統摩爾定律。以中科院海云平臺為例，其是一個典型的基于云計算的協同服務平臺，通過海端實現數據的采集與前處理，通過云端實現數據的統一存儲、查詢、分析與知識提取。同時，云端通過自動負載均衡實現平臺自適應。在以智慧城市為典型應用場景中，這一平臺云端日數據增量規模達到10G以上。同時，這一平臺不但要滿足數據簡單檢索的要求，還要支撐各種挖掘、分析與知識提取活動中多值查詢與布爾查詢等復雜操作。隨著數據規模的快速增長，如何在海量數據的基礎上，面向云計算的動態環境，提供高性能復雜查詢支撐成為一個重要難題。

查詢是一種復雜的數據操作，當數據集達到一定規模后，數據查詢的效率就成為信息系統性能的主要瓶頸。索引是實現提高數據檢索與查詢效率的重要手段。索引技術的組織方法有兩個重要方向即正向索引與倒排索引。在傳統的關系數據庫中，倒排索引應用較為廣泛。同時，根據索引的數據結構，又形成有序索引與散列索引基本類型。B+-Tree索引是典型的有序索引，其采以平衡樹為基礎，組織一維數據結構實現數據的檢索，由于其結構高效等優點，其在傳統的關系數據庫中廣泛應用。然而，在上述海云平臺的應用環境中，數據集規模較大，這就導致B+-Tree的結構膨脹較為嚴重，同時，對于多值與布爾查詢仍需要復雜的交叉過濾處理，因此整體查詢效率受數據集規模影響較大。

2000年以來，數據規模膨脹導致的復雜查詢困難問題引起了相關研究人員的注意。2004年Google等一批研究機構以云計算為基礎，先后推出鍵值(key-value)數據庫為代表的大數據存儲、查詢解決方案?；趉ey-value的的云數據存儲查詢技術具有高可擴展性、高可用性和容錯性等特點，能夠實現對海量數據的高效存儲與查詢的目的。key-value數據庫，以散列索引為基礎，通過rowkey與數據對象取值的哈希建立映射關系，針對rowkey索引無法排序的問題，研究人員又將其與B+Tree索引等技術相結合。key-value數據庫在rowkey上的查詢速度較快，但在非rowkey只能采用全表掃描的方式實現，雖然通過MapReduce等并行架構可以一定程度上提高查詢速度，整體而言，針對多值查詢與布爾查詢的效率仍然較低，當數據集規模較大時，查詢速度不能滿足應用需求。

另一方面，分布式是當前大規模數據集存儲管理采用的主流架構。以前述海云平臺為例，其云端采用典型的并行數據存儲管理架構，通過上層master節點實現資源調度與數據分發。通過底層worker節點實現數據本地存儲，為了減少本地數據集IO負載，其內部采用分頁(默認512k)的方式讀寫數據。同時，在云計算環境中，為了滿足負載均衡的要求，數據會根據一定的調度策略在節點之間進行遷移。這就要求索引在支撐高性能復雜查詢的同時，具有較好的遷移適應性。云計算環境中的上述問題導致索引創建、維護與查詢操作的困難。

發明內容

圍繞上述問題，本發明就云環境中海量數據索引技術開展研究工作。形成兩層索引框架。其頂層為全局索引，該索引以數據的不同屬性形成維度，為每個維度以散列倒排的方式建立取值與分頁之間的映射關系。在底層的局部索引中建立與上層維度取值對應的索引，實現與本地存儲分頁中數據的映射。這一索引結構高效，平衡性與擴展性較好，該索引具有查詢執行效率受數據集規模影響較小的特點，且支持多維與布爾查詢。同時，在云環境節點發生變換時，僅在全局索引進行節點遷移的維護工作，索引維護較為簡單，能夠滿足云存儲環境的要求。