Implementing Quota as a Service

* Describe Quota/RateLimit Algorithms
* Describe OSS Quota/RateLimit Packages / Services
* Describe How we developed Quota as a Service

Transcript

1. Implementing Quota as a Service @nasa9084
2. $ whoami • @nasa9084 • LINE corp. • Go / Kubernetes / emacs • https://blog.web-apps.tech
3. <advertisement>
5. </advertisement>
6. Quota as a Service
7. “Quota”
8. Quota /kwóʊṭə/ 1. ෼୲෼ɺׂΓ౰ͯ 2. (੡଄ɾ༌ೖग़ͳͲͷ)طఆ[ׂΓ౰ͯ]਺ྔ 3. (ड͚ೖΕΔҠຽɾձһɾֶੜͳͲͷ)ఆ਺ɾఆһ —https://ejje.weblio.jp/content/quota
9. WHY?
10. Why implement “Quota as a Service”? • We are developing / managing Monitoring system • Very many requests • Easy to abuse → We need Quota/Rate Limit for our services
11. Don’t use Quota / RateLimit lib simply? • LINE has many services (also our team) • Need Quota / RateLimit per services • Need manage configurations for each services • Need database for each services • Not want to manage extra DBs…
12. Algorithms
13. Token Bucket • Limit the average rate of traffic • Allow some burstiness • Bucket is an abstracted container • We can implement as buffer or queue
14. Token Bucket Algorithm 1. Add Tokens into Bucket per 1/r seconds • Bucket can hold b Tokens 2. When n bytes packet is coming, remove n Tokens and send the packet 3. If Bucket does not have n Tokens, the packet becomes non-conformant • Drop the packet • Queue the packet until Bucket charges enough Tokens • Send with non-conformant flag
15. Leaky Bucket • Limit the peak rate of traffic • Not allow burstiness • Same as Generic Cell Rate Algorithm • Used for ATM Network
16. Leaky Bucket Algorithm • A fixed capacity bucket • If the bucket is empty, stops leaking • Packet is water • It is possible to add a specific amount of packet to the bucket • If the amount of packet would cause the bucket to exceed its capacity, then the packet is non-conformant
17. Fixed Window Counter • Limit requests per REAL time duration • Window is fixed • e.g. 100 requests / 10:00 - 10:59 10:00 11:00 Requests
18. Fixed Window Counter • Over quota in configured duration • e.g. 5 requests/hour 09:00 10:00 11:00 6 requests/hour
19. Sliding Window Counter • Limit requests since ${window_size} ago • Window limitation window moves as time passes
20. Existing Solutions
21. QuotaLibs
22. vladimir-bukhtoyarov/bucket4j • Written in Java • Based on Token Bucket algorithm • Scalable for multi-threading
23. tomasbasham/ratelimit • Written in python • Implemented as decorator • Not using database!
24. QuotaService
25. square/quotaservice • Written in Go • gRPC service • Based on Token Bucket algorithm • Still WIP…
26. lyft/ratelimit • Written in Go • As gRPC service • Assumed to use with envoy
27. Quota as a Service for us
28. Implement Quota as a Service • (Of course) Write with Go • Clean Architecture (-like) • Standard Project Layout * ᵓᴷᴷ cmd/ # main.go ᵓᴷᴷ init/ # systemd ᵋᴷᴷ internal/ ᵓᴷᴷ cmd/ ᴹ ᵓᴷᴷ httpgen/ # generate http router ᴹ ᵋᴷᴷ mockgen/ # generate mock ᵋᴷᴷ pkg/ ᵓᴷᴷ apiserver/ ᵓᴷᴷ domain ᵓᴷᴷ errors/ ᵓᴷᴷ infra/ # implementation ᵓᴷᴷ interceptor/ # gRPC middleware ᵓᴷᴷ interfaces/ # interfaces ᵓᴷᴷ middleware/ #http middleware ᵋᴷᴷ rpc/ *golang-standards/project-layout
29. Reduce Management Cost • Generate Codes as possible as we can • Reduce middle-wares/services managed by ourselves
30. Generate Codes as possible as we can • gRPC + REST • gRPC: rate limiting • REST: registration • gRPC server/client code generated from Protocol Buffers • REST server/client code generated from OpenAPI spec • Mock from interfaces
31. Central Dogma • Service Configuration Repository by LINE • Highly available • Version Controlled based on Git • Can watch by client • Apply config change by event base • Can mirror GitHub to Central Dogma
32. Reduce Services We Should Manage • Configuration Management • GitHub Pull Request for WUI + Central Dogma as Database • User Authentication / User metadata DB • LDAP + session store (Redis)
33. Q?