NATS 내부에서 살펴보는 메시지 매칭 구현

NATS는 분산 시스템을 연결하는 기술이다. 메시지 주소 지정, 검색 및 교환, 서비스 스트림 처리를 담당하며, 서비스 간 데이터를 안전하고 빠르게 전달하는 Pub/Sub 기반 메시지 브로커다.

이번 아티클에서는 NATS 내부에서 메시지 처리를 수행하는 핵심 자료구조인 Sublist를 살펴보고, NATS가 subject 기반 메시징 시스템을 어떻게 효율적으로 운영하는지 알아본다.

subject 기반 메시징이란, 메시지를 특정한 subject에 따라 분류하고, 해당 subject에 관심 있는 구독자(subscriber)에게만 발행자(publisher)의 메시지를 전달하는 방식의 메시징 모델이다. 이는 이메일의 수신자 주소나 HTTP의 URL path와 비슷한 개념으로, 메시지의 라우팅 경로를 의미한다.

NATS는 subject를 중심으로 구독자와 발행자가 서로 연결된다. 발행자는 특정 subject에 메시지를 발행하고, 구독자는 그 subject에 대한 구독을 등록함으로써 메시지를 수신할 수 있다.

subject는 문자열 기반의 트리 구조로 구성되며, 구분자로 ‘.’을 사용한다. 이는 계층적인 이름 체계를 제공하여 유연하고 직관적인 메시지 설계를 가능하게 한다.

예를 들어, 센서 데이터를 보내는 시스템에서는 다음과 같이 subject를 구성할 수 있다:

• sensor.temp
• sensor.temp.room1
• sensor.humidity.room2

이러한 subject 체계는 다양한 용도에 맞게 주제를 구조화하고, 이를 기반으로 구독 범위를 세밀하게 조절할 수 있는 장점을 제공한다.

subscription은 subject와 정확히 일치하거나, 와일드카드를 이용하여 여러 subject에 대응할 수 있다.

와일드카드 종류:

• *: 단일 수준 와일드카드(partial wildcard). 예: sensor.*.room1은 sensor.temp.room1, sensor.humid.room1등에 매칭됨
• >: 다중 수준 와일드카드(full wildcard). 예: sensor.>는 sensor.temp.room1, sensor.temp.room2, sensor.humid등 모든 하위 subject에 매칭됨

이러한 유연한 패턴 덕분에 NATS는 동적인 환경에서도 강력한 확장성과 표현력을 가진 메시징 시스템을 제공한다. 서비스 간의 느슨한 결합(loose coupling)을 가능하게 하며, 시스템 확장성과 유지보수를 용이하게 만든다.

NATS는 subject 기반 메시징을 구현하기 위해 발행자의 발행과 구독자의 구독 이벤트를 서로 매칭해야 한다. 이를 효율적으로 실행하기 위해 NATS는 내부에서 Sublist라는 자료 구조를 이용하고 있다. 이 부분에 대한 NATS 내부 코드를 확인해보자.

발행 / 구독에 대한 내부 코드

확인할 NATS 버전: v2.11.0

(코드 내부에서 꼭 확인해야 할 중요한 부분은 🟩로 표시하고, 가볍게 넘어가도 될 부분은 ⬛로 표시한다.)

메시지 발행 부분

먼저 발행 부분 코드를 확인하자. 클라이언트의 발행 이벤트는 다음 함수에서 처리된다.

위 코드에서 acc.sl의 Match 메서드를 호출한다. acc.sl에 해당하는 타입은 NATS에서 Sublist라는 타입의 포인터이다.

메시지 구독 부분

이번에는 구독 부분 코드를 확인하자. 클라이언트의 구독 이벤트는 다음 함수에서 처리된다.

구독의 경우 acc.sl의 Insert 메서드를 통해 subject에 대한 정보를 Sublist 포인터에 추가한다.

결론

위 두 부분의 코드를 확인하면 다음과 같은 로직으로 구현돼 있음을 알 수 있다.

• 발행: Sublist의 Match 메서드를 호출하여 subject에 매칭된 대상에게 메시지를 전달한다.
• 구독: Sublist의 Insert 메서드를 호출하여 해당 subject를 구독하도록 구현한다.

따라서 실제 subject에 대한 구독자를 저장하고 찾는 로직은 Sublist의 Match와 Insert에 있다. 그럼 이제 이 두 메서드를 확인해보자.

Sublist는 prefix tree와 유사한 기능을 제공하기 때문에, 위에서 소개한 메서드를 확인하기 전에 prefix tree에 대해 잠시 알아보자.

prefix tree(또는 trie라 불린다)는 문자열 검색을 효율적으로 수행하기 위해 트리 구조로 구현된 자료구조이다. prefix tree는 문자열의 문자를 트리의 노드로 저장해 루트부터 말단 노드까지의 경로가 하나의 문자열이 된다. 예를 들어 ‘cat’, ‘cart’, ‘dog’에 대한 prefix tree는 다음과 같이 구성된다.

prefix tree는 문자열을 내부에서 효율적으로 활용하는데, 동작 방식에 다음과 같은 특징이 있다.

• 문자열 조회: 예시에서 ‘cat’을 찾으면 root부터 출발해 c → a → t 순으로 노드를 순회하며 탐색한다.
• 문자열 삽입: 예시에서 ‘car’를 추가하면 root부터 c → a를 찾고, r을 a의 자식 노드로 등록한다.

