A Comprehensive Analysis of Superpage Management Mechanisms and Policies : QuickSilver

A Comprehensive Analysis of Superpage Management Mechanisms and Policies : QuickSilver (Weixi Zhu, Alan L. Cox and Scott RixnerRice University)

A Comprehensive Analysis of Superpage Management Mechanisms and Policies | USENIX

Open Access Media USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and o

www.usenix.org

superpage (2MB pages)는 오늘날 많은 컴퓨터 시스템에서 large-memory 워크로드의 주소 변환 오버헤드를 줄이기 위해 사용된다. 본 논문에서는 superpage의 생애주기 동안의 일련의 이벤트와 이벤트에 대한 반응을 간단하게 설명한다. 또한 superpage와 설계 과정에서의 트레이드오프를 더 잘 이해할 수 있게 하는 프레임워크를 제안한다. 이 프레임워크에서 왜 새로운 설계가 런타임, 지연시간, 메모리 소비 측면에서 다른 성능을 보이는지 다루며, latency spike와 memory bloat의 근원을 설명하며 QuickSilver를 소개한다. QuickSilver는 새로운 superpage 관리 디자인으로 주소 변환 성능을 유지하면서도 latency spike와 memory bloat을 설명한다.

1. Introduction

컴퓨터 물리적 메모리 크기의 증가 + 큰 메모리 데이터를 필요로 하는 어플리케이션 등장
일부 어플리케이션은 물리적 메모리에 전체 데이터가 상주할 수 있길 바람
일부 어플리케이션은 내부 물리적 메모리 크기를 초과하는 데이터를 다뤄 중앙 집중에서 벗어난 프레임워크를 사용하거나 보조 저장장치 사용
두 경우 모두 메모리 사용량이 크고, virtual-to-physical address (VA to PA) translation 가상 메모리 주소와 물리 메모리 주소간 변환을 하는 비용이 커져 성능에 영향을 미침
superpage (huge page) 는 이러한 VA-PA 변환 비용을 줄이기 위해 사용된다.
- ex) x86-64 아키텍쳐의 경우에 superpage를 도입한 경우
- 페이지 테이블 레벨 감소
- TLB miss 감소 -> TLB miss로 인한 메모리 접근 횟수 감소
- TLB 엔트리의 효율적 사용

논문 개요

1. transparent하게 관리되는 superpage의 라이프사이클에서 발생하는 다섯가지 이벤트 정의
  - 물리적 superpage가 할당됨 (연속적인 2MB의 물리적 메모리 영역을 확보)
  - 물리적 superpage가 준비됨 (zeroed / 초기화)
  - 2MB의 가상 메모리 공간 -> 물리적 superpage 맵핑 생성
  - 맵핑 파괴
  - 물리적 메모리 할당 해제
2. 각 이벤트를 핸들링하기 위한 다양한 최신 접근 방법 분석
3. FreeBSE, Linux - THP, Ingens, HawkEye가 각 이벤트 트리거되었을 때의 각 성능 및 정책 등의 비교
4. transparent한 superpage 관리에 대한 새로운 발견 제시
  - 물리적 할당의 coupling, 준비, superpage 맵핑은 memory bloat를 발생시켜 superpage를 덜 할당하게 함
  - 최신 비동기적 out-of-place 프로모션(연속적인 일반 page들을 superpage로 승진시키는 것)을 지연시키는 것은 서버 워크로드에서 꼬리 지연시간 문제를 완화하는 반면 물리적 superpage 할당을 지연시키고superpage의 주소 변환 이점을 감소시킴
  - 물리적 superpage 할당은 in-place 프로모션을 가능하게 하고 비동기적, out-of-place 프로모션이 덜 필요하게 함
  - 물리적 superpage를 예약하고 superpage의 부분적 할당 해제를 지연을 가능한 많이 하는 것은 fragmentation(단편화)를 최소화하여 superpage의 사용과 그로 인한 성능 이점을 증가시키는데 도움을 줌
  - bulk zeroing (대량으로 한번에 초기화)는 현대 프로세서의 zeroing 방식보다 효율적
5. QuickSilver 소개
  - 새로운 transparent superpage 관리 시스템
  - FreeBSD의 reservation-based 물리적 메모리 할당자 기반
  - aggressive한 superpage 할당의 이점을 높이면서도 memory bloat과 단편화 문제를 완화함
  - 단편화가 심한 메모리 상에서도 좋은 성능 유지 가능
  - 단편화가 증가해도 다른 시스템에 비해 꼬리 지연시간이 적음
  - Ingens 만큼 memory bloat을 완화함

2. Transparent Superpage Management

이번 장에서는 각 이벤트 들이 언제 트리거되어야 하는지, 또 어떻게 이 이벤트들을 핸들링해야 하는지 등에 대한 가능한 옵션들 간의 트레이드 오프에 대해 설명함

2.1 Physical Superpage Allocation

물리적 superpage 할당에 필요한 조건

물리적 메모리 할당자에게 사용 가능하고 연속적인 2MB 영역이 있어야 함
단편화가 심할 경우 연속적인 물리적 메모리 영역이 있을 수 없기 때문에 할당 불가

