怎么做分布式存儲的面試?
一個實習生小朋友騙我說他不會，問我這些題目怎么做。這明擺著換個法子來面試我呀!要是真啥都不會能來我司實習么?全是套路啊。不過原文出題還是很有水平的，所以我決定寫一寫。
1. 用cas實現(xiàn)spinlock.
spinlock在網(wǎng)上應該一搜一大把，我試著給出一個simple甚至naive的實現(xiàn)。
- type SpinLock struct {
- count uint64
- }
- func (l *SpinLock) Lock() {
- for !atomic.CompareAndSwapUint64(&l.count, 0, 1) {
- }
- }
- func (l *SpinLock) Unlock() {
- atomic.StoreUint64(&l.count, 0)
- }
若是較真的話可以看看這里。這個題的考點不在這里，問無鎖實現(xiàn)，原子操作，ABA問題這些底層方向思路就走偏了。其實多線程的并發(fā)安全，跟多個事務的并發(fā)安全，在某種程度上是共通的。 這才是考察的核心問題，比如我做了一個kv引擎，只提供了get set 和cas操作，那么能否在這個基礎上，實現(xiàn)一個鎖操作的API?假設我們能實現(xiàn)出鎖操作，那我們又能否利用這個鎖，實現(xiàn)出跨多個key的修改操作的安全API?如何保證原子語義，要么全成功，要么全失敗。
事實上僅用cas這套搞出跨多key的修改是蠻蛋疼的，再細節(jié)到網(wǎng)絡失敗的時候鎖的釋放，深入思考下就會想到，因為網(wǎng)絡是有3態(tài)的：成功失敗和不可知。一般會基于快照做，只有cas的保證太弱了。
cas提供的原子性，這是一個很重要的點，假設在分布式的事務里面，跨分片的事務提供能否成功，只取決于一個primary key的提交是否能成功。這里有兩個問題思考一下也挺有意思，第一，跨多機的時候，如何提供對某一個key的原子語義?第二，如果只有對一個key的原子保證，如果實現(xiàn)跨許多機器跨多個key-value的原子操作語義?
扯淡扯遠了，我們看下一題吧。
2. 實現(xiàn)單機kv存儲系統(tǒng), 多節(jié)點共享kv存儲服務, 怎么解決external consistency的問題?
- kv存儲N=0
- 用戶A和B操作kv存儲系統(tǒng)按照下面時序:
- 1.用戶A執(zhí)行操作: INC N;
- 2.用戶A通知用戶B執(zhí)行操作;
- 3.用戶B執(zhí)行操作: if (N % 2 == 0) {N*=2;} else {N +=3;}
- 怎么保證結果符合預期呢? 在網(wǎng)絡傳輸影響操作到達次序的情況下, 怎么保證B后于A完成操作.
- 如果這個過程插入了C, 又如何做呢?
外部一致性我記得不是太清了(假裝一臉認真)，產(chǎn)生因果關系的操作之間，執(zhí)行順序滿足因的操作應該先于果?有點像因果率一致?A操作引發(fā)了B，那么B一定應該看得到A執(zhí)行產(chǎn)生的結果。這個例子里面因為這個因果關系，似乎是希望B看到的值應該是N INC之后的值。
兩個操作都訪問到了N，如果保證操作的安全?無非是，加鎖和MVCC。加鎖很好理解，讀寫鎖，寫寫沖突，讀寫沖突。那么該如何理解MVCC?MVCC其實很類似一個特殊的cas，它保證了涉及到跨多key修改的原子操作語義，這樣也可以理解為什么MVCC可以把并發(fā)粒度控制得更好。
這里是說的單機存儲引擎，如果放到分布式里面會更復雜一點。事務A的開始時間戳先于事務B，但是事務B的提交卻先于A，這時會發(fā)生什么事情?用多版本帶一個邏輯時鐘，就可以處理這種情況：假設A做INC N操作的時候邏輯時間是5，給B發(fā)消息變成6，B收到消息以后，它操作的N的版本應該是6以后的。只需要邏輯時鐘，就可以檢測到有相互關聯(lián)性的事務。如果這個過程插入了C，如果C跟A和B沒有共同修改的key，那么C的影響可以忽略。如果有修改到N，但是沒有跟A和B交互，那么可以認為C的存在與其它用戶并沒有因果關系，邏輯時鐘也不會檢測到這一點，是能滿足external consistency的。
3. 鎖實現(xiàn)和版本控制用那個呢?
兩者都是方法和手段，并不沖突和矛盾。鎖有很多不同的粒度，比如一把全局的大鎖;再比如讀寫鎖，任一時刻如果有寫，就不能進行其它操作，而讀鎖之間相互不影響;我看了好些傻逼的實現(xiàn)都是一把全局大鎖，像boltdb，還有l(wèi)eveldb的Go語言封裝里面提供的Transaction接口，都是很沒節(jié)操的。前陣子我還考慮過寫一個RangeLock，調(diào)整鎖的粒度：只有被同步訪問到的key之間，才會有鎖沖突，比如我在操作A他在操作B，相互是不影響的。遇到鎖沖突了會變得復雜，回滾操作必須記得釋放之前的鎖，加鎖也要有點技巧，如果一個操作鎖了A去請求B，另一個操作鎖了B去請求A，就成環(huán)死鎖了。
MVCC也會遇到?jīng)_突，沖突時無非兩種手段：過一會兒重試或者abort。看!這本質(zhì)上也是鎖，樂觀鎖悲觀鎖而已。所以并不是用了MVCC鎖的概念就消失了。不過MVCC是個好東西，它比鎖可以提供更細粒度的并發(fā)。通過讀歷史版本，讓讀和寫之間的沖突進一步降低。代價當然是問題被搞得更加復雜了。
如何選擇?根據(jù)實際的場景具體情況具體去分析。挑選適當?shù)母綦x級別，RC/RR/SI。
4. kv系統(tǒng)數(shù)據(jù)要持久化, 怎么保證在供電故障的情況下, 依然不丟數(shù)據(jù).
先寫WAL再做寫操作，常識。出故障了從check point重放日志，就可以恢復之前的狀態(tài)機。
5. flush/fsync/WAL/磁盤和ssd的順序?qū)?/strong>
說到這個問題，就不得不先從緩存聊起。由于下一級的硬件跟不上上一級的讀寫速度，緩存這東西應運而生。硬盤有緩存，操作系統(tǒng)有緩存，標準庫也有緩存，用戶還可能自己設緩存，總之是各種的緩存。命中緩存時，可以大大提高讀的速度，只有當緩存穿透才會到下層去請求數(shù)據(jù)。寫操作也由于緩存的存在而變成了批量操作，吞吐得以提高。
然而寫的時候遇到突然斷電的情況，數(shù)據(jù)還在緩存層沒刷下去，就尷尬了...會丟數(shù)據(jù)!如果要保證可靠寫這里我們需要采取些法子，手動將緩存刷進磁盤里。
flush是刷C標準庫的IO緩存。fsync是系統(tǒng)調(diào)用，頁緩存會被刷到磁盤上。
寫IO有好多種方式，最笨的調(diào)用C的IO庫，然后還有操作系統(tǒng)的read/write，或者mmap又或者使用direct-io，甚至是寫祼設備。關于這些寫下去相關知識也不少。
WAL是常識性的東西，先出日志，重放日志就可以得到快照，即使快照壞掉了，重放日志也可以恢復出正常的快照。而且做同步一般都是基于日志來做的。
最后是磁盤和ssd，了解硬件的特性對于理解優(yōu)化非常重要。磁盤是需要尋道的，而尋道的硬件機制決定了這個操作快不了。硬盤順序讀寫本身的速率比較快，但尋道卻要花掉10ms，所以隨機讀寫性能會比較著。ssd那邊沒有尋道操作，讀的速度非?？?。然而順序?qū)懙膬?yōu)勢相對磁盤并沒有高多少。如果沒記錯，ssd大概就200MB/s的級別，而磁盤順序?qū)懸灿薪咏?00MB的級別。
6. 單機kv存儲系統(tǒng), 從掉電到系統(tǒng)重啟這段時間, 不可用, 如何保證可用性呢?
要有副本。不然哪來可用性A?而有了副本，一致性C又麻煩來了，呵呵。
7. 數(shù)據(jù)復制, 日志復制, 有哪些實現(xiàn)方法呢?
做數(shù)據(jù)同步操作時，一般是找到快照點，將快照的數(shù)據(jù)發(fā)過去，之后再從放這個點之后的日志數(shù)據(jù)。回放日志就可以增量同步了，不過增量同步也有不爽的，中間斷了太多就需要重新全量。最蛋疼的問題是，增量同步只能做最終一致性。主掛了切到從，丟一段時間的數(shù)據(jù)。
8. 做主從復制, 采用pull和push操作, 那個好呢?
如果保證一致性，由主push并收到應答處理。如果不保證，由從做pull比較好，從可以掛多個，還可以串起來玩。
9. 如何保證多副本的一致性? RSM
副本是一致性的最大敵人，一旦有了副本，就有可能出現(xiàn)副本間不同步的情況。異步寫的方式頂多只能做到最終一致性，所以必須同步寫。寫主之后，同步完其它節(jié)點從才返回結果。不過寫所有節(jié)點太慢了，而且掛掉節(jié)點時可用性有問題。
在raft出來之前，號稱工業(yè)上唯一只有一種一致性協(xié)議的實現(xiàn)，就是paxos。然而paxos即難懂，又難實現(xiàn)。無論對于教育還是工程角度都它媽蛋疼的要死，還它媽的統(tǒng)治了業(yè)界這么多年。強勢安利一波raft。
10. 分布式共識算法: zab, paxos, raft.
zab還沒研究過。basic paxos還勉強能看一看，multi paxos就蛋疼了，看得云里霧里。raft我寫過幾篇博客，話題太大，這里不展開了。不過不管是哪一種，搞分布式是逃不掉的。
11. commit語意是什么呢?
私以為是ACID里面的D，持久性。一旦提交了，就不會丟。
12. 單機或者單個leader的qps/tps較低, 如何擴大十倍?
如果能加機器就搞分布式。做分布式就走兩個方向：可以分片就讓leader分片，負載就分攤開了吞吐就上來了;可以副本就考慮走follower read，壓力就分到了follower中。只要架構做的scalable了，擴大10倍1000都好說。
如果不能走分布式，就考慮優(yōu)化單機性能。網(wǎng)絡的瓶頸就batch + streaming。CPU，內(nèi)存什么都不說了。硬盤不行就換SSD。
如果是qps，讀嘛，該上緩存上緩存。唯有寫是不好優(yōu)化的，tps就合理選擇LSM存儲引擎，合并寫操作，順序?qū)憽Ｔ趺醋屜到y(tǒng)性能更好這個話題，展開就更多了，不過最后我還是想講個笑話。
某大廠某部門半年間系統(tǒng)性能優(yōu)化了3倍，怎么優(yōu)化的?因為他們升級了最新版本的php，php編譯器的性能提升了3倍。所以嘛...問我怎么優(yōu)化?升級硬件吧，升級更牛B的硬件，立桿見影。我們客戶把TiDB的硬盤升級到了SSD，性能立馬提升了10倍。
13. 怎么做partitioning和replicating呢?
分片和副本，分布式系統(tǒng)里面的三板斧。系統(tǒng)規(guī)模大了，單機承受不住，肯定就分片。做存儲是有狀態(tài)服務，不能單個分片掛了系統(tǒng)就掛了，于是必須有副本。其實兩個都麻煩。
分片的麻煩的關鍵，在于分片調(diào)整。比如按hash分的，按range分的，只要涉及調(diào)整，就蛋疼。數(shù)據(jù)遷移是免不了，如果整個過程是無縫的?如果做到不停機升級?升級處理過程中，無信息的更新以及一致性，都是比較惡心的。
副本麻煩的關鍵，就是一致性了。有副本就引入了一致性問題，paxos可以解救你，如果大腦不會暴掉。
具體的怎么分片還是看業(yè)務的。而副本什么也看一致性級別要求，強同步，半同步，最終一致性亂七八糟的。
14. 存儲或者訪問熱點問題, 應該怎么搞?
加緩存。或者業(yè)務調(diào)整看能否hash將訪問打散。
15. CAP原理
去問google。先問google。容易google到的都不要問我。誰要問我這種東西，我拒絕回答，并給他一個鏈接：《提問的智慧》。
16. 元數(shù)據(jù)怎么管理?
etcd呀。開源這么多輪子，不好好用多浪費。
17. membership怎么管理?
etcd呀。lease。上線下線都注意走好流程。
18. 暫時性故障和永久性故障有哪些呢?
暫時性故障：網(wǎng)絡閃斷，磁盤空間滿了，斷電，整機房掉電，光纖被挖斷了(中國大的互聯(lián)網(wǎng)公司服務質(zhì)量的頭號敵人)，被ddos了 永久性故障：硬盤掛了，系統(tǒng)掛了，被墻了。
擦，我分不清勒。
19. failover和data replication怎么搞呢?
haproxy
20. 磁盤的年故障率預估是多少?
待會去google一下。先瞎寫寫，假設一塊磁盤一年故障的概率是P，假設系統(tǒng)有100塊磁盤，那么整個系統(tǒng)的磁盤故障率就變成了(1-(1-P)^100)，我知道這個概率會變得非常大。
這時我們考慮RAID的情況。RAID 0卵用都沒有，壞一塊就壞了。計算公式跟之前一樣的。RAID 1兩塊盤互為鏡像，可以把P就成P/4。還有RAID 01/10，怎么計算來的?還有就是糾錯碼技術。計算更復雜了。
分布式以后，上層可以控制分片和副本數(shù)，跟RAID一個道理，然后掛一個副本不會掛，要掛掉系統(tǒng)的大多數(shù)......但是故障率是多少呢?操!數(shù)學沒學好，怎么辦啊?
ssd跟磁盤不一樣的地方，它以整個block為單位操作，在寫入之前需要先擦除，而擦除的次數(shù)是有上限的，所以壽命比磁盤的要短很多。具體是多久，還是得問google。
21. kv系統(tǒng)存儲小王, 小李, 小張三個人的賬戶余額信息, 數(shù)據(jù)分別在不同的節(jié)點上, 怎么解決小王向小李, 小李向小張同時轉(zhuǎn)款的問題呢?
兩階段提交。打個廣告：我們的TiKV提供了分布式事務，這個問題很好解決。
- Prewrite 小王賬戶減;小張賬戶加 Commit
- Prewrite 小張賬戶減;小李賬戶加 Commit
搞定!
真是越寫越是瞎扯淡去了...要是讓我們的實習生面試我，估計我要掛...也許當初是混進公司的吧，噓!別讓老板知道了。
