TLB-Hit Model

TLB-Hit Model

• TLB-Hit Model: 자주 사용되는 변환 결과나 정책 판단 결과를 빠른 경로에 저장해두고, 같은 요청이 다시 들어왔을 때 복잡한 판단 과정을 생략하는 성능 모델
• TLB 는 Translation Lookaside Buffer 의 약자로, CPU 가 가상 주소를 물리 주소로 변환할 때 최근에 사용한 주소 변환 결과를 캐싱하는 구조이다.
  • CPU 가 메모리에 접근할 때 매번 Page Table 을 순차적으로 탐색하면 비용이 크다. 그래서 최근에 사용한 주소 변환 결과를 TLB 에 저장해두고, 같은 주소 영역에 다시 접근하면 TLB 에서 바로 변환 결과를 가져온다.
• TLB-Hit Model 은 이러한 TLB 의 동작 방식을 일반적인 시스템 성능 최적화 모델로 확장한 것이다.
  • 즉, 반복적으로 발생하는 요청에 대해 매번 전체 검증을 수행하지 않고, 이전에 계산한 결과를 캐시에 저장해두었다가 빠르게 재사용하는 방식이다.

TLB 의 기본 개념

TLB 를 이해하기 위해서는 먼저 가상 메모리와 주소 변환을 이해해야 한다.

현대 운영체제에서는 프로세스가 물리 메모리 주소를 직접 사용하는 것이 아니라, 가상 주소를 사용한다.

프로세스 입장에서는 자신만의 독립된 메모리 공간을 사용하는 것처럼 보이지만, 실제로는 운영체제와 MMU 가 가상 주소를 물리 주소로 변환해서 메모리에 접근한다.

예를 들어 어떤 프로세스가 다음과 같은 주소에 접근한다고 하면

0x7fffffff1234

이 주소는 실제 물리 메모리 주소가 아니라 가상 주소이다.

CPU 가 이 주소의 데이터를 읽으려면 해당 가상 주소가 실제 물리 메모리의 어느 위치에 매핑되어 있는지 알아야 한다.

이때 사용하는 자료구조가 Page Table 이다.

• Virtual Address: 프로세스가 사용하는 가상 주소
• Physical Address: 실제 메모리의 물리 주소
• Page Table: 가상 주소와 물리 주소의 매핑 정보를 저장하는 테이블
• MMU: 주소 변환을 수행하는 하드웨어 구성 요소
• TLB: 최근 주소 변환 결과를 캐싱하는 고속 캐시

즉, TLB 는 Page Table 을 매번 탐색하는 비용을 줄이기 위해 존재한다.

Address Translation

Address Translation 은 가상 주소를 물리 주소로 변환하는 과정이다.

프로세스가 메모리에 접근하면 CPU 는 해당 주소를 바로 물리 메모리 주소로 사용하지 않는다.

먼저 MMU 를 통해 주소 변환을 수행한다.

주소 변환 과정은 대략 다음과 같이 진행된다.

1. CPU 가 가상 주소로 메모리 접근을 요청한다.
2. MMU 가 해당 가상 주소의 변환 정보가 TLB 에 있는지 확인한다.
3. TLB 에 변환 정보가 있으면 바로 물리 주소를 얻는다.
4. TLB 에 변환 정보가 없으면 Page Table 을 탐색한다.
5. Page Table 에서 변환 정보를 찾으면 TLB 에 저장한다.
6. 변환된 물리 주소로 실제 메모리에 접근한다.

이때 3번처럼 TLB 에 변환 정보가 있는 경우를 TLB Hit 라고 하고, 4번처럼 TLB 에 변환 정보가 없어서 Page Table 을 탐색해야 하는 경우를 TLB Miss 라고 한다.

TLB Hit

TLB Hit 는 필요한 주소 변환 정보가 TLB 안에 이미 존재하는 경우이다.

예를 들어 CPU 가 특정 가상 주소에 접근하려고 할 때, 해당 가상 페이지가 어떤 물리 프레임에 매핑되어 있는지 TLB 에 저장되어 있다면 Page Table 을 다시 탐색할 필요가 없다.

이 경우 MMU 는 TLB 에 저장된 변환 정보를 바로 사용한다.

Virtual Address
        ↓
      TLB
        ↓
Physical Address

TLB Hit 가 발생하면 주소 변환 과정이 매우 빠르게 끝난다.

즉, TLB Hit 는 캐시 hit 와 비슷하게 볼 수 있다.

