CockroachDB: The Resilient Geo-Distributed SQL Database

語言: CN / TW / HK

一直以來對CockroachDB(CRDB for short)的設計和實現很感興趣,最近抽時間研究了下,發現其在技術上還是領先了同類NewSQL產品不少的,個人感覺應該是目前最為先進的類Spanner分散式資料庫系統,因此這篇文章會盡可能詳細的討論下其系統的多個方面,重點是事務和一致性相關。

paper中針對的是v.19.2.2版本,不過官方文件中是基於最新的v.21.1.7,兩者在描述上有一些衝突的地方,而官方文件中會更為詳盡些,因此本文的很多介紹將盡量將paper與官方reference結合,並以reference為準。

介紹

隨著時代發展,大型跨國企業的事務型工作負載開始出現跨地理位置的趨勢,同時他們也追求對資料放置位置的細粒度控制以及高效能。一般其需求有如下幾點:

  1. 遵循所在地區的資料本地化合規要求,同時儘量保證資料的就近訪問以提供高效能
  2. 為使用者提供高可用的服務,容忍哪怕是region級的失效
  3. 為了簡化上層應用的開發,提供SQL的操作介面和可序列化的事務語義

CRDB是面向具有全球級使用者的企業或組織,基於雲平臺提供具有擴充套件性、高可用性、強一致性和高效能的OLTP事務型資料庫。如其名字,其具有很強的容災和自動恢復能力。為了滿足以上提到的使用者需求,它提供了以下幾個主要功能:

  1. 容錯和高可用: 通過多副本(通常是3-replicas)提供容錯能力,通過自動化的快速恢復實現高可用能力
  2. 跨地理位置的分割槽策略和副本放置策略: CRDB本身是share-nothing架構,可以自動實現水平擴充套件,它內部基於一些啟發式規則來決定資料的放置方式,使用者也可以為資料設定分割槽方案,並從分割槽粒度上控制資料的放置位置
  3. 高效能事務: CRDB的事務協議非常嚴格且對效能做了大量優化,支援跨分割槽事務和可序列化的隔離級別並且不依賴任何特殊的硬體,只需要常規伺服器和基於軟體的時鐘同步協議,因此可以做到跨雲部署。
  4. 有先進的query optimizer和query execution engine,此外一個成熟的資料庫產品所需要的輔助功能如 online schema change / backup and restore / fast import / JSON support等都有支援。

系統架構

本身是share-nothing的架構,每個node同時提供儲存和計算能力。在任一節點內,系統實現了一種分層的架構如下:

  • SQL層

負責查詢優化和執行,對下層的讀寫請求則轉換為KV操作,一般情況下,在SQL層看來,下層是一個單體的KV儲存(一些情況下會暴露出分佈特性)

  • Transaction層

對上層提供事務語義的保證,對到達的KV操作提供隔離性和併發控制等

  • Distribution層

對上層提供一個全域性單調遞增的key space的抽象,所有的資料包括system data/user data都在這個key space內。CRDB採用了range partition的策略,連續的key range以64MB左右為單位進行切分,每個range也就是複製和遷移的基本資料單元(等同於TiKV中的Region)。

從key到Range的對映在system data中,是一個2層的index,同時在每個節點上都有一份cache,方便快速從key定位對應range。

64MB是一個適當的大小,遷移時不會產生大量快速,同時也可以提供不錯的range scan的資料區域性性。 和TiKV一樣,range會根據size自動做split和merge,同時也可以split來避免熱點或儲存的不均衡。

  • Replication層

基於Raft完成多副本的共識,每個range構成一個raft group,複製的內容是kv請求 執行的結果, 基於command形成RSM。

在每個range內,存在一個leaseholder的概念,應該和raft leader是基本等價的,但不同的是leader如果想避免通過raft log做一致性讀取,需要實現raft演算法中的lease read功能,這個leaseholder就是為了這個功能而存在,只有leaseholder才能進行一致性讀,併發起寫操作。

在raft協議中,一個raft group中的前後lease間隔必須保證不會重疊,在CRDB中,這一點通過HLC來實現,具體後面請看這篇單獨的文章,介紹了CRDB的一致性等問題:

通過多副本CRDB實現了容錯能力:

  • 如果是短時間失效例如leader突然crash,raft group會自然選舉出新leader並持續提供服務,重啟後的原leader會rejoin到group中,並變為follower並追上必要的update logs。
  • 如果是長時間失效,CRDB可以自動的補全under-replicated的Ranges,而新建立replica的放置策略也可以有多種:
    • 手動指定: 對於每個節點可以新增必要的“標籤”:系統配置,所在位置等,在建立table時,可以在schema中加入特殊的"region"列,並建立為分割槽表,這樣對不同分割槽可以對映到不同的region中。
    • 自動決定: CRDB內部會基於一系列啟發式規則,總體上是保證系統負載的均衡。
  • Storage層

