不吹不黑的為菊廠的應用運維管理AOM點個贊。Why？
某菊廠應用運維管理工具AOM每天處理着億級條資料，這麼多資料是怎麼存儲的呢？
說到資料存儲就會想到關系型資料庫，比如mysql，oracle，sybase。關系型資料庫有自己的優勢，資料強一緻性，支援事務，通用，技術成熟。但是對于大批量資料的存儲和查詢就稍顯吃力，畢竟AOM每秒的寫入資料至少都是上萬條，甚至是十幾萬條，随着系統規模增長，資料庫的擴容也成為新的瓶頸。
AOM的資料存儲系統使用的是非關系型資料庫-----cassandra,相比關系型資料庫，cassandra擁有高并發，大資料下讀寫能力強，支援分布式，易擴充等優點，目前也有最緻命的缺點，不支援事務，不過對于事務我們可以通過zk/etcd等其他元件協助完成。
對于關系型資料庫相比非關系型資料庫為什麼會有這麼大的差異，這個就得從兩者的架構上來講了，下面編者以mysql和cassandra進行對比分析。
不管是mysql還是cassandra，最終資料的存儲都要落盤，我們先來看下磁盤的寫入原理：
磁盤的基本元件可分為以下幾部分：磁頭，盤片，盤面，磁道，柱面，扇區等。
盤片被劃分成一系列同心環，圓心是盤片中心，每個同心環叫做一個磁道，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段，每個段叫做一個扇區，每個扇區是磁盤的最小存儲單元。當需要從磁盤讀取資料時，系統會将資料邏輯位址傳給磁盤，磁盤的控制電路按照尋址邏輯将邏輯位址翻譯成實體位址，即确定要讀的資料在哪個磁道，哪個扇區。為了讀取這個扇區的資料，需要将磁頭放到這個扇區上方，為了實作這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然後磁盤 旋轉将目标扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
即一次訪盤請求（讀/寫）完成過程由三個動作組成：
1）尋道（時間）：磁頭移動定位到指定磁道
2）旋轉延遲（時間）：等待指定扇區從磁頭下旋轉經過
3）資料傳輸（時間）：資料在磁盤與記憶體之間的實際傳輸
大家應該有過類似的經曆，進行資料拷貝時，檔案個數越少，單個檔案越大，拷貝的速率越快，反之檔案個數多，單個檔案小，拷貝的速率越慢，這其中的原因就是因為在拷貝小檔案時，系統的耗時基本都耗費在尋址上了。Cassandra相比mysql有更高的寫入能力，就是因為cassandra采用了更高效的寫入機制，該機制大大縮短了磁盤的尋址時間（準确來講應該是尋址次數）。
我們先來看下Mysql(InnoDB)的索引原理, InnoDB的索引采用B+樹，其資料結構如下所示：
所有的資料都存儲在葉子節點，葉子節點之間都有指針，這是為了做範圍周遊。B+樹的優勢在于快速索引，B+樹的層高基本都在2~3層，也就意味着一次資料查找隻需要2~3次IO操作。而且每次的單條資料都非常穩定，耗時和查找次數都差不多。B+樹最大的性能問題是會産生大量的随機IO，随着資料的插入，葉子節點會慢慢分裂，邏輯上連續的節點實體上确不連續，甚至相隔甚遠，順序周遊的時候，會産生大量的随機IO操作。這正如大家熟知的ArrayList和LinkedList，ArrayList在記憶體中是一塊連續的記憶體，通路的時候順序通路，LinkedList是多個記憶體塊通過指針串聯起來的，通路的時候必須先通過指針擷取下一個記憶體塊的位址，然後再通過位址通路，是以ArrayList的通路遠遠高于LinkedList。B+樹的葉子節點就類似一個LinkedList，随着葉子節點的分裂，在做順序檢索時，跨葉子節點的通路往往需要先找到下一個葉子節點的位址（磁盤尋址），然後才能通路到具體的葉子節點。
B+樹的順序檢索會産生大量的随機IO，B+樹的寫入同樣會産生類似的問題，比如上圖B+樹中的9和86，它們所屬的葉子節點在磁盤上相隔甚遠，資料插入時就會産生兩次随機寫入。當大批量資料寫入時，随機IO操作的次數也就更多。
如下是一張随機讀寫和順序讀寫的性能比對圖：
從上圖可以直覺的感受到随機讀寫與順序讀寫的差異，這兩者完全不在一個量級。用過kafka和HDFS的開發者就會發現kafka和HDFS的磁盤IO使用率非常高，有時甚至接近磁盤的最大寫入速率，這個就是因為kafka和HDFS是基于檔案的順序寫入（當然還有其他技術）。從以上分析來看，磁盤的随機讀取/寫入是影響mysql順序檢索和批量寫入的最大因素，那我們有沒有辦法減少這種随機寫入呢，此時LSM-Tree（Log-Structured Merge-Tree）呼之欲出。
2006年，google發表了BigTable的論文。BigTable的資料結構就采用了LSM（http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.2782&rep=rep1&type=pdf）。目前LSM被很多資料庫作為存儲結構，比如HBase，Cassandra，LevelDB。LSM抛棄了大多數資料庫使用的傳統檔案組織方法，通過減少更新/寫入操作帶來的随機操作次數來提高資料的寫入能力。
LSM Tree的核心思路其實非常簡單，就是假定記憶體足夠大，是以不需要每次有資料更新就必須将資料寫入到磁盤中，而可以先将最新的資料駐留在磁盤中，等到積累到一定數目之後，再使用歸并排序的方式将記憶體内的資料合并追加到磁盤隊尾(因為所有待排序的樹都是有序的，可以通過合并排序的方式快速合并到一起)。
LSM的核心思路可以分為兩部分：
①、資料先寫入記憶體
②、将記憶體中的資料排序後追加到磁盤隊尾。
LSM由兩個或兩個以上的存儲結構組成。最簡單的LSM由兩部分組成，一部分常駐記憶體，稱為C0；另一部分存儲在硬碟上，稱為C1。
資料寫入時，先記錄到本地的記錄檔檔案（HLog或CommitLog）,為将來做資料恢複使用。然後将資料寫入到C0中，由于C0使用的是記憶體，是以插入性能遠遠高于磁盤寫入。當C0的節點數目超過一定門檻值時，會将C0中的資料進行一次排序，然後追加到C1樹中。
多部件的LSM就是包含多個存儲結構：
随着資料規模增加，C0中的資料超過門檻值後就會往磁盤中寫入一個新的file,這樣磁盤中的樹（file）會越來越多。當較小的Ci-1個數超過一定門檻值的時候，會進行Ci-1和Ci的合并。合并是為了減少整個C樹的個數，加快搜尋速度。
資料查詢的時候，會按照樹的生成時間按照從新到舊的順序逐個周遊每個C樹，即C0,C1,C2….Ck。為什麼要按照時間順序從最近往之前周遊呢，這就是LSM的另一個巧妙點（更新/删除）。
LSM的更新和删除操作都是往C0上新增一條記錄，通過新記錄+标記的方式完成，是以在周遊的時候必須按照時間順序進行周遊，這樣就可以保證資料更新和删除的正确性，同時保證了資料的順序寫入。目前LSM在進行C樹合并時，會對删除和更新記錄進行合并。
我們來看下HBase的整個架構圖：
HBase是基于HDFS之上采用LSM結構做的資料存儲。HBase的主要部件可以分為如下幾類：
storeFile:小檔案，不可編輯。即寫入到磁盤中的C樹。
Hlog:LSM中用于記錄寫入記錄的記錄檔，為了将來做資料恢複使用，畢竟C0中的資料是在記憶體中存儲，當HBase當機後，記憶體中的資料就會丢失，此時需要從Hlog中恢複。
Memstore:即C0樹。至此，LSM和B+樹的對比也就講完了。