狠狠撸

BeansDB 设计与实现

刘洪清
Davies@douban.com
2011/4/8

11年4月8日星期五

?需求

? 设计

? 实现

? 回顾


产物需求


产物需求
? 图片
? 头像,个人相册, 图片墙
? 电台单曲


产物需求
? 图片
? 头像,个人相册, 图片墙
? 电台单曲
? 长文本
? 评论,日记,作品,博客, 小组话题
? 用户属性, 条目属性

技术需求


技术需求
? 存储大量小文件(字段)


技术需求
? 可扩展性


技术需求
? 可扩展性
? 可靠性


技术需求
? 可扩展性
? 可靠性
? 可用性


技术需求
? 可扩展性
? 可靠性
? 可用性
? 一致性


技术需求
? 可扩展性
? 可靠性
? 可用性
? 一致性
? 低成本

两个原则


两个原则

? KISS


两个原则

? KISS
? 尽量复用开源方案


初步方案


初步方案
? 存储大量小文件
? key/value, get/set/delete
? hash, bucket


初步方案
? 存储大量小文件
? key/value, get/set/delete
? hash, bucket
? 可扩展性
? 独立存储节点,独立数据目录
? bucket 扩展

初步方案
Node1 Node2 Node3 Node4

set a get b

Clients


深入设计


深入设计
? 可靠性
? 多机冗余(N=3)
? 同步写, 依次读


深入设计
? 可靠性
? 多机冗余(N=3)
? 同步写, 依次读
? 一致性
? 最终一致性
? Hash Tree 同步 (外部脚本)
? 冲突: 独立版本号+更新时间


Proxy 1

Clients



Proxy 1

set a

Clients



Proxy 1

set a get b

Clients


Sync with HT


Proxy 1

set a get b

Clients


Sync with HT


Proxy 1
Node5
set a get b

Clients


Sync with HT

Sync

Proxy 1
Node5
set a get b

Clients


存储节点实现


存储节点实现
? Key/Value存储引擎
? ACID(宽松)


存储节点实现
? ACID(宽松)
? 网络协议
? memcache 协议


存储节点实现
? ACID(宽松)
? 网络协议
? memcache 协议
? 同步接口
? Hash Tree(哈希树)


存储节点实现
? ACID(宽松)
? 网络协议
? memcache 协议
? 同步接口
? Hash Tree(哈希树)
? 多线程模型

存储引擎


存储引擎
? Tokyo Cabinet
? 简单, 轻量, 小数据时性能不错
? crash, 大数据量时性能不好


存储引擎
? Tokyo Cabinet
? Berkeley DB
? 过重, 存储稍大的文件性能不好


存储引擎
? Tokyo Cabinet
? Berkeley DB
? 过重, 存储稍大的文件性能不好
? Bitcask
? 内存索引 + 日志结构数据文件

内存索引
追加写入

数据格式 Bitcask


内存索引
追加写入

hint

数据格式 Bitcask


优化叠颈迟肠补蝉办


? 每bucket一个Bitcask


? 数据空间
? 256 对齐, 最多256个, 自动压缩
? 在线GC, 外部控制


? 数据空间
? 256 对齐, 最多256个, 自动压缩
? 在线GC, 外部控制
? 启动时间
? hint 文件, QuickLZ L3压缩
? 多线程

Hash Tree
0 Node
1 key1 Key
key2 Version
2 key3 Hash
Root key4 Position
0 3
Hash(Key) = 0x02f93fea
Bucket 0 0
e Hash
1
f Count


Hash Tree优化


Hash Tree优化
? Hash Table


