BeansDB的设计与实现


BeansDB 设计与实现 刘洪清 Davies@douban.com 2011/4/8 11年4月7日星期四 •需求 •设计 •实现 •回顾 11年4月7日星期四 产品需求 11年4月7日星期四 产品需求 •图片类应用 • 个人相册,群体相册(线上活动), 图片墙 • FM 11年4月7日星期四 产品需求 •图片类应用 • 个人相册,群体相册(线上活动), 图片墙 • FM •文本类应用 • 评论,日记,作品,博客 11年4月7日星期四 技术需求 11年4月7日星期四 技术需求 •存储大量小文件(字段) 11年4月7日星期四 技术需求 •存储大量小文件(字段) •可扩展性 11年4月7日星期四 技术需求 •存储大量小文件(字段) •可扩展性 •可靠性 11年4月7日星期四 技术需求 •存储大量小文件(字段) •可扩展性 •可靠性 •可用性 11年4月7日星期四 技术需求 •存储大量小文件(字段) •可扩展性 •可靠性 •可用性 •一致性 11年4月7日星期四 技术需求 •存储大量小文件(字段) •可扩展性 •可靠性 •可用性 •一致性 •低成本 11年4月7日星期四 两个原则 11年4月7日星期四 两个原则 •KISS 11年4月7日星期四 两个原则 •KISS 11年4月7日星期四 两个原则 •KISS •尽量复用开源方案 11年4月7日星期四 开源项目参考 11年4月7日星期四 开源项目参考 •MogileFS 11年4月7日星期四 开源项目参考 •MogileFS •Dynamo 11年4月7日星期四 开源项目参考 •MogileFS •Dynamo •Memcached 11年4月7日星期四 开源项目参考 •MogileFS •Dynamo •Memcached •Riak 11年4月7日星期四 初步方案 11年4月7日星期四 初步方案 •存储大量小文件 • key/value, get/set/delete • hash, bucket 11年4月7日星期四 初步方案 •存储大量小文件 • key/value, get/set/delete • hash, bucket •可扩展性 • 独立存储节点,独立数据目录 • bucket 扩展 11年4月7日星期四 Node1 Node2 Node3 Node4 set a get b Clients 初步方案 11年4月7日星期四 深入设计 11年4月7日星期四 深入设计 •可靠性 • 多机冗余(N=3) • 同步写(W=2), 依次读(R=1) 11年4月7日星期四 深入设计 •可靠性 • 多机冗余(N=3) • 同步写(W=2), 依次读(R=1) •一致性 • 最终一致性 • Hash Tree 同步 (外部脚本) • 冲突: 独立版本号+更新时间 11年4月7日星期四 Sync with HT Proxy 1 Node1 Node2 Node3 Node4 set a get b Clients 11年4月7日星期四 存储节点实现 11年4月7日星期四 存储节点实现 •数据存储引擎 • Key/Value, ACID(宽松) 11年4月7日星期四 存储节点实现 •数据存储引擎 • Key/Value, ACID(宽松) •网络协议 • memcache 协议 11年4月7日星期四 存储节点实现 •数据存储引擎 • Key/Value, ACID(宽松) •网络协议 • memcache 协议 •同步接口 • 哈希树 11年4月7日星期四 存储节点实现 •数据存储引擎 • Key/Value, ACID(宽松) •网络协议 • memcache 协议 •同步接口 • 哈希树 •线程模型 11年4月7日星期四 存储引擎 11年4月7日星期四 存储引擎 •TokyoCabinet • 简单, 轻量, 小数据时性能不错 • crash, 大数据量时性能不好 11年4月7日星期四 存储引擎 •TokyoCabinet • 简单, 轻量, 小数据时性能不错 • crash, 大数据量时性能不好 •BerkeleyDB • 过重, 存储稍大的文件性能不好 11年4月7日星期四 存储引擎 •TokyoCabinet • 简单, 轻量, 小数据时性能不错 • crash, 大数据量时性能不好 •BerkeleyDB • 过重, 存储稍大的文件性能不好 •Bitcask • 内存索引 + 日志结构数据文件 11年4月7日星期四 Bitcask 内存索引 数据格式 追加写入 hint 11年4月7日星期四 优化Bitcask 11年4月7日星期四 优化Bitcask •每bucket一个Bitcask 11年4月7日星期四 优化Bitcask •每bucket一个Bitcask •数据空间 • 256 对齐, 最多256个, 自动压缩 • 在线GC, 外部控制 11年4月7日星期四 优化Bitcask •每bucket一个Bitcask •数据空间 • 256 对齐, 最多256个, 自动压缩 • 在线GC, 外部控制 •启动时间 • hint 文件, QuickLZ L3压缩 • 多线程 11年4月7日星期四 Hash Tree 0 key1 key2 key3 key4 1 2 3 e f 0 Bucket 0 Key Version Hash Position Hash(Key) = 0x02f93fea Node Hash Count 0 1 Root 11年4月7日星期四 Hash Tree优化 11年4月7日星期四 Hash Tree优化 •Hash Table 11年4月7日星期四 Hash Tree优化 •Hash Table •Node, Item 连续存放 • {1}{16}{256} • {Size, Count, [{Ver, Hash, Pos, Key}, ....] • 128 个自动分裂 11年4月7日星期四 Hash Tree优化 •Hash Table •Node, Item 连续存放 • {1}{16}{256} • {Size, Count, [{Ver, Hash, Pos, Key}, ....] • 128 个自动分裂 •重新编码key • /topic/1234567/body=>{/topic/%d/body, 123} 11年4月7日星期四 同步过程 V1 V2 V-3V1 V2 Set Sync Set Delete V-3 Sync GC 节点 A 节点 B 客户端 时间Get V1 V2 11年4月7日星期四 网络协议 11年4月7日星期四 网络协议 •memcache 文本协议 • 复用memcached的网络协议层代码 • 有大量客户端可用 11年4月7日星期四 网络协议 •memcache 文本协议 • 复用memcached的网络协议层代码 • 有大量客户端可用 •适当扩展 • @fff, ?xxxx, flush_all • get_multi, set_multi, delete_multi 11年4月7日星期四 IO与多线程模型 11年4月7日星期四 IO与多线程模型 •并发与IO • 并发连接多, 并发请求少 • 异步网络IO, 同步磁盘IO 11年4月7日星期四 IO与多线程模型 •并发与IO • 并发连接多, 并发请求少 • 异步网络IO, 同步磁盘IO •多线程模型 • 连接/线程绑定 • 半同步/半异步 • leader/follower 11年4月7日星期四 Leader/Follower模型 Mutex try to lock unlock wait for event remove event fd do the work (blocking) Leader Follower 11年4月7日星期四 Proxy 实现 11年4月7日星期四 Proxy 实现 •Go 实现 • 易于实现高并发应用, 性能可接受 11年4月7日星期四 Proxy 实现 •Go 实现 • 易于实现高并发应用, 性能可接受 •自动路由 • 根据 Merkle Tree得到数据分布 • 更高可用性 11年4月7日星期四 Proxy 实现 •Go 实现 • 易于实现高并发应用, 性能可接受 •自动路由 • 根据 Merkle Tree得到数据分布 • 更高可用性 •负载均衡 • 减少IO慢的节点的请求量 11年4月7日星期四 版本历史 11年4月7日星期四 版本历史 •0.1, like MogileFS 2008.8 • WebDAV, inotify, sync, client 11年4月7日星期四 版本历史 •0.1, like MogileFS 2008.8 • WebDAV, inotify, sync, client •0.2, like TokyoTrant 2008.12 • TC, HTree, sync, mc client 11年4月7日星期四 版本历史 •0.1, like MogileFS 2008.8 • WebDAV, inotify, sync, client •0.2, like TokyoTrant 2008.12 • TC, HTree, sync, mc client •0.3, like memcachedb 2009.6 • HTree in TC, on Disk 11年4月7日星期四 版本历史(2) 11年4月7日星期四 版本历史(2) •0.4 2010.2 • proxy 11年4月7日星期四 版本历史(2) •0.4 2010.2 • proxy •0.5 reload 2010.10 • Bitcask, Leader/Follower 11年4月7日星期四 原型开发 11年4月7日星期四 原型开发 •原型开发 • 快速验证想法 11年4月7日星期四 原型开发 •原型开发 • 快速验证想法 •Python • Cython 扩展 11年4月7日星期四 原型开发 •原型开发 • 快速验证想法 •Python • Cython 扩展 •Go • cgo 扩展, 容易开发高并发应用 11年4月7日星期四 实际部署案例(1) 11年4月7日星期四 实际部署案例(1) •数据量 • 图片, 音频: 1k到20M • 310M x 3 = 930 M • 590G x 16 x 3 = 28T • 17 个节点, 约 50 块SATA硬盘 11年4月7日星期四 实际部署案例(1) •数据量 • 图片, 音频: 1k到20M • 310M x 3 = 930 M • 590G x 16 x 3 = 28T • 17 个节点, 约 50 块SATA硬盘 •性能: • 250 qps左右, 有CDN • Med/Avg/90%/99%: 16/29/69/232 ms 11年4月7日星期四 各节点数据分布 11年4月7日星期四 线上运行状态截图 (图片, mp3, 3亿) 11年4月7日星期四 11年4月7日星期四 实际部署案例(2) 11年4月7日星期四 实际部署案例(2) •数据量 • 文本字段: 100到100k • 550M x 3 = 1.65 B • 50G x 16 x 3 = 2.4T • 13 个节点, 约 13 块SATA硬盘 11年4月7日星期四 实际部署案例(2) •数据量 • 文本字段: 100到100k • 550M x 3 = 1.65 B • 50G x 16 x 3 = 2.4T • 13 个节点, 约 13 块SATA硬盘 •性能: • 200 qps左右, 有memcached作缓存 • Med/Avg/90%/99%: 1/14/15/104 ms 11年4月7日星期四 Thanks! Q/A ? 11年4月7日星期四 杭州站 · 2011年10月20日~22日 www.qconhangzhou.com(6月启动) QCon北京站官方网站和资料下载 www.qconbeijing.com
还剩81页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 1 人已下载

下载pdf

pdf贡献者

cameron6

贡献于2011-08-09

下载需要 5 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf