海量數據存儲與處理

⑴ 海量空間數據存儲

(一)空間數據存儲技術

隨著地理信息系統的發展，空間資料庫技術也得到了很大的發展，並出現了很多新的空間資料庫技術(黃釗等，2003)，其中應用最廣的就是用關系資料庫管理系統(RDBMS)來管理空間數據。

用關系資料庫管理系統來管理空間數據，主要解決存儲在關系資料庫中的空間數據與應用程序之間的數據介面問題，即空間資料庫引擎(SpatialDatabase Engine)(熊麗華等，2004)。更確切地說，空間資料庫技術是解決空間數據對象中幾何屬性在關系資料庫中的存取問題，其主要任務是:

(1)用關系資料庫存儲管理空間數據;

(2)從資料庫中讀取空間數據，並轉換為GIS應用程序能夠接收和使用的格式;

(3)將GIS應用程序中的空間數據導入資料庫，交給關系資料庫管理。

空間資料庫中數據存儲主要有三種模式:拓撲關系數據存儲模式、Oracle Spatial模式和ArcSDE模式。拓撲關系數據存儲模式將空間數據存在文件中，而將屬性數據存在資料庫系統中，二者以一個關鍵字相連。這樣分離存儲的方式由於存在數據的管理和維護困難、數據訪問速度慢、多用戶數據並發共享沖突等問題而不適用於大型空間資料庫的建設。而OracleSpatial實際上只是在原來的資料庫模型上進行了空間數據模型的擴展，實現的是「點、線、面」等簡單要素的存儲和檢索，所以它並不能存儲數據之間復雜的拓撲關系，也不能建立一個空間幾何網路。ArcSDE解決了這些問題，並利用空間索引機制來提高查詢速度，利用長事務和版本機制來實現多用戶同時操縱同一類型數據，利用特殊的表結構來實現空間數據和屬性數據的無縫集成等(熊麗華等，2004)。

ArcSDE是ESRI公司開發的一個中間件產品，所謂中間件是一個軟體，它允許應用元素通過網路連接進行互操作，屏蔽其下的通訊協議、系統結構、操作系統、資料庫和其他應用服務。中間件位於客戶機/伺服器的操作系統之上，管理計算資源和網路通訊，並營造出一個相對穩定的高層應用環境，使開發人員可以集中精力於系統的上層開發，而不用過多考慮系統分布式環境下的移植性和通訊能力。因此，中間件能無縫地連入應用開發環境中，應用程序可以很容易地定位和共享中間件提供的應用邏輯和數據，易於系統集成。在分布式的網路環境下，客戶端的應用程序如果要訪問網路上某個伺服器的信息，而伺服器可能運行在不同於客戶端的操作系統和資料庫系統中。此時，客戶機的應用程序中負責尋找數據的部分只需要訪問一個數據訪問中間件，由該中間件完成網路中數據或服務的查找，然後將查找的信息返回給客戶端(萬定生等，2003)。因此，本系統實現空間資料庫存儲的基本思想就是利用ArcSDE實現各類空間數據的存儲。

目前，空間數據存儲技術已比較成熟，出現了許多類似ArcSDE功能的中間件產品，這些軟體基本上都能實現空間數據的資料庫存儲與管理，但對於海量空間數據的存儲，各種軟體性能差別較大。隨著數據量的增長，計算機在分析處理上會產生很多問題，比如數據不可能一次完全被讀入計算機的內存中進行處理。單純依賴於硬體技術，並不能滿足持續增長的數據的處理要求。因此需要在軟體上找到處理海量數據的策略，並最終通過軟硬體的結合完成對海量數據的處理。在海量數據存儲問題上，許多專家從不同側面進行過研究，Lindstrom在地形簡化中使用了外存模型(Out-of-core)技術;鍾正採用了基於數據分塊、動態調用的策略;汪國平等人在研究使用高速網路進行三維海量地形數據的實時交互瀏覽中，採用了分塊、多解析度模板建立模型等方法。這些技術、方法已經在各自系統上進行了研究和實現。本系統採用的ArcSDE軟體基本上也是採用分塊模型的方法，具體存儲和操作不需要用戶過多了解，已經由ArcSDE軟體實現。因此，對海量數據的存儲管理，更需要從數據的組織方式等方面進行設計。塔里木河流域生態環境動態監測系統採集了大量的遙感影像、正射影像等柵格結構的數據，這些數據具有很大的數據量，為適應流域空間基礎設施的管理需要，採取一種新的方式來管理、分發這些海量數據以適應各部門的快速瀏覽和管理需要。

