새로운 메모리 계층과 운영체제의 역할

목차

• 계층 메모리 시스템의 등장
• 첫번째 문제: 페이지 교체 알고리즘
• 두번째 문제: 공간 효율성

계층 메모리 시스템의 등장

DRAM 의 한계

DRAM 의 직접도는 꾸준히 향상되고 있지만 그 속도는 점점 줄어들고 있다. 인텔에 따르면 초기에는 3년마다 4배씩 성장했고 (Phase 1), 그 후 20여년 동안 2년에 2배씩 성장했고 (Phase 2), 최근 10년 동안에는 4년에 2배씩 성장하는데 그치고 있다고 한다 (Phase 3). DRAM 의 성장이 둔화하는 것과는 다르게, 데이터 처리량 즉 메모리 요구량은 급격히 증가하고있다. 오래전 글자로 소비되던 컨텐츠는 사진을 넘어 이제 동영상으로 소비되고 있고, 대규모 언어 모델과 같은 인공지능은 엄청난 양의 데이터를 학습하고있다. 메모리 요구량와 DRAM 의 성장의 차이가 커지면서 DRAM 을 대체할 메모리 디바이스가 중요해졌다.

둔화된 DRAM 성장 속도 (출처: Intel)

대안 메모리 연구

이러한 DRAM 의 한계를 극복하기 위해, Persistent Memory (PM), Non-volatile Memory (NVM), 혹은 Storage Class Memory (SCM) 라고 불리는 메모리/스토리지 디바이스 연구가 활발하다. 대표적으로, 상변이를 활용한 Phase Change RAM(PCRAM), 강유전체를 활용한 Ferroelectric RAM, 전자 스핀 방향을 활용한 Spin-Transfer Torque RAM 등이 있다. 인텔은 PCRAM 을 기반으로한 최대 512GB 크기의 Intel Optane Persistent Memory 를 상용화했다.

새로운 메모리 반도체 기술 (출처: SK Hynix)

새로운 소재의 메모리 연구 뿐만 아니라 여러 노드의 DRAM 으로 메모리 풀을 만들어서 커다란 메모리를 만들려는 시도도 있다. 이런 방식을 Remote Memory 혹은 Disaggregated Memory 라고 부른다. 예전에는 RDMA NIC 을 이용해 원격 노드 DRAM 의 데이터를 로컬 DRAM 으로 복사해서 데이터의 접근하는 방식이 많이 연구 되었다. 최근에는 CPU 에서 바로 원격 메모리에 접근하면서 캐시 일관성까지 제공하는 Compute Express Link (CXL) 이 메모리 풀을 구현하기 위한 수단으로 각광받고 있다.

CXL 을 이용한 메모리 풀 (출처: CXL)

새로운 메모리 계층

이러한 대안 연구가 활발하지만, 아직 새로운 메모리 디바이스 혹은 원격 메모리 접근방법이 기존 로컬 DRAM 을 접근하는것 만큼 좋은 성능을 내지 못하고있다. 그래서 새로운 대안이 DRAM 을 완전히 대체하기보다 DRAM 이 대안 메모리의 캐시처럼 동작하도록 계층화해서 사용하는것이 현실적이다.

메모리 계층 (출처: semiengineering.com)

메모리 계층은 CPU 에 가까울수록 높은 성능(높은 대역폭, 낮은 지연속도)을 보이지만 용량이 작고 비싸며, CPU 에 멀어질수록 성능은 낮지만 용량이 크고 가격이 저렴하다. 그래서 메모리 계층은 성능 최적화를 위해 최대한 높은 계층에서 데이터를 접근할 수 있도록 관리된다. 캐시(L1, L2, ⋯, LLC)와 DRAM 사이의 데이터 이동은 하드웨어에 의해 관리되고 (Intel CAT 처럼 소프트웨어에서 캐시를 컨트롤 할 수 있는 방법을 제공하지만 관리 주체는 하드웨어다) DRAM 부터 그 아래 계층간 데이터 이동은 소프트웨어에 의해 관리된다. 새로운 메모리 계층(SCM)도 마찬가지로 성능 최적화를 위해 관리되어야한다. SCM 은 DRAM 아래 위치하기 때문에, 운영체제 연구자들은 새로운 메모리 계층의 최적화를 위한 여러가지 계층 메모리 시스템(Tiered Memory System)을 제안하고있다.

