토큰 버킷 알고리즘 (Token Bucket Algorithm)

한 줄 정의: 일정한 속도로 "토큰"을 채워 넣는 가상의 통을 두고, 요청이 들어올 때마다 토큰을 하나씩 소모하게 하여 트래픽 속도를 제한하는 알고리즘입니다.

쉽게 풀면

놀이공원 입장권을 상상해 보세요. 매표소는 1분에 딱 10장씩만 표를 새로 찍어내고, 방문객은 표가 있어야만 입장할 수 있습니다. 표가 남아 있으면 여러 명이 한꺼번에 몰려도 즉시 입장할 수 있지만, 표가 다 떨어지면 새 표가 나올 때까지 기다려야 합니다. 토큰 버킷 알고리즘도 이와 같습니다. 정해진 속도로 "토큰"이 통(bucket)에 채워지고, 요청이 하나 들어올 때마다 토큰을 하나 꺼내 씁니다. 통에 토큰이 남아 있으면 순간적으로 몰리는 요청도 어느 정도 받아 줄 수 있고(버스트 허용), 토큰이 바닥나면 그 이후 요청은 거절되거나 대기하게 됩니다.

왜 중요한가

토큰 버킷 알고리즘은 네트워크 트래픽 셰이핑, 분산 시스템의 API 요청 제한, 클라우드 서비스의 과금 정책 설계 등 실무와 밀접하게 연결되어 있어 시스템 논문과 산업 사례 보고서에서 두루 다루어집니다. 단순히 요청 속도를 제한하는 것을 넘어, 평균 처리율과 순간 폭주(버스트) 허용치를 별도로 조절할 수 있다는 점이 리키 버킷 같은 다른 방식과 비교되며 자주 논의됩니다. 또한 분산 환경에서 여러 서버에 걸쳐 토큰 상태를 어떻게 일관되게 유지할지는 그 자체로 별도의 연구 주제가 됩니다.

논문에서는 이렇게 쓰입니다

"API 서버의 과도한 요청으로부터 시스템을 보호하기 위해 클라이언트별로 토큰 버킷 알고리즘(token bucket algorithm)을 적용하여 초당 요청 수를 제한하였다."

이 문장은 "한 사용자가 짧은 시간에 너무 많은 요청을 보내지 못하도록, 토큰이 채워지는 속도만큼만 요청을 허용하는 방식을 사용했다"는 뜻입니다.

"네트워크 스위치에서 토큰 버킷 기반 트래픽 셰이핑을 적용하여 상위 링크의 대역폭 초과 사용을 방지하였다."

네트워크 장비 수준에서 토큰 버킷을 이용해 대역폭 사용량을 조절한 사례를 설명하는 문장이다.

"분산 레이트 리미터는 여러 노드에서 토큰 버킷 상태를 공유 저장소에 동기화하여 일관된 속도 제한을 유지하였다."

단일 서버가 아닌 여러 서버로 구성된 분산 시스템에서 토큰 버킷을 적용할 때의 어려움과 해결 방식을 다룬 예문이다.

조금 더 깊게 보면

토큰 버킷과 자주 비교되는 방식으로 리키 버킷(leaky bucket) 알고리즘이 있는데, 리키 버킷은 요청을 일정한 속도로만 내보내 트래픽을 매끄럽게 만드는 데 초점을 맞추는 반면, 토큰 버킷은 버킷에 쌓인 토큰만큼 순간적인 버스트 트래픽을 허용한다는 차이가 있습니다. 실제 구현에서는 토큰이 채워지는 속도(버킷 충전율)와 버킷의 최대 용량이라는 두 가지 매개변수를 조합해 평균 처리율과 허용 가능한 버스트 크기를 각각 독립적으로 설계할 수 있으며, 이 조합 방식이 논문에서 성능 평가의 핵심 변수로 다뤄지는 경우가 많습니다.

주의할 점

토큰 버킷은 통의 크기(버킷 용량)를 얼마로 두느냐에 따라 순간적인 트래픽 폭주를 어느 정도까지 허용할지가 달라집니다. 버킷을 너무 크게 잡으면 순간 폭주를 막지 못하고, 너무 작게 잡으면 정상적인 사용자 요청까지 자주 거절될 수 있어 서비스 특성에 맞춰 값을 조정해야 합니다. 이 알고리즘은 API 서버의 레이트 리미팅을 구현하는 대표적인 방법 중 하나입니다.