LSM存储组织结构介绍 - bangerlee

标签: lsm 组织结构 bangerlee | 发表时间:2015-03-01 21:16 | 作者:bangerlee
出处:

LSM(Log Structured Merge Trees)数据组织方式被应用于多种数据库,如LevelDB、HBase、Cassandra等,下面我们从为什么使用LSM、LSM的实现思路两方面介绍这种存储组织结构,完成对LSM的初步了解。

 

存储背景回顾

LSM相较B+树或其他索引存储实现方式,提供了更好的写性能。究其原因,我们先回顾磁盘相关的一点背景知识。

 

顺序操作磁盘的性能,较随机读写磁盘的性能高很多,我们实现数据库时,也是围绕磁盘的这点特性进行设计与优化。如果让写性能最优,最佳的实现方式就是日志型(Log/Journal)数据库,其以追加(Append)的方式写磁盘文件。

 

有得即有舍,万事万物存在权衡,带来最优写性能的同时,单纯的日志数据库读性能很差,为找到一条数据,不得不遍历数据记录,要实现范围查询(range)几乎不可能。为优化日志型数据库的读性能,实际应用中通常结合以下几种优化措施:

二分查找(Binary Search): 在一个数据文件中使用二分查找加速数据查找

哈希(Hash): 写入时通过哈希函数将数据放入不同的桶中,读取时通过哈希索引直接读取

B+树: 使用B+树作为数据组织存储形式,保持数据稳定有序

外部索引文件: 除数据本身按日志形式存储外,另对其单独建立索引加速读取,如之前介绍的 《一种Bitcask存储模型的实现》

 

以上措施都很大程度提升了读性能(如二分查找将时间复杂度提升至O(log(N))),但相应写性能也有折损,第一写数据时需要维护索引,这视索引的实现方式,最差情况下可能涉及随机的IO操作;第二如果用B+树等结构组织数据,写入涉及两次IO操作,先要将数据读出来再写入。

 

LSM存储结构

LSM存储实现思路与以上四种措施不太相同,其将随机写转化为顺序写,尽量保持日志型数据库的写性能优势,并提供相对较好的读性能。具体实现方式如下:

1. 当有写操作(或update操作)时,写入位于内存的buffer,内存中通过某种数据结构(如skiplist)保持key有序

2. 一般的实现也会将数据追加写到磁盘Log文件,以备必要时恢复

3. 内存中的数据定时或按固定大小地刷到磁盘,更新操作只不断地写到内存,并不更新磁盘上已有文件

4. 随着越来越多写操作,磁盘上积累的文件也越来越多,这些文件不可写且有序

5. 定时对文件进行合并操作(compaction),消除冗余数据,减少文件数量

 

以上过程用图表示如下:

LSM存储结构的写操作,只需更新内存,内存中的数据以块数据形式刷到磁盘,是顺序的IO操作,另外磁盘文件定期的合并操作,也将带来磁盘IO操作。

LSM存储结构的读操作,先从内存数据开始访问,如果在内存中访问不到,再顺序从一个个磁盘文件中查找,由于文件本身有序,并且定期的合并减少了磁盘文件个数,因而查找过程相对较快速。

 

合并操作是LSM实现中重要的一环,LevelDB、Cassandra中,使用基于层级的合并方式(Levelled compaction),生成第N层的时候,对N-1层的数据进行排序,使得每层内的数据文件之间都是有序的,但最高层除外,因为该层不断有数据文件产生,因而只是数据文件内部按key有序。

 

除最高层外,其他层文件间数据有序,这也加速了读过程,因为一个key对应的value只存在一个文件中。假设总共有N层,每层最多K个数据文件,最差的情况下,读操作先遍历K个文件,再遍历每层,共需要K+(N-1)次读盘操作。

 

总结

LSM存储框架实现的思路较简单,其先在内存中保存数据,再定时刷到磁盘,实现顺序IO操作,通过定期合并文件减少数据冗余;文件有序,保证读取操作相对快速。

我们需要结合实际的业务场景选择合适的存储实现,不存在万金油式的通用存储框架。LSM适用于写多、读相对少(或较多读取最新写入的数据,该部分数据存在内存中,不需要磁盘IO操作)的业务场景。

 

参考文章: Log Structured Merge Trees


本文链接: LSM存储组织结构介绍,转载请注明。

相关 [lsm 组织结构 bangerlee] 推荐:

LSM存储组织结构介绍 - bangerlee

