본문 바로가기

논문 리뷰

A Comprehensive Analysis of Superpage Management Mechanisms and Policies

  • Superpages (2MB pages) = Hugepage
  • superpage의 생애 주기 동안 발생하는 이벤트, 그 이벤트가 어떻게 트리거되고 반응하지는지에 대한 설계 탐구
  • superpage 관리와 다른 설계를 했을 때의 트레이드오프를 이해할 수 있는 프레임워크 제안 
  • 제안하는 프레임워크를 기반으로 왜 최신 설계들이 서로 다른 성능을 내는지에 대해 논의 
  • latency spike와 memory bloat의 원인 규명
  • Quicksilver 소개 : 새로운 superpage 관리 디자인 -> 주소 변환 성능을 유지한 채 latency spike와 memory bloat 설명 

1. Introduction

modern computer -> 메모리 크기 증가, 가상 메모리 사용 -> memory footprint 큼 -> VA to PA 주소 변환 비용 증가 -> 성능에 악 영향 

주소 변환 비용을 감소시키기 위해 superpages(hugepage) 도입 

hugepage 사용 장점 

  • hierarchical page table의 1level 제거 -> TLB miss 발생시 필요한 메모리 접근 횟수 감소 
  • TLB 엔트리 하나당 수용하는 메모리의 크기가 (2MB) 커기지 때문에 TLB를 보다 효율적으로 사용 가능

hugepage 도입 문제점 

  • 운영체제가 superpage를 효율적인 방식으로 관리하는 것이 어려움

본 논문에서 다루는 것

  • transparent하게 관리되는 superpage의 생애 주기에서 발생하는 5가지 이벤트 정의 
더보기
  • be allocated : (superpage는 2MB라고 가정) 2MB의 연속적인 물리적 메모리 공간을 물리적 메모리 할당자로부터 할당 받아야 한다
  • be prepared : 익명의 메모리에 대해서 전체 2MB 영역은 zero (초기화) 되어야 한다
  • mappping from virtual memory to physical memory created
  • mapping destroyed
  • physical memory deallocated 
  • 5가지의 각 이벤트를 핸들링하기 위한 최신 접근법들 분석 
더보기
  • THP -FreeBSD, Linux
  • Ingens
  • HawkEye
  • superpage 관리에 대한 새로운 observation 제안
더보기
  • (리눅스의 THP에서 처럼) superpage의 물리적 할당, 준비, 맵핑은 memory bloat이 크게 발생
  • 서버 워크로드에서 tail latency 문제를 완화하기 위해 superpage 할당을 지연하는 것은 superpage가 주는 주소 변환 이점을 감소시킴
  • superpage 할당은 in-place 프로모션이 가능하고, 비동기적으로 out-of-place 프로모션도 필요로 함 
  • 물리적 superpage를 예약하고 가능한 superpage의 부분적 할당 해제를 지연시키는 것은 fragmentation 발생을 줄이고, superpage을 더 많이 사용하게 해 주소 변환 이점 초래
  • bulk zeroing = 효율적 
  • Quicksilver 소개  
더보기
  • FreeBSD의 reservation 기반 물리적 메모리 할당을 기반으로 하는 superpage 관리 시스템 
  • 메모리 bloat과 fragmentation을 완화하면서도 aggressive한 superpage 할당이 가능하게 함
  • Ingens으로 memory bloat을 제한

 

2. Transparent Superpage Management

2.1. Physical Superpage Allocation 

  • 물리적으로 superpage 크기만큼의 연속적이고 사용가능한 메모리 공간이 있다면 동기적으로 할당 
    • 메모리 단편화가 심한 경우 할당 불가능 -> 일반적인 크기의 4KB page 할당
  • 가상 메모리에 4KB page가 할당된 이후에는 비동기적으로 superpage로 할당될 수도 있음 
    • OS가 free physcial memory를 만들기 위해 migration을 하거나
    • 어플리케이션이 page 가 free되어 superpage를 사용할 수 있을 때까지 기다림 
  • free physical superpage가 있으면 이전에 접근된 가상 메모리 공간에 할당될 수 있음

