自從 Google 發(fā)布 Spanner 論文后，國(guó)內(nèi)外相繼推出相關(guān)數(shù)據(jù)庫(kù)產(chǎn)品或服務(wù)來(lái)解決數(shù)據(jù)庫(kù)的可擴(kuò)展問(wèn)題。字節(jié)跳動(dòng)在面對(duì)海量數(shù)據(jù)存儲(chǔ)需求時(shí)，也采用了相關(guān)技術(shù)方案。本次分享將介紹我們?cè)跇?gòu)建此類(lèi)系統(tǒng)中碰到的問(wèn)題，解決方案以及技術(shù)演進(jìn)。

一、背景

互聯(lián)網(wǎng)產(chǎn)品中存在很多種類(lèi)的數(shù)據(jù)，不同種類(lèi)的數(shù)據(jù)對(duì)于存儲(chǔ)系統(tǒng)的一致性，可用性，擴(kuò)展性的要求是不同的。比如，金融、賬號(hào)相關(guān)的數(shù)據(jù)對(duì)一致性要求比較高，社交類(lèi)數(shù)據(jù)例如點(diǎn)贊對(duì)可用性要求比較高。

還有一些大規(guī)模元數(shù)據(jù)存儲(chǔ)場(chǎng)景，例如對(duì)象存儲(chǔ)的索引層數(shù)據(jù)，對(duì)一致性，擴(kuò)展性和可用性要求都比較高，這就需要底層存儲(chǔ)系統(tǒng)在能夠保證數(shù)據(jù)強(qiáng)一致的同時(shí)，也具有良好的擴(kuò)展性。在數(shù)據(jù)模型上，有些數(shù)據(jù)比如關(guān)系，KV 模型足夠用;有些數(shù)據(jù)比如錢(qián)包、賬號(hào)可能又需要更豐富的數(shù)據(jù)模型，比如表格。

分布式存儲(chǔ)系統(tǒng)對(duì)數(shù)據(jù)分區(qū)一般有兩種方式：Hash 分區(qū)和 Range 分區(qū)。Hash 分區(qū)對(duì)每條數(shù)據(jù)算一個(gè)哈希值，映射到一個(gè)邏輯分區(qū)上，然后通過(guò)另外一層映射將邏輯分區(qū)映射到具體的機(jī)器上，很多數(shù)據(jù)庫(kù)中間件、緩存中間件都是這樣做的。這種方式的優(yōu)點(diǎn)是數(shù)據(jù)寫(xiě)入一般不會(huì)出現(xiàn)熱點(diǎn)，缺點(diǎn)是原本連續(xù)的數(shù)據(jù)經(jīng)過(guò) Hash 后散落在不同的分區(qū)上變成了無(wú)序的，那么，如果需要掃描一個(gè)范圍的數(shù)據(jù)，需要把所有的分區(qū)都掃描一遍。

相比而言，Range 分區(qū)對(duì)數(shù)據(jù)進(jìn)行范圍分區(qū)，連續(xù)的數(shù)據(jù)是存儲(chǔ)在一起的，可以按需對(duì)相鄰的分區(qū)進(jìn)行合并，或者中間切一刀將一個(gè)分區(qū)一分為二。業(yè)界典型的系統(tǒng)像 HBase。這種分區(qū)方式的缺點(diǎn)是一、對(duì)于追加寫(xiě)處理不友好，因?yàn)檎?qǐng)求都會(huì)打到最后一個(gè)分片，使得最后一個(gè)分片成為瓶頸。優(yōu)點(diǎn)是更容易處理熱點(diǎn)問(wèn)題，當(dāng)一個(gè)分區(qū)過(guò)熱的時(shí)候，可以切分開(kāi)，遷移到其他的空閑機(jī)器上。

從實(shí)際業(yè)務(wù)使用的角度來(lái)說(shuō)，提供數(shù)據(jù)強(qiáng)一致性能夠大大減小業(yè)務(wù)的負(fù)擔(dān)。另外 Range 分區(qū)能夠支持更豐富的訪問(wèn)模式，使用起來(lái)更加靈活?；谶@些考慮，我們使用 C++ 自研了一套基于 Range 分區(qū)的強(qiáng)一致 KV 存儲(chǔ)系統(tǒng) ByteKV，并在其上封裝一層表格接口以提供更為豐富的數(shù)據(jù)模型。

二、架構(gòu)介紹

1、系統(tǒng)組件

整個(gè)系統(tǒng)主要分為 5 個(gè)組件：SQLProxy, KVProxy, KVClient, KVMaster 和 PartitionServer。其中，SQLProxy 用于接入 SQL 請(qǐng)求，KVProxy 用于接入 KV 請(qǐng)求，他們都通過(guò) KVClient 來(lái)訪問(wèn)集群。KVClient 負(fù)責(zé)和 KVMaster、PartitionServer 交互，KVClient 從 KVMaster 獲取全局時(shí)間戳和副本位置等信息，然后訪問(wèn)相應(yīng)的 PartitionServer 進(jìn)行數(shù)據(jù)讀寫(xiě)。PartitionServer 負(fù)責(zé)存儲(chǔ)用戶(hù)數(shù)據(jù)，KVMaster 負(fù)責(zé)將整個(gè)集群的數(shù)據(jù)在 PartitionServer 之間調(diào)度。

集群中數(shù)據(jù)會(huì)按照 range 切分為很多 Partition，每個(gè) Partition 有多個(gè)副本，副本之間通過(guò) Raft 來(lái)保證一致性。這些副本分布在所有的 PartitionServer 中，每個(gè) PartitionServer 會(huì)存儲(chǔ)多個(gè) Partition 的副本，KVMaster 負(fù)責(zé)把所有副本均勻的放置在各個(gè) PartitionServer 中。

各個(gè) PartitionServer 會(huì)定期匯報(bào)自身存儲(chǔ)的副本的信息給 KVMaster，從而 KVMaster 有全局的副本位置信息。Proxy 接到 SDK 請(qǐng)求后，會(huì)訪問(wèn) KVMaster 拿到副本位置信息，然后將請(qǐng)求路由到具體的 PartitionServer，同時(shí) Proxy 會(huì)緩存一部分副本位置信息以便于后續(xù)快速訪問(wèn)。由于副本會(huì)在 PartitionServer 之間調(diào)度，故 Proxy 緩存的信息可能是過(guò)期的，這時(shí)當(dāng) PartitionServer 給 Proxy 回應(yīng)副本位置已經(jīng)變更后，Proxy 會(huì)重新向 KVMaster 請(qǐng)求副本位置信息。

2、分層結(jié)構(gòu)

如上圖所示是 ByteKV 的分層結(jié)構(gòu)。

接口層對(duì)用戶(hù)提供 KV SDK 和 SQL SDK，其中 KV SDK 提供簡(jiǎn)單的 KV 接口，SQL SDK 提供更加豐富的 SQL 接口，滿(mǎn)足不同業(yè)務(wù)的需求。

事務(wù)層提供全局一致的快照隔離級(jí)別(Snapshot Isolation)，通過(guò)全局時(shí)間戳和兩階段提交保證事務(wù)的 ACID 屬性。

彈性伸縮層通過(guò) Partition 的自動(dòng)分裂合并以及 KVMaster 的多種調(diào)度策略，提供了很強(qiáng)的水平擴(kuò)展能力，能夠適應(yīng)業(yè)務(wù)不同時(shí)期的資源需求。

一致性協(xié)議層通過(guò)自研的 ByteRaft 組件，保證數(shù)據(jù)的強(qiáng)一致性，并且提供多種部署方案，適應(yīng)不同的資源分布情況。

存儲(chǔ)引擎層采用業(yè)界成熟的解決方案 RocksDB，滿(mǎn)足前期快速迭代的需求。并且結(jié)合系統(tǒng)未來(lái)的演進(jìn)需要，設(shè)計(jì)了自研的專(zhuān)用存儲(chǔ)引擎 BlockDB。

空間管理層負(fù)責(zé)管理系統(tǒng)的存儲(chǔ)空間，數(shù)據(jù)既可以存儲(chǔ)在物理機(jī)的本地磁盤(pán)，也可以接入其他的共享存儲(chǔ)進(jìn)行統(tǒng)一管理。

三、對(duì)外接口

1、KV 接口

ByteKV 對(duì)外提供兩層抽象，首先是 namespace，其次是 table，一個(gè) namespace 可以有多個(gè) table。具體到一個(gè) table，支持單條記錄的 Put、Delete 和 Get 語(yǔ)義。其中 Put 支持 CAS 語(yǔ)義，僅在滿(mǎn)足某種條件時(shí)才寫(xiě)入這條記錄，如僅在當(dāng)前 key 不存在的情況下才寫(xiě)入這條記錄，或者僅在當(dāng)前記錄為某個(gè)版本的情況下才寫(xiě)入這條記錄等，同時(shí)還支持 TTL 語(yǔ)義。Delete 也類(lèi)似。

除了這些基本的接口外，還提供多條記錄的原子性寫(xiě)入接口 WriteBatch, 分布式一致性快照讀 MultiGet, 非事務(wù)性寫(xiě)入 MultiWrite 以及掃描一段區(qū)間的數(shù)據(jù) Scan 等高級(jí)接口。WriteBatch 可以提供原子性保證，即所有寫(xiě)入要么全部成功要么全部失敗，而 MultiWrite 不提供原子性保證，能寫(xiě)成功多少寫(xiě)成功多少。

MultiGet 提供的是分布式一致性快照讀的語(yǔ)義：MultiGet 不會(huì)讀到其他已提交事務(wù)的部分修改。Scan 也實(shí)現(xiàn)了一致性快照讀的語(yǔ)義，并且支持了前綴掃描，逆序掃描等功能。

2、表格接口

表格接口在 KV 的基礎(chǔ)上提供了更加豐富的單表操作語(yǔ)義。用戶(hù)可以使用基本的 Insert，Update，Delete，Select SQL 語(yǔ)句來(lái)讀寫(xiě)數(shù)據(jù)，可以在 Query 中使用過(guò)濾(Where/Having)排序(OrderBy)，分組(GroupBy)，聚合(Count/Max/Min/Avg)等子句。同時(shí)在 SDK 端我們也提供了 ORM 庫(kù)，方便用戶(hù)的業(yè)務(wù)邏輯實(shí)現(xiàn)。

四、關(guān)鍵技術(shù)

1、自研 ByteRaft

作為一款分布式系統(tǒng)，容災(zāi)能力是不可或缺的。冗余副本是最有效的容災(zāi)方式，但是它涉及到多個(gè)副本間的一致性問(wèn)題。

