如何編寫一個分布式數據庫

講師: 劉奇(goroutine)

個人簡介：

PingCAP創始人兼CEO。分布式系統專家，擅長分布式數據庫，分布式緩存。目前從事NewSQL方向的創業，通過開源方式重建google內部的F1和spanner。目前項目已經開源，https://github.com/pingcap/tidb

正文內容：

大家好, 我是開源項目 分布式 NewSQL 數據庫 TiDB 和 分布式緩存 Codis 的 創始人 劉奇, 之前在京東， 豌豆莢做 infrastructure 相關的事情, 現在在創業 (PingCAP), 方向是分布式數據庫. 最近如果有朋友關注開源社區或者HackerNews 的話，可能會發現一個叫 TiDB 的數據庫項目吸引了一些眼球（https://github.com/pingcap/tidb ) 。 這是我們開源的第一個東西，短短幾天得到了過千Star，特別感謝大家的支持和鼓勵。

今天主要介紹一下 NewSQL 與 TiDB 的設計實現, 未來的一些 Roadmap 以及 一些做開源項目的心得。

大家可能經常用數據庫，但是很少寫一個數據庫（實在是有點 hardcore），今天我就從一個開發者的角度，來看看如何寫一個分布式數據庫，因為這個話題實在太大，我試著講一下，講的不好請各位海涵 :D

數據庫系統架構如何分層

某種程度上看來，數據庫作為整個系統的核心，這句話其實并不夸張，數據庫的選型關系到上層業務代碼實現的方方面面，現在比較流行的架構方案是上層業務邏輯微服務化，并且結合分布式緩存，這套框架已經基本能做到上層業務的彈性擴展，但是最底層的數據存儲還是很難去中心化（除非整個技術棧中去除關系型數據庫（RDBMS）, 全部采用 NoSQL）。所以，經常是 RDBMS 成為整個系統的瓶頸。

在長期的斗爭中，大家總結出了很多方式來擴展最底層的關系型數據庫：

1. 主從，一主多從，雙寫，通過隊列暫存請求... 這些方案其實并沒有解決問題，寫入仍然是單點，而且對于 DBA 的挑戰比較大，今天我們暫時就不討論了。

2. 通過中間件 Sharding，常見的開源方案有： Cobar, TDDL, Vitess, Kingshard, MyCat 等，這些方案的思路是攔截 SQL 的請求通過 sharding key 和一定規則，將請求轉發/廣播到不同的 MySQL 實例上，從而實現水平擴展的效果，這個方案基本解決了單點寫入的問題，對于業務來說整體的吞吐也上來了，看上去不錯，這個方案是大多數業務遇到性能瓶頸的解決方案，但是缺點也是有的：

1）大多中間件都沒有解決動態擴容的問題，多采用了靜態的路由策略，擴容一般還處于人工 x2 的狀態，對 DBA 要求比較高。

2）從一定程度上來說都放棄了事務，這是由于一條語句有可能會涉及到多個數據庫實例，實現分布式 事務是一個比較難的事情，我們后面會詳細的介紹。

3）對業務不透明，需要指定 sharding key， 心智負擔較大

特別是第二點，由于放棄事務，對于上層業務的程序的寫法帶來很多的影響，有一些中間件支持部分的事務，但是需要使用者保證參與事務的行都會落在一臺實例上（例如 sharding key 選為 userid 按照同一個 user_id 下的多行進行事務操作，）對于一些簡單的業務來說還比較好，但是一旦對于一致性的要求比較高的業務，就會給開發者帶來了比較大的心智負擔，比如通過隊列繞開（http://blog.jobbole.com/89140/ ）等技巧。

因為上述原因，有些業務就拋棄了 RDBMS，直接上 NoSQL，常見的選型方案是：HBase，MongoDB， Cassandra 等，簡單介紹一下：

