etcd的多版本并發控制

系列文章目錄

淺談分布式系統與一緻性協定（一）

淺談分布式系統與一緻性協定（二）

淺談分布式系統與一緻性協定（三）

深入淺出之etcd

深入淺出之etcd(二)

etcd版本之v3

etcd之安全性闡述

在資料庫領域，并發控制是一個具有挑戰性的領馭。常見的并發控制方式包括悲觀并發控制，樂觀并發控制和多版本并發控制

悲觀并發控制

在關系型資料庫中，并發控制（又名悲觀鎖，Pessimistic Concurrency Control ,PCC）是一種并發控制的方法。它可以阻止一個事物以影響其他使用者的方式來修改資料。它可以阻止一個事務以影響其他使用者的方式來修改資料。如果一個事物執行的操作對某行資料應用了鎖，那麼隻有在這個事務将鎖釋放後，其他事務才能執行與該鎖沖突的操作。悲觀并發控制主要用于資料競争激烈的環境，以及發生并發沖突時使用鎖保護資料的成本要低于復原事務的成本環境中。

樂觀并發控制

樂觀并發控制（又名樂觀鎖）也是一種并發控制的方法。它假設多使用者并發的事務在處理時彼此之間互不影響，各個事務能夠在不産生鎖的情況下處理格子影響的那部分資料。在送出資料更新之前，每個事務都會檢查在該事務讀取資料之後，有沒有其他事務又修改了資料。如果其他事務有更新的化，那麼送出的事務會發生復原。

樂觀并發控制多用于資料競争不大，沖突較少的環境。在這種環境下，偶爾發生事務復原的成本要低于讀取資料時鎖定資料的成本，是以，這種環境下樂觀并發控制可以獲得比其他并發控制方法更高的吞吐量

多版本并發控制

多版本并發控制（Multiversion Concurrency Control ,MVCC）并不是一個與樂觀并發控制和悲觀并發控制對立的概念。它能夠與兩者很好的結合以增加事務的并發量，目前最流行的SQL資料庫MySQL和PostgreSQL都對MVCC進行實作。MVCC每一個寫操作都會建立一個新版本的資料，讀操作會從有限多個版本的資料中挑選一個最合适的（要麼是最新版本，要麼是指定版本）的結果傳回。通過這種方式，讀寫操作之間的沖突不再需要收到關注。

為什麼選擇MVCC

對一個系統進行優化時，相應的思路并不是憑空産生的，而實存在一定的方法論，首先我們應該分析etcd的使用場景，然後才能進行針對性的優化。首先etcd定位是一個分布式，一緻的key-value存儲，主要用途時共享配置和服務發現，它不是一個類似于ceph那樣存儲海量資料的存儲體系，也不是類似于MySQL這樣的SQL資料庫。它存儲的其實是一些非常重要的中繼資料，中繼資料的寫操作是非常少的，但是會有很多用戶端同時watch這些中繼資料的變更。也就是說etcd使用場景是一種“讀多寫少”的場景，etcd的一個key其實不不會頻繁變更，但是一旦發生變更，etcd就需要通知監聽這個key的所有用戶端

因為同一時間可能會存在很多使用者連接配接，那麼這段時間一定會存在許多并發問題，比如資料競争。etcd必須保證并發操作産生的結果是安全的。etcd v2是一個純記憶體資料庫，整個資料庫有一個stop the world的鎖，可以通過所鎖機制來解決并發帶來的資料問題，但是通過鎖的方式存在一些缺點：

• 鎖的粒度不好控制，每次操作stop the world時都會鎖住整個資料庫
• 讀鎖和寫鎖會互相阻塞（block）
• 如果使用基于鎖的隔離機制，并且有一段很長的讀事務，那麼在這段時間内這個對象就會無法被改寫，後面的事務會被阻塞，直到這個事務完成為。這種機制對于并發性能來說影響很大

多版本并發控制（MVCC）則以一種優雅的方式解決了所帶來的問題。在MVCC中，每當想要更改或者删除某個資料對象時，DBMS不會在原地删除或者修改這個已有的資料對象本身，而實針對該資料對象建立一個新的版本，這樣一來，并發讀取操作仍然可以讀取老版本的資料，而寫資料就可以同時進行。這個模式的好處在于，可以讀取操作不再阻塞，事實上根本不需要鎖。

etcd v2存儲機制實作

etcd v2是一個純記憶體資料庫，寫操作通過Raft複制日志檔案，複制成功後将資料寫入到記憶體，整個資料庫在記憶體中是一個簡單的樹形結構。etcd v2并未實時地将記憶體中的資料寫入到磁盤，持久化是靠快照實作的，具體實作就是将整個記憶體中的資料複制一份，然後序列化成JSON，寫入磁盤，成為一個快照。做快照的時候使用的是複制出來的資料庫，用戶端讀寫請求依然落在原始的資料庫上，這樣的話，做快照的操作不會阻塞用戶端的讀寫請求

etcd v3資料模型

etcd v3可靠的存儲不經常更新的資料，并且提供可靠的watch查詢。etcd v3與etcd v2不同的是，它支援暴露舊版本的鍵值來支援高效的快照和watch曆史事件。一個持久化的，多版本并發控制的資料模型非常适合etcd v3使用場景——因為如果僅僅維持一個key，一個value的資料模型，那麼連續更新就隻能儲存最後一個value，曆史版本無法追溯，而多版本則可以解決這個問題