캐시에서 데이터를 바로 찾으면 메모리까지 내려가지 않아도 되는 것처럼, TLB 에서 주소 변환 정보를 바로 찾으면 Page Table 을 탐색하지 않아도 된다.

TLB Miss

TLB Miss 는 필요한 주소 변환 정보가 TLB 안에 없는 경우이다.

TLB 에 변환 정보가 없다면 MMU 는 Page Table 을 탐색해서 가상 주소에 대응되는 물리 주소를 찾아야 한다.

Virtual Address
        ↓
      TLB
        ↓
     Miss
        ↓
   Page Table Walk
        ↓
Physical Address

이 과정을 Page Table Walk 또는 Page Walk 라고 한다.

Page Walk 는 TLB Hit 에 비해 훨씬 비싸다.

특히 x86-64 환경에서는 다단계 Page Table 구조를 사용하기 때문에, 하나의 주소 변환을 위해 여러 단계의 Page Table Entry 를 읽어야 할 수 있다.

일반적인 4-level paging 기준으로는 다음과 같은 구조를 거칠 수 있다.

PML4
 ↓
PDPT
 ↓
PD
 ↓
PT
 ↓
Physical Page

즉, TLB Miss 가 발생하면 단순히 한 번 더 확인하는 수준이 아니라, 여러 단계의 메모리 접근이 추가될 수 있다.

그래서 메모리 접근 자체는 캐시에 존재하더라도, 주소 변환에서 TLB Miss 가 발생하면 전체 접근 시간이 증가할 수 있다.

TLB Hit Rate

TLB Hit Rate 는 전체 주소 변환 요청 중 TLB Hit 가 발생한 비율이다.

TLB Hit Rate = TLB Hit Count / Total Translation Count

예를 들어 전체 주소 변환 요청이 1000번 발생했고, 그 중 990번이 TLB Hit 라면 TLB Hit Rate 는 99% 이다.

990 / 1000 = 0.99

TLB Hit Rate 가 높다는 것은 대부분의 주소 변환이 빠른 경로에서 처리된다는 의미이다.

반대로 TLB Miss Rate 가 높다는 것은 Page Walk 가 자주 발생한다는 의미이다.

TLB Miss Rate = 1 - TLB Hit Rate

TLB Hit Rate 가 99% 라면 TLB Miss Rate 는 1% 이다.

TLB-Hit Model 의 핵심

TLB-Hit Model 의 핵심은 반복되는 작업을 빠른 경로에서 처리하는 것이다.

원래 TLB 는 주소 변환 결과를 캐싱한다.

하지만 이 구조를 일반화하면 다음과 같이 볼 수 있다.

• 자주 반복되는 요청은 캐시에 저장한다.
• 같은 요청이 다시 들어오면 캐시에서 바로 판단한다.
• 캐시에 없거나 복잡한 요청만 느린 경로로 보낸다.
• 정책이나 상태가 바뀌면 기존 캐시를 무효화한다.

즉, TLB-Hit Model 은 단순한 캐싱이 아니라, 빠른 경로와 느린 경로를 분리해서 전체 시스템의 평균 비용을 줄이는 모델이다.

Request
   ↓
Fast Path Cache
   ↓
Hit  →  Cached Decision
Miss →  Full Evaluation

여기서 중요한 것은 모든 요청을 캐시에 넣는 것이 아니다.

반복 가능성이 높고, 동일한 결과를 재사용할 수 있고, 상태 변화에 따라 안전하게 무효화할 수 있는 요청만 캐싱해야 한다.

Fast Path 와 Slow Path

TLB-Hit Model 에서는 보통 Fast Path 와 Slow Path 를 나누어서 생각한다.

• Fast Path: 캐시 hit 가 발생했을 때 실행되는 빠른 경로
• Slow Path: 캐시 miss 가 발생했을 때 전체 판단을 수행하는 느린 경로

Fast Path 는 매우 단순해야 한다.

Fast Path 안에서 복잡한 문자열 비교, 많은 조건 검사, 외부 통신, 동적 메모리 할당 같은 작업을 수행하면 빠른 경로의 의미가 줄어든다.

반대로 Slow Path 는 비교적 복잡한 판단을 수행할 수 있다.

예를 들어 보안 정책 판단 시스템이 있다고 하면 Slow Path 에서는 다음과 같은 작업을 수행할 수 있다.

