Bloom filter로 글로벌 라우팅 속도를 200배 높인 방법

Vercel의 글로벌 라우팅 서비스가 경로 유효성 검증에 쓰던 JSON 파일이 대형 사이트에서 1.5MB+로 팽창해 싱글 스레드 이벤트 루프를 p99.9 기준 250ms 블록하는 병목을 유발했다. Bloom filter(확률적 자료구조)로 교체해 경로 조회 레이턴시를 p99 기준 200배 줄이고, 메모리 15% 감소, TTFB p75+ 10% 개선을 달성했다.

핵심 포인트

문제: 대형 이커머스·문서 사이트의 경로 조회 JSON 파일이 1.5MB+로 팽창, 싱글 스레드 이벤트 루프를 p99.9에서 250ms 블록했다.
Bloom filter는 false negative 없이 false positive만 발생하는 특성이 경로 유효성 검증에 딱 맞다 — 없는 경로를 있다고 오판하면 저장소 요청 1번 추가, 있는 경로를 없다고 오판하면 절대 안 된다.
Base64 비트 배열을 문자열로 파싱하지 않고 바이트 온디맨드 디코딩으로 필터 생성 속도를 파일 읽기 속도에 바인딩했다.
결과: p99 조회 레이턴시 100ms → 0.5ms(200배), p99.9 250ms → 2.4ms(100배). 파일 크기 70-80% 감소.
메모리 압박 해소로 GC 병목이 줄면서 레거시 JSON 방식 배포들도 전 percentile에서 속도가 향상됐다.

상세 정리

문제 맥락: 라우팅 서비스는 불필요한 저장소 요청·열거 공격 방지를 위해 매 요청마다 경로 존재 여부를 검증한다. 빌드 출력물의 모든 경로를 담은 JSON 파일을 파싱하는 방식이었다.
이벤트 루프 블로킹: Node.js 싱글 스레드 특성상 JSON 파싱 중 다른 요청을 처리할 수 없다. 중소 사이트는 1ms 미만이지만 대형 사이트(1.5MB+ 파일)에서 p99.9가 250ms까지 치솟았다.
Bloom filter 알고리즘: 키를 여러 해시 함수로 해싱해 해당 비트 인덱스를 1로 설정(삽입). 조회 시 동일하게 해싱해 모든 비트가 1이면 존재 가능, 하나라도 0이면 확실히 부재.
false positive/negative 비대칭 활용: false negative(존재하는 경로를 없다고 판단) 불가, false positive(없는 경로를 있다고 판단)만 발생. false positive 시 저장소 요청이 1번 더 나가는 비용만 추가돼 허용 가능한 트레이드오프다.
2서비스 조율: 빌드 서비스가 배포 경로들로 Bloom filter를 생성해 JSON Lines 파일로 업로드(1행: 파라미터 n/p/m/k/s, 2행: Base64 인코딩 비트 배열). 라우팅 서비스(Node.js)가 이를 로드해 쿼리.
바이트 온디맨드 디코딩: Base64 데이터를 문자열로 변환하면 거대한 문자열 객체 생성 비용이 발생. 대신 따옴표를 무시하고 바이트를 쿼리 시점에 온디맨드로 디코딩해 필터 생성 속도를 파일 읽기 속도에 바인딩했다.
성능 결과: p99 조회 레이턴시 100ms → 0.5ms(200배), p99.9 250ms → 2.4ms(100배). 라우팅 서비스 heap/메모리 15% 감소. TTFB p75 이상 10% 개선. 파일 크기 70-80% 감소.
부수 효과: 메모리 압박 해소로 GC 병목이 완화됐고, 이전 JSON 방식을 쓰는 레거시 배포들도 전 percentile에서 응답 속도가 향상됐다.

왜 읽나Bloom filter의 false negative/positive 비대칭이 실제 시스템에서 어떻게 활용되는지, Node.js 싱글 스레드 환경에서 대용량 자료구조 파싱 병목을 확률적 자료구조로 해결하는 과정과 200배 성능 수치를 함께 이해하고 싶은 백엔드·인프라 엔지니어에게 필수 참고서.

Vercel Blog 블로그

원문은 여기서 이어서 읽을 수 있어요

원문 읽기

읽음 (0)

·takedown 요청

Bloom filter로 글로벌 라우팅 속도를 200배 높인 방법

이 글과 비슷한

대규모 도그푸딩: cdnjs를 Cloudflare 개발자 플랫폼으로 이전하다

Dependabot 길들이기: 업데이트 묶고, 주기 늦추고, 보안은 빠르게

Cloudflare, 프라이버시 프로토콜 디버깅 CLI pvcli 오픈소스 공개