Copy-on-Write B-Tree (CoW B-Tree)

Copy-on-Write B-Tree (CoW B-Tree)

B-Tree의 변형으로 노드 수정 시 기존 노드를 변경하지 않고 새 노드를 생성(Copy-on-Write)하여 일관된 스냅샷과 충돌 없는 읽기를 지원하는 영속 자료구조

목적: 스냅샷 지원, 충돌 없는 동시 읽기, 크래시 안전성, 불변성

특징: 쓰기 시 복사, 불변 노드, 스냅샷 무료, 가비지 컬렉션 필요

동작

• •읽기: 현재 루트에서 탐색, 락 없음
• •쓰기: 변경 경로의 노드 복사 → 새 노드에 수정 → 새 루트 원자적 교체
• •스냅샷: 현재 루트 포인터 저장, 즉시 완료 O(1)

쓰기 과정

크래시 안전성: 새 루트 커밋 전 크래시 → 이전 상태 유지, 저널링 불필요

가비지 컬렉션: 참조되지 않는 이전 버전 노드 회수, Epoch 기반

장점: 무료 스냅샷, 락프리 읽기, 크래시 안전, 시간 여행 쿼리

단점: 쓰기 증폭(경로 복사), 가비지 컬렉션 오버헤드, 공간 사용 증가

적용사례: Btrfs, ZFS, LMDB, CockroachDB, FoundationDB

비교: CoW B-Tree(불변/스냅샷) vs In-place B-Tree(직접수정/WAL) vs LSM(쓰기최적화)

연관: B-Tree, 스냅샷, Btrfs, ZFS, 영속 자료구조