Google的BigTable架构在分布式结构化存储方面大名鼎鼎,其中的MergeDump模型在读写之间找到了一个较好的平衡点,很好的解决了web scale数据的读写问题。
MergeDump的理论基础是LSM-Tree (Log-Structured Merge-Tree), 原文见:LSM Tree
下面先说一下LSM-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
LSM使用了一个算法来延迟批处理索引变更,然后类似归并排序的方式串联起一个基于内存的组件和若干基于磁盘的组件上面的所有变更信息。该算法相比于传统的B树访问方式大大减少磁盘臂的移动开销。
Chucky: A Succinct Cuckoo Filter for LSM-Tree Niv Dayan, Moshe Twitto Pliops
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的KV数据库性能优化.doc
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 ...
本项目将基于LSM Tree开发一个简化的键值存储系统。支持以下基本操作: PUT(K,V)设置键K的值为V GET(K)读取键K的值 DELETE(K)删除键K的值 其中K是64位有符号整数,V位字符串 LSM Tree的键值存储系统分为内存存储和...
“ #driftdb” 一个支持多隔离等级原生事务的LSM-Tree数据库。
It is an LSM survey paper, listing all techniques a storage engineer should know about LSM. Highly recommended!
摘要:伴随着数据量的大规模爆发和云计算的快速发展,早期由于缺乏标准化和其他问题而发展缓慢的键值存储(keyvaluestorage,KVStorage)进入了飞
lglsm-100鼠标扫描器驱动是一个的扫描仪驱动软件。用户可以通过安装这个驱动程序解决设备不能正常扫描使用问题。需要的话就下载安装吧。驱动介绍LG鼠标扫描器驱动是由lg官方发布的一款扫描仪跟鼠标合二为一的驱动...
python-lsm-db, SQLite4 LSM数据库的python 绑定 sqlite4键/值存储 LSM的快速 python 绑定。功能:嵌入式零conf数据库。使用游标进行遍历的键支持。事务性( 包括嵌套事务) 。基于单个编写器/多读者MVCC的事务并发...
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 ...
C&D西恩迪 LSM-0.75/16-D12 模块电源说明书pdf,C&D西恩迪 LSM-0.75/16-D12 模块电源说明书
资源来自pypi官网。 资源全名:lsm-db-0.6.1.tar.gz
笔记该LSM-trie实现不使用任何用户空间缓存。 I / O限制了其读取性能。 如果您正在寻找用于快速写入,读取和范围搜索的高性能SSD KV存储,请查看 。建造编译器: clang或gcc(在Makefile中更改)。 用于SHA1功能的...
python库,解压后可用。 资源全名:lsm-0.1.4-cp36-cp36m-win_amd64.whl