(二)影像金字塔結構

影像資料庫的組織是影像資料庫效率的關鍵，為了獲得高效率的存取速度，在數據的組織上使用了金字塔數據結構和網格分塊數據結構。該技術主導思想如下:

(1)將資料庫中使用到的紋理處理成為大小一致的紋理塊;

(2)為每塊紋理生成5個細節等級的紋理，分別為0、1、2、3、4，其中1級紋理通過0級紋理1/4壓縮得到，2級紋理通過1級紋理1/4壓縮得到，…，以此類推;

(3)在顯示每個塊數據之前，根據顯示比例的大小，並以此決定該使用那一級的紋理;

(4)在內存中建立紋理緩沖池，使用LRU演算法進行紋理塊的調度，確保使用頻率高的紋理調度次數盡可能少。

(三)影像數據壓縮

影像數據壓縮有無損壓縮和有損壓縮兩個方法，具體採取哪種壓縮方法需根據具體情況確定。對於像元值很重要的數據，如分類數據、分析數據等採用無損壓縮(即LZ77演算法)，否則採用有損壓縮(即JPEG演算法)。通過對影像數據的壓縮，一方面可以節約存儲空間，另一方面可以加快影像的讀取和顯示速度。影像數據的壓縮一般與構建金字塔同時進行，在構建影像金字塔過程中自動完成數據的壓縮。

⑵ 　海量數據存儲與管理

正如上述，在國土資源遙感綜合調查信息中，既包含有多源、多時相、多尺度、多解析度、多類型的遙感圖像數據和基礎地理數據，也包括在項目開展過程中衍生的許多觀測和分析資料，數據量十分龐大。因此，根據數據共享的要求，在數據生產、管理、應用服務以及更新和維護過程中，如何組織和管理好這些海量數據，如何快速、全面有效地訪問和獲得所需數據，成為面臨的突出問題。在這里，採用何種方式利用現有的大型商業化關系資料庫系統高效地存儲與管理這些數據，成為能否發揮系統最大性能的關鍵所在。

傳統的GIS系統對空間數據（與空間位置、空間關系有關的數據）的存儲與管理大多採用這些商業軟體特定的文件方式，如：ArcInfo的Coverage、MapInfo的Tab、MAPGIS的WL等。如果數據量越多，這些文件就會越大，數據的處理就會越復雜，其存儲、檢索、管理也就越困難，而且其最大的缺點還在於不能進行多用戶並發操作。由此可見，用以往傳統的存儲機制去管理像遙感綜合調查這樣的海量數據，顯然難以滿足要求。而近年來發展起來的空間資料庫引擎技術則是解決海量數據存儲管理的途徑之一。

本系統建設過程中，採用了空間資料庫引擎ArcSDE＋大型關系資料庫Oracle組合技術，較理想地實現了遙感綜合調查海量數據的存儲、檢索、查詢、處理。眾所周知，Oracle提供了大型資料庫環境，能夠很好地處理海量數據，而ArcSDE可將具有地理特徵的空間數據和非空間數據統一載入到Oracle中去，因此，通過ArcSDE空間資料庫引擎，可將Oracle海量數據管理功能載入到GIS系統中，並可利用Oracle的強大管理機制進行高效率的事務處理、記錄鎖定、並發控制等服務操作。

⑶ 大數據的存儲

⼤數據的存儲⽅式是結構化、半結構化和⾮結構化海量數據的存儲和管理，輕型資料庫⽆法滿⾜對其存儲以及復雜的數據挖掘和分析操作，通常使⽤分布式⽂件系統、No sql 資料庫、雲資料庫等。

結構化、半結構化和⾮結構化海量數據的存儲和管理，輕型資料庫⽆法滿⾜對其存儲以及復雜的數據挖掘和分析操作，通常使⽤分布式⽂件系統、No SQL 資料庫、雲資料庫等。

1 分布式系統：分布式系統包含多個⾃主的處理單元，通過計算機⽹絡互連來協作完成分配的任務，其分⽽治之的策略能夠更好的處理⼤規模數據分析問題。

主要包含以下兩類：

1）分布式⽂件系統：存儲管理需要多種技術的協同⼯作，其中⽂件系統為其提供最底層存儲能⼒的⽀持。分布式⽂件系統 HDFS 是⼀個⾼度容錯性系統，被設計成適⽤於批量處理，能夠提供⾼吞吐量的的數據訪問。