ByteKV 采用 Raft[1]作為底層復(fù)制算法來(lái)維護(hù)多個(gè)副本間的一致性。由于 ByteKV 采用 Range 分片，每個(gè)分片對(duì)應(yīng)一個(gè) Raft 復(fù)制組，一個(gè)集群中會(huì)存在非常多的 Raft Group。組織、協(xié)調(diào)好 Raft Group 組之間的資源利用關(guān)系，對(duì)實(shí)現(xiàn)一個(gè)高性能的存儲(chǔ)系統(tǒng)至關(guān)重要;同時(shí)在正確實(shí)現(xiàn) Raft 算法基礎(chǔ)上，靈活地為上層提供技術(shù)支持，能夠有效降低設(shè)計(jì)難度。因此我們?cè)趨⒖剂藰I(yè)界優(yōu)秀實(shí)現(xiàn)的基礎(chǔ)上，開(kāi)發(fā)了一款 C++ 的 Multi-Raft 算法庫(kù) ByteRaft。

日志復(fù)制是 Raft 算法的最基本能力，ByteKV 將所有用戶(hù)寫(xiě)入操作編碼成 RedoLog，并通過(guò) Raft Leader 同步給所有副本;每個(gè)副本通過(guò)回放具有相同序列的 RedoLog，保證了一致性。有時(shí)服務(wù) ByteKV 的機(jī)器可能因?yàn)橛布收?、掉電等原因發(fā)生宕機(jī)，只要集群中仍然有多數(shù)副本存活，Raft 算法就能在短時(shí)間內(nèi)自動(dòng)發(fā)起選舉，選出新的 Leader 進(jìn)行服務(wù)。最重要的是，動(dòng)態(tài)成員變更也被 Raft 算法所支持，它為 ByteKV 的副本調(diào)度提供了基礎(chǔ)支持。ByteKV 的 KVMaster 會(huì)對(duì)集群中不同機(jī)器的資源利用率進(jìn)行統(tǒng)計(jì)匯總，并通過(guò)加減副本的方式，實(shí)現(xiàn)了數(shù)據(jù)的遷移和負(fù)載均衡;此外，KVMaster 還定期檢查機(jī)器狀態(tài)，將長(zhǎng)時(shí)間宕機(jī)的副本，從原有的復(fù)制組中摘除。

ByteRaft 在原有 Raft 算法的基礎(chǔ)上，做了很多的工程優(yōu)化。如何有效整合不同 Raft Group 之間的資源利用，是實(shí)現(xiàn)有效的 Multi-Raft 算法的關(guān)鍵。ByteRaft 在各種 IO 操作路徑上做了請(qǐng)求合并，將小粒度的 IO 請(qǐng)求合并為大塊的請(qǐng)求，使其開(kāi)銷(xiāo)與單 Raft Group 無(wú)異;同時(shí)多個(gè) Raft Group 可以橫向擴(kuò)展，以充分利用 CPU 的計(jì)算和 IO 帶寬資源。ByteRaft 網(wǎng)絡(luò)采用 Pipeline 模式，只要網(wǎng)絡(luò)通暢，就按照最大的能力進(jìn)行日志復(fù)制;同時(shí) ByteRaft 內(nèi)置了亂序隊(duì)列，以解決網(wǎng)絡(luò)、RPC 框架不保證數(shù)據(jù)包順序的問(wèn)題。ByteRaft 會(huì)將即將用到的日志都保留在內(nèi)存中，這個(gè)特性能夠減少非常多不必要的 IO 開(kāi)銷(xiāo)，同時(shí)降低同步延遲。

ByteRaft 不單單作為一個(gè)共識(shí)算法庫(kù)，還提供了一整套的解決方案，方便各類(lèi)場(chǎng)景快速接入，因此除了 ByteKV 使用外，還被字節(jié)內(nèi)部的多個(gè)存儲(chǔ)系統(tǒng)使用。

除了上述功能外，ByteRaft 還為一些其他企業(yè)場(chǎng)景提供了技術(shù)支持。

1)Learner

數(shù)據(jù)同步是存儲(chǔ)系統(tǒng)不可或缺的能力。ByteKV 提供了一款事務(wù)粒度的數(shù)據(jù)訂閱方案。這種方案保證數(shù)據(jù)訂閱按事務(wù)的提交順序產(chǎn)生，但不可避免的導(dǎo)致擴(kuò)展性受限。在字節(jié)內(nèi)部，部分場(chǎng)景的數(shù)據(jù)同步并不需要這么強(qiáng)的日志順序保證，為此 ByteRaft 提供了 Learner 支持，我們?cè)?Learner 的基礎(chǔ)上設(shè)計(jì)了一款松散的按 Key 有序復(fù)制的同步組件。

同時(shí)，由于 Learner 不參與日志提交的特性，允許一個(gè)新的成員作為 Learner 加入 Raft Group，等到日志差距不大時(shí)再提升為正常的跟隨者。這個(gè)過(guò)程可以使得 KVMaster 的調(diào)度過(guò)程更為平滑，不會(huì)降低集群可用性。

2)Witness

在字節(jié)內(nèi)部，ByteKV 的主要部署場(chǎng)景為三中心五副本，這樣能夠保證在單機(jī)房故障時(shí)集群仍然能夠提供服務(wù)，但是這種方式對(duì)機(jī)器數(shù)量要求比較大，另外有些業(yè)務(wù)場(chǎng)景只能提供兩機(jī)房部署。因此需要一種不降低集群可用性的方案來(lái)降低成本。Witness 作為一個(gè)只投票不保存數(shù)據(jù)的成員，它對(duì)機(jī)器的資源需求較小，因此 ByteRaft 提供了 Witness 功能。

有了 Witness，就可以將傳統(tǒng)的五副本部署場(chǎng)景中的一個(gè)副本替換為 Witness，在沒(méi)有降低可用性的同時(shí)，節(jié)省出了部分機(jī)器資源。另外一些只有兩機(jī)房的場(chǎng)景中，也可以通過(guò)租用少量的第三方云服務(wù)，部署上 Witness 來(lái)提供和三中心五副本對(duì)等的容災(zāi)能力。更極端的例子場(chǎng)景，比如業(yè)務(wù)有主備機(jī)房的場(chǎng)景下，可以通過(guò)增加 Witness 改變多數(shù)派在主備機(jī)房的分布情況，如果主備機(jī)房隔離，少數(shù)派的機(jī)房可以移除 Witness 降低 quorum 數(shù)目從而恢復(fù)服務(wù)。

2、存儲(chǔ)引擎

1)RocksDB

和目前大多數(shù)存儲(chǔ)系統(tǒng)一樣，我們也采用 RocksDB 作為單機(jī)存儲(chǔ)引擎。RocksDB 作為一個(gè)通用的存儲(chǔ)引擎，提供了不錯(cuò)的性能和穩(wěn)定性。RocksDB 除了提供基礎(chǔ)的讀寫(xiě)接口以外，還提供了豐富的選項(xiàng)和功能，以滿(mǎn)足各種各樣的業(yè)務(wù)場(chǎng)景。然而在實(shí)際生產(chǎn)實(shí)踐中，要把 RocksDB 用好也不是一件簡(jiǎn)單的事情，所以這里我們給大家分享一些經(jīng)驗(yàn)。

①Table Properties

Table Properties 是我們用得比較多的一個(gè)功能。RocksDB 本身提供一些內(nèi)置的 SST 統(tǒng)計(jì)信息，并且支持用戶(hù)自定義的 Table Properties Collector，用于在 Flush/Compaction 過(guò)程中收集統(tǒng)計(jì)信息。具體來(lái)說(shuō)，我們利用 Table Properties 解決了以下幾個(gè)問(wèn)題：

• 我們的系統(tǒng)是采用 Range 切分?jǐn)?shù)據(jù)的，當(dāng)一個(gè) Range 的數(shù)據(jù)大小超過(guò)某個(gè)閾值，這個(gè) Range 會(huì)被分裂。這里就涉及到分裂點(diǎn)如何選取的問(wèn)題。一個(gè)簡(jiǎn)單的辦法是把這個(gè) Range 的數(shù)據(jù)掃一遍，根據(jù)數(shù)據(jù)大小找到一個(gè)中點(diǎn)作為分裂點(diǎn)，但是這樣 IO 開(kāi)銷(xiāo)會(huì)比較大。所以我們通過(guò) Table Properties Collector 對(duì)數(shù)據(jù)進(jìn)行采樣，每隔一定的數(shù)據(jù)條數(shù)或者大小記錄一個(gè)采樣點(diǎn)，那么分裂的時(shí)候只需要根據(jù)這些采樣點(diǎn)來(lái)估算出一個(gè)分裂點(diǎn)即可。
• 多版本數(shù)據(jù)進(jìn)行啟發(fā)式垃圾回收的過(guò)程，也是通過(guò) Table Properties 的采樣來(lái)實(shí)現(xiàn)的。在存儲(chǔ)引擎中，一條用戶(hù)數(shù)據(jù)可能對(duì)應(yīng)有一條或多條不同版本的數(shù)據(jù)。我們?cè)?Table Properties Collector 中采集了版本數(shù)據(jù)的條數(shù)和用戶(hù)數(shù)據(jù)的條數(shù)。在垃圾回收的過(guò)程中，如果一個(gè) Range 包含的版本數(shù)據(jù)的條數(shù)和用戶(hù)數(shù)據(jù)的條數(shù)差不多，我們可以認(rèn)為大部分用戶(hù)數(shù)據(jù)只有一個(gè)版本，那么就可以選擇跳過(guò)這個(gè) Range 的垃圾回收。另外，垃圾回收除了要考慮多版本以外，還需要考慮 TTL 的問(wèn)題，那么在不掃描數(shù)據(jù)的情況下如何知道一個(gè) Range 是否包含已經(jīng)過(guò)期的 TTL 數(shù)據(jù)呢?同樣是在 Table Properties Collector 中，我們計(jì)算出每條數(shù)據(jù)的過(guò)期時(shí)間，然后以百分比的形式記錄不同過(guò)期時(shí)間的數(shù)據(jù)條數(shù)。那么，在垃圾回收的過(guò)程中，給定一個(gè)時(shí)間戳，我們就能夠估算出某一個(gè) Range 里面包含了多少已經(jīng)過(guò)期的數(shù)據(jù)了。
• 雖然 RocksDB 提供了一些參數(shù)能夠讓我們根據(jù)不同的業(yè)務(wù)場(chǎng)景對(duì) compaction 的策略進(jìn)行調(diào)整，比如 compaction 的優(yōu)先級(jí)等，但是實(shí)際上業(yè)務(wù)類(lèi)型多種多樣，很難通過(guò)一套單一的配置能夠滿(mǎn)足所有的場(chǎng)景。這時(shí)候其實(shí)我們也可以根據(jù)統(tǒng)計(jì)信息來(lái)對(duì) compaction 進(jìn)行一定的“干預(yù)”。比方說(shuō)有的數(shù)據(jù)區(qū)間經(jīng)常有頻繁的刪除操作，會(huì)留下大量的 tombstone。如果這些 tombstone 不能被快速的 compaction 清除掉，會(huì)對(duì)讀性能造成很大，并且相應(yīng)的空間也不能釋放。針對(duì)這個(gè)問(wèn)題，我們會(huì)在上層根據(jù)統(tǒng)計(jì)信息(比如垃圾數(shù)據(jù)比例)及時(shí)發(fā)現(xiàn)并主動(dòng)觸發(fā) compaction 來(lái)及時(shí)處理。

