beansdb 卷土重来

2010-12-23 18:57:06

距上次发布 beansdb-0.3.0 以来, 又过了一年. 经过一年的线上运营锤炼, 它一直在不断改进中, 到现在已经有了非常大的变化, 下面简单描述一下:

完全放弃了ToykoCabinet 作为存储引擎, 它在数据的可靠性, 一致性, 以及大数据量下的性能有不少问题, 已经不能满足 beansdb 对数据存储的需求. 于是重新实现了一种基于日志结构的存储引擎 Bitcask,  借鉴自 Riak 项目的一份设计文档: http://downloads.basho.com/papers/bitcask-intro.pdf

Bitcask 有以下优点: 读写低时延, 高写入吞吐量, 能处理大规模数据集而性能不会显著下降, 数据持久化更好, 不用担心crash会导致数据丢失, 通过简单的rsync就能在线备份数据, 还能恢复被错误覆盖的数据.算法简单, 代码容易维护和调优, 在大数据量和高负载下的性能容易估计.

Bitcask 也有缺点, 它要求所有key信息全部放入内存, 在启动时一次性载入. 这对内存索引的效率提出了非常高的要求. beansdb中改进的HashTree有更好的空间效率, 它根据key的特点进行了重新编码, 大大降低了空间消耗, 每条记录平均只需20字节, 其中包括key, 版本,hash, 位置等信息, 这样一台8G内存的服务器可以存储 4亿条记录.如果记录平均大小为1k的文本, 则能存 400G, 如果是平均大小为100k的图片, 则能存40T.

启动时间也是Bitcask算法的缺点, 目前在一分钟大概能载入5千万条记录的索引, 还有进一步优化的空间.如果是意外crash后的重启, 时间会稍微长一点, 视数据量的大小而定, 一般也不会超过10分钟.

日志结构存储的另一个问题是会有空洞, beansdb 支持外部控制的在线垃圾回收过程, 可以安排在夜里进行.通常在硬盘不是太紧张的情况下, 几个月进行一次垃圾回收就可以了. 

之前网络层采用的是memcached的代码, 它使用libevent, 每个连接是跟固定的线程绑定的,在存储引擎中使用这种线程模型容易发生阻塞, 磁盘IO操作阻塞当前线程进而阻塞了其它连接的网络IO,因而直接基于epoll/kqueue 实现 leader/follower 模式的线程池, 响应时间会更好, 尤其是在并发访问比较高的时候.

为了简化维护, 在部署beansdb时增加了一层 proxy, 它是用 go 实现的, 会根据后端存储节点的数据情况自动做数据路由和负载均衡.proxy 时无状态的, 可以部署多台开实现扩容和HA. 添加新节点时只要改一下proxy的配置, 而数据迁移时无需更改任何配置.

目前我们部署了两个实例, 一个用来存文本数据, 共有13.3亿条记录, 总数据量为 2.8T, 分散在 8 个节点的 10 块SATA盘上, qps 为 160, 99% 的时间在 70ms 以内.

另外一个实例用来存储图片和单曲, 共有 7.5 亿, 数据量为 22T, 分散在 17 个节点的 约 50 块硬盘上,  qps 为 180, 99% 时间在 300 ms 以内.

目前代码和文档还没有同步更新到 beansdb.googlecode.com 上去, 近期会进行完善. 有兴趣的同学, 可以先拿一份最新的代码去尝尝鲜: http://beansdb.googlecode.com/files/beansdb-0.5.3.tar.gz

提前祝大家圣诞快乐, 元旦快乐, 新年快乐, 还有情人节更快乐~

Update: 已经更新到 0.5.3, 修正了几个代码编译问题.

 - Davies

2010-12-23 18:58:34 totty (白天敲键盘，晚上弹钢琴。)

学习了！

2010-12-23 18:59:53 Bear (^O^)

沙发，赞！

2010-12-23 19:02:18 Davies (hacking@DB)

你们手好快, 刚修正了下载连接.

2010-12-23 19:02:30 放开那个西红柿 (童话还不够美好。)

学习了。

2010-12-23 19:39:17 J (Done is better than perfect.)

学习了

2010-12-23 19:45:41 Sunjoy

顶+学习！

2010-12-23 20:04:49 fangy (I dreamed a dream)

顶

2010-12-23 20:13:04 碧海潮生 (无人相无我相)

牛逼我们也在用riak

2010-12-23 20:14:32 uitony (5→10)

国庆节快乐

2010-12-23 20:27:19 flex (提高效率)

我顶~~刚刚在moosefs的发布页面看到你的名字~

