Coordinated and Efficient Huge Page Management with Ingens

Coordinated and Efficient Huge Page Management with Ingens

위 논문을 읽고 정리한 내용입니다. 

Notion에서 정리하고 복붙해서 구조가 조금 이상하게 느껴지신다면 다음 링크에서 보시면 됩니다. 

---

Abstract

• RAM (random access memory)
  • 휘발성 메모리
  • 어느 위치에 저장된 데이터든지 읽고 쓰는데 동일한 시간이 걸리는 주기억장치
• 메모리 용량이 증가함에 따라 하드웨어 주소 변환 오버헤드가 증가한다.
• → 하드웨어에서 huge page를 엔트리로 갖는 TLB 를 사용한다.
• 운영체제와 하이퍼바이저가 huge page를 지원한다.
• → best-effort algorithm, spot fixes
• Ingens
  • huge page를 지원하는 프레임워크
  • first-class resource로써 huge page의 연속성을 관리한다.
  • page의 접근 빈도와 사용률을 추적한다.
  ⇒ 현재 시스템에서 문제가되는 fairness와 성능 원인을 제거한다.
• (본 논문의 프로토타입은 fairness, performance 향상, tail-latency 감소, memory bloat 감소)

1. Introduction

• RAM 용량 증가 → challenge for address translation
• Huge page를 사용하는 이유
  • modern CPU: logical to physical mapping을 위해 page table + TLBs 사용
  • hardware-supported address virtualization은 multi-level page table을 사용하는데 이것은 주소 변환 worst case의 cost를 증폭시킨다.
  ⇒ 따라서 하드웨어는 TLB miss 빈도를 줄이기 위해 huge page를 도입한다.
• (이 매커니즘은 huge page를 관리하는 운영체제와 하이퍼바이저의 능력에 따라 성능이 좌우된다. )
• recent architecture
  • 90년대까지 CPU는 TLB에 huge page를 저장할 수 있는 엔트리의 개수를 제한했다.
  • 새로운 아키텍처는 dual-level TLBs에 수천개의 huge page 엔트리를 저장할 수 있도록 지원한다.
  • huge page를 지원하기 위해 소프트웨어 (운영체제와 하이퍼바이저 등)가 메모리 관리를 개선시켜야 한다.
  • 운영체제는 일반적으로 4KB page에 초점을 맞춘 메모리 관리를 하기 위해 best-effort 알고리즘과 spot fixes를 사용했다.
  • 즉, 오늘날 운영체제는 huge page를 지원하는데 부적절하다.
• Ingens
  • 운영체제와 하이퍼바이저의 best-effort 알고리즘과 spot-fixes를 대체할 메모리 관리 매커니즘
  • 증가한 TLB 용량과 huge page를 지원하는데 적절한 방식
  • Ingens은 huge page 지원과 관련된 문제를 다음과 같이 해결하였다.
    • Latency: huge page는 높은 latency 분산과 tail latency 증가를 초래하지만 Ingens는 tail-latency를 감소시킨다.
    • ** tail-latency : response time의 대부분을 차지하는 I/O 요청 중 작은 비율을 차지하는 response time으로 시스템간 경쟁, 복잡한 서비스, 증가하는 요청 등의 다양한 원인으로 인해 발생한다.
    • Bloat: huge page는 내부 단편화로 인해 CPU나 가상머신이 많은 양의 메모리를 차지하게 하지만 Ingens는 이러한 bloat 현상이 0.8%로 적게 발생한다.
    • Unfairness: Ingens는 huge page의 greedy allocation으로 인한 unfairness를 완화한다.
    • High-performance memory savings: Ingens은 성능을 유지하면서 메모리 사용량을 줄인다.
  ** memory contiguity is an explicit resource to be allocated across processes
• explicit resource: 어플리케이션이나 가상머신에 할당되기 위해서 별도의 관리가 필요한 자원으로 기존 Linux에서는 memory contiguity가 implicit하게 관리되지만 huge page을 적절하게 사용하기 위해서는 contiguity도 별도의 관리가 필요하다고 주장한다.