2.2 Physical Superpage Preparation

  • 물리적 superpage가 할당되고 나면 mapping되기 전에 초기 데이터로 준비 (해당 메모리 구역 초기화) 
  • preparation 3가지 방식
    1. zeroing : 가상 메모리 공간이 익명이라면 그냥 해당 페이지를 zero
    2. file reading : 가상 메모리 공간이 memory-mapped 파일 이라면 데이터는 반드시 파일로부터 read 
    3. copying : 가상 메모리 공간이 현재 4KB page에 맵핑된 경우 해당 페이지에 존재하는 콘텐츠를 physical superpage로 반드시 복사 

2.3 Superpage Mapping Creation 

  • 맵핑되기 전까지는 4KB mapping에 접근할 수 있지만 이후에는 4KB의 수정 및 접근 등을 추적할 수 없음 
    • 따라서 운영체제는 superpage 중 일부가 dirty 상태라면 superpage mapping을 지연 
  • superpage mapping은 페이지 fault 발생시 생겨남 또는 비동기적으로 생기기도함 

2.4 Superpage Mapping Destruction 

  • superpage는 언제든 destroy될 수 있음 
  • 가상 superpage의 일부가 free 되거나 보호 정책이 바뀔 경우는 반드시 destroy 되어야 함 
    • 이 경우 destroy된 이후에 아직 사용중인 일부 페이지에 대한 4KB mapping이 재생성되어야 함 
  • superpage mapping 을 하면 OS는 superpage를 구성하는 내부의 4KB page의 접근 및 수정 여부를 추적할 수 없음 
    • 이런 경우 OS는 superpage mapping을 destroy하고 4KB x 512 mapping으로 대체하여 fine-grained 메모리 관리를 해야 함 
    • superpage에 첫번째 수정 발생 또는 메모리 사용량이 큰 경우  ->  superpage destroy -> 4KB 마다 수정 여부 표시 또는 swapping 가능 

2.5 Physical Superpage Deallocation 

Physical Superpage Deallocation이 발생하는 경우 

  • 어플리케이션이 일부 또는 전체 virtual superpage 를 free
  • 어플리케이션 종료 
  • 운영체제가 memory reclaimation(회수)가 필요한 경우 

Deallocation을 위해 필요한 조건

  • superpage mapping 제거 -> 2MB 전체가 물리적 메모리 할당자로 돌아가거나 4KB page로 쪼개짐 
  • 4B로 쪼개진 페이지를 메모리 할당자로 반납하는 것은 단편화를 증가시켜 추후 superpage 할당을 더 어렵게 함
  • superpage의 일부 또는 전체가 메모리 할당자로 반납되기 전에 superpage에 포함된, 초기화는되었지만 free되지 않은 모든 4KB 페이지들은 반드시 보존되어야 한다.     ↓ (?) 
Before part or all of a physical superpage is returned to the physical memory allocator, any constituent pages that have been prepared but not freed must be preserved.

Presevation 방식 

  • In-use 페이지들은 반납되지 않고 유지되고 해당 페이지에 대하여 4KB 맵핑이 만들어짐
  • 또는 in-use 페이지들을 다른 물리적 페이지로 복사해주고, 전체 superpage는 반납
  • in-use 페이지들을 반납하기 전에 보조저장장치에 write

 

3. State-of-the-art Designs

3.1 FreeBSD

  • reservation 기반의 메모리 할당자 : 물리적 superpage 할당과 preparation을 분리 

FreeBSD의 Allocation 

  • 정렬된 2MB 메모리 영역에서 첫번째 page fault가 발생하면 물리적 superpage 할당(reserve) 시도
    • 물리적 superpage 할당이 가능하면 2MB 크기를 넘는 memory-mapped 파일 할당  
    • anonymous 메모리는 가능하다면 크가와 상관없이 항상 superpage 사용 
  • 물리적 superpage가 anonymous 메모리에 할당되면, 페이지 fault가 발생한 4KB page는 prepare되고, 예약된 엔트리가 만들어져 모든 구성 페이지들을 트랙킹
    • 해당 2MB 영역에서 페이지 fault가 발생하면 페이지 할당을 하지 않고 superpage 내의 4KB 페이지를 준비
    • superpage의 preparation은 가지고 있는 모든 페이지의 preparation이 끝나면 끝남 
  • FreeBSD는 superpage 맵핑을 page fault 중에 동기적으로 생성
    • 오직 모든 4KB page들의 protection 상태 수정 상태들이 같은 경우에만 superpage mapping 생성 

