2. 캐시 내부 구조

LevelDB 캐시 메커니즘 분석 — 코드 레벨 딥다이브

GitHub 레포: https://github.com/sss654654/leveldb-cache-analysis 논문: KSC 2022 "LevelDB 캐시 구조 및 성능 분석" (홍수빈, 최민국, 유시환, 최종무) 기간: 2022.07 ~ 2022.12 | 단국대학교 System Software Lab 학부연구생

---

이 문서는 단국대학교 시스템 소프트웨어 연구실(DKU-StarLab)에서 6개월간 수행한 LevelDB 캐시 메커니즘 연구를 기술적으로 상세히 정리한 것이다. Google이 개발한 key-value 스토어 LevelDB의 내부 캐시 구조를 C++ 소스코드(cache.cc, table_cache.cc, db_impl.cc) 레벨에서 분석하고, AWS EC2에서 db_bench와 YCSB 벤치마크로 최적 캐시 파라미터를 도출하여 KSC 2022 학부생 논문으로 게재했다.

---

Part 2. 캐시 내부 구조

4. Table Cache(인덱스 캐시) — SSTable의 Index Block을 캐싱

Section 3에서 SSTable을 열 때마다 Footer → Index Block → Data Block 순으로 디스크를 읽는다고 했다.

Table Cache는 이 중 "Footer 읽기 + Index Block 파싱" 비용을 제거하는 캐시다. → 한번 열었던 SSTable의 Index Block을 메모리에 캐싱해두면, 다음에 같은 SSTable에 접근할 때 디스크를 건너뛸 수 있다.

Table Cache가 저장하는 것

Table Cache가 정확히 뭘 저장하는지부터 이해해야 한다.

Table Cache 구조:
┌─────────────────────────────────────────────┐
│  Key: file_number (SSTable 파일 번호)       │
│  Value: struct TableAndFile {               │
│    RandomAccessFile* file;  // 열린 SST 파일│
│    Table* table;            // Index Block  │
│  };                                         │
└─────────────────────────────────────────────┘

Key = SSTable의 file_number.

→ LevelDB는 SSTable 파일을 생성할 때마다 고유한 번호를 부여하므로, file_number로 어떤 SSTable인지 식별.

Value = TableAndFile 구조체. 두 가지를 묶어서 저장한다:

• RandomAccessFile* → 운영체제 레벨에서 열린 파일 핸들. 이게 캐싱되면 파일을 열 때 발생하는 open() 시스템 콜을 생략할 수 있다.
• Table* → 해당 SSTable의 Index Block 전체를 파싱한 결과.

여기서 "Index Block"이란 무엇인가?

• Section 2에서 SSTable은 여러 Data Block + Index Block + Footer 등으로 구성된다고 했다.
• 이 중 Index Block은 SSTable의 목차다.
• 구체적으로 말하면
  • "Data Block 0에는 user:000 ~ user:099가 있고 파일 내 offset은 0이다",
  • "Data Block 1에는 user:100 ~ user:199가 있고 offset은 4096이다" — 이런 매핑 정보가 전부 들어있다.
• 즉 Index Block 하나만 메모리에 있으면 그 SSTable 전체에서 원하는 key가 어느 Data Block에 있는지를 디스크를 더 읽지 않고도 바로 판단할 수 있다. 이것이 Table Cache에 Index Block을 캐싱하는 핵심 이유다.

Table Cache 용량과 실제 의미

• Table Cache의 기본 용량은 최대 1,000개 엔트리다 (벤치마크 도구 db_bench의 --open_files 옵션으로 조절).
• 엔트리 1개 = SSTable 1개의 {파일 핸들 + Index Block}이므로:
  • → Table Cache에 1,000개 엔트리가 들어있다 = 1,000개 SSTable 각각의 목차(Index)가 전부 메모리에 올라와 있다.
  • → 어떤 SSTable에 접근하든 "이 key는 Data Block 몇 번(offset 얼마)에 있다"를 디스크 없이 즉시 판단 가능.
  • → 반대로 SSTable이 1,200개인데 Table Cache가 1,000개라면?
  • 나머지 200개에 접근할 때는 캐시 미스가 발생하여 매번 디스크에서 Footer → Index Block을 읽어야 한다.

캐시 미스 vs 캐시 히트 — 두 경로의 차이

경로 1: 캐시 미스 — SSTable을 처음 열 때 거치는 과정이다.

FindTable(file_number=123):
  handle = cache_->Lookup(123)           // 캐시 엔진에 조회
  // → nullptr 반환 (캐시에 없음)

  // ── 캐시 미스: 비용 큰 작업 시작 ──
  file = TableFileName(123)              // 파일 경로 생성: "000123.ldb"
  f = NewRandomAccessFile(file)          // ① 파일 열기 (OS open() 시스템 콜)
  table = Table::Open(f)                 // ② 디스크에서 읽기 시작
  //  Table::Open 내부:
  //    1) 파일 끝에서 48바이트 읽기 → Footer 파싱       ← Disk Read #1
  //    2) Footer에서 Index Block의 위치(offset, size) 획득
  //    3) Index Block 읽기 및 파싱                      ← Disk Read #2
  //    4) Meta Index Block → Filter Block 로드          ← Disk Read #3
  tf = new TableAndFile{f, table}
  handle = cache_->Insert(123, tf, 1)    // ③ 캐시에 저장 (charge=1)
  return handle

캐시 미스 한 번에 최소 3번의 Disk Read + 1번의 open() 시스템 콜이 발생한다.

 

경로 2: 캐시 히트 — 같은 SSTable에 두 번째로 접근할 때다.

FindTable(file_number=123):
  handle = cache_->Lookup(123)           // 캐시 엔진에 조회
  // → handle 반환! (캐시에 있음)

  // ── 캐시 히트! ──
  // handle 안에 이미 TableAndFile이 들어있다:
  //   tf->file  = RandomAccessFile* (열린 파일 핸들 → open() 불필요)
  //   tf->table = Table* (Index Block이 이미 파싱되어 메모리에 존재)
  //
  // → Disk I/O = 0번. 시스템 콜 = 0번. 즉시 반환.
  return handle

캐시 히트 후 — Table Cache에서 Data Block 위치를 찾기까지

FindTable이 반환한 handle에서 Table 객체를 꺼내면, 이 Table 안에 Index Block이 이미 파싱된 상태로 존재한다. 이후의 흐름이 핵심이다.

TableCache::Get(file_number=123, key="user:150"):

  // Step 1: Table Cache에서 Index Block 획득
  handle = FindTable(123)                // 캐시 히트 → 메모리에서 바로 반환
  table = handle->value->table           // Table 객체 꺼냄

  // Step 2: Index Block에서 "key가 어느 Data Block에 있는지" 결정 (전부 메모리 연산)
  //
  // Index Block 내부 (메모리에 이미 존재):
  //   entry[0]: {last_key: "user:099",  offset: 0,    size: 4096}  → Data Block 0
  //   entry[1]: {last_key: "user:199",  offset: 4096, size: 4096}  → Data Block 1
  //   entry[2]: {last_key: "user:299",  offset: 8192, size: 4096}  → Data Block 2
  //
  // "user:150"을 찾는다면?
  //   → Index Block에서 Binary Search
  //   → "user:150" ≤ "user:199" → Data Block 1 (offset: 4096)에 있다!
  //   → Disk I/O 없이, 메모리 연산만으로 위치 결정 완료.

  // Step 3: Bloom Filter 확인 (Filter Block도 Table 객체 안에 메모리로 존재)
  //   → "user:150"이 Data Block 1에 정말 있을 수 있는가?
  //   → True  → Data Block 읽기 진행 (Step 4로)
  //   → False → 이 SSTable에는 key가 없음. 다음 SSTable로 넘어감. Disk I/O 완전 회피!

  // Step 4: Data Block 1을 실제로 가져와야 한다
  //   → 여기서 Block Cache가 개입한다 (Section 5)
  table->InternalGet(key)

비교 정리:

	캐시 미스 (최초 접근)	캐시 히트 (재접근)
