使用 LSM-Tree 思想基于.NET 6.0 C# 寫個 KV 數據庫（案例版）

為啥要實現一個數據庫

大概2018年的時候，就萌生了想自己研發一個數據庫的想法了，雖然，造輪子可能不如現有各種產品的強大，但是，能造者寥寥無幾，而且，造數據庫的書更是少的可憐，當然，不僅僅是造數據庫的書少，而是各種各樣高級的產品的創造級的書都少。

雖然，現在有各種各樣的開源，但是，像我這種底子薄的，就不能輕易的了解，這些框架的架構設計，以及相關的理念，純看代碼，沒個長時間，也不容易了解其存在的含義。

恰逢其時，前一個月看到【癡者工良】大佬的一篇《【萬字長文】使用 LSM Tree 思想實現一個 KV 數據庫》文章給我很大觸動，讓我停滯的心，又砰砰跳了起來，雖然大佬是用GO語言實現的，但是，對我來講，語言還是個問題么，只要技術思想一致，我完全可以用C#實現啊，也算是對【癡者工良】大佬的致敬，我這邊緊隨其后。

當然，我自己對數據的研究也是耗時很久，畢竟，研究什么都要先從原理開始研究，從谷歌三個論文《GFS，MapReduce，BigTable》開始，但是，論文，畢竟是論文，讀不懂啊，又看了網上各種大佬的文章，還是很蒙蔽，實現的時候，也沒人交流，導致各種流產。

有時候，自己實現某個產品框架的時候，總是在想，為啥BUG都讓我處理一個遍哦，后來一想，你自己從新做個產品，也不能借鑒技術要點，那還不是從零開始，自然一一遇到BUG。

下圖就是，我在想做數據庫后，自己寫寫畫畫，但是，實際做的時候，邏輯表現總沒有那么好，當然，這個是關系型數據庫，難度比較高，下面可以看看之前的手稿，都是有想法了就畫一下。

實現難度有點高，現在這個實現是KV數據庫，算是列式數據庫了，大名鼎鼎的HBase，底層數據庫引擎就是LSM-Tree的技術思想。

LSM-Tree 是啥子

LSM-Tree 英文全稱是 Log Structured Merge Tree （中文：日志結構合并樹），是一種分層，有序，面向磁盤的數據結構，其核心思想是充分了利用了，磁盤批量的順序寫要遠比隨機寫性能高的技術特點，來實現高寫入吞吐量的存儲系統的核心。

具體的說，原理就是針對硬盤，盡量追加數據，而不是隨機寫數據，追加速度要比隨機寫的速度快，這種結構適合寫多讀少的場景，所以，LSM-Tree被設計來提供比傳統的B+樹或者ISAM更好的寫操作吞吐量，通過消去隨機的本地更新操作來達到這個性能目標。

相關技術產品有Hbase、Cassandra、Leveldb、RocksDB、MongoDB、TiDB、Dynamodb、Cassandra 、Bookkeeper、SQLite 等

所以，LSM-Tree的核心就是追加數據，而不是修改數據。

LSM-Tree 架構分析

其實這個圖已經表達了整體的設計思想了，主體其實就圍繞著紅色的線與黑色的線，兩部分展開的，其中紅色是寫，黑色是讀，箭頭表示數據的方向，數字表示邏輯順序。

整體包含大致三個部分，數據庫操作部分（主要為讀和寫），內存部分(緩存表和不變緩存表)以及硬盤部分(WAL Log 和 SSTable)，這三個部分。

先對關鍵詞解釋一下

MemoryTable

內存表，一種臨時緩存性質的數據表，可以用二叉排序樹實現，也可以用字典來實現，我這邊是用字典實現的。

WAL Log

WAL 英文 (Write Ahead LOG) 是一種預寫日志，用于在系統故障期間提供數據的持久性，這意味著當寫入請求到來時，數據首先添加到 WAL 文件（有時稱為日志）并刷新到更新內存數據結構之前的磁盤。

如果用過Mysql，應該就知道BinLog文件，它們是一個道理，先寫入到WAL Log里，記錄起來，然后，寫入到內存表，如果電腦突然死機了，內存里的東西肯定丟失了，那么，下一次重啟，就從WAL Log 記錄表里，從新恢復數據到當前的數據狀態。

Immutable MemoryTable

Immutable(不變的)，相對于內存表來講，它是不能寫入新數據，是只讀的。

