之前一直聽說過 Calvin悄蕾，也知道有基于 Calvin 的分布式數(shù)據(jù)庫 FaunaDB翘瓮，但一直沒太關注 Calvin 是如何實現(xiàn)的逗概。最近剛好看到一篇文章颅夺，討論了 Calvin vs Spanner蔬胯，立刻就引起了我的興趣对供。因為 TiKV 是基于 Google Spanner 來構建的，所以在很多方面氛濒，我們跟 Calvin 也有很強的對比性产场。當然，僅僅通過一篇 blog 是不夠的舞竿，所以我還是決定先看看 Calvin 相關的論文京景，知道 Calvin 主要做了啥，才好跟 TiKV 對比炬灭。
Calvin 在設計的時候醋粟，并不是為了某一個獨立的系統(tǒng)設計的。Calvin 提供了一個事務調(diào)度層和數(shù)據(jù)復制層重归，采用一個確定鎖機制米愿，來為不同的存儲系統(tǒng)提供分布式事務支持”撬保可以看出育苟，Calvin 的愿景還是非常偉大的，這種可拔插椎木，分層的設計我們 TiDB 這邊也是非常推崇的违柏。這也就更加深了我研究它的興趣。
Traditional Distributed Transaction
對于很多傳統(tǒng)的分布式數(shù)據(jù)庫來說香椎，通常會使用 Agreement Protocol （譬如通常的 two-phase commit）機制來實現(xiàn)分布式事務漱竖，但這個會有一些問題。
首先就是網(wǎng)絡開銷比較大畜伐，一次事務要經(jīng)過多次網(wǎng)絡交互馍惹。有時候這些開銷可能比實際的事務執(zhí)行時間還長。同時玛界，為了保證事務的一致性万矾，我們需要對訪問的數(shù)據(jù)進行加鎖處理，而這個鎖通常只有在事務完成之后才會被釋放慎框。雖然我們能做很多優(yōu)化良狈，譬如將多個并發(fā)的請求作為一個 batch 減少網(wǎng)絡開銷，但這個仍然沒有辦法減少鎖沖突開銷笨枯。
另外薪丁，在分布式事務上面使用鎖遇西，也容易引起死鎖問題，而處理因為死鎖導致的事務終止或者重試窥突，也會增大事務的延時和降低整個系統(tǒng)的吞吐努溃。
Deterministic Database
Calvin 并沒有采用通用的 2PC 實現(xiàn)，Calvin 的目標是盡量的減少分布式事務的開銷阻问，采用的方式很簡單梧税，當一個事務需要多個節(jié)點一起參與的時候，不同節(jié)點在獲取鎖和開始執(zhí)行事務之前称近，就已經(jīng)在外面確定好了如何執(zhí)行這個事務第队。
Calvin 是一個 deterministic database，也就是說刨秆，對于需要處理的事務凳谦，Calvin 會在全局確定好事務的順序，并按照這個順序執(zhí)行衡未。這些事務的執(zhí)行順序尸执，我們可以認為是一個全局的有序 log，并且 Calvin 會通過復制機制來備份到不同的副本上面缓醋。所有的副本都是可以并行的順序執(zhí)行這些 log 的如失。這樣，即使一個副本當?shù)羲土唬硗飧北疽踩匀荒軋?zhí)行并且 commit 事務褪贵。
Calvin Architecture
在前面說到，Calvin 致力于提供的是一個通用的分布式事務解決方案抗俄，所以它可以適配非常多的 storage脆丁，只要這些底層的 storage 系統(tǒng)實現(xiàn)了通常的 CRUD 操作。也就是說动雹，我們可以在單機上面使用 RocksDB槽卫，然后加上 Calvin，就可以對外提供一個支持分布式事務的數(shù)據(jù)庫了胰蝠。
Calvin 主要分為三層：
- Sequencing layer晒夹，也就是 sequencer，負責攔截事務并且將它們放到一個全局的事務序列里面姊氓。這個序列也就是事務執(zhí)行的順序。Sequencer 也同時會處理復制和日志喷好。
- Scheduling layer翔横，也就是 scheduler，它使用一種 deterministic locking scheme 的技術來編排事務的執(zhí)行梗搅，在保證 sequencer 指定的順序下禾唁，盡可能的允許多個事務并發(fā)的執(zhí)行效览。
- Storage layer，最終的數(shù)據(jù)存儲層荡短，可拔插丐枉，能支持不同的 storage。
上面三層都是可以水平擴展的掘托，Calvin 的整個架構如下:
對于 Calvin 來說瘦锹，只要理解了 sequencer 和 scheduler 是如何設計的，那么其實就能理解 Calvin 是如何工作的了闪盔。
Sequencer
Sequencer 的主要作用就是接受客戶端發(fā)過來的事務請求弯院，然后將它們排序，記錄到日志泪掀。因為這些事務是順序排好序了听绳，所以只要依次執(zhí)行，就一定保證整個系統(tǒng)的事務一致性异赫。最簡單的做法當然就是用一個節(jié)點來處理椅挣，但大家知道這鐵定不行，首先就是會有單點問題塔拳，另外就是隨著數(shù)據(jù)量的膨脹鼠证，單個節(jié)點鐵定承載不了。
Calvin 的 sequencer 是能獨立水平擴展的蝙斜，每個 sequencer 會使用一個 10ms 的 epoch 來批量收集一批 client 的請求名惩， 將它們作為一個 batch，然后 sequencer 將這個 batch 持久化到 storage孕荠，并通過復制算法將其備份到其他的副本娩鹉。 Sequencer 支持通常的 Master/Slave 異步復制，以及 Paxos 的復制稚伍。雖然異步復制性能好很多弯予，不過為了保證數(shù)據(jù)安全，采用 Paxos 是一個更好的方案个曙。
當一個 batch 被復制到足夠的副本以后锈嫩，這個 batch 對應的 GUID 會被存儲到一個 Paxos 的 MetaLog 上面，為了更好的提高吞吐垦搬，Calvin 會將多個 GUID 作為 batch 存放到 MetaLog 里面呼寸。
也就是說，Calvin 在 sequencer 這層的處理其實就是將事務做 batch猴贰，通過 Paxos 將 batch 復制到不同的副本对雪，然后在一個中心 Paxos 里面保存對應的 meta 信息。因為 MetaLog 里面保存的事務是順序的米绕，所以外面只需要讀取 MetaLog瑟捣，然后找到對應的事務數(shù)據(jù)馋艺，就能夠順序處理了。
如果真的如我上面這么猜測迈套，Calvin 在 sequencer 這層其實還是有一個處理 MetaLog 瓶頸 Paxos捐祠。
當 transaction batch 復制成功之后，sequencer 就將這個 batch 發(fā)給所有的 scheduler桑李，并帶上 sequencer 的 Node ID踱蛀，以及上面提到的 epoch number。
Scheduler
Calvin 通過 Sequencer 來保證事務的全局有序芙扎，如果完全順序依次執(zhí)行事務星岗，一定可以保證事務的一致性，但這樣性能會很慢戒洼。但如果并發(fā)執(zhí)行俏橘，有可能會遇到不同事務操作相同數(shù)據(jù)的并發(fā)問題。
Calvin 在 Scheduler 這層使用了 deterministic lock scheme 機制保證事務能夠被安全的并發(fā)執(zhí)行圈浇。這個機制大概是這樣的：
- 在所有的 scheduler 上面有一個總的 Lock manager
- 各個節(jié)點自己的 scheduler 只負責 lock 自己本地的數(shù)據(jù)
- 類似嚴格的 two phase locking寥掐，但加入了一些確定限制
- 所有的事務一定要拿到 lock 之后才能開始執(zhí)行
- 所有在事務里面的 lock 順序也是跟全局事務順序一致的，也就是說磷蜀，如果兩個事務 A 和 B 需要獨占一個 lock召耘，A 事務在 B 事務的前面，那么 A 一定比 B 先拿到 lock
- 使用一個單獨的線程來順序處理 lock 請求
- Lock manager 必須按照全局事務順序來授權 lock
按照這個機制褐隆，如果我沒有猜錯污它，Lock manager 應該也是一個單點。
當一個事務拿到所有的 lock 之后庶弃，scheduler 就要開始執(zhí)行這個事務了衫贬，會做如下幾個步驟處理：
- Read/Write 分析，scheduler 會分析這次事務 read 和 write 需要處理的數(shù)據(jù)在哪里歇攻，那些在本地固惯，那些在其他節(jié)點，其他節(jié)點的數(shù)據(jù)叫做 participant缴守，對于需要 write 的節(jié)點葬毫，叫做 active participant，而對于 read 的節(jié)點屡穗，叫做 passive participant贴捡。
- 執(zhí)行 local read。
- 執(zhí)行 remote reads村砂。scheduler 會將 read 請求發(fā)給其他 participants 去執(zhí)行烂斋。
- Collect remote read results
- 執(zhí)行事務，并且 apply local write，對于其他節(jié)點的 write源祈，其他的 scheduler 會自己 apply。
小結(jié)
這里僅僅介紹了我對 Calvin 兩個最重要的組件 Sequencer 和 Scheduler 理解色迂，還有一些 dependent transaction 和 checkpoint 并沒有說明香缺。
按照我的理解，對于 Calvin 來說歇僧，它通過一個全局單點的 log 來保證事務的順序性图张，同時有一個全局 lock manager 來保證事務執(zhí)行的并發(fā)一致性，所以它對于沖突比較嚴重的分布式事務應該有很好的性能诈悍。但它畢竟存在幾個邏輯上面的單點祸轮，所以到底能 scale out 到多少，以及最多能頂住多少的外部請求侥钳，我其實是存疑的适袜。而且 Calvin 的源碼實現(xiàn)比較簡單，F(xiàn)aunaDB 又沒有開源舷夺，所以我其實也并不清楚它如何實現(xiàn)的苦酱。
至于 Calvin vs Spanner 那邊文章，因為已經(jīng)有很多翻譯了给猾，這里就不在說明疫萤。后續(xù)看有沒有時間寫寫 Calvin 跟 TiKV 這邊對比的東西。