파일 열기	open() 시스템 콜 실행	이미 열린 파일 핸들 재사용
Footer 읽기	디스크에서 48바이트 Read	불필요 (이미 파싱 완료)
Index Block	디스크에서 Read + 파싱	메모리에서 즉시 사용
Filter Block	디스크에서 Read	메모리에서 즉시 사용
"key가 어느 Block에?"	위 과정을 전부 거친 후에야 판단 가능	메모리의 Index Block에서 Binary Search → 즉시 판단
Disk I/O 횟수	최소 3회	0회

Table Cache가 히트하면 "이 SSTable에서 key는 Data Block 1(offset 4096)에 있다"라는 판단까지가 전부 메모리에서 끝난다.

남은 문제는 그 Data Block 1의 실제 데이터를 어떻게 가져오느냐다. 또 디스크에서 읽어야 하나? 여기서 Block Cache가 등장한다. → table->InternalGet(key)

---

5. Block Cache(블록 캐시) — Data Block과 Filter Block을 캐싱

Table Cache가 "어느 Block에 key가 있는지 찾는 지도(Index Block)"를 캐싱한다면,

Block Cache는 **"실제 데이터 자체(Data Block)"**를 캐싱한다.

Section 4의 흐름을 이어가면: Table Cache 히트로 "key가 Data Block 1(offset 4096)에 있다"까지 알게 되었다. 이제 그 Data Block 1을 읽어야 하는데, 또 디스크에서 읽으면 느리다. Block Cache가 이 Data Block을 메모리에 캐싱해두면 디스크를 건너뛸 수 있다.

Block Cache가 저장하는 것

Block Cache 구조:
┌──────────────────────────────────────────────┐
│  Key: cache_id + block_offset                │
│  Value: Block Data (Data Block 또는 Filter)  │
└──────────────────────────────────────────────┘

Key = cache_id + block_offset 조합.

• 왜 단순히 block_offset만 쓰지 않는가?
• 서로 다른 SSTable 파일에서 동일한 offset에 Block이 위치할 수 있기 때문이다.
• SSTable A의 offset 4096에 있는 Data Block과 SSTable B의 offset 4096에 있는 Data Block은 완전히 다른 데이터다.
• 이를 구별하기 위해 각 SSTable 파일에 고유한 cache_id를 부여하고, cache_id + block_offset 조합으로 유일성을 보장한다.
• 예: SSTable A(cache_id=7)의 offset 4096 → key는 "7_4096", SSTable B(cache_id=12)의 offset 4096 → key는 "12_4096".

Value = 파싱된 Data Block 전체.

• key-value 쌍들이 정렬되어 있고, restart point 배열도 함께 메모리에 올라온다.
• 캐시 히트면 이 Block 안에서 Binary Search로 원하는 key를 바로 찾을 수 있다.

Block Cache 용량과 실제 의미

• Block Cache의 기본 용량은 4MB다 (db_bench의 --cache_size 옵션으로 조절).
• Table Cache가 "엔트리 개수(SSTable 개수)"로 관리되는 것과 달리, Block Cache는 "메모리 바이트 크기"로 관리된다. 이 차이가 중요하다.
• 구체적으로 계산해보면:
  • Data Block 하나의 기본 크기는 4KB다.
  • 4MB 캐시에는 약 1,000개 Data Block이 들어간다.
  • 100MB 데이터를 저장하면 Data Block이 약 25,000개 생성된다.
  • 4MB 캐시로는 전체의 약 4%만 캐싱 가능하다.
  • 나머지 96%에 접근할 때는 캐시 미스가 발생하여 매번 디스크에서 Block을 읽어야 한다.
  • 이것이 Part 3 벤치마크에서 cache_size를 키울수록 readrandom 성능이 개선되는 이유다.

하나의 SSTable에 Data Block은 몇 개?

Data Block 하나의 기본 크기는 4KB (block_size 옵션, 기본값 4096 bytes).

SSTable 하나의 기본 최대 크기는 2MB (max_file_size, Compaction 출력 기준).

SSTable 1개 ≈ 2MB
Data Block 1개 ≈ 4KB
→ 하나의 SSTable 안에 Data Block ≈ 약 500개

 

(실제로는 Index Block, Filter Block, Footer 등도 공간을 차지하므로 약 450~490개 정도)

SSTable 파일 (2MB)
├── Data Block 0   (4KB)  ← key:aaa ~ key:bzz
├── Data Block 1   (4KB)  ← key:caa ~ key:dzz
├── Data Block 2   (4KB)  ← key:eaa ~ key:fzz
├── ...
├── Data Block 489 (4KB)  ← key:yaa ~ key:zzz
├── Filter Block
├── Meta Index Block
├── Index Block            ← "Data Block 0은 offset 0, Block 1은 offset 4096, ..."
└── Footer (48 bytes)

Block Cache의 캐싱 단위와 방식

핵심: Block Cache는 SSTable 단위가 아니라, Data Block 단위(개별 4KB 블록)로 캐싱한다.

Table Cache와의 결정적 차이가 여기에 있다:

• Table Cache: SSTable 1개 통째로 엔트리 1개
• Block Cache: SSTable 안의 Data Block 1개씩 엔트리 1개

즉 SSTable 하나에 Data Block이 500개 있으면, Block Cache에는 최대 500개의 별도 엔트리로 들어간다.

Block Cache는 필요할 때만, 요청된 블록만 캐싱한다 (Lazy Loading / On-Demand). SSTable을 열었다고 해서 그 안의 Data Block 500개가 한꺼번에 캐시에 올라오는 게 아니다.

Get("user:150") 호출
  │
  ├─ Table Cache 히트 → Index Block이 메모리에 있음
  │   → Index Block에서 Binary Search
  │   → "user:150은 Data Block 37번(offset 151552)에 있다" 판단
  │
  └─ Block Cache에서 "이 SSTable의 Data Block 37번" 조회
      │
      ├─ [캐시 히트] → 이미 메모리에 있음 → 바로 반환
      │
      └─ [캐시 미스] → 아직 이 블록을 한 번도 읽은 적 없음
           │
           ├─ 1) 디스크에서 offset 151552 위치의 4KB를 읽음 (Disk Read 1회)
           ├─ 2) CRC32 체크섬 검증 (데이터 손상 확인)
           ├─ 3) Snappy 압축 해제 (압축되어 있는 경우)
           ├─ 4) Block 객체로 파싱 (restart point 배열 구성 등)
           │     → 이 파싱된 Block 객체가 "캐싱되는 데이터"
           └─ 5) Block Cache에 Insert
                 key = "cache_id(7) + offset(151552)" → "7_151552"
                 value = 파싱된 Block 객체 (4KB)
                 charge = 4096 (이 블록의 바이트 크기)

두 캐시의 역할 비교

	Table Cache	Block Cache
한 마디로	"SSTable의 목차"를 캐싱	"실제 데이터"를 캐싱
캐싱 대상	Index Block + 파일 핸들	Data Block, Filter Block
Key	file_number (SSTable 번호)	cache_id + block_offset
용량 단위	엔트리 개수 (기본 1,000개)	바이트 크기 (기본 4MB)
db_bench 옵션	--open_files(엔트리 개수 조절)	--cache_size(바이트 크기 조절)
히트 시 효과	파일 열기 + Footer + Index 파싱 전부 생략	디스크에서 Block 읽기 생략
미스 비용	크다 (시스템 콜 + Disk Read 3회)	중간 (Disk Read 1회)
동작 순서	먼저 조회 (1단계)	Table Cache 히트 후 조회 (2단계)

두 캐시는 계층적으로 동작한다:

1. Table Cache 먼저 조회 → Index Block으로 "key가 어느 Data Block에 있는지" 결정
2. Block Cache 조회 → 그 Data Block의 실제 데이터를 반환

---

여기까지가 "Table Cache가 뭘 저장하고", "Block Cache가 뭘 저장하는지"다.

그런데 Section 4의 FindTable 코드를 보면 cache_->Lookup(123), cache_->Insert(123, tf, 1)이 나왔고,

Section 5의 Block Cache에서도 block_cache->Lookup(cache_key), block_cache->Insert(cache_key, block, block_size)가 나왔다. 변수 이름만 다를 뿐 둘 다 동일한 Lookup()과 Insert()를 호출하고 있다.

