今天秀才就帶大家來看另一個(gè)后端面試戰(zhàn)場(chǎng)上的經(jīng)典系統(tǒng)設(shè)計(jì)問題：設(shè)計(jì)實(shí)現(xiàn)一個(gè)限流器。“設(shè)計(jì)限流器”其實(shí)也跟“設(shè)計(jì)短鏈系統(tǒng)”一樣，需要從多個(gè)維度出發(fā)，層層遞進(jìn)，抽絲剝繭?？此坪?jiǎn)單的功能背后，潛藏著分布式環(huán)境下的狀態(tài)同步、高并發(fā)處理的性能挑戰(zhàn)、不同業(yè)務(wù)場(chǎng)景的算法選型以及服務(wù)高可用等一系列復(fù)雜的工程難題。

下面秀才就帶大家庖丁解牛，從一個(gè)核心需求出發(fā)，逐步構(gòu)建出一個(gè)穩(wěn)健、高效、可擴(kuò)展的百萬級(jí)QPS限流系統(tǒng)。讓你在面試中游刃有余，盡顯高手風(fēng)范。

一、什么是限流器

拿到問題之后，還是老規(guī)矩，首先得搞明白面試官讓我們?cè)O(shè)計(jì)的究竟是一個(gè)什么東西。限流器顧名思義，是一種控制流量的機(jī)制，用于在高并發(fā)系統(tǒng)中限制用戶或服務(wù)的請(qǐng)求速率，避免系統(tǒng)因?yàn)檫^多請(qǐng)求而崩潰。比如允許用戶每分鐘發(fā)起 100 次請(qǐng)求，超出限額的請(qǐng)求將被拒絕響應(yīng)

二、需求梳理

面試官：“我們來聊聊系統(tǒng)設(shè)計(jì)吧。如果要你來實(shí)現(xiàn)一個(gè)高性能的限流器，你會(huì)怎么設(shè)計(jì)？”

系統(tǒng)設(shè)計(jì)是典型的開放性問題，我們要做的第一步永遠(yuǎn)是跟面試官對(duì)齊需求。

1. 功能需求

假設(shè)在本次面試中，面試官是讓你為某社交媒體平臺(tái)的 API 設(shè)計(jì)一個(gè)限流器。這就意味著我們限流器的功能是限制單個(gè) HTTP 請(qǐng)求（如發(fā)布推文、獲取時(shí)間線或上傳照片），而不是更高層次的操作或業(yè)務(wù)功能。所以，我們要將重點(diǎn)討論用于控制流量和保護(hù)系統(tǒng)的服務(wù)端實(shí)現(xiàn)方案。雖然客戶端限流作為補(bǔ)充方案也有其價(jià)值，但這里不是我們討論的重點(diǎn)。

核心需求：

• 系統(tǒng)應(yīng)通過用戶 ID、IP 地址或 API 密鑰識(shí)別客戶端，以應(yīng)用適當(dāng)?shù)南拗啤?/li>
• 系統(tǒng)應(yīng)根據(jù)可配置的規(guī)則限制 HTTP 請(qǐng)求（例如，每分鐘每個(gè)用戶 100 次 API 請(qǐng)求）。
• 當(dāng)超出限制時(shí)，系統(tǒng)應(yīng)拒絕請(qǐng)求并返回 HTTP 429 狀態(tài)碼，并包含有用的頭部信息（如剩余速率限制、重置時(shí)間）。

2. 非功能需求

明確系統(tǒng)功能之后，此時(shí)你應(yīng)當(dāng)向面試官確認(rèn)規(guī)模預(yù)期。我們?cè)O(shè)計(jì)的這個(gè)系統(tǒng)，是為日請(qǐng)求量幾千次的初創(chuàng)公司API設(shè)計(jì)的，還是為一個(gè)需要每秒處理數(shù)百萬請(qǐng)求的大型平臺(tái)設(shè)計(jì)的呢？系統(tǒng)的規(guī)模將直接決定我們的架構(gòu)選型。

假設(shè)面試官給出的目標(biāo)是：每日1億活躍用戶，產(chǎn)生每秒100萬次請(qǐng)求（1M QPS）。

(1) 核心需求

這個(gè)量級(jí)，一下就將設(shè)計(jì)挑戰(zhàn)拉滿了?；诖耍覀兛梢酝茖?dǎo)出具體的非功能性需求：

• 低延遲：限流邏輯本身不能成為性能瓶頸，其引入的延遲開銷應(yīng)極?。ɡ纾看螜z查耗時(shí) < 10ms）。
• 高可用：限流系統(tǒng)作為核心基礎(chǔ)設(shè)施，必須具備極高的可用性。在分布式環(huán)境下，可以接受最終一致性，因?yàn)楣?jié)點(diǎn)間限流狀態(tài)的微小延遲是可以容忍的。
• 高并發(fā)：系統(tǒng)必須能夠穩(wěn)定處理每日1億活躍用戶帶來的每秒100萬次請(qǐng)求。

最后我們可以將需求整理出來，如果有白板的話，我們可以在白板上做一個(gè)需求呈現(xiàn)

三、底層設(shè)計(jì)

需求明確之后，我們可以開始勾勒系統(tǒng)的內(nèi)部結(jié)構(gòu)了，先從核心實(shí)體和接口定義開始。

“好的，根據(jù)剛才的需求，我們可以抽象出幾個(gè)核心實(shí)體來構(gòu)建我們的限流模型。”

