一個(gè)實(shí)習(xí)生小朋友騙我說(shuō)他不會(huì)，問(wèn)我這些題目怎么做。這明擺著換個(gè)法子來(lái)面試我呀！要是真啥都不會(huì)能來(lái)我司實(shí)習(xí)么？全是套路啊。不過(guò)原文出題還是很有水平的，所以我決定寫(xiě)一寫(xiě)。

1. 用cas實(shí)現(xiàn)spinlock.

spinlock在網(wǎng)上應(yīng)該一搜一大把，我試著給出一個(gè)simple甚至naive的實(shí)現(xiàn)。

若是較真的話可以看看這里。這個(gè)題的考點(diǎn)不在這里，問(wèn)無(wú)鎖實(shí)現(xiàn)，原子操作，ABA問(wèn)題這些底層方向思路就走偏了。其實(shí)多線程的并發(fā)安全，跟多個(gè)事務(wù)的并發(fā)安全，在某種程度上是共通的。 這才是考察的核心問(wèn)題，比如我做了一個(gè)kv引擎，只提供了get set 和cas操作，那么能否在這個(gè)基礎(chǔ)上，實(shí)現(xiàn)一個(gè)鎖操作的API？假設(shè)我們能實(shí)現(xiàn)出鎖操作，那我們又能否利用這個(gè)鎖，實(shí)現(xiàn)出跨多個(gè)key的修改操作的安全API？如何保證原子語(yǔ)義，要么全成功，要么全失敗。

事實(shí)上僅用cas這套搞出跨多key的修改是蠻蛋疼的，再細(xì)節(jié)到網(wǎng)絡(luò)失敗的時(shí)候鎖的釋放，深入思考下就會(huì)想到，因?yàn)榫W(wǎng)絡(luò)是有3態(tài)的：成功失敗和不可知。一般會(huì)基于快照做，只有cas的保證太弱了。

cas提供的原子性，這是一個(gè)很重要的點(diǎn)，假設(shè)在分布式的事務(wù)里面，跨分片的事務(wù)提供能否成功，只取決于一個(gè)primary key的提交是否能成功。這里有兩個(gè)問(wèn)題思考一下也挺有意思，第一，跨多機(jī)的時(shí)候，如何提供對(duì)某一個(gè)key的原子語(yǔ)義？第二，如果只有對(duì)一個(gè)key的原子保證，如果實(shí)現(xiàn)跨許多機(jī)器跨多個(gè)key-value的原子操作語(yǔ)義？

扯淡扯遠(yuǎn)了，我們看下一題吧。

2. 實(shí)現(xiàn)單機(jī)kv存儲(chǔ)系統(tǒng)， 多節(jié)點(diǎn)共享kv存儲(chǔ)服務(wù)， 怎么解決external consistency的問(wèn)題？

kv存儲(chǔ)N=0

用戶A和B操作kv存儲(chǔ)系統(tǒng)按照下面時(shí)序：

1.用戶A執(zhí)行操作： INC N;

2.用戶A通知用戶B執(zhí)行操作;

3.用戶B執(zhí)行操作： if （N % 2 == 0） {N*=2;} else {N +=3;}

怎么保證結(jié)果符合預(yù)期呢？ 在網(wǎng)絡(luò)傳輸影響操作到達(dá)次序的情況下， 怎么保證B后于A完成操作。

如果這個(gè)過(guò)程插入了C， 又如何做呢？

外部一致性我記得不是太清了（假裝一臉認(rèn)真），產(chǎn)生因果關(guān)系的操作之間，執(zhí)行順序滿足因的操作應(yīng)該先于果？有點(diǎn)像因果率一致？A操作引發(fā)了B，那么B一定應(yīng)該看得到A執(zhí)行產(chǎn)生的結(jié)果。這個(gè)例子里面因?yàn)檫@個(gè)因果關(guān)系，似乎是希望B看到的值應(yīng)該是N INC之后的值。

兩個(gè)操作都訪問(wèn)到了N，如果保證操作的安全？無(wú)非是，加鎖和MVCC。加鎖很好理解，讀寫(xiě)鎖，寫(xiě)寫(xiě)沖突，讀寫(xiě)沖突。那么該如何理解MVCC？MVCC其實(shí)很類似一個(gè)特殊的cas，它保證了涉及到跨多key修改的原子操作語(yǔ)義，這樣也可以理解為什么MVCC可以把并發(fā)粒度控制得更好。

