检索技术核心20讲
陈东
奇虎360商业产品事业部资深总监
立即订阅
1626 人已学习
课程目录
已更新 13 讲 / 共 25 讲
0/4登录后,你可以任选4讲全文学习。
课前必学 (2讲)
开篇词 | 学会检索,快人一步!
免费
导读 | 三步走策略,轻松搞定检索!
基础技术篇 (8讲)
01 | 线性结构检索:从数组和链表的原理初窥检索本质
02 | 非线性结构检索:数据频繁变化的情况下,如何高效检索?
03 | 哈希检索:如何根据用户ID快速查询用户信息?
04 | 状态检索:如何快速判断一个用户是否存在?
05 | 倒排索引:如何从海量数据中查询同时带有“极”和“客”的唐诗?
测一测 | 检索算法基础,你掌握了多少?
特别加餐 | 倒排检索加速(一):工业界如何利用跳表、哈希表、位图进行加速?
特别加餐 | 倒排检索加速(二):如何对联合查询进行加速?
进阶实战篇 (3讲)
06 | 数据库检索:如何使用B+树对海量磁盘数据建立索引?
07 | NoSQL检索:为什么日志系统主要用LSM树而非B+树?
08 | 索引构建:搜索引擎如何为万亿级别网站生成索引?
检索技术核心20讲
登录|注册

07 | NoSQL检索:为什么日志系统主要用LSM树而非B+树?

陈东 2020-04-10
你好,我是陈东。
B+ 树作为检索引擎中的核心技术得到了广泛的使用,尤其是在关系型数据库中。
但是,在关系型数据库之外,还有许多常见的大数据应用场景,比如,日志系统、监控系统。这些应用场景有一个共同的特点,那就是数据会持续地大量生成,而且相比于检索操作,它们的写入操作会非常频繁。另外,即使是检索操作,往往也不是全范围的随机检索,更多的是针对近期数据的检索。
那对于这些应用场景来说,使用关系型数据库中的 B+ 树是否合适呢?
我们知道,B+ 树的数据都存储在叶子节点中,而叶子节点一般都存储在磁盘中。因此,每次插入的新数据都需要随机写入磁盘,而随机写入的性能非常慢。如果是一个日志系统,每秒钟要写入上千条甚至上万条数据,这样的磁盘操作代价会使得系统性能急剧下降,甚至无法使用。
那么,针对这种频繁写入的场景,是否有更合适的存储结构和检索技术呢?今天,我们就来聊一聊另一种常见的设计思路和检索技术:LSM 树(Log Structured Merge Trees)。LSM 树也是近年来许多火热的 NoSQL 数据库中使用的检索技术。

如何利用批量写入代替多次随机写入?

