7月28日下午，openGemini线下Meetup第二站于北京理工大学圆满结束。
在本次技术沙龙中，openGemini社区带来的议题是《数据结构和算法在数据库中的应用》，由社区发起人向宇为北理学子们分享openGemini时序数据库中使用的数据结构和算法，分别从意义、结构、与B+tree的区别、优化等方面对LSM-Tree做了重点讲解。
下面是本场分享的完整内容，干货满满，不要错过~
时序数据库中使用到的数据结构和算法概览
数据结构
- Array(含动态数组)
-
Map（含HashMap, BitMap）
-
字典树
-
倒排索引
-
大小堆
-
链表
-
LSM tree
算法
-
分词算法
-
数据压缩算法
-
排序算法（堆排、插入、归并、快速）
-
查找算法（二分、树的遍历）
-
异常检测/预测算法（AI）
-
数据编解码算法
-
内存复用
-
Raft
-
链接复用
LSM Tree 现代NoSQL数据库存储引擎核心
LSM-tree : Log-StructuredMerge-tree, 不是树，它只是一种分层的组织数据的结构，主要解决大数据场景下数据如何高效写入的问题。
核心思想：
-
随机写转换为顺序写，充分利用每一次I/O，从而实现高效地顺序写入数据
-
数据分层合并，避免数据文件随时间的推移而分散的问题
图片来源：https://anyview.fun/2022/09/23/%E4%B8%80%E6%96%87%E4%BA%86%E8%A7%A3lsm-tree/
为什么NoSQL数据库集体抛弃B+tree？
B+树优点：利用局部性原理，加载1个node，正好是一个Page，只需读1次I/O，B+树更加的矮胖，减少了I/O次数，所以效率非常高。
B+树缺点：如果主键不是有序递增的，导致每次插入数据产生大量的数据迁移和空间碎片。即使主键是有序递增的，大量写请求的分布仍是随机的，这就可能造成大量的磁盘随机读写，导致磁盘IO耗时增加。
一次磁盘IO的耗时主要由三部分组成：寻道时间+ 旋转延迟+ 数据传输时间
优化方向：尽量减小寻道时间和旋转延迟，即减少随机I/O
总结：在大数据场景下，数据量大，写并发大，采用B+树，性能太差，LSM-tree主要是解决这个问题，将大量随机写改为顺序写。
参考论文：《The Design and Implementation ofa Log-Structured File System》
LSM-tree 如何保证数据按顺序写？
为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了 LSM 树。LSM 把大量写入缓存在内存，当积攒到一定程度后，将他们批量写入文件中，这要一次 I/O 可以进行多条数据的写入，从而大幅提升写操作，作为代价的是牺牲了一些读性能。
LSM-tree 在openGemini的实现
openGemini把大量并发写入的时序数据按时间线key分桶缓存在内存，每个桶称之为Record，一个Record存一条时间线的数据，并按列组织。缓存会定期持久化到磁盘文件中。
LSM-tree 优化
LSM-tree通过减少随机I/O从而获得较好的写入吞吐量，但后台的Compacttion（文件合并）依然带来较大的写入I/O放大，影响了写性能，而且频繁写，对磁盘寿命也有影响。因此，关于怎么减少LSM写放大和如何提升LSM查询性能的相关研究并不匮乏。
LSM-tree 优化方法：
参考论文：《LSM-based Storage Techniques: A Survey》
LSM-tree 优化方法之一：布隆过滤器
布隆过滤器：一个很长的二进制向量和一系列随机映射函数，当所有的hash函数指向的bit位均为1时，表示目标数据存在，反之不存在。
应用场景：处理海量数据时，使用布隆过滤器实现去重，相比于 Set 集合的去重功能而言，布隆过滤器在空间上能节省 90% 以上。
当布隆过滤器判断某个值不存在时，那这个值肯定不存在
当它判定某个值存在时，其实这个值只是有可能存在，这个误判概率大约在 1% 左右。
Thanks for reading
openGemini从2019年开始演进，积累了非常多的数据结构和算法方面的优化实践经验，社区针对高校开发者提供技术指导和相关的社区开发培训，欢迎同学们以及广大开发者加入社区学习、参与开发、提升个人技术能力。
第三期meetup正在筹备中~
我们的故事又将在哪里延续？让我们一起期待✨...
