数据库内核的并发控制

大部分程序员最先接触并发编程, 一般是从编程语言里的多线程和锁开始. 但是, 并发控制是一种广义的技术思想, 千万不可将眼光局限于编程语言所提供的锁. 将编程语言里的并发控制技术推广, 就能得到任何层面的并发控制技术.

以操作一个文件为例, 如果不做并发控制, 就会遇到数据完整性问题. 例如, 我们写入的一项数据, 对应着现实对象, 如果不做并发控制, 那么可能读到的时两项数据的混合体, 或者只读到一项数据的部分.

互斥锁

互斥锁是最简单的并发控制技术, 无论读还是写, 通通进行排队, 一次只处理一个请求(读或者写). 这种技术实现起来简单, 不容易出 bug, 如果为了快速实现, 可以采用此技术. 但是, 因为涉及到排队串行化, 所以在很多实际场景中, 这种技术会非常低效.

以操作一个文件为例, 给文件加一把互斥锁(任何层面的锁, 未必和编程语言或者操作系统所提供的锁对应). 当想要往文件中写入数据时, 先获取锁, 然后写入. 同样, 想要从文件中读取数据时, 先获取锁, 然后读.

读写锁

读写锁把请求进行分类, 然后按读和写两种类型进行排队, 不再按单个请求进行排队. 多个读请求可以同时进行, 但是, 写请求不能和读请求同时进行, 因为它们是不同的类型. 特别的, 写类型内部继续按单个请求为维度进行排队.

一般读写锁不允许读操作插队到写操作的前面, 以避免写饥饿.

回到文件操作的例子, 因为读操作可以并发进行, 这样, 整个系统的总体吞吐量就上去了. 不过, 类型之间依然有排队, 写和读之间有互斥, 效率还不是最高的.

MVCC - 多版本并发控制

可以从多个角度去理解 MVCC, 这些角度虽然不同, 但都是正确的.

我们从锁粒度(分区, Sharding)的角度去理解 MVCC. 我们把一个文件人为地划分为多个分段, 每一个分段对应一把锁(互斥锁或者读写锁), 当针对其中一个分段加锁时, 并不影响其它分段的操作, 因此可以并发操作. 这种方法其实和使用多个文件是类似的, 原来我们全部的数据只写入同一个文件, 现在我们使用多个文件多把锁.

如果数据有新旧顺序, 例如文件是 Append Only 的, 那么我们记录一个进度位置(check point), 在进度之前可以并发的读, 因为进度之前的数据已经确保不会发生变化. 进度条之后, 采用串行化写.

正如我在 之前的一篇文章所提到的, MVCC 技术的核心是标记. 在快速的内存中保存着唯一的单点标记, 即使串行化访问内存标记也不会慢. 因为内存标记的存在, 同时慢速的硬盘支持并发读, 即使读到 Obsoleted 数据也无妨, 根据内存标记可以决定是否现场废弃.

基于多版本的并发控制技术, 有可能产生无效数据, 所以需要有 垃圾回收机制(GC).

实际例子

Redolog 是很多数据库系统的必备基础组件, 即使某个数据库系统没有一个叫 Redolog 的模块, 那么它也有某个模块做的是 Redolog 一模一样的事情, 所以, 不要在意名字, 看实质.

Redolog 模块的接口是这样的:

  type RedologManager interface {
    // 读取指定序号的日志
    func Get(seq Sequence) => Entry
    // 追加写一条日志
    func Append(ent Entry)
    // 将日志序列回滚到指定序号
    func Rollback(seq Sequence)
}

具体实现是这样的:

  type FileManger struct {
    var r_mux RWMutex
    var checkpoint Sequence
    var reader FileReader
    
    var w_mux Mutex
    var writer FileWriter
}

func (fm *FileManager)Get(seq Sequence) {
    // 可以并发读文件, 所以加读锁
    rm.r_mux.RLock()
    // 只返回该版本之前的数据
    if seq <= rm.checkpoint){
        rm.reader.Read(seq)
    }
    rm.r_mux.RUnlock()
}

func (fm *FileManager)set_checkpoint(seq Sequence) {
    rm.r_mux.Lock()
    rm.checkpoint = seq
    rm.r_mux.Unlock()
}

func (fm *FileManager)Append(ent Entry) {
    // 写操作不能并发, 所以加互斥锁
    rm.w_mux.Lock()
    {
        // 先追加并持久化文件
        rm.writer.Write(ent)
        rm.writer.Fsync()
        rm.reader.SetFileSize(rm.writer.FileSize())

        // 然后再增加进度
        rm.set_checkpoint(ent.Seq)
    }
    rm.w_mux.Unlock()    
}

func (fm *FileManager)Rollback(seq Sequence) {
    // 写操作不能并发, 所以加互斥锁
    rm.w_mux.Lock()
    {
        // 先减少进度
        rm.set_checkpoint(seq)

        // 然后再回滚持久化数据(收缩文件)
        rm.writer.Truncate(seq)
        rm.writer.Fsync()
        rm.reader.SetFileSize(rm.writer.FileSize())
    }
    rm.w_mux.Unlock()
}

// TODO: 如果关闭 auto fsync, 那么写操作不会立即影响持久化
func (fm *FileManager)AutoFsync(enable bool) {
}

该模块支持并发读, 所以加的是读锁(r_mux). 而且, 在读的同时可以写, 所以, 读和写加的是不同的锁. 但是, 写操作不可以并发, 所以写操作之间加的是互斥锁(w_mux). 在写操作的过程中, 涉及到更新进度, 所以, 在更新进度的时候, 需要加进度锁的写锁.

Related posts:

1. Binlog, Redolog 在分布式数据库系统中的应用
2. 接口与实现分离
3. 小心递归次数限制
4. 消除JavaScript闭包的一般方法
5. 必须放在循环中的pthread_cond_wait