2）分布式鍵值系統：分布式鍵值系統⽤於存儲關系簡單的半結構化數據。典型的分布式鍵值系統有 Amazon Dynamo，以及獲得⼴泛應⽤和關注的對象存儲技術(Object Storage)也可以視為鍵值系統，其存儲和管理的是對象⽽不是數據塊。

2 Nosql 資料庫：關系資料庫已經⽆法滿⾜ Web2.0 的需求。主要表現為：⽆法滿⾜海量數據的管理需求、⽆法滿⾜數據⾼並發的需求、⾼可擴展性和⾼可⽤性的功能太低。No SQL 資料庫的優勢：可以⽀持超⼤規模數據存儲，靈活的數據模型可以很好地⽀持 Web2.0 應⽤，具有強⼤的橫向擴展能⼒等，典型的 No SQL 資料庫包含以下⼏種：

3 雲資料庫：雲資料庫是基於雲計算技術發展的⼀種共享基礎架構的⽅法，是部署和虛擬化在雲計算環境中的資料庫。

⑷ 介紹一下海量數據的處理方法

介紹一下海量數據的處理方法
適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集
基本原理及要點：
對於原理來說很簡單，位數組+k個獨立hash函數。將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這個過程並不保證查找的結果是100%正確的。同時也不支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。
還有一個比較重要的問題，如 何根據輸入元素個數n，確定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大於E的情況 下，m至少要等於n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為0，則m應 該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。
舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。
注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(准確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。
擴展：
Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF採用counter中的最小值來近似表示元素的出現頻率。
問題實例：給你A,B兩個文件，各存放50億條URL，每條URL佔用64位元組，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢?
根據這個問題我們來計算下內存的佔用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個bit。 現在可用的是340億，相差並不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。
2.Hashing
適用范圍：快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存
基本原理及要點：
hash函數選擇，針對字元串，整數，排列，具體相應的hash方法。
碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。
擴展：
d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數，h1和h2。在存儲一個新的key時，同時用兩個哈希函數進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個位置已經存儲的（有碰撞的）key比較多，然後將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。
問題實例：1).海量日誌數據，提取出某日訪問網路次數最多的那個IP。

IP的數目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內存，然後進行統計。

3.bit-map

適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下

基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話號碼

擴展：bloom filter可以看做是對bit-map的擴展

問題實例：

1)已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

8位最多99 999 999，大概需要99m個bit，大概10幾m位元組的內存即可。

2)2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。

將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map。

4.堆

適用范圍：海量數據前n大，並且n比較小，堆可以放入內存

基本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小於最大元素，則應該替換那個最大元 素。這樣最後得到的n個元素就是最小的n個。適合大數據量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。

擴展：雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。

問題實例：
1)100w個數中找最大的前100個數。

用一個100個元素大小的最小堆即可。

5.雙層桶劃分

適用范圍：第k大，中位數，不重復或重復的數字

基本原理及要點：因為元素范圍很大，不能利用直接定址表，所以通過多次劃分，逐步確定范圍，然後最後在一個可以接受的范圍內進行。可以通過多次縮小，雙層只是一個例子。

擴展：

問題實例：
1).2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。

有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然後將數據分離到不同的區域，然後不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁碟空間，就可以很方便的解決。

2).5億個int找它們的中位數。

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然後讀取數據統計落到各個區域里的數的個數，之後我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然後第二次掃描我們只統計落在這個區域中的那些數就可以了。

實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然後確定區域的第幾 大數，在將該區域分成2^20個子區域，然後確定是子區域的第幾大數，然後子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。

6.資料庫索引

適用范圍：大數據量的增刪改查

基本原理及要點：利用數據的設計實現方法，對海量數據的增刪改查進行處理。
擴展：
問題實例：

7.倒排索引(Inverted index)

適用范圍：搜索引擎，關鍵字查詢

基本原理及要點：為何叫倒排索引?一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。

以英文為例，下面是要被索引的文本：
T0 = 「it is what it is」
T1 = 「what is it」
T2 = 「it is a banana」
我們就能得到下面的反向文件索引：
「a」: {2}
「banana」: {2}
「is」: {0, 1, 2}
「it」: {0, 1, 2}
「what」: {0, 1}
檢索的條件」what」, 「is」 和 「it」 將對應集合的交集。

正 向索引開發出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很 容易看到這個反向的關系。

擴展：

問題實例：文檔檢索系統，查詢那些文件包含了某單詞，比如常見的學術論文的關鍵字搜索。

8.外排序

