버스트 트래픽 처리 방법: Leaky Bucket 및 Token Bucket 알고리즘

API7.ai

January 5, 2023

OpenResty (NGINX + Lua)

이전 글들에서 우리는 애플리케이션의 전반적인 성능과 밀접한 관련이 있는 코드 최적화와 캐시 설계에 대해 배웠으며, 이는 우리의 주목을 받을 만한 주제였습니다. 그러나 실제 비즈니스 시나리오에서는 급증하는 트래픽이 성능에 미치는 영향도 고려해야 합니다. 여기서 급증하는 트래픽은 뉴스 속보, 프로모션 등과 같은 정상적인 트래픽일 수도 있고, DDoS 공격과 같은 비정상적인 트래픽일 수도 있습니다.

OpenResty는 현재 주로 WAF(웹 애플리케이션 방화벽) 및 API 게이트웨이와 같은 웹 애플리케이션의 접근 계층으로 사용되며, 이러한 애플리케이션은 앞서 언급한 정상 및 비정상적인 급증 트래픽을 처리해야 합니다. 결국, 급증하는 트래픽을 처리하지 못하면 백엔드 서비스가 쉽게 다운될 수 있고, 비즈니스가 적절히 대응하지 못할 수 있습니다. 따라서 오늘은 급증 트래픽을 처리하는 방법에 대해 살펴보겠습니다.

트래픽 제어

트래픽 제어는 WAF 및 API 게이트웨이의 필수 기능입니다. 이는 일부 알고리즘을 통해 인그레스 트래픽을 통제하고 조절함으로써 상위 서비스가 적절히 기능할 수 있도록 보장하며, 시스템의 건강을 유지합니다.

백엔드의 처리 능력이 제한적이기 때문에 비용, 사용자 경험, 시스템 안정성 등 여러 측면을 고려해야 합니다. 어떤 알고리즘을 사용하더라도 정상적인 사용자 요청이 느려지거나 거부되는 것을 피할 수 없으며, 이는 사용자 경험의 일부를 희생시키는 것입니다. 따라서 비즈니스 안정성과 사용자 경험을 균형 있게 유지하면서 트래픽을 제어해야 합니다.

실제로 일상 생활에서도 "트래픽 제어" 사례를 많이 찾아볼 수 있습니다. 예를 들어, 중국의 춘절 여행 시즌에는 지하철역, 기차역, 공항 등 교통 허브에 사람들이 몰리게 되는데, 이러한 교통 수단의 처리 능력이 제한적이기 때문입니다. 따라서 승객들은 줄을 서서 일정량씩 입장해야 하며, 이는 그들의 안전과 교통의 정상적인 운영을 보장합니다.

이는 승객의 경험에 영향을 미치지만, 전체적으로 시스템의 효율적이고 안전한 운영을 보장합니다. 예를 들어, 줄을 서지 않고 일제히 입장하게 한다면, 결과적으로 전체 시스템이 다운될 수 있습니다.

기술로 돌아가서, 예를 들어 상위 서비스가 분당 10,000개의 요청을 처리하도록 설계되었다고 가정해 봅시다. 피크 시간에 진입점에서 트래픽 제어가 없다면, 작업 스택이 분당 20,000개에 도달할 수 있으며, 이 상위 서비스의 처리 성능은 분당 5,000개의 요청으로 저하될 수 있고 계속 악화되어 결국 서비스 불가 상태가 될 수 있습니다. 이는 우리가 원하는 결과가 아닙니다.

이러한 급증 트래픽에 대처하기 위해 우리가 사용하는 일반적인 트래픽 제어 알고리즘은 누출 버킷 알고리즘과 토큰 버킷 알고리즘입니다.

누출 버킷 알고리즘

먼저 누출 버킷 알고리즘을 살펴보겠습니다. 이 알고리즘은 일정한 요청 속도를 유지하고 트래픽의 급증을 완화하는 것을 목표로 합니다. 하지만 어떻게 이를 달성할까요? 먼저, 위키피디아의 누출 버킷 알고리즘 소개에서 나온 개념적 추상화를 살펴보겠습니다.

누출 버킷 알고리즘

클라이언트의 트래픽을 물이 흐르는 파이프로 상상할 수 있으며, 이 물의 유속은 때로는 빠르고 때로는 느릴 수 있습니다. 외부 트래픽 처리 모듈은 물을 받는 버킷으로, 바닥에 구멍이 있어 물이 새어 나갑니다. 이것이 누출 버킷 알고리즘의 이름의 유래이며, 다음과 같은 이점이 있습니다:

