처리율 제한 장치의 설계

네트워크 시스템에서 처리율 제한 장치는 클라이언트 / 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치입니다.

요청 횟수가 제한 장치에 정의된 threshold (임계치)를 넘어서면 추가로 도달한 호출은 처리가 중단됩니다.

예시는 다음과 같습니다.

1. 사용자는 초당 2회 이상 새 글을 올릴 수 없다.
2. 같은 IP주소로는 하루에 10개 이상의 계정을 생성할 수 없다.
3. 같은 디바이스로는 주당 5회 이상 리워드를 요청할 수 없다.
   이를 테면, 수강 신청 서비스의 연속 클릭(따닥) 또한 비슷한 맥락이라고 할 수 있습니다.

문제 이해 및 설계 범위 확정

이러한 처리율 제한 장치의 구현을 위해선 여러가지 알고리즘을 활용할 수 있고, 각각의 방법은 장단점을 가지고 있습니다.

책에서는 면접관-지원자 구조로 요구사항을 이끌어 내고 있습니다.

요구사항

• 설정된 처리율을 초과하는 요청은 정확하게 제한한다.
• 낮은 응답시간 : 이 처리율 제한 장치는 HTTP응답시간에 나쁜 영향을 주어선 안된다.
• 가능한 한 적은 메모리를 써야한다.
• 분산형 처리율 제한 : 하나의 처리율 제한 장치를 가능한 한 많은 서버나 프로세스에서 공유할 수 있어야 한다.
• 예외 처리 : 요청이 제한되었을 떄는 그 사실을 분명하게 보여주어야 한다.
• 높은 결함 감내성(fault tolerance) : 제한 장치에 장애가 생기더라도, 전체 시스템에 영향을 주어선 안된다.

---

개략적 설계안 제시

교재에서는 기본적인 클라이언트 - 서버 모델을 사용합니다.

일차적으로 처리율 제한 장치를 어디에 둘 것인지 고민이 필요합니다.

1. 처리율 제한 장치는 어디에 둘 것인가?

세 가지 방법이 가능합니다.

1. 클라이언트 측에 두기
2. 서버 측에 두기
3. 미들웨어의 형태로 중간에 두기

1 번 방법의 경우, 클라이언트의 요청은 쉽게 위변조가 가능합니다.
따라서 모든 클라이언트의 구현을 통제하는 것에 제약이 존재하기 때문에 적합한 방법이 아닐 수도 있습니다.

2번 방법의 경우, 다음과 같은 그림으로 설명될 수 있습니다.

하지만 위 구현은 각 서버에 도달하기 전 까지 처리율을 제한할 수 없다는 점이 단점입니다.

어차피 처리하지 못 할 요청이라면, 서버에 도달하기 전에 결정하는 방법도 좋을 것 같습니다.

3번 방법의 경우, 다음과 같은 구성이 가능합니다.

위 구조에서 threshold를 초과하는 요청을 마주하게 된다면, 미들웨어가 가로채어 중간에 반환하는 구조를 만들어 낼 수 있습니다.

MSA를 채택하는 현대의 서버 구조에서는, API gateway 단에 처리율 제한장치를 구현하곤 합니다.

그 이유가 뭘까요 ?

 

API gateway는 클라이언트와 서비스 간 트래픽을 통제하는 중앙 진입점 역할을 합니다.

따라서 요청을 한 곳에서 처리할 수 있기 때문에, 정책 적용과 변경이 용이하다는 장점이 있습니다.

또한, 개별 마이크로서비스에 처리율 제한을 두는 경우, 각 서비스가 부하를 감지해야 하지만, API gateway에서 처리율 제한을 적용하면 부하를 줄일 수 있습니다.

---

처리율 제한 알고리즘

처리율 제한 알고리즘은 여러가지가 존재하고, 장단점도 각기 다릅니다.

• 토큰 버킷(token bucket)
• 누출 버킷(leaky bucket)
• 고정 윈도 카운터(fixed window counter)
• 이동 윈도 로그(sliding window log)
• 이동 윈도 카운터(sliding window counter)

토큰 버킷 알고리즘

토큰 버킷 알고리즘은 다음과 같습니다.

토큰 버킷은 지정된 용량을 갖는 컨테이너이고, 사전 설정된 양의 토큰이 주기적으로 채워집니다.
토큰이 꽉 찬 버킷에는 더 이상의 토큰은 추가되지 않습니다. (버려집니다.)

교재의 예제는 용량이 4인 버킷을 중심으로 설명합니다.

• 충분한 토큰이 있는 경우, 버킷에서 토큰 하나늘 꺼낸 후 요청을 시스템에 전달합니다.
• 만약 토큰이 없다면, 해당 요청은 버려집니다.

위 알고리즘은 두개의 인자를 받습니다.

1. 버킷 크기 : 버킷에 담을 수 있는 최대 토큰 갯수
2. 토큰 공급률 : 초당 몇 개의 토큰이 버킷에 공급되는가?

통상적으로 API 엔드포인트 마다 버킷을 별도로 둡니다.

1. 하루에 한 번 포스팅 할 수 있다.
2. 150명 까지 친구를 추가할 수 있다.
3. 다섯 번 까지 좋아요 버튼을 누를 수 있다.
   다음과 같이, 세개의 엔드포인트에 대한 제약이 존재한다면, 사용자 마다 3개의 버킷이 필요합니다.

장점

1. 구현이 쉽습니다.
2. 메모리 사용 면에서 효율적입니다.
3. 짧은 시간에 집중되는 트래픽도 처리 가능합니다.

단점

1. 버킷 크기와 토큰 공급률이라는 두 개 인자를 가지고 있는데, 이 값을 튜닝하는 것이 까다롭습니다.

누출 버킷 알고리즘

누출 버킷 알고리즘은 토큰 버킷 알고리즘과 비슷하지만, 요청 처리율이 고정되어 있습니다. 위 알고리즘은 보통 FIFO 큐로 구현합니다.

• 요청이 도착하면 큐가 가득 찼는지 봅니다. 빈자리가 있다면 큐에 요청을 추가합니다.
• 큐가 가득 차 있다면 새 요청을 버립니다.
• 지정된 시간마다 큐에서 요청을 꺼내어 처리합니다.

• 버킷 크기 : 큐 사이즈와 같은 값입니다.
• 처리율 : 지정된 시간당 몇개의 항목을 처리할지 지정하는 값입니다. 보통 초 단위로 표현됩니다.

장점

• 큐의 크기가 제한되어 있어, 메모리 사용량 측면에서 효율적입니다.
• 고정된 처리율을 갖고 있기 때문에, 안정적인 출력이 필요한 경우 적합합니다.

단점

• 단시간에 많은 트래픽이 몰리는 경우, 큐에는 오래된 요청들이 쌓이게 되고, 그 요청들을 제때 처리 못하면 최신의 요청들은 버려지게 됩니다.
  즉, 서버의 사양에 따라 병목현상이 발생할 수 있습니다. 하지만 이 경우, 이전 요청이 늦게 처리되는 것이 아닌, 버려진다는 점에서 치명적으로 작용할 수 있습니다.
• 파라미터 튜닝이 까다롭습니다.

고정 윈도 카운터 알고리즘

• 타임라인을 고정된 간격의 윈도우로 나누고, 각 윈도마다 타이머를 붙입니다.
• 요청이 접수될 떄마다 카운터의 값이 1씩 증가합니다.
• 이 카운터의 값이 사전에 설정된 threshold에 도달하면, 새로운 요청은 새 원도가 열릴 때 까지 버려집니다.

간단하게, Time slice 방식입니다.

위 그림에서 시스템은 초당 세개까지의 요청만을 허용합니다.
따라서 3개가 초과되는 요청은 제한에 걸려 전달되지 않습니다.

이 알고리즘의 문제 중 하나는, 윈도우의 경계 부근에 순간적으로 많은 트래픽이 집중될 경우, 할당된 양보다 더 많은 요청이 처리될 수 있다는 점 입니다.

시간이 1분을 기준으로 하고 있기 때문에, 기준점을 옮겨서 확인하면, 목표 기준치를 초과할 수 있습니다.
(1시 1분~1시 2분은 5개의 요청을 받았으나, 1시 1분 30초 ~ 1시 2분 30초는 10개의 요청을 받음)

장점

• 메모리 효율이 좋습니다.
• 이해하기 쉽습니다.
• 윈도우가 닫히는 시점에 카운터를 초기화 하는 방식이기 때문에, 특정한 트래픽 패턴을 처리하기 적합합니다.

단점

• 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우, 기대했던 시스템의 처리 한도보다 많은 양의 요청을 처리하게 됩니다.

이동 윈도 로깅 알고리즘

이동 윈도 로깅 알고리즘은 고정 윈도 카운터 알고리즘의 중대한 문제를 해결할 수 있습니다.

• 이동 윈도 로깅 알고리즘은 요청의 타임스탬프를 추적합니다. 데이터는 보통 Redis의 sorted set 같은 캐시에 보관합니다.
• 새 요청이 오면 만료된 타임스탬프는 제거합니다. 만료된 타임스탬프는 그 값이 현재 윈도의 시작 시점보다 오래된 타임스탬프를 말합니다.
• 새 요청의 타임스탬프를 로그에 추가합니다.
• 로그의 크기가 허용치보다 같거나 작으면, 요청을 시스템에 전달합니다. 그렇지 않은 경우에는 처리를 거부합니다.

1. 요청이 1:00:01에 도착했을 때, 로그는 비어있는 상태입니다. 따라서 요청은 허용됩니다.
2. 새로운 요청이 1:00:30에 도착합니다. 타임스탬프가 로그에 추가됩니다. 추가 직후 로그의 크기는 2이며, 허용 한도보다 크지 않습니다. 따라서 요청은 시스템에 전달됩니다.
3. 새로운 요청이 1:00:50에 도착합니다. 타임스탬프가 로그에 추가됩니다. 직후 로그의 크기는 3으로, 허용 한도보다 큰 값이기 때문에 타임스탬프는 로그에 남지만 요청은 거부됩니다.
4. 새로운 요청이 1:01:40에 도착합니다. 범위(1:00:40, 1:01:40)안의 요청을 제외하고는 만료된 요청입니다. 따라서 두개의 만료된 타임스탬프를 로그에서 삭제합니다.

즉, 로깅을 추가하여 검증하는 방식입니다.

장점

• 매커니즘이 정교하기 때문에, 어느 순간을 보더라도 시스템의 처리율 한도를 넘기지 않습니다.

단점

• 다량의 메모리를 사용합니다.

이동 윈도 카운터 알고리즘

해당 알고리즘은 고정 윈도 카운터 알고리즘과, 이동 윈도 로깅 알고리즘을 결합한 방식입니다.

처리율 제한 장치의 한도가 분당 7개 요청으로 설정되어 있고, 이전 1분동안 5개의 요청이, 현재 1분 동안 3개의 요청이 왔다고 가정했을 때

현재 1분의 30% 시점에 도착한 새 요청은 현재 윈도에 몇 개의 요청이 온 것으로 보고 처리해야 할까요 ?

• 현재 1분간의 요청 수 + 직전 1분 간의 요청 수 * 이동 윈도와 직전 1분이 겹치는 비율
  이 공식에 따르면 현재 윈도에 들어있는 요청은 6.5개, 6개 입니다.
  예제에서 분당 7개의 한도 요청이라고 가정했기 때문에, 1분의 30% 시점에 도달한 시점의 신규 요청은 시스템으로 전달됩니다. 하지만 그 직후에는 한도에 도달했기 때문에, 요청을 처리할 수 없습니다.

