上一篇說到了Google Spanner--全球級分布式數(shù)據(jù)庫,但我覺得Spanner不能稱作NewSQL,因為Spanner雖然有外部一致性、類SQL接口和常見事務(wù)支持,但和傳統(tǒng)關(guān)系型數(shù)據(jù)庫相比功能仍不夠豐富,對此,Google在Spanner上開發(fā)了F1,擴展了Spanner已有特性成為名副其實的NewSQL數(shù)據(jù)庫;F1目前支撐著谷歌的AdWords核心業(yè)務(wù)皿哨。

簡介
AdWords業(yè)務(wù)本來使用MySQL+手工Sharding來支撐,但在擴展和可靠性上不能滿足要求,加上Spanner已經(jīng)在同步復(fù)制睁壁、外部一致性等方面做的很好,AdWords團隊就在Spanner上層開發(fā)了混合型數(shù)據(jù)庫F1(F1意味著:Filial 1 hybrid,混合著關(guān)系數(shù)據(jù)的豐富特性和NoSQL的擴展性),并于2012年在生產(chǎn)環(huán)境下替代MySQL支撐著AdWords業(yè)務(wù)(注意：F1和Spanner之間關(guān)系并不是MariaDB基于MySQL再開發(fā)的關(guān)系,而是類似InnoDB存儲引擎和MySQL Server層的關(guān)系--F1本身不存儲數(shù)據(jù),數(shù)據(jù)都放在Spanner上)。

F1設(shè)計目標
1.可擴展性:F1的用戶經(jīng)常有復(fù)雜查詢和join,F1提供了增加機器就能自動resharding和負載均衡。
2.高可用性:由于支撐著核心業(yè)務(wù),分分鐘都是money,不能因為任何事故(數(shù)據(jù)中心損壞、例行維護、變更schema等)而出現(xiàn)不可用狀況暗甥。
3.事務(wù):Spanner的外部一致性的是不夠的,標準ACID必須支持。
4.易用性:友好的SQL接口捉捅、索引支持撤防、即席查詢等特性能大大提高開發(fā)人員的效率。

F1規(guī)模
截止這篇論文發(fā)表之時(2013年)F1支撐著100個應(yīng)用,數(shù)據(jù)量大概100TB,每秒處理成百上千的請求,每天掃描數(shù)十萬億行記錄,和以前MySQL相比,延遲還沒增加;在這樣規(guī)模下,可用性竟達到了驚人的99.999%!

F1架構(gòu)總覽

使用F1的用戶通過client library來連接,請求再負載均衡到一個F1節(jié)點,F1再從遠Spanner讀寫數(shù)據(jù),最底層是分布式文件系統(tǒng)Colossus.負載均衡器會優(yōu)先把請求連到就近的數(shù)據(jù)中心里的F1,除非這數(shù)據(jù)中心不可用或高負載.通常F1和對應(yīng)Spanner都在同一個數(shù)據(jù)中心里,這樣能加快訪問Spanner的速度,假如同處的Spanner不可用,F1還能訪問遠程的Spanner,因為Spanner是同步復(fù)制的嘛,隨便訪問哪個都行棒口。
大部分的F1是無狀態(tài)的,意味著一個客戶端可以發(fā)送不同請求到不同F(xiàn)1 server,只有一種狀況例外:客戶端的事務(wù)使用了悲觀鎖,這樣就不能分散請求了,只能在這臺F1 server處理剩余的事務(wù)寄月。
你可能會問上圖的F1 Master和Slave Pool干嘛的?它們其實是并行計算用的,當query planner發(fā)現(xiàn)一個SQL可以并行加速執(zhí)行的話,就會將一個SQL分拆好多并行執(zhí)行單位交到slave pool里去執(zhí)行,F1 Master就是監(jiān)控slave pool健康情況和剩余可用slave數(shù)目的.除了SQL,MapReduce任務(wù)也可用F1來分布式執(zhí)行辜膝。