1. 核心實(shí)體定義

盡管限流器聽起來像個(gè)簡(jiǎn)單的基礎(chǔ)設(shè)施，但其內(nèi)部邏輯需要我們精確建模：

• 規(guī)則（Rule）：定定義不同場(chǎng)景限制的速率限制策略。每條規(guī)則指定參數(shù)，如每個(gè)時(shí)間窗口的請(qǐng)求數(shù)、適用的客戶端以及覆蓋的端點(diǎn)。例如：“已認(rèn)證用戶每小時(shí)可請(qǐng)求 1000 次”或“搜索 API 每分鐘每個(gè) IP 允許 10 次請(qǐng)求?！?/li>
• 客戶端（Client）：被限流的對(duì)象實(shí)體。它可以是一個(gè)用戶（通過UserID識(shí)別）、一個(gè)IP地址，或者一個(gè)API密鑰。每個(gè)客戶端都有一個(gè)關(guān)聯(lián)的限流狀態(tài)，用于實(shí)時(shí)追蹤其當(dāng)前是否符合規(guī)則。
• 請(qǐng)求（Request）：進(jìn)入系統(tǒng)的、需要被評(píng)估的API請(qǐng)求。每個(gè)請(qǐng)求都攜帶了上下文信息，如客戶端身份、訪問的端點(diǎn)和時(shí)間戳，這些信息是判斷適用哪條規(guī)則的依據(jù)。
• 這三者協(xié)同工作：當(dāng)一個(gè)請(qǐng)求到達(dá)時(shí)，系統(tǒng)首先識(shí)別出其對(duì)應(yīng)的客戶端，然后查找適用于該客戶端的規(guī)則，最后檢查其當(dāng)前使用量是否超限，從而決定是放行還是拒絕。

2. 系統(tǒng)接口設(shè)計(jì)

限流器本質(zhì)上是一個(gè)被其他業(yè)務(wù)服務(wù)調(diào)用的基礎(chǔ)設(shè)施組件，其接口設(shè)計(jì)應(yīng)當(dāng)力求簡(jiǎn)潔直觀。我們可以設(shè)計(jì)一個(gè)核心接口，供其他服務(wù)調(diào)用，以判斷請(qǐng)求是否應(yīng)該被允許。

/**
 * 檢查請(qǐng)求是否被允許
 * @param clientId 客戶端唯一標(biāo)識(shí) (用戶ID, IP地址, 或 API Key)
 * @param ruleId 規(guī)則唯一標(biāo)識(shí)
 * @return 一個(gè)包含是否通過、剩余次數(shù)和重置時(shí)間的對(duì)象
 */
isRequestAllowed(clientId, ruleId) -> {
    passes: boolean,      // 是否允許通過
    remaining: number,    // 剩余請(qǐng)求次數(shù)
    resetTime: timestamp  // 計(jì)數(shù)器重置的時(shí)間戳
}

這個(gè)方法接收客戶端ID和規(guī)則ID，返回一個(gè)布爾值表示是否允許請(qǐng)求。同時(shí)，它還會(huì)返回客戶端需要知道的元數(shù)據(jù)，用于填充X-RateLimit-Remaining和X-RateLimit-Reset這兩個(gè)HTTP響應(yīng)頭。

四、高層架構(gòu)設(shè)計(jì)

我們首先得設(shè)計(jì)出一個(gè)滿足核心功能需求的最小可行產(chǎn)品(MVP)。它不需要具備擴(kuò)展性或完美無缺，只是為后續(xù)開發(fā)奠定基礎(chǔ)。然后我們逐一檢查每個(gè)功能需求，確保高層設(shè)計(jì)能滿足所有要求。

1. 限流器應(yīng)該部署在什么位置？

面試官：“實(shí)體和接口定義清楚了。那么從架構(gòu)層面看，你認(rèn)為這個(gè)限流器應(yīng)該部署在系統(tǒng)的哪個(gè)位置？”

這是一個(gè)關(guān)鍵的架構(gòu)決策點(diǎn)，它直接決定了限流器能獲取哪些上下文信息，以及它如何與系統(tǒng)的其他部分集成。你可以展示幾種方案，并分析其優(yōu)劣，最終給出你的選擇。

“關(guān)于部署位置，業(yè)界主要有三種方案，各有優(yōu)劣。我們可以逐一分析?！?/p>

(1) 進(jìn)程內(nèi)限流

最直接的想法是，讓每個(gè)應(yīng)用服務(wù)或微服務(wù)自己內(nèi)部實(shí)現(xiàn)限流邏輯。當(dāng)請(qǐng)求進(jìn)入服務(wù)時(shí)，服務(wù)檢查自己內(nèi)存中的計(jì)數(shù)器，更新并決定是否放行。這種方式非?？?，因?yàn)橐磺卸荚趦?nèi)存中完成，沒有網(wǎng)絡(luò)開銷。”

但這個(gè)方案有個(gè)致命缺陷：狀態(tài)不共享。每個(gè)服務(wù)實(shí)例只知道自己接收到的流量，無法看到全局的流量情況。假設(shè)我們限制一個(gè)用戶每分鐘100個(gè)請(qǐng)求，如果有5個(gè)服務(wù)實(shí)例，請(qǐng)求被均勻分發(fā)，那么每個(gè)實(shí)例可能只看到20個(gè)請(qǐng)求，都會(huì)誤認(rèn)為‘遠(yuǎn)未達(dá)到閾值’，從而輕松放行。但從全局看，該用戶實(shí)際上已經(jīng)發(fā)起了100個(gè)請(qǐng)求。如果負(fù)載均衡策略變化，或者流量分布不均，限流效果就完全不可控了。所以，這種方案只適用于單體應(yīng)用，或者能容忍限流精度嚴(yán)重偏差的場(chǎng)景。”