이 cache_의 정체가 뭔가? Table Cache든 Block Cache든 내부적으로 동일한 캐시 엔진을 사용한다. 이 엔진이 어떤 구조로 되어 있는지를 Section 6~9에서 분석한다.

---

6. 캐시 엔진의 기본 단위 — LRUCache

Table Cache와 Block Cache가 공유하는 캐시 엔진을 이해하려면, 먼저 LRU(Least Recently Used)라는 개념을 알아야 한다.

LRU란?

• 캐시는 메모리에 데이터를 저장하므로 용량에 한계가 있다. 캐시가 꽉 찼는데 새 데이터를 넣어야 한다면 기존 데이터 중 하나를 버려야 한다. 이때 "어떤 데이터를 버릴 것인가?"를 결정하는 정책이 필요하다.
• LRU = "가장 오랫동안 사용하지 않은 데이터를 먼저 버린다."
• 직관적으로 합리적이다: 최근에 읽은 데이터는 곧 다시 읽을 확률이 높고, 오랫동안 안 읽은 데이터는 앞으로도 안 읽을 확률이 높다.
• 비유하면 책상 위에 책을 쌓아두는 것이다. 읽을 때마다 맨 위에 올려놓고, 책상이 꽉 차면 맨 아래(가장 오래 안 읽은 것)부터 치운다.
• LevelDB의 캐시 엔진은 이 LRU 정책을 구현한 LRUCache 클래스다. Table Cache도, Block Cache도 내부적으로 LRUCache를 사용한다. (정확히는 LRUCache를 16개 묶은 ShardedLRUCache를 사용하는데, 이건 Section 9에서 다룬다. 먼저 하나의 LRUCache가 어떻게 동작하는지부터 이해한다.)

LRUCache의 세 가지 자료구조

하나의 LRUCache는 세 가지 자료구조의 협동으로 동작한다.

class LRUCache {
  size_t capacity_;     // 용량 한도
  size_t usage_;        // 현재 사용량

  HandleTable table_;   // ① 해시 테이블 — key로 O(1) 조회
  LRUHandle lru_;       // ② 미사용 엔트리 리스트 — eviction 후보
  LRUHandle in_use_;    // ③ 사용 중 엔트리 리스트 — eviction 보호
  port::Mutex mutex_;   // 이 캐시를 보호하는 Lock
};

각 자료구조의 역할을 먼저 한 줄씩 정리한다.

자료구조	역할
HandleTable (table_)	해시 테이블. key를 넣으면 해당 캐시 엔트리를 O(1)로 찾아준다. "이 SSTable의 Index Block이 캐시에 있는가?"를 빠르게 답하는 역할
lru_ (이중 연결 리스트)	아무도 읽고 있지 않은 캐시 엔트리들이 대기하는 리스트. 캐시가 꽉 차면 여기서 가장 오래된 것부터 제거(eviction)한다
in_use_ (이중 연결 리스트)	누군가 현재 읽고 있는 캐시 엔트리들이 머무는 리스트. 사용 중이므로 절대 eviction되지 않는다

왜 리스트가 두 개 필요한가? 안전성 때문이다.

만약 lru_ 리스트 하나만 있으면:

• 스레드 A가 Data Block을 읽고 있는 중에
• 스레드 B의 Insert로 캐시가 꽉 차서 그 Block이 evict되면
• → 스레드 A가 이미 없어진 메모리를 읽게 된다 (use-after-free 버그)

→ in_use_ 리스트에 있는 동안은 절대 evict되지 않으므로 이 문제를 방지한다.

capacity_와 usage_가 캐시 동작의 핵심이다:

• Insert할 때 새 엔트리의 크기(charge)가 usage_에 더해진다
• usage_가 capacity_를 초과하면 → lru_에서 오래된 엔트리를 제거하여 usage_ 감소
• 이것이 LRU eviction의 트리거

charge의 의미는 Table Cache와 Block Cache에서 다르다:

	charge 값	의미
Block Cache	Block의 실제 바이트 크기	4KB block이면 charge=4096. 큰 block은 캐시 용량을 많이 차지
Table Cache	고정값 1	엔트리 하나당 charge= 1. capacity=1000이면 최대 1000개 SSTable을 캐싱

Block Cache는 "메모리 용량" 기준이고, Table Cache는 "파일 개수" 기준으로 관리된다는 차이다.

LRUHandle — 캐시 엔트리의 실체

그림의 전체 구조부터 잡는다.

(1) ShardedLRUCache
┌───────────────────────────────────────────────────────┐
│  LRUCache(1)  LRUCache(2)  LRUCache(…)  LRUCache(16) │
└───────────────────────────────────────────────────────┘
        │
        ▼
(2) 하나의 LRUCache 내부
┌───────────────────────────────────────────────────────┐
│                                                       │
│  (4) HandleTable      (5) lru_       (6) in_use_      │
│  ┌──────────────┐   ┌────────────┐   ┌────────────┐  │
│  │  [LRUHandle] │   │ [LRUHandle]│   │            │  │
│  │  [LRUHandle] │   │ [LRUHandle]│   │ [LRUHandle]│  │
│  │  [LRUHandle] │   │            │   │            │  │
│  └──────────────┘   └────────────┘   └────────────┘  │
│   해시 테이블         evict 후보       사용중 보호     │
│                                                       │
│  HandleTable의 노드는 lru_ 또는 in_use_에도           │
│  동시에 연결되어 있다. 이것이 핵심이다.                 │
└───────────────────────────────────────────────────────┘

연결 관계 (화살표가 박스를 넘나든다):
  HandleTable [LRUHandle] ──파랑 next_hash──→ HandleTable 내 다음 노드
                          ──주황 next──────→ lru_ 또는 in_use_ 내 다음 노드
                          ──초록 prev──────→ lru_ 또는 in_use_ 내 이전 노드

 

(3) struct LRUHandle — 그림의 모든 LRUHandle 노드가 이 구조체다. HandleTable에도, lru_에도, in_use_에도 전부 같은 타입이다.

struct LRUHandle {
  void* value;           // 캐시된 데이터 (Table* 또는 Block*)
  size_t charge;         // 이 엔트리의 크기 (usage_ 계산에 사용)
  uint32_t hash;         // key의 해시값
  uint32_t refs;         // 참조 카운트 ← 핵심!

  LRUHandle* next_hash;  // ← 그림의 파랑 화살표
  LRUHandle* next;       // ← 그림의 주황 화살표
  LRUHandle* prev;       // ← 그림의 초록 화살표

  void (*deleter)(const Slice&, void* value);  // 삭제 콜백
};

 

구조체의 포인터 3개가 그림의 화살표 3개와 1:1 대응한다.

그림 화살표    포인터 필드    연결 대상              역할
────────────────────────────────────────────────────────────
파랑 →        next_hash     (4) HandleTable 내부   해시 충돌 시 같은 버킷의
                                                   다음 노드. O(1) 조회용
주황 →        next          (5) lru_ 또는          이중 연결 리스트의
                            (6) in_use_            다음 노드
초록 →        prev          (5) lru_ 또는          이중 연결 리스트의
                            (6) in_use_            이전 노드

 

하나의 LRUHandle이 두 곳에 동시에 걸려있는 이유:

하나의 LRUHandle 노드
├── 파랑 next_hash → HandleTable(4번) 안에서 다른 노드와 체이닝
│                    → key로 O(1) 조회 가능
│
├── 주황 next ─────→ lru_(5번) 또는 in_use_(6번) 안에서 순서대로 연결
└── 초록 prev ─────→ → O(1) 삽입/삭제 가능

HandleTable 쪽(파랑)을 타면 → "이 데이터가 캐시에 있는가?" O(1) 조회

lru_/in_use_ 쪽(주황/초록)을 타면 → "이 데이터를 버려도 되는가?" O(1) 판단

두 연산 모두 O(1)이어야 캐시가 빠르게 동작한다. 이것이 "Hash Table + Doubly Linked List" 조합이라는 LRU Cache의 클래식한 구현 패턴이다.

 

refs(참조 카운트)가 노드의 위치를 결정한다

LRUHandle의 refs 필드가 그 노드가 그림의 (5) lru_에 갈지, (6) in_use_에 갈지를 결정한다.

