500ns 파서의 해부학: libphonenumber를 Rust로 포팅하기

프리랜스 프로젝트로 시작했다. Rust로 백엔드 서비스를 작성하고 있었고, 국제 전화번호를 검증해야 했다. 여느 Rust 개발자처럼 crates.io로 가서 그 작업에 가장 인기 있는 라이브러리를 가져왔다.

그리고 그들의 GitHub 이슈를 열어봤다.

내가 본 것은 오래도록 방치된, 처리되지 않은 버그들의 공동묘지였다. “국가 번호 부분이 어떤 경우에는 잘려 나갑니다”(Open). “국가 접두사와 같은 시퀀스로 시작하는 번호가 잘못 파싱됩니다”(Open). “00 접두사가 붙은 국제 번호가 파싱되지 않습니다”(Open).

Google의 거대한 C++ libphonenumber 라이브러리를 포팅하는 일은 믿을 수 없을 만큼 복잡한 작업이고, 그 크레이트의 저자들이 그 일을 감당해낸 것에 깊은 존경을 보낸다. 하지만 나는 그 버그들을 안고는 고객의 프로젝트를 출시할 수 없었다. 그래서 약간 미친 일을 하기로 했다. C++ libphonenumber를 버그-투-버그로 호환되게 포팅하되, 최대 성능을 위해 처음부터 새로 구축한 구현을 작성하는 것이었다.

아래는 라이브러리가 정규식에 대해 점점 더 “멍청해지도록” 만든 것이 어떻게 눈부시게 빠른 속도로 이어졌는지에 대한 이야기다.

Phase 1: 초기 프로토타입과 Protobuf 함정

첫 번째 도전은 단순히 Google의 C++ 코드베이스를 헤쳐 나가는 일이었다. 그 언어가 주력 언어가 아닐 때는 쉽지 않다. 나는 5,000줄짜리 파일들을 맹목적으로 복사하고 싶지 않았기 때문에, 로직을 Rust답게 모듈로 쪼개기 시작했다.

첫 번째 전략적 실수는 정규식을 다루는 방식이었다. Google의 라이브러리는 RE2를 사용하며 FullMatch, FindAndConsume 같은 정확한 경계 검사에 크게 의존한다. 나는 순진하게도 표준 regex 크레이트 호출로 바꾸고, match.start == 0 && end == strlen인지 확인하면 될 거라고 가정했다.

그다음은 메타데이터였다. 전화번호 검증은 지구상의 모든 국가에 대한 방대한 규칙 집합에 의존한다. 처음에는 이 데이터에 대한 Rust 구조체를 손으로 작성할 수 있을 거라 생각했다. 틀렸다. C++ 메타데이터 생성 스크립트는 원시 바이너리 protobuf 배열을 출력한다. 이를 읽기 위해 protobuf-gen을 사용해야 했다(다만 현재 prost나 더 커스텀한 무언가로 마이그레이션할 계획이다). 또 다른 초반 난관은 문자열 정규화였다. 이 라이브러리는 “Decimal Number” (Nd) 범주의 어떤 유니코드 문자든 표준 ASCII 숫자로 변환해야 한다. 이를 위해 거대한 ICU 라이브러리를 끌어오고 싶지 않았다. 내 해결책은 dec_from_char라는 별도의 경량 크레이트를 작성하는 것이었다. 초기에는 UnicodeProps.txt를 읽는 매크로로 생성한 거대한 match 문에 불과했다. Nd 문자가 그렇게 많지는 않기 때문에, 바이너리 크기를 작게 유지하면서도 수용 가능한 성능을 유지할 수 있었다. 동작하는 프로토타입이 생겼다. 기본 테스트 스위트도 통과했다. 그래서 나는 프로젝트에서 한동안 긴 휴식을 취했다.

Phase 2: 공백기와 경고 신호

코드베이스에서 떨어져 있던 동안, 한 유용한 기여자가 Pull Request를 열었다. 그들은 C++ RegexBasedMatcher를 Rust로 직접 포팅했고, Google 라이브러리가 사용하던 정확한 앵커드 매칭을 처리하기 위해 전역 RegexCache까지 포함시켰다. 업스트림 로직에 완벽하게 정확했다. 하지만 로컬에서 벤치마크를 돌렸을 때 나는 숨이 멎는 줄 알았다.

