这不最近入职了 PingCAP, 然后对自己从事的工作完全不了解，于是只能去恶补数据库和存储相关的知识，不过在我看来… 完全不懂并不是坏事，第一就是成长空间巨大，第二就是看待问题的角度并不一样因此可能会产出一些🚢新的思路呢～
言归正传，今天我就用这么几天浅薄的技术 “积累”, 简单聊一聊 LSM🌲…
不知道从什么时候开始，貌似是一家首页 404 号称不作恶的公司做出来了 Big Table, 然后使用了一个论文, 然后这篇论文提出了一条🚢新的道路，没有 B🌲, 写入效率高于读取效率，这咋听起来并不怎么靠谱的数据结构居然吊打了 MySQL 这种老牌数据库，但可惜 Big Table 是闭源的… 不过！不久之后，随着原创作者开源了根据这篇算法写的一个单机开源数据库 LevelDB 直接引爆了生态，一下子各个号称分布式的存储系统跟风就上，随着 FaceBook 做出了RocksDB (也就是我现在负责填坑的项目，写的是真的菜), 奠定了新一代分布式数据库的存储引擎，我司 TiKV 也是在这个上建的，那今天柠檬带大家看看究竟这个数据结构在干啥…
所以这颗🌲干啥的#
首先，所有技术的诞生都有当时时代的局限性，现在我们所处的这个时代，服务器是用不起高吞吐量的随机读写的 SSD 的，也没有一个没有性能损耗就可以达到高吞吐量随机读写且稳定的存储介质，所以在这个时代，大批量顺序读写的效率要比随机读写高出 20 倍以上 (真实数据并不是胡诌), 所以为了加速数据写入到存储介质的速度，必须使用顺序读写.
LSM🌲就诞生了！#
LSM🌲 全名: Log-Structured Merge Tree.
简而言之，就是像我们写 Log 一样写入数据，这样就保证了顺序写入.
但同时带来了一个巨大的问题，我们知道 log 就像一个链表，链表的随机访问如果没有 index 结构的话那么复杂度将会达到 O (N), 这玩意儿咋用啊！？这个问题将在后面读取的时候进行解答.
我们在前面提到了 404 公司的 LevelDB, 在 LevelDB 的里面存储引擎的 LSM🌲是搭配着 SSTable 进行使用的，
SSTable 全名: Sorted-String Table
404 公司是这么描述的:
An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings.
所以我们知道了 LSM🌲在 LevelDB 中是搭配了一个持久化有序不可变的键值存储结构，存储的一个键和一个数据的 offset. 有了 offset 搭配 mmap 就可以瞬间找到俺们的 LSM🌲存的信息了～吆西！
所以 LSM🌲的写入过程就是如下:
- 有人告诉我他要写数据，我先打个 log, 避免写的时候裂开
- 把这个数据写入到内存中的 SSTable 里面 (也可能是要删除数据，已知我们是打 log 所以这时候就是写入「他死了」), 然后同时写入到内存里的一个表里面.
- 内存里的表大到一定程度之后就会开一个新的表，然后旧的表就不可写入了
- 旧的表在合适的时机写入到硬盘～
- 然后随着硬盘上的小表越来越多，将会在合适的时机 (比如半夜三更) 进行一次 merge, 变成一个大表，merge 的过程中会删除掉标记了「他死了」的数据。由于这些表都是有序的，merge 过程就是一个简单的离线 merge sort.
那么读取的过程也就简单明了了～
- 内存看看表里有没？-- 很快
- 没有 -- 看看最近存的小表里有没有
- 还没有 -- 看看最近的大一点的表里有没有
- 还没有 -- 以此类推
那么… 怎么好像看起来读取还是最慢的情况下是 O (N)?!
那么下面就是今天的重点了，大家拿出笔记本📓, 但是不会考.
读取优化#
🔴⚫🌲#
由于作者表示能够用 20 行 Haskell 写出红黑树，你们写不出来你们菜，所以不讲.
HashTable#
// 这里是个递归
GOTO 0x00;
跳表#
好的，恭喜🎉你来到了大多数存储引擎都在使用的优化，跳表.
level 2: [11] [21] [41] [70]
level 1: [11] [14] [21] [31] [41] [58] [70]
level 0: [11] [12] [14] [15] [21] [24] [31] [39] [41] [49] [58] [61] [70]
一个跳表有 N 个 level,
因为我们的 LSM🌲是一个有序的数据结构，所以理论上我们就可以达到无限接近 O (log N) 的读取速度.
怎么写… 估计看我博客的小朋友应该都已经脑子里写了个差不多的，那么我们大概讲一下生成多少层跳表空间浪费和时间增加能达到相对的平衡.
首先，现实生活中数据库处理的数据量是非常庞大的，肯定不可能按照两个建一层这么粗暴的方法构建，这样会带来巨量的空间浪费，所以实际我们使用一个非常巧妙的概率策略:
抛硬币
因为硬币的正反面正好各占 50% 的概率所以严格和跳表的 log 吻合～
int 这个节点会在第几层有缓存呢(){
var level = 0;
while ( true ){
var 随机数 = random.nextInt();
if ( 随机数 % 2 == 0 ) {
level += 1;
} else {
break;
}
}
return level;
}
这样虽然很不公平，也可能出现一些非洲人节点访问次数很多但就不是索引的情况，但是基于概率来讲相对比较平稳.
下期预告：可能会讲一下老迟的 AgateDB 借鉴的项目 Badger 的 SSD 优化以及如何吊打 RocksDB 的，敬请期待～