• 명령어 경로 검사
• 파일 경로 prefix 검사
• 네트워크 주소 검사
• 프로세스 권한 검사
• 정책 테이블 탐색
• 감사 로그 생성

하지만 같은 요청이 반복된다면 매번 이 과정을 수행할 필요가 없다.

첫 번째 요청에서 Slow Path 로 판단한 결과를 캐시에 저장하고, 이후 같은 요청은 Fast Path 에서 바로 처리할 수 있다.

Decision Cache

TLB-Hit Model 을 보안 정책 판단에 적용하면 Decision Cache 라는 구조를 만들 수 있다.

Decision Cache 는 특정 요청에 대한 정책 판단 결과를 저장하는 캐시이다.

예를 들어 다음과 같은 요청이 있다고 하면

process: mcp-agent
operation: file_open
path: /home/user/workspace/test.txt

정책 엔진이 이 요청을 검사한 결과 허용이라고 판단했다면, 이 결과를 캐시에 저장할 수 있다.

key   = mcp-agent:file_open:/home/user/workspace/test.txt
value = allow

이후 같은 프로세스가 같은 파일을 다시 열려고 하면 전체 정책을 다시 검사하지 않고 캐시에 저장된 allow 결과를 바로 사용할 수 있다.

Request
   ↓
Decision Cache
   ↓
allow

이 구조가 TLB-Hit Model 과 유사한 이유는 TLB 가 주소 변환 결과를 저장하는 것처럼, Decision Cache 는 정책 판단 결과를 저장하기 때문이다.

• TLB: Virtual Address → Physical Address
• Decision Cache: Request Key → Policy Decision

즉, TLB-Hit Model 을 정책 엔진에 적용하면 주소 변환 캐시가 아니라 정책 판단 캐시로 확장할 수 있다.

Cache Key

TLB-Hit Model 에서 중요한 것 중 하나는 Cache Key 이다.

Cache Key 는 어떤 요청이 같은 요청인지 구분하기 위한 값이다.

Cache Key 를 너무 단순하게 만들면 서로 다른 요청이 같은 요청으로 잘못 판단될 수 있다.

반대로 Cache Key 를 너무 복잡하게 만들면 캐시 hit 가 잘 발생하지 않는다.

예를 들어 파일 접근 정책을 캐싱한다고 하면 다음과 같은 요소들을 Cache Key 로 사용할 수 있다.

• 프로세스 식별자
• 작업 종류
• 파일 경로
• 접근 권한
• 정책 세대 번호
• 네임스페이스 정보
• 사용자 식별자

단순히 파일 경로만 Cache Key 로 사용하면 문제가 생길 수 있다.

key = /etc/passwd

이렇게 하면 어떤 프로세스가 접근했는지, 읽기인지 쓰기인지, 현재 정책이 무엇인지 구분할 수 없다.

그래서 실제 정책 캐시에서는 보통 요청의 의미를 구분할 수 있는 정보들을 함께 묶어서 key 를 만든다.

key = process_id + operation + resource_id + permission + policy_epoch

이렇게 하면 같은 리소스라도 접근 주체나 접근 방식이 다르면 서로 다른 요청으로 판단할 수 있다.

Hit 와 Miss 의 비용 차이

TLB-Hit Model 은 hit 와 miss 의 비용 차이를 전제로 한다.

캐시 hit 의 비용이 miss 의 비용과 비슷하다면 캐시를 둘 이유가 없다.

TLB-Hit Model 이 효과적이려면 다음 조건이 필요하다.

• Fast Path 비용이 충분히 작아야 한다.
• Slow Path 비용이 상대적으로 커야 한다.
• 같은 요청이 반복적으로 발생해야 한다.
• 캐시 무효화 비용이 과도하게 크지 않아야 한다.

예를 들어 정책 판단 비용을 단순화해서 다음과 같이 표현할 수 있다.

Average Cost = Hit Rate * Hit Cost + Miss Rate * Miss Cost

Hit Rate 가 높고 Hit Cost 가 작을수록 전체 평균 비용은 줄어든다.

예를 들어 다음과 같은 값이 있다고 하면

Hit Rate  = 0.99
Hit Cost  = 100ns
Miss Cost = 5000ns

평균 비용은 다음과 같이 계산할 수 있다.

Average Cost = 0.99 * 100ns + 0.01 * 5000ns
             = 99ns + 50ns
             = 149ns

반대로 Hit Rate 가 50% 라면 다음과 같이 된다.

