편집토론문서 역사

Characterizing a Memory Allocator at Warehouse Scale 


Zhuangzhuang Zhou, Vaibhav Gogte, ..., Parthasarathy Ranganathan
ASPLOS 2025

개요

Memory allocator가 구글정도 되는 스케일의 서버 단에서는 어떤 오버헤드가 발생하며, 어떻게 최적화를 수행할 수 있을까?

Motivation

메모리 할당을 최적화하여 Warehouse-scale computers (WSC)의 생산성을 향상시키는 것이 중요하다. 이를 통해서 Datacenter tax를 최적화 하여 데이터 센터에서 사용하는 에너지를 절약하여, 비용 향상을 꾀하는 것이 목적이다.

Importance

이전 연구들은 주로 특정 Application혹은 라이브러리의 CPU 오버헤드에 초점을 맞추었다. 그러나, 이 연구에서는 General한 Memory allocator를 최적화 하는 것이 더 유익하다고 주장한다. 이 연구는 메모리 할당 최적화를 통해서 WSC레벨의 응용프로그램들에 대한 성능을 향상시킬 수 있다고 주장한다. 특히 이 연구는 Application의 CPU stall과 같은 문제가 20-64$정도 Cache miss와 같은 Application이 아닌 Memory allocator에서 발생한다고 이야기 하기 떄문에, 메모리 할당을 개선한다면 상당한 성능 향상을 가져올 수 있다고 주장한다.

또한 저자들은 Warehouse-scale에서의 성능 분석이 어떤 특징을 가지고, 일반 Application과는 어떤 차이점을 가지는지 철저히 분석하여 그에 따른 Optimization을 제공하는 연구가 없음을 지적하며, 이러한 연구의 중요성을 설파하고 있다.

Main Idea

주요 아이디어는 TCMalloc 메모리 할당자를 재설계하여 Cache locality을 개선하고 Cache miss를 줄여 WSC 환경에서 애플리케이션 생산성을 향상시키는 것이다. 이 연구는 TCMalloc의 세부 특성을 분석하고, 이러한 분석에서 도출된 인사이트를 바탕으로 여러 설계 개선안을 제안하였다.

Memory Allocator의 성능 분석

이 문단은 TCMAlloc에 대한 이해를 요구함으로, 논문 혹은 TCMalloc에 대한 문서를 읽어야 잘 이해 가능하다.

Allocation latency
Latency측면에서, Memory allocator의 Per-cpu cache에서 처리할 수록 Allocation latency가 작았다. 이는 Contiguous allocation의 경우에 Per-cpu cache hit이 잘 일어나기 때문에 당연한 현상이다.
Malloc CPU cycles
Malloc CPU cycles은 대략 3.6%-10.1% 정도 차지한다. TCMalloc과 같은 경우에는 Per-CPU cache에서 53%정도의 시간을 사용하였다.
Memory fragmentation
Fragmentation ratio란 (Fragmented memory / Live in-use memory)를 의미한다. 전체적으로는 22.2%의 Memory fragmentation이 발생하였으며, External 18.8% (Memory allocator가 Cache하고 있는 사용하지 않아 발생하는 오버헤드), Internal 3.4% (할당한 메모리와 할당을 요청한 메모리의 크기 차이에서 발생하는 오버헤드)정도 발생하였다. TCMalloc에서는 Central heap과 Pageheap에서 대부분의 External Fragmentation이 발생하였는데, 이는 Central free list는 소속된 모든 오브젝트가 Free되야만 OS로 메모리를 free하고, pageheap는 free spans들을 hugepage를 통해서 관리하기 때문에 그런것으로 분석되었다.
Distribution of allocated objects
1KB보다 작은 Obnjects들이 전체 메모리 에서는 28%만 차지하였지만 98%의 Allocated objects들의 사이즈였다. 8KB이상의 메모리 오브젝트들은 50%의 메모리를 차지하였다. Object들의 Lifetime은 매우 Variation이 다양하였다. 일반적으로 오브젝트 크기가 작을수록 적은 Lifetime을 가지는 경우가 대부분이었다. 46%의 오브젝트 할당이 1 milisecond보다 작은 lifetime을 가지고 있었다. 1GB보다큰 object 할당은 65%가 하루보다 큰 lifetime을 가지고 있었다.

Design

  1. Heterogeneous Per-CPU Cache: Application의 비균일한 Per-cpu cache사용량에 대한 보정을 위해서 사용하였다.
  2. NUCA-aware Transfer Cache: 비균일 캐시 아키텍처를 가진 플랫폼에서 캐시 지역성을 유지하기 위해
  3. Central Freelist with Span Prioritization: 할당 위치를 개선하기 위해.
  4. Lifetime-aware Hugepage Filler: 대용량 페이지 커버리지를 개선하고 변환 조회 버퍼(TLB) 미스를 줄이기 위해​
