[논문 리뷰] Enhanced Configurable Snapshot: Snapshot-based Fast Booting on NAND Flash with Lifetime Control

Abstract

<연구 배경: 빠른 부팅 방식인 영구 메모리 부팅은 아직 상용화 하기엔 이르다>

많은 소비자 전자기기에서 사용자 경험을 개선하기 위한 빠른 boot time은 이제 주된 이슈가 되었다. 영구 메모리를 사용한 즉각적인 on/off는 1초 미만의 부팅을 주장하지만, 기술적 성숙도는 여전히 진행중이고 가격은 현실적인 수준에 도달하지 못하였다. 따라서, NAND flash를 사용한 스냅샷 기반 부팅은 현재 소비자 산업에서 매력적인 솔루션이다.

그러나 스냅샷 기반 부팅 기술은 스냅샷 이미지를 저장할 때 NAND flash 메모리와 같은 기본 스토리지 장치에 추가적인 write를 발생시킨다. 따라서 NAND flash 메모리에 이 기술을 나이브하게 적용하면 NAND flash의 제한된 수명으로 신뢰성 문제가 발생하게 된다.

 

<연구 소개: NAND flash의 수명을 향상시키기 위한 고속 부팅 솔루션을 제시>

본 논문에선 수명을 향상시키기 위해 특별히 설계된 NAND flash 메모리 기반의 스냅샷 기반 고속 부팅 기술인 새로운 솔루션, Enhanced Configurable Snapshot(ECS)을 제안한다. 또한 부팅 시간을 향상시키기 위한 다양한 기술을 제시한다. 실험 결과 ECS는 Linux 커널에서 기존의 스냅샷 기반 부팅보다 평균적으로 2.5배 - 126.3배 더 긴 수명과 1.5배 더 빠른 부팅 시간을 제공하는 것으로 나타났다.

 

1. Introduction

<연구 배경: snapshot 기반의 부팅이 쓰이게 된 이유>

양질의 고객 경험을 위해 많은 모바일 기기와 임베디드 기기에서 fast booting 에 대한 수요가 증가해왔다. 예를 들어, 자동차의 후방 뷰 카메라 시스템은 운전자가 시동을 건 직후 바로 준비가 되는것이 안전과 편의성 측면에서 중요하다. 수많은 노력들이 booting time을 감소시키기  위해 가해져 왔고, 영구 메모리를 사용한 instant booting의 SOTA는 1초 미만의 부팅을 주장한다.

그러나 불행하게도, 영구 메모리를 사용한 기술의 성숙도는 아직 발전중에 있고, 가격이 현실적인 수준에 도달하지 못하였다. 따라서, snapshot 기반의 부팅이 현재 산업계에서 유망한 솔루션이다.

과거 연구들에 따르면, 안드로이드 OS는 평균 25 - 30초의 부팅시간을 가지고있고 snapshot 기반의 방법을 사용해 5초로 현저히 부팅시간을 감소시킬 수 있다고 한다.

 

<snapshot 기반 부팅 프로세스 설명>

snapshot 기반의 부팅, 다른말로 hibernation 기반 혹은 suspend-to-resume 부팅은, 근본적으로 suspend와 resume이라는 두가지 단계로 구성되는 disk에서의 재개(resume) 연산이다. 매번 시스템이 suspended 될 때 마다, 시스템은 자신의 메모리 상태(memory status)를 생성해 연결된 disk에 저장한다. Rusuming될 때, 기존 메모리 상태의 이미지를 복원함으로써, 시스템은 많은 복잡한 초기화 코드들을 생략할 수 있게되며, 이는 부팅 지연시간(latency)의 감소로 나타난다.

 

<문제 제기: 기존 snapshot 기반 부팅은 disk에 추가적인 write 연산을 수행해야한다>

비록 snapshot 기반의 방식이 부팅 시간을 현저히 줄이지만, 이는 필연적으로 동반된 disk에 추가적인 write 연산들을 수행하게 된다. 이러한 disk가 NAND flash 메모리를 기반으로 하는 경우 이 방법을 순진하게 채택하면 NAND flash 메모리의 제한된 쓰기 내구성으로 인해 문제가 발행하게 된다. 불행하게도 많은 최신 소비자 가전 제품은 매력적인 기능 덕분에 eMMC나 UFS같은 NAND flash 메모리를 기본 스토리지 장치로 사용한다.

 