SSTable

SSTable 英文 (Sorted Strings Table) ，有序字符串表，就是有序的字符串列表，使用它的好處是可以實現稀疏索引的效果，而且，合并文件更為簡單方便，我要查某個Key，但是，它是基于某個有序Key之間的，可以直接去文件里查，而不用都保存到內存里。

這里我是用哈希表實現的，我認為浪費一點內存是值得的，畢竟為了快，浪費點空間是值得的，所以，目前是全索引加載到內存，而數據保存在SSTable里，當然，如果是為了更好的設計，也可以自己去實現有序表來用二分查找。

我這個方便實現了之后，內存會加載大量的索引，相對來講是快的，但是，內存會大一些，空間換時間的方案。

下面開始具體的流程分析

LSM-Tree Write 路線分析

看下圖，數據寫入分析

跟著紅色線走，關注我從此不迷路。

LSM-Tree Write 路線分析第一步

第一步，只有兩個部分需要注意的部分，分別是內存表和WAL.Log

寫入數據先存儲內存表，是為了快速的存儲到數據庫數據。

存儲到WAL.Log，是為了防止異常情況下數據丟失。

正常情況下，寫入到WAL.Log一份，然后，會寫入到內存一份。

當程序崩潰了，或者，電腦斷電異常了，重復服務后，就會先加載WAL.Log，按照從頭到尾的順序，恢復數據到內存表，直至結束，恢復到WAL.Log最后的狀態，也就是內存表數據最后的狀態。

注

這里要注意的是，當后面的不變表(Immutable MemoryTable)寫入到SSTable的時候，會清空WAL.Log文件，并同時把內存表的數據直接寫入到WAL.log表中。

LSM-Tree Write 路線分析第二步

第二步，比較簡單，就是在內存表count大于一定數的時候，就新增一個內存表的同時，把它變為 Immutable MemoryTable （不變表），等待SSTable的落盤操作，這個時候，Immutable MemoryTable會有多個表存在。

LSM-Tree Write 路線分析第三步

第三步，就是數據庫會定時檢查 Immutable MemoryTable （不變表）不變表是否存在，如果存在，就會直接落盤為SSTable表，不論當前內存里有多少 Immutable MemoryTable （不變表）。

默認從內存落盤的第一級SSTable都是 Level 0，然后，內置了當前的時間，所以是兩級排序，先分級別，然后，分時間。

LSM-Tree Write 路線分析第四步

第四步，其實就是段合并或者級合并壓縮，就是判斷 level0 這一個級別的所有 SSTable文件(SSTable0，SSTable1，SSTable2)，判斷它們的總大小或者判斷它們的總個數來判斷，它們需不需要進行合并。

其中 Level 0 的大小如果是10M，那么 ,Level 1的大小就是 100M，依此類推。

當Level0的所有SSTable文件超過了10M，或者限定的大小，就會從按照WAL.Log的順序思路，重新合并為一個大文件，先老數據再新數據這樣遍歷合并，如果已經刪除的，則直接剔除在外，只保留最新狀態。

如果 Level1的（全部SSTable）大小超過100M，那么，觸發Level1的收縮動作，執行過程跟Level0一樣的操作，只是級別不同。

這樣壓縮的好處是使數據盡可能讓文件量盡可能的少，畢竟，文件多，管理就不是很方便。

至此，寫入路線已經分析完畢

注

查詢的時候，要先新數據，后舊數據，而分段合并壓縮的時候，要先老數據墊底，新數據刷狀態，這個是實現的時候需要注意的點。

LSM-Tree Read 路線分析

這就是數據的查找過程，跟著黑線和數字標記，很容易就看到了其訪問順序

1. MemoryTable (內存表)
2. Immutable MemoryTable (不變表)
3. Level 0-N (SSTableN-SSTable1-SSTable0) (有序字符串表)

基本上來說就這三部分，而級別表是從0級開始往下找的，而每級內部的SSTable是從新到舊開始找的，找到就返回，不論key是刪除還是正常的狀態。

LSM-Tree 架構分析與實現

核心思想：

其實就是一個時間有序的記錄表，會記錄每個操作，相當于是一個消息隊列，記錄一系列的動作，然后，回放動作，就獲取到了最新的數據狀態，也類似CQRS中的Event Store（事件存儲），概念是相同的，那么實現的時候，就明白是一個什么本質。