2. Background

huge page를 지원하는 운영체제와 하이퍼바이저에 대한 overview

최신의 huge page 관리 기법의 성능 이점을 보여주는 실험

2.1 Virtual memory hardware trends

• virtual memory는 RAM에서 사용하는 주소 공간과 프로그램이 사용하는 주소 공간을 분리한다.
• page table은 하드웨어 TLB에 캐시된 page table 엔트리로 virtual → physical page number로 맵핑을 한다.
• huge page → TLB reach 증가 ↔ internal & external fragmentation 발생
• **TLB reach : TLB에 cache할 수 있는 데이터의 양
• huge page를 지원하기 위한 최근 하드웨어 트렌드
  • DRAM growth : DRAM 사이즈 증가는 더 깊은 페이지 테이블을 만들게 하고, page table의 reach를 증가시킨다.
  • Hardware memory virtualization : extended page table (Intel), nested page table (AMD)는 메모리 주소 변환이 더 복잡하다.게스트의 각 layer lookup은 호스트의 multi-level translation이 필요하기 때문에 latency가 증가한다.
  • 변환하는 동안 guest의 physical address = host의 virtual address 로 인지한다.
  • Increased TLB reach : Intel이 two-level TLB를 만들었고, 두번째 level의 TLB는 huge page를 엔트리로 갖는다.

⇒ TLB reach를 증가시켜 miss를 줄이기 위해 huge page를 사용하면서도 단편화를 줄이고, contiguity를 유지시키기 위해 운영체제의 메모리 관리가 필요하다.

2.2 Operating system support for huge page

• 초기 huge page를 지원하는 운영체제는 huge page pool로부터 explicit huge page allocation을 위한 인터페이스를 분리했다.
  • Windows는 explicit memory management API를 사용하여 huge page allocation을 한다.
  • OS X는 memory allocation API에 explicit flag를 설정하여 huge page를 사용한다.
  • Linux는 explicit allocation interface (hugetlbfs)를 통해 huge page를 사용한다
• **Transparent huge page**
  • virtual memory 에서 huge page를 사용하는 것을 지원하는 것으로 페이지의 크기를 자동으로 promotion, demotion 하는 것을 hugetlbfs 단점 없이 지원한다.
  • ** huge page의 생성, 관리, 사용의 대부분을 자동화하는 추상화 계층
  • transparent management of huge page는 multi-programmed & dynamic workload를 지원한다.
• Linux is greedy and aggressive
  • Greedy: page fault handler를 호출하여 local 정보를 기반으로 huge page promotion을 수행한다.
  • huge page를 즉각적으로 할당하기 위해 필요한 정보만을 고려하여 promotion을 수행하기 때문에 해당 page의 사용량 등은 고려하지 않는다.
  • Aggressive: 항상 huge page를 할당하려고 한다.
  • huge page는 2MB의 연속적인 물리적 메모리 공간이 필요하지만 메모리 공간이 부족한 경우도 있다.
  =>Linux는 huge page 사용으로 인한 성능 이점이 떨어질 수 있는 방식을 사용 중이다.

2.3 Hypervisor support for huge pages

• Ingens는 Linux + KVM case에 초점을 맞춘다.
• 하이퍼바이저에서 Ingens는 host의 huge page를 guest의 physical memory에 매핑하는 것을 지원한다.
• Ingens는 하이퍼바이저처럼 동작하기 때문에 extended page table을 수정하여 huge page를 사용한다.즉, CPU가 생성한 virtual address는 guest 운영체제가 구축한 page table을 통해 physical address로 변환하고, 이 physical address가 하이퍼바이저가 구축한extended page table을 통해서 machine address로 변환하여 메모리에 접근하는 것이다.
•  
• ** Intel의 extended page table: physical address에서 virtual address로 변환하는 기능을 하드웨어적으로 구현한 것으로 하이퍼바이저가 운영한다.
• Ingens는 운영체제와 하이퍼바이저에 동일한 memory management model을 적용한다.

2.4 Performance improvement from huge pages