適用范圍：大數據的排序，去重

基本原理及要點：外排序的歸並方法，置換選擇 敗者樹原理，最優歸並樹

擴展：

問題實例：
1).有一個1G大小的一個文件，裡面每一行是一個詞，詞的大小不超過16個位元組，內存限制大小是1M。返回頻數最高的100個詞。

這個數據具有很明顯的特點，詞的大小為16個位元組，但是內存只有1m做hash有些不夠，所以可以用來排序。內存可以當輸入緩沖區使用。

9.trie樹

適用范圍：數據量大，重復多，但是數據種類小可以放入內存

基本原理及要點：實現方式，節點孩子的表示方式

擴展：壓縮實現。

問題實例：
1).有10個文件，每個文件1G， 每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序 。

2).1000萬字元串，其中有些是相同的(重復),需要把重復的全部去掉，保留沒有重復的字元串。請問怎麼設計和實現?

3).尋找熱門查詢：查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復後，不超過3百萬個，每個不超過255位元組。

10.分布式處理 maprece

適用范圍：數據量大，但是數據種類小可以放入內存

基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。

擴展：

問題實例：

1).The canonical example application of MapRece is a process to count the appearances of

each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);

void rece(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a 「1″ value by

the Map function, using the word as the result key. The framework puts together all the pairs

with the same key and feeds them to the same call to Rece, thus this function just needs to

sum all of its input values to find the total appearances of that word.

2).海量數據分布在100台電腦中，想個辦法高效統計出這批數據的TOP10。

3).一共有N個機器，每個機器上有N個數。每個機器最多存O(N)個數並對它們操作。如何找到N^2個數的中數(median)?

經典問題分析

上千萬or億數據（有重復），統計其中出現次數最多的前N個數據,分兩種情況：可一次讀入內存，不可一次讀入。

可用思路：trie樹+堆，資料庫索引，劃分子集分別統計，hash，分布式計算，近似統計，外排序

所 謂的是否能一次讀入內存，實際上應該指去除重復後的數據量。如果去重後數據可以放入內存，我們可以為數據建立字典，比如通過 map，hashmap，trie，然後直接進行統計即可。當然在更新每條數據的出現次數的時候，我們可以利用一個堆來維護出現次數最多的前N個數據，當 然這樣導致維護次數增加，不如完全統計後在求前N大效率高。

如果數據無法放入內存。一方面我們可以考慮上面的字典方法能否被改進以適應這種情形，可以做的改變就是將字典存放到硬碟上，而不是內存，這可以參考資料庫的存儲方法。
當然還有更好的方法，就是可以採用分布式計算，基本上就是map-rece過程，首先可以根據數據值或者把數據hash(md5)後的值，將數據按照范圍劃分到不同的機子，最好可以讓數據劃分後可以一次讀入內存，這樣不同的機子負責處理各種的數值范圍，實際上就是map。得到結果後，各個機子只需拿出各 自的出現次數最多的前N個數據，然後匯總，選出所有的數據中出現次數最多的前N個數據，這實際上就是rece過程。
實際上可能想直接將數據均分到不同的機子上進行處理，這樣是無法得到正確的解的。因為一個數據可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上，同時還可 能存在具有相同數目的數據。比如我們要找出現次數最多的前100個，我們將1000萬的數據分布到10台機器上，找到每台出現次數最多的前 100個，歸並之後這樣不能保證找到真正的第100個，因為比如出現次數最多的第100個可能有1萬個，但是它被分到了10台機子，這樣在每台上只有1千個，假設這些機子排名在1000個之前的那些都是單獨分布在一台機子上的，比如有1001個，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每台機子選出出現次數最多的1000個再歸並，仍然會出錯，因為可能存在大量個數為1001個的發生聚集。因此不能將數據隨便均分到不同機子上，而是要根據hash 後的值將它們映射到不同的機子上處理，讓不同的機器處理一個數值范圍。
而外排序的方法會消耗大量的IO，效率不會很高。而上面的分布式方法，也可以用於單機版本，也就是將總的數據根據值的范圍，劃分成多個不同的子文件，然後逐個處理。處理完畢之後再對這些單詞的及其出現頻率進行一個歸並。實際上就可以利用一個外排序的歸並過程。
另外還可以考慮近似計算，也就是我們可以通過結合自然語言屬性，只將那些真正實際中出現最多的那些詞作為一個字典，使得這個規模可以放入內存。

⑸ 海量數據分析處理方法

