使用 LSMTree 思想基于.Net 6.0 C# 实现 KV 数据库

????优质资源分享????

???? Python实战微信订餐小程序 ????	进阶级	本课程是python flask+微信小程序的完美结合，从项目搭建到腾讯云部署上线，打造一个全栈订餐系统。
????Python量化交易实战????	入门级	手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

文章有点长，耐心看完应该可以懂实际原理到底是啥子。

这是一个KV数据库的C#实现，目前用.NET0实现的，目前算是属于雏形，骨架都已经完备，毕竟刚完工不到一星期。

这个其实也算是NoSQL的雏形，有助于深入了解相关数据库的内部原理概念，也有助于实际入门。

适合对数据库原理以及实现感兴趣的朋友们。

整体代码，大概1500行，核心代码大概500行。

为啥要实现一个数据库

大概2018年的时候，就萌生了想自己研发一个数据库的想法了，造轮子可能不如现有各种产品的强大，能造者寥寥无几，造数据库的书更是少的可怜，不仅仅是造数据库的书少，而是各种各样高级的产品的创造级的书都少。

现在有各种各样的开源，像我这种底子薄的，就不能轻易的了解，这些框架的架构设计，以及相关的理念，纯看代码，没个长时间，也不容易了解其存在的含义。

恰逢其时，前一个月看到【痴者工良】大佬的一篇《【万字长文】使用LSMTree思想实现一个KV数据库》文章给我很大触动，让我停滞的心，又砰砰跳了起来，虽然大佬是用GO语言实现的，对我来讲，语言还是个问题么，只要技术思想一致，我完全可以用C#实现啊，也算是对【痴者工良】大佬的致敬，我这边紧随其后。

我自己对数据的研究也是耗时很久，毕竟，研究什么都要先从原理开始研究，从谷歌三个论文《GFS，MapReduce，BigTable》开始，论文，毕竟是论文，读不懂啊，又看了网上各种大佬的文章，还是很蒙蔽，实现的时候，也没人交流，导致各种流产。

有时候，自己实现某个产品框架的时候，总是在想，为啥BUG都让我处理一个遍哦，后来一想，你自己从新做个产品，也不能借鉴技术要点，那还不是从零开始，自然一一遇到BUG。

下就是，我在想做数据库后，自己写写画画，实际做的时候，逻辑表现总没有那么好，这个是关系型数据库，难度比较高，下面可以看看之前的手稿，都是有想法了就画一下。

实现难度有点高，现在这个实现是KV数据库，算是列式数据库了，大名鼎鼎的HBase，底层数据库引擎就是LSM-Tree的技术思想。

LSM-Tree是啥子

LSM-Tree英文全称是LogStructuredMergeTree，是一种分层，有序，面向磁盘的数据结构，其核心思想是充分了利用了，磁盘批量的顺序写要远比随机写性能高的技术特点，来实现高写入吞吐量的存储系统的核心。

具体的说，原理就是针对硬盘，尽量追加数据，而不是随机写数据，追加速度要比随机写的速度快，这种结构适合写多读少的场景，LSM-Tree被设计来提供比传统的B+树或者ISAM更好的写操作吞吐量，通过消去随机的本地更新操作来达到这个性能目标。

相关技术产品有Hbase、Cassandra、Leveldb、RocksDB、MongoDB、TiDB、Dynamodb、Cassandra、Bookkeeper、SQLite等

LSM-Tree的核心就是追加数据，而不是修改数据。

LSM-Tree架构分析

其实这个已经表达了整体的设计思想了，主体其实就围绕着红色的线与黑色的线，两部分展开的，其中红色是写，黑色是读，箭头表示数据的方向，数字表示逻辑顺序。

整体包含大致三个部分，数据库操作部分，内存部分以及硬盘部分，这三个部分。

先对关键词解释一下

内存表，一种临时缓存性质的数据表，可以用二叉排序树实现，也可以用字典来实现，我这边是用字典实现的。