②遇到的問(wèn)題和解決辦法

除了上面提到的幾個(gè)用法以外，這里我們?cè)俳o大家分享 RocksDB 使用過(guò)程中可能遇到的一些坑和解決辦法：

• 你是否遇到過(guò)數(shù)據(jù)越刪越多或者已經(jīng)刪除了很多數(shù)據(jù)但是空間長(zhǎng)時(shí)間不能釋放的問(wèn)題呢?我們知道 RocksDB 的刪除操作其實(shí)只是寫(xiě)入了一個(gè) tombstone 標(biāo)記，而這個(gè)標(biāo)記往往只有被 compact 到最底層才能被丟掉的。所以這里的問(wèn)題很可能是由于層數(shù)過(guò)多或者每一層之間的放大系數(shù)不合理導(dǎo)致上面的層的 tombstone 不能被推到最底層。這時(shí)候大家可以考慮開(kāi)啟 level_compaction_dynamic_level_bytes這個(gè)參數(shù)來(lái)解決。
• 你是否遇到過(guò) iterator 的抖動(dòng)導(dǎo)致的長(zhǎng)尾問(wèn)題呢?這個(gè)可能是因?yàn)?iterator 在釋放的時(shí)候需要做一些清理工作的原因，嘗試開(kāi)啟 avoid_unnecessary_blocking_io 來(lái)解決。
• 你是否遇到過(guò) ingest file 導(dǎo)致的抖動(dòng)問(wèn)題?在 ingest file 的過(guò)程中，RocksDB 會(huì)阻塞寫(xiě)入，所以如果 ingest file 的某些步驟耗時(shí)很長(zhǎng)就會(huì)帶來(lái)明顯的抖動(dòng)。例如如果 ingest 的 SST 文件跟 memtable 有重疊，則需要先把 memtable flush 下來(lái)，而這個(gè)過(guò)程中都是不能寫(xiě)入的。所以為了避免這個(gè)抖動(dòng)問(wèn)題，我們會(huì)先判斷需要 ingest 的文件是否跟 memtable 有重疊，如果有的話會(huì)在 ingest 之前先 flush，等 flush 完了再執(zhí)行 ingest。而這個(gè)時(shí)候 ingest 之前的 flush 并不會(huì)阻塞寫(xiě)，所以也就避免了抖動(dòng)問(wèn)題。
• 你是否遇到過(guò)某一層的一個(gè)文件跟下一層的一萬(wàn)個(gè)文件進(jìn)行 compaction 的情況呢?RocksDB 在 compaction 生成文件的時(shí)候會(huì)預(yù)先判斷這個(gè)文件跟下一層有多少重疊，來(lái)避免后續(xù)會(huì)產(chǎn)生過(guò)大的 compaction 的問(wèn)題。然而，這個(gè)判斷對(duì) range deletion 是不生效的，所以有可能會(huì)生成一個(gè)范圍非常廣但是實(shí)際數(shù)據(jù)很少的文件，那么這個(gè)文件再跟下一層 compact 的時(shí)候就會(huì)涉及到非常多的文件，這種 compaction 可能需要持續(xù)幾個(gè)小時(shí)，期間所有文件都不能被釋放，磁盤(pán)很容易就滿(mǎn)了。由于我們需要 delete range 的場(chǎng)景很有限，所以目前我們通過(guò) delete files in range + scan + delete 的方式來(lái)替換 delete range。雖然這種方式比 delete range 開(kāi)銷(xiāo)更大，但是更加可控。雖然也可以通過(guò) compaction filter 來(lái)進(jìn)一步優(yōu)化，但是實(shí)現(xiàn)比較復(fù)雜，我們暫時(shí)沒(méi)有考慮。

由于篇幅有限，上面只是提了幾個(gè)可能大家都會(huì)遇到的問(wèn)題和解決辦法。這些與其說(shuō)是使用技巧，還不如說(shuō)是“無(wú)奈之舉”。很多問(wèn)題是因?yàn)?RocksDB 是這么實(shí)現(xiàn)的，所以我們只能這么用，即使給 RocksDB 做優(yōu)化往往也只能是一些局部調(diào)整，畢竟 RocksDB 是一個(gè)通用的存儲(chǔ)引擎，而不是給我們系統(tǒng)專(zhuān)用的。因此，考慮到以后整個(gè)系統(tǒng)的演進(jìn)的需要，我們?cè)O(shè)計(jì)了一個(gè)專(zhuān)用的存儲(chǔ)引擎 BlockDB。

2)BlockDB

①功能需求

BlockDB 需要解決的一個(gè)核心需求是數(shù)據(jù)分片。我們每個(gè)存儲(chǔ)節(jié)點(diǎn)會(huì)存儲(chǔ)幾千上萬(wàn)個(gè)數(shù)據(jù)分片，目前這些單節(jié)點(diǎn)的所有分片都是存儲(chǔ)在一個(gè) RocksDB 實(shí)例上的。這樣的存儲(chǔ)方式存在以下缺點(diǎn)：

• 無(wú)法對(duì)不同數(shù)據(jù)分片的資源使用進(jìn)行隔離，這一點(diǎn)對(duì)于多租戶(hù)的支持尤為重要。
• 無(wú)法針對(duì)不同數(shù)據(jù)分片的訪問(wèn)模式做優(yōu)化，比如有的分片讀多寫(xiě)少，有的分片寫(xiě)多讀少，那么我們希望對(duì)前者采取對(duì)讀更加友好的 compaction 策略，而對(duì)后者采取對(duì)寫(xiě)更加友好的 compaction 策略，但是一個(gè) RocksDB 實(shí)例上我們只能選擇一種單一的策略。
• 不同數(shù)據(jù)分片的操作容易互相影響，一些對(duì)數(shù)據(jù)分片的操作在 RocksDB 中需要加全局鎖(比如上面提到的 ingest file)，那么數(shù)據(jù)分片越多鎖競(jìng)爭(zhēng)就會(huì)越激烈，容易帶來(lái)長(zhǎng)尾問(wèn)題。
• 不同數(shù)據(jù)分片混合存儲(chǔ)會(huì)帶來(lái)一些不必要的寫(xiě)放大，因?yàn)槲覀儾煌瑯I(yè)務(wù)的數(shù)據(jù)分片是按照前綴來(lái)區(qū)分的，不同數(shù)據(jù)分片的前綴差別很大，導(dǎo)致寫(xiě)入的數(shù)據(jù)范圍比較離散，compaction 的過(guò)程中會(huì)有很多范圍重疊的數(shù)據(jù)。

雖然 RocksDB 的 Column Family 也能夠提供一部分的數(shù)據(jù)切分能力，但是面對(duì)成千上萬(wàn)的數(shù)據(jù)分片也顯得力不從心。而且我們的數(shù)據(jù)分片還需要支持一些特殊的操作，比如分片之間的分裂合并等。因此，BlockDB 首先會(huì)支持?jǐn)?shù)據(jù)分片，并且在數(shù)據(jù)分片之上增加資源控制和自適應(yīng) compaction 等功能。

除了數(shù)據(jù)分片以外，我們還希望減少事務(wù)的開(kāi)銷(xiāo)。目前事務(wù)數(shù)據(jù)的存儲(chǔ)方式相當(dāng)于在 RocksDB 的多版本之上再增加了一層多版本。RocksDB 內(nèi)部通過(guò) sequence 來(lái)區(qū)分不同版本的數(shù)據(jù)，然后在 compaction 的時(shí)候根據(jù) snapshot sequence 來(lái)清除不可見(jiàn)的垃圾數(shù)據(jù)。我們的事務(wù)在 RocksDB 之上通過(guò) timestamp 來(lái)區(qū)分不同版本的用戶(hù)數(shù)據(jù)，然后通過(guò) GC 來(lái)回收對(duì)用戶(hù)不可見(jiàn)的垃圾數(shù)據(jù)。這兩者的邏輯是非常相似的，目前的存儲(chǔ)方式顯然存在一定的冗余。因此，我們會(huì)把一部分事務(wù)的邏輯下推到 BlockDB 中，一方面可以減少冗余，另一方面也方便在引擎層做進(jìn)一步的優(yōu)化。

采用多版本并發(fā)控制的存儲(chǔ)系統(tǒng)有一個(gè)共同的痛點(diǎn)，就是頻繁的更新操作會(huì)導(dǎo)致用戶(hù)數(shù)據(jù)的版本數(shù)很多，范圍查找的時(shí)候需要把每一條用戶(hù)數(shù)據(jù)的所有版本都掃一遍，對(duì)讀性能帶來(lái)很大的影響。實(shí)際上，大部分的讀請(qǐng)求只會(huì)讀最新的若干個(gè)版本的數(shù)據(jù)，如果我們?cè)诖鎯?chǔ)層把新舊版本分離開(kāi)來(lái)，就能夠大大提升這些讀請(qǐng)求的性能。所以我們?cè)? BlockDB 中也針對(duì)這個(gè)問(wèn)題做了設(shè)計(jì)。

②性能需求

除了功能需求以外，BlockDB 還希望進(jìn)一步發(fā)揮高性能 SSD(如 NVMe)隨機(jī) IO 的特性，降低成本。RocksDB 的數(shù)據(jù)是以文件單位進(jìn)行存儲(chǔ)的，所以 compaction 的最小單位也是文件。如果一個(gè)文件跟下一層完全沒(méi)有重疊，compaction 可以直接把這個(gè)文件 move 到下一層，不會(huì)產(chǎn)生額外的 IO 開(kāi)銷(xiāo)?？梢韵胂?，如果一個(gè)文件越小，那么這個(gè)文件跟下一層重疊的概率也越小，能夠直接復(fù)用這個(gè)文件的概率就越大。

