導讀：etcd是用於共享配置和服務發現的分散式，一致性的KV儲存系統，在CoreOS和Kubernetes等開源專案中廣泛使用。本文作者深入分析了etcd儲存模組的設計和實現，對於深入學習Go儲存有很大參考作用。

 

作者 codedump codedump.info 博主，多年從事網際網路伺服器後臺開發工作。可訪問作者部落格閱讀 codedump 更多文章。

 

在前面已經分析了Raft演演算法原理、etcd raft庫的實現，接著就可以看etcd如何使用raft實現儲存服務的了。

 

以下的分析主要針對etcd V3版本的實現。

 

概覽

 

下圖中展示了etcd如何處理一個客戶端請求的涉及到的模組和流程。圖中淡紫色的矩形表示etcd，它包括如下幾個模組：

• etcd server：對外接收客戶端的請求，對應etcd程式碼中的etcdserver目錄，其中還有一個raft.go的模組與etcd-raft庫進行通訊。etcdserver中與儲存相關的模組是applierV3，這裡封裝了V3版本的資料儲存，WAL（write ahead log），用於寫資料日誌，etcd啟動時會根據這部分內容進行恢復。
• etcd raft：etcd的raft庫，前面的文章已經具體分析過這部分程式碼。除了與本節點的etcd server通訊之外，還與叢集中的其他etcd server進行互動做一致性資料同步的工作（在圖中叢集中其他etcd服務用橙色的橢圓表示）。

 

在上圖中，一個請求與一個etcd叢集互動的主要流程分為兩大部分：

 

1. 寫資料到某個etcd server中。
2. 該etcd server與叢集中的其他etcd節點進行互動，當確保資料已經被儲存之後應答客戶端。

 

請求流程劃分為了以下的子步驟：

 

• 1.1：etcd server收到客戶端請求。
• 1.2：etcd server將請求傳送給本模組中的raft.go，這裡負責與etcd raft模組進行通訊。
• 1.3：raft.go將資料封裝成raft日誌的形式提交給raft模組。
• 1.4：raft模組會首先儲存到raftLog的unstable儲存部分。
• 1.5：raft模組透過raft協議與叢集中其他etcd節點進行互動。

 

註意在以上流程中，假設這裡寫入資料的etcd是leader節點，因為在raft協議中，如果提交資料到非leader節點的話需要路由到etcd leader節點去。

 

而應答步驟如下：

 

• 2.1：叢集中其他節點向leader節點應答接收這條日誌資料。
• 2.2：當超過叢集半數以上節點應答接收這條日誌資料時，etcd raft透過Ready結構體通知etcd server中的raft該日誌資料已經commit。
• 2.3：raft.go收到Ready資料將首先將這條日誌寫入到WAL模組中。
• 2.4：通知最上層的etcd server該日誌已經commit。
• 2.5：etcd server呼叫applierV3模組將日誌寫入持久化儲存中。
• 2.6：etcd server應答客戶端該資料寫入成功。
• 2.7：最後etcd server呼叫etcd raft，修改其raftLog模組的資料，將這條日誌寫入到raftLog的storage中。

 

從上面的流程可以看到

 

• etcd raft模組在應答某條日誌資料已經commit之後，是首先寫入到WAL模組中的，因為這個模組只是新增一條日誌，所以速度會很快，即使在後面applierV3寫入失敗，重啟的時候也可以根據WAL模組中的日誌資料進行恢復。
• etcd raft中的raftLog，按照前面文章的分析，其中的資料是儲存到記憶體中的，重啟即失效，上層應用真實的資料是持久化儲存到WAL和applierV3中的。

 

以下就來分析etcd server與這部分相關的幾個模組。

 

etcd server與raft的互動

 

EtcdServer結構體，負責對外與客戶端進行通訊。內部有一個raftNode結構的成員，負責與etcd的raft庫進行互動。

 

