하단에 링크 추가한 Line 블로그의 이미지입니다.

<대규모 시스템 설계 기초> "4장 처리율 제한 장치"를 읽고 작성하는 포스트 입니다.

처리율 제한 장치란 ?

처리율 제한 장비(Rate Limiter)는 클라이언트가 보내는 트래픽의 처리율(Rate)을 제어하기 위한 장치다.
일반적으로 정의된 임계치(Threshold)를 넘어가면 추가로 들어온 모든 호출은 처리를 중단한다.

ex) 사용자 는 초당 2회 이상 새 글을 올릴 수 없다.

처리율 제한 장치를 사용할 때의 장점은

• Dos 공격에 의한 자원 고갈 방지
• 비용 절감
• 서버 과부하를 방지

등 예상할 수 있는 것들이다.

처리율 제한 장치를 설계할 시 고려할 점

해당 책에서 포인트로 잡는 것은 다음과 같다

• 처리율 제한 장치를 어디에 구축할 것인지 (클라이언트 vs 서버)
• 어떤 기준을 잡고 API 호출을 제한할 것인지
• 시스템 규모는 어느정도일지
• 분산 환경인지
• 독립된 서비스인지, Application에 포함되는지
• 장치에 걸러진 경우 사용자가 그 사실을 알아야 하는지

위 포인트를 기준으로 나온 시스템 요구사항이 이러하다고 가정을 해본다.

• 설정된 처리율 초과시, 정확하게 제한하고
• 낮은 응답 시간을 가지며
• 가능한 적은 메모리를 쓴다
• 분산형 처리율 제한(Distributed Rate Limiting)
  • 하나의 처리율 제한 장치를 여러 곳에서 공유
• 예외 처리
  • 요청이 제한되었을 때 사용자에게 보여준다
• 높은 결함 감내성(Fault Tolerance)
  • 제한 장치에 장애가 생겨도 전체 시스템에 영향을 주면 안된다.

처리율 제한 장치를 어디에 구축할 것인지 ?

• 클라이언트는 쉽게 위변조가 가능하므로 서버에 구축한다
• 서버에 구축시 같은 서버에 직접 구현하는 경우와
• 미들웨어로 처리율 제한 장치를 따로 두어 API 서버로 가는 요청을 따로 통제할 수 있다.
• 일반적으로 처리율 제한 장치는 API Gateway에 구축하는 편이다

장치에 걸러진 경우 사용자가 그 사실을 알아야 하는지 ?

• 이때 제한범위 이상의 Request를 보낸 경우 장치에서 HTTP 상태코드 429(Too many request)로 알려줄 수 있다.

어떤 기준을 잡고 처리율을 제한할 것인지?

일반적으로 처리율 제한에 사용되는 알고리즘은 다음과 같다

• 토큰 버킷(Token Bucket)
• 누출 버킷(Leaky Bucket)
• 고정 윈도 카운터(Fixed Window Counter)
• 이동 윈도 로그(Sliding Window Log)
• 이동 윈도 카운터(Sliding Window Counter)

토큰 버킷 알고리즘의 경우 지정된 용량을 갖는 컨테이너에 정해진 양의 토큰이 주기적으로 채워지고 토큰이 꽉찬 경우 채워지지 않는다(버려진다). 그리고 요청이 들어올 때마다 토큰을 하나 사용해 요청을 처리한다. 즉 정해진 크기만큼 일정 시간마다 요청을 처리할 수 있게 된다.

버킷은 몇개나 사용해야할까?

공급제한 규칙에 따라 달라진다.

• 통상적으로 API Endpoint 마다 별도의 버킷을 둔다
  • ex) 사용자마다 하루에 1번 포스팅 가능하고, 150명까지 추가할 수 있고 좋아요는 5번 가능하다면 사용자마자 3개의 버킷 필요.
  • ex) 전체 시스템을 초당 N개의 요청으로 제한하고 싶다면 모든 요청이 하나의 버킷을 공유하도록 하면 된다.

나머지 4가지 알고리즘은 처리에 대해 섬세하게 다른 부분이 있어 자세한 것은 구글 검색을 추천한다.

중요한 것은 처리율 제한 알고리즘은 얼마나 많은 요청이 접수되었는지 추적하는 카운터를 추적 대상별로 두고 어떤 한도를 넘어서면 한도를 넘어선 요청을 거부한다는 것이다.

그렇다면 카운터는 어디에 보관할까?

• 일반적으로 빠른 속도가 요구되기때문에 메모리에서 동작하는 캐시가 바람직하다.
• Redis가 자주 사용된다.

병행성이 심한 환경이라면 ?

