阿里架構師深度剖析：微服務介面鑑許可權流背後的資料結構和演算法

微服務是最近幾年才興起的概念。簡單點講，就是把複雜的大應用，解耦拆分成幾個小的應用。這樣做的好處有很多。比如，這樣有利於團隊組織架構的拆分，畢竟團隊越大協作的難度越大；再比如，每個應用都可以獨立運維，獨立擴容，獨立上線，各個應用之間互不影響。不用像原來那樣，一個小功能上線，整個大應用都要重新發布。

不過，有利就有弊。大應用拆分成微服務之後，服務之間的呼叫關係變得更復雜，平臺的整體複雜熵升高，出錯的機率、debug 問題的難度都高了好幾個數量級。所以，為了解決這些問題，服務治理便成了微服務的一個技術重點。

所謂服務治理，簡單點講，就是管理微服務，保證平臺整體正常、平穩地執行。服務治理涉及的內容比較多，比如鑑權、限流、降級、熔斷、監控告警等等。這些服務治理功能的實現，底層依賴大量的資料結構和演算法。今天，我就拿其中的鑑權和限流這兩個功能，來帶你看看，它們的實現過程中都要用到哪些資料結構和演算法。

鑑權背景介紹

以防你之前可能對微服務沒有太多瞭解，所以我對鑑權的背景做了簡化。

假設我們有一個微服務叫使用者服務（User Service）。它提供很多使用者相關的介面，比如獲取使用者資訊、註冊、登入等，給公司內部的其他應用使用。但是，並不是公司內部所有應用，都可以訪問這個使用者服務，也並不是每個有訪問許可權的應用，都可以訪問使用者服務的所有介面。

我舉了一個例子給你講解一下，你可以看我畫的這幅圖。這裡面，只有 A、B、C、D 四個應用可以訪問使用者服務，並且，每個應用只能訪問使用者服務的部分介面。

要實現介面鑑權功能，我們需要事先將應用對介面的訪問許可權規則設定好。當某個應用訪問其中一個介面的時候，我們就可以拿應用的請求 URL，在規則中進行匹配。如果匹配成功，就說明允許訪問；如果沒有可以匹配的規則，那就說明這個應用沒有這個介面的訪問許可權，我們就拒絕服務。

如何實現快速鑑權？

介面的格式有很多，有類似 Dubbo 這樣的 RPC 介面，也有類似 Spring Cloud 這樣的HTTP 介面。不同介面的鑑權實現方式是類似的，我這裡主要拿 HTTP 介面給你講解。

鑑權的原理比較簡單、好理解。那具體到實現層面，我們該用什麼資料結構來儲存規則呢？使用者請求 URL 在規則中快速匹配，又該用什麼樣的演算法呢？

實際上，不同的規則和匹配模式，對應的資料結構和匹配演算法也是不一樣的。所以，關於這個問題，我繼續細化為三個更加詳細的需求給你講解。

1。如何實現精確匹配規則？

我們先來看最簡單的一種匹配模式。只有當請求 URL 跟規則中配置的某個介面精確匹配時，這個請求才會被接受、處理。為了方便你理解，我舉了一個例子，你可以看一下。

不同的應用對應不同的規則集合。我們可以採用散列表來儲存這種對應關係。我這裡著重講下，每個應用對應的規則集合，該如何儲存和匹配。

針對這種匹配模式，我們可以將每個應用對應的許可權規則，儲存在一個字串陣列中。當用戶請求到來時，我們拿使用者的請求 URL，在這個字串陣列中逐一匹配，匹配的演算法就是我們之前學過的字串匹配演算法（比如 KMP、BM、BF 等）。

規則不會經常變動，所以，為了加快匹配速度，我們可以按照字串的大小給規則排序，把它組織成有序陣列這種資料結構。當要查詢某個 URL 能否匹配其中某條規則的時候，我們可以採用二分查詢演算法，在有序陣列中進行匹配。

而二分查詢演算法的時間複雜度是 O（logn）（n 表示規則的個數），這比起時間複雜度是O（n）的順序遍歷快了很多。對於規則中介面長度比較長，並且鑑權功能呼叫量非常大的情況，這種最佳化方法帶來的效能提升還是非常可觀的。

2。如何實現字首匹配規則？