但是在實(shí)際使用中，我們并不能把文件設(shè)置得特別小，因?yàn)槲募鄬?duì)文件系統(tǒng)并不友好?；谶@一想法，我們?cè)?BlockDB 中把數(shù)據(jù)切分成 Block 進(jìn)行存儲(chǔ)，而 Block 的粒度比文件小得多，比如 128KB。這里的 Block 可以類(lèi)比為 SST 文件里的 Block，只是我們把 SST 文件的 Block 切分開(kāi)來(lái)，使得這些 Block 能夠單獨(dú)被復(fù)用。但是以 Block 為單位進(jìn)行存儲(chǔ)對(duì)范圍掃描可能不太友好，因?yàn)橥粋€(gè)范圍的數(shù)據(jù)可能會(huì)分散在磁盤(pán)的各個(gè)地方，掃描的時(shí)候需要大量的隨機(jī)讀。不過(guò)在實(shí)際測(cè)試中，只要控制 Block 的粒度不要太小，配合上異步 IO 的優(yōu)化，隨機(jī)讀依然能夠充分發(fā)揮磁盤(pán)的性能。

另外，為了進(jìn)一步發(fā)揮磁盤(pán)性能，減少文件系統(tǒng)的開(kāi)銷(xiāo)，BlockDB 還設(shè)計(jì)了一個(gè) Block System 用于 Block 的存儲(chǔ)。Block System 類(lèi)似于一個(gè)輕量級(jí)的文件系統(tǒng)，但是是以 Block 為單位進(jìn)行數(shù)據(jù)存儲(chǔ)的。Block System 既可以基于現(xiàn)有的文件系統(tǒng)來(lái)實(shí)現(xiàn)，也可以直接基于裸盤(pán)來(lái)實(shí)現(xiàn)，這一設(shè)計(jì)為將來(lái)接入 SPDK 和進(jìn)一步優(yōu)化 IO 路徑提供了良好的基礎(chǔ)。

3、分布式事務(wù)

前面在介紹接口部分時(shí)，提到了 ByteKV 原子性的 WriteBatch 和滿(mǎn)足分布式一致性快照讀的 MultiGet。WriteBatch 意味著 Batch 內(nèi)的所有修改要么都成功，要么都失敗，不會(huì)出現(xiàn)部分成功部分失敗的情況。MultiGet 意味著不會(huì)讀取到其他已提交事務(wù)的部分?jǐn)?shù)據(jù)。

ByteKV 大致采用了以下幾種技術(shù)來(lái)實(shí)現(xiàn)分布式事務(wù)：

• 集群提供一個(gè)全局遞增的邏輯時(shí)鐘，每個(gè)讀寫(xiě)請(qǐng)求都通過(guò)該模塊分配一個(gè)時(shí)間戳，從而給所有請(qǐng)求都分配一個(gè)全局的順序。
• 一個(gè) Key 的每次更新都在系統(tǒng)中產(chǎn)生一個(gè)新的版本，保證新的寫(xiě)入不會(huì)影響到舊的讀的快照。
• 在寫(xiě)請(qǐng)求的流程中引入兩階段提交，保證寫(xiě)入可以有序、原子性的提交。

1)全局授時(shí)服務(wù)

毫無(wú)疑問(wèn)，給所有的事件定序，能讓分布式系統(tǒng)中的很多問(wèn)題都得以簡(jiǎn)化。我們也總是見(jiàn)到各種系統(tǒng)在各種各樣的物理時(shí)鐘、邏輯時(shí)鐘、混合邏輯時(shí)鐘中取舍。ByteKV 從性能、穩(wěn)定性和實(shí)現(xiàn)難度的角度綜合考慮，在 KVMaster 服務(wù)中實(shí)現(xiàn)了一個(gè)提供全局遞增時(shí)間戳分配的接口，供集群所有的讀寫(xiě)模塊使用，該接口保證吐出的時(shí)間戳是全局唯一且遞增的。

之所以采用這樣的架構(gòu)，是因?yàn)槲覀冇X(jué)得：

• 時(shí)鐘分配的邏輯非常簡(jiǎn)單，即便是由一個(gè)單機(jī)模塊來(lái)提供，也能得到穩(wěn)定的延時(shí)和足夠的吞吐。
• 我們可以使用 Raft 協(xié)議來(lái)實(shí)現(xiàn)時(shí)鐘分配模塊的高可用，單機(jī)的失敗絕不會(huì)成為系統(tǒng)的單點(diǎn)。

在具體實(shí)現(xiàn)上，為了保證時(shí)鐘的穩(wěn)定、高效和易用，我們也做了一些工程上的努力和優(yōu)化：

• 同一個(gè)客戶(hù)端拿時(shí)鐘的邏輯是有 Batch 的，這樣可以有效減少 RPC 的次數(shù)。
• 時(shí)鐘的分配要用獨(dú)立的 TCP Socket，避免受到其他的 RPC 請(qǐng)求的干擾。
• 時(shí)鐘的分配用原子操作，完全規(guī)避鎖的使用。
• 時(shí)鐘要盡量接近真實(shí)的物理時(shí)間，非常有利于一些問(wèn)題的調(diào)試。

2)多版本

幾乎所有的現(xiàn)代數(shù)據(jù)庫(kù)系統(tǒng)都會(huì)采用多版本機(jī)制來(lái)作為事務(wù)并發(fā)控制機(jī)制的一部分，ByteKV 也不例外。多版本的好處是讀寫(xiě)互不阻塞。對(duì)一行的每次寫(xiě)入都會(huì)產(chǎn)生一個(gè)新的版本，而讀取通常是讀一個(gè)已經(jīng)存在的版本。邏輯上的數(shù)據(jù)組織如下：

相同的 Key 的多個(gè)版本會(huì)連續(xù)存儲(chǔ)在一起，方便具體版本的定位，同時(shí)版本降序排列以減少查詢(xún)的開(kāi)銷(xiāo)。

為了保證編碼后的數(shù)據(jù)能夠按我們期望的方式排序，對(duì) RocksDB Key 我們采用了內(nèi)存可比較編碼[2]，這里之所以沒(méi)有自定義 RocksDB 的 compare 函數(shù)，是因?yàn)椋?/p>

• Key 比較大小是在引擎讀寫(xiě)中非常高頻的，而默認(rèn)的 memcmp 對(duì)性能非常友好。
• 減少對(duì) RocksDB 的特殊依賴(lài)，提高架構(gòu)的靈活性。
• 為了避免同一個(gè) Key 的多個(gè)版本持續(xù)堆積而導(dǎo)致空間無(wú)限膨脹，ByteKV 有一個(gè)后臺(tái)任務(wù)定期會(huì)對(duì)舊版本、已標(biāo)記刪除的數(shù)據(jù)進(jìn)行清理。在上篇中，存儲(chǔ)引擎章節(jié)做了一些介紹。

3)兩階段提交

ByteKV 使用兩階段提交來(lái)實(shí)現(xiàn)分布式事務(wù)，其大致思想是整個(gè)過(guò)程分為兩個(gè)階段：第一個(gè)階段叫做 Prepare 階段，這個(gè)階段里協(xié)調(diào)者負(fù)責(zé)給參與者發(fā)送 Prepare 請(qǐng)求，參與者響應(yīng)請(qǐng)求并分配資源、進(jìn)行預(yù)提交(預(yù)提交數(shù)據(jù)我們叫做 Write Intent);第一個(gè)階段中的所有參與者都執(zhí)行成功后，協(xié)調(diào)者開(kāi)始第二個(gè)階段即 Commit 階段，這個(gè)階段協(xié)調(diào)者提交事務(wù)，并給所有參與者發(fā)送提交命令，參與者響應(yīng)請(qǐng)求后把 Write Intent 轉(zhuǎn)換為真實(shí)數(shù)據(jù)。

在 ByteKV 里，協(xié)調(diào)者由 KVClient 擔(dān)任，參與者是所有 PartitionServer。接下來(lái)我們從原子性和隔離性角度來(lái)看看 ByteKV 分布式事務(wù)實(shí)現(xiàn)的一些細(xì)節(jié)。

①首先是如何保證事務(wù)原子性對(duì)外可見(jiàn)?

這個(gè)問(wèn)題本質(zhì)上是需要有持久化的事務(wù)狀態(tài)，并且事務(wù)狀態(tài)可以被原子地修改。業(yè)界有很多種解法，ByteKV 采用的方法是把事務(wù)的狀態(tài)當(dāng)作普通數(shù)據(jù)，單獨(dú)保存在一個(gè)內(nèi)部表中。我們稱(chēng)這張表為事務(wù)狀態(tài)表，和其他業(yè)務(wù)數(shù)據(jù)一樣，它也分布式地存儲(chǔ)在多臺(tái)機(jī)器上。事務(wù)狀態(tài)表包括如下信息：

• 事務(wù)狀態(tài)：包括事務(wù)已開(kāi)始，已提交，已回滾等狀態(tài)。事務(wù)狀態(tài)本身就是一個(gè) KV，很容易做到原子性。
• 事務(wù)版本號(hào)：事務(wù)提交時(shí)，從全局遞增時(shí)鐘拿到的時(shí)間戳，這個(gè)版本號(hào)會(huì)被編碼進(jìn)事務(wù)修改的所有 Key 中。
• 事務(wù) TTL：事務(wù)的超時(shí)時(shí)間，主要為了解決事務(wù)夯死，一直占住資源的情況。其他事務(wù)訪問(wèn)到該事務(wù)修改的資源時(shí)，如果發(fā)現(xiàn)該事務(wù)已超時(shí)，可以強(qiáng)行殺死該事務(wù)。

在事務(wù)狀態(tài)表的輔助下，第二階段中協(xié)調(diào)者只需要簡(jiǎn)單地修改事務(wù)狀態(tài)就能完成事務(wù)提交、回滾操作。一旦事務(wù)狀態(tài)修改完成，即可響應(yīng)客戶(hù)端成功， Write Intent 的提交和清理操作則是異步地進(jìn)行。

②第二個(gè)問(wèn)題是如何保證事務(wù)間的隔離和沖突處理?

ByteKV 會(huì)對(duì)執(zhí)行中的事務(wù)按照先到先得的原則進(jìn)行排序，后到的事務(wù)讀取到 Write Intent 后進(jìn)行等待，直到之前的事務(wù)結(jié)束并清理掉 Write Intent 。Write Intent 對(duì)于讀請(qǐng)求不可見(jiàn)，如果 Write Intent 指向的事務(wù) Prepare 時(shí)間大于讀事務(wù)時(shí)間，那么 Write Intent 會(huì)被忽略;否則讀請(qǐng)求需要等待之前的事務(wù)完成或回滾，才能知道這條數(shù)據(jù)是否可讀。

