1. 前言
????????會(huì)想著寫izanami這么一個(gè)數(shù)據(jù)庫(kù)，很大一部分原因是因?yàn)榭匆姾芏鄶?shù)據(jù)分析的同事老是自嘲道“只會(huì)group by”。以前做RDBMS的時(shí)候，遇到group by通常都會(huì)希望后面的列跟著索引，那樣的話數(shù)據(jù)預(yù)先就是排好序的，比較方便。但是但多數(shù)數(shù)據(jù)庫(kù)都是采用B-Tree這種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)索引的，當(dāng)內(nèi)存中的數(shù)據(jù)寫入磁盤的時(shí)候，會(huì)有大量的隨機(jī)IO，一塊普通的機(jī)械盤iops大概也就一兩百的樣子，很難說(shuō)能夠滿足業(yè)務(wù)需求。剛好差不多弄了一年的HBase，對(duì)LSM樹有比較深的了解，所以就想著能不能用LSM樹，實(shí)現(xiàn)一個(gè)分布式存儲(chǔ)系統(tǒng)，專門存索引數(shù)據(jù)，這樣對(duì)olap分析也許會(huì)有幫助。
2.? 關(guān)于LSM樹
???????? 其實(shí)說(shuō)白了LSM樹跟B-Tree沒(méi)有什太大的區(qū)別，甚至可以說(shuō)為了讀取效率，LSM樹的“夢(mèng)想”就是變成一個(gè)B-Tree。雖然隨機(jī)的內(nèi)存IO雖然理論上來(lái)說(shuō)會(huì)因?yàn)閏ache實(shí)效而導(dǎo)致效率偏低，但是由于它是電子設(shè)備還是要比只能達(dá)到幾百iops的磁盤強(qiáng)很多。LSM樹針對(duì)這種原理，將最近寫入的可能產(chǎn)生隨機(jī)IO的數(shù)據(jù)都放到內(nèi)存內(nèi)部，以一顆B-Tree或者跳躍表的形式維護(hù)，等數(shù)據(jù)量到達(dá)一定大小或者過(guò)了一段時(shí)間之后在flush到磁盤上形成一個(gè)文件，這樣這個(gè)文件可以看成是一個(gè)序列化的B-Tree。隨著時(shí)間推移，磁盤上的文件會(huì)越來(lái)越多，但是查詢的時(shí)候，每個(gè)文件都可能有你想要的數(shù)據(jù)，再加上普通磁盤iops就那么點(diǎn)，所以讀取效率就自然低了，為了解決這個(gè)問(wèn)題最常見的兩個(gè)做法就是布隆過(guò)濾器跟compact了，布隆過(guò)濾器是個(gè)治標(biāo)不治本的辦法，compact說(shuō)白了就是將多個(gè)局部有序的存放在磁盤上的B-Tree重讀重寫一次，形成一顆單獨(dú)的B-Tree，這樣一來(lái)只會(huì)有一棵樹，單次查詢的iops就降下來(lái)了（雖然compact也可以刪除多余數(shù)據(jù)，但是還是感覺(jué)降低iops是最重要的）。
???????? 既然LSM樹在oltp這種需要iops的系統(tǒng)中表現(xiàn)不佳，那么把它放到olap系統(tǒng)中怎么樣呢？這樣可以實(shí)時(shí)寫入，而且olap系統(tǒng)可以借助系統(tǒng)的page/cache達(dá)到跟內(nèi)存讀差不了太多的效果。
3. 關(guān)于izanami
????????izanami是本人以LSM樹，結(jié)合索引的原理，寫的一個(gè)分布式數(shù)據(jù)庫(kù)。由于近一年來(lái)都在維護(hù)公司的HBase，所以這個(gè)數(shù)據(jù)庫(kù)也融合了很多HBase的概念，比如使用非結(jié)構(gòu)化的存儲(chǔ)方式、最基本的數(shù)據(jù)模型都是一種叫做cell的數(shù)據(jù)結(jié)構(gòu)。但是由于堅(jiān)持“解決gc最好的辦法是不用java”這種理念，所以是使用C語(yǔ)言編寫的。
3.1 基礎(chǔ)結(jié)構(gòu)
???????? 從某種角度來(lái)看，HBase是以rowkey/family/column/ts/type/mvcc/value為最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，構(gòu)成的最結(jié)構(gòu)化的行式數(shù)據(jù)庫(kù)。而izanami則是以column/value/rowkey/mvcc為最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)構(gòu)成的列式數(shù)據(jù)庫(kù)，而且兩者同樣都使用rowkey作為分區(qū)鍵，分區(qū)的名字也模仿HBase叫做region。其實(shí)izanami與orc這類列式存儲(chǔ)不同，orc可以說(shuō)是按照column/rowkey/value這樣的方式進(jìn)行存儲(chǔ)，這樣在列比較多的時(shí)候，就不用額外存儲(chǔ)空間在每個(gè)列的部分都存儲(chǔ)rowkey，相較于izanami省了不少存儲(chǔ)空間；但是在本人看來(lái)izanami的存儲(chǔ)方式也有自己的優(yōu)勢(shì)，值相近的數(shù)據(jù)都物理上連續(xù)在一起，其實(shí)這樣分析的時(shí)候做分析就非常方便了，這樣相當(dāng)于自帶了shuffle的功能，不需要額外的空間做分組聚合，oom的錯(cuò)誤概率也會(huì)變小，而且這樣存儲(chǔ)數(shù)據(jù)傾斜的概率會(huì)小很多。
下面是個(gè)例子
3.2關(guān)于數(shù)據(jù)冗余
????????可以考慮使用壓縮來(lái)改善izanami的存儲(chǔ)冗余，HBase的存儲(chǔ)原理其實(shí)跟izanami差不多，但是親測(cè)使用snappy之后，空間普遍只有原來(lái)的五分之一，再者按照壓縮的原理來(lái)說(shuō)，izanami的壓縮率可能比HBase更高，因?yàn)閏olumn、value、rowkey的相似度是依次遞減的，壓縮的原理又是用短的數(shù)據(jù)替代出現(xiàn)次數(shù)多的長(zhǎng)的數(shù)據(jù)，按照izanami的存儲(chǔ)原理，相似度最高的column更有可能存儲(chǔ)到一起，所以理論上壓縮率說(shuō)不定更高（自己精力有限，暫時(shí)做不了）。
3.3關(guān)于compact
????????正如前面所說(shuō)，compact過(guò)程對(duì)LSM樹系統(tǒng)尤為重要，但是其本質(zhì)就是將所有選中文件重讀重寫了一次，帶來(lái)的不小的讀寫放大，而且像HBase這種系統(tǒng)在文件數(shù)太多的情況下，compact速度還是不受限制的。雖然compact有很多不好的影響，但是為了讀取、尤其是oltp的隨機(jī)讀取，不得不做。izanami的定位是解決olap問(wèn)題，每次讀取（起碼在筆者的代碼中）都會(huì)讀取從選中文件中讀取一個(gè)比較大的數(shù)據(jù)塊（默認(rèn)1M），可以利用操作系統(tǒng)的page/cache 實(shí)現(xiàn)緩沖，但是隨著文件數(shù)量增加，每次讀取任務(wù)對(duì)應(yīng)的動(dòng)態(tài)生成的reader（代碼中一個(gè)動(dòng)態(tài)生成的數(shù)據(jù)結(jié)構(gòu)）也會(huì)變多，reader又是會(huì)在讀取過(guò)程中不斷排序的，所以理論上來(lái)說(shuō)也應(yīng)該有個(gè)compact操作來(lái)定時(shí)合并文件。可是compact的核心代碼就是用戶發(fā)出的讀取請(qǐng)求加上文件的flush，再加上筆者精力有限，也沒(méi)有實(shí)現(xiàn)。
3.4 關(guān)于delete與update
???????? 現(xiàn)在筆者做的模型是不支持這兩種操作的，雖然就筆者接觸的業(yè)務(wù)中，這兩種操作在分析系統(tǒng)中其實(shí)也不多，但是要支持也有辦法的。在每個(gè)region內(nèi)部維護(hù)另一個(gè)LSM樹，當(dāng)對(duì)應(yīng)的region接收到某個(gè)rowkey的某個(gè)column的刪除請(qǐng)求后，在這課LSM中添加一個(gè)類似column/rowkey/mvcc這樣的數(shù)據(jù)，當(dāng)客戶端有讀取請(qǐng)求的時(shí)候要保證讀取的cell中的mvcc要大于這個(gè)額外LSM樹中對(duì)應(yīng)記錄的mvcc。至于update則可以看成一次delete加上一次put操作。
???????? 隨著記錄刪除數(shù)據(jù)的LSM樹引入，可能會(huì)額外多一種compact。當(dāng)一個(gè)cell有多次刪除的時(shí)候，在新增的LSM樹中會(huì)有多條mvcc不同，但是rowkey跟column相同的數(shù)據(jù)，可以單獨(dú)使用一種compact專門針對(duì)這種記錄合并，只保存mvcc最大的cell。只有3.3中的compaction才可以徹底刪除所有的這種刪除記錄。
3.5 關(guān)于非結(jié)構(gòu)化
????????之所以將izanami設(shè)計(jì)為非結(jié)構(gòu)，是基于以下這種考慮，比如現(xiàn)在有個(gè)地理位置的列需要分析，但是這種數(shù)據(jù)又是每天都有的，業(yè)務(wù)有需要按天分析，那么可以考慮設(shè)計(jì)location20180101、location20180102這兩個(gè)列，分別表示兩天上報(bào)的數(shù)據(jù)。而且如果業(yè)務(wù)需要分析所有l(wèi)ocation數(shù)據(jù)的話，這些數(shù)據(jù)又是相鄰的。
3.6 izanami的缺點(diǎn)跟不規(guī)范的地方
????????izanami也有很多缺點(diǎn)：
????????1）對(duì)于oltp類型的讀取，izanami是完全沒(méi)能派上用場(chǎng)的；
????????2）為了而且方便最后內(nèi)存中的數(shù)據(jù)寫入文件，筆者沒(méi)有寫成一顆B-Tree，而是一個(gè)有序的文件；
????????3）關(guān)于izanami在分區(qū)容錯(cuò)性，由于筆者能力有限，也采用了最簡(jiǎn)單最粗暴的“CA”型方式。
4. 關(guān)于CAP的一些個(gè)人理解
4.1 一些CAP的說(shuō)法
????????CAP理論在分布式存儲(chǔ)系統(tǒng)中似乎已經(jīng)成為了一種共識(shí)，但是筆者認(rèn)為有些關(guān)于CAP的說(shuō)法實(shí)在是不能認(rèn)同：
????????1）MySQL（Innodb）是CA型數(shù)據(jù)庫(kù)
????????CAP理論是針對(duì)分布式系統(tǒng)的，MySQL（Innodb）在沒(méi)有mycat這類中間件的情況下，完全就是單機(jī)的，怎么能這樣劃分呢？
????????2）CAP最多三者取其二
????????任何一個(gè)關(guān)于HBase的教材幾乎都會(huì)表示HBase是為了一致性而放棄可用性的系統(tǒng)，是一種CP型。但是如果按照三者最多取其二的說(shuō)法，那HBase就不該有可用性，平時(shí)讀寫又怎么可能會(huì)成功呢？
???????? 其實(shí)按照CAP論文里的內(nèi)容，個(gè)人感覺(jué)論文想表達(dá)的意思是在保證分區(qū)可容忍的分布式系統(tǒng)中，當(dāng)遇到分區(qū)問(wèn)題時(shí)，這個(gè)系統(tǒng)只能在可用性與一致性之間選擇一個(gè)。說(shuō)白了就是通常都是通過(guò)多副本來(lái)保證有幾臺(tái)機(jī)器宕機(jī)也不會(huì)影響服務(wù)，但是副本之間同步策略在宕機(jī)的情況下可能會(huì)導(dǎo)致數(shù)據(jù)不一樣。
????????可如果真的是這么想，其實(shí)就沒(méi)有把單副本的分布式系統(tǒng)考慮進(jìn)來(lái)了，難道只有一個(gè)副本的hdfs就不是分布式嗎？沒(méi)有slave的redis cluster 就不是分布式嗎？
4.2 關(guān)于“CAP”的一家之言
? ? ? ? 筆者通常都是這么理解CAP的，即這三種屬性對(duì)于存儲(chǔ)系統(tǒng)而言（包括非分布式）都不是一種要么有要么沒(méi)有的屬性，應(yīng)該說(shuō)0~100分，不同的系統(tǒng)在這三項(xiàng)上面的得分有高有低。
????????對(duì)于單副本的一致性可以說(shuō)是絕對(duì)的100分，但是完全不能容忍分區(qū)、即P可以說(shuō)是0分；兩個(gè)副本的hdfs跟200個(gè)副本的hdfs相比，兩者的分區(qū)容錯(cuò)性也是不可同日而語(yǔ)的。像HBase這種系統(tǒng)，默認(rèn)情況下發(fā)生宕機(jī)而且region沒(méi)有重新分配的話，就是不會(huì)對(duì)相應(yīng)區(qū)間內(nèi)的數(shù)據(jù)提供讀寫服務(wù)，所以可用性不是太高；cassandra在合適的一致性設(shè)置下，就算發(fā)生某臺(tái)機(jī)器宕機(jī)，仍然還可以從別的地方讀取，只是可能讀的不一樣了。至于一致性、已經(jīng)有很多說(shuō)法了、什么強(qiáng)一致、弱一致、最終一致。
????????所以本人通常都是按如下的雷達(dá)圖來(lái)理解一個(gè)存儲(chǔ)系統(tǒng)的“CAP”屬性：
???????? 灰色的三角表示這個(gè)存儲(chǔ)系統(tǒng)各項(xiàng)都是滿分。像HBase默認(rèn)情況下，可以用紅色三角表示，通過(guò)單臺(tái)機(jī)器對(duì)外提供某一片數(shù)據(jù)的服務(wù)，保證了強(qiáng)一致性（可能一致性還不至于那么滿，畢竟跟單副本的一致性比起來(lái)可能還是要差些）；當(dāng)HBase開啟second replica的時(shí)候就像藍(lán)色三角形那樣，一致性變差了，但是可用性增強(qiáng)了，至于為什么沒(méi)有畫成完全的可用性，也是考慮到掛了兩臺(tái)機(jī)器、即使有second replica也是無(wú)法服務(wù)提供讀寫服務(wù)的；最后就是單機(jī)版的innodb，它就像圖中的黑色三角形一致性可以說(shuō)是絕對(duì)的，但是分區(qū)容錯(cuò)能力完全是0。
???????? izanami為了編寫方便，本人也是參考黑色的三角形實(shí)現(xiàn)的。
5. 總結(jié)
????????如果說(shuō)mr/spark為olap系統(tǒng)帶來(lái)了并行計(jì)算、orc/parquet為olap帶來(lái)了列式存儲(chǔ)、kylin為olap帶來(lái)了預(yù)計(jì)算，那么izanami則為olap帶來(lái)了預(yù)排序（或者叫預(yù)分組）。這也是筆者對(duì)分布式系統(tǒng)（無(wú)論是存儲(chǔ)還是計(jì)算）給出的一份自己的答卷。
????????下面是izanami的git地址，代碼寫的不好，很多地方都很粗糙，甚至可能不用特殊手段調(diào)不通，但是可以參考一下：
????????https://github.com/kencao1994/izanami
