Tair存儲引擎之一Leveldb中資料的存儲思想

1. Tair ldb簡單介紹

1.1 tair非持久化/持久化存儲引擎

tair 是淘寶自己開發的一個分布式 key/value 存儲引擎. tair 分為持久化和非持久化兩種使用方式. 非持久化的 tair 可以看成是一個分布式緩存. 持久化的 tair 将資料存放于磁盤中. 在最新版本的tair trunk中目前實作了以下4種存儲引擎。

非持久化：mdb

持久化：fdb、kdb和 ldb
      

分别基于四種開源的key/value資料庫：Memcached、Firebird、Kyoto Cabinet和LevelDB。其中memcached和Firebird是關系型存儲資料庫，而Kyoto Cabinet和LevelDB是Nosql資料庫。

這裡我研究的是Google開源的快速輕量級的單機KV存儲引擎leveldb的實作方式。

1.2 leveldb簡單介紹

leveldb的基本特性：

• 提供key/value支援，key和value是任意的位元組數組
• 資料按key内部排序
• 調用者可以提供自定義的比較函數修改排序規則
• 基本的接口有 Put(key,value), Get(key), Delete(key).
• 支援批量修改（原子操作）
• 使用者可以建立臨時snapshot來獲得資料的一個視圖
• 支援正向和反向周遊資料
• 使用Snappy compression library對資料進行壓縮
• 外部操作（例如檔案系統操作）通過虛接口傳遞使得使用者可以自定義與作業系統的互動

限制：

• 非SQL資料庫，是以不支援關系資料模型，也就不支援SQL語句查詢以及索引查詢
• 一次隻能有一個程序（可能是多線程的）通路資料庫
• 沒有内置用戶端-伺服器的支援，有這個需求的應用程式必須自己實作封裝

2.  leveldb中資料的存儲結構—LSM

說到存儲引擎我立刻想到MySQL的兩大常用存儲引擎myisam和innodb，關系型資料庫的資料存儲在邏輯的表空間中，而資料庫索引一般都是用的B/B+樹系列，包括MySQL及NoSQL中的MongoDB。那為什麼在磁盤中要使用B+樹來進行檔案存儲呢？首先磁盤本身是一個順序讀寫快，随機讀寫慢的系統，磁盤的性能主要受限于磁盤的尋道時間，那麼如果想高效的從磁盤中找到資料，就需要減少尋道次數，也就是盡量減少磁盤的IO次數，而磁盤IO次數又取決于資料在磁盤上的組織方式。B+樹是一種專門針對磁盤存儲而優化的N叉排序樹，以樹節點為機關存儲在磁盤中，從根開始查找所需資料所在的節點編号和磁盤位置，将其加載到記憶體中然後繼續查找，直到找到所需的資料。B+樹的存儲方式使得具有良好的查找、插入和修改的性能，但如果有大量的更新插入删除等綜合寫入，最後會因為需要循環利用磁盤塊而出現較多的随機IO，大量時間消耗在磁盤尋道時間上，如果是一個運作時間很長的B+樹，那麼幾乎所有的請求，都是随機IO。因為磁盤塊本身已經不再連續，很難保證可以順序讀取。這是B+樹在磁盤結構中最大的問題。

那麼如何能夠解決這個問題呢？

目前主流的思路有以下幾種

（1）放棄部分讀性能，使用更加面向順序寫的樹的結構來提升寫性能。

     這個類别裡面，從資料結構來說，就我所知并比較流行的是兩類，

     一類是COLA（Cache-Oblivious Look ahead Array），代表應用是tokuDB。

     一類是LSM tree(Log-structured merge Tree)或SSTable，代表的應用有Cassandra、HBase、levelDB 及衆多類BigTable存儲。

（2）使用ssd，讓尋道成為往事。
      

Leveldb的資料存儲方式采用的是LSM(log-structured-merge)的實作方法，簡單來說就是将原來的直接維護索引樹變為增量寫的方式，這樣能夠保證對磁盤的操作是順序的。具體的LSM實作可以看”The log-structured merge-tree“這篇論文。Log-Structured的思想最早由 Rosenblum和Ousterhout于1992年在研究日志結構的檔案系統時提出。他們将整個磁盤就看做是一個日志，在日志中存放永久性資料及其索引，每次都添加到日志的末尾；通過将很多小檔案的存取轉換為連續的大批量傳輸，使得對于檔案系統的大多數存取都是順序性的，進而提高磁盤帶寬使用率，故障恢複速度快。 O'Neil等人受到這種思想的啟發，借鑒了Log不斷追加（而不是修改）的特點，結合B-tree的資料結構，提出了一種延遲更新，批量寫入硬碟的資料結構LSM-tree及其算法。LSM-tree努力地在讀和寫兩方面尋找一個平衡點以最小化系統的存取性能的開銷，特别适用于插入頻率遠大于查詢頻率的應用場景。