이기종 Per-CPU 캐시 (Per-CPU 캐시는 TCMalloc이 내부적으로 사용하는 Per-core 캐시 리스트를 말함)
TCMalloc에서 사용하는 Per-CPU 캐시의 경우, WSC 환경에서 자주 일어나는 CPU 코어 재배치에 대비하기 위해 vCPU ID를 사용한다. 그러나, Load spikes와 Diurnal usage 때문에 vCPU를 사용하더라도 서로 다른 스레드 사이에서 Per-CPU 캐시 미스율 차이가 발생하였다. 이 문제를 해결하기 위해, Per-CPU 캐시 크기를 동적으로 조절하도록 설계하였다. 별도의 백그라운드 스레드가 주기적으로 캐시 사용량을 모니터링하고 재조절하도록 하였다. 이를 통해 내부 단편화 문제를 어느 정도 해결하였다.
NUCA-aware 전송 캐시
소켓마다 Last-level 캐시에 접근하는 속도는 균일하지 않다 (Non-uniform). 이러한 NUCA 구조는 WSC 환경에서 많은 CPU 코어들을 유지하기 때문에 더 심해진다. 이때, Intra-cache 지연이 Inter-cache 지연보다 약 2.07배 더 컸다. 따라서 같은 Intra 캐시들이 동일한 캐시 라인을 공유하도록, Per-CPU 캐시에 메모리를 할당할 때 NUCA 구조를 고려하였다. 이는 메모리 전송 캐시를 최적화함으로써 달성되었다. NUCA-aware 전송 캐시는 해제된 메모리 오브젝트가 같은 Inter-cache 도메인에 속할 경우 재할당이 가능하도록 하였으며, 주기적으로 할당되지 않은 해제된 오브젝트들을 배치하여 해제하였다. 이를 통해 LLC 로드 미스를 4.37% 줄였고, 전체적으로 0.28%-1.72%의 성능 향상을 이루었다.
Central Free List
수명이 다른 오브젝트가 같은 Span을 공유하면, Span은 모든 오브젝트가 해제되어야만 재할당될 수 있어 외부 단편화가 증가하고 메모리 오버헤드가 증가할 수 있다. 그러나 TCMalloc은 Span에 있는 메모리를 재사용할 때, 단순한 링크드 리스트로 가장 앞에 있는 Span에서 수명과 상관없이 할당한다. 이는 해제될 수 있는 Span이 해제되지 못하게 하는 문제를 일으킬 수 있다. 이 문제를 해결하기 위해 Span에 있는 수명 크기에 따라 리스트 인덱스를 만들고, 수명이 긴 오브젝트가 있을 경우 그 Span에서 할당하도록 하여 수명에 의한 오버헤드를 약 1.41% 줄였다.
Pageheap
페이지 힙은 내부적으로 Huge page를 사용하는데, 이 Huge page가 외부 단편화의 51%를 차지할 정도로 큰 비중을 차지하고 있었다. TCMalloc은 이를 위해 내부적으로 페이지 힙 중 가장 많은 Span을 가지고 있는 페이지 힙을 '가장 해제될 확률이 적다'고 판단하여 Span을 할당한다. 그러나 이 논문에서는 추가적으로 수명을 고려하여 중앙 자유 목록 관리처럼 페이지 힙도 할당 알고리즘을 고도화해야 한다고 주장하였다. 작은 오브젝트와 큰 오브젝트는 수명이 다르기 때문에, 특정 크기 기준으로 페이지 힙을 크기에 따라 다르게 사용하도록 하여 수명을 반영시켰고, 결과적으로 1.02%의 성능 증가와 0.82%의 메모리 오버헤드 감소를 가져왔다.

Result

재설계된 TCMalloc은 플릿 처리량이 1.4% 증가하고 메모리 사용량이 3.5% 감소하였다. 상위 다섯 개 애플리케이션의 경우 처리량이 0.7%에서 8.1%까지, 메모리 사용량이 1.0%에서 6.3%까지 향상되었다. 이러한 향상은 Warehouse-scale에서는 매우 큰 비용 절감 효과로 다가오기 때문에 Practical한 연구라고 할 수 있을 것이다.

Contribution

1. WSC 환경에서 TCMalloc의 포괄적인 특성 분석을 제공. 2. 단순히 CPU 오버헤드를 줄이는 것보다 애플리케이션 생산성을 최적화하는 것의 이점을 입증. 3. 다른 최신 메모리 할당자에도 적용할 수 있는 TCMalloc의 구체적인 설계 변경안을 제안

Criticisms

이 연구는 유망한 개선점을 제시하지만, WSC 워크로드의 끊임없는 변화로 인해 엄격한 종단 간 평가를 수행하는 데 어려움이 있을 수 있다. 또한, 제안된 최적화의 영향은 특정 애플리케이션과 워크로드에 따라 다를 수 있으며, Memory overhead와 Performance overhead에 대한 Overhead-trade off가 나와 있지 않다.

Conclusion

이 연구는 메모리 할당 최적화의 중요성을 성공적으로 강조하고 있다. 애플리케이션 생산성에 중점을 두고 TCMalloc의 타겟 설계 개선을 구현함으로써 대규모 컴퓨팅 환경에서 상당한 효율성 향상을 달성하는 견고한 접근 방식을 제시한다.