RE#: F#로 구현한 세상에서 가장 빠른 정규식 엔진, 그 내부 구조와 한계

정규표현식(Regex) 엔진 아키텍처는 지난 수십 년간 크게 두 진영으로 나뉘어 있었습니다. 하나는 선형 시간 복잡도를 보장하지만 기능이 제한적인 Thompson NFA 방식이고, 다른 하나는 고급 기능을 지원하지만 악의적인 입력에 지수 시간으로 폭발해버리는 Backtracking 방식입니다.

최근 F#으로 작성된 RE#이라는 엔진이 POPL 2025에 논문과 함께 공개되었습니다. 교집합과 여집합 연산자를 지원하면서도 선형 시간 복잡도를 보장한다는 주장이죠. 솔직히 처음엔 학술적인 장난감 아닌가 의심했습니다만, 벤치마크와 내부 구현을 뜯어보니 엔지니어링 적으로 배울 점이 꽤 많았습니다. 단순히 이론을 구현한 것을 넘어, 실무적인 최적화가 듬뿍 담겨 있더군요.

오늘은 이 RE# 엔진이 어떻게 기존 산업계 표준 엔진들을 성능으로 압도했는지, 그리고 Hacker News에서 제기된 현실적인 한계점은 무엇인지 딥다이브 해보겠습니다.

Brzozowski 미분과 Minterm 압축

이 엔진의 핵심 기반은 1964년 Janusz Brzozowski가 고안한 정규식 미분입니다. 개념은 놀랍도록 단순합니다. 어떤 정규식 R에 대해 문자 c를 소비했을 때, 나머지 매칭해야 할 정규식을 반환하는 함수입니다.

예를 들어 hello를 h로 미분하면 ello가 됩니다. 이 방식의 가장 큰 장점은 교집합과 여집합 연산자에 대해서도 별도의 복잡한 상태 머신 변환 없이 자연스럽게 분배 법칙이 성립한다는 것입니다.

하지만 실무에서 미분 방식을 그대로 쓰면 알파벳 크기만큼의 상태 전이를 계산해야 하므로 메모리와 성능이 박살납니다. RE#은 이를 해결하기 위해 Minterm 압축을 사용합니다. 문자를 개별적으로 다루는 대신, 정규식이 관심을 가지는 동치 클래스로 묶어버리는 겁니다. 이 단순한 기법 하나로 메모리 사용량을 극적으로 줄이고 핫루프의 성능을 끌어올렸습니다.

NFA를 건너뛴 Lazy DFA와 llmatch 알고리즘

제가 가장 흥미롭게 본 부분은 매칭 알고리즘입니다. 보통 정규식 엔진은 NFA를 거쳐 DFA로 변환하거나 NFA 상태를 시뮬레이션합니다. NFA 시뮬레이션은 매칭 시 비용이 발생해 실무에서 대용량 텍스트를 처리할 때 병목이 됩니다. 반면 전체 DFA를 미리 빌드하는 것은 상태 폭발 위험이 있죠.

RE#은 NFA를 아예 건너뛰고, 미분을 사용해 필요한 DFA 상태만 런타임에 지연 생성합니다. 여기에 더해 RE#은 POSIX 표준인 매칭 의미론을 채택했습니다. 우리가 흔히 쓰는 PCRE 엔진은 먼저 선언된 분기를 우선하는 방식을 사용합니다. 이 방식은 교환 법칙이 성립하지 않아 논리 연산을 망가뜨립니다. 교집합과 여집합을 수학적으로 올바르게 지원하려면 순서에 상관없이 가장 긴 매치를 찾는 것이 필수적입니다.

이를 효율적으로 구현하기 위해 RE#은 양방향 스캔 기법을 사용합니다.

처음엔 첫 번째 매치를 찾기 위해 1TB짜리 로그 파일을 끝에서부터 읽는다고 생각해서 기겁했습니다. 하지만 이 알고리즘은 단일 매치가 아닌 텍스트 내의 모든 매치를 추출할 때 진가를 발휘합니다. 두 번의 선형 스캔만으로 완벽한 결과를 뱉어냅니다.

F#의 선택: 우아함과 더러움의 공존

언어 선택도 짚고 넘어갈 만합니다. F#은 대수적 데이터 타입과 패턴 매칭을 지원하므로 컴파일러나 정규식 AST를 모델링하는 데 압도적으로 유리합니다. 실제 RE#의 코드를 보면 AST 구조가 매우 깔끔하게 정의되어 있습니다.

하지만 핫패스로 들어가면 이야기가 달라집니다. 초당 수조 번 실행되는 DFA 매칭 루프를 최적화하기 위해 저자는 함수형 패러다임을 버리고 포인터와 메모리 풀을 동원했습니다. 이상은 함수형으로, 현실은 포인터로 타협하는 시스템 프로그래밍의 씁쓸한 진리를 다시 한번 확인하게 됩니다.

Hacker News의 비판적 시각: 정말 완벽한가?

Hacker News 스레드에서는 이 기술의 실무적 한계에 대한 날카로운 지적들이 쏟아졌습니다. 저 역시 동의하는 몇 가지 치명적인 포인트가 있습니다.

  • 상태 폭발과 DoS 취약점: 학계에서 이미 증명되었듯, 확장된 정규식의 DFA는 최악의 경우 이중 지수 크기로 폭발할 수 있습니다. 저자는 입력 문자 하나당 최대 하나의 상태만 생성되므로 괜찮다고 방어했지만, HN 유저들은 캐시된 DFA 상태가 누적되면 결국 메모리 고갈을 유발하는 공격 벡터가 될 수 있다고 반박했습니다.
  • 실시간 스트리밍 처리의 한계: 스캔 알고리즘은 전체 입력을 메모리에 올려두고 역방향 스캔을 해야 합니다. 따라서 네트워크 소켓에서 들어오는 스트림 데이터를 실시간으로 검사하는 유스케이스에는 전혀 적합하지 않습니다.
  • 네이밍 센스: 이건 기술적 문제는 아닙니다만, 닷넷 생태계에서 RE#이라는 이름은 JetBrains의 유명한 툴인 ReSharper와 너무 겹칩니다. 검색 엔진 최적화 측면에서 최악의 선택이 아닐까 싶네요.

총평

RE#은 정규표현식 엔진 역사에 기록될 만한 훌륭한 엔지니어링 성과입니다. 1960년대의 잊혀진 이론을 발굴해 현대적인 최적화와 결합한 점은 박수받아 마땅합니다. 특히 복잡한 로그 파싱 정규식을 작성할 때, 스파게티 코드를 짜는 대신 교집합과 여집합으로 속성을 우아하게 분리할 수 있다는 점은 엄청난 혁신입니다.

솔직히 당장 프로덕션에 도입할 수 있을까요? 외부의 악의적인 사용자가 입력하는 임의의 정규식을 처리해야 한다면 아직은 시기상조입니다. 하지만 내부 시스템에서 신뢰할 수 있는 정규식을 사용해 대규모 문서를 일괄 분석하는 배치 작업이라면, 현존하는 어떤 엔진보다 빠르고 정확한 결과를 제공할 것입니다.