欢迎访问欧博网址!

首页科技正文

勇者胜体育:LSM设计一个数据库引擎

admin2020-09-2072

Log-Structured Merge-Tree,简称 LSM。

以 Mysql、postgresql 为代表的传统 RDBMS 都是基于 b-tree 的 page-orented 存储引擎。现代计算机的最大处置瓶颈在磁盘的读写上,数据存储无法绕开磁盘的读写,纯内存型数据库除外,但由于内存存储的不稳定性,我们一样平常只将内存型的存储作为缓存系统。

为提升数据库系统的写性能,我们发现磁盘的顺序写性能远远大于随机写性能,甚至性能高于内存的随机写。以是在许多偏向写性能的数据库系统中,以牺牲一部门读性能和增大写放大的情况下引入了 LSM 数据结构。

设计一个数据库引擎

我们从头最先设计一个数据库引擎。数据模型很简朴,我们选最简朴的 Key-Value 结构,一条数据只有一个 Key 和一个 Value。操作只有 get 和 put,如下:

get(key);

put(key, value);

从最简朴的最先,每个数据库一个data.db文件,我们像写日志一样,将每条纪录 append 到文件末端。

key1,value1
key2,value2
key3,value3
key10,value10
key8,value8

这样我们已经完成了 80%了,然后需要完成读功效。如上数据文件,若需要查询 key2 数据,我们只能从文件开头最先遍历,当直到读取到 key2 数据:

for (row in rows) {
   if (row.key == "key1") {
      return row;
   }
}

好了,一个简朴的数据库就完成了。

什么?完成了?是的,完成了,虽然说拿出去会被砍死,但谁也不能否认它已经完成了一个数据库系统的最基本功效。

这样的遍历是十分花费性能的。那么怎么提高读取性能呢?建立一个内存索引“Index”即可,最简朴的方式,在内存中维护一个 Map,存储每个 key 对应的文件内容偏移量。这样读取一条纪录就只需要一次内存操作加上一次磁盘操作就可以了。

b-tree 是因何泛起的?想一想上面的 Map 结构的索引有什么瑕玷?Map 索引解决了随机单点读的性能问题,但无法解决 Rang 查询,好比需要查询 key 在 key1 和 key200 之间的数据。于是,就有了 b-tree,b 树是有序的结构树,可以很简朴的举行 Rang 查询。

b-tree 将所有数据都索引在内存中,当数据无限增进时,将无法在内存中存放这么大的索引文件。

我们来看看 LSM 的实现。

LSM 架构

SSTable:LSM 的磁盘文件,称作SSTable(Sorted String Table)。望文自满,LSM 存储在磁盘中的文件,数据也是按 Key 排序存储的,这样就可以解决上面讲到的数据量大了之后无法将数据所有索引到内存中的问题。若是磁盘文件也是有序的,那么内存索引可以接纳”希罕索引“(Sparse Index),可以每一段纪录一个索引,将数据逻辑上分成多个block,希罕索引只需要纪录每个block的偏移量,每条数据通过遍历block实现。这样索引量将大大减小。

Memtable:LSM 的内存结构叫做MemtableMemtable是一个有序结构,同样可以接纳树结构,可以用跳表。LSM 写数据时,只需要写入内存中的Memtable,当Memtable到达一定量之后,会异步刷入磁盘,就是上面的SSTable

immutable Memtable:在数据从内存Memtable刷入SSTable时,为制止读写锁导致的性能问题,LSM 会在内存中 copy 一份immutable Memtable表,顾名思义,这个数据结构不能改变,新写入的数据只会写入新的Memtableimmutable Memtable供刷盘线程读取,查询数据的请求也可以接见这个数据结构,这样若是数据在内存中,就不需要接见磁盘,可以提供数据查询的效率。

WAL:write ahead log,预写日志,关于 WAL,可以参考我之前的文章《你常听说的 WAL 到底是什么》。在 LSM 中,在数据刷入磁盘前,为防止异常导致数据丢失,LSM 会先将数据写入 WAL,然后写入 SSTable,系统重启时,LSM 会从 WAL 中回溯 SSTable,当写完一个 SSTable 时,LSM 会清算掉过时的 WAL 日志,防止 WAL 过量。

LSM 写

LSM 的写包罗四个流程:

  1. 写入 WAL
  2. 写入 memtable
  3. memtable 到达阈值时,复制 imutable memtable
  4. 异步刷入磁盘

LSM 删除

为保证顺序写磁盘,LSM 不会去直接删除数据,而是通过写一条 delete 标识来示意数据被删除,数据只有在被 Compact 时才会被真正删除。

LSM 读

LSM 读取数据将从memtableimutablesstable依次读取,直到读取到数据或读完所有条理的数据结构返回无数据。以是当数据不存在时,需要依次读取各层文件。LSM 可以通过引入布隆过滤器来先判断一个数据是否存在,制止无效的扫文件。

LSM 合并

LSM 的合并计谋是 LSM 很主要的一个部门,我们将放在下一篇文章中单独解说。

LSM 结构的应用十分普遍,诸如Bigtable,HBase,LevelDB,SQLite4, Tarantool , RocksDB,WiredTiger ,Apache Cassandra,InfluxDB 底层都使用了 LSM。只好的文章,我们将详细解说 LSM 在 leveldb 或 Cassandra 中的实现。

推荐:

Mysql 大表问题和解决
Mysql 主键问题
列式存储
时间序列数据库(TSDB)初识与选择
十分钟领会 Apache Druid
Apache Druid 底层存储设计
Apache Druid 的集群设计与事情流程

,

欧博Allbet<

www.dfxwy36.com欢迎进入欧博开户平台(Allbet Gaming),欧博开户平台开放欧博(Allbet)开户、欧博(Allbet)代理开户、欧博(Allbet)电脑客户端、欧博(Allbet)APP下载等业务

|

转载声明:本站发布文章及版权归原作者所有,转载本站文章请注明文章来源!

本文链接:https://www.chinadsn9.com/post/624.html

网友评论

2条评论
  • 2020-05-25 00:03:37

    www.66rfd.com(www.jswx10086.com)是Sunbet 申博的官方网站。www.66rfd.com提供申博开户(sunbet开户)、SunbetAPP下载、Sunbet代理合作等业务。棒棒的,期待下一个

    • 2020-07-18 11:59:39

      @AllbetGmaing开户 欧博APP下载欢迎进入欧博APP下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。还可以,之前看了一些

最新评论

  • 环球UG 10/19 说:

    Allbet开户欢迎进入Allbet开户(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。会不断进步的

  • AllbetGmaing下载 10/19 说:

    欧博APP欢迎进入欧博APP(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。踩一下,溜了

  • 联博以太坊高度 10/19 说:

    联博API接口www.326681.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。感觉已经火了

  • 皇冠APP下载 10/18 说:

    欧博手机版欢迎进入欧博手机版(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。哈哈,交流起来

  • UG环球网址 10/18 说:

    Allbet客户端下载欢迎进入Allbet客户端下载(www.aLLbetgame.us):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。可以,在看

  • Allbet登录网址 10/18 说:

    欧博亚洲官网开户网址欢迎进入欧博亚洲官网开户网址(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。找了好久,心心念念的

  • 环球UG开户 10/17 说:

    欧博allbet注册欢迎进入欧博allbet注册(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。想穿越进去

  • Allbet代理 10/16 说:

    平心在线欢迎进入平心在线官网(原诚信在线、阳光在线)。平心在线官网开www.px111.net放平心在线会员登录网址、平心在线代理后台网址、平心在线APP下载、平心在线电脑客户端下载、平心在线企业邮局等业务。很值,优点无数