첫번째 문제: 페이지 교체 알고리즘

메모리 계층 성능 최적화의 목표는 간단하다. 가능한 많은 데이터 접근이 상위 계층에서 일어나게 하면 된다. 가능하다면, 다음 접근될 데이터를 미리 상위 계층에 가져다 놓고 상위 계층에 공간이 부족하면 상위 계층에 존재하는 데이터 중 가장 먼 미래에 접근될 데이터를 하위 계층으로 내리면 된다. 하지만 미래를 정확히 내다보는 것은 불가능하기 때문에 미래를 예측해야 하는데, 미래를 예측하는 가장 합당한 방법은 과거 데이터 접근 패턴을 활용하는 것이다. 널리 받아들여지는 통념은 과거의 핫데이터는 미래에도 핫데이터일 가능성이 높고 과거 콜드데이터는 앞으로도 콜드할 가능성이 높다는 것이다. 따라서 계층 메모리 시스템은 핫/콜드 페이지 구분 정책(hot and cold page classification policy)이 필요하다. 따라서 계층 메모리 시스템은 핫/콜드 페이지 구분 정책(hot and cold page classification policy) 즉 페이지 교체 알고리즘(page replacement algorithm)이 필요하다.

이상과 현실 (출처: Wires at el. OSDI’14)

최신성과 빈도

어떤 데이터가 핫한지는 명확한 정의가 없다. 다만 hot 한 정도(hotness)를 측정하기 위해 사용되는 척도가 크게 두가지가 있고 그 두가지 중 하나 혹은 둘을 잘 조합해서 데이터의 hotness 를 측정한다. 그 두가지는 빈도(frequency)와 최신성(recency)이다. 빈도는 지금까지 얼마나 많이 접근 되었는지를 나타낸다. 빈도로 핫/콜드 페이지를 구분하는 가장 간단한 정책은 Least Frequently Used (LFU) 다. LFU 는 빈도가 곧 핫한 정도이다. 즉 빈도가 높은 페이지가 핫하고 빈도가 낮은 페이지는 콜드하다. 최신성을 기반으로 한 정책으로는 Least Recently Used (LRU) 가 있다. LRU 에서는 최신성이 곧 핫한 정도이며, 마지막 접근 시점이 현재와 가까울수록 핫하고 멀어질수록 콜드하다. 지금까지 제안된 계층 메모리 시스템에서는 조금 더 복잡한 알고리즘으로 핫/콜드 페이지를 구분하지만 결국 휴리스틱에 기반한 최신성과 빈도의 조합이다.

계층 메모리 시스템에서 사용하는 페이지 알고리즘이 사용하는 척도 (출처: Lee at el. SOSP’23)

페이지 접근 내역

계층 메모리 시스템 이전에 이러한 페이지 알고리즘 혹은 케시 알고리즘에 대한 많은 연구가 있었다. 하지만 이런 알고리즘을 계층 메모리 시스템에 적용하는 것은 쉽지 않다. 그 이유는 운영체제가 모든 데이터 접근 내역을 알 수 없기 때문이다. 기존 캐시 알고리즘 연구는 데이터 접근 내역이 주어졌을 때 더 좋은 성능을 보여주는 알고리즘을 제안한다. 하지만 운영체제에서 알 수 있는 데이터 접근 내역은 매우 제한적이다.