장점

• 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다.
• 메모리 효율이 좋다.

단점

• 요청이 균등하게 분포되어 있다고 가정한 상태에서 계산하기 때문에 다소 느슨합니다. 하지만 생각보다 심각한 정도는 아닙니다.

 

---

개략적인 아키텍처

기본적으로 모든 알고리즘이 처리하는 방식은 비슷한 양상을 띄고 있습니다.
각 요청별로 카운터를 두고, 한도를 넘어서는 요청을 거부하는 방식입니다.

Redis는 통상적으로 메모리 기반 Nosql이기 때문에, 해당 기능을 구현하기 적합한 미들웨어 입니다.

• INCR : 메모리에 저장된 카운터의 값을 1 증가시킵니다.
• EXPIRE : 카운터에 타임아웃 값을 설정합니다. 설정 시간이 지나면 카운터는 자동으로 삭제됩니다.

• 클라이언트가 미들웨어에 요청을 보냅니다.
• 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와 한도를 검사합니다.
• 한도에 도달하지 안았다면 요청은 API 서버로 전달됩니다.

---

상세 설계

https://github.com/envoyproxy/ratelimit

 

구체적인 예제는 포함하지 않겠습니다.

다음과 같은 오픈소스를 사용해서 처리율 제한 규칙을 구현할 수도 있습니다.

어떤 요청이 한도 제한에 걸리면 API 는 HTTP 429(Too many requests)를 반송합니다. 경우에 따라 큐에 보관할 수도 있겠습니다.

처리율 제한 장치가 사용하는 HTTP 헤더

이를 사용자가 감지하기 위해선 헤더에 상태 값을 전달하며 통신할 수 있습니다.

• X-Ratelimit-Remaining : 윈도 내에 남은 처리 가능 요청의 수
• X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
• X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림

사용자가 너무 많은 요청을 보내고, 큐잉을 진행하지 않는다면 429 too many request오류를

X-Ratelimit-Retry-After 헤더와 함께 반환합니다.

 

• 처리율 제한 규칙은 디스크에 보관합니다. workers는 수시로 규칙을 디스크에서 읽어, 캐시에 저장합니다.
• 클라이언트가 요청을 보내면, 먼저 처리율 제한 미들웨어에 도달합니다.
• 처리율 제한 미들웨어는 규칙을 캐시에서 가져옵니다. 또한 카운터 및 타임스탬프를 레디스 캐시에서 가져옵니다.
• 이후 검증에 따라 API 서버에 보내거나, 버리거나 큐잉을 진행합니다.

---

분산 환경에서의 처리율 제한 장치의 구현

단일 서버는 어렵지 않지만, 분산 환경에서는 난이도가 높습니다.

자주 등장하는 토픽입니다.

1. Race condition
2. Synchoronization

Race Condition

위에서 서술한 대로, 다음과 같이 동작합니다.

• 레디스에서 카운터의 값을 읽는다.
• counter +1 이 threshold를 넘는지 본다.
• 그렇지 않다면 레디스에 보관된 카운터 값을 1 증가시킨다.

병행성이 심한 환경은 다음과 같은 이슈가 나타날 수 있습니다.

위 Race Condition을 해결하는 방법은 Lock 입니다. 하지만 락은 시스템의 성능을 많이 떨어뜨리게 됩니다.

위 미들웨어는 API 서버에 도달하기 전의 구성 요소인데, 해당 요소에서 락을 통해 자원을 관리할 경우, 요구되는 throughput에 도달하지 못할 가능성이 존재합니다.

위 문제는 Lua script와, sorted set으로 해결할 수 있습니다.

 

Lua Script Example

local limit = 10  -- 최대 요청 허용 수
local window = 60 -- 제한 시간 (초)

