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

[roy2220]

https://github.com/roy2220/plainkv （目前仅支持 Linux ）

实现思路：

• 使用文件空间分配器
• 在文件上构建一张的巨大的线性哈希表

[pkwenda]

收藏学习

[Comdex]

大佬能不能写写实现细节

[ClarkAbe]

star 了，测试了一下速度挺快的，而且内存的内心毫无波澜，实现方式应该是空间换时间和内存

[roy2220]

@Comdex 哈哈，主要是我太懒了，感觉说话（表达）比写代码还要累。。。
实现细节还蛮多的，先说说哈希表的部分，普通的哈希表有一个致命的缺陷：当 numKeys/numBuckets 达到某个阀值（ load factor ）的时候，需要 rehash，这个操作会瞬间耗费大量的 cpu （而且哈希表构建在磁盘上的话，还要算上 io ）。有没有办法把这个 rehash 的过程切分成一小步一小步，分摊到每次插入的操作上？这个就是<线性哈希>算法解决的问题。虽然 rehash 的过程被分摊了，但是 bucket 数组的空间还是需要连续的（不然没办法根据 hashcode 定位了），一般会采用“翻倍”的策略，让最大可用 bucket 的数量保持在 2^N。如果考虑存储海量的数据，bucket 数组空间翻倍（分配新的空间，拷贝旧数据到新空间，释放旧的空间）也是一个耗 cpu 和 io 的点。为了解决这个问题我把 bucket 数组切成固定长度的段（ segment，64kb ），段与段之间不需要空间上的连续，然后额外维护一张段表（需要空间上连续）指向这些散落的段。这样就把 bucket 数组空间翻倍就弱化为段表空间翻倍，大大降低了影响。

[firemiles]

持久化是用什么格式，我看用了你自己写的 fsm

[roy2220]

@Comdex
@ClarkAbe 再说说文件空间管理的部分，为了把问题分而治之，我做一个“文件空间分配器”的抽象，只负责分配可用的文件空间（实际上就是一个文件偏移），充当最底层的存储层。分配算法上借鉴了现代内存分配器的思想，大块空间和小块空间分开治理，大块空间（>=64kb ）使用了 buddy 分配算法（用位图做标记，用红黑树做空闲块索引）。小块内存用 freelist 管理（从 buddy 上分配一大块，挂到 freelist 上按需切割），还做了一些小块内存释放后和临近的小块合并的优化，用了侵入式循环双链表作为小块内存的 overhead，把所有空闲 or 非空闲的块串在一起，实现时间复杂度 O(1)的合并。但这些思路都是传统内存分配器上借鉴的，可能不太适用在文件空间的分配上，所以这个“文件空间分配器”还有很大的改进空间

[roy2220]

@firemiles dei，自己实现的一个（比较 naive 的）存储层。详情看楼上，刚刚回复

[nicoljiang]

很硬核，很厉害～
但是挑个刺：阀值 ⇢ 阈值

[roy2220]

@nicoljiang 😂在关公面前耍剃刀了，能做出 dogedoge 是真的强👍🏻