海量數據分析處理方法
一、Bloom filter
適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集
基本原理及要點：
對於原理來說很簡單，位數組+k個獨立hash函數。將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這個過程並不保證查找的結果是100%正確的。同時也不支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。
還有一個比較重要的問題，如何根據輸入元素個數n，確定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大於E的情況下，m至少要等於n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為0，則m應該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。
舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。
注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(准確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。
擴展：
Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF採用counter中的最小值來近似表示元素的出現頻率。
問題實例：給你A,B兩個文件，各存放50億條URL，每條URL佔用64位元組，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？
根據這個問題我們來計算下內存的佔用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個bit。現在可用的是340億，相差並不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。
二、Hashing
適用范圍：快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存
基本原理及要點：
hash函數選擇，針對字元串，整數，排列，具體相應的hash方法。
碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。
擴展：
d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數，h1和h2。在存儲一個新的key時，同時用兩個哈希函數進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個位置已經存儲的（有碰撞的）key比較多，然後將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。
問題實例：
1).海量日誌數據，提取出某日訪問網路次數最多的那個IP。
IP的數目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內存，然後進行統計。
三、bit-map
適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下
基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話號碼
擴展：bloom filter可以看做是對bit-map的擴展
問題實例：
1)已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。
8位最多99 999 999，大概需要99m個bit，大概10幾m位元組的內存即可。
2)2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map。
四、堆
適用范圍：海量數據前n大，並且n比較小，堆可以放入內存
基本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小於最大元素，則應該替換那個最大元素。這樣最後得到的n個元素就是最小的n個。適合大數據量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。
擴展：雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。
問題實例：
1)100w個數中找最大的前100個數。
用一個100個元素大小的最小堆即可。
五、雙層桶劃分-—其實本質上就是【分而治之】的思想，重在分的技巧上！
適用范圍：第k大，中位數，不重復或重復的數字
基本原理及要點：因為元素范圍很大，不能利用直接定址表，所以通過多次劃分，逐步確定范圍，然後最後在一個可以接受的范圍內進行。可以通過多次縮小，雙層只是一個例子。
擴展：
問題實例：
1).2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然後將數據分離到不同的區域，然後不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁碟空間，就可以很方便的解決。
2).5億個int找它們的中位數。
這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然後讀取數據統計落到各個區域里的數的個數，之後我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然後第二次掃描我們只統計落在這個區域中的那些數就可以了。
實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然後確定區域的第幾大數，在將該區域分成2^20個子區域，然後確定是子區域的第幾大數，然後子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。
六、資料庫索引
適用范圍：大數據量的增刪改查
基本原理及要點：利用數據的設計實現方法，對海量數據的增刪改查進行處理。
七、倒排索引(Inverted index)
適用范圍：搜索引擎，關鍵字查詢
基本原理及要點：為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。
以英文為例，下面是要被索引的文本： T0 = 「it is what it is」 T1 = 「what is it」 T2 = 「it is a banana」
我們就能得到下面的反向文件索引：
「a」: {2} 「banana」: {2} 「is」: {0, 1, 2} 「it」: {0, 1, 2} 「what」: {0, 1}
檢索的條件」what」,」is」和」it」將對應集合的交集。
正向索引開發出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關系。
擴展：
問題實例：文檔檢索系統，查詢那些文件包含了某單詞，比如常見的學術論文的關鍵字搜索。
八、外排序
適用范圍：大數據的排序，去重
基本原理及要點：外排序的歸並方法，置換選擇敗者樹原理，最優歸並樹
擴展：
問題實例：
1).有一個1G大小的一個文件，裡面每一行是一個詞，詞的大小不超過16個位元組，內存限制大小是1M。返回頻數最高的100個詞。
這個數據具有很明顯的特點，詞的大小為16個位元組，但是內存只有1m做hash有些不夠，所以可以用來排序。內存可以當輸入緩沖區使用。
九、trie樹
適用范圍：數據量大，重復多，但是數據種類小可以放入內存
基本原理及要點：實現方式，節點孩子的表示方式
擴展：壓縮實現。
問題實例：
1).有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序。
2).1000萬字元串，其中有些是相同的(重復),需要把重復的全部去掉，保留沒有重復的字元串。請問怎麼設計和實現？
3).尋找熱門查詢：查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復後，不超過3百萬個，每個不超過255位元組。
十、分布式處理 maprece
適用范圍：數據量大，但是數據種類小可以放入內存
基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。
擴展：
問題實例：
1).The canonical example application of MapRece is a process to count the appearances ofeach different word in a set of documents:
2).海量數據分布在100台電腦中，想個辦法高效統計出這批數據的TOP10。
3).一共有N個機器，每個機器上有N個數。每個機器最多存O(N)個數並對它們操作。如何找到N^2個數的中數(median)？

