------ 本文是學習算法的筆記，《資料結構與算法之美》，極客時間的課程 ------
微服務簡單點說，就是把複雜的大應用，解耦拆分成幾個小的應用。這樣的好處很多，比如，有利于團隊組織架構的拆分，畢竟團隊越大協作的難度越大；每個應用也可能獨立運維，獨立擴容，獨立上線，各個應用之間互不影響。
不過，有利就有弊，大應用拆分之後，服務之間的調用關系就變得更複雜，平台整體熵升高，出錯的機率、debug問題難度都高了好幾個數量級。是以，為了解決這些問題，服務治理便成了微服務的一個技術重點。
所謂服務治理，簡單點講，就是管理微服務，保證平台整體正常、平穩地運作。服務治理涉及的内容比較多，比如鑒權、限流、降級、熔斷、監控警告等等。這些服務治理功能的實作，底層依賴大量的資料結構和算法。
鑒權前景介紹
假設我們有一個微服務叫使用者服務（User Service）。它提供很多使用者相關的接口，比如擷取使用者資訊、注冊、登入等，給公司内部的其他應用使用。但并不是公司内部所有應用，都可以通路這個使用者服務，也并不是每個有通路權限的應用，都可以通路使用者服務的所有接口。
我舉個例子，如下圖，這裡面，隻有A、B、C、D四個應用可以通路使用者服務，并且，每個應用隻能通路使用者服務的部分接口。
要實作接口鑒權功能，我們需要事先将應用對接口的通路權限規則設定好。當某個應用通路其中一個接口的時候，我們就可能拿應用的請求URL，在規則中進行比對。如果成功，就說明允許通路；如果沒有可以比對的規則，那就說明這個應用沒有這個通路權限，我們就拒絕服務。
如何實作快速鑒權
接口的格式有很多，有類似 Dubbo 這樣的 RPC 接口，了有類似 Spring Cloud 這樣的 HTTP 接口。不同的接口的鑒權實作方式是類似的，這裡主要拿 HTTP 接口來講解。
鑒權的原理比較簡單、好了解。那具體來實作層面，我們該用什麼資料結構來存儲規則呢？使用者請求URL 在規則中快速比對，又該用什麼樣的算法呢？
實際上，不同的規則和比對模式，對應的資料結構和比對算法也是不一樣的。是以，關于這個問題，細化為三個更加詳細的需求來講解。
- 如何實作精确比對規則？
我們先來看最簡單的一種比對模式。隻有當請求URL跟中配置的某個接口精确比對時，這個請求才會被接受、處理。
不同的應用對應不同的規則集合。我們可以采用散清單來存儲這種對應關系。
針對這種比對模式，我們可以将每個應用對應的權限規則，存儲在一個字元串數組中。當使用者請求到來時，我們拿使用者的請求 URL，在這個字元串數組中逐一比對，比對的算法就是我們之前學過的字元串比對算法（比如 KMP、BM、BF等）
規則不會經常變動，是以，為了加快比對速度，我們可以按字元串在大小給規則排序，把它組織成有序數組這種資料結構。當要查找某個 URL 能否比對其中某條規則的時候，我們可以優勝二分查找算法，在有序數組中進行比對。
而二分查找算法的時間複雜度是 O(logn)（n 表示規則的個數），這比起時間複雜度是 O(n)的順序周遊快了很多。對于規則中接口長度比較長，并且鑒權功能調整調用量非常大的情況，這種優化方法帶來的性能提升還是非常可觀的。
- 如何實作字首比對規則？
我們再來看一種稍微複雜的比對模式。隻要某條規則可以比對請求 URL 的字首，我們就說這條規則能夠跟這個請求 URL 比對。
不同的應用對應不同的規則集合。我們采用散清單來存儲這種對應關系。這裡着重說下，每個應用的規則集合，最适合用什麼樣的資料結構來存儲。
在Trie 樹那節，我們講過，Trie 樹非常适合用來做字首比對。是以，針對這個需求，我們可以将每個使用者的規則集合，組織成 Trie 樹這種資料結構。
不過，Trie 樹中的每個節點不是存儲單個字元，而是存儲接口被 “/” 分割之後的子目錄（比如“/user/name”被分割為 “user”，“name”兩個子目錄）。因為規則并不會經常變動，是以，在 Trie 樹中，我們可以把每個節點的子節點們，組織成有序數組這種資料結構。當在比對的過程中，我們可以利用二分查找算法，決定從一個節點應該跳到哪一個子節點。
3. 如何實作模糊比對規則？
如果我們的規則更加複雜，規則中包含通配符，比如 “**” 表示比對任意多個子目錄，“*” 表示比對任意一個子目錄。隻要使用者請求 URL可以跟某條規則模糊比對，我們就說這條規則适用于這個請求。
不同的應用對應不同的規則集合。我們仍采用散清單存儲這種對應關系。我們着重看下，每個使用者對應的規則集合，該用什麼資料結構來存儲？針對這種包含通配符的模糊比對，我們又該使用什麼算法來實作呢？
在回溯算法那節裡，正規表達式的例子。我們采用回溯算法，拿請求 URL跟每條規則逐一進行模糊比對。不過，這個解決思路的時間複雜度是非常高的。我們需要拿每一個規則，跟請求 URL 比對一遍。但實際上，并不是每條規則都包含通配符。我們可以把不含通配符的規則和含有通配符的規則分開處理。
把不含通配符的規則，組織成有序數組或者 Trie 樹（具體組織成什麼結構，視具體的需求而定，是精确比對，就組織成有序數組，是字首比對，就組織成 Trie 樹），而這一部分是非常高效。剩下的是少數包含通配符的規則，我們隻要把它們簡單的存儲在一個數組中就可以了。盡管比對越來比較慢，但畢竟這種規則比較少，是以這種方法也是可以接受的。
當接收到一個請求 URL 之後，我們可以先在不包含通配符的有序數組或者 Trie 樹中查找。如果能夠比對，就不需要繼續在通配符規則中比對了；如果不能比對，就繼續在通配符規則中查找比對。
如何實作精準限流
最簡單的限流算法叫固定時間視窗限流算法。這咱算法是如何工作的呢？首先我們需要標明一個時間起點，之後每當有接口請求到來，我們就将計數器加一。如果在目前視窗内，根據限流規則（比如每秒最大允許 100 次通路請求），出現累加通路次數超過限流值的情況時，我們就拒絕後續通路請求。當進入下一個視窗之後，計數器清零重新計數。
這種基于固定時間視窗的限流算法的缺點是，限流過于粗略，無法應對兩個時間視窗臨界時間的突發流量。這是怎麼回事呢？
假設我們的限流規則是，每秒鐘不能超過100次接口請求。第一個1s時間視窗内，100次接口請求都集中在最後10ms 内。在第二個 1s 的時間視窗内，100次接口請求都集中在最開始的 10ms 内。雖然兩個時間視窗流量都符合限流要求，但在兩個時間視窗臨界的 20 ms 内，會集中有200次接口請求。固定時間視窗限流算法并不能對這種情況做限制，是以，集中在這 20ms 内的 200 次請求就有可能壓垮系統。
為了解決這個問題，我們可以對固定時間視窗限流算法稍加改造。我們可以限制任意時間視窗（比如 1s）内，接口數都不能超過某個門檻值（比如 100次）。是以，相對于固定時間視窗限流算法，這個算法叫滑動時間視窗限流算法 。
流量經過滑動時間視窗限流算法整形之後，可以保證任意一個 1s 的時間視窗内，都不會超過最大允許的限流值，從流量曲線來看會更加平滑。
我們假設限流規則是，在任意 1s 内，接口的請求次數都不能大于 K 次。我們就可以維一個大小為 K+1 的循環隊列，用來記錄 1s 内到來的請求。注意，這裡循環隊列的大小等于限流次數加一，因為循環隊列存儲資料時會浪費一個存儲單元。
當有新的請求到來時， 我們将與這個新請求的時間間隔超過 1s 的請求，從隊列中删除。然後，我們再來看看循環隊列中是否有空閑位置。如果有，則把新的請求存儲在隊列的尾部（tail 指針所指的位置）；如果沒有，則說明這1秒内的請求次數已經超過了限流值 K，是以這個請求被拒絕服務。
下圖的例子中，限流規則是，任意1内，接口的請求次數不能大于6次。
即便滑動時間視窗限流算法可以保證任意時間視窗内，接口請求次數不會超過最大限流值，但是仍然不能防止，在細時間粒度上通路過于集中的問題。
比如剛剛舉的那個例子，第一個 1s 的時間視窗内，100次請求集中在最後 10ms中，也就是說，基于時間視窗的限流算法，不管是固定時間視窗還是滑動時間視窗，隻能在標明的時間粒度上限流，對標明時間粒度内的更加細粒度的通路頻率不做限制。
總結引申
關于鑒權，我們講了三種不同的規則比對模式，不管是哪種比對模式，我們都可以用散清單來存儲不同應用對應的不同規則集合。對于每個應用的規則集合的存儲，三種比對模式使用不同的資料結構。
對于第一種精确比對模式，我們利用有序數組來存儲每個應用的規則集合，并且通過二分查找和字元串比對算法，來比對請求 URL 與規則。對于第二種字首比對模式，我們利用 Trie 樹來存儲每個應用的規則集合。對于第三種模糊比對模式，我們采用普通的數組來存儲包含通配符的規則，通過回溯算法，來進行請求URL與規則的比對。
關于限流，我們講了兩種限流算法，第一種是固定時間視窗限流算法，第二種是滑動時間視窗限流算法。對于滑動時間視窗限流算法，我們用了循環隊列來實作。比起固定時間視窗限流算法，它對流量整形效果更好，流量更加平滑。