HBase 來自 Google 的 Big Table 的論文，底層存儲依賴 HDFS 來實現擴展性，通過對 Key 進行 Range 化、列式存儲（多 Region ）的管理，使整個集群達到比較高的隨機讀寫性能（吞吐），比較適用于海量小 Key/Value 讀寫業務，強一致性，支持多版本，支持 Table 和半結構化的數據存儲。但是缺點是并不支持復雜查詢，同時并沒有支持跨行事務。我認為 HBase 是一個 CP 的系統。沒有官方的 SQL 支持，有一些第三方的公司做了 SQL on HBase （比如 Phoenix）但是大多都用于 OLAP 領域，面向 OLTP 的不多。

Cassandra 來自 Dynamo 的模型，比較大的特點是，C* 可以根據業務的需求進行決定它是 CP 還是 AP（最終一致性），C* 采用的 WRN 模型，當 W + R > N 的時候是 CP 系統，W+R <= N 時是 AP 系統，但是擁有最終一致性，其中 W 代表寫入幾個節點算成功，R 表示讀幾個節點算成功，N 是可寫入多少節點。C* 2.0+ 支持了 CAS 算是支持了單行事務。C* 的讀寫性能略優于 HBase（http://www.planetcassandra.org/nosql-performance-benchmarks/）但是我認為吧，在分布式系統中的單機 benchmark 其實意義不大，因為系統都是可以水平擴展的，能滿足需求即可。

MongoDB Cluster 網上吐槽的非常多，個人不太熟悉，就不評論了。

以上 NoSQL 的問題是，接口表達力相比 SQL 而言差了很多，對于很多現有業務來說，從 RDBMS 重構至 NoSQL 基本無異于重寫。所以問題就來了，我們能不能既享受 NoSQL 帶來的擴展能力，同時又不丟失像單機一樣的事務能力，并且還能使用 SQL？