계층 메모리 시스템 이전 운영체제에서 데이터 접근 내역을 확인하는 방법은 두가지였다. 첫번째는 Page Table Entry (PTE) 의 접근 비트(accessed bit)를 확인하는 방법이다. 이 비트는 CPU 가 페이지에 접근하기 위해 페이지 테이블 워크를 할 때 1로 세팅된다. 운영체제는 주기적으로 PTE 의 접근 비트를 모니터링하면서 접근 여부를 확인하고 이 비트를 0 으로 세팅한다. 이 방법은 몇가지 단점이 있다. 첫번째, 운영체제가 주기적으로 PTE 를 확인해야하는데 메모리가 커질수록 모든 페이지의 PTE 를 한번 모니터링 하는데 오랜 시간이 소요된다. 두번째는 페이지 테이블 워크를 해야만 접근이 기록된다는 점이다. 자주 접근되는 페이지일수록 TLB 에서 바로 주소변환이 이뤄질텐데 이런 경우에는 PTE 접근 비트가 켜지지 않는다. 세번째는 Huge Page (2MB = 512×4KB)를 사용하면 2MB 당 하나의 접근 비트를 갖게되어 접근 기록의 해상도가 매우 낮아지게 된다는 점이다.

운영체제가 페이지 접근을 확인하는 두번째 방법은 의도적으로 불필요한 Page Fault 를 발생시켜서 페이지에 접근할때 운영체제가 데이터 접근 기록을 남기는 방법이다. 운영체제는 접근여부를 확인할 페이지를 샘플링해서 일부러 해당 페이지의 PTE Reserved Bits (Rsvd.) 중 하나 혹은 Protection Bit (2 U/S)를 세팅한다. 그러면 CPU 가 페이지 워크를 할 때 Page Fault 를 발생시켜서 운영체제가 이 접근에 대해 처리하도록 Page Fault Handler 를 호출하게 되고 여기서 운영체제는 페이지 접근을 기록한다. 이 방법은 불필요한 Page Fault 를 발생시키기 때문에 어플리케이션 성능을 악화시킬 수 있다. 샘플링을 많이 할수록 페이지 접근 여부를 정확히 알 수 있지만 그만큼 어플리케이션 성능을 악화시킨다.

PTE 구조 (출처: Intel Software Developer Manual)

최근 제안된 계층 메모리 시스템 HeMem(Raybuck at el. SOSP’21)에서는 이런 문제를 해결하고자 최신 Intel CPU 에서 제공하는 Processor Event-Based Sampling (PEBS)을 활용한 페이지 접근 내역 수집방법을 제안한다. PEBS 는 CPU 에서 원하는 이벤트가 발생 했을 때 샘플링하여 그 내용을 특정 메모리 영역에 기록해준다. 예를들어 LLC miss 에 대해 알고싶다면 해당 이벤트를 샘플링해서 어떤 주소를 접근하다가 LLC miss 가 발생했는지 미리 정해둔 메모리 영역에 기록한다. 운영체제는 주기적으로 이 메모리 영역에 기록된 샘플링된 하드웨어 이벤트와 그 내용을 확인할 수 있다. 이 방법은 앞서 설명한 두 방법(PTE 접근 비트 모니터링, 의도적 Page Fault)의 문제점을 해결한다. 모든 PTE 를 확인하지 않고도 접근한 페이지 목록을 얻을 수 있고, TLB 에서 주소변환이 되더라도 접근 기록이 남게되며, 접근한 데이터의 주소값을 알 수 있기 때문에 huge page 로 매핑됐다고 하더라도 4KB 단위로 접근 여부를 세분화할 수 있다. 또한 Page fault 가 발생하지 않고 운영체제가 주기적으로 지정된 메모리 영역을 조회하기 때문에 어플리케이션 성능에 영향을 거의 주지 않는다.

PEBS 를 통해 접근 기록을 얻는 방법은 훨씬 좋은 성능을 보이지만 여전히 남아있는 숙제가 있다. 설령 모든 접근 기록을 얻을 수 있다해도, 기존 페이지 교체 알고리즘 연구에서 제안하는 알고리즘의 시간/공간 복잡도를 운영체제가 구현하여 제공하는 것이 효율적일지 알 수 없다. 운영체제는 어떤 어플리케이션이 실행될지 가정할 수 없는데 어플리케이션마다 데이터에 접근하는 패턴은 매우 상이하다. 어떤 어플리케이션은 특정 메모리 영역을 집중적으로 접근하지만 어떤 어플리케이션은 데이터를 처음부터 끝까지 반복해서 접근하는 패턴을 보이기도 한다. 새로운 페이지 알고리즘을 제안한다고 해도 어떤 어플리케이션 셋에서는 좀 더 효율적일 수 있지만 그 반대 케이스도 분명히 존재하기 때문에 페이지 교체 알고리즘 간 성능비교가 쉽지도 않다. 그래서인지 리눅스의 경우 DRAM-Storage 간 페이지 교체 알고리즘이 매우 간단하다. 결국 대용량 메모리를 사용하는 어플리케이션은 그동안 운영체제의 페이지 교체 알고리즘에 의존하기보다 자체적으로 페이지 교체 알고리즘을 구현하는 식(e.g., 데이터베이스의 버퍼 캐시)으로 메모리를 사용하는것이 효율적이다.

