一文讀懂 etcd 的 mvcc 實現

做Go開發的同學平時接觸到 Etcd 的機會比較多，今天邀請到做過 DBA 的研發老兵董大哥給大家分享一下 Etcd 的 mvcc 實現。

提到事務必談 ACID 特性, 基於悲觀鎖的實現會有讀寫衝突問題，性能很低，爲了解決這個問題，主流數據庫大多采用版本控制 mvcc[1] 技術，比如 oracle, mysql, postgresql 等等。讀可以不加鎖，只需要讀歷史版本即可 (寫寫還是衝突). 根據事務能看到不同版本的數據，還產生了隔離級別的問題，比如 mysql 默認的 repeatable-read, oracle 默認的 read-commited. 本文暫時只講 mvcc, 隔離實現放到下文。

mvcc 不同數據庫實現也不同，mysql 原地更新數據，將多版本保存到 undo, 而 postgresql 直接插入不同版本數據，過期的數據由 vacuum 來刪除。etcd 的實現類似 pg, 本次分享看一下 etcd 的實現原理。

Revision

可以先閱讀我的文章 etcd 中讓人頭大的 version, revision, createRevision, modRevision[2] 來了解下幾個版本的概念。

type revision struct {
 // main is the main revision of a set of changes that happen atomically.
 main int64
 // sub is the sub revision of a change in a set of changes that happen
 // atomically. Each change has different increasing sub revision in that
 // set.
 sub int64
}

main 是版本 id, 邏輯時間戳全局遞增。sub 表示當前事務內操作 changes 的順序 id, 從 0 開始遞增。

靜態存儲

etcd 的 mvcc 數據存儲分兩部分：內存保存所有 key 對應的版本信息，用於快速範圍查詢與點查，而磁盤存儲所有不同版本的真實數據。

kvindex btree

內存數據由 btree 來維護，從圖上可以看到，key 是用戶真實的 key, value 是對應所有的版本信息。

type keyIndex struct {
 key         []byte
 modified    revision // the main rev of the last modification
 generations []generation
}

// generation contains multiple revisions of a key.
type generation struct {
 ver     int64
 created revision // when the generation is created (put in first revision).
 revs    []revision
}

keyIndex 保存 key 的所有版本信息，每刪除一次都會生成一個 generation, 每個 generation 保存了這個生命週期內從創建到刪除中間的所有版本號。

磁盤 boltdb

磁盤負責存儲所有數據，key 是 revision, value 是 mvccpb.KeyValue, 存儲引擎是 boltdb

type KeyValue struct {
 // key is the key in bytes. An empty key is not allowed.
 Key []byte `protobuf:"bytes,1,opt,`
 // create_revision is the revision of last creation on this key.
 CreateRevision int64 `protobuf:"varint,2,opt,`
 // mod_revision is the revision of last modification on this key.
 ModRevision int64 `protobuf:"varint,3,opt,`
 // version is the version of the key. A deletion resets
 // the version to zero and any modification of the key
 // increases its version.
 Version int64 `protobuf:"varint,4,opt,`
 // value is the value held by the key, in bytes.
 Value []byte `protobuf:"bytes,5,opt,`
 // lease is the ID of the lease that attached to key.
 // When the attached lease expires, the key will be deleted.
 // If lease is 0, then no lease is attached to the key.
 Lease int64 `protobuf:"varint,6,opt,`
}

mvccpb.KeyValue 存儲本次操作的 key, value, 還有相關的所有版本信息。

Range 查找

每次數據操作，都會在 etcdserver 層開啓一個事務 txn, Range 操作是 Read 讀事務，然後調用 txn 的 Range 方法，直接看 mvcc 目錄下 kvstore_txn.go 文件的實現。

func (tr *storeTxnRead) Range(key, end []byte, ro RangeOptions) (r *RangeResult, err error) {
 return tr.rangeKeys(key, end, tr.Rev(), ro)
}

func (tr *storeTxnRead) rangeKeys(key, end []byte, curRev int64, ro RangeOptions) (*RangeResult, error) {
 rev := ro.Rev
 if rev > curRev {
  return &RangeResult{KVs: nil, Count: -1, Rev: curRev}, ErrFutureRev
 }
 if rev <= 0 {
  rev = curRev
 }
 if rev < tr.s.compactMainRev {
  return &RangeResult{KVs: nil, Count: -1, Rev: 0}, ErrCompacted
 }
  
 revpairs := tr.s.kvindex.Revisions(key, end, rev)
  ......
 kvs := make([]mvccpb.KeyValue, limit)
 revBytes := newRevBytes()
 for i, revpair := range revpairs[:len(kvs)] {
  revToBytes(revpair, revBytes)
  _, vs := tr.tx.UnsafeRange(keyBucketName, revBytes, nil, 0)
    ......
  if err := kvs[i].Unmarshal(vs[0]); err != nil {
    ......
  }
 }
 tr.trace.Step("range keys from bolt db")
 return &RangeResult{KVs: kvs, Count: len(revpairs), Rev: curRev}, nil
}

省略部份無關代碼，直接看主幹部份

檢查所查找的 rev 版本是否有效，超過當前版本不行，被 compact 刪除的也不行
根據指定版本去 kvindex 即內存 btree 中查找，所有符合 rev 版本從 key 到 end 的版本信息
遍歷所有版本，UnsafeRange 去底層磁盤 boltdb 中獲取真實 key/value

