Rate Limiting

Rate limiting - concurrency in go 

Why do we need Rate Limiting? 

• malicious users can access your system as quickly as their resources allow it. -> they can do all kinds of things
• 악의적이지 않더라도, 큰 볼륨으로 operation을 수행하거나, 실행하려는 코드가 buggy하다면, performance를 저하시킬수 있다. 일반적으로 서비스에서는 어느정도의 성능을 지속적으로 유지할 수 있다는 것을 보증하고 싶어하고, 한명의 유저라도 그 agreement에 영향을 받는다면 좋지 않은 결과를 낳는다. 일반적으로 유저들은 시스템에 대한 자신들의 접근이 sandboxed되어 있다고 생각하고, 다른 유저들의 행동에 영향을 주거나 받지 않는다고 생각하는데, 만약 이 mental model이 깨지게 된다면 이탈할 확률이 높아진다. 
• 즉, performance와 stability측면에서 중요하다고 할 수 있다. 

Token Bucket Rate Limiter 

• token을 저장하는 bucket이 있고, bucket은 depth가 있고, depth가 d라고 하면,한번에 d 만큼의 access token을 가지고 있을 수 있음을 의미한다. 토큰이 없으면 요청은 denied 되고 token이 available될때까지 queue 에 넣고 기다린다. 
  
  • d(depth of the bucket): how many tokens are available for immediate use. permits bursts of at most d tokens. 
  • r: rate at which they are replenished. token 이 bucket에 added back 되는 rate를 의미한다. 
• 이 두개로 burstiness and overall rate limit을 조절할 수 있다. 
• leaky bucket 은 contrant 한 속도로 처리할 수 있는 반면에 token bucket은 버스트 요청도 허용된다. 버스트 요청은 간헐적으로 이용하지만 최대한 빠른 round trip을 원하는 caller에게 유리하다. 

 

we can use this library :  https://pkg.go.dev/golang.org/x/time/rate 

• use Limiter to block our requests until we're given an access token. 
  
  • func (lim *Limiter) WaitN(ctx, n int): blocks until lim permits n events to happen. if returns an error if n exceeds the Limiter's burst size, the Context is canceled, or the expected wait time exceeds the Context's Deadline. 
• In this chapter, rate limiting is done within the APIConnection which is client side, but normally a rate limiter would be running on a server. 

rate package - golang.org/x/time/rate - Go Packages

 

Single rate limiter 로 위의 예시에서는 사용했지만, 사실 하나의 rate limiter를 사용하게 되면, rate limiter의 intent에 대한 많은 정보를 잃게 된다. 그래서 이 책에서는 간단한 aggregate rate limiter를 만들어본다.  

RateLimiter라는 interface를 만들고, MultiLimiter struct가 이것을 implement하도록 하게 되면, reculsively define할 수 있게 된다. multiLimiter 안에 multiLimiter가 여러개 들어있는 형태 같이. 

secondLimit := rate.NewLimiter(Per(2, time.Second), 1)
minuteLimit := rate.NewLimiter(Per(10, time.Minute), 10) 

// MultiLimiter(secondLimit, minuteLimit)

이렇게 되면, coarse-grained limit을 명확히 드러내면서도, finer level of detail 의 request 갯수를 제한하는 것이 가능해진다. 이런 기능들을 다양한 resource들에서 limit을 정하기 위해서 사용되기도 한다. 예를 들어 disk access, network access같은 것에 따로 rate limit을 세팅하는 것이 가능하다. readFile 같은 기능에 대해서는 limits from the API limiter와 disk limiter를 합쳐서 limit을 건다. 

이렇게 logical rate limiter들을 하나의 여러개의 group으로 조합하는 것이 가능해진다. 

 

Leaky Bucket Algorithm 

Flow control의 대표적인 알고리즘이다. 

• FIFO Queue 에 담겨 미리 규정된 속도로 처리된다. 
• FIFO Queue가 가득차 있지 않은 경우에는 요청을 받아들인다. 
• FIFO Queue가 가득차 있을 때 요청이 들어오면 client에게 에러를 리턴한다. 

일정한 속도로 요청을 처리할 수 있다. 또한 구현이 쉽다는 장점이 있다. 

 

leaky bucket 구현 예시 

• https://gist.github.com/gh-codejitsu/7bfa2b2153be57f199a844bde240c3fa
• https://etloveguitar.tistory.com/127 
• https://github.com/uber-go/ratelimit/blob/main/limiter_atomic.go 

 

질문 : 

https://go.dev/doc/effective_go 의 Leaky buffer부분 구현은 어떤 것을 의미하나?

 

client goroutine 에서는 source로부터 데이터를 받는 loop이 존재하고, buffer를 allocating 하고 freeing하는 것을 피하기 위해서 free list를 유지하고, buffered channel을 사용해서 표현한다. server loop은 message를 client로부터 받아서, 처리하고, free list 에 자리가 남아있을때만 buffer를 돌려놓는다. 

 

Client send -> server receive -> client send (client는 channel이 비게 되어 다음 for loop을 진행한다. ) & server process (server는 buffer를 받자마자 process를 실행한다.) -> server 가 process가 끝나고 receive -> 반복적으로 진행될 것.

 

이 leaky buffer 부분은 leaky bucket algorithm과 관계가 있는가?