實現單node內的本地kV儲存,目前使用的是RocksDB。

關於資料的放置策略,paper中具體給出了3種常用策略,基本上都是在效能和容錯能力間做trade-off:

  • Geo-Partitioned Replicas

一個partition內的replica的複製不跨region,這樣一個range的所有副本都固定在一個region內,這樣可以符合資料本地化的合規要求,讀寫效能也會不錯,但無法抵抗region level的失效

例如上圖,同一個region內的所有replica都保留在該region內。

  • Geo-Partitioned Leaseholders

一個partition內的leader都固定在某個region內,但其他replica可以跨range複製,這樣可以有不錯的local read效能,但需要cross-region write,同時也提供了跨region的容災能力

  • Duplicated Indexes

在CRDB中,所有的資料都以索引形式來組織,所以和MySQL類似,主表也是基於primary key的聚簇索引。如果讀負載比較重,可以將二級索引在多個region間建立多份copy,這樣各個region內都可以利用本地index做快速的讀取,缺點則是寫放大(多份index),因此比較適合資料很少變更的情況。

事務

事務是CRDB中最為亮眼的功能,在跨地域部署的前提下,它依然提供了serializable的最強隔離級別,以及近乎linearizability的線性一致性保障,同時還有不錯的效能,可以說是相當牛逼。

首先介紹下CRDB為了事務的延遲和吞吐,做的幾個主要的優化:

  • Write Pipelining

每個針對KV的寫請求到達range leader時,leader會在本地先做evaluation,確定這個request在資料上會產生怎樣的結果,這個結果就是要在多副本間複製的內容,一旦計算完成,就立即向“client”端(gateway node,接收使用者請求的節點)返回一個叫做provisional ACK的東西,同時非同步執行復制,gateway受到ACK後會傳送後續的請求,這樣請求的本地執行就和結果的複製並行了起來,形成pipeline。儘可能減少了操作延遲。

當然,gateway node作為事務的coordinator會跟蹤所有in-flight(沒複製完成)的操作集合。

  • Parallel commit

最直接的方式,當所有in-flight的寫操作都複製完成時,coordinator發起commit的提交操作並完成複製,此時事務就算是提交完成了,但這意味著更多的round-trip和更大的延遲。為此CRDB採用了一個比較激進的方案:

當最後一個write操作回覆provisional ACK後,coordinator立即發起請求,修改事務狀態為 staging + [所有pending write集合]。 然後進入wait狀態等待所有pending write操作都完成,一旦確認都完成就直接向客戶端告知事務已提交,然後非同步的將事務狀態改為committed

這樣來看,實際的write操作和commit操作都形成了流水線,可以很好的減少複製的延遲,理論上如果寫足夠快,2輪的複製延遲(一輪是所有write操作,一輪是staging狀態)內,事務就可以完成提交,當然缺點也很明顯,由於staging -> commit的狀態是非同步修改的,有可能其他併發事務在檢視該事務狀態是看到的仍是staging,那麼需要去確定所有pending的write opertions是否已經完成,如果完成就等同於commit狀態。

實際上,通過這種原子性修改事務狀態的方式,也實現了分散式事務的原子提交,所有寫入資料的可見性也是原子性的switch。

CRDB的事務只支援可序列化的隔離級別,採用了MVTO的併發控制方式,每個事務被分配唯一的時間戳,事務基於時間戳的順序建立在序列化歷史中的先後順序,也就是說,一個事務所有的讀寫操作,都在這個時間戳上“原子性瞬時”完成。

關於事務的部分我會更多參考官方文件的介紹,按照架構層次從上到下介紹整體流程:

  • SQL

client的請求首先到達叢集中某個node,稱為gateway node,它負責SQL的解析優化等,並在execution engine中轉換為對於的KV操作,注意這裡沒有range的概念。

  • Transaction

事務層會在gateway中建立TxnCoordSender,它負責整個事務的執行,TxnCoordSender基於gateway本地的時間戳為事務設定初始ts(既是read ts也是commit ts)。

事務層會把執行層下發的類似put/get的KV請求,打包為BatchRequest,傳送到下層。

為了記錄事務狀態,TxnCoordSender會在事務的第一個write操作所在的range上寫入一條額外的記錄 transaction record。 這個記錄保持了事務的狀態,變化序列是pending -> staging -> committed/aborted。