<ECS 방식 제시>

이러한 문제를 해결하기 위해 flash 장치의 수명을 최적화하도록 설계된 최신 NAND flash 메모리용 새로운 스냅샷 기반 부팅 솔루션인 Enhanced Configurable Snapshot(ECS)를 제안한다. figure1은 ECS를 사용한 I/O 스택 레이어를 보여준다. 전원 관리 레이어는 suspend 및 resume 시퀀스를 담당하고 블록 I/O 레이어는 실제로 읽기 및 쓰기 I/O 작업을 수행한다. 이 두 계층 사이에 NAND flash 장치의 수명 문제를 해결하기 위해 ECS를 구현한다.

 

보다 구체적으로, NAND 플래시 메모리의 수명은 다음 두 가지 요인에 의해 크게 좌우된다.

(a) write traffic

(b) write amplification factor(WAF) 값

 

따라서 우리의 주요 목표는 다음과 같다.

(a) 스냅샷 이미지의 크기를 최대한 줄이고, 

(b) WAF 값을 최소화하기 위해 물리적인 write I/O 패턴을 효율적으로 관리하는 방법을 제공하는 것.

 

본 논문에서는 또한 읽기 I/O 성능 향상에 초점을 맞춰 부팅 시간을 단축하기 위한 다양한 기술에 대해 논의한다.

 

<주요 기여점>

1. NAND flash 메모리의 수명 향상에 초점을 맞춘 새로운 스냅샷 기반 고속 부팅 솔루션인 ECS를 제안한다.
2. 스냅샷 이미지의 크기 및 WAF 값을 줄이기 위한 다양한 기술을 소개한다. 파일 페이지 분리, 중복 제거, 압축, 로그 구조 물리적 세그먼트 관리 및 가비지 컬렉션이 있다.
3. 실제 장치에서 기존 스냅샷 기반 부팅에 비해 ECS를 사용했을 때의 수명 및 부팅 시간 개선을 정량적으로 분석한다.

<본 논문의 나머지 구성>

(2장) snapshot 기반 부팅 및 NAND flash 메모리의 수명에 대한 배경 지식 소개

(3장) 스냅샷 이미지를 자세히 분석

(4장) 제안하는 설계 및 기술에 대해 논의

(5장) 평가 결과

(6장) 관련 연구 제시

(7장) 결론

 

2. Background

2.1. 리눅스에서 snapshot 기반의 부팅

snapshot 기반 부팅은 최대 절전 모드(hibernation) 기반 또는 일시 중단-재개(suspend-resume) 부팅 이라고도 하며, 리눅스 커널의 현재 소프트웨어 suspend 방식을 기반으로 한다. Figure 2는 ECS를 사용한 이 방법을 요약한 것이다(빨간 영역이 ECS가 구현된 위치임). 일반적으로 이 방법은 일시 중단 및 재개의 두 가지 절차로 구성된다.

1. suspend 절차는 장치를 일시 중단하고 현재 메모리 및 시스템 상태의 스냅샷을 만든다. 전원을 끄기 전에 스냅샷 이미지를 디스크에 쓴다. 
2. resume 절차는 disk에서 이전 스냅샷 이미지를 읽고 복잡한 초기화 프로세스를 건너뛰어 커널로 직접 점프한다.

본 논문에서는 더 빠른 booting time을 위해 부트 로더가 커널 대신 스냅샷 이미지를 복원한다. 우리는 suspend 절차를 위해 리눅스 커널에 ECS를 구현하여, 스냅샷 이미지 크기를 줄이고 write I/O 작업을 관리하는 데 초점을 맞췄다. 동시에, 우리는 resume 절차를 위해 부트로더에도 ECS를 구현해 quick booting을 위한 read I/O 작업 관리에 초점을 맞췄다.

 

2.2. NAND Flash 수명의 문제점