⑹ 海量數據存儲

存儲技術經歷了單個磁碟、磁帶、RAID到網路存儲系統的發展歷程。網路存儲技術就是將網路技術和I/O技術集成起來，利用網路的定址能力、即插即用的連接性、靈活性，存儲的高性能和高效率，提供基於網路的數據存儲和共享服務。在超大數據量的存儲管理、擴展性方面具有明顯的優勢。

典型的網路存儲技術有網路附加存儲NAS（Network Attached Storage）和存儲區域網SAN（Storage Area Networks）兩種。

1）NAS技術是網路技術在存儲領域的延伸和發展。它直接將存儲設備掛在網上，有良好的共享性、開放性。缺點是與LAN共同用物理網路，易形成擁塞，而影響性能。特別是在數據備份時，性能較低，影響在企業存儲應用中的地位。

2）SAN技術是以數據存儲為中心，使用光纖通道連接高速網路存儲的體系結構。即將數據存儲作為網路上的一個區域獨立出來。在高度的設備和數據共享基礎上，減輕網路和伺服器的負擔。因光纖通道的存儲網和LAN分開，使性能得到很大的提高，而且還提供了很高的可靠性和強大的連續業務處理能力。在SAN中系統的擴展、數據遷移、數據本地備份、遠程數據容災數據備份和數據管理等都比較方便，整個SAN成為一個統一管理的存儲池（Storage Pool）。SAN存儲設備之間通過專用通道進行通信，不佔用伺服器的資源。因此非常適合超大量數據的存儲，成為網路存儲的主流。

3）存儲虛擬化技術是將系統中各種異構的存儲設備映射為一個單一的存儲資源，對用戶完全透明，達到互操作性的目的和利用已有的硬體資源，把SAN內部的各種異構的存儲資源統一成一個單一視圖的存儲池，可根據用戶的需要方便地切割、分配。從而保持已有的投資，減少總體成本，提高存儲效率。

存儲虛擬化包括3個層次結構：基於伺服器的虛擬化存儲、基於存儲設備的虛擬化存儲和基於網路的虛擬化存儲。

1）基於伺服器的虛擬化存儲由邏輯管理軟體在主機/伺服器上完成。經過虛擬化的存儲空間可跨越多個異構的磁碟陣列，具有高度的穩定性和開放性，實現容易、簡便。但對異構環境和分散管理不太適應。

2）基於存儲設備的虛擬化存儲，因一些高端磁碟陣列本身具有智能化管理，可以實現同一陣列，供不同主機分享。其結構性能可達到最優。但實現起來價格昂貴，可操作性差。

3）基於網路的虛擬化存儲，通過使用專用的存儲管理伺服器和相應的虛擬化軟體，實現多個主機/伺服器對多個異構存儲設備之間進行訪問，達到不同主機和存儲之間真正的互連和共享，成為虛擬存儲的主要形式。根據不同結構可分為基於專用伺服器和基於存儲路由器兩種方式。①基於專用伺服器的虛擬化，是用一台伺服器專用於提供系統的虛擬化功能。根據網路拓撲結構和專用伺服器的具體功能，其虛擬化結構有對稱和非對稱兩種方式。在對稱結構中數據的傳輸與元數據訪問使用同一通路。實現簡單，對伺服器和存儲設備的影響小，對異構環境的適應性強。缺點是專用伺服器可能成為系統性能的瓶頸，影響SAN的擴展。在非對稱結構中，數據的傳輸與元數據訪問使用不同通路。應用伺服器的I/O命令先通過命令通路傳送到專用伺服器，獲取元數據和傳輸數據視圖後，再通過數據通路得到所需的數據。與對稱結構相比，提高了存儲系統的性能，增加了擴展能力。②基於存儲路由器的SAN虛擬化，存儲路由器是一種智能化設備，既具有路由器的功能，又針對I/O進行專門優化。它部署在存儲路由器上，多個存儲路由器保存著整個存儲系統中的元數據多個副本，並通過一定的更新策略保持一致性。這種結構中，因存儲路由器具有強大的協議功能，所以具有更多的優勢。能充分利用存儲資源，保護投資。能實現軟硬體隔離，並輔有大量的自動化工具，提高了虛擬伺服器的安全性，降低對技術人員的需求和成本。

