BPF LRU per-CPU hash map

  • BPF LRU per-CPU hash map(BPF_MAP_TYPE_LRU_PERCPU_HASH): Hash map 구조에 LRU eviction 과 per-CPU value 저장 방식을 함께 적용한 BPF map
  • BPF program 은 커널 내부에서 실행되기 때문에 일반적인 userspace 자료구조를 그대로 사용할 수 없다.
    • 그렇기 때문에 BPF program 에서 상태를 저장하거나, user space 와 데이터를 공유하거나, 반복적으로 조회되는 값을 캐싱하기 위해서는 BPF map 을 사용해야 한다.
  • BPF_MAP_TYPE_LRU_PERCPU_HASH 는 key-value 형태로 데이터를 저장하지만, value 를 CPU 별로 분리해서 저장하고 map 이 가득 차면 오래 사용되지 않은 entry 를 자동으로 제거한다.

즉, BPF LRU per-CPU hash map 은 다음 세 가지 개념이 합쳐진 map 이다.

  • Hash map
  • LRU
  • Per-CPU map

BPF map

BPF map 은 BPF program 과 user space 가 데이터를 주고받기 위해 사용하는 커널 내부 자료구조이다.

BPF program 은 커널 안에서 실행되기 때문에 일반적인 전역 변수나 동적 메모리 할당을 자유롭게 사용할 수 없다.

그래서 BPF program 이 실행 중에 상태를 저장해야 하거나, user space 프로그램이 BPF program 의 결과를 읽어야 할 때 BPF map 을 사용한다.

BPF map 은 보통 다음과 같은 용도로 사용된다.

  • 패킷 카운터 저장
  • 프로세스별 상태 저장
  • 정책 정보 저장
  • 이벤트 통계 저장
  • 캐시 저장
  • BPF program 과 user space 사이의 데이터 공유

예를 들어 특정 PID 에 대한 접근 허용 여부를 저장하고 싶다면, PID 를 key 로 두고 허용 여부를 value 로 저장할 수 있다.

key: pid
value: decision

BPF program 은 hook 이 실행될 때마다 map 을 조회해서 해당 PID 에 대한 정책 판단 결과를 가져올 수 있다.

Hash map

Hash map 은 key 를 기준으로 value 를 저장하는 자료구조이다.

BPF 에서 BPF_MAP_TYPE_HASH 는 일반적인 key-value 저장소로 사용할 수 있는 map 이다.

예를 들어 다음과 같은 형태로 데이터를 저장할 수 있다.

key: 1000
value: 1

여기서 key 는 1000 이고 value 는 1 이다.

BPF hash map 에서 key 와 value 는 단순한 정수뿐만 아니라 struct 로도 만들 수 있다.

예를 들어 정책 캐시에서는 다음과 같이 key 를 구성할 수 있다.

struct cache_key {
    __u32 pid;
    __u32 resource_hash;
};

이렇게 하면 단순히 PID 만으로 판단하는 것이 아니라, PID 와 resource hash 를 함께 묶어서 하나의 key 로 사용할 수 있다.

즉, BPF hash map 은 BPF program 내부에서 특정 key 에 대한 상태를 빠르게 조회하기 위해 사용되는 자료구조라고 볼 수 있다.

Per-CPU map

Per-CPU map 은 CPU 마다 별도의 value 저장 공간을 가지는 BPF map 이다.

일반적인 hash map 에서는 하나의 key 에 대해 하나의 value 가 존재한다.

key -> value

하지만 per-CPU hash map 에서는 하나의 key 에 대해 CPU 별 value 가 따로 존재한다.

key -> value for CPU 0
key -> value for CPU 1
key -> value for CPU 2
key -> value for CPU 3

즉, 같은 key 를 조회하더라도 현재 BPF program 이 실행 중인 CPU 에 따라 접근하는 value 슬롯이 달라질 수 있다.

이렇게 CPU 별로 value 를 분리하면 여러 CPU 가 동시에 같은 메모리 영역을 수정하는 상황을 줄일 수 있다.

일반적인 map 에서 여러 CPU 가 같은 value 를 동시에 수정하면 race condition 이 발생할 수 있다.

예를 들어 여러 CPU 가 동시에 같은 counter 를 증가시킨다고 하면, 값을 안전하게 갱신하기 위해 atomic 연산이나 spin lock 같은 동기화가 필요할 수 있다.

하지만 per-CPU map 에서는 CPU 마다 value 공간이 분리되어 있기 때문에 현재 CPU 의 value 만 수정하면 된다.

