TiKV是什么

一個(gè)全局有序的分布式 Key-Value 引擎

起初，看到這句話的時(shí)候并沒有深刻的體會(huì)，現(xiàn)在回過頭看這句話，每個(gè)詞都是有用的。有序、分布式、kv存儲(chǔ)構(gòu)成了TiKV的核心元素。

TiKV 的特性

• 多副本
• 具有水平擴(kuò)展能力
• 提供分布式事務(wù)支持

Key有序

首先，需要解釋的是全局有序。這點(diǎn)很重要，作為數(shù)據(jù)庫底層的存儲(chǔ)有很多場景需要全局有序。
當(dāng)我們想快速的獲取某一行的數(shù)據(jù)的時(shí)候，基于主鍵可以迅速的找到對(duì)應(yīng)的key，這個(gè)我們之前已經(jīng)說過; 但是還有很多場景需要找一批數(shù)據(jù)，比如where id > 1 and id < 100 , 全局的有序可以幫出我們迅速的定位到數(shù)據(jù)存在于什么地方，省去了全局掃表的過程。

現(xiàn)在問題來了，如何實(shí)現(xiàn)全局有序呢？
答案其實(shí)很簡單，rocksdb。 那我們就按圖索驥，看看rocksdb是什么。

rocksdb

在我看來，選擇rocksdb 也是一個(gè)誤打誤撞的結(jié)果。從出發(fā)點(diǎn)上，rocksdb來源于leveldb，都是想解決傳統(tǒng)硬盤IO吞吐問題，因此使用了Sorted String Table + LSM tree 來做存儲(chǔ)。
選擇這種結(jié)構(gòu)的基礎(chǔ)假設(shè)是隨機(jī)訪問要比塊訪問慢，因此盡量將數(shù)據(jù)連續(xù)的存儲(chǔ)下來。數(shù)據(jù)連續(xù)的存儲(chǔ)，那么它勢(shì)必是有序的結(jié)構(gòu)。在這個(gè)場景下rocksdb天然是一個(gè)有序key 的存儲(chǔ)，而這個(gè)也恰恰是TiKV需要的東西。

我們不妨簡單的看一下rocksdb的API：

  std::string value;
  rocksdb::Status s = db->Get(rocksdb::ReadOptions(), key1, &value);
  if (s.ok()) s = db->Put(rocksdb::WriteOptions(), key2, value);
  if (s.ok()) s = db->Delete(rocksdb::WriteOptions(), key1);

for (it->Seek("hello"); it->Valid(); it->Next()) {
  // Do something with it->key() and it->value().
}

auto iter = db->NewIterator(ReadOptions());
iter->Seek("a1");        // iter->Key() == "a1";
iter->Seek("a3");        // iter->Key() == "a3";
iter->SeekForPrev("c4"); // iter->Key() == "c4";
iter->SeekForPrev("c3"); // iter->Key() == "c2";

從這幾個(gè)接口可以簡單的看出來，rocksdb天然的有序?qū)傩浴Ｊ褂眠@樣的存儲(chǔ)，相似的key 會(huì)分布在相似的地方，對(duì)SQL查詢中的order， range查詢有非常大的效率的提升。

分布式kv

如果沒有分布式，失去了橫向的擴(kuò)展能力，那么整個(gè)地基都將不復(fù)存在，分布式數(shù)據(jù)庫也無從談起。
分布式系統(tǒng)區(qū)別于單機(jī)系統(tǒng)或者集群是缺少排它鎖資源。多線程程序，在需要同步的時(shí)候，無論獲取數(shù)據(jù)庫鎖，redis鎖，都是因?yàn)檫@些系統(tǒng)是單機(jī)系統(tǒng)。假象一下，多線程程序分布在不同的機(jī)器上，在整個(gè)系統(tǒng)中缺少單點(diǎn)資源來做鎖，同步是多么難的事情。

在我看來，分布式要解決的問題是兩個(gè)：

1. 副本一致性
2. 分布式事務(wù)的一致性

副本一致性是用來解決可用性問題的，而分布式事務(wù)是用來解決一致性的，加上分布式的網(wǎng)絡(luò)分區(qū)，這就構(gòu)成了CAP。

那么，從宏觀往細(xì)節(jié)看，我們首先看看分布式事務(wù)是什么東西

分布式事務(wù)

TiKV 分布式事務(wù)采用了Google 的Percolator系統(tǒng)的實(shí)現(xiàn)。在Percolator中，google為了解決索引批處理任務(wù)時(shí)間周期長的問題，將創(chuàng)建倒排索引索引的MapReducee 任務(wù)拆成了一系列的小任務(wù)。假設(shè)只有一個(gè)網(wǎng)站的數(shù)據(jù)有更新，那么倒排索引只會(huì)影響到有限的一些相關(guān)網(wǎng)頁，那么這個(gè)任務(wù)可以非常快速的完成，不需要重新啟動(dòng)一個(gè)全量的MapReduce任務(wù)。