첫째, 버킷으로 들어오는 물의 양이 적든 많든, 버킷에서 나가는 물의 속도는 일정합니다. 이 안정적인 트래픽은 상위 서비스에 친화적이며, 이것이 트래픽 셰이핑의 목적입니다.

둘째, 버킷 자체는 일정한 부피를 가지고 있으며, 일정량의 물을 축적할 수 있습니다. 이는 클라이언트 요청이 즉시 처리되지 않을 경우 큐에 대기할 수 있음을 의미합니다.

셋째, 버킷의 부피를 초과하는 물은 버킷이 받아들이지 않고 흘러갑니다. 이에 상응하는 비유는 클라이언트 요청이 큐 길이를 초과하면 클라이언트에게 실패 메시지를 반환하는 것입니다. 이 순간 서버 측에서는 너무 많은 요청을 처리할 수 없으며, 큐 대기는 불필요해집니다.

그렇다면 이 알고리즘은 어떻게 구현해야 할까요? OpenResty에 내장된 resty.limit.req 라이브러리를 예로 들어보겠습니다. 이는 누출 버킷 알고리즘으로 구현된 속도 제한 모듈입니다. 다음 글에서 이에 대해 더 자세히 소개할 예정이지만, 오늘은 간단히 다음 코드를 살펴보겠습니다. 이 코드가 핵심입니다:

local elapsed = now - tonumber(rec.last)
excess = max(tonumber(rec.excess) - rate * abs(elapsed) / 1000 + 1000,0)
if excess > self.burst then
    return nil, "rejected"
end
-- return the delay in seconds, as well as excess
return excess / rate, excess / 1000

이 코드를 간단히 읽어보겠습니다. elapsed는 현재 요청과 마지막 요청 사이의 밀리초 수이며, rate는 초당 설정한 속도입니다. rate의 최소 단위는 0.001초/요청이므로, 위에서 구현된 코드는 이를 계산하기 위해 1000을 곱해야 합니다.

excess는 큐에 남아 있는 요청 수를 나타내며, 0은 버킷이 비어 있음을 의미하고, burst는 전체 버킷의 부피를 나타냅니다. excess가 burst보다 크면 버킷이 가득 찼음을 의미하며, 들어오는 트래픽은 바로 버려집니다. excess가 0보다 크고 burst보다 작으면 큐에 대기하여 처리되며, 여기서 반환된 excess/rate는 대기 시간입니다.

이렇게 하면 burst 크기를 조정하여 급증 트래픽의 큐 길이를 제어할 수 있으며, 백엔드 서비스의 처리 능력은 변하지 않습니다. 그러나 물론, 사용자에게 요청이 너무 많으니 나중에 다시 시도하라고 알릴지, 아니면 사용자가 더 오래 기다리게 할지는 비즈니스 시나리오에 따라 다릅니다.

토큰 버킷 알고리즘

토큰 버킷 알고리즘과 누출 버킷 알고리즘은 모두 백엔드 서비스가 급증 트래픽에 의해 타격을 받지 않도록 보장하는 것을 목표로 하지만, 두 알고리즘은 구현 방식이 다릅니다.

누출 버킷 알고리즘은 엔드포인트 IP를 사용하여 트래픽 및 속도 제한의 기초를 수행합니다. 이렇게 하면 각 클라이언트의 누출 버킷 알고리즘의 출구 속도는 고정됩니다. 그러나 이는 다음과 같은 문제를 야기합니다:

사용자 A의 요청이 빈번하고 다른 사용자의 요청이 드물다면, 누출 버킷 알고리즘은 A의 일부 요청을 느리게 하거나 거부할 수 있습니다. 이는 서비스가 그 시점에 이를 처리할 수 있고, 전체 서비스 압력이 그리 높지 않음에도 불구하고 말입니다.

이때 토큰 버킷이 유용합니다.

누출 버킷 알고리즘이 트래픽을 완화하는 데 초점을 맞춘다면, 토큰 버킷은 급증 트래픽이 백엔드 서비스로 들어갈 수 있도록 허용합니다. 토큰 버킷의 원리는 버킷에 고정된 속도로 토큰을 넣고, 버킷이 가득 차지 않는 한 계속 토큰을 넣는 것입니다. 이렇게 하면 엔드포인트에서 오는 모든 요청은 먼저 토큰 버킷에서 토큰을 얻어야 백엔드에서 처리할 수 있습니다. 버킷 안에 토큰이 없다면 요청은 거부됩니다.

