建设网站 备案,青岛网上房地产网站,产品软文模板,wordpress搜索频率文章有点长#xff0c;耐心看完应该可以懂实际原理到底是啥子。这是一个KV数据库的C#实现#xff0c;目前用.NET 6.0实现的#xff0c;目前算是属于雏形#xff0c;骨架都已经完备#xff0c;毕竟刚完工不到一星期。当然#xff0c;这个其实也算是NoSQL的雏形#xff0c… 文章有点长耐心看完应该可以懂实际原理到底是啥子。这是一个KV数据库的C#实现目前用.NET 6.0实现的目前算是属于雏形骨架都已经完备毕竟刚完工不到一星期。当然这个其实也算是NoSQL的雏形有助于深入了解相关数据库的内部原理概念也有助于实际入门。适合对数据库原理以及实现感兴趣的朋友们。整体代码大概1500行核心代码大概500行。为啥要实现一个数据库大概2018年的时候就萌生了想自己研发一个数据库的想法了虽然造轮子可能不如现有各种产品的强大但是能造者寥寥无几而且造数据库的书更是少的可怜当然不仅仅是造数据库的书少而是各种各样高级的产品的创造级的书都少。虽然现在有各种各样的开源但是像我这种底子薄的就不能轻易的了解这些框架的架构设计以及相关的理念纯看代码没个长时间也不容易了解其存在的含义。恰逢其时前一个月看到【痴者工良】大佬的一篇《【万字长文】使用 LSM Tree 思想实现一个 KV 数据库 》文章给我很大触动让我停滞的心又砰砰跳了起来虽然大佬是用GO语言实现的 但是对我来讲语言还是个问题么只要技术思想一致我完全可以用C#实现啊也算是对【痴者工良】大佬的致敬我这边紧随其后。当然我自己对数据的研究也是耗时很久毕竟研究什么都要先从原理开始研究从谷歌三个论文《GFSMapReduceBigTable》开始但是论文毕竟是论文读不懂啊又看了网上各种大佬的文章还是很蒙蔽实现的时候也没人交流导致各种流产。有时候自己实现某个产品框架的时候总是在想为啥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 LogWAL 英文 (Write Ahead LOG) 是一种预写日志用于在系统故障期间提供数据的持久性这意味着当写入请求到来时数据首先添加到 WAL 文件有时称为日志并刷新到更新内存数据结构之前的磁盘。如果用过Mysql应该就知道BinLog文件它们是一个道理先写入到WAL Log里记录起来然后写入到内存表如果电脑突然死机了内存里的东西肯定丢失了那么下一次重启就从WAL Log 记录表里从新恢复数据到当前的数据状态。Immutable MemoryTableImmutable(不变的)相对于内存表来讲它是不能写入新数据是只读的。SSTableSSTable 英文 (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文件(SSTable0SSTable1SSTable2)判断它们的总大小或者判断它们的总个数来判断它们需不需要进行合并。其中 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.logSSTable和MemoryTable 的管理职责)2. Wal.log(记录临时数据日志)3. MemoryTable(记录数据到内存同时为数据库查找功能提供接口服务)4. SSTable(管理SSTable文件并提供SSTable的查询功能)所以针对这几个对象来设计相关的类接口设计。KeyValue (具体数据的结构)设计的时候要先设计实际数据的结构我是这样设计的主要有三个主要的信息key, DataValueDeleted 其中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/returnspublic bool IsSuccess(){return !Deleted || DataValue ! null;}/// summary/// 值存不存在无论删除还是不删除/// /summary/// returns/returnspublic bool IsExist(){if (DataValue ! null !Deleted || DataValue null Deleted){return true;}return false;}public T GetT() where T : class{if (Value null){Value DataValue.AsObjectT();}return (T)Value;}public static KeyValue Null new KeyValue() { DataValue null };
}IDataBase (数据库接口)主要对外交互用的主体类数据库类增删改查接口都用 get,set,delete 表现。/// summary
/// 数据库接口
/// /summary
public interface IDataBase : IDisposable
{/// summary/// 数据库配置/// /summaryIDataBaseConfig DataBaseConfig { get; }/// summary/// 获取数据/// /summaryKeyValue Get(string key);/// summary/// 保存数据(或者更新数据)/// /summarybool Set(KeyValue keyValue);/// summary/// 保存数据(或者更新数据)/// /summarybool Set(string key, object value);/// summary/// 获取全部key/// /summaryListstring GetKeys();/// summary/// 删除指定数据并返回存在的数据/// /summaryKeyValue DeleteAndGet(string key);/// summary/// 删除数据/// /summaryvoid Delete(string key);/// summary/// 定时检查/// /summaryvoid Check(object state);/// summary/// 清除数据库所有数据/// /summaryvoid 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/// 数据库数据目录/// /summarypublic string DataDir { get; set; }/// summary/// 0 层的 所有 SsTable 文件大小总和的最大值单位 MB超过此值该层 SsTable 将会被压缩到下一层/// 每层数据大小是上层的N倍/// /summarypublic int Level0Size { get; set; }/// summary/// 层与层之间的倍数/// /summarypublic int LevelMultiple { get; set; }/// summary/// 每层数量阈值/// /summarypublic int LevelCount { get; set; }/// summary/// 内存表的 kv 最大数量超出这个阈值内存表将会被保存到 SsTable 中/// /summarypublic int MemoryTableCount { get; set; }/// summary/// 压缩内存、文件的时间间隔多久进行一次检查工作/// /summarypublic int CheckInterval { get; set; }
}IMemoryTable (内存表)这个表其实算是对内存数据的管理表了主要是管理 MemoryTableValue 对象这个对象是通过哈希字典来实现的当然你也可以选择其他结构比如有序二叉树等。/// summary
/// 内存表(排序树二叉树)
/// /summary
public interface IMemoryTable : IDisposable
{IDataBaseConfig DataBaseConfig { get; }/// summary/// 获取总数/// /summaryint GetCount();/// summary/// 搜索(从新到旧从大到小)/// /summaryKeyValue Search(string key);/// summary/// 设置新值/// /summaryvoid Set(KeyValue keyValue);/// summary/// 删除key/// /summaryvoid Delete(KeyValue keyValue);/// summary/// 获取所有 key 数据列表/// /summary/// returns/returnsIListstring GetKeys();/// summary/// 获取所有数据/// /summary/// returns/returns(ListKeyValue keyValues, Listlong times) GetKeyValues(bool Immutable);/// summary/// 获取不变表的数量/// /summary/// returns/returnsint GetImmutableTableCount();/// summary/// 开始交换/// /summaryvoid Swap(Listlong times);/// summary/// 清空全部数据/// /summaryvoid Clear();
}MemoryTableValue (对象的实现)主要是通过 Immutable 这个属性实现了对不可变内存表的标记具体实现是通过判断 IDataBaseConfig.MemoryTableCount (内存表的 kv 最大数量)来实现标记的。public class MemoryTableValue : IDisposable
{public long Time { get; set; } IDHelper.MarkID();/// summary/// 是否是不可变/// /summarypublic bool Immutable { get; set; } false;/// summary/// 数据/// /summarypublic Dictionarystring, 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;}
}IWalLogwallog就简单许多就直接把KeyValue 写入到文件即可为了保证WalLog的持续写所以对象内部保留了此文件的句柄。而SSTable就没有必要了随时读。/// summary
/// 日志
/// /summary
public interface IWalLog : IDisposable
{/// summary/// 数据库配置/// /summaryIDataBaseConfig DataBaseConfig { get; }/// summary/// 加载Wal日志到内存表/// /summary/// returns/returnsIMemoryTable LoadToMemory();/// summary/// 写日志/// /summaryvoid Write(KeyValue data);/// summary/// 写日志/// /summaryvoid Write(ListKeyValue data);/// summary/// 重置日志文件/// /summaryvoid Reset();
}ITableManage (SSTable表的管理)为了更好的管理SSTable需要有一个管理层这个接口就是它的管理层其中SSTable会有多层每次用 Level时间戳db 作为文件名用作外部识别。/// summary
/// 表管理项
/// /summary
public interface ITableManage : IDisposable
{IDataBaseConfig DataBaseConfig { get; }/// summary/// 搜索(从新到老,从大到小)/// /summaryKeyValue Search(string key);/// summary/// 获取全部key/// /summaryListstring GetKeys();/// summary/// 检查数据库文件如果文件无效数据太多就会触发整合文件/// /summaryvoid Check();/// summary/// 创建一个新Table/// /summaryvoid CreateNewTable(ListKeyValue values, int Level 0);/// summary/// 清理某个级别的数据/// /summary/// param nameLevel/parampublic void Remove(int Level);/// summary/// 清除数据/// /summarypublic void Clear();
}ISSTable(SSTable 文件)SSTable的内容管理应该就是LSM-Tree的核心了数据的合并以及数据的查询写入加载都是偏底层的操作需要一丢丢的数据库知识。/// summary
/// 文件信息表 存储在IO中
/// 元数据 | 索引列表 | 数据区(数据修改只会新增并修改索引列表数据)
/// /summary
public interface ISSTable : IDisposable
{/// summary/// 数据地址/// /summarypublic string TableFilePath();/// summary/// 重写文件/// /summarypublic void Write(ListKeyValue values, int Level 0);/// summary/// 数据位置/// /summarypublic Dictionarystring, DataPosition DataPositions { get; }/// summary/// 获取总数/// /summary/// returns/returnspublic int Count { get; }/// summary/// 元数据/// /summarypublic ITableMetaInfo FileTableMetaInfo { get; }/// summary/// 查询数据/// /summary/// param namekey/param/// returns/returnspublic KeyValue Search(string key);/// summary/// 有序的key列表/// /summary/// returns/returnspublic Liststring SortIndexs();/// summary/// 获取位置/// /summaryDataPosition GetDataPosition(string key);/// summary/// 读取某个位置的值/// /summarypublic object ReadValue(DataPosition position);/// summary/// 加载所有数据/// /summary/// returns/returnspublic ListKeyValue ReadAll(bool incloudDeleted true);/// summary/// 获取所有keys/// /summary/// returns/returnspublic Liststring GetKeys();/// summary/// 获取表名/// /summary/// returns/returnspublic long FileTableName();/// summary/// 文件的大小/// /summary/// returns/returnspublic long FileBytes { get; }/// summary/// 获取级别/// /summarypublic int GetLevel();
}IDataPosition(数据稀疏索引算是)方便数据查询方便和方便从SSTable里读取到实际的数据内容。/// summary
/// 数据的位置
/// /summary
public interface IDataPosition
{/// summary/// 索引起始位置/// /summarypublic long IndexStart { get; set; }/// summary/// 开始地址/// /summarypublic long Start { get; set; }/// summary/// 数据长度/// /summarypublic long Length { get; set; }/// summary/// key的长度/// /summarypublic long KeyLength { get; set; }/// summary/// 是否已经删除/// /summarypublic 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 数据长度:1762. 实际文件大小:215 MB3. 插入1000000条数据 耗时:29545毫秒 或 29.5457999 秒,4. 平均每秒插入:34482条 或 30373 等( 配置不一样环境不一样会有不同但是大致差不多)5. 多次插入数据长度不同配置不同插入速度都会受到影响加载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/kCpV0evSuISET7wGyB9Efgcstack : 让我们建立一个简单的数据库https://cstack.github.io/db_tutorial/数据库内核杂谈 - 一小时实现一个基本功能的数据库https://www.jianshu.com/p/76e5cb53c864谷歌三大论文 GFSMapReduceBigTable 中的GFS和BigTable致谢名单1. 痴者工良2. 陶德虽然与以上大佬没有太过深入的交流毕竟咖位还是有点高的但是通过文章以及简单的交流中让我对数据库的研究更深一步甚至真实的搞出来了再次感谢。代码地址https://github.com/kesshei/LSMDatabaseDemo.githttps://gitee.com/kesshei/LSMDatabaseDemo.git阅一键三连呦感谢大佬的支持您的支持就是我的动力!版权蓝创精英团队公众号同名CSDN同名