그래서 write-heavy 한 상황에서 성능상 유리하다.

단, per-CPU map 은 CPU 수만큼 value 공간을 따로 가져야 한다.

따라서 CPU 수가 많고 value 크기가 크면 메모리 사용량이 증가한다.

즉, per-CPU map 은 동기화 비용을 줄이는 대신 메모리를 더 사용하는 구조이다.

LRU

LRU 는 Least Recently Used 의 약자이다.

LRU 는 가장 오래 사용되지 않은 데이터를 먼저 제거하는 방식이다.

캐시에서 자주 사용되는 정책 중 하나이며, 제한된 크기의 저장 공간을 관리할 때 사용된다.

예를 들어 map 의 최대 entry 수가 3개라고 하면 다음과 같이 데이터가 들어갈 수 있다.

A
B
C

이 상태에서 새로운 데이터 D 를 넣어야 하는데 map 이 이미 가득 찼다면, 기존 데이터 중 가장 오래 사용되지 않은 entry 를 제거하고 D 를 넣는다.

B
C
D

이때 제거된 entry 가 A 라면, A 가 가장 오래 사용되지 않은 entry 였다고 볼 수 있다.

BPF LRU hash map 도 이와 비슷하게 동작한다.

max_entries 로 정해진 최대 entry 수에 도달했을 때 새로운 key 를 넣으려고 하면, 커널은 LRU 정책에 따라 기존 entry 중 하나를 제거하고 새로운 entry 를 넣는다.

BPF_MAP_TYPE_LRU_HASH

BPF_MAP_TYPE_LRU_HASH 는 일반적인 BPF hash map 에 LRU eviction 기능을 추가한 map 이다.

기본적인 hash map 은 map 이 가득 찬 상태에서 새로운 entry 를 넣으려고 하면 실패할 수 있다.

하지만 LRU hash map 은 map 이 가득 찬 상태에서 새로운 entry 를 넣으려고 할 때, 오래 사용되지 않은 entry 를 제거해서 공간을 확보할 수 있다.

즉, BPF_MAP_TYPE_LRU_HASH 는 다음과 같은 특징을 가진다.

  • key-value 형태로 데이터를 저장한다.
  • map 의 최대 크기는 max_entries 로 정한다.
  • map 이 가득 차면 LRU 정책에 따라 entry 를 제거한다.
  • value 는 모든 CPU 가 공유하는 하나의 value 이다.

일반적인 LRU hash map 은 여러 CPU 가 같은 value 를 볼 수 있다.

따라서 여러 CPU 가 같은 entry 를 동시에 수정하는 경우에는 동기화나 atomic 연산을 고려해야 한다.

BPF_MAP_TYPE_LRU_PERCPU_HASH

BPF_MAP_TYPE_LRU_PERCPU_HASH 는 LRU hash map 과 per-CPU hash map 이 합쳐진 형태이다.

즉, hash map 처럼 key-value 형태로 데이터를 저장하고, map 이 가득 차면 LRU 정책에 따라 entry 를 제거하며, value 는 CPU 별로 분리된다.

정리하면 다음과 같다.

  • key-value 형태로 데이터를 저장한다.
  • value 는 CPU 별로 따로 존재한다.
  • map 이 가득 차면 LRU 정책으로 오래 사용되지 않은 entry 를 제거한다.
  • BPF program 에서 bpf_map_lookup_elem() 을 호출하면 현재 CPU 의 value 슬롯에 접근한다.
  • BPF program 에서 bpf_map_update_elem() 을 호출하면 현재 CPU 의 value 슬롯에 접근한다.

예를 들어 CPU 0 에서 같은 key 를 조회하면 CPU 0 의 value 를 가져오고, CPU 1 에서 같은 key 를 조회하면 CPU 1 의 value 를 가져온다.

key A
    CPU 0 value
    CPU 1 value
    CPU 2 value
    CPU 3 value

이 구조는 각 CPU 에서 독립적으로 빠르게 갱신되는 데이터를 저장할 때 유용하다.

LRU_HASH 와 LRU_PERCPU_HASH 의 차이

BPF_MAP_TYPE_LRU_HASH 와 BPF_MAP_TYPE_LRU_PERCPU_HASH 는 둘 다 LRU eviction 을 지원한다.