물리적 superpage 할당 방식

메모리 매니저가 할당 정책과 메모리 마이그레이션 등을 이용해서 지속적으로 사용 가능한 연속적 2MB 공간을 확보하려고 함
사용 가능한 물리적 superpage가 있으면, 이전에 접근되었던 가상 메모리 영역에 할당하면서 이전에 할당된 모든 4KB 페이지들은 새로운 물리적 superpage로 마이그레이션
페이지 부재 발생시 동기적으로 트리거
- 이미 free한 물리적 superpage가 존재하면 동기적 할당이 유리
백그라운드에서 비동기적으로 할당 수행
- 운영체제가 마이그레이션 또는 어떤 프로세스가 종료되어 free한 공간이 생길 때까지 기다려 free superpage 생성하려고 함
- 가상 메모리에 4KB 페이지로 이미 할당이 된 이후에도 물리적 superpage로 비동기적 할당 가능

2.2 Physical Superpage Preparation

물리적 superpage가 할당된 뒤, 맵핑되기 전에 초기화하는 것

물리적 superpage preparation 발생 시기

페이지 부재가 발생한 4KB 페이지는 그 즉시 준비
한번에 또는 점진적으로 준비 가능
- 점진적 준비는 페이지 부재 지연시간을 감소시키고, 절대 접근될리 없는 불필요한 4KB의 준비 최소화
- 점진적 준비를 구성 페이지로 4KB 맵핑을 사용하게 되는데 이는 superpage 성능 이점을 감소시킴
- 한번에 준비는 가상 메모리 영역에서 추후 발생할 수 있는 페이지 부재를 방지하고 superpage 맵핑의 즉각적인 생성 허용

물리적 superpage Preparation 방식

superpage의 모든 구성 페이지들은 아래 세가지 방식으로 반드시 준비되어 있어야 함
1. Zeroing : 가상 메모리 영역이 익명 (anonymous) 이라면 해당 페이지의 내용을 파일로 백업한 뒤, zeroing
2. File Reading : 가상 메모리 영역이 memory-mapped 파일 이라면, 데이터는 반드시 백업 파일에서 읽어져야 함
3. Copying : 가상 메모리 영역이 현재 4KM 페이지에 맵핑되어 있다면, 페이지에 저장된 내용들을 물리적 superpage에 복사
구성 페이지 중 일부 또는 전체가 기존에 이미 맵핑된 4KB 페이지일 수 있음

2.3 Superpage Mapping Creation

물리적 superpage가 완전히 준비된 후, 가상 메모리 영역과 맵핑되어야 함 (VA-PA 주소 변환 정보 생성)
운영체제는 superpage의 구성 4KB 페이지의 접근 및 수정 여부 추적 불가

맵핑을 위한 조건

물리적 메모리가 여전히 4KB 맵핑으로 접근될 수 있어야 함
이후, 운영체제가 해당 4KB 페이지 각각에 대한 수정 및 접근 추적 능력을 상실
-> superpage의 구성 페이지 일부가 dirty인 경우 추후 불필요한 IO를 방지하기 위해 superpage 맵핑 생성을 지연시키기도 함
물리적 superpage 준비가 비동기적이라면 superpage 맵핑도 비동기적
일부 아키텍처에서는 이전에 만들어진 4KB 맵핑을 우선적으로 파괴

맵핑 생성 시기

페이지 부재가 발생시
메모리 영역에 대한 초기 부재 발생시
superpage가 준비된 이후, 부재 발생시

2.4 Superpage Mapping Destruction

맵핑 파괴 조건

언제든 파괴될 수 있음
가상 superpage의 일부분이 free되거나 보호 정책이 변경된 경우
- superpage의 개별 페이지 접근 및 수정 여부 추적이 불가능해서 superpage에 첫번째 수정이 발생한 경우 운영체제는 바로 이 superpage를 파괴하는 문제 발생
- 문제 해결을 위해 읽기 전용 superpage 맵핑을 만들고, 쓰기 접근으로 인해 발생하는 페이지 부재를 따로 사용
- 또는 일정 메모리 사용량을 넘은 경우에만 superpage 맵핑을 파괴하는 방식 사용
맵핑이 파괴된 이후, free되지 않고 남아 있는 4KB 페이지들에 대한 맵핑을 반드시 다시 만들어 주어야 함

2.5 Physical Superpage Deallocation

물리적 superpage 할당 해제 시기

어플리케이션이 가상 superpage 일부 또는 전체를 free할 때
어플리케이션이 종료되었을 때
운영체제가 메모리 reclaim해야 할 때

물리적 superpage 할당 해제 과정

할당 해제 전, superpage 맵핑 파괴
할당 해제
전체 2MB 메모리가 물리적 메모리 할당자에게 반환
또는 물리적 superpage가 4KB 페이지로 쪼개짐
- 이런 경우, 운영체제는 페이지 일부를 물리적 할당자에 반납
- 일부 반납은 단편화를 증가시켜 물리적 superpage 할당 가능성을 낮아짐

물리적 superpage 할당 해제 조건