F1數(shù)據(jù)模型
F1的數(shù)據(jù)模型和Spanner很像--早期Spanner的數(shù)據(jù)模型很像Bigtable,但后來Spanner還是采用了F1的數(shù)據(jù)模型.
邏輯層面上,F1有個和RDBMS很像的關(guān)系型schema,額外多了表之間層級性和支持Protocol Buffer這種數(shù)據(jù)類型.那表之間層級性怎么理解呢?其實就是子表的主鍵一部分必須引用父表,譬如:表Customer有主鍵(CustomerId)，它的子表Campaign的主鍵必須也包含(CustomerId),就變成這種形式(CustomerId, CampaignId);以此可推假如Campaign也有子表AdGroup,則AdGroup的主鍵必須這種形式--(CustomerId,CampaignId, AdGroupId).最外面父表Customer的主鍵CustomerId就叫一個root row,所有引用這個root row的子表相關(guān)row組成了Spanner里的directory(這個解釋比Spanner那篇論文反而清楚,囧),下圖比較了RDBMS和F1漾肮、Spanner的層級結(jié)構(gòu)區(qū)別:

Protocol Buffer
不要聽名字感覺Protocol Buffer是個緩存什么之類的,其實Protocal Buffer是個數(shù)據(jù)類型,就像XML、Json之類,一個數(shù)據(jù)類型而已;因為在谷歌內(nèi)部的廣泛使用,所以F1也支持它,但是是當做blob來對待的.Protocol Buffer語義簡單自然,還支持重復(fù)使用字段來提高性能(免得建子表)初橘。

索引
所有索引在F1里都是單獨用個表存起來的,而且都為復(fù)合索引,因為除了被索引字段,被索引表的主鍵也必須一并包含.除了對常見數(shù)據(jù)類型的字段索引,也支持對Buffer Protocol里的字段進行索引.
索引分兩種類型:
Local:包含root row主鍵的索引為local索引,因為索引和root row在同一個directory里;同時,這些索引文件也和被索引row放在同一個spanserver里,所以索引更新的效率會比較高.
global:同理可推global索引不包含root row,也不和被索引row在同一個spanserver里.這種索引一般被shard在多個spanserver上;當有事務(wù)需要更新一行數(shù)據(jù)時,因為索引的分布式,必須要2PC了.當需要更新很多行時,就是個災(zāi)難了,每插入一行都需要更新可能分布在多臺機器上的索引,開銷很大;所以建議插入行數(shù)少量多次.

無阻塞schema變更
考慮F1的全球分布式,要想無阻塞變更schema幾乎是mission impossible,不阻塞那就只好異步變更schema,但又有schema不一致問題(譬如某一時刻數(shù)據(jù)中心A是schema1,而數(shù)據(jù)中心B是對應(yīng)確是schema2),聰明的谷歌工程師想出了不破壞一致性的異步變更算法,詳情請參見--Online, Asynchronous Schema Change in F1

ACID事務(wù)
像BigTable的這樣最終一致性數(shù)據(jù)庫,給開發(fā)人員帶來無休止的折磨--數(shù)據(jù)庫層面的一致性缺失必然導致上層應(yīng)用使用額外的代碼來檢測數(shù)據(jù)一致性;所以F1提供了數(shù)據(jù)庫層面的事務(wù)一致性,F1支持三種事務(wù):
1.快照事務(wù):就是只讀事務(wù),得益于Spanner的全局timestamp,只要提供時間戳,就能從本地或遠程調(diào)用RPC取得對應(yīng)數(shù)據(jù).
2.悲觀事務(wù):這個和Spanner的標準事務(wù)支持是一樣的,參見Google NewSQL之Spanner.
3.樂觀事務(wù):分為兩階段:第一階段是讀,無鎖,可持續(xù)任意長時間;第二階段是寫,持續(xù)很短.但在寫階段可能會有row記錄值沖突（可能多個事務(wù)會寫同一行）,為此,每行都有個隱藏的lock列,包含最后修改的timestamp.任何事務(wù)只要commit,都會更新這個lock列,發(fā)出請求的客戶端收集這些timestamp并發(fā)送給F1 Server,一旦F1 Server發(fā)現(xiàn)更新的timestamp與自己事務(wù)沖突,就會中斷本身的事務(wù).
可以看出樂觀事務(wù)的無鎖讀和短暫寫很有優(yōu)勢:
1.即使一個客戶端運行長時間事務(wù)也不會阻塞其他客戶端.
2.有些需要交互性輸入的事務(wù)可能會運行很長時間,但在樂觀事務(wù)下能長時間運行而不被超時機制中斷.
3.一個悲觀事務(wù)一旦失敗重新開始也需要上層業(yè)務(wù)邏輯重新處理,而樂觀事務(wù)自包含的--即使失敗了重來一次對客戶端也是透明的.
4.樂觀事務(wù)的狀態(tài)值都在client端,即使F1 Server處理事務(wù)失敗了,client也能很好轉(zhuǎn)移到另一臺F1 Server繼續(xù)運行.
但樂觀事務(wù)也是有缺點的,譬如幻讀和低吞吐率.