• guest와 host 모두 4KB page를 사용한 경우, page table walk 실행 시간의 47.5% spend
• guest와 host 모두 huge page를 사용한 경우, page table walk 실행 시간의 4.2%만 spend

⇒ guest와 host 운영체제를 지원하는 transparent huge page support를 통해 성능 향상 (약 53%)

3. Current huge page problems

guest 운영체제 = Linux

guest 하이퍼바이저 = KVM

3.1 Page fault latency and synchronous promotion

• anonymous memory space 에 프로세스 fault가 발생하면 page fault handler가 physical memory를 page로 다시 할당한다.리눅스가 4KB page를 사용하는 경우 프로세스 fault가 발생하면 즉시 요청을 upgrade하고, 공간이 충분하다면 huge page를 할당한다. (greedy approach)
  • page fault latency 증가하는 이유
• ** anonymous memory : 커널로부터 직접 할당받은 메모리 영역으로 heap 을 거치지 않는다.
• page fault latency를 줄이기 위해 Linux는 asynchronously하게 huge page를 사용해야 한다.
• → asynchronous-only huge page promotion : 2% → 30% 까지 속도를 향상시킨다. (huge page 사용시 page fault latency가 증가하는 문제를 해결하는 것은 아님)

3.2 Increased memory footprint (bloat)

• memory bloat : 너무 많은 객체를 할당하여 메모리 사용이 급증하는 현상 (high memory usage)
• huge page는 성능을 향상시키지만 application이 huge page를 효과적으로 할당하지 못하는 경우가 있다.= TLB miss를 줄이지만 bloat가 증가한다.
• ex) Linux는 huge page가 단편화를 발생시킴에도 불구하고 가능하다면 최대한 huge page를 할당한다. (best-effort algorithm)
• 각 가상머신에서 Redis와 MongoDB를 사용했을 때, huge page로 인한 memory bloat
  • Redis (2백만 개의 키에 8KB 객체를 채우고 키의 70%를 randomly 삭제)huge page를 메모리에 할당하면 내부 단편화가 발생하고 메모리 사용량이 크게 증가하기 때문에 Linux는 huge page에 메모리를 거의 할당하지 않는다.
  • Redis는 물리적 메모리에 드물게 할당하고 삭제된 객체를 백업하여 메모리를 free 상태로 만든다.
  • MongoDB (처음 저장소에 1500만 개의 1KB 객체에 대하여 1000만 건의 요청을 받음)Linux는 사용되지 않는 메모리와 huge page를 사용한다.
  • → MongoDB는 huge page를 사용하여 메모리 사용량이 23% 증가한다.
  • MongoDB는 virtual address space에 객체를 거의 할당하지 않는다.
  • 즉, huge page를 사용하여 memory를 더 많이 사용하게 된다.
• application의 할당 패턴과 메모리 단편화 → huge page 사용 → 메모리 사용량
• ⇒ Linux의 huge page 할당 방식으로 application의 총 메모리 사용량을 예측할 수 없어 사용량을 고려한 page 할당을 할 수 없다.

3.3 Huge pages increase fragmentation

• aggressive promotion of huge page는 memory fragmentation을 발생시키면서 physical memory contiguity를 빠르게 소모한다.
• fragmentation 증가는 page fault latency와 memory bloat를 증가시키기 때문에 추가적인 성능 저하로 이어진다.

3.4 Comparison with FreeBSD huge page support

• FreeBSD
  • FreeBSD는 reservation-based huge page allocation을 사용하여 transparent huge page를 지원한다.
  • application이 2MB virtual address 공간에 접근하려고 하면 page fault handler는 연속된 메모리를 예약하지만 huge page공간을 사용하지 않고, base page를 할당한다.
  • 메모리 공간의 page 사용률을 모니터링하고, 예약된 메모리의 모든 base page가 할당된 경우에만 huge page를 사용한다.
  • 따라서 FreeBSD는 Linux의 huge page promotion보다 느리고, 메모리 사용률이 2MB 이상이 된 경우에 huge page promotion을 한다.
  • file-cached page에 huge page를 지원한다.
  • page cache나 swapping에서 페이지를 제거할 때 I/O traffic을 줄이기 위해 writable huge page를 만든다.
  • Linux huge page promotion보다 성능은 떨어지지만 메모리 bloat는 줄인다.
