AVX-512로 라우팅 테이블 조회를 가속한다 - planb-lpm 프로젝트

인터넷 라우터가 하는 일, 생각보다 까다로워요

라우터가 패킷을 받으면 가장 먼저 하는 일이 "이 IP 주소를 어디로 보낼까?"를 결정하는 거예요. 이걸 LPM(Longest Prefix Match, 최장 접두사 매칭)이라고 부르는데, 말이 어렵지만 원리는 간단해요. 라우팅 테이블에 2001:db8::/32, 2001:db8:1234::/48 같은 규칙들이 수십만 개 있을 때, 들어온 IP 주소와 가장 길게 겹치는 규칙을 찾아서 그 규칙이 가리키는 다음 홉(next hop)으로 보내는 거예요. 비슷한 걸 찾는 게 아니라 가장 구체적인 규칙을 찾는다는 게 핵심이에요.

이게 왜 어렵냐면, 글로벌 BGP 풀 테이블(Border Gateway Protocol의 전체 라우팅 테이블)은 IPv6만 해도 수십만 개 엔트리가 있고, 1초에 수백만~수천만 패킷을 처리해야 하거든요. 패킷 하나당 조회 시간이 마이크로초 단위로 관리돼야 해요. 그래서 하드웨어 라우터는 TCAM이라는 특수 메모리를 쓰는데, 이게 비싸고 전력도 많이 먹어요. 소프트웨어만으로 이 속도를 낼 수 있다면 범용 서버를 라우터로 쓸 수 있게 되고, 그게 요즘 핫한 "소프트웨어 데이터 플레인" 트렌드의 핵심이에요.

planb-lpm은 어떻게 빠르게 만들었을까

GitHub의 esutcu/planb-lpm 프로젝트는 AVX-512라는 인텔 CPU의 벡터 명령어 세트를 활용해서 IPv6 LPM 조회를 가속하는 C/C++ 구현이에요. AVX-512가 뭐냐면, 한 번의 CPU 명령으로 512비트, 즉 64바이트를 한꺼번에 비교하거나 계산할 수 있는 기능이에요. IPv6 주소가 128비트니까 AVX-512 레지스터 하나에 4개의 IPv6 주소를 올려놓고 한방에 비교할 수 있다는 뜻이죠.

데이터 구조로는 선형화된 B+ 트리(linearized B+-tree)를 써요. 이게 왜 중요하냐면, 일반적인 포인터 기반 트리는 노드를 따라갈 때마다 메모리 여기저기를 들르느라 CPU 캐시 미스가 많이 나거든요. 그런데 트리를 배열 하나에 연속적으로 깔아놓으면(linearize) 캐시 라인 단위로 한 번에 여러 키를 가져다 비교할 수 있어요. 이걸 AVX-512의 병렬 비교랑 합치면, 트리의 한 노드에서 16개 갈림길을 한 사이클에 비교해서 어디로 내려갈지 정할 수 있어요.

벤치마크도 실제 BGP 덤프 데이터를 써서 돌렸다고 해요. 합성 데이터가 아니라 진짜 인터넷 경로 분포를 쓴다는 점이 중요해요. 왜냐하면 LPM의 성능은 접두사 길이의 분포에 크게 좌우되거든요. 학술 논문에서 깔끔하게 균등 분포로 테스트한 결과랑 실제 BGP 테이블에서의 성능은 차이가 많이 나요.

업계 맥락: 소프트웨어 라우팅의 흐름

이 영역에서 유명한 선행 작품들이 꽤 있어요. DPDK에 기본 포함된 LPM 구현, VPP(Vector Packet Processing)의 mtrie, 그리고 리눅스 커널의 fib_trie 같은 것들이요. 학술 쪽으로는 DXR, SAIL, Poptrie가 잘 알려진 알고리즘이에요. Poptrie는 특히 IPv6에서 popcount 명령어를 이용해 비트맵 기반으로 조회를 압축한 우아한 설계라서 많이 참고돼요.

planb-lpm의 포지셔닝은 AVX-512 최신 기능을 적극 활용해서 캐시 친화성과 SIMD 병렬성을 동시에 극대화하는 쪽이에요. 요즘 인텔 Sapphire Rapids, AMD Genoa 같은 최신 서버 CPU가 AVX-512를 본격 지원하면서, 몇 년 전만 해도 "AVX-512 쓰면 클럭이 떨어져서 오히려 느려진다"던 얘기가 많이 완화됐거든요. 그래서 지금이 이런 SIMD 친화 라우팅이 재조명되는 타이밍이기도 해요.

한국 개발자에게 주는 시사점

통신사, 대형 CDN, 클라우드 인프라팀에서 일하는 분들이라면 직접적으로 관심 가는 주제일 거예요. KT, SK브로드밴드, LG U+ 같은 ISP는 물론이고, 네이버, 카카오 같은 곳에서도 자체 데이터 플레인을 고민하거든요. 일반 백엔드 엔지니어라도 캐시 친화적 자료구조 + SIMD라는 조합은 배워둘 가치가 커요. 검색 엔진, 피처 스토어, 시계열 DB 같은 곳에서 같은 테크닉이 재활용되거든요.

당장 실무에 이식할 게 아니더라도, 레포지토리를 받아서 벤치마크 코드를 읽어보는 것만으로도 좋은 공부가 돼요. 특히 _mm512_* 인트린식(intrinsic)들이 실제 어떤 문제 해결에 쓰이는지 감을 잡는 데 훌륭한 레퍼런스예요.