(2) 專用服務(wù)限流

第二種方案是限流器作為獨(dú)立微服務(wù)部署在客戶端與應(yīng)用服務(wù)器之間。當(dāng)應(yīng)用服務(wù)收到請(qǐng)求后，先向這個(gè)限流服務(wù)發(fā)起一次RPC或HTTP調(diào)用，詢問：‘用戶A的這次請(qǐng)求是否允許？’限流服務(wù)維護(hù)著一個(gè)集中的計(jì)數(shù)器，返回‘允許’或‘拒絕’。”

這種架構(gòu)非常靈活。應(yīng)用服務(wù)可以傳遞豐富的業(yè)務(wù)上下文給限流服務(wù)，比如用戶的會(huì)員等級(jí)、賬戶狀態(tài)等，從而實(shí)現(xiàn)復(fù)雜的動(dòng)態(tài)限流邏輯，比如“周五期間允許額外請(qǐng)求”這類復(fù)雜業(yè)務(wù)邏輯。還可以為系統(tǒng)不同部分配置獨(dú)立的限流服務(wù)，各自針對(duì)特定需求進(jìn)行調(diào)優(yōu)。最重要的是，由于狀態(tài)是集中管理的，限流的精度非常高。

不過，它的缺點(diǎn)也很明顯。首先是延遲，每次業(yè)務(wù)請(qǐng)求都憑空增加了一次網(wǎng)絡(luò)往返。即使限流服務(wù)響應(yīng)很快（比如10ms），在高并發(fā)下，累積的延遲也是非?？捎^的。其次，我們引入了一個(gè)新的單點(diǎn)故障風(fēng)險(xiǎn)。如果限流服務(wù)掛了，我們必須做出選擇：是‘故障開放’（fail-open），放行所有流量，可能壓垮后端；還是‘故障關(guān)閉’（fail-closed），拒絕所有請(qǐng)求，導(dǎo)致整個(gè)API不可用？這兩種選擇都很難接受。最后，運(yùn)維復(fù)雜度也增加了。”

(3) API網(wǎng)關(guān)/負(fù)載均衡器層

“綜合考慮，最優(yōu)的方案是將限流邏輯前置，集成在系統(tǒng)的入口層，比如API網(wǎng)關(guān)或負(fù)載均衡器上。所有外部請(qǐng)求在到達(dá)任何應(yīng)用服務(wù)之前，必須先經(jīng)過這一層。網(wǎng)關(guān)根據(jù)請(qǐng)求信息（如IP、請(qǐng)求頭、API密鑰）應(yīng)用限流規(guī)則，直接決定是轉(zhuǎn)發(fā)給后端，還是立即返回HTTP 429?！?/p>

這種方法是生產(chǎn)系統(tǒng)中最主流的做法，因?yàn)樗拍詈?jiǎn)單且提供了強(qiáng)大的保護(hù)。應(yīng)用服務(wù)器永遠(yuǎn)不會(huì)看到被阻止的請(qǐng)求，因此它們可以完全專注于處理合法流量。

當(dāng)然，它也有局限性，主要在于上下文信息有限。網(wǎng)關(guān)層通常只能獲取到HTTP請(qǐng)求本身的信息，很難感知到深層次的業(yè)務(wù)邏輯。例如，要實(shí)現(xiàn)‘高級(jí)會(huì)員享受10倍限額’這樣的規(guī)則，就需要會(huì)員狀態(tài)信息能通過JWT令牌等方式傳遞到網(wǎng)關(guān)層。

另一個(gè)關(guān)鍵問題是限流狀態(tài)的存儲(chǔ)位置。網(wǎng)關(guān)需要快速訪問計(jì)數(shù)器和時(shí)間戳，這通常意味著要使用 Redis 這類內(nèi)存存儲(chǔ)。但這樣會(huì)引入外部依賴，還需要處理 Redis 響應(yīng)緩慢或不可用的情況。

經(jīng)過上面三種方案的分析，雖然各有其局限性，但是綜合來看。我們還是要選擇更優(yōu)的第三種方案，在API網(wǎng)關(guān)/負(fù)載均衡器層實(shí)現(xiàn)限流。你可以這樣回復(fù)面試官：

“面試官，綜合以上分析，我選擇方案三，在API網(wǎng)關(guān)層實(shí)現(xiàn)限流。 這是業(yè)界最成熟的模式，既能實(shí)現(xiàn)集中控制，又避免了為每個(gè)請(qǐng)求增加額外的網(wǎng)絡(luò)調(diào)用開銷?！?/p>

2. 如何識(shí)別客戶端？

在確定了限流器在架構(gòu)中的位置之后，現(xiàn)在我們需要專注下一個(gè)問題：如何識(shí)別客戶端？這兩個(gè)決策相互關(guān)聯(lián)——部署位置的選擇會(huì)影響你能輕松獲取哪些客戶端信息，而識(shí)別策略又會(huì)影響限流器的合理部署位置。