LSM樹可以看作是一個N階合并樹。資料寫操作（包括插入、修改、删除）都在記憶體中進行，并且都會建立一個新記錄（修改會記錄新的資料值，而删除會記錄一個删除标志），這些資料在記憶體中仍然還是一棵排序樹，當資料量超過設定的記憶體門檻值後，會将這棵排序樹和磁盤上最新的排序樹合并。當這棵排序樹的資料量也超過設定門檻值後，和磁盤上下一級的排序樹合并。合并過程中，會用最新更新的資料覆寫舊的資料（或者記錄為不同版本）。

在需要進行讀操作時，總是從記憶體中的排序樹開始搜尋，如果沒有找到，就從磁盤上的排序樹順序查找。

在LSM樹上進行一次資料更新不需要磁盤通路，在記憶體即可完成，速度遠快于B+樹。當資料通路以寫操作為主，而讀操作則集中在最近寫入的資料上時，使用LSM樹可以極大程度地減少磁盤的通路次數，加快通路速度。

3. 分析Get/Put/Delete和對應Prefix系列接口的資料在leveldb中存儲特點

在了解LSM後，需要知道基于LSM結構的存儲引擎的資料有什麼存儲特點，下面簡單總結幾點。

（1）leveldb中各個存儲檔案是分層的，新插入的值放在記憶體表中，稱為memtable（通過skiplist實作），該表寫滿時變為immutable table，并建立新的memtable接收寫操作，而immutable table是不可變更的，會通過Compact過程寫入level0，其中的資料被組織成sstable的資料檔案，是以，同時最多會存在兩個memtable（正在寫的memtable和immutable memtable）。level0的檔案會通過背景的Compact過程寫入level1，level1的檔案又會寫入level2，依次類推，這是”Merge Dump“的流程。

（2）leveldb在寫操作時隻是單純的在檔案末尾增加一條記錄而不會改動原來的資料，更新key直接插入一條新的key/value資料（即key已經存在），而删除操作可以看成插入一條value為空的資料，為了區分真實kv資料和删除操作的mock資料，使用ValueType來辨別：

enum ValueType { 
    kTypeDeletion = 0x0, 
    kTypeValue = 0x1 
};
           

除此之外，leveldb每次更新（Put/Delete)操作都擁有一個版本，由SequnceNumber來辨別，整個db有一個全局值儲存着目前使用到的SequnceNumber。SequnceNumber在leveldb有重要的地位，key的排序，compact以及snapshot都依賴于它。leveldb内部按照key非遞減，SequnceNumber非遞增，ValueType非遞增排序，這樣查詢時便可以找到key對應的最新值，如果type位kTypeDeletion則不存在。

（3）考慮節約空間，leveldb對key的存儲進行字首壓縮後再寫入sstable，每個entry中會記錄key與前一個key字首相同的位元組（shared_bytes）以及自己獨有的位元組（unshared_bytes）。讀取時，對block進行周遊，每個key根據前一個key以及shared_bytes/unshared_bytes可以構造出來。

（4）最重要的一點：由于tair是根據hash分區的，而prefix系列的接口是根據prefixkey去hash的。是以能確定擁有相同prefix的key在同一台伺服器上。

4. 簡單總結

首先講述了leveldb的基本特性，然後簡單講解了leveldb存儲結構的來源LSM的基本思想和适用場景，最後總結了幾點leveldb中存儲資料的特點，實際的存儲結構較複雜，有記憶體存儲結構和持久化存儲結構。下一步繼續探索LevelDB的存儲過程。

5. 參考資料

（1）tair官網介紹

（2）leveldb官網介紹

（3）日志結構的合并樹 The Log-Structured Merge-Tree

（4）從LSM-Tree、COLA-Tree談到StackOverflow、OSQA

（5）為什麼檔案存儲要選用B 樹這樣的資料結構?