⑺ 如何處理海量數據

在實際的工作環境下，許多人會遇到海量數據這個復雜而艱巨的問題，它的主要難點有以下幾個方面：
一、數據量過大，數據中什麼情況都可能存在。
如果說有10條數據，那麼大不了每條去逐一檢查，人為處理，如果有上百條數據，也可以考慮，如果數據上到千萬級別，甚至 過億，那不是手工能解決的了，必須通過工具或者程序進行處理，尤其海量的數據中，什麼情況都可能存在，例如，數據中某處格式出了問題，尤其在程序處理時， 前面還能正常處理，突然到了某個地方問題出現了，程序終止了。
二、軟硬體要求高，系統資源佔用率高。
對海量的數據進行處理，除了好的方法，最重要的就是合理使用工具，合理分配系統資源。一般情況，如果處理的數據過TB級，小型機是要考慮的，普通的機子如果有好的方法可以考慮，不過也必須加大CPU和內存，就象面對著千軍萬馬，光有勇氣沒有一兵一卒是很難取勝的。
三、要求很高的處理方法和技巧。
這也是本文的寫作目的所在，好的處理方法是一位工程師長期工作經驗的積累，也是個人的經驗的總結。沒有通用的處理方法，但有通用的原理和規則。
下面我們來詳細介紹一下處理海量數據的經驗和技巧：
一、選用優秀的資料庫工具
現在的資料庫工具廠家比較多，對海量數據的處理對所使用的資料庫工具要求比較高，一般使用Oracle或者DB2，微軟 公司最近發布的SQL Server 2005性能也不錯。另外在BI領域：資料庫，數據倉庫，多維資料庫，數據挖掘等相關工具也要進行選擇，象好的ETL工具和好的OLAP工具都十分必要， 例如Informatic，Eassbase等。筆者在實際數據分析項目中，對每天6000萬條的日誌數據進行處理，使用SQL Server 2000需要花費6小時，而使用SQL Server 2005則只需要花費3小時。
二、編寫優良的程序代碼
處理數據離不開優秀的程序代碼，尤其在進行復雜數據處理時，必須使用程序。好的程序代碼對數據的處理至關重要，這不僅僅是數據處理准確度的問題，更是數據處理效率的問題。良好的程序代碼應該包含好的演算法，包含好的處理流程，包含好的效率，包含好的異常處理機制等。
三、對海量數據進行分區操作
對海量數據進行分區操作十分必要，例如針對按年份存取的數據，我們可以按年進行分區，不同的資料庫有不同的分區方式，不 過處理機制大體相同。例如SQL Server的資料庫分區是將不同的數據存於不同的文件組下，而不同的文件組存於不同的磁碟分區下，這樣將數據分散開，減小磁碟I/O，減小了系統負荷， 而且還可以將日誌，索引等放於不同的分區下。
四、建立廣泛的索引
對海量的數據處理，對大表建立索引是必行的，建立索引要考慮到具體情況，例如針對大表的分組、排序等欄位，都要建立相應 索引，一般還可以建立復合索引，對經常插入的表則建立索引時要小心，筆者在處理數據時，曾經在一個ETL流程中，當插入表時，首先刪除索引，然後插入完 畢，建立索引，並實施聚合操作，聚合完成後，再次插入前還是刪除索引，所以索引要用到好的時機，索引的填充因子和聚集、非聚集索引都要考慮。
五、建立緩存機制
當數據量增加時，一般的處理工具都要考慮到緩存問題。緩存大小設置的好差也關繫到數據處理的成敗，例如，筆者在處理2億條數據聚合操作時，緩存設置為100000條/Buffer，這對於這個級別的數據量是可行的。
六、加大虛擬內存
如果系統資源有限，內存提示不足，則可以靠增加虛擬內存來解決。筆者在實際項目中曾經遇到針對18億條的數據進行處理， 內存為1GB，1個P42.4G的CPU，對這么大的數據量進行聚合操作是有問題的，提示內存不足，那麼採用了加大虛擬內存的方法來解決，在6塊磁碟分區 上分別建立了6個4096M的磁碟分區，用於虛擬內存，這樣虛擬的內存則增加為 4096*6 + 1024 =25600 M，解決了數據處理中的內存不足問題。
七、分批處理
海量數據處理難因為數據量大，那麼解決海量數據處理難的問題其中一個技巧是減少數據量。可以對海量數據分批處理，然後處 理後的數據再進行合並操作，這樣逐個擊破，有利於小數據量的處理，不至於面對大數據量帶來的問題，不過這種方法也要因時因勢進行，如果不允許拆分數據，還 需要另想辦法。不過一般的數據按天、按月、按年等存儲的，都可以採用先分後合的方法，對數據進行分開處理。
八、使用臨時表和中間表
數據量增加時，處理中要考慮提前匯總。這樣做的目的是化整為零，大表變小表，分塊處理完成後，再利用一定的規則進行合 並，處理過程中的臨時表的使用和中間結果的保存都非常重要，如果對於超海量的數據，大表處理不了，只能拆分為多個小表。如果處理過程中需要多步匯總操作， 可按匯總步驟一步步來，不要一條語句完成，一口氣吃掉一個胖子。
九、優化查詢SQL語句
在對海量數據進行查詢處理過程中，查詢的SQL語句的性能對查詢效率的影響是非常大的，編寫高效優良的SQL腳本和存儲 過程是資料庫工作人員的職責，也是檢驗資料庫工作人員水平的一個標准，在對SQL語句的編寫過程中，例如減少關聯，少用或不用游標，設計好高效的資料庫表 結構等都十分必要。筆者在工作中試著對1億行的數據使用游標，運行3個小時沒有出結果，這是一定要改用程序處理了。
十、使用文本格式進行處理
對一般的數據處理可以使用資料庫，如果對復雜的數據處理，必須藉助程序，那麼在程序操作資料庫和程序操作文本之間選擇， 是一定要選擇程序操作文本的，原因為：程序操作文本速度快；對文本進行處理不容易出錯；文本的存儲不受限制等。例如一般的海量的網路日誌都是文本格式或者 csv格式（文本格式），對它進行處理牽扯到數據清洗，是要利用程序進行處理的，而不建議導入資料庫再做清洗。
十一、定製強大的清洗規則和出錯處理機制
海量數據中存在著不一致性，極有可能出現某處的瑕疵。例如，同樣的數據中的時間欄位，有的可能為非標準的時間，出現的原因可能為應用程序的錯誤，系統的錯誤等，這是在進行數據處理時，必須制定強大的數據清洗規則和出錯處理機制。
十二、建立視圖或者物化視圖
視圖中的數據來源於基表，對海量數據的處理，可以將數據按一定的規則分散到各個基表中，查詢或處理過程中可以基於視圖進行，這樣分散了磁碟I/O，正如10根繩子吊著一根柱子和一根吊著一根柱子的區別。
十三、避免使用32位機子（極端情況）
目前的計算機很多都是32位的，那麼編寫的程序對內存的需要便受限制，而很多的海量數據處理是必須大量消耗內存的，這便要求更好性能的機子，其中對位數的限制也十分重要。
十四、考慮操作系統問題
海量數據處理過程中，除了對資料庫，處理程序等要求比較高以外，對操作系統的要求也放到了重要的位置，一般是必須使用伺服器的，而且對系統的安全性和穩定性等要求也比較高。尤其對操作系統自身的緩存機制，臨時空間的處理等問題都需要綜合考慮。
十五、使用數據倉庫和多維資料庫存儲
數據量加大是一定要考慮OLAP的，傳統的報表可能5、6個小時出來結果，而基於Cube的查詢可能只需要幾分鍾，因此處理海量數據的利器是OLAP多維分析，即建立數據倉庫，建立多維數據集，基於多維數據集進行報表展現和數據挖掘等。
十六、使用采樣數據，進行數據挖掘
基於海量數據的數據挖掘正在逐步興起，面對著超海量的數據，一般的挖掘軟體或演算法往往採用數據抽樣的方式進行處理，這樣 的誤差不會很高，大大提高了處理效率和處理的成功率。一般采樣時要注意數據的完整性和，防止過大的偏差。筆者曾經對1億2千萬行的表數據進行采樣，抽取出 400萬行，經測試軟體測試處理的誤差為千分之五，客戶可以接受。
還有一些方法，需要在不同的情況和場合下運用，例如使用代理鍵等操作，這樣的好處是加快了聚合時間，因為對數值型的聚合比對字元型的聚合快得多。類似的情況需要針對不同的需求進行處理。
海量數據是發展趨勢，對數據分析和挖掘也越來越重要，從海量數據中提取有用信息重要而緊迫，這便要求處理要准確，精度要高，而且處理時間要短，得到有價值信息要快，所以，對海量數據的研究很有前途，也很值得進行廣泛深入的研究。