구성 페이지 일부 또는 전체가 반납되기 전에 모든 구성 페이지들은 free 된 것이 아니라 준비 상태에 있어야 하고, 예약되어 있어야 함
예약 Preservation 발생 방법
- 사용 중인 페이지는 할당자에게 반납되지 않고 유지하도록 함
- 사용 중인 페이지는 다른 물리적 페이지로 복사되어 전체 superpage가 반납될 수 있게 함
- 사용 중인 페이지를 반납하기 전에 보조 저장 장치에 쓰기 시킴

3. State-of-art Designs

각 아티텍쳐에서의 최신 디자인과 최신 연구 프로토타입에 대한 소개

3.1 FreeBSD

모든 종류의 메모리 (memory-mapped filew, executables, ... ) 에서 transparet superpage 지원
reservation-based 메모리 할당자가 물리적 superpage 할당자 대신 preparation 수행

superpage allocate/reserve

2MB 영역에서 페이지 부재가 발생하면 superpage 할당 시도
물리적으로도 연속된 2MB 메모리가 있으면 2MB 크기를 넘는 memory-mapped 파일에 superpage 할당
anonymous 메모리는 그 크기와 상관없이 항상 superpage를 사용할 수 있음

memeory-mapped file : 가상 메모리에 있는 파일 내용을 저장한 파일(메모리 맵 파일)을 이용해서 파일과 메모리간 맵핑 정보를 통해 여러 프로세스를 포함한 어플리케이션이 메모리에 직접 읽고 쓰는 방식으로 파일을 수정할 수 있음

superpage preparation

anonymouse 페이지에 superage 가 할당되면, 페이지 부재가 발생한 4KB 페이지만 준비되고, 구성 페이지를 추적하기 위해 예약된 엔트리가 생성됨
이후에 2MB 영역에 발생하는 페이지 부재는 페이지 할당을 생략하고 물리적 superpage에 추가적인 4KB를 더 preparation 함
superpage의 모든 구성 페이지가 준비되면 preparation 완료
file-backed 메모리의 경우는 위와 같으나 IO 오버헤드를 최소화하기 위해 64KB 일괄로 준비

superpage mapping creation

페이지 부재가 발생하면 동기적으로 맵핑 생성
모든 구성 페이지들의 특성 (보호 정책, 수정 여부 등)이 동일할 때에만 맵핑 생성

superpage mapping destruction

구성 페이지 일부의 특성이 변하면 맵핑 파괴
수정이 발생되기 전에 선점적으로 맵핑을 파괴하기도 함
-> 전체 superpage 대신 일부 4KB 페이지만 dirty 된 것으로 표시되게 함
마지막 구성 페이지까지 dirty 즉, 구성 페이지 전부 dirty 페이지가 되면 다시 dirty superpage 맵핑을 생성

superpage deallocation

가능한 메모리 단편화를 최소화할 수 있게 하여 free 물리적 superpage의 이용 가능성을 높임
메모리 사용량이 기준점을 넘은 경우, 부분적으로 준비된 superpage를 찾아 쪼갬
-> 2MB 물리적 메모리 영역 내에 사용되지 않은 메모리가 다른 데에 사용될 수 있게 함

3.2 Linux (THP)

anonymous memory만 superpage 사용 가능

superpage allocate/reserve

2MB 가상 메모리 영역에 첫번째 페이지 부재가 발생하면 물리적 superpage 할당 시도 = first-touch 정책
할당 실패 하고, 단편화 제거가 가능한 경우, 페이지 마이그레이션을 통해 즉시 메모리 컴팩션 수행하여 free 물리적 superpage 확보
-> 페이지 부재 지연시간 증가 , 단편화가 심한 경우 마이그레이션도 실패할 수 있음

superpage preparation

물리적 superpage가 할당되면 한번에 전체 페이지 zeroing (preparation)
-> 초기 페이지 부재 지연시간 증가, 평균 지연시간 감소

superpage mapping creation

준비 직후, 맵핑 생성

superpage mapping destruction

superpage의 일부 또는 전체가 언맵되거나 특성이 바뀐 경우, destruction

superpage deallocation

일부 또는 전체가 free되면 할당 해제
해제된 메모리는 즉시 reclaim

khugepaged

비동기적으로 페이지 테이블을 스캔하는 커널 데몬
최소 1개 이상의 dirty 4KB페이지가 포함된 정렬된 2MB 익명의 가상 메모리 영역을 발견하면, 물리적 superpage 할당 시도
free된 물리적 superpage가 이미 있으면, 해당 가상 메모리 영역을 얻음
없다면 메모히 컴팩션을 호출하여 페이지 마이그레이션을 통해 superpage 요청
khugepaged 의 superpage events
1. 물리적 superpage 준비 전, 2MB 가상 메모리 영역에 접근을 막아 해당 영역에 대한 페이지 부재 방지하고, 이미 존재하는 4KB 맵핑을 파괴
  -> TLB shootdown발생, CPU 캐시 오염
  -> 기본적으로 매 10초마다 8개의 superpage 할당