2010-12-23 20:41:41 Davies (hacking@DB)

同一台上测试:
$ beansdb -d
$ memstorm -s boromir:7900 -n 1000000 -k 10 -l 100

----
Num of Records : 1000000
Non-Blocking IO : 0
TCP No-Delay : 0

Successful [SET] : 1000000
Failed [SET] : 0
Total Time [SET] : 51.77594s
Average Time [SET] : 0.00005s

Successful [GET] : 1000000
Failed [GET] : 0
Total Time [GET] : 40.93667s
Average Time [GET] : 0.00004s

平均 2w qps, 写入比读稍微慢一点

----

测试中的top, beansdb CPU占用率 56% 左右, memstorm 36%

top - 20:33:52 up 22 days, 1:00, 3 users, load average: 8.51, 7.51, 7.15
Tasks: 309 total, 10 running, 289 sleeping, 1 stopped, 9 zombie
Cpu(s): 55.9%us, 12.8%sy, 0.0%ni, 12.9%id, 10.3%wa, 0.5%hi, 7.6%si, 0.0%st
Mem: 16528604k total, 16419228k used, 109376k free, 95292k buffers
Swap: 2097144k total, 840k used, 2096304k free, 7816092k cached

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
24804 davies 15 0 317m 92m 708 S 56 0.6 0:35.99 ./beansdb
26114 davies 15 0 10592 796 640 S 36 0.0 0:19.44 memstorm -s boromir:7900 -n 1000000 -k 10 -l 100

2010-12-23 20:42:22 Davies (hacking@DB)

对比一下 memcached 的, 它更快写入 2.5w, 读取 3.3万.

也是应该的, 比较beansdb 是持久存储.

其实这种测试没多大意义,
现在的CPU已经足够快了, 一般很难碰到它的瓶颈,
首先是IO, 然后是网络.

----
Num of Records : 100000
Non-Blocking IO : 0
TCP No-Delay : 0

Successful [SET] : 100000
Failed [SET] : 0
Total Time [SET] : 3.87546s
Average Time [SET] : 0.00004s

Successful [GET] : 100000
Failed [GET] : 0
Total Time [GET] : 2.97511s
Average Time [GET] : 0.00003s
----

2010-12-23 20:45:36 Davies (hacking@DB)

@碧海潮生, Riak 是Erlang 实现的, 当时找 Bitcask 的实现代码没找到. 担心Erlang 实现的内存效率不太好, 影响单节点的容量上限. 有时间了再学习一下.

2010-12-23 20:46:48 Davies (hacking@DB)

@flex, 1.6.19 基本上把我们的补丁都合并了, 很赞. moosefs 的一个负责人还特意给我发了封通知邮件, 很欣慰.

2010-12-23 20:59:26 胖子 (Phase One, preparation)

目前的速度已经很不错了，赞！

2010-12-23 21:28:49 11月的心情

支持一下，嘿嘿

2010-12-23 21:29:28 mhb (1kg. 爱聚)

果然如你所说。。圣诞大礼啊

2010-12-23 21:43:17 雾都孤狗 (洗洗睡了)

有机会尝尝鲜

2010-12-24 00:31:26 WillYang

赞啊！
向前辈学习！

2010-12-24 08:06:28 Ryutlis (Merry Xman)

太赞了！

2010-12-24 08:57:32 mysoko (事情搞复杂了，就是还没搞懂)

太赞了！！学习!!!

