「Go面經」算法 并發模型 緩存落盤 etcd actor模型
Hello，大家好，我是陽哥。失蹤人口回歸，最近太忙，好久沒有更文啦。
本文先分享2段面經，文末總結了關鍵問題的復盤筆記。一定要看到最后！
求職者情況
分享一下好友的最新面經。
簡單說下這位好友的情況：坐標成都，游戲行業，3年開發經驗，最近2年做Go語言開發，1年Java/PHP工作經驗。
手撕CSAPP選手，半年前堅持打卡手寫的學習筆記。（最近半年被公司摧殘，沒時間了....）
面經分享
第一家
Golang后端，3年+經驗，游戲行業，成都，15~25K
下面以對話的方式大概描述問題：
A--->面試官
B--->我
A：自我介紹
B：巴拉巴拉
A：Actor 模型你是怎么理解的？
B：無鎖的并發計算模型，Actor 有自己的狀態，只能通過 mailBox 去收發消息、異步消息傳遞~
A：你不是百度了吧？
B：沒有。因為我覺得它的一部分思想和 Go 的 GMP 挺像的，好記（這里我就給自己挖坑了，擦嘞~）
A：你能說說它們哪里像嗎？
B：Go 的調度器全局隊列和它的 MailBox 挺像的
A：那你的意思是，實現 MailBox，你會使用隊列嗎？
B：是的，用 chan 關鍵字，元素類型為 Interface
A：這樣是可以，那么我給你一個場景，在同一時刻，有 1 萬個消息打進來呢？
B：增加緩沖區大小、無鎖隊列、批量處理消息、背壓機制
A：能從數據結構的角度說說嗎？
B：chan 底層是數組，線性結構，我想用非線性結構紅黑樹接收消息
A：為什么？
B：因為 epoll 模型就是這么做的
A：優勢是什么
B：忘了...
A：你再想想，比如動態調整緩沖區，可是是一瞬間打進來的，你怎么知道調整的多大，預留也不好做，巴拉巴拉
B：額，不知道
A：用環形隊列
B：啊？我沒想到，因為我的印象里，它的特定是固定大小，消息太多了，不是會覆蓋嗎，會導致消息丟失。（我提出這個疑問的時候，他沒有繼續給我聊了，如果只用環形隊列肯定有這個問題）我確實沒有想到，很少用到它...
A：你能聊聊分布式嗎？
B：巴拉巴拉，有擴展性、容錯、很多節點，不同地域、數據共享，巴拉巴拉
A：你提到了數據共享，那你說說一致性你怎么做？
B：我會先想到用 etcd 吧，因為它的 raft 可以保證一致性
A：繼續...
B：etcd Leader選舉、數據復制、心跳、然后讀取，保證一致性，巴拉巴拉它們的細節
A：etcd 是鍵值數據庫呀，主要場景是配置之類的吧，那我現在有一個場景，就是 10w qps 如何承載 50w qps 的場景，同時保證它們的數據一致性
B：啥？（我有點沒聽懂這個問題，硬來）首先是能夠承載這個量級吧，考慮主從復制，然后用分片技術水平擴展、異步處理、加緩存巴拉巴拉
A：主從同步你能說說典型的應用嗎？
B：（我已經被前面那個問題問蒙蔽了，想說 Redis 的，有點開不了口）額...
A：Redis 就是主從吧！
B：是....是的
然后就下來就是 Redis 拷打小皮鞭了，不多說了，謝謝大家。
第二家
Golang后端，坐標成都，游戲行業，15~20k
先說感受，總體不是很難。下面聽我慢慢聊：
A -> 面試官
B -> 我
A：自我介紹
B：巴拉巴拉
A：我看你簡歷上提到力扣做了挺多題的。
B：是的，但是已經有段時間沒做了，做過的題我都有基本思路。
A：你能說說你知道哪些排序嗎？
B：冒泡、選擇、插入、快速、歸并、堆、桶
A：快排你能說一下它的思路嗎？
B：通過選擇一個基準元素，將數組分割成左右兩個子數組，再對子數組進行遞歸排序，直到整個數組有序。
A：穩定排序和不穩定排序的概念能換說一下嗎？
B：假如排序前后兩個元素的相對順序在排序后仍然不變，那么這種算法就是穩定排序。不穩定排序反之。（這里答的其實不太好，可以結合前面提到的排序算法說一下，哪些具體的算法是穩定的）
A：你對二叉樹了解嗎？
B：了解的，樹形結構，有根節點、父節點、子節點、葉子節點、度、高度、深度這些概念。
A：常見的二叉樹有哪些？
B：平衡二叉樹、二叉搜索樹，巴拉巴拉。
A：能說一下前序遍歷和后序遍歷嗎？
B：前序遍歷，遍歷順序是根節點、左子樹、右子樹。后序遍歷是左子樹、右子樹、根節點。
A：前序遍歷和后續遍歷能夠構建一顆二叉樹嗎？
B：額，這個問題我不太理解。。。
A：沒事，換一個問題。Go 語言中的 Map 是如何實現的，你能聊一聊嗎？
B：Map 是使用哈希表、鏈表來實現的。然后我從散列函數、解決哈希沖突、動態擴容、并發安全性聊
A：Go 的并發模式你了解嗎？
B：請問是指的扇入扇出模式、for select 循環模式這種嗎？（后來回憶一下，面試官想讓我聊的應該是CSP并發模型）
A：不是，你可以說一說你了解的 Go 的并發原語
B：好的，我從兩個部分簡單說一下，一個就是關鍵字，另一個是包。像關鍵字有 go，創建協程。channel，進行通信。select，處理 channel 的收發。mutex，鎖。context，上下文。包的話 atomic。
A：你知道 csp 嗎，能簡單說一下嘛？
B：（我腦子里第一時間和 cap 搞混了，但還是拉回來了）csp 是一種通信協作模型。在 Go 里面有一句很經典的話，不要用共享內存來通信，要用通信來共享內存。
A：（露出了滿意的笑容，扭頭看向旁邊的同事）我沒什么問的了，你有什么問的嗎？
B：你之前用過 mongodb，存儲在 mongodb 中的索引你是怎么設計的？
A：不好意思，我之前沒有關注過這個部分，因為之前的整體架構都是將需要落盤的數據放在內存，然后標記臟位，通過一些策略來異步落盤，而需要查詢數據時，也是直接從內存查詢，因為項目啟動時，會把所有的玩家數據加載到內存中。
B：沒事，那我們聊一下 redis 吧，你知道 redis 的落盤方案嗎？
A：知道，AOF、RDB（然后開始介紹它們的特點）巴拉巴拉
B：你會如何評估 redis 的落盤方案？
A：我會從數據安全性、可恢復性、性能、硬盤空間成本、使用場景來評估。
B：硬盤空間成本？你能具體說說嗎？
A：AOF占用空間大等....巴拉巴拉。
B：redis 的 Key 過長會影響性能嗎？
A：額，我覺得應該會影響性能，因為你問了這個問題，但是這個我沒太關注過，對于 Key 我更在意的是可讀性。
最后聊了一些 Redis 的數據結構，又繼續聊了一下一些特定二叉樹的概念，還問了我對于矩陣、向量的理解，我就圍繞以前做過的天賦系統聊了一下矩陣。
復盤！復盤！
為了對大家更有幫助，我把面試中回答的關鍵問題，做了復盤和調研，總結如下：
Actor模型
Actor模型是一種并發計算模型，用于描述并發系統中的實體和它們之間的通信。在Actor模型中，系統中的每個實體被稱為一個Actor，每個Actor都有自己的狀態和行為，并且可以通過消息傳遞與其他Actor進行通信。
在Actor模型中，每個Actor都是獨立的，它們之間沒有共享的內存。Actor之間通過異步消息傳遞進行通信，一個Actor可以向其他Actor發送消息，也可以接收其他Actor發送的消息。當一個Actor接收到消息時，它可以根據消息內容和自身的狀態來決定如何處理消息，并可能改變自身的狀態或向其他Actor發送消息。
Actor模型的特點包括：
1. 并發性： 每個Actor都可以獨立地執行，不受其他Actor的影響，從而實現并發執行。
2. 無共享狀態： 每個Actor都有自己的狀態，不與其他Actor共享內存，避免了共享狀態帶來的并發問題。
3. 異步消息傳遞： Actor之間通過異步消息傳遞進行通信，消息的發送和接收是非阻塞的，提高了系統的響應性能。
4. 面向對象： 每個Actor都可以看作是一個對象，具有自己的狀態和行為，可以封裝數據和方法。
總結一下：通過使用Actor模型，可以簡化并發系統的設計和實現，提高系統的可擴展性和可維護性。同時，Actor模型也能夠有效地處理并發問題，避免了傳統并發編程中常見的共享狀態和鎖競爭的問題。
對比Go的GMP模型和Actor模型
Go的GMP（Goroutine, M, P）模型和Actor模型都是用于并發編程的模型，但在一些方面有所不同。
Go的GMP模型是Go語言并發編程的基礎，它通過goroutine（輕量級線程）和調度器（scheduler）來實現并發。GMP模型中的goroutine是Go語言中的并發執行單元，它可以獨立地執行函數或方法。調度器負責將goroutine分配給線程（P），以便并行執行。線程（P）是操作系統線程的抽象，它負責執行goroutine。M（Machine）是Go語言運行時系統的一部分，它管理線程的創建和銷毀，并提供與操作系統的交互。GMP模型的優點是輕量級的goroutine和高效的調度器，使得并發編程變得簡單且高效。
Actor模型是一種并發編程模型，它通過將并發執行的單元（稱為actor）之間的通信和狀態封裝在一起來實現并發。在Actor模型中，每個actor都是獨立的實體，它們通過消息傳遞進行通信。每個actor都有自己的狀態和行為，并且只能通過接收和發送消息來與其他actor進行通信。Actor模型的優點是提供了一種結構化的方式來處理并發，避免了共享狀態和鎖的問題。
雖然GMP模型和Actor模型都是用于并發編程，但它們在實現方式和語義上有所不同。GMP模型更加底層，直接操作線程和goroutine，適用于需要更細粒度控制的場景。而Actor模型更加高級，通過消息傳遞來實現并發，適用于需要更結構化和可擴展的場景。
總結起來，GMP模型適用于Go語言中的并發編程，提供了輕量級的goroutine和高效的調度器；而Actor模型適用于一般的并發編程，通過消息傳遞來實現并發。
epoll模型
epoll是一種在Linux系統中用于高效處理大量并發連接的I/O事件通知機制。它具有以下特點：
- 支持高并發：epoll使用事件驅動的方式，能夠同時處理大量的并發連接，適用于高并發的網絡應用場景。
- 高效的事件通知機制：epoll采用了基于事件驅動的方式，當有事件發生時，內核會將事件通知給應用程序，而不需要應用程序輪詢檢查事件是否發生，從而減少了系統資源的消耗。
- 支持邊緣觸發和水平觸發：epoll提供了兩種工作模式，邊緣觸發（EPOLLET）和水平觸發（EPOLLIN/EPOLLOUT）。邊緣觸發模式只在狀態發生變化時通知應用程序，而水平觸發模式則在狀態可讀或可寫時都會通知應用程序。
- 支持多種I/O事件類型：epoll可以同時監控多種I/O事件類型，包括讀事件、寫事件、錯誤事件等。
- 高效的內核數據結構：epoll使用紅黑樹和雙向鏈表等高效的數據結構來管理大量的文件描述符，提高了事件的處理效率。
總之，epoll模型具有高并發、高效的事件通知機制和多種I/O事件類型的支持，適用于處理大量并發連接的網絡應用場景。
etcd保證數據一致性
etcd通過使用Raft一致性算法來保證數據的一致性。 Raft是一種分布式一致性算法，它將集群中的節點分為Leader、Follower和Candidate三種角色，通過選舉機制選出Leader節點來處理客戶端的請求。
當客戶端向etcd發送寫請求時，Leader節點會將該請求復制到其他節點的日志中，并等待大多數節點確認接收到該日志條目。一旦大多數節點確認接收到該日志條目，Leader節點會將該請求應用到自己的狀態機中，并將結果返回給客戶端。同時，Leader節點會通知其他節點將該請求應用到自己的狀態機中。
如果Leader節點失去連接或崩潰，剩余的節點會通過選舉機制選出新的Leader節點。新的Leader節點會根據自己的日志和其他節點的日志進行比較，保證自己的日志是最新的，并將缺失的日志條目復制給其他節點，以保持數據的一致性。
通過Raft算法，etcd能夠保證數據在集群中的一致性，并且在Leader節點失效時能夠快速選舉出新的Leader節點，保證系統的可用性和數據的一致性。
redis的落盤方案
Redis的落盤方案主要有兩種：RDB（Redis Database）和AOF（Append Only File）。
- RDB（Redis Database）：RDB是Redis默認的持久化方式。它通過將Redis的內存數據快照保存到磁盤上的二進制文件中來實現持久化。RDB的優點是快速和緊湊，適合用于備份和恢復數據。RDB的缺點是在發生故障時可能會丟失一部分數據，因為RDB是定期進行持久化的，而不是實時的。
- AOF（Append Only File）：AOF是另一種持久化方式，它通過將Redis的寫操作追加到文件末尾來記錄數據的變化。AOF的優點是可以提供更好的數據安全性，因為它記錄了每個寫操作，可以在發生故障時進行恢復。AOF的缺點是相對于RDB來說，文件體積較大，恢復數據的速度較慢。
在實際應用中，可以根據需求選擇適合的落盤方案。如果對數據的安全性要求較高，可以選擇AOF方式；如果對數據的實時性要求較高，可以選擇RDB方式。另外，也可以同時使用RDB和AOF兩種方式，以提供更好的數據保護和恢復能力。
本文轉載自微信公眾號「 程序員升級打怪之旅」，作者「王中陽Go」，可以通過以下二維碼關注。
轉載本文請聯系「 程序員升級打怪之旅」公眾號。
