LSM-Tree (日志结构合并树)
LSM-Tree(日志结构合并树)是一种高效处理写操作的存储结构,广泛应用于NoSQL数据库如LevelDB和RocksDB。其核心思想是将随机写入转换为顺序写入,提升吞吐量。以下是其原理及Java实现示例:
### **LSM-Tree 原理**
1. **结构组成**:
- **MemTable**:内存中的有序结构(如跳表),用于快速写入。
- **Immutable MemTable**:MemTable写满后转为只读,准备刷盘。
- **SSTable(Sorted String Table)**:磁盘上的有序文件,由MemTable刷入生成,多个SSTable分层存储。
2. **写入流程**:
- 数据先写入MemTable。
- MemTable满后转为Immutable MemTable,异步刷入磁盘生成SSTable。
- 磁盘SSTable按层级组织,通过合并(Compaction)消除冗余数据。
3. **读取流程**:
- 依次查找MemTable、Immutable MemTable和各层SSTable。
- 使用布隆过滤器减少无效磁盘访问。
4. **合并(Compaction)**:
- 合并多个SSTable,保留最新数据,减少文件数量,提升读取效率。
---
### **Java 示例代码**
```java
import java.io.*;
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
public class LSMTree {
private ConcurrentSkipListMap<String, String> memTable = new ConcurrentSkipListMap<>();
private ConcurrentSkipListMap<String, String> immutableMemTable = null;
private List<File> sstables = new ArrayList<>();
private static final int MAX_MEMTABLE_SIZE = 1000;
// 写入数据
public synchronized void put(String key, String value) {
memTable.put(key, value);
if (memTable.size() >= MAX_MEMTABLE_SIZE) {
switchMemTable();
}
}
// 切换MemTable并刷盘
private void switchMemTable() {
immutableMemTable = memTable;
memTable = new ConcurrentSkipListMap<>();
flushToSSTable(immutableMemTable);
immutableMemTable = null;
}
// 将数据写入SSTable文件
private void flushToSSTable(ConcurrentSkipListMap<String, String> data) {
String filename = "sstable_" + System.currentTimeMillis() + ".txt";
File file = new File(filename);
try (BufferedWriter writer = new BufferedWriter(new FileWriter(file))) {
for (Map.Entry<String, String> entry : data.entrySet()) {
writer.write(entry.getKey() + "," + entry.getValue());
writer.newLine();
}
sstables.add(file);
} catch (IOException e) {
e.printStackTrace();
}
}
// 读取数据
public String get(String key) {
String value = memTable.get(key);
if (value != null) return value;
if (immutableMemTable != null) {
value = immutableMemTable.get(key);
if (value != null) return value;
}
// 从最新SSTable开始查找
for (int i = sstables.size() - 1; i >= 0; i--) {
value = searchInSSTable(sstables.get(i), key);
if (value != null) return value;
}
return null;
}
// 在SSTable中查找键
private String searchInSSTable(File file, String key) {
try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
String line;
while ((line = reader.readLine()) != null) {
String[] parts = line.split(",", 2);
if (parts[0].equals(key)) {
return parts.length > 1 ? parts[1] : null;
}
}
} catch (IOException e) {
e.printStackTrace();
}
return null;
}
// 合并SSTable文件
public void compact() {
if (sstables.size() < 2) return;
List<File> oldFiles = new ArrayList<>(sstables);
sstables.clear();
TreeMap<String, String> mergedData = new TreeMap<>();
// 按旧到新顺序合并,保留最新值
for (File file : oldFiles) {
try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
String line;
while ((line = reader.readLine()) != null) {
String[] parts = line.split(",", 2);
String key = parts[0];
String value = parts.length > 1 ? parts[1] : null;
mergedData.put(key, value);
}
} catch (IOException e) {
e.printStackTrace();
}
}
// 写入新文件并清理旧文件
String filename = "sstable_merged_" + System.currentTimeMillis() + ".txt";
File mergedFile = new File(filename);
try (BufferedWriter writer = new BufferedWriter(new FileWriter(mergedFile))) {
for (Map.Entry<String, String> entry : mergedData.entrySet()) {
writer.write(entry.getKey() + "," + entry.getValue());
writer.newLine();
}
sstables.add(mergedFile);
for (File f : oldFiles) {
f.delete();
}
} catch (IOException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
LSMTree lsm = new LSMTree();
// 示例操作
lsm.put("key1", "value1");
lsm.put("key2", "value2");
System.out.println(lsm.get("key1")); // 输出 value1
}
}
```
### **代码说明**
1. **写入优化**:使用跳表(`ConcurrentSkipListMap`)作为MemTable,写满后转为Immutable并刷盘。
2. **读取流程**:依次检查内存表和SSTable文件,确保获取最新数据。
3. **合并策略**:简单合并所有SSTable,生成新文件并删除旧文件,保留最新键值。
### **优化方向**
- **分层存储**:引入层级结构,每层数据量逐层递增,合并策略更精细。
- **布隆过滤器**:快速判断键是否存在于SSTable,减少IO。
- **索引优化**:为SSTable维护内存索引,加速查找。
LSM-Tree通过顺序写入和定期合并,在高写入场景下表现优异,适合日志系统、时序数据库等应用。
相关文章:
LSM-Tree (日志结构合并树)
LSM-Tree(日志结构合并树)是一种高效处理写操作的存储结构,广泛应用于NoSQL数据库如LevelDB和RocksDB。其核心思想是将随机写入转换为顺序写入,提升吞吐量。以下是其原理及Java实现示例: ### **LSM-Tree 原理** 1. **…...
【深入理解JWT】从认证授权到网关安全
最近的项目学习中,在进行登陆模块的用户信息验证这一部分又用到了JWT的一些概念和相关知识,特在此写了这篇文章、方便各位笔者理解JWT相关概念 目录 先来理解JWT是什么? 区分有状态认证和无状态认证 有状态认证 VS 无状态认证 JWT令牌的…...
利用 Open3D 保存并载入相机视角的简单示例
1. 前言 在使用 Open3D 进行三维可视化和点云处理时,有时需要将当前的视角(Camera Viewpoint)保存下来,以便下次再次打开时能够还原到同样的视角。本文将演示如何在最新的 Open3D GUI 界面(o3d.visualization.gui / o…...
智绘教:Windows平台上的高效悬浮窗画笔工具深度解析
在Windows平台上,一款高效、实用的悬浮窗画笔工具对于提升工作效率和演示效果至关重要。今天,我要为大家介绍一款备受好评的悬浮窗画笔程序——智绘教。这款软件以其丰富的功能和便捷的操作,成为了众多用户心中的首选。接下来,让我们一起深入了解智绘教的各项特性。 一、体…...
从“Switch-case“到“智能模式“:C#模式匹配的终极进化指南
当代码开始"思考" 你是否厌倦了层层嵌套的if-else地狱?是否想过让代码像侦探推理一样优雅地解构数据?C#的模式匹配正是这样一把瑞士军刀,从C# 7.0到C# 12,它已悄然进化成改变编程范式的利器。 一、模式匹配的三重境界…...
【Linux】进程优先级 | 进程调度(三)
目录 前言: 一、进程优先级: 1.通过nice值修改优先级: 二、进程切换: 三、上下文数据 四、Linux真实调度算法: 五、bitmap位图: 六、命令总结: 总结: 前言: 我…...
wordpress按不同页调用不同的标题3种形式
在WordPress中,可以通过多种方式根据不同的页面调用不同的标题。这通常用于实现SEO优化、自定义页面标题或根据页面类型显示不同的标题内容。 使用wp_title函数 wp_title函数用于在HTML的title标签中输出页面标题。你可以通过修改主题的header.php文件来实现自定义…...
音频进阶学习十六——LTI系统的差分方程与频域分析一(频率响应)
文章目录 前言一、差分方程的有理式1.差分方程的有理分式2.因果系统和ROC3.稳定性与ROC 二、频率响应1.定义2.幅频响应3.相频响应4.群延迟 总结 前言 本篇文章会先复习Z变换的有理分式,这是之前文章中提过的内容,这里会将差分方程和有理分式进行结合来看…...
css实现左右切换平滑效果
2025.02.25今天我学习了如何用css实现平滑效果 一、html相关代码 (1)设置往左、往右的动画属性,样式可以放在同一级。 (2)必须设置唯一key进行刷新数据,使用v-show来展示每次渲染的组件数量。 <tran…...
详解Tomcat下载安装以及IDEA配置Tomcat(2023最新)
目录 步骤一:首先确认自己是否已经安装JDK步骤二:下载安装Tomcat步骤三:Tomcat配置环境变量步骤四:验证Tomcat配置是否成功步骤五:为IDEA配置Tomcat 步骤一:首先确认自己是否已经安装JDK jdk各版本通用安…...
Docker快速使用指南
docker pull ubuntu:22.04 //先拉取一个基础镜像,一般是操作系统创建一个Dockerfile,放在任意目录下,内容如下 # 使用 Ubuntu 22.04 作为基础镜像 FROM ubuntu:22.04# 设置环境变量,避免安装过程中出现交互提示 ENV DEBIAN_FRONT…...
【Project】基于Prometheus监控docker平台
一、设计背景 1.1项目简介 本项目旨在创建一个全面的容器化应用程序监控解决方案,基于Prometheus监控Docker平台上的各种服务。在当今的软件开发环境中,容器化技术已成为一种关键的工具,使应用程序能够更快速、可靠地交付和扩展。然而&…...
Binder通信协议
目录 一,整体架构 二,Binder通信协议 三,binder驱动返回协议 四,请求binder驱动协议 一,整体架构 二,Binder通信协议 三,binder驱动返回协议 binder_driver_return_protocol共包含18个命令,分别是: 四,…...
使用 Postman 访问 Keycloak 端点
1. 引言 在本教程中,我们将首先快速回顾 OAuth 2.0、OpenID 和 Keycloak。然后,我们将了解 Keycloak REST API 以及如何在 Postman 中调用它们。 2. OAuth 2.0 OAuth 2.0 是一个授权框架,它允许经过身份验证的用户通过令牌向第三方授予访问…...
uniapp-X 对象动态取值
有个对象,例如 const data{age:12,list:[1,2,3,4]} 有个函数如下 export function getValueByPath(obj:UTSJSONObject, path:string):any {const current obj.getAny(path) as any;// 返回最终的值return current; } 期待 通过执行getValueByPath("xx.xx…...
建模软件Blender与Blender GIS插件安装教程
Blender(blender.org - Home of the Blender project - Free and Open 3D Creation Software)是一款功能强大的开源3D创作套件,它支持整个3D管道—建模、渲染、动画制作、模拟、渲染、合成和运动跟踪,甚至视频编辑和游戏制作&…...
数据解析与处理
数据解析与处理是数据科学、分析或开发中的核心步骤,涉及从原始数据中提取、清洗、转换和存储有效信息的过程。 一、数据解析 数据解析就是将原始数据(如文本、二进制、日志、API响应等)转换为结构化格式(如表格、字典、JSON等&…...
强化学习概览
强化学习的目标 智能体(Agent)通过与环境(Environment)交互,学习最大化累积奖励(Cumulative Reward)的策略。 数学抽象 马尔科夫决策过程(MDP) 收益 由于马尔科夫决…...
如何在netlify一键部署静态网站
1. 准备你的项目 确保你的静态网站文件(如 HTML、CSS、JavaScript、图片等)都在一个文件夹中。通常,项目结构如下: my-static-site/ ├── index.html ├── styles/ │ └── styles.css └── scripts/└── script.js…...
2024中国信通院“集智”蓝皮书合集(附下载)
【目 录】 1. 数字政府一体化建设蓝皮书(2024年) 2. 数字乡村发展实践蓝皮书(2023年) 3. 中国工业互联网发展成效评估报告(2024年) 4. 云计算蓝皮书(2024年) 5. 具身智能发展报告…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
