RAM 100TB를 추가로 절약한 방법 — 일관성 해싱을 수학과 Rust로 다듬기

본문

Cloudflare는 전 세계 수천 대의 서버와 페타바이트(PB) 규모의 RAM, 수백만 개의 CPU 코어를 운영하고 있으며, 모든 자원이 여러 서비스에 의해 높은 수준으로 사용되고 있습니다. 이런 규모에서는 작은 최적화도 전 세계 인프라에서 크게 확대됩니다. 이번 사례에서는 Pingora 기반 내부 로드 밸런싱 서비스인 Pingora Backend Router(PBR)의 일관성 해싱(consistent hashing) 구현을 손봐 전 세계에서 100TB 이상의 RAM을 회수했습니다. 이는 앞서 DNS 팀이 절약한 100TB에 추가되는 성과입니다.

PBR에서 일관성 해싱을 사용하는 이유

PBR은 URL을 기반으로 캐시 가능한 요청을 특정 서버로 라우팅합니다. 이를 통해 데이터센터마다 파일을 한 번만 저장하고, 각 파일이 어디에 있는지 안정적으로 찾을 수 있습니다. 일관성 해싱에서는 서버와 작업을 해시 함수의 출력값에 대응시키며, 해시 공간은 최댓값에서 0으로 이어지는 원형 링처럼 생각할 수 있습니다. 각 요청은 자신의 해시값에서 왼쪽 방향으로 가장 먼저 만나는 서버에 배정됩니다. 서버가 추가되거나 제거되어도 전체 요청을 크게 재배치하지 않는다는 점이 핵심입니다.

하지만 서버를 하나의 해시로만 표현하면 각 서버가 담당하는 링의 구간 크기가 크게 달라질 수 있습니다. 해시값은 사실상 무작위이므로 한 서버가 지나치게 큰 구간을 차지하고 다른 서버는 작은 구간만 차지하는 일이 발생합니다. 요청량은 서버가 차지하는 구간의 크기에 비례하므로, 이런 편차는 부하 불균형으로 이어집니다.

해시 개수와 통계적 편차

서버마다 여러 개의 해시를 배치하면 여러 구간을 합산하는 과정에서 길이가 긴 구간과 짧은 구간이 서로 상쇄되어 분포가 균등해집니다. NGINX의 서버당 기본 해시 개수는 160개이며, Pingora도 같은 값을 기본값으로 사용합니다. 예를 들어 서버가 100대일 때 서버당 해시가 하나뿐이면 변동계수(coefficient of variation)가 약 99%에 이르지만, 서버당 160개의 해시를 사용하면 약 8%까지 낮아집니다.

Cloudflare는 서버의 저장 공간에 따라 요청량을 배분해야 했기 때문에 ketama 알고리즘을 사용했습니다. 서버마다 저장 공간이 다르므로 디스크 용량을 가중치(weight)로 사용해 해시 개수를 조정합니다. 컴퓨팅 중심의 다른 서비스에서는 CPU나 GPU 개수가 가중치가 될 수도 있습니다. 또한 규정 준수(compliance) 요건이나 캐싱 기능의 활성화 여부에 따라 특정 요청을 처리할 수 있는 서버 집합이 달라집니다. 이 경우 하나의 링에 해시를 더 추가하는 것으로는 충분하지 않으며, 가능한 기능 조합마다 별도의 링이 필요합니다. 링이 많아질수록 저장해야 할 해시 데이터도 함께 커집니다.

Rust 구조체 정렬이 만든 메모리 비용

성능 팀의 조사에서 PBR은 pingora-ketama 관련 구조체에 예상보다 많은 메모리를 사용하고 있었습니다. 기존 구조체는 해시값을 저장하는 32비트 정수와 서버 인덱스를 저장하는 32비트 정수로 구성되어 있었습니다. 서버 인덱스가 16비트면 충분하다고 판단해 다음처럼 바꿀 수 있을 것처럼 보였습니다.

struct Point { hash: u32, index: u32, } struct PointV2 { hash: u32, index: u16, }

그러나 Rust의 메모리 정렬(alignment) 규칙 때문에 index를 u16으로 줄이는 것만으로는 구조체 크기가 줄지 않습니다. 가장 큰 필드인 hash가 4바이트 정렬을 요구하므로 구조체 전체 크기도 그 배수로 맞춰져야 하며, 결과적으로 최소 8바이트가 필요합니다. #[repr(packed)]를 사용하는 방법도 있지만 정렬되지 않은 메모리 접근과 관련된 문제 때문에 논쟁의 여지가 있습니다.

Cloudflare는 대신 두 값을 바이트 배열에 직접 저장하고 접근 시 getter로 변환하는 방식을 사용했습니다. 4바이트 hash와 2바이트 index를 합쳐 총 6바이트를 저장하는 Point([u8; 6]) 구조체를 만들고, from_ne_bytes를 이용해 각각 u32와 u16으로 읽습니다. 코드가 더 장황해지지만, 이 방식은 구조체 하나를 8바이트에서 6바이트로 줄여 일관성 해싱 메모리 사용량을 25% 낮췄습니다. 원문은 이 두 방식이 컴파일 후에는 같은 결과로 이어진다고 설명합니다.

해시를 90% 줄여도 되는가

Cloudflare는 서버당 해시 개수를 늘릴수록 부하 분포가 얼마나 정확해지는지 다시 계산했습니다. 연속적인 원형 링을 가정한 수학적 예측과 달리 실제 구현은 32비트 정수 해시를 사용하며, 해시 개수가 늘어날수록 충돌 확률이 빠르게 올라갑니다. 생일 문제(birthday paradox)로 알려진 현상입니다. 해시가 충돌하면 이상적인 경우에 각각 요청 분포에 기여해야 할 일부 항목이 무작위로 사라져 예측할 수 없는 오차가 생깁니다.