Average Cost = 0.5 * 100ns + 0.5 * 5000ns
             = 50ns + 2500ns
             = 2550ns

즉, TLB-Hit Model 에서는 Hit Rate 를 높게 유지하는 것이 매우 중요하다.

Locality

TLB-Hit Model 이 잘 동작하는 이유는 프로그램이나 시스템 요청에 Locality 가 존재하기 때문이다.

Locality 는 최근에 사용한 데이터나 리소스를 다시 사용할 가능성이 높다는 성질이다.

Locality 는 크게 두 가지로 나눌 수 있다.

• Temporal Locality: 최근에 접근한 대상에 다시 접근할 가능성이 높음
• Spatial Locality: 접근한 대상 근처의 다른 대상에 접근할 가능성이 높음

TLB 에서는 같은 페이지에 반복적으로 접근하면 Temporal Locality 때문에 TLB Hit 가 발생하기 쉽다.

또한 인접한 메모리 영역을 순차적으로 접근하면 Spatial Locality 때문에 같은 페이지 또는 가까운 페이지의 변환 정보가 재사용될 수 있다.

정책 판단에서도 비슷한 Locality 가 나타날 수 있다.

예를 들어 MCP Agent 가 특정 workspace 안에서 반복적으로 파일을 읽고 쓴다고 하면, 같은 경로 prefix 에 대한 접근이 반복된다.

/home/user/workspace/a.txt
/home/user/workspace/b.txt
/home/user/workspace/c.txt

이런 경우 매번 전체 정책을 검사하는 대신, workspace prefix 에 대한 판단 결과를 캐싱하면 빠르게 처리할 수 있다.

Policy Epoch

TLB-Hit Model 에서 캐시를 사용할 때 가장 조심해야 하는 부분은 오래된 판단 결과이다.

정책이 변경되었는데 이전 정책 기준으로 계산된 캐시 결과를 계속 사용하면 보안 문제가 발생할 수 있다.

예를 들어 기존 정책에서는 /tmp/test.txt 접근이 허용되어 있었다고 하면

/tmp/test.txt -> allow

이 결과가 캐시에 저장될 수 있다.

그런데 이후 정책이 변경되어 /tmp/test.txt 접근이 차단되었다고 하면

/tmp/test.txt -> deny

이때 기존 캐시에 저장된 allow 결과를 그대로 사용하면 정책 변경이 적용되지 않는다.

이 문제를 해결하기 위해 Policy Epoch 를 사용할 수 있다.

Policy Epoch 는 정책의 세대 번호이다.

정책이 변경될 때마다 Epoch 값을 증가시키고, 캐시 key 에 해당 Epoch 를 포함한다.

key = request + policy_epoch

예를 들어 기존 정책의 epoch 가 1 이었다면 캐시는 다음과 같이 저장될 수 있다.

key   = file_open:/tmp/test.txt:epoch_1
value = allow

정책이 변경되어 epoch 가 2 가 되면 같은 요청이라도 key 가 달라진다.

key   = file_open:/tmp/test.txt:epoch_2
value = deny

이렇게 하면 이전 정책에서 만들어진 캐시 결과를 현재 정책에서 잘못 사용하는 문제를 줄일 수 있다.

Cache Invalidation

Cache Invalidation 은 기존 캐시 값을 더 이상 사용할 수 없도록 만드는 과정이다.

TLB 에서도 Page Table 이 변경되면 기존 TLB Entry 를 무효화해야 한다.

예를 들어 어떤 가상 주소가 기존에는 물리 주소 A 에 매핑되어 있었는데, 이후 물리 주소 B 로 바뀌었다고 하면 기존 TLB Entry 를 그대로 사용하면 잘못된 주소에 접근하게 된다.

정책 캐시에서도 마찬가지이다.

정책이 바뀌었거나, 리소스 상태가 바뀌었거나, 프로세스 권한이 바뀌었다면 기존 캐시 결과를 무효화해야 한다.

Cache Invalidation 이 제대로 되지 않으면 다음과 같은 문제가 발생할 수 있다.

• 이미 차단되어야 하는 요청이 계속 허용됨
• 이미 허용되어야 하는 요청이 계속 차단됨
• 감사 정책이 변경되었는데 로그가 남지 않음
• 프로세스 권한 변경이 반영되지 않음

따라서 TLB-Hit Model 에서 캐시 hit 성능만큼 중요한 것이 캐시 무효화의 정확성이다.

L1, L2, L3 구조