많은 가전제품이 매력적인 기능 덕분에 NAND 플래시 메모리를 기본 스토리지로 채택한다. 하지만 NAND 플래시는 쓰기 내구성이 제한되어 있다. NAND 플래시 메모리의 수명은 다음과 같이 표현할 수 있다.

여기서 용량은 device의 용량, ProgramEraseCycle은 program-erase 주기, 쓰기 트래픽은 쓰여진 데이터의 양, WAF는 Write Amplification Factor을 나타낸다.

NAND 플래시를 물리적으로 교체하지 않는 한 용량과 program-erase 주기를 제어할 수 없기 때문에 NAND의 수명은 쓰기 트래픽 및 WAF 값에 따라 달라진다. 안타깝게도, 기존의 스냅샷 기반 부팅 기술은 WAF값을 제어할 수 없다. 이는 WAF가 쓰기 I/O 패턴과 크기에 따라 달라지며 일반적으로 완전히 무작위이기 때문이다. 연구에 따르면, NAND flash의 수명을 예측하기 위해선, 일정한 WAF값을 추정해야 한다. 일정한 WAF 값을 얻는 가장 좋은 방법은 FTL(Flash Translation Layer)보다 높은 수준에서 쓰기 I/O를 조작하는 것이다. 본 논문에서는 커널 수준에서 임의의 쓰기 I/O 패턴을 조작하여 일정하고 작은 WAF값을 만드는 방법을 소개한다.

 

3. Snapshot Image 분석

이 섹션에서는 suspend 프로세스 동안의 스냅샷 이미지를 검사한다. 더 구체적으로는, 스냅샷 이미지들을 특성별로 분류하여 다양한 페이지로 나누고 스냅샷 크기를 줄이는 방법을 연구한다. 또한 스냅샷 기반 부팅을 여러 번 실행할 때 중복 제거로 인해 발생하는 스냅샷 이미지의 단편화 문제를 검사한다.

3.1. Memory Workload

일반적으로 스냅샷 이미지의 크기는 메모리 워크로드의 영향을 받는다. 본 논문에서는 다음 네 가지 경우로 워크로드를 분류할 수 있다.

(1) Idle

• 첫 번째 경우는 Idle workload로 스냅샷 부팅을 반복하는 것이기 때문에, 앱을 실행하지 않고 스냅샷 부팅만 반복한다. 이 경우 workload의 영향은 최소화된다.

(2) Apps

• 두 번째 경우는 suspend 단계 전에 안드로이드에서 기본 애플리케이션 목록을 반복적으로 실행하는 것이다. 애플리케이션에는 Android Auto, Apple CarPlay, Calendar, Files, Contacts and AVN (Audio Video Navigation) 등이 있다.

(3) Multimedia

• 세 번째 경우는 일시 중단 단계 전에 멀티미디어 앱을 반복적으로 실행하여 비디오 및 오디오를 재생하는 것이다.

(4) Random

• 마지막 경우는 Monkey test를 실행하여 workload를 생성하는 것이다. Monkey test는 설치된 앱을 무작위로 실행하여 임의의 workload를 생성한다. 이 경우는 다른 경우들 보다 더 많은 메모리를 할당한다.

우리는 시스템이 suspend phase로 들어가기 전에 불필요한 애플리케이션을 종료하여 resume pahse를 위한 최소한의 App수를 유지하였음을 강조한다. 이 방법은 snapshot 크기를 효과적으로 줄이고 전원을 켰을 때 시스템을 가능한 한 빨리 사용할 수 있도록 한다.

 

3.2. Snapshot Image Breakdown

suspend 단계 동안 메모리 상태가 저장되고 resume 단계에서 복원되어 시스템은 계속 실행될 수가 있다. 기기가 suspend된 이후의 메모리 상태를 snapshot 이미지라고 한다. 리눅스 커널에서 전체 스냅샷 이미지는 일시 중단 프로세스 중 특정 시점에 다른 메모리 공간으로 복사되어 sotrage 에 기록된다. 스냅샷 이미지는 다양한 용도로 사용되는 페이지로 구성된다. 페이지의 특성을 더 자세히 연구하기 위해 먼저 시스템의 각 페이지 사용량을 관찰하고 스냅샷 크기를 줄이는 방법에 따라 세 그룹으로 분류한다:

 