Put 更新數據

etcdserver 層同樣要開啓事務，只不過是寫事務。然後實現直接看 mvcc 目錄下 kvstore_txn.go

func (tw *storeTxnWrite) put(key, value []byte, leaseID lease.LeaseID) {
 rev := tw.beginRev + 1
 c := rev
 oldLease := lease.NoLease

 // if the key exists before, use its previous created and
 // get its previous leaseID
 _, created, ver, err := tw.s.kvindex.Get(key, rev)
 if err == nil {
  c = created.main
  oldLease = tw.s.le.GetLease(lease.LeaseItem{Key: string(key)})
 }
 tw.trace.Step("get key's previous created_revision and leaseID")
 ibytes := newRevBytes()
 idxRev := revision{main: rev, sub: int64(len(tw.changes))}
 revToBytes(idxRev, ibytes)

 ver = ver + 1
 kv := mvccpb.KeyValue{
  Key:            key,
  Value:          value,
  CreateRevision: c,
  ModRevision:    rev,
  Version:        ver,
  Lease:          int64(leaseID),
 }

 d, err := kv.Marshal()
  ......

 tw.tx.UnsafeSeqPut(keyBucketName, ibytes, d)
 tw.s.kvindex.Put(key, idxRev)
 tw.changes = append(tw.changes, kv)
 tw.trace.Step("store kv pair into bolt db")
  ......
}

省去不太相關的 lease 操作，只看主幹邏輯

根據當前版本 key, rev 查找內存 kvindex, 看看是否有當前 key 的版本記錄。主要是獲取這個 key 當前的 createdRevision 與 Version
生成 mvccpb.KeyValue 信息，主要是確定這次操作的 ModRevision
UnsafeSeqPut 操作寫磁盤 boltdb, key 是 Revision, value 是 mvccpb.KeyValue 序列化後的數據
最後更新 kvindex btree

Delete 刪除

同樣需要開啓寫事務，直接看源碼

func (tw *storeTxnWrite) DeleteRange(key, end []byte) (int64, int64) {
 if n := tw.deleteRange(key, end); n != 0 || len(tw.changes) > 0 {
  return n, tw.beginRev + 1
 }
 return 0, tw.beginRev
}

func (tw *storeTxnWrite) deleteRange(key, end []byte) int64 {
 rrev := tw.beginRev
 if len(tw.changes) > 0 {
  rrev++
 }
 keys, _ := tw.s.kvindex.Range(key, end, rrev)
 if len(keys) == 0 {
  return 0
 }
 for _, key := range keys {
  tw.delete(key)
 }
 return int64(len(keys))
}

同樣需要先查找內存 kvindex, 找到所有符合的待刪除版本，然後調用 delete 去刪

func (tw *storeTxnWrite) delete(key []byte) {
 ibytes := newRevBytes()
 idxRev := revision{main: tw.beginRev + 1, sub: int64(len(tw.changes))}
 revToBytes(idxRev, ibytes)

 if tw.storeTxnRead.s != nil && tw.storeTxnRead.s.lg != nil {
  ibytes = appendMarkTombstone(tw.storeTxnRead.s.lg, ibytes)
 } else {
  // TODO: remove this in v3.5
  ibytes = appendMarkTombstone(nil, ibytes)
 }

 kv := mvccpb.KeyValue{Key: key}

 d, err := kv.Marshal()
 if err != nil {
  if tw.storeTxnRead.s.lg != nil {
   tw.storeTxnRead.s.lg.Fatal(
    "failed to marshal mvccpb.KeyValue",
    zap.Error(err),
   )
  } else {
   plog.Fatalf("cannot marshal event: %v", err)
  }
 }

 tw.tx.UnsafeSeqPut(keyBucketName, ibytes, d)
 err = tw.s.kvindex.Tombstone(key, idxRev)
 ......
}

生成 ibytes, 然後追加一個 appendMarkTombstone 標記，表示這個 revision 是 delete，並且生成一個只含有 key 的 mvccpb.KeyValue
UnsafeSeqPut 刪除磁盤 boltdb, 注意這裏底層只是標記刪除，磁盤空間並不釋放
Tombstone 結束當前生命週期，生成一個新的空 generation, 更新 kvindex

數據過期

與 pg 比較像，過期與刪除數據都是惰性刪除的。etcd 可以配置只保留固定時間的數據，所以會週期性的 Compact. 同樣分爲兩部分，內存 btree 數據如果發現當前 generation 爲空，並且最大 Revision 己過期，那就從 btree 中刪除。

磁盤數據由 boltdb 維護，只會標記爲刪除，磁盤空間可以回收利用，但是不會自動釋放，只有調用 Defrag 纔會重建磁盤文件。

另外說到存儲引擎 boltdb, 這個東西性能一般，除了 etcd 沒有什麼知名項目在用。讀事務是併發，但是寫事務是串行的，所以內部會將盡可能多的寫入 batch 一起操作，異步提交。

小結

這次分享就這些，以後面還會分享更多關於 etcd 的內容。

參考資料

[1]

什麼是 mvcc: https://en.wikipedia.org/wiki/Multiversion_concurrency_control,

[2]

etcd 中讓人頭大的 version, revision, createRevision, modRevision: https://mp.weixin.qq.com/s/TFcSEBBMnb0wJ_A3R4Jfqw,

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/6F4MxaDDFEB0IZgyPKtP-A