WAL英文是一种预写日志，用于在系统故障期间提供数据的持久性，这意味着当写入请求到来时，数据首先添加到WAL文件并刷新到更新内存数据结构之前的磁盘。

如果用过Mysql，应该就知道BinLog文件，它们是一个道理，先写入到WALLog里，记录起来，然后，写入到内存表，如果电脑突然死机了，内存里的东西肯定丢失了，下一次重启，就从WALLog记录表里，从新恢复数据到当前的数据状态。

Immutable，相对于内存表来讲，它是不能写入新数据，是只读的。

SSTable英文，有序字符串表，就是有序的字符串列表，使用它的好处是可以实现稀疏索引的效果，合并文件更为简单方便，我要查某个Key，它是基于某个有序Key之间的，可以直接去文件里查，而不用都保存到内存里。

这里我是用哈希表实现的，我认为浪费一点内存是值得的，毕竟为了快，浪费点空间是值得的，目前是全索引加载到内存，而数据保存在SSTable里，如果是为了更好的设计，也可以自己去实现有序表来用二分查找。

我这个方便实现了之后，内存会加载大量的索引，相对来讲是快的，内存会大一些，空间换时间的方案。

下面开始具体的流程分析

LSM-TreeWrite路线分析

看下，数据写入分析

LSM-TreeWrite路线分析第一步

第一步，只有两个部分需要注意的部分，分别是内存表和WAL.Log

写入数据先存储内存表，是为了快速的存储到数据库数据。

存储到WAL.Log，是为了防止异常情况下数据丢失。

正常情况下，写入到WAL.Log一份，然后，会写入到内存一份。

当程序崩溃了，或者，电脑断电异常了，重复服务后，就会先加载WAL.Log，按照从头到尾的顺序，恢复数据到内存表，直至结束，恢复到WAL.Log最后的状态，也就是内存表数据最后的状态。

这里要注意的是，当后面的不变表写入到SSTable的时候，会清空WAL.Log文件，并同时把内存表的数据直接写入到WAL.log表中。

LSM-TreeWrite路线分析第二步

第二步，比较简单，就是在内存表count大于一定数的时候，就新增一个内存表的把它变为ImmutableMemoryTable，等待SSTable的落盘操作，这个时候，ImmutableMemoryTable会有多个表存在。

LSM-TreeWrite路线分析第三步

第三步，就是数据库会定时检查ImmutableMemoryTable不变表是否存在，如果存在，就会直接落盘为SSTable表，不论当前内存里有多少ImmutableMemoryTable。

默认从内存落盘的第一级SSTable都是Level0，然后，内置了当前的时间，所以是两级排序，先分级别，然后，分时间。

LSM-TreeWrite路线分析第四步

第四步，其实就是段合并或者级合并压缩，就是判断level0这一个级别的所有SSTable文件，判断它们的总大小或者判断它们的总个数来判断，它们需不需要进行合并。

其中Level0的大小如果是10M，那么,Level1的大小就是100M，依此类推。

当Level0的所有SSTable文件超过了10M，或者限定的大小，就会从按照WAL.Log的顺序思路，重新合并为一个大文件，先老数据再新数据这样遍历合并，如果已经删除的，则直接剔除在外，只保留最新状态。

如果Level1的大小超过100M，触发Level1的收缩动作，执行过程跟Level0一样的操作，只是级别不同。

这样压缩的好处是使数据尽可能让文件量尽可能的少，毕竟，文件多，管理就不是很方便。

至此，写入路线已经分析完毕

查询的时候，要先新数据，后旧数据，而分段合并压缩的时候，要先老数据垫底，新数据刷状态，这个是实现的时候需要注意的点。

LSM-TreeRead路线分析

这就是数据的查找过程，跟着黑线和数字标记，很容易就看到了其访问顺序

MemoryTableImmutableMemoryTableLevel0-N

基本上来说就这三部分，而级别表是从0级开始往下找的，而每级内部的SSTable是从新到旧开始找的，找到就返回，不论key是删除还是正常的状态。