由于我們選擇了 API 網(wǎng)關(guān)的方法，我們的限流器只能訪問 HTTP 請(qǐng)求本身中的信息。這包括請(qǐng)求的 URL/路徑、所有 HTTP 頭（如 Authorization、User-Agent、X-API-Key 等）、查詢參數(shù)以及客戶端的 IP 地址。雖然我們理論上可以對(duì)外部數(shù)據(jù)庫(kù)或其他服務(wù)進(jìn)行調(diào)用，但這會(huì)增加我們希望避免的延遲，因此我們將堅(jiān)持使用請(qǐng)求本身的信息。

我們首先需要確定什么使“客戶端”具有唯一性。我們使用的鍵決定了如何應(yīng)用限制。我們有三個(gè)主要選項(xiàng)：

• 用戶 ID：適用于經(jīng)過身份驗(yàn)證的 API。每個(gè)登錄用戶都有自己的速率限制配額。這通常以 JWT 令牌的形式出現(xiàn)在 Authorization 頭中。
• IP 地址：適用于公共 API 或沒有用戶賬戶的情況。但需注意 NAT 后或企業(yè)防火墻內(nèi)的用戶。IP 地址通常出現(xiàn)在 X-Forwarded-For 請(qǐng)求頭中。
• API 密鑰：開發(fā)者 API 常用方式。每個(gè)密鑰持有者擁有獨(dú)立限額。最常見的是通過 X-API-Key 請(qǐng)求頭進(jìn)行標(biāo)識(shí)。

到了這一步，面試官很可能會(huì)提問：所有用戶都經(jīng)過身份驗(yàn)證嗎？這是一個(gè)需要 API 密鑰的開發(fā)者 API 嗎？等等。

在實(shí)際應(yīng)用中，你可能需要結(jié)合多種限制。也許已認(rèn)證用戶比匿名 IP 獲得更高的限制，而高級(jí)用戶可能獲得更多。這反映了真實(shí)系統(tǒng)不僅執(zhí)行全局限制，還疊加多層規(guī)則。例如：

• 每個(gè)用戶的限制：“小明每小時(shí)可以發(fā)出 1000 次請(qǐng)求”
• 單 IP 限制："該 IP 每分鐘可發(fā)起 100 次請(qǐng)求"
• 全局限制："我們的 API 每秒總共可處理 50,000 次請(qǐng)求"
• 端點(diǎn)特定限制：“搜索 API 限制為每分鐘 10 次請(qǐng)求，但個(gè)人資料更新為每分鐘 100 次”

你的限流器需要檢查所有適用的規(guī)則，并執(zhí)行最嚴(yán)格的那個(gè)。如果小明已經(jīng)使用了他 1000 次請(qǐng)求中的 50 次，但他的 IP 地址已經(jīng)達(dá)到了 100 次請(qǐng)求的限制，他就會(huì)被阻止。

3. 限流算法選定

面試官：“OK，部署在API網(wǎng)關(guān)是個(gè)合理的選擇?，F(xiàn)在我們來聊聊最核心的部分：你打算用什么算法來決定一個(gè)請(qǐng)求是否應(yīng)該被放行？”

這是設(shè)計(jì)的靈魂所在。你需要展示你對(duì)不同算法的理解，并能根據(jù)場(chǎng)景做出權(quán)衡。

“限流算法主要有四種，它們?cè)诰取①Y源消耗和實(shí)現(xiàn)復(fù)雜度上各有千秋。我們可以逐一分析?！?/p>

(1) 固定窗口計(jì)數(shù)器

最簡(jiǎn)單的方法是將時(shí)間劃分為固定窗口（如 1 分鐘的時(shí)間段），并在每個(gè)窗口中計(jì)數(shù)請(qǐng)求。對(duì)于每個(gè)用戶，我們會(huì)維護(hù)一個(gè)在每個(gè)新窗口開始時(shí)重置為零的計(jì)數(shù)器。如果在某個(gè)窗口內(nèi)計(jì)數(shù)器超過限制，則拒絕新的請(qǐng)求，直到窗口重置。

例如，在每分鐘 100 次請(qǐng)求的限制下，時(shí)間窗口可能劃分為 12:00:00-12:00:59、12:01:00-12:01:59 等。用戶在每個(gè)窗口期內(nèi)可以發(fā)起 100 次請(qǐng)求，之后必須等待下一個(gè)窗口開啟。

實(shí)現(xiàn)起來非常簡(jiǎn)單。只需使用一個(gè)哈希表，將客戶端 ID 映射到（計(jì)數(shù)器，窗口起始時(shí)間）這對(duì)值即可。

{
  "alice:12:00:00": 100,
  "alice:12:01:00": 5,
  "bob:12:00:00": 20,
  "charlie:12:00:00": 0,
  "dave:12:00:00": 54,
  "eve:12:00:00": 0,
  "frank:12:00:00": 12,
}

這種算法實(shí)現(xiàn)簡(jiǎn)單，但缺點(diǎn)在于窗口邊界的臨界問題。比如：限流閥值為每秒5個(gè)請(qǐng)求，單位時(shí)間窗口為1秒。如果在前0.5秒到1秒的時(shí)間內(nèi)并發(fā)5個(gè)請(qǐng)求，接著在1秒到1.5秒的時(shí)間內(nèi)又并發(fā)5個(gè)請(qǐng)求。雖然這兩個(gè)時(shí)間段各自都沒有超過限流閾值，但如果計(jì)算0.5秒到1.5秒的總請(qǐng)求數(shù)，則總共是10個(gè)請(qǐng)求，已經(jīng)遠(yuǎn)遠(yuǎn)超過了1秒內(nèi)不超過5個(gè)請(qǐng)求的限流標(biāo)準(zhǔn)。

