Cloudflare, Pingora 일관된 해싱 최적화로 RAM 100TB 절감

Cloudflare의 Performance 팀은 Pingora Backend Router(PBR)에서 사용하는 pingora-ketama 라이브러리의 과도한 메모리 사용 문제를 해결해 전 세계 인프라에서 100TB 이상의 RAM을 회수했다. 이는 대규모 분산 시스템에서 알고리즘 미세 조정이 미치는 거대한 영향을 보여준다.

일관된 해싱의 메모리 비효율성

PBR은 캐시 가능한 요청을 URL 기반으로 라우팅하기 위해 일관된 해싱을 사용한다. 기존 방식은 서버당 다수의 해시를 생성해 분포의 불균형을 줄였으나, 이는 상당한 메모리 오버헤드를 유발했다. 특히 기능별 서버 제한이 있는 경우, 기존 링에 해시를 추가할 수 없어 기능 조합별로 새로운 해시 링을 생성해야 하는 구조적 한계가 있었다.

Rust 기반 구조 최적화 및 해시 수 감소

Rust의 메모리 정렬 규칙으로 인해 발생하던 패딩을 제거하기 위해 #[repr(packed)] 대신 raw byte array와 getter를 사용하는 방식을 채택해 해싱 메모리 사용량을 25% 감소시켰다.

또한, 32-bit 해시의 Birthday Paradox 충돌 확률과 시뮬레이션 결과를 분석하여 서버당 해시 수를 90% 줄이기로 결정했다. 2048개 서버 규모에서 10,000~100,000 해시 범위까지 테스트한 결과, 해시 수 감소가 요청 분포의 예측 불가능한 오차로 이어지지 않음을 확인했다.

안전한 마이그레이션과 v2 링 도입

전역적인 캐시 무효화를 방지하기 위해 구버전(Ketama)과 신버전(소형) 링을 PBR 메모리에 동시 유지하는 마이그레이션 전략을 수립했다. 요청별로 링 버전을 선택할 수 있는 프레임워크를 통해 데이터센터 단위 점진적 롤아웃을 진행했으며, 최종적으로 구버전 링을 제거했다.

이 과정을 통해 개발된 pingora-ketama v2는 압축된 저장 형식과 빠른 정렬 알고리즘을 적용했으며, 현재 홍보되지 않은(unadvertised) cargo feature로 제공된다. v1과 v2 링을 동시에 실행할 수 있어 안정성을 확보하면서도 성능 개선을 달성했다.