實習生面試分布式存儲的21道經典試題

一個實習生小朋友騙我說他不會，問我這些題目怎么做。這明擺著換個法子來面試我呀！要是真啥都不會能來我司實習么？全是套路啊。不過原文出題還是很有水平的，所以我決定寫一寫。

1. 用cas實現spinlock.

spinlock在網上應該一搜一大把，我試著給出一個simple甚至naive的實現。

實習生面試分布式存儲的經典試題

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

事實上僅用cas這套搞出跨多key的修改是蠻蛋疼的，再細節到網絡失敗的時候鎖的釋放，深入思考下就會想到，因為網絡是有3態的：成功失敗和不可知。一般會基于快照做，只有cas的保證太弱了。

cas提供的原子性，這是一個很重要的點，假設在分布式的事務里面，跨分片的事務提供能否成功，只取決于一個primary key的提交是否能成功。這里有兩個問題思考一下也挺有意思，第一，跨多機的時候，如何提供對某一個key的原子語義？第二，如果只有對一個key的原子保證，如果實現跨許多機器跨多個key-value的原子操作語義？

扯淡扯遠了，我們看下一題吧。

2. 實現單機kv存儲系統，多節點共享kv存儲服務，怎么解決external consistency的問題？

kv存儲N=0

用戶A和B操作kv存儲系統按照下面時序：

1.用戶A執行操作： INC N;

2.用戶A通知用戶B執行操作;

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

怎么保證結果符合預期呢？在網絡傳輸影響操作到達次序的情況下，怎么保證B后于A完成操作。

如果這個過程插入了C，又如何做呢？

外部一致性我記得不是太清了（假裝一臉認真），產生因果關系的操作之間，執行順序滿足因的操作應該先于果？有點像因果率一致？A操作引發了B，那么B一定應該看得到A執行產生的結果。這個例子里面因為這個因果關系，似乎是希望B看到的值應該是N INC之后的值。

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

這里是說的單機存儲引擎，如果放到分布式里面會更復雜一點。事務A的開始時間戳先于事務B，但是事務B的提交卻先于A，這時會發生什么事情？用多版本帶一個邏輯時鐘，就可以處理這種情況：假設A做INC N操作的時候邏輯時間是5，給B發消息變成6，B收到消息以后，它操作的N的版本應該是6以后的。只需要邏輯時鐘，就可以檢測到有相互關聯性的事務。如果這個過程插入了C，如果C跟A和B沒有共同修改的key，那么C的影響可以忽略。如果有修改到N，但是沒有跟A和B交互，那么可以認為C的存在與其它用戶并沒有因果關系，邏輯時鐘也不會檢測到這一點，是能滿足external consistency的。

3. 鎖實現和版本控制用那個呢？

兩者都是方法和手段，并不沖突和矛盾。鎖有很多不同的粒度，比如一把全局的大鎖;再比如讀寫鎖，任一時刻如果有寫，就不能進行其它操作，而讀鎖之間相互不影響;我看了好些傻逼的實現都是一把全局大鎖，像boltdb，還有leveldb的Go語言封裝里面提供的Transaction接口，都是很沒節操的。前陣子我還考慮過寫一個RangeLock，調整鎖的粒度：只有被同步訪問到的key之間，才會有鎖沖突，比如我在操作A他在操作B，相互是不影響的。遇到鎖沖突了會變得復雜，回滾操作必須記得釋放之前的鎖，加鎖也要有點技巧，如果一個操作鎖了A去請求B，另一個操作鎖了B去請求A，就成環死鎖了。

MVCC也會遇到沖突，沖突時無非兩種手段：過一會兒重試或者abort。看！這本質上也是鎖，樂觀鎖悲觀鎖而已。所以并不是用了MVCC鎖的概念就消失了。不過MVCC是個好東西，它比鎖可以提供更細粒度的并發。通過讀歷史版本，讓讀和寫之間的沖突進一步降低。代價當然是問題被搞得更加復雜了。

如何選擇？根據實際的場景具體情況具體去分析。挑選適當的隔離級別，RC/RR/SI。

4. kv系統數據要持久化，怎么保證在供電故障的情況下，依然不丟數據。

先寫WAL再做寫操作，常識。出故障了從check point重放日志，就可以恢復之前的狀態機。

5. flush/fsync/WAL/磁盤和ssd的順序寫

說到這個問題，就不得不先從緩存聊起。由于下一級的硬件跟不上上一級的讀寫速度，緩存這東西應運而生。硬盤有緩存，操作系統有緩存，標準庫也有緩存，用戶還可能自己設緩存，總之是各種的緩存。命中緩存時，可以大大提高讀的速度，只有當緩存穿透才會到下層去請求數據。寫操作也由于緩存的存在而變成了批量操作，吞吐得以提高。

然而寫的時候遇到突然斷電的情況，數據還在緩存層沒刷下去，就尷尬了。。。會丟數據！如果要保證可靠寫這里我們需要采取些法子，手動將緩存刷進磁盤里。

flush是刷C標準庫的IO緩存。fsync是系統調用，頁緩存會被刷到磁盤上。

寫IO有好多種方式，最笨的調用C的IO庫，然后還有操作系統的read/write，或者mmap又或者使用direct-io，甚至是寫祼設備。關于這些寫下去相關知識也不少。

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

最后是磁盤和ssd，了解硬件的特性對于理解優化非常重要。磁盤是需要尋道的，而尋道的硬件機制決定了這個操作快不了。硬盤順序讀寫本身的速率比較快，但尋道卻要花掉10ms，所以隨機讀寫性能會比較著。ssd那邊沒有尋道操作，讀的速度非常快。然而順序寫的優勢相對磁盤并沒有高多少。如果沒記錯，ssd大概就200MB/s的級別，而磁盤順序寫也有接近100MB的級別。