V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
roy2220
V2EX  ›  分享创造

用 go 实现一个简单的 KV 存储

  •  1
     
  •   roy2220 · 2020-03-04 19:07:44 +08:00 · 2760 次点击
    这是一个创建于 1485 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://github.com/roy2220/plainkv (目前仅支持 Linux )

    实现思路:

    10 条回复    2020-03-06 20:45:23 +08:00
    pkwenda
        1
    pkwenda  
       2020-03-04 23:15:38 +08:00
    收藏学习
    Comdex
        2
    Comdex  
       2020-03-05 16:45:13 +08:00
    大佬能不能写写实现细节
    ClarkAbe
        3
    ClarkAbe  
       2020-03-05 17:15:34 +08:00 via iPhone
    star 了,测试了一下速度挺快的,而且内存的内心毫无波澜,实现方式应该是空间换时间和内存
    roy2220
        4
    roy2220  
    OP
       2020-03-05 17:21:35 +08:00   ❤️ 1
    @Comdex 哈哈,主要是我太懒了,感觉说话(表达)比写代码还要累。。。
    实现细节还蛮多的,先说说哈希表的部分,普通的哈希表有一个致命的缺陷:当 numKeys/numBuckets 达到某个阀值( load factor )的时候,需要 rehash,这个操作会瞬间耗费大量的 cpu (而且哈希表构建在磁盘上的话,还要算上 io )。有没有办法把这个 rehash 的过程切分成一小步一小步,分摊到每次插入的操作上?这个就是<线性哈希>算法解决的问题。虽然 rehash 的过程被分摊了,但是 bucket 数组的空间还是需要连续的(不然没办法根据 hashcode 定位了),一般会采用“翻倍”的策略,让最大可用 bucket 的数量保持在 2^N。如果考虑存储海量的数据,bucket 数组空间翻倍(分配新的空间,拷贝旧数据到新空间,释放旧的空间)也是一个耗 cpu 和 io 的点。为了解决这个问题我把 bucket 数组切成固定长度的段( segment,64kb ),段与段之间不需要空间上的连续,然后额外维护一张段表(需要空间上连续)指向这些散落的段。这样就把 bucket 数组空间翻倍就弱化为段表空间翻倍,大大降低了影响。
    firemiles
        5
    firemiles  
       2020-03-05 17:32:48 +08:00
    持久化是用什么格式,我看用了你自己写的 fsm
    roy2220
        6
    roy2220  
    OP
       2020-03-05 17:37:34 +08:00
    @Comdex
    @ClarkAbe 再说说文件空间管理的部分,为了把问题分而治之,我做一个“文件空间分配器”的抽象,只负责分配可用的文件空间(实际上就是一个文件偏移),充当最底层的存储层。分配算法上借鉴了现代内存分配器的思想,大块空间和小块空间分开治理,大块空间(>=64kb )使用了 buddy 分配算法(用位图做标记,用红黑树做空闲块索引)。小块内存用 freelist 管理(从 buddy 上分配一大块,挂到 freelist 上按需切割),还做了一些小块内存释放后和临近的小块合并的优化,用了侵入式循环双链表作为小块内存的 overhead,把所有空闲 or 非空闲的块串在一起,实现时间复杂度 O(1)的合并。但这些思路都是传统内存分配器上借鉴的,可能不太适用在文件空间的分配上,所以这个“文件空间分配器”还有很大的改进空间
    roy2220
        7
    roy2220  
    OP
       2020-03-05 17:40:14 +08:00
    @firemiles dei,自己实现的一个(比较 naive 的)存储层。详情看楼上,刚刚回复
    nicoljiang
        9
    nicoljiang  
       2020-03-06 17:10:01 +08:00
    很硬核,很厉害~
    但是挑个刺:阀值 ⇢ 阈值
    roy2220
        10
    roy2220  
    OP
       2020-03-06 20:45:23 +08:00 via iPhone
    @nicoljiang 😂在关公面前耍剃刀了,能做出 dogedoge 是真的强👍🏻
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3347 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 10:44 · PVG 18:44 · LAX 03:44 · JFK 06:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.