따라서 길이가 N인 문자열에 대해 조회와 삽입 연산은 O(N)의 시간복잡도를 가진다. 이 때문에 자동 완성과 문자열 검색에 자주 활용된다. NATS의 subject 매칭을 위한 Sublist 구현에서도 prefix tree의 로직과 유사한 부분이 존재한다.

이제 Sublist 내부 구현을 확인하기 전에 먼저 타입을 살펴보자.

이 부분에서 특이한 구현은 트리 구조를 level과 node 타입으로 분리하고 있다는 것이다. 트리는 root level부터 출발하고, 각 level은 여러 node로 구성된다. 이때 node의 next 필드는 level 타입으로 이루어진다.

먼저 구독자를 추가하는 Insert 메서드의 구현을 확인하자. 이 함수의 구현은 다음 단계로 나눠져 있다.

1. 문자열 토큰화
2. 문자열 토큰을 이용한 트리 노드 추가
3. 노드에 구독자 정보 추가

해당 부분에 대한 코드를 살펴보자.

먼저 토큰화는 다음과 같이 구현돼 있다. 단순한 일반적인 문자열 파싱이다.

다음으로 문자열 토큰을 이용한 트리 노드 추가 부분이다. 기본적인 로직은 prefix tree에서 문자열 삽입을 시도하는 경우와 매우 유사하다. 트리의 root부터 출발해 node와 level을 계층식으로 조회하고, 없는 경우 생성한다. 이때 *와 > 같은 특수 문자는 예외적으로 처리한다.

node 조회가 끝나면 구독자 정보를 해당 node에 추가한다.

즉, 코드로 확인한 세부 구현 방식은 다음과 같다.

1. 문자열 토큰화: 단순 반복문을 이용해 문자열 토큰을 분리한다.
2. 문자열 토큰을 이용한 트리 노드 추가: 문자열 토큰을 순회하며 prefix tree의 루트부터 말단 node까지 삽입 로직을 진행한다.
3. 노드에 구독자 정보 추가: 말단 node에 구독자 정보를 추가한다.

다음은 발행자가 메시지를 전달할 대상을 조회하기 위한 Match 메서드이다. 이 함수의 구현은 다음 단계로 이루어진다.

1. 캐시 체크
2. 문자열 토큰화
3. 매칭
4. 캐시 갱신

해당 부분의 코드를 살펴보자.
캐시로 사용하는 맵에서 subject에 대한 매치 결과를 가져온다.

문자열 토큰화 부분은 Insert 메서드에서 확인한 부분과 유사하다.

다음으로 매칭 로직이 동작하는 부분이다.

여기서 matchLevel이라는 함수를 호출하는데, s.root와 tokens을 전달해 result를 구성한다. 그럼 matchLevel 함수를 확인해보자.

이 함수에서 매칭 로직은 토큰을 순회하며 다음과 같이 동작한다.

• level이 없어 노드 매칭이 불가한 경우 즉시 종료한다.
• 현재 level에 ‘>’(full wildcard)가 있으면 현재 토큰부터 남은 토큰과 무조건 매칭돼 결과를 추가한다.
• 현재 level에 ‘*’(partial wildcard)가 있으면 다음 토큰부터 재귀 탐색한다.
• 현재 토큰과 일치하는 토큰 문자열이 있으면 다음 level로 이동한다.

마지막 토큰 순회를 마치고 node가 존재할 경우 해당 node의 결과를 추가한다. Match 함수의 특징은 입력인 subject에 wildcard가 없다는 것이다. 따라서 루트 노드부터 말단 노드까지 매칭할 때 각 노드가 가진 wildcard를 확인하며, Insert로 이전에 등록된 구독자 정보를 추가한다.

동작 예시
foo.bar.baz를 발행했을 때 만약 구독자가 다음의 subject를 구독하는 조건을 살펴보면 다음과 같이 매칭되는 것을 위 함수를 통해 확인할 수 있다.

1. foo.bar.baz ✅ 정확한 일치
2. foo.bar.* ✅ partial wildcard로 baz 포함
3. foo.bar ❌ 일치하지 않음
4. foo.* ❌ 단계가 맞지 않음
5. foo.> ✅ full wildcard로 일치
6. ✅ full wildcard로 일치

이후 결과를 단순하게 캐싱한다.

즉, Match 함수는 크게 다음과 같은 특징을 가진다.

• 캐시를 사용해 캐시가 존재하는 경우 early return 한다.
• 매칭 시 prefix tree의 검색 로직처럼 토큰을 순회하면서 말단 노드까지 찾아 결과를 생성한다. 이때 wildcard를 고려한 조건 분기를 통해 알맞은 구독자를 매칭한다.
• 캐싱 결과를 갱신한다.

NATS의 내부 메시징 매칭 로직을 살펴보았다. NATS 내부의 Sublist는 subject 기반 메시징의 성능과 확장성을 보장하는 핵심 자료구조로, 구독자 검색을 빠르게 수행할 수 있는 prefix tree 기반 구조를 가지고 있다.

Insert 메서드는 subject를 토큰 단위로 나누고 prefix tree 방식으로 트리를 구성해 구독자를 등록한다.

Match 메서드는 트리를 탐색해 일치하는 구독자를 효율적으로 찾는다. 이러한 구조를 통해 NATS는 여러 구독자가 존재하는 상황에서도 낮은 지연 시간과 높은 처리량을 유지할 수 있다.

참고자료

• Client Protocol | NATS Docs
• Subject-Based Messaging | NATS Docs