2010-12-24 11:30:50 23号 (http://twitter.com/number23_cn)

2010-12-24 11:37:36 happy九拍 (低调的喝水)

给力，学习了

2010-12-24 12:49:11 [已注销]

的确很赞！我们这边也打算用beansdb来做储存。之前的tc的那个就很好了，这个更赞

2010-12-24 13:13:02 半梦半醒

很给力，学习！

2010-12-24 13:16:46 Yingfeng

赞放弃TC

2010-12-24 13:20:13 digwa

good ，比较给力

2010-12-24 13:20:51 pyleaf (2011践行自己的想法)

什么时候把nodejs也加进去

2010-12-24 13:24:38 Nowgoo (候补绿毛水怪)

强力mark

2010-12-24 13:31:24 hk

学习

2010-12-24 13:32:23 Brightman

没太明白这句话意思“之前网络层采用的是memcached的代码, 它使用libevent, 每个连接是跟固定的线程绑定的,在存储引擎中使用这种线程模型容易发生阻塞, 磁盘IO操作阻塞当前线程进而阻塞了其它连接的网络IO ”
beansdb 工作线程是多线程还是单线程？

2010-12-24 13:33:30 Tsung W. (Read-Only)

大侠能不能把代码放github上管理？

2010-12-24 14:02:39 kula (time)

用golang实现的proxy开源吗?
能不能简单介绍下这个, 以及golang的性能如何

2010-12-24 14:09:32 Brightman

看了《Inside beansdb》，worker是多线程，另外问一下：
高可用：通过多个可读写的用于备份实现高可用
beansdb是否实现了Dynamo中的RW节点数量配置？在那部分代码中实现的？谢谢

2010-12-24 14:32:45 张万凯

event-driven是移植Redis代码的，不错

2010-12-24 15:13:00 lanye

定

2010-12-24 15:16:33 Skiyo (苦逼矮穷丑挨踢攻城湿)

2010-12-24 15:36:11 Davies (hacking@DB)

@Brightman: beansdb 是多线程, leader/follower pattern 的线程池, 可以找到相关论文.

@Tsung W: github 是好东西, 可还没习惯怎么用, 公司内部基本上是SVN.
现在的策略是主要内部的SVN, 等稳定了再同不到外部的github或者 google code等.

2010-12-24 15:40:26 Davies (hacking@DB)

@kula, proxy 也会开源的, 还不确定是独立项目, 或者放beansdb代码库内部.
目前 proxy 单核可以处理 1500 qps 左右, 在现在普遍的多核服务器上性能问题不大.

<Inside Beansdb> 文档比较老了, 需要更新, 但核心架构基本没变. R/W 的配置可以在proxy 处实现, 对于不同的应用, 可以通过部署不同的proxy来满足.

2010-12-24 15:43:23 Davies (hacking@DB)

@Wankai Zhang: epoll/kqueue 那部是来自 Redis, 它的确封装得很简单, 非常好.

之前还尝试过用libev, 但它跟libevent一样, 为了照顾 select, 接口很死板, 没法实现或者说没法很好地实现leader/follower 模式.

2010-12-24 16:21:55 Yingfeng

riak有bitcask的c代码阿

关于并发pattern， half-async/half-sync 更清晰，而且context switch应当会小点

2010-12-24 16:30:32 Davies (hacking@DB)

@Yingfeng:

当初在Riak 发布在github 中的代码没找到 bitcask 的实现, 惭愧...

leader/follower 的 context switch 是比 half-async/half-sync 小的, 一个线程拿到事件通知后就可以立即处理, 不需要context switch, 在响应时间上可以更每连接一个线程相比.

这是它的主要优势, 而且不需要一个队列来管理请求, 在我的实现中, 只需要一个锁就可以了. 还可以进一步优化, 对于某些不会block的事件, 直接在leader中处理完而不释放控制权, 进一步减少多个事件之间的context switch.

2010-12-24 16:56:29 海黎 (2011年你要坚强!)

mark~

2010-12-24 18:45:39 au9ustine (膜拜DEK大神……)

mark~~

2010-12-24 18:50:49 fcicq (专业数据结构算法设计)

等排序索引也可以这样改头换面卷土重来的时候就更有趣了.

2010-12-24 20:20:06 dodge (昨日不可追，明日不可留)

好东西

2010-12-24 21:00:57 不合时宜。 (我是一病人啊)

GEEK什么的我很崇拜

2010-12-25 03:57:11 鲤鱼先生 (太猖狂，太冲动)

很给力，先MARK。

2010-12-25 15:24:51 liuxinglanyue (liuxinglanyue)

mark

2010-12-25 18:22:53 张万凯

@davies 呵呵，前几天去豆瓣面试的时候，洪强宁还问我怎么移植的Redis的event代码来着。

2010-12-26 22:31:20 摇尾巴的狼 (Wanna be a freak!)

关注一下你，呵呵。我下学期的毕设选择了NoSQL这个方向，希望能在您这里学到东西哈~

2010-12-27 12:29:27 泡沫

一直做手机开发，现在要转服务器，满头雾水。有什么好的入门级书籍看看吗？

2010-12-28 15:15:15 refactor (点点点点 i)

bitcask在merge的时候，内存中hashtree的value_pos不再指向新data file正确的位置，这个是怎么处理的呢？

2010-12-28 15:19:36 Davies (hacking@DB)

merge 的时候, 生产一个小的hash tree, 对应新生产的数据文件, 一个数据文件 merge 完成后, 会锁住写, 并这个小的hash tree的内容更新到主体 hash tree 中, 这个过程是MlgN 复杂度的内存操作, N是一个bucket 的记录数, M 是当前数据文件的记录数, M 一般在1M以内, 更新应该能在 1s 左右的时间内完成.

2010-12-28 16:16:23 refactor (点点点点 i)

那在这1s的合并时间内，该数据文件中的数据记录是可访问的吧。（例如对更新后的记录从新数据文件获取，还没更新的继续访问旧文件，是这样的吧）
另外您说的bucket就是指什么啊？

2010-12-28 16:27:55 Davies (hacking@DB)

这里的bucket 是指 bitcask 中一个数据文件, 最大 2G. 在更新期间读也不可以, 会出错. 可以在proxy处通过读其它节点解决. 这个部分可能还会改善.

2010-12-28 16:53:39 iammutex (我就是你擦肩而过的那个人)

不知道merge操作具体是如何做的，是遍历hash表还是扫数据文件，感觉代价应该都不小。
merge生成新数据文件需要空间存储。最坏的情况下是不是merge前的数据文件和merge后的数据文件会同时存在，在最后一个新文件生成时才能删除旧的数据文件，这时候机器磁盘的空间利用率是否会永远不超过50％？

2010-12-28 16:54:41 refactor (点点点点 i)

更新期间写会出错比较好理解，但是更新期间读为什么会出错：更新过的hash tree记录（entry）将指向新的数据文件，还没来得急更新的继续从老数据文件中读取数据。会在哪里出错呢？

2010-12-28 17:08:41 Davies (hacking@DB)

@iammutex: merge 是单线程顺序读写IO, 代价不算大. merge 的单元是一个数据文件, 最大2G, merge 过程中不需要大量剩余空间.

@refactor: 数据文件是按照顺序号访问的, 现在不可以同时访问两个数据文件(merge前和后), 那么在更新hash tree 的 pos 期间, 肯定有一部分读会出错, 如果这个过程足够短且上层能容错, 还是可以接受的.

2010-12-28 19:35:59 iammutex (我就是你擦肩而过的那个人)

@Davies 也就是说merge操作的单元是单个数据文件？（一个数据文件merge后生成一个较小的新文件，然后再merge下一个，生成新的，这样？）那对于同一个key可能存在于多个文件中的情况，这个冗余能通过merge消除吗？还是说在写的时候会有特殊操作让这种冗余不会出现。
谢谢回复～

2010-12-28 20:43:48 Davies (hacking@DB)

@iammutex: 一个 key 只会存在与某一个数据文件中, 在merge时,扫描到的key, 如果其在hash tree(全局的)的pos并不是指向当前文件, 就说明无效了, merge 时被跳过.

2010-12-29 16:05:36 iammutex (我就是你擦肩而过的那个人)

@Davies 我之前想偏了，一直纠结到是扫数据文件还是遍历hash表，原来是扫数据文件加查询hash表，确实这样开销不会大，也不会有太大的冗余数据存在。多谢指教～

2010-12-30 16:37:54 Brightman

@Davies beansdb ppt中讲到的同步(HashTree)是指A主机完全冗余备份A'主机？
因为Key本身是会写到多个bucket中去，已经起到了冗余备份作用，这样理解正确么？

2010-12-30 18:59:58 Davies (hacking@DB)

@Brightman：对，但是节点不需要完全对称。正常的写操作已经保证有多份，用Hash Tree来同步，是为了解决异常情况下导致的数据缺失或者不一致。

2011-01-01 13:36:24 imonyse (Less is More)

@Davies, 这个放出的0.5.2版有点小问题，在我的Mac上链接时出错：
　　　　Undefined symbols:
　　　　 "_aeApiUpdateEvent", referenced from:
　　　　 _update_event in beansdb-thread.o
　　　　ld: symbol(s) not found
　　　　
经检查，问题出在thread.c里的update_event()函数调用了aeApiUpdateEvent()，但在ae_kqueue.c和ae_select.c里，都没有aeApiUpdateEvent的实现。那么，在没有epoll的系统上，应该都会出这个问题。　　　　
　　　　$ diff -u ae_kqueue_orig.c ae_kqueue.c
　　　　--- ae_kqueue_orig.c 2011-01-01 11:46:07.000000000 +0800
　　　　+++ ae_kqueue.c 2011-01-01 11:41:10.000000000 +0800
　　　　@@ -44,6 +44,10 @@
　　　　 return 0;
　　　　 }
　　　　
　　　　+static int aeApiUpdateEvent(EventLoop *eventLoop, int fd, int mask) {
　　　　+ return aeApiAddEvent(eventLoop, fd, mask);
　　　　+}
　　　　+
　　　　 static int aeApiDelEvent(EventLoop *eventLoop, int fd) {
　　　　 aeApiState *state = eventLoop->apidata;
　　　　 struct kevent ke;

2011-01-01 14:16:51 Davies (hacking@DB)

多谢 coderweasel, 已经修正. 最近忘了在 Mac 上测试. 节后重新发布一个版本.

2011-01-03 17:12:40 天使大哥

前几天刚把beansdb的老代码看了个遍，没想到这要更新了～

2011-01-13 11:09:57 Davies (hacking@DB)

已经发布了 0.5.3, 修正了几处编译问题.

2011-01-13 14:11:48 Skyet (成熟的开始...)

mark

2011-01-19 11:58:54 zhuowater (悄悄地来到这个地方)

有上100亿条小块记录，每个大概40字节，需要多少节点？适合海量存储，高写入高读取，但低并发的环境吗？

2011-01-19 17:10:38 Davies (hacking@DB)

100亿的话, 索引全部内存, 大概需要 10G * 20 = 200G, 一节点 32G内存的话, 大概需要10个节点, 如果在存2-3份, 就需要更多. 硬盘的消耗比较少.

能处理高并发, 大概什么量级? 读的瓶颈估计在硬盘.

对于这么小的记录, 用key-value存储不是很合适(每个key的开销偏大), 用mysql+sharding 等来实现可能更好一些.

2011-01-26 21:38:03 [已注销]

遇学术界高人，请教

2011-03-10 10:19:17 AKun

在LZ的介绍Inside BeansDB里：
HashTree 实现提到
 时间效率
 每秒插入近百万条
这个是指什么数据插入近百万条？
从楼主各个性能测试的数据里单机性能应该在2~3wqps，17个节点怎么就能达到“近百万条”了？

2011-03-10 10:34:40 Davies (hacking@DB)

在启动的时候, 需要扫描Hint文件, 将索引信息放入Hash Tree, 这个时候到插入速度有每秒近百万条.

2011-03-16 14:39:59 甘立平 (http://www.42ic.com)

存储1k-20K左右的文本数据与mysql比是否有优势，主要是RSS条目的内容。10w条左右。

2011-03-16 15:29:42 Davies (hacking@DB)

10w 条的话, 还是用mysql吧. beansdb 的主要优势是大数据量的可扩展性等.

2011-05-16 17:15:04 binary war

Davies,往beansdb添加存储节点时，数据迁移是如何进行的？
选择那些数据来迁移，如何保证beansdb不停机的情况下完成迁移？

2011-07-13 23:06:48 hoterran (Go, Boston Celtics)

网络库这块怎么和redis一样？

2011-08-31 18:06:53 子江 (ZT哥从此不再荡漾！)

最近还更新不？就卡在 0.5.3 么？

2011-08-31 23:52:48 iammutex (我就是你擦肩而过的那个人)

@hoterran 嗯，网络IO是和Redis一样，事件具体处理基本上和Memcached一样～

2011-09-06 20:29:07 rezilla (i ain't not no undummy)

太新潮了，go都用上了能介绍下特性吗？

2011-09-07 15:40:30 Davies (hacking@DB)

目前正在内侧少量改进的 0.5.4, 稍后会打包放出。

2011-09-07 17:03:13 rezilla (i ain't not no undummy)

赞期待

2011-09-21 15:15:23 王xx

hi,Davie,想请教4个问题，问题有点多，不好意思啊：

1.使用beansdb的话，先需要估测上限的容量，比如256个bucket，再开始根据256，以及每bucket的备份数N=3，以及现有比如20个节点，来决定每个节点存256个bucket中的哪几个，最终形成一张bucket和节点之间的映射关系。以上描述的对吗？是不是在生产运行过程中，不可能新产生一个bucket，都是预先规划好的？那上限空间不够用了怎么办呢？

2.proxy中可能会根据具体业务的逻辑id，把具体业务的key，通过sharding映射到具体的bucket上？然后再根据bucket和节点的映射表，找到对应的3台节点（假设N=3），再根据负载的情况，选择1台（假设W=1）写入该节点，写入的过程是这样吗？但是另外2台就得靠定时的同步操作来保持一致了吗？还是一般都设置W=N=3？使得每次写入的过程中，就把几个节点都写入了。

3.关于每个节点上的hashtree，假设整个beansdb节点群中一共256个bucket，但a节点上只有4个bucket，是不是a节点的hashtree只有这4个bucket的详细的bitcask信息，其他252个位置是空的。因此单节点的内存容量限制了该节点能存多少条记录，并不限制整体节点群中的存储量，是吗？

4.另外在定时的sync的时候，是不是也只是2个节点间，如果有重叠的bucket，才会同步？

> 我来回应

> Davies的日记