Percolator 中的分布式事務(wù)其實(shí)很容易明白，設(shè)計(jì)也很巧妙。它采用的是主從鎖，從鎖標(biāo)記主鎖來源達(dá)到了事務(wù)的最終一致性。

搬運(yùn)一下論文中的轉(zhuǎn)賬流程

Bob 有10元錢， Joe有2元錢，現(xiàn)在Bob 要給Joe 轉(zhuǎn)賬7元錢

PreWrite 操作

第一步， Bob 賬戶減少7元

此時(shí) Bob在version7上將數(shù)據(jù)變更，同時(shí)加上主鎖，這個(gè)時(shí)候其他的客戶端讀數(shù)據(jù)發(fā)現(xiàn)7是空，會(huì)往下找6,6指向的數(shù)據(jù)是version5, 因此依然是10.

第二步 Joe 賬戶上增加7元

此時(shí)， 同第一步一樣，金額增加，不同的是鎖加入的是從鎖，這個(gè)從鎖指向了主鎖對(duì)應(yīng)的行。

Commit 操作

第三步，將刪除主鎖

第四步， 刪除從鎖

幾個(gè)思考

在這里，思考問題的時(shí)候，不要去想副本的一致性問題，TiKV的副本一致性是由raft 協(xié)議來保證的，具體后續(xù)會(huì)有介紹。目前轉(zhuǎn)賬模型可以簡單的看作Bob, Joe 數(shù)據(jù)在兩臺(tái)電腦上。解釋兩個(gè)問題

1. 為什么要多版本

如果沒有多版本是否可以？ 當(dāng)然可以。我可以將同一個(gè)數(shù)據(jù)分成兩份，A和B。讀取的時(shí)候直接那讀的A，寫的時(shí)候開啟一個(gè)事務(wù)，讀取一下數(shù)據(jù)，備份到B里，在事務(wù)期間，讀寫都在這里進(jìn)行。事務(wù)結(jié)束的時(shí)候?qū)?shù)據(jù)覆蓋到A里面。實(shí)時(shí)上確實(shí)有開源的分布式數(shù)據(jù)庫采用這種方式。 或者更極端一些，數(shù)據(jù)只保留一份，那么僅僅是在事務(wù)發(fā)生的過程中，所有的讀請(qǐng)求都需要排隊(duì)，等待事務(wù)完成。多版本并非是 Percolator中特有的東西。MVCC (多版本訪問控制)可以將讀寫分離開，是用來提高整個(gè)系統(tǒng)的吞吐量的。與此同時(shí)，配合一些技巧，可以達(dá)到RR的事務(wù)隔離級(jí)別。

2. 鎖放在了多版本的行上？

無論是論文，還是代碼的實(shí)現(xiàn)，的確如此。但是我們來看本質(zhì)，Bob的數(shù)據(jù)，無論在任何時(shí)間點(diǎn)上，要么沒有鎖，要么就是最高的版本上有一個(gè)寫鎖。這個(gè)完全可以將鎖和版本分割開。Bob有多版本，一個(gè)鎖，存儲(chǔ)在不同的地方，也是可以的。

在TiKV的實(shí)現(xiàn)上也比較巧妙。如果按照論文的方法，我們很有可能就會(huì)在TiDB上為每個(gè)表偷偷的創(chuàng)建兩列lock、write。
之前我們也說過，TiDB將數(shù)據(jù)庫表的行作為value，保存在TiKV中。TiKV并不關(guān)心value具體內(nèi)容是什么。那么TiDB創(chuàng)建這兩列，自己來維護(hù)lock也是很自然的想法。
TiKV 并沒有這么做，而是將事務(wù)處理的相關(guān)內(nèi)容下移到了TiKV中來做。那么問題來了，TiKV不應(yīng)該理解value中的結(jié)構(gòu)，TiKV是怎么實(shí)現(xiàn)的呢？
rocksdb在3.0后引入了一個(gè)新特性Column Families，kv并非是平鋪的，而是使用cf當(dāng)作容器來存儲(chǔ)，在一個(gè)cf中，key 是唯一的，但是在多個(gè)cf 中可以有同樣的key。這樣做到了一定的隔離性。這個(gè)特性很redis的db的概念一樣。

查看代碼可以看到， TiKV 使用了三個(gè)cf, 一個(gè)用來存儲(chǔ)kv, 一個(gè)用來存儲(chǔ)鎖， 一個(gè)用來存儲(chǔ)data的數(shù)據(jù)指針。同一個(gè)key, 在cf中可以獲取到value, lock, write，這樣就實(shí)現(xiàn)了邏輯上的Percolator的行結(jié)構(gòu)。

pub type CfName = &'static str;

pub const CF_DEFAULT: CfName = "default";

pub const CF_LOCK: CfName = "lock";

pub const CF_WRITE: CfName = "write";

pub const CF_RAFT: CfName = "raft";

pub const LARGE_CFS: &[CfName] = &[CF_DEFAULT, CF_WRITE];

