猜解leveldb写性能

Time: 四月 17, 2012
Category: storage

如题,猜测。

我们知道leveldb的很出色,随机读写的性能可以分别达到 164,000 ops/sec 和 129,000 ops/sec,这是官方的Benchmarks数据。

leveldb最关键的核心技术在于基于level思想的sstable文件compact策略,因为这种设计,大大的改善了Random Writes的性能。levledb的memtable/immutable是一个skiplist链表,而skiplist insert的时间复杂度是O(logn),也就是说,insert的时间复杂度是随着问题规模的增长而线性上升的,呵呵,不知到大家注意到没。

高性能kv的实现现在跑的比较火的就数lsm-tree,主要的思路就是先在内存里cache到某个阀值然后dump到磁盘,再由其他线程或者进程来进行compact操作,于是首先会引出的第一个问题是:

1、sstable文件的管理以及如何执行compact的操作,这个地方直接影响到读性能,这也是为什么采用lsm-tree的key-value存储引擎读性能一直提升不上去的原因,尤其是一些老旧数据的检索。

我当初也主要没考虑过在skiplist这一部分做过优化,毕竟skiplist主要还是内存操作。

但是leveldb的作者可不是这么想的,这种想法可真是so easy但是又很难引起大家的注意:就是靠缩小问题的规模来达到提升insert性能的目的。我今晚在食堂吃饭,想到这点的时候就没差点笑喷了,有意思,哈哈 ^_^

但是如果这样做的话会导致sstable文件会非常的多,而且会产生大量的小文件,所以如果没有一套非常优秀的compact策略的话只有傻子才会这样做,我当初在研究lsm论文后,采用的思想是直接dump大sstable文件,sstable文件量小,容易管理,查询性能也比较好,当然后来也意识到很多问题,这是后话了。

所以Jeff Dean和Sanjay Ghemawat设计了一种基于level的compact策略,然后让memtable达到一个非常小的阀值后直接dump成小文件,由后台进程来进行compact管理。memtable的阀值由 write_buffer_size(include/leveldb/options.h)控制,默认是4mb左右,假设key是20bytes,value是80bytes,这个阀值可以容纳4w个entries左右。

根据skiplist的查找时间复杂度O(logn),我在本机上做了一个简单的测试,主要计算随着规模的增长每随机插入一条数据的开销。

测试环境:

Date: Tue Apr 17 23:45:07 2012
CPU: 2 * Pentium(R) Dual-Core CPU T4400 @ 2.20GHz
CPUCache: 1024 KB
System: Centos Linux 2.6.32-220.el6.i686 #1 SMP Tue Dec 6 16:15:40 GMT 2011 i686 i686 i386 GNU/Linux

实际上只使用了一个CPU,测试结果

测试代码:https://github.com/pipul/coutune/tree/master/skiplist

很明显,随着skiplist的cardinality不断变大,插入每条数据的开销越来越多,不过当n趋向无穷大的时候,这种变化会渐趋不明显。而在刚开始的时候,insert开销抖增。所以,想要获得最好的random writes性能,skiplist的cardinality尽量控制到百万级别以下

2 comments to “猜解leveldb写性能”

  1. likun说道:

    你的研究方法很好,我以前研究东西就是随便看一下他的结论,但是没有像为什么是这样的结论,你的这篇文章让我体会很深。

    请问你的最后这一章图是用什么东西弄的?
    谢谢。

Leave a Comment