16.7.3.2 FSM(Finite State Machine) 및 Trie 트리 파싱을 통한 O(1) 해시 룩업(Hash Look-up) 강하 전술

정규표현식(Regex)을 남발한 ACL 권한 검열이 초당 150만 번 통과되어야 할 라우터의 스루풋을 고작 4만 번 수준으로 박살 냈다는 치명적 파멸(16.7.3.1장 참조)을 직면했다.
라우터 코어 스레드 한가운데 자리 잡은 이 “병목의 눈“을 뜯어고쳐야 한다. 초당 백만 번 쏟아지는 패킷 문자열(factory/robot_3/temp)이 권한 목록에 있는지 없는지 가장 무식하고, 가장 빠르게 검열해 내어 허가도장(Pass)을 찍어주는 궁극의 수학적 자료구조로 시스템을 환골탈태 시켜야 한다.

본 절에서는 비결정적 정규표현식(NFA/Regex)의 CPU 백트래킹 지옥을 불태워버리고, 오직 1바이트 포인터 점프만으로 검열을 0.01마이크로초 컷에 종결짓는 Trie (Prefix Tree) 기반 FSM(결정적 유한 상태 기계) 컴파일 및 O(1) 해시 적중(Hash Look-up) 강하 전술을 설파한다.

1. 인간의 룰(Rule)을 기계의 트리(Tree)로 분쇄 컴파일

인간 관리자는 여전히 룰을 짤 때 패턴을 쓰는 게 편하다.

Rule 1: factory/*/temp (어떤 로봇이든 온도 센서는 통과)
Rule 2: factory/robot_boss/video (보스 로봇의 영상만 통과)
Rule 3: sensor/** (sensor 밑의 모든 하위 트리 통과)

이걸 Zenoh 라우터가 매 패킷이 들어올 때마다 텍스트 비교를 하고 있으면 끝장이다.
아키텍트가 설계한 똑똑한 데몬은, 맨 처음 구동(Boot-up)되어 설정 파일을 읽어 들이는 그 1회용 찰나의 순간에! 저 인간 친화적 문자열 룰셋 1,000개를 모조리 갈아서 거대한 하나의 결정적 메모리 노드 트리(Trie FSM) 로 굳혀(Compile)버린다.

graph TD;
    Root["factory/ (Node 1)"] --> Wild["* (Node 2)"]
    Root --> Boss["robot_boss/ (Node 3)"]
    Wild --> Temp["temp (Node 4: 허용!)"]
    Boss --> Video["video (Node 5: 허용!)"]

이 메모리 가지치기 구조(Trie) 안에서는 정규식 문자열 검색 함수(std::regex_match)가 존재하지 않는다.
오직 들어오는 토픽 문자열을 슬래시(/) 단위로 토큰화(Tokenizing) 한 뒤, 다음 메모리 포인터 주소로 깡충깡충 뛰어넘는(Pointer Jump) 행위만 남는다.

2. 레이턴시 0의 예술: 결정적(Deterministic) 강하 타격

초당 백만 개씩 패킷이 미친 듯이 라우터 인터페이스를 치고 들어온다.
패킷의 문패가 factory/robot_7/temp 라면, 이 엔진의 연산은 어떻게 폭주하는가?

첫 단어 factory 를 본다. $\rightarrow$ O(1) 해시 테이블(Hash Table) 로 루트를 찔러 Node 1 주소를 따낸다. (CPU 소모: 극소)
다음 단어 robot_7 을 본다. Node 1의 자식 중 robot_7 이 없다. $\rightarrow$ 즉각 와일드카드(*) 분기점인 Node 2 로 상태(State) 포인터를 무조건 이동(Determine) 시킨다! (백트래킹 없음!)
마지막 단어 temp를 본다. Node 2의 자식에 temp 가 있다. $\rightarrow$ Node 4 도착! 거기에 “허용(Pass)” 도장이 찍혀있다. 끝!

이 과정에서 문자열 단위의 무거운 검사 루프는 단 한 번도 돌지 않았다.
슬래시를 기준으로 찢은 3번의 Key 조각들을 차례대로 O(1) 해시 룩업(Hash Look-up)하며 포인터 사다리를 3번 탔을 뿐이다(Time Complexity: 트리의 깊이 O(K) 에 절대 종속).

3. O(1) 해시 룩업과 스루풋의 부활

문자열 파싱을 버리고 Trie Tree + FSM State Transition 의 무식한 메모리 매핑 구조로 치환했을 때, 라우터 스레드의 성능 곡선은 비현실적일 만큼 폭발한다.

정규표현식 룰렛 1,000개가 걸려있을 때 텍스트 매칭 루프: 초당 4만 패킷 (CPU Core 100% 포화)
1,000개의 룰을 1개의 거대한 Trie FSM 구슬로 압축한 상태에서 Hash Look-up 강하 시: 초당 145만 패킷 (CPU 15% 이하!)

인가된 권한 룰셋(ACL Rules)이 10개든, 10만 개든 상관없이 검색 시간은 길어지지 않는다. 룰이 많아지면 처음에 메모리에 띄우는 Trie 트리의 덩치(RAM)가 10MB에서 100MB로 늘어날 뿐, 한 패킷이 들어와서 단어 3개를 타고 종착역(Pass/Deny)에 떨어지는 횟수(O(K))는 수학적으로 완벽하게 동일하기 때문이다.

데이터 라우팅의 Critical Path 한가운데에 놓인 보안 검열의 병목을, CPU 수학 연산(Regex) 계층에서 무식하지만 빠른 메모리 포인터 구조(Data Structure) 계층으로 강제 전이시키는 것. 인간의 느슨한 문자열 논리를 가장 딱딱하고 결정적인 메모리 오토마타 기계(FSM)로 선행 압축(Pre-compile)해 두는 이 통치 기법만이 10기가비트 선로의 쏟아지는 트래픽을 지연 오차 없이 도살하며 가려내는 분산 보안 아키텍처의 필승 런북이다.