etcd v3将資料存儲在一個多版本的持久化key-value存儲裡面。值得注意的是，作為key-value存儲的etcd 會将資料存儲在另一個key-value資料庫中。當持久簡直存儲的值發生變化時，持久化鍵值儲存先前版本的鍵值對。etcd 背景的鍵值存儲實際是不可變的，etcd操作不會就地更新結構，而實始終生成一個更新之後的結構。發生修改後，key先前的版本的所有制仍然可以通路和watch。為了防止資料存儲随時間的推移無限增長，并且為了維護舊版本，etcd可能會壓縮（删除）key的舊版本資料

邏輯視圖

etcd v3存儲的邏輯視圖是一個扁平的二進制鍵空間。該鍵空間對key有一個此法排序索引，是以此範圍查詢的成本很低

etcd鍵空間可能維護很多revision。每個原子修改（例如，一個事務操作可能包含多個操作）都會在鍵空間上建立一個新的revision，之前revision所有資料均保持不變，舊版本（version）的key仍然可以通過之前的revision進行通路。同樣，revision也是被索引的，是以Watcher可以實作高效的範圍watch。revision在etcd中可以起到邏輯時鐘的作用。revision在叢集的聲明周期時單調遞增的。如果因為節省空間而壓縮空間，那麼在此revision之前的的revision都會被删除，隻保留之後的revision

我們将key建立和删除的過程稱為一個生命周期。在etcd中，每個key都可能有多個生命周期，也就是說被建立，删除多次。建立一個key時，如果在目前revision中該key不存在（即之前沒有建立過），那麼它的revision就會被設定為1.删除key就會生成一個key的墓碑。可以通過将其version重置0來結束key的生命周期。對key的每一次修改都會增加其version，是以，key的version在key的一次生命周期中是單調遞增的。

revision是叢集狀态的版本号，存儲狀态每一次更新（例如，寫，删除，事務等）都會讓revision值加1。version特指etcd鍵空間某個key從建立開始被修改的次數，即KeyValue.Version。

實體視圖

etcd将實體資料存儲為一棵持久化B+樹中的鍵值對。為了高效，每個revision的存儲狀态都隻包含相較于之前revision的增量。一個revision可能對應于樹中的多個key

B+樹中的鍵值對的key即revision，revision是一個2元組（main，sub），其中main是該revision的主版本号，sub是同一revision的副版本号，其用于區分同一個revision的不同key。B+樹中的鍵值對的value包含了相對于之前revision的修改，即相對于之前revision的一個增量

B+樹按key的字典位元組序進行排序。這樣，etcd v3對revision增量的範圍查詢（range query，即從某個revision到另一個revision）會很快——因為我們已經記錄了從一個特定revision到其他revision的修改量。etcd v3的壓縮操作會删除過時的鍵值對

etcd v3還在記憶體中維護一個基于B樹的二級索引來加快對key的範圍查詢。該B樹索引的key是向使用者暴露的etcd v3存儲的key，而該B樹索引的value則是一個指向上文談論的持久化B+樹的增量的指針。etcd v3的壓縮操作會删除指向B樹索引的無效指針

etcd v3的MVCC實作

etcd v2二點每一個key都隻保留一個value，是以資料庫并不大，可以直接放到記憶體中。但是etcd v3實作了每一個MVCC以後 ，每一個key的value都會儲存，即存在多個曆史版本。對此一個自然的解決方案就是将資料存儲在磁盤中。etcd v3目前使用BoltDB将資料存儲到磁盤中。

BoltDB是根據Howard Chu的LMDB項目開發的一個存粹的Go語言版的key/value存儲。它的目标是為項目提供一個簡單，高效，可嵌入式的，可序列化的鍵/值資料庫，而不是要求像一個MySQL那樣完整的資料庫伺服器。BoltDB還是一個支援事務的鍵值存儲etcd的事務就是基于BoltDB的事務實作的。

BoltDB隻提供簡單的key/value存儲，沒有其他特性，也是以BoltDB可以做到代碼精簡，品質高，非常适合yiBoltDB為基礎在其之上建構更加複雜的資料庫功能。由于BoltDB的設計适合“讀多寫少”的場景

etcd在BoltDB中存儲的key是revision，value是etcd自己的key-value組合，也就是說etcd會在BoltDB中儲存每個版本，進而實作多版本機制

revision主要有兩部分組成，第一部分是main rev，每操作以此事務就加一第二部分是sub rev，同一事務每進行以此操作就加1。這樣的實作方式帶來的問題就是整個資料庫會越來越大，最終超過磁盤容量。是以MVCC還需要定期删除老的版本，etcd提供了指令行工具以及配置選項，供使用者手動删除老版本資料操作為資料壓縮

了解了etcd v3的磁盤存儲之後，可以看到想要從BoltDB查詢資料，必須通過revision，但是用戶端都通過key來查詢value的，是以etcd v3在記憶體中維護一個kvindex，儲存的就是key與revision的映射關系，用來加速查詢。kvindex，是基于Google開源的Golang的B樹實作的，也就是前文提到的etcd v3在記憶體中維護的二級索引。這樣用戶端通過key來查詢value時候，會先在kvindex中查詢這個key的所有revision，然後通過revision從這BoltDB中查詢資料。

之前講過，etcd v2的資料持久化機制是依靠定期做快照來實作的，即将記憶體中整個資料庫都複制一份，然後序列化到磁盤，做快照會對磁盤造成較大的壓力。而etcd v3實作了MVCC之後，資料是實時寫入BoltDB資料庫的，資料持久化其實已經分攤每次對key的寫請求上了，是以etcd v3就不需要做快照了。

需要注意的是，etcd v3雖然不需要做快照，但是需要定期對資料庫進行壓縮，因為磁盤的容量是有限的，不可能儲存key的所有曆史版本的value。