(2) 滑動(dòng)窗口計(jì)數(shù)

滑動(dòng)窗口正是為了解決固定窗口的臨界問題而生的。它將一個(gè)大的時(shí)間窗口（比如1分鐘）分割成更小粒度的子窗口（比如60個(gè)1秒的子窗口）。每次請(qǐng)求到來，當(dāng)前子窗口的計(jì)數(shù)器加一。當(dāng)整個(gè)大窗口向右滑動(dòng)時(shí)，它會(huì)丟棄掉最左邊的子窗口的計(jì)數(shù)值，并納入一個(gè)新的子窗口。整個(gè)大窗口的請(qǐng)求總數(shù)，就是所有子窗口計(jì)數(shù)器的總和。通過這種更平滑的窗口移動(dòng)方式，滑動(dòng)窗口避免了固定窗口在邊界上的突刺問題，使得限流控制更加精確。

雖然滑動(dòng)窗口可以一定程度上解決窗口臨界流量已出問題，但是因?yàn)榛瑒?dòng)窗口本質(zhì)其實(shí)是將窗口粒度更小，但是        不管多小，仍然是以窗口來限制，所以總會(huì)存在流量不均導(dǎo)致的限流不準(zhǔn)確問題

假設(shè)窗口以0.5s為小周期移動(dòng)，如下圖，在【0.5s，1.5s】，【1.5s，2.5s】間其實(shí)都是合理的，不會(huì)有流量超出，但是其實(shí)在【0.8s，1.8s】間就有10個(gè)請(qǐng)求了，并沒有達(dá)到限流效果

(3) 漏斗桶

漏斗限流算法的核心思想是將請(qǐng)求存儲(chǔ)在一個(gè)漏斗中，漏斗以固定的速率漏出請(qǐng)求。如果漏斗被填滿，新到達(dá)的請(qǐng)求將被丟棄。請(qǐng)求可以以以不定的速率流入漏桶，而漏桶以固定的速率流出，所以漏斗算法可以將突發(fā)流量均勻地配，確保系統(tǒng)在穩(wěn)定的負(fù)載下運(yùn)行

但是這種方式同樣存在以下兩個(gè)問題：

• 無法動(dòng)態(tài)調(diào)整流量：漏斗的漏出速率是固定的，不夠靈活，無法根據(jù)實(shí)際流量情況進(jìn)行動(dòng)態(tài)調(diào)整。
• 突發(fā)流量處理有限：在突發(fā)流量過大的情況下，漏斗可能很快被填滿，大量請(qǐng)求將被拒絕，可能會(huì)導(dǎo)致服務(wù)質(zhì)量下降。

(4) 令牌桶（推薦）

想象每個(gè)客戶端都有一個(gè)桶，可以容納一定數(shù)量的令牌（突發(fā)容量）。令牌以穩(wěn)定的速率（補(bǔ)充速率）被添加到桶中。每個(gè)請(qǐng)求會(huì)消耗一個(gè)令牌。如果沒有可用的令牌，請(qǐng)求就會(huì)被拒絕。

例如，一個(gè)桶可能容納 100 個(gè)令牌（允許最多 100 個(gè)請(qǐng)求的突發(fā)），并以每分鐘 10 個(gè)令牌的速度補(bǔ)充（穩(wěn)定速率為每分鐘 10 個(gè)請(qǐng)求）?？蛻舳丝梢粤⒓窗l(fā)出 100 個(gè)請(qǐng)求，然后必須等待令牌補(bǔ)充。

該算法既能處理持續(xù)負(fù)載（通過補(bǔ)充速率控制），又能應(yīng)對(duì)臨時(shí)突發(fā)流量（通過桶容量控制）。實(shí)現(xiàn)也很簡(jiǎn)單，只需為每個(gè)客戶端記錄（令牌數(shù)，最后補(bǔ)充時(shí)間）。難點(diǎn)在于選擇合適的桶容量和補(bǔ)充速率，以及處理"冷啟動(dòng)"場(chǎng)景——閑置客戶端重新激活時(shí)會(huì)擁有滿桶令牌。

所以這里，選用令牌桶算法是最合適的。它在簡(jiǎn)潔性、內(nèi)存效率和處理真實(shí)流量模式之間取得了最佳平衡，既能適應(yīng) API 流量的突發(fā)特性，又能嚴(yán)格執(zhí)行整體速率限制。

這里面試官又可能會(huì)問了，“令牌桶確實(shí)是不錯(cuò)的選擇。但我們有百萬QPS，這么多用戶的令牌桶狀態(tài)，應(yīng)該存放在哪里？如果存在各個(gè)網(wǎng)關(guān)實(shí)例的內(nèi)存里，不又回到進(jìn)程內(nèi)限流的老問題了嗎？”

此時(shí)你就可以從容的想面試官介紹接下來更深入的設(shè)計(jì)了：