Formatting Comparison/rlibphonenumber: format(National)
                        time:   [3.5683 ms 3.5991 ms 3.6337 ms]
                        change: [+22240% +22556% +22875%] (p = 0.00 < 0.05)
                        Performance has regressed.

성능이 22,000% 이상 퇴보했다. 번호 하나를 포매팅하는 데 갑자기 밀리초가 걸렸다. 나는 정중히 PR을 거절하면서 이렇게 생각했다. “정확한 C++ 내부 호환성이 성능을 박살 내는 값어치는 없다.” 당시에는 이 PR이 내 코드에 있는 훨씬 더 깊은 결함을 드러내는, 아주 선명한 경고 신호였다는 사실을 깨닫지 못했다. 나는 대수롭지 않게 넘겼다.

Phase 3: 복귀와 차분 퍼저

몇 달 뒤, 나는 라이브러리로 돌아왔다. v1.0을 공개하기 전에, 내 라이브러리가 Google의 것과 완전히 동일하게 동작한다는 절대적인 증거가 필요했다. 수동으로 엣지 케이스를 작성하는 것은 불가능했기 때문에, 차분 퍼징(differential fuzzing)을 선택했다. cxx를 통해 원본 C++ 라이브러리를 링크하고, 두 구현에 수백만 개의 랜덤 문자열을 먹여 출력값을 비교했다.

퍼저는 거의 즉시 크래시가 났다. CD(+48X666666644 같은 문자열이 Rust 코드에서는 무효로 표시되는데 C++에서는 유효로 표시되고 있었다.

그제야 이해가 됐다. 몇 달 전 기여자는 단지 C++를 그대로 옮기기 위해서 그랬던 게 아니었다. 내 순진한 start == 0 && end == strlen 경계 검사는 복잡한 엣지 케이스에서 근본적으로 깨져 있었다. 내부 정규식 패턴이 구성된 방식 때문에, 내 단순한 경계 체크는 유효한 문자열이 통과하는 것을 허용하지 못하고 있었다. 나는 C++의 앵커드 정규식이 제공하는 정확함이 필요했다. 하지만 런타임에 문자열을 할당하고 컴파일하는 RegexCache의 22,000% 성능 페널티를 받아들이는 것은 절대 원치 않았다.

Phase 4: 빠른 방식으로 Regex 고치기

런타임에 문자열을 할당하지도 않고 전역 캐시를 락하지도 않으면서, 수천 개의 정규식을 어떻게 앵커링할까? 작업을 빌드 타임으로 옮기면 된다. 나는 XML 메타데이터를 파싱하는 Java 빌드 스크립트를 수정해 패턴을 미리 ^(?:...)$로 감싸도록 했다. 하지만 런타임에 정규식의 서로 다른 변형을 3개나 초기화하면 메모리가 부풀어 오른다. 대신 RegexTriplets라는 구조체를 만들었다.

#[derive(Debug, Clone)]
pub struct RegexTriplets {
    pub pattern_base: Option<String>,
    pub original: OnceLock<Result<Option<Regex>, crate::regexp::Error>>,
    pub anchor_start: OnceLock<Result<Option<Regex>, crate::regexp::Error>>,
    pub anchor_full: OnceLock<Result<Option<Regex>, crate::regexp::Error>>,
}

이 구조체는 스택에 놓이며 크기는 84바이트에 불과하다. pattern_base로 원시 문자열을 유지하고(내부 로직이 때로는 이를 슬라이스해야 하기 때문에), 특정한 정확 매치 변형이 요청될 때에만 실제 Regex 객체를 지연 초기화한다. 사실상 공짜인 Rust의 문자열 슬라이싱([..])을 활용함으로써, 최소한의 런타임 오버헤드로 C++ 구현의 정확함을 달성했다.

Phase 5: WASM, Regex-lite, 그리고 커스텀 유니코드 Trie

내 주요 목표 중 하나는 WebAssembly 지원이었다. Rust 백엔드 호스팅 비용을 내지 않고도 라이브 웹 프리뷰를 원했다. 하지만 초기 WASM 빌드는 몇 메가바이트나 됐다. 가장 큰 원인은 regex 크레이트였다. DFA 상태 머신을 WASM에 컴파일하는 것은 엄청난 공간을 차지한다. 나는 regex-lite로 바꿨고, 바이너리 크기는 보기 좋게 ~500kB까지 떨어졌다.

하지만 한 가지 문제가 있었다. regex-lite는 \p{L}(문자)이나 \p{N}(숫자) 같은 유니코드 범주를 지원하지 않는다. 국제 전화번호 라이브러리에서 완전한 유니코드 지원을 포기하는 것은 선택지가 아니었다. 이를 해결하기 위해 dec_from_char 크레이트를 완전히 새 코드 생성기로 다시 작성했다. 거대한 match 문 대신, 이제 build.rs가 필요한 유니코드 속성에 대해 Trie 비슷한 룩업 테이블을 미리 계산한다. 고정된 청크 크기를 사용해 0x10FFFF까지의 어떤 문자에 대해서도 O(1) 조회를 제공하는 배열을 생성한다.

impl Category {
    #[inline(always)]
    pub fn from_char(c: char) -> ::std::option::Option<Self> {
        let cp = c as u32;
        if cp > MAX_CODEPOINT { return None; }

        let index_idx = (cp >> SHIFT) as usize;

        // SAFETY: Arrays are generated to cover up to 0x10FFFF
        unsafe {
            let block_idx = *CATEGORY_INDICES.get_unchecked(index_idx) as usize;
            let offset = (cp & MASK) as usize;
            let final_pos = (block_idx << SHIFT) + offset;
            *CATEGORY_BLOCKS.get_unchecked(final_pos)
        }
    }
}

이 덕분에 중요한 핫 패스들에서 정규식을 완전히 제거할 수 있었다. 불필요한 후행 문자를 제거하는 작업은, 루프 내부에서 느린 정규식 매치를 수행하던 방식에서:

// The old, slow regex way
pub(crate) fn trim_unwanted_end_chars<'a>(&self, phone_number: &'a str) -> &'a str {
    // ... loop with regex.full_match() ...
}