• 경쟁 조건 이슈가 발생할 수 있다.
  • ex) Redis에 Counter 3을 가져와 작업을 완료해 다시 +1 하기 전에 다른 요청이 Counter 3을 가져가서 두 요청이 Counter 4를 업데이트 하는 식의 현상 (원래 값은 5가 되어야함)
• 경쟁 조건은 일반적으로 Lock으로 해결하지만 시스템 성능을 떨어뜨릴 수 있다
• Lock 대신 Lua Script와 Redis의 Sorted Set을 사용하기도 한다.

동기화 이슈

• 분산 환경에서 처리율 제한 장치 서버를 여러 대 두면 동기화가 필요하다
• 웹은 State-less이므로 웹은 기존에 가져온 장치의 정보를 가질 수 없기 때문에 Counter 관리가 정상적으로 수행되지 않는다.

이를 해결하기 위해

• 고정 세션(Sticky Session)을 이용해 같은 클라이언트 요청은 같은 처리율 제한 장치로 보내도록 할 수 있지만, 확장 가능성과 유연성이 떨어진다.
• 대신 Redis와 같은 중앙 집중형 데이터 저장소를 쓴다.
  • 즉 분산 환경에서 처리율 제한 장치는 중앙에 1개의 서버만 사용하는 것이다.

처리율 제한장치를 모니터링 한다면

• 채택된 처리율 알고리즘이 효과적인지 확인한다
• 정의한 처리율 제한 규칙이 효과적인지 확인한다.

추가적으로 알면 좋을 것

• 경성(hard) 처리율 제한 / 연성(soft) 처리율 제한, 임계치를 절대 넘을 수 있는지 잠시 동안은 넘어도 되는지 차이
• 예시는 Application Layer지만 OSI 다양한 계층에서 처리율 제한 가능하다는 것
• 클라이언트는 어떻게 설계하는게 좋을까 ?
  • 클라이언트 측 캐시를 사용해 API 호출 횟수를 줄이고
  • 임계치를 알고 짧은 시간동안 너무 많이 호출하지 않도록 하고
  • 에러나 예외를 Gracefully하게 복구하도록 하며
  • 재시도(retry) 로직을 구현할 때는 back-off를 충분하게 둔다

---

추가적으로 찾아본 것

Ratelimit 오픈소스

예제로 나온 Ratelimit 오픈소스

• 버킷 알고리즘을 읽으면서 버킷이 아주 많이 생성될 것으로 예상되었는데 Domain과 Desctiptors, limit 조건, now 시간을 기준으로 Redis Key를 만들어 캐싱하고 있었다.
  • 수가 엄청 나게 많아져도 Redis Key로 생성하는 것이므로 문제가 없나보다 (?)
• 해당 오픈 소스는 근사치까지 최대한 처리하고 처리 불가능하면 HTTP 429를 보내는 것으로 보인다
• 근사치 등 처리의 근거는 레디스 캐시 서버에서 가져온다.

병행성이 심한 환경에서의 Redis의 Sorted Set와 Lua Script

Redis Sorted Set

• 토큰 버킷 알고리즘을 사용하기엔 결함이 있었다
  • 일부 프로세스는 버킷을 계속 다시 채워야함. (너무 처리할 데이터가 많다)
    • 위 Ratelimit에서 궁금했던 사항이 문제점으로 등장했다.
      • Ratelimit의 경우 내부에서 추가적으로 처리하는지 대규모 시스템에서 사용할 수 없는 수준인지는 코드를 좀 더 뜯어봐야 알 것 같다.
  • 더 정교한 방식이 필요했다
• Redis의 Sorted Set을 이용해서, 각 유저는 자신과 연결된 정렬된 집합을 가지고 있다가
• 사용자가 작업을 수행하려 하면 한 interval 전에 발생한 집합 요소를 모두 삭제한다
• 그리고 집합의 모든 요소를 가져와서 현재 타임스탬프를 세트에 추가한다
• ... 그 외 자세한 방식은 링크를 참조
• 이 방식의 장점은 모든 작업을 Redis를 이용해 원자적 작업으로 수행할 수 있다는 것
  • Redis Lua Script
    • Redis의 Lua Script는 Redis에서 명령어를 원자적(Atomic)으로 수행할 수 있게 해준다

Scaling your API with rate limiters

• 간략히 정리하면 여러 종류의 Rate Limiter를 사용해 종류별로 Rate를 제한한다.
• 이를 통해 병행성을 최대한 낮춘다.

추가로 읽어볼 것

• 고 처리량 분산 비율 제한기 by Line Engineering
  • 해당 책에서는 기본적인 Redis를 이용한 중앙집중적 구조만 나왔지만 Client Side에서 분산하는 구조도 나온다. 또한 논블로킹 구조도 있어 다양한 형태의 분산 처리기에 대해 공부할 수 있다. 현업에서 어떤 식으로 사용되는지도 확인할 수 있다.