refs 값    위치                  의미
────────────────────────────────────────────────────
refs = 0   어디에도 없음          메모리에서 완전 삭제
refs = 1   (5) lru_ 리스트       캐시만 참조 → eviction 가능
refs = 2   (6) in_use_ 리스트    캐시 + 사용자 1명 → eviction 불가
refs = 3   (6) in_use_ 리스트    캐시 + 사용자 2명 → eviction 불가

 

 

상태 전이를 그림과 함께 따라간다.

── 시나리오: SSTable 123번의 Index Block을 캐싱하는 전체 흐름 ──

[1단계] Insert — 처음 캐시에 넣을 때

FindTable(123) → cache_->Insert(123, tf, 1) → 새 LRUHandle 생성, refs=2 (캐시 1 + 호출자 1)

(4) HandleTable        (5) lru_           (6) in_use_
┌──────────────┐   ┌──────────────┐   ┌──────────────┐
│  [SST-123]   │   │  (비어있음)   │   │  [SST-123]   │
│   파랑 등록   │   │              │   │   refs=2      │
│              │   │              │   │  주황/초록 연결 │
└──────────────┘   └──────────────┘   └──────────────┘

HandleTable에 파랑으로 등록 + in_use_에 주황/초록으로 연결

왜 (6) in_use_인가? → 호출자가 Index Block을 아직 쓰고 있으니까. 쓰는 중에 eviction되면 안 되므로 보호.

 

[2단계] Release — 사용 완료 후

호출자가 Index Block 사용 끝 → cache_->Release(handle) → refs-- → refs=1 (캐시만 참조) → (6) in_use_에서 주황/초록 끊고 → (5) lru_로 재연결

(4) HandleTable        (5) lru_           (6) in_use_
┌──────────────┐   ┌──────────────┐   ┌──────────────┐
│  [SST-123]   │   │  [SST-123]   │   │  (비어있음)   │
│   파랑 유지   │   │   refs=1     │   │              │
│              │   │  주황/초록 연결 │   │              │
└──────────────┘   └──────────────┘   └──────────────┘

in_use_ → lru_로 이동. 이제 eviction 후보.
HandleTable 파랑 연결은 유지 → 조회는 여전히 가능.

아무도 안 쓰니까 eviction 후보가 된다. 단, 바로 삭제는 아니다. 캐시에 남으면서 다음 Lookup을 기다린다.

 

[3단계] Lookup — 다시 접근할 때 (캐시 히트)

FindTable(123) → cache_->Lookup(123) → HandleTable(4번)에서 파랑 화살표를 따라 O(1)로 찾음! → refs++ → refs=2 → (5) lru_에서 주황/초록 끊고 → (6) in_use_로 재연결

(4) HandleTable        (5) lru_           (6) in_use_
┌──────────────┐   ┌──────────────┐   ┌──────────────┐
│  [SST-123]   │   │  (비어있음)   │   │  [SST-123]   │
│   파랑 유지   │   │              │   │   refs=2      │
│              │   │              │   │  주황/초록 연결 │
└──────────────┘   └──────────────┘   └──────────────┘

lru_ → in_use_로 복귀. 다시 보호 상태.
Disk I/O = 0번. 이것이 캐시 히트.

 

[4단계] Eviction — 캐시가 꽉 찼을 때

새 데이터 Insert → usage_ > capacity_ 초과 → (5) lru_에서 가장 오래된 노드(lru_.next)를 선택 → HandleTable(4번)에서 파랑 제거 + lru_(5번)에서 주황/초록 제거 → refs-- → refs=0 → 메모리 해제

(4) HandleTable        (5) lru_           (6) in_use_
┌──────────────┐   ┌──────────────┐   ┌──────────────┐
│  (제거됨)     │   │  (제거됨)     │   │              │
│              │   │              │   │              │
│              │   │              │   │              │
└──────────────┘   └──────────────┘   └──────────────┘

파랑/주황/초록 모두 제거. refs=0 → 메모리 해제.
핵심: (6) in_use_에 있는 노드는 절대 건드리지 않는다.

왜 리스트가 두 개 필요한가? — 안전성 때문이다.

• 만약 lru_ 리스트 하나만 있으면:
• 스레드 A가 Data Block을 읽고 있는 중에 스레드 B의 Insert로 캐시가 꽉 차서 그 Block이 evict되면 → 스레드 A가 이미 없어진 메모리를 읽게 된다 (use-after-free 버그)
• in_use_ 리스트에 있는 동안은 절대 evict되지 않으므로 이 문제를 방지한다. 그림에서 (5) lru_와 (6) in_use_가 분리된 이유가 바로 이것이다.

charge의 의미 — Table Cache와 Block Cache에서 다르다

LRUHandle의 charge 필드는 "이 엔트리가 캐시 용량을 얼마나 차지하는가"를 나타낸다.

Insert할 때 charge가 usage_에 더해지고, usage_가 capacity_를 초과하면 eviction이 발생한다.

캐시           charge 값                  의미
──────────────────────────────────────────────────────
Block Cache    Block의 실제 바이트 크기    4KB block이면 charge=4096
Table Cache    고정값 1                    capacity=1000이면 최대 1000개

Block Cache는 "메모리 용량" 기준이고, Table Cache는 "파일 개수" 기준으로 관리된다.

 

비유로 이해:

LRUCache = 도서관 한 곳
├── capacity_  = 서가 최대 수용량 (책 1000권까지)
├── usage_     = 현재 서가에 꽂힌 책 수 (지금 750권)
│
├── HandleTable table_  = 검색 컴퓨터 (도서 검색 시스템)
│   → "이 책 있어?" 물으면 즉시 답해줌 (O(1))
│   → 책이 도서관에 있는 한, 검색 컴퓨터에 항상 등록되어 있음
│
├── lru_      = 서가 (아무도 안 읽고 있는 책들이 꽂혀있는 곳)
│   → 서가가 꽉 차면 여기서 가장 오래 안 읽힌 책부터 버림
│
├── in_use_   = 열람석 (누군가 지금 읽고 있는 책들이 놓인 곳)
│   → 여기 있는 책은 절대 버리지 않음. 읽는 중이니까.
│
└── mutex_    = 도서관 출입문 잠금장치
              → 한 번에 한 명만 도서관 시스템을 조작 가능
              → 두 명이 동시에 같은 책을 빌리고/반납하면 꼬이니까

• Table Cache → usage_를 "권 수"로 셈. 책 1권 들어오면 usage_ += 1. capacity_ = 1000이면 최대 1000권.
• Block Cache → usage_를 "무게(바이트)"로 셈. 4KB짜리 책 들어오면 usage_ += 4096. capacity_ = 4MB면 총 무게 4MB까지.

---

7. Insert / Lookup / Eviction — 캐시의 핵심 동작

Section 6에서 LRUCache의 세 가지 자료구조(HandleTable, lru_, in_use_)와 refs 상태 전이를 봤다. 이제 이 구조들이 실제로 어떻게 협동하는지 — Insert, Lookup, Release, Eviction의 구체적 흐름을 추적한다.

Insert 흐름 — 새 데이터를 캐시에 넣기

Table Cache에서 캐시 미스 시 cache_->Insert(123, tf, 1)이 호출되면:

LRUCache::Insert(key, hash, value, charge):
  1. 새 LRUHandle 'e' 생성 (refs = 1)
  2. if (capacity_ > 0):         // 캐시가 활성화되어 있으면
       refs++                     // refs = 2 (캐시 + 호출자)
       LRU_Append(&in_use_, e)   // in_use_ 리스트에 추가
       usage_ += charge          // 사용량 증가
  3. table_.Insert(e)            // HandleTable에 등록 (O(1) 조회 가능하게)
  4. while (usage_ > capacity_): // ← 용량 초과 시 eviction!
       old = lru_.next            // lru_에서 가장 오래된 노드
       LRU_Remove(old)           // 리스트에서 제거
       table_.Remove(old)        // HandleTable에서도 제거
       usage_ -= old->charge     // 사용량 감소
       old->refs--               // refs = 0 → 메모리 해제

핵심 포인트:

• 새 엔트리는 바로 in_use_(refs는 1에서 2로 변경)에 들어간다 (호출자가 사용 중이니까)
• 용량 초과 시 lru_에서 오래된 것을 제거 (in_use_는 건드리지 않는다)
• 그래서 lru_가 비어 있으면? → eviction이 일어나지 않아 usage_가 capacity_를 넘을 수 있다 → 모든 엔트리가 사용 중이라 버릴 수 있는 게 없는 상황

Lookup 흐름 — 캐시에서 데이터 조회

cache_->Lookup(123) 호출 시:

LRUCache::Lookup(key, hash):
  1. table_.Lookup(key, hash)    // HandleTable에서 O(1) 검색
  2. if (찾음):
       Ref(handle)               // refs++ 
       // refs가 1→2가 되면: lru_ → in_use_로 이동
       // (아무도 안 읽던 것을 누군가 읽기 시작 → eviction 보호)
       return handle
  3. else:
       return nullptr             // 캐시 미스

Lookup이 성공하면 그 엔트리가 lru_에서 in_use_로 이동한다. 이것이 "최근 사용됨"을 표시하는 방식이다. → 사용 중인 동안은 eviction에서 보호된다.

Release 흐름 — 사용 완료 알림

Lookup으로 얻은 handle의 사용이 끝나면 Release를 호출해야 한다.

LRUCache::Release(handle):
  1. refs--
  2. if (refs == 1):               // 캐시만 참조 (사용자 없음)
       LRU_Remove(handle)          // in_use_에서 제거
       LRU_Append(&lru_, handle)   // lru_로 이동 (eviction 후보가 됨)

Release하면 refs가 감소하고, 아무도 참조하지 않으면(refs == 1, 캐시 자체만 참조) lru_로 돌아간다. 이 시점부터 eviction 대상이 된다.

전체 사이클을 Table Cache 예시로 따라가기

─── 시나리오: SSTable 123에 처음 접근 후 재접근 ───

[1단계] 처음 접근 — 캐시 미스 후 Insert
  FindTable(123):
    cache_->Lookup(123) → nullptr (미스)
    ... 디스크에서 읽기 ...
    cache_->Insert(123, tf, 1)
    → LRUHandle{key=123, value=tf, refs=2} 생성
    → in_use_ 리스트에 배치
    → 현재 상태: lru_: (비어있음)  in_use_: [123(refs=2)]

[2단계] FindTable 호출자가 사용 완료
    cache_->Release(handle)
    → refs-- → refs=1
    → in_use_ → lru_로 이동
    → 현재 상태: lru_: [123(refs=1)]  in_use_: (비어있음)

[3단계] 같은 SSTable 재접근 — 캐시 히트
  FindTable(123):
    cache_->Lookup(123)
    → HandleTable에서 찾음! handle 반환
    → refs++ → refs=2
    → lru_ → in_use_로 이동
    → 현재 상태: lru_: (비어있음)  in_use_: [123(refs=2)]
    → Disk I/O = 0번!

[4단계] 다시 사용 완료 → Release → lru_로 복귀 → eviction 가능 상태

이 Insert → Release → Lookup → Release 사이클이 반복된다. "가장 오랫동안 사용하지 않은 데이터"는 lru_ 리스트의 head(lru_.next) 쪽에 쌓이고, 용량 초과 시 head부터 제거된다.

---

8. HandleTable — O(1) 조회를 가능하게 하는 커스텀 해시 테이블

Section 6~7에서 table_.Lookup(), table_.Insert()를 계속 호출했다. 이 table_의 정체가 HandleTable이다. key를 넣으면 해당 LRUHandle을 O(1)로 찾아주는 해시 테이블이다.

 

도서관 비유를 이어가면, HandleTable은 검색 컴퓨터다. "123번 책 있어?" 하면 즉시 그 책(LRUHandle)을 찾아준다. Python의 dict, Java의 HashMap과 같은 역할인데, LevelDB는 표준 라이브러리를 쓰지 않고 직접 구현했다.

class HandleTable {
  uint32_t length_;             // 버킷 배열의 크기 (항상 2의 거듭제곱)
  uint32_t elems_;              // 저장된 엔트리 수
  LRUHandle** list_;            // 버킷 배열
};

 

동작 원리 — 버킷 배열 + 체이닝

dict가 내부적으로 어떻게 동작하는지 생각하면 된다. "key를 해시 함수에 넣어서 번호를 뽑고, 그 번호의 칸에 데이터를 넣는다."

예시: 버킷 4칸짜리 HandleTable (버킷 = 서랍이라고 생각)

key "SST-123"을 해시 → hash값 = 1299
서랍 번호 = 1299 & (4-1) = 1299 & 3 = 3
→ list_[3]에 저장

key "SST-456"을 해시 → hash값 = 2051
서랍 번호 = 2051 & 3 = 3
→ list_[3]에 저장 → 123이랑 같은 서랍! (해시 충돌)

해시 충돌이란? 서로 다른 key인데 해시 계산 결과가 같은 서랍 번호가 나온 것이다. SST-123과 SST-456은 완전히 다른 SSTable인데 우연히 같은 3번 서랍에 배정된 것이다.

 

이 충돌을 처리하는 방법이 체이닝(Chaining)이다. 같은 서랍 안에서 next_hash 포인터로 한 줄로 연결한다.

서랍 3번에 2개가 충돌로 들어간 경우:

list_[3] → [SST-123] --next_hash→ [SST-456] → nullptr

next_hash = 같은 서랍 안에서 다음 책을 가리키는 포인터. 그게 전부다.
그림의 파랑 화살표가 바로 이 next_hash다.

 

전체 버킷 배열의 모습:

list_[0] → nullptr                                          (비어있음)
list_[1] → [SST-789] → nullptr                              (1개)
list_[2] → nullptr                                          (비어있음)
list_[3] → [SST-123] --next_hash→ [SST-456] → nullptr       (2개, 충돌)

 

Lookup이 어떻게 동작하는지:

"SST-123 찾아줘"
→ 해시 계산 → 서랍 3번
→ 서랍 열어 → 첫 번째 = SST-123 → 맞음! 바로 반환

"SST-456 찾아줘"
→ 해시 계산 → 서랍 3번
→ 서랍 열어 → 첫 번째 = SST-123 → 아님
→ next_hash 따라감 → SST-456 → 맞음! 반환

"SST-999 찾아줘"
→ 해시 계산 → 서랍 1번
→ 서랍 열어 → SST-789밖에 없음 → "없음" 반환

서랍 번호를 해시로 바로 계산하니까 4개 서랍을 다 뒤질 필요 없이 서랍 하나만 열면 된다. 이것이 O(1)인 이유다.

다만 체인이 길어지면 느려진다. 서랍 하나에 책 10권이 쌓이면 next_hash를 10번 따라가야 하니까. 그래서 Resize가 필요하다.

 

next_hash와 next/prev의 차이

여기서 헷갈리기 쉬운 포인트가 있다. LRUHandle에는 포인터가 3개 있는데, 각각 완전히 다른 용도다.

next_hash (파랑) → HandleTable 안에서 체이닝 (단방향)
                   같은 서랍 안에서 다음 책을 가리킴
                   HandleTable 전용

next/prev (주황/초록) → lru_ 또는 in_use_에서 이중 연결 리스트
                       서가나 열람석에서 앞뒤 책을 가리킴
                       HandleTable이랑 전혀 상관없음

next_hash는 단방향이고(앞으로만 따라감), next/prev는 이중 연결(앞뒤로 왔다갔다)이다. 서로 다른 자료구조에서 독립적으로 동작한다.

 

버킷 결정에서 hash & (length_ - 1)을 쓰는 이유

hash % length_ (나머지 연산)  → 느림
hash & (length_ - 1) (비트 AND) → 빠름

이 두 연산이 같은 결과를 내려면 length_가 2의 거듭제곱이어야 한다.

length_ = 4  →  length_ - 1 = 3  →  이진수 0011
hash = 1299  →  이진수 ...0100 0001 0011
1299 & 3     =  0011 & 0011 = 0011 = 3  ← hash % 4 = 3과 동일

그래서 length_를 항상 2의 거듭제곱(4, 8, 16, 32, ...)으로 유지한다.

 

Resize 정책 — 서랍이 꽉 차면 확장