這里是說(shuō)的單機(jī)存儲(chǔ)引擎，如果放到分布式里面會(huì)更復(fù)雜一點(diǎn)。事務(wù)A的開(kāi)始時(shí)間戳先于事務(wù)B，但是事務(wù)B的提交卻先于A，這時(shí)會(huì)發(fā)生什么事情？用多版本帶一個(gè)邏輯時(shí)鐘，就可以處理這種情況：假設(shè)A做INC N操作的時(shí)候邏輯時(shí)間是5，給B發(fā)消息變成6，B收到消息以后，它操作的N的版本應(yīng)該是6以后的。只需要邏輯時(shí)鐘，就可以檢測(cè)到有相互關(guān)聯(lián)性的事務(wù)。如果這個(gè)過(guò)程插入了C，如果C跟A和B沒(méi)有共同修改的key，那么C的影響可以忽略。如果有修改到N，但是沒(méi)有跟A和B交互，那么可以認(rèn)為C的存在與其它用戶并沒(méi)有因果關(guān)系，邏輯時(shí)鐘也不會(huì)檢測(cè)到這一點(diǎn)，是能滿足external consistency的。

3. 鎖實(shí)現(xiàn)和版本控制用那個(gè)呢？

兩者都是方法和手段，并不沖突和矛盾。鎖有很多不同的粒度，比如一把全局的大鎖;再比如讀寫(xiě)鎖，任一時(shí)刻如果有寫(xiě)，就不能進(jìn)行其它操作，而讀鎖之間相互不影響;我看了好些***的實(shí)現(xiàn)都是一把全局大鎖，像boltdb，還有l(wèi)eveldb的Go語(yǔ)言封裝里面提供的Transaction接口，都是很沒(méi)節(jié)操的。前陣子我還考慮過(guò)寫(xiě)一個(gè)RangeLock，調(diào)整鎖的粒度：只有被同步訪問(wèn)到的key之間，才會(huì)有鎖沖突，比如我在操作A他在操作B，相互是不影響的。遇到鎖沖突了會(huì)變得復(fù)雜，回滾操作必須記得釋放之前的鎖，加鎖也要有點(diǎn)技巧，如果一個(gè)操作鎖了A去請(qǐng)求B，另一個(gè)操作鎖了B去請(qǐng)求A，就成環(huán)死鎖了。

MVCC也會(huì)遇到?jīng)_突，沖突時(shí)無(wú)非兩種手段：過(guò)一會(huì)兒重試或者abort?？矗∵@本質(zhì)上也是鎖，樂(lè)觀鎖悲觀鎖而已。所以并不是用了MVCC鎖的概念就消失了。不過(guò)MVCC是個(gè)好東西，它比鎖可以提供更細(xì)粒度的并發(fā)。通過(guò)讀歷史版本，讓讀和寫(xiě)之間的沖突進(jìn)一步降低。代價(jià)當(dāng)然是問(wèn)題被搞得更加復(fù)雜了。

如何選擇？根據(jù)實(shí)際的場(chǎng)景具體情況具體去分析。挑選適當(dāng)?shù)母綦x級(jí)別，RC/RR/SI。

4. kv系統(tǒng)數(shù)據(jù)要持久化， 怎么保證在供電故障的情況下， 依然不丟數(shù)據(jù)。

先寫(xiě)WAL再做寫(xiě)操作，常識(shí)。出故障了從check point重放日志，就可以恢復(fù)之前的狀態(tài)機(jī)。

5. flush/fsync/WAL/磁盤(pán)和ssd的順序?qū)?/h2>

說(shuō)到這個(gè)問(wèn)題，就不得不先從緩存聊起。由于下一級(jí)的硬件跟不上上一級(jí)的讀寫(xiě)速度，緩存這東西應(yīng)運(yùn)而生。硬盤(pán)有緩存，操作系統(tǒng)有緩存，標(biāo)準(zhǔn)庫(kù)也有緩存，用戶還可能自己設(shè)緩存，總之是各種的緩存。命中緩存時(shí)，可以大大提高讀的速度，只有當(dāng)緩存穿透才會(huì)到下層去請(qǐng)求數(shù)據(jù)。寫(xiě)操作也由于緩存的存在而變成了批量操作，吞吐得以提高。

然而寫(xiě)的時(shí)候遇到突然斷電的情況，數(shù)據(jù)還在緩存層沒(méi)刷下去，就尷尬了。。。會(huì)丟數(shù)據(jù)！如果要保證可靠寫(xiě)這里我們需要采取些法子，手動(dòng)將緩存刷進(jìn)磁盤(pán)里。

flush是刷C標(biāo)準(zhǔn)庫(kù)的IO緩存。fsync是系統(tǒng)調(diào)用，頁(yè)緩存會(huì)被刷到磁盤(pán)上。

寫(xiě)IO有好多種方式，最笨的調(diào)用C的IO庫(kù)，然后還有操作系統(tǒng)的read/write，或者mmap又或者使用direct-io，甚至是寫(xiě)祼設(shè)備。關(guān)于這些寫(xiě)下去相關(guān)知識(shí)也不少。

