Google的BigTable架构在分布式结构化存储方面大名鼎鼎,其中的MergeDump模型在读写之间找到了一个较好的平衡点,很好的解决了web scale数据的读写问题。
MergeDump的理论基础是LSM-Tree (Log-Structured Merge-Tree),
LSM思想非常朴素,就是将对数据的更改hold在内存中,达到指定的threadhold后将该批更改批量写入到磁盘,在批量写入的过程中跟已经存在的数据做rolling merge。
拿update举个例子:
比如有1000万行数据,现在希望UPDATE TABLE a set
addr='new addr' WHERE pk = '833',
如果使用B-Tree类似的结构操作,就需要:
1. 找到该条记录所在的page,
2. load page到内存(如果恰好该page已经在内存中,则省略该步)
3. 如果该page之前被修改过,则先flush page to disk
4. 修改数据
上面的动作平均来说有两次disk I/O,如果采用LSM-Tree类似结构,则:
1. 将需要修改的数据直接写入内存
可见这里是没有disk I/O的。当然,我们要说,这样的话读的时候就费劲了,需要merge disk上的数据和memory中的修改数据,这显然降低了读的性能。
确实如此,所以作者其中有个假设,就是写入远大于读取的时候,LSM是个很好的选择。我觉得更准确的描述应该是”优化了写,没有显著降低读“,因为大部分时候我们都是要求读最新的数据,而最新的数据很可能还在内存里面,即使不在内存里面,只要不是那些更新特别频繁的数据,其I/O次数也是有限的。
所以LSM-Tree比较适合的应用场景是:insert数据量大,读数据量和update数据量不高且读一般针对最新数据。
文章读下来有以下几点感受:
1. 基本思想早就有了,作者给出了较好的表现形式。
2. Merge是page/block级别的,而不是BigTable中的文件级别的。这一点主要原因可能是BigTable在分布式场景下做block级别很困那,而且GFS也不支持修改。
3. 其提出的比较标准比较有趣,将磁盘容量,转速等结合起来给出一个以美元为单位的cost标准,然后跟B-Tree结构的实现做了比较,结果当然是大大胜出。但是这里我觉得作者有些比较是不合理的,比如LSM使用log而B-Tree没有使用,这显然对B-Tree不公,其实B-Tree如果使用log,写入性能应该不比LSM差,顺序读取可能差一些。
4. 在Multi components 中,提出Ci/Ci+1的比例达到20的时候是最优的,这个数字意义不大,但是其中的分析方法对于Merge策略的选择是个启发。
分享到:
相关推荐
The Log-Structured Merge-Tree (LSM-Tree).pdf
Chucky: A Succinct Cuckoo Filter for LSM-Tree Niv Dayan, Moshe Twitto Pliops
LSM使用了一个算法来延迟批处理索引变更,然后类似归并排序的方式串联起一个基于内存的组件和若干基于磁盘的组件上面的所有变更信息。该算法相比于传统的B树访问方式大大减少磁盘臂的移动开销。
基于LSM-tree的KV数据库性能优化.doc
LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small DataXingbo Wu1, Yuehai Xu1, Zili Shao2, and Song Jiang11 Wayne State University, {wuxb,yhxu,sjiang}@wayne.edu 2 The Hong Kong ...
LSM-Tree关键技术[收集].pdf
基于更新热点感知的LSM-Tree查询优化.docx
基于非易失性内存的LSM-tree存储系统优化.docx
LSM-trie: An LSM-tree-based Ultra-LargeKey-Value Store for Small DataXingbo WuYuehai XuSong JiangZili ShaoThe Hong KongPolytechnic UniversityThe Challenge on Today’s Key-Value Store• Trends on ...
“ #driftdb” 一个支持多隔离等级原生事务的LSM-Tree数据库。
本项目将基于LSM Tree开发一个简化的键值存储系统。支持以下基本操作: PUT(K,V)设置键K的值为V GET(K)读取键K的值 DELETE(K)删除键K的值 其中K是64位有符号整数,V位字符串 LSM Tree的键值存储系统分为内存存储和...
摘要:伴随着数据量的大规模爆发和云计算的快速发展,早期由于缺乏标准化和其他问题而发展缓慢的键值存储(keyvaluestorage,KVStorage)进入了飞
这是第一个将LSM-tree引入PostgreSQL外部数据包装器(FDW)。 底层存储引擎可以是RocksDB。 FDW还用于VidarDB引擎,VidarDB引擎是用于各种工作负载的通用存储引擎。 请参阅链接以获取有关VidarDB引擎的更多信息。
It is an LSM survey paper, listing all techniques a storage engineer should know about LSM. Highly recommended!
High-performance transaction system applications typically insert rows in a History table to provide an activity trace; at the same time the transaction system generates log records for purposes of ...
We present WiscKey, a persistent LSM-tree-based key-value store with a performance-oriented data layout that separates keys from values to minimize I/O amplification. The design of WiscKey is highly ...
一种很多索引树采用的技术,比如lsm-tree等等
levelDB是淘宝开源存储Tair的底层实现,基于LSM-tree实现
背景介绍LSM Tree(Log-structured merge tree) 是一种高性能的存储数据结构。传统关系型数据库使用 B+ tree 或一些变体作为
[原网页] 从LSM-Tree、COLA-Tree谈到StackOverflow、OSQA [原网页] 程序员编程艺术第一~二十七章集锦与总结(教你如何编程),及PDF免分下载 [原网页] 教你如何迅速秒杀掉:99%的海量数据处理面试题 [原网页] 程序员...