두번째 문제: 공간 효율성

메모리 사용량이 늘어나면서 huge page 를 사용하는것이 대중화되고있다. huge page 는 512개의 4KB page 를 하나의 페이지로 묶어서 TLB coverage 를 높이고, 페이지 워크를 줄여서 어플리케이션의 데이터 접근 성능을 향상시킨다. 하지만 huge page 는 메모리 부풀림(memory bloat)을 관리하지 않으면 오히려 성능을 악화시킬 수 있다. 메모리 부풀림 현상은 내부 단편화(internal fragmentation)에 의해 발생하는데, huge page 영역 중 극히 일부만 사용하는데도 huge page 로 할당해버리면 금방 메모리가 부족해지는 현상을 야기한다. 많은 연구들이 이 문제를 해결하기 위한 방법들을 제안한다.

Huge page 로 인한 비효율적인 공간 활용

SCM 이 등장하기 전에는 DRAM 아래 바로 스토리지였기 때문에 메모리 부풀림 현상은 메모리 스왑을 발생시켰지만 계층 메모리 시스템에서는 cold huge page 를 SCM 으로 마이그레이션하게된다. 하지만 여전히 공간 효율성의 문제가 남아있다. 위 그림을 보면 왼쪽 상태에서 DRAM 의 두번째 huge page 가 SCM 의 세번째 huge page 보다 cold 하기 때문에 migration 을 통해 가운데 상태처럼 DRAM 을 hot huge page 로 채울 수 있다. 하지만 마이그레이션 된 huge page 는 내부 단편화로 인해 DRAM 의 일부 영역을 비효율적인 공간으로 (cold 한 상태로) 남겨두게 된다. 좀 더 DRAM 공간을 효율적으로 사용하려면 DRAM 과 SCM 의 내부 단편화된 huge 들을 base page (4KB) 로 쪼개서 오른쪽 상태처럼 핫한 base page 를 DRAM 으로 이동해서 채워야한다.

개념은 간단하지만 huge page 를 쪼개서 공간 활용도를 높일 때 고려해야할 것이 있다. 첫번째, base page 로 쪼개면 TLB coverage 가 낮아지고 페이지 워크로 인한 메모리 접근 시간이 늘어난다. 이 비용을 들여서라도 SCM 대신 DRAM 에 page 를 이동하는게 더 효율적인지 계산하는 것은 결코 쉬운일이 아니다. 두번째 고려해야할 것은 huge page 재결합이다. 데이터 접근 패턴은 변화한다. 일시적으로 내부 단편화가 생긴 huge page 가 쪼개져서 base page 로 흩어졌다가 다시 모든 base page 들이 핫해질 수도 있다. 그러면 다시 huge page 로 재결합하는 것이 훨씬 효율적일텐데, 흩어진 base page 를 재결합 가능하게 모으는 것도 비용이 발생한다. 이런 문제를 고려하지는 않았지만 Memtis(Lee at el. SOSP’23)는 huge page 의 내부 단편화를 측정하고 쪼개는 휴리스틱한 기준을 제안하고 내부 단편화를 고려하지 않은 계층 메모리 시스템보다 좋은 성능을 보여준다.

이렇듯 계층 메모리 시스템이 풀어야할 문제는 결코 쉽지 않지만 많은 연구를 통해 조금씩 해결해 나간다면 10년, 20년 뒤 컴퓨팅 환경은 지금과는 다른 형상이 되어있을 수도 있다.