“您提到了關(guān)鍵。這個(gè)狀態(tài)必須是集中存儲(chǔ)和共享的。對(duì)于這種對(duì)性能要求極高、且數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單的場(chǎng)景，Redis 是不二之選。它是一個(gè)高性能的內(nèi)存數(shù)據(jù)庫(kù)，所有API網(wǎng)關(guān)實(shí)例都可以訪問它，作為我們令牌桶狀態(tài)的唯一事實(shí)來源?！?/p>

“具體實(shí)現(xiàn)上，我們可以為每個(gè)用戶在Redis中維護(hù)一個(gè)Hash結(jié)構(gòu)，存儲(chǔ)兩個(gè)關(guān)鍵信息：tokens（當(dāng)前令牌數(shù)）和last_refill_timestamp（上次補(bǔ)充令牌的時(shí)間戳）?！?/p>

“當(dāng)請(qǐng)求到達(dá)網(wǎng)關(guān)時(shí)，流程如下：

• 網(wǎng)關(guān)根據(jù)用戶ID，用HMGET從Redis獲取該用戶的令牌桶狀態(tài)。
• 在網(wǎng)關(guān)內(nèi)存中，根據(jù)當(dāng)前時(shí)間與last_refill_timestamp的時(shí)間差，以及令牌生成速率，計(jì)算出這段時(shí)間應(yīng)該補(bǔ)充多少新令牌，更新本地的令牌數(shù)（但不能超過桶容量）。
• 判斷更新后的令牌數(shù)是否大于等于1。如果是，則請(qǐng)求允許通過，并將令牌數(shù)減1；如果否，則拒絕請(qǐng)求。
• 將更新后的令牌數(shù)和當(dāng)前時(shí)間戳，用HSET寫回Redis?！?/li>

厲害的面試官很容易發(fā)現(xiàn)這里還有問題，“等一下，你這個(gè)‘讀-改-寫’的流程，在分布式環(huán)境下不會(huì)有并發(fā)問題嗎？比如兩個(gè)請(qǐng)求同時(shí)到達(dá)不同的網(wǎng)關(guān)實(shí)例？

確實(shí)存在競(jìng)態(tài)條件（Race Condition）。兩個(gè)網(wǎng)關(guān)實(shí)例可能同時(shí)讀取到還剩1個(gè)令牌，都認(rèn)為可以放行，結(jié)果就是多放行了一個(gè)請(qǐng)求。雖然Redis的MULTI/EXEC事務(wù)可以保證寫的原子性，但讀操作在事務(wù)之外，無法解決這個(gè)問題。

這里我們可以引入Lua腳本，最終的解決方案是，將整個(gè)‘讀-計(jì)算-更新’的邏輯封裝成一個(gè)Lua腳本，發(fā)送給Redis執(zhí)行。Redis保證Lua腳本的執(zhí)行是原子的。這樣，整個(gè)限流決策過程就在Redis服務(wù)端一氣呵成，徹底避免了競(jìng)態(tài)條件。

MULTI
HSET 小明:bucket tokens <new_token_count>
HSET 小明:bucket last_refill <current_timestamp>
EXPIRE 小明:bucket 3600
EXEC

之后還可以在這里可以總結(jié)一下選擇Redis的原因：

• 高性能：基于內(nèi)存，簡(jiǎn)單操作可達(dá)亞毫秒級(jí)響應(yīng)。
• 原子操作：通過Lua腳本保證了并發(fā)安全。
• 高可用：支持主從復(fù)制和哨兵/集群模式。
• 自動(dòng)過期：可以利用EXPIRE命令，自動(dòng)清理長(zhǎng)時(shí)間不活躍用戶的令牌桶數(shù)據(jù)，防止內(nèi)存泄漏。”

到這里，一個(gè)基本可用的限流器就已經(jīng)設(shè)計(jì)完了，最終結(jié)果是在所有網(wǎng)關(guān)實(shí)例中實(shí)現(xiàn)精確、一致的速率限制。無論小明的第 100 個(gè)請(qǐng)求發(fā)送到網(wǎng)關(guān) A、B 還是 C，它們都能看到相同的令牌桶狀態(tài)并執(zhí)行相同的限制。

五、擴(kuò)展性設(shè)計(jì)：邁向百萬QPS

面試官：“方案很完善。但我們最初的目標(biāo)是百萬QPS。單個(gè)Redis實(shí)例，即使性能再好，恐怕也扛不住這么大的流量吧？”

單個(gè)Redis實(shí)例的處理能力通常在10萬QPS級(jí)別，無法滿足100萬QPS的目標(biāo)。因此，我們必須對(duì)Redis進(jìn)行水平擴(kuò)展，也就是部署一個(gè)Redis集群。

1. 如何擴(kuò)展Redis？

我們需要將海量的用戶令牌桶數(shù)據(jù)，分散到多個(gè)Redis實(shí)例上。關(guān)鍵在于分片（Sharding）。

我們可以采用一致性哈希算法。當(dāng)一個(gè)請(qǐng)求到來時(shí)，網(wǎng)關(guān)提取客戶端標(biāo)識(shí)(UserID、IP或API Key)，這里，對(duì)于認(rèn)證用戶，我們對(duì)其用戶 ID 進(jìn)行哈希以確定存儲(chǔ)其速率限制數(shù)據(jù)的 Redis 分片。對(duì)于匿名用戶，我們對(duì)其 IP 地址進(jìn)行哈希處理。對(duì)于 API 密鑰請(qǐng)求，我們則對(duì) API 密鑰進(jìn)行哈希。

