丨算法實戰(zhàn)四剖析微服務(wù)接口鑒權(quán)限流背后的數(shù)據(jù)結(jié)構(gòu)和

及的內(nèi)容比較多，比如鑒權(quán)、限流、降級、熔斷、告警等等。這些服務(wù)治理功能的以防你之前可能對微服務(wù)沒有太多了解，所以我對鑒權(quán)的背景做了簡假設(shè)我們有一個微服務(wù)叫用戶服務(wù)（UserService）。它提供很多用戶相關(guān)的接口，比如獲用，都可以這個用戶服務(wù)，也并不是每個有權(quán)限的應(yīng)用，都可以用戶服務(wù)的所我舉了一個例子給你講解一下，你可以看我畫的這幅圖。這里面，只有A、B、C、D要實現(xiàn)接口鑒權(quán)功能，我們需要事先將應(yīng)用對接口的權(quán)限規(guī)則設(shè)置好。當(dāng)某個應(yīng)用其中一個接，我們就可以拿應(yīng)用的請求URL，在規(guī)則中進行匹配。如果匹配成功，就說明允許；如果沒有可以匹配的規(guī)則，那就說明這個應(yīng)用沒有這個接口的權(quán)限，我們就服務(wù)。接口的格式有很多，有類似Dubbo樣的RPC口，也有類似SpringCloud樣HTTP接口。不同接口的鑒權(quán)實現(xiàn)方式是類似的，我這里主要拿HTTP接口給你講解鑒權(quán)的原理比較簡單、好理解。那具體到實現(xiàn)層面，我們該用什么數(shù)據(jù)結(jié)構(gòu)來規(guī)則呢？用戶請求URL在規(guī)則中快速匹配，又該用什么樣的算法呢？如何實現(xiàn)精確匹配規(guī)我們先來看最簡單的一種匹配模式。只有當(dāng)請求URL規(guī)則中配置的某個接口精確匹配不同的應(yīng)用對應(yīng)不同的規(guī)則集合。我們可以采用散列表來這種對應(yīng)關(guān)系。我這里著重講下，每個應(yīng)用對應(yīng)的規(guī)則集合，該如何和匹配。針對這種匹配模式，我們可以將每個應(yīng)用對應(yīng)的權(quán)限規(guī)則，在一個字符串?dāng)?shù)組中。當(dāng)用戶請求到來時，我們拿用戶的請求URL，在這個字符串?dāng)?shù)組中逐一匹配，匹配的算法就是我們之前學(xué)過的字符串匹配算法（比如KMP、BM、BF等）。它組織成有序數(shù)組這種數(shù)據(jù)結(jié)構(gòu)。當(dāng)要查找某個URL能否匹配其中某條規(guī)則的時候，我們而二分查找算法的時間復(fù)雜度是O(logn)（n表示規(guī)則的個數(shù)），這比起時間復(fù)雜度是O(n)種優(yōu)化方法帶來的性能提升還是非?？捎^的。如何實現(xiàn)前綴匹配規(guī)我們再來看一種稍微復(fù)雜的匹配模式。只要某條規(guī)則可以匹配請求URL的前綴，我們就說這條規(guī)則能夠跟這個請求URL匹配。同樣，為了方便你理解這種匹配模式，我還是舉一個不同的應(yīng)用對應(yīng)不同的規(guī)則集合。我們采用散列表來這種對應(yīng)關(guān)系。我著重講一下，每個應(yīng)用的規(guī)則集合，最適合用什么樣的數(shù)據(jù)結(jié)構(gòu)來。在Trie那節(jié)，我們講到，Trie非常適合用來做前綴匹配。所以，針對這個需求，我們可以將每個用戶的規(guī)則集合，組織成Trie樹這種數(shù)據(jù)結(jié)構(gòu)。不過，Trie樹中的每個節(jié)點不是單個字符，而是接口被“/”分割之后的（比如“/user/name”被分割為“user”“name”兩個子）。因為規(guī)則并不會經(jīng)常變動，所以，在Trie樹中，我們可以把每個節(jié)點的子節(jié)點們，組織成有序數(shù)組這種數(shù)據(jù)結(jié)如何實現(xiàn)模糊匹配規(guī)如果我們的規(guī)則更加復(fù)雜，規(guī)則中包含通配符，比如“**”表示匹配任意多個 。只要用戶請求URL可以跟某條規(guī)則模糊匹配，我們就不同的應(yīng)用對應(yīng)不同的規(guī)則集合。我們還是采用散列表來這種對應(yīng)關(guān)系。這點我們剛才講過了，這里不再重復(fù)說了。我們著重看下，每個用戶對應(yīng)的規(guī)則集合，該用什么數(shù)據(jù)結(jié)構(gòu)來？針對這種包含通配符的模糊匹配，我們又該使用什么算法來實現(xiàn)呢？解決思路，來解決這個問題。我們采用回溯算法，拿請求URL跟每條規(guī)則逐一進行模糊匹章節(jié)復(fù)下。不過，這個解決思路的時間復(fù)雜度是非常高的。我們需要拿每一個規(guī)則，跟請求URL實際上，我們可以結(jié)合實際情況，挖掘出這樣一個的條件，那就是，并不是每條規(guī)則都包含通配符，包含通配符的只是少數(shù)。于是，我們可以把不包含通配符的規(guī)則和包含通配符的規(guī)則分開處理。我們把不包含通配符的規(guī)則，組織成有序數(shù)組或者Trie樹（具體組織成什，視具體的需求而定，是精確匹配，就組織成有序數(shù)組，是前綴匹配，就組織成Trie樹），而部分匹配就會非常高效。剩下的是少數(shù)包含通配符的規(guī)則，我們只要把它們簡單在一當(dāng)接收到一個請求URL之后，我們可以先在不包含通配符的有序數(shù)組或者Trie樹中查找。如果能夠匹配，就不需要繼續(xù)在通配符規(guī)則中匹配了；如果不能匹配，就繼續(xù)在通配符規(guī)則中查找匹配。講完了鑒權(quán)的實現(xiàn)思路，我們再來看一下所謂限流，顧名思義，就是對接口調(diào)用的頻率進行限制。比如每秒鐘過100次重要的作用。比如在秒殺、大促、雙11、618等場景中，限流已經(jīng)成為了保證系統(tǒng)平穩(wěn)運按照不同的限流粒度，限流可以分為很多種類型。比如給每個接口限制不同的頻率，或者給所有接口限制總的頻率，又或者更細粒度地限制某個應(yīng)用對某個接口的頻率等不同粒度的限流功能的實現(xiàn)思路都差不多，所以，我今天主要針對限制所有接口總的頻最簡單的限流算法叫固定時間窗口限流算法。這種算法是如何工作的呢？首先我們需要選定根據(jù)限流規(guī)則（比如每秒鐘最大允許100次請求），出現(xiàn)累加次數(shù)超過限流值的情況時，我們就后續(xù)的請求。當(dāng)進入下一個時間窗口之后，計數(shù)器就重新計假設(shè)我們的限流規(guī)則是，每秒鐘過100次接口請求。第一個1s時間窗口內(nèi)，100次接口請求都集中在最后10ms。在第二個1s時間窗口內(nèi)，100接口請求都集中在最開始的10ms內(nèi)。雖然兩個時間窗口內(nèi)流量都符合限流要求（≤100個請求），但在兩個時間窗口臨界的20ms內(nèi)，會集中有200次接口請求。固定時間窗口限流算法并不能對這種情況做限制，所以，集中在這20ms內(nèi)的200次請求就有可能壓垮系統(tǒng)。為了解決這個問題，我們可以對固定時間窗口限流算法稍加改造。我們可以限制任意時間窗口（比如1s）內(nèi)，接口請求數(shù)都過某個閾值（比如100次）。因此，相對于固定時流量經(jīng)過滑動時間窗口限流算法整形之后，可以保證任意一個1s的時間窗口內(nèi)，都不會超過最大允許的限流值，從流量曲線上來看會更加平滑。那具體到實現(xiàn)層面，我們該如何來做呢？我們假設(shè)限流的規(guī)則是，在任意1s內(nèi)，接口的請求次數(shù)都不能大于K次。我們就一個大小為K+1的循環(huán)隊列，用來記錄1s內(nèi)到來的請求。注意，這里循環(huán)隊列的大小等于限當(dāng)有新的請求到來時，與這個新請求的時間間隔超過1s的請求，從隊列中刪除。然后，我們再來看循環(huán)隊列中是否有空閑位置。如果有，則把新請求在隊列尾部（tail指針?biāo)傅奈恢茫?；如果沒有，則說明這1秒內(nèi)的請求次數(shù)已經(jīng)超過了限流值K，所以這個任意1s內(nèi)，接口的請求次數(shù)都不能大于6次。值，但是仍然不能防止，在細時間粒度問過于集中的問題。比如我剛剛舉的那個例子，第一個1s的時間窗口內(nèi)，100次請求都集中在最后10ms中，也就是說，基于時間窗口的限流算法，不管是固定時間窗口還是滑動時間窗口，只能在選定的時間粒度上限流，對選定時間粒度內(nèi)的更加細粒度的頻率不做限制。果感，你可以自己去研究一下。關(guān)于鑒權(quán)，我們講了三種不同的規(guī)則匹配模式。不管是哪種匹配模式，我們都可以用散列來不同應(yīng)用對應(yīng)的不同規(guī)則集合。對于每個應(yīng)用的規(guī)則集合的，三種匹配模式使不同的數(shù)據(jù)結(jié)構(gòu)對于第一種精確匹配模式，我們利用有序數(shù)組來每個應(yīng)用的規(guī)則集合，并且通過二分查找和字符串匹配算法，來匹配請求URL與規(guī)則。對于第二種前綴匹配模式，我們利用Trie樹來每個應(yīng)用的規(guī)則集合。對于第三種模糊匹配模式，我們采用普通的數(shù)組來包含通配符的規(guī)則，通過回溯算法，來進行請求URL與規(guī)則的匹配。關(guān)于限流，我們講了兩種限流算法，第一種是固定時間窗口限流算法，第二種是滑動時間窗口限流算法。對于滑動時間窗口限流算法，我們用了之前學(xué)習(xí)過的循環(huán)隊列來實現(xiàn)。比起固定時間窗口限流算法，它對流量的整形效果更好，流量更加平滑。從今天的學(xué)習(xí)中，我們也可以看出，對于基礎(chǔ)架構(gòu)工程師來說，如果不精通數(shù)據(jù)結(jié)構(gòu)和算法，我們就很難開發(fā)出性能卓越的基礎(chǔ)架構(gòu)、中間件。這其實就體現(xiàn)了數(shù)據(jù)結(jié)構(gòu)和算法的重要性。分析一下鑒權(quán)那部分內(nèi)容中，前綴匹配算法的時間復(fù)雜度和空間復(fù)雜最后，有個消息提前通知你一下。本節(jié)是專欄的倒數(shù)第二節(jié)課了，不知道學(xué)到現(xiàn)在，你掌握得怎么樣呢？為了幫你復(fù)習(xí)鞏固，做到真正掌握這些知識，我針對專欄涉及的數(shù)據(jù)結(jié)構(gòu)和算法，精心編制了一套練習(xí)題。從正月初一到初七，每天發(fā)布一篇。你要做好準(zhǔn)備哦！ 不得售賣。頁面已增加防盜追蹤，將依 上一 54|算法實戰(zhàn)（三）：剖析高性能隊列Disruptor背后的數(shù)據(jù)結(jié)構(gòu)和算下一 56|算法實戰(zhàn)（五）：如何用學(xué)過的數(shù)據(jù)結(jié)構(gòu)和算法實現(xiàn)一個短系統(tǒng)言精選留言言suke置 展/ 15展 展 2展 青銅5周 2請教老師一個問題哈，為啥鑒權(quán)算法里，每個應(yīng)用的規(guī)則要放到有序數(shù)組呢，放hashhashset對于小數(shù)據(jù)量也不一定比有序數(shù)組效率高呢。畢竟hashset還要計算哈希值、何 言 2展向 太棒了，給老師點