Databricks에서의 고성능 속도 제한

Databricks 엔지니어로서, 우리는 훌륭한 동료들과 함께 도전적인 문제에 대해 작업할 수 있는 특권을 가지고 있습니다. 이 엔지니어링 블로그 게시물에서는 Databricks에서 고성능 속도 제한 시스템을 어떻게 구축했는지 설명해 드리겠습니다. 당신이 Databricks 사용자라면, 이 블로그를 이해하지 못해도 플랫폼을 최대한 활용하는 데 문제가 없습니다. 하지만 내부를 살펴보는 데 관심이 있다면, 우리가 어떤 멋진 작업을 해왔는지 읽어보세요!

배경

요율 제한은 다중 사용자 시스템에서 사용자 간의 격리 및 과부하 보호를 제공하기 위해 리소스 사용을 제어하는 것입니다. Databricks의 맥락에서 이것은 계정, 작업 공간, 사용자 등 사이의 격리를 제공하는 것일 수 있으며, 대부분의 경우 초당 실행된 작업 수, 초당 API 요청 수 등의 시간 단위 제한으로 외부에서 볼 수 있습니다. 그러나 서비스의 클라이언트 간 용량을 관리하는 등의 내부적인 사용 용도로 요율 제한을 사용할 수도 있습니다. 레이트 제한 집행은 Databricks를 신뢰할 수 있게 만드는 중요한 역할을 하지만, 이 집행은 최소화해야 하는 오버헤드를 발생시킨다는 점을 주목해야 합니다.

문제점

2023년 초, Databricks의 기존 Ratelimit 인프라는 Ratelimit 서비스에 호출을 하는 Envoy 입구 게이트웨이와 서비스를 지원하는 단일 Redis 인스턴스로 구성되어 있었습니다(그림 1). 이것은 어떤 기계 클러스터가 지역 내에서 받을 것으로 예상되는 초당 쿼리(QPS) 및 초당 계산의 일시적인 특성에 대해 완벽하게 적합했습니다. 그러나 회사가 고객 기반을 확장하고 새로운 사용 사례를 추가함에 따라, 우리를 그 지점까지 이끈 것이 미래의 필요성을 충족시키기에 충분하지 않을 것이라는 것이 분명해졌습니다. 실시간 모델 서빙 및 기타 높은 qps 사용 사례가 도입되면서, 한 고객이 현재 Ratelimit 서비스가 처리할 수 있는 것보다 훨씬 많은 트래픽을 보낼 수 있는 상황에서 몇 가지 문제가 발생했습니다.

• 높은 꼬리 지연 시간 - 우리의 서비스는 특히 두 번의 네트워크 홉이 관여하고 있고, 클라우드 제공 업체 중 하나에서 10ms-20ms의 P99 네트워크 지연 시간이 있을 때, 무거운 트래픽 하에서 꼬리 지연 시간이 너무 높았습니다.
• 제한된 처리량 - 어느 정도까지는 더 많은 기계를 추가하고 포인트 최적화(캐싱 등)를 하면서도 더 많은 트래픽을 처리할 수 없게 되었습니다.
• Redis를 단일 실패 지점으로 - 우리의 단일 Redis 인스턴스가 우리의 단일 실패 지점이었고, 우리는 이에 대해 무언가를 해야 했습니다. 서비스를 재설계할 시간이었습니다.

용어

Databricks에서는 RatelimitGroup (RLG)이라는 개념을 가지고 있으며, 이는 우리가 보호해야 하는 리소스 또는 리소스 집합을 나타내는 문자열 식별자입니다. 예를 들어, API 엔드포인트 등입니다. 이러한 리소스는 작업 공간/사용자/계정 수준에서 제한을 설정하는 등 특정 차원에서 보호될 것입니다. 예를 들어, 차원은 "FooBarAPI를 workspaceId로 보호하고 싶고, 이 요청의 workspaceId는 12345입니다."라는 메시지를 전달할 것입니다. 차원은 다음과 같이 표현될 것입니다:

단일 shouldRateLimit 요청은 여러 설명자를 가질 수 있으며, 예를 들어 특정 API에 대해 작업 공간 및 사용자 수준에서 제한을 설정하는 것일 수 있습니다.

Descriptor 스키마는 다음과 같이 보일 것입니다:

솔루션

낮은 지연 시간 응답