그러나 OpenResty는 라이브러리에서 토큰 버킷을 구현하여 트래픽과 속도를 제한하지 않습니다. 따라서 여기서는 UPYUN이 오픈소스로 공개한 토큰 버킷 기반 속도 제한 모듈 lua-resty-limit-rate를 예로 들어 간단히 소개하겠습니다:

local limit_rate = require "resty.limit.rate"

-- global 20r/s 6000r/5m
local lim_global = limit_rate.new("my_limit_rate_store", 100, 6000, 2)

-- single 2r/s 600r/5m
local lim_single = limit_rate.new("my_limit_rate_store", 500, 600, 1)

local t0, err = lim_global:take_available("__global__", 1)
local t1, err = lim_single:take_available(ngx.var.arg_userid, 1)

if t0 == 1 then
    return -- global bucket is not hungry
else
    if t1 == 1 then
        return -- single bucket is not hungry
    else
        return ngx.exit(503)
    end
end

이 코드에서는 두 개의 토큰 버킷을 설정했습니다: 전역 토큰 버킷과 ngx.var.arg_userid를 key로 하는 토큰 버킷으로, 사용자별로 나뉩니다. 두 토큰 버킷의 조합은 다음과 같은 주요 이점이 있습니다:

  • 전역 토큰 버킷에 토큰이 남아 있다면 사용자의 토큰 버킷을 확인할 필요가 없으며, 백엔드 서비스가 정상적으로 운영될 수 있다면 사용자의 급증 요청을 최대한 처리할 수 있습니다.
  • 전역 토큰 버킷이 없는 경우 요청을 무조건 거부할 수 없으므로, 개별 사용자의 토큰 버킷을 확인하고 급증 요청이 많은 사용자의 요청을 거부해야 합니다. 이렇게 하면 다른 사용자의 요청이 영향을 받지 않도록 보장됩니다.

분명히, 토큰 버킷은 누출 버킷보다 더 유연하며, 급증 트래픽이 백엔드 서비스로 전달될 수 있는 상황을 허용합니다. 그러나 물론, 둘 다 장단점이 있으며, 상황에 따라 선택하여 사용할 수 있습니다.

NGINX의 속도 제한 모듈

이 두 알고리즘을 살펴본 후, 마지막으로 NGINX에서 속도 제한을 구현하는 방법을 살펴보겠습니다. NGINX에서 limit_req 모듈은 가장 일반적으로 사용되는 속도 제한 모듈이며, 다음은 간단한 구성입니다:

limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;

server {
    location /search/ {
        limit_req zone=one burst=5;
    }
}

이 코드는 클라이언트의 IP 주소를 key로 사용하고, one이라는 10M 메모리 공간 주소를 요청하며, 속도를 초당 1 요청으로 제한합니다.

서버의 location에서 one 속도 제한 규칙을 참조하고, brust를 5로 설정합니다. 속도가 1r/s를 초과하면 동시에 5개의 요청을 큐에 대기시킬 수 있으며, 일정한 버퍼 영역을 제공합니다. brust를 설정하지 않으면 속도를 초과하는 요청은 바로 거부됩니다.

이 NGINX 모듈은 누출 버킷을 기반으로 하므로, 위에서 설명한 OpenResty의 resty.limit.req와 본질적으로 동일합니다.

요약

NGINX에서 속도 제한의 가장 큰 문제는 동적으로 수정할 수 없다는 것입니다. 결국, 설정 파일을 수정한 후 다시 시작해야 적용되며, 이는 빠르게 변화하는 환경에서는 받아들일 수 없습니다. 따라서 다음 글에서는 OpenResty에서 동적으로 트래픽 및 속도 제한을 구현하는 방법을 살펴보겠습니다.

마지막으로, WAF 및 API 게이트웨이의 관점에서, 정상적인 사용자 요청과 악의적인 요청을 식별하는 더 나은 방법이 있을지 고려해 보겠습니다. 정상적인 사용자의 급증 트래픽의 경우 백엔드 서비스를 신속하게 확장하여 서비스 용량을 늘릴 수 있지만, 악의적인 요청의 경우 접근 계층에서 바로 거부하는 것이 더 좋습니다.

이 글을 동료와 친구들에게 공유하여 함께 배우고 성장할 수 있도록 해주세요.