文章有點長，耐心看完應該可以懂實際原理到底是啥子。

這是一個KV數據庫的C#實現，目前用.NET 6.0實現的，目前算是屬于雛形，骨架都已經完備，畢竟剛完工不到一星期。

當然，這個其實也算是NoSQL的雛形，有助于深入了解相關數據庫的內部原理概念，也有助于實際入門。

適合對數據庫原理以及實現感興趣的朋友們。

整體代碼，大概1500行，核心代碼大概500行。

為啥要實現一個數據庫

大概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();
}

數據結構分析

內部表的結構就不用說了，很簡單，就是一個哈希字典，而有兩個結構是要具體分析的，那就是 WALLog和SSTable文件。

WALLog 結構分析

這個圖橫向不好畫，我畫成豎向了，WalLog里面存儲的就是時間序的KeyValue數據，當它加載到Memory Table的時候，其實就是按照我所標的數字順序依次疊加到最后的狀態的。

同理，SSTable 數據分段合并壓縮的時候，其實是跟這個一個原理的。

SSTable 結構分析

SSTable，它本身是一個文件名字大致如下:

0_16586442986880000.db

格式為層級_時間戳.db 這樣的方式搞的命名規則，為此我還搞了一個生成時間序不重復 ID的簡單算法。

SSTable 數據區

數據區就很簡單，把KeyValue.DataValue直接ToJson 就可以了，然后，直接寫文件。

SSTable 稀疏索引區

這個區是按照與數據區對應的key的順序寫入的，主要是把DataValue對應的開始地址和結束地址放入到這個數據區了，另外把key也寫入進去了。

好處是為了，當此SSTable加載索引(IDataPosition)到內存，省的把數據區的內容也加載進去，查找就方便許多，這也是索引的作用。

元數據區

這個按照協議來講，屬于協議頭，但是為啥放最后面呢，其實是為了計算方便，這也算是一個小妙招。

其中不僅包含了數據區的開始和結束，稀疏索引區的開始和結束，還包含了，此SSTable的版本和創建時間，以及當前SSTable所在的級別。

SSTable 分段合并壓縮

剛看這段功能邏輯的時候，腦子是懵的，使勁看了好久，分析了好久，還是把它寫出來了，剛開始不理解，后來理解了，寫著就容易許多了。

看下圖:

其實合并是有狀態的，這個就是中間態，我把他放到了圖中間，然后，用白色的虛框表示。

整體邏輯就是，先從內存中定時把不變表生成為0級的SSTable，然后，0級就會有許多文件，如果這些文件大小超過了閾值，就合并此級的文件為一個大文件，按照WalLog的合并原理，然后把信息重新寫入到本地為1級SSTable即可。

以此類推。

下面一個動圖說明其合并效果。

這個動圖也說明一些事情，有此圖，估計對原理就會多懂一些。

LSMDatabase 性能測試

目前我這邊測試用例都挺簡單，如果有bug，就直接改了。我這邊測試是，直接寫入一百萬條數據，測試結果如下:

keyvalue 數據長度:151 實際文件大小:217 MB 插入1000000條數據耗時:79320毫秒或79.3207623秒,平均每秒插入:52631條

keyvalue 數據長度:151 實際文件大小:221 MB 插入1000000條數據耗時:27561毫秒或 27.5616519 秒,平均每秒插入:37037條

1.?keyvalue 數據長度:176
2.?實際文件大小:215 MB
3.?插入1000000條數據耗時:29545毫秒或 29.5457999 秒,
4.?平均每秒插入:34482條或 30373 等( 配置不一樣，環境不一樣，會有不同，但是大致差不多)
5.?多次插入數據長度不同，配置不同，插入速度都會受到影響