等待事務(wù)提交可能會(huì)影響讀請(qǐng)求的延遲，一種簡(jiǎn)單的優(yōu)化方式是讀請(qǐng)求將還未提交的事務(wù)的提交時(shí)間戳推移到讀事務(wù)的時(shí)間戳之后。前面說(shuō)了這么多 Write Intent，那么 Write Intent 到底是如何編碼的使得處于事務(wù)運(yùn)行中還沒(méi)有提交的數(shù)據(jù)無(wú)法被其他事務(wù)讀到?這里也比較簡(jiǎn)單，只需要把 Write Intent 的版本號(hào)設(shè)置為無(wú)窮大即可。

除了上述問(wèn)題外，分布式事務(wù)需要解決容錯(cuò)的問(wèn)題。這里只討論協(xié)調(diào)者故障的場(chǎng)景，協(xié)調(diào)者故障后事務(wù)可能處于已經(jīng)提交狀態(tài)，也可能處于未提交狀態(tài);部分 PartitionServer 中的 Write Intent 可能已經(jīng)提交或清理，也可能還保留在那里。

如果事務(wù)已經(jīng)提交，隨后的讀寫(xiě)事務(wù)碰到遺留的 Write Intent 時(shí)，會(huì)根據(jù)事務(wù)狀態(tài)表中的狀態(tài)來(lái)輔助之前的事務(wù)提交或清理 Write Intent;如果事務(wù)還未提交，后續(xù)事務(wù)會(huì)在之前的事務(wù)超時(shí)(事務(wù) TTL)后修改事務(wù)狀態(tài)為已回滾，并異步地清理 Write Intent。

由于 Write Intent 本身也包含著事務(wù)的相關(guān)信息，如果我們把參與者列表也記錄在 Write Intent 中，就可以把事務(wù)提交的標(biāo)志從原子的修改完事務(wù)狀態(tài)修改為所有 Write Intent 都完成持久化，從而降低一次提交延遲;而后續(xù)的操作碰到 Write Intent 后可以根據(jù)參與者列表還原出事務(wù)狀態(tài)。

4、分區(qū)自動(dòng)分裂和合并

前面提到 ByteKV 采用 Range 分區(qū)的方式提供擴(kuò)展性，這種分區(qū)方式帶來(lái)的一個(gè)問(wèn)題是：隨著業(yè)務(wù)發(fā)展，原有的分區(qū)結(jié)構(gòu)不再適用于新的業(yè)務(wù)模式。比如業(yè)務(wù)寫(xiě)入熱點(diǎn)變化，熱點(diǎn)從一個(gè)分區(qū)漂移到另一個(gè)分區(qū)。為了解決這個(gè)問(wèn)題，ByteKV 實(shí)現(xiàn)了自動(dòng)分裂的功能：通過(guò)對(duì)用戶(hù)寫(xiě)入進(jìn)行采樣，當(dāng)數(shù)據(jù)量超過(guò)一定閾值后，從中間將 Range 切分為兩個(gè)新的 Range。分裂功能配合上調(diào)度，提供了自動(dòng)擴(kuò)展的能力。

ByteKV 實(shí)現(xiàn)的分裂過(guò)程比較簡(jiǎn)單，當(dāng)某個(gè) Range 發(fā)現(xiàn)自己已經(jīng)達(dá)到分裂條件，便向 KVMaster 申請(qǐng)執(zhí)行一次分裂并拿到新分區(qū)的相關(guān)元信息，然后在 Range 內(nèi)部執(zhí)行分裂操作。分裂命令和普通的操作一樣，作為一條日志，發(fā)送給本 Range 的 Raft Leader;當(dāng)日志提交后，狀態(tài)機(jī)根據(jù)日志攜帶的信息，在原地拉起一個(gè)新的 Raft 副本，這些新副本共同服務(wù)分裂后的一半分區(qū)，原來(lái)的副本服務(wù)另一半分區(qū)。

在另外一些場(chǎng)景，比如大量的 TTL，大量的先寫(xiě)后刪，會(huì)自動(dòng)地分裂出大量的分區(qū)。當(dāng) TTL 過(guò)期、數(shù)據(jù)被 GC 后，這些分裂出來(lái)的分區(qū)就形成了大量的數(shù)據(jù)碎片：每個(gè) Raft Group 只服務(wù)少量的數(shù)據(jù)。這些小分區(qū)會(huì)造成無(wú)意義的開(kāi)銷(xiāo)，同時(shí)維護(hù)它們的元信息也增加了 KVMaster 的負(fù)擔(dān)。針對(duì)這種情況，ByteKV 實(shí)現(xiàn)了自動(dòng)合并功能，將一些較小的區(qū)間和與之相鄰的區(qū)間合并。

合并的過(guò)程比分裂復(fù)雜，master 將待合并的兩個(gè)相鄰區(qū)間調(diào)度到一塊，然后發(fā)起一次合并操作。如上圖所示，這個(gè)過(guò)程分為兩步：首先左區(qū)間發(fā)起一次操作，拿到一個(gè)同步點(diǎn)，然后在右區(qū)間發(fā)起合并操作;右區(qū)間會(huì)進(jìn)行等待，只要當(dāng)前 Server 中左區(qū)間同步點(diǎn)前的數(shù)據(jù)都同步完成，就能夠安全地修改左右區(qū)間的元信息，完成合并操作。

5、負(fù)載均衡

負(fù)載均衡是所有分布式系統(tǒng)都需要的重要能力之一。無(wú)法做到負(fù)載均衡的系統(tǒng)不僅不能充分利用集群的計(jì)算和存儲(chǔ)資源，更會(huì)因?yàn)閭€(gè)別節(jié)點(diǎn)因負(fù)載過(guò)重產(chǎn)生抖動(dòng)進(jìn)而影響服務(wù)質(zhì)量。設(shè)計(jì)一個(gè)好的負(fù)載均衡策略會(huì)面對(duì)兩個(gè)難點(diǎn)，一是需要均衡的資源維度很多，不僅有最基本的磁盤(pán)空間，還有 CPU、IO、網(wǎng)絡(luò)帶寬、內(nèi)存空間等，二是在字節(jié)跳動(dòng)內(nèi)部，機(jī)器規(guī)格非常多樣，同一個(gè)集群內(nèi)的不同節(jié)點(diǎn)，CPU、磁盤(pán)、內(nèi)存都可能不同。我們?cè)谠O(shè)計(jì)負(fù)載均衡策略時(shí)采取了循序漸進(jìn)的辦法，首先只考慮單一維度同構(gòu)機(jī)型的場(chǎng)景，然后擴(kuò)展到多個(gè)維度異構(gòu)機(jī)型。下面介紹一下策略的演進(jìn)過(guò)程。

1)單維度調(diào)度策略

以磁盤(pán)空間單一維度為例，并假設(shè)所有節(jié)點(diǎn)的磁盤(pán)容量完全相同。每個(gè)節(jié)點(diǎn)的磁盤(pán)空間使用量等于這個(gè)節(jié)點(diǎn)上所有副本的數(shù)據(jù)量之和。將所有副本一一分配并放置在某一個(gè)節(jié)點(diǎn)上就形成了一個(gè)副本分配方案。一定有一個(gè)方案，各節(jié)點(diǎn)的數(shù)據(jù)量的方差值最低，這種狀態(tài)我們稱(chēng)之為“絕對(duì)均衡”。

隨著數(shù)據(jù)的持續(xù)寫(xiě)入，節(jié)點(diǎn)的數(shù)據(jù)量也會(huì)持續(xù)發(fā)生變化，如果要讓集群始終保持“絕對(duì)均衡”狀態(tài)，就需要不斷的進(jìn)行調(diào)度，帶來(lái)大量的數(shù)據(jù)遷移開(kāi)銷(xiāo)。不僅如此，某個(gè)維度的絕對(duì)均衡會(huì)使得其它維度的絕對(duì)均衡無(wú)法實(shí)現(xiàn)。從成本和可行性的角度，我們定義了一種更弱的均衡狀態(tài)，稱(chēng)之為“足夠均衡”，它放松了均衡的標(biāo)準(zhǔn)，一方面降低了調(diào)度的敏感度，少量的數(shù)據(jù)量變化不會(huì)引起頻繁調(diào)度，另一方面也讓多個(gè)維度同時(shí)達(dá)到這種弱均衡狀態(tài)成為可能。為了直觀表達(dá)“足夠均衡”的定義，我們畫(huà)這樣一個(gè)示意圖進(jìn)行說(shuō)明：

• 每個(gè)節(jié)點(diǎn)是一根柱子，柱子的高度是它的數(shù)據(jù)量，所有節(jié)點(diǎn)由高到低依次排列
• 計(jì)算出所有節(jié)點(diǎn)的平均數(shù)據(jù)量 Savg，并畫(huà)一條橫線，叫做平均線
• 平均數(shù)據(jù)量分別加、減一個(gè) alpha 值得到高水位值和低水位值，alpha 可以取 Savg 的 10%或 20%，它決定了均衡的松緊程度，根據(jù)水位值畫(huà)出高水位線和低水位線

根據(jù)節(jié)點(diǎn)數(shù)據(jù)量與三條線的關(guān)系，將它們劃分為四個(gè)區(qū)：

• 高負(fù)載區(qū)/主動(dòng)遷出區(qū)：節(jié)點(diǎn)數(shù)據(jù)量高于高水位值
• 高均衡區(qū)/被動(dòng)遷出區(qū)：節(jié)點(diǎn)數(shù)據(jù)量低于高水位值且高于平均值
• 低均衡區(qū)/被動(dòng)遷入?yún)^(qū)：節(jié)點(diǎn)數(shù)據(jù)量高于低水位值且低于平均值
• 低負(fù)載區(qū)/主動(dòng)遷入?yún)^(qū)：節(jié)點(diǎn)數(shù)據(jù)量低于低水位值

當(dāng)節(jié)點(diǎn)位于高負(fù)載區(qū)時(shí)，需要主動(dòng)遷出副本，目標(biāo)節(jié)點(diǎn)位于遷入?yún)^(qū);當(dāng)節(jié)點(diǎn)位于低負(fù)載區(qū)時(shí)，需要主動(dòng)遷入副本，來(lái)源節(jié)點(diǎn)是遷出區(qū)

