- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
lsm 更像是一种设计索引的思想。它把数据分为两个部分,一部分放在内存里,一部分是存放在磁盘上,内存里面的数据检索方式可以利用红黑树,跳表这种时间复杂度低的数据结构进行检索.
而当 内存数据到达一定阀值的时候则会将数据同步到一个新的磁盘文件 上。此时写入磁盘的方式是顺序写,这也是为什么lsm写入性能高的原因.
打住,你说写入性能高,但是我们知道内存中的数据如果在处于正在同步到磁盘的过程中,如果此时有新数据的插入,则会带来并发读写问题,要想解决就要给这片内存区域加锁了。 加锁会导致写入过程阻塞,这样性能会高吗 ?
业界一般是这样解决的,当内存到达某个阀值后,就将这片内存标记为可读,然后新的数据插入将会写到新的内存区域,而旧的内存因为是只读的原因,便可以不加锁的进行同步到磁盘的过程.
再来思考,由于每次同步是生成一个新的磁盘文件,那么 lsm是如何再多个磁盘文件范围里进行数据检索的呢? 由于内存容量有限,每次生成的磁盘文件必然不会过大,这样会不会产生大量的小容量的磁盘文件?
我来回答下, 查找数据的时候是从多个磁盘文件中读取数据,然后对结果进行合并,只取最新的数据.
这里已经可以看到和b+tree比较明显的区别了,b+tree是插入的时候进行原地合并,而lsm则是读取时进行数据合并.
由于数据在内存中是有序的,所以在写入磁盘时,也保证了每个小的磁盘文件是有序的。我们将这些 小的磁盘文件称作sstable .
但是这样的设计还有没有问题,如果仅仅保证sstable文件有序, 不同sstable文件索引的范围有重叠的话,我们查找一个值的时候就可能会在多个sstable文件里寻找,最差的情况可能要找所有的sstable文件 ,如图:
有个索引范围是1-1000的sstable,和值范围为500-2000的sstable,当我们查找600时,无法一开始就知晓600在哪个sstable里.
因此,业界一般是这样做,对多个小文件进行合并,让磁盘文件之间不再有覆盖关系.
将索引范围合并后,两个sstable之间将不再重叠,便能快速检索到 查询的值所在的sstable了.
还没完,刚才提到了合并sstable文件,合并既能让sstable文件之间不会产生索引范围覆盖,又能减少大量小体积的sstable, 但是在什么时候进行合并呢 ?
如果在新增sstable时进行合并,新增一个sstable,发现现有的sstable和和新增的sstable索引的范围都有重合关系,是不是要将新增的sstable全部与现有的sstable进行多路归并排序,然后再生成新的一个或多个sstable.
这样的效率真的会高吗? 新增的索引体积是比较小的,如果新增一个比较小的数量级的sstable文件就去合并所有的sstable文件显然是不合理的,并且由于新增的sstable体积小,产生较为频繁, 如果每次都全量合并将会导致磁盘io在较长时间都处于一个比较高的值 .
所以,最后业界的实现一般采用下面的多层次合并的方式。每一层的容量是上一层容量的10倍.
level0层 是标记为可读的那片内存直接顺序写入磁盘形成的sstable 文件的集合,只有4个文件,注意由于level0是内存直接写入生成的,所以 level0层索引范围是有重合 的,而其他层的索引范围将不会有重合产生.
当再有新的的sstable文件生成时,那么新的sstable就会和当前层有重合的sstable合并到下一层。 当新增一个sstable时,sstable的范围是500 ~ 1000 ,那么这个范围中level0层有500 ~ 1000的sstable和300 ~ 1200的sstable都和新增的sstable有重合,所以需要将这3个sstable一起合并到下一层,而合并到下一层时,发现上一层需要合并的索引范围是500 ~ 1200,所以找出level1层中与此索引范围有重合的sstable,即level1 中标记为红色的sstable,然后再与它们进行合并产生新的sstable.
如果合并后发现当前层的容量达到了某个阀值,那么就又会将当前层的sstable继续合并到一层,一般我们会限制一个最大的层数,到达最大层数后就不再继续合并了.
这样多层滚动合并的设计能很好的解决每次新的sstable产生可能引发的高磁盘io的情况,因为它将之前的一次性合并按层次分摊到了多次,将整个合并过程分摊到了不同的时间段,缓解了写放大问题.
从lsm的实现上来看,已经能够明白它的一个数据写入和检索过程。这里再来总结一下。 lsm 写入时,会先写入到内存,内存里数据的检索一般是比较高效的数据结构,类似跳表,红黑树等,内存中的数据是有序。 内存到达某个阀值后,会将这片内存标记为只读,后续新的写入将在新的内存区域上进行,而只读的内存会将有序的数据写入到磁盘level0层,形成sstable文件。当level0层的sstable文件超过4个后,将会与level1层sstable产生合并行为,level0层以后的层级的索引范围都是没有重合的.
lsm读取数据时,同样先从内存中读取,如果读取不到则会从磁盘由低层到高层进行读取,读取到则返回,读取不到则直至最后一层为止。由于level0层以后的 每层 sstable数据都是有序且不重合的,在快速检索到数据所在的sstable 后,便能快速通过二分查找判断数据是否在该层中,真实实现,在sstable还用上了布隆过滤,来快速判断元素不在sstable的情况。如果该层找不到,则继续往下一层寻找.
可以看到,在读取数据时,最差的情况要遍历所有的层次,这也是为什么说lsm适合写多读少的场景,在读时也最好读取最近的数据.
b+tree的索引更新是原地更新,原地更新带来的代价很明显,第一个是要加锁,第二个由于更新时各个节点之前的在磁盘位置并不相邻带来的随机写入问题。 但b+tree的随机读性能很好,上千万的数据最多也只需要两三次磁盘io.
而lsm在高效写的优势下 带来了读放大问题,最坏的情况可能要在lsm多层磁盘索引结构中,每个层次都找一遍。在写频繁的场景下,查询也基本上是查最近数据时,lsm具有很好的性能.
问了一通之后,算是理清楚了lsm的原理了,平时我也倾向于向自己发问来不断剖析问题,结尾我再问一个问题吧,这篇文章里,我一共问了几个问题呢?
最后此篇关于疯一样的向自己发问-剖析lsm索引原理的文章就讲到这里了,如果你想了解更多关于疯一样的向自己发问-剖析lsm索引原理的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
本文全面深入地探讨了Docker容器通信技术,从基础概念、网络模型、核心组件到实战应用。详细介绍了不同网络模式及其实现,提供了容器通信的技术细节和实用案例,旨在为专业从业者提供深入的技术洞见和实
📒博客首页:崇尚学技术的科班人 🍣今天给大家带来的文章是《Dubbo快速上手 -- 带你了解Dubbo使用、原理》🍣 🍣希望各位小伙伴们能够耐心的读完这篇文章🍣 🙏博主也在学习阶段,如若发
一、写在前面 我们经常使用npm install ,但是你是否思考过它内部的原理是什么? 1、执行npm install 它背后帮助我们完成了什么操作? 2、我们会发现还有一个成为package-lo
Base64 Base64 是什么?是将字节流转换成可打印字符、将可打印字符转换为字节流的一种算法。Base64 使用 64 个可打印字符来表示转换后的数据。 准确的来说,Base64 不算
目录 协程定义 生成器和yield语义 Future类 IOLoop类 coroutine函数装饰器 总结 tornado中的
切片,这是一个在go语言中引入的新的理念。它有一些特征如下: 对数组抽象 数组长度不固定 可追加元素 切片容量可增大 容量大小成片增加 我们先把上面的理念整理在这
文章来源:https://sourl.cn/HpZHvy 引 言 本文主要论述的是“RPC 实现原理”,那么首先明确一个问题什么是 RPC 呢?RPC 是 Remote Procedure Call
源码地址(包含所有与springmvc相关的,静态文件路径设置,request请求入参接受,返回值处理converter设置等等): spring-framework/WebMvcConfigurat
请通过简单的java类向我展示一个依赖注入(inject)原理的小例子虽然我已经了解了spring,但是如果我需要用简单的java类术语来解释它,那么你能通过一个简单的例子向我展示一下吗?提前致谢。
1、背景 我们平常使用手机和电脑上网,需要访问公网上的网络资源,如逛淘宝和刷视频,那么手机和电脑是怎么知道去哪里去拿到这个网络资源来下载到本地的呢? 就比如我去食堂拿吃的,我需要
大家好,我是飞哥! 现在 iptables 这个工具的应用似乎是越来越广了。不仅仅是在传统的防火墙、NAT 等功能出现,在今天流行的的 Docker、Kubernets、Istio 项目中也经
本篇涉及到的所有接口在公开文档中均无,需要下载 GitHub 上的源码,自己创建私有类的文档。 npm run generateDocumentation -- --private yarn gene
我最近在很多代码中注意到人们将硬编码的配置(如端口号等)值放在类/方法的深处,使其难以找到,也无法配置。 这是否违反了 SOLID 原则?如果不是,我是否可以向我的团队成员引用另一个“原则”来说明为什
我是 C#、WPF 和 MVVM 模式的新手。很抱歉这篇很长的帖子,我试图设定我所有的理解点(或不理解点)。 在研究了很多关于 WPF 提供的命令机制和 MVVM 模式的文本之后,我在弄清楚如何使用这
可比较的 jQuery 函数 $.post("/example/handler", {foo: 1, bar: 2}); 将创建一个带有 post 参数 foo=1&bar=2 的请求。鉴于 $htt
如果Django不使用“延迟查询执行”原则,主要问题是什么? q = Entry.objects.filter(headline__startswith="What") q = q.filter(
我今天发现.NET框架在做计算时遵循BODMAS操作顺序。即计算按以下顺序进行: 括号 订单 部门 乘法 添加 减法 但是我四处搜索并找不到任何文档确认 .NET 绝对 遵循此原则,是否有此类文档?如
已结束。此问题不符合 Stack Overflow guidelines .它目前不接受答案。 我们不允许提出有关书籍、工具、软件库等方面的建议的问题。您可以编辑问题,以便用事实和引用来回答它。 关闭
API 回顾 在创建 Viewer 时可以直接指定 影像供给器(ImageryProvider),官方提供了一个非常简单的例子,即离屏例子(搜 offline): new Cesium.Viewer(
As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be
我是一名优秀的程序员,十分优秀!