構(gòu)建大數(shù)據(jù)系統(tǒng)的前沿技術(shù)概述

第一部分存儲(chǔ)模型之前，先拋兩個(gè)問題：

1)這些存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，主要是來優(yōu)化什么操作的?

2)SSD對(duì)于這些存儲(chǔ)結(jié)構(gòu)有什么樣的影響?

一. 存儲(chǔ)模型--讀和寫的取舍

一個(gè)好的存儲(chǔ)結(jié)構(gòu)，我們希望的是更新數(shù)據(jù)快，查找特定的數(shù)據(jù)也快，最好占用空間還小，一般來說，這算得上是對(duì)存儲(chǔ)的終極要求了。

終極要求，這東西一般都是YY，但是，加上一定的限制條件，在特定的時(shí)期，數(shù)據(jù)大爆炸之前，單機(jī)時(shí)代，B樹這個(gè)結(jié)構(gòu)，可以算得上是銀彈?；旧纤械?a href='/map/guanxixingshujuku/' style='color:#000;font-size:inherit;'>關(guān)系型數(shù)據(jù)庫系統(tǒng)都采用這種結(jié)構(gòu)。SqlServer和Oracle都采用B樹，Mysql，Db2還有informix采用的B+樹，

磁盤讀數(shù)據(jù)和寫數(shù)據(jù)的過程，1)移動(dòng)磁頭到對(duì)用的扇區(qū)，2)然后磁頭接觸磁道，寫或者讀數(shù)據(jù)，3)通過總線傳輸?shù)絻?nèi)存或者寄存器。

磁頭移動(dòng)時(shí)間，十分之一秒的級(jí)別，讀寫的時(shí)間，按照普通磁盤，7200轉(zhuǎn)的，差不多在百分之一秒級(jí)不到，還有一個(gè)耗時(shí)就是總線傳輸時(shí)間，這個(gè)基本可以忽略，在10的8次方分之秒。

另一個(gè)背景知識(shí)是，文件系統(tǒng)， 讀寫是有最小操作單位的塊，每次I/O操作，都是整塊操作。塊大小，跟文件系統(tǒng)的格式有關(guān)，fat32，ext3/4等等，常見的塊大小4096個(gè)字節(jié)，塊大小可以調(diào)整，塊，對(duì)應(yīng)到物理的扇區(qū)。

通過上面的分析，有效的優(yōu)化是降低磁頭定位的次數(shù);B樹就是綜合讀寫兩方面的需求，提出的對(duì)磁頭定位操作優(yōu)化的結(jié)構(gòu)。隱含的數(shù)據(jù)特征是：重查詢，輕新增，并發(fā)寫要求不高?？偟臄?shù)據(jù)量優(yōu)先，單挑記錄會(huì)被反復(fù)更新，這剛好就是單機(jī)時(shí)代的數(shù)據(jù)特征。在做關(guān)系型數(shù)據(jù)庫表設(shè)計(jì)的時(shí)候，知道這點(diǎn)會(huì)比較有用。

B+樹和B*樹是B樹的兩種變形，B+樹降低了中間節(jié)點(diǎn)的數(shù)據(jù)大小，同樣的塊大小，可以存儲(chǔ)更多的數(shù)據(jù)，檢索上更有效率，但是，實(shí)際數(shù)據(jù)讀取上有妥協(xié)。B*樹，相對(duì)于B數(shù)在節(jié)點(diǎn)的分裂，旋轉(zhuǎn)，平衡方面有增強(qiáng)。

進(jìn)入互聯(lián)網(wǎng)時(shí)代，數(shù)據(jù)的特征有了變化，寫多讀少，數(shù)據(jù)具備熱點(diǎn)時(shí)間。有效期之后的數(shù)據(jù)，就相當(dāng)于傳統(tǒng)數(shù)據(jù)庫的歸檔。另外一個(gè)有利的變化，是內(nèi)存變得很便宜，可以用足夠低的成本hold住熱點(diǎn)數(shù)據(jù)。這種前提下，順序?qū)懽龀志没?，熱點(diǎn)數(shù)據(jù)保持在內(nèi)存中，并且在內(nèi)存中進(jìn)行排序，保證順序?qū)懭氲臄?shù)據(jù)是有序的。

基于這樣的思路，就有了LSM-Tree和COLA-Tree兩種改進(jìn)。區(qū)別在于LSM的MemTable保持固定大小，持久化數(shù)據(jù)的索引都有compaction階段完成。COLA的思路，是Memtable就按照固定的邏輯完成索引更新。COLA里面是沒有Memtable這個(gè)名稱的。

基本上現(xiàn)存所有的NoSQL都是采用LSM-Tree的思路，除了TokuDB。

Cassandrda和LevelDB，需要特別提一下，他們兩個(gè)在Compaction階段的實(shí)現(xiàn)，是參考了COLA的做法的，sstable做了分層合并。COLA在層之間，還引入了分形樹(Fractal Tree)的實(shí)現(xiàn)，改進(jìn)索引性能，Cassandra和LevelDB是沒有，單層上數(shù)據(jù)檢索，還是采用的BloomFilter和二分法。

二.實(shí)時(shí)計(jì)算-精度和速度的權(quán)衡