FreeBSD의 Destruction

  • superpage의 일부 페이지의 protection 상태가 바뀌거나 일부가 unmapping되면 destruction 
    • 전체 superpage에 dirty 표시하지 않고 4KB mapping 하나에 표시 
    • 모든 구성 페이지들이 수정되면 하나의 dirty superpage mapping 생성 
  • 가능한 deallocation을 미룸 -> 메모리 단편화를 최소화하고, free physical superpage의 사용성을 보존하기 위해
  • superpage 중 일부가 prepared된 것을 찾고, 그것에 대응하는 reservation을 쪼개어 해당 2MB 영역이 회수될 수 있도록 함 

3.2 Linux

Linux의 superpage Allocation

  • 리눅스의 THP는 익명 메모리에만 superpage를 할당
  • 첫번째 page fault 발생시 2MB 가상 메모리 공간에 물리적 superpage 할당 
  • superpage 할당이 실패하면 즉시 페이지 migration를 통해 메모리 compaction을 수행하고 superpage를 생성
    • 단편화가 심한 상황에서는 migration도 실패하게 됨 

Linux의 superpage preparation

  • 전체 superpage는 항상 할당 직후에 초기화되어야 함 
    • 초기 page fault latency는 증가시키지만 평균 latency는 감소 

Linux의 superpage Mapping

  • preparation 이후에 mapping이 즉시 생성됨 

Linux의 superpage Destruction

  • superpage의 일부 또는 전체가 unmapp되거나 protection 상태가 바뀌면 mapping이 destroy

Linux의 superpage Deallocation

  • superpage의 일부 또는 전체가 free되면 superpage는 deallocate
  • 그리고 free 된 메모리는 즉시 회수됨

Linux의 khugepaged

  • first-touch 정책 : 첫번째 page fault 발생시에만 superpage 할당 가능 
  • khugepaged : 페이지 테이블을 비동기적으로 스캔하여 최소 1개의 dirty 4KB mapping 을 포함한 2MB 가상 메모리 공간 탐색하여 superpage 할당 시도 
    • superpage 할당할 공간이 있으면 성공이고, 그렇지 않으면 페이지 migration으로 메모리를 회수하는 메모리 컴팩션 수행
  • virtual 2MB 영역 접근, 페이지 fault 막고 기존의 4KB mapping을 destroy 한 후에 superpage preparation 
    • 이전에 맵핑되었던 페이지들의 콘텐츠는 복사되고, unmapped된 페이지들은 zero

3.3 Ingens and HawkEye 

Ingens Paper Review

 

Coordinated and Efficient Huge Page Management with Ingens

Abstract

www.notion.so

  • Ingen은 FMFI를 기준으로 fragmentation이 적을 경우 aggressive huge page promotion을 한다. (Linux의 THP처럼) 반면에 fragmentation이 큰 경우 base page의 일정 비율이 할당된 이훼 promotion을 수행하는 conservative utilization based 전략을 사용한다 (FreeBSD처럼)

    즉, memory fragmentation 정도를 고려하여 memory float과 MMU overhead (performance)를 조절한다.

  • page mapping전 수행해야 하는 page zeroing 작업으로 인해 page fault latency가 발생하는 문제를 해결하기 위해 page fault handle 과정에서는 base page를 할당하기만 하고 khugepaged (비동기, 백그라운드 스레드)로 promotion 작업을 넘긴다.

    이는 page allocation latency를 감소시킬 수 있으나 page fault 발생 시 우선적으로 base page만을 할당한다면 spatial locality가 좋은 프로세스에 huge page를 할당하는 이점이 줄어들 수 있다.

  • fairnes를 보장하기 위해 메모리 연속성을 명시적으로 관리하고 접근 빈도를 표시하여 프로세스의 우선순위가 높고, huge page를 조금 가지고 있는 프로세스에게 promotion 우선권을 부여한다.

    → 디테일한 상황 판단으로 fairness를 보장할 수 없다.

HawkEye Paper Review

 