생성된 테이블을 활용하는 단일 네이티브 Rust 이터레이터 메서드로 바뀌었다.

// The new, instant way
pub(crate) fn trim_unwanted_end_chars<'a>(&self, phone_number: &'a str) -> &'a str {
    phone_number.trim_end_matches(|c| {
        c != '#' && uniprops_without_nl::uniprops::Category::from_char(c).is_some()
    })
}

Phase 6: 제로 할당 포매팅

이 시점에서 파싱은 믿을 수 없을 만큼 빨랐지만, 포매팅은 국내 번호에 선행 0을 덧붙일 때 힙 할당이 필요했다. 진정한 제로-할당 포매팅을 달성하기 위해, 나는 이 인기 크레이트를 복제하고 수정해 zeroes_itoa라는 커스텀 정수-문자열 포매터를 작성했다.

pub fn format(&mut self, mut n: u64, leading_zero_count: usize) -> Cow<'_, str> {
    let mut curr = self.bytes.len();
    let buf_ptr = self.bytes.as_mut_ptr() as *mut u8;
    let lut_ptr = DEC_DIGITS_LUT.as_ptr();

    // ...
    let final_len = self.bytes.len() - curr;
    let bytes = unsafe { slice::from_raw_parts(buf_ptr.add(curr), final_len) };
    unsafe { str::from_utf8_unchecked(bytes).into() }
}

필요한 패딩이 64바이트 스택 버퍼를 초과하지 않는 한(전화번호에서는 사실상 불가능하다), 이는 Cow::Borrowed(&str)를 반환하며 시스템 할당자를 완전히 피한다.

최종 결과

차분 퍼징, 빌드 타임 정규식 컴파일, 커스텀 유니코드 Trie, 그리고 스택 할당 정수 포매팅을 통해 rlibphonenumber는 이제 완전히 안정적이며, Google 업스트림과 버그-투-버그 호환이고, 믿을 수 없을 만큼 빠르다.

아래는 Google 업스트림 C++ 구현과의 최종 성능 비교다.

전체 파싱은 ~500나노초, E.164 포매팅은 30나노초를 약간 넘는 수준에 도달했다.

고처리량 백엔드 서비스를 다루고 있다면, 저장소는 여기에서 찾을 수 있다: github.com/vloldik/rlibphonenumber