Leaky bucket / token bucket

Leaky bucket과 token bucket은 속도 제어에 사용되는 일반적인 알고리즘이다. 이 포스트에서는 두 알고리즘에 대해 알아본다.

Token bucket algorithm

토큰 버킷 알고리즘은 일정한 주기로 토큰이 채워지는 버킷의 아이디어를 기반으로 한다. 각 토큰은 API에 한 번의 요청을 할 수 있는 권한을 나타낸다. 클라이언트가 요청을 하고자 할 때 버킷에서 토큰 하나를 사용한다. 버킷이 비어있으면 요청은 거부되거나 토큰을 사용할 수 있을 때 까지 대기한다. 토큰 버킷 알고리즘을 사용하면 버킷에 충분한 토큰이 있는 한 클라이언트가 원하는 만큼 빠르게 토큰을 사용할 수 있다.

토큰 버킷 알고리즘의 장점은 클라이언트에 유연성과 응답성을 제공한다는 것이다. 클라이언트는 토큰이 있는 한 언제든지 요청을 할 수 있다. 또한 클라이언트는 필요할 때 버킷 용량까지 스로틀링 없이 요청을 대량으로 보낼 수 있다. 토큰 버킷 알고리즘의 단점은 악의적이거나 greedy한 클라이언트에 의해 악용될 수 있다는 점이다. 클라이언트가 원하는 만큼 빠르게 요청을 보낼 수 있기 때문에 버킷에 있는 모든 토큰을 소모하고 다른 클라이언트가 API에 엑세스하지 못하게 할 수 있다. 또한 토큰 버킷 알고리즘은 원활하고 일관된 요청 속도를 보장하지 않기 때문에 꾸준한 흐름이 필요한 일부 API에서는 문제가 발생할 수 있다.

Leaky Bucket Algorithm

누수 버킷 알고리즘은 일정한 비율로 물이 새는 양동이에 대한 아이디어를 기반으로 동작한다. API에 대한 각 요청은 버킷에 들어가는 물방울로 표현된다. 버킷에는 최대 용량이 있어 요청의 폭발적인 증가를 제한한다. 버킷이 가득 차면 들어오는 모든 요청은 거부되거나 버킷에 공간이 생길 때 까지 대기한다. 요청은 버킷의 누수율과 동일한 고정된 수치로 처리되게 된다. 누수 버킷 알고리즘은 요청이 얼마나 빨리 도착하는지에 관계 없이 시간이 지남에 따라 요청이 균등하게 분산되도록 보장한다.

누수 버킷 알고리즘의 장점은 API에 공정성과 안정성을 제공한다는 점이다. 특정 클라이언트가 API를 독점하거나 요청이 폭주하는 것을 방지하고 모든 클라이언트가 API에 엑세스할 수 있는 동등한 기회를 갖도록 보장한다. 또한 들어오는 요청량의 갑작스러운 변동을 완화하고 수용 가능하고 일관된 요청 비율을 생성함으로써 API의 성능과 안정성을 개선하고 과부하 또는 충돌의 위험을 줄일 수 있다. 누수 버킷 알고리즘의 단점은 주어진 리소스를 온전히 다 활용할 수 없다는 점이다. 이 알고리즘은 실제 수요와 트래픽 패턴에 관계 없이 고정된 비율의 요청을 허용한다. 즉, 클라이언트가 사용 가능한 대역폭을 최적으로 사용할 수 없으며 리소스를 낭비하게 된다. 또한 클라이언트가 필요로할 때 요청을 대량으로 할 수 없으며 버킷의 대기열 대기열 효과로 인해 지연 또는 거부되는 경험을 할 수 있다.