Tag: bucket

在 Lobsters Daily 上看到這篇 2017 年的文章，Figma 的工程師講怎麼做 rate limit：「An alternative approach to rate limiting」，只要大一點的站台就會遇到 spammer 之類的攻擊，就會希望實做自動化的機制擋住 spammer。

文章裡面提到了三種方式，第一種 (類) 提到了經典的 Token bucket 與 Leaky bucket，這邊文章提供的演算法是讓每個使用者都會有一筆資料紀錄在 Redis 裡面 (這邊的用法可以抽換換成 Memcached)，裡面記錄了最後一次的 access time 以及還剩下多少 token 可以用，接下來就可以照時間計算 token 的補充與消耗：

但這個演算法的缺點是 race condition，需要另外設計一些機制確保操作的 atomic：

不過大多數的實做就算不管 atomic 也還行 OK，只是會比較不精確一點。

第二個方法他叫做 Fixed window counters，這個方法把時間切齊為單位 (像是 60 秒為一個 window)，所以可以把起點的時間也放到 key 裡面，然後 value 就是數量：

這個作法的好處就是簡單，而且 Redis 與 Memcached 都有提供 atomic 的 +1 操作。但缺點是可能會發生兩倍以上的 request，像是 5 reqs/min 的限制有可能會有連續的一分鐘內達到 10 reqs/min：

不過我覺得就 antispam 來說算是夠用了，當年 (大概是 2007 或是 2008 年？) 在 PIXNET 時用 C 寫 Apache module 就是把資料丟到 Memcached 裡面就是這樣實做的，然後每次學術網路的實驗室跑來掃站的就會自動被擋 XDDD

第三種方式他們稱作 Sliding window log，就是把每個 request 的 timestamp 都存起來，這個部份用 Redis 的資料結構會比用 Memcached 方便一些：

這個方式在控制上更精確，不過空間成本上就高很多... 這樣算是把常見的實做方式都提到了。