1、物聯網數據存儲及管理物聯網數據存儲及管理分析目錄n物聯網數據存儲現狀分析n海量元數據查詢需求分析n物聯網元數據管理系統設計n面向數據更新的結構設計和分析 n面向預計算的元數據組織結構數據立方體 物聯網數據存儲現狀分析 n大規模存儲系統的應用越來越廣泛，存儲容量也從以前的TB（Terabyte）級上升到PB（Petabyte）級甚至EB（Exabyte）級。n隨著存儲系統規模不斷增大，在大規模文件系統中，文件的數量高達幾十億個，在這種海量數據中查找和管理文件變得異常困難。物聯網數據存儲現狀分析n這與互聯網環境形成了鮮明的對比：n由于搜索引擎技術的發展，在互聯網的環境下查找信息很方便，n而用戶在存

2、儲系統中找到想要的信息比在互聯網上查找信息更加困難 物聯網數據存儲現狀分析n如今存儲系統中的數據量的快速增長使得查找和管理文件異常的困難，n為了能夠合理的管理這些不斷增多的海量數據，n不管是用戶還是管理者都需要能夠高效的獲得文件的屬性。物聯網數據存儲現狀分析n元數據查詢包含索引文件元數據，例如索引節點和一些擴展屬性，能夠幫助回答很多復雜查詢問題。n利用文件屬性，元數據查詢允許點查詢、范圍查詢、top-k查詢和聚集查詢，n這些使得復雜的、特定的查詢變得簡單。物聯網數據存儲現狀分析n能夠幫助管理者回答n“哪些文件在過去的一周里增長很快？”n或者是“哪些應用程序和用戶的文件占用大多數存儲空間？”n元

3、數據查詢也能夠幫助用戶找到10個最近訪問的報告或最大的虛擬機鏡像。n準確地回答這些問題能夠極大的提高用戶和管理者管理大規模存儲系統中的文件。物聯網數據存儲現狀分析n現存的系統一般都采用通用型的數據庫管理系統（Database Management System，DBMS）來索引元數據，n由于DBMS不能很好的適用于多維元數據的查詢，n查詢效率非常低物聯網數據存儲現狀分析n這就限制了在大規模存儲系統中元數據查詢的性能和可擴展性，n所以在大規模存儲系統中要想獲得快速、高效的元數據查詢是很難實現的。物聯網數據存儲現狀分析n從而使得一些復雜查詢非常耗時、效率低下，n不能有效地支持用戶或管理者查找到想要

4、的文件，或得到想要的數據。n例如，“我最近修改過的PPT在哪？”n或者“我的目錄下這個文件有幾個副本？ 物聯網數據存儲現狀分析n為了解決上述問題，必須提供一種高效的多維元數據查詢系統，而且必須滿足以下特點：n第一，必須能夠從存儲系統中快速收集到元數據；n第二，查詢和更新必須快速而且可擴展；n第三，必須能夠快速的返回計算結果，比如用戶提交一個復雜查詢后并不想長時間在線等待計算結果，有時這個過程非常費時物聯網數據存儲現狀分析n例如n“某公司想統計一個星期內用戶產生的數據總量有多少？”n或者“最近一星期內排前五名的熱點文件是哪五個？”，n用戶或管理者希望系統能夠預先計算好這些結果而不用在線等待，當提

5、交查詢后能夠快速返回結果物聯網數據存儲現狀分析n第四，資源需求必須很低，現存的很多元數據查詢工具需要專門的CPU、內存以及硬盤，這就使得它們非常昂貴而且很難集成到存儲系統中；n第五，查詢的接口必須靈活好用，對于現存的文件系統接口和查詢語言，復雜查詢非常困難 物聯網數據存儲現狀分析n在海量的數據中，讓用戶獲得想要的信息至關重要，n對存儲系統中多維元數據查詢的研究將大大提高文件元數據的查詢效率，n實現復雜查詢，縮短響應時間，n這對于用戶或管理者查找和管理文件，以及決策支持都有重要的意義 海量元數據查詢需求分析 n現在的存儲系統都是采用層次化的目錄結構來組織文件的，層次化結構使得文件的訪問效率不高。

