网站专栏怎么做漂亮,优化大师班级优化大师,小米发布会在哪看,建站平台与自己做网站数据库管理-第127期 LSM Tree#xff08;202301225#xff09;
说起分布式数据库#xff0c;绕不开的一个话题就是LSM Tree#xff0c;全称为log-structured merge-tree#xff0c;回到吕海波老师授权过的那句话“没搞过Oracle的#xff0c;但又是数据库圈里的人#x…数据库管理-第127期 LSM Tree202301225
说起分布式数据库绕不开的一个话题就是LSM Tree全称为log-structured merge-tree回到吕海波老师授权过的那句话“没搞过Oracle的但又是数据库圈里的人特别做数据库开发的对Oracle的印象就是集中式、落后、旧时代的产物超过Oracle很简单基于Poxos/Raft随便上个分布式就可以了。如果再实现个LSM Tree那就超过Oracle太多了。”可见LSM Tree对于分布式数据库是很重要的一个东西无论是国外的HBase、Cassandra、LevelDB、RocksDB等还是国内较为出名的OceanBase、TiDB等都是使用LSM Tree来组织数据。
1 基本
LSM Tree和B Tree是数据库创建block(块)的时候提到的两种基础数据结构。B Tree一般用于较少查询和插入时间的场景而LSM Tree则用于写压力非常大而读要求不是那么高的场景。 LSM Tree并非是一个所谓的新技术从维基百科来看这是一个诞生于1996年的技术较早发表用于具体技术则是2006年Google发表的论文《Bigtable: A Distributed Storage System for Structured Data》这篇论文也被誉为分布式数据库开山鼻祖之作后面很多分布数据库也都是基于这一篇论文的理论建立起来的。
2 机制
LSM Tree的出现是为了大数据量的OLAP场景其最大的机制也可以说是优势是可以充分利用磁盘顺序写的优势而带来非常强大的数据写入性能当然在查询这块牺牲了一定性能一般来说是慢于B Tree当然这个性能也是可以接受的。而随着内存与SSD价格的持续走低以及容量的极大提升基于LSM Tree的数据库读性能也有了显著提升。 一个简单版本的LSM Tree包含两层类似于树状的数据架构
Memtable(内存表)完全驻留在内存中定义为T0组件SSTable(Sorted String Table)存储在磁盘上定义为T1组件 新纪录被插入到Memtable中(T0组件)。如果插入导致T0组件超过一定的大小阈值则从T0中删除一个连续的条目段并将其合并到磁盘上的SSTable(T1组件)中。
3 组件
LSM Tree主要使用3个组件来优化读写操作
Sorted String Table (SSTables)
数据按排序顺序排序的因此无论何时读取数据在最坏的情况下其时间复杂度将为O(Log(N))其中N是数据库表中的条目数。
Memtable
这是一个内存结构 以排序方式存储数据 作为回写(Write-Back)缓存 当到达一定大小时将作为SSTable刷入数据库 当磁盘中SSTable的数量增加时如果某些key不存在于记录中时
要查询这些key需要读取所有SSTable这增加了读取时间的复杂度为了克服这个问题Bloom filter出现了Bloom filter是一种节省空间的数据结构它可以告诉我们记录中是否缺少key准确率为99.9%要使用此filter我们可以在写入数据的时候向其添加记录并在读取请求开始时检查key以便在请求第一次出现时更有效地服务请求 Compaction
直接翻译过来就是压实 磁盘中以SSTable的形式存储数据时假设有N个SSTable每个表的大小为M 最坏情况下读取时间复杂度为O(N* Log(M))因此随着SSTable数量的增加读时间复杂度也会增加; 此外当我们只是刷新数据库中的SSTable时相同的Key存在于多个SSTable中 这时候Compactor就能发挥作用compactor在后台运行合并SSTable并删除相同的多行并添加最新数据的新键并将它们存储在新的合并/压缩的SSTable中。 正是这一组件许多基于LSM Tree的分布式数据库也在标榜自己在存储侧的压缩能力可以节省存储成本。
4 问题
LSM Tree既然有较强的写入响应能力存储节省能力那么LSM Tree就没有缺点么
还是借用吕海波老师的总结“LSMTree最主要的问题它是针对OLAP。底层Skiplist锁的粒度要么太细锁太多。要么锁粒度太粗锁一大段链表。传通架构锁就在块上块上加个Pin比Skiplist的并发性要好。”说真的这句话看的不是太明白读性能偏低但是在强大硬件和分布式MPP加持下也能带来不错的读性能写放大还是那句话NVMe SSD上那都不是事延迟合并带来的不一致特别是分布式架构同分片不同节点合并进度不同可能导致连续两次在不同节点查询的结果不一致当然这些都是可以通过一些技术手段解决的等等等等
总结
这不是我一个擅长的领域以前没有接触过也是翻了不少英文文档来写这一篇文章可能还有些东西是不对的也是一种尝试吧也想着去看看国产分布式数据库引以为傲的底层。 老规矩不知道写了些啥。