LSM-Tree架构分析与实现

核心思想：

其实就是一个时间有序的记录表，会记录每个操作，相当于是一个消息队列，记录一系列的动作，然后，回放动作，就获取到了最新的数据状态，也类似CQRS中的EventStore，概念是相同的，那么实现的时候，就明白是一个什么本质。

Wal.log和SSTable，都是为了保证数据能落地持久化不丢失，而MemoryTable，偏向临时缓存的概念，也有为了加速访问的作用。

从这几个点来看，就分为了以下几个大的对象

Database数据库Wal.logMemoryTableSSTable

针对这几个对象来设计相关的类接口设计。

KeyValue

设计的时候，要先设计实际数据的结构，我是这样设计的

主要有三个主要的信息，key,DataValue，Deleted，其中DataValue是Object类型的，我这边写入到文件里的话，是直接写入的。

/// 
/// 数据信息 kv
/// 
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;
    }

    /// 
    /// 是否存在有效数据,非删除状态
    /// 
    /// 
    public bool IsSuccess()
    {
        return !Deleted || DataValue != null;
    }
    /// 
    /// 值存不存在，无论删除还是不删除
    /// 
    /// 
    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();
 }
 return (T)Value;
 }

 public static KeyValue Null = new KeyValue() { DataValue = null };
}
折叠

IDataBase

主要对外交互用的主体类，数据库类，增删改查接口，都用get,set,delete表现。

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

IDataBase.Check

这个是定期检查ImmutableMemoryTable的定时操作，主要依赖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时的阈值配置，还有检测间隔时间配置。

IMemoryTable

这个表其实算是对内存数据的管理表了，主要是管理MemoryTableValue对象，这个对象是通过哈希字典来实现的，你也可以选择其他结构，比如有序二叉树等。

/// 
/// 内存表(排序树，二叉树)
/// 
public interface IMemoryTable : IDisposable
{
    IDataBaseConfig DataBaseConfig { get; }
    /// 
    /// 获取总数
    /// 
    int GetCount();
    /// 
    /// 搜索(从新到旧，从大到小)
    /// 
    KeyValue Search(string key);
    /// 
    /// 设置新值
    /// 
    void Set(KeyValue keyValue);
    /// 
    /// 删除key
    /// 
    void Delete(KeyValue keyValue);
    /// 
    /// 获取所有 key 数据列表
    /// 
    /// 
    IList<string> GetKeys();
    /// 
    /// 获取所有数据
    /// 
    /// 
    (List keyValues, List<long> times) GetKeyValues(bool Immutable);
 /// 
 /// 获取不变表的数量
 /// 
 /// 
 int GetImmutableTableCount();
 /// 
 /// 开始交换
 /// 
 void Swap(List<long> times);
 /// 
 /// 清空全部数据
 /// 
 void Clear();
}

MemoryTableValue

主要是通过Immutable这个属性实现了对不可变内存表的标记，具体实现是通过判断IDataBaseConfig.MemoryTableCount来实现标记的。

public class MemoryTableValue : IDisposable
{
    public long Time { get; set; } = IDHelper.MarkID();
    /// 
    /// 是否是不可变
    /// 
    public bool Immutable { get; set; } = false;
    /// 
    /// 数据
    /// 
    public Dictionary<string, KeyValue> Dic { get; set; } = new();

    public void Dispose()
    {
        Dic.Clear();
    }

    public override string ToString()
    {
        return $"Time {Time} Immutable：{Immutable}";
    }
}

什么时机表状态转换为ImmutableMemoryTable的

我这里实现的是从Set的入口处实现的，如果数目大于IDataBaseConfig.MemoryTableCount就改变其状态

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

wallog，就简单许多，就直接把KeyValue写入到文件即可，为了保证WalLog的持续写，对象内部保留了此文件的句柄。而SSTable，就没有必要了，随时读。