6、n訪問某個文件必須通過層次型的目錄樹結構到達文件的保存位置，n如果不知道文件保存位置，就必須遍歷整個目錄或使用操作系統的搜索功能，n而操作系統僅能依靠文件名來檢索和查找數據。海量元數據查詢需求分析 n在最近的十幾年里，新數據類型（多媒體、電子郵件）不斷涌現，n這些數據中包含了大量的元數據信息。n認識到現有文件系統的不足，學術界和工業界都做了大量的工作來研究如何利用豐富的元數據信息來提高文件的管理和搜索效率 海量元數據查詢需求分析n在大規模存儲系統中查找和管理文件顯得更加困難，n元數據查詢可以很好的解決點查詢、范圍查詢、top-k查詢以及聚集查詢，n便于進行一些復雜、特殊的查詢。n能夠快速地實現

7、上述查詢能極大地提高用戶或管理者對大規模存儲系統的管理 海量元數據查詢需求分析n在大規模存儲系統提供高效的元數據查詢是一個很大的挑戰，n而現在有一些商業元數據查詢系統主要致力于小型的存儲系統（最多幾千萬個文件）n并且常常很慢，耗費的資源多 海量元數據查詢需求分析n在大規模存儲系統中想要實現高效的元數據查詢，需滿足以下幾點: n最小的資源需求最小的資源需求p元數據查詢不應該需要額外的硬件，它應該集成到存儲系統中而不降低系統的性能。p現在大多數的元數據查詢系統都需要專門的CPU、內存以及磁盤，p使得它們非常昂貴而且很難部署，這就限制它們的擴展性 海量元數據查詢需求分析n快速的元數據收集快速的元數據

8、收集n必須從幾十億、幾百億個文件中周期性的收集發生改變的元數據，n而不會給整個存儲系統帶來額外負載，使得系統變慢。n現在的爬行算法（crawling method）非常慢而且消耗系統資源 海量元數據查詢需求分析n快速可擴展的索引查詢和更新快速可擴展的索引查詢和更新n查詢必須快速，甚至隨著系統規模的擴大，性能依舊能保持很好，能夠快速周期性的對元數據索引進行更新。n但是，現存的系統一般都采用通用型的關系型數據庫來索引元數據。nDBMS常常使用重量級的鎖和事務，這給系統增加負載 海量元數據查詢需求分析n易用的查詢接口易用的查詢接口n大多數系統輸出簡單的查詢應用程序接口，n但是研究表明專門設計的接口能

9、夠很好表達且容易使用，n這會大大提升查詢體驗。 物聯網元數據管理系統設計 n系統設計要求系統設計要求n第一、高性能，能夠快速的從文件系統中聚集元數據，解決并發操作、熱點數據的管理和訪問等問題；n第二、查找和更新速度必須快且可靠?，F有的系統一般采用通用的DBMS來索引元數據，但是通用的DBMS的設計并不完全適合各種應用場合，比如元數據查找，特別是支持各種復雜的元數據查詢，熱點數據查詢等；而且在大規模存儲系統中會限制其性能和擴展性。物聯網元數據管理系統設計n第三、低的資源消耗。保證元數據查詢不需要占用太多的存儲空間，且不會降低系統的性能。n第四、接口靈活好用。現有的文件系統接口不能很好的支持各種復

10、雜文件查詢。n第五、良好的伸縮性及可用性。隨著存儲系統的規模越來越大，必須保證系統具有良好的伸縮性和可用性 多維元數據組織結構 n傳統的索引方法已不能滿足多維數據的索引和查詢要求，n比如哈希表是數據的精確匹配而不能進行范圍查詢，n而B樹索引一維數據而不能搜索多維空間。n目前存在大量的空間數據索引方法多維元數據組織結構n一般來說，常見的多維空間數據索引有兩種數據組織方式：基于規則的分割方法和基于數據的分割方法。n基于規則分割的索引結構按照特定算法對數據空間進行劃分，包括KD樹、網格等，n這種方法僅適用于數據分布均勻的情況，在數據分布不均勻時會引起索引結構的不平衡。n基于數據的分割方法有R樹，Ce

