限制流量的方式 (rate limit)
source link: https://blog.gslin.org/archives/2021/10/29/10401/%e9%99%90%e5%88%b6%e6%b5%81%e9%87%8f%e7%9a%84%e6%96%b9%e5%bc%8f-rate-limit/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
限制流量的方式 (rate limit)
在 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 方便一些：
這個方式在控制上更精確，不過空間成本上就高很多... 這樣算是把常見的實做方式都提到了。
Related
Memcached 與 Redis 的比較
在「Memcached vs Redis - More Different Than You Would Expect」這邊看到對 Memcached 與 Redis 的分析。 這兩套軟體都很常被拿來用作 cache 機制，所以一般來說比較時就是比兩邊都有的東西 (如果你要 pub-sub 之類的東西，在這兩套裡面只有 Redis 有)。 最前面還是先講了對使用者 (開發者) 的差異，很明顯的是 Redis 對各種不同的資聊結構都有支援，這點可以從 Redis 被官方被稱作 Data Structures Server 就可以知道 (在「An introduction to Redis data types and abstractions」這篇可以看到)，而 Memcached 只支援了 key-value 架構。 不過如果是以 cache 來說，的確 key-value 架構就還蠻好用的。…
October 13, 2021In "Computer"
自適應演算法與 A/B Testing
在 Hacker News Daily 上看到三年前的舊文章，講自適應演算法取代常見的 A/B testing：「20 lines of code that will beat A/B testing every time」。 就拿原文裡面的例子來說明，我想要測試 "Buy Now!" 這個按鈕的顏色來得知哪個顏色的 click rate 最高，而我有 Orange、Green 以及 White 三種顏色為候選。 一開始我初始值都設為「展示了 1 次，被點擊了 1 次」，所以每個點擊率都是 100%： OrangeGreenWhite 1/1 = 100%1/1=100%1/1=100% 然後你的網站上只要展示「點擊率最高的那個顏色」，並且記錄下來展示次數與點擊率就好，而整個過程會是自適應而被自動被淘汰掉，最後可能會變成這樣，就會固定是綠色的了： OrangeGreenWhite 114/4071 = 2.8%205/6385=3.2%59/2264=2.6% 而這樣做的好處是節省人力成本：你不需要 A/B Testing 完後再人工介入修改。 對於更複雜的例子，雖然原文沒有提到，但你可以直接展開來做，舉例來說，你假設顏色與地區兩個變數所帶出來的 click rate…
April 8, 2016In "Computer"
ORDB 結束營業
在 Slashdot 上看到 ORDB 將在月底結束營業的消息：ORDB.org Going Offline，官方的公告在 ORDB.org is shutting down 這篇，預定 2006 年年底全部關閉，屆時網頁也無法連上，所以放一份公告在最後面吧。 ORDB 是一項免費卻擁有接近 0% 誤判的 DNSBL 服務，ORDB 讓使用者輸入要求偵測的 IP address，然後 ORDB 就會以程式自動偵測是否為 Open Relay 然後列入名單。 Open Relay 對於發廣告信的人是成本最低的方式，但由於有 ORDB 存在，對於想要擋的人也是最容易阻擋的方式。參考我之前寫過的 擋 mail spam 這篇。 利用 ORDB 擋正規的 Mail Server，再利用 Greylisting 擋直接連線到 SMTP server 但不正規的 Mail Client 是目前前端最好的方法：幾乎…
December 19, 2006In "Computer"
Author Gea-Suan LinPosted on October 29, 2021October 29, 2021Categories Computer, Murmuring, Network, Programming, Service, Spam, WWWTags access, algorithm, antispam, bucket, figma, leaky, limit, limiting, memcached, rate, redis, spam, spammer, token One thought on “限制流量的方式 (rate limit)”
Leave a Reply Cancel reply
Your email address will not be published. Required fields are marked *
Comment
Name *
Email *
Website
Notify me of follow-up comments by email.
Notify me of new posts by email.
Post navigation
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK