談談系統設計的面試

這個題目我一直在考慮要不要寫，因為有一天也許我們彼此會坐在一方小桌的兩端，聊聊系統設計，而我這麼做有泄題兜底之嫌。不過，考慮到不是所有的讀者都會來 TubiTV 這座小廟面試，而這個方面的確是很多朋友的弱項，我就略說幾句。

請聽題：一個使用 rail（或者 django，或者 express，...）和 MySQL 做的 API 系統，最近流量從 6,000 RPM 激增至 20,000 RPM，整個系統的壓力驟升，現在需要在應用層設計一套緩存方案來降低整個系統的負荷。要求是：緩存方案不能在 web 層（包括 proxy）做，也不能使用 framework 自帶的，或者第三方的緩存模塊。

大部分的面試者一看，這問題簡單啊，使用 redis（或者 memcached），加在應用伺服器和資料庫伺服器之間，讀取數據的時候如果沒有命中緩存，則讀取資料庫並寫入緩存，下次再讀相同的數據時就能命中緩存，大大減輕資料庫的壓力了。

這回答對么？不好說。也許對，也許不對。但你要這麼快搶答的話基本上就會被面試官斃了。

系統設計的面試重在討論和交流，釐清一切限制條件，然後在這些限制條件下面找到一個比較合理的解決方案。它不是編程題或者演算法題，弄清楚題目的要求就可以寫開始答案的。

好的面試者應該主動發問，來盡量找全限制條件，而不是直接假設。拿上述回答來說，面試者還沒開始認真分析問題所在，就想當然認為壓力在資料庫一側（是的，流量激增之後 90% 的可能性都是資料庫先扛不住壓力，但這是假設，不能化作前提），從可能錯誤的前提出發，必然會得出一個很可能錯誤的解決方案。

所以比較對路的思考過程是：

現有系統的架構是什麼樣子？

作為一個已有系統的優化項目，不了解現有系統的架構，歷史（演變的過程和演變的原因，當然，在面試中這個可以省去）而立刻上手設計都是在耍流氓。

• web 伺服器，應用伺服器，資料庫伺服器等之間的關係以及數量？
• 現在有沒有使用類似於 redis / memcached 的緩存伺服器？如果有，它們用來處理什麼任務？（如果有人問道這個，會有大大的加分）

目前哪個部分在系統中壓力最大？

這個問題非常重要，你得需要先知道問題在哪再考慮優化。如果問題出在應用伺服器，那麼，可能需要做頁面級的緩存；如果問題出在資料庫伺服器上，可以做數據級或者頁面級的緩存。

我們希望達到一個什麼樣的 capacity？

很多有多年一線工作經驗的面試者在這樣一個系統設計中竟然不去考慮究竟需要一個什麼樣的 capacity，就進入到具體的解決方案，這樣是不妥的。capacity 因問題而異，在這例子中，起碼要考慮 1) 緩存系統每秒的處理能力 2) 緩存系統的容量。對於一個 20k PRM 的請求數量，緩存系統應該能承受 50k，100k，甚至 200k PRM 的請求。至於容量，應該考慮假設所有不同的請求都被緩存（worst case），需要多大的容量，在限定的軟硬體條件下，是否能達到這個容量，達不到的話，什麼樣的上限比較合理。

有了這樣一個目標後，你還需要對你要使用的工具有個譜。有一個面試者說用 redis 做緩存，因為 redis 很快。「很快」是個很虛的概念，我於是問這個面試者你覺得 redis 對於 1k 大小的value，在 commodity hardware 上做 GET 操作每秒鐘的 QPS 是多少？對此，面試者一點概念也沒有，我讓他猜，他竟然給了個 3-5k QPS 的估值。我自己印象中 redis benchmark GET 操作大概是 100k 這個數量級，當然，每次返回 1k 大小的數據會拖累這個結果，但絕不會差出來兩個數量級。

有了設計容量的概念後，我們需要知道要緩存數據的大小，這其中，median size，average size，max size 都需要了解一下，起碼知道是什麼量級。返回 2k 大小的數據和 200k 大小的數據的處理方式可能是完全不同的，假設你的緩存系統的容量是 1M，2k 數據大小的緩存直接佔用的內存是 2G，而 200k 則是 200G，後者顯然不能使用內存來做緩存，只能用文件系統緩存。

講到文件系統，多說兩句。用文件系統做緩存則需要注意 unix 的目錄實際上是一個記錄文件名和 inode 對應關係的 map（你可以 ls -ai1 . 查看）。單個目錄下的文件越多，這個 map 越大，需要的讀取次數就越多（一般系統調用會每次讀 32k 或者類似的量級），所以當一個目錄下的文件特別多時，訪問效率會急劇下降。這是為什麼常見的文件緩存系統都是用兩級甚至多級目錄，1M 個文件，一級目錄使用兩個字母或數字，可以有 (26 + 10) 平方個二級目錄，也就是 1296 個目錄，每個目錄名兩個位元組，加上 inode 和其他一些消耗， 10-20 位元組完全夠用，一次讀取就能獲得所有二級目錄，而二級目錄平均是 772 個文件，一次讀取也能完成，總共兩次讀取，找到緩存文件，而如果把 1M 個文件放在一個目錄下，如果每個記錄 32 位元組，需要 1000 次讀取。這種分級緩存的思路在很多系統中都能見到，比如 TLB（不過多級 TLB 主要是為了節省內存）。

設計是否有優化的地方？

如今，內存，硬碟已經非常便宜，很多時候我們做系統設計，已經不需要一個比特或者一個位元組地去扣細節，但這並不意味著更好的，更省內存，更快運行的方案就沒有價值。我曾在一個面試中和面試者討論一個系統設計的優化，那個面試者對我「逼」著他優化演算法很不理解，他認為 computation 這麼便宜，錢不是問題，多加幾台機器並行運算就可以了。這是一種錯誤的做事態度。

永遠不要忘了設計應該是面向未來的，如果通過更換更好的演算法，能節省數十倍的內存（bitmap vs hashmap），或者數十倍的運算（bloom filter pre-filter vs raw computation），那麼你省下的不僅僅是當下的資源（或者金錢），還有未來的時間 —— 因為，當你的應用有10倍的流量時，你還能夠應對自如。

此外，優化可能會從量變轉化為質變。一個 analytics 應用如果每五分鐘才能完成一次分析，一小時僅能進行 12 次分析；如果將其優化成 30 秒完成，一個小時就可能完成 120 次，用戶可以更快地掌握趨勢。

一個認為資源不是問題，錢不是問題的設計者，只能是一個平庸的設計者。

每個認真的程序員應該這樣看待自己：In me the tiger sniffs the rose.