WAL是常識(shí)性的東西，先出日志，重放日志就可以得到快照，即使快照壞掉了，重放日志也可以恢復(fù)出正常的快照。而且做同步一般都是基于日志來(lái)做的。

最后是磁盤(pán)和ssd，了解硬件的特性對(duì)于理解優(yōu)化非常重要。磁盤(pán)是需要尋道的，而尋道的硬件機(jī)制決定了這個(gè)操作快不了。硬盤(pán)順序讀寫(xiě)本身的速率比較快，但尋道卻要花掉10ms，所以隨機(jī)讀寫(xiě)性能會(huì)比較著。ssd那邊沒(méi)有尋道操作，讀的速度非常快。然而順序?qū)懙膬?yōu)勢(shì)相對(duì)磁盤(pán)并沒(méi)有高多少。如果沒(méi)記錯(cuò)，ssd大概就200MB/s的級(jí)別，而磁盤(pán)順序?qū)懸灿薪咏?00MB的級(jí)別。

6. 單機(jī)kv存儲(chǔ)系統(tǒng)， 從掉電到系統(tǒng)重啟這段時(shí)間， 不可用， 如何保證可用性呢？

要有副本。不然哪來(lái)可用性A？而有了副本，一致性C又麻煩來(lái)了，呵呵。

7. 數(shù)據(jù)復(fù)制， 日志復(fù)制， 有哪些實(shí)現(xiàn)方法呢？

做數(shù)據(jù)同步操作時(shí)，一般是找到快照點(diǎn)，將快照的數(shù)據(jù)發(fā)過(guò)去，之后再?gòu)姆胚@個(gè)點(diǎn)之后的日志數(shù)據(jù)。回放日志就可以增量同步了，不過(guò)增量同步也有不爽的，中間斷了太多就需要重新全量。最蛋疼的問(wèn)題是，增量同步只能做最終一致性。主掛了切到從，丟一段時(shí)間的數(shù)據(jù)。

8. 做主從復(fù)制， 采用pull和push操作， 那個(gè)好呢？

如果保證一致性，由主push并收到應(yīng)答處理。如果不保證，由從做pull比較好，從可以掛多個(gè)，還可以串起來(lái)玩。

9. 如何保證多副本的一致性？ RSM

副本是一致性的最大敵人，一旦有了副本，就有可能出現(xiàn)副本間不同步的情況。異步寫(xiě)的方式頂多只能做到最終一致性，所以必須同步寫(xiě)。寫(xiě)主之后，同步完其它節(jié)點(diǎn)從才返回結(jié)果。不過(guò)寫(xiě)所有節(jié)點(diǎn)太慢了，而且掛掉節(jié)點(diǎn)時(shí)可用性有問(wèn)題。

在raft出來(lái)之前，號(hào)稱工業(yè)上唯一只有一種一致性協(xié)議的實(shí)現(xiàn)，就是paxos。然而paxos即難懂，又難實(shí)現(xiàn)。無(wú)論對(duì)于教育還是工程角度都它媽蛋疼的要死，還它媽的統(tǒng)治了業(yè)界這么多年。強(qiáng)勢(shì)安利一波raft。

10. 分布式共識(shí)算法： zab， paxos， raft.

zab還沒(méi)研究過(guò)。basic paxos還勉強(qiáng)能看一看，multi paxos就蛋疼了，看得云里霧里。raft我寫(xiě)過(guò)幾篇博客，話題太大，這里不展開(kāi)了。不過(guò)不管是哪一種，搞分布式是逃不掉的。

11. commit語(yǔ)意是什么呢？

私以為是ACID里面的D，持久性。一旦提交了，就不會(huì)丟。

12. 單機(jī)或者單個(gè)leader的qps/tps較低， 如何擴(kuò)大十倍？

如果能加機(jī)器就搞分布式。做分布式就走兩個(gè)方向：可以分片就讓leader分片，負(fù)載就分?jǐn)傞_(kāi)了吞吐就上來(lái)了;可以副本就考慮走follower read，壓力就分到了follower中。只要架構(gòu)做的scalable了，擴(kuò)大10倍1000都好說(shuō)。

如果不能走分布式，就考慮優(yōu)化單機(jī)性能。網(wǎng)絡(luò)的瓶頸就batch + streaming。CPU，內(nèi)存什么都不說(shuō)了。硬盤(pán)不行就換SSD。

如果是qps，讀嘛，該上緩存上緩存。唯有寫(xiě)是不好優(yōu)化的，tps就合理選擇LSM存儲(chǔ)引擎，合并寫(xiě)操作，順序?qū)?。怎么讓系統(tǒng)性能更好這個(gè)話題，展開(kāi)就更多了，不過(guò)最后我還是想講個(gè)笑話。

