LSM Tree 底层设计理念
- 场景:设计一个海量读写的的kv数据库,优先保证写入速度,但是读取速度也不能很慢
- 因为海量数据存储,不能使用内存,得存到文件里。
- Q:对已经落盘的文件,怎么根据key修改value
- A:读取文件找到指定的key,修改指定的值
- Q:需要随机磁盘io,磁头、磁道、扇区三者合一,然后进行io操作,慢
- A:追加写:不找之前的了,直接写新的key-value(顺序io),新的key代替老的key
- Q:查询的时候一个key对应多个value,还需要排序过滤,慢
- A:异步compaction:新建一个文件(SSTable)接受新的写入数据,写到一定数量后关闭,然后创建一个新的SSTable,对关闭的SSTable进行异步的合并,根据key+版本删除旧版本数据
- Q:文件中检索指定的key 有什么方案
- A:同一个SSTable中,key按顺序排列
- A:创建若干索引文件
- A:每个SSTable,记录其 kmax,kmin
- A:对SSTable切分,分出若干segement并记录kmax,kmin
- A:每个segement添加一个bloomfilter,用于快速过滤
- Q:为了key在SSTable中按序排列,那写SSTable的过程也是随机io
- A:创建一个内存中的memtable,写入过程统一写入memtable,在内存中使key有序,而且同一个memtable写入相同的key,直接就可以在memtable中进行合并,一定大小后,溢写到磁盘形成SSTable,这样SSTable就是 key有序且唯一的数据结构,溢出过程也是顺序io
- Q:写入过程和溢写磁盘过程有冲突
- A:当一个memtable满足溢出条件后就停止写入,创建一个新的memtable,并将前一个memtable 改成 immutable memtable(不可变更的内存表)同时将 immutable memtable溢写磁盘
- Q:内存有序的memtable,用什么数据结构实现?
- A:跳表、红黑树,跳表合适并发比较好、实现更简单(不一定,lsm只是一个架构,怎么实现无所谓)
- Q:内存写磁盘的操作不够健壮,万一写的过程失败了怎么办
- A:采用预写日志机制WAL,将数据先写入日志中,然后写入memtable(该过程是原子性的),如果immutable memtable溢写形成(该过程是原子性的)SSTable的过程失败,可以将WAL数据重放,形成memtable,然后重试
- Q:每个sstable内部主键唯一且有序,但是多个之间还是会有冲突啊
- A:没错由immutable memtable形成的SSTable确实会有这个问题,我们得想办法把他们合并起来
- A:由immutable memtable形成的SSTable我们给他起个名字叫Level0层,假设0层的数据最多存10MB,如果一旦超出10MB我们就把它放到Level1层,而且在放的时候我们要根据Key进行合并,每个SSTable都有key区间(比如从a-e),在放到Level1层的时候,我们先根据key区间找到会受到合并影响的Level1的SSTable(比如SSTable1[a,c],SSTable2[d,e]),然后让他们三个SSTable 做一个排队按高矮个排序的动作,咋排呢?
- 先都站到一起,根据Key排序小的在前,大的在后,相同的key后来的替代先来的,这样之后三个SSTable的key就合并成了一个不重复且有序的大SSTable,但是也不能太大,按照大小限制,再切分成多个SSTable(上述假设可能最后会形成 [a,c],[d,e]两个SSTable)
- 这样从Level1层开始,一个key多个值的问题我们解决了,SSTable之间的key也是全局有序。
有序且唯一
- Q:Level0层的SSTable合并到Level1时,万一某个SSTable包含了Level2的最小Key和最大Key,这样就覆盖到了Level1整层,那Level1中所有的SSTable都要进行一次排序啊
- A:确实会有这个问题,因为level0中的SSTable key的范围没法控制,那得继续往下分层(这就是分层原因),Level0层存10M,那Level1层就存100M(10倍),Level1层满了就往Level2进行合并,level1中的SSTable key的范围肯定不会出现[Minkey,MaxKey],因为是有序的,而且每个SSTable的数据量均等。
- A:为了防止数据量过大依然导致这种问题,我们多分几层(默认7层),假设L0 10M 那7层 10*10^7,能存很多了。
- Q:那分这么多层,找的范围也多啊
- A:不是的,数据是从上往下流转的,新来了一个a=1,那我先找memtable,再找L0 SSTable、L1 SSTable。。,找到之后就不往下找了,自动就完成了冷热数据分离,热数据在上边,冷数据在下边
- Q:那万一我查一个最冷的Key呢?
- A:那就是最长寻址过程了:
- 1、memtable 内存快速查询,如果没找到
- 2、immutable memtable 内存快速查询,如果没找到
- 3、Level0,根据索引文件,获取到可能包含这个Key的所有SSTable,每一个SSTable都得读一遍,看看是否存在,但是可以倒序读,先读新的SSTable,再读老的SSTable,读取到就不用继续往下读了,如果没找到
- 4、Level1-Levelk,每一层都要根据索引文件,直接定位到包含这个key的SSTable segement,如果有,只会有一个SSTable,因为每一层内部都是有序的
- 5、对这个SSTable的所有的segement,循环进行bloom过滤,判断是否存在
- 6、bloom如果存在,判断是否为bloom假命中,
- 7、如果真命中,最后给出value的值,否则判断下一个segement
- 6、bloom如果存在,判断是否为bloom假命中,
- 5、对这个SSTable的所有的segement,循环进行bloom过滤,判断是否存在
- 4、Level1-Levelk,每一层都要根据索引文件,直接定位到包含这个key的SSTable segement,如果有,只会有一个SSTable,因为每一层内部都是有序的
- 3、Level0,根据索引文件,获取到可能包含这个Key的所有SSTable,每一个SSTable都得读一遍,看看是否存在,但是可以倒序读,先读新的SSTable,再读老的SSTable,读取到就不用继续往下读了,如果没找到
- 2、immutable memtable 内存快速查询,如果没找到
- 1、memtable 内存快速查询,如果没找到
- A:那就是最长寻址过程了:
相关文章:
LSM Tree 底层设计理念
场景:设计一个海量读写的的kv数据库,优先保证写入速度,但是读取速度也不能很慢 因为海量数据存储,不能使用内存,得存到文件里。 Q:对已经落盘的文件,怎么根据key修改value A:读取文件…...
面向对象设计规则和各类设计模式
面向对象设计(Object-Oriented Design, OOD)是一种软件设计方法论,它使用对象、类、继承、封装、多态等概念来组织代码。面向对象设计的核心目标是提高软件的可维护性、可扩展性和复用性。在面向对象设计中,遵循一定的设计原则和模…...
Artec Leo3D扫描仪在重型机械设备定制中的应用【沪敖3D】
挑战:一家加拿大制造商需要有效的方法,为富于变化且难度较高的逆向工程,快速、安全、准确地完成重型机械几何采集。 解决方案:Artec Leo, Artec Studio, Geomagic for SOLIDWORKS 效果:Artec Leo三维扫描代替过去的手动…...
Linux下socket广播通讯的实现
概念大家都很清楚,不赘述。 广播必然用UDP这套东西。 setsockopt() 函数及其在广播中的应用: 在 C 网络编程中,setsockopt() 函数用于设置套接字选项,这些选项可以控制套接字的各种行为。对于广播通信,我们特别关心…...
Tiptap,: 富文本编辑器入门与案例分析
Tiptap 是一个现代的富文本编辑器,基于 ProseMirror 打造,旨在提供一个灵活且功能强大的文本编辑解决方案。它具有开箱即用的能力,同时也允许开发者根据业务需求进行高度定制化扩展。与传统的富文本编辑器相比,Tiptap 提供了更精细…...
数智读书笔记系列002 埃隆·马斯克传
书名:埃隆马斯克传 作者:【美】沃尔特艾萨克森 译者:孙思远;刘家琦 出版社:中信出版集团 出版时间:2023年9月 ISBN:9787521758399 这本书是关于特斯拉CEO埃隆马斯克的传记,作者…...
linux环境一句话后门
原文地址:linux环境一句话后门 – 无敌牛 欢迎参观我的个人博客:无敌牛 – 技术/著作/典籍/分享等 注意:本文章只做网络安全技术交流使用,切莫用来做坏事。 也可以叫一句话木马,一个意思。 设置监听 回连端口可以…...
django——admin后台管理1
一、admin后台管理 访问url进入: http://127.0.0.1:8000/admin 创建超级管理用户 终端输入以下命令: python manage.py createsuperuser (py36_pingping) E:\django学习\day03-django入门\demo>python manage.py createsuperuser Username: mo…...
QT图形/视图架构详解(一)
场景、视图与图形项 图形/视图架构主要由 3 个部分组成,即场景、视图和图形项,三者的关系如图所示: 场景、视图和图形项的关系 场景(QGraphicsScene 类) 场景不是界面组件,它是不可见的。场景是一个抽象的…...
h5 区分ios和安卓
h5 区分ios和安卓 const systemInfo uni.getSystemInfoSync(); if (systemInfo.platform "ios" || systemInfo.platform "android") {}h5 区分微信小程序与app用条件编译条件编译 js #ifdef MP-WEIXIN #endif...
爬虫基础知识点
最近看了看爬虫相关知识点,做了记录,具体代码放到了仓库,本文仅学习使用,如有违规请联系博主删除。 这个流程图是我使用在线AI工具infography生成的,这个网站可以根据url或者文本等数据自动生成流程图,挺…...
golang 实现简单redis服务3(实现多类型数据结构支持)
redis各种数据类型的工作原理stringlisthashset(集合)zset(有序集合)(思考1):为什么redis使用跳跃表而不是红黑树?(思考2): 都可以范围取值,为什么mysql使用b树不用跳跃表,为什么redis使用跳跃表不用b树? 之前的redis只实现了基本数据string类型的操作,那能不能实现多种数据类…...
【硬件测试】基于FPGA的4ASK调制解调通信系统开发与硬件片内测试,包含信道模块,误码统计模块,可设置SNR
目录 1.算法仿真效果 2.算法涉及理论知识概要 3.Verilog核心程序 4.开发板使用说明和如何移植不同的开发板 5.完整算法代码文件获得 1.算法仿真效果 本文是之前写的文章: 《基于FPGA的4ASK调制解调系统,包含testbench,高斯信道模块,误码率统计模块,可以设置不同SNR》 的…...
配置mysqld(读取选项内容,基本配置),数据目录(配置的必要性,目录下的内容,具体文件介绍,修改配置)
目录 配置mysqld 读取选项内容 介绍 启动脚本 基本配置 内容 端口号 数据目录的路径 配置的必要性 配置路径 mysql数据目录 具体文件 修改配置时 权限问题 配置mysqld 读取选项内容 介绍 会从[mysqld] / [server] 节点中读取选项内容 优先读取[server] 虽然服务…...
【roadMap】我转行软件测试的经历
软件测试这行咋样? 如果你简单了解过「软件测试工程师」这个岗位,就会知道它的基本特点: 待遇比开发低,比其他行业高入门丝滑,算是技术岗最简单的一类测试行业有细分领域:功能、性能、自动化… 每个行业…...
回归任务与分类任务应用及评价指标
能源系统中的回归任务与分类任务应用及评价指标 一、回归任务应用1.1 能源系统中的回归任务应用1.1.1 能源消耗预测1.1.2 负荷预测1.1.3 电池健康状态估计(SOH预测)1.1.4 太阳能发电量预测1.1.5 风能发电量预测 1.2 回归任务中的评价指标1.2.1 RMSE&…...
半导体制造全流程
半导体制造是一个极其复杂且精密的过程,主要涉及将硅片加工成功能强大的芯片。以下是半导体制造的全流程概述: 1. 硅材料制备 硅提纯: 使用冶金级硅,进一步提纯为高纯度硅(电子级硅),纯度可达 …...
Mac m2电脑上安装单机Hadoop(伪集群)
1. 引言 本教程旨在介绍在Mac 电脑上安装Hadoop 2. 前提条件 2.1 安装JDK Mac电脑上安装Hadoop,必须首先安装JDK,并配置环境变量(此处不做详细描述) 2.2 配置ssh环境 关闭防火墙 在Mac下配置ssh环境,防止后面启…...
React 第十六节 useCallback 使用详解注意事项
useCallback 概述 1、useCallback 是在React 中多次渲染缓存函数的 Hook,返回一个函数的 memoized的值; 2、如果多次传入的依赖项不变,那么多次定义的时候,返回的值是相同的,防止频繁触发更新; 3、多应用在 父组件为函…...
悬赏任务源码(悬赏发布web+APP+小程序)开发附源码
悬赏任务源码是指一个软件或网站的源代码,用于实现悬赏任务的功能。悬赏任务是指发布方提供一定的奖励,希望能够找到解决特定问题或完成特定任务的人。悬赏任务源码通常包括任务发布、任务接受、任务完成和奖励发放等功能的实现。搭建悬赏任务源码是一个…...
Collection接口
目录 一. Collection基本介绍 二. Collection中的方法及其使用 1. 添加元素 (1) 添加单个元素 (2) 添加另一集合中的所有元素 2. 删除元素 (1) 删除单个元素 (2) 删除某个集合中包含在其他集合中的元素 (3) 保留两个集合中的交集部分, 删除其他元素. 3. 遍历元素 (1) …...
电机驱动模块L9110S详解
电机驱动模块是一种用于控制和驱动电机的设备,它能够将控制信号转化为适合电机操作的电流和电压。通过电机驱动模块,可以实现对电机的速度、方向等参数进行精确控制。 今天我们要介绍的 L9110S 电机驱动适合大学生、工程师、个人DIY、电子爱好者们学习和…...
路由之间是怎么跳转的?有哪些方式?
1. React 路由跳转方式(React Router) 在 React 中,路由跳转通常使用 React Router 来管理。React Router 提供了不同的跳转方式。 <Link> 组件跳转 使用 <Link> 组件来进行路由跳转,它会渲染为一个 HTML <a> …...
AudioSegment 将音频分割为指定长度时间片段 - python 实现
DataBall 助力快速掌握数据集的信息和使用方式,会员享有 百种数据集,持续增加中。 需要更多数据资源和技术解决方案,知识星球: “DataBall - X 数据球(free)” -------------------------------------------------------------…...
双目摄像头标定方法
打开matlab 找到这个标定 将双目左右目拍的图像上传(左右目最好不少于20张) 等待即可 此时已经完成标定,左下角为反投影误差,右边为外参可视化 把这些误差大的删除即可。 点击导出 此时回到主页面,即可看到成功导出 Ca…...
题解 - 莱布尼茨三角形
题目描述 世界上著名的莱布尼茨三角形如图所示,请编程输出图中排在第n行从左边数第m个位置上的数。 输入 共一行,有二个整数N 和M(N<15),两数间用空格隔开。 输出 共一行,有二个整数,两数间用“/”隔开ÿ…...
低代码开发:企业数智化转型中的关键角色与实践案例分析
引言 随着信息技术的飞速发展,企业数智化转型已成为提升竞争力和实现可持续发展的必经之路。在这一过程中,低代码开发平台作为一种新兴的开发模式,正逐渐成为企业数智化转型的关键角色。本文将探讨低代码开发在企业数智化转型中的作用&#x…...
【ubuntu24.04】PDFMathTranslate 本地PDF翻译GPU部署
https://huggingface.co/spaces/reycn/PDFMathTranslate-Docker排不上号官方都是要安装包,感觉可以本地试着源码部署一下, http://localhost:7860/官方是这个端口,但是我本地启动是:5000IDEA 里本地 backend启动效果 GUI 是监听7860的...
基于Spring Boot + Vue的摄影师分享交流社区的设计与实现
博主介绍:java高级开发,从事互联网行业六年,熟悉各种主流语言,精通java、python、php、爬虫、web开发,已经做了多年的设计程序开发,开发过上千套设计程序,没有什么华丽的语言,只有实…...
高空坠物识别
目录 一、回答二、其他参考 prompt 有没有识别高空坠物的github项目一、回答 根据您的请求,以下是一些在GitHub上可以找到的关于识别高空坠物的项目: 1、overthecity 这是一个监控高空抛物的云端服务项目,它利用Edison的计算能力对高空抛物…...
22. 正则表达式
一、概述 正则表达式(regular expression)又称 规则表达式,是一种文本模式(pattern)。正则表达式使用一个字符串来描述、匹配具有相同规格的字符串,通常被用来检索、替换那些符合某个模式(规则&…...
阿里云数据库MongoDB版助力极致游戏高效开发
客户简介 成立于2010年的厦门极致互动网络技术股份有限公司(以下简称“公司”或“极致游戏”),是一家集网络游戏产品研发与运营为一体的重点软件企业,公司专注于面向全球用户的网络游戏研发与运营。在整个产业链中,公…...
leetcode230.二叉搜索树中第k小的元素
标签:二叉搜索树;中序遍历 给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 小的元素(从 1 开始计数)。 示例 1: 输入:root [3,1,4,null,2], k 1…...
深入了解C++中const的用法
文章目录 一、C中的const如何理解?二、C中的const与C语言中的const有何区别?三、const与指针、引用的结合使用 一、C中的const如何理解? 在C中,const是一个关键字,用来表示常量性,意在告诉编译器某些变量或…...
adb连接逍遥安卓模拟器失败的问题解决方案
1、逍遥安卓模拟器进入系统应用,设置-关于平板电脑-版本号,连续点击3次以上,直到提示进入开发者模式,返回设置界面,进入【开发者选项】-【USB调试】开启,之后重启模拟器再次adb尝试连接。 2、android stud…...
【Go基础】Go算法常用函数整理
Go算法常用函数整理 使用 Go 语言编写算法题时,掌握一些常用的函数和用法可以大大提高效率。 1. 排序 (slices 包): slices.Sort(x []T): 对切片 x 进行升序排序。需要 Go 1.18 版本。T 需要实现 constraints.Ordered 接口,例如…...
【rust杂乱笔记】
code . 打开vscode fn main() {println!("hello world!") }loop{}循环; break跳出循环 // 引入三方库 use rand::Rng; // 引入标准库中的输入输出 use std::cmp::Ordering; use std::io;// main函数 先执行main函数 fn main() {// 打印的宏方法// 打印提示信息print…...
BFS算法题
目录 1.BFS 2.树里的宽搜 题目一——429. N 叉树的层序遍历 - 力扣(LeetCode) 题目二——103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode) 题目三——662. 二叉树最大宽度 - 力扣(LeetCode) 题目四——…...
辅助函数:mapMutations,mutations里的方法映射到组件的methods中
或者,页面已经映射了该方法 ,直接在该页面使用该方法。也就是不用在组件函数中向仓库传递修改数据信息,直接使用映射过来的方法修改数据 修改标题 跟在methods中定义函数不一样调用mutations方法修改标题不一样,新修改的数据是要写…...
XX服务器上的npm不知道咋突然坏了
收到同事的V,说是:182上的npm不知道咋突然坏了,查到这里了,不敢动了。 咱一定要抓重点:突然坏了。这里的突然肯定不是瞬间(大概率是上次可用,这次不可用,中间间隔了多长时间&#x…...
2024年山西省第十八届职业院校技能大赛 (高职组)“信息安全管理与评估”赛项规程
2024年山西省第十八届职业院校技能大赛 (高职组)“信息安全管理与评估”赛项规程 一、赛项名称 赛项名称:信息安全管理与评估 英文名称:Information Security Management and Evaluation 赛项组别:高职教师组 赛项归属…...
Excel拆分脚本
Excel拆分 工作表按行拆分为工作薄 工作表按行拆分为工作薄 打开要拆分的Excel文件,使用快捷键(AltF11)打开脚本界面,选择要拆分的sheet,打开Module,在Module中输入脚本代码,然后运行脚本 Su…...
深入解析MySQL事务隔离级别与锁机制在银行账户业务中的应用
一、引言 在金融行业,尤其是银行账户业务中,数据的一致性和安全性至关重要。MySQL作为一种广泛使用的数据库,其事务隔离级别和锁机制在保证数据一致性方面发挥着重要作用。本文将针对银行账户查询与转账业务,探讨如何运用事务锁来…...
Linux 设备树
学习设备树之前你需要知道什么? 因为设备树描述了整个芯片和开发板等所有硬件信息内容,所以他的信息量是非常庞大的,RK的linux的设备树算下来大概就有九千多行,大家不要被这个数字给吓到,这些内容都是原厂工程师写的&a…...
Ollama管理本地开源大模型,用Open WebUI访问Ollama接口
现在开源大模型一个接一个的,而且各个都说自己的性能非常厉害,但是对于我们这些使用者,用起来就比较尴尬了。因为一个模型一个调用的方式,先得下载模型,下完模型,写加载代码,麻烦得很。 对于程序的规范来说,只要东西一多,我们就需要一个集中管理的平台,如管理python…...
面向对象进阶:多态
黑马程序员Java个人笔记 BV17F411T7Ao p129~132 目录 多态 多态调用成员的特点 调用成员变量 调用成员方法 理解 多态的优势 解耦合 多态的弊端 解决方案:强制类型转换 instanceof jdk14新特性,将判断和强转放一起 总结 多态 多态调…...
设置IMX6ULL开发板的网卡IP的两种方法(临时生效和永久有效两种方法)
设置开发板网卡的IP,有两种方法。 方法一:临时生效 第一种方式是临时设置,只有本次有效,重启后又要重新设,命令为: ifconfig eth0 192.168.5.9设置成功后可以使用ifconfig命令来查看已设置的 IP 地址。 …...
Navicat for MySQL 查主键、表字段类型、索引
针对Navicat 版本11 ,不同版本查询方式可能不同 1、主键查询 (重点找DDL!!!) 方法(1) :右键 - 对象信息 - 选择要查的表 - DDL - PRIMARY KEY 方法(2&…...
二十七、Tomcat专题总结与拓展
文章目录 一、Tomcat设计思路总结1、Tomcat整体架构2、Tomcat设计思路 二、Tomcat源码设计精髓三、拓展:SpringBoot整合Tomcat源码分析四、拓展:SpringBoot整合Undertow实战1、Undertow概述2、SpringBoot集成Undertow2.1、引入依赖2.2、application.prop…...
WPF+MVVM案例实战与特效(三十九)- 深度剖析一个弧形进度条的实现
文章目录 1、使用 Path 结合 ArcSegment 绘制圆弧1、属性解读2、静态圆弧3、动态圆弧4、运行效果5、圆弧两端点的形状2、总结1、使用 Path 结合 ArcSegment 绘制圆弧 1、属性解读 Path 是 WPF 中的一个标记元素,用于绘制复杂的几何路径形状,而 ArcSegment 用于描述 Path 中…...