视频网站免费送会员怎么做,需要注册的网站建设,建设企业网站要多少钱,电商具体是做什么的上班背景
学习极客实践课程《检索技术核心20讲》https://time.geekbang.org/column/article/215243#xff0c;文档形式记录笔记。
内容
磁盘和内存数据读取特点
工业界中数据量往往很庞大#xff0c;比如数据无法全部加载进内存#xff0c;无法支持索引的高效实时更新…背景
学习极客实践课程《检索技术核心20讲》https://time.geekbang.org/column/article/215243文档形式记录笔记。
内容
磁盘和内存数据读取特点
工业界中数据量往往很庞大比如数据无法全部加载进内存无法支持索引的高效实时更新因此对于复杂的业务问题和业务场景往往需要检索技术进行组合和升级。
内存称为随机访问存储器只要给出内存地址就能直接访问数据。 磁盘是机械器件访问数据的时候需要磁盘篇转到磁头下面尽管磁盘旋转速度很快但是和内存随机访问相比一般来说会是10万到100万倍左右但如果是顺序访问大批量数据的话磁盘的性能和内存就是一个数量级的。
为何磁盘顺序读写比较快磁盘的最小读写单位是扇区较早期的磁盘的一个扇区是512字节随着发展目前常见的磁盘扇区是4K个字节OS一次会读写多个扇区所以OS的最小读写单位是块Block也叫做簇Cluster顺序读取磁盘这样OS就能一次读取多个块这样相对下来效率会比较高。
PSSSD硬盘和内存读写效率
以机械硬盘举例顺序读写比随机读写少了多次 seek 的时间。 HDD 的 seek 耗时是 10ms 吞吐率是 100MB/s也就是每秒能 write 100MB 的数据。 那么以 1KB 为单位纯写入1KB数据只需要 10us 是seek 的 1/1000。SSD在seek时间上比HDD要快很多但是SSD的工作原理如下SSD最高层是 NAND Flash每个 NAND Flash 里有多个 Block Block 里又包括很多 PageSSD 的特点就是读和写都要以 Page 为单位最少一个 Page。通常一个 Page 是 4k 或 8k。顺序读写只涉及到一个Page随机读写涉及到多个Page造成读写放大。
SSD是以page作为读写单位以block作为垃圾回收单位因此批量顺序写性能依然大幅高于随机写SSD的性能和内存相比依然有差距因此先在内存处理好再批量写入SSD依然是高效的。
索引和数据分离之BTree
对磁盘的访问次数要尽可能少假如使用一个数组存储信息到磁盘这个大数组需要占用很多块在查找的过程中就需要多次加载块到内存进行二分查找直到查询结束这样一次查询可能需要访问很多次磁盘这种情况应该尽量避免。索引和数据文件分离是一种常见的设计思路BTree就是这莫设计的。
索引和数据文件分离就是假如需要存储的内容比较多那么得放入磁盘但是全部字段放入的话查询需要访问很多次磁盘效率比较低因此可以拆分一个索引文件索引文件只存储数据项的唯一标识以及指向磁盘数据的指针这样索引文件会小很多某些情况下可以加载进内存进行查询。
这种称为线性索引对于更新频繁的场景有序数据并不是一个很好的选择删除数据更新数据的话需要进行索引调整而数组是连续的内存空间二叉树和Hash索引往往更具有普适性但是Hash索引又不支持范围查询因此使用二叉树做索引比较合适。 B Tree结构
B 树给出了将树形索引的所有节点都存在磁盘上的高效检索方案使得索引技术摆脱了内存空间的限制得到了广泛的应用。 B 树是一棵完全平衡的 m 阶多叉树。所谓的 m 阶指的是每个节点最多有 m 个子节点并且每个节点里都存了一个紧凑的可包含 m 个元素的数组。
B树的一个关键设计就是节点的数据大小和OS块大小一致这样可以提高磁盘的读取效率节点存储的元素不是一个元素而是m个元素的有序数组。
B树的另外一个关键设计就是所有节点分为叶子节点、非叶子节点结构是一样的但是存储的内容是不同的。非叶子节点存储key以及树形结构的指针而不是数据的指针这样可以使用更少的节点组织数据。叶子节点可以存储指针 or 数据像MySQL中的innoDB就是存储的数据MyISAM存储的就是指针。
另外B树还讲同一层的所有节点做成有序的双链表这样可以进行很好的范围查询以及灵活调整能力。
B 树的一个节点就能存储一个包含 m 个元素的数组这样的话一个只有 2 到 4 层的 B 树就能索引数量级非常大的数据了因此 B 树的层数往往很矮。比如说一个 4K 的节点的内部可以存储 400 个元素那么一个 4 层的 B 树最多能存储 400^4也就是 256 亿个元素。
另外可以前几层的节点数据加载到内存中做缓存进一步减少索引文件磁盘访问次数。比如说对于一个 4 层的 B 树每个节点大小为 4K那么第一层根节点就是 4K第二层最多有 400 个节点一共就是 1.6M第三层最多有 400^2也就是 160000 个节点一共就是 640M。对于现在常见的计算机来说前三层的内部节点其实都可以存储在内存中只有第四层的叶子节点才需要存储在磁盘中。这样一来我们就只需要读取一次磁盘即可。这也是为什么B 树要将内部节点和叶子节点区分开的原因。通过这种只让内部节点存储索引数据的设计我们就能更容易地把内部节点全部加载到内存中了。
BTree动态调整
插入删除元素节点调整比如以一个m3的B树需要插入ID6的这个记录首先需要二分查找到叶子节点叶子节点未满的话直接插入就行。
叶子节点满了的话需要进行叶子节点块分裂比如插入ID10的记录就要进行分裂逻辑就是生成一个新的节点然后讲数据平分。叶子节点分裂完成以后上一层的内部节点也需要修改。但如果上一层的父节点也是满的那么上一层的父节点也需要分裂。
删除也需要动态调整节点也需要进行判断如果从一个元素已经满的叶子节点删除一个元素直接删除即可。如果一个叶子节点删除某个元素后有一半以上的空间为空就需要移动兄弟的节点可以成功转移的条件是元素转移后该节点及其兄弟节点的空间必须都能维持在半满以上。如果无法满足这个条件就说明兄弟节点其实也足够空闲那我们直接将该节点的元素并入兄弟节点然后删除该节点即可。
思考1B树的一个很大优势就是适合做范围查询。如果我们要检索值在 x 到 y 之间的所有元素你会怎么操作呢想到就是找出x值所在的节点然后沿着叶子节点向后找直到找到y。这里需要注意B树的叶子节点块之间也不是连续存储的采用两次二分就不太适合了不能将全部数据一次取出。
非关系型数据结构存储之LSM树
在关系型数据库之外还有许多常见的大数据应用场景比如日志系统、监控系统。这些应用场景有一个共同的特点那就是数据会持续地大量生成而且相比于检索操作它们的写入操作会非常频繁。另外即使是检索操作往往也不是全范围的随机检索更多的是针对近期数据的检索。
如果是一个日志系统每秒钟要写入上千条甚至上万条数据使用B树随机写入这样的磁盘操作代价会使得系统性能急剧下降甚至无法使用。一种常见的设计思路和检索技术LSM 树Log Structured Merge Trees。LSM 树也是近年来许多火热的 NoSQL 数据库中使用的检索技术。
LSM的设计思路
针对B树随机写入慢的特点可以考虑将数据按照 block块 写入可以大幅减少写入次数。
LSM树就是根据这个思路设计的**批量写入以批量顺序写入磁盘减少随机写入次数 **先将数据放入内存的树中积攒到一定量在写入磁盘当数据写入时延迟写磁盘将数据先存放在内存中的树里进行常规的存储和查询。当内存中的树持续变大达到阈值时再批量地以块为单位写入磁盘的树中。
图源https://zhuanlan.zhihu.com/p/415799237
LSM的结构是一个森林类似BKD-Tree可以分为内存树、磁盘树
至于磁盘树可以使用类似B树实现按照Block写入效率比较高磁盘树是一棵满二叉树其实是一个SSTable结构存储kv结构为了好理解可以理解为B树也就是叶子节点都是满的。对于内存树结构可以使用AVL、跳表等实现。数据首先写入到内存树满了之后刷到磁盘中在内存中的数据支持更快的检索和修改。
LSM的结构 主要有三部分组成
_MemTable_MemTable是在**内存**中的数据结构用于保存最近更新的数据会按照Key有序地组织这些数据LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义例如Hbase使跳跃表来保证内存中key的有序。因为数据暂时保存在内存中内存并不是可靠存储如果断电会丢失数据因此通常会通过WAL(Write-ahead logging预写式日志)的方式来保证数据的可靠性。_Immutable MemTable_当 MemTable达到一定大小后会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理在转存过程中不阻塞数据更新操作。_SSTable(Sorted String Table)磁盘树可以有很多层每层可以有多个SSTable有序键值对_集合是LSM树组在**磁盘**中的数据结构。为了加快SSTable的读取可以通过建立key的索引以及布隆过滤器来加快key的查找。一个key可以存在不同level的的不同SSTable中但是上一层的level的key新鲜度总是高于下层的同一层中的多个SSTable只能有一个key。 LSM的崩溃恢复
内存树的数据断电易丢失LSM使用WAL预写日志技术来保证数据不丢失在写入数据到内存的时候快速的写入日志到磁盘具体步骤
内存中的程序在处理数据时会先将对数据的修改作为一条记录顺序写入磁盘的 log 文件作为备份。由于磁盘文件的顺序追加写入效率很高因此许多应用场景都可以接受这种备份处理。在数据写入 log 文件后备份就成功了。接下来该数据就可以长期驻留在内存中了。系统会周期性地检查内存中的数据是否都被处理完了比如被删除或者写入磁盘并且生成对应的检查点Check Point记录在磁盘中。然后我们就可以随时删除被处理完的数据了。这样一来log 文件就不会无限增长了。系统崩溃重启我们只需要从磁盘中读取检查点就能知道最后一次成功处理的数据在 log 文件中的位置。接下来我们就可以把这个位置之后未被处理的数据从 log 文件中读出然后重新加载到内存中。
通过这种预先将数据写入 log 文件备份并在处理完成后生成检查点的机制可以安全的使用内存来检索、存储数据了。
LSM的数据合并思路
内存树被写满之后需要将数据合并到磁盘中的树中称之为滚动合并Rolling Merge。 便于理解同样磁盘树理解为B树参考链表的归并排序将内存树和磁盘树的数据读取出来放入内存进行归并需要注意的是为了提高磁盘树的读写效率对于磁盘树除了根节点外的节点尽可能放入连续的块中这样可以按块加载多个相邻的数据节点这样的块叫做 多页块Multi-Pages Block。 合并步骤
第一步以多页块为单位将 C1 树的当前叶子节点从前往后读入内存。读入内存的叫作清空块Emptying Block意思是处理完以后会被清空。第二步将 C0 树的叶子节点和清空块中的数据进行归并排序把归并的结果写入内存的一个新块中叫作填充块Filling Block。第三步如果填充块写满了我们就要将填充块作为新的叶节点集合顺序写入磁盘。这个时候如果 C0 树的叶子节点和清空块都没有遍历完我们就继续遍历归并将数据写入新的填充块。如果清空块遍历完了但是C1叶子节点还没遍历完我们就去 C1 树中顺序读取新的多页块加载到清空块中。第四步重复第三步直到遍历完 C0 树和 C1 树的所有叶子节点并将所有的归并结果写入到磁盘。这个时候我们就可以同时删除 C0 树和 C1 树中被处理过的叶子节点。 这样就完成了滚动归并的过程。在 C0 树到 C1 树的滚动归并过程中你会看到几乎所有的读写操作都是以多页块为单位将多个叶子节点进行顺序读写的。而且因为磁盘的顺序读写性能和内存是一个数量级的这使得 LSM 树的性能得到了大幅的提升。
LSM树的检索之删除标记
先查内存树如果内存有直接作为结果返回内存中的数据是最新的。 如果内存树没有查询磁盘树先以单棵B树为例这时候查到数据需要检查数据的时效性因为LSM批量写入的特点可能存在磁盘脏数据问题。 如一个数据已经被写入系统了并且我们也把它写入 C1 树了。但是在最新的操作中这个数据被删除了那我们自然不会在 C0 树中查询到这个数据。可是它依然存在于 C1 树之中。LSM解决办法是依然采用延迟写入尽量避免随机访问磁盘树对于被删除的数据同样将这个数据key插入到内存树只不过key上加了删除标志。 这样一来当我们在 C0 树中查询时如果查到了一个带着删除标志的 key就直接返回查询失败我们也就不用去查询 C1 树了。在滚动归并的时候我们会查看数据在 C0 树中是否带有删除标志。如果有滚动归并时就将它放弃。这样 C1 树就能批量完成“数据删除”的动作。
LSM树的两种合并策略
合并时机
因为内存不是无限大Level 0树达到阈值时需要将数据从内存刷到磁盘中这是合并操作的第一个场景需要对磁盘上达到阈值的顺序文件进行归并并将归并结果写入下一层归并过程中会清理重复的数据和被删除的数据(墓碑标记)。我们分别对上述两个场景进行分析
为了防止SSTable的数量不断增加合并策略很关键主要介绍两种基本策略size-tiered和leveled
size-tiered 策略size-tiered策略保证每层SSTable的大小相近同时限制每一层SSTable的数量。如上图每层限制SSTable为N当每层SSTable达到N后则触发Compact操作合并这些SSTable并将合并后的结果写入到下一层成为一个更大的sstable。由此可以看出当层数达到一定数量时最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重**。**即使对于同一层的SSTable每个key的记录是可能存在多份的只有当该层的SSTable执行compact操作才会消除这些key的冗余记录。leveled策略限制每一层的SSTable总文件大小。 LSM的检索
如果内存树没有查询磁盘树以SSTable为例先查level1的多个SSTable没有就查level2的一次类推如果在level2的SSTabel都找到了key就返回结果。
综上我们可以给出LSM树的优缺点
优增、删、改操作飞快写吞吐量极大。缺对于SSTable实现的磁盘树读操作性能相对被弱化不擅长区间范围的读操作 归并操作较耗费资源。
如果说B/B树的读写性能基本平衡的话LSM树的设计原则通过舍弃部分读性能换取了无与伦比的写性能。该数据结构适合用于写吞吐量远远大于读吞吐量的场景得到了NoSQL届的喜爱和好评。
思考LSM磁盘树可以很多层每层可有多个SSTable多个SSTable不像单个B树那样可以直接按照key查找值而是一个key可以存在不同层的不同SSTable中一层多个SSTable只能有一个相同key这样查时间比较久的数据的时候如何保证找到最新的key以及值一个key可以存在不同level中但是上一层的level的key新鲜度总是高于下层的同一层中多个SSTable只有一个key。
思考1内存树可以使用什么结构取决于应用场景可以使用哈希表、红黑树、跳表等比如需要范围扫描可以使用跳表或者红黑树、AVL比较合适。