在仔細思考過這個問題后，其實并非不可能，而且實際上，有很多公司都已經嘗試過造出了這類稱為 NewSQL 的產品，比如 Google 的 Spanner 和 F1 (http://research.google.com/pubs/pub41344.html )，被 Apple 收購的 FoundationDB， 近年出現的 CockroachDB，TiDB 等，都是主打提供 SQL 及分布式事務的數據庫產品。

這類數據庫的模型都比較統一：即在下層提供一個支持事務的分布式 KV 層，上層構造 SQL Layer，將 SQL 語句翻譯成 KV 的事務操作，進而實現在分布式存儲上的帶事務的 SQL 的支持。實際上單機數據庫的模型也在往這個方向上靠，比如 sqlite4, MySQL。

我們接下來從上到下，以 TiDB 為例看看如何實現一個分布式數據庫，先上架構圖

由于篇幅原因，以下主要說說 SQL Layer 和 KV。

1. SQL Layer

寫一個 SQL Layer 第一步考慮的是 Lexer 和 Parser ，做詞法和語法解析，生成語法樹。值得一提的是，整個 TiDB是用純 Go 開發的，在 Go 的世界里，官方是推薦使用 yacc 來進行語言應用的開發，Go 官方也提供了 yacc 的工具。至于 yacc 的語法在這里就不提了，我們使用了一個開源的 Parser 生成器， cznic/goyacc 和 cznic/ebnf2y (打個廣告： http://github.com/cznic 這個歪國朋友做了很多 go 來開發語言應用的工具，同時還是一個 go 的嵌入式數據庫 ql 的作者，目前也在給 TiDB 貢獻 Parser 部分的代碼) 。

其中 ebnf2y 是一個 EBNF to Yacc 的轉換工具，可以通過 EBNF（主要是 EBNF 比較好寫 :D ） 生成一個 Go 版本的 yacc 文件。然后用這個 yacc 文件通過 goyacc 生成 Paser 的 Go 代碼。詞法分析器是通過 cznic/golex 工具生成的。詳細的例子可以參考 TiDB 根目錄下的 parser 文件夾和 Makefile，有完整的實現。

TiDB 是支持大部分常用的 MySQL 語法的（CRUD, JOIN，GROUP BY...）Anyway 雖然比較苦逼，這步算是基本完成了，現在 TiDB 應該擁有 Go 的項目中最完整的 MySQL yacc/lex 文法實現，可以生成語法樹。而且相對獨立，如果有朋友對類 SQL 的語法感興趣，想實現一個小數據庫的話，可以參考一下 :)

運行時通過 Parser 編譯 SQL 語句拿到 AST（抽象語法樹）后，下一步是生成查詢計劃，會根據不同的語句類型，生成執行計劃 Plan。值得注意的是，Plan 并不是的一個孤立的東西，多個 Plan 其實是可以疊加執行的。形成一個 Plan Tree。

例如一個最簡單的例子： SELECT * FROM t WHERE id > 0；

通過 Parser 會生成一個 SelectStmt 對象，它的 Plan 是 ：第一步會從AST 結構的 From 成員中生成一個 TableDefaultPlan(t)（默認掃全表，從頭到尾）。然后從 Where 子句中構造出 Plan 的時候會將上一步生成的 TableDefaultPlan 作為參數傳入, 然后根據 Where 的表達式來決定到底是不是轉換成 IndexPlan（使用索引掃表）或者是直接生成一個 FilterDefaultPlan（在上一個 Plan 的執行過程中上疊加一個 Filter 操作）。簡單來說，Plan 就是根據語句的語法元素來決定應該如何對數據集進行掃描，生成結果集的一系列方法。

在傳統的數據庫中，生成好 Plan Tree 以后，會進行執行計劃的優化，有很多查詢優化的理論就不一一細說了，目前 TiDB 并沒有太多的查詢優化（但是最基本的索引識別還是有的），目前的理論多是針對單機的數據庫的查詢優化，但是在分布式系統中如何進行優化，是一個有待探討的課題，我們未來也會在這方面進行一些嘗試。

這里就不細說了，這個話題展開能寫一本書。。。實際上我們也確實準備寫本書，而且 REPO 也建立了，見 https://github.com/ngaut/builddatabase

到這一步為止還是停留在比較正統的 SQL Layer 的實現階段，下面我們介紹事務 KV 引擎，這部分是實現整個系統的核心。

2. 分布式事務

當你有一個支持跨行事務的 kv 層時，在上層構建 SQL 引擎就會方便很多。但是就像上文提到的目前的 NoSQL 很少有能支持這個的，但是也不是沒法搞，而且基本上就只有一種辦法，2PC（二階段提交），或者性能更差的 3PC， 很多算法都是在 2PC 上進行的優化。

簡單提一下 2PC，在事務開始的時候，協調者第一階段會將要修改的內容發給各個事務的參與者，參與者將事務內容寫入本地 WAL 后回復OK給協調者，當協調者收到所有的參與者回復后，協調者再次向所有參與者發送 Commit（或者 Abort） 指令，并在事務狀態表里標記該事務為成功（失敗）。

在 2PC 中我們還是可以看到幾個不太協調的東西，一個協調者的選取，另一個是事務狀態表的一致性如何保證，還有就是如何實現事務的隔離性。

先說協調者的問題，在傳統的 2PC 中，為了實現分布式事務的一致性（先提交的事務的結果，需要被后發起的事務看到），當有多個協調者的時候，如何實現事務的時序呢？單協調者肯定不能忍受，在這點上 Google 有很多嘗試，比如在 Percolator 中采用中心授時服務器（不會是單點，應該是一個 Paxos Group），在 Spanner 中使用高度同步的原子鐘，就是為了解決標記事務的先后。

事務狀態表，這個是用來查詢已成功事務的，在第二階段的 Commit 過程中，理論上協調者是不需要收到所有參與者的返回的，因為收到第一階段所有參與者的成功返回后（寫入 WAL），就可以標記事務成功，如果第二階段有人掛了，當它恢復的時候，第一步會去事務狀態表中詢問這個事務是否已經被標記成功，如果成功的話，就寫入本地庫，如果不成功的話，就丟棄 WAL。這個狀態表修改是不需要跨行事務的，所以使用傳統的做法，sharding 或者按照 range 存儲即可，但是考慮到這個表的讀請求可能會比較大（因為新開始事務需要知道當前最新的事務號，以支持 MVCC），可以通過 Paxos 做多副本。

接下來說到事務的隔離性，在我們的系統中，提供 SI 和 SI+ 樂觀鎖 兩個級別，對應到 MySQL 里面SI+ 樂觀鎖 可以理解為 select for update 語句，但行為略有不同。所以，我們需要實現 MVCC，上一段中我們已經知道每個事務都會對應一個事務編號，而且這個事務編號是全局有序的。

當我開始新事務 y 的時候，我需要得知我當前的最新已提交事務號 x，然后在我的 y 事務中看到的整個數據庫的視圖都是這個事務 x 完成后的狀態（即使在 y 開始后，有其他的事務 x' 提交，y 是看不到 x' 的內容的）。

實現這一點并不困難，底層存儲引擎支持的話，比如 LevelDB 內部就已經實現了（參考 Snapshot 實現），LMDB 也是一個在 MVCC-BTree 的實現。TiDB 的可插拔的存儲引擎設計可以很方便的實現。比較 tricky 的是沖突的解決策略，在實際的場景中，比如剛才 y 事務開始后，x' 修改了 y 事務中修改的某個行 r，因為有 SI 此時 y 事務是不知道 r 已經被修改擁有更新的版本號，此時比較合理的做法是讓 y 事務回滾，然后重試，在 TiDB 中也是這么做的。

TiDB 做了接口的嚴格分層，將 KV 存儲的接口和 SQL Layer 分離得比較徹底，目前本地的存儲引擎 (LevelDB, RocksDB, LMDB, BoltDB) 都已經支持，分布式引擎目前第一階段打算采用了 HBase + Coprocessor 來實現，分布式事務模型采用 Google 的 Percolator 模型，近期將會開源。

下面我們從TIDB的代碼層面看看一些更細節的實現。

首先是執行方法：

// 代碼去掉錯誤處理以及和原理無關的代碼

func (s *session) Execute(sql string) ([]rset.Recordset, error) {

statements, err := Compile(sql) // 編譯 SQL 語句

var rs []rset.Recordset

for _, st := range statements {

r := runStmt(s, st) // 執行語句

rs = append(rs, r)

}

return rs, nil

}

明顯可以看到代碼分為編譯和執行兩個步驟，相信很多同學再一次想起大學的編譯原理課程了吧 ：）

我們再來看看編譯過程，也可以看到明確的兩個步驟，詞法分析和語法分析

// Compile is safe for concurrent use by multiple goroutines.

func Compile(src string) ([]stmt.Statement, error) {

l := parser.NewLexer(src) // 生成一個詞法分析器

if parser.YYParse(l) != 0 { // 語法分析，得到語法樹

return nil, errors.Trace(l.Errors()[0])

}

return l.Stmts(), nil

}

看看最后生成的語法樹長什么樣子：

// SelectStmt is a statement to retrieve rows selected from one or more tables.

// See: https://dev.mysql.com/doc/refman/5.7/en/select.html

type SelectStmt struct {

Distinct bool

Fields []*field.Field

From *rsets.JoinRset

GroupBy *rsets.GroupByRset

Having *rsets.HavingRset

Limit *rsets.LimitRset

Offset *rsets.OffsetRset

OrderBy *rsets.OrderByRset

Where *rsets.WhereRset

// select for update

Lock coldef.LockType

Text string

}

接下來我們以查詢為例再來看下，select語句構造邏輯大概是這樣的：

// The whole phase for select is

// `from -> where -> lock -> group by -> having -> select fields -> distinct -> order by -> limit -> final`

func (s *SelectStmt) Plan(ctx context.Context) (plan.Plan, error) {

var (

r plan.Plan

err error

)

if s.From != nil {

r, err = s.From.Plan(ctx)

}

if w := s.Where; w != nil {

r = rsets.WhereRset{Expr: w.Expr, Src: r}).Plan(ctx)

}

// Get select list for futher field values evaluation.

// select * from table; 將 * 轉化為具體的field

selectList, err := plans.ResolveSelectList(s.Fields, r.GetFields())

switch {

case !rsets.HasAggFields(selectList.Fields) && s.GroupBy == nil:

// If no group by and no aggregate functions, we will use SelectFieldsPlan.

r = (&rsets.SelectFieldsRset{Src: r, SelectList: selectList}).Plan(ctx)

default:

r = (&rsets.GroupByRset{By: groupBy, Src: r, SelectList: selectList}).Plan(ctx)

}

if s := s.Having; s != nil {

r = rsets.HavingRset{

Src: r,

Expr: s.Expr}).Plan(ctx)

}

