###### tags: `提升程式設計師的面試力`

# Chapter 9 系統設計和可擴充性

### 核心概念

**水平和垂直可延展性**

垂直延展代表著增加特定節點的資源
水平延展代表著增加節點的數量

**負載平衡器**

由一個可複製的伺服器組成的網路，此種伺服器 代表著相同的程式碼和存取相同資料的許可權。

**資料庫去正規劃和Nosql**

去正規劃代表著增加籠於資訊已加快資料讀取的速度

Nosql 不支援Join 他的設計目的是要更容易做擴展。

**資料庫分區**

垂直分區:依功能分區

基於Key(或雜湊)的分區:使用不同的計算方式將資料分散在不同的伺服器上，使用時再依照不同的計算方式取直。

基於目錄的分區:維護一個查閱資料表來搜尋資料

**快取**

把資料放在記憶體中 可以提供非常快速的結果。

**非同步處理和佇列**

緩慢的操作最好猜非同步動作完成，否則使用者就需要一直等待程序完成。

**網路指標**

頻寬:單位時間內可以傳輸最大的資料量
傳輸量：單位時間內實際可以傳輸的資料量
延遲:資料從一端到另一端所需的時間

**MapReduce**

MapReduce[1]是Google提出的一個軟體架構，用於大規模資料集的並列運算。概念「Map（對映）」和「Reduce（歸約）」

