????优质资源分享????
???? 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结构分析
这个横向不好画,我画成竖向了,WalLog里面存储的就是时间序的KeyValue数据,当它加载到MemoryTable的时候,其实就是按照我所标的数字顺序依次叠加到最后的状态的。
同理,SSTable数据分段合并压缩的时候,其实是跟这个一个原理的。
SSTable结构分析
SSTable,它本身是一个文件名字大致如下:
格式为层级_时间戳.db这样的方式搞的命名规则,为此我还搞了一个生成时间序不重复ID的简单算法。
SSTable数据区
数据区就很简单,把KeyValue.DataValue直接ToJson就可以了,然后,直接写文件。
SSTable稀疏索引区
这个区是按照与数据区对应的key的顺序写入的,主要是把DataValue对应的开始地址和结束地址放入到这个数据区了,另外把key也写入进去了。
好处是为了,当此SSTable加载索引到内存,省的把数据区的内容也加载进去,查找就方便许多,这也是索引的作用。
元数据区
这个按照协议来讲,属于协议头,但是为啥放最后面呢,其实是为了计算方便,这也算是一个小妙招。
其中不仅包含了数据区的开始和结束,稀疏索引区的开始和结束,还包含了,此SSTable的版本和创建时间,以及当前SSTable所在的级别。
SSTable分段合并压缩
刚看这段功能逻辑的时候,脑子是懵的,使劲看了好久,分析了好久,还是把它写出来了,刚开始不理解,后来理解了,写着就容易许多了。
看下:
其实合并是有状态的,这个就是中间态,我把他放到了中间,然后,用白色的虚框表示。
整体逻辑就是,先从内存中定时把不变表生成为0级的SSTable,然后,0级就会有许多文件,如果这些文件大小超过了阈值,就合并此级的文件为一个大文件,按照WalLog的合并原理,然后把信息重新写入到本地为1级SSTable即可。
以此类推。
下面一个动说明其合并效果。
这个动也说明一些事情,有此,估计对原理就会多懂一些。
LSMDatabase性能测试
目前我这边测试用例都挺简单,如果有bug,就直接改了。我这边测试是,直接写入一百万条数据,测试结果如下:
keyvalue数据长度:151实际文件大小:217MB插入1000000条数据耗时:79320毫秒或73207623秒,平均每秒插入:52631条
keyvalue数据长度:151实际文件大小:221MB插入1000000条数据耗时:27561毫秒或25616519秒,平均每秒插入:37037条
keyvalue数据长度:176
实际文件大小:215MB插入1000000条数据耗时:29545毫秒或25457999秒,平均每秒插入:34482条或30373等多次插入数据长度不同,配置不同,插入速度都会受到影响
加载215MB1000000条数据条数据耗时:2322毫秒,也就是2秒
内存稳定后占用500MB左右。
稳定查询耗时:百条查询平均每条查询耗时:0毫秒。可能是因为用了字典的缘故,查询速度会快点,特别点查询会有0.300左右的耗时个别现象。
查询keys,一百万条耗时3秒,这个有点耗时,应该是数据量太大了。
至此,此项目已经结束,还没有经历过压力测试,整体骨架和内容已经完备,可以根据具体情况修复完善。目前我这边是没啥子问题的。
任何事情的开始都是艰难的,跨越时间的长河,一步一步的学习,才有了今天它的诞生,会了就是会了,应对下一个相关问题就会容易许多,我对这样的壁垒称之为,知识的屏障。
一叶障目,还真是存在,如何突破,唯有好奇心,坚持下去,一点点挖掘。
文章为作者独立观点,不代表观点
Lester Levenson2022-12-10
没有吗?不好意思啊,20年我的股票从10块涨到来年10送2又涨到我以为牛市来了呢。你的股票没涨吗?