하지만 value 저장 방식이 다르다.

  • BPF_MAP_TYPE_LRU_HASH: 하나의 key 에 대해 하나의 value 를 가진다.
  • BPF_MAP_TYPE_LRU_PERCPU_HASH: 하나의 key 에 대해 CPU 별 value 를 가진다.

예를 들어 key 가 A 라고 하면 BPF_MAP_TYPE_LRU_HASH 는 다음과 같은 구조가 된다.

A -> value

반면 BPF_MAP_TYPE_LRU_PERCPU_HASH 는 다음과 같은 구조가 된다.

A -> CPU 0 value
A -> CPU 1 value
A -> CPU 2 value
A -> CPU 3 value

따라서 모든 CPU 가 같은 값을 공유해야 하는 경우에는 BPF_MAP_TYPE_LRU_HASH 가 더 적합할 수 있다.

반대로 CPU 별로 독립적인 통계나 캐시를 유지하고 싶다면 BPF_MAP_TYPE_LRU_PERCPU_HASH 가 더 적합하다.

BPF_F_NO_COMMON_LRU

LRU hash map 을 이해할 때 헷갈리기 쉬운 부분이 BPF_F_NO_COMMON_LRU 이다.

BPF_MAP_TYPE_LRU_PERCPU_HASH 라고 해서 항상 LRU list 까지 CPU 별로 완전히 분리되는 것은 아니다.

기본적으로 LRU map 은 공통 LRU list 를 사용할 수 있다.

이때 BPF_F_NO_COMMON_LRU flag 를 사용하면 per-CPU LRU list 를 사용하도록 요청할 수 있다.

정리하면 다음과 같다.

BPF_MAP_TYPE_LRU_HASH
    BPF_F_NO_COMMON_LRU 없음 -> Global LRU, global value
    BPF_F_NO_COMMON_LRU 있음 -> Per-CPU LRU, global value

BPF_MAP_TYPE_LRU_PERCPU_HASH
    BPF_F_NO_COMMON_LRU 없음 -> Global LRU, per-CPU value
    BPF_F_NO_COMMON_LRU 있음 -> Per-CPU LRU, per-CPU value

여기서 중요한 것은 map type 과 LRU list 의 범위가 서로 다른 개념이라는 것이다.

BPF_MAP_TYPE_LRU_PERCPU_HASH 에서 per-CPU 라는 말은 value 가 CPU 별로 분리된다는 의미이다.

반면 BPF_F_NO_COMMON_LRU 는 LRU list 를 공통으로 사용할지 CPU 별로 나눌지에 대한 flag 이다.

즉, BPF_MAP_TYPE_LRU_PERCPU_HASH 와 BPF_F_NO_COMMON_LRU 는 같은 의미가 아니다.

Map 선언

libbpf CO-RE 스타일에서는 다음과 같이 BPF_MAP_TYPE_LRU_PERCPU_HASH map 을 선언할 수 있다.

#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>

struct cache_key {
    __u32 pid;
    __u32 resource_hash;
};

struct cache_value {
    __u64 decision;
    __u64 timestamp;
};

struct {
    __uint(type, BPF_MAP_TYPE_LRU_PERCPU_HASH);
    __uint(max_entries, 8192);
    __uint(map_flags, BPF_F_NO_COMMON_LRU);
    __type(key, struct cache_key);
    __type(value, struct cache_value);
} decision_cache SEC(".maps");

위 map 은 다음과 같은 의미를 가진다.

  • map type 은 BPF_MAP_TYPE_LRU_PERCPU_HASH 이다.
  • 최대 entry 수는 8192 개이다.
  • key 는 struct cache_key 이다.
  • value 는 struct cache_value 이다.
  • value 는 CPU 별로 분리된다.
  • LRU list 도 BPF_F_NO_COMMON_LRU 로 인해 CPU 별로 분리된다.

이런 형태는 고빈도 정책 판단 캐시나 CPU-local 통계 저장에 사용할 수 있다.

Lookup 동작

BPF program 에서 map 을 조회할 때는 bpf_map_lookup_elem() helper 를 사용한다.

static __always_inline int lookup_decision(struct cache_key *key)
{
    struct cache_value *value;

    value = bpf_map_lookup_elem(&decision_cache, key);
    if (!value)
        return -1;

    return value->decision;
}

BPF_MAP_TYPE_LRU_PERCPU_HASH 에서 bpf_map_lookup_elem() 을 호출하면 현재 CPU 에 해당하는 value 슬롯을 조회한다.