etcd V3版本的API，透過GRPC協議與客戶端進行互動，其相關程式碼在etcdserver/v3_server.go中。以一次Put請求為例，最後將會呼叫的程式碼在函式EtcdServer::processInternalRaftRequestOnce中，程式碼的主要流程分析如下。

1. 拿到當前raft中的apply和commit索引，如果commit索引比apply索引超出太多，說明當前有很多資料都沒有apply，傳回ErrTooManyRequests錯誤。
2. 呼叫s.reqIDGen.Next()函式生成一個針對當前請求的ID，註意這個ID並不是一個隨機數而是一個嚴格遞增的整數。同時將請求序列化為byte資料，這會做為raft的資料進行儲存。
3. 根據第2步中的ID，呼叫Wait.Register函式進行註冊，這會傳回一個用於通知結果的channel，後續就透過監聽該channel來確定是否成功儲存了提交的值。
4. 呼叫Raft.Process函式提交資料，這裡傳入的引數除了前面序列化的資料之外，還有使用超時時間建立的Context。
5. 監聽前面的Channel以及Context物件： a. 如果context.Done傳回，說明資料提交超時，使用s.parseProposeCtxErr函式傳回具體的錯誤。 b. 如果channel傳回，說明已經提交成功。

    

 

從以上的流程可以看出，在呼叫Raft.Process函式向Raft庫提交資料之後，等待被喚醒的Channel才是正常提交資料成功的路徑。

 

在EtcdServer.run函式中，最終會進入一個死迴圈中，等待raftNode.apply傳回的channel被喚醒，而raftNode繼承了raft.Node的實現，從前面分析etcd raft的流程中可以明白，EtcdServer就是在向raft庫提交了資料之後，做為其上層消費Ready資料的應用層。

 

自此，整體的流程大體已經清晰：

 

1. EtcdServer對外透過GRPC協議接收客戶端請求，對內有一個raftNode型別的成員，該型別繼承了raft.Node的實現。
2. 客戶端透過EtcdServer提交的資料修改都會透過raftNode來提交，而EtcdServer本身透過監聽channel與raft庫進行通訊，由Ready結構體來透過EtcdServer哪些資料已經提交成功。
3. 由於每個請求都會一個對應的ID，ID系結了Channel，所以提交成功的請求透過ID找到對應的Channel來喚醒提交流程，最後通知客戶端提交資料成功。

 

WAL

 

以上介紹了EtcdServer的大體流程，接下來看WAL的實現。

 

前面已經分析過了，etcd raft提交資料成功之後，將通知上面的應用層（在這裡就是EtcdServer），然後再進行持久化資料儲存。而資料的持久化可能會花費一些時間，因此在應答應用層之前，EtcdServer中的raftNode會首先將這些資料寫入WAL日誌中。這樣即使在做持久化的時候資料丟失了，啟動恢復的時候也可以根據WAL的日誌進行資料恢復。

 

etcdserver模組中，給raftNode用於寫WAL日誌的工作，交給了介面Storage來完成，而這個介面由storage來具體實現：

可以看到，這個結構體組合了WAL和snap.Snapshotter結構，Snapshotter負責的是儲存快照資料。

 

WAL日誌檔案中，每條日誌記錄有以下的型別：

1. Type：日誌記錄型別，下麵詳細解釋都有哪些型別。
2. Crc：這一條日誌記錄的校驗資料。
3. Data：真正的資料，根據型別不同儲存的資料也不同。

 

日誌記錄又有如下的型別：

 

1. metadataType：儲存的是元資料（metadata），每個WAL檔案開頭都有這型別的一條記錄資料。
2. entryType：儲存的是raft的資料，也就是客戶端提交上來並且已經commit的資料。
3. stateType：儲存的是當前叢集的狀態資訊，即前面提到的HardState。
4. crcType：校驗資料。
5. snapshotType：快照資料。

 

