系統設計學習筆記 - 附近的朋友
仿製一個臉書的「附近的朋友」功能
這次來讀《System Design Interview – An Insider's Guide: Volume 2》中的章節——附近的朋友，即類似於 Facebook Nearby friends（意外地發現最近這個服務要收掉了）或 Zenly 這樣的服務。
這個章節在書中放在 Proximity Service 之後，以大綱來看它就不再著墨於演算法選擇，而放了更多的快取及機器的設置上。
需求釐清
- 距離的判定：在實務上實現距離可能很不實用，因為中間如果隔了某些特殊地形如河流或鐵道就會導致兩點間的實際移動時間拉得十分長。但章節中先以直線距離做估計。
- 使用者座標需要快速迭代或移除：考慮使用者可能會選擇往朋友方移動，故服務要有辦法相對快速地去更新使用者座標，或是當使用者座標過久沒有更新的時候予以移除。
- 歷史資料儲存：在理想狀況下可以儲存使用者歷史座標紀錄以作他用，並且不必考慮法規問題。
聽起來就是 Facebook 會幹的勾當。
架構
在抽象的概念上使用者們會建立起類似於 網狀拓墣 那樣的結構：
但當然我們無法透過既有的網路技術直接達成，所以實際上這樣的服務仍然會是組成一個類似 星狀拓墣 的結構：
而中間的點那個點則必須是一個十分強大服務，其必須同步接收所有使用者的座標更新、並將更新的資訊發送給該使用者所有距離夠近的朋友們。
用這樣的兩句話敘述上，它的工作不算複雜，但問題就在資料的傳送量過於龐大。在假設有 1 千萬活躍使用者、每 30 秒上傳一次座標且他們平均擁有 40 個在附近的朋友來看，則：
這個後端服務每秒要處理 1333 萬個座標更新的通知。
具現化
由於座標更新的通知量過大，所以這裡就不是以前面章節中的座標搜尋 API 服務加上大量橫向擴展的方法來暴力面對問題。
User and database icons created by Freepik - Flaticon
起手式的 LB 依然被提及，就不贅述。其核心元件會包含：
- API 服務：這裡的 API 服務僅提供核心功能如登入、認證及好友管理等。
- 雙向 WebSocket 服務：設計上利用 WebSocket 來維持通訊，所有的座標更新、資訊推送皆透過 WebScoket 這端來處理。
- 發布/訂閱佇列（Pub/Sub）：作者建議直接使用 Pub/Sub 可以用極低的運算資源去管理數以百萬計的資訊推送。 這裡的設計上是對每個使用者開 channel，然後該使用者個座標更新就發布進使用者專屬的佇列中，而訂閱端則是該使用者的所有朋友們。 邏輯上將這個一對多反過來變成多對一，即將座標更新發布到每個朋友的 channel 應該也是可可行，不這樣做的原因可能是因為當朋友不在線上則會浪費管理那個朋友的 channel 的資源。
這個架構下，當使用者 #1 的座標更新，它的相關資訊會被 WebSocket 接收並送進 channel#1，朋友 #2, #3, #4 的 WebSocket 因為訂閱了 channel#1 故會得到通知，並且將資訊推送到朋友的手機裡。相對的，朋友 #5 的座標更新了，則使用者 #1 所連線的 WebSocket 也會從 channel#5 收到事件，並且推送給 #1 的手機。
為什麼不使用資料庫？
書中給的解釋為，因為這樣的服務只需要專注提供當下的朋友座標即可，它並沒有需要去使用如資料庫這類的長期方案。相對地，Redis 的反應十分迅速，並且有支援 TTL——在清理快取這塊，例如將長時間未更新的使用者移除，這種需求上可以更輕易地達成。
但這裡有個問題，同為 in-memory 的其他解決方案被略過了。在前面章節中介紹到四元樹有難以更新的問題，可以視為是一個不選它的合理理由；但 Google S2 再一次的被無視，也許是消耗的運算資源過高、也許是他們就真的沒需要這麼完整的功能。
營運面
服務擴充的問題
API server 較為簡單，它本質是一個把 DB 包成 API 打出去的服務，故應該可以輕易的橫向擴充。
但 WebSocket 則非，它是有狀態的（Stateful）服務，故在關閉運算節點之前會需要先進行耗盡（drain）的過程，同時 LB 也要避免新的流量被導向即將關閉的節點。另外在部署新版的服務時也要處理相同的過程。
至於這樣的 LB 要怎麼處理呢？書中的答案是砸錢解決——直接使用各 IaaS 提供的 LB。不過想像上可能是透過 LB 做 health check，然後把要收走的 node 的 readiness probe 打掉。
資料庫負載
此章節考慮的活躍使用者數量極高，導致資料庫的負載會是一個要考慮的點——它已經不太是單一 RDBMS 可以撐得著的資料量及使用量。
以 user database 來說，裡面儲存的資料有使用者基本資訊及朋友清單，這些資料特性上可以用使用者的 UID 做分群，故其實直接走 sharding 做橫向擴充可以解決問題。而另一方面，如果有這麼多的使用者的情況下，使用者資料應該會由另一個專職的部門在處理——簡單地說，直接打內部 API 去拿資料就好，資料庫怎麼管理是別人的事。
快取
在常見的需求下，直接使用一個 Redis 去做快取就是個十分足夠了。但這裡的題目設計卻是每秒 33 萬個請求，這樣的數字以單一 Redis 來說就太高了。
回過頭來，這個快取適用於儲存使用者最後回報的位子，故可以直接用使用者 ID 做 sharding，這樣就能輕鬆地處理掉這個數量級的快取。
發布/訂閱佇列
使用發布/訂閱的方式管理使用者間的座標更新是個十分有效率的手段，但問題就在這裡假設的資料量實在太大了：一千萬線上用戶、每個人有 100 個朋友同時也在線上。
以記憶體使用量來看，每個資料欄位佔據約 20 bytes 的大小，則會有約 200GB 的資料需要保存在記憶體中，在這個方面來看最小的伺服器需求為兩台。
以 CPU 使用量來看，這邊的假設是現代化的機房搭配 Gigabit 級的內網可以達到每秒 10 萬筆推送。承前面計算的每秒共 1,400 萬筆推送來看則會需要 140 台伺服器才能解決到這麼多需求。
很明顯地 CPU 會是發布/訂閱服務這塊的瓶頸，並且新的問題也同時誕生——該如何去管理一個分散式的發布/訂閱叢集。而書中給出的建議則是 Consistent hashing。
雖然書中在 Consistent hashing 著墨了不少，但到頭來還是上網看其他人的介紹來認識它的，這裡就不重新嘗試解釋了，我懶。