local client_ip = ngx.var.remote_addr
local key = "rate_limit:" .. client_ip

-- NGINX의 shared_dict 사용

local store = ngx.shared.rate_limit_store
local current_time = os.time()

-- 기존 요청 수와 타임스탬프 가져오기

local data, err = store:get(key)
local request_count, last_time = 0, current_time


if data then
    request_count, last_time = string.match(data, "^(%d+):(%d+)$")
    request_count = tonumber(request_count)
    last_time = tonumber(last_time)
end

-- 요청이 새로운 시간 창에 들어가면 카운터 초기화

if current_time - last_time >= window then
    request_count = 0
    last_time = current_time
end

-- 요청 허용 여부 판단
if request_count < limit then
    request_count = request_count + 1
    store:set(key, request_count .. ":" .. last_time, window)
    return -- 요청 허용
else
    ngx.status = 429
    ngx.say("Rate limit exceeded")
    ngx.exit(429)

end

Redis Sorted Set Example

각 사용자는 연관된 정렬된 세트를 갖습니다. 키와 값은 동일하며, 작업이 시도된 (마이크로초) 시간과 동일합니다.
    
- 사용자가 작업을 수행하려고 할 때, 우리는 먼저 한 간격 전에 발생한 세트의 모든 요소를 ​​삭제합니다. 이는 Redis의 `ZREMRANGEBYSCORE`명령으로 달성할 수 있습니다.
    
-  `ZRANGE(0, -1)`을 사용하여 세트의 모든 요소를 ​​가져옵니다.
    
- `ZADD`을 사용하여 현재 타임스탬프를 세트에 추가합니다.
    
- 우리는 (공간을 절약하기 위해) 집합의 속도 제한 간격과 동일한 TTL을 설정합니다.
    
- 모든 작업이 완료된 후, 페치된 요소의 수를 센다. 한계를 초과하면 작업을 허용하지 않는다.
    
- 또한 가장 큰 페치된 요소를 현재 타임스탬프와 비교할 수도 있습니다. 너무 가까우면 해당 작업을 허용하지 않습니다.

Synchronization

사용자가 많아질 경우, 처리율 제한 장치에도 scale out이 필요할 수 있습니다. 그래서 스케일 아웃을 진행하게 된다면, 동기화 문제를 해결해야 합니다.

이에 대한 한 가지 해결책은, sticky-session을 사용해, 서버와 요청을 고정시키는 방식입니다.

하지만 이 방식은, stateless의 장점을 활용할 수 없는 방식입니다.

따라서 Redis와 같은 중앙 집중형 데이터 저장소를 사용하는 것이 조금 더 바람직한 방법일 수 있습니다.

---

성능 최적화

어떻게 성능을 최적화 할 수 있을까요 ?

바로 처리를 사용자와 가까운 지역에서 미리 진행하는 방식입니다.

엣지 서버를 두어서, 사용자 지역 근처에서 처리율 제한 정치를 거친 이후 본 서버로 전달 하여 지연 시간을 단축시킬 수 있습니다.

---

더 알아보면 좋을 주제들

• hard / soft 처리율 제한
  • hard limit : 요청의 개수는 임계치를 절대 넘어설 수 없다.
  • soft limit : 요청의 개수는 잠시 동안은 임계치를 넘어설 수 있다.
• 다양한 계층에서의 처리율 제
  • 해당 장에서는 Application계층의 제한만 다루었지만, 더 높고 정확한 성능이 필요할 경우 IP계층에서도 제한이 가능합니다.
• 무조건 처리율 제한 장치를 마주하는 것이 좋은 설계가 아니다.
  • 클라이언트 캐시를 사용해 API 호출 줄이기
  • threshold를 이해하고, 짧은 시간 동안 너무 많은 메세지 보내지 않게 구현하기
  • 에러나 예외 처리 코드 도입하여, 유연한 복구 지원하기.
  • retry를 시도할 때는, 충분한 back off 시간을 두기