HawkEye: Efficient Fine-grained OS Support for Huge Pages

Abstract

www.notion.so

  • Primitives of HawkEye
    • 비동기 page pre-zeroing을 이용하여 page fault latency 감소
    • 할당된 huge page 내부에 zero-filled baseline page 식별 및 중복 제거하여 memory float 방지
    • huge page 크기 영역의 fine-grained access trackin, access coverage(huge page 내의 base page가 몇 개나 접근되었는지)를 기준으로 promotion 결정
    • MMU 오버헤드를 기준으로 fairness 추정
  • Asychronous page pre-zeroing
    • Linux buddy allocator에서 2개의 배열을 이용하여 free page 관리
      1. zero: 프로세스에 page 할당을 위해 사용
      2. non-zero : 프로세스가 반납한 page가 추가되는 배열
    • 비동기 스레드가 주기적으로 non-zero 배열에서 page-zeroing을 수행하고 zero 배열로 보낸다.
    • 이때, 비동기 스레드는 rate-limited로 일정 시간당 작업량이 제한된다. 그리고 zeroing을 수행할대 CPU 캐시를 거치지 않고 write buffer에 바로 데이터를 쓰도록 하는 non-temporal write 방식을 취한다. 이 방식으로 인해 기존의 캐시 성능에 영향을 주지 않고 pre-zeroing을 할 수 있다.
    • pre-zeroing이 불필요한 메모리 영역을 필요로 하는 경우 non-zero 배열에서 우선적으로 할당한다.
  • Memory bloat vs Performance
    • page fault가 처음 발생하면 huge page를 할당

    • memory 사용량이 높은 경우

      → 기존의 huge page들을 스캑하여 사용되지 않는 base page를 threshold 이상으로 가지고 있는 경우 demotion하고 zero-filled base page의 중복은 제거한다.

    • 주기적으로 bloat recovery 스레드를 발생시켜 huge page가 필요하지 않다고 판단되는 프로세스에서 demotion을 수행한다.

  • Fine-grained huge page promotion
    • 기존의 huge page 기법은 virtual address 내림차순으로 page promotion을 한다.
    • HawkEye는 메모리 접근 패턴을 기반으로 promotion을 한다.
    • access-coverage : 짧은 간격으로 huge page sized 영역에서 접근된 base page의 개수를 나타낸다.
      1. access-coverage는 다음과 같은 프로세스를 매 30초 마다 반복한다.

        i) 정기적으로 page table access bit을 샘플링하고, 샘플링 결과들의 access-coverage의 exponential moving average(EMA)를 유지한다.

        **exponential moving average : 가장 최근의 데이터 포인트에 더 큰 가중치와 중요성을 부여하는 이동 평균 (MA) 유형이다.

        ii) page table access bit를 clear하고, 1초 후에 몇 개의 bit가 set되었는지 테스트한다. (1초 동안 접근된 page 개수 측정)

      2. access-coverage는 해당 영역의 TLB에 필요한 base page 엔트리의 개수를 나타낸다.

        → huge page promotion으로 인한 benefit을 추정하는데 사용한다.

        높은 access-coverage를 가진 영역은 TLB 경쟁이 많이 발생할 수 있기 때문에 huge page promotion의 이점이 크다.

        그래서 access-coverage가 높은 영역에 huge page 할당한다.

 

4. Analysis of Existing Designs 

더보기

Benchmarks

  • GUPS : 2^32 serial random memory access to 2^30 64-bit integers
  • Graphchi-PR, BlockSVM, ANN : 데이터가 큰 태스크 해결을 위해 out-of-core implementation 사용 
    • Graphchi-PR : 전처리된 트위터-2010 데이터셋에서 페이지랭크 3iteration  연산
    • BlockSVM : kdd2010-bridge 데이터셋에 분류 모델 훈련시킴
    • ANN : 전처리된 해시 테이블 (2GB)에서 가장 가까운 이웃에 임의로 쿼리를 날림 
  • XSBench : Monte Carlo neutron transport 알고리즘의 병렬 계산 커널
  • Canneal, freqmine : PARSEC 벤치마크 + 큰 메모리 사용량

Observation 1

