V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
Sponsored by
LinkedIn
不坐班的神仙工作 · 去任何你想去的地方远程,赚一线城市的工资
2000 个不用出门 Social 的全球远程工作,帮助 V2EX 的小伙伴开启全新的工作方式。
Promoted by LinkedIn
roseduan
V2EX  ›  分享创造

用 Go 语言写的一个 kv 存储引擎

  •  
  •   roseduan ·
    roseduan · 189 天前 · 2701 次点击
    这是一个创建于 189 天前的主题,其中的信息可能已经有所发展或是发生改变。

    经历了大概 4 个月的打磨,LotusDB 的第一个 release 版本终于发布了,我看了下,有 200 多次 commit (接近 rosedb 一年多的 commit 次数了)。

    图片

    项目地址: https://github.com/flower-corp/lotusdb

    有了 rosedb 在 bitcask 模型上的实践之后,以及自己在存储这方面的一些经验积累,去年底的时候,在上班路上突然想到的一个 idea ,让我有了做一个新的 kv 存储引擎的想法。

    有了想法之后便是验证,因为其实心里还是没谱,我又在 Github 上翻了翻,并没有同类型的实现。后来又找一些大佬沟通了下,证明我的想法是可行的。

    这期间还发现了 Usenix Fast 上的一篇关于优化 LSM 的论文,发现论文的内容跟我的 idea 非常类似,这算是又多了一个理论依据,于是便决定开干了。

    感兴趣的可以参考下论文,叫做 SLM-DB ,地址: https://www.usenix.org/conference/fast19/presentation/kaiyrakhmet

    众所周知,数据存储引擎,目前最主流的两种模型是 B+ 树和 LSM 树,B+ 树在关系型数据库例如 Mysql 中应用比较广泛,而 LSM 的典型代表 rocksdb 也是大多数分布式系统数据落盘的首选。

    B+ 树读性能稳定,而 LSM 写吞吐高,LotusDB 在这基础上做了一个巨大的改动,就是完全舍弃掉 LSM 中的 SST 文件,改由 B+ 树来存储索引,而 value 存放则参考了 Wisckey 和 bitcask 模型的设计,存储到单独的 value log 文件中。

    LotusDB 是对 LSM 和 B+ 树的优势结合,目前并没有同类型的实现,我们应该是第一个吃螃蟹的人。

    LotusDB 的架构图如下:

    图片

    前台的写入和 LSM 完全一致,先写 wal 再写 memtable 。

    而读取则会从 memtable 开始,如果 memtable 找到了,直接返回;没找到的话则从 B+ 树中查询索引,然后根据索引信息到 value log 中获取 value 。

    大家可以先了解个大概,后续我会出一个完整的《 LotusDB 设计与实现》系列文章,全面解析 LotusDB 的架构细节以及代码实现,目前已经写了几篇待发布,欢迎关注公众号的后续更新:

    图片

    再来看看 LotusDB 提供的一些基本接口,目前实现了基础的 Put 、Get 、Delete 接口,并且支持 Column Family (借鉴于 rocksdb ),以及 value log 的自动 GC 回收。

    简单的使用方法如下:

    package main
    
    import (
    	"github.com/flower-corp/lotusdb"
    	"io/ioutil"
    	"time"
    )
    
    // basic operations for LotusDB:
    // put
    // put with options
    // get
    // delete
    // delete with options
    func main() {
    	path, _ := ioutil.TempDir("", "lotusdb")
    	opts := lotusdb.DefaultOptions(path)
    	db, err := lotusdb.Open(opts)
    	if err != nil {
    		panic(err)
    	}
    	defer db.Close()
    
    	// 1.----put----
    	key1 := []byte("name")
    	err = db.Put(key1, []byte("lotusdb"))
    	if err != nil {
    		// ...
    	}
    
    	key2 := []byte("feature")
    	// 2.----put with options----
    	writeOpts := &lotusdb.WriteOptions{
    		Sync:      true,
    		ExpiredAt: time.Now().Add(time.Second * 100).Unix(),
    	}
    	err = db.PutWithOptions(key2, []byte("store data"), writeOpts)
    	if err != nil {
    		// ...
    	}
    
    	// 3.----get----
    	val, err := db.Get(key1)
    	if err != nil {
    		// ...
    	}
    	if len(val) > 0 {
    		// ...
    	}
    
    	// 4.----delete----
    	err = db.Delete(key1)
    	if err != nil {
    		// ...
    	}
    
    	// 5.----delete with options----
    	deleteOpts := &lotusdb.WriteOptions{
    		Sync:       false,
    		DisableWal: true,
    	}
    	err = db.DeleteWithOptions([]byte("dummy key"), deleteOpts)
    	if err != nil {
    		// ...
    	}
    }
    
    

    目前自认为 LotusDB 的代码质量比之前的 RoseDB 好多了,单元测试更加完备,注释清晰,代码也更加简洁规范,如果你是 Go 新手,或者准备学习 Go ,也能够把项目当做练习素材,自己对照着来学习。

    当然我们的愿景还是打造一个能够在生产环境中实际落地的存储引擎,目前的版本只是一个开始,后续还会有非常多的工作,包括但不限于:

    • batch 操作,保证原子性
    • 多个 Column Family 保证原子性
    • 基于 SSI 的事务
    • Iterator 迭代器
    • 数据压缩
    • 数据备份
    • index 的分裂

    如果大家在使用或者学习的过程中,有任何问题都可以微信联系我:

    图片

    觉得有帮助的话,欢迎给项目点个 star 支持下

    项目地址: https://github.com/flower-corp/lotusdb

    16 条回复    2022-03-22 16:36:52 +08:00
    shisang
        1
    shisang  
       189 天前
    lsm + B+ 整合感觉怪怪的,一个 append-only , 一个 replace update ,lsm 就相当于一个 buffer ?
    roseduan
        2
    roseduan  
    OP
       189 天前
    @shisang B+ tree 只存储索引信息,其实也有类似的实现,rust 的 sled 比较类似
    linglin0924
        3
    linglin0924  
       189 天前
    已 star ,留着日后看数据库学习。
    calano
        4
    calano  
       189 天前
    以前研究过 boltDB ,这个也学习下
    roseduan
        5
    roseduan  
    OP
       189 天前
    @calano 项目也用到了 boltdb 存索引
    roseduan
        6
    roseduan  
    OP
       189 天前
    @linglin0924 感谢支持
    dilu
        7
    dilu  
       189 天前
    支持 duan 大佬,加油
    Sailwww
        8
    Sailwww  
       189 天前
    支持
    roseduan
        9
    roseduan  
    OP
       189 天前
    @dilu 感谢
    roseduan
        10
    roseduan  
    OP
       189 天前
    @Sailwww 感谢
    dongcidaci
        11
    dongcidaci  
       189 天前 via Android
    支持一下,感觉最近流行造 lsm tree 的轮子啊,前不久才看到一个类似的项目
    BeijingBaby
        12
    BeijingBaby  
       188 天前
    有性能测试数据吗?和其他同类项目对比?
    roseduan
        13
    roseduan  
    OP
       188 天前
    @BeijingBaby 暂时还没来得及写
    roseduan
        14
    roseduan  
    OP
       188 天前
    @dongcidaci 哈哈,折腾下
    A01514035
        15
    A01514035  
       188 天前
    那几篇设计与实现的设计文章哪里可以看啊,想看看技术原理
    roseduan
        16
    roseduan  
    OP
       188 天前
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4415 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 42ms · UTC 08:37 · PVG 16:37 · LAX 01:37 · JFK 04:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.