서랍이 4개인데 책이 5권 들어오면? 서랍당 평균 1.25권씩 쌓여서 체인을 따라가는 시간이 늘어난다.

HandleTable은 "엔트리 수(elems_) > 버킷 수(length_)"가 되면 서랍을 2배로 늘린다. 서랍당 평균 1개 이하를 유지해야 O(1)이 보장되니까.

Resize 전: 서랍 4개, 책 5권
  list_[0] → [A]
  list_[1] → nullptr
  list_[2] → [B] → [C]          ← 체인 길이 2
  list_[3] → [D] → [E]          ← 체인 길이 2

Resize 실행: 서랍 4개 → 8개로 확장
  1) 새 서랍 8개 만듦
  2) 모든 책을 꺼내서 hash & (8-1)로 새 서랍 번호 계산
  3) 새 서랍에 다시 배치
  4) 옛 서랍 폐기

Resize 후: 서랍 8개, 책 5권
  list_[0] → nullptr
  list_[1] → [A]
  list_[2] → [B]
  list_[3] → nullptr
  list_[4] → [C]
  list_[5] → [D]
  list_[6] → nullptr
  list_[7] → [E]

→ 서랍이 넉넉하니까 충돌이 줄어서 체인이 짧아짐 → 다시 빨라짐

초기 length_ = 4. 엔트리가 늘어나면 4 → 8 → 16 → 32 → ... 로 2배씩 확장. Resize 자체는 전체 엔트리를 옮기니까 O(n)이지만, 삽입 n번당 Resize는 log(n)번만 발생하므로 평균적으로(amortized) O(1)이다.

 

LevelDB가 표준 라이브러리 대신 직접 구현한 이유

왜 std::unordered_map을 안 쓰고 굳이 만들었는가? 3가지 이유가 있다.

1. 별도 노드 할당 불필요

std::unordered_map:
  Insert할 때마다 내부적으로 new Node() 호출 → 메모리 할당 오버헤드 발생

HandleTable:
  LRUHandle 안에 이미 next_hash가 있으니까 추가 할당 없이 바로 체이닝 가능
  → 메모리 할당/해제 비용 = 0

 

2. 단순한 Resize 조건

std::unordered_map:
  load factor(기본 1.0) 기반으로 Resize 판단 → 범용적이지만 복잡

HandleTable:
  elems_ > length_ → Resize
  → "서랍당 평균 1개 이하" 유지. 단순하고 캐시 패턴에 딱 맞음

 

3. hash 값 캐싱

일반 해시 테이블:
  Resize할 때 모든 key를 다시 해싱해야 함 → 비용 큼

HandleTable:
  LRUHandle에 hash를 미리 저장해둠 (struct 안의 uint32_t hash)
  → Resize할 때 저장된 hash를 그대로 쓰면 됨 → 재해싱 불필요 → Resize 빠름

정리하면, LRUHandle이라는 노드 하나에 해시 테이블용 필드(next_hash, hash)까지 미리 내장해놨기 때문에 범용 해시 테이블보다 훨씬 가볍고 빠르게 동작한다. 캐시처럼 Insert/Lookup이 초당 수만~수십만 번 호출되는 환경에서 이 차이가 의미 있다.

---

9. ShardedLRUCache — 왜 16개로 나누는가

Section 6~8에서 분석한 LRUCache 하나의 동작을 이해했다. 그런데 실제로 Table Cache와 Block Cache가 사용하는 것은 LRUCache 그 자체가 아니라, LRUCache 16개를 묶은 ShardedLRUCache다.

왜 하나로 쓰지 않고 16개로 나누는가? Lock 경합 문제 때문이다.

단일 LRUCache의 문제

Section 6에서 LRUCache에는 port::Mutex mutex_가 있다고 했다. Lookup이든 Insert든 캐시에 접근할 때마다 이 Lock을 잡아야 데이터 무결성이 보장된다.

단일 캐시의 문제:
  스레드 A: cache->Lookup(key_1)  → Lock 획득 → 조회 중...
  스레드 B: cache->Lookup(key_2)  → Lock 대기 (A가 끝날 때까지)
  스레드 C: cache->Insert(key_3)  → Lock 대기
  스레드 D: cache->Lookup(key_4)  → Lock 대기

  → 동시에 하나의 요청만 캐시에 접근 가능
  → LevelDB에 동시 Get() 요청이 많으면 캐시가 병목이 된다

해결: 16개 샤드로 분산

ShardedLRUCache는 16개의 독립된 LRUCache로 구성된다. 각 샤드는 자기만의 Lock을 갖는다. → 서로 다른 샤드에 접근하는 요청들은 동시에 진행된다.

static const int kNumShardBits = 4;
static const int kNumShards = 1 << 4;    // 16개 샤드

class ShardedLRUCache {
  LRUCache shard_[kNumShards];  // 16개 독립 LRUCache (각자 Lock 보유)
  uint64_t last_id_;            // cache_id 발급용 카운터

  // key의 해시값 상위 4비트로 샤드 결정
  static uint32_t Shard(uint32_t hash) {
    return hash >> (32 - kNumShardBits);  // 상위 4비트 추출
  }

  Cache::Handle* Lookup(const Slice& key) {
    uint32_t hash = HashSlice(key);
    return shard_[Shard(hash)].Lookup(key, hash);  // 해당 샤드만 Lock
  }

  Cache::Handle* Insert(const Slice& key, void* value, size_t charge, ...) {
    uint32_t hash = HashSlice(key);
    return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
  }
};

 

동작 예시:

16개 샤드로 분산:
  스레드 A: Lookup(key_1) → hash 상위 4비트 = 3  → shard_[3] Lock 획득
  스레드 B: Lookup(key_2) → hash 상위 4비트 = 7  → shard_[7] Lock 획득 (동시!)
  스레드 C: Insert(key_3) → hash 상위 4비트 = 12 → shard_[12] Lock 획득 (동시!)
  스레드 D: Lookup(key_4) → hash 상위 4비트 = 3  → shard_[3] Lock 대기 (A와 같은 샤드)

  → 4개 중 3개가 동시 진행. 단일 캐시 대비 큰 폭의 동시성 향상

해시값에서 샤드를 결정하는 원리

hash >> (32 - 4)는 32비트 해시값의 최상위 4비트를 추출한다.

hash = 0xA3F0_1234 (이진수: 1010 0011 1111 ...)
hash >> 28 = 0xA = 10 → 10번째 샤드

hash = 0x7B20_5678 (이진수: 0111 1011 ...)
hash >> 28 = 0x7 = 7 → 7번째 샤드

왜 하위 비트가 아니라 상위 비트를 쓰는가?

• Section 8의 HandleTable에서 버킷 결정에 하위 비트를 사용 (hash & (length_ - 1))
• 샤드 결정에도 하위 비트를 쓰면 → 특정 샤드의 특정 버킷에 데이터가 몰리는 편향 발생
• 상위 비트 = 샤드, 하위 비트 = 버킷 → 두 차원에서 독립적으로 분산

capacity 분배

전체 capacity를 16개 샤드에 균등 분배(올림 나눗셈)한다.

per_shard = (capacity + (kNumShards - 1)) / kNumShards

예시:
  capacity=100 → per_shard = (100+15)/16 = 7
  총 capacity = 7×16 = 112 (원래보다 약간 커짐)
  → 의도적 설계: "부족한 것보다는 약간 넘치는 것이 낫다"

 

실제 벤치마크에서의 capacity 흐름:

db_bench --cache_size=4194304 (4MB, Block Cache):
  → per_shard = 4,194,304(bytes) / 16 = 262,144 bytes (256KB)
  → Data Block 1개 = 4,096 bytes (4KB)
  → 262,144 / 4,096 = 64
  → 각 샤드에 약 64개 Data Block 수용

db_bench --open_files=1000 (Table Cache):
  → NewLRUCache(1000 - 10) = NewLRUCache(990)
  → per_shard = 990 / 16 = 62 (올림)
  → 각 샤드에 최대 62개 SSTable의 Index Block 수용
  (왜 10을 빼는가? LevelDB가 내부적으로 10개 파일을 예약하므로)

DevOps에서의 동일한 원리