Coupling physical allocation, preparation, and mapping of superpages leads to memory bloat and fewer superpage mappings. It also is not compatible with transparent use of multiple superpage sizes.

superpage의 할당, 준비, 맵핑을 결합하는 것(=Linux's first touch policy) 은 메모리 낭비를 초래하고 superpage 맵핑을 더 적게 하도록 하며, 여러 사이즈의 superpage들을 효율적으로 사용하는 것에 적합하지 않다. 

  • Linux's first touch policy의 장점 
    • 짧은 page walk time 
    • TLB 효율성 증가 
    • 즉각적인 주소 변환 
    • superpage 를 많이 사용하여 page fault 발생 횟수 감소
    • => 연속적인 free 메모리가 충분한 경우 최고의 mapping policy 
  • Linux's first touch policy의 점 
    • memory bloat 
    • superpage의 preparation time으로 인한 시간 낭비 
    • virtual memory가 커짐에 따라 superpage mapping을 생성할 기회가 사라짐 
      • page fault -> 리눅스는 힙 영역을 넘어서 superpage mapping을 생성할 수 없기 때문에 4KB 페이지를 인스톨함 -> 나중에 힙 영역이 넓어져도 superpage mapping을 할 수 없음 
    • 더 큰 anonymous  또는 file-backed superpage로 확장될 수 없음 

Observation 2

Asynchronous, out-of-place promotion alleviates latency spikes but delays physical superpage allocations.

비동기, out-of-place promotion (4KB 여러개  -> superpage)는 latency spike를 완화하지만 물리적 superpage 할당을 지연시킴

  • promotion-based 정책은 4KB mapping을 사용한 뒤 나중에 그것들을 superpage mapping으로 대체할 수 있음 
    • 이 방식은 superpage mapping 생성에 대한 더 나은 결정을 할 수 있게 하고, 다양한 사이즈의 superpage 지원할 수 있게 함
    • out-of-place promotion (Ingens and HawkEye) : 물리적 superpage는 미리 할당되지 않고, 페이지 부재가 발생하면 4KB 페이지가 할당됨 (연속적이지 않아도 됨) -> 운영체제가 superpage mapping을 생성하려고 하면 반드시 할당하고 이미 mapped된 4KB 페이지를 migrate하고 zeroing해야 함 -> 기존의 4KB mapping은 무효화 
    • in-place promotion (FreeBSD) 
  • Linux는 커지는 힙에도 superpage mapping을 생성할 수 있게 하는 khugepaged 사용 
    • 메모리 단편화 -> superpage 할당을 실패하면 메모리 compaction을 시도 
  • Ingens & HawkEye : Linux의 first-touch 정책을 disable 하고 대신 khugepagesd를 개선시킴 
    • superpage 할당을 critical path에서 내림 
    • latency spike 완화시팀 
    • => khugepaged가 주요한 superpage 관리 매커니즘으로 작동 
  • out-of-place promotion은 물리적 suprpage 할당을 지연시키지만 궁극적으로 superpage mapping을 생성 
  • 가장 보수적인 in-place promotion 정책이 superpage mapping 생성을 가장 빠르게 함 

Observation 3

Reservation-based policies enable speculative physical page allocation, which enables the use of multiple page sizes, in-place promotion, and obviates the need for asynchronous, out-of-place promotion.

reservation 기반 정책은 다양한 사이즈의 페이지, in-place promotion을 허용하는 물리 페이지 할당을 하고, 비동기, out-of-place promotion의 필요성을 제거

  • in-place promotion은 page migration이 필요 없고, first-touch에 superpage를 생성하고 점진적으로 내부의 4KB 페이지를 prepare, mapping 함 -> allocation은 즉시하지만 mapping creation을 지연됨 
  • FreeBSD
    • in-place promotion 정책 + reservation system -> superpage를 conservative 하게 생성하여 성능 저하로 이어지지 않게 함
    • 즉각적으로 superpage 를 할당하지만 mapping 생성은 지연시킴 
    • anonymous 메모리에 대해서는 물리적 superpage 할당을 aggressive하게 함 : 페이지 부재가 발생하면 항상 superpage를 할당 

Observation 4

Reservations and delaying partial deallocation of physical superpages fight fragmentation.

superpage reservation 과 부분적 deallocation 지연은 단편화를 방지함 

기존의 시스템에서 메모리 단편화 핸들링하는 방법 

  • 리눅스는 superpage 할당에 실패하면 즉시 메모리 컴팩션을 수행 -> greedy하게 superpage를 사용

  • FreeBSD는 superpage의 부분적 deallocation을 지연 시킴 -> free superpage의 회수 가능성을 증가시킴  (4KB 페이지 하나가 곧 free된다면 해당 페이지들은 lower-ordered buddy queue에 놓고, reallocated될 확률을 높임) 
    • 즉, 부분적 deallocation은 메모리 단편화를 줄이기 위해서만 수행 
  • Ingens은 백그라운드에서 defragment를 활발하게 수행 
    • 참조되지 않는 메모리를 migrate하여 실행 중인 어플리케이션에 영향을 최소화함
    • 리눅스에 비해 적은 latency spike
    • 그러나, migration은 프로세서와 메모리 자원을 많이 소비함

Observation 5

Bulk zeroing is more efficient on modern processors than repeated 4KB zeroing.

대량을 한번에 zeroing하는 것이 4KB 여러 개를 반복해서 zeroing 하는 것보다 효율적

  • 현대 CPU들은 2MB 페이지를 bulk zeroing으로 빠르게 zero
    • bulk zeroing : 4KB 보다 크기가 큰 어셈블리 언어 페이지를 호출

 

5. Design and Implementation

5.1 Design 

Aggressive Physical Superpage Allocation 

  • Quicksilver는 FreeBSD의 reservation system 유지
    • 다양한 사이즈의 superpage 지원
    • memory bloat 방지 
    • superpage가 사용할 수도 있는 가상 메모리 영역이 처음 접근되었을 때 물리적 superpage를 할당 
  • page migration을 피하기 위해 동기적으로 수행 

Hybrid Physical Superpage Preparation

  • 점진적 preparation과 일괄 preparation 사이의 균형 유지 
  • reservation : 초기에 점진적 preparation -> 초기 pagef fault latency 최소화, 즉각적인 주소 변환 이점 감소 
  • 따라서 Quicksilver는 threshold 추가 (t)
    • t 4KB pages prepared -> superpage의 남은 부분을 모두 일괄적으로 prepare
    • 이 방식은 즉시 superpage를 prepare하거나 map하는 것이 아니라  bloat을 감소시킴 
  • 64 4KB 페이지가 접든되면 물리적 superpage가 거의 populated 될 확률 높음 -> 남은 페이지들의 준비와 superpage를 생성할 가능성 높음 
  • bulk zeroing으로 superpage의 남은 부분을 zero filling할 때 속도를 향상시킴 

Relaxed Superpage Mapping Creation 

  • 항상 물리적 superpage가 완전히 준비되면 mapping을 생성하도록 하기 위해 내부 페이지의 접근 또는 수정 상태가 다른 경우 superpage mapping을 생성하지 않음 (=Linux, Ingens, HawkEye)
  • file-backed superpage에 대해서 추가적인 디스트 입출력을 피하기 위해 FreeBSD의 write-protection 매커니즘을 유지 -> 모든 내부 페이지들이 접근된 경우는 사용하지 않음 
  • file-backed superpage는 fully prepared 일때 fully 접근되지 않을 수도 있음 
  • 서로 다른 access bit을 허용하여 file-backed superpage 생성을 더 많이 하도록 함 

On-demand Superpage Mapping Destruction 

  • 아래와 같은 경우에 mapping destruction 
    • superpage 내부의 메모리 일부 또는 전부가 free 되었을 때
    • superpage 내부의 메모리 일부의 protection 상태가 변경되었을 때
    • 물리적 superpage가 메모리 회수를 위해 deallocate되어야 하는 경우 
  • Quicksilver는 FreeBSD의 destroying mapping 정책을 유지하여 위에서 언급한 경우에만 destruction 

Preemptive Physical Superpage Dealllocation 

  • 물리적 superpage의 일부 deallocation 을 지연 -> 단편화 방지, 동기 물리적 superpage 할당의 효율성 극대화X
  • Quicksilver는 free physical superpage의 타겟 개수를 유지
  • preemptive deallocation -> 잘사용되지 않고 덜 접근되는 superpage를 피함 
  • 장점
    • 적은 페이지 migrate
    • preemptive migration 은 백그라운드에서 발생해서 critical path에 영향 X
    • 덜 접근되는 superpage에서 deallocation이 발생하기 때문에 실행 중인 프로세스에 최소의 영향만 줌 

5.2 Implementation

Quicksilver

  • FreeBSD 11.2 에 구현 
  • FreeBSD의 file-backed 메모리에 대한 superpage 지원 개선 
  • anonymous memory에 초점

Hybrid Preparation 

  • physical superpage는 threshold (t) 에 그 개수가 도달할 때까지 점진적으로 prepared
  • superpage의 남은 부분들은 zero-filling (prepared) 
  • 동기적(Sync-t), 비동기적(Async-t)으로 preparation 가능
    • Async-t
      • 주기적으로 physical reservation 연결 리스트를 스캔하고, t 에 도달할 때까지 가장 active한 remainder에서부터 zero-filling을 시작 -> 프로세스 아이디가 아닌 physical allocation activity 순서에 따라 prepare 되기 때문에 fairness 보장 
      • 4KB 페이지 개별적으로 zeroed -> zero 성능은 떨어지지만 락 경쟁 감소 
      • 모든 페이지가 zero 된 즉시 superpage mapping이 생성되는 것이 아니라 zero된 이후 첫번째 page fault 발생 이후 생성
    • Sync-t
      • 가능한 가장 큰 bulk 사이즈로 페이지 zeroing -> 페이지 zeroing이 끝나면 페이지 fault handler는 즉시 superpage mapping을 생성할 수 있음

Relaxed Mapping Creation

  • anonymous 메모리 -> relaxed mapping creation  => 수정 및 접근 상태 확인X
  • Sync-t가 zero-filling을 완료한 이후에 즉시 superpage mapping creation을 하게 함 
  • file-backed 메모리 -> Async-t 이후 첫번재 page fault가 발생한 superpage 에서 mapping 생성 
  • relaxing accexx bit checking -> Quicksilver superpage mapping creation 시도 

Preemptive Deallocation

  • 물리적 superpage는 자주 잘 사용되지 않는 상태가 됨 -> deallocation 지연 
  • 충분한 superpage 할당을 보장하기 위해 Quicksilver는 잘 사용되지 않는 superpage의 deallocation preemptive하게 수행하여 free superpage를 회수하는 데몬을 사용
    • free physical suprpage의 target number 유지
    • 주기적으로 reservation 스캔하고, inactive time 확인하여 deallocation 여부 결정
    • inactive time이 길면 데몬은 superpage 내부의 4KB 페이지들을 migrate 하여 free physical superpage를 회수 
    • 실행 중인 어플리케이션 간의 경쟁을 피하기 위해 데몬은 최대 메모리 대역폭을 1GB/s로 제한

 

6. Methodology 

Fragmentation 

  • 단편화 정도 나타내는 레벨: (단편화 없음) Frag-0 < Frag-50 < Frag-100 (단편화 심함)
  • 메모리 pressure이 있기 전까지 fragment 발생시킴 -> then starts over and fragments a target number of superpages.
  • superpage fragment : 2MB 가상 메모리 영역을 touch, touch하지 않은 부분은 unmap
  • superpage allocation을 유발하고 부분적 deallocation을 강제하여 superpage 단편화 발생시킴 

Library Differences

  • 같은 라이브러리라도 운영체제마다 그 성능이 다른 부분을 조정하여 모든 시스템에서 정확히 같은 바이너리가 실행되어 그 차이를 제거

System Tuning

  • 리눅스 튜닝 X
  • FreeBSD는 40Gbps NIC 버퍼 사이즈를 사용, libc 라이브러리를 FreeBSD12.0에서 가져옴, 최근 패치된 superpage repromotion 가능성 증가, 익명 메모리에 대한 dirty 비트 - relaxed 
  • Ingens and HawkEye - default setting
    • Ingens - superpage threshold : 90%-utilization => 0% , 1GB/s proactive memory compaction 
    • HawkEye - 1.6MB/s 속도로 promotion => 100% CPU maximum, promotion threshold 1

 

7. Evaluation 

Quicksilver variant : Sync1, Sync-64, Async-64, Async-256

7.1 Non-fragmented (Frag-0) Performance 

Performance speedup over Linux under three fragmentation levels. Red boxes indicate that the system performs worse than Linux on that application. The normalized standard deviation of runtime is no greater than 5% unless specified in parentheses.

Sync-1 vs Linux 

  • Sync-1은 증가하는 힙을 예측하여 superpage 할당 (리눅스보다 좋은 성능) 
  • Sync-1은 ANN과 Graphchi-PR에서 file-backed superpage 생성이 리눅스보다 좋은 성능 

Promotion Speed

  • out-of-place promotion은 느림 
  • redis cold 워크로드에서 Ingens와 HawkEye 성능 < Linux-4KB (백그라운드에서 superpage 관리할때 실행 중인 어플리케이션에 영향 있음)
  • Sync-64 > Async-64 (Async-64는 실행 중인 어플리케이션에 영향을 줄 수 있는 백그라운드 zeroing을 하기 때문)
  • less aggressive preparation, mapping 정책 > 즉각적인 mapping 

7.2 Performance Under Framentation

Performance speedup over Linux under three fragmentation levels. Red boxes indicate that the system performs worse than Linux on that application. The normalized standard deviation of runtime is no greater than 5% unless specified in parentheses.
Redis throughput (GB/s) and 95th latency (ms) of workloads Cold and Warm. Numbers in parentheses are 95th latencies. The maximum standard deviation is 0.04GB/s for throughput and 0.57ms for 95th latency.

  • 리눅스는 Redis cold 워크로드에서 Linux-4KB 보다 Frag-50/100에서 더 높은 tail latency -> on-allocation defragmentation은 page fault latency를 더 증가시키기 때문
  • FreeBSDSMS deframentation을 활발하게 하지 않아서 latency도 적음 
  • Ingens와 HawkEye는 page fault과 superpage 할당을 별개로 하고 백그라운드에서 메모리 컴팩션 -> 해당 워크로드에서 latency spike 감소, interference 감소 
    • 단편화 정도가 증가할수록 리눅스 보다 속도가 빨라진다. 
    • HawkEye는 XSBench 조금 느림 -> 어플리케이션이 실행될 때 대부분의 메모리 컴팩션이 실패하고 중요한 데이터가 높은 주소공간에 위치하기 때문 
  • Quicksilver는 지속적으로 non-server, server 워크로드에서 모두 좋은 성능을 냄 
    • 백그라운드 defragmentation은 page fault latency 증가를 피하면서 unfragment 

7.3 Memory Bloat 

  • 대부분의 시스템이 기본 리눅스 대비 1% 미만의 memory bloat만이 발생하지만 long-running 서버는 여전이 memory bloat 발생
  • 어플리케이션이 자주 allocation, deallocation을 자주 하면 aggressive superpage preparation 정책은 preemptively preparation을 하고 free memory를 낭비하여 주소 변환 이점을 감소시킴 

Redis memory consumption (GB) of four workloads. Khugepaged further bloats memory in Linux

  • Redis 워크로드의 메모리 소비 비교 
    • 리눅스가 가장 memory bloat이 심함 -> khugepaged가 원인 (일부 deallocated된 superpage가 스캔되면 superpage를 재생성하기 위해 다시 할당하여 어플리케이션이 메모리를 free하거나 defragment하는 것을 무시) 
    • HawkEye는 TLB 오버헤드가 적은 경우 superpage 할당을 중지
    • FreeBSD만 fully utilizsed superpage promotion 
    • Async-256은 conservative promotion threshold를 가짐 

Sync-1 vs Sync-64

  • aggressive preparation (Sync-1) -> 과도한 superpage 생성 / long-running 서버에서 잘 사용되지 않는 superpage를 생성하여 메모리 연속성이나 전력을 낭비 
  • Sync-64가 long-running 서버에서 유리 

 

8. Conclusions

  • Quicksilver -> aggressive superpage allocation하면서도 memory bloat과 fragmentation 문제를 완화 
  • Sync-1에 비해 64가 long-running server에 적당 (과도한 superpage 생성 X)