刚才我们提到 B+ 树随机写入慢的问题,对于这个问题,我们现在来思考一下优化想法。操作系统对磁盘的读写是以块为单位的,我们能否以块为单位写入,而不是每次插入一个数据都要随机写入磁盘呢?这样是不是就可以大幅度减少写入操作了呢?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《检索技术核心20讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(12)

  • innocent
    为了性能内存中的树至少有两棵吧

    作者回复: 你提到了性能问题,的确是这样的。在高性能的lsm树实现中,不仅仅是内存中要有两棵,磁盘上还要有多棵。
    具体工业界是怎么真正实现一个高性能的lsm树,后面我会再具体介绍。

    2020-04-11
    1
    2
  • 兰柯一梦
    感觉取决于系统需要提供什么样的功能,如果系统需要提供高效的查询不需要范围scan那么C0用hashmap都可以,如果需要scan那么平衡树或者skiplist比较合适。leveldb是使用skiplist来实现的,这里的checkpoint主要目的是定期将数据落盘后用来对log文件进行清理的,使得系统重启时不需要重放过多的log影响性能

    作者回复: 你说的很对,取决于使用场景。有的系统的确是使用哈希表的。还有使用红黑树和跳表的都有。

    2020-04-10
    2
  • xzy
    请问,如果wal所在的盘和数据在同一个盘,那怎么保证wal落盘是顺序写呢,我理解也得寻道寻址

    作者回复: 你这个问题很好!我提炼出来有三个点:
    1.wal的日志文件能否保证在物理空间上是顺序的?
    这个是可以做到的。日志文件都是追加写模式,包括可以提前分配好连续的磁盘空间,不受其他文件干扰。因此是可以保证空间的连续性。
    2.wal的日志文件和其他数据文件在一个磁盘,那么是否依然会面临磁头来回移动寻道寻址的问题?
    这个问题的确存在,如果日志文件和数据文件在同一个盘上,的确可能面临一个磁头来回移动的情况。因此,尽量不要在一个磁盘上同时开太多进程太多文件进行随机写。包括你看lsm的写磁盘,也是采用了顺序写。
    3.如果第二个问题存在,那么wal依然高效么?
    wal依然是高效的。一方面,如果是wal连续写(没有其他进程和文件竞争磁头),那么效率自然提升;另一方面,往磁盘的日志文件中简单地追加写,总比处理好数据,组织好b+树的索引结构再写磁盘快很多。

    2020-04-10
    1
    1
  • 考虑的点
    1 随机和顺序存取差距不大
    2 什么样的有序结构适合高并发的写入
    对于2,必须插入的时候只影响局部,这样上锁这样开销就只在局部细粒度上,如果是树可能存在需要调整树高的各种旋转或者分裂合并操作。对于1,在说不用像b树那样降低树高,底层数据节点搞比较大的块,可以充分利用指针这种随机读取的力量,当然块太小有内存碎片之类的问题,以及jvm老年代跨代引用新生代之类问题,所以hbase中跳表的实现是基于chunk的。
    感觉自己好像逻辑不是很通,自己还想的不够透彻,其实也在思考全内存的数据库和基于b树这样的数据库在它的缓存可以容纳全部块,不用换入换出,这两种情况下全内存数据库的优势在哪里。

    作者回复: 全内存数据库的确是一个研究热点。Redis的广泛流行也是这个潮流的一个例子。
    b+树即使能全部缓存到内存中,但你思考一下它插入删除的效率(分裂合并节点),它不会比红黑树这些结构效率高。因此,纯内存的环境下,红黑树和跳表这类结构更受欢迎。

    2020-04-10
    1
  • pedro
    不知道为什么我昨天发布成功的评论没有被通过,可能 bug了,那我重说一次😭。

    问题,前面的文章提到 B 树是为了解决磁盘 io 的问题而引入的,所以 B 树自然不适合做内存索引,适合的是红黑球和跳表。

    当然也有例外,如小而美的 Bitcask 就选择了哈希表作为内存索引,是学习 Log-structure 的最佳入门数据库。

    作者回复: 很好!你提到了bitcask,它是用哈希表作为内存索引的。其他的一些nosql实现,还有选择红黑树和跳表的。因此你会发现,对于内存中高效检索的技术选型,不同应用会根据自己的需求,选择我们在基础篇介绍过的适用技术。

    2020-04-11
  • 那时刻
    请问两个关于检查点check point的问题。
    1.检查点也是要落盘,和WAL一样的位置么?
    2.在数据删除和同步到硬盘之后会生成检查点,还有其它情况会生成检查点么?

    作者回复: 1.check point的信息是独立存在的,和wal的日志文件是不同文件。
    2.check point的触发条件可以有多个,比如说间隔时长达到了预定时间,比如说wal文件增长到一定程度,甚至还可以主动调用check point相关命令强制执行。

    2020-04-11
  • xzy
    你好,这里还有个问题:如果是ssd,顺序写和随机写的差异不大,那么是否还有必要写wal, 毕竟写wal相当于double写了数据,那直接就写数据是否性能还会更好呢

    作者回复: 这是一个好问题!对于SSD,这些理论和方法是否依然有效?答案是yes。
    考虑这么两点:
    1.SSD是以page作为读写单位,以block作为垃圾回收单位,因此,批量顺序写性能依然大幅高于随机写!
    2.SSD的性能和内存相比依然有差距,因此,先在内存处理好,再批量写入SSD依然是高效的。

    2020-04-10
  • 一步
    当内存的C0 树满时, 都要 把磁盘的 C1 树的全部数据 加载到内存中合并生成新树吗? 我感觉这样性能不高啊。

    还有就是 类型日志系统,都是天然按照时间排序;这样的话 ,就可以直接把 C0 树的叶子节点直接放到 C1 树的叶子节点后面啊,没有必要在进行合并生成新树了

    作者回复: 你提了一个非常好的问题!把c1树的全部叶子节点处理一次的确效率不高,因此实际上会有多棵不同大小的磁盘上的树。包括工业界还有其他的优化思路。后面会介绍。
    此外,直接把c0树的叶子节点放在c1树后面,这样的话叶子节点就不是有序的了,就无法高效检索了。

    2020-04-10
  • 一步
    填充块写满了,我们就要将填充块作为新的叶节点集合顺序写入磁盘,

    这个时候 填充快写的磁盘位置会是之前C1 叶子节点 清空块的位置吗? 还是另外开辟有个新的空间,当新的树生成后,在把旧的C1树 磁盘数据空间在标记为删除?

    作者回复: 是新的磁盘空间。因为c1树要保证在磁盘上的连续性,如果是利用原c1树的旧空间的话,可能会放不下(因为合并了c0树的数据)。

    2020-04-10
  • 一步
    对于 对数据敏感的数据库,基本上都会采用 WAL 技术,来防止数据在内存中丢失, 比如 MySQL 的 redo log
    2020-04-10
  • Mq
    B+树数据存储是以块为单位的,读到内存也是以块为单位,一个块里面如果数据多了顺序查找也不是太快。
    内存存储我觉得应该选择跳表,他的查找、插入、删除都跟树一样,只是空间上会多一些消耗,他对范围查找的支持是其他内存数据结构一大优势。
    另外,我感觉文章中有把c0写成c1的地方,不知道我理解对不‘和普通的 B+ 树相比,C1 树有一个特点’

    作者回复: 在内存数据库里面,Redis是一个典型的代表,它的确就是使用跳表的。
    另外两点:
    1.b+树块内的查找,可以使用二分查找,而不是顺序查找,这样能加快检索效率。
    2.你说的是否“c0和c1树写错”的地方,这个的确没有写错哦,你可以仔细想一想,为什么c1树有这个特点“叶子节点是全满的”。

    2020-04-10
    1
  • 每天晒白牙
    思考题
    对于c0树因为是存放在内存中的,可以用平衡二叉树或跳表来代替 B+ 树

    作者回复: 是的。如果你有关注一些内存数据库,你会发现,有好些是使用跳表和红黑树来实现的。比如Redis。
    可见,b+树不是万能的。我们理解了存储介质的特性以后,能帮助我们在合适的场景做出正确的技术选型。

    2020-04-10
收起评论
12
返回
顶部