if s.Distinct {

r= rsets.DistinctRset{Src: r,

SelectList: selectList}).Plan(ctx)

}

if s := s.OrderBy; s != nil {

rsets.OrderByRset{By: s.By,

Src: r,

SelectList: selectList}).Plan(ctx)

}

if s := s.Offset; s != nil {

rsets.OffsetRset{Count: s.Count, Src: r}).Plan(ctx)

}

if s := s.Limit; s != nil {

rsets.LimitRset{Count: s.Count, Src: r}).Plan(ctx)

}

rsets.SelectFinalRset{Src: r,

SelectList: selectList}).Plan(ctx)

return r, nil

}

有興趣的同學可以看下具體的代碼，這里我們就先不介紹了，我們繼續：）

SQL層如何映射到KV層

最終所有的操作都會映射到 KV 層，我們來看一個簡單的例子，假設有一個 user 表：

RowID (隱藏列）	uid	name	email
1	xx	bob	bob@gmail.com

如果支持 select uid, name, email from user; 最終會變成哪些 KV 操作呢？ 在 TiDB 里面，所有的表都有一個唯一的ID， 所有的列也都有唯一的ID，假設 user 表的 ID 為1， uid 的 ID 為2，name的 ID 為3， email的 ID 為 4。那么最后存儲在 KV 層的大概是這樣的：

整個key的邏輯結構：

TableID : RowID : ColumnID

一個具體的例子

Key Value

1 : 1 : 1 nil

1 : 1 : 2 xx

1 : 1 : 3 bob

1 : 1 : 4 bob@email.com

第一個1是表的 ID， 第二個是RowID， 第三個是列的 ID，冒號表示分隔符

上面的SQL語句最終會被映射成指令：

uid := kv.Get( “ 1 : 1 : 2 ” )

name := kv.Get( “ 1 : 1 : 3 " )

email := kv.Get( “ 1 : 1 : 4 " )

其它語句類似，會被翻譯成相應的 Put 和 Delete 操作，詳細的請參考 TiDB 源碼。

下面我們聊聊 TiDB 的索引實現

還是以上面的表為例，在name上面建立唯一索引，最后存儲的索引KV大概是這樣的(idx表示index)：

Key Value

1 : Idx : 3 : bob 1

這里的Value就是實際上的RowID

這樣如果遇到語句 select email from user where name = ‘bob’; 的時候就會自動通過索引來找到 RowID，然后通過 RowID 做一次 kv.Get 操作就能拿到。

類似的，非唯一索引可以通過添加一個RowID的后綴到 key 后面，假設系統里面有兩個 bob， 那么實際存儲格式大概是這樣的：

Key Value

1 : Idx : 3 : bob : 1 1

1 : Idx : 3 : bob : 2 2

實際的代碼做了適當的優化，這里只是為了便于理解。

聊到這里，是不是大家對如何實現多引擎支持都比較好奇呢？我們繼續看看這個：）

默認 TiDB 單機模式使用 Goleveldb 和 BoltDB 作為存儲引擎和測試引擎，因為這兩個都是純go實現，沒有依賴，但性能都不好 :(

我們來看看 Transaction的接口，從這個接口也能看出對底層存儲引擎的要求

// Transaction defines the interface for operations inside a Transaction.

type Transaction interface {

// Get gets the value for key k from KV store.

Get(k Key) ([]byte, error)

// Set sets the value for key k as v into KV store.

Set(k Key, v []byte) error

// Seek searches for the entry with key k in KV store.

Seek(k Key, fnKeyCmp func(key Key) bool) (Iterator, error)

// Deletes removes the entry for key k from KV store.

Delete(k Key) error

// Commit commites the transaction operations to KV store.

Commit() error

// Rollback undoes the transaction operations to KV store.

Rollback() error

}

由于需要 seek，所以底層的存儲引擎的 KV 必須是有序的，能夠 scan。對于一個事務內的所有寫操作都是先 buffer 住，最后 commit 時才提交，所以對單機的 KV 引擎來講，支持 Batch 寫入的原子操作即可，即使不支持也可以通過 lock 的方式來搞定。同時由于合理的抽象， TiDB 能夠輕松支持多個存儲引擎。TiDB 自然也可以作為一個很好的 bench 工具， 大家可以用來bench 各種存儲引擎了 ：）

為了便于大家理解，或者想給TiDB添加新的引擎支持，我們寫了 lmdb 的引擎的例子，只用了大約200行代碼，見 https://github.com/pingcap/tidb-lmdb

開源的心得

下面想和大家聊一下怎么做開源，算是這幾個月來的小小的感悟吧。

關于如何做開源，在中國鮮有認真做開源項目的商業公司，這和整個浮躁的大環境是分不開的，很多國內的開源項目基本就只是 Push 代碼到 Github 上而已，有的甚至就再也不更新了。我個人認為優秀的開源項目是社區和商業公司支持缺一不可的，特別是基礎軟件領域。

TiDB 的目標是做一個全球性的開源項目，所以我們非常刻意的去營造社區的氛圍，比如我們選擇一個比較早期的版本的時間點開源，早期一些比較容易修改和上手的 Bug 會可以留下來，吸引社區的愛好者來修改。Github 已經搭建了一個非常好的代碼協作平臺，我們不管是公司內部的私有項目還是外部的開源項目，都是完全通過 Github 協作的（有機會我可以講講我們 PingCAP 的工作流）

btw，提交的 patch 被合并到主干后，我們都會給這個 contributor 郵寄一件我們的 t-shirt :)

另外提交 PR 也需要相應的標準和格式，TiDB 的標準見 https://github.com/pingcap/tidb/blob/master/docs/CONTRIBUTING.md

對于TiDB而言，通過

https://github.com/pingcap/tidb/issues/158

參與項目是最好的切入點，由于MySQL有大量 builtin 的函數，目前TiDB只實現了一部分。

比較值得注意的是，文檔，README 和 Issues 及討論必須需要英文書寫，否則很難吸引外國的社區貢獻，這個也是大多數國內開源項目通病。

TiDB 的計劃是：

1. 繼續完善 SQL 層，更完整的兼容 MySQL 語法。

2. 實現異步 Schema 變更，在分布式系統中，DDL 是不容許阻塞的，這個算法比較巧妙，可以參考 Google 的一篇論文（http://research.google.com/pubs/pub41376.html）

3. 繼續開發 HBase 的引擎，第一個可以在生產環境中使用的版本應該是搭載 HBase 引擎的

4. 更長期的計劃是去掉 HBase，構建自己的 Kv 層，畢竟 HBase 并不是為 SQL 優化的 Kv，而且在依賴太重，我個人不太喜歡 Hadoop，非常難容器化。

5. 多租戶

6. 容器化

由于時間關系，我們今天的分享就先到這里了，感謝大家的支持：）

以后有機會，我們再聊聊下面的東西：

HBase的分布式事務實現，以及TiDB如何讓HBase擁有SQL能力

MySQL協議支持，更重要的哲學問題是為什么選擇支持MySQL協議

如何在KV的引擎上實現行鎖

隔離級別的選擇，select for update語句的特殊處理

如何用HLC實現去中心化的事務管理

在線異步動態schema變更

Q&A

1 事務狀態表如何解決單點問題

多副本，比如通過Paxos或者Raft等一致性協議

2. TiDB和MySQL的區別是什么？能不能編譯到一起Go應用里面

可以把 TiDB 理解成一個無比強大的分布式 MySQL, MySQL 自身主要是單機的。

可以和Go應用編譯到一起：）

3. TiDB目前的roadmap是什么？什么時候可以應用于產品中，后期API會不會改變很多？

TiDB 的計劃是：

1. 繼續完善 SQL 層，更完整的兼容 MySQL 語法。

2. 實現異步 Schema 變更，在分布式系統中，DDL 是不容許阻塞的，這個算法比較巧妙，可以參考 Google 的一篇論文（http://research.google.com/pubs/pub41376.html）

3. 繼續開發 HBase 的引擎，第一個可以在生產環境中使用的版本應該是搭載 HBase 引擎的

4. 更長期的計劃是去掉 HBase，構建自己的 Kv 層，畢竟 HBase 并不是為 SQL 優化的 Kv，而且在依賴太重，我個人不太喜歡 Hadoop，非常難容器化。

5. 多租戶

6. 容器化

我們目前主要兼容 MySQL 協議，所以接口比較穩定，直接使用 MySQL 客戶端就可以，現在我們已經支持了各種ORM，比如Beego， Xorm等等。

4 分布式事務目前是否只支持hbase

是的，暫時是的

5. Why choose golang to build a database?

Golang的開發和運行效率都很理想，Go語言官方有很好的規范，統一的風格和標準，我們都很喜歡它：）

6. 請問事務更新沖突為什么不采用行級鎖？其他被回滾的事務如果在被發現沖突前已經結束怎么處理？

TiDB 采用了行鎖，上面也提到，由于時間關系，沒有來得及詳細講，后面的問題沒看明白，請詳細描述下：）

7.分布式kv如何做到任意擴展？

Sharding, split, merge

8. 如采用raft之類做事務狀態表，對吞吐量有多大影響？

事務狀態表也可以分配一個key，讓狀態合理散落到整個分布式系統里面，不存在性能瓶頸

9. 是否對比過如mysql ndb cluster，相對這類實現有哪些優缺點？

MySQL上面的cluster由于局限于MySQL本身，在分布式上面受到的約束很多，類似PG的xc，好多年都很難有突破性的進展，這方面其它的分布式數據庫基本都選擇了一開始就朝著分布式去做設計，優缺點見上面的 roadmap， 里面很多東西基于MySQL的方案都很難搞定

10. "事務狀態表，這個是用來查詢已成功事務的，在第二階段的 Commit 過程中，理論上協調者是不需要收到所有參與者的返回的，因為收到第一階段所有參與者的成功返回后（寫入 WAL），就可以標記事務成功，如果第二階段有人掛了，當它恢復的時候，第一步會去事務狀態表中詢問這個事務是否已經被標記成功，如果成功的話，就寫入本地庫，如果不成功的話，就丟棄 WAL。"——這個能否再說明一下，既然第二階段有人掛了，為什么去查詢第一階段為成功以后，還是繼續寫入本地？

由于多副本存在，而且前面已經有了wal，所以其它副本會接替掛了的，繼續apply wal就行

11. 抽象語法樹這塊是不是類似web中的路由樹的構建？

這個有點像，又不太像，抽象語法樹一般用于編譯領域比較多

12. NuoDB對比F1 TiDB 如何？

NuoDB不太清楚，也沒怎么見到用戶使用，TiDB 基本上是朝著F1作為目標去的，F1是Google出品目前全球最好的分布式OLTP數據庫.

來自：http://mp.weixin.qq.com/s?__biz=MjM5OTcxMzE0MQ%3D%3D