(1) File pages (필수 아님)

• 파일 페이지들은 물리적인 read I/O 연산을 숨김으로서 성능을 개선하기 위해 임시로 할당되어 사용된다. 이러한 페이지는 스냅샷 이미지를 만드는 데 필요하지 않다. File pages를 삭제하기만 하면 스냅샷 이미지를 줄일 수 있다

(2) Same pages (필수)

• File pages를 제외한 모든 페이지는 스냅샷 이미지를 만드는데 필요하다. 먼저 내용이 다른 페이지와 동일한 페이지를 찾을 수 있다. 이러한 페이지를 same pages로 정의한다. 스냅샷 이미지를 만드는 데는 same pages의 사본 하나만 필요하다. 즉, 단일 페이지만 저장하여 스냅샷 이미지를 줄일 수 있다.

(3) Unique pages (필수)

• 마지막으로 Unique pages를 정의한다. 이러한 페이지는 file pages또는 same pages가 아니다. 모든 unique pages는 스냅샷 이미지를 만드는 데 필요하다. 압축을 통해 스냅샷 이미지를 줄일 수 있다.

 

첫째, 리눅스 커널에서 file pages는 읽기 I/O 성능 향상을 위해 캐시(cache)와 똑같이 작동한다. 프로세스가 필요할 때마다 스토리지에 I/O를 요청하지 않고 파일에서 데이터에 엑세스할 수 있도록 시스템에서 자주 요청되는 파일로 할당된다. 이러한 페이지는 중복되며 시스템은 성능 저하를 감수하면서 file pages 없이 실행할 수 있다. 따라서 이러한 file pages를 간단히 삭제할 수 있다. file pages가 읽기 I/O 성능 저하를 일으키지 않더라도 스냅샷 크기가 줄어들어 전체 성능이 실제로 향상된다.

 

둘째, file pages 외에 모든 페이지는 스냅샷 이미지를 만드는 데 필요하다. 그 중에서는 내용이 서로 동일한 페이지가 있다. 이러한 same pages는 동일한 페이지를 모두 저장하는 대신, 페이지를 하나만 저장하여 줄일 수 있다. 예를 들어 리눅스 커널에서 KSM(Kernel Same-page Merging) 기술도 동일한 작접ㅇ르 수행한다. KSM은 메모리 페이지를 스캔하여 동일한 페이지를 단일 쓰기 방지 페이지로 바꾼다.

 

마지막으로, Unique pages는 File pages또는 Same psages가 아니다. 스냅샷 이미지를 만들려면 모든 Unique pages를 저장해야한다. 이러한 페이지를 줄이는 유일한 방법은 압축하는 것이다.

Figure 3는 다양한 메모리 워크로드에서 스냅샷 이미지의 File, Same 및 Unique pages 크기를 보여준다. 스냅샷 이미지는 Idle, App, Multimedia 및 Random workload에서 각각 30.9%, 36.0%, 35.8%, 54.2%를 줄일 수 있다. 또한, Same pages에서 중복 제거를 통해 스냅샷 크기를 평균 18% 더 줄일 수 있다. 마지막으로 모든 Unique pages를 저장해야 하므로 Unique pages에서는 감소가 없다. 마지막에 압축을 수행할 수 있다.

 

3.3. 다중 일시 중단 단계에서의 중복 제거(Deduplication across Multiple Suspend Phases)

3.2절에서는 주로 다양한 페이지 그룹으로 스냅샷 이미지를 분석하는 방법에 중점을 두었다. 이 섹션에서는 스냅샷 기반 부팅을 여러 번 실행할 때 중복 제거가 스냅샷 이미지에 미치는 영향에 대해 연구한다. 여기서 중복 제거는 서로 다른 단계에서 동일한 페이지가 있음을 의미한다. 이 용어는 각 일시 중단 단계에서 스냅샷 이미지 간의 동일한 페이지를 나타내는 이전 3.2절의 Same pages와 다르다.