11、ll樹等，按照數據的分布特性逐層劃分空間 多維元數據組織結構n如果系統基于每個維度單獨建立索引，則需要對每個維度進行查找之后將結果做交集。n如果系統按照多維屬性信息建立了空間索引結構，則可以同時在文件大小、創建時間和修改時間這個三個屬性維度上做約束，大大減少了查詢的數據量和查詢的時間代價。n系統耗費一定的存儲空間維護空間索引結構，在提供各種復雜查詢服務時可以有效的減少查詢時間延遲 相關研究工作: R樹結構n與B樹相似，R樹是一種高度平衡的樹，它的葉子節點的記錄包含數據對象的指針。n如果索引是磁盤駐留的，則每個節點對應一個磁盤頁，以節點為單位讀取和寫入。n該結構設計使得空間搜索只需要訪問一小部分

12、的節點，大大提高檢索效率。n索引結構是完全動態的；插入、刪除和查找操作能同時進行而且不需要定期地對樹的結構進行重新組織 相關研究工作相關研究工作:B樹、樹、B-樹、樹、B+樹、樹、B*樹樹nB樹樹 即二叉搜索樹：1.所有非葉子結點至多擁有兩個兒子（Left和Right）；2.所有結點存儲一個關鍵字；3.非葉子結點的左指針指向小 于其關鍵字的子樹，右指針 指向大于其關鍵字的子樹；如：B樹樹n B樹的搜索，從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那么就命中；否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的

13、關鍵字；n如果B樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那么B樹的搜索性能逼近二分查找；但它比連續內存空間的二分查找的優點是，改變B樹結構（插入與刪除結點）不需要移動大段的內存數據，甚至通常是常數開銷；B樹樹是一種多路搜索樹（并不是二叉的）：1.定義任意非葉子結點最多只有M個兒子；且M2；2.根結點的兒子數為2, M；3.除根結點以外的非葉子結點的兒子數為M/2, M；4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；6.非葉子結點的關鍵字：K1, K2, , KM-1；且Ki Ki+1；7.

14、非葉子結點的指針：P1, P2, , PM；其中P1指向關鍵字小于K1的子樹，PM指向關鍵字大于KM-1的子樹，其它Pi指向關鍵字屬于(Ki-1, Ki)的子樹；8.所有葉子結點位于同一層；如：（M=3）B-樹樹B樹樹B+樹是B-樹的變體，也是一種多路搜索樹：1.其定義基本與B-樹同，除了：2.非葉子結點的子樹指針與關鍵字個數相同；3.非葉子結點的子樹指針Pi，指向關鍵字值屬于Ki, Ki+1)的子樹（B-樹是開區間）；5.為所有葉子結點增加一個鏈指針；6.所有關鍵字都在葉子結點出現；如：（M=3）B+樹樹n是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；nB*樹定義了非葉子結

15、點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）；B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數據復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針；B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那么將一部分數據移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各復制1/3的數據到新結點，最后在父結點增加新結點的指針；所以，B*樹分配新結點的概

16、率比B+樹要低，空間使用率更高；B*樹樹nB樹：二叉樹，每個結點只存儲一個關鍵字，等于則命中，小于走左結點，大于走右結點；nB-樹：多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字范圍的子結點；n所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中；nB+樹：在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；nB*樹：在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率從1/2提高到2/3；相關研究工作相關研究工作:B樹、樹、B-樹、樹、B+樹、樹、B*樹樹相關研究工作: R樹結構