Wal.log和SSTable，都是為了保證數據能落地持久化不丟失，而MemoryTable，偏向臨時緩存的概念，當然，也有為了加速訪問的作用。

所以，從這幾個點來看，就分為了以下幾個大的對象

1. Database 數據庫( 起到對Wal.log，SSTable和MemoryTable 的管理職責)
2. Wal.log(記錄臨時數據日志)
3. MemoryTable(記錄數據到內存，同時為數據庫查找功能提供接口服務)
4. SSTable(管理SSTable文件，并提供SSTable的查詢功能)

所以，針對這幾個對象來設計相關的類接口設計。

KeyValue (具體數據的結構)

設計的時候，要先設計實際數據的結構，我是這樣設計的

主要有三個主要的信息，key, DataValue，Deleted ，其中DataValue是Byte[]類型的，我這邊寫入到文件里的話，是直接寫入的。

/// <summary>
/// 數據信息 kv
/// </summary>
public class KeyValue
{
    public string Key { get; set; }
    public byte[] DataValue { get; set; }
    public bool Deleted { get; set; }
    private object Value;
    public KeyValue() { }
    public KeyValue(string key, object value, bool Deleted = false)
    {
        Key = key;
        Value = value;
        DataValue = value.AsBytes();
        this.Deleted = Deleted;
    }
    public KeyValue(string key, byte[] dataValue, bool deleted)
    {
        Key = key;
        DataValue = dataValue;
        Deleted = deleted;
    }
    /// <summary>
    /// 是否存在有效數據,非刪除狀態
    /// </summary>
    /// <returns></returns>
    public bool IsSuccess()
    {
        return !Deleted || DataValue != null;
    }
    /// <summary>
    /// 值存不存在，無論刪除還是不刪除
    /// </summary>
    /// <returns></returns>
    public bool IsExist()
    {
        if (DataValue != null && !Deleted || DataValue == null && Deleted)
        {
            return true;
        }
        return false;
    }
    public T Get<T>() where T : class
    {
        if (Value == null)
        {
            Value = DataValue.AsObject<T>();
        }
        return (T)Value;
    }
    public static KeyValue Null = new KeyValue() { DataValue = null };
}

IDataBase (數據庫接口)

主要對外交互用的主體類，數據庫類，增刪改查接口，都用 get,set,delete 表現。

/// <summary>
/// 數據庫接口
/// </summary>
public interface IDataBase : IDisposable
{
    /// <summary>
    /// 數據庫配置
    /// </summary>
    IDataBaseConfig DataBaseConfig { get; }
    /// <summary>
    /// 獲取數據
    /// </summary>
    KeyValue Get(string key);
    /// <summary>
    /// 保存數據(或者更新數據)
    /// </summary>
    bool Set(KeyValue keyValue);
    /// <summary>
    /// 保存數據(或者更新數據)
    /// </summary>
    bool Set(string key, object value);
    /// <summary>
    /// 獲取全部key
    /// </summary>
    List<string> GetKeys();
    /// <summary>
    /// 刪除指定數據，并返回存在的數據
    /// </summary>
    KeyValue DeleteAndGet(string key);
    /// <summary>
    /// 刪除數據
    /// </summary>
    void Delete(string key);
    /// <summary>
    /// 定時檢查
    /// </summary>
    void Check(object state);
    /// <summary>
    /// 清除數據庫所有數據
    /// </summary>
    void Clear();
}

IDataBase.Check (定期檢查)

這個是定期檢查Immutable MemoryTable(不變表)的定時操作，主要依賴IDataBaseConfig.CheckInterval 參數配置其觸發間隔。

它的職責是檢查內存表和檢查SSTable 是否觸發分段合并壓縮的操作。

public void Check(object state)
{
    //Log.Info($"定時心跳檢查!");
    if (IsProcess)
    {
        return;
    }
    if (ClearState)
    {
        return;
    }
    try
    {
        Stopwatch stopwatch = Stopwatch.StartNew();
        IsProcess = true;
        checkMemory();
        TableManage.Check();
        stopwatch.Stop();
        GC.Collect();
        Log.Info($"定時心跳處理耗時:{stopwatch.ElapsedMilliseconds}毫秒");
    }
    finally
    {
        IsProcess = false;
    }
}

IDataBaseConfig (數據庫配置文件)

數據庫的配置文件，數據庫保存在哪里，以及生成SSTable時的閾值配置，還有檢測間隔時間配置。