• Linux vs FreeBSD (huge page로 인한 성능 이점 비교)
  • dense, uniform access memory pattern에서는 둘의 속도가 비슷하다.
  • Free BSD는 asynchronous promotion을 지원하지 않기 때문에 메모리를 점진적으로 할당하는 application의 경우 이점이 줄어든다.

3.5 Unfair performance

• 본 논문의 모든 측정은 Linux를 게스트 운영체제로, KVM을 호스트 하이퍼바이저로 사용하는 가상 머신에서 수행한 결과이다.
• Ingens는 이 환경의 memory management code를 수정했다.
• Linux는 contiguity를 fair하게 redistribute하지 않기 때문에 unfair performance를 초래한다.VM0이 가능한 모든 huge page (3GB)를 얻는다.VM1이 메모리를 할당하는 동안 실행이 시작되는 VM2와 VM3는 huge page없이 실행된다.Linux는 asynchronous promotion을 통해 최근에 free된 huge page 3GB를 모두 VM3에 할당한다. → VM간 unfairness 발생
• VM0이 종료되고, 가지고 있던 huge page들을 반납한다.
• VM1이 메모리를 할당하기 시작하면 Linux는 huge page allocation을 위해 compact memory를 수행하지만 810MB에 그친다.
• → 실험: 메모리가 단편화된 상태인 4개의 가상 머신, 각 가상 머신에 8GB 메모리 할당

3.6 Memory sharing vs performance

• 하이퍼바이저는 동일한 콘텐츠를 가지고 있는 서로 다른 가상 머신들에 page를 share하고 detect한다.
• memory sharing : 가상머신이 사용하는 메모리 양을 감소시키고, VM consolidation ratio를 증가시킨다.
• ** VM consolidation ratio: 각 host machine에서 실행시킬 수 있는 virtual machine의 수
• KVM에서 host의 page sharing
  • base page단위로 수행된다.
  • base page의 content가 다른 가상머신에서 중복되지만 huge page 내부에 해당 base page가 들어 있는 경우 KVM은 huge page를 sharing할 수 있도록 base page들로 쪼갠다.
  → bloat를 줄이는 것을 우선시하여 성능에 안좋을 수 있다.
• huge page sharing
  • huge page demotion을 방지하기 위해 huge page에 속한 base page는 공유될 수 없다.
  • huge page를 base page로 쪼개는 것이 아니라 huge page 자체를 공유할 수 있게 한다.
• 실험 결과, huge page sharing은 성능에 좋지만, 메모리 소모량 감소가 적다.⇒ page sharing + huge page management
• (performance ↑ memory-saving ↓ - trade-off)

4. Design

• Ingens (=memory manager) 의 goal :
• transparent huge page 를 지원하여 latency, latency 분산, bloat를 줄이고, fairness를 보장하며, 성능과 memory saving 간의 trade-off 조절하는 것.
• Ingens의 basic primitives :
  1. utilization tracking
  2. access frequency tracking
  3. contiguity monitoring
• Ingens의 code and data structure** Promote-kth
• ** Scan-kth
•  

4.1 Monitoring space and time

