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

[[285707]]

概覽

下圖中展示了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這個概念，以下面的例子來說明。

比如通過批量接口兩次更新兩對鍵值，第一次寫入數據時，寫入

 

 

而在第二次更新寫入數據

 

 

其中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過期了。

其他的就很簡單了:

lessor啟動之后會運行一個goroutine協程，在這個協程里定期查詢哪些Lease超時，超時的Lease將通過expiredC channel通知外部。

而針對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中。