/// 
/// 日志
/// 
public interface IWalLog : IDisposable
{
    /// 
    /// 数据库配置
    /// 
    IDataBaseConfig DataBaseConfig { get; }
    /// 
    /// 加载Wal日志到内存表
    /// 
    /// 
    IMemoryTable LoadToMemory();
    /// 
    /// 写日志
    /// 
    void Write(KeyValue data);
    /// 
    /// 写日志
    /// 
    void Write(List data);
    /// 
    /// 重置日志文件
    /// 
    void Reset();
}

ITableManage

为了更好的管理SSTable，需要有一个管理层，这个接口就是它的管理层，其中SSTable会有多层，每次用Level+时间戳+db作为文件名，用作外部识别。

/// 
/// 表管理项
/// 
public interface ITableManage : IDisposable
{
    IDataBaseConfig DataBaseConfig { get; }
    /// 
    /// 搜索(从新到老,从大到小)
    /// 
    KeyValue Search(string key);
    /// 
    /// 获取全部key
    /// 
    List<string> GetKeys();
    /// 
    /// 检查数据库文件，如果文件无效数据太多，就会触发整合文件
    /// 
    void Check();
    /// 
    /// 创建一个新Table
    /// 
    void CreateNewTable(List values, int Level = 0);
    /// 
    /// 清理某个级别的数据
    /// 
    /// 
    public void Remove(int Level);
    /// 
    /// 清除数据
    /// 
    public void Clear();
}

ISSTable

SSTable的内容管理，应该就是LSM-Tree的核心了，数据的合并，以及数据的查询，写入，加载，都是偏底层的操作，需要一丢丢的数据库知识。

/// 
/// 文件信息表 （存储在IO中）
/// 元数据 | 索引列表 | 数据区(数据修改只会新增，并修改索引列表数据) 
/// 
public interface ISSTable : IDisposable
{
    /// 
    /// 数据地址
    /// 
    public string TableFilePath();
    /// 
    /// 重写文件
    /// 
    public void Write(List values, int Level = 0);
    /// 
    /// 数据位置
    /// 
    public Dictionary<string, DataPosition> DataPositions { get; }
    /// 
    /// 获取总数
    /// 
    /// 
    public int Count { get; }
    /// 
    /// 元数据
    /// 
    public ITableMetaInfo FileTableMetaInfo { get; }
    /// 
    /// 查询数据
    /// 
    /// 
    /// 
    public KeyValue Search(string key);
    /// 
    /// 有序的key列表
    /// 
    /// 
    public List<string> SortIndexs();
    /// 
    /// 获取位置
    /// 
    DataPosition GetDataPosition(string key);
    /// 
    /// 读取某个位置的值
    /// 
    public object ReadValue(DataPosition position);
    /// 
    /// 加载所有数据
    /// 
    /// 
    public List ReadAll(bool incloudDeleted = true);
    /// 
    /// 获取所有keys
    /// 
    /// 
    public List<string> GetKeys();
    /// 
    /// 获取表名
    /// 
    /// 
    public long FileTableName();
    /// 
    /// 文件的大小
    /// 
    /// 
    public long FileBytes { get; }
    /// 
    /// 获取级别
    /// 
    public int GetLevel();
}
折叠

IDataPosition

方便数据查询方便和方便从SSTable里读取到实际的数据内容。

/// 
/// 数据的位置
/// 
public interface IDataPosition
{
    /// 
    /// 索引起始位置
    /// 
    public long IndexStart { get; set; }
    /// 
    /// 开始地址
    /// 
    public long Start { get; set; }
    /// 
    /// 数据长度
    /// 
    public long Length { get; set; }
    /// 
    /// key的长度
    /// 
    public long KeyLength { get; set; }
    /// 
    /// 是否已经删除
    /// 
    public bool Deleted { get; set; }
    public byte[] GetBytes();
}

数据结构分析

内部表的结构就不用说了，很简单，就是一个哈希字典，而有两个结构是要具体分析的，那就是WALLog和SSTable文件。

WALLog结构分析