純粹從性能對(duì)比，COLA跟B樹算是公平對(duì)決，數(shù)據(jù)如下：塊大小4098字節(jié)

查詢Cola比B樹慢12倍，插入速度是B樹的340倍。

LSM不具備可比性，更多靠cache命中的效率。

之前提到的問題，SSD的影響，這么看起來，SSD對(duì)B樹和Toku的影響要比LSM大(只是相對(duì)的)，這些算法，對(duì)于ssd來說，算法對(duì)性能的影響并不重要，比較重要的反而是，通過算法降低，flash的讀寫次數(shù)，達(dá)到延長ssd使用壽命和減少損壞率。

除了需要保存檢索數(shù)據(jù)，還需要對(duì)數(shù)據(jù)進(jìn)行計(jì)算，流計(jì)算，實(shí)時(shí)計(jì)算的框架，已經(jīng)是大數(shù)據(jù)里面到處可見，Storm，Spark Stream等等，這些流行框架更多是調(diào)度系統(tǒng)，真正的計(jì)算還需要自己來實(shí)現(xiàn)。

在我現(xiàn)在的實(shí)際工作中，常見的有點(diǎn)難度的計(jì)有exist是否存在，distinct count 去重計(jì)數(shù)，top n 等等在 window內(nèi)部。

所有這些計(jì)算，對(duì)于內(nèi)存都是很巨大的挑戰(zhàn)。可行的做法，就是引入精度，接受概率。

這些做法，在數(shù)據(jù)挖掘的領(lǐng)域，已經(jīng)是司空見慣的做法，比如關(guān)聯(lián)規(guī)則挖掘的Apriori跟Fp-growth等都引入的概率的做法。

很多程序員其實(shí)也用過，一說就知道，Bloom Filter做去重，接受一定概率的誤差，換來空間的減少，提升性能。

接下來介紹幾個(gè)，我在實(shí)際工作中，用得比較多的方法，實(shí)際上是幾個(gè)概念。

1)Bloom Filter

2)Sketching

3)基數(shù)估計(jì)

BF略過，大家都知道。Sketching，用于做頻率估計(jì)，估算數(shù)據(jù)流中每個(gè)數(shù)據(jù)的出現(xiàn)次數(shù)?；舅悸芬哺鶥F差不多，通過互相獨(dú)立的hash函數(shù)依次處理輸入，接受一定程度的正負(fù)錯(cuò)判，估計(jì)值在一定概率內(nèi)正確，這個(gè)概率可調(diào)整。這類方法的另一個(gè)優(yōu)勢是可以很容易實(shí)現(xiàn)分布式，能夠合并。

Sketch有幾個(gè)變種，basic sketch， counter sketch和counter min sketch，依次各有改進(jìn)。

Bf和counter min sketch算是當(dāng)前最優(yōu)的top n的方法。Cms對(duì)于重復(fù)度高的效果較好，重復(fù)度不高了，有基于cms基礎(chǔ)上的改進(jìn)，counter-mean-min sketch。

上面在存儲(chǔ)模型中間沒有提到，cms還能夠用在nosql的range query索引上，不追求精確度，在性能方面完爆B樹。

基數(shù)估計(jì)也是類似的思路，用很少的空間，計(jì)算集合的勢，常見的算法有Linear counter，LogLog counter兩類，分別使用在重復(fù)情況比較明顯和重復(fù)情況相對(duì)于總量來說較低

Redis在支持bitmap之后，在2.8.9之后，直接提供了hyperloglog的支持，每個(gè) HyperLogLog 鍵只需要花費(fèi) 12 KB 內(nèi)存，就可以計(jì)算接近 2^64 個(gè)不同元素的基 數(shù)。線性的counter也可以直接利用bitmap實(shí)現(xiàn)。Hash函數(shù)的murmur是比較可以無腦使用的實(shí)現(xiàn)。

具體的算法描述，大家可以問百度，不細(xì)說了，知道有哪些可用場景就好。我們主要用在風(fēng)險(xiǎn)檢測的參數(shù)計(jì)算方面。

三.分布式持久化-CAP的妥協(xié)

對(duì)于分布式持久化的內(nèi)容，也扯兩句，我個(gè)人很喜歡Dynamo模型的對(duì)稱結(jié)構(gòu)，BigTable的管理節(jié)點(diǎn)實(shí)在是不美觀。也就是zk和gossip+vector clock的戰(zhàn)爭，這種選擇也就決定了各自在CAP和ACID中間能夠達(dá)到的水平。

四.日志為中心的基礎(chǔ)架構(gòu)設(shè)計(jì)

ArchSummit全球架構(gòu)師峰會(huì) 上我也推薦過kafka的作者寫的文章，在推薦一次，個(gè)人覺得每一個(gè)做分布式系統(tǒng)設(shè)計(jì)的架構(gòu)師，都應(yīng)該讀幾遍才好。

給大家看這樣一個(gè)圖

蘇寧現(xiàn)在整體數(shù)據(jù)系統(tǒng)建設(shè)思路，差不多就是這樣，通過日志，串行所有操作，避免沖突?；旧蠞M足異地多活的需求。中間過程，分實(shí)時(shí)計(jì)算，批量計(jì)算并且在服務(wù)層合并數(shù)據(jù)。