我們再來看一種稍微複雜的匹配模式。只要某條規則可以匹配請求 URL 的字首，我們就說這條規則能夠跟這個請求 URL 匹配。同樣，為了方便你理解這種匹配模式，我還是舉一個例子說明一下。

不同的應用對應不同的規則集合。我們採用散列表來儲存這種對應關係。我著重講一下，每個應用的規則集合，最適合用什麼樣的資料結構來儲存。

之前剖析Trie樹的文章中，就講過，Trie 樹非常適合用來做字首匹配。所以，針對這個需求，我們可以將每個使用者的規則集合，組織成 Trie 樹這種資料結構。

不過，Trie 樹中的每個節點不是儲存單個字元，而是儲存介面被“/”分割之後的子目錄（比如“/user/name”被分割為“user”“name”兩個子目錄）。因為規則並不會經常變動，所以，在 Trie 樹中，我們可以把每個節點的子節點們，組織成有序陣列這種資料結構。當在匹配的過程中，我們可以利用二分查詢演算法，決定從一個節點應該跳到哪一個子節點。

3。如何實現模糊匹配規則？

如果我們的規則更加複雜，規則中包含萬用字元，比如“*

”表示匹配任意多個子目錄，“

”表示匹配任意一個子目錄。只要使用者請求 URL 可以跟某條規則模糊匹配，我們就說這條規則適用於這個請求。為了方便你理解，我舉一個例子來解釋一下。

不同的應用對應不同的規則集合。我們還是採用散列表來儲存這種對應關係。這點我們剛才講過了，這裡不再重複說了。我們著重看下，每個使用者對應的規則集合，該用什麼資料結構來儲存？針對這種包含萬用字元的模糊匹配，我們又該使用什麼演算法來實現呢？

還記得剖析回溯演算法的文章中講的正則表示式的例子嗎？我們可以藉助正則表示式那個例子的解決思路，來解決這個問題。我們採用回溯演算法，拿請求 URL 跟每條規則逐一進行模糊匹配。如何用回溯演算法進行模糊匹配，這部分我就不重複講了。

不過，這個解決思路的時間複雜度是非常高的。我們需要拿每一個規則，跟請求 URL 匹配一遍。那有沒有辦法可以繼續最佳化一下呢？

實際上，我們可以結合實際情況，挖掘出這樣一個隱形的條件，那就是，並不是每條規則都包含萬用字元，包含萬用字元的只是少數。於是，我們可以把不包含萬用字元的規則和包含萬用字元的規則分開處理。

我們把不包含萬用字元的規則，組織成有序陣列或者 Trie 樹（具體組織成什麼結構，視具體的需求而定，是精確匹配，就組織成有序陣列，是字首匹配，就組織成 Trie 樹），而這一部分匹配就會非常高效。剩下的是少數包含萬用字元的規則，我們只要把它們簡單儲存在一個數組中就可以了。儘管匹配起來會比較慢，但是畢竟這種規則比較少，所以這種方法也是可以接受的。

當接收到一個請求 URL 之後，我們可以先在不包含萬用字元的有序陣列或者 Trie 樹中查詢。如果能夠匹配，就不需要繼續在萬用字元規則中匹配了；如果不能匹配，就繼續在萬用字元規則中查詢匹配。

限流背景介紹

講完了鑑權的實現思路，我們再來看一下限流。

所謂限流，顧名思義，就是對介面呼叫的頻率進行限制。比如每秒鐘不能超過 100 次呼叫，超過之後，我們就拒絕服務。限流的原理聽起來非常簡單，但它在很多場景中，發揮著重要的作用。比如在秒殺、大促、雙 11、618 等場景中，限流已經成為了保證系統平穩執行的一種標配的技術解決方案。

按照不同的限流粒度，限流可以分為很多種型別。比如給每個介面限制不同的訪問頻率，或者給所有介面限制總的訪問頻率，又或者更細粒度地限制某個應用對某個介面的訪問頻率等等。

不同粒度的限流功能的實現思路都差不多，所以，我今天主要針對限制所有介面總的訪問頻率這樣一個限流需求來講解。其他粒度限流需求的實現思路，你可以自己思考。

如何實現精準限流？

最簡單的限流演算法叫固定時間視窗限流演算法。這種演算法是如何工作的呢？首先我們需要選定一個時間起點，之後每當有介面請求到來，我們就將計數器加一。如果在當前時間視窗內，根據限流規則（比如每秒鐘最大允許 100 次訪問請求），出現累加訪問次數超過限流值的情況時，我們就拒絕後續的訪問請求。當進入下一個時間視窗之後，計數器就清零重新計數。

