미니 페이지 메모리 관리: Bf-Tree 뒤의 버퍼 풀

Source: Dev.to

안녕하세요, 저는 마네시와르입니다. 저는 FreeDevTools online—모든 개발 도구, 치트 코드 및 TLDR을 한 곳에 모아 개발자들이 웹을 뒤져 찾지 않고도 필요한 것을 쉽게 찾고 사용할 수 있도록 하는 무료 오픈‑소스 허브—에 대해 작업하고 있습니다.

요약

어제 우리는 mini‑pages와 pinned inner nodes가 B‑Tree의 실행 경로를 어떻게 재구성하여 핫 레코드를 CPU에 가깝게 유지하고 중요한 경로에서 경쟁을 제거하는지 살펴보았습니다.

오늘은 덜 눈에 띄지만 동등하게 중요한 부분에 초점을 맞춥니다:

Bf‑Tree가 미니‑페이지 메모리를 관리하는 방법

미니‑페이지가 존재하게 되면, 진정한 도전이 시작됩니다: 이들은 가변 크기, 변경 가능, 그리고 고도로 동시성을 가집니다. 기존의 페이지 기반 버퍼 풀은 전혀 맞지 않습니다.

이 글에서는 Bf‑Tree가 미니‑페이지용 특수 버퍼 풀을 설계하는 방법과 원형 버퍼가 올바른 추상화임을 밝혀내는 과정을 살펴봅니다.

왜 Mini‑Pages는 다른 Buffer Pool이 필요한가

Mini‑pages는 고정‑크기 디스크 페이지가 아닙니다. 이들은:

• 동적으로 크기가 늘어나고 줄어듭니다
• 자주 접근되고 수정됩니다
• 삭제될 때까지 순수하게 메모리 내에 존재합니다

이러한 특성은 세 가지 근본적인 과제를 제시합니다:

1. Memory management – 단편화를 방지하면서 모든 mini‑page의 정확한 위치를 추적합니다.
2. Hotness‑aware eviction – 어떤 mini‑pages를 메모리에 유지하고 어떤 것을 디스크로 플러시할지 결정합니다.
3. Concurrency at scale – 많은 스레드가 메모리를 안전하게 할당, 삭제 및 회수하도록 하면서도 SSD 대역폭을 최대한 활용합니다.

전통적인 allocators와 LRU‑style buffer pools는 여기서 어려움을 겪습니다. Bf‑Tree는 다른 접근 방식을 취합니다.

핵심 아이디어: 미니‑페이지를 위한 원형 버퍼

Bf‑Tree는 모든 미니‑페이지를 대형 원형 버퍼 안에 저장합니다.

• Allocation → tail에 Append
• Reclamation → head에서 Remove

버퍼가 가득 차면, eviction은 선형적으로 앞으로 진행됩니다. 이 설계는 FASTER의 하이브리드 로그에서 영감을 받았지만, 미니‑페이지와 B‑Tree 의미론에 맞게 조정되었습니다.

장점

• 할당이 빠르고 순차적입니다.
• Eviction이 예측 가능합니다.
• 단편화가 최소화됩니다.

단순한 원형 버퍼는 뜨거운 미니‑페이지를 너무 과도하게 evict할 수 있으므로, Bf‑Tree는 설계를 더욱 정교화합니다.

Source:

세 개의 영역, 하나가 아니다: 핫 미니‑페이지 보호

자주 접근되는 미니‑페이지가 퇴출되지 않도록 하기 위해, 원형 버퍼는 세 개의 이동 포인터를 사용해 구분됩니다:

• Tail 주소
• Second‑chance 주소
• Head 주소

이 포인터들은 두 개의 논리적 영역을 만듭니다:

인‑플레이스 업데이트 영역 (~90 %)

• 미니‑페이지를 직접 수정할 수 있습니다.
• 핫 미니‑페이지는 주로 이곳에 머뭅니다.
• 대부분의 업데이트가 이 영역에서 발생합니다.

복사‑온‑액세스 영역 (~10 %)

• 퇴출 직전의 미니‑페이지가 이곳에 위치합니다.
• 접근 시 Tail 로 복사되어 “두 번째 기회”를 부여받습니다.

이 메커니즘은 복잡한 LRU 관리 없이도 핫 미니‑페이지가 Head 쪽으로 이동해 퇴출되는 것을 방지합니다.

성장, 축소 및 재사용 처리