某大廠某部門(mén)半年間系統(tǒng)性能優(yōu)化了3倍，怎么優(yōu)化的？因?yàn)樗麄兩?jí)了最新版本的php，php編譯器的性能提升了3倍。所以嘛。。。問(wèn)我怎么優(yōu)化？升級(jí)硬件吧，升級(jí)更牛B的硬件，立桿見(jiàn)影。我們客戶把TiDB的硬盤(pán)升級(jí)到了SSD，性能立馬提升了10倍。

13. 怎么做partitioning和replicating呢？

分片和副本，分布式系統(tǒng)里面的三板斧。系統(tǒng)規(guī)模大了，單機(jī)承受不住，肯定就分片。做存儲(chǔ)是有狀態(tài)服務(wù)，不能單個(gè)分片掛了系統(tǒng)就掛了，于是必須有副本。其實(shí)兩個(gè)都麻煩。

分片的麻煩的關(guān)鍵，在于分片調(diào)整。比如按hash分的，按range分的，只要涉及調(diào)整，就蛋疼。數(shù)據(jù)遷移是免不了，如果整個(gè)過(guò)程是無(wú)縫的？如果做到不停機(jī)升級(jí)？升級(jí)處理過(guò)程中，無(wú)信息的更新以及一致性，都是比較惡心的。

副本麻煩的關(guān)鍵，就是一致性了。有副本就引入了一致性問(wèn)題，paxos可以解救你，如果大腦不會(huì)暴掉。

具體的怎么分片還是看業(yè)務(wù)的。而副本什么也看一致性級(jí)別要求，強(qiáng)同步，半同步，最終一致性亂七八糟的。

14. 存儲(chǔ)或者訪問(wèn)熱點(diǎn)問(wèn)題， 應(yīng)該怎么搞？

加緩存?；蛘邩I(yè)務(wù)調(diào)整看能否hash將訪問(wèn)打散。

15. CAP原理

去問(wèn)google。先問(wèn)google。容易google到的都不要問(wèn)我。誰(shuí)要問(wèn)我這種東西，我拒絕回答，并給他一個(gè)鏈接：《提問(wèn)的智慧》。

16. 元數(shù)據(jù)怎么管理？

etcd呀。開(kāi)源這么多輪子，不好好用多浪費(fèi)。

17. membership怎么管理？

etcd呀。lease。上線下線都注意走好流程。

18. 暫時(shí)性故障和永久性故障有哪些呢？

暫時(shí)性故障：網(wǎng)絡(luò)閃斷，磁盤(pán)空間滿了，斷電，整機(jī)房掉電，光纖被挖斷了（中國(guó)大的互聯(lián)網(wǎng)公司服務(wù)質(zhì)量的頭號(hào)敵人），被ddos了 永久性故障：硬盤(pán)掛了，系統(tǒng)掛了，被墻了。

擦，我分不清勒。

19. failover和data replication怎么搞呢？

haproxy

20. 磁盤(pán)的年故障率預(yù)估是多少？

待會(huì)去google一下。先瞎寫(xiě)寫(xiě)，假設(shè)一塊磁盤(pán)一年故障的概率是P，假設(shè)系統(tǒng)有100塊磁盤(pán)，那么整個(gè)系統(tǒng)的磁盤(pán)故障率就變成了（1-（1-P）^100），我知道這個(gè)概率會(huì)變得非常大。

這時(shí)我們考慮RAID的情況。RAID 0卵用都沒(méi)有，壞一塊就壞了。計(jì)算公式跟之前一樣的。RAID 1兩塊盤(pán)互為鏡像，可以把P就成P/4。還有RAID 01/10，怎么計(jì)算來(lái)的？還有就是糾錯(cuò)碼技術(shù)。計(jì)算更復(fù)雜了。

分布式以后，上層可以控制分片和副本數(shù)，跟RAID一個(gè)道理，然后掛一個(gè)副本不會(huì)掛，要掛掉系統(tǒng)的大多數(shù)。。。。。。但是故障率是多少呢？操！數(shù)學(xué)沒(méi)學(xué)好，怎么辦?。?/p>

ssd跟磁盤(pán)不一樣的地方，它以整個(gè)block為單位操作，在寫(xiě)入之前需要先擦除，而擦除的次數(shù)是有上限的，所以壽命比磁盤(pán)的要短很多。具體是多久，還是得問(wèn)google。

21. kv系統(tǒng)存儲(chǔ)小王， 小李， 小張三個(gè)人的賬戶余額信息， 數(shù)據(jù)分別在不同的節(jié)點(diǎn)上， 怎么解決小王向小李， 小李向小張同時(shí)轉(zhuǎn)款的問(wèn)題呢？

兩階段提交。打個(gè)廣告：我們的TiKV提供了分布式事務(wù)，這個(gè)問(wèn)題很好解決。

Prewrite 小王賬戶減;小張賬戶加 Commit

Prewrite 小張賬戶減;小李賬戶加 Commit