/// <summary>
/// 數據庫相關配置
/// </summary>
public interface IDataBaseConfig
{
    /// <summary>
    /// 數據庫數據目錄
    /// </summary>
    public string DataDir { get; set; }
    /// <summary>
    /// 0 層的 所有 SsTable 文件大小總和的最大值，單位 MB，超過此值，該層 SsTable 將會被壓縮到下一層
    /// 每層數據大小是上層的N倍
    /// </summary>
    public int Level0Size { get; set; }
    /// <summary>
    /// 層與層之間的倍數
    /// </summary>
    public int LevelMultiple { get; set; }
    /// <summary>
    /// 每層數量閾值
    /// </summary>
    public int LevelCount { get; set; }
    /// <summary>
    /// 內存表的 kv 最大數量，超出這個閾值，內存表將會被保存到 SsTable 中
    /// </summary>
    public int MemoryTableCount { get; set; }
    /// <summary>
    /// 壓縮內存、文件的時間間隔，多久進行一次檢查工作
    /// </summary>
    public int CheckInterval { get; set; }
}

IMemoryTable (內存表)

這個表其實算是對內存數據的管理表了，主要是管理 MemoryTableValue 對象，這個對象是通過哈希字典來實現的，當然，你也可以選擇其他結構，比如有序二叉樹等。

/// <summary>
/// 內存表(排序樹，二叉樹)
/// </summary>
public interface IMemoryTable : IDisposable
{
    IDataBaseConfig DataBaseConfig { get; }
    /// <summary>
    /// 獲取總數
    /// </summary>
    int GetCount();
    /// <summary>
    /// 搜索(從新到舊，從大到小)
    /// </summary>
    KeyValue Search(string key);
    /// <summary>
    /// 設置新值
    /// </summary>
    void Set(KeyValue keyValue);
    /// <summary>
    /// 刪除key
    /// </summary>
    void Delete(KeyValue keyValue);
    /// <summary>
    /// 獲取所有 key 數據列表
    /// </summary>
    /// <returns></returns>
    IList<string> GetKeys();
    /// <summary>
    /// 獲取所有數據
    /// </summary>
    /// <returns></returns>
    (List<KeyValue> keyValues, List<long> times) GetKeyValues(bool Immutable);
    /// <summary>
    /// 獲取不變表的數量
    /// </summary>
    /// <returns></returns>
    int GetImmutableTableCount();
    /// <summary>
    /// 開始交換
    /// </summary>
    void Swap(List<long> times);
    /// <summary>
    /// 清空全部數據
    /// </summary>
    void Clear();
}

MemoryTableValue (對象的實現)

主要是通過 Immutable 這個屬性實現了對不可變內存表的標記，具體實現是通過判斷 IDataBaseConfig.MemoryTableCount (內存表的 kv 最大數量)來實現標記的。

public class MemoryTableValue : IDisposable
{
    public long Time { get; set; } = IDHelper.MarkID();
    /// <summary>
    /// 是否是不可變
    /// </summary>
    public bool Immutable { get; set; } = false;
    /// <summary>
    /// 數據
    /// </summary>
    public Dictionary<string, KeyValue> Dic { get; set; } = new();
    public void Dispose()
    {
        Dic.Clear();
    }
    public override string ToString()
    {
        return $"Time {Time} Immutable：{Immutable}";
    }
}

什么時機表狀態轉換為 Immutable MemoryTable(不變表)的

我這里實現的是從Set的入口處實現的，如果數目大于IDataBaseConfig.MemoryTableCount (內存表的 kv 最大數量)就改變其狀態

public void Check()
{
    if (CurrentMemoryTable.Dic.Count() >= DataBaseConfig.MemoryTableCount)
    {
        var value = new MemoryTableValue();
        dics.Add(value.Time, value);
        CurrentMemoryTable.Immutable = true;
    }
}

IWalLog

wallog，就簡單許多，就直接把KeyValue 寫入到文件即可，為了保證WalLog的持續寫，所以，對象內部保留了此文件的句柄。而SSTable，就沒有必要了，隨時讀。