當(dāng)所有節(jié)點(diǎn)都位于兩個(gè)均衡區(qū)時(shí)，集群達(dá)到“足夠均衡”狀態(tài)，下面這個(gè)圖就是一種“足夠均衡”狀態(tài)

2)多維度調(diào)度策略

以前面的單維度調(diào)度為基礎(chǔ)，多維度調(diào)度的目標(biāo)是使集群在多個(gè)維度上同時(shí)或盡量多地達(dá)到足夠均衡的狀態(tài)。

我們先想象一下，每個(gè)維度都有前面提到的示意圖表示它的均衡狀態(tài)，N 個(gè)維度就存在 N 個(gè)圖。當(dāng)一個(gè)副本發(fā)生遷移的時(shí)候，會(huì)同時(shí)改變所有維度的均衡狀態(tài)，也就是說(shuō)所有的示意圖都會(huì)發(fā)生改變。

如果所有維度都變得更加均衡(均衡區(qū)的節(jié)點(diǎn)數(shù)變多了)，或者一部分維度更均衡而另一部分維度不變(均衡區(qū)的節(jié)點(diǎn)數(shù)不變)，那么這個(gè)遷移是一個(gè)好的調(diào)度;反正，如果所有維度都變得更加不均衡(均衡區(qū)的節(jié)點(diǎn)數(shù)變少了)，或者一部分維度更不均衡而另一部分維度不變，那么這個(gè)遷移是一個(gè)不好的調(diào)度。

還有第三種情況，一部分維度更均衡同時(shí)也有一部分維度更不均衡了，這是一個(gè)中性的調(diào)度，往往這種中性的調(diào)度是不可避免的，例如集群中只有 A、B 兩個(gè)節(jié)點(diǎn)，A 的流量更高而 B 的數(shù)據(jù)量更高，由 A 向 B 遷移副本會(huì)使流量更均衡而數(shù)據(jù)量更不均衡，由 B 向 A 遷移副本則相反。

為了判斷這種中性的調(diào)度能否被允許，我們引入了優(yōu)先級(jí)的概念，為每個(gè)維度賦予一個(gè)唯一的優(yōu)先級(jí)，犧牲低優(yōu)維度的均衡度換來(lái)高優(yōu)維度更加均衡是可被接受的，犧牲高優(yōu)維度的均衡度換來(lái)低優(yōu)維度更加均衡則不可被接受。

仍然考慮前面的例子，因?yàn)榱髁窟^(guò)高會(huì)影響讀寫(xiě)響應(yīng)時(shí)間進(jìn)而影響服務(wù)質(zhì)量，我們認(rèn)為流量的優(yōu)先級(jí)高于數(shù)據(jù)量?jī)?yōu)先級(jí)，因此由 A 向 B 遷移可被接受。但是也存在一個(gè)例外，假設(shè) B 節(jié)點(diǎn)的剩余磁盤(pán)空間已經(jīng)接近 0，并且連集群中最小的副本都無(wú)法容納時(shí)，即使流量的優(yōu)先級(jí)更好，也不應(yīng)該允許向 B 遷移任何副本了。為了直觀表達(dá)這種資源飽和狀態(tài)，我們?cè)谑疽鈭D上增加一條硬限線：

配合這個(gè)示意圖，多維度的負(fù)載均衡策略如下：

• 將多個(gè)維度按照優(yōu)先級(jí)排序，從高優(yōu)維度到低優(yōu)維度依次執(zhí)行上文描述的單維度調(diào)度策略，僅對(duì)流程做少量修改;
• 源節(jié)點(diǎn)上最接近Sbest但小于Sbest的副本為候選遷移對(duì)象，如果它導(dǎo)致任一下列情況出現(xiàn)，則將它排除，選擇下一個(gè)副本作為候選對(duì)象，直到找到合適的副本為止;
• 遷移之后，目標(biāo)機(jī)器在更高優(yōu)維度上將處于高水位線以上
• 遷移之后，目標(biāo)機(jī)器在更低優(yōu)維度上將處于硬限線以上
• 如果對(duì)于某一目標(biāo)節(jié)點(diǎn)，源節(jié)點(diǎn)上無(wú)法選出遷移對(duì)象，將排在目標(biāo)節(jié)點(diǎn)前一位的節(jié)點(diǎn)作為新的目標(biāo)節(jié)點(diǎn)，重復(fù)上述過(guò)程
• 如果對(duì)于所有目標(biāo)節(jié)點(diǎn)，源節(jié)點(diǎn)上仍然無(wú)法選出遷移對(duì)象，將該源節(jié)點(diǎn)從排序列表中剔除，重復(fù)上述過(guò)程

3)異構(gòu)機(jī)型調(diào)度策略

對(duì)于同構(gòu)機(jī)型，一個(gè)單位的負(fù)載在每個(gè)節(jié)點(diǎn)上都會(huì)使用同樣比例的資源，我們可以?xún)H根據(jù)負(fù)載值進(jìn)行調(diào)度，而不必這些負(fù)載使用了多少機(jī)器資源，但在異構(gòu)機(jī)型上這是不成立的。

舉個(gè)例子，同樣是從磁盤(pán)上讀取 1MB 的數(shù)據(jù)，在高性能服務(wù)器上可能只占用 1%的 IO 帶寬和 1%的 CPU cycle，而在虛擬機(jī)上可能會(huì)占用 5%的 IO 帶寬和 3%的 CPU cycle。在不同性能的節(jié)點(diǎn)上，同樣的負(fù)載將產(chǎn)生不同的資源利用率。

要將前面的調(diào)度策略應(yīng)用到異構(gòu)機(jī)型的場(chǎng)景中，首先要將按負(fù)載值進(jìn)行調(diào)度修改為按資源利用率進(jìn)行調(diào)度。對(duì)于數(shù)據(jù)量來(lái)說(shuō)，要改為磁盤(pán)空間利用率;對(duì)于流量來(lái)說(shuō)，要改為 CPU 利用率、IO 利用率等等。為了簡(jiǎn)化策略，我們將內(nèi)存、磁盤(pán) IO、網(wǎng)絡(luò) IO 等使用情況全部納入到 CPU 利用率中。解釋一下為什么這么做：

• 對(duì)內(nèi)存來(lái)說(shuō)，我們的進(jìn)程內(nèi)存使用量的上限是通過(guò)配置項(xiàng)控制的，在部署時(shí)，我們會(huì)保證內(nèi)存使用量一定不會(huì)超過(guò)物理內(nèi)存大小，剩余物理內(nèi)存全部用于操作系統(tǒng)的 buffer/cache，實(shí)際上也能夠被我們利用。內(nèi)存大小會(huì)通過(guò)影響諸如 MemTable、BlockCache 的大小而影響節(jié)點(diǎn)性能，而這種影響最終會(huì)通過(guò) CPU 和 IO 的使用量反映出來(lái)，所以我們考察 CPU 和 IO 的利用率就能把內(nèi)存的使用情況納入進(jìn)來(lái)。
• 對(duì)于磁盤(pán) IO 來(lái)說(shuō)，IO 利用率最終也會(huì)反映在 CPU 利用率上(同步 IO 體現(xiàn)在 wa 上，異步 IO 體現(xiàn)在 sys 上)，因此我們考察 CPU 利用率就能把磁盤(pán) IO 的使用情況納入進(jìn)來(lái)。
• CPU 中有三級(jí) cache，也有寄存器，在考慮 CPU 利用率時(shí)，會(huì)把它當(dāng)作一個(gè)整體，不會(huì)單獨(dú)分析 cache 或是寄存器的使用情況。內(nèi)存和磁盤(pán)可以想象成 CPU 的第四、五級(jí) cache，內(nèi)存越小、磁盤(pán) IO 越慢，CPU 的利用率越高，可以將它們視為一個(gè)整體。

異構(gòu)調(diào)度要解決的第二個(gè)問(wèn)題是，資源利用率和負(fù)載值之間的轉(zhuǎn)換關(guān)系。舉個(gè)例子，A、B 兩個(gè)節(jié)點(diǎn)的 CPU 利用率分別是 50%和 30%，節(jié)點(diǎn)上每個(gè)副本的讀寫(xiě)請(qǐng)求也是已知的，如何從 A 節(jié)點(diǎn)選擇最佳的副本遷移到 B 節(jié)點(diǎn)，使 A、B 的 CPU 利用率差距最小，要求我們必須計(jì)算出每個(gè)副本在 A、B 節(jié)點(diǎn)上分別會(huì)產(chǎn)生多少 CPU 利用率。為了做到這一點(diǎn)，我們盡可能多的收集了每個(gè)副本的讀寫(xiě)請(qǐng)求信息，例如：

• 讀寫(xiě)請(qǐng)求的 key、value 大小
• 讀的 cache 命中率
• 更新的隨機(jī)化程度、刪除的比例

根據(jù)這些信息，將每個(gè)讀寫(xiě)請(qǐng)求轉(zhuǎn)換成 N 個(gè)標(biāo)準(zhǔn)流量。例如，一個(gè) 1KB 以?xún)?nèi)的請(qǐng)求是一個(gè)標(biāo)準(zhǔn)流量，一個(gè) 1~2KB 的請(qǐng)求是 2 個(gè)標(biāo)準(zhǔn)流量;命中 cache 的請(qǐng)求是一個(gè)標(biāo)準(zhǔn)流量，未命中 cache 的請(qǐng)求是 2 個(gè)標(biāo)準(zhǔn)流量。知道節(jié)點(diǎn)上總的標(biāo)準(zhǔn)流量值，就能根據(jù) CPU 利用率算出這個(gè)節(jié)點(diǎn)上一個(gè)標(biāo)準(zhǔn)流量對(duì)應(yīng)的 CPU 利用率，進(jìn)而能夠算出每個(gè)副本在每個(gè)節(jié)點(diǎn)上對(duì)應(yīng)的 CPU 利用率了。

綜上，異構(gòu)機(jī)型調(diào)度策略只需要在多維度調(diào)度策略的基礎(chǔ)上做出如下修改：

• 節(jié)點(diǎn)按照資源利用率排序，而不是負(fù)載值
• 每個(gè)副本的負(fù)載值要分別轉(zhuǎn)換成源節(jié)點(diǎn)的資源利用率和目標(biāo)節(jié)點(diǎn)的資源利用率，在異構(gòu)機(jī)型上，同一個(gè)副本的資源利用率會(huì)有較大的不同

4)其它調(diào)度策略