這種基於固定時間視窗的限流演算法的缺點是，限流策略過於粗略，無法應對兩個時間視窗臨界時間內的突發流量。這是怎麼回事呢？我舉一個例子給你解釋一下。

假設我們的限流規則是，每秒鐘不能超過 100 次介面請求。第一個 1s 時間視窗內，100次介面請求都集中在最後 10ms 內。在第二個 1s 的時間視窗內，100 次介面請求都集中在最開始的 10ms 內。雖然兩個時間視窗內流量都符合限流要求（≤100 個請求），但在兩個時間視窗臨界的 20ms 內，會集中有 200 次介面請求。固定時間視窗限流演算法並不能對這種情況做限制，所以，集中在這 20ms 內的 200 次請求就有可能壓垮系統。

為了解決這個問題，我們可以對固定時間視窗限流演算法稍加改造。我們可以限制任意時間視窗（比如 1s）內，介面請求數都不能超過某個閾值（比如 100 次）。因此，相對於固定時間視窗限流演算法，這個演算法叫

滑動時間視窗限流演算法

。

流量經過滑動時間視窗限流演算法整形之後，可以保證任意一個 1s 的時間視窗內，都不會超過最大允許的限流值，從流量曲線上來看會更加平滑。那具體到實現層面，我們該如何來做呢？

我們假設限流的規則是，在任意 1s 內，介面的請求次數都不能大於 K 次。我們就維護一個大小為 K+1 的迴圈佇列，用來記錄 1s 內到來的請求。注意，這裡迴圈佇列的大小等於限流次數加一，因為迴圈佇列儲存資料時會浪費一個儲存單元。

當有新的請求到來時，我們將與這個新請求的時間間隔超過 1s 的請求，從佇列中刪除。然後，我們再來看迴圈佇列中是否有空閒位置。如果有，則把新請求儲存在佇列尾部（tail 指標所指的位置）；如果沒有，則說明這 1 秒內的請求次數已經超過了限流值 K，所以這個請求被拒絕服務。

為了方便你理解，我舉一個例子，給你解釋一下。在這個例子中，我們假設限流的規則是，任意 1s 內，介面的請求次數都不能大於 6 次。

即便滑動時間視窗限流演算法可以保證任意時間視窗內，介面請求次數都不會超過最大限流值，但是仍然不能防止，在細時間粒度上訪問過於集中的問題。

比如我剛剛舉的那個例子，第一個 1s 的時間視窗內，100 次請求都集中在最後 10ms 中，也就是說，基於時間視窗的限流演算法，不管是固定時間視窗還是滑動時間視窗，只能在選定的時間粒度上限流，對選定時間粒度內的更加細粒度的訪問頻率不做限制。

實際上，針對這個問題，還有很多更加平滑的限流演算法，比如令牌桶演算法、漏桶演算法等。如果感興趣，你可以自己去研究一下。

總結

今天，我們講解了跟微服務相關的介面鑑權和限流功能的實現思路。現在，我稍微總結一下。

關於鑑權，我們講了三種不同的規則匹配模式。不管是哪種匹配模式，我們都可以用散列表來儲存不同應用對應的不同規則集合。對於每個應用的規則集合的儲存，三種匹配模式使用不同的資料結構。

對於第一種精確匹配模式，我們利用有序陣列來儲存每個應用的規則集合，並且透過二分查詢和字串匹配演算法，來匹配請求 URL 與規則。對於第二種字首匹配模式，我們利用 Trie樹來儲存每個應用的規則集合。對於第三種模糊匹配模式，我們採用普通的陣列來儲存包含萬用字元的規則，透過回溯演算法，來進行請求 URL 與規則的匹配。

關於限流，我們講了兩種限流演算法，第一種是固定時間視窗限流演算法，第二種是滑動時間視窗限流演算法。對於滑動時間視窗限流演算法，我們用了之前學習過的迴圈佇列來實現。比起固定時間視窗限流演算法，它對流量的整形效果更好，流量更加平滑。

從今天的學習中，我們也可以看出，對於基礎架構工程師來說，如果不精通資料結構和演算法，我們就很難開發出效能卓越的基礎架構、中介軟體。這其實就體現了資料結構和演算法的重要性。