The Evolution of LeanStore
LeanStore是一个针对多核及SSD优化(主要优化读性能)的键值存储引擎,本文将完整的展示整个LeanStore的组件,并且讨论关键的设计细节
Related Work
过去十几年的来多针对flash优化的数据库很少,大部分新的系统都聚焦到优化内存(比如: VoltDB、Hekaton等)或者是持久化内存。不过有两个先进的开源存储引擎需要提到:MongoDB的默认存储引擎WiredTiger以及基于LSM针对写优化的RocksDB
和LeanStore不同,WiredTiger的B树节点使用来两种不同的数据结构来表示。节点的内存表示是动态分配的不定长page,硬盘表示则是将节点存储不可变的block,这些block组成了文件。内存表示使用前缀压缩,而硬盘表示则使用使用snappy压缩。和LeanStore类似,查找操作使用内存指针找到节点,如果遇到unswizzled节点则需要从硬盘中加载后构建内存表示才能访问。更新操作则在leaf上的per-key skiplist上进行,当节点满了,则需要淘汰,这是会将这些更新合并,序列化来创建硬盘表示。在LeanStore中,节点是原地更新的只有一种表示,因此免去了序列化的开销
RocksDB 这个没啥好讲的
Overview
Functionality
LeanStore支持基本的key value操作(insert/update/delete, point/range lookup)以及事务语义(begin,commit,rollback),采用C++实现,作为库提供
B-tree
LeanStore中用于存放数据和索引的结构是B+树,键值对都是字符序列,使用者需要自己解释这些字符序列的含义。虽然B树不如某些纯内存数据结构快(如ART),但同样有可观的内存性能并且适合非内存场景,LeanStore中采用了多种优化尽量减小和纯内存数据结构的差距
Synchroization Primitives
现代CPU的总体性能通常由核的规模决定的,因此在LeanStore中实现了一个低开销,通用的可扩展同步框架,并且易于使用,这个框架会在后文描述
Buffer Manager
在LeanStore中主要使用 pointer swizzling 和 轻量的置换算法 去掉了传统buffer manager必须的page id映射以及每page的状态跟踪。所谓的 pointer swizzling 就是指节点间的访问通过内存指针进行,swizzled表示加载到内存的地址,unswizzled表示在硬盘中的位置。当系统内存不足时,随机选中的页面就会unswizzeled进入cooling stage,如果一个页特别的热,那么会从cooling stage移除重新变为swizzled,否则将在它到底cooling stage队列末端时会被剔除。后文会描述LeanStore是如何大幅简化page淘汰以及针对SSD的优化
Snapshot Isolation and MVCC
LeanStore中通过MVCC实现支持snapshot isolation(不支持SSI),同时发现OLTP的MVCC和OLAP查询相互影响,为了解决这个问题,LeanStore结合1. 一个高效的、支持细粒度垃圾回收的日志提交协议,2. 一个辅助的数据结构用来存放逻辑删除的tuple,避免干扰事务,3. 一个自适应的版本存储方案
Logging
基于磁盘的数据库系统中,事务的持久化是通过WAL来保证的,因为WAL通常作为一个中心化的数据结构,因此在多核场景成为了一个竞争点,影响多核扩展。在LeanStore中,采用每线程的WAL并且通过轻量的基于page的跟踪机制确保正确性,这将在后文详细描述
B+-Tree
基于经典的slotted-page B树节点布局,LeanStore实现了数个B树的优化
Node Layout
fig2中前面的slot存放了key/value的偏移和长度,对于内部节点来说value则是子节点的指针
Fence Keys and Prefix Compression
从fig2可以看出有两个fence keys: lower_fence以及upper_fence,他们是key的前缀表示范围(lower_fence, upper_fence]
,并且是不可变的,在分裂或合并是初始化。当B树创建时,leaf page的范围则设置为特殊值 -♾️到 ♾️。使用fence keys可以很轻松的实现所谓的前缀压缩技术,prefix就是从fence keys的最长公共前缀,如fig2中的prefix就是lower_fence和upper_fence的最长公共前缀
Speeding Up Binary Search with Heads
在slotted-page的表示中虽然也可以进行二分查找,但还是需要对每个key比较,这就设计到解引用指针来获取到key,这个过程会造成大量的cache misses。为了减少cache miss,LeanStore从key中提取前4个字符作为无符号整形表示,称为head。默认情况下所有的key都采用字典序来进行比较,这意味着在小端机器上需要反转字节顺序才能包装和字符串一样的字典序(例如:a = “125” b = “1233” 按照字典序比较,那么 a > b,转为无符号整数后则变成了 a < b,当使用bswap后就后字典序一样了)。这样在查找时先对head进行二分,当head相同时再使用key来进行二分查找
Avoiding Binary Search with Hints
在LeanStore中,为了缩小二分查找的范围,还在节点的头部增加了一个cacheline大小(通常64字节)的hints,hints是一个4字节的数组,因此它共有16个槽位,它存放的就是前面提到的head。在修改节点时通过updateHints
来修改对应的hints槽位,那么这必然有一个key到槽位的映射,这个映射通过slot_count / (hints_count + 1)
来完成,其中slot_count
是slotted page中的槽位数也就是当前的key个数。有了hints数组后查找过程就变为了:1. 在hints中找到需要进行二分差早的范围,2. 使用这个范围进行二分查找。而在hints中查找的流程如下
简单来说,就是从key的head中挑选出16个作为hint,并利用这个hint缩小查找的范围(即hints中 [pos, pos2)
),而hints数组的个数也可以通过配置,并且可以通过SIMD加速操作
Contention Split and XMerge
简单来说,前者的作用就是通过状态记录来判断当前节点是否是竞争节点,如果是就分裂成两个,使用不同的latch保护减少竞争;后者的作用是随机的合并当前节点的作用兄弟,增加buffer pool的利用率,毕竟前者多数时候都发生在节点未满的状态,详见 cidr2021
Practical and Scalable Synchronization
Optimistic Lock Coupling
使用乐观锁可以消除读操作的竞争,在原来的实现中依赖于单个版本的原子计数和自旋锁实现,这个简单的设计对于数据库的工作负载来讲并不是那么健壮,例如需要面临CPU的优先级反转以及调度的公平性等问题
Hybrid Latches
在最新的LeanStore设计中,除了原有的乐观模式外还增加了 “pessimistic shared” 和 “exclusive” 模式。它们使用std::shared_mutex
配合由std::atomic<uint64_t>
作为版本计数实现。这三种模式适用于不同的场景,例如:对长查询,如在范围查找时,使用 pessitmitic shared 模式,这样不用担心并发的修改导致重试;在短查询,如leaf node查找或时inner node遍历,首先尝试使用 optimistic 模式,在发现已经被锁定时转换为 pessimistic shared 模式;对于修改操作,如插入,直接使用 exclusive 模式
Page Guard
借助RAII机制可operator重载,一旦latch从某个模式开始,知道结束都不会变,同时避免latch泄漏。当需要升级时将当前的latch移动到目标latch中即可
Implementing Restart In C++
在LeanStore中,由于在访问子节点时并没有持有它父节点的latch,并且是乐观锁模式,在处理遇到的冲突时(如:并发修改)需要回退,这个过程涉及到对象的清理,内存的回收。和OCC(optimistic concurrenry control)不同,LeanStore为了最小化重试的开销,在整个过程中随时都可能重试,而OCC在最后才重试。同时这些需要清理的数据可能是跨函数的,因此goto
不能用,而使用C++异常的开销太大了,因此LeanStore以来C库的longjump
封装了一个JumpMu
来辅助完成重试时的清理工作(有一说一,这个真的是 tedious and error-prone)
简单来讲就是在没分配一个对象时就在thread-local的变量中记录下用lambda包装的清理函数(如:析构),并调用setjmp
,在需要重试时,先调用记录下的lambda清理完成后再调用longjmp
回退到开始的地方
Buffer Manager
这里先讲一下背景,18年的那篇paper中的主要优化就是针对buffer manager的,其中主要的优化点是:1, 去掉buffer pool中的hash表,使用 swip (swizzled pointer)直接访问缓存中的page;2. 一个轻量的缓存淘汰策略,采用随机+second chance结合,避免了对每个page的缓存状态的跟踪,对于cooling状态的page放在cooling stage FIFO queue中,对于hot page,会从cooling状态转为hot,因此需要从FIFO中移除,因此增加一个hash表来做映射(page id => FIFO entry)。这些东西也有自己的问题,例如,由于没有hash表(latch)那么page在淘汰时如何保证没有其他线程还在使用呢?那篇paper的解决办法是采用 epoch-based memory reclamation(ebr),除此之外还有一些其他的问题,这里就不赘诉,请查看参考
Memory Relcamation is Unnecessary
在前面的设计中,LeanStore实现了基于epoch的内存清理,它不仅是侵入性的维护还很复杂,并且并不健壮,例如,当一个线程很慢时就会阻碍到page的淘汰。最终LeanStore意识到这个组件并不是必须的,只要保证:1. 略(因为并没有在代码中发现对应的部分)2. 不将淘汰页面的内存归还给OS,这个很明显,因为是一个buffer pool。结果就是删掉了代码中的ebr部分
Page Replacement
Lightweight Replacement Strategy Without a Cooling Stage
LeanStore发现,前面设计的 cooling stage 在hot path(只读操作)上起了反作用,因此决定替换掉它,保留在后台鉴别cold page的部分(大部分传统的buffer manager缺是跟踪hot page)。下面就是新设计的实现细节
Swizzling-Based Second Chance Implementation
当需要空闲page时,挑选随机挑选page组成大小为64的集合,并且加载它们的状态。随后遍历它们冷却热的page:1. 设置当前page在parent中的child swip的最高有效位(cooling bit),2. 将page的状态修改为 cool。在淘汰前,任何已冷却的脏页都需要先刷盘。完全采用second chance的结果是不在需要hash表和FIFO queue,同时cool的page仍然保存着内存的指针,只不过打上了标记能鉴别是否是cool的,这和前面的设计完全相反(前面的设计需要将unswizzled的page的swip替换为page id,通常就是在文件中的位置)。在访问时,如果cooling bit没有设置,那么之间就是指针解引用,如果设置了就需要将它去掉并且page的状态修改为hot
在实现中page实际有三种状态:evicted、cool 和 hot,按照second chance的策略,当发现状态为cool时才会将page状态转为evicted,这时再次访问就需要从文件加载了
No Parent Pointers with Top Down Tree Traversals
由于淘汰page需要修改它父节点的child swip,因此为了方便旧的设计在page中存放了parent的指针。后来LeanStore发现,虽然这看起来很高效,但实际上也造成了多个限制导致系统变得复杂,例如:每当需要分裂时都需要更新这个指针;父节点修改时加latch也需要非常小心,通常lock-coupling都是top-down的,而这里需要bottom-up(个人觉得这才是主要的原因,毕竟fence keys都加了,加个parent指针问题不大)。结果就是使用findParent
的实现从root开始遍历查找,当然由于LeanStore中树节点没有sibling指针,本来也需要使用findParent
来辅助分裂和合并
Scaling to Multiple NVMe SSDs
为了避免同一个page被不同的线程多次加载到buffer pool,旧的设计使用一个锁来同步所有的线程,这对于单个SSD来说是足够的,但面对多个SSD这个锁就成为了性能瓶颈。为了充分释放多个SSD的性能,新的设计从以下几方面着手:
- I/O 分区
简单来讲,就是将page id按照线程数分成多个分区,page id随机的落在某个分区,目的是避免负载倾斜,这样相当于减小了锁的粒度,也就减少了锁的竞争 - 后台页面供给线程
将旧设计的前台page evict操作移到后台,结合I/O分区,可以在多个后台线程并行的执行淘汰任务,同时可以结合AIO或者io_uring,批量的刷写脏页
Logging
一开始设计的可扩展分布式日志是针对傲腾这类持久化内存的,然后后来Intel丢掉了这块业务,因此新的设计改为针对SSD优化,并且实现了Early Lock Release (ELR),它虽然减小了事务的abort率。这两者使得跨线程的日志依赖成本增加,因此LeanStore提出一种细粒度的依赖跟踪机制以减少依赖假阳性,下面的讨论,假设事务的隔离级别为Read Committed 或 Snapshot Isolation
Group Commit
简单来讲就是每个工作线程在本地的ring buffer中维护了将要刷写的日志(pre-commited)的指针,另外有一个后台的Group Commit Thread (GCT)不停的收集每个线程的pre-commited日志。工作线程在commit时需要等待GCT写入安全的提交TS(即 >= 当前事务的start ts),GCT首先将pre-commited日志刷盘(使用aio),然后fsync
持久化,随后计算安全的提交TS,举例如下
上图中有两个worker,上面运行着不同的事务,其中worker0 有TX8和TX10待提交,worker1有TX9、TX11和TX13待提交,由于8,9,10没有依赖关系(下面会介绍),因此可以之间刷盘,并且计算出的安全提交TS就是10,那么work0上的TX0和TX10的commit就可以返回,work1上的TX9也可以返回
Dependency Tracking
结合分布式日志和ELR,事务提交的依赖关系必须被明确。由于ELR,T1在将WAL持久化前就释放了写锁,而T2在读取了T1修改的数据,那么T2就不能在T1前提交。如果T1和T2在同一个工作线程,那么并不会对性能产生影响。但如果T1和T2在不同的线程,那么可能或造成线程相互等待。使用粗粒度的Global Sequence Number (GSN)来做依赖跟踪会导致们多false positive的依赖关系,例如:T1和T2并发的修改了同一个page上的不同的记录,使用GSN做依赖跟踪的结果就是T1和T2相互依赖,因此,需要区分User Txn 和 System Txn (这个在LeanStore中还没有实现)
System vs. User Transactions
用户事务执行存储引擎客户端的命令,通常有一个开始和提交的时间戳,这个时间戳通常是全局的原子计数,用户事务的副作用仅在提交后对自身可见。系统事务这是存储引擎在执行命令时内部触发的(例如:B+树的分裂合并),它的副作用则会对所有的事务可见,虽然不会修改用户的数据内容本身,但是会改变数据存储形式,通常系统事务数据修改前会独占的锁住所有受影响的页面,它的开始和提交时间戳通常就取自另一个全局的原子计数
Commit Condition
一个用户事务是否能提交依赖于它之前的用户事务和系统事务。每个页面在修改时存放了当前系统事务的txid, 对于系统事务来说,只需要记录读取页面时看到的最大的 txid。对于用户事务来说,使用开始时间戳作为txid就行。而Group Commit Thread就需要计算两个watermark:sys_wm 和 user_wm,当一个事务的 sys txid 和 user_txid 都小于等于这两个watermark时就可以提交了
以上就是这篇paper的主要内容,其中夹杂着个人的一些注释,这篇paper主要讲了一些LeanStore演化过程中纠正的一些设计,以及新提出的设计,虽然,但是,这些东西还有很多没有实现,比如:区分 user txn和system txn,continuous checkpointing 等,甚至前面提到的说是后面详细介绍的都没讲: 区分OLTP和OLAP的Graveyard Index,Remote Flush Avoidance,这些东西在其他的paper中提到
后续可能会开一篇专门讲讲LeanStore中对应的实现,以及补全本篇中缺失的部分