우리가 해결하고자 했던 첫 번째 문제는 Ratelimit 서비스의 지연 시간을 개선하는 것이었습니다. 속도 제한은 궁극적으로 단지 계수 문제이며, 우리는 이상적으로 항상 메모리 내에서 속도 제한 요청에 대답할 수 있는 모델로 이동하고 싶었습니다. 왜냐하면 이것은 매우 빠르고, 우리의 대부분의 속도 제한은 QPS에 기반하고 있었기 때문입니다. 이는 이러한 카운트가 일시적이며 서비스 인스턴스가 재시작하거나 충돌하는 것에 대해 복원력이 필요하지 않음을 의미합니다. 기존 설정은 Envoy의 일관된 해싱 을 사용하여 캐시 히트율을 높이고, 동일한 요청을 동일한 기계로 보내는 방식으로 이미 제한된 메모리 내 계산을 수행했습니다. 그러나, 1) 이것은 non-Envoy 서비스와 공유할 수 없었고, 2) 서비스 크기 조정 및 재시작 중의 할당 변동은 우리가 여전히 Redis와 정기적으로 동기화해야 함을 의미했고, 3) 일관된 해싱은 핫스팟에 취약하며, 부하가 고르게 분산되지 않았을 때 우리는 종종 인스턴스 수를 늘려 부하를 더 잘 분산시키려고 했으며, 이는 서비스 이용률이 불량하게 이어졌습니다.

운이 좋게도, 몇몇 멋진 사람들이 Databricks에 합류했고, 그들은 Dicer라는 오토샤딩 기술을 설계하고 있었습니다. 이 기술은 상태를 가진 서비스를 관리하기 쉽게 만들면서도, 상태 없는 서비스 배포의 모든 이점을 유지할 수 있게 해줍니다. 이것은 우리가 모든 속도 제한 계수를 메모리에 유지함으로써 서버 측 지연을 제어할 수 있게 해주었습니다. 왜냐하면 클라이언트는 Dicer에게 요청을 목적지 서버에 매핑하도록 요청할 수 있었고, 서버는 Dicer와 함께 요청의 적절한 소유자인지 확인할 수 있었기 때문입니다. 메모리 내에서 계수하는 것은 분명히 더 간단하고 빠르며, Dicer는 우리가 서버 측 꼬리 지연을 개선하고 저장 솔루션에 대해 걱정하지 않고 수평으로 확장할 수 있게 해주었습니다. 즉, 이것은 우리의 단일 실패 지점(Redis)을 제거하고 동시에 더 빠른 요청을 가능하게 했습니다!

효율적인 확장

우리가 문제의 일부를 어떻게 해결할 수 있는지 이해했지만, 예상되는 대량의 요청을 처리하는 좋은 방법은 아직 없었습니다. 우리는 이 문제에 대해 서버 수를 크게 늘리는 대신 더 효율적이고 똑똑하게 접근해야 했습니다. 결국, 우리는 한 클라이언트 요청이 Ratelimit 서비스에 대한 한 요청으로 번역되는 것을 원하지 않았습니다. 왜냐하면 규모가 큰 경우, Ratelimit 서비스에 대한 수백만 개의 요청은 비용이 많이 들기 때문입니다.

우리의 선택지는 무엇이었을까요? 우리는 많은 것들을 고려했지만, 우리가 고려했던 옵션 중 일부는

• 클라이언트에서 토큰을 미리 가져와서 로컬에서 요청에 응답하려고 시도합니다.
• 일련의 요청을 묶어 보내고, 응답을 기다린 후 트래픽을 통과시키는 것입니다.
• 요청의 일부만 보내기 (즉. 샘플링).

이러한 옵션들 중 어느 것도 특히 매력적이지 않았습니다; 프리페칭(a)은 초기화 중이거나 클라이언트에서 토큰이 소진되거나 만료될 때 많은 예외 상황이 있습니다. 배치 (b)는 불필요한 지연과 메모리 압박을 추가합니다. 그리고 샘플링 (c)은 높은 qps 경우에만 적합하며, 일반적으로 우리는 실제로 낮은 속도 제한을 가질 수 있습니다.

우리가 설계한 것은 배치 보고라는 메커니즘으로, 두 가지 원칙을 결합합니다: 1) 우리의 클라이언트는 중요한 요율 제한 경로에서 원격 호출을 하지 않을 것이며, 2) 우리의 클라이언트는 낙관적 요율 제한을 수행할 것입니다. 즉, 기본적으로 요청을 통과시키되, 특정 요청을 거부하려는 경우에만 거부합니다. 우리는 백엔드 서비스가 일정 비율의 초과 제한을 허용할 수 있기 때문에, 확장성을 위한 대안으로 비율 제한에 대한 엄격한 보장이 없어도 괜찮았습니다. 고수준에서 보면, 배치 리포팅은 클라이언트 측에서 로컬 카운팅을 하고 주기적으로 (예: 100ms)는 카운트를 서버에 보고합니다. 서버는 클라이언트에게 어떤 항목이 요율 제한이 필요한지 알려줄 것입니다.

