프로덕션에서 발생한 소프트 락업 메시지를 계기로 BPF LPM 트라이의 병목을 추적하고, 트라이/프리픽스 매칭 개요와 벤치마크, 그리고 현재 커널 구현의 한계를 정리한다.
URL: https://blog.cloudflare.com/a-deep-dive-into-bpf-lpm-trie-performance-and-optimization/
Title: BPF LPM 트라이 성능과 최적화 심층 분석
2025-10-21
8 min read
이 글은 日本語로도 제공됩니다.
모든 것은 프로덕션에서 정체불명의 소프트 락업(soft lockup) 메시지 하나로 시작했습니다. 단 한 줄의 난해한 로그가, 우리가 쓰는 가장 기본적인 자료구조 중 하나인 BPF LPM 트라이의 성능이라는 깊은 굴로 우리를 이끌었습니다.
BPF 트라이 맵(BPF_MAP_TYPE_LPM_TRIE)은 네트워크 패킷을 라우팅할 때 IP 및 IP+포트 매칭 같은 작업에 대거 사용됩니다. 즉, 요청이 결과를 반환하기 전에 올바른 서비스들을 통과하도록 보장하는 데 쓰입니다. 이 자료구조의 성능은 고객에게 서비스를 제공하는 데 매우 중요하지만, 현 구현의 속도는 만족스럽지 못합니다. 우리는 BPF LPM 트라이 맵에 수백만 엔트리를 저장할 때 여러 병목을 경험했습니다. 예를 들어 엔트리 조회(lookup)가 완료되기까지 수백 밀리초가 걸리거나, 맵을 해제(free)하는 과정이 CPU 하나를 10초 이상 묶어 두는 경우가 있었습니다. 실제로 Cloudflare의 Magic Firewall 규칙을 평가할 때 BPF 맵이 사용되는데, 이런 병목 때문에 일부 고객에게서는 트래픽 패킷 손실까지 발생했습니다.
이 글에서는 트라이와 프리픽스 매칭이 동작하는 방식의 간단한 복습, 벤치마크 결과, 그리고 현재 BPF LPM 트라이 구현의 부족한 점들을 정리합니다.
트라이(trie) 자료구조를 마지막으로 본 지 오래됐거나(혹은 처음이라면), 트라이는 (이진 트리와 비슷한) 트리 자료구조로, 주어진 키에 대해 데이터를 저장하고 검색할 수 있으며 각 노드는 키 비트의 일부를 저장합니다.
검색은 경로를 따라 트리를 순회(traversal)하는 방식으로 수행되는데, 이 순회 경로는 사실상 키를 재구성합니다. 즉 노드가 전체 키를 저장할 필요가 없습니다. 이는 전통적인 이진 탐색 트리(BST)와 다릅니다. BST의 기본 불변식(invariant)은 왼쪽 자식 노드의 키가 현재 노드보다 작고 오른쪽 자식은 더 크다는 것입니다. BST는 각 검색 단계마다 비교를 해야 하므로 각 노드가 전체 키를 저장해야 합니다.
다음은 BST가 아래 키들의 값을 저장하는 예시입니다:
ABC
ABCD
ABCDEFGH
DEF
비교를 위해, 같은 키 집합을 저장하는 트라이는 다음과 같이 생길 수 있습니다.
이처럼 비트를 분할하는 방식은 데이터에 중복이 있을 때 매우 메모리 효율적입니다. 예를 들어 키에서 프리픽스가 흔하게 공유되는 경우, 공유되는 데이터는 노드 한 세트만 필요합니다. 이런 이유로 트라이는 문자열을 효율적으로 저장하는 데 자주 쓰입니다(예: 단어 사전). 문자열 “ABC”와 “ABCD”를 저장할 때 3바이트 + 4바이트(ASCII 가정)가 필요한 것이 아니라, “ABC”가 공유되므로 3바이트 + 1바이트만 있으면 됩니다(트라이에서 실제로 필요한 비트 수는 구현에 따라 달라집니다).
트라이는 더 효율적인 검색도 제공합니다. 예를 들어 BST에서 키 “CAR”가 존재하는지 확인하려면 루트의 오른쪽 자식(키 “DEF” 노드)으로 간 뒤, 그 왼쪽 자식을 확인해야 합니다. 존재한다면 그 위치에 있어야 하기 때문입니다. 트라이는 프리픽스 순서로 검색하므로 더 효율적입니다. 이 예에서는 트라이는 루트에서 이미 해당 키가 트라이에 있을지 없을지를 알 수 있습니다.
이 설계는 트라이가 최장 프리픽스 매칭(longest prefix match)을 수행하거나 CIDR 기반의 IP 라우팅에 매우 적합하게 만듭니다. CIDR은 IP 주소 공간을 더 효율적으로 사용하기 위해 도입되었습니다(더 이상 클래스가 8비트 단위 4개 버킷에 고정될 필요가 없음). 하지만 네트워크 부분이 어디에서든 끊길 수 있어 복잡성이 증가합니다. CIDR 스킴을 라우팅 테이블에서 처리하려면 정확히 일치하는 항목을 찾는 대신, 테이블에서 가장 긴(가장 구체적인) 프리픽스를 매칭해야 합니다.
트라이 탐색이 각 노드에서 1비트 비교만 수행한다면 그것은 바이너리 트라이(binary trie)입니다. 더 많은 비트를 비교한다면 멀티비트 트라이(multibit trie)라고 부릅니다. 트라이에는 IP나 서브넷 주소를 포함해 어떤 것이든 저장할 수 있습니다. 결국 모두 0과 1이기 때문입니다.
멀티비트 트라이의 노드는 바이너리 트라이보다 메모리를 더 쓰지만, 컴퓨터는 어차피 멀티비트 워드로 동작하므로 마이크로아키텍처 관점에서는 멀티비트 트라이가 더 효율적입니다. 더 빠르게 비트를 건너갈 수 있어, 데이터를 찾기 위해 필요한 비교 횟수가 줄어듭니다. 전형적인 공간 대 시간(space vs time) 트레이드오프입니다.
트라이에는 다른 최적화도 있습니다. 트라이에 저장하는 데이터의 분포가 균일하지 않아 성긴(sparse) 영역이 있을 수 있습니다. 예를 들어 멀티비트 트라이에 “A”와 “BCDEFGHI”를 저장한다면 노드는 몇 개나 필요할까요? ASCII를 사용한다면, 루트 노드에서 “A”는 왼쪽으로, “B”는 오른쪽으로 분기하는 바이너리 트라이를 만들 수 있습니다. 8비트 노드를 쓴다면 “C”, “D”, “E”, “F”, “G”, “H”, “I”를 저장하기 위해 7개의 노드가 더 필요합니다.
트라이에 다른 문자열이 없다면 이는 꽤 비효율적입니다. “B”를 매칭하고 첫 레벨에 도달하는 순간, 그 프리픽스를 가진 문자열이 트라이에 하나뿐임을 알 수 있고, 경로 압축(path compression)을 사용해 나머지 노드 생성을 피할 수 있습니다. 경로 압축은 “C”, “D”, “E” 같은 노드들을 “I” 같은 단일 노드로 대체합니다.
트리를 순회하다 “I”에 도달하면, 여전히 건너뛴 비트(“CDEFGH”)가 검색 키와 일치하는지 비교해야 합니다. 건너뛴 비트를 어디에 어떻게 저장하는지는 구현에 따라 다릅니다. BPF LPM 트라이는 단순히 리프 노드에 전체 키를 저장합니다. 데이터가 더 촘촘해질수록 경로 압축의 효과는 줄어듭니다.
반대로 데이터 분포가 조밀하고, 예를 들어 트라이의 첫 3레벨이 완전히 채워져 있다면 어떨까요? 이 경우 레벨 압축(level compression)을 사용하여 해당 레벨의 모든 노드를 2**3개의 자식을 가진 단일 노드로 대체할 수 있습니다. 이것이 레벨-압축 트라이(Level-Compressed Tries)가 동작하는 방식이며, 리눅스 커널의 IP 라우트 조회에서 사용됩니다(net/ipv4/fib_trie.c 참고).
다른 최적화도 많지만, 이 글에서는 여기까지만 다루어도 충분합니다. 왜냐하면 커널의 BPF LPM 트라이 구현은 우리가 방금 논의한 세 가지를 모두 충분히 활용하지 않기 때문입니다.
다음은 AMD EPYC 9684X 96코어 머신에서 BPF selftests benchmark를 실행한 수치입니다. 여기서 트라이는 1만(10K) 엔트리, 32비트 프리픽스 길이를 가지며, 키 범위 [0, 10K) 내 모든 키에 대해 엔트리가 존재합니다.
Operation Throughput Stddev Latency lookup 7.423M ops/s 0.023M ops/s 134.710 ns/op update 2.643M ops/s 0.015M ops/s 378.310 ns/op delete 0.712M ops/s 0.008M ops/s 1405.152 ns/op free 0.573K ops/s 0.574K ops/s 1.743 ms/op
1만 엔트리를 가진 BPF LPM 트라이를 해제(free)하는 시간이 눈에 띄게 큽니다. 최근 우리는 이것이 너무 오래 걸려 프로덕션에서 소프트 락업 메시지가 쏟아지는 문제를 겪었습니다.
이 벤치마크는 최악의 경우 동작을 어느 정도 보여줍니다. 키가 너무 촘촘하게 채워져 있어 경로 압축이 완전히 무력화됩니다. 다음 섹션에서는 조회(lookup) 연산을 살펴보며 어떤 병목이 있는지 알아봅니다.
kernel/bpf/lpm_trie.c의 LPM 트라이 구현은 앞서 소개한 최적화 중 일부를 포함합니다. 리프 노드에서는 멀티비트 비교가 가능하지만, 각 내부 노드(internal node)에 자식 포인터가 두 개뿐이기 때문에, 트리가 조밀하고 1비트만 다른 데이터가 많으면 멀티비트 비교는 사실상 1비트 비교로 퇴화합니다.
예를 들어 봅시다. 숫자 0, 1, 3을 BPF LPM 트라이에 저장한다고 가정합니다. 이 값들은 32비트 또는 64비트 머신 워드 하나에 충분히 들어가므로, 트라이에서 다음에 방문할 노드를 결정하는 데 비교 한 번이면 될 것 같기도 합니다. 하지만 그건 현재 노드가 3개의 자식 포인터를 지원할 때만 가능합니다(공정하게 말하면, 대부분의 트라이 구현은 그렇게 합니다). 즉, 3갈래 분기(3-way branching) 결정을 하고 싶지만 BPF LPM 트라이는 자식이 두 개뿐이라 2갈래 분기(2-way branch)로 제한됩니다.
아래는 이 2-자식 트라이의 다이어그램입니다.
리프 노드는 초록색으로 표시되어 있고, 중앙에는 이진 문자열 형태의 키가 있습니다. 8비트 비교 한 번이면 어떤 노드가 해당 키를 가지는지 충분히 결정할 수 있음에도, BPF LPM 트라이 구현은 부모(이 경우 주황색 루트 노드)에 자식이 2개뿐이어서 경로 순회에 2갈래 분기 결정을 ‘주입’하기 위해 중간 노드(파란색)를 삽입합니다. 리프 노드에 도달하면 BPF LPM 트라이는 키를 확인하기 위해 멀티비트 비교를 수행할 수 있습니다. 만약 노드가 더 많은 자식 포인터를 지원한다면, 위 트라이는 다음과 같이 바뀌어 3갈래 분기가 가능해지고 조회 시간이 줄어듭니다.
이 2-자식 설계는 트라이의 높이(height)에 영향을 줍니다. 최악의 경우 완전히 채워진 트라이는 사실상 높이가 log2(nr_entries)인 이진 탐색 트리처럼 되며, 트라이의 높이는 키를 검색하기 위해 필요한 비교 횟수에 영향을 줍니다.
위 트라이는 BPF LPM 트라이가 경로 압축의 한 형태를 어떻게 구현하는지도 보여줍니다. 키가 1비트만 다른 두 노드가 존재해 2갈래 분기가 필요할 때만 중간 노드를 삽입하면 됩니다. 3 대신 15(0b1111)를 삽입해도 트라이의 레이아웃은 바뀌지 않습니다. 여전히 루트의 오른쪽 자식에 노드 하나만 필요합니다.
마지막으로, BPF LPM 트라이는 레벨 압축을 구현하지 않습니다. 역시 이는 트라이의 노드가 두 자식만 가질 수 있기 때문입니다. IP 라우트 테이블은 보통 많은 프리픽스를 공유하며, 상위 레벨에서 조밀하게 채워진 트라이를 자주 보게 되므로, IP 라우트를 포함한 트라이에서는 레벨 압축이 매우 효과적입니다.
다음 그래프는 엔트리 수가 1개에서 10만(100K)개로 증가할 때 LPM 트라이의 조회 처리량(백만 ops/sec 단위)이 어떻게 저하되는지 보여줍니다.
100만 엔트리에 도달하면 처리량은 약 150만 ops/sec 수준이며, 엔트리 수가 증가할수록 계속 하락합니다.
왜 그럴까요? 처음에는 L1 데이터 캐시(L1 dcache) 미스율이 원인입니다. 트라이에서 순회해야 하는 노드들이 모두 캐시 미스 기회가 되기 때문입니다.
그래프를 보면 L1 dcache 미스율은 비교적 일정하게 유지되는데도 처리량은 계속 감소합니다. 약 8만(80K) 엔트리 즈음부터는 dTLB 미스율이 병목이 됩니다.
BPF LPM 트라이는 커널 메모리 프리리스트에서 개별 노드를 동적으로 할당하므로, 노드들은 임의의 주소에 존재할 수 있습니다. 즉 트라이를 따라 경로를 순회하면 거의 확실히 캐시 미스가 발생하고, 경우에 따라 dTLB 미스도 발생합니다. 엔트리 수와 트라이 높이가 증가할수록 상황은 더 나빠집니다.
BPF LPM 트라이의 현재 한계를 이해했으니, 이제 인터넷의 미래를 위해 더 성능 좋고 효율적인 해법을 만들기 위한 작업을 진행할 수 있습니다.
우리는 이미 이 벤치마크들을 업스트림 리눅스 커널에 기여했습니다. 하지만 시작에 불과합니다. 특히 우리의 워크로드에서 많이 쓰이는 조회(lookup) 함수를 중심으로 BPF LPM 트라이의 성능을 개선할 계획이 있습니다. 이 글에서 다룬 여러 최적화는 net/ipv4/fib_trie.c 코드에서 이미 사용되고 있으므로, 자연스러운 첫 단계는 그 코드를 리팩터링해 공통의 레벨-압축 트라이 구현을 재사용할 수 있도록 하는 것입니다. 앞으로의 블로그 포스트에서 이 작업을 심도 있게 다룰 예정입니다.
더 많은 성능 수치에 관심이 있다면, Jesper Brouer가 다음에 일부를 기록해 두었습니다: https://github.com/xdp-project/xdp-project/blob/main/areas/bench/bench02_lpm-trie-lookup.org.
Cloudflare의 커넥티비티 클라우드는 기업 전체 네트워크를 보호하고, 고객이 인터넷 규모의 애플리케이션을 효율적으로 구축하도록 돕고, 어떤 웹사이트나 인터넷 애플리케이션이든 가속하며, DDoS 공격을 막고, 해커를 차단하며, Zero Trust 여정을 지원할 수 있습니다.
어떤 기기에서든 1.1.1.1에 방문해 인터넷을 더 빠르고 안전하게 만드는 무료 앱을 시작해 보세요.
더 나은 인터넷을 만들기 위한 우리의 미션을 더 알고 싶다면 여기서 시작하세요. 새로운 커리어 방향을 찾고 있다면 채용 공고를 확인해 보세요.
