HawkEye: Efficient Fine-grained OS Support for Huge Pages
위 논문을 읽고 정리한 내용입니다.
Notion에서 보기
Abstract
- 운영 체제는 주소 변환 오버헤드를 감소시키는데 효율적인 huge page 관리기법이 필요하다.
- recent work : Ingens
- https://www.notion.so/Coordinated-and-Efficient-Huge-Page-Management-with-Ingens-a04ce99fe56e42cbb4b12b8dba3ad6a0#f3998d04c03b48e3bee0b66283c3cdfe
- HawkEye/Linux : 새로운 huge page 관리 기법
- performance, page fault latency, memory bloat 관련 issue를 다룬다.
- primary idea of HawkEye algorithm:
- async page pre-zeroing
- de-duplication of zero-filled pages
- fine-grained page access tracking
- measurement of address translation overheads through hardware performance counters
1. Introduction
- large multi-level TLBs, page-walks caches, multiple page size 등을 지원하는 아티텍쳐들은 다양한 워크로드에 적합한 page size를 결정하는 섬세한 운영체제가 필요하다.
- 그러나 운영체제 기반의 huge page 관리 알고리즘은 적합하지 않아서 huge page로 인한 성능 이점이 잘 나타나지 않고 있다.address translation overhead, memory bloat, page fault latency, fairness vs
- overheads of the algorithms itself
- ** 운영체제 기반 huge page 관리 알고리즘의 trade-offs:
- 본 논문에서는 huge page 관련 issue와 current huge page 관리 접근법의 약점을 논의하고, 새로운 huge page 관리 알고리즘을 제안한다.
- representative state-of-the-art system
- Linux's transparent huge page (THP)
- khugepaged (background kernel thread)
- 연속적인 메모리가 available하면 page fault 발생시 huge page를 할당한다.
- 연속적인 메모리가 unavailable하면 base page를 huge page로 promotion한다. (필요시 memory compaction을 수행한다.)
- 단편화가 심한 경우, background promotion을 수행한다.
- huge page promotion을 수행하는 동안 khugepaged는 가장 먼저 온 프로세스부터 프로세스 내의 모든 huge page promotion을 한다. (FCFS 방식)
- 보안을 위해서 page는 synchronously 초기화된다
CPU는 메모리에 request를 할때 virtual address로 한다.
-
MMU의 page table 접근 속도를 향상시키기 위해 address translation 정보를 캐시한 TLB를 사용한다.
-
MMU가 page table을 참조하여 virtual address → physical address translation을 하여 memory에 접근한다.
- FreeBSD - multiple huge page sizes
- page fault handler에서 물리적 메모리의 연속적인 공간을 예약한다.
- huge page sized 영역의 모든 base page가 할당될 때까지 promotion을 지연시킨다.
- 예약된 연속적인 메모리 공간이 일부만 사용된다면 사용되지 않은 page들은 page allocator로 돌려보낸다.
- 이러한 방식으로 FreeBSD는 리눅스보다 메모리 contiguity를 효율적으로 관리한다.
- Linux's transparent huge page (THP)
- recent research paper
- Ingenshttps://www.notion.so/Coordinated-and-Efficient-Huge-Page-Management-with-Ingens-a04ce99fe56e42cbb4b12b8dba3ad6a0#3952cd84085648fd977b90f89620a185
- address translation overhead와 memory bloat의 balance를 고려한 adaptive 전략을 사용한다.
- 과도한 memory bloat를 방지하기 위해 utilization-threshold를 고려하여 huge page allocation 을 한다.
- synchronous page zeroing으로 인한 page fault latency를 줄이기 위해 asynchronous huge page allocation을 수행한다.
- **page zeroing : 삭제된 데이터 위에 0을 쓰는 것
- 프로세서간 fairness를 보장하기 위해 memory contiguity를 명시적으로 관리하고, share-based 정책을 도입하여 huge page를 할당한다.
- Ingens 논문 정리 자료:
- Ingenshttps://www.notion.so/Coordinated-and-Efficient-Huge-Page-Management-with-Ingens-a04ce99fe56e42cbb4b12b8dba3ad6a0#3952cd84085648fd977b90f89620a185
- HawkEye
- huge page 관리를 위한 자동화된 운영체제 레벨의 솔루션
- memory bloat, address translation overhead ↔ page fault latency balancing
- huge page로 인한 성능 이점을 극대화한 huge page 할당
- virtualized system에서 memory sharing 방식 개선
2. Motivation
2.1 Address Translation Overhead vs Memory Bloat
- Linux의 synchronous huge page allocation은 MMU (Memory management unit) overhead를 최소화하는데 초점을 맞추고 있다.
- → 프로세스가 할당받은 huge page의 일부만 사용한다면 memory bloat가 발생한다.
- FreeBSD는 huge page 크기의 공간의 모든 base page가 할당된 후 promotion을 수행한다. (huge page mapping을 지연시킨다.)
- → memory bloat는 줄일 수 있지만 성능 이점이 줄어들 수 있다.
- Ingens는 메모리 fragmentation이 적을 경우에는 aggressive huge page promotion을 수행한다. FMFI가 0.5보다 작은 경우에 리눅스처럼 가능한 경우 바로 huge page promotion을 하고, 큰 경우에는 base page의 일정 비율이 할당된 후에 promotion을 수행하는 conservative utilization-based 전략을 사용한다.** fragmentation 측정을 위해 FMFI (free memory fragmentation index)를 사용한다.
- 즉, 메모리의 fragmentation을 고려하여 memory bloat과 MMU overhead를 조절한다.
- 본 논문에서는 48 GB 메모리 시스템에서 실행되는 Redis key-value store로 간단한 실험을 하여 aggressive huge page allocation 중 발생하는 memory bloat 문제가 해결되지 않았음을 보여준다.
- 워크로드ii) 메모리 공간에 산재되어 있는 key들을 임의로 선정하여 80% 삭제한다.이때, 커널의 khugepaged 스레드는 page가 반납된 영역을 huge page로 promote한다.** resident-set-size (RSS) : 해당 프로세스에 할당되어 RAM에 들어 있는 메모리 양을 표시하는데 사용된다. swap-out된 메모리를 포함하지 않고, 해당 라이브러리의 페이지가 실제로 메모리에 있는 한 공유 라이브러리의 메모리와 모든 스택 및 힙 메모리를 포함한다.Ingens는 RSS가 32 GB가 될떄까지 aggressive huge page allocation을 하고, 넘어가면 conservative promotion을 한다.
- iii) 일정 시간 차를 두고, 45 GB in-memory data set에 key-value pair 17 KB를 삽입한다.
- ** madvise() : 커널에게 시작 주소와 주소 길이로 주소 범위를 알려주는 시스템 콜
- Redis가 madvise 시스템 콜로 운영체제에 page를 반납할 때, 해당하는 huge page mapping은 꺠지고, resident-set size(RSS)가 약 11 GB로 줄어든다.
- i) 11 million key-value pairs of size (10 B, 4 KB) 를 45 GB의 in-memory data set에 삽입한다.
- Linux는 28 GB의 bloat를 발생시키고, Ingens는 20 GB의 bloat를 발생시킨다.
- 그럼에도 불구하고 Ingens는 memory 사용량이 적은 경우에 memory bloat가 발생하는 현상을 해결하지 못하였다.
- → conservative promotion을 수정하여 Ingens의 문제를 해결하고자 한다.
- HawkEye는 memory bloat를 발생시키지 않으면서 aggressive promotion을 수행하도록 한다.
2.2 Page fault latency vs Number of page faults
- 운영체제는 page를 process address space로 mapping하기 전에 page zeroing을 해야한다. 그런데 huge page clearing은 매우 expensive하여 높은 page fault latency를 초래하게 된다.
- Ingens는 이 문제를 피하기 위해 page fault handler에서는 base page만 할당하고 khugepaged 비동기식 스레드에 promotion 작업을 넘긴다.⇒ spatial locality가 좋은 접근 패턴에서 page fault가 적게 발생하는 huge page의 이점이 무효화된다.
- ( = 큰 메모리 영역을 할당하고 초기화하는 프로세스는 spatial locality가 좋은 접근 패턴을 보이는데 base page만 할당한다면 page fault 발생 횟수가 증가하여 성능이 저하된다. )
- → page allocation latency 를 감소시킨다.
- the number of page fault vs page fault latency 실험을 위한 workload
- 10 GB buffer
- 각 base page 마다 one byte
- 10번 실행
- Linux의 THP는 THP없는 Linux보다 500배 이상 page fault 발생 횟수를 감소시켜 4배 이상의 성능 개선을 보이지만 평균 page fault latency보다 133배 느려진다.
- Ingens는 Linux 2 MB에 비해 상당히 큰 latency 감소를 보이지만 page fault 발생 횟수를 감소시키진 않는다.→ 결과적으로 해당 워크로드는 Ingens에서 page fault가 많이 발생하기 때문에 전체적으로 성능이 저하된다.
- ⇒ page fault가 발생했을 때 page zeroing을 하지 않으면 page fault latency와 page fault 발생 횟수를 모두 감소시킬 수 있다. (HawkEye의 rate-limited asynchronous page pre-zeroing)
- (base page 90%이상을 할당한 후부터 promotion을 수행하기 때문에)
2.3 Huge page allocation across multiple processes
- 운영체제는 메모리 fragmentation을 고려하며 프로세스들에게 huge page를 fair하게 할당해야 한다.
- Ingens는 fair한 할당을 위해 memory contiguity를 자원처럼 관리하고, 자주 접근되지 않는 page를 표시하는 idleness penalty factor를 사용하여 proportional huge page promotion metric를 계산한다.https://www.notion.so/Coordinated-and-Efficient-Huge-Page-Management-with-Ingens-a04ce99fe56e42cbb4b12b8dba3ad6a0#befe9d166d964b398be4b83f41eb0e1a
- → 프로세스의 우선순위가 높고, huge page를 더 적게 가지고 있을 수록 커널은 해당 프로세스에 huge page promotion에 대한 우선권을 준다.
- Ingens의 fairness 보장 정책의 약점 (scenario):TLB pressure가 높은 프로세스의 접근은 huge page 영역 내의 많은 base page로 분산되고, 다른 프로세스는 소수의 접근은 base page에 집중될 수 있다.
- 이러한 경우, TLB pressure가 높은 프로세스의 huge page promotion은 다른 프로세스에 비해 더 필요한 상황이지만 Ingens는 promotion metric으로만 우선권을 부여하기 때문에 두 프로세스를 동일하게 여긴다.
- 두개의 프로세스들이 비슷한 huge page 요구를 하지만 한 프로세스의 TLB pressure가 더 높은 경우를 가정한다.
- fairness 보장을 위해 모든 프로세스의 MMU 오버헤드를 균일하게 만드는 것이 필요하다.→ 전체적인 시스템 성능을 개선시킨다.
- → 위의 상황에서 각 프로세스가 30%, 10%의 MMU 오버헤드를 가지고 있다면 30% 의 MMU 오버헤드를 가진 프로세스가 10%에 도달할 때까지 huge page 할당 우선권을 주는 것이다.
- Ingens는 fragmentation이 적은 상황에서 huge page promotion을 수행한다. huge page가 자주 접근되지 않으면 해당 프로세스의 promotion metric을 낮춘다.
- → 만약 해당 프로세스가 huge page promotion이 필요한 다른 메모리 공간이 자주 접근된다면 MMU 오버헤드가 증가한다.
- Linux와 Ingens는 높은 VA 부터 낮은 VA로 순차적 스캔을 통해 huge page promotion을 수행한다.
- → 먼저 스캔되는 VA에 높인 hot 영역이 유리하기 때문에 unfair하다.
2.4 How to capture address translation overheads?
- 보통 working-set size (WSS)로 MMU 오버헤드를 측정한다.→ 오늘날 하드웨어에는 적합하지 않은 측정법이다.
- (WSS가 클수록 MMU 오버헤드가 크다.)
- 본 논문에서는 하드웨어 performance counter를 이용하여 TLB 오버헤드를 직접 측정한다.
- HawkEye-PMU :하드웨어 performance counter로 MMU 오버헤드 측정
- HawkEye-G : 메모리 접근 패턴으로 MMU 오버헤드 측정
- ↔ performance counter가 없는 하드웨어의 경우 HawkEye/Linux는 두가지 algorithm/implementation을 제시한다.
3. Design Implementation
- primary observations
- asynchronous page pre-zeroing → page fault latency 단축
- 할당된 huge page 내부에 zero-filled baseline page 식별, 중복 제거 → memory bloat 방지
- huge page 크기 영역의 fine-grained access tracking, access coverage (huge page 내의 baseline page가 몇 개나 접근되었는지) 기준 → promotion 결정
- fairness → MMU 오버헤드 기준으로 추정
3.1 Asynchronous page pre-zeroing
Async pre-zeroing
- 사용가능한 free page의 zeroing은 rate-limited background kernel thread에서 비동기식으로 수행되어야 한다.
- → high page fault latency 방지
- Linux 개발자들은 pre-zeroing이 전체적인 성능에 좋지 않을 것이라고 주장했다.
- async pre-zeroing thread는 cache를 지저분하게 만들어 주 워크로드를 방해할 것이다.
- double cache miss : 동일한 page에 zeroing을 위해 한번 접근하고, 프로세스에 의해 실제 접근을 또 한번 해야 한다.
- → 전체적인 성능 저하
- 이 문제는 memory write with non-temporal hints 하드웨어로 해결 가능하다.
- ** non temporal: 메모리 load/store 하는 중에 캐시를 우회하도록 하는 하드웨어 명령어 (필요없는 caching을 방지)
- pre-zeroing이 실제 워크로드에 성능 이점을 보이는지 정확하지 않다.
- pre-zeroing에 대한 과거의 논의들은 4 KB page를 고려한 것이다.
- pre-zeroing이 25%까지 page fault 오버헤드를 줄이지만 4 KB page에 대해서는 반드시 성능 개선을 보이지는 않는다.
- 그러나 huge page에 대해서는 page fault 오버헤드를 97% 감소시켜 엄청난 성능 향상을 보인다.
- ex) 가상머신의 부팅 시간을 14배 빠르게 한다.
- async pre-zeroing thread는 cache를 지저분하게 만들어 주 워크로드를 방해할 것이다.
- pre-zeroing은 가상화 시스템에 이점을 제공한다.
- guest's physical address (GPA) space에서 zero page의 수를 증가시킨다.
- content-based page-sharing
- page copy들을 각자의 content로 식별하는 것
- pages with identical contents들은 언제, 어디서, 어떻게 그 콘텐츠들이 생성되는지와 상관없이 공유될 수 있다.
- 각 page들의 content를 시스템의 모든 다른 page들의 content와 비교하는 것을 expensive 하다.→ page content의 full comparison을 통해 page가 완전히 identical하다고 확인하면 성공적인 match (기존에 있는 shared page와 match한다는 뜻)(→ match 실패시 차후에 발생할 match를 예상하여 page COW를 표시한다.)
- → 해당 page를 공유하기 위해 copy-on-write 기술을 사용한다. shared page에 write가 발생하면 fault가 발생하고, write을 수행한 프로세스에 대하여 private page를 제공한다.
- → 효율적인 page 식별을 위해 hashing을 사용한다. content를 요약한 hash value는 copy-on-write를 표시해 둔 페이지를 엔트리로 가지고 있는 hash table의 lookup key 로 사용된다. 만약 새로운 page의 hash value가 table의 엔트리와 일치하면 해당 page는 identical할 가능성이 높다. (실패 가능성도 존재한다)
- 장점:ii) sharing 가능한 정도가 높아진다.
- i) code를 수정하거나 이해할 필요가 없어진다.
- 단점→ write 오버헤드 증가
- ↔ unshared page는 COW 표시를 하지 않고, hint 엔트리로 태깅을 해둔다. hint page의 content는 re-hash한다. 만약 hash 값이 바뀌면 hint page는 수전되고, 이전의 hint도 제거된다. 만약 hash값이 그대로이면 full comparison을 수행하고, 해당 page의 공유가 가능하다고 여긴다.
- i) 스캔한 모든 page에 copy-on-write 표시를 해야 한다.
- content-based page-sharing
- → virtualization host에서 content-based page-sharing이 가능하게 한다.
- guest's physical address (GPA) space에서 zero page의 수를 증가시킨다.
- async pre-zeroing 를 구현하기 위해, HawkEye가 Linux buddy allocator에서 2개의 리스트를 이용하여 free page들을 관리한다.ii) non-zero : 프로세스가 반납한 page들은 일단 non-zero 리스트에 추가된다.** non-temporal : CPU의 캐시를 거치지 않고, write buffer 에 바로 데이터를 쓰는 명령 (moventq)→ pre-zeroing은 sequential 메모리 접근을 포함하기 때문에 non-temporal 명령을 사용하면 cache를 더럽히지 않고 기존의 caching 성능을 유지할 수 있다.
- → copy-on-write나 file system-backed memory region은 pre-zeroing이 불필요하기 때문에 이러한 메모리 영역의 경우에는 우선적으로 non-zero 리스트에서 우선적으로 할당한다. (즉, zeroing이 필요없는 경우에는 non-zero 리스트의 page 할당)
- ** rate-limited : 일정 시간당 작업할 수 있는 정도를 제한하는 것
- rate-limited thread 가 주기적으로 page를 non-zero 리스트에서 non-temporal write를 사용하여 zero-filling을 한 뒤, zero list로 보낸다.
- i) zero : 프로세스에 page 할당을 하기 위해 사용된다.
3.2 Managing bloat vs performance
- insight
- large-memory 워크로드에서 대부분의 할당은 zero-filled page 할당이다. (COW page, mmap 등을 통한 filesystem-backed page 등은 제외)
- scale-out 워크로드에서 huge page들은 주로 초기에 커널에 의해 zero-filled된 anonymous page를 사용한다.
- ** scale out : 장비를 추가하여 워크로드를 분담하여 성능을 높이는 병렬 컴퓨팅 구현
- 리눅스는 오직 anonymous memory로만 huge page를 지원한다.→ memory bloat 방지
- **anonymous memory : 특정 파일이나 디바이스와 관련 없는 메모리
- 본 논문의 접근법
- 첫번째 page fault 발생시 huge page를 할당한다.
- memory 사용량이 높은 경우에는 사용되지 않는 메모리를 복구시키기 위해 기존의 huge page를 스캔하여 그 중 zero-filled baseline page를 식별한다.
- huge page 내부에 zero-filled baseline page의 개수가 threshold를 넘었다면 해당 huge page를 baseline page로 쪼개고, 일반적인 COW page 관리 기법으로 zero-filled baseline page들의 중복을 제거한다.
- ** Copy On Write : page를 공유하다가 한 프로세스가 해당 page에 대해 write을 하면 page를 복사하여 write를 수행하게 하는 기법
- → 드물게 COW page fault가 많이 발생할 수도 있다.
- HawkEye는 memory bloat를 해결하기 위해 시스템 내에 할당된 메모리의 양에 워터마크를 사용한다. -high and low** bloat-recovery thread 는 할당된 메모리의 양이 low 아래로 떨어질 때까지 주기적으로 실행된다. 프로세스의 MMU 오버헤드를 기반으로 huge page 할당이 demotion을 위해 스캔되어야 하는 프로세스를 선택한다.→ 0이 아닌 byte를 처음으로 만날 때까지 baseline page가 zero-filled 인지 확인하기 위해 스캔한다. (실제로 스캔되어야 하는 byte 수가 아주 적다 - 실험에서는 4 KB page 당 평균 9.11 byte)⇒ bloat-recovery thread의 오버헤드는 할당된 메모리의 양이 아닌 bloat page의 개수와 비례한다.
- → 따라서 프로세스의 baseline page들을 스캔하기 위해 필요한 byte는 약 10 byte 정도 이지만 나머지 4096 byte의 bloat page를 발견할 수 있다.
- (MMU 오버헤드가 가장 작은 프로세스 = huge page가 가장 덜 필요한 프로세스가 선택된다)
- → 할당된 메모리의 양이 high를 초과하면 bloat-recovery thread가 활성화된다.
- bloat-recovery thread는 content-based page sharing을 위해 사용되는 de-duplication kernel thread와 비슷하다. (ksm - 리눅스 커널의 same page merging thread)→ Ingens는 이러한 문제를 해결하기 위해 자주 접근되는 huge page에 ksm을 이용하여 demotion을 수행했다⇒ 위 기술들은 사용되지 않는 zero-filled page를 식별하고, same-page merging 보다 빠르게 실행되어 bloat-recovery를 보완할 수 있다.
- → SmartMD는 접근 빈도와 반복 비율을 기반으로 page demotion을 수행했다.
- 그러나 ksm thread와 huge page management (khugepaged)가 상호 지원되지 않는다.
3.3 Fine-grained huge page promotion
- 효율적인 huge page promotion : 성능 극대화 + huge page promotion 횟수 최소화
- 현행 시스템은 virtual address를 내림차순으로 스캔하여 page promotion을 한다.
- → 낮은 VA space 에 hot page가 있는 프로세스에는 비효율적이다.
- 본 논문에서는 memory access 패턴을 기반으로 promotion decision을 한다.
- ⇒ HawkEye에서 사용할 metric = access-coverage
- access-coverage : 짧은 간격으로 huge page sized 영역에서 접근된 base page의 개수를 나타낸다.
- access-coverage는 다음과 같은 프로세스를 매 30초 마다 반복한다.**exponential moving average : 가장 최근의 데이터 포인트에 더 큰 가중치와 중요성을 부여하는 이동 평균 (MA) 유형이다.
- ii) page table access bit를 clear하고, 1초 후에 몇 개의 bit가 set되었는지 테스트한다. (1초 동안 접근된 page 개수 측정)
- i) 정기적으로 page table access bit을 샘플링하고, 샘플링 결과들의 access-coverage의 exponential moving average(EMA)를 유지한다.
- access-coverage는 해당 영역의 TLB에 필요한 base page 엔트리의 개수를 나타낸다.높은 access-coverage를 가진 영역은 TLB 경쟁이 많이 발생할 수 있기 때문에 huge page promotion의 이점이 크다.
- 그래서 access-coverage가 높은 영역에 huge page 할당한다.
- → huge page promotion으로 인한 benefit을 추정하는데 사용한다.
- HawkEye는 pre-process 자료 구조를 이용하여 access-coverage 기반의 promotion을 구현했다. = access_map (비슷한 access-coverage를 가진 huge page 영역을 담고 있는 bucket의 배열)
- x86의 2 MB huge page
- access-coverage 값의 범위: 0-512
- 논문의 프로토타입에서는 access_map에 10개의 bucket을 유지하였다.→ access-coverage 50-99 = bucket 1 ...
- → access-coverage 0-49 = bucket 0
- region 들은 매 sampling 주기마다 새롭게 계산되는 EMA-based access-coverage를 기반으로 재배열될 수 있다.
- region이 위로 이동하면 bucket의 head에 추가되고, 아래로 이동하면 tail에 추가된다.
- bucket내부에서는 page를 head부터 tail 순으로 promotion을 수행한다.
- 이러한 방식으로 최근에 접근된 region에 promotion 우선순위를 부여한다.
- HawkEye의 access_map은 FreeBSD의 population_map과 Ingens의 access_bitvector와 유사하다
- memory hotness의 index, 세분화된 huge page promotion = HawkEye
- → huge page의 메타데이터를 이용하여 page 사용률과 접근을 표시하는 자료구조
3.4 Huge page allocation across multiple processes
- access-coverage를 사용한 전략은 예상되는 MMU 오버헤드가 큰 프로세스가 포함된 영역의 promotion이 우선되게 한다.
- ~ TLB 사용량이 높을 것이라고 예상되는 process나 region을 먼저 huge page promotion을 수행시킨다.
- HawkEye는 모든 프로세스의 가장 높은 access-coverage index가 비어있지 않은 region 부터 promotion을 한다.example )HawkEye-G (= hardware performance counter)는 다음과 같은 순서로 promotion을 한다.MMU 오버헤드는 access-coverage와 접근 패턴의 다양한 특징에 의해 결정되는 것이다.
- 따라서 HawkEye-PMU는 일단 가장 먼저 가장 큰 MMU 오버헤드 추정치를 가진 프로세스를 선택하고, 선택한 프로세스의 VA영역을 내림차순으로 선택한다. 그리고 가장 큰 MMU 오버헤드가 유사한 프로세스 간에는 round-robin을 사용한다.
-
A1,B1,C1,C2,B2,C3,C4,B3,B4,A2,C5,A3
- access_map에 A, B, C 프로세스와 각 VA 영역이 있다고 하자
- 여러 개의 프로세스가 가장 높은 non-empty index를 가지고 있는 경우, round-robin 방식으로 프로세스간 fairness를 보장한다.
3.5 Limitations and discussion
HawkEye에서는 다루지 않은 huge page management와 관련된 issue들
1) Thresholds for identifying memory pressure
- HawkEye는 memory bloat를 처리하기 위해 정적으로 구성된 값인 2개의 워터마크 (high, low)로 메모리 사용량의 범위를 측정한다.
- 메모리 사용량이 지속적으로 변동하는 경우 이러한 정적인 threshold를 사용하는 것은 위험할 수 있다.
- 따라서 동적인 threshold를 적용하는 솔루션이 필요하다.
2) Huge page starvation
- HawkEye는 전체적인 성능을 최적화시키면서 MMU 오버헤드를 기반으로 huge page 할당을 하지만 하나의 프로세스에 huge page allocation를 계속해서 하는 것은 다른 프로세스들의 starvation 문제를 유발한다.
- → 프로세스간 unfair huge page share
- huge page 할당이 제한되어야 하는 경우 기존의 Linux의 cgroups와 같은 자원 제한/모니터링 툴과 결합시키는 것이 하나의 솔루션이 될 수 있다.
- **cgroup : control groups / 프로세스들의 자원 사용을 제한하고 격리시키는 리눅스 커널의 기능
3) Other algorithms
- 본 논문에서는 일부 managment algorithm을 다루지 않는다.
- promotion 오버헤드를 줄이기 위한 rate limiting khugepaged
- same-page merging을 통해 sharing을 보완하기 위해 낮은 사용량을 기반으로 하는 demotion
- page tabel access-bit tracking, compaction algorithm 오버헤드를 최소화하는 기법
4. Evaluation
- experimental paltform
- HawkEye is implemented in Linux kernel v4.3
- Intel Haswell-EP
- E5-2690 v3 서버
- CentOS v7.4
- 96 GB memeory
- 48 cores
- 2.3 GHz씩 파티션된 socket * 2 (NUMA의 영향을 피하기 위해 워크로드 한개당 1개의 socket)
- L1 TLB - 4 KB * 64 entries + 2 MB * 8 entries
- L2 TLB - 4 KB * 1024 entries + 2 MB * 1024 entries
- L1 cache - 768 KB, L2 cache - 3 MB, shared L3 cache - 30 MB
- 96 GB SSD_backed swap partition
- 다양한 워크로드 - ranging from HPC (고성능 컴퓨팅), graph algorithm, in-memory databses, genomics, machine learning
- ** in-memory computing : 어플리케이션의 클라우드화, 모바일화, 글로벌화로 인하여 발생하는 익스트림 트랜잭션의 고성능 처리를 지원하기 위한 기반 기술로 어플리케이션 운영을 위한 데이터를 하드디스크가 아닌 메인 메모리에 모두 올려두고 서비스 하는 것을 말한다.
- 평가 항목
- access-coverage를 기반으로 한 fine-grained promotion 전략으로 인한 performance, fairness 개선
- memoey bloat와 performance의 tradeoff
- page fault latency의 영향
- aysnc pre-zeroing thread로 인한 cache interference
- aysnc page pre-zeroing 으로 인한 memory 효율성의 영향
- 사용한 벤치마크
Performance advantages of fine-grained huge page promotion
- access-coverage 기반 promotion 전략의 효과를 측정하기 위해 알고리즘이 높은 address translation 오버헤드 → 낮은 address translation 오버헤드로 복구하는데 걸리는 시간을 측정한다.
- promotion이 없는 상황에서 계속해서 높은 address tranlsation 오버헤드가 있는 워크로드를 테스트한다.
- 기존의 huge page promotion은 virtual address의 오름차순으로 이루어지는 반면, HawkEye는 access-coverage를 기반으로 page promotion을 한다.→ HawkEye는 적절한 huge page 할당을 통해 높은 address translation 오버헤드로 부터 빠르게 회복한다. (Linux 보다 13%, Ingens보다 12% 성능 향상을 보인다.)→ virtual address space에 분포가 넓은 접근 패턴을 보이는 워크로드에서 HawkEye는 Linux, Ingens와 비슷한 성능을 보인다.
- → huge page promotion 당 절약된 평균 실행 시간을 측정한 결과에서도 HawkEye가 높은 성능 개선을 보인다. (리눅스보다 HawkEye-G는 6.7배 이상, HawkEye-PMU는 44배 이상 promotion으로 인해 절약되는 시간이 크다.)
Fairness advantages of fine-grained huge page promotion
- multiple application에서 performance와 fairness를 모두 측정하기 위해 identical applications, heterogenous application을 순차적으로 실험하였다. (각 프로세스들을 동시에 실행시킴)
1) Identical Workloads
- 비슷한 수준의 MMU 오버헤드를 가지는 각 application에게 fair하게 huge page 할당이 이루어지는지 분석하기 위해 identical application으로 실험을 한다.
- Linux, Ingens, HawkEye 각각에서 Graph500과 XSBench를 동시에 실행시켰을 때의 MMU 오버헤드와 huge page 할당을 보여주는 그래프 :
→ Linux가 한번에 하나의 프로세스에 huge page promotion을 수행하여 성능 불균형을 초래하는 반면, HawkEye는 모든 워크로드에서 공평한 huge page 할당을 한다.
→ Linux의 평균보다 HawkEye-PMU는 1.13~1.15배, HawkEye-G는 1.13~1.15배 정도 속도가 빨라진다.
→ Ingens는 huge page promotion을 부분적으로 수행하는데, 실험에서 적용한 워크로드에서는 성능 대선이 보이지 않는다. (리눅스보다 안좋은 성능을 보인다.)
⇒ page의 접근 빈도에 따라 huge page promotion 우선권을 부여하기 때문에 다른 기법에 비해 fair하고, MMU 오버헤드가 적다.
2) Heterogenous workloads
- heterogenous application을 비교하여 memory fragmentation과 pressure로 인한 성능을 분석한다.
- 워크로드를 TLB sensitive set, TLB insesitive set으로 그룹화하여 실험을 수행했다.실행 순서에 따른 huge page 정책의 영향을 살펴보기 위해 각 set은 두번씩 실행된다.⇒ after Redis : redis가 이미 메모리 영역을 할당 받아 실행되고 있는 상태이기 때문에 상대적으로 fragmented되어 있고, memory pressure도 높은 상태이다기 때문에 huge page 할당이 적게 이루어진다.
- ⇒ before Redis : 메모리 상태가 fragemented되어 있지 않고, memory pressure도 절하기 때문에 기존 application들이 huge page를 많이 할당 받을 수 있다.
- **TLB-sensitive : application의 성능이 TLB에 큰 영향을 받는다는 의미 (address translation overhead가 크다 / 큰 메모리 working set을 가지는 application)
- execute a lightly loaded Redis server with1KB-sized 40M keys servicing 10K requests per-second
- TLB sensitive 워크로드에서 4 KB page에 대한 속도 향상을 보여주는 그래프 :
- before Redis & after Redis
→ Linux의 경우, 실행 순서의 영향이 가시적이다.
— Before case: THP를 지원하는 Linux는 TLB sensitive 한 워크로드에서 huge page promotion을 수행하여 baseline page에 대한 성능 개선이 보인다.
— After case : 그에 반해 after Redis의 경우, TLB sensitive 한 워크로드에서 huge page promotion은 좋지 않은 성능을 보인다. (huge page 할당이 거의 없다)
→ Ingens의 경우, 실행 순서는 큰 영향을 받지 않지만 large memory 워크로드를 선호한다. 그리고 TLB sensitive 워크로드에서 최선의 성능을 보이지는 않는다.
→ HawkEye-PMU는 MMU 오버헤드를 기반으로 huge page promotion을 수행하고, HawkEye-G는 access-coverage 기반 MMU 오버헤드 추정을 기반으로 huge page promotion을 수행하여 4 KB page에 대하여 15-60% 성능 개선을 보인다.
Performance in virtualized systems
- KVM 하이퍼바이저 + Ubuntu 16.04 + fragemented system
- HawkEye가 host, guest, both 계층에서 사용되는 각 3가지 경우에서 실험을 한다.
- 실험 결과→ HawkEye는 가상 환경에서 Linux보다 18-90% 성능 개선을 보인다.
Bloat vs performance
- populate a Redis instance with 8M (10B key, 4KB value) key-value pairs
- → delete 60% randomly selected keys
- THP가 지원되지 않는 Linux-4 KB 의 경우, memory bloat가 발생하지 않지만 성능이 떨어진다.
- THP가 지원되는 Linux-2MB는 좋은 성능을 보이지만 memory bloat가 있다.
- Ingens는 memory bloat - performance의 tradeoff가 있다.
- (사용률 threshold가 높을수록 memory 가 효율적이고, 낮을수록 memory bloat를 허용하고 성능이 좋아진다.)
- HawkEye는 메모리 사용량이 낮은 경우에는 aggressive huge page allocation을 하다가 사용량에 따라 전략을 전환하기 때문에 시스템의 상태에 따라 MMU 오버헤드를 낮추어 성능을 향상시키고, memory 효율성을 높일 수 있다.
Fast page faults
- 운영체제의 page fault handler의 효율성에 따라 성능이 평가된다.KVM과 JVM의 spin-up time을 측정한다.
- ** spin-up time: The period of time taken by the drive to perform this process
- 2 MB value를 insert 할때 Redis의 throughput을 측정한다.
- HawkEye-4KB 의 async page pre-zeroing의 성능 이점은 크게 보이지 않고, 다른 page fault 오버헤드가 성능을 좌우한다.
- HawkEye-2MB 의 aysnc page pre-zeroing은 리눅스보다 Redis에서 1.26배, SparseHash에서 1.62배 성능 개선을 보인다.
- 가상머신의 spin-up time은 page fault에 의해서만 결정되기 때문에 huge page에 대한 async pre-zeroing으로 가상머신의 spin-up time을 크게 감소시킨다.
- 실험에 사용된 워크로드는 page fault가 많이 발생하기 때문에 Ingen의 사용량 기반 promotion은 성능 저하를 유발한다.
Async pre-zeroing enables memory sharing in virtualized environments
- 가상머신 내부의 async pre-zeroing은 가상 머신간 memory sharing을 가능하게 한다.
- ** same-page merging (KSM)
- 하이퍼바이저가 프로세스간, 가상 머신간 동일한 content를 가진 page를 공유할 수 있게 하는 커널의 기능
- 동일한 content를 가진 물리적 page들을 스캔하고, 해당 물리적 page에 mapping되는 virtual page를 식별하기 위해 스캔을 한다.
- → 하나의 page는 수정하지 않은 상태로 두고, 각 중복되는 page들이 같은 물리적 page를 가리키도록 다시 mapping 한다.
- = kernel shared memory, memory merging, memory deduplication :
- ** same-page merging (KSM)
- 가상 머신의 free memory는 가상머신의 pre-zeroing과 host의 same-page merging을 통해 host에 반납된다.
- HawkEye가 실행되는 가상머신에서 전체적인 시스템 성능 측정 결과:그러나 PageRank에서는 불필요한 same-page merging으로 인해 COW page fault 발생이 증가하여 약간 성능이 떨어진다.
- HawkEye-G는 Pedis와 MongoDB에서 높은 throughput과 상당한 tail latency 감소를 보인다.
Performance overheads of HawkEye
- non-fragmented system, huge page로 인한 이점이 없는 몇개의 워크로드로 HawkEye의 성능을 평가하였다.→ HawkEye의 access-bit tracking, asynchronous huge page promotion, memory deduplication의 오버헤드는 무시할만 하다.
- → HawkEye의 async pre-zeroing thread는 오버헤드가 발생한다.
- → 같은 시나리오에서 Linux와 Ingens의 성능과 유사한 성능을 보인다.
Overheads of async pre-zeroing
- memory와 cache interference로 인해 async pre-zeroing 오버헤드가 발생한다.
- → 이러한 오버헤드를 피하기 위해 non-temporal hint로 memory store를 한다.
- async pre-zeroing의 cache effect를 보여주는 그래프→ non-temporal hint 사용하면 async pre-zeroing으로 인한 오버헤드를 대폭 감소시킬 수 있다. (나머지 오버헤드는 추가적인 memory traffic)
Comparison between Hawk-PMU and HawkEye-G
- HawkEye-G가 TLB 경쟁에 대한 단순하고 근사한 추정을 기반으로 하지만 대부분의 경우 TLB sensitive 프로세스와 메모리 영역을 식별하는 데 상당히 정확하다.
- HawkEye-PMU는 일부 경우에 HawkEye-G 보다 좋은 성능을 보인다.
- 높은 access-coverage와 서로 다른 MMU 오버헤드를 보이는 네가지 워크로드를 TLB sensitive와 inseneitive set에서 실행시켰다
⇒ HawkEye-PMU는 HawkEye-G 보다 36% 좋은 성능을 보인다.
5. Related Work
Hardware Support
- TLB-miss 빈도를 줄이는 것과 TLB-miss 프로세싱을 빠르게 만드는 것이 목적이다.
- Large multi-level TLBs , multiple page size
- → TLB-miss를 최소화한다.
- TLB-miss path에서 memory lookup을 피하기 위해 page-walk-cache를 사용한다.
- POM-TLB는 single memory lookup을 사용하여 TLB miss를 처리하고, address translation을 가속하기 위해 data cache를 사용한다.
- **POM-TLB : 메모리의 일부로 아주 큰 translation lookaside buffer를 사용하여 address translation 오버헤드를 줄인다. radix-4 타입의 page table에 한번만 접근하여 translation이 가능하다. POM-TLB는 메모리 공간의 일부이기 때문에 entry들이 L2, L3에 캐시될 수 있다.
- Direct segments는 특별한 segmentation 하드웨어를 사용하여 완전히 TLB-miss processing 비용을 제거한다.
- 운영체제 수준에서의 memory fragmentation을 해결하기 위해 고안된 하드웨어 설계로 CoLT, Coalesced-Large-reach TLB가 등장했다.→ page-walk cache와 huge page로 확장되었다.
- → 불연속적인 메모리에서 huge page를 지원하는 기술이 제안되었다.
- → 운영체제가 제공하는 contiguous mapping을 기반으로 base page를 사용하여 TLB reach를 늘린다.
- HawkEye에게 하드웨어 최적화는 필수적인 것은 아니고 보완적인 요소이다.
Software Support
- FreeBSD의 huge page management는 superpage의 작업의 영향을 받았다.
- Carrefour-LP는 huge page의 ad-hoc 사용은 추가적인 remote memeory 접근과 node간 불균형으로 인해 NUMA 시스템에서는 성능 저하를 유발할 수 있다는 것을 보인다. 그리고 이를 해결하기 위해 hardware-profiling 기반의 기술을 제안한다.
- Gorman et al은 page의 이동성을 고려하여 클러스터링된 페이지의 fragmentation를 방지하는 기법을 제안했다.
- Illuminator은 Linux의 fragmentation 완화 기법의 결정적인 결함을 강조하고, 문제를 해결하는 기법을 제공했다.
- 물리적 메모리 단편화와 NUMA 시스템을 다루는 메커니즘이 중요하고 그 방법은 HawkEye를 견고하게 만드는데 적용될 수 있다.
- 컴파일러나 어플리케이션 hint는 운영체제가 특정 주소 공간의 huge page mapping의 우선순위를 정하는데 도움을 준다.
- huge page를 지원하기 위한 대안적인 방법은 lihugetlbs가 연구중이다.→ 사용자가 각 어플리케이션을 고려하고 미리 huge page를 할당해야 하기 때문에 불편하다.
- → 사용자가 huge page 할당을 제어하는 것
- Windows와 OS X는 huge page를 reservation 기반으로만 제공한다** THP 관련 이슈 : huge page를 사용할 수 있게 지원하는 것이 오히려 성능 저하를 유발한다.
- → THP 관련 이슈를 피할 수 있다.
6. Conclusions
- THP는 필수적이지만 복잡하다
- 성능과 시스템 안정성의 균형을 맞출 수 있는 자동화되고, 효율적이며 효과적인 알고리즘이 필요하다.
- 따라서 본 논문에서는 기존의 huge page management와 관련된 새로운 알고리즘으로 HawkEye를 제안한다.
7. 장점과 단점
1) 장점
- access frequency 뿐만 아니라 recency도 반영하여 promotion 결정을 하여 fairness를 보장한다.
- memory pressure를 고려하여 huge page 할당을 하여 memroy bloat와 performance간 균형을 유지한다.
- pre-zeroing을 하여 page fault latency를 감소시킨다.
2) 단점
- 매 30초마다 access-coverage를 계산하고 bucket의 배열을 갱신하는 오버헤드가 생긴다.
- memory pressure를 평가하기 위한 threshold가 고정되어 있기 때문에 이를 잘못 설정할 경우 memory pressure가 높은 경우 huge page를 base page로 쪼개거나 낮은 경우 huge page 할당을 계속하는 등의 선택을 적절하게 하지 못할 수도 있다.
- MMU 오버헤드가 낮은 프로세스는 huge page starvation 현상이 있을 수 있다.