etcd使用兩個目錄分別存放WAL檔案以及快照檔案。其中，WAL檔案的檔案名格式是“16位的WAL檔案編號-該WAL第一條entry資料的index號.wal”，這樣就能從WAL檔案名知道該WAL檔案中儲存的entry資料至少大於什麼索引號。而快照檔案名的格式則是“16位的快照資料最後一條日誌記錄任期號-16位的快照資料最後一條記錄的索引號.snap”。

 

Etcd會管理WAL目錄中的所有WAL檔案，但是在生成快照檔案之後，在快照資料之前的WAL檔案將被清除掉，保證磁碟不會一直增長。

 

比如當前etcd中有三個WAL檔案，可以從這些檔案的檔案名知道其中存放資料的索引範圍。

 

在生成快照檔案之後，此時就只剩一個WAL檔案和一個快照檔案了：

 

 

那麼，又是在什麼情況下生成快照檔案呢？Etcdserver在主迴圈中透過監聽channel獲知當前raft協議傳回的Ready資料，此時會做判斷如果當前儲存的快照資料索引距離上一次已經超過一個閾值（EtcdServer.snapCount），此時就從raft的儲存中生成一份當前的快照資料，寫入快照檔案成功之後，就可以將這之前的WAL檔案釋放了。

 

以上流程和對應的具體函式見下麵的流程圖。

 

 

backend store的實現

revision概念

 

Etcd儲存資料時，並不是像其他的KV儲存那樣，存放資料的鍵做為key，而是以資料的revision做為key，鍵值做為資料來存放。如何理解revision這個概念，以下麵的例子來說明。

 

比如透過批次介面兩次更新兩對鍵值，第一次寫入資料時，寫入和，在Etcd這邊的儲存看來，存放的資料就是這樣的：

 

而在第二次更新寫入資料和後，儲存中又記錄（註意不是改寫前面的資料）了以下資料：

 

 

其中revision有兩部分組成，第一部分成為main revision，每次事務遞增1；第二部分稱為sub revision，一個事務內的一次操作遞增1。 兩者結合，就能保證每次key唯一而且是遞增的。

 

 

但是，就客戶端看來，每次操作的時候是根據Key來進行操作的，所以這裡就需要一個Key對映到當前revision的操作了，為了做到這個對映關係，Etcd引入了一個記憶體中的Btree索引，整個操作過程如下麵的流程所示。

 

 

查詢時，先透過記憶體中的btree索引來查詢該key對應的keyIndex結構體，然後再根據這個結構體才能去boltdb中查詢真實的資料傳回。

 

所以，下麵先展開討論這個keyIndex結構體和btree索引。

 

keyIndex結構

 

keyIndex結構體有以下成員：

 

• key：儲存資料真實的鍵。
• modified：最後一次修改該鍵對應的revision。
• generations：generation陣列。

 

如何理解generation結構呢，可以認為每個generation對應一個資料從建立到刪除的過程。每次刪除key的操作，都會導致一個generation最後新增一個tombstone記錄，然後建立一個新的空generation記錄新增到generations陣列中。

 

generation結構體存放以下資料：

 

• ver：當前generation中存放了多少次修改，其實就是revs陣列的大小-1（因為需要去掉tombstone）。
• created：建立該generation時的revision。
• revs：存放該generation中存放的revision陣列。

 

以下圖來說明keyIndex結構體：

 

 

如上圖所示，存放的鍵為test的keyIndex結構。

 

它的generations陣列有兩條記錄，其中generations[0]在revision 1.0時建立，當revision2.1的時候進行tombstone操作，因此該generation的created是1.0；對應的generations[1]在revision3.3時建立，緊跟著就做了tombstone操作。

 

所以該keyIndex.modifiled成員存放的是3.3，因為這是這條資料最後一次被修改的revision。

 

一個已經被tombstone的generation是可以被刪除的，如果整個generations陣列都已經被刪除空了，那麼整個keyIndex記錄也可以被刪除了。

 

 

