Mini-Pages: Leaf Page 경계 다시 생각하기
Source: Dev.to
안녕하세요, 저는 마네슈와르입니다. 저는 FreeDevTools online에서 작업하고 있으며, 현재 모든 개발 도구, 치트 코드, TLDR을 한 곳에 모은 서비스를 구축하고 있습니다 — 개발자들이 인터넷을 뒤져 찾는 번거로움 없이 빠르게 도구를 찾고 사용할 수 있는 무료, 오픈‑소스 허브입니다.
어제 기사에서는 B‑Tree와 LSM‑Tree가 현대 하드웨어를 충분히 활용하지 못하는 이유를 살펴보았습니다—하나는 캐시 오염으로, 다른 하나는 압축, 증폭, 운영 복잡성 때문에 무거워집니다.
오늘은 이러한 구조가 부족한 이유를 넘어 페이지 자체를 무엇이 대체하는지 살펴보겠습니다.
The Bf‑Tree Answer: Mini‑Pages
Bf‑Tree의 답변은 또 다른 캐시, 버퍼 또는 튜닝 트릭이 아니라 리프 노드의 구조적 재고입니다.
이 재설계의 중심에는 새로운 원시 요소인 mini‑page가 있습니다.
- mini‑page는 슬림하고 메모리 내에 존재하는 리프 페이지의 버전으로, 범위가 엄격히 제한되고 의도적으로 구축됩니다.
- 버퍼‑풀 페이지나 LSM memtable과 달리, mini‑page는 오직 리프 노드에만 존재하며, 리프 페이지당 하나의 mini‑page만 존재할 수 있습니다.
이 설계 선택은 의도된 것입니다. mini‑page는 일반적인 캐시가 아니라; 리프 페이지의 정확한 확장으로, 다음을 목표로 설계되었습니다:
- 최근 업데이트 버퍼링
- 자주 접근되는 레코드 캐싱
핵심은 전체 페이지를 메모리로 끌어들이지 않고 이를 수행한다는 점입니다.
페이지‑레벨 증폭 없이 쓰기 흡수
쓰기 작업이 리프 페이지를 대상으로 할 때, Bf‑Tree는 디스크에 있는 페이지를 즉시 건드리지 않습니다. 대신, 쓰기는 리프의 mini‑page에 삽입됩니다:
- mini‑page가 없으면 최소 크기의 페이지가 생성됩니다(64 바이트 정도, 캐시 라인에 정렬).
- mini‑page 내부의 레코드는 정렬된 상태를 유지하여 공간 지역성을 보존합니다.
- 삽입은 포인터 체이닝이 아닌 이진 탐색을 사용합니다.
업데이트가 누적되면서 mini‑page는 동적으로 성장합니다:
- 가득 차면 크기가 두 배가 됩니다.
- 성장은 상한(최대 4 KB)에 도달할 때까지 계속됩니다.
mini‑page가 그 한계에 도달하거나 evict되어야 할 경우, 시스템은 mini‑page를 디스크에 있는 기본 리프 페이지와 배치 병합합니다.
이를 통해 동시에 두 가지를 달성합니다:
- 쓰기는 메모리에서 흡수·합쳐집니다.
- 디스크 쓰기는 더 크고 효율적인 배치로 수행됩니다.
델타 체인도 없고, 여러 구조에 대한 per‑update 로그도 없으며, 백그라운드 컴팩션 파이프라인도 없습니다. 업데이트는 로컬에 머물고, 정렬되며, 캐시 친화적입니다.
페이지를 캐시하지 않고 핫 레코드 캐시
읽기도 유사하게 엄격한 흐름을 따릅니다. 디스크에 접근하기 전에, 조회는 mini‑page를 이진 탐색합니다:
- 히트: 레코드가 즉시 반환됩니다.
- 미스: 해당 리프 페이지를 디스크에서 읽어옵니다.
레코드를 로드한 뒤, Bf‑Tree는 확률적으로(예: 1 % 확률) 해당 레코드를 다시 mini‑page에 캐시할 수 있습니다. 이는 차가운 데이터를 mini‑page에 가득 채우는 것을 방지하면서, 핫 레코드가 자연스럽게 축적되게 합니다.
핵심 구분점: mini‑page는 페이지가 아니라 레코드를 캐시합니다.
전통적인 B‑Tree는 하나의 레코드만 핫하더라도 전체 페이지를 캐시합니다. LSM 시스템은 로우 캐시와 블록 캐시를 별도로 나누어 각각 메모리 예산과 튜닝 노브를 가집니다. mini‑page는 이러한 양극단을 피합니다.
캐시된 갭을 활용한 레인지 스캔 적응
레코드‑레벨 캐시만으로는 충분하지 않습니다. 레인지 스캔은 공간 지역성에 의존하는데, 개별 레코드만 캐시하면 오히려 방해가 됩니다. Bf‑Tree는 우아한 피벗을 통해 이를 해결합니다.
mini‑page가 최대 크기에 도달하면, 전체 리프‑페이지 표현으로 병합·승격될 수 있습니다. 이는 디스크 레이아웃을 그대로 반영합니다. 이 시점에서:
- mini‑page는 실질적으로 페이지‑레벨 캐시가 됩니다.
- 레인지 스캔은 공간 지역성을 회복합니다.
- 별도의 캐시 계층이 필요하지 않습니다.
따라서 동일한 메모리 예산으로 다음을 유동적으로 지원할 수 있습니다:
- 포인트 조회(작은 mini‑page 활용)
- 레인지 스캔(전체 크기의 페이지 활용)
행 캐시와 블록 캐시 사이에 정적 파티셔닝을 요구하는 시스템과 달리, Bf‑Tree는 워크로드 패턴 변화에 따라 자동으로 적응합니다.
하나의 레이아웃, 두 가지 역할
mini‑page와 리프 페이지는 물리적 레이아웃이 정확히 동일합니다; 차이는 크기뿐입니다.
- 두 경우 모두 정렬된 key–value 쌍을 저장하고 효율적인 조회를 지원합니다.
- mini‑page는 가변 길이를 허용하고, 리프 페이지는 디스크에 고정 크기로 존재합니다.
이 통합 레이아웃은:
- 구현 복잡성을 감소시키고
- 중복 로직을 없애며
- 메모리와 디스크에 동일한 최적화를 적용할 수 있게 합니다.
내부적으로 각 페이지는 컴팩트한 노드‑메타데이터 헤더로 시작하고, 이어서 메타데이터 엔트리와 실제 key–value 데이터가 반대 방향에서 채워집니다. 삽입은 전체 페이지가 아니라 메타데이터만 이동시켜 수행됩니다.
records, keeping operations fast and cache‑friendly.
매핑 페이지와 동시성 유지
리프 페이지는 항상 디스크에 존재하고, 미니‑페이지는 메모리에 존재합니다. 두 페이지 모두 동일한 논리 페이지 ID를 통해 참조됩니다.
Bf‑Tree는 인‑메모리 매핑 테이블을 사용하여 이 페이지 ID를 다음 중 하나로 변환합니다:
- 메모리 주소 (미니‑페이지), 또는
- 디스크 오프셋 (리프 페이지)
매핑 테이블은 페이지 주소와 함께 읽기‑쓰기 잠금을 64‑비트 단일 워드에 포함합니다. 미니‑페이지와 그 리프 페이지가 동일한 페이지 ID를 공유하기 때문에:
- 하나를 잠그면 자동으로 다른 것도 잠깁니다.
- 동시성 모델이 단순해집니다.
- 추가 조정 계층이 필요하지 않습니다.
이 간접화는 페이지 위치를 페이지 정체성으로부터 분리시켜, 트리 전체에 걸쳐 포인터를 다시 쓰지 않고도 메모리와 디스크 사이를 자유롭게 이동할 수 있게 합니다.
왜 미니‑페이지가 중요한가
미니‑페이지는 캐시 조정이 아니라 페이지가 무엇인가에 대한 근본적인 재정의입니다. 메모리와 디스크 사이의 경계를 흐리면서도 순서, 지역성, 예측 가능성을 유지합니다.
- 쓰기 작업이 로컬화됩니다.
- 읽기 작업이 선택적으로 이루어집니다.
- 범위 스캔이 효율성을 회복합니다—백그라운드 압축, 다단계 탐색, 캐시 파티셔닝 없이.
여기서 Bf‑Tree… (필요에 따라 계속).
- **Tree** stops being a “better B‑Tree” and starts looking like a **new storage primitive**—one that finally aligns data structures with modern hardware realities.
[](https://hexmos.com/freedevtools/)
👉 **Check out:** [FreeDevTools](https://hexmos.com/freedevtools/)
Any feedback or contributors are welcome!
It’s online, open‑source, and ready for anyone to use.
⭐ **Star it on GitHub:** [FreeDevTools](https://github.com/HexmosTech/FreeDevTools)