【萬字長文】使用 LSM-Tree 思想基於.Net 6.0 C# 實現 KV 資料庫（案例版）

来源:https://www.cnblogs.com/kesshei/archive/2022/07/26/16519862.html
-Advertisement-
Play Games

任何事情的開始都是艱難的，跨越時間的長河，一步一步的學習，才有了今天它的誕生，會了就是會了，那麼，應對下一個相關問題就會容易許多，我對這樣的壁壘稱之為，知識的屏障。 ...


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

這是一個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是Object類型的，我這邊寫入到文件里的話，是直接寫入的。

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

載入215 MB 1000000條數據條數據 耗時:2322 毫秒，也就是2秒(載入SSTable)

記憶體穩定後占用500MB左右。

穩定查詢耗時: 百條查詢平均每條查詢耗時: 0毫秒。可能是因為用了字典的緣故，查詢速度會快點，但是，特別點查詢會有0.300左右的耗時個別現象。

查詢keys，一百萬條耗時3秒，這個有點耗時，應該是數據量太大了。

至此，此項目已經結束，雖然，還沒有經歷過壓力測試，但是，整體骨架和內容已經完備，可以根據具體情況修複完善。目前我這邊是沒啥子問題的。

總結

任何事情的開始都是艱難的，跨越時間的長河，一步一步的學習，才有了今天它的誕生，會了就是會了，那麼，應對下一個相關問題就會容易許多，我對這樣的壁壘稱之為，知識的屏障。

一葉障目，還真是存在，如何突破，唯有好奇心，堅持下去，一點點挖掘。

參考資料

【萬字長文】使用 LSM Tree 思想實現一個 KV 資料庫

https://www.cnblogs.com/whuanle/p/16297025.html

肖漢松：《從0開始：500行代碼實現 LSM 資料庫》

https://mp.weixin.qq.com/s/kCpV0evSuISET7wGyB9Efg

cstack : 讓我們建立一個簡單的資料庫

https://cstack.github.io/db_tutorial/

資料庫內核雜談 - 一小時實現一個基本功能的資料庫

https://www.jianshu.com/p/76e5cb53c864

谷歌三大論文 GFS，MapReduce，BigTable 中的GFS和BigTable

致謝名單

  1. 痴者工良
  2. 陶德

雖然與以上大佬沒有太過深入的交流，畢竟咖位還是有點高的，但是，通過文章以及簡單的交流中，讓我對資料庫的研究更深一步，甚至真實的搞出來了，再次感謝。

代碼地址

https://github.com/kesshei/LSMDatabaseDemo.git

https://gitee.com/kesshei/LSMDatabaseDemo.git

閱

一鍵三連呦！，感謝大佬的支持，您的支持就是我的動力!

版權

藍創精英團隊（公眾號同名，CSDN同名）


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 配置cri-docker使kubernetes1.24以docker作為運行時
    鏡像下載、功能變數名稱解析、時間同步請點擊 阿裡雲開源鏡像站 從kubernetes 1.24開始，dockershim已經從kubelet中移除，但因為歷史問題docker卻不支持kubernetes主推的CRI（容器運行時介面）標準，所以docker不能再作為kubernetes的容器運行時了，即從ku ...
  • [apue] 文件中的空洞
    空洞的概念 linux 上普通文件的大小與占用空間是兩個概念，前者表示文件中數據的長度，後者表示數據占用的磁碟空間，通常後者大於前者，因為需要一些額外的空間用來記錄文件的某些統計信息或附加信息、以及切分為塊的數據信息 (通常不會占用太多)。文件占用空間也可以小於文件尺寸，此時文件內部就存在空洞了。 ...
  • 【操作系統】磁碟尋道演算法
    寫在前面 本系列的文章是博主邊學邊記錄的，可能不是特別的正確，因為會加上博主自己的理解，僅供參考。 正文: 1.磁碟的訪問時間 為了讀或者寫，磁頭必須能移動到所指定的磁軌上，並等待所指定的扇區的開始位置旋轉到磁頭下，然後開始讀取或者寫入數據。那麼可以把對磁碟的訪問時間分為以下三個部分： 1.尋道時間 ...
  • 一文搞懂 Redis 架構演化之路
    現如今 Redis 變得越來越流行，幾乎在很多項目中都要被用到，不知道你在使用 Redis 時，有沒有思考過，Redis 到底是如何穩定、高性能地提供服務的？ 我使用 Redis 的場景很簡單，只使用單機版 Redis 會有什麼問題嗎？ 我的 Redis 故障宕機了，數據丟失了怎麼辦？如何能保證我的... ...
  • DTS搭載全新自研內核，突破兩地三中心架構的關鍵技術｜騰訊雲資料庫
    隨著企業規模的擴大，對資料庫可用性要求越來越高，更多企業採用兩地三中心、異地多活的架構，以提高資料庫的異常事件應對能力。 在資料庫領域，我們常聽的“兩地三中心”、“異地多活”到底是什麼呢？ “兩地三中心”就是生產數據中心、同城災備中心、異地災備中心。這種模式下，兩個地域的三個數據中心互聯互通，當一個 ...
  • sqlDeveloper工具快速入門
    場景 我們在連接oracle資料庫的時候 常用方式一般有以下三種： pl/sql deceloper navicat sqlDeveloper 其中， pl/sql developer是最經典的，也是我個人最常用的 navicat操作簡單，覆蓋的資料庫類型較多 sqlDeveloper是官方出品，功 ...
  • Linux—搭建Apache(httpd)服務
    1、httpd簡介？ http是Apache超文本傳輸協議伺服器的主程式。它是一個獨立的後臺進程，能夠處理請求的子進程和線程。 http常用用的兩個版本是httpd-2.2和httpd-2.4 CentOS6系列的預設httpd版本是httpd-2.2版本的rpm包 CentOS7系列的預設http ...
  • JetBrains DataGrip 2022 Mac(多引擎資料庫管理工具)
    JetBrAIns DataGrip 2022 for Mac不管是在國內還是國外都是一款不容小覷的資料庫客戶端軟體。DataGrip 2022 Mac中文版可用於完成資料庫的常用操作，包括查詢數據、修改數據，創建資料庫、表等，它對於資料庫的支持很寬泛，從PostgreSQL到MySQL再到Orac ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類