• Ingens에서 huge page 이용을 위한 space와 접근 빈도 (time)을 측정하기 위해 효율적인 매커니즘 두가지를 도입했다.
• space 와 time 측정 정보를 수집하여 해당 정보를 통해 커널의 정책 결정을 돕는다.
• 1. Util bitvector (space)
  • 각 huge-page sized memory region 내에서 사용된 base page를 기록한다.
  • ** 2MB region은 512개의 base page를 포함한다.
  • bit = 1 : 해당 bit에 대응하는 base page는 사용 중이라는 것을 나타낸다.
  • bitvector는 radix tree에 저장된다.
    • radix tree
      
      
    • *** radix tree : 공간 사용이 최적화된 trie 자료 구조이다. 만약 특정 노드의 자손이 하나 밖에 없다면 그 노드는 자식 노드와 결합된다. 즉, 모든 내부 노드는 적어도 두명 이상의 자손을 가지게 된다. edge는 개체들의 순서로 라벨링 될 수 있어 작은 set을 가지거나 긴 prefix를 가지는 경우에 유리하다.
    • *** Trie = prefix tree : 주로 string을 가지는 dynamic set, 혹은 연관 배열을 저장하는데 사용되는 정렬된 트리 자료 구조로 트리상에서의 위치가 현재의 키를 나타낸다. 특정 노드의 모든 후손들은 그 노드에서와 동일한 prefix를 가지며 루트 노드는 빈 문자열을 갖는다. 값은 리프 노드나 특정 키에 해당하는 내부 노드에서만 존재한다.
  • Ingens는 huge-page number을 bitvector lookup을 위한 key로 사용한다.
  • page fault handler가 업데이트 한다.
• 1. Access bitvector (time)
  • base/huge page에 프로세스가 최근에 접근한 히스토리를 기록한다.
  • scan-kth : 주기적으로 페이지 테이블 내부의 프로세스의 하드웨어 access bit을 스캔하여 각 페이지마다 접근 빈도 정보를 8-bit vector로 저장한다.
  • Ingens는 bitvector로부터 exponential moving average (EMA / 지수 이동 평균)를 계산한다.** weight = bitvector에서 1로된 bit의 개수** α = 파라미터
  • ** F1 = t 시간에 접근 빈도
  •  
  • 계산 결과를 통해 페이지가 얼마나 자주 접근되는지 확인한다.

4.2 Fast page faults

• page fault handling를 빠르게 하기 위해서 huge page allocation (매커니즘) 과 promotion decision (policy)를 분리한다.
• Linux에서는 page fault handler가 언제 huge page promotion을 하고, 비동기적으로 사용하도록 백그라운드 스레드(Promote-kth)에게 신호를 줄지 결정한다.
• ** promote-kth: 메모리 공간이 부족하다면 compaction을 수행하고, page fault handler가 알려주는 page를 사용한다.
• Ingens의 page fault handler는 절대 latency가 긴 huge page allocation을 수행하지 않는다.
• Promote-kth가 실행되면, promotion할 다양한 page 후보 list를 가지고 그것들을 사용한 후에는 추가적인 다른 후보 page를 찾기 위해 virtual memory 스캔을 재개한다.

4.3 Utilization-based promotion (mitigate bloat)

• Ingens는 메모리 contiguity를 explicit하게 한다.
• (프로세스/가상머신이 사용 정도에 따라 할당 된 영역을 대부분 사용하기로 결정할 때만 연속 메모리를 할당한다. / 별도의 메모리 continguity관리 프로세스가 있다. )
• Ingens는 page fault handler에서 base page를 할당하고, base page 할당을 util bitvector에 표시한다.
• base page가 충분히 할당되었다고 계산될 때 (논문에서는 90%이상 할당되었을 때) page fault handler가 Promote-kth를 wake up 시켜 huge page promotion을 하게 한다.
• 사용 정도를 확인하기 때문에 memory bloating을 완화할 수 있다.
• Utilization-based demotion (performance)
  • 프로세스들은 free를 호출하여 base page를 반납한다.⇒ 이러한 huge page demotion은 성능을 저하시킨다.
  • 반납된 base page가 huge page에 포함되면 리눅스는 huge page를 즉시 demote한다.
  • Ingens는 사용률이 높은 huge page의 demotion은 지연시킨다.사용률이 threshold보다 떨어지면 huge page를 demote하고 그때 util bitvector에 0 인 page를 반납한다.
  • huge page내부의 base page를 반납하면 util bitvector에 해당 page에 대한 bit을 0으로 clear한다.

4.4 Proactive batched compaction (reduce fragmentation)

