说明

COW,Copy-On-Write技术,是在并发资源访问场景中的一种资源保护模式。当资源仅有读取访问而无更新时,资源仅存在单一副本,但当有对资源进行修改时,将资源复制一份,然后修改复制后的资源,这便是Copy On Write的核心含义。

下面是Wikipedia对Copy-On-Write的定义:

Copy-on-write (COW), sometimes referred to as implicit sharing[1] or shadowing,[2] is a resource management technique used in computer programming to efficiently implement a “duplicate” or “copy” operation on modifiable resources.[3] If a resource is duplicated but not modified, it is not necessary to create a new resource; the resource can be shared between the copy and the original. Modifications must still create a copy, hence the technique: the copy operation is deferred to the first write. By sharing resources in this way, it is possible to significantly reduce the resource consumption of unmodified copies, while adding a small overhead to resource-modifying operations.

COW技术主要有以下应用场景:

  • Linux虚拟内存管理,当父进程创建子进程时,子进程与父进程共享物理page,只有当其一要修改该page内容时,才会将page复制一份,然后修改该复制的page副本,并且不影响原page的数据。
  • 存储系统:很多存储系统使用COW技术来实现snapshot等高级特性

在BoltDB中也采用了COW技术,来保证数据一致性,具体原理我们会在下面详细说明。

BoltDB的COW

BoltDB作为一个通用的嵌入式KV存储系统,其主要场景无非是记录的读取与更新(包括插入)。而这其中一个很重要的点是读写并发时的数据一致性问题。更新后的KV记录数据需要能够在其被提交至数据库后对其他访问者可见。

例如下面的场景:进程打开数据库,其创建的子线程A负责从数据库读入KV记录,而子线程B负责更新其中记录。可能会出现对于其中的某一条记录R,A正好去读,而B同时需要更新。

BoltDB之COW技术

那么这时候问题就来了:为了保证数据一致性,在B更新R的时候,该Record必须被锁住,这样在有更新的时候所有的操作都被串行化了,而更新又是一个比较耗时的动作,因此,如果这样会极大地影响系统性能。

为了解决这种问题,前人们想出来了一个很聪明的办法,如下:

BoltDB之COW技术

该解决办法的思路是:

  • 线程A正在访问的记录R不动,将该记录copy一份,称之为R’;
  • 线程B修改上面copy出来的记录R’;
  • 线程B修改完成后,更新索引,以后访问的都是被B修改后的记录R’
  • 在A完成对R的读后,R占据的空间被释放;
  • 至此,老的记录R被完全抹去,后续只能访问被B修改后的R’。

看上面的过程,可不就是一个Copy On Write过程么?
对了,请大家务必记住一点,BoltDB不支持写写并发。

BoltDB的COW实现

每次的更新或者查询在BoltDB内部实现流程如下:

  1. 创建Tx并初始化;
  2. 执行查询/更新
  3. 根据2的结果执行Tx.Commit或者Tx.RollBack()

可以看到,在BoltDB的核心API中,Tx绝对是一个基础的数据结构,我们就来看看Tx是怎么被创建和初始化的。

我们接下来以一个更新事务为例来说明。

Tx创建

Tx,也即数据库中常说的“事务”,代表了一组对数据库的操作的集合,事务的主要特征是原子性,也即:事务中的更新操作集合要么全部执行,要么全部不执行,不会出现部分执行的情况。

一切起源于DB.Update(),这是BoltDB对使用者暴露的KV记录更新API:

func (db *DB) Update(fn func(*Tx) error) error {
    t, err := db.Begin(true)
    if err != nil {
        return err
    }

    defer func() {
        if t.db != nil {
            t.rollback()
        }
    }()

    t.managed = true

    err = fn(t)
    t.managed = false
    if err != nil {
        _ = t.Rollback()
        return err
    }

    return t.Commit()
}

func (db *DB) Begin(writable bool) (*Tx, error) {
    if writable {
        return db.beginRWTx()
    }
    return db.beginTx()
}