2. 물리적 superpage의 모든 구성 페이지들을 한번에 preparation
3. 이전에 맵핑된 페이지의 내용은 복제해 두고 기존의 페이지는 zeroed
4. superpage 맵핑을 생성
어플리케이션이 가상 메모리에 맵핑되지 않은 superpage의 일부 메모리를 해제
-> superpage 맵핑 파괴와 물리적 메모리 할당 해제 발생
-> 남아 있는 사용중인 메모라는 4KB 페이지로 맵핑
memory bloat가 심하게 발생

3.3 Ingens and HawkEye

first-touch 정책으로 인한 페이지 부재 latency spike와 khugepaged로 인한 memory bloat을 완화하기 위한 프로토타입
first-touch 정책 대신 페이지 부재 발생시에만 하나의 4KB 페이지 할당, 준비, 맵핑이 가능하게 함
khugepaged는 Linux, Ingen, HawkEye 모두 순서, threshold, superpage 생성 비율 등을 다르게 줌

Ingens

superpage 내부의 90% 이상의 구성 페이지가 사용 중이라면 superpage 생성하도록 threshold 늘려 memory bloat 완화
페이지 부재가 발생한 2MB 영역의 리스트를 가지고, 해당 리스트가 비어있지 않다면 superpage 맵핑 생성 유지
비동기적 superpage 생성은 공정성 문제 유발 (일부 프로세스에 지연시간 길어짐)
- superpage를 적게 가지고 있는 프로세스에 우선권을 줌, 사용되지 않는 메모리는 aggressive한 비율로 컴팩션 수행

HawkEye

khugepaged와 threshold 동일 (2MB 영역에 4KB 페이지가 하나 이상 사용중이면 superpage 생성)
메모리 사용량이 늘어나면 superpage를 스캔하여 초기 상태인 4KB 페이지를 copy-on-write하여 하나의 zero-filled 페이지를 reclaim 되도록 함
2MB-aligned 영역의 후보 리스트 있음
- 각 엔트리의 메모리 활용률, 프로세스 거주 사이즈, 샘플링된 접근 빈도, TLB 오버헤드에 따라 가중치를 줌
- TLB 오버헤드가 가장 커, 가중치가 가장 큰 것을 superpage 맵핑 생성 (=fine-grained superpage management)
마이그레이션 기반 superpage 맵핑 생성 외에 CPU 자원을 더 소비함
실행 중인 프로세스의 개입을 피하기 위해 리눅스 기존의 promotion 속도를 사용

4. Analysis of Existing Designs

Platforms	Intel E3-1245 v6-based 서버 4 cores 32GB DDR4 2400 ECC RAM 256GB NVMe SSD Linux v 4.3 FreeBSD v 11.2 Swapping 비허용
Benchmarks	GUPS: 랜덤 액세스 수행 Graphchi-PR: 전처리된 트위터-2010 데이터셋에서 페이지랭크 3 이터레이션 계산 BlockSVM : kdd2010-bride 데이터셋에 분류 모델 훈련시킴 ANN : 전처리된 2GB 해시 테이블에 랜던하게 가장 가까운 이웃 질문 XSBench : Monte Carlo 뉴런 전송 알고리즘의 병렬 계산 커널 PARSEC, Gcc, mcf, DSjeng, XZ, SPEC CPU2017 : 큰 메모리 사용
Workloads	Cold Redis workload : 4KB 객체의 16GB 빈 레디스 인스턴스 Warm Redis wordkload : 4KB 객체의 5:5 = set:get 상태인 거의 찬 레디스 인스턴스

Observations 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의 5가지 이벤트를 묶어두는 것은 메모리 낭비을 유발하고, superpage 맵핑이 적어지게 한다. 또한, 다양한 superpage 크기를 사용하는 것은 좋지 않다.

리눅스이 first-touch 정책은 superpage의 물리적 할당, 준비, 맵핑 생성을 함께 묶어둠
first-touch 정책의 장점:
- 즉각적인 주소 변환 이점 제공
- 페이지 테이블 스캔 시간 단축
- TLB 효율 증가
- 많이 사용되는 superpage의 페이지 부재 횟수 감소
- => 충분한 연속적인 free 메모리가 있는 경우 최선의 맵핑 정책
first-touch 정책의 단점:
- memory bloat
- 사용률이 낮은 superpage 준비하며 시간 낭비
- 리눅스는 페이지 부재 발생시 힙을 넘어서 맵핑을 만들 수 없어서 가상 메모리가 증가할 때 superpage 맵핑을 생성할 기회 잃음
  <-> khugepages, FreeBSD (promotion-based 정책) : 힙이 커짐에 따라 superpage 맵핑 생성 가능
- 더 큰 익명 또는 백업 파일 superpage로 확장 불가

첫번째 페이지 부재 발생시, aggressive하게 할당을 하는것이 효율적.

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

비동기적, out-of-place 프로모션은 latency spike를 완화하지만 물리적 superpage 할당을 지연시킨다.