同時為了維持事務的活躍性,TxnCoordSender會週期性的下發heartbeat到transaction record。

注:

CRDB對於transaction record的處理有一個lazy的優化,即只在必要時才寫入事務狀態記錄,由於這只是個優化,具體細節不再講解,有興趣可以參考CRDB documents

  • Distribution

分佈層的處理仍然在gateway node上,會建立DistSender,針對上層下發的BatchRequest,利用前面提到的key -> range的二級索引結構將BatchRequest拆解為針對各個range的BatchRequest,然後並行的向所有range的leader下發,如前面所說的write pipeling,一個BatchRequest一旦收到provisional ACK就立即下發下一個。

  • Replication

Range leader在收到request後要依次執行以下操作:

  • 檢測rw衝突

為了避免rw衝突,需要檢查當前的write ts是否小於目標key的最近read ts,如果小於則違反了事務的序列化順序(晚的讀操作已經發生,早的寫操作還沒有進行),這是不能允許的,這樣也就保證了

  1. 任何已讀的歷史都不會被更改
  2. 讀總是獲取最近的已提交版本。

為了能夠檢測該衝突,每個range會維護一個timestamp cache,記錄每個key的最近read ts。每個對key的讀操作都會更新該timestamp cache。同時timestamp cache還負責一件事:記錄一個事務的時間戳是否被"push"過,這個後面會介紹。

  • 加讀寫latch

到latch manager中獲取該key的latch,注意latch不是事務鎖,只負責規避對同一key的併發操作衝突,操作完成後(複製完成)即可釋放,這樣保證了一個邏輯物件的讀、寫操作是依次完成的。

  • 對請求本地執行(evaluate)

無論請求是read/write,都要先到storage layer對併發事務的write intent做衝突檢測。

write intent 是事務尚未提交的寫操作,在事務提交前,它寫入的KV中除了正常的MVCC value外,還包含一個pointer,指向該事務的transaction record,這樣其他事務可以從write intent獲取到事務狀態,如果沒有該pointer,則認為這是一個普通的多版本value,版本由其commit ts決定。

write intent起到了預寫入值 + 獨佔鎖的意義,這裡鎖是指事務鎖,任一時刻只有一個事務能夠寫入write intent,代表了對資料的最新寫入

假設txnB遇到txnA的write intent,處理流程如下:

txnB讀取/寫入,遇到A的intent,到transaction record上判斷事務的狀態:

  1. commited,則這已經是一個普通value,幫助消除其pointer資訊
  2. aborted,忽略該intent並幫助刪除
  3. pending,需要判斷事務活躍性
    1. 事務已不活躍(與TxnCoordSender的heartbeat沒有更新),視為aborted處理
    2. 事務活躍,這裡要看下write intent的時間戳
      1. write intent的時間戳小於txnB ts
        1. 如果是read,這裡需要等待,因為read是要保證讀取最近已提交資料的,因此如果跳過該intent讀取更早版本,可能忽略掉這個本應該看到的提交。
        2. 如果是write,也需要等待因為無法判斷write intent事務最終會以哪個時間戳提交(可能被向後push),如果被push到了一個比txnB的ts更晚的時間戳,則txnB當前本質上是應該執行的,因此要等待來判斷會不會出現這種情況。
      2. write intent的時間戳大於txnB ts
        1. 如果是read,忽略該intent,讀取更早版本資料
        2. 如果是write,則當前事務abort掉,以更大的時間戳restart
  4. staging,先驗證事務是否已提交,如果已提交按commited處理,否則按照pending處理

遇到write intent的情況在CRDB中稱為transaction conflict,在處理完conflict後,之前遇到的intent將不復存在,看下對非write intent的處理:

  • read
  1. 讀到ts更大的已提交value,跳過
  2. 讀到比ts更小的已提交value,則可以讀取
  3. 如果已提交value的wts和當前事務的read ts有不確定區間的重合(有偏差的HLC時間戳),則無法確定該value是否可見, 向後push讀事務的時間戳 到不確定區間之後,然後讀取該資料。

這種向後push時間戳的策略實際是對abort -> restart的一種優化,為了保證事務的原子性,在commit ts被push後,要做一個 read refresh 的操作:

假設commit ts從ts1被推到ts2,需要驗證[ts1 -> ts2]時間範圍內,之前事務所有已經讀取的值,是否發生了變化!這個從直覺上很好理解,如果值發生了變化,在ts1上發生的事務與ts2上發生的事務就不再等價了,那麼對於已完成的寫操作,為什麼不需要驗證呢?其實也很簡單,因為寫入的都是write intent,而intent本身就代表了對key的最新操作,是獨佔的,不會有其他事務有更新的write intent或者write,因此不必驗證。

