Write order is essential to guarantee the crash consistency of the user data. There are two examples of essential write orders for the consistency: the write order between data blocks and the metadata which points to the data blocks, and the write order between a data structure and a commit block of the data structure. Modern IO stack does not support the ordering primitive. So, modern software guarantees the write order by using a durability primitive such as fsync() or flush. However, it disturbs to saturate the performance of the state of the art hardware with the large writeback cache, parallel flash chip architecture, and deep command queue depth.
This dissertation separates the ordering guarantee from the durability guarantee. In the first part of this dissertation, we develop Order-Preserving Block Device. There are three write order reversions in Block Device: the reversion between Issue order and Dispatch order by IO scheduler, the reversion between Dispatch order and Transfer order by DMA controller, and the reversion between Transfer order and Flush order by storage firmware. To resolve these reversions, Order-Preserving Block Device adopts three techniques; Epoch-based IO Scheduler, Order-Preserving Dispatch, and cache_barrier command.
In the second part of this dissertation, we redesign the consistency guaranteeing mechanism in the journaling filesystem (EXT4) and the log-structured filesystem (F2FS) by using Order-Presrving Block Device. For the journaling filesystem, we develop Concurrent Journaling Filesystem, CJFS for short. Existing journaling filesystem guarantees the write order by using the durability primitives. It serializes every IO request for the transaction commit. CJFS resolves the serial transaction commit, removing the durability primitives called for the write order thanks to Order-Preserving Block Device. CJFS has some challenges such as the conflict between transactions, the low coalescing degree of the transaction, and the excessive flush calls for durability of transactions. To overcome the challenges, this dissertation adopts four novel techniques including Dual-Thread Journal Design, Multi-Version Shadow paging, Opportunistic Coalescing, and Compound Flush. For the log-structured filesystem, we develop Lightweight Checkpoint. The checkpoint in the existing log-structured filesystem blocks all file operations for the consistency of the checkpoint. The checkpoint wakes up the blocked file operations just after its completion. The checkpoint uses the durability primitive to guarantee two write orders; the write order between the checkpoint contents and the checkpoint commit block, and the write order between the checkpoint and file operations which are called after the checkpoint. Lightweight Checkpoint removes these durability primitives thanks to Order-Preserving Block Device. Lightweight Checkpoint returns after the dispatching of cache_barrier command. It improves the filesystem performance significantly, minimizing the blocked time of file operations during the checkpoint.
In the third part of this dissertation, we optimize the transaction mechanism of applications such as a database by using Order-Preserving Block Device and filesystem level transaction. Modern applications implement their transaction themselves. They call excessive fsync()s for the write order. Order-Preserving Block Device provides ordering guaranteeing system calls, fbarrier() and fdatabarrier(), which return just after write requests for dirty pages and cache_barrier are dispatched. However, the transaction mechanisms still have a severe write amplification and a excessive context switch overhead because the transaction mechanisms are implemented as a sophisticated combination of system calls. In this dissertation, we expose the filesystem level transaction to applications. The applications can protect their data with lightweight filesystem level transaction but without the sophisticated and heavyweight application level transaction. We implement our transaction model in a log-structured filesystem (F2FS), and we call the new transactional filesystem exF2FS. We design the new multi-file transaction model, Membership-Oriented Transaction, and we add system calls to use Membership-Oriented Transaction. To overcome the memory bloat problem and the conflict between transactions and the garbage collection, exF2FS adopts two technical ingredients, Stealing and Shadow Garbage Collection.
쓰기 순서 보장 기능은 사용자 데이터의 크래시 일관성 보장을 위한 필수 기능이다. 데이터 블록과 그 데이터 블록을 참조하는 메타데이터 사이의 쓰기 순서 보장, 자료구조와 그 자료구조의 커밋 블록 사이의 쓰기 순서 보장이 대표적인 사용 예다. 현대 입출력 스택은 쓰기 순서 보장 기능을 지원하지 않는다. 때문에 현대 소프트웨어들은 fsync()나 flush 명령어 등 내구성 보장 기능으로 쓰기 순서를 보장한다. 하지만, 이들은 대용량 쓰기 캐시, 병렬 플래시 구조, 대용량 커맨드 큐 등이 탑재된 최신 하드웨어의 성능을 낭비하게 한다.
본 논문은 현대 입출력 스택에서 순서 보장 기능을 영속성 보장 기능으로부터 분리한다. 본 논문의 첫 번째 주제는 Order-Preserving Block Device 개발이다. 현대 블록 디바이스에서는 세 번의 쓰기 순서 불일치가 발생한다. 입출력 스케줄러에 의한 Issue 순서와 Dispatch 순서의 불일치, DMA 컨트롤러에 의한 Dispatch 순서와 Transfer 순서의 불일치, 스토리지 펌웨어에 의한 Transfer 순서와 Flush 순서의 불일치다. Order-Preserving Block Device에서는 세 가지 순서 불일치를 해결하기 위해 세 가지 기법(Epoch-based IO Scheduler, Order-Preserving Dispatch, cache_barrier 명령어)을 사용한다.
본 논문의 두 번째 주제는 Order-Preserving Block Device의 순서 보장 기능을 이용하여 저널링 파일 시스템(EXT4)과 로그 구조 파일 시스템(F2FS)의 일관성 보장 기법을 다시 디자인하는 것이다. 저널링 파일 시스템에서는 병렬 저널링 파일 시스템(Concurrent Journaling Filesystem, CJFS)을 개발한다. 기존 저널링 파일 시스템은 내구성 보장 기능으로 쓰기 순서를 보장한다. 이는 트랜잭션 커밋이 발생시키는 모든 입출력 요청을 직렬화한다. CJFS는 순서 보장에 이용된 내구성 보장 기능을 제거하여 직렬 트랜잭션 커밋을 해결한다. 이를 위해 Order-Preserving Block Device의 순서 보장 기능을 이용한다. 병렬 저널링을 구현하는 것은 트랜잭션 간의 충돌 문제, 낮은 트랜잭션의 병합 정도(Coalescing degree), 트랜잭션 커밋 횟수 증가에 따른 잦은 트랜잭션 내구성 보장 기능 호출 문제 등의 어려움을 동반한다. 이를 해결하기 위해 네 가지 기법(Dual-Thread Journal Design, Multi-Version Shadow Paging, Opportunistic Coalescing, Compound Flush)을 추가로 개발한다. 로그 구조 파일 시스템에서는 경량 체크포인트(Lightweight Checkpoint)를 개발한다. 기존 로그 구조 파일 시스템의 체크포인트는 호출되는 즉시 모든 파일 연산을 멈추게 한다. 체크포인트의 일관성을 보장하기 위해서다. 체크포인트가 완료되어야 멈추었던 연산들이 재개된다. 체크포인트는 두 개의 내구성 보장 기능을 사용한다. 첫 번째 내구성 보장 기능은 체크포인트 내용과 체크포인트 커밋 블록 사이의 순서 보장을 위한 것이고, 두 번째 내구성 보장 기능은 체크포인트와 체크포인트 이후에 호출되는 파일 연산들 간의 순서 보장을 위한 것이다. 경량 체크포인트는 Order-Preserving Block Device의 순서 보장 기능을 이용하여 체크포인트가 호출하는 내구성 보장 기능들을 제거한다. 경량 체크포인트는 cache_barrier 명령어를 스토리지에 전달하고 반환한다. 파일 연산들이 체크포인트 때문에 멈추는 시간을 최소화하여 전체 파일 시스템 성능을 개선한다.
본 논문의 세 번째 주제는 어플리케이션(데이터베이스, 키 밸류 스토어)의 트랜잭션 메커니즘을 Order-Preserving Block Device와 파일 시스템 수준 트랜잭션으로 최적화하는 것이다. 현대 어플리케이션들은 자신만의 트랜잭션을 구현하여 사용한다. 이들은 쓰기 순서 보장을 위해 과도한 양의 fsync()를 호출한다. Order-Preserving Block Device는 순서 보장 시스템 콜인 fbarrier()와 fdatabarrier()를 제공한다. 이들은 더티 페이지 쓰기 요청들과 cache_barrier 명령어를 스토리지에 전달하고 반환한다. 하지만, 트랜잭션 메커니즘은 여전히 쓰기 증폭 문제와 과도한 문맥 전환 문제를 갖고 있다. 어플리케이션의 트랜잭션 메커니즘이 시스템 콜들의 복잡한 조합으로 구현되었기 때문이다. 본 논문은 파일 시스템 수준 트랜잭션을 어플리케이션에게 노출시킨다. 어플리케이션들은 복잡한 메커니즘을 구현할 필요 없이 파일 시스템 수준 트랜잭션을 사용하여 사용자 데이터의 일관성을 지킬 수 있다. 본 논문의 트랜잭션 모델을 로그 구조 파일 시스템인 F2FS에 적용하여 exF2FS를 개발한다. 본 논문은 새로운 다중 파일 트랜잭션 모델인 Membership-Oriented Transaction을 개발한다. 이를 사용하기 위한 인터페이스들을 시스템 콜에 추가한다. 로그 수준 파일 시스템의 파일 시스템 수준 트랜잭션은 메모리 용량 초과 (memory bloat) 문제와 파일 시스템 가비지 컬렉션과의 충돌 문제를 갖고 있다. 이를 해결하기 위해 Stealing과 Shadow Garbage Collection을 개발한다.