promotion 기반 정책은 4KB 맵핑 사용 후 나중에 superpage 맵핑으로 교체 가능
-> superpage 맵핑 생성 결정에 도움, 다양한 크기의 superpage로 확장 가능
out-of-place promotion
- 물리적 superpage를 미리 할당할 필요 없음
- 페이지 부재 발생시 4KB 페이지 할당
- 운영체제가 superpage 맵핑을 생성하기로 결정하면 반드시 물리적 superpage 할당하고, 맵핑된 4KB 페이지를 마이그레이트 하고, 남은 페이지들을 zeroing 함
- 이때, 물리적 superpage 할당 전에 생성되었던 4KB 맵핑은 더 이상 유효하지 않음
- 운영체제는 페이지 테이블을 스캔하여 2MB 영역을 찾아 백그라운드에서 해당 영역에 대한 프로모션을 수행하기 때문에 물리적 superpage 할당과 맵핑을 지연시킴
리눅스, 인젠, 호크아이 모두 비동기적, out-of-place 프로모션을 사용해서 페이지 마이그레이션 비용을 줄임
- 리눅스의 khugepaged는 힙이 커질때 superpage 맵핑을 보충
  -> 지속적으로 천천히 superpage가 많아지지만 memory bloat가 쉽게 발생
- 리눅스는 메모리 단편화로 인해 superpage 할당에 실패하면 메모리 컴팩션 수행
  -> 진행 중인 페이지 부재를 막고, 지연시간 늘어남
- 인젠과 호크아이는 first-touch 정책을 제한하고, 서버 워크로드에서 지연 시간 발생을 피할 수 있도록 khugepaged의 기능을 향상시켜 사용
  -> superpage 할당을 크리티컬 패쓰에서 수행하지 않아 지연 시간 발생을 줄임
FreeBSD는 in-place promotion 수행
- out-of-place 보다 낮은 성능
- 가장 보수적인 in-place promotion 정책은 superpage 맵핍을 빠르게 생성

Observations 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을 사용하는 물리적 superpage 할당을 허용하고, 비동기적, out-of-place 프로모션의 필요성을 낮춘다.

in-place 프로모션
- 페이지 마이그레이션이 필요 없음
- 첫번째 페이지 부재 발생 만으로 물리적 superpage를 생성
- 페이지 할당 없이 연속적인 4KB 페이지를 준비 및 맵핑
- 즉, 물리적 superpage의 할당은 즉각적으로 이루어지지만 맵핑 생성은 지연됨
- 4KB 페이지 할당을 우회하기 위해 할당된 모든 물리적 superpage를 추적하는 북키핑 시스템을 필요로 함
FreeBSD
- in-place 프로모션 정책
- reservation 기반
- 즉시 물리적 superpage 할당은 하지만
- superpage 맵핑 생성은 보수적으로 수행
  -> superpage로 인한 주소 변환 이점 희생
- 물리적 superpage를 익명 메모리에 대해 aggressive하게 할당
- 익명 메모리에 페이지 부재 발생 시, 급진적으로 물리적 superpage를 할당하고 힙이 커지길 예상함
  -> khugepaged의 필요성 줄임

FreeBSD의 reservation 기반 할당 시스템은 익명 메모리에 대해 공격적인 할당을 하여 더 많은 superpage를 사용하게 함. 또한 다양한 사이즈의 superpage를 지원하고, 메모리 bloat를 방지함.

Observation 4: Reservations and delaying partial deallocation of physical superpages fight fragmentation.

물리적 superpage의 부분적 할당 해제를 지연시키는 것과 예약하는 것은 단편화 정도와 대조된다.

장시간 실행되는 서버 워크로드에서 아주 일부의 4KB 페이지들이 superpage 맵핑으로 인한 이점이 적으면서도 물리적 superpage를 소비, 단편화 많이 발생시킴
기존 시스템에서 메모리 단편화를 다루는 방법
- 리눅스 : superpage 할당 실패 즉시 메모리 컴팩션 -> 탐욕적 방식으로 superpage 사용, 페이지 부재 차단 위험
  단편화 상태에서 superpage를 탐욕적으로 사용하면 스루풋이 약간 더 좋지만 높은 꼬리 지연시간 발생
- FreeBSD는 free한 물리적 superpage reclaim 가능성을 높이기 위해 물리적 superpage의 부분적 할당 해제를 지연시킴
  superpage의 일부 구성 페이지가 빨리 해제되면 버디 큐의 낮은 순서로 들어가게 되어 빠르게 다른 목적으로 재할당이
  즉, 부분적 할당해제는 오직 메모리 사용량이 많은 경우 할당 해제로 단편화를 줄일 수 있는 경우에만 수행
- Ingens은 페이지 부재 블락킹을 피하기 위해 백그라운드에서 메모리 단편화 제거를 수행
  -> 참조되지 않는 메모리는 우선 마이그레이트 하여 실행 중인 어플리케이션에 미치는 영향을 최소화
  -> 리눅스와 비교하여 더 적은 지연시간 발생
  <-> 마이그레이션은 프로세서 및 메모리 자원을 많이 소비함 (자원 효율 bad)

superpage의 부분적 할당해제를 지연시키는 것은 단편화를 효과적으로 제한하게 함.

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