靈活的鎖顆粒度
F1默認使用行級鎖,且只會鎖這行的一個默認列;但客戶端也能顯示制定鎖其他欄;值得注意的是F1支持層級鎖,即:鎖定父表的幾列,這樣子表的對應(yīng)列也會相應(yīng)鎖上,這種層級鎖能避免幻讀.

變更歷史記錄
早前AdWords還使用MySQL那會,他們自己寫java程序來記錄數(shù)據(jù)庫的變更歷史,但卻不總是能記錄下來:譬如一些Python腳本或手工SQL的改變.但在F1里,每個事務(wù)的變更都會用Protocol Buffer記錄下來,包含變更前后的列值、對應(yīng)主鍵和事務(wù)提交的時間戳,root表下會產(chǎn)生單獨的ChangeBatch子表存放這些子表;當一個事物變更多個root表,還是在每個root表下子表寫入對應(yīng)變更值,只是多了一些連接到其他root表的指針,以表明是在同一個事務(wù)里的.由于ChangeBatch表的記錄是按事務(wù)提交時間戳順序來存放,所以很方便之后用SQL查看.
記錄數(shù)據(jù)庫的變更操作有什么用呢?谷歌廣告業(yè)務(wù)有個批準系統(tǒng),用于批準新進來的廣告;這樣當指定的root row發(fā)生改變,根據(jù)改變時間戳值,批準系統(tǒng)就能受到要批準的新廣告了.同樣,頁面展示要實時顯示最新內(nèi)容,傳統(tǒng)方法是抓取所有需要展示內(nèi)容再和當前頁面展示內(nèi)容對比,有了ChangeBatch表,變化的內(nèi)容和時間一目了然,只要替換需要改變的部分就行了.

F1客戶端
F1客戶端是通過ORM來與F1 Server打交道了,以前的基于MySQL實現(xiàn)的ORM有些常見缺點:
1.對開發(fā)人員隱藏數(shù)據(jù)庫層面的執(zhí)行
2.循環(huán)操作效率的低下--譬如for循環(huán)這種是每迭代一次就一個SQL
3.增加額外的操作(譬如不必要的join)
對此,谷歌重新設(shè)計了個新ORM層,這個新ORM不會增加join或者其他操作,對相關(guān)object的負載情況也是直接顯示出來,同時還將并行和異步API直接提供開發(fā)人員調(diào)用.這樣似乎開發(fā)人員要寫更多復(fù)雜的代碼,但帶來整體效率的提升,還是值得的.
F1提供NoSQL和SQL兩種接口,不但支持OLTP還支持OLAP;當兩表Join時,數(shù)據(jù)源可以不同,譬如存儲在Spanner上表可以和BigTable乃至CSV文件做join操作.

分布式SQL
既然號稱NewSQL,不支持分布式SQL怎么行呢.F1支持集中式SQL執(zhí)行或分布式SQL執(zhí)行,集中式顧名思義就是在一個F1 Server節(jié)點上執(zhí)行,常用于短小的OLTP處理,分布式SQL一般適用OLAP查詢,需要用到F1 slave pool.因為的OLAP特性,一般快照事務(wù)就ok了.
請看如下SQL例子:
SELECT agcr.CampaignId, click.Region,cr.Language, SUM(click.Clicks)FROM AdClick clickJOIN AdGroupCreative agcrUSING (AdGroupId, CreativeId)JOIN Creative crUSING (CustomerId, CreativeId)WHERE click.Date ='2013-03-23'GROUP BY agcr.CampaignId, click.Region,cr.Language

可能的執(zhí)行計劃如下:

