『壹』 介紹一下海量數據的處理方法
介紹一下海量數據的處理方法
適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集
基本原理及要點：
對於原理來說很簡單，位數組+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，效率不會很高。而上面的分布式方法，也可以用於單機版本，也就是將總的數據根據值的范圍，劃分成多個不同的子文件，然後逐個處理。處理完畢之後再對這些單詞的及其出現頻率進行一個歸並。實際上就可以利用一個外排序的歸並過程。
另外還可以考慮近似計算，也就是我們可以通過結合自然語言屬性，只將那些真正實際中出現最多的那些詞作為一個字典，使得這個規模可以放入內存。
『貳』 BitMap及其在ClickHouse中的應用
問題要從面試或者大數據場景下最常見的一個演算法說起，問題是這樣的，假如有幾十億個unsigned int類型的數據，要求去重或者計算總共有多少不重復的數據？最簡單的辦法就是直接利用一個HashMap，進行去重。但是這裡面有個內存使用量的問題，幾十億個元素，即使不考慮HashMap本身實現所用到的數據結果，單單key本身，假如每個unsigned int佔用4個位元組，簡單算一下的話，這里都需要幾十GB的內存佔用，因此，這里就引出了BItMap。
BItMap的思想非常簡單，就是用一個bit表示一個二元的狀態，比如有或者沒有，存在或者不存在，用bit本身的位置信息，對應不同的數據。比如針對上面的問題，我們可以開辟一個2^32 bit的內存空間，每一個bit存儲一個unsigned int類型的數據，有就是1，沒有就是0，總共需要存儲unsigned int類型的最大范圍個數據，也就是2^32 個數據，這個2^32其實就是所謂的基數。如下圖所示：
假如存在數字8，那就把對應的第8位的值賦為1。上圖插入的數據為1、3、7、8。接著依次把所有的數據遍歷然後更新這個BitMap。這樣我們就可以得到最終結果。
假如上面的問題變成了對幾十億個URL做判斷，那應該怎麼去做呢？URL沒有辦法和BitMap的位置關系對應上，所以，我們需要加一層哈希，把每個URL經過哈希運算得到一個整數，然後對應上BitMap。如下圖所示：
但是有哈希，肯定會存在碰撞，如果BitMap基數（也就是長度）比較小，那碰撞的概率就大，如果基數比較大，那佔用的空間又會比較多。Bloom Filter的思想就是引入多個哈希函數來解決沖突的問題。也就是說對每個URL，經過多個哈希函數的運算，得到多個值，每個數值對應的BitMap的對應的位置都賦值為1。這個兩個URL經過多個哈希函數結果還是一樣的概率就大大降低。
但是由於依然存在沖突的可能性（其實沖突就是來源於我們BitMap的長度小於了數據量的基數，這也就是犧牲了准確性換來了空間使用的減少），所以Bloom Filter 存在假陽性的概率，不適用於任何要求 100% 准確率的場景，也就是說Bloom Filter 只能用來判無，不能用來判有。比如一個URL經過多次哈希運算之後，發現對應的BitMap的位置都已經是1了，那也不能說明，這個URL之前存在過了，也有可能是哈希沖突的結果。但是一個URL經過多次哈希運算之後，發現對應的BitMap的位置不是都是1，那當前URL之前一定是沒有存在過的。
可以看到，Bloom Filter 引入多次哈希，在查詢效率和插入效率不變的情況下，用較少空間的BitMap解決大數據量的判斷問題。
大部分情況下僅僅做有無的判斷是不能滿足使用需求的，我們還是需要真正意義上的BitMap（可以方便的用來做交並等計算），但是最好可以在基數比較大的時候，依然可以佔用相對比較小的空間。這就是RoaringBitMap所要實現的。
簡單來說RoaringBitMap是BitMap的一種帶索引的復雜BitMap數據結構。以32位的RoaringBitMap為例，首先劃分2^16 個空間（Container），每個Container內部都是一個大小為2^16 bit的BitMap，總的內存使用量還是2^32 = 512Mb。這樣的話和普通的BitMap是沒有區別的，而RoaringBitMap的創新之處在於每個Container內的BitMap是在沒有使用到的情況下是可以不分配內存空間的。這樣可以大大減小內存的使用量。
（這個圖片是Roaring Bitmaps: Implementation of an Optimized Software Library 論文原圖）
要將一個4個位元組的數據插入RoaringBitMap，首先要用數據的高16位，找到對應的Container，然後用數據的低16在Container中插入。
在每個Container內部，RoaringBitMap不是簡單的用BitMap來進行數據的存儲，而是把Container的類型劃分為幾種，不同的Container用來存儲不同情況的數據。
當2個位元組（4個位元組的原數據，低16位用來插入具體的Container中）的數據，總的個數小於4096個的時候，當前Container使用 array Container。為什麼是4096個呢？4096*2B=8Kb，而一個Container如果是bitmap的結構的話，最多也就是2^16bit=8Kb的空間。所以這里當數據個數小於4096使用array Container會更節省空間。當然這里名字為array Container，實際上是鏈表結構，不需要最開始就初始化4096個short int的數組。
當array Container存儲的數到4096個的時候（也就是使用內存到8Kb的時候），array Container會轉換為bitmap container，bitmap container就是一個2^16 bit普通的bitmap，可以存儲2^16 = 65536個數據。這個8Kb還有一個好處，是可以放到L1 Cache中，加快計算。
這個嚴格的說，只是一種數據壓縮存儲方法的實現。其壓縮原理是對於連續的數字只記錄初始數字以及連續的長度，比如有一串數字 12,13,14,15,16 那麼經過壓縮後便只剩下12,5。從壓縮原理我們也可以看出，這種演算法對於數據的緊湊程度非常敏感，連續程度越高壓縮率也越高。當然也可以實現其他的壓縮方法。
RoaringBitMap其核心就在於加了一層索引，利用復雜的數據結構換取了空間上的效率。需要注意的是這里並沒有增加計算的復雜度，其出色的數據結構讓其在做交並計算的時候性能也毫不遜色。
ClickHouse中有bloom_filter類型的Skipping indexs，可以方便的用來過濾數據。
ClickHouse實現了大量的BitMap的函數，用來操作BitMap。ClickHouse中的BitMap在32位的時候用的是Set實現的，大於32位的時候也是使用RoaringBitMap實現的。我們這里不看具體的函數，我們來看一個典型的使用場景。
最常見的一個場景是根據標簽來進行用戶的圈選。常見的解決辦法是有一張用戶標簽表，比如
要查詢標簽tag1='xx'和tag2='xx'的用戶需要執行SQL：
但是由於不可能對每個tag列構建一級索引，所以這條SQL執行的效率並不高。可選的一種方式是先構建關於標簽的BitMap數據結果，然後進行查詢：
（1） 創建tag的bitmap表：
（2）寫入數據
（3）查詢
如果有多張tag表，進行交並計算（要比普通的用戶表進行JOIN或者IN計算要高效很多）：
『叄』 Redis 大數據內存優化 (RoaringBitmap)
最近碰到手機設備匹配的業務, 用戶在我司後台可以上傳人群包, 裡面存放的是設備的MD5標識符; 一個人群包大概有千萬級的MD5數據, 與廣告請求所攜帶設備標識進行匹配.
嘗試插入1kw條數據, key為設備MD5值, value為1, 此時Redis中存在1kw條key-value鍵值對.
通過 info 指令查看內存佔用:
8bit = 1b = 0.001kb
bitmap即點陣圖, 就是通過最小的單位bit來進行0或者1的設置，表示某個元素對應的值或者狀態。
一個bit的值，或者是0，或者是1；也就是說一個bit能存儲的最多信息是2。
場景: 有用戶id分別為1, 2, 3, 4, 5, 6, 7, 8的用戶, 其中用戶2, 5在今日登錄, 統計今
日登錄用戶
採用點陣圖存儲: 用戶id為偏移量, 可以看做是在點陣圖中的索引, value為true
通過 bitcount 獲取登錄用戶數為2:
測試offset從1-1kw連續整數時候的內存佔用:
可以發現內存佔用僅為 1.19MB, 1個億的數據也才12MB, 極大的減少了內存;
由於我們的業務沒有如此完美的情況出現, 採用設備MD5的hash做Offset, 不會出現連續正整數的情況;
各常用Hash函數性能對比: https://byvoid.com/zhs/blog/string-hash-compare/
所以我們接下來測試1kw條MD5數據的點陣圖內存佔用:
查看Redis內存佔用:
問題: 為什麼同樣1kw的bitmap, MD5數據的Hash佔用會比 測試一 的多200倍?
將32位無符號整數按照高16位分桶，即最多可能有216=65536個桶，稱為container。存儲數據時，按照數據的高16位找到container（找不到就會新建一個），再將低16位放入container中。也就是說，一個RBM就是很多container的集合。
圖中示出了三個container：
1kw條MD5數據的插入: