Bitalos

# Bitalosdb

# 问题&方案

  • 问题：标准LSM-Tree存在读写放大问题；数据规模越大，读写放大的资源消耗越大；如何用更低的成本承载更大规模写入&读取？

  • 方案：基于Bitalostree解决读放大，基于Bithash实现KV分离解决写放大，基于冷热数据分离进一步节省内存及硬盘消耗

# 读写放大分析

  • 定义

写放大: 累计写入硬盘字节数 / 原始数据字节数

读放大: 单次查询所执行的I/O次数

  • 参数
N=原始数据字节数
L=单条KV的平均字节数
B=文件系统page字节数
F=lsm中最小层单个文件字节数；bitalosdb中bitalostree的updatetable单个文件字节数
k=lsm(Ln单个文件字节数)/(Ln-1单个文件字节数)；bitalosdb(succinctable单个文件字节数)/(updatetable单个文件字节数)
j=bitalosdb中bitalostree分裂系数，即1个succinctable分裂为j个succinctable
  • 结论
写放大 读放大
b+tree O(B/L) O(logB/L(N/B))
lsm-leveled O(k*logk(N/F)) O((log(N/F)*log(N/B))/log(k))
lsm-size tiered O(logk(N/F)) O(k*log(N/F)*log(N/B)/log(k))
bitalosdb (k+1)/2+1/(j-1) O(log(kF/B))

# 写放大对比

  • 引擎配置
bitalosdb pebble(lsm-tree) bboltdb(b+tree)
DisableWAL: true
UseBithash: true
UseMapIndex: true
 DisableWAL: true
L0FileSize: 256MB
Compression: Snappy
BlockSize: 32KB
L0CompactionThreshold: 8
L0StopWritesThreshold: 32
LBaseMaxBytes: 4GB
 NoSync: true
NoGrowSync: true
NoFreelistSync: false
PageSize: 4KB
  • 测试结果
Cumulative Write 10G 20G 100G
Key: 20B
Value: 128B		 Count: 74051160 Count: 148102320 Count: 740511600
bitalosdb 37GB 82GB 331GB
pebble 72GB 493GB 7172GB
bboltdb
(10000 items per commit)		 551GB 1189GB 6045GB

# 关键技术

  • Bithash（KV分离技术），具备O(1)检索效率，可独立完成GC，实现value与index解耦。

  • Bitalostree（高性能压缩索引技术），基于超大Page的B+ Tree，运用全新的索引压缩技术，消除B+ Tree的写放大，并将读性能发挥到极致。

  • Bitalostable（冷热数据分离技术），承载冷数据存储，提升数据压缩率，减少索引内存消耗，实现更合理的资源利用（开源稳定版具备基础功能，企业版支持更全面的冷热分离）。

# IO架构

bitalosdb-io

# KV分离

# 方案分析

  • 方案A

kv-separation-1

  • 方案B

kv-separation-2

  • 方案C

kv-separation-3

  • 分析

kv-separation-analysis

  • 总结

    • 方案A&B在vlog-GC时，需要查询&更新索引，消耗额外的CPU及IO资源

    • 方案C在vLog读取时，会触发多次随机读取，读性能存在优化空间

    • Bitalosdb在保障vLog高性能读取的同时，实现GC在vLog内部闭环，无需查询&更新索引

# 技术详情

  • 文件结构

bithash-1

  • 数据写入

bithash-2

  • 数据读取

bithash-3

  • 索引写入

bithash-4

# 高性能压缩索引

bitalostree

  • 备注：开源版支持图中90%的压缩格式，企业版支持全部索引压缩格式

Bitalostored →

ZUOYEBANG