이 "Lock 경합을 줄이기 위해 데이터를 분산한다"는 원리는 실무에서 반복적으로 등장한다.

시스템	연결
Redis Cluster	16384개 hash slot으로 데이터를 분산. key를 CRC16 해싱하여 slot 결정. LevelDB의 16-Shard와 동일한 원리
Kafka Partitioning	Key 해싱으로 파티션 결정. 파티션별 독립 Consumer가 병렬 처리. 파티션 수 = 최대 병렬도
ConcurrentHashMap (Java)	내부적으로 segment(Java 7) 또는 Node 단위(Java 8+)로 Lock을 분산. LevelDB ShardedLRUCache와 동일한 동기화 전략
DB Connection Pool	여러 커넥션으로 동시 쿼리 처리. 단일 커넥션이면 직렬화

---

캐시가 적용된 전체 읽기 흐름

Section 4~9에서 캐시의 전체 구조를 분석했다. 정리하면:

캐시 구조 계층:

ShardedLRUCache (Table Cache 인스턴스)
  └─ 16개 LRUCache 샤드
       └─ 각 샤드: HandleTable + lru_ + in_use_

ShardedLRUCache (Block Cache 인스턴스)
  └─ 16개 LRUCache 샤드
       └─ 각 샤드: HandleTable + lru_ + in_use_

두 캐시 인스턴스는 독립적이지만, 내부 구조는 완전히 동일하다.

 

이제 Section 3에서 봤던 읽기 경로에 캐시가 어떻게 끼어드는지 전체 그림을 보자.

DBImpl::Get(key)
  │
  ├─ 1. Memtable::Get       ← 메모리 (가장 최신 데이터, SkipList)
  │     찾으면 반환, 못 찾으면 ↓
  │
  ├─ 2. Immutable Memtable  ← 메모리 (flush 대기 중인 데이터)
  │     찾으면 반환, 못 찾으면 ↓
  │
  └─ 3. Version::Get        ← 디스크 SSTable (L0 → L1 → ... → Ln)
        │
        │  L0: 모든 SSTable 확인 (key 범위 겹침 가능)
        │  L1+: Binary Search로 해당 key가 포함된 SSTable 1개만 확인
        │
        └─ TableCache::Get(file_number, key)
             │
             ├─ [1st Lookup] TableCache::FindTable ─── Table Cache 조회
             │   ShardedLRUCache::Lookup(file_number)
             │   → hash 상위 4비트로 16개 샤드 중 하나 선택 (Section 9)
             │   → 해당 샤드의 HandleTable에서 O(1) 조회 (Section 8)
             │   → 캐시 히트: refs++ → in_use_로 이동 (Section 7)
             │   → 캐시 미스: 디스크에서 읽기 → Insert → eviction 가능 (Section 7)
             │
             └─ [2nd Lookup] Table::InternalGet ─── Block Cache 조회
                  │
                  ├─ Index Block에서 key가 속한 Data Block의 offset 확인 (메모리 연산)
                  ├─ Bloom Filter 확인 → "없다" → Disk I/O 없이 스킵
                  │
                  └─ ShardedLRUCache::Lookup(cache_id + offset)
                     → 캐시 히트: 메모리에서 Data Block 반환
                     → 캐시 미스: 디스크에서 Block 읽기 → Insert

핵심: ShardedLRUCache::Lookup이 두 번 호출된다.

	1st Lookup (Table Cache)	2nd Lookup (Block Cache)
질문	"이 SSTable의 Index Block이 캐싱되어 있는가?"	"실제 Data Block이 캐싱되어 있는가?"
히트 시	파일 열기 + Index Block 파싱 생략	디스크에서 Block 읽기 생략
미스 비용	크다 (파일 열기 + Footer + Index 파싱)	중간 (디스크에서 Block 1개 읽기)

 

Best Case vs Worst Case

Best Case: 두 캐시 모두 히트 (Disk I/O = 0)

Get("user:150")
  ├─ Memtable → 없음
  ├─ Immutable → 없음
  └─ TableCache::Get
       ├─ [Table Cache 히트] → Index Block 메모리에서 → "Data Block 1에 있다"
       ├─ [Bloom Filter] → "있을 수 있음"
       └─ [Block Cache 히트] → Data Block 메모리에서 → value 반환
  총 Disk I/O = 0번

 

Worst Case: 두 캐시 모두 미스 (Disk I/O = 4)

Get("user:150")
  ├─ Memtable → 없음
  ├─ Immutable → 없음
  └─ TableCache::Get
       ├─ [Table Cache 미스]
       │   open() 시스템 콜 + Footer(Disk#1) + Index Block(Disk#2) + Filter(Disk#3)
       │   → cache_->Insert → 다음엔 히트
       └─ [Block Cache 미스]
           Data Block(Disk#4) + CRC 검증 + 압축 해제
           → cache_->Insert → 다음엔 히트
  총 Disk I/O = 4번 + 시스템 콜 1번

	Best (두 캐시 히트)	Worst (두 캐시 미스)
시스템 콜	0번	1번 (file open)
Disk I/O	0번	4번
소요 시간	~29 μs/op (벤치마크 기준)	~150 μs/op (벤치마크 기준)
성능 차이	—	약 5배 느림

Worst Case라도 한 번만 미스하면 캐시에 저장되므로, 같은 SSTable·같은 Block에 대한 다음 접근부터는 Best Case 경로를 탄다. 이것이 캐시의 본질이다.

---

10. 샤딩과 파티셔닝 — "차이가 뭔가?"

Section 9에서 LevelDB의 ShardedLRUCache가 16개 샤드로 나뉘어 Lock 경합을 줄인다는 것을 봤다. 면접에서 "샤딩이랑 파티셔닝의 차이는요?"라는 질문을 받았을 때, 이 개념들을 정확히 구분해서 답해야 한다.

 

핵심 차이 — 한 문장 정리

파티셔닝(Partitioning): 하나의 DB 서버 안에서 테이블을 논리적/물리적으로 나누는 것.
샤딩(Sharding): 여러 DB 서버로 데이터를 물리적으로 분산하는 것.

[비유]

파티셔닝 = 한 도서관 안에서 서가를 층별로 나누기
  1층: 문학 (ㄱ~ㅁ)
  2층: 문학 (ㅂ~ㅎ)
  3층: 과학
  → 여전히 같은 건물, 같은 사서(DB)가 관리

샤딩 = 여러 도서관으로 분산
  강남 도서관: 문학
  서초 도서관: 과학
  송파 도서관: 역사
  → 물리적으로 다른 건물, 독자(앱)가 어디 갈지 결정

 

 

파티셔닝 (Partitioning)

정의와 목적: 하나의 큰 테이블을 여러 조각으로 나눠서 쿼리 성능 향상과 관리 편의성을 얻는다. 단일 서버 내부에서 일어난다.

-- MySQL Range Partitioning 예시
CREATE TABLE orders (
    id BIGINT,
    created_at DATE,
    ...
) PARTITION BY RANGE (YEAR(created_at)) (
    PARTITION p2022 VALUES LESS THAN (2023),
    PARTITION p2023 VALUES LESS THAN (2024),
    PARTITION p2024 VALUES LESS THAN (2025)
);

-- 쿼리 시 자동으로 해당 파티션만 스캔 (Partition Pruning)
SELECT * FROM orders WHERE created_at = '2023-05-15';
→ MySQL이 p2023만 조회 (나머지 무시)

-- 오래된 데이터 삭제도 빠름
ALTER TABLE orders DROP PARTITION p2022;  -- 수 초 내 완료

 

왜 빠른가?

[파티셔닝 전 — 3억 건 테이블]
SELECT * FROM users WHERE id = 150000000;
→ B-Tree 인덱스 30GB (RAM에 안 들어감)
→ 디스크 I/O 발생 → 느림

[파티셔닝 후 — 3개 파티션]
Partition p0: id 1~100,000,000
Partition p1: id 100,000,001~200,000,000  ← 여기만 조회
Partition p2: id 200,000,001~300,000,000

→ 인덱스 크기 1/3 → RAM에 들어갈 확률 ↑ → 빠름

 

파티셔닝의 한계

여전히 같은 서버:
  - CPU/메모리/디스크 한계 그대로
  - 서버 죽으면 전체 접근 불가 (SPOF)
  - 네트워크 대역폭 한계 그대로

→ 이 문제들을 해결하려면 샤딩 필요

 

샤딩 (Sharding)

정의와 목적: 데이터를 여러 물리적 서버(Shard)로 분산하여 수평 확장과 고가용성을 얻는다.

[Hash-based Sharding 예시]

users 테이블을 3개 서버로 분산:

┌──────────────┐  ┌──────────────┐  ┌──────────────┐
│ MySQL 서버 1  │  │ MySQL 서버 2  │  │ MySQL 서버 3  │
│ user_id      │  │ user_id      │  │ user_id      │
│ 1~1,000,000  │  │ 1,000,001~   │  │ 2,000,001~   │
│              │  │ 2,000,000    │  │ 3,000,000    │
└──────────────┘  └──────────────┘  └──────────────┘
   Shard 0           Shard 1           Shard 2

애플리케이션이 Shard 결정:
  user_id = 1,500,000
  → hash(1,500,000) % 3 = 1
  → Shard 1 서버로 쿼리 전송

 

샤딩의 트레이드오프

장점	단점
서버 추가로 용량/성능 무한 확장	애플리케이션이 Shard 관리 (복잡도 ↑)
각 Shard 독립적 (장애 격리)	다른 Shard 간 JOIN 불가
병렬 처리 가능	분산 트랜잭션 복잡

 

 

Redis에서의 샤딩 — Redis Cluster

Redis Cluster는 16,384개 Hash Slot으로 데이터를 분산한다.

[Redis Cluster 구조]

16,384개 Slot을 3개 노드에 분배:

┌─────────────────┐  ┌─────────────────┐  ┌─────────────────┐
│  Redis Node 1   │  │  Redis Node 2   │  │  Redis Node 3   │
│  Slot 0~5460    │  │  Slot 5461~10922│  │  Slot 10923~16383│
└─────────────────┘  └─────────────────┘  └─────────────────┘

키가 들어오면:
1) CRC16(key) % 16384 → Slot 번호
2) 해당 Slot 담당 노드로 라우팅

 