如上圖所示，keyIndex.compact(n)函式可以對keyIndex資料進行壓縮操作，將刪除滿足main revision < n的資料。

 

• compact(2)：找到了generations[0]的1.0 revision的資料進行了刪除。
• compact(3)：找到了generations[0]的2.1 revision的資料進行了刪除，此時由於generations[0]已經沒有資料了，所以這一整個generation被刪除，原先的generations[1]變成了generations[0]。
• compact(4)：找到了generations[0]的3.3 revision的資料進行了刪除。由於所有的generation資料都被刪除了，此時這個keyIndex資料可以刪除了。

 

treeIndex結構

 

Etcd中使用treeIndex來在記憶體中存放keyIndex資料資訊，這樣就可以快速的根據輸入的key定位到對應的keyIndex。

 

treeIndex使用開源的github.com/google/btree來在記憶體中儲存btree索引資訊，因為用的是外部庫，所以不打算就這部分做解釋。而如果很清楚了前面keyIndex結構，其實這部分很好理解。

 

所有的操作都以key做為引數進行操作，treeIndex使用btree根據key查詢到對應的keyIndex，再進行相關的操作，最後重新寫入到btree中。

 

store

 

前面講到了WAL資料的儲存、記憶體索引資料的儲存，這部分討論持久化儲存資料的模組。

 

etcd V3版本中，使用BoltDB來持久化儲存資料（etcd V2版本的實現不做討論）。所以這裡先簡單解釋一下BoltDB中的相關概念。

 

BoltDB相關概念

 

BoltDB中涉及到的幾個資料結構，分別為DB、Bucket、Tx、Cursor、Tx等。

 

其中：

• DB：表示資料庫，類比於Mysql。
• Bucket：資料庫中的鍵值集合，類比於Mysql中的一張資料表。
• 鍵值對：BoltDB中實際儲存的資料，類比於Mysql中的一行資料。
• Cursor：迭代器，用於按順序遍歷Bucket中的鍵值對。
• Tx：表示資料庫操作中的一次只讀或者讀寫事務。

 

Backend與BackendTx介面

 

Backend和BackendTx內部的實現，封裝了BoltDB，太簡單就不做分析了。

 

Lessor介面

 

etcd中沒有提供針對資料設定過期時間的操作，透過租約（Lease）來實現資料過期的效果。而Lessor介面就提供了管理租約的相關介面。

 

比如，使用etcdctl命令可以建立一個lease：

etcdctl lease grant 10 lease 694d67ed2bfbea03 granted with TTL(10s)

 

這樣就建立了一個ID為694d67ed2bfbea03的Lease，此時可以將鍵值與這個lease進行系結：

etcdctl put –lease=694d67ed2bfbea03 a b

 

當時間還沒超過過期時間10S時，能透過etcd拿到這對鍵值的資料。如果超時了就獲取不到資料了。

 

從上面的命令可以看出，一個Lease可以與多個鍵值對應，由這個Lease透過管理與其系結的鍵值資料的生命週期。

 

etcd中，將Lease ID存放在名為“lease”的Bucket中，註意在這裡只存放Lease相關的資料，其鍵值為：，之所以不存放與Lease系結的鍵值，是因為這些鍵值已經存放到另外的Bucket裡了，寫入資料的時候也會將這些鍵值系結的Lease ID寫入，這樣在恢復資料的時候就可以將鍵值與Lease ID系結的關係寫入記憶體中。

 

即：Lease這邊需要持久化的資料只有Lease ID與TTL值，而鍵值對這邊會持久化所繫結的Lease ID，這樣在啟動恢復的時候可以將兩者對應的關係恢復到記憶體中。

 

明白了以上關係再來理解Lessor的實現就很簡單了。

 

lessor中主要包括以下的成員：

 

