上一篇文章講到了利用令牌桶（token bucket）和漏桶（leaky bucket）算法進行訪問頻率限制彤蔽，這些非常通用偿渡，但是也有一些問題颠放，怎么解決（更準確說應(yīng)該是緩解）呢饼酿？
回到最初問題的來源棉圈，其實只要把所有的請求都記錄下來涩堤，每次新來一個請求看最近一段時間有沒有超標即可。然而分瘾，一般并不能這么粗暴的記錄每一條記錄的時間戳胎围，然后統(tǒng)計，因為內(nèi)存可能扛不住德召，CPU可能也扛不住白魂。
于是，有了固定窗口計數(shù)（Fixed Window Counter）這樣的算法上岗。算法做的就是每小段時間用一個值記錄起始時間福荸，另一個值記錄個數(shù)即可。比如肴掷，限制是每1分鐘60次敬锐，那么就在每個整分點（11:11:00）這樣開始計數(shù)，每次來請求就增加記錄次數(shù)呆瞻，如果超過60次台夺，就意味著頻率超標了。然后每個這樣的記錄的過期時間是1分鐘痴脾，這樣颤介，如果一個用戶訪問幾次之后，不再訪問，內(nèi)存中對應(yīng)的記錄值也會清掉滚朵。事實上Github好多實現(xiàn)就是用了這樣的算法冤灾。
這樣的做法，明顯有個不合理的部分辕近。那就是頻率峰值可能不均分韵吨，例如，雖然設(shè)置的是1分鐘訪問5次亏推，但假設(shè)訪問都集中在11:00:40学赛，這樣子，11點11分確實只訪問了5次吞杭。接下來盏浇，11:01:00數(shù)據(jù)清除，11:01:15秒有5次訪問芽狗，也符合規(guī)范绢掰。然而， 11:00:40 到11:01:15這段時間（不足1分鐘）童擎，卻能訪問10次滴劲！
看來這樣的方法也不行顾复，問題在于：
- 不能在周期邊界暴力清空
- 隨著時間推移班挖，確實需要清掉一些舊的不用了的數(shù)據(jù)
基于這兩點，于是有了最終比較符合需求的算法：滑動窗口計數(shù)（Sliding window counters）芯砸。我突然意識到這個方法萧芙，是因為前段時間瞄了一下TCP協(xié)議（真是牛逼的協(xié)議啊）假丧，然后網(wǎng)上一查双揪，發(fā)現(xiàn)早就被別人提出來了（見文末參考文檔）。
算法思路在于包帚，不是單純地記錄每次請求的時間戳（開頭說了渔期，可能太耗空間），而是把請求按照一段一段計數(shù)渴邦。比如疯趟， 1分鐘5次這樣的要求，可以把一分鐘劃分成60秒几莽，然后每秒只用一個數(shù)字表示這一秒有多少個請求迅办。這樣，請求再多章蚣，也只需要60個數(shù)字記錄（因為分成了60份）。同理，1小時100次纤垂，可以把時間劃分成分鐘矾策，進行記錄。
然后峭沦， 每次有新請求來的時候贾虽，刪除已經(jīng)沒用的數(shù)據(jù)（超過限定期限的，比如上面說的1小時）吼鱼，然后算出時間戳蓬豁，計數(shù)增加。如果沒有超過限制菇肃，那么地粪，就設(shè)置整個數(shù)據(jù)（下面示例中的“user_A"）的過期時間（如果以后用戶都不訪問了， 這些數(shù)據(jù)會在過期之后被回收掉）琐谤。
一個用戶的記錄示例：
"user_A": {"11:00:00": 5, "11:01:00": 3}
份數(shù)劃分的意義何在呢蟆技？顯然首先是為了省內(nèi)存（同時統(tǒng)計也快），其次是為了控制誤差斗忌。事實上质礼，這個算法是有誤差的。比如假設(shè)1小時被劃分成60份织阳， 也就是每分鐘一份眶蕉，11:00:40的訪問會被記錄在11點整上， 而12:00:10會被記錄在12點整上唧躲，這兩個整點其實在不同的時間段造挽，也就是說考慮12點整的訪問時，已經(jīng)不用去考慮11點整的訪問量了惊窖。而實際上刽宪，11:00:40和12:00:10的相差是不足一個小時的，邏輯上它們的訪問量應(yīng)該算在同一個小時里界酒。
不過圣拄，實際中，算法實現(xiàn)的時候毁欣，應(yīng)該能接受這樣的誤差（如果不能接受庇谆，需要在清楚過期數(shù)據(jù)的時候，注意這樣的邊界問題凭疮，比如額外保留一份小時間段的數(shù)據(jù)饭耳。因為算法本身無法區(qū)分11:00:00和11:00:40這樣的訪問）。
這個算法設(shè)置好合理的劃分（如果用redis执解，不要超過128寞肖，因為效率），自己估算好最大誤差值（很顯然，極端情況下新蟆，依然可以在同一個時間段內(nèi)允許兩倍的訪問）觅赊，應(yīng)該可以在實際運用中起到比較好的效果了。
說了這么多琼稻，我在Github上搜了一下吮螺，似乎還沒有Golang對應(yīng)的實現(xiàn)。接下來帕翻，我會想辦法抽時間實現(xiàn)一下鸠补。
更新：
實現(xiàn)過程中，滑動窗口計數(shù)的時候嘀掸，發(fā)現(xiàn)太多需要改動一段一段計數(shù)的地方紫岩。感覺用hash不如序列化然后用string存取快。
實現(xiàn)地址：
restrictor
參考文章：
https://blog.figma.com/an-alternative-approach-to-rate-limiting-f8a06cf7c94c