배치 보고 흐름은 다음과 같이 보였습니다:

• 클라이언트는 통과시킨 요청 수(outstandingHits)와 거부한 요청 수(rejectedHits)를 기록합니다.
• 주기적으로, 클라이언트의 프로세스가 수집된 카운트를 서버에 보고합니다.
  • 예를 들어. KeyABC_SubKeyXYZ: outstandingHits=624, rejectedHits=857;
KeyQWD_SubKeyJHP: outstandingHits=876, rejectedHits=0
• 서버는 응답 배열을 반환합니다
  • KeyABC_SubKeyXYZ: rejectTilTimestamp=..., rejectionRate=...
    KeyQWD_SubKeyJHP: rejectTilTimestamp=..., rejectionRate=...

이 접근법의 이점은 엄청났습니다; 우리는 실질적으로 제로 지연 레이트 제한 호출을 할 수 있었고, 일부 꼬리 지연 호출에 비해 10배의 개선을 이루었으며, 레이트 제한 트래픽을 (상대적으로) 일정한 qps 트래픽으로 바꿀 수 있었습니다! 메모리 내 속도 제한을 위한 Dicer 솔루션과 결합하면, 여기서부터는 모두 순조롭게 진행되는 건가요?

세부사항이 중요합니다

비록 우리가 최종 목표에 대해 좋은 아이디어를 가지고 있었지만, 실제로 이를 현실로 만드는 데는 많은 엔지니어링 작업이 필요했습니다. 여기에는 우리가 겪었던 몇 가지 도전과 우리가 어떻게 이를 해결했는지가 포함되어 있습니다.

높은 Fanout

RateLimitGroup과 차원을 기반으로 샤딩이 필요했기 때문에, 이전에는 N 차원을 가진 단일 RateLimitRequest가 N개의 요청, 즉 전형적인 팬아웃 요청으로 변할 수 있었습니다. 이것은 배치 보고와 결합될 때 특히 문제가 될 수 있습니다. 왜냐하면 단일 배치 요청이 많은 수 (500개 이상)의 다른 원격 호출로 확산될 수 있기 때문입니다. 이 문제를 해결하지 않으면, 클라이언트 측의 대기 시간이 급격히 증가할 수 있습니다(원격 호출 1회 대기에서 500회 이상의 원격 호출 대기로), 서버 측의 부하도 증가할 수 있습니다(전체 원격 요청 1회에서 500회 이상의 원격 요청으로). 우리는 이를 Dicer 할당에 따라 설명자를 그룹화함으로써 최적화했습니다 - 같은 복제본에 할당된 설명자는 단일 요율 제한 배치 요청으로 그룹화되어 해당 대상 서버로 전송되었습니다. 이것은 클라이언트 측의 꼬리 지연 시간 증가를 최소화하는 데 도움이 되었고 (배치 요청은 중요한 경로에 있지 않지만 백그라운드 스레드에서 처리되므로 꼬리 지연 시간의 일부 증가는 허용 가능하며), 서버로의 증가된 부하를 최소화했습니다 (각 서버 복제본은 배치 주기당 클라이언트 복제본에서 최대 1개의 원격 요청을 처리합니다).

집행 정확도

배치 보고 알고리즘이 비동기식이며, 업데이트된 카운트를 요율 제한 서비스에 보고하기 위해 시간 기반 간격을 사용하기 때문에, 우리는 요율 제한을 집행하기 전에 너무 많은 요청을 허용할 가능성이 매우 높았습니다. 비록 우리가 이러한 제한을 퍼지로 정의할 수 있었지만, 우리는 X% (예를 들어, 5%) 이상의 제한을 넘어서지 않을 것이라는 보장을 주고 싶었습니다. 제한을 과도하게 초과하는 것은 주로 두 가지 이유 때문에 발생할 수 있습니다:

• 한 배치 창 (예를 들어, 100ms) 동안의 트래픽은 요율 제한 정책을 초과할 수 있습니다.
• 우리의 많은 사용 사례는 고정 창 알고리즘 과 초당 요율 제한을 사용했습니다. 고정 창 알고리즘의 속성은 각 "창"이 새롭게 시작된다는 것입니다 (즉. 리셋하고 0부터 시작하므로), 우리는 상수(하지만 높은) 트래픽 동안마다 요율 제한을 초과할 수 있습니다!

이 문제를 해결한 방법은 세 가지였습니다:

• 우리는 요율 제한 서비스 응답에 거부율을 추가하여, 과거의 기록을 사용하여 언제 그리고 얼마나 많은 트래픽을 클라이언트에서 거부할지 예측할 수 있었습니다.
  rejectionRate=(estimatedQps-rateLimitPolicy)/estimatedQps 이는 다가오는 초의 트래픽이 지난 초의 트래픽과 비슷할 것이라는 가정을 사용합니다.