• 메모리에 연속적인 공간을 유지하기 위해 Ingens는 물리적 메모리의 fragmentation 상태를 모니터링 하고, 능동적으로 메모리 compact를 수행한다.
• Ingens는 FMFI를 threshold 이하로 유지시킨다.
• **FMFI: free memory fragmentation index - 0~1로 fragmentation 정도를 나타낸다.
• proactive compaction은 주기적인 스캔 이후에 Promote-kth 에서 발생한다. proactive compaction은 높은 CPU 사용률을 보이기 때문에 Ingens는 한번 compaction 수행시 최대 compact 할 수 있는 메모리 양을 100MB로 제한한다.
• Ingens는 compaction 과정에서 자주 접근되는 페이지는 이동시키지 않아 그로 인한 성능 저하를 줄인다.

4.5 Balance page sharing with performance

• Ingens는 application performance와 page sharing을 균형을 맞추기 위해 접근 빈도 정보를 이용한다.
• → huge page 내부의 base page sharing이 가능하도록 huge page의 demotion 여부를 결정한다.
• Ingens는 huge page가 자주 접근되는 경우에는 sharing을 거부하고, 그렇지 않은 경우에는 page sharing을 하기 위해 huge page를 demotion한다.
• page sharing을 위해 커널은 공유한 page를 read-only로 표시하고, 프로세스가 해당 page에 write하려는 경우에 sharing을 중단시키고, 프로세스에게 새로운 page를 할당한다. (copy-on-write 매커니즘과 유사)
• → write가 시도된 page 주변의 huge page의 사용률을 확인하여 높은 경우 page를 huge page로 promote한다.

4.6 Proportional promotion manages contiguity

• Ingens는 가상머신과 프로세스 간 fair memory contiguity를 모니터링하고 분배한다.**자주 접근되지 않는 page를 idle memory로 count하고, penalty를 부과한다.
• → idleness penalty가 있는 메모리를 비례적으로 공평하게 공유하는 기법 사용
• page당 공유 정도를 반영한 프로로세스별 메모리 promotion metric 공식 M** S = 프로세스의 huge page 공유 우선순위** (f +τ(1−f)) = 자주 접근되지 않는 huge page에 적용한 penalty factor→ fairness 보장
• ⇒ 즉, 프로세스의 우선순위 (M) 가 높고, huge page를 더 적게 가지고 있을 수록 커널은 해당 프로세스에 huge page promotion에 대한 우선권을 준다.
• ** H = 프로세스에 할당된 huge page가 지원하는 bytes
•  

4.7 Fair promotion

• Promote-kth 는 promotion metric을 사용하여 fair contiguity allocation을 한다.*** Mi = 프로세스 i 의 promotion metric⇒ 즉, 값이 작을수록 fair한 상태를 나타낸다.
• *** M = 모든 프로세스의 promotion metric 평균
•  

5. Implementation

• Ingens는 Linux 4.3.0에서 구현
• page utilization + access frequency tracking + Linux의 huge page table mapping와 memory compaction

5.1 Huge page promotion

• promote-kth : Linux의 khugepaged를 대체하여 huge page promotion scheduling을 수행한다.
• promote-kth의 priority list
  1. high : page fault handler의 promotion 요청을 담고 있는 global list
  base page들이 물리적 메모리에서 연속되지 않은 경우에 page fault handler가 huge page promotion 요청→ promotion 후에 물리적 메모리에 불연속적으로 할당되어 있던 base page들을 반납한다.
  1. normal : Promote-kth가 주기적으로 주소 공간을 스캔 할 때 채워지는 애플리케이션 별 list
  application의 virtual address space는 다른 virtual address 공간과 합쳐질 수도 있고 줄어들 수도 있다.