리눅스 커널에서는 원래 생성된 스냅샷 이미지가 다음 suspend 단계를 위해 더이상 쓰이지 않는다. 즉, 이전 스냅샷 이미지에 대한 지식 없이 매번 일시 중단 단계에서 새 스냅샷 이미지가 생성된다. 이러한 스냅샷 이미지를 조사한 결과 여러 스냅샷 이미지에서 일부 페이지가 중복되는 것을 발견하였다. 이러한 중복된 페이지지를 활용하면 물리적 쓰기 트래픽을 중복된 페이지의 양만큼 줄일 수 있다. 이는 플래시 메모리의 수명 향상으로 이어진다. 이 접근 방식은 여러 스냅샷 이미지에 걸쳐 더 많은 중복 페이지가 있을 때 효과적이다.

Figure 4는 이 아이디어를 보여준다. 첫 번째 suspend 단계에선 스토리지에 스냅샷 이미지가 없기때문에 모든 페이지가 물리적으로 기록된다. 그러나, 두번 째 단계에서는 페이지 A와 B가 중복되므로 페이지 E와 F만 물리적으로 기록된다. 이 경우 수명을 2배로 연장할 수 있다. 세 번째 단계에서는 페이지 A가 다시 중복된다. 그리고 페이지 C가 처음으로 중복된다. 결과적으로 페이지 H와 I만 물리적으로 기록되어 수명이 2배 더 길어진다.

 

얼마나 많은 스토리지가 소비되는지 측면에서 총 8페이지가 물리적으로 기록되며 이 양을 accumulated write size(누적된 쓰기 크기)라고 한다. 여러 suspend 단계에 걸쳐 누적 쓰기 크기가 서서히 증가하는 것을 관찰하였다(Figure 5 참고). 저장할 스냅샷 이미지 크기가 거의 일정하게 유지되는 것을 관찰했기 때문에 여러 일시 중단 단계에 걸쳐 중복 제거로 인한 단편화가 존재해야 한다.

 

3.4. 여러 Suspend 단계에 걸친 단편화

Figure 4에서 일부 페이지는 두 번 이상 중복될 수 있지만 다른 페이지는 전혀 중복되지 않는 것을 알 수 있다. 더 많은 suspend 단계를 실행할수록 이로 인한 더 많은 단편화가 발생할 수 있음을 관찰하였다. Figure 6는 처음 세 번의 suspend 단계에서 실제 스냅샷 이미지의 처음 500개의 샘플 페이지를 보여준다. 빨간색으로 표시된 박스는 중복된 페이지를 나타낸다. 또한 중복된 페이지의 정도는 색의 척도로 표시된다. 색이 어두울수록 페이지가 더 많이 중복된 것이다.

 

Figure 6에서 두 가지 주요 제한 사항을 발견하였다.

첫째, 스토리지 용량이 제한되어 있으므로 특정 시점에 스냅샷 이미지를 저장할 수 없다. 이러한 제한을 극복하기 위해 사용하지 않는 공간(흰색으로 표시된)을 덮어써야 한다. 이렇게 하면 제한이 해결되지만 중복 비율이 감소한다. 따라서 향후 suspend 단계에서 중복되지 않을 페이지를 효율적으로 선택해야 한다. 이에 대해서는 4.3.3 절에서 논의한다.

둘째, 스냅샷 이미지의 단편화 정도는 여러 suspend 단계에 따라 점차 증가한다. 즉, 빨간색으로 표시된 상자의 분포가 suspend 단계에 따라 변경된다. 이로 인해 더 많은 페이지 그룹을 읽어야 하므로 resume 단계에서 부팅 시간이 느려진다. 이는 스냅샷 이미지를 읽을 때 read I/O 작업의 크기가 단일 페이지의 크기보다 크기 때문이다. 일반적으로 전체 read I/O 시간을 줄이기 위해 시스템은 페이지를 그룹으로 읽는다. 따라서 중복된 페이지가 많더라도 단편화로 인해 실제 read I/O 횟수는 점차 증가한다. Figure 5는 각 resume 단계에서 read I/O 횟수를 보여준다. 시간이 지남에 따라 점차 증가함을 알 수 있다. 이로 인해 부팅 시간이 저하된다. 단편화로 인한 불이익과 이를 해결하는 방법에 대해서는 4.4절에서 논의한다.

 

(이어서 계속)