TLB-Hit Model 은 여러 단계의 계층 구조로 확장할 수 있다.

CPU 의 캐시 구조가 L1, L2, L3 로 나뉘는 것처럼 정책 판단 파이프라인도 여러 단계로 나눌 수 있다.

예를 들어 다음과 같은 구조를 생각할 수 있다.

L1 Fast Path
    ↓ miss
L2 Semi-Fast Path
    ↓ miss
L3 Slow Path

L1 은 가장 빠른 경로이다.

L1 에서는 완전히 동일한 요청이나 매우 단순한 key 기반 판단만 처리한다.

request_key -> decision

L2 는 L1 보다는 느리지만 L3 보다는 빠른 경로이다.

L2 에서는 prefix match, resource id 기반 캐시, 간단한 정책 테이블 조회 같은 작업을 수행할 수 있다.

L3 는 가장 느린 경로이다.

L3 에서는 전체 정책 평가, 복잡한 조건 검사, 상세 로그 생성, 사용자 공간 연동 같은 작업을 수행할 수 있다.

이 구조의 목적은 대부분의 반복 요청을 L1 또는 L2 에서 처리하고, 정말 복잡하거나 새로운 요청만 L3 로 보내는 것이다.

eBPF 정책 집행에서의 TLB-Hit Model

TLB-Hit Model 은 eBPF 기반 정책 집행에서도 사용할 수 있다.

eBPF LSM 을 이용하면 파일 접근, 명령 실행, 네트워크 연결 같은 커널 경로에서 정책을 검사할 수 있다.

예를 들어 다음과 같은 Hook 이 있다고 하면

bprm_check_security
file_open
file_permission
socket_connect

각 Hook 은 시스템에서 매우 자주 호출될 수 있다.

만약 모든 Hook 호출마다 전체 정책을 검사하면 오버헤드가 커질 수 있다.

그래서 TLB-Hit Model 을 적용하면 반복되는 요청은 캐시 hit 로 빠르게 처리하고, 새로운 요청이나 복잡한 요청만 느린 정책 평가 경로로 넘길 수 있다.

예를 들어 파일 읽기 요청이 반복적으로 발생한다고 하면

file_permission:/home/user/workspace/a.txt:read

첫 번째 접근에서는 전체 정책을 검사한다.

L1 miss
L2 miss
L3 policy evaluation
decision = allow

그 후 결과를 캐시에 저장한다.

cache[file_permission:/home/user/workspace/a.txt:read] = allow

이후 같은 요청이 다시 들어오면 L1 에서 바로 처리된다.

L1 hit
decision = allow

이렇게 하면 커널 경로에서 반복적으로 발생하는 정책 판단 비용을 줄일 수 있다.

TLB-Hit Model 과 단순 캐싱의 차이

TLB-Hit Model 은 단순히 캐시를 사용하는 것과는 조금 다르다.

단순 캐싱은 결과를 저장하고 다시 사용하는 것에 초점이 있다.

반면 TLB-Hit Model 은 전체 시스템의 실행 경로를 hit 중심으로 설계하는 것에 가깝다.

즉, 중요한 것은 캐시 자료구조 하나를 추가하는 것이 아니라, 대부분의 요청이 빠른 경로에서 끝나도록 시스템을 설계하는 것이다.

• Fast Path 는 짧고 예측 가능해야 한다.
• Slow Path 는 복잡한 판단을 담당해야 한다.
• Hit Rate 를 높일 수 있는 key 설계가 필요하다.
• 정책 변경 시 안전한 invalidation 이 가능해야 한다.
• miss 가 발생해도 전체 시스템이 안정적으로 동작해야 한다.

이런 점에서 TLB-Hit Model 은 성능 최적화와 안정성 설계를 함께 고려하는 모델이라고 볼 수 있다.

정리

TLB-Hit Model 은 CPU 의 TLB 동작 방식에서 가져온 성능 최적화 모델이다.

TLB 는 가상 주소를 물리 주소로 변환한 결과를 캐싱하고, 같은 주소 변환 요청이 다시 들어오면 Page Table Walk 를 생략한다.

이때 변환 정보가 TLB 에 있으면 TLB Hit 이고, 없으면 TLB Miss 이다.

TLB-Hit Model 은 이 구조를 일반화해서 반복되는 요청을 빠른 경로에서 처리하고, 새로운 요청이나 복잡한 요청만 느린 경로에서 처리하도록 만든다.