• → virtual address region들이 합쳐져 huge page를 만들 수 있다.
• → promote-kth는 물리적 메모리에 huge page 크기의 연속적 공간을 할당하고 해당하는 불연속적 메모리에서 데이터를 복사한다. 그리고 연속적인 물리적 메모리를 프로세스의 virtual address space와 mapping한다.
• promote-kth는 각 application의 promotion metric을 비교하고, 가장 unfair한 상태의 프로세스를 선택하여 huge page promotion 우선권을 부여한다.
• 16 MB의 page를 스캔하고 10초 동안 sleep 한다 (=Linux default setting)→ promoted huge page의 개수를 기록한다.⇒ 한 application이 promote-kth를 독점하는 것을 방지하고 fairness를 보장한다.
• → 만약 너무 적은 promotion huge page를 가지고 있다면 120초 동안 normal priority list에서 해당 application을 제외시킨다.
• 프로세스의 address space 전체를 스캔한다.

5.2 Access frequency tracking

• Linux 4.3.
  • access bit tracking framework 추가
  • 커널은 각 물리적 페이지에 idle flag를 추가하여 page가 사용되지 않은 상태로 남아 있을 때 hardware access bit을 사용한다.
  • scan-kth는 주기적인 application 메모리 스캔을 하는 동안 idle page를 찾아내기 위해 access bit tracking framework를 사용한다.
  • x86에서는 access bit을 clear하면 해당 page가 TLB invalid 되어 성능 저하가 발생한다.
• Ingens의 frequency-aware profiling and sampling
  • scan-kth는 page 접근 빈도를 보고 자주 접근되지 않으면 access bit을 clear한다.
  • 자주 접근되는 page는 20% 확률로 clear한다.

5.3 Limitations and future work

• Linux는 anonymous memory에 대해서만 transparent huge page를 지원한다.
• → huge page도 캐시할 수 있게 한다면 Ingens가 read-only page cache 지원을 개선하면서 huge page management를 할 수 있다.
• 하드웨어 기반의 huge page의 access bit tracking을 더 세밀하게 수행하면 write으로 인한 I/O 낭비가 감소하고, huge page를 공정하게 demote할 수 있다.
• NUMA considerations
  • Ingens는 노드이 global NUMA 공간보다 local NUMA 공간의 page를 선호한다.
  • global NUMA node간 memory가 공유되면 huge page는 메모리 controller간 메모리 요청의 불균형을 초래하고 접근 지역성과 성능 이점을 감소시킨다.→ 잘못된 page sharing (관련이 없는 데이터가 같은 페이지에 있는 현상)과 자주 접근되는 page (hot page effect)로 인한 현상
  • (즉, NUMA node간 huge page로 메모리 공유하는 것은 나쁘다)
  ⇒ 따라서 Linux의 huge page allocation 매커니즘은 NUMA node간 huge page의 균형을 맞추고, huge page 내부에 서로 관련이 없는 data가 같이 있거나 자주 접근될 가능성이 있는 경우 huge page를 분해할 수 있도록 해야 한다.scan-kth가 huge page가 자주 접근될지에 대한 여부를 페이지 접근 빈도를 통해 측정할 수 있게 하고, promote-kth로 huge page가 demote되어야 하는지 확인할 수 있다.
• ** Ingens로 확장할 수 있는 매커니즘

6. Evaluation

• 실험환경: two Intel Xeon E5-2640 v3 2.60GHz CPUs (Haswell) with 64 GB memory and two 256 MB SSDs / Linux 4.3 and Ubuntu 14.04 for both the guest and host system / use only 4KB and 2MB huge pages
• 사용률 기반의 promotion과 demotion 성능과 Ingens의 huge page를 사용하는 application간 fairness를 보장하는 능력 측정
• ⇒ Ingens는 접근 빈도가 비슷한 page를 merge하여 huge page로 promotion하여 memory saving과 huge page로 인한 성능 이점을 모두 제공한다.

6.1 Ingens overhead

• utilization-based huge page promotion 성능 (리눅스와 비교)→ Ingens는 리눅스보다 huge page promotion을 덜 수행하기 때문에 속도 저하 발생
• : 최악의 경우 3.0 %, 평균 0.7 % 속도 저하
• access bit tracking으로 인한 CPU 오버헤드는 스캔이 수행되는 page 개수에 따라 결정된다.

6.2 Utilization-based promotion