• 우리는 과도한 트래픽의 명백한 경우를 즉시 차단하기 위해 클라이언트 측 로컬 속도 제한기를 추가하여 깊이 방어를 추가했습니다.
• 자동 샤딩을 구현한 후, 우리는 메모리 내 토큰-버킷 요율 제한 알고리즘을 구현했는데, 이는 몇 가지 큰 이점을 가져다 주었습니다:
  1. 이제 우리는 트래픽의 제어 가능한 폭발을 허용할 수 있습니다
  2. 더 중요한 것은, 토큰 버킷이 고정 창 알고리즘처럼 매 시간 간격마다 재설정하는 대신 지속적으로 카운트하고, 심지어 음수로 갈 수 있기 때문에 시간 간격을 건너뛰는 정보를 "기억"한다는 것입니다. 따라서, 고객이 너무 많은 요청을 보내면, 우리는 그들이 제한을 얼마나 초과했는지 "기억"하고, 버킷이 적어도 제로로 채워질 때까지 요청을 거부할 수 있습니다. 우리는 이전에 Redis에서 이 토큰 버킷을 지원할 수 없었습니다. 왜냐하면 토큰 버킷은 Redis에서 상당히 복잡한 작업을 필요로 했기 때문입니다. 이것은 우리의 Redis 지연 시간을 증가시켰습니다. 이제, 토큰 버킷이 매 시간 간격마다 기억 상실을 겪지 않기 때문에, 우리는 거부율 메커니즘을 없앨 수 있었습니다.
  3. 추가 버스트 기능을 활성화하지 않은 토큰 버킷은 슬라이딩 윈도우 알고리즘을 근사할 수 있으며, 이는 "리셋" 문제를 겪지 않는 고정 윈도우의 더 나은 버전입니다.

토큰 버킷 접근법의 이점은 그렇게 크기 때문에, 우리는 모든 속도 제한을 토큰 버킷으로 전환하게 되었습니다.

비행 중인 비행기 재구축

우리가 도달하고자 하는 최종 상태를 알고 있었지만, 그것은 중요한 서비스에 대해 두 가지 독립적인 주요 변경을 필요로 했고, 이 중 어느 것도 그 자체로 잘 작동할 것이라는 보장이 없었습니다. 그리고 이 두 가지 변경을 함께 롤아웃하는 것은 기술적이고 위험 관리적인 이유로 옵션이 아니었습니다. 우리가 해야 했던 흥미로운 일들 중 일부:

• 우리는 우리의 envoy ingress에 localhost 사이드카를 구축하여 배치 보고와 자동 샤딩을 적용할 수 있었습니다. 왜냐하면 envoy는 우리가 변경할 수 없는 서드 파티 코드이기 때문입니다.
• 메모리 내 속도 제한이 있기 전에, 우리는 배치 리포팅 요청의 꼬리 지연 시간을 줄이기 위해 Redis에 대한 쓰기를 Lua 스크립트를 통해 배치 처리해야 했습니다. 왜냐하면 설명자를 하나씩 Redis에 보내는 것은 네트워크 라운드 트립 때문에 너무 느렸기 때문입니다, 심지어 우리가 배치 실행으로 전환했다 해도 말이죠.
• 우리는 다양한 트래픽 패턴과 속도 제한 정책을 가진 트래픽 시뮬레이션 프레임워크를 구축하여, 이 전환 과정에서 우리의 정확성, 성능, 그리고 확장성을 평가할 수 있었습니다.

현재 상태와 미래의 작업

배치 보고와 메모리 내 토큰 버킷 요율 제한의 성공적인 롤아웃으로, 우리는 꼬리 지연 시간이 크게 개선되는 것을 보았습니다(일부 경우에는 최대 10배!) 그리고 서버 측 트래픽의 선형 이하 성장을 보았습니다. 우리의 내부 서비스 클라이언트들은 속도 제한 호출을 할 때 원격 호출이 없고, Ratelimit 서비스의 독립적인 확장을 할 수 있다는 것에 특히 만족하고 있습니다.

팀은 또한 서비스 메시 라우팅 및 제로 설정 과부하 보호와 같은 다른 흥미로운 영역에도 작업하고 있으므로, 더 많은 블로그 게시물을 기대해 주세요! 그리고 Databricks는 항상 더 훌륭한 엔지니어를 찾고 있습니다. 우리와 함께 할 수 있으면 좋겠습니다!

(이 글은 AI의 도움을 받아 번역되었습니다. 원문이 궁금하시다면 여기를 클릭해 주세요)