Mini‑pages는 쓰기를 흡수하면서 자주 크기가 조정됩니다. Bf‑Tree는 다중 자유 리스트를 사용하여 크기 클래스별로 그룹화합니다:

1. 페이지가 커지거나 작아질 때 새로운 mini‑page를 할당합니다.
2. 내용을 새로운 할당으로 복사합니다.
3. 이전 메모리를 적절한 자유 리스트에 반환합니다.

이렇게 하면 할당 속도가 빨라지고 시간이 지남에 따라 단편화가 감소합니다.

원형 버퍼 API: 최소하지만 충분함

버퍼 풀은 미니 페이지에 맞춘 간결한 API를 제공합니다.

할당

메모리는 다음에서 가져옵니다:

• 크기에 맞는 경우 자유 리스트에서, 또는
• 테일에서 (테일을 전진시켜).

테일이 헤드에 너무 가까워지면 할당이 실패하고 삭제가 트리거됩니다.

삭제

삭제는 항상 헤드 근처에서 시작됩니다:

1. 더러운 레코드가 디스크의 리프 페이지와 다시 병합됩니다.
2. 매핑 테이블이 업데이트됩니다.
3. 헤드 포인터가 전진합니다.

여러 스레드가 동시에 삭제할 수 있지만, 포인터 전진은 순차적으로 유지됩니다.

해제

해제된 메모리는 크기별 자유 리스트에 반환되어 재사용됩니다.
페이징 없음, 페이지당 잠금 없음, LRU 큐 없음.

Performance‑Critical Optimizations

이 버퍼가 핫 경로에 위치하기 때문에, 여러 저수준 최적화가 중요합니다.

Minimal Fragmentation

• 미니‑페이지가 서로 바로 뒤에 배치됩니다.
• 각 할당은 8 바이트의 메타데이터만을 포함합니다.
• 페이지 경계에 맞춰 정렬할 필요가 없으므로 메모리가 조밀하고 예측 가능합니다.

Huge Pages for TLB Efficiency

미니‑페이지가 4 KB 경계를 넘어갈 수 있습니다. 과도한 페이지 테이블 워크를 피하기 위해:

• 원형 버퍼는 거대한 페이지(huge pages) 로 지원됩니다.
• 이는 TLB 압력을 크게 감소시킵니다.

Parallel Eviction with Ordered Progress

Eviction은 헤드를 순차적으로 진행해야 하지만, 실제 작업은 병렬화될 수 있습니다:

• 스레드들이 미니‑페이지를 병렬로 evict합니다.
• 모든 이전 evict가 완료된 후에만 헤드 포인터가 앞으로 이동합니다.

이렇게 하면 정확성을 유지하면서도 병렬 I/O를 활용할 수 있습니다.

왜 이 설계가 작동하는가

Mini‑pages는 이미 리프 노드의 동작 방식을 바꾸었습니다. 이 버퍼 풀은 그들이 확장될 수 있도록 보장합니다.

전체 설계는:

• 할당자 단편화를 방지합니다.
• LRU 오버헤드 없이 핫 mini‑pages를 상주하게 합니다.
• 대규모 동시성을 지원합니다.
• 콜드 데이터를 디스크로 효율적으로 스트리밍합니다.

가장 중요한 것은 Bf‑Tree의 철학과 일치한다는 점입니다:

관심사를 분리하고 각 경로를 독립적으로 최적화한다.

• 내부 노드: 빠르고, 고정되며, 경쟁이 없는 탐색.
• 리프 페이지: 디스크 상에서 안정적인 구조.
• Mini‑pages: 유연하고, 적응 가능하며, 메모리 내 작업 집합.

버퍼 풀은 모든 것을 연결하여 Bf‑Tree의 mini‑page 아키텍처에 고성능·저경합 기반을 제공합니다.

# FreeDevTools

`r` pool is what makes that separation viable in practice.

[![FreeDevTools](https://media2.dev.to/dynamic/image/width=800,height=,fit=scale-down,gravity=auto,format=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fo5e57lh7rtwwwe2d694n.png)](https://hexmos.com/freedevtools/)

👉 **Check out:** [FreeDevTools](https://hexmos.com/freedevtools/)

Any feedback or contributions are welcome!  
It’s online, open‑source, and ready for anyone to use.

⭐ **Star it on GitHub:** [FreeDevTools](https://github.com/HexmosTech/FreeDevTools)