즉, 같은 key 라도 CPU 0 에서 조회하면 CPU 0 의 value 를 가져오고, CPU 1 에서 조회하면 CPU 1 의 value 를 가져온다.

이 때문에 per-CPU map 을 사용할 때는 “같은 key 이므로 항상 같은 value 가 나온다” 고 생각하면 안 된다.

현재 실행 중인 CPU 에 따라 value 가 달라질 수 있다.

Update 동작

BPF program 에서 map 에 값을 넣거나 갱신할 때는 bpf_map_update_elem() helper 를 사용한다.

static __always_inline int update_decision(struct cache_key *key, __u64 decision)
{
    struct cache_value value = {
        .decision = decision,
        .timestamp = bpf_ktime_get_ns(),
    };

    return bpf_map_update_elem(&decision_cache, key, &value, BPF_ANY);
}

BPF_ANY 는 key 가 없으면 새로 만들고, key 가 이미 있으면 기존 값을 갱신한다.

BPF_NOEXIST 는 key 가 없을 때만 새로 만든다.

BPF_EXIST 는 key 가 이미 있을 때만 갱신한다.

BPF_ANY     -> create or update
BPF_NOEXIST -> create only
BPF_EXIST   -> update only

LRU map 에서 update 는 eviction 과 연결될 수 있다.

map 이 아직 가득 차지 않았다면 새로운 entry 를 넣으면 된다.

하지만 map 이 max_entries 에 도달한 상태라면 새로운 entry 를 넣기 위해 기존 entry 중 하나를 제거해야 한다.

이때 LRU 정책이 사용된다.

Delete 동작

BPF program 에서 entry 를 삭제할 때는 bpf_map_delete_elem() helper 를 사용한다.

static __always_inline int delete_decision(struct cache_key *key)
{
    return bpf_map_delete_elem(&decision_cache, key);
}

삭제는 key 단위로 수행된다.

따라서 per-CPU value 를 가진 map 이라고 하더라도 key 를 삭제하면 해당 key 에 연결된 entry 가 제거된다.

즉, 특정 CPU 의 value 만 따로 삭제하는 방식이 아니라 key 자체를 제거한다고 이해하면 된다.

Userspace 접근

User space 에서 per-CPU map 을 조회할 때는 BPF program 내부에서 조회할 때와 다르게 생각해야 한다.

BPF program 내부에서는 현재 CPU 의 value 슬롯에 접근한다.

하지만 user space 에서 per-CPU map 을 읽으면 CPU 별 value 들을 함께 다뤄야 한다.

예를 들어 CPU 가 4개라면 user space 에서는 하나의 key 에 대해 다음과 같은 value 배열을 읽어야 한다.

value[0] -> CPU 0 value
value[1] -> CPU 1 value
value[2] -> CPU 2 value
value[3] -> CPU 3 value

따라서 counter 같은 값을 저장했다면 user space 에서는 CPU 별 값을 모두 합산해야 전체 값을 얻을 수 있다.

total = value[0] + value[1] + value[2] + value[3]

이 구조 때문에 per-CPU map 은 BPF program 내부에서는 빠르지만, user space 에서 값을 읽고 해석하는 과정은 조금 더 복잡해질 수 있다.

메모리 구조

BPF_MAP_TYPE_LRU_PERCPU_HASH 는 CPU 별 value 를 가지기 때문에 일반 hash map 보다 메모리를 더 많이 사용한다.

일반적인 hash map 은 하나의 key 에 대해 value 하나만 저장한다.

key -> value

하지만 per-CPU hash map 은 하나의 key 에 대해 CPU 수만큼 value 를 저장한다.

key -> value[CPU count]

예를 들어 value 크기가 16바이트이고 CPU 가 8개라면, 하나의 key 에 대해 value 저장 공간만 대략 128바이트가 필요하다.

16 * 8 = 128

여기에 hash map entry 관리에 필요한 커널 내부 메타데이터와 LRU list 관리 비용도 추가된다.

따라서 max_entries 를 크게 잡고 CPU 수가 많은 환경에서 사용하면 메모리 사용량이 빠르게 증가할 수 있다.

즉, per-CPU map 은 성능을 얻기 위해 메모리를 더 사용하는 구조이다.

LRU eviction 과정

LRU eviction 은 map 이 가득 찼을 때 새로운 entry 를 넣기 위해 기존 entry 를 제거하는 과정이다.

일반적인 hash map 에서는 map 이 가득 차면 새로운 entry 를 넣지 못하고 실패할 수 있다.