오늘날 컴퓨터에서는 bulk zeroing은 반복적으로 4KB zeroing을 하는 것보다 더 효율적이다.

오늘날 컴퓨터은 멀티프로세스 환경에서 비동기 페이지 제로는 오히려 성능을 저하시킴, 2MB 페이지를 한번에, 빠르게 제로 가능

5. Design and Implementation

QuickSilver

향상된 transparent superpage management system
in-place promotions
based on FreeBSD : reservation-based superpage management

5.1 Design

Aggressive Physical Superpage Allocation

FreeBSD의 reservation 할당 시스템 기반
superpage가 사용할 수도 있는 가상 메모리 영역에 첫번재 접근이 시도되면 물리적 superpage 할당
할당은 동기적으로 수행하여 페이지 마이그레이션 방지
단점
- preparation와 superpage 맵핑을 지연시켜 성능 저하
  <-> reservation 의 문제가 아니라 preparation, 맵핑 정책의 문제
- 사용률이 낮은 물리적 superpage를 reservation에 가지고 있는 것은 차후의 superpage 할당에 방해가 됨
  <-> 사용 정도에 따른 할당해제 정책으로 해결

Hybrid Physical Superpage Preparation

기존의 reservation 시스템은 점진적으로 준비 (ex zeroing)을 하는데 이는 초기 페이지 부재 지연시간을 최소화하지만 주소 변환 이점을 줄임
Quicksilver는 threshold t 설정
- t 만큼의 4KB 페이지가 준비되면 superpage의 남은 부분은 한번에 준비
- 즉각적인 준비와 맵핑을 하지 않아서 memory bloat 줄임

Relaxed Superpage Maping Creation

전체 물리적 superpage가 준비되면 그 즉시 익명 메모리에 superpage 맵핑을 생성하는 것은 약간 단점
QuickSilver는 구성 페이지가 접근되거나 수정이 발생하면 superpage 맵핑을 생성하지 않도록 변경되어 superpage가 일단 완전히 준비가 되면 항상 맵핑을 생성하도록 함 (=리눅스, 인젠, 호크아이)
file-backed 시스템에서는 write-protection 매커니즘을 유지하여 불필요한 디스크 입출력을 줄임
-> 서로 다른 액세스 비트를 가질 수 있게 하는 것은 더 많은 file-backed superpage 맵핑을 만들게 함

On-demand Superpage Mapping Destruction

superpage 맵핑 파괴하는 경우
- superpage의 일부 또는 전체가 free 된 경우
- superpage의 일부 또는 전체의 protection bit가 바뀐 경우
- 물리적 superpager가 메모리 reclaim으로 인해 할당 해제된 경우
QuickSilver도 위와 같은 정책 유지

Preemptive Physical Superpage Deallocation

superpage 부분적 할당 해제를 방지하여 단편화를 예방하지만 동기적 물리적 superpage 할당에는 좋지 않음
QuickSilver는 free 물리적 superpage의 타겟 넘버를 정하고 유지
사용률이 적은 reservation은 선점적으로 할당 해제
-> 부분적으로 준비를 한 물리적 superpage는 아직 superpage로 맵핑되지 않았기 때문에 할당 해제는 memory bloat을 감소시키고, 메모리 연속성을 회복시킴 (defragment)
즉, 사용류리 적고, 덜 접근되는 superpage는 preemptive deallocation 시킴
장점
- 적은 양의 페이지가 마이그레이트 됨
- 선점적인 마이그레이션이 백그라운드에서 발생해서 크리티컬 패쓰에 영향 X
- 실행 중인 프로세스에 최소한의 영향

5.2 Implemetation

Hybrid Preparation

물리적 superpage 준비는 threshold t 만큼의 4KB 페이지가 준비될때까지는 점진적으로 진행되다가 t를 넘으면 한번에 수행
** 준비 = zeroing
threshold를 기준으로 하는 동기적, 비동기적 준비
1. Sync-t
  - 페이지 폴트 핸들러에 의해 가능한 큰 사이즈로 zeroing
  - 페이지 폴트 핸들러는 제로잉이 완료된 직후에 superpage 맵핑 생성 가능
2. Async-t
  - 주기적으로 부분적으로만 물리적 할당이 있는 reservation 리스트를 스캔
  - t에 도달할 떄까지 가장 활발한 reservation부터 zeroing 시작
  - 순서대로 수행하지 않고 할당 정도에 따라 zeroing 순서가 결정되어 공평성 문제 발생
  - 4KB 페이지가 개별적으로 제로잉 하여 제로잉 성능은 떨어지지만 락 경쟁은 줄임
  - zeroing은 프로세스의 가상 주소 공간과 별개로 비동기적으로 수행돼서 모든 준비가 완료된 뒤 첫번째 페이지 폴트가 발생하기 전까지 맵핑이 생성되지 않음

Relaxed Mapping Creation

익명의 메모리에 대해서 superpage 맵핑 생성은 relax 상태
-> dirty, access bit 확인하는 것 무시하기 위해
Sync-t가 벌크로 제로잉을 완료한 직후에 superpage 맵핑을 생성할 수 있게 함
file-backed 메모리에 대해 superpage 맵핑은 해당하는 물리적 superpage 에 첫번재 페이지 부재 발생 시 생성됨
QuickSilver는 액세스 비트 확인을 relaxing한(무시) 후, superpage 맵핑 생성