KVMaster 中，有一個(gè)定時(shí)任務(wù)執(zhí)行上述的負(fù)載均衡策略，叫做“負(fù)載均衡調(diào)度器”，這里不再贅述;同時(shí)，還有另一個(gè)定時(shí)任務(wù)，用來(lái)執(zhí)行另一類(lèi)調(diào)度，叫做“副本放置調(diào)度器”，除了副本安全級(jí)別(datacenter/rack/server)、節(jié)點(diǎn)異常檢測(cè)等基本策略之外，它還實(shí)現(xiàn)了下面幾種調(diào)度策略：

• 業(yè)務(wù)隔離策略：不同 namespace/table 可以存放在不同的節(jié)點(diǎn)上。每個(gè) namespace/table 可指定一個(gè)字符串類(lèi)型的 tag，每個(gè)節(jié)點(diǎn)可指定一個(gè)或多個(gè) tag，副本所在 namespace/table 的 tag 與某節(jié)點(diǎn) tag 相同時(shí)，才可放置在該節(jié)點(diǎn)上。調(diào)度器會(huì)對(duì)不滿(mǎn)足 tag 要求的副本進(jìn)行調(diào)度。
• 熱點(diǎn)檢測(cè)：當(dāng)某個(gè)數(shù)據(jù)分片的數(shù)據(jù)量達(dá)到一定閾值時(shí)會(huì)發(fā)生分裂，除此之外，當(dāng)它的讀寫(xiě)流量超過(guò)平均值的某個(gè)倍數(shù)后，也會(huì)發(fā)生分裂。當(dāng)分裂發(fā)生后，其中一個(gè)新產(chǎn)生的分片(左邊或右邊)的所有副本都會(huì)遷移至其他節(jié)點(diǎn)，避免節(jié)點(diǎn)成為訪問(wèn)熱點(diǎn)。
• 碎片檢測(cè)：當(dāng)某個(gè)數(shù)據(jù)分片的數(shù)據(jù)量和讀寫(xiě)流量都小于平均值的一定比例時(shí)，會(huì)與它所相鄰的分片進(jìn)行合并。合并前會(huì)將小分片的所有副本遷移至相鄰分片所在的節(jié)點(diǎn)上。

五、表格層

前面提到，KV 數(shù)據(jù)模型過(guò)于簡(jiǎn)單，很難滿(mǎn)足一些復(fù)雜業(yè)務(wù)場(chǎng)景的需求。比如：

• 字段數(shù)量和類(lèi)型比較多
• 需要在不同的字段維度上進(jìn)行復(fù)雜條件的查詢(xún)
• 字段或查詢(xún)維度經(jīng)常隨著需求而變化。

我們需要更加豐富的數(shù)據(jù)模型來(lái)滿(mǎn)足這些場(chǎng)景的需求。在 KV 層之上，我們構(gòu)建了表格層 ByteSQL，由前面提到的 SQLProxy 實(shí)現(xiàn)。ByteSQL 支持通過(guò)結(jié)構(gòu)化查詢(xún)語(yǔ)言(SQL)來(lái)寫(xiě)入和讀取，并基于 ByteKV 的批量寫(xiě)入(WriteBatch)和快照讀接口實(shí)現(xiàn)了支持讀寫(xiě)混合操作的交互式事務(wù)。

1、表格模型

在表格存儲(chǔ)模型中，數(shù)據(jù)按照數(shù)據(jù)庫(kù)(database), 表(table)兩個(gè)邏輯層級(jí)來(lái)組織和存放。同一個(gè)物理集群中可以創(chuàng)建多個(gè)數(shù)據(jù)庫(kù)，而每個(gè)數(shù)據(jù)庫(kù)內(nèi)也可以創(chuàng)建多個(gè)表。表的 Schema 定義中包含以下元素：

• 表的基本屬性，包括數(shù)據(jù)庫(kù)名稱(chēng)，表名稱(chēng)，數(shù)據(jù)副本數(shù)等。
• 字段定義：包含字段的名字，類(lèi)型，是否允許空值，默認(rèn)值等屬性。一個(gè)表中須至少包含一個(gè)字段。
• 索引定義：包含索引名字，索引包含的字段列表，索引類(lèi)型(Primary Key，Unique Key，Key 等)。一個(gè)表中有且僅有一個(gè)主鍵索引(Primary Key)，用戶(hù)也可以加入二級(jí)索引(Key 或 Unique Key 類(lèi)型)來(lái)提高 SQL 執(zhí)行性能。每個(gè)索引都可以是單字段索引或多字段聯(lián)合索引。

表中的每一行都按照索引被編碼成多個(gè) KV 記錄保存在 ByteKV 中，每種索引類(lèi)型的編碼方式各不相同。Primary Key 的行中包含表中的所有字段的值，而二級(jí)索引的行中僅僅包含定義該索引和 Primary Key 的字段。具體每種索引的編碼方式如下：

Primary Key: pk_field1, pk_field2,... => non_pk_field1, non_pk_field2...  
Unique Key: key_field1, key_field2,...=> pk_field1, pk_field2...  
NonUnique Key: key_field1, key_field2,..., pk_field1, pk_field2...=>  

其中 pk_field 是定義 Primary Key 的字段，non_pk_field 是表中非 Primary Key 的字段，key_field 是定義某個(gè)二級(jí)索引的字段。=> 前后的內(nèi)容分別對(duì)應(yīng) KV 層的 Key 和 Value 部分。Key 部分的編碼依然采用了上述提到的內(nèi)存可比較編碼，從而保證了字段的自然順序與編碼之后的字節(jié)順序相同。而 Value 部分采用了與 protobuf 類(lèi)似的變長(zhǎng)編碼方式，盡量減少編碼后的數(shù)據(jù)大小。每個(gè)字段的編碼中使用 1 byte 來(lái)標(biāo)識(shí)該值是否為空值。

2、全局二級(jí)索引

用戶(hù)經(jīng)常有使用非主鍵字段做查詢(xún)條件的需求，這就需要在這些字段上創(chuàng)建二級(jí)索引。在傳統(tǒng)的 Sharding 架構(gòu)中(如 MySQL Shard 集群)，選取表中的某個(gè)字段做 Sharding Key，將整個(gè)表 Hash 到不同的 Shard 中。

由于不同 Shard 之間沒(méi)有高效的分布式事務(wù)機(jī)制，二級(jí)索引需要在每個(gè) Shard 內(nèi)創(chuàng)建(即局部二級(jí)索引)。這種方案的問(wèn)題在于如果查詢(xún)條件不包含 Sharding Key，則需要掃描所有 Shard 做結(jié)果歸并，同時(shí)也無(wú)法實(shí)現(xiàn)全局唯一性約束。

為解決這種問(wèn)題，ByteSQL 實(shí)現(xiàn)了全局二級(jí)索引，將主鍵的數(shù)據(jù)和二級(jí)索引的數(shù)據(jù)分布在 ByteKV 的不同的分片中，只根據(jù)二級(jí)索引上的查詢(xún)條件即可定位到該索引的記錄，進(jìn)一步定位到對(duì)應(yīng)的主鍵記錄。這種方式避免了掃描所有 Shard 做結(jié)果歸并的開(kāi)銷(xiāo)，也可以通過(guò)創(chuàng)建 Unique Key 支持全局唯一性約束，具有很強(qiáng)的水平擴(kuò)展性。

3、交互式事務(wù)

ByteSQL 基于 ByteKV 的多版本特性和多條記錄的原子性寫(xiě)入(WriteBatch)，實(shí)現(xiàn)了支持快照隔離級(jí)別(Snapshot Isolation)的讀寫(xiě)事務(wù)，其基本實(shí)現(xiàn)思路如下：

• 用戶(hù)發(fā)起 Start Transaction 命令時(shí)，ByteSQL 從 ByteKV Master 獲取全局唯一的時(shí)間戳作為事務(wù)的開(kāi)始時(shí)間戳(Start Timestamp)，Start Timestamp 既用作事務(wù)內(nèi)的一致性快照讀版本，也用作事務(wù)提交時(shí)的沖突判斷。
• 事務(wù)內(nèi)的所有寫(xiě)操作緩存在 ByteSQL 本地的 Write Buffer 中，每個(gè)事務(wù)都有自己的 Write Buffer 實(shí)例。如果是刪除操作，也要在 Write Buffer 中寫(xiě)入一個(gè) Tombstone 標(biāo)記。
• 事務(wù)內(nèi)的所有讀操作首先讀 Write Buffer，如果 Write Buffer 中存在記錄則直接返回(若 Write Buffer 中存在 Tombstone 返回記錄不存在);否則嘗試讀取 ByteKV 中版本號(hào)小于 Start Timestamp 的記錄。
• 用戶(hù)發(fā)起 Commit Transaction 命令時(shí)，ByteSQL 調(diào)用 ByteKV 的 WriteBatch 接口將 Write Buffer 中緩存的記錄提交，此時(shí)提交是有條件的：對(duì)于 Write Buffer 中的每個(gè) Key，都必須保證提交時(shí)不能存在比 Start Timestamp 更大的版本存在。如果條件不成立，則必須 Abort 當(dāng)前事務(wù)。這個(gè)條件是通過(guò) ByteKV 的 CAS 接口來(lái)實(shí)現(xiàn)的。

由上述過(guò)程可知，ByteSQL 實(shí)現(xiàn)了樂(lè)觀模式的事務(wù)沖突檢測(cè)。這種模式在寫(xiě)入沖突率不高的場(chǎng)景下非常高效。如果沖突率很高，會(huì)導(dǎo)致事務(wù)被頻繁 Abort。

4、執(zhí)行流程優(yōu)化

ByteSQL 提供了更加豐富的 SQL 查詢(xún)語(yǔ)義，但比起 KV 模型中簡(jiǎn)單的 Put，Get 和 Delete 等操作卻增加了額外的開(kāi)銷(xiāo)。SQL 中的 Insert，Update 和 Delete 操作實(shí)際都是一個(gè)先讀后寫(xiě)的流程。以 Update 為例，先使用 Get 操作從 ByteKV 讀取舊值，在舊值上根據(jù) SQL 的 Set 子句更新某些字段生成新值，然后用 Put 操作寫(xiě)入新值到 ByteKV。