하지만 LRU hash map 에서는 오래 사용되지 않은 entry 를 제거해서 새로운 entry 를 넣을 수 있다.

흐름은 대략 다음과 같다.

  1. BPF program 이 새로운 key 를 update 한다.
  2. map 에 빈 공간이 있는지 확인한다.
  3. 빈 공간이 있으면 그대로 entry 를 추가한다.
  4. 빈 공간이 없으면 LRU 후보를 찾는다.
  5. 오래 사용되지 않은 entry 를 제거한다.
  6. 제거된 공간에 새로운 entry 를 넣는다.

다만 커널 내부의 LRU 구현은 단순한 linked list 하나로만 동작한다고 보면 안 된다.

성능과 lock contention 을 줄이기 위해 CPU-local 상태, global list, batch 처리 같은 구조가 함께 사용될 수 있다.

그래서 BPF LRU map 의 LRU 는 일반적인 userspace LRU 캐시처럼 모든 접근 순서를 완벽하게 정렬해서 관리하는 구조라기보다는, 커널 환경에서 성능과 근사적인 LRU 성질을 함께 고려한 구조라고 이해하는 것이 적절하다.

Global LRU 와 Per-CPU LRU

LRU map 에서 LRU list 는 global 로 관리될 수도 있고, CPU 별로 관리될 수도 있다.

Global LRU 는 모든 CPU 가 하나의 LRU list 를 공유하는 방식이다.

CPU 0
CPU 1
CPU 2
CPU 3
  -> Global LRU

이 방식은 전체 map 관점에서 오래 사용되지 않은 entry 를 고르기 쉽다.

하지만 여러 CPU 가 하나의 LRU list 를 함께 사용하므로 경합이 생길 수 있다.

Per-CPU LRU 는 CPU 마다 LRU list 를 따로 가지는 방식이다.

CPU 0 -> LRU 0
CPU 1 -> LRU 1
CPU 2 -> LRU 2
CPU 3 -> LRU 3

이 방식은 CPU 별 경합을 줄일 수 있다.

하지만 각 CPU 의 LRU list 가 분리되기 때문에 한 CPU 에서는 공간이 부족한데 다른 CPU 의 list 에는 여유가 있는 상황이 생길 수 있다.

즉, per-CPU LRU 는 성능상 유리할 수 있지만 전체 map 의 공간을 항상 균등하게 활용한다고 보기는 어렵다.

BPF_F_NO_COMMON_LRU 의 주의점

BPF_F_NO_COMMON_LRU 를 사용하면 LRU list 가 CPU 별로 분리된다.

이때 LRU node 는 서로 다른 LRU list 사이를 자유롭게 이동할 수 없다.

따라서 특정 CPU 의 LRU list 에서 entry pressure 가 높아지면 해당 CPU 의 list 안에서 eviction 이 일어난다.

반대로 다른 CPU 쪽 list 에 여유가 있더라도 그 여유 공간을 직접 가져와서 사용하는 방식은 제한될 수 있다.

그래서 BPF_F_NO_COMMON_LRU 는 성능을 위해 경합을 줄이는 선택이지만, 전체 공간 활용 관점에서는 trade-off 가 있다.

정리하면 다음과 같다.

  • Global LRU 는 전체 map 관점에서 관리하기 좋다.
  • Per-CPU LRU 는 CPU 간 경합을 줄이기 좋다.
  • Per-CPU LRU 는 CPU 별 공간 편차가 생길 수 있다.
  • BPF_F_NO_COMMON_LRU 는 value 를 per-CPU 로 만드는 flag 가 아니라 LRU list 를 per-CPU 로 만드는 flag 이다.

정리

BPF LRU per-CPU hash map 은 BPF_MAP_TYPE_LRU_PERCPU_HASH 를 의미한다.

이 map 은 hash map, LRU, per-CPU value 저장 방식을 결합한 BPF map 이다.

Hash map 이기 때문에 key-value 형태로 데이터를 저장하고, LRU map 이기 때문에 map 이 가득 차면 오래 사용되지 않은 entry 를 자동으로 제거한다.

또한 per-CPU map 이기 때문에 하나의 key 에 대해 CPU 별 value 공간을 따로 가진다.

'DevSec' 카테고리의 다른 글

API와 ABI  (0) 2026.06.15
PCB  (0) 2026.06.14
TLB-Hit Model  (0) 2026.06.13
eBPF for Windows  (0) 2026.06.11
eBPF  (0) 2026.06.10

티스토리툴바