Preemptive Deallocation

QuickSilver는 사용률이 적은 물리적 superpage를 선점적으로 할당 해제하여 메모리 reclaim을 하는 청소 데몬 사용
- free 물리적 superpage의 개수가 타넷 넘버를 유지하도록 함
- 주기적으로 reservation 리스트를 스캔하고 사용되지 않는 시간 검사하여 사용량 적은 메모리 할당 해제

6. Methodology

Fragmentation

단편화 정도 : Frag-0/50/100 (숫자가 클수록 단편화 심함)
first-touch 정책을 사용하는 유저 스페이스 툴에 적용
1. 메모리 사용량이 많아질 때까지 superpage 단편화
2. superpage의 타겟 넘버를 다시 시작하고 단편화
물리적 할당과 부분적 할당 해제를 강제하여 superpage 단편화 유발

Library Differences

FreeBSD는 내장된 라이브버리 컴파일러로 실행 파일과 라이브버리를 동적으로 링킹
리눅스는 GNU 라이브러리 컴파일러 사용
모든 시스템에 정확히 같은 바이너리를 실행시켜 가능한 라이브러리 차이로 인한 영향 제거

System Tunning

CPU 경쟁이 적을 때 , 리눅스의 khugepaged를 더 공격적으로 개조하면 성능이 좋아짐
반면, CPU가 바쁠때, khugepaged까지 공격적으로 하면 성능이 저하됨
그래서 리눅스의 기존 시스템을 그대로 둠
FreeBSD11.2은 최상의 Redis 성능을 내지 못함
- 1Gbps NICs에 적합한 네트워크 소켓 버퍼 사이즈를 사용하기 때문
  -> 40 Gbps로 변경
- 라이브러리 컴파일러가 ERMS 최적화를 하지 않아서
  -> 12.0에서 라이브러리 컴파일러 가져옴
- 페이지 부재를 저장하는 MADV_FREE를 하고 다시 프로모션을 하지 않기 때문
  -> 새로운 패치 적용
Ingens은 90%-사용률에 도달하면 superpage로 프로모션 (기본)
-> 0% ~ 90% 로 변형 줌
HawkEye는 1.6MB/s 속도로 프로모션
-> 1GB/s까지 가능하게, threshold 1 일 때 100% CPU

7. Evaluation

** QuickSilver = Sync-1/64, Async-64/256

7.1 Non-fragmented (Frag-0) Performance

Sync-1 vs. Linux

Sync-1은 리눅스와 동일한 준비 및 맵핑 정책 사용
단편화가 없을 경우, 성능 유사
힙이 커지면 Sync-1이 공격적으로 superpage 할당하여 리눅스보다 성능 좋음 (canneal, gcc)
Sync-1이 file-backed superpage를 만들어 리눅스보다 성능 좋음 (ANN, Graphchi-PR)

Promotion Speed

단편화가 거의 없는 경우 성능 비교
- FreeBSD > Ingens, HawkEye
- out-of-place 프로모션은 그 속도가 느림을 증명
Sync-64는 대부분 Async-64보다 성능 좋음 (Async-64는 방해될 수 있는 백그라운드에서 페이지 제로잉을 해서)
Sync-64와 1은 덜 공격적인 준비와 맵핑 정책을 사용해서 첫번째 접근시 즉각적으로 맵핑을 만들어내는 결과가 유사 (..64 = .. 1)

7.2 Performance Under Fragmentation

Frag-50/100 상태, Redis Cold 워크로드에서 리눅스는 superpage를 사용하는 것이 더 꼬리 지연시간이 길어짐
FreeBSD는 메모리 defragement를 활발하게 하지 않아서 지연시간이 늘어나지 않음
Ingens, HawkEye는 페이지 부재 - superpage 할당 분리시키고, 백그라운드에서 메모리 컴팩션을 수행해서 지연 시간 늘어나지 않음
QuickSilver는 백그라운드 defragmentation은 페이지폴트 지연시간이 증가하는 것을 방지하고, unfragmented 성능 회복에 성공했기 때문에 논서버, 서버 워크로드에서 모두 균일하게 성능을 냄

Graphchi-PR

모든 어플리케이션에서 Sync-t와 Async-t 시스템은 전부 리눅스와 비슷하거나 좋은 성능을 냄
Frag-100에서 Async-64는 1.68 속도 향상, 물리적 superpage 개수 많음 (Ingens 보다 좋은 성능)
defragement에 사용되는 데몬으로 활발하게 defrag.
in-place 프로모션으로 속도 향상
Sync-64sms 2.11 속도 향상, superpage 개수는 async와 유사
Sync는 벌크 제로잉을 통해 superpage 생성 지연 없음

7.3 Memory Bloat