- - 博客园_首页
LSM(Log Structured Merge Trees)数据组织方式被应用于多种数据库,如LevelDB、HBase、Cassandra等,下面我们从为什么使用LSM、LSM的实现思路两方面介绍这种存储组织结构,完成对LSM的初步了解. LSM相较B+树或其他索引存储实现方式,提供了更好的写性能.

[转][转]LSM-Tree (BigTable 的理论模型)

- - heiyeluren的Blog
LSM-Tree理论模型:. 来源:http://www.cnblogs.com/raymondshiquan/archive/2011/06/04/2072630.html . Google的BigTable架构在分布式结构化存储方面大名鼎鼎,其中的MergeDump模型在读写之间找到了一个较好的平衡点,很好的解决了web scale数据的读写问题.

RPC框架实现 - 容灾篇 - bangerlee

- - 博客园_首页
RPC(Remote Procedure Call,远程过程调用)框架是分布式服务的基石,实现RPC框架需要考虑方方面面. 其对业务隐藏了底层通信过程(TCP/UDP、打包/解包、序列化/反序列化),使上层专注于功能实现;框架层面,提供各类可选架构(多进程/多线程/协程);应对设备故障(高负载/死机)、网络故障(拥塞/网络分化),提供相应容灾措施.

IT科技公司的组织结构图

- fei - 86pm沙龙—发现·学习·分享 86pm.com
上个月,Web设计师Manu Cornet在自己的博客上,画了一组美国科技公司的组织结构图. 在他笔下,亚马逊等级森严且有序;谷歌结构清晰,产品和部门之间却相互交错且混乱;Facebook架构分散,就像一张散开的网络;微软内部各自占山为….

几大科技公司的组织结构图

- Hming - 爱范儿 · Beats of Bits
狂热 Android 开发者,果粉,webOS 粉,拥抱新事物,特别是 disruptive 类型的新技术新服务. © lordhong for 爱范儿 · Beats of Bits | 原文链接 · 23 热评 · 关注我们微博 · 订阅全文 · Google+ · #ifanrlive 快讯.

数字技术演进下的组织结构

- 喜鵲君 - It Talks-魏武挥的blog
IT圈里的人员流动其实是很频繁的,既包括跳槽,也包括拉出去单干创业. 最近比较大的人员变动是百度的高级副总裁沈皓瑜离职,有传言说他要加盟京东出任COO,但尚未获得证实. 一直以来,舆论上似乎对百度留人的问题是存有“刻板印象”的:这个公司留不住人. 从起家的百度七剑客之变,到第二代高管的频繁更替(比较有名跑路的有梁冬、俞军、李一男),百度即便是高管,都有点“铁打营盘流水兵”的意思.

IT企业组织结构图之国内版

- 开忆 - cnBeta.COM
前几天的一张六大科技巨头组织结构图,以蛋疼的方式真实地刻画了各公司的企业文化. 受此启发,雷锋网如法炮制了国内六大互联网巨头、亦即Tables版的组织结构图,Tables的解释颇多,详细请参考即将出版的《Tables》作者岑峰的博客,但这里分别代表:腾讯、阿里巴巴、百度、雷军系、周鸿t的奇虎360、搜狐.

美国知名IT公司的组织结构图

- 子予 - YesKafei Daily
AMAZON, GOOGLE, FACEBOOK, MICROSOFT, APPLE, ORACLE 这些知名的IT公司,这些大型技术公司的组织结构都各不一样. 具有自己的企业文化,等级制度,在一定程度上决定了公司的走向和产品规模(也许相反). 谷歌重磅推出抗衡Facebook的项目:Google+(内测中).

JavaScript代码组织结构良好的5个特点[reuqire.js]

- - SegmentFault 最新的文章
随着JavaScript项目的成长,如果你不小心处理的话,他们往往会变得难以管理. 我们发现自己常常陷入的一些问题: 当在创建新的页面时发现,很难重用或测试之前写的代码. 当我们更深处地研究这些问题,我们发现根本原因是无效的依赖管理造成的. 比如,脚本A依赖脚本B,并且脚本B又依赖脚本C,当C没有被正确引入时,整个依赖链就无法正常工作了.

从组织结构图看Google、Facebook、微软等大公司的企业文化

- Jim - cnBeta.COM
判断一家公司企业文化的标准有很多,其中之一就是组织结构图. 刚在新浪微博@RadeZ处看到一张有趣的组织结构图,里面包括了亚马逊、Google、Facebook、微软、苹果、甲骨文等六家公司的组织结构图. 从图中我们可以看出亚马逊有着严格的等级制度;Google也有清晰的等级,但是部门之间相互交错;Facebook就像是一张分布式网络;微软则是各自占山为王;苹果是一个人说了算.