对于更新操作,调用的是db.beginRWTx,创建的是一个Writeable的Tx。

func (db *DB) beginRWTx() (*Tx, error) {
    if db.readOnly {
        return nil, ErrDatabaseReadOnly
    }

    // 加锁保证不会产生写写并发
    db.rwlock.Lock()

    db.metalock.Lock()
    defer db.metalock.Unlock()

    // Exit if the database is not open yet.
    if !db.opened {
        db.rwlock.Unlock()
        return nil, ErrDatabaseNotOpen
    }

    // Create a transaction associated with the database.
    t := &Tx{writable: true}
    t.init(db)
    db.rwtx = t

    var minid txid = 0xFFFFFFFFFFFFFFFF
    for _, t := range db.txs {
        if t.meta.txid < minid {
            minid = t.meta.txid
        }
    }
    if minid > 0 {
        db.freelist.release(minid - 1)
    }

    return t, nil
}

到这里其实就是在这里创建了一个writeable的Tx并调用其init()方法来初始化。

func (tx *Tx) init(db *DB) {
    tx.db = db
    tx.pages = nil

    tx.meta = &meta{}
    db.meta().copy(tx.meta)

    // Copy over the root bucket.
    tx.root = newBucket(tx)
    tx.root.bucket = &bucket{}
    *tx.root.bucket = tx.meta.root

    if tx.writable {
        tx.pages = make(map[pgid]*page)
        tx.meta.txid += txid(1)
    }
}

好的,到这里,我们看到,Tx的初始化是将db当前的root信息记录在tx中,这也就相当于tx中存储了当前数据库的根节点(root)信息副本,接下来tx可能会修改这些信息,并最终将这些信息修改反映在数据库中。

数据更新

这里我们就不多说了,毕竟前面已经详细描述过该过程。我们只消清楚一点:该更新过程发生在内存,具体来说,首先将需更新的记录所在的page加载至内存的node,然后更新node中的记录。

BoltDB之COW技术

Tx提交更新

我们在上面阶段完成所有的更新,如果一切顺利,我们最后便是提交更新。所谓的提交更新只是将内存node中的数据再写回至page。

这个过程我们在之前的Bucket存储结构中也做过详细的描述。主要是将所有涉及到修改的node再写回到磁盘,但是有一点需要特别注意的是,这个写回并非是将node写回至其被加载的yuan’shipage,而是分配新的page写回。这在node.spill()函数中有体现:

func (n *node) spill() error {
    ......
    var nodes = n.split(tx.db.pageSize)
    for _, node := range nodes {
        // Add node's page to the freelist if it's not new.
        if node.pgid > 0 {
            tx.db.freelist.free(tx.meta.txid, tx.page(node.pgid))
            node.pgid = 0
        }

        // Allocate contiguous space for the node.
        // 分配全新page来写回node内容
        p, err := tx.allocate((node.size() / tx.db.pageSize) + 1)
        if err != nil {
            return err
        }

        // Write the node.
        if p.id >= tx.meta.pgid {
            panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", p.id, tx.meta.pgid))
        }
        node.pgid = p.id
        node.write(p)
        node.spilled = true
        ......
    }
}

除了对数据更新的提交之外,Tx.Commit还需要对系统的元数据更新也提交至磁盘。还记得我们Tx初始化时候copy了一份db的meta信息么,在上面的写入过程中,该meta可能已经被修改(主要是指系统的root page的id,如新的root从page 3变成了page 4)。此时我们需要将这种meta的变化持久化到磁盘,便于下次可以从新的root读取到正确的数据。因此,在Tx.Commit还有一个过程便是Tx.writeMeta()。在阅读代码时需要特别注意。

因此,总的看来,在Tx执行了Commit后,原始数据被读入内存、修改后再写入磁盘新的地方,数据原始存储的page内容并未被修改,其他仍在引用旧page的访问者依然读取的是旧记录的数据,直到其访问完成,该旧page被释放,新的修改被提交至磁盘,以后的访问都只有新的修改后的记录可见。