在一些場(chǎng)景下，某些字段的值可能是 ByteSQL 內(nèi)自動(dòng)生成的(如自動(dòng)主鍵，以及具有 DEFAULT/ON UPDATE CURRENT_TIMESTAMP 屬性的時(shí)間字段)或根據(jù)依賴(lài)關(guān)系計(jì)算出來(lái)的(如 SET a = a+1)，用戶(hù)需要在 Insert，Update 或 Delete 操作之后立即獲取實(shí)際變更的數(shù)據(jù)，需要在寫(xiě)入之后執(zhí)行一次 Select 操作。總共需要兩次 Get 操作和一次 Put 操作。為了優(yōu)化執(zhí)行效率，ByteSQL 中實(shí)現(xiàn)了 PostgreSQL/Oracle 語(yǔ)法中的 Returning 語(yǔ)義：在同一個(gè) Query 請(qǐng)求中將 Insert/Update 的新值或 Delete 的舊值返回，節(jié)省了一次 Get 開(kāi)銷(xiāo)。

UPDATE table1 SET count = count + 1 WHERE id >= 10 RETURNING id, count; 

5、在線 schema 變更

業(yè)務(wù)需求的不斷演進(jìn)和變化導(dǎo)致 Schema 變更成為無(wú)法逃避的工作，傳統(tǒng)數(shù)據(jù)庫(kù)內(nèi)置的 Schema 變更方案一般需要阻塞整表的讀寫(xiě)操作，這是線上應(yīng)用所無(wú)法接受的。ByteSQL 使用了 Google F1 的在線 Schema 變更方案[3]，變更過(guò)程中不會(huì)阻塞線上讀寫(xiě)請(qǐng)求。

ByteSQL Schema 元數(shù)據(jù)包含了庫(kù)和表的定義，這些元數(shù)據(jù)都保存在 ByteKV 中。SQLProxy 實(shí)例是無(wú)狀態(tài)的，每個(gè)實(shí)例定期從 ByteKV 同步 Schema 到本地，用來(lái)解析并執(zhí)行 Query 請(qǐng)求。

同時(shí)集群中有一個(gè)專(zhuān)門(mén)的 Schema Change Worker 實(shí)例負(fù)責(zé)監(jiān)聽(tīng)并執(zhí)行用戶(hù)提交的 Schema 變更任務(wù)。Schema Change Worker 一旦監(jiān)聽(tīng)到用戶(hù)提交的 Schema 變更請(qǐng)求，就將其放到一個(gè)請(qǐng)求隊(duì)列中并按序執(zhí)行。本節(jié)從數(shù)據(jù)一致性異常的產(chǎn)生和解決角度，闡述了引入 Schema 中間狀態(tài)的原因。詳細(xì)的正確性證明可以參考原論文。

由于不同的 SQLProxy 實(shí)例加載 Schema 的時(shí)機(jī)并不相同，整個(gè)集群在同一時(shí)刻大概率會(huì)有多個(gè)版本的 Schema 在使用。如果 Schema 變更過(guò)程處理不當(dāng)，會(huì)造成表中數(shù)據(jù)的不一致。以創(chuàng)建二級(jí)索引為例，考慮如下的執(zhí)行流程：

• Schema Change Worker 執(zhí)行了一個(gè) Create Index 變更任務(wù)，包括向 ByteKV 中填充索引記錄和寫(xiě)入元數(shù)據(jù)。
• SQLProxy 實(shí)例 1 加載了包含新索引的 Schema 元數(shù)據(jù)。
• SQLProxy 實(shí)例 2 執(zhí)行 Insert 請(qǐng)求。由于實(shí)例 2 尚未加載索引元數(shù)據(jù)，Insert 操作不包含新索引記錄的寫(xiě)入。
• SQLProxy 實(shí)例 2 執(zhí)行 Delete 請(qǐng)求。由于實(shí)例 2 尚未加載索引元數(shù)據(jù)，Delete 操作不包含新索引記錄的刪除。
• SQLProxy 實(shí)例 2 加載了包含新索引的 Schema 元數(shù)據(jù)。

第 3 步和第 4 步都會(huì)導(dǎo)致二級(jí)索引和主鍵索引數(shù)據(jù)的不一致的異常：第 3 步導(dǎo)致二級(jí)索引記錄的缺失(Lost Write)，第 4 步導(dǎo)致二級(jí)索引記錄的遺留(Lost Delete)。這些異常的成因在于不同 SQLProxy 實(shí)例加載 Schema 的時(shí)間不同，導(dǎo)致有些實(shí)例認(rèn)為索引已經(jīng)存在，而另外一些實(shí)例認(rèn)為索引不存在。具體而言，第 2 步 Insert 的異常是由于索引已經(jīng)存在，而寫(xiě)入方認(rèn)為其不存在;第 3 步的 Delete 異常是由于寫(xiě)入方感知到了索引的存在，而刪除方未感知到。實(shí)際上，Update 操作可能會(huì)同時(shí)導(dǎo)致上述兩種異常。

為了解決 Lost Write 異常，我們需要保證對(duì)于插入的每行數(shù)據(jù)，寫(xiě)入實(shí)例需要先感知到索引存在，然后再寫(xiě)入;而對(duì)于 Lost Delete 異常，需要保證同一行數(shù)據(jù)的刪除實(shí)例比寫(xiě)入實(shí)例先感知到索引的存在(如果寫(xiě)入實(shí)例先感知索引，刪除實(shí)例后感知，刪除時(shí)有可能會(huì)漏刪索引而導(dǎo)致 Lost Delete)。

然而，我們無(wú)法直接控制不同 SQLProxy 實(shí)例作為寫(xiě)入實(shí)例和刪除實(shí)例的感知順序，轉(zhuǎn)而使用了間接的方式：給 Schema 定義了兩種控制讀寫(xiě)的中間狀態(tài)：DeleteOnly 狀態(tài)和 WriteOnly 狀態(tài)，Schema Change Worker 先寫(xiě)入 DeleteOnly 狀態(tài)的 Schema 元數(shù)據(jù)，待元數(shù)據(jù)同步到所有實(shí)例后，再寫(xiě)入 WriteOnly 狀態(tài)的 Schema 元數(shù)據(jù)。那些感知到 DeleteOnly 狀態(tài)的實(shí)例只能刪除索引記錄，不能寫(xiě)入索引記錄;感知到 WriteOnly 狀態(tài)的實(shí)例既可以刪除又可以插入索引記錄。這樣就解決了 Lost Delete 異常。

而對(duì)于 Lost Write 異常，我們無(wú)法阻止尚未感知 Schema WriteOnly 狀態(tài)的實(shí)例寫(xiě)入數(shù)據(jù)(因?yàn)檎麄€(gè) Schema 變更過(guò)程是在線的)，而是將填充索引記錄的過(guò)程(原論文中稱(chēng)之為 Reorg 操作)推遲到了 WriteOnly 階段之后執(zhí)行，從而既填充了表中存量數(shù)據(jù)對(duì)應(yīng)的索引記錄，也填充了那些因?yàn)?Lost Write 異常而缺失的索引記錄。待填充操作完成后，就可以將 Schema 元數(shù)據(jù)更新為對(duì)外可見(jiàn)的 Public 狀態(tài)了。

我們通過(guò)引入兩個(gè)中間狀態(tài)解決了 Schema 變更過(guò)程中數(shù)據(jù)不一致的異常。這兩個(gè)中間狀態(tài)均是對(duì) ByteSQL 內(nèi)部而言的，只有最終 Public 狀態(tài)的索引才能被用戶(hù)看到。這里還有一個(gè)關(guān)鍵問(wèn)題：如何在沒(méi)有全局成員信息的環(huán)境中確保將 Schema 狀態(tài)同步到所有 SQLProxy 實(shí)例中?解決方案是在 Schema 中維護(hù)一個(gè)全局固定的 Lease Time，每個(gè) SQLProxy 在 Lease Time 到期前需要重新從 ByteKV 中加載 Schema 來(lái)續(xù)約。

Schema Change Worker 每次更新 Schema 之后，需要等到所有 SQLProxy 加載成功后才能進(jìn)行下一次更新。這就需要保證兩次更新 Schema 的間隔需要大于一定時(shí)間。至于多長(zhǎng)的間隔時(shí)間是安全的，有興趣的讀者可以詳細(xì)閱讀原論文[3]來(lái)得到答案。如果某個(gè) SQLProxy 因?yàn)槟撤N原因無(wú)法在 Lease Time 周期內(nèi)加載 Schema，則設(shè)置當(dāng)前 ByteSQL 實(shí)例為不可用狀態(tài)，不再處理讀寫(xiě)請(qǐng)求。

六、未來(lái)探討

1、更多的一致性級(jí)別

在跨機(jī)房部署的場(chǎng)景里，總有部分請(qǐng)求需要跨機(jī)房獲取事務(wù)時(shí)間戳，這會(huì)增加響應(yīng)延遲;同時(shí)跨機(jī)房的網(wǎng)絡(luò)環(huán)境不及機(jī)房?jī)?nèi)部穩(wěn)定，跨機(jī)房網(wǎng)絡(luò)的穩(wěn)定性直接影響到集群的穩(wěn)定性。實(shí)際上，部分業(yè)務(wù)場(chǎng)景并不需要強(qiáng)一致保證。在這些場(chǎng)景中，我們考慮引入混合邏輯時(shí)鐘 HLC[4]來(lái)替代原有的全局授時(shí)服務(wù)，將 ByteKV 改造成支持因果一致性的系統(tǒng)。同時(shí)，我們可以將寫(xiě)入的時(shí)間戳作為同步口令返回給客戶(hù)端，客戶(hù)端在后續(xù)的請(qǐng)求中攜帶上同步口令，以傳遞業(yè)務(wù)上存在因果關(guān)系而存儲(chǔ)系統(tǒng)無(wú)法識(shí)別的事件之間的 happen-before 關(guān)系，即會(huì)話一致性。

此外，還有部分業(yè)務(wù)對(duì)延遲極其敏感，又有多數(shù)據(jù)中心訪問(wèn)的需求;而 ByteKV 多機(jī)房部署場(chǎng)景下無(wú)法避免跨機(jī)房延遲。如果這部分業(yè)務(wù)只需要機(jī)房之間保持最終一致即可，我們可以進(jìn)行機(jī)房間數(shù)據(jù)同步，實(shí)現(xiàn)類(lèi)最終一致性的效果。

2、Cloud Native

隨著 CloudNative 的進(jìn)一步發(fā)展，以無(wú)可匹敵之勢(shì)深刻影響著現(xiàn)有的開(kāi)發(fā)部署模型。ByteKV 也將進(jìn)一步探索與 CloudNative 的深入結(jié)合。探索基于 Kubernetes 的 auto deployment, auto scaling, auto healing。進(jìn)一步提高資源的利用率，降低運(yùn)維的成本，增強(qiáng)服務(wù)的易用性。提供一個(gè)更方便于 CloudNative 用戶(hù)使用的 ByteKV。