모든 시스템은 리눅스-4KB보다 memory bloat가 1% 미만으로 적음 (오래 실행되는 서버는 memory bloat 발생할 수도)
어플리케이션이 메모리를 자주 할당 및 해제하면 공격적인 superpage preparation 정책은 선점적으로 superpage를 준비하여 메모리가 부족해지고 그로 인한 주소 변환 이점이 적어짐
Redis 워크로드
- 리눅스 메모리 bloat 가장 큼
- Sync-1 리눅스와 같은 정책을 사용했어도 적은 메모리 소비
  -> 즉, khugepageda가 memory bloat의 주범! (부분적으로 할당 해제된 superpage가 스캔될 때 khugepaged가 superpage 생성하도록 재할당하여 메모리 free 및 defragmentation 고려하지 않음)
리눅스 이외의 다른 시스템들은 모두 메모리 사용량을 제한
- HawkEye, FreeBSD, Async-256은 가장 적은 메모리 사용 / 메모리 bloat 40-60%
- HawkEye는 TLB 오버헤드가 적을 때 superpage 할당하지 않음
- FreeBSD는 전체 사용되는 superpage만을 프로모션
- Async-256은 기준이 높은 프로모션 threshold 사용

Sync-1 s. Sync-64

메모리 bloat 측면에서 공격적인 준비 정책은 superpage를 과하게 생성할 수 있음
Sync-1은 시스템 준비 시간의 13.9%를 사용, 장시간 실행되는 서버에서는 너무 많은 superpage를 할당해서 전력이 낭비되고 메모리 연속성이 안좋아짐
Sync-64는 1의 경우를 방지하여 성능 저하가 덜함 -> 장시간 실행되는 서버에서 더 선호됨

8. Related Work

Direct segments

large memory 어플리케이션을 위한 기존의 페이지 기반 주소 변환을 돕기 위해 제안됨
주소 변환 비용을 감소시킴
거의 시스템 메모리 전체를 할당하는 시스템 제한
궁극적으로 운영체제가 물리적 메모리를 할당 및 사용의 유연성 제한

Automatic TLB entry coalescing (합치기)

TLB reach 늘리기 위해 제안된 기법
페이지 워크는 동일한 캐시 라인에서 여러 개의 4KB 맵핑을 찾아서 로드하는데 이때 맵핑들이 연속적인 페이지이고 동일한 접근 권한을 갖는다면 하나의 TLB 엔트리로 합침
하드웨어에서 자동으로 수행
운영체제도 물리적으로 연속된 메모리를 수행하도록 해야 함
AMD Ryzen 프로세서가 사용

superpage 사용

운영체제는 superpage를 지원하여 관리자가 수동으로 superpage 사용을 제어하게 함 (Linux)
huge page 개수를 정적으로 설정한 huge page pool은 반드시 어플리케이션 실행 전 관리자에 의해 할당되어야 함
persistant huge page는 메모리에 고정되고 mmap 시스템콜을 호출하기 위해 특정 플래그를 사용해야 함
윈도우와 OS X에서 지원하는 superpage는 리눅스의 persistent huge page와 유사

수동 제어를 하지 않기 위한 프로토티입 및 시스템

FreeBSD, Linux, HawkEye, Ingens
superpage의 투명한 관리를 위해 OS 많이 개발되고 효율적 핸들링을 위한 개선 등장
- 리눅스 superpage 관리 개선 연구 : 메모리 단편화 감소시키고, 사용량 적은 페이지 추적하는 매커니즘으로 조심스러운 물리적 superpage 할당
- 메모리 단편화 줄이고, 물리적 메모리 연속성을 증가시키는 방향으로 연구
- 마이그레이션 최소화
리눅스의 lumpy reclaim - 연속성 증가시키도록 개발됨 : inactive한 4KB 페이지를 찾아서 2MB superpage relcaim을 하고 모든 dirty 4KB 페이지를 2MB 블럭에 스왑

9. Conclusions

superpage 관리 매커니즘과 정책에 대해 분석
superpage의 라이프사이클의 5가지 이벤트와 관련된 프레임워크, 이벤트에 정책을 적용한 결과와 비교
프레임워크 분석을 통해 발견한 QuickSilver 설계에 모티브가 된 5가지 관찰 결과
QuickSilver는 공격적인 superpage 할당의 이점 + memory bloat 완화 + 단편화 문제 완화
QuickSilver - Sync-1, Sync-64는 단편화 상황에서 기존 시스템들과 비슷하거나 성능이 좋음
Sync-64는 사용률이 적은 superpage 생성을 공격적으로 하지 않기 때문에 장시간실행되는 서버에서 더 좋음

References

'논문 리뷰' 카테고리의 다른 글

HawkEye: Efficient Fine-grained OS Support for Huge Pages (0)	2021.04.06
Redundant Memory Mappings for Fast Access to Large Memories (0)	2021.04.06
Coordinated and Efficient Huge Page Management with Ingens (0)	2021.04.06
A Comprehensive Analysis of Superpage Management Mechanisms and Policies (0)	2021.01.26
SFS : Random Write Considered Harmful in Solid State Drives (0)	2021.01.11

seungyoon's

A Comprehensive Analysis of Superpage Management Mechanisms and Policies : QuickSilver