對於這種由於時間戳的不確定區間而後推事務的情況,read refresh操作要立即進行,驗證成功才能繼續後續操作。

  • write

前面已經介紹了rw衝突的檢測,如果發現write ts比timestamp cache中的最近read ts更大,則沒有問題,如果更小,則當前write事務的時間戳要被 後推 到比read ts更大。

如果遇到的已提交value的ts比當前write ts更小,則沒有問題,正常覆蓋。

如果已提交value的ts比當前write ts更大或者兩者處於不確定區間,則類似wr衝突的情況,當前事務的ts要被 後推 到大於已提交value的ts。

這裡提到的push操作,並不是立即做read refreshing檢測的,而是在事務發起commit時完成(為何不立即檢測??)

paper中對於事務的協調演算法和leader上對操作的處理演算法,如下兩圖所示:

可以看到pipelining write的處理和如果出現push(第10行)的refresh驗證

處理流程遵循了上面介紹的get latch -> evaluate -> replicate -> release latch的流程,但沒有展開具體evaluate的過程,不過evaluate返回的資訊中表明瞭可能發生時間戳的push。

  • commit
  1. 首先判斷自己是否被abort了(被更高優先順序事務abort或者一度不再活躍),如果abort則結束並清理。
  2. 如果判斷自己被push過,則執行read refreshing,成功則繼續,否則事務abort並重啟。
  3. 以上兩個檢查通過後,則進入快速commit流程:

DistSender獲取各個BatchRequest的ACK後,會向TxnCoordSender彙總所有的in-flight write操作和所有讀操作的結果,TxnCoordSender在向transaction record記錄staging狀態時,會把in-flight writes同時記錄下來。當等待確定所有in-flight write複製完成後,向client返回提交成功。然後非同步改變transaction狀態為commit,並對write intent做cleanup,清理Pointer使其稱為普通的MVCC value。

到此主要的事務處理流程已經介紹完了,總的來看,處理流程是比較標準的,先檢測了rw衝突,然後是wr/ww衝突,當併發衝突解決後,再考慮timestamp ordering演算法中不允許出現的過晚讀/過晚寫問題,從而保證各個事務對於一個key的操作是依次序列執行,且物理執行順序與事務的時間戳保持一致,也就是說,對於單key事務來說,CRDB可以提供線性一致性的最強保證。

時鐘同步與一致性模型

關於CRDB的HLC-based時鐘機制,以及它所能提供的一致性保證,在單獨一篇文章中進行了詳細的分析,請參看:

這裡就不再贅述了,官方有篇不錯的文章也很值得一看:

SQL層

關於SQL層paper中介紹的不多,總的來說,其對外提供了PostgreSQL的方言和通訊協議。

  • Query Optimizer

採用了Cascades的優化器框架,並利用DSL定義了一系列的transformation rules,例如:

這樣一條DSL定義了match pattern 和 replace pattern,描述如果operator tree中的運算元滿足箭頭左側形式,則可以轉換為箭頭右側的形式。CRDB是用go寫的,DSL也會編譯成go code。

transformation rules分為兩類

  1. Normalization rules,也就是重寫,認為這類轉換是一定要執行的,原來的plan tree不再保留,CRDB中目前有290+的Normalization rule
  2. Exploration rules,不一定會產生更有計劃,例如join ordering,join method等,這種轉換會保留原始plan tree,並基於cost選擇更優plan,CRDB中目前有29條Exploration rule

實現了統一的search演算法,會交錯去apply兩種rules,直到探索了所有轉換。

前面也提到,SQL層一般是不感知下層的分佈資訊的,看做一個單體的KV store,但在optimize時有一些特殊情況:

有些情況下可以利用schema中的partition資訊進行一些特定優化,如:存在idx(region, id),可以靜態改寫query

SELECT * From t where id = 5;
=>
SELECT * From t where id = 5 AND (region = 'east' or region = 'west');

使其可以利用上這個idx。

或者在存在duplicate index時,在考慮不同index副本的訪問cost時,考慮其分佈資訊。

  • Query Planning and Execution

執行有兩種模式

  1. gateway mode : 所有SQL計算都在gateway節點內完成,這種適合掃描資料量較小的情況,很多TP應用的查詢屬於這類
  2. distributed mode:也就是MPP模式,在這種模式下,會有一個專門的physical planning階段,將optimizer產生的單機計劃,轉換為分散式的DAG plan,其中要覺得運算元的並行執行方式,以及資料分發方式,類似下圖:

關於CRDB的優化器,youtube上有個不錯的視訊,是本paper的一作Rebecca Taft在cmu的talk,大家有興趣可以看下:

在每個data stream的內部,CRDB還支援兩種不同的執行模式,根據input cardinality和plan complexity決定: CockroachDB's Query Optimizer (Rebecca Taft, Cockroach Labs) 在每個data stream的內部,CRDB還支援兩種不同的執行模式,根據input cardinality和plan complexity決定:

  1. row-at-a-time,經典的iterator模型,支援所有的SQL運算元計算
  2. vector-at-a-time,向量化執行模型,支援部分SQL運算元,當data從KV中讀取出來後,要先轉換為column format的vector,流經各運算元後,再發送給end user之間轉換回行格式,每個運算元的實現支援了selection vector的輸入。
  • Schema change

CRDB的online schema change參考了F1的方案,具體細節paper中沒有講,可以參考F1的paper,大概來說,每個schema的變更被拆解為一系列的versions,通過控制叢集在任一時間點上,任兩個node一定處於兩個相鄰versions之間,則可以允許叢集的各個node在不同時間點非同步的完成向新schema的轉換,同時仍可對外提供服務。

經驗總結

從2015年成立以來,CRDB Lab在多年的設計、開發中總結了一系列的經驗或者收穫,概述如下:

  • Raft Made Live

雖然raft的paper給出了比較明確、詳細的實現細節,但工程實踐中仍然有很多可以優化的點:

  1. 將同一個node上所有range leader向follower的heartbeat統一,從而大量減少無數range之間heartbeat帶來的網路開銷
  2. Joint Consensus,raft paper中原始的實現方案在執行group成員變更中有個限制,每次只能增加或移除1個成員,這樣就會在過程中存在兩種情況:

上面是先做移除,可以看到group內只有2個member,無法保證quorum

下面是先做增加,group內變為了4個member,這是的quorum變為了3,一旦region3失效了,quorum將被打破。

因此兩種中間狀態都存在可用性問題。

為此CRDB實現了Join Consensus機制,也就是說,在group成員變更時,需要同時滿足old / new兩種configuration,任何寫操作都要同時在兩個raft group下達成quorum才能成功。

具體細節可以參考CRDB官網:

值得一提的是,TiDB5.0的release中,也實現了Joint Consensus。

  • 去除Snapshot Isolation

CRDB事務的設計初衷就是基於MVTO的可序列化事務,支援SI對於他們來說開發成本很高,帶來的效能收益卻沒有那麼大,因為需要對每個read操作加事務鎖,對原有設計破壞的比較厲害,因此他們放棄了對SI的支援。

  • Version Upgrades的坑

在做滾動升級中,有可能一個raft group中的多個node處於不同的軟體版本,在早期實現中複製的是request,然後各個replica各自執行evaluate並apply結果,但這樣可能導致不同replica得到不同執行結果(不同版本二進位制),因此後續改為了先在leader做evaluate,然後複製結果。

  • Follow the workload

CRDB提供這種功能,希望能夠讓leader自適應的跟隨user位置的變化來調整自身的locality,從而始終保持較低的訪問延遲,但實踐證明這個方案很少被使用,使用者決定對於特定負載進行手動的調優並固化下來已經可以達到非常好的效果,而且這種自適應的策略在通用系統中也很難表現良好,經常無法保證效能的可預期性,而這對於使用者來說是至關重要的。

總結

在我來看,CRDB在NewSQL的OLTP型資料庫系統中已經領先了其他競品不少,通過大量的激進優化和開發積累,它建立了很多技術優勢:

  1. 比較先進的query optimizer和executor,支援mpp的並行執行方式,單個執行流中也可以執行向量化的執行。
  2. 先進的事務模型,提供了最為嚴格的隔離級別和幾乎接近完美的一致性模型,同時還能利用大量優化來保證足夠好的效能和擴充套件性,現在看來除了對熱點併發事務的處理不夠理想外,其擴充套件性和事務吞吐、延遲都還是很不錯的
  3. 自動維護能力,包括熱點打散,負載均衡,自動恢復機制等,減輕了運維負擔
  4. 跨地理位置部署的能力和靈活的資料放置策略

類似的系統如YugabyteDB,TiDB,甚至Kudu,雖然各自實現了其中的一些功能,甚至實現的更好,但綜合來看,作為一款分散式大規模OLTP資料庫產品,短時間內應該沒有哪款產品可以超越。