`
chenwei6111
  • 浏览: 7271 次
  • 来自: ...
最近访客 更多访客>>
社区版块
存档分类
最新评论

LSM-Tree (BigTable 的理论模型)

 
阅读更多
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策略的选择是个启发。
分享到:
评论

相关推荐

    Cassandra #01 Overview.pdf

    3. **LSM-Tree 存储结构**:Cassandra 使用了类似于 BigTable 的 LSM-Tree(Log-Structured Merge Tree)存储结构,分为 Memtables 和 SSTables 两部分。Memtables 是内存中的数据结构,新写入的数据首先存储在这里...

    《HBASE系统运维实践》淘宝资深数据库工程师许飞飞

    HBase的LSMTree(Log-Structured Merge-Tree)是一种存储结构,它把数据的插入操作转化为追加写操作,这种方式可以提高写入速度,并且保证写入的稳定性。与传统数据库的B+树相比,LSM-Tree在处理追加写、合并读操作...

    12 LSM 树在 Apache HBase 等存储系统中的应用1

    Apache HBase 是一个基于 Google 的 Bigtable 模型构建的分布式、面向列的非关系型数据库(NoSQL),它广泛应用于大数据存储场景。LSM 树(Log-Structured Merge-Tree)是 HBase 等存储系统中的一种核心数据结构,...

    分布式数据库样例

    8. 分布式索引:索引是提高查询效率的关键,分布式数据库需要考虑如何在多个节点间构建和维护索引,如分布式B树、Bitcask或LSM-Tree等。 9. 拓扑结构:分布式数据库可以采用星型、树型、环形、网状等拓扑结构,具体...

    HBase在淘宝的应用和优化

    - **高性能读写**:利用LSM-Tree设计确保即使在数据量巨大的情况下也能保持较快的写入速度; - **灵活的数据模型**:支持灵活的列族和列定义,允许动态增加列; - **强一致性**:保证数据的一致性,满足业务系统对...

    Apache Cassandra

    Cassandra的一个核心概念是Log-Structured Merge-Tree(LSM树)。LSM树是针对写入密集型工作负载的高效存储结构,它通过延迟数据合并操作并将其写入到磁盘来提高写入性能。Cassandra将数据写入到内存中的结构(称为...

    大数据技术基础培训-HBase技术介绍.pptx

    与传统的关系型数据库B+树不同,HBase采用了Log-Structured Merge-Tree(LSM树)的数据结构,这种设计优化了写操作,通过先将数据写入日志,然后批量写入内存,当内存满时再flush到磁盘。后台线程会定期合并磁盘上的...

    Hadoop题库.pdf

    - LSM是Log-Structured Merge Tree的缩写,是一种用于存储和检索大量数据的数据结构。 20. **LSM描述**: - LSM结构通过顺序存储优化写操作,数据先写入内存,然后定期Flush到磁盘。 21. **LSM操作性能**: - ...

    程序员系统设计题

    9. **写速度优化**:为了提高写入速度,可以采用日志结构合并树(LSM-Tree)的数据库系统(如LevelDB或Cassandra),它们优化了写操作,牺牲了一部分读性能。 10. **Hadoop**:Hadoop是大数据处理的基石,包括HDFS...

    分布式架构存储实践

    - **LSM树**:Log-Structured Merge Tree(LSM树)是一种优化的存储结构,适用于写入密集型的应用场景,如Google Bigtable和Cassandra等分布式数据库系统。 - **位图**:位图通常用于实现Bloom Filter等数据结构,...

    Hbase架构简介、实践

    - **LSM树(Log-Structured Merge Tree)**:这是一种数据结构,用于提高读取性能。通过将写入操作记录到磁盘上的日志文件中,然后周期性地合并这些日志文件来减少磁盘访问次数。这种结构非常适合大数据环境下的读...

    Hbase.docx

    1. **LSM树(Log-Structured Merge Tree)** - **定义**:LSM树是一种特殊的树形数据结构,被设计用于提高磁盘数据写入效率。它的设计理念是在内存中维护最新的数据变更,然后批量地将这些变更写入磁盘,以此减少随机...

    Hadoop试题(卷)试题(卷)库.doc

    21. LSM含义:LSM(Log-Structured Merge Tree)是一种日志结构合并树,常用于键值存储系统,如HBase,优化写入性能。 22. LSM描述:LSM树通过顺序写入磁盘,然后定期合并数据来优化写入性能,读取操作可能需要合并...

    《大数据平台搭建与配置管理》期末试题试卷及答案AB卷2套.docx

    Java基础(类定义、import语句),以及Hadoop生态系统的其他组件,如YARN、HDFS的块和副本策略、Hive的数据模型(行、列族、表分区)、HBase的LSM(Log-Structured Merge Tree)存储结构,以及Storm的组件(Spout和...

Global site tag (gtag.js) - Google Analytics