上圖只是一個最可能的執(zhí)行計劃,其實一個SQL通常都會產(chǎn)生數(shù)十個更小的執(zhí)行單位,每個單位使用有向無閉環(huán)圖((DAG)來表示并合并到最頂端;你可能也發(fā)現(xiàn)了在上圖中都是hash partition而沒有range partition這種方式,因為F1為使partition更加高效所以時刻動態(tài)調(diào)整partition,而range partition需要相關(guān)統(tǒng)計才好partition,所以未被采用.同時partition是很隨機的,并經(jīng)常調(diào)整,所以也未被均勻分配到每個spanserver,但partition數(shù)目也足夠多了.repartition一般會占用大量帶寬,但得益于交換機等網(wǎng)絡(luò)設(shè)備這幾年高速發(fā)展,帶寬已經(jīng)不是問題了.除了join是hash方式,聚集也通過hash來分布式--在單個節(jié)點上通過hash分配一小段任務(wù)在內(nèi)存中執(zhí)行,再最后匯總.
可能受到H-Store的影響,F1的運算都在內(nèi)存中執(zhí)行,再加上管道的運用,沒有中間數(shù)據(jù)會存放在磁盤上,這樣在內(nèi)存中的運算就是脫韁的馬--速度飛快;但缺點也是所有內(nèi)存數(shù)據(jù)庫都有的--一個節(jié)點掛就會導致整個SQL失敗要重新再來.F1的實際運行經(jīng)驗表明執(zhí)行時間不遠超過1小時的SQL一般足夠穩(wěn)定.
前面已經(jīng)說過,F1本身不存儲數(shù)據(jù),由Spanner遠程提供給它,所以網(wǎng)絡(luò)和磁盤就影響重大了;為了減少網(wǎng)絡(luò)延遲,F1使用批處理和管道技術(shù)--譬如當做一個等值join時,一次性在外表取50M或10w個記錄緩存在內(nèi)存里,再與內(nèi)表進行hash連接;而管道技術(shù)(或者叫流水線技術(shù))其實也是大部分數(shù)據(jù)庫使用的,沒必要等前一個結(jié)果全部出來再傳遞整個結(jié)果集給后一個操作,而是第一個運算出來多少就立刻傳遞給下個處理.對磁盤延遲,F1沒上死貴的SSD,仍然使用機械硬盤,而機械硬盤因為就一個磁頭并發(fā)訪問速度很慢,但谷歌就是谷歌,這世上除了磁盤供應(yīng)商恐怕沒其他廠商敢說對機械磁盤運用的比谷歌還牛--谷歌以很好的顆粒度分散數(shù)據(jù)存儲在CFS上,再加上良好的磁盤調(diào)度策略,使得并發(fā)訪問性能幾乎是線性增長的.

高效的層級表之間join
當兩個join的表是層級父子關(guān)系時,這時的join就非常高效了;請看下例:
SELECT * FROM Customer JOIN Campaign USING (CustomerId)
這這種類型的join,F1能一次性取出滿足條件的所有行,如下面這樣:

Customer(3)  
  Campaign(3,5)
  Campaign(3,6)
Customer(4)  
  Campaign(4,2)
  Campaign(4,4)

F1使用種類似merge join的cluster join算法來處理.
值得注意的是,一個父表即使包含多個子表,也只能與它的一個子表cluster join;假如兩個子表A和B要join呢,那得分成兩步走了:第一步就是上述的父表先和子表A做cluster join,第二步再將子表B也第一步的結(jié)果做join.

客戶端的并行
SQL并行化后大大加速處理速度,但也以驚人速度產(chǎn)生產(chǎn)生運算結(jié)果,這對最后的總匯聚節(jié)點和接受客戶端都是個大挑戰(zhàn).F1支持客戶端多進程并發(fā)接受數(shù)據(jù),每個進程都會收到自己的那部分結(jié)果,為避免多接受或少接受,會有一個endpoint標示.

Protocol Buffer的處理
Protocol Buffer既然在谷歌廣泛使用著,F1豈有不支持之理?其實Protocol Buffer在F1里是被當做一等公民優(yōu)先對待的,下面是個Protocol Buffer和普通數(shù)據(jù)混合查詢的例子:

SELECT c.CustomerId, c.Info  
FROM Customer AS c  
WHERE c.Info.country_code ='US'  

其中c是個表,c.Info是個Protocol Buffer數(shù)據(jù),F1不但支持將c.Info全部取出,而且也能單獨提取country_code這個字段; Protocol Buffer支持一種叫repeated fields的東東,可以看做是父表的子表,唯一區(qū)別是顯式創(chuàng)建子表也就顯式制定外鍵了,而repeated fields是默認含有外鍵;這么說還是太抽象,舉個例子:

SELECT c.CustomerId, f.feature  
FROM Customer AS c  
  PROTO JOIN c.Whitelist.feature AS f
WHERE f.status ='STATUS_ENABLED'  

c是個表,c.Whitelist是Protocol Buffer數(shù)據(jù),c.Whitelist.feature就是repeated fields了(當做c的子表);雖然看起來很奇怪c與它的Whitelist.feature做join,但把c.Whitelist.feature當做一個子表也就解釋的通了.
Protocol Buffer還可以在子查詢中使用,如下面例子:

SELECT c.CustomerId, c.Info,  
 (SELECT COUNT(*) FROM c.Whitelist.feature) nf
FROM Customer AS c  
WHERE EXISTS (SELECT * FROM c.Whitelist.feature f WHERE f.status !='ENABLED')  

Protocol Buffer雖然省了建子表的麻煩,卻帶來額外性能開銷:1.即使只需要取一小段,也要獲取整個Protocol Buffer,因為Protocol Buffer是被當做blob存儲的;2.取得數(shù)據(jù)要經(jīng)過解壓充岛、解析后才能用,這又是一筆不菲開銷.

在谷歌使用規(guī)模
F1和Spanner目前部署在美國的5個數(shù)據(jù)中心里支撐Adwords業(yè)務(wù),東西海岸各兩個,中間一個;直覺上感覺3個數(shù)據(jù)中心就已經(jīng)很高可用了,為什么谷歌要選擇5個呢?假如只部署在3個數(shù)據(jù)中心,一個掛了后剩余兩個必須不能掛,因為commit成功在Paxos協(xié)議里需要至少2節(jié)點;但如果第二個節(jié)點又掛了此時就真的無法訪問了,為了高可用,谷歌選擇了5個數(shù)據(jù)中心節(jié)點.
東海岸有個數(shù)據(jù)中心叫做preferred leader location,因為replica的Paxos leader優(yōu)先在這個數(shù)據(jù)中心里挑選.而在Paxos協(xié)議里,read和commit都要經(jīng)過leader,這就必須2個來回,所以客戶端和F1 Server最好都在leader location這里保檐，有助降低網(wǎng)絡(luò)延遲.

性能
F1的讀延遲通常在5_{10ms,事務(wù)提交延遲高些50}150ms,這些主要是網(wǎng)絡(luò)延遲;看起來是很高,但對于客戶端的總體延遲,也才200ms左右,和之前MySQL環(huán)境下不相上下,主要是新ORM避免了以前很多不必要的其他開銷.
有些非交互式應(yīng)用對延遲沒太高要求,這時就該優(yōu)化吞吐量了.盡量使用不跨directory的小事務(wù)有助于分散從而實現(xiàn)并行化,所以F1和Spanner的寫效率是很高的.其實不光寫效率高,查詢也很迅速,單條簡單查詢通常都能在10ms內(nèi)返回結(jié)果,而對于非常復(fù)雜的查詢,得益于更好的并發(fā)度,也通常比之前MySQL的時候快.
之前MySQL的查詢數(shù)據(jù)都是不壓縮存儲在磁盤上,磁盤是瓶頸,而在F1里數(shù)據(jù)都是壓縮的,雖然壓縮解壓過程帶來額外CPU消耗,但磁盤卻不在是瓶頸,CPU利用率也更高,以CPU換空間總體還是值得的.

結(jié)尾
可以看到F1完善了Spanner已有的一些分布式特性,成為了分布式的關(guān)系型數(shù)據(jù)庫,也即炒的火熱的NewSQL;但畢竟谷歌沒公布具體實現(xiàn)代碼,希望盡早有對應(yīng)開源產(chǎn)品面世可以實際把玩下.

參考資料
F1 - The Fault-Tolerant Distributed RDBMS Supporting Google's Ad Business
F1: A Distributed SQL Database That Scales