Hash Tree优化
? Hash Table
? Node, Item 连续存放
? {1}{16}{256}
? {Size, Count, [{Ver, Hash, Pos, Key}, ....]
? 128 个自动分裂


Hash Tree优化
? Hash Table
? Node, Item 连续存放
? {1}{16}{256}
? {Size, Count, [{Ver, Hash, Pos, Key}, ....]
? 128 个自动分裂
? 重新编码key
? /topic/1234567/body=>{/topic/%d/body,
123}

同步过程
节点 A

节点 B

客户端
时间


同步过程
节点 A V1

节点 B V1

客户端 Set
时间


同步过程
节点 A V1 V1

节点 B V1

客户端 Set
时间


同步过程
节点 A V1 V1

节点 B V1 V2

客户端 Set Set
时间


同步过程
节点 A V1 V1 V2

Sync

节点 B V1 V2

客户端 Set Set
时间


同步过程
节点 A V1 V1 V2

Sync

节点 B V1 V2 V2

客户端 Set Set
时间


同步过程
节点 A V1 V1 V2

Sync

节点 B V1 V2 V2

客户端 Set Set Get
时间


同步过程
节点 A V1 V1 V2 V-3

Sync

节点 B V1 V2 V2

客户端 Set Set Get Delete
时间


同步过程

Sync Sync

节点 B V1 V2 V2 V-3

客户端 Set Set Get Delete
时间


同步过程

Sync Sync

节点 B V1 V2 V2 V-3

客户端 Set Set Get Delete GC
时间


网络协议


网络协议
? memcache 文本协议
? 复用memcached的网络协议层代码
? 有大量客户端可用


网络协议
? memcache 文本协议
? 复用memcached的网络协议层代码
? 有大量客户端可用
? 适当扩展
? @fff, ?xxxx, ?ush_all
? get_multi, set_multi, delete_multi

滨翱与多线程模型


? 并发与IO
? 并发连接多, 并发请求少
? 异步网络IO, 同步磁盘IO


? 并发与IO
? 并发连接多, 并发请求少
? 异步网络IO, 同步磁盘IO
? 多线程模型
? 多个连接与线程绑定
? 半同步, 半异步
? leader follower

尝别补诲别谤-贵辞濒濒辞飞别谤模型
Leader try to lock

wait for event
Mutex
remove event fd

unlock

Follower do the work (blocking)


Proxy 实现


Proxy 实现
? Go 实现
? 易于实现高并发应用, 性能可接受


Proxy 实现
? Go 实现
? 自动路由
? 根据 Merkle Tree得到数据分布
? 更高可用性


Proxy 实现
? Go 实现
? 自动路由
? 根据 Merkle Tree得到数据分布
? 更高可用性
? 负载均衡
? 减少IO慢的节点的请求量

版本历史


版本历史
? 0.1, like MogileFS 2008.8
? WebDAV, inotify, sync, client


版本历史
? 0.2, like TokyoTrant 2008.12
? TC, HTree, sync, mc client


版本历史
? 0.2, like TokyoTrant 2008.12
? TC, HTree, sync, mc client
? 0.3, like memcachedb 2009.6
? HTree in TC, on Disk


版本历史(2)


版本历史(2)

? 0.4 2010.2
? proxy


版本历史(2)

? 0.4 2010.2
? proxy
? 0.5 reload 2010.10
? Bitcask, Leader/Follower


实际部署案例(1)


? 数据量
? 图片, 音频: 1k到20M
? 310M x 3 = 930 M
? 590G x 16 x 3 = 28T
? 17 个节点, 约 50 块SATA硬盘


? 数据量
? 图片, 音频: 1k到20M
? 310M x 3 = 930 M
? 590G x 16 x 3 = 28T
? 性能：
? 250 qps左右, 有CDN
? Med/Avg/90%/99%: 16/29/69/232 ms

各节点数据分布


线上运行状态截图 (图片, mp3, 3亿)


? 数据量
? 文本字段: 100到100k
? 550M x 3 = 1.65 B
? 50G x 16 x 3 = 2.4T


? 数据量
? 文本字段: 100到100k
? 550M x 3 = 1.65 B
? 50G x 16 x 3 = 2.4T
? 性能：
? 200 qps左右, 有memcached作缓存
? Med/Avg/90%/99%: 1/14/15/104 ms

Thanks!
Q/A ?


原型开发


原型开发
? 原型开发
? 快速验证想法


原型开发
? 原型开发
? Python
? Cython 扩展


原型开发
? 原型开发
? Python
? Cython 扩展
? Go
? cgo 扩展, 容易开发高并发应用

狠狠撸

Qcon 2011：Beansdb 的设计与实现

More Related Content

Qcon 2011：Beansdb 的设计与实现