1K 行 C 写了 3 年,这是我从业以来写过的最烧脑的代码!

2018 年 1 月 23 日
 begeekmyfriend
就这么一个数据结构玩意儿,B+树磁盘存储 CRUD: https://github.com/begeekmyfriend/bplustree

从 2014 年 9 月第一次提交了内存版本实现,到 2018 年 1 月的磁盘版本,总共(坚持)提交了近 200 次。。。

我已经没有力气去说明这三年都迭代了些什么,总之取得了这样的性能(视机器而定)

100W 插入——~3s
100W 删除——~3s
1KW 插入——<30s
1KW 删除——<30s
1 亿插入——<5min
1 亿删除——<5min
10 亿插入——~45min
10 亿删除——~45min

好吧,1 billion 那是我意淫的,我等不起这么多时间。。。读性能就不用列了吧,B+树你懂的

老实说 3 年前我就想写一个 DB,SQL 那种,但光一个 B+树耗了我 3 年最好的时光。我承认不是天才,3 年的迭代都是我犯过的浑与错误,一直坚持到现在。我以为与其写一个各方面都平庸的成品,不如写一个尽量做到极致的 demo,代码量基本维持在 1K 行。好歹也累积了 300+stars 了,感谢用户们的认可。

这种迭代是烧脑的,也是痛苦的。每一次对结构体的压榨,都要牵动数百行源文件的更改,有时候一个提交意味着一整个下午,我的大脑长时间处于马拉松选手泡在 20~30 公里处的感觉,相信不少同行都有过这种体验。。。

不多说了,大家认为有何改进的地方,欢迎交流~
21844 次点击
所在节点    程序员
131 条回复
shaco
2018 年 1 月 24 日
三年坚持一个 DEMO,值得尊敬!!
skadi
2018 年 1 月 24 日
@begeekmyfriend 具体的没测,但是高效肯定能做到啊.
soli
2018 年 1 月 24 日
@begeekmyfriend

回复 #26 楼:

不需要公平哈。
至少 Redis、MySQL 熟悉的人比较多,有个对比的话,比较容易在技术选型的时候做取舍。
kylix
2018 年 1 月 24 日
楼主精神可嘉,顶一下!
jyf
2018 年 1 月 24 日
如果是 kv 的话 可以考虑跟同领域的对比 也不一定非得是 sql 嘛 比如 sphia/wired tiger
Em5O7B1JGfjQnBry
2018 年 1 月 24 日
本来不想说的,,,看到 append 的内容,你是可以试着实现一下并发的 B+tree,并且不再是一个独立的数据结构,而是作为整个带事务的数据库的一部分,就知道为什么不实现删除操作也是合理的了。
begeekmyfriend
2018 年 1 月 24 日
@svenFeng 删除和插入本质都是一样的写操作而已,怎么并发就不能实现了?
hugee
2018 年 1 月 24 日
大师
Em5O7B1JGfjQnBry
2018 年 1 月 24 日
@begeekmyfriend 不是不能,而是考虑到性能和删除会引发一系列问题,代价太大完全不合算的,你可以看看 B-link tree,并发 B+树的一种变种,说不定就能理解这种权衡了
jsfaint
2018 年 1 月 24 日
给楼主点赞!
ahonn
2018 年 1 月 24 日
牛,虽然看不太懂。但是这个 1k 行代码能写 3 年就已经很了不起了。专研精神 Max
frend94
2018 年 1 月 24 日
看了 lzGitHub,大佬哇
begeekmyfriend
2018 年 1 月 24 日
@svenFeng 粗略浏览了一下 B-link,传说中的分布式索引?有文章证明了插入和查询线程之间的并发正确性,那是因为插入只会分裂新的节点,新分裂的节点不存在引用关系,故而可以避免竞态。而删除则会导致合并,对于已存在引用关系的节点,则必然导致竞态。故而只能用全局锁,对每一个 CRUD 操作加锁,就会损失性能,是这个意思吧?我很好奇如果没有删除,那么废弃的 key 怎么处理?
begeekmyfriend
2018 年 1 月 24 日
@svenFeng 对于我目前实现的 B+树来说,实现插入 /查询的并发并非什么难事,我一共只用到 MIN_CACHE_NUM=5 个内存映射 node cache,对每一个 cache 加锁就可以了。
fcten
2018 年 1 月 24 日
@begeekmyfriend 给 cache 加锁就是全局锁,插入、查询不应该使用全局锁
begeekmyfriend
2018 年 1 月 24 日
@fcten 不是吧,一个 cache 对应一个 node 啊,只是在操作内部引用 cache 的时候才上锁。全局锁指的是整个 tree 用一把锁,这才是对 CRUD 操作上锁。
begeekmyfriend
2018 年 1 月 24 日
@fcten 不同 cache 对应的 node 如果不存在引用关系,那么就不存在竞态问题和互斥处理
fcten
2018 年 1 月 24 日
@begeekmyfriend 你不是说只有 5 个 cache 吗,那就是对应 5 个锁了?我不清楚你的具体实现,你这样能做到 5 个以上的并发吗?
fcten
2018 年 1 月 24 日
@begeekmyfriend 而且,你的 node 对应了很多记录吧。理论上最优的话应该是操作某个记录就只给这个记录加锁。对整个 block 加锁会锁住很多无关的记录
begeekmyfriend
2018 年 1 月 24 日
@fcten
1、cache 数目跟线程数目有关系吗? 1W 个线程引用 cache A,只会用一把锁互斥啊
2、cache A 的锁又不会给 cache B 上锁,这在分裂新节点情况下是不存在竞态的。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://v2ex.ih06.com/t/425258

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX