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. 具身智能发展报告…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