通過一致性哈希算法計(jì)算出該標(biāo)識(shí)應(yīng)該路由到哪個(gè)Redis分片。這樣可以保證同一個(gè)客戶端的所有請(qǐng)求，始終命中同一個(gè)Redis實(shí)例，確保其限流狀態(tài)的完整性?！?/p>

在生產(chǎn)環(huán)境中，我們通常會(huì)直接使用Redis Cluster方案。它內(nèi)置了數(shù)據(jù)分片邏輯（通過16384個(gè)哈希槽），API網(wǎng)關(guān)只需要連接到集群，客戶端庫(kù)會(huì)自動(dòng)處理請(qǐng)求到正確節(jié)點(diǎn)的路由，無需我們自己實(shí)現(xiàn)復(fù)雜的一致性哈希邏輯。假設(shè)我們部署10個(gè)Redis分片，每個(gè)分片承載10萬QPS，理論上就能達(dá)到100萬QPS的目標(biāo)。

2. 如何保證高可用？

現(xiàn)在我們有了多個(gè)Redis分片，每個(gè)分片都成了系統(tǒng)的關(guān)鍵依賴。如果任何一個(gè)分片宕機(jī)，所有速率限制數(shù)據(jù)存儲(chǔ)在該分片上的用戶將失去速率限制功能。這會(huì)導(dǎo)致可用性問題，如果用戶在無法獲得正確的速率限制響應(yīng)時(shí)開始積極重試，還可能引發(fā)級(jí)聯(lián)故障。我們需要對(duì)故障模式做出根本性決策：關(guān)閉故障還是開放故障？

面試官：“那當(dāng)一個(gè)Redis分片不可用時(shí)，你選擇故障開放還是故障關(guān)閉？”

這是一個(gè)經(jīng)典的取舍問題。

• 故障關(guān)閉（Fail-Closed）：當(dāng)無法連接Redis時(shí)，拒絕所有未知狀態(tài)的請(qǐng)求。這能最大限度地保護(hù)后端系統(tǒng)，但會(huì)犧牲可用性，可能在限流組件故障時(shí)導(dǎo)致API整體不可用。
• 故障開放（Fail-Open）：當(dāng)無法連接Redis時(shí)，放行所有請(qǐng)求。這能保證API的可用性，但犧牲了保護(hù)作用，可能在流量洪峰時(shí)因失去限流而導(dǎo)致整個(gè)后端系統(tǒng)雪崩。

對(duì)于我們這個(gè)社交媒體平臺(tái)，限流失敗往往和流量激增同時(shí)發(fā)生（比如熱點(diǎn)事件）。在這種情況下，保護(hù)后端系統(tǒng)是第一要?jiǎng)?wù)。因此，我會(huì)選擇故障關(guān)閉。短暫地拒絕一部分請(qǐng)求，遠(yuǎn)比整個(gè)平臺(tái)崩潰的代價(jià)要小。”

當(dāng)然，選擇故障模式只是兜底策略。更重要的是通過高可用設(shè)計(jì)來避免故障。標(biāo)準(zhǔn)的做法是為每個(gè)Redis分片配置主從復(fù)制（Master-Slave Replication）。每個(gè)主節(jié)點(diǎn)都有一個(gè)或多個(gè)從節(jié)點(diǎn)實(shí)時(shí)同步數(shù)據(jù)。當(dāng)主節(jié)點(diǎn)故障時(shí)，可以自動(dòng)或手動(dòng)進(jìn)行故障轉(zhuǎn)移（Failover），將一個(gè)從節(jié)點(diǎn)提升為新的主節(jié)點(diǎn)。Redis Sentinel或Redis Cluster本身就提供了強(qiáng)大的高可用和故障轉(zhuǎn)移能力?！?/p>

3. 如何最小化延遲？

每次限速檢查都需要與 Redis 進(jìn)行一次網(wǎng)絡(luò)往返，這會(huì)增加用戶請(qǐng)求的延遲。盡管 Redis 操作通常在亞毫秒級(jí)別，但網(wǎng)絡(luò)開銷每請(qǐng)求可能增加幾毫秒。在每秒 100 萬次請(qǐng)求的情況下，這種延遲可能會(huì)成為一個(gè)問題。

這里我們主要有兩種優(yōu)化手段：

• 連接池：API網(wǎng)關(guān)與Redis之間維護(hù)一個(gè)持久的連接池，避免為每個(gè)請(qǐng)求都重新建立TCP連接，從而省去握手帶來的開銷。
• 地理就近部署：將API網(wǎng)關(guān)和Redis集群部署在同一個(gè)數(shù)據(jù)中心或可用區(qū)內(nèi)，確保極低的網(wǎng)絡(luò)延遲。對(duì)于全球化的服務(wù)，可以在全球多個(gè)Region部署多套限流設(shè)施，通過DNS等方式將用戶路由到最近的接入點(diǎn)。

當(dāng)然還有一種優(yōu)化手段，那就是本地緩存的方式，但是這里可能會(huì)存在一個(gè)本地緩存和redis緩存的一致性問題。當(dāng)出現(xiàn)不一致的時(shí)候，陳舊的緩存數(shù)據(jù)可能導(dǎo)致不正確的速率限制決策。通常來說，前兩項(xiàng)優(yōu)化基本上可以滿足一般的業(yè)務(wù)需求了

4. 如何處理熱點(diǎn)問題？