/// <summary>
/// 日志
/// </summary>
public interface IWalLog : IDisposable
{
    /// <summary>
    /// 數據庫配置
    /// </summary>
    IDataBaseConfig DataBaseConfig { get; }
    /// <summary>
    /// 加載Wal日志到內存表
    /// </summary>
    /// <returns></returns>
    IMemoryTable LoadToMemory();
    /// <summary>
    /// 寫日志
    /// </summary>
    void Write(KeyValue data);
    /// <summary>
    /// 寫日志
    /// </summary>
    void Write(List<KeyValue> data);
    /// <summary>
    /// 重置日志文件
    /// </summary>
    void Reset();
}

ITableManage (SSTable表的管理)

為了更好的管理SSTable，需要有一個管理層，這個接口就是它的管理層，其中SSTable會有多層，每次用 Level+時間戳+db 作為文件名，用作外部識別。

/// <summary>
/// 表管理項
/// </summary>
public interface ITableManage : IDisposable
{
    IDataBaseConfig DataBaseConfig { get; }
    /// <summary>
    /// 搜索(從新到老,從大到小)
    /// </summary>
    KeyValue Search(string key);
    /// <summary>
    /// 獲取全部key
    /// </summary>
    List<string> GetKeys();
    /// <summary>
    /// 檢查數據庫文件，如果文件無效數據太多，就會觸發整合文件
    /// </summary>
    void Check();
    /// <summary>
    /// 創建一個新Table
    /// </summary>
    void CreateNewTable(List<KeyValue> values, int Level = 0);
    /// <summary>
    /// 清理某個級別的數據
    /// </summary>
    /// <param name="Level"></param>
    public void Remove(int Level);
    /// <summary>
    /// 清除數據
    /// </summary>
    public void Clear();
}

ISSTable(SSTable 文件)

SSTable的內容管理，應該就是LSM-Tree的核心了，數據的合并，以及數據的查詢，寫入，加載，都是偏底層的操作，需要一丟丟的數據庫知識。

/// <summary>
/// 文件信息表 （存儲在IO中）
/// 元數據 | 索引列表 | 數據區(數據修改只會新增，并修改索引列表數據) 
/// </summary>
public interface ISSTable : IDisposable
{
    /// <summary>
    /// 數據地址
    /// </summary>
    public string TableFilePath();
    /// <summary>
    /// 重寫文件
    /// </summary>
    public void Write(List<KeyValue> values, int Level = 0);
    /// <summary>
    /// 數據位置
    /// </summary>
    public Dictionary<string, DataPosition> DataPositions { get; }
    /// <summary>
    /// 獲取總數
    /// </summary>
    /// <returns></returns>
    public int Count { get; }
    /// <summary>
    /// 元數據
    /// </summary>
    public ITableMetaInfo FileTableMetaInfo { get; }
    /// <summary>
    /// 查詢數據
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public KeyValue Search(string key);
    /// <summary>
    /// 有序的key列表
    /// </summary>
    /// <returns></returns>
    public List<string> SortIndexs();
    /// <summary>
    /// 獲取位置
    /// </summary>
    DataPosition GetDataPosition(string key);
    /// <summary>
    /// 讀取某個位置的值
    /// </summary>
    public object ReadValue(DataPosition position);
    /// <summary>
    /// 加載所有數據
    /// </summary>
    /// <returns></returns>
    public List<KeyValue> ReadAll(bool incloudDeleted = true);
    /// <summary>
    /// 獲取所有keys
    /// </summary>
    /// <returns></returns>
    public List<string> GetKeys();
    /// <summary>
    /// 獲取表名
    /// </summary>
    /// <returns></returns>
    public long FileTableName();
    /// <summary>
    /// 文件的大小
    /// </summary>
    /// <returns></returns>
    public long FileBytes { get; }
    /// <summary>
    /// 獲取級別
    /// </summary>
    public int GetLevel();
}

IDataPosition(數據稀疏索引算是)

方便數據查詢方便和方便從SSTable里讀取到實際的數據內容。

/// <summary>
/// 數據的位置
/// </summary>
public interface IDataPosition
{
    /// <summary>
    /// 索引起始位置
    /// </summary>
    public long IndexStart { get; set; }
    /// <summary>
    /// 開始地址
    /// </summary>
    public long Start { get; set; }
    /// <summary>
    /// 數據長度
    /// </summary>
    public long Length { get; set; }
    /// <summary>
    /// key的長度
    /// </summary>
    public long KeyLength { get; set; }
    /// <summary>
    /// 是否已經刪除
    /// </summary>
    public bool Deleted { get; set; }
    public byte[] GetBytes();
}