17、nR樹是一個高度平衡樹，它是B樹在k維上的自然擴展，用空間對象的MBR來近似表達空間對象，根據地物的MBR建立R樹，可以直接對空間中占據一定范圍的空間對象進行索引。R樹的每一個結點都對應著磁盤頁D和區域I，如果結點不是葉結點，則該結點的所有子結點的區域都在區域I的范圍之內，而且存儲在磁盤頁D中。如果結點是葉結點，那么磁盤頁D中存儲的將是區域I范圍內的一系列子區域，子區域緊緊圍繞空間對象，一般為空間對象的外接矩形。 n一個空間數據庫由代表對象的的集合組成。n每個對象元組都有一個唯一的標識符，可通過這些標識符來檢索對象元組。nR樹的葉節點按以下形式記錄索引記錄的入口 比較典型的有R+樹、R樹、壓縮

18、R樹等。 相關研究工作: R樹結構n特點； 1根節點若非葉子節點，則至少有兩個子節點； 2每個非根葉節點和非葉節點包含的實體個數均介于m和M之間； 3所有葉子節點在同一層次； R樹兄弟結點對應的空間區域可以重疊，可以較容易地進行插入和刪除操作。但正因為區域之間有重疊，空間索引可能要對多條路徑進行搜索后才能得到最后的結果。 R樹的空間分布圖 Bloom filternBloom Filter是一種空間效率很高的隨機數據結構，它利用位數組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。Bloom Filter的這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集

19、合的元素誤認為屬于這個集合（false positive）。因此，Bloom Filter不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下，Bloom Filter通過極少的錯誤換取了存儲空間的極大節省。n由一個很長的二進制向量數組和一系列隨機映射函數組成，n它只需要哈希表 1/8 到 1/4 的大小就能解決同樣規模的集合的查詢問題 Bloom filterBloom filter nBloom filter的本質是哈希計算，不同之處在于Bloom filter對同一數據使用多個哈希函數進行多次哈希，將結果保存在同一個向量數組中，n所以Bloom filter在達到相同的功能的情

20、況下比原始的哈希結構更節約存儲空間。nBloom filter算法的一個缺點在于查詢一個元素是否在集合S上可能存在失誤定位(False Positive) n集合表示和元素查詢集合表示和元素查詢n下面我們具體來看Bloom Filter是如何用位數組表示集合的。初始狀態時，Bloom Filter是一個包含m位的位數組，每一位都置為0。Bloom filtern為了表達S=x1, x2,xn這樣一個n個元素的集合，Bloom Filter使用k個相互獨立的哈希函數（Hash Function），它們分別將集合中的每個元素映射到1,m的范圍中。對任意一個元素x，第i個哈希函數映射的位置hi(x)

21、就會被置為1（1ik）。注意，如果一個位置多次被置為1，那么只有第一次會起作用，后面幾次將沒有任何效果。在下圖中，k=3，且有兩個哈希函數選中同一個位置（從左邊數第五位）。 Bloom filtern在判斷y是否屬于這個集合時，我們對y應用k次哈希函數，如果所有hi(y)的位置都是1（1ik），那么我們就認為y是集合中的元素，否則就認為y不是集合中的元素。下圖中y1就不是集合中的元素。y2或者屬于這個集合，或者剛好是一個false positive。 算法算法Bloom filter Bloom filterRBF索引結構 n從B樹演變而來的R樹結構，能有效地支持多維范圍查詢。n但是，R樹不能

22、有效地支持點查詢。因為成員查詢只能在葉子節點上進行，相應的操作將導致查詢效率很低。n然而，Bloom filter是一種空間利用率高且能有效地支持點查詢的結構。RBF索引結構n一種叫做RBF的新的空間存儲結構來存儲多維元數據，n基本思路是是擴展經典的R樹結構，n將Bloom filter插入到每個R樹結點上來支持點查詢，n維持多維范圍信息并實現空間效率 RBF索引結構面向數據更新的結構設計和分析 nR樹更新 n基于R樹的索引在商業上得到廣泛應用和發展，n但是它在頻繁更新操作時性能低下。nR樹及其變體在空間索引結構中占據主導地位，R樹更新 n傳統的空間索引的研究主要考慮靜態數據，n只關注高效的查

