數據即索引-大數據索引漫談
- 2019 年 12 月 24 日
- 筆記
傳統意義上的索引，目標是為了加快查詢速度，但獨立於數據，通常可以加載到內存，典型的比如B-Tree等。
但在大數據里，這點就變得有點trick了，因為即使索引比實際數據小很多，但是因為實際數據實在是大，所以索引依然會很大，很有可能依然無法放入到內存，所以會導致很多傳統數據庫的索引模式對大數據其實是不work的。因為我對傳統數據庫的知識有限，所以接下來我重點還是會放在大數據索引相關的思考上。
大數據索引葉子節點通常是chunk(block)/file/cube而不會是最細粒度的Row。一則大數據採用的是列式存儲，二則如果到Row級別，我們前面說了，索引會非常非常的大。這說明大數據索引追求的是chunk(block)/file/cube skip,最終目標是盡量減少不必要的文件掃描，但對於定位到的文件，還是需要【暴力】filter 出chunk(block)/file/cube里的記錄，最後返回。通過這種模式可以有效減少Task數，因為通常一個chunk(block)/file/cube 對應一個或者多個Task,提升查詢速度。
在進一步討論之前，我們簡單說下chunk(block)/file/cube 的概念。 chunk(block)可以組成file,多個file 可以組成一個cube.之所以分成三個層級，是為了方便多個層級的索引構建。比如執行cube的索引就可能非常小，其次是file, file裏面又可以自己包含block的索引。比如Carbondata就是到block級別的。
前面我們提到，本質上大數據的索引是在做 file skip(你定位到一個cube其實就是為了找到一組file,或者你找到一個block,你也需要找到block所在的file)，精準定位file集合可以有效的減少task數目，提升查詢速度。而通常對於一張表，文件數總數是不會很大的(畢竟HDFS的文件數量也是有上限的），比如幾千到幾十萬。這個時候就可以很好的使用B-Tree等索引了，當然，實際上數據這麼小的情況，我們還可以直接使用一個線性結構保存，需要的時候過濾下即可，不一定需要使用樹結構（越簡單越好）。但是，大數據其實對單表查詢並不多，反而是多表關聯子查詢特別多，意味着我們最終單表我們還是要過濾出非常大量的數據，而結果集越大，那麼可能命中的file數越大，對於條件
from table1 where x>100 && y< 100000
假設table1有一萬個文件，如果記錄是隨機分配到一萬個文件，那麼大概率where x>100&& y<100000 的記錄就會散落在所有的文件里，這個時候file skip的意義就沒有了，因為這意味着我們需要訪問訪問所有的文件。所以，為了能夠讓file skip變得有意義，我們需要確保數據按一定分佈規則分佈到這一萬個文件里。對於where x>100&& y<100000，我們可以用z-ordering index將x,y這個二維的過濾條件轉化成一個一維的地址，這樣我們就地址按區間分佈到這一萬個文件里，這樣就可以讓file skip起作用。
前面我們得到結論，無論如何，在大數據里做索引，本質上都是為了實現file skip,而file skip必然要改變數據的在文件集合里的分佈情況。從某種意義上說，帶有一定分佈規律的數據自身就是索引，我們傳統所說的索引只是保存了這種分佈規律。
這個事實其實會帶來一個比較有意思的結果，就是大數據里的索引和數據可以保持一樣大。而在傳統數據庫中，索引可能遠小於數據，也可能遠大於數據。因為通常一種數據分佈只能滿足一定類型（或者維度組合的）查詢，所以為了滿足多種查詢需求，我們可能需要多種數據分佈，那麼就需要有N份數據的存儲。所以我覺得數據湖應該要擁抱這個事實。
通常而言，這是一種無損的索引模式，因為即使我們不能利用數據分佈加快數據的查詢速度，但是我們依然可以回退到【暴力】掃描從而得到正確結果。比如用戶的查詢不符合z-ordering index的要求，我們依然可以跳過z-ordering index得到正確的結果，付出的代價不過是降低了響應速度。
而我們以前數倉分層模型里提到的視圖概念，尤其是最近開始火熱的物化視圖，則是一種有損索引模式。在物化視圖裡，裏面本質上存儲的也是數據，但是這個數據不是簡單的改變了數據在文件集合里的分佈，而是直接做了提純，所以他只能滿足特定查詢。儘管如此，物化視圖滿足前面我們提及的數據即索引的規則。
大家對布隆過濾器有一定的了解，他是一個並不精確的算法，通過一些組合維度判定一條記錄是不是已經存在。通常我們可以為每個file準備一個布隆過濾器，也可以為一個cube準備一個布隆過濾器，這取決於你的內存需求，然後因為布隆過濾器判定一個row不在，那他一定不在，而如果他判定在，則可能在，所以我們可能會將一個不包含某個row的文件判定為包含，但不會將一個實際包含了某個Row的文件判定為不包含，也就是說會多出一些文件，但是因為我們只是為了減少不必要的文件，而不是一定要精確的進行判定，所以布隆過濾器顯得非常有用。然而，他從某種角度完全可以被z-ordering index所取代，因為z-ordering index可以實現多維度組合的file skip。但是為什麼我們可能還是偏向於使用布隆過濾器呢？z-ordering index需要改變數據的分佈，這意味着我們可能為此需要多付出一倍存儲的代價，而布隆過濾器則會小很多，然後可以被載入內存。但是如果話說回來，某種角度而言，數據分佈是必須要滿足的，在某些場景，如果不滿足數據分佈，布隆過濾器可能會發揮所有的文件，這甚至會有損性能。
總結下，以物化視圖為代表的有損索引，和以z-ordering index為代表的的無損索引，本質上都是以數據分佈作為索引。大數據索引解決的核心問題是file skip而非rwo skip, 而file skip必然會帶來數據在文件集中的分佈要求，為了滿足多樣化的查詢，從而使得數據發生膨脹，而膨脹率則是索引（數據分佈）的數量N*數據大小。
