A.H. Hunter, Chris Kennelly, Paul Turner, Darryl Gove, Tipp Moseley OSDI 2021
개요
Huge page를 효과적으로 Allocation하는 User-level allocator를 TCMalloc기반으로 개발하였다. 최대한 Packing시켜서, huge page release를 최소화할 수 있도록 stacked allocator design, radio active allocation policy등을 적용하였다.
Motivation
Huge page는 TLB miss를 줄여서 컴퓨팅 자원을 빠르게 사용할 수 있도록 한다. 그러나 Huge page를 고려하여서 Memory allocator를 작성하게 되면, Huge page allocation policy에 해당하는 CPU자원을 먹는다는 단점이 있따.
Importance
기존의 Transparent huge page와 같은 시스템은 Kernel이 User-level semantic을 모른다는 점에서 한계가 있었다. 따라서 User level allocator을 "잘" 사용하여서, Huge page의 성능상의 이점을 최대한으로 끌어내는 것이 목적이다.
Main Idea
Huge page aware allocation은 다음과 같은 Challenge를 가진다.
- 총 메모리 사용량을 예측할 수 없다. 즉 메모리의 Lifetime을 Allocation time에 정확히 예측하는 것은 불가능하다.
- 메모리의 효율적인 사용을 위해서, Huge page를 쪼개서 kernel에 return하는 것은 낭비가 심하다. 즉 Allocator은 최대한 Huge page align된 상태로 Kernel에 Release해야 한다.
- Huge page allocator자체로 매우 비싸기 떄문에, 잘못된 Policy decision을 최소화 하여야 한다.
기본 아이디어는, Huge page를 최대한 효과적으로 사용하기 위해서, 최대한 Huge page영역을 Internal fragmentation이 발생하지 않도록 사용하는 것이다.
Design
- Huge allocator
- Huge allocator은 할당된 Virtual memory를 관리한다. 모든 OS mapping은 Huge allocator을 통해서 일어난다. Huge allocator은 OS로부터 할당받은 Fresh allocation(unbacked)을 관리하는 역활을 담당한다.
- Huge cache
- 할당된 Huge page(backed)들을 관리하는 Cache영역이다. Huge page에서 만약 Huge filler가 채울수 없는 경우 (Huge page 사이즈 보다 Request크기가 같거나 클 경우)에는 바로 Huge cache에서 할당한다. Huge cache는 Huge page를 OS에 할당과 반납할때 사용되는 비용을 동일하게 계산하여서, 간단한 window알고리즘을 통해서 Memory를 반납한다. (자세한 알고리즘에 대한 설명은 논문 참고)
- Huge Filler
- Huge page에서 사용되지 않고 있는 free영역을 free list를 통해서 관리하고, Huge filler가 Allocation에서 그러한 부분을 찾아서 채워넣도록 하였다. 이처럼 Huge cache에게 현재 사용하고 있는 free list를 찾아서 Notification해주는 부분을 Huge filler라고 하였다.
- Huge Filler는 최대한 Huge page를 채우면서도, 다른 한편으로 최대한으로 비워서, Huge page allocation에 따른 비용을 줄여야 한다. 그러나 Allocation을 예측하기 힘들기 때문에 이 부분이 Challenge포인트가 된다. 또한 Internal fragmentation을 최소화 하여야 한다.
- Huge Filler는 이 문제들을 해결하기 위해서, L: Longest free range, A: Total number fo allocations, U: Total number of used pages의 Metric을 사용해서 Allocation priority를 결정하였다. L >= K, 그리고 Radiocative decay type allocation을 통해서 On-demand request에 대한 Allocation policy를 근사시켰다. (자세한 알고리즘은 논문 4,4 HugeFiller 참고) 여기서 흥미로운 사실은 Best-fit 알고리즘은 Overhead 뿐만 아니라, 근사치에서도 제일 좋지 않은 결과를 얻었다는 점이었다. 먼저 Lowest possible L을 고른다. 여기서 당연히 K(Requested size)보다는 커야 한다. 이를 통해서 제일 Fragmentation이 발생할 huge page를 선택한다. 그 다음 A를 U에 우선하여 고른다. 이는 Fullness보다는 Fragmentation, 즉 방사선 모델에 의거하여, Allocation이 제일 많은 page가 가장 나중에 free될 확률이 높음을 반영시키는 것이다.
Evaluation
- 결과적으로 기존 ffmalloc대비 약 12%의 메모리 overhead를 줄였으며 TLB miss rate를 6%감소시켜 성능적으로 3%정도의 향상을 구글 시스템 전체적으로 가져올 수 있었다.
Conclusion
- 언듯 보기에는 Naive한 Memory allocator개발, 즉 Enginnering적인 논문처럼 보이지만, 내용은 좀더 흥미로운 내용들이 많이 있다.
- 또한 Huge page관리를 커널이 하는 것보다는 User가 할경우, 어떠한 Optimization이 가능한지, 기존의 kernel-based huge page management와는 다른 차별성이 있다.