전역 테이블 (Global Table) 방식 - 접근 제어 행렬의 희소性问题을 해결하기 위한 연결 리스트 구현

핵심 인사이트 (3줄 요약)

본질: 전역 테이블(Global Table)은 접근 제어 행렬에서 권한이 존재하는 칸만을 <도메인, 객체, 권한> 3단 튜플로 저장하는 자료구조이다. 빈 칸(Null)을 저장하지 않아 공간 복잡도를 $O(실제 권한 수)$로 절감한다.

가치: 이 희소성 압축(Sparse Compression) 덕분에, 수천만 개의 파일이 있는 시스템에서도 실제 권한 설정만 메모리에 저장하여 RAM을 절약할 수 있다.

한계: 권한 확인 시 리스트 전체를 순차 탐색해야 하므로 $O(N)$ 시간 복잡도가 발생하고, 중앙 테이블에 동시 접근 시 락 경합(Lock Contention) 문제가 발생한다.

1. 개요 및 배경 (Context & Necessity)

1.1 희소 행렬의 문제점

구분	전체 칸 수	실제 권한 칸	낭비 공간
수치	도메인 1만 × 파일 1만 = 1억 칸	약 1만 칸	99.99%

1억 칸의 메모리를 할당하면 대부분의 칸이 비어있어 극심한 메모리 낭비가 발생한다.

1.2 전역 테이블의 해결책

"권한이 있는 경우만 저장한다"

[ 기존 2차원 행렬 ]
        파일1     파일2     파일3
도메인A  Read     Null      Null
도메인B  Null     Read     Null
도메인C  Null     Read     Write

[ 전역 테이블 (Linked List) ]
Head -> < 도메인A, 파일1, {Read} >
      -> < 도메인B, 파일2, {Read} >
      -> < 도메인C, 파일2, {Read} >
      -> < 도메인C, 파일3, {Write} >

2. 아키텍처 및 핵심 원리 (Deep Dive)

2.1 시간-공간 트레이드오프

구분	2차원 배열	전역 테이블
공간 복잡도	$O(	D
시간 복잡도	$O(1)$ (인덱싱)	$O(N)$ (선형 탐색)
적용	메모리 풍부한 환경	메모리 제약 환경

2.2 동시 접근 문제

여러 프로세스가 동시에 전역 테이블에 접근하면:

읽기/쓰기 충돌 방지을 위해 뮤텍스 잠금(Mutex Lock) 필요
잠금 대기 시간이 증가하면 성능 저하 발생

3. 실무 적용: 방화벽 규칙 테이블

3.1 iptables와 전역 테이블

방화벽(iptables)의 규칙 체인도 전역 테이블과 유사한 구조다:

[Chain: INPUT]
Rule 1: DROP   IP 192.168.1.100
Rule 2: ACCEPT TCP 80
Rule 3: DROP   ALL

패킷이 들어올 때마다 위에서 아래로 순차적으로 규칙을 매칭한다. 규칙이 10만 개인 경우, 마지막 규칙까지 확인해야 하므로 $O(N)$ 시간이 소요된다.

3.2 eBPF와 해시 기반 최적화

최신 리눅스에서는 **eBPF(extended Berkeley Packet Filter)**를 활용하여:

규칙을 해시 테이블에 저장
평균 $O(1)$ 시간에 규칙 매칭

4. 기대효과 및 결론

공간 절약: 희소 행렬 문제를 해결하여 메모리를 효율적으로 사용
시간 비용: 선형 탐색으로 인해 접근 검증 시간이 증가
현대적 대안: eBPF, 해시 테이블 등을 활용한 최적화

관련 개념	설명
접근 제어 행렬 (573장)	전역 테이블의 원본 수학적 모델
ACL (575장)	접근 제어 행렬을 객체 기준으로 분할
Capability (576장)	접근 제어 행렬을 주체 기준으로 분할
해시 테이블	전역 테이블의 탐색 성능을 개선하는 자료구조

👶 어린이를 위한 3줄 비유 설명

전역 테이블은 학교의 **"출입 가능 명단"**과 같다. 모든 학생과 모든 교실의 관계를 적는 게 아니라, "출입 가능한 조합"만을 적어둔다.
공간 절약은名簿(명부)에서 빈 칸을 지우고 許可(허용)된 경우만 적는 것과 같다. 공간은 절약되지만, 모든 학생의 출입 가능 교실을 알려면名簿를 모두 읽어야 한다.
락 경합은 여러 名簿(명부) 관리자가 동시에名簿를 수정하려고 할 때, 한 명씩만 수정해야 해서 대기 시간이 발생하는 것과 같다.