pub const ALL_CFS: &[CfName] = &[CF_DEFAULT, CF_LOCK, CF_WRITE, CF_RAFT];

pub const DATA_CFS: &[CfName] = &[CF_DEFAULT, CF_LOCK, CF_WRITE];

注意代碼中最后一樣DATA_CFS，就是Percolator行結(jié)構(gòu)的視圖。

代碼的實(shí)現(xiàn)

我們先簡單的看一小段代碼是如何調(diào)用write的

    pub fn async_raw_put(
        &self,
        ctx: Context,
        cf: String,
        key: Vec<u8>,
        value: Vec<u8>,
        callback: Callback<()>,
    ) -> Result<()> {
        if key.len() > self.max_key_size {
            callback(Err(Error::KeyTooLarge(key.len(), self.max_key_size)));
            return Ok(());
        }
        self.engine.async_write(
            &ctx,
            vec![
                Modify::Put(Storage::rawkv_cf(cf)?, Key::from_encoded(key), value),
            ],
            box |(_, res): (_, engine::Result<_>)| callback(res.map_err(Error::from)),
        )?;
        KV_COMMAND_COUNTER_VEC.with_label_values(&["raw_put"]).inc();
        Ok(())
    }

在這里Modify::Put，會(huì)異步的發(fā)送Put消息，有接收消息的代碼來處理相關(guān)邏輯，它會(huì)將數(shù)據(jù)寫到存儲(chǔ)中。其中需要三個(gè)參數(shù)：cf，key, value。

其中代碼在storage/mvcc/write.rs 中定義了一個(gè)Write結(jié)構(gòu)

pub enum WriteType {
    Put,
    Delete,
    Lock,
    Rollback,
}

const FLAG_PUT: u8 = b'P';
const FLAG_DELETE: u8 = b'D';
const FLAG_LOCK: u8 = b'L';
const FLAG_ROLLBACK: u8 = b'R';


pub struct Write {
    pub write_type: WriteType,
    pub start_ts: u64,
    pub short_value: Option<Value>,
}


pub type Value = Vec<u8>;

感覺就是用來處理value的，但是為什么保存的時(shí)候加上了 write_type start_ts ，這個(gè)還沒有弄明白。

本質(zhì)是什么

在我看來分布式事務(wù)逃不過2PC，為什么這么說呢？在一個(gè)分布式系統(tǒng)中，每個(gè)節(jié)點(diǎn)無法有效的獲取全局狀態(tài)。這個(gè)時(shí)候需要一個(gè)協(xié)調(diào)者他來記錄每個(gè)人的狀態(tài)，并對(duì)其發(fā)號(hào)施令。而為什么是兩階段呢？我感覺是為了讓rollback過程邏輯上是可以成功的。

我們不防舉一個(gè)簡單的小例子：

假設(shè)需要給用戶做一次退款，退款由兩部分組組成，其中一部分是賬戶余額，一部分是優(yōu)惠劵。如果不使用2PC，賬戶余額直接增加退款金額后，優(yōu)惠劵退款失敗了。這個(gè)時(shí)候用戶已經(jīng)看到了賬戶余額的變更，如果這個(gè)時(shí)候用戶做了一筆提現(xiàn)操作，那么rollback 是不會(huì)成功的。
如果是用2PC, prepare階段給用戶賬戶上加鎖，禁止其他任何賬戶的變更請(qǐng)求，必須等待當(dāng)前事務(wù)處理完成后才可以執(zhí)行。那么rollback 是可以成功的。不會(huì)出現(xiàn)一致性問題。

我們生活中有大量的場景使用2PC，跑步比賽，預(yù)備-----開始！ 預(yù)備就是大家都在上鎖，開始就是在執(zhí)行任務(wù)。

所以，分布式事務(wù)本質(zhì)是在第一個(gè)階段各個(gè)節(jié)點(diǎn)需要加鎖來為整個(gè)事務(wù)做準(zhǔn)備。等所有人都準(zhǔn)備好了，那么開始執(zhí)行事務(wù)。

Percolator中使用的事務(wù)方法巧妙的地方在于除去了中間的協(xié)調(diào)者，使用主從鎖、從鎖維持主鎖的引用，在任意一個(gè)時(shí)期，每個(gè)節(jié)點(diǎn)都知道當(dāng)前事務(wù)是否執(zhí)行完成（或者應(yīng)該怎么redo 或者rollback）?？疵靼走@個(gè)，TiKV中分布式事務(wù)的本質(zhì)就弄明白了。

PS:

1. TiKV, TiDB 中大量參考了Google 論文中的相關(guān)內(nèi)容，吸收了本質(zhì)原理，排除無用東西。 Percolator論文中介紹Percolator是一個(gè)大型系統(tǒng)，其中使用了上述的主從鎖來解決分布式事務(wù)問題。因此，在我看來，Percolator不能跟主從鎖的分布式事務(wù)劃等號(hào).