面試官：“如果某個(gè)用戶（比如一個(gè)爬蟲或一個(gè)熱門應(yīng)用的后端服務(wù)）請(qǐng)求量特別大，把分配給它的那個(gè)Redis分片打滿了，怎么辦？”

這是一個(gè)典型的熱點(diǎn)Key問題。單個(gè)客戶端的請(qǐng)求壓垮一個(gè)分片，這通常意味著濫用行為或設(shè)計(jì)不當(dāng)?shù)暮戏蛻舳恕?/p>

• 針對(duì)濫用流量：我們可以設(shè)計(jì)一個(gè)‘自動(dòng)拉黑’機(jī)制。當(dāng)一個(gè)客戶端在短時(shí)間內(nèi)持續(xù)觸發(fā)限流（例如，一分鐘內(nèi)觸發(fā)10次），就自動(dòng)將其IP或API Key加入一個(gè)臨時(shí)黑名單（也可以存在Redis里），在更上游的防火墻或網(wǎng)關(guān)層面直接拒絕其后續(xù)所有請(qǐng)求。
• 針對(duì)合法高流量客戶：可以提供更高等級(jí)的API套餐，為他們分配更高的限流閾值，甚至在物理上將他們路由到專用的、資源更豐富的限流集群。同時(shí)，也應(yīng)該在API文檔和SDK中，倡導(dǎo)客戶端也實(shí)現(xiàn)合理的客戶端限流和退避策略，從源頭平滑請(qǐng)求。

5. 動(dòng)態(tài)調(diào)整規(guī)則配置

面試官：“設(shè)計(jì)得非常全面了。最后一個(gè)問題，如果運(yùn)營(yíng)同學(xué)想臨時(shí)調(diào)整某個(gè)API的限流規(guī)則，比如在大促期間提高下單接口的限制，我們總不能每次都去修改配置發(fā)版吧？”

這里就涉及到限流規(guī)則的動(dòng)態(tài)配置了，這其實(shí)是一個(gè)錦上添花的設(shè)計(jì)，如果在面試的時(shí)候你能夠考慮到，將是一個(gè)很大的加分項(xiàng)。

你可以這樣回答，“當(dāng)然不能。限流規(guī)則必須支持動(dòng)態(tài)配置。我們可以將規(guī)則存儲(chǔ)在一個(gè)外部的配置中心，比如Nacos、Apollo，或者簡(jiǎn)單的數(shù)據(jù)庫(kù)表中。API網(wǎng)關(guān)實(shí)例會(huì)訂閱這些配置的變更。

訂閱的方式主要有以下兩種：

• 拉（Pull）模式：網(wǎng)關(guān)定時(shí)去配置中心拉取最新的規(guī)則，緩存在本地內(nèi)存。這種方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，配置服務(wù)可以簡(jiǎn)單到只是一個(gè)數(shù)據(jù)庫(kù)表。但配置更新有延遲，在更改規(guī)則和該規(guī)則在所有網(wǎng)關(guān)中生效之間總存在一個(gè)時(shí)間窗口。如果由于攻擊需要緊急降低限制，您可能需要等待長(zhǎng)達(dá) 30 秒才能使更改傳播。對(duì)于大多數(shù)操作場(chǎng)景，這種延遲是可以接受的，但在緊急情況下可能會(huì)出現(xiàn)問題。
• 推（Push）-based：網(wǎng)關(guān)與配置中心建立長(zhǎng)連接。一旦配置發(fā)生變更，配置中心會(huì)主動(dòng)將新規(guī)則推送給所有網(wǎng)關(guān)實(shí)例。這種方式實(shí)時(shí)性最好，但架構(gòu)更復(fù)雜。需要額外處理連接故障、確保所有網(wǎng)關(guān)都能接收更新，并應(yīng)對(duì)部分網(wǎng)關(guān)更新成功而其他網(wǎng)關(guān)失敗的場(chǎng)景。當(dāng)推送系統(tǒng)不可用時(shí)，還需要設(shè)計(jì)回退機(jī)制。

對(duì)于大多數(shù)場(chǎng)景，基于輪詢的‘拉模式’（比如每30秒拉一次）已經(jīng)足夠。如果對(duì)實(shí)時(shí)性要求極高，可以選擇基于推送的方案。”

六、小結(jié)

到這里，一個(gè)百萬QPS限流系統(tǒng)的設(shè)計(jì)差不多就完成了。

回顧我們的整個(gè)設(shè)計(jì)過程，這個(gè)方案有什么特點(diǎn)？首先是需求驅(qū)動(dòng)的設(shè)計(jì)思路，我們沒有一上來就談技術(shù)，而是先搞清楚要解決什么問題。其次是技術(shù)選型的權(quán)衡邏輯，每一個(gè)關(guān)鍵決策點(diǎn)都有充分的對(duì)比分析，比如為什么選API網(wǎng)關(guān)部署、為什么用令牌桶算法、為什么用Redis集群。最后是對(duì)非功能性需求的關(guān)注，不僅要功能正確，還要考慮性能、可用性、可運(yùn)維性等工程實(shí)踐問題。

面試官看重的是什么？不是你背了多少技術(shù)名詞，而是你能不能把一個(gè)模糊的問題變成清晰的解決方案。當(dāng)你展示出這種結(jié)構(gòu)化思考和全局權(quán)衡的能力時(shí)，就證明了你具備處理復(fù)雜系統(tǒng)問題的潛質(zhì)。