시뮬레이션과 예측값을 비교한 결과, 2,048대의 서버를 운영하는 데이터센터에서는 서버당 해시가 10,000개에서 100,000개 사이로 늘어날 때 충돌 때문에 오차율이 증가했습니다. 이 분석을 바탕으로 Cloudflare는 부하 분산에 눈에 띄는 오차를 추가하지 않으면서 서버당 생성하는 해시를 90% 줄일 수 있다고 판단했습니다. 따라서 구조체 저장 형식을 압축한 데 이어, 해시 링 자체의 크기도 크게 줄였습니다.

캐시를 무효화하지 않는 마이그레이션

해시 링을 바꾸면 일부 캐시 가능한 요청이 다른 백엔드로 이동합니다. 새 링이 더 효율적이더라도 네트워크 전체가 한 번에 새 링으로 전환되면 사실상 대부분의 캐시가 무효화될 수 있습니다. 그러면 RAM 최적화가 오리진(origin) 트래픽의 급증으로 바뀔 수 있기 때문에 Cloudflare는 전역 일괄 전환을 피했습니다.

전환 기간 동안 PBR은 기존의 큰 ketama 링과 새로 줄인 링을 모두 메모리에 보관했습니다. 각 요청은 기존 마이그레이션 프레임워크를 통해 어느 링을 사용할지 결정했으며, 요청 해시를 기준으로 한 전환 결정은 안정적으로 유지됐습니다. 문제가 발견되면 PBR을 다시 배포하지 않고도 새 요청을 기존 링으로 되돌릴 수 있어 롤백 경로도 확보했습니다.

배포는 작은 검증 위치에서 시작해 점점 더 큰 데이터센터 그룹으로 확대했습니다. 새 링을 사용하는 트래픽 비율과 새 링이 허용되는 데이터센터 범위를 독립적으로 조절한 것이 핵심입니다. 단순한 전역 비율 방식이었다면 모든 지역에서 캐시 교체가 동시에 일어났겠지만, 데이터센터 단위의 전환은 장애 범위를 제한하고 변경의 안전성을 검증하기 쉽게 했습니다. 과정에서는 백엔드 선택 추적, 링 버전 카운터, PBR 연결 오류, 프로세스 메모리, 시작 시간, 캐시 동작, 오리진 트래픽을 관찰했습니다. 전환이 100% 완료된 뒤에는 임시로 유지하던 기존 링 경로를 제거했습니다.

결과와 공개된 구현

변경 전후의 PBR 메모리 사용량을 비교한 결과, 큰 해시 링을 사용하는 PBR 버전이 완전히 제거된 시점에 사용 메모리가 급격히 감소했습니다. 전체 변경으로 Cloudflare는 100TB의 메모리를 절약했습니다. 관련 변경 사항은 pingora-ketama crate에 아직 공식적으로 크게 알리지 않은 Cargo feature 형태로 제공됩니다. v2 링에는 압축된 저장 형식, 더 빠른 정렬 방식, 노드당 기본 해시 개수를 조정하는 기능이 포함됩니다.

안정성과 제어 가능성을 우선했기 때문에 v1 링은 기존 pingora-ketama의 동작과 동일하게 유지됩니다. 라이브러리는 v1과 v2를 동시에 실행하고 요청별로 어느 링을 언제 사용할지 결정할 수 있도록 합니다. Cloudflare는 이 사례를 통해 Rust 자체보다도 시스템의 단순하거나 당연해 보이는 선택을 수치와 수학으로 다시 검토하는 과정이 큰 최적화로 이어질 수 있다고 설명합니다.

Hacker News 반응

• @agosta — 훌륭한 기사입니다! 일상적인 프로그래밍 과제에서는 미적분을 충분히, 아니 거의 전혀 사용하지 않는 사람으로서, Kevin이 그 유도 과정(보충 글에 링크되어 있습니다)을 파고든 내용이 정말 즐거웠습니다. 여기서 부정적으로 말하는 사람들은 모두 건포도나 삼키면 됩니다.
• @terabyteoff — 감사합니다! 사람들이 제가 당신에게 돈을 주고 이런 말을 하게 했다고 생각할 테니, 조금 자제해 주세요.
• @proc0 — Rust 부분은 해시를 저장하는 구조체에 관한 부분뿐인데, 2바이트가 그렇게 큰 차이를 만들 정도로 정말 많은 해시가 필요한가요? 글에서는 자세히 설명하지 않았지만, 모든 컴퓨터의 모든 작업마다 해시가 하나씩 있는 것이라면 그럴 수도 있겠네요.
• @agosta — 맞습니다. 바로 그 점, 즉 비용을 줄일 수 있었던 영역이 핵심입니다. 부하 분산을 저하시키지 않으면서 실제로는 얼마나 많은 해시를 없앨 수 있는지 알아낸 것입니다.
• @ricardobeat — 이런 최적화는 인상적이지만, 회사가 언제부터 서로 꿰뚫어 볼 수 없는 사일로의 집합이 되어 아무것도 예상대로 작동하지 않게 되는지 생각하게 됩니다. 요즘은 AI 덕분에 코드베이스를 탐색하는 일이 훨씬 빨라졌으니 이런 문제가 덜할 수도 있겠네요.

원문: Cloudflare Blog / 번역·요약: Trawling