• 7개의 웹 페이지로 구성된 Cloudstone benchmark 중 홈페이지와 일부 2 MB 메모리를 사용하는 페이지만 수정했다. Linux + Ingens 환경에서 Cloudstone의 throughput과 latency를 비교했다.
• Ingens는 page fault handler에서 메모리 compaction을 동기적으로 수행하지 않기 때문에 평균 page fault latency를 감소시킨다.
• 하지만 메모리 단편화가 적은 경우, Ingens는 memory bloat를 줄이기 위해 huge page allocation을 덜하기 떄문에 page fault가 더 많이 발생하여 Linux에 비해 성능이 떨어진다.메모리 단편화가 0.5이하인 경우에는 Ingens도 Linux의 aggressive huge page allocation을 한다.
• → adaptive policy :

6.3 Memory bloating evaluation

• Ingens는 성능에 영향을 주지 않으면서 memory bloat를 최소화하고자 한다.
• 이 능력을 측정하기 위해 Redis key-value store를 벤치마크로 사용했다.

⇒ Ingens는 성능에 미치는 영향을 최소화하면서 memory bloat를 감소시켰다.

6.4 Fair huge page promotion

• Ingens는 application의 share priority 정보를 활용하여 huge page distribution을 보장한다. (우선순위에 비례하여 huge page 할당)
• Linux는 각 application address space를 선형적으로 스캔하여 동기적으로 huge page promotion을 수행한다.

⇒ Ingens는 fair한 huge page allocation을 지원한다.

6.5 Trade off of memory saving and performance

• page sharing에서 memory saving과 performance 간 trade off
• Ingens는 6.8 % memory saving + 2.5 % 성능 저하
• ** 성능저하의 원인: 전체 페이지 중 huge page의 비율이 높음 (접근 빈도 기반 huge page demotion 과 promotion)

7. Related work

• Operating system support
  • 연속성은 인지하면서 다양한 사이즈의 페이지를 지원하고, 단편화를 감소시키는 운영체제가 구현되었다.Ingens의 utilization-based promotion에 사용되는 util bitvector은 population map과 유사하지만 reservation-based allocation과 달리 huge page allocation을 promotion decision과 분리시켜 프로세스가 종료한 후에 contiguity를 공평하게 재분배한다.
  • → reservation-based allocation : 미리 연속된 범위의 페이지를 할당하고 promotion을 지연시킨다.
  • 재배치 가능성에 따라 페이지를 그룹화하여 단편화를 완화하고 contiguity을 promote하는 OS의 물리적 페이지 allocator의 placement policy가 제안되었다.
  • +libhugetlbfs와 같은 명시적인 huge page 요청을 위한 인터페이스가 제안되었다.
• Hardware support
  • page table walk를 빠르게 하거나 그 빈도를 줄이거나 miss 빈도를 줄여야 TLB miss 오버헤드를 줄일 수 있다.
  • → multi-page mapping 기법 : TLB 하나의 엔트리에 여러개의 페이지 mapping 할 수 있어 TLB reach를 증가시킨다.
  • GLUE는 연속적인 작은 page translation을 TLB 내부에서 하나의 huge page translation 으로 그룹화한다.

8. Conclusion

• Ingens는 운영체제와 하이퍼바이저의 transparent huge page 를 지원한다.
• huge page로 인한 성능 이점을 유지하면서 tail-latency를 줄이고, fairness를 유지하며 bloat를 최소화한다.

9. Ingens의 장점과 단점

1) 장점

사용빈도를 기반으로 적절한 huge page promotion & demotion >>

• huge page를 사용하여 TLB miss와 page fault latency를 줄여 성능을 높인다.
• huge page로 인한 memory bloat을 줄여 메모리를 절약한다.
• promotion metrics를 통해 프로세스별 huge page promotion 우선순위를 적용하여 프로세스 간 huge page fairness를 높인다.

2) 단점

• page의 접근 빈도와 프로세스 별 huge page promotion 우선순위 등을 계산해야 하기 때문에 aggressive한 Linux의 huge page 할당 방식보다 느릴 수 있다.
• Access bit과 Util bit tracking으로 인한 오버헤드가 발생한다.