HBase之LSM树(Log-Structured Merge-Tree)存储引擎
HBase之LSM树(Log-Structured Merge-Tree)存储引擎详细介绍
目录
- LSM树概述
- LSM树的核心设计思想
- HBase中LSM树的架构设计
- 写入流程
- 读取流程
- 合并(Compaction)机制
- LSM树的优缺点
- HBase LSM树的优化策略
1. LSM树概述
1.1 什么是LSM树
LSM树（Log-Structured Merge-Tree，日志结构合并树）是一种面向磁盘存储的数据结构，由Patrick O’Neil等人于1996年提出。它通过将随机写转换为顺序写来优化写入性能，特别适合写密集型应用场景。
1.2 HBase为什么选择LSM树
HBase作为构建在HDFS之上的分布式列式存储系统，选择LSM树作为其底层存储引擎主要基于以下原因：
| 特性 | B+树 | LSM树 | HBase需求 |
|---|---|---|---|
| 写入性能 | 随机写，性能较低 | 顺序写，性能高 | 高吞吐写入 |
| 读取性能 | 点查询快 | 需要合并多个SSTable | 可接受 |
| 空间利用率 | 较高 | 可能产生碎片 | 可通过Compaction解决 |
| 范围查询 | 友好 | 友好 | 支持范围扫描 |
| 压缩效率 | 一般 | 较好 | 节省存储空间 |
1.3 LSM树的历史演进
早期阶段
1996
Patrick
O'Neil提出LSM树概念
用于优化写密集型应用
数据库应用
2004
Bigtable采用LSM架构
2006
Cassandra发布
使用LSM作为存储引擎
2007
HBase项目启动
基于Bigtable设计
现代发展
2010
RocksDB发布
高性能LSM实现
2015
HBase 1.0发布
优化Compaction策略
2020+
云原生数据库广泛采用LSM
如TiKV、CockroachDB
LSM树发展历史
2. LSM树的核心设计思想
2.1 核心原理
LSM树的核心思想是将随机写转换为顺序写，通过以下机制实现：
- 内存缓冲：所有写入操作首先进入内存中的可变数据结构
- 批量刷盘：当内存达到阈值时，批量写入磁盘形成不可变文件
- 分层存储：磁盘上的文件按大小分层组织
- 后台合并：后台进程定期合并文件，减少文件数量
2.2 LSM树的基本架构
LSM树基本架构
磁盘存储
刷盘
合并
合并
合并
L0层
最新数据
写入请求
WAL
Write-Ahead Log
MemTable
内存可变表
L1层
L2层
Ln层
最老数据
2.3 LSM树的关键组件
2.3.1 MemTable（内存表）
MemTable是内存中的可变数据结构，通常使用跳表(Skip List)实现，具有以下特性：
- 高效插入：O(log n)的时间复杂度
- 有序存储：按键排序，便于范围查询
- 内存管理：当达到阈值时触发刷盘
2.3.2 WAL（Write-Ahead Log）
WAL是预写日志，用于数据持久化和故障恢复：
MemTable
WAL
Client
MemTable
WAL
Client
1. 追加写入日志
2. fsync确保持久化
3. 返回成功
4. 更新内存表
2.3.3 SSTable（Sorted String Table）
SSTable是磁盘上的不可变有序文件，具有以下特点：
- 不可变性：写入后不再修改
- 有序性：按键排序存储
- 索引结构：包含数据块和索引块
3. HBase中LSM树的架构设计
3.1 HBase存储架构概览
HBase RegionServer
WAL存储
Region 1
Store 1 (CF)
HDFS存储
刷盘
合并
Store 2 (CF)
HDFS存储2
HFile-4
HFile-5
MemStore
BlockCache
MemStore
内存
BlockCache
读缓存
HFile-1
HFile-2
HFile-3
HLog
WAL文件
写入请求
3.2 HRegion与Store的关系
HBase Table
表 Table
Region 1
RowKey: a-m
Region 2
RowKey: n-z
Store: CF1
Store: CF2
Store: CF3
MemStore
HFiles on HDFS
MemStore
HFiles on HDFS
3.3 HFile文件结构
HFile是HBase中SSTable的具体实现，其内部结构如下：
HFile v3 结构
HFile File
File Header
版本信息、压缩类型等
Data Block 1
实际键值对数据
Data Block 2
Data Block N
Meta Block
布隆过滤器等元数据
File Info
文件统计信息
Bloom Filter
快速判断key是否存在
Data Index
数据块索引
Meta Index
元数据块索引
File Trailer
文件尾部指针
3.4 MemStore内部结构
MemStore内部结构
MemStore
ConcurrentSkipListMap
有序数据结构
Cell 1
RowKey: key1
Timestamp: ts1
Cell 2
RowKey: key2
Timestamp: ts2
Cell N
RowKey: keyN
Timestamp: tsN
Snapshot
用于刷盘的快照
MVCC
多版本并发控制
4. 写入流程
4.1 完整写入流程图
HDFS
MemStore
WAL
RegionServer
Client
HDFS
MemStore
WAL
RegionServer
Client
后台异步流程
alt
[达到阈值]
1. Put/Delete操作
2. 检查Region状态
3. 追加写入WAL
4. sync到HDFS
5. 写入成功
6. 更新MemStore
7. 返回成功
8. 检查大小阈值
9. 创建Snapshot
10. 刷盘为HFile
11. 清空Snapshot
4.2 写入路径详解
Region在线
Region迁移
WAL可用
WAL不可用
失败
成功
未达阈值
达到阈值
客户端写入请求
检查Region
检查WAL
返回错误
NotServingRegionException
写入WAL
返回错误
Sync WAL到HDFS
Sync成功?
返回错误
写入失败
写入MemStore
MemStore
大小检查
返回成功给客户端
创建Snapshot
创建新MemStore
异步刷盘
写入HFile到HDFS
清除Snapshot
4.3 写入性能优化
HBase通过以下机制优化写入性能：
- 批量写入：支持MultiPut操作，减少RPC开销
- 异步刷盘：MemStore刷盘是异步的，不阻塞写入
- WAL分组：HBase 2.0+支持WAL按Region分组，提高并发
- 延迟刷盘：可配置延迟刷盘时间，合并多次写入
写入优化机制
批量写入
MultiPut
异步刷盘
不阻塞写入
WAL分组
提高并发
延迟刷盘
合并写入
提升写入性能
5. 读取流程
5.1 完整读取流程图
HDFS
MemStore
BlockCache
RegionServer
Client
HDFS
MemStore
BlockCache
RegionServer
Client
alt
[缓存命中]
[缓存未命中]
1. Get/Scan操作
2. 查询BlockCache
3. 缓存命中?
4. 返回数据
5. 查询MemStore
6. MemStore数据
7. 读取HFile
8. HFile数据
9. 更新缓存
10. 返回合并后的数据
5.2 读取路径详解
命中
未命中
可能存在
肯定不存在
客户端读取请求
查询BlockCache
返回缓存数据
查询MemStore
获取MemStore数据
查询Snapshot
获取Snapshot数据
读取HFile
布隆过滤器
读取数据块
跳过此文件
合并数据源
更新BlockCache
返回数据
结束
5.3 多版本读取
HBase支持多版本数据读取，通过时间戳实现：
多版本数据组织
RowKey: user001
ColumnFamily: info
ColumnFamily: data
Qualifier: name
Qualifier: age
Value: 张三
TS: 1000
Value: 李四
TS: 2000
Value: 王五
TS: 3000
Value: 25
TS: 1000
Value: 26
TS: 2000
5.4 读取性能优化
读取优化机制
BlockCache
读缓存
布隆过滤器
快速过滤
前缀Trie
加速RowKey查找
列编码
减少数据量
提升读取性能
6. 合并(Compaction)机制
6.1 Compaction概述
Compaction是LSM树的核心机制，用于：
- 合并多个SSTable，减少文件数量
- 清理已删除/过期的数据
- 提高读取性能
6.2 Compaction类型
Compaction分类
Compaction
Minor Compaction
小合并
Major Compaction
大合并
合并相邻层级的
少量HFile
合并所有HFile
清理删除标记
6.3 Minor Compaction流程
HFile
HDFS
Store
CompactionChecker
HFile
HDFS
Store
CompactionChecker
1. 检查是否需要Compaction
2. 选择待合并的HFile
3. 读取HFile数据
4. 返回数据
5. 合并数据
6. 应用TTL和删除标记
7. 写入新HFile
8. 写入完成
9. 更新元数据
10. 删除旧HFile
11. Compaction完成
6.4 Major Compaction流程
是
否
是
到达时间
未到时间
触发Major Compaction
手动触发?
手动Major Compaction
自动触发?
时间检查
自动Major Compaction
跳过
选择所有HFile
读取所有HFile
全量合并
清理过期数据
清理删除标记
写入新HFile
删除旧HFile
完成
结束
6.5 Compaction策略
HBase提供多种Compaction策略：
Compaction策略
Compaction策略
RatioBasedCompaction
基于比例的策略
FIFOCompaction
先进先出策略
TieredCompaction
分层策略
StripeCompaction
条带策略
DateTieredCompaction
时间分层策略
6.5.1 RatioBasedCompaction策略
这是HBase默认的Compaction策略，基于文件大小比例选择待合并的文件：
RatioBasedCompaction选择逻辑
2倍比例
2倍比例
2倍比例
2倍比例
合并
合并
L0: 10MB
L1: 20MB
L2: 40MB
L3: 80MB
L4: 160MB
6.5.2 TieredCompaction策略
LevelDB和RocksDB风格的分层Compaction：
TieredCompaction分层结构
合并
合并
合并
L0层
多个重叠文件
L1层
不重叠文件
L2层
不重叠文件
L3层
不重叠文件
File1
File2
File3
File4
File5
6.6 Compaction对性能的影响
Compaction性能影响
正面影响
减少文件数量
提高读取性能
清理删除数据
释放存储空间
数据局部性优化
减少IO
负面影响
消耗IO资源
影响读写性能
消耗CPU资源
数据解压/压缩
产生临时文件
占用额外空间
7. LSM树的优缺点
7.1 LSM树的优点
LSM树优点
写入性能
顺序写
高吞吐量
适合写密集场景
存储效率
高压缩率
减少碎片
节省空间
扩展性
易于水平扩展
适合分布式存储
支持大数据量
简单性
结构简单
易于实现
维护成本低
7.2 LSM树的缺点
LSM树缺点
读取性能
需要合并多个文件
点查询性能较差
空间放大
写放大
多次写入同一数据
Compaction开销大
IO资源消耗高
延迟问题
Compaction阻塞
读取延迟抖动
空间回收延迟
复杂性
Compaction策略复杂
参数调优困难
故障恢复复杂
7.3 LSM树与B+树对比
LSM树 vs B+树
LSM树
写入性能: ★★★★★
B+树
写入性能: ★★★☆☆
读取性能: ★★★☆☆
读取性能: ★★★★★
空间效率: ★★★★☆
空间效率: ★★★☆☆
范围查询: ★★★★☆
范围查询: ★★★★★
缓存友好: ★★★☆☆
缓存友好: ★★★★★
8. HBase LSM树的优化策略
8.1 写入优化
HBase写入优化策略
WAL优化
异步WAL
WAL分组
WAL压缩
MemStore优化
调整MemStore大小
优化刷盘策略
并发MemStore
Compaction优化
Off-peak Compaction
Compaction限流
并行Compaction
8.2 读取优化
HBase读取优化策略
缓存优化
BlockCache调优
BucketCache
组合缓存
索引优化
布隆过滤器
RowKey设计
列族优化
扫描优化
Scan Caching
Scan Batching
反向扫描
8.3 存储优化
HBase存储优化策略
压缩
GZIP压缩
LZO压缩
Snappy压缩
ZSTD压缩
编码
Delta编码
前缀编码
快速差分编码
布隆过滤器
RowKey布隆过滤器
RowCol布隆过滤器
8.4 参数调优建议
| 参数 | 默认值 | 推荐值 | 说明 |
|---|---|---|---|
| hbase.regionserver.global.memstore.size | 0.4 | 0.3-0.4 | MemStore总内存占比 |
| hbase.hregion.memstore.flush.size | 128MB | 256MB | 单个MemStore刷盘阈值 |
| hbase.hstore.blockingStoreFiles | 10 | 15-20 | 阻塞写入的文件数 |
| hbase.hstore.compaction.max | 10 | 15-20 | 单次Compaction最大文件数 |
| hbase.regionserver.thread.compaction.large | 1 | 2-4 | 大Compaction线程数 |
| hbase.regionserver.thread.compaction.small | 1 | 4-8 | 小Compaction线程数 |
8.5 监控指标
HBase LSM树监控指标
写入指标
写入QPS
写入延迟
WAL大小
读取指标
读取QPS
读取延迟
缓存命中率
Compaction指标
Compaction队列长度
Compaction耗时
Compaction数据量
存储指标
StoreFile数量
StoreFile大小
Region大小
总结
LSM树作为HBase的核心存储引擎，通过将随机写转换为顺序写，实现了极高的写入性能。虽然读取性能相对B+树有所牺牲，但通过BlockCache、布隆过滤器等优化手段，仍然能够满足大多数场景的需求。
理解LSM树的原理和HBase的实现细节，对于HBase的性能调优和故障排查至关重要。在实际应用中，需要根据业务特点选择合适的Compaction策略、压缩算法和缓存配置，以获得最佳的性能表现。
关键要点回顾
- LSM树核心思想：将随机写转换为顺序写，通过内存缓冲和后台合并实现
- HBase实现：MemStore + WAL + HFile三层结构
- 写入流程：WAL -> MemStore -> 异步刷盘为HFile
- 读取流程：BlockCache -> MemStore -> HFile，多路合并
- Compaction机制：Minor和Major Compaction，清理数据，优化读取
- 优化策略：缓存、压缩、布隆过滤器、参数调优
© 版权声明
文章版权归作者所有，未经允许请勿转载。