[wiki](https://zh.wikipedia.org/zh-tw/MapReduce)

**考量點**

1. 失敗
系統任何部分的失敗，需要有處置計畫

2. 可用性和可靠性
（Reliability）是指定時間 t 內，產生正式輸出的機率。
（Availability）是指系統的運作時間，工作時間比總時間，一般用百分比表示，例如99.999%（5個9）

[wiki](https://zh.m.wikipedia.org/zh-tw/%E5%8F%AF%E9%9D%A0%E6%80%A7%E3%80%81%E5%8F%AF%E7%94%A8%E6%80%A7%E5%92%8C%E5%8F%AF%E7%B6%AD%E8%AD%B7%E6%80%A7)

3. 大量讀vs大量寫

4. 安全性

**沒有完美的系統**

系統設計上一定會有取捨的存在，需要確認情境問題的範圍、做出相對合理的假設並基於這些假設建立可靠的設計。

**問題舉例**

步驟一：
先縮小範圍:從數百萬個，縮小成數十個檔案

步驟二：
思考檔案數量增加到數百萬個會另外出現出什麼問題。

步驟三

評估最後的解決方案，看最後程式結構面要不要另外實做不同的方式，增加效率或是解決其中的問題。

### 9.5
快取：想像有一台能簡化搜尋引擎的web伺服器。這個系統有100台機器可以回應搜尋查詢，然後可以使用processSearch(string query )呼叫另一組機器來實際獲得結果。回應查詢的機器是隨機選擇的，因次不能保證相同的請求總是由相同的機器回應。processSearch方法非常昂貴。請為最近得查詢設計快取機制。

1. 確定問題的範圍
* 限定在搜尋的查詢
* 只有100台機器
2. 做出合理的假設
* 除了呼叫processSearch 外，所有的查詢都在被呼叫的初始機器上
* 想要快取得查詢數量很大(數百萬)
* 機器之前的呼叫相對較快
* 查詢的結果是一個由URL組成的有序串列，每個URL都有一個50字元的標頭和200字的摘要。
* 最熱門的查詢非常常出現，因此他們總是出現在快取中。

3. 繪製主要的組件

4. 識別關鍵問題
* 要能高效的搜尋給定的值
* 要讓舊資料過期，以便我們可以用新資料替換他

4.1. 為單一個系統設計一個快取
* 使用link list 可以將新項移到前面，也可以方便清除舊資料
* 雜湊表可以讓我們高效的找到資料

4.2. 擴展到多個機器
* 每台機器都有自己的快取:每次都當一個新的查詢，無法發揮重複查詢的利用
* 每台機器都有一個快取副本: 當更新的時候每台機器的快取都需更新，而且能快取的資料相對少
* 每台機器儲存快取的一個區段: 利用特殊的計算，可以增大快取的值，減少使用process search 的數量。

4.3. 當內容變化時更新結果
* URL 內容改變: 定期迭代快取
* 結果的順序隨著頁面變化而變化: 定期迭代快取
* 出現與特定查詢的新頁面:設置ttl 強迫更新

5. 針對關鍵問題進行重新設計

* 對於某些熱門的查詢，是否可以讓他跟其他機器請求完後，留在自己的快取上面？
* 根據雜湊值分配機器，而不是隨機分配?
* 是否設置ttl 自然去刷新
### 9.6

銷售排名：一個大型電子商務公司希望列出最暢銷的產品，分別是所有產品中最暢銷的產品和各分類底下最暢銷的產品。

1. 確定問題的範圍
* 只要注重與這個問題相關的元件，而不是整個電子商務系統
* 銷售排名的含義: 什麼時間區間的銷售，有權重嗎
* 每個產品可以擁有多類別，而不是子類別
2. 做出合理的假設
* 統計資料不需要是100%最新的，對於最受歡迎的產品可以每小時更新一次，不受歡迎的產品可以一天再更新一次
* 對於最後歡迎的產品精准度是很重要的，其他的產品可以對精准度有差異
* 最低的更新時間為一個小時，統計時間大約為最近七天

3. 繪製主要的元件


將每一個訂單號碼都儲存到資料庫中，每個一小時左右，從資料庫中按類別取得銷售資料，計算總銷售額，對其排序並將其儲存在某種銷售排名資料快取中。

4. 識別關鍵問題

* 分析是昂貴的: 因為如果每次都直接重算，對資料庫的消耗是巨大的，如果只紀錄總銷售額，不是每筆購買，每次購買都會更新組銷售額的欄位。因為我們不想要每一天都重算過去區間的銷售額，可以依照不同的區間去切分過去的銷售額，減少搜尋的範圍(day,hour)
* 會非常頻繁的寫資料庫: 將購買紀錄存在某種記憶體快取中，定期計算，並更新資料庫。 關於排序的誤差可以在所有的計算都計算完後再執行排名，或是只更新某個時間點前的紀錄，依據此做排名
* Join 成本昂貴: 可以分開來，先取得此類別的所有商品在排序，而不是直接呼叫join 進行排序可以減少成本，思考減少使用join 的數量可以增加效率。
* 資料庫的查詢成本可能也很昂貴: 如果查詢跟寫的成本很昂貴可以使用紀錄檔，直接使用不同的分類作為一個資料夾，每個分類一定需要一個，把不同的產品id 或是 天的資料合併，這樣就可以很快速的算出結果
### 9.7
個人財務經理: 解釋你將如何設計一個個人理財經理。這個系統會連接到您的銀行帳戶，分析您的消費習慣，並提出建議。
1. 確定問題的範圍
* 建立一個帳戶，並將您的銀行帳戶加到這個帳號中。您可以將多個銀行帳戶加到這個帳戶裡面
* 他可以取得所有的財務歷史，或至少銀行允許你取得所有的財務歷史。
* 這個歷史包括支出的錢、收入的錢和當前的錢。
* 每款項交易都有一個與之相關的類別
* 存在某種資料來源，可以在一定程度上告訴系統某個交易與哪個類別相關聯。和某些情況下，使用者可以在類別不同時修正。
* 使用者將使用該系統獲得其支出的建議。這些建議來自一群典型的使用者，但是這些條件可以被自訂的條件預算覆蓋過去
* 我們假設這只是一個網站
* 我們可能會定期或特定條件下的電子郵件通知
* 我們假設無法讓使用者自訂規則來指定交易類別
* 我們假設依照交易對象來分類，而不是價格或日期。

2. 做出合理的架設
* 增加或刪除銀行帳戶相對不常發生
* 系統寫入的工作是很繁重的。一個使用者可能針對每天進行新的交易，但是使用者很少會一週存取網站一次以上。事實上，系統與他們的主要互動可能是透電子郵件。
* 一個交易被分配到一個類別後，只有在再使用者要求的時候才修改。
* 銀行不會向我們的系統推送資料，我們需要自己從銀行取得資料
* 對於超出預算的使用者。不需要立即發送提醒

3. 繪製主要元件


依照此架構我們可以定期的取得銀行資料，頻率依照使用者決定
取得新資料後，將把一些資料儲存在一個原始的、未處理的交易清單中。將資料丟入分類器中，分類器將每個交易分類一個類別並將這些分類的交易存在一個資料儲存庫。
預算分析器取得分類交易，依照別更新每個使用者的預算，並儲存使用者的預算。
4. 識別關鍵問題
* 這是一個資料量很大的系統，我們希望他可以快速回覆，因次我們將交易做成非同步
* 我們至少需一個queue，可以將需要完成的工作排隊。
* 這些任務有不同的優先順序，因為某些任務需要比其他任務執行的更頻繁。
* 系統中還有一個重要的東西是電子郵件系統，我們可以用一個任務定期抓取使用者的資料，檢查他們是否超出了預算
* 我們應該考慮合併這樣的知識: 系統可能會有很多不活躍的使用者，需要他們從系統中移除或是將他們的帳戶設為低活動
* 系統中最大的瓶頸可能是取得和分析大量的資料。

4.1. 分類器和預算分析器
* 取得一個使用者個交易時，就可以將它分類並整格這些資料。
* 因為要處理大量的交易，所以是用一般的資料庫很像沒有很適合
* 存到一個資料組中，可能會更好


這樣大多數的任務都只要在紀錄檔中處理，最後在更新回資料庫中，減少了資料的讀取與寫入。

4.2. 使用者改變類別
可以更新已分類的交易，他會觸發預算的重新計算，將舊類別減少，新類別中增加。

### 9.8
設計一個像是[Pastebin](https://pastebin.com/)的系統，使用者可以輸入一段文字，並獲得一個隨機生成的URL 來存取他
1. 確定問題的範圍
* 系統不支援使用者帳號或編輯文件
* 系統追蹤會分析每個頁面被存取的次數
* 舊文件在長時間未被存取後會被刪除
* 雖然在存取文件時不會做真正的身份驗證，但是要讓使用者無法輕易猜到網址。
* 該系統有一個前端和一個ＡＰＩ
* 每個ＵＲＬ的分析，可以透過每個面上的「status」連結存取。不過，他在預設的情況下不會顯示

2. 作出合裡的假設
* 該系統的流量很大，包含數百萬個文件
* 在不同的文件之間的流量分佈並不均勻，有些文件的存取次數比其他文件多很多。

3. 繪製主要組件
* 做一個簡單的設計，追蹤ＵＲＬ和他們關連的檔案並分析存取這些檔案的頻率。
* 資料庫vs文件中：因為不需要搜尋所以存在文件中看起來是個好選項。
* 
* 一個簡單的資料庫記錄ＵＲＬ與文件的關係，另外一個資料庫記錄追蹤存取的資料，每次存取統計資料時，會從資料庫中取得相關資料。

4. 找出關鍵的問題

* 有些檔案的存取次數非常的多，所以將資料儲存在記憶體中可以增加效率，所以使用快取
* 資料庫分片。是否要用hash 後再分片去處理，但是這樣子會有增加資料庫的問題。
* 生成ＵＲＬ:使用GUID 因為他的隨機分散性很高也不容易有衝突，所以要保證完全不衝突的狀態下只要再加上簡易的檢測就可以了。
* 分析： 儲存每次的原始資料vs只存自己要用到的資料