Introduction Goetz哥最近出了一本新书: More Modern Btree Techniques，里面多次提到了有关Btree/排序结构的压缩技术，比较关键的一个就是offset value encoding，并且也提到了Google的Napa/F1 Query使用了这种技术来加速查询。这篇文章就来介绍一下offset value encoding具体是怎么做的，以及这个技术如何能够加速查询。 在介绍Offset Value Encoding之前，先大概了解一下他的基本思路，Goetz哥在老版本的…
这篇文章来介绍一下MySQL的默认存储引擎Innodb，文章整体基于MySQL8.0的代码实现。 之前的介绍中Innodb Introduction，主要讲了很多前台写链路相关的代码，对于Innodb整体介绍的并非那么全面，所以这篇文章来做一下更加全面但是相对简要的介绍，期望读者可以了解Innodb中各个模块的基本原理 这次来尝试一下bottom-up approach TableSpace Innodb构建于文件系统之上，不过没有使用多少文件系统的特性，很多管理相关的工作都是TableSpace这一层做的，约等于…
Innodb Undo 在前文中已经介绍了Innodb中的Undo Log的作用，主要有三个点，分别是保存旧版本，回滚事务，以及作为持久化的活跃事务状态表。这篇文章中来细节介绍一下Innodb中的Undo Log，对于Undo Log来说，需要关注的有：Undo Log是如何组织的，Undo Log的类型，Undo Log何时做GC，Innodb如何通过Undo做事务回滚，保证事务原子性，在Crash Recovery的时候，Undo起到了什么作用。 Undo Log 组织 先回忆一下，Innodb中的一个表空间下…
这篇文章简略介绍一下Innodb中的一些组件，以及一些实现的优化。后续会针对不同的模块做细致的分析。之所以要先做一个简略的介绍，是因为Innodb本身的代码结构层次划分的并不是很清晰，无法层层递进式的去分析，个人在阅读源码的时候流程也是这样，先有一个大概的思路，再去扣细节。所以先有一个简略的介绍，每个模块的作用都是什么，也可以让读者在后续文章的阅读中有更多的背景，也省略了后续文章中需要介绍相关模块背景的时间。 可能叫Introduction不是很妥，因为并没有很全面的介绍，这篇文章我们主要关注前台的读写链路。 In…
LevelDB Recover 过一遍LevelDB的Recover流程。 DB::Open DBImpl::Recover 给当前的db上锁。防止有什么并发的OpenDB之类的。 看看有没有CurrentFile，没有的话打开一个新的DB。 VersionSet::Recover 读取Current，找到Manifest文件。 读取Manifest，重放VersionEdit。 如果Manifest过大，或者是重新将Manifest文件通过Append的方式打开的时候失败了，就会放弃Reuse Manifest。…
LevelDB Read 读链路主要分为两个，一个是点读，一个是RangeScan。 点读的接口是Get DBImpl::Get ref住当前的mem table，immmutable mem table，以及version 先读mem table，再读immutable memtable，最后调version->Get() 读完后更新统计信息，可能触发SeekCompaction Unref 读MemTable的时候会构建LookupKey。这是因为写入MemTable的时候会用一个varint作为leng…
LevelDB Compaction Compaction分为MinorCompaction和MajorCompaction。我们就直接叫Flush Memtable和Compaction SST。 LevelDB的Immutable memtable只能由一个。Flush Memtable优先级比较高，因为会影响前台写链路。 Flush memtable的调用点为CompactMemTable()。有两个调用点，不过都是后台线程做Compaction，所以不会出现并发Compaction的情况。 调用链路如下： …
Innodb-1 Linkbuf 代码主要在innobase/include/ut0link_buf.h中 link buf的作用在注释中有写到 Link buffer - concurrent data structure which allows: concurrent addition of links single-threaded tracking of connected path created by links limited size of window with holes (missing l…
database
Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?
Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? Abstract 列式数据分析引擎的发展引起了一系列对scan operator的优化。比如column-group storage, vectorized execution, shared scans, working directly over compressed data, using SIMD and multi-co…