23、詢處理，R樹的更新性能很差，n不能直接用于頻繁更新的應用環境R樹更新n存儲系統下元數據的更新是很頻繁的，n直接對索引的修改會產生大量的磁盤操作并可能引起索引結構的不平衡。n已經存在的各種基于R樹索引的更新機制主要采取的是自頂向下模式 減少更新操作的方法 n位置預測位置預測n一種減少對象更新操作次數的策略是采用線性函數來表示移動對象的位置，n保存對象的運動特性，包括當前位置和速度參數等，n通過這些數據可以預測將來一段時間后的位置 減少更新操作的方法n容忍更新容忍更新n減少更新次數的另一種策略是容忍更新。并不是每次更新都需要一個至上而下的刪除操作和插入操作。n當一個對象的新位置沒有移出原來的MBR

24、，換句話說就是該對象還在同一個葉子節點內時，n只要修改對應葉子節點的數據信息即可，不需要刪除后插入，也不可能引起分裂和合并操作 延遲更新 n更新操作包括刪除和插入兩個步驟，延遲更新也包括延遲刪除和延遲插入兩個方面。n延遲刪除的策略是將更新信息立即插入，而舊的對象信息不會立即刪除，n而是使用某種策略將未刪除的索引信息緩存起來以便區分新舊數據，直到緩沖區滿或者其它情況下才進行刪除操作 批量操作nR樹的批量插入策略是當前研究的熱點之一。n其中STLT (Small-Tree-Large-Tree) 技術，n首先利用輸入數據集建立一棵小R（Small tree）樹，n然后將小R樹插入到原有的大R樹（L

25、arge tree）中 批量操作nGBI（Generalized Bulk Insertion）技術利用聚類算法將輸入數據集分割為多個空間上接近的數據組，n為每個數據組建立R樹結構，n最后將這些R樹結構批量插入到目標R樹中 多版本文件更新系統 nVersioning文件系統保存被修改的文件之前的版本，來實現用戶誤操作以及系統錯誤后的數據恢復。nVersioning文件系統存在的主要問題是不能有效地保存大量的version，version數據消耗大量的存儲空間，n對version的刪除的策略，恢復系統時version的選擇問題等 多版本文件更新系統nCedar采用簡單的version策略來幫助客

26、戶在誤操作后恢復數據。n最近的Elephant文件系統提供了一系列的version選項，n用來保存對用戶最為重要的文件的version。多版本文件更新系統nCVFS提出兩種有效節省空間的version元數據結構，n對于inodes和indirect blocks采用Journal-based元數據，n而對于目錄采用Multiversion B樹，有效地節省了version占用的空間。多版本文件更新系統nCausality-based versioning結合causal relationship和versioning技術，n通過causal connection使得version更具意義，n提

27、出新的在何時創建version的算法；n通過causal relationship定位version，能夠更有效的在錯誤后恢復到正確的version 面向預計算的元數據組織結構數據立方體 n數據立方體（Data Cube）是分析數據倉庫數據的基本單位，是聯機分析處理（On-Line Analytical Processing, OLAP）中的主要對象，n是一項可對數據倉庫中的數據進行快速訪問的技術。n數據立方體是一個數據集合，通常由數據倉庫的子集構造，并組織和匯總成一個由一組維度和度量值定義的多維結構。n數據立方體提供一種便于使用的查詢數據機制，響應時間短 數據立方體n數據立方體是多維數據庫的基本結構，n并作為在多維數據庫上定義的所有操作符的輸入輸出基本單位。n將它定義為一個四元組，這四個組件分別表示數據立方體的特征 數據立方體n在典型的OLAP應用中，存在一個中心關系或數據集合，稱作事實表。n事實表代表感興趣的事件或對象。n事實表通常有幾個表示維的屬性和一個或多個度量屬性，n這些度量屬性一般是用戶想要查詢到的一些值 維數據立方體表示 數據立方體的計算 n數據立方體的計算是數據倉庫實現的一項基本任務，數據立方體計算也稱為數據立方體的物化（Materialization）n簡單的說，它是將常用的查詢按照各自的屬性分組（Group by）提前計算出結果并保存起來