• leaseMap map[LeaseID]*Lease：儲存LeaseID與Lease實體之間的對應關係。
• itemMap map[LeaseItem]LeaseID：leaseItem實際存放的是鍵值，所以這個map管理的就是鍵值與Lease ID之間的對應關係。
• b backend.Backend：持久化儲存，每個Lease的持久化資料會寫入名為“lease”的Bucket中。
• minLeaseTTL int64：最小過期時間，設定給每個lease的過期時間不得小於這個資料。
• expiredC chan []*Lease：透過這個channel通知外部有哪些Lease過期了。

 

其他的就很簡單了:

 

1. lessor啟動之後會執行一個goroutine協程，在這個協程裡定期查詢哪些Lease超時，超時的Lease將透過expiredC channel通知外部。
2. 而針對Lease的CRUD操作，都需要進行加鎖才能操作。

 

KV介面

 

有了以上的準備，可以開始分析資料儲存相關的內容了。在etcd V3中，所有涉及到資料的儲存，都會透過KV介面。

store結構體實現了KV介面，其中最重要的就是封裝了前面提到的幾個資料結構：

• b backend.Backend：用於將持久化資料寫入BoltDB中。
• kvindex index：儲存key索引。
• changes []mvccpb.KeyValue：儲存每次寫操作之後進行了修改的資料，用於通知watch了這些資料變更的客戶端。

 

在store結構體初始化時，根據傳入的backend.Backend，初始化backend.BatchTx結構，後面的任何涉及到事務的操作，都可以透過這個backend.BatchTx來進行。

其實有了前面的準備，理解store結構做的事情已經不難，以一次Put操作為例，其流程主要如下圖所示：

 

applierV3

 

EtcdServer內部實現中，實際使用的是applierV3介面來進行持久化資料的操作。

這個介面有以下幾個實現，但是其中applierV3backend的實現是最重要的，其內部使用了前面提到的KV介面來進行資料的處理。

 

另外，applierV3介面還有其他幾個實現，這裡分別列舉一下。

• applierV3backend：基礎的applierV3介面實現，其他幾個實現都在此實現上做功能擴充套件。內部呼叫EtcdServer中的KV介面進行持久化資料讀寫操作。
• applierV3Capped：磁碟空間不足的情況下，EtcdServer中的applierV3切換到這個實現裡面來，這個實現的任何寫入操作都會失敗，這樣保證底層儲存的資料量不再增加。
• authApplierV3：在applierV3backend的基礎上擴展出許可權控制的功能。
• quotaApplierV3：在applierV3backend的基礎上加上了限流功能，即底層的儲存到了上限的話，會觸發限流操作。

 

綜述

 

下圖將上面涉及到的關鍵資料結構串聯在一起，看看EtcdServer在收到Raft庫透過Ready channel通知的可以持久化資料之後，都做了什麼操作。

 

1. raft庫透過Ready Channel通知上層的raftNode哪些資料可以進行持久化。
2. raftNode啟動之後也是會啟動一個Goroutine來一直監聽這個Ready Channel，以便收到可以持久化資料的通知。
3. raftNode在收到Ready資料之後，將首先寫入WAL日誌中。這裡的WAL日誌由storage結構體來管理，分為兩大部分：WAL日誌以及WAL快照檔案資料Snapshotter，後者用來避免WAL檔案一直增大。
4. raftNode在寫WAL資料完成之後，透過apply Channel通知EtcdServer。
5. EtcdServer啟動之後也是啟動一個Goroutine來監聽這個channel，以便收到可以持久化資料的通知。
6. EtcdServer透過呼叫applierV3介面來持久化資料。applierV3backend結構體實現applierV3介面, applierV3backend結構體實現applierV3介面，內部透過呼叫KV介面進行持久化操作。而在實現KV介面的store結構體中，treeIndex負責在記憶體中維護資料鍵值與revision的對應關係即keyIndex資料，Backend介面負責持久化資料，最後持久化的資料將落盤到BoltDB中。