Hash Tag — 관련 키를 같은 Slot에 모으기

CGV에서 중요한 개념.

[문제]
sessions:{topgun}:waiting → Slot 7890 (Node 2)
sessions:{topgun}:active  → Slot 3421 (Node 1)

→ 다른 노드에 있으면 Lua 스크립트로 원자적 조작 불가 ✗

[해결: Hash Tag {}]
sessions:{topgun}:waiting
         ^^^^^^^^ 이 부분만 해시

sessions:{topgun}:active
         ^^^^^^^^ 이 부분만 해시

→ 두 키 모두 CRC16("topgun") % 16384 = 같은 Slot
→ 같은 노드에 저장 → Lua 스크립트 가능 ✓

 

CGV 적용:

// 모든 대기열 키에 {movieId} Hash Tag 사용
String waitingKey = String.format("sessions:{%s}:waiting", movieId);
String activeKey = String.format("sessions:{%s}:active", movieId);

// 같은 노드에 있으므로 원자적 이동 가능
redisTemplate.execute(luaScript, 
    Arrays.asList(waitingKey, activeKey), ...);

 

LevelDB ShardedLRUCache와의 비교

Section 9의 ShardedLRUCache도 샤딩이지만 목적이 다르다.

비교	Redis Cluster	LevelDB ShardedLRUCache
목적	데이터 용량 확장	Lock 경합 감소 (동시성)
Shard 수	16,384 Hash Slot	16 LRUCache
범위	여러 서버 (네트워크)	단일 프로세스 메모리
Shard 결정	CRC16(key) % 16384	hash(key) >> 28 (상위 4비트)
용량 한계	서버 추가로 무한 확장	프로세스 메모리 한계

[Redis Cluster — 수평 확장]
┌─────────┐  ┌─────────┐  ┌─────────┐
│ Node 1  │  │ Node 2  │  │ Node 3  │  ← 물리적으로 다른 서버
│ 5TB     │  │ 5TB     │  │ 5TB     │
└─────────┘  └─────────┘  └─────────┘
   총 15TB 저장 가능

[LevelDB ShardedLRUCache — 동시성]
┌──────────────────────────────────┐
│  LevelDB 프로세스 (단일 서버)      │
│  ┌────┐ ┌────┐     ┌────┐       │
│  │ S0 │ │ S1 │ ... │S15 │       │  ← 16개 샤드
│  └────┘ └────┘     └────┘       │
│   각자 Lock 보유 → 동시 접근 가능  │
└──────────────────────────────────┘
   총 용량 = 프로세스 메모리 한계

공통점: 해시 기반 분산, 독립적 동작, 병렬 처리
차이점: Redis는 용량 확장, LevelDB는 Lock 분산

 

왜 16개 vs 16,384개?

LevelDB 16개:

• Lock 경합 감소가 목적 → 16개면 충분 (CPU 코어 수 고려)
• 샤드당 메모리 오버헤드 있음 → 너무 많으면 비효율

Redis 16,384개:

• 노드 추가 시 Slot 단위로 이동 → 세밀한 조정 가능
• 16,384 = 2^14 → 비트맵 2KB로 표현 가능 (메타데이터 작음)
• CRC16 % 16384 연산이 빠름

 

CGV 프로젝트에서의 적용

현재 규모 — 샤딩 불필요

10만 동시 접속:
  - 대기열 10만 명: ~15MB
  - Active 1만 명: ~2MB
  - 세션 키: ~5MB
  ────────────────
  총: ~32MB

dev: Redis Pod 512Mi → 6% 사용
prod: ElastiCache 1GB → 3% 사용

→ 단일 Redis로 충분 ✓

 

확장 시나리오 — 100만 동시 접속

Redis Cluster 3 노드:

Node 1: sessions:{movie-A}:* (33만 명)
Node 2: sessions:{movie-B}:* (33만 명)
Node 3: sessions:{movie-C}:* (34만 명)

→ Hash Tag {movieId} 덕분에 영화별 자동 분산
→ 각 영화의 대기열 연산은 단일 노드에서 원자적 처리

 

면접 답변 템플릿

Q: "샤딩과 파티셔닝의 차이는?"

A: 파티셔닝은 단일 DB 서버 안에서 테이블을 나누는 것이고,
   샤딩은 여러 DB 서버로 데이터를 분산하는 것입니다.

   파티셔닝은 쿼리 성능 향상이 목적이고,
   샤딩은 수평 확장(용량/처리량 증가)이 목적입니다.

   CGV 프로젝트는 현재 단일 Redis로 충분하지만,
   100만 동시 접속 시 Redis Cluster를 고려할 수 있습니다.

 

Q: "Redis Cluster에서 Hash Tag를 왜 쓰나?"

A: Redis Cluster는 키를 16,384개 Hash Slot으로 분산하는데,
   관련된 여러 키를 같은 노드에 모아야 Lua 스크립트로
   원자적 연산이 가능합니다.

   Hash Tag {}를 사용하면 중괄호 안 문자열만 해시하므로,
   sessions:{topgun}:waiting과 sessions:{topgun}:active가
   모두 같은 Slot에 배치되어 원자적 이동이 가능합니다.

 

Q: "LevelDB ShardedLRUCache도 샤딩인가?"

A: 개념적으로는 샤딩이지만 목적이 다릅니다.

   Redis Cluster는 데이터 용량 확장을 위해 여러 서버로 분산하고,
   LevelDB는 Lock 경합을 줄여 동시성을 높이기 위해
   단일 프로세스 메모리 안에서 16개로 나눈 것입니다.

   둘 다 해시 기반 분산과 독립적 동작이라는 공통점이 있지만,
   Redis는 네트워크 분산, LevelDB는 메모리 내 분산입니다.

---

 

정리:

개념	범위	목적	CGV 적용
파티셔닝	단일 서버	쿼리 성능, 관리	현재 불필요
샤딩	여러 서버	수평 확장	100만 확장 시 고려
Hash Tag	Redis Cluster	원자적 연산	{movieId} 사용
ShardedLRUCache	LevelDB 메모리	Lock 분산	Section 9 참고