17th USENIX Conference on File and Storage (이하 FAST ‘19)은 파일 시스템 및 스토리지 관련 분야를 다루는 저명한 국제 학술대회이다. 이번 FAST ‘19논문 발표와 Invited talk, 아직 진행중인 연구를 발표하는 WiP, 포스터 세션으로 구성되었다.
이번 FAST ‘19에서는 총 26편의 논문이 발표되었다. 26편의 논문은 총 8개의 세션으로 분리되어 발표되었다: Persistent Memory Systems, File Systems, Deduplication, Storage Potpourri, NVM File and Storage Systems, Big Systems, Flash and Emerging Storage Systems, Erasure Coding and Reliability.
Flash and Emerging Storage Systems 세션에서는 서울대학교와 삼성에서 투고한 논문이 발표되었다. 논문의 제목은 “Fully Automatic Stream Management for Multi-Streamed SSDs Using Program Contexts”이다. 해당 논문은 사용자 데이터의 Hot/Cold 여부를 나누고 SSD의 스트림에 Hot/Cold 데이터를 분리하여 쓰는 기술에 대한 내용을 다루었다. 이제까지는 메타데이터와 데이터를 구분하여 스트림에 쓰는 기술밖에 없었으나, 사용자 데이터의 Hot/Cold 여부를 구분하였다는 것에서 큰 의미를 갖는 논문이었다. 사용자 데이터의 Hot/Cold 여부를 구분한 방법은 간단하면서도 기발한 아이디어를 사용하였다. 사용자가 커널에게 시스템 콜을 통해 IO 요청을 하려면 사용자만의 특정 Call path를 경유한다. 이 때, 함수를 호출할 때마다 생기는 Return address들이 사용자 스택에 저장된다. 해당 Return address들은 IO 요청을 위한 시스템 콜 호출 위치마다 다를 것이다. 즉, 사용자 스택에 저장되어 있는 Return address들을 기반으로 해쉬값을 추출하면 사용자의 IO 요청들을 분리할 수 있다. 본 논문에서는 위와 같은 방법으로 사용자의 IO 요청들을 분리하고 각 IO 요청별로 쓰기 빈도를 저장한다. 그리고 쓰기 빈도가 높은 IO 요청 패턴을 Hot으로 구분하고, Hot stream을 통해 데이터를 쓴다.
다른 흥미로운 논문으로는 “Optimizing Systems for Byte-Addr
essable NVM by Reducing Bit Flipping”과 “Large-Scale Graph Processing on Emerging Storage Devices”가 있었다.
“Optimizing Systems for Byte-Addressable NVM by Reducing Bit Flipping”은 비휘발성 메모리를 위한 효율적인 자료구조를 소개하는 논문이었다. Byte-addressable Non-Volatile Memory (BNVM)은 커널의 IO path 없이 간단한 방법으로 persistent data를 저장할 수 있는 차세대 저장장치이다. 특히, BNVM은 Bit Flipping을 통해 Fin-grained write가 가능하다는 장점이 있다. power consumption과 wear-leveling은 BNVM에서 가장 중요한 요소이다. 이 두 요소의 효율은 Flip하는 bit의 수와 반비례한다. 해당 논문은 Flip하는 bit의 수를 줄여 효율적으로 BNVM을 사용하도록 하는 자료구조들을 제안한다. 수정할 내용이 같을 때 Flip하는 bit의 수를 줄이려면 원본 데이터와 변경된 데이터의 결과를 xor한 결과가 -1 이어야 한다. -1은 모든 비트가 1임을 의미한다. 즉, 원본 데이터와 변경된 데이터의 비트 패턴이 최대한 유사해야 Flip하는 bit의 수가 줄어든다. 두 데이터 간의 유사도를 줄이는 방법은 여러가지가 있을 수 있다. 그 중 한가지 방법은 데이터의 비트 수를 줄이는 것이다. 더 적은 비트에서 변경이 발생하기 때문에 비트 패턴이 유사할 확률은 증가한다. 해당 논문은 데이터의 비트 수를 줄인 특수한 알고리즘인 xor linked list를 제안한다. 일반 linked list는 데이터, next 포인터, prev 포인터를 갖는다. xor linked list는 데이터, xor 포인터를 갖는다. xor 포인터는 next 포인터와 prev 포인터의 xor 결과이다. xor은 결과로부터 인자를 얻을 수 있는 특성을 갖기 때문에, xor 포인터 필드 하나는 next 포인터와 prev 포인터를 모두 표현할 수 있다. 그리고, next 포인터와 prev 포인터를 하나의 필드로 크기를 줄였기 때문에 원본 데이터와 변경된 데이터의 비트 패턴이 유사할 확률은 올라간다. 해당 논문은 이러한 xor의 특성을 활용하여 linked list 뿐만 아니라 hash table, red black tree 또한 최적화 시켰다. 그 결과, bit flip 횟수를 3.56배 감소시켰다.
“Large-Scale Graph Processing on Emerging Storage Devices”은 Flash storage를 위한 그래프 처리 기법을 소개하는 논문이었다. 그래프 처리는 대형 데이터셋을 처리하는데 필요한 기초적인 컴퓨팅 기술이다. 하지만, 대형 그래프를 처리하는 것은 메모리나 스토리지에 대한 find-grained random access를 많이 야기한다. 많은 이전 연구들은 그래프 데이터를 DRAM에 전부 저장하거나, 일부만 저장하여 최적화했다. 특히, find-grained random access가 많은 Vertex Data를 DRAM에 저장하고, 상대적으로 coarser grained access가 많은 Edge data를 스토리지에 저장하여 그래프 처리의 성능을 최적화시켰다. 하지만, 그래프의 크기가 커질수록 DRAM 메모리에 그래프 데이터의 일부를 저장하는 방법은 비효율적이게 된다. SSD의 용량 확장과 성능 향상은 대형 그래프 데이터셋을 저장하고 높은 성능을 제공하는데 도움이 되었지만, SSD의 large access granularity는 상당한 bandwidth로 그래프 처리를 하는데 방해가 된다. 이전 연구들은 그래프 데이터의 일부를 메인 메모리에 저장하거나 그래프 데이터를 효율적으로 분할하여 이 문제를 완화하려 했다. 이러한 기술들은 하드디스크를 위해서 디자인되었고, SSD의 높은 대역폭을 활용할 수 없거나, vertex 데이터를 스토리지에 저장할 때, 쉽게 적용할 수 없다. 해당 논문의 이전 연구인 GraFBoost는 모든 그래프 데이터를 SSD에 저장하고, global sequential IO를 제공하는 fully external graph processing 프레임워크이다. 성능 이득이 있음에도 불구하고, global sequential IO는 그래프 데이터셋의 크기를 급증시켜 확장성을 저해한다. 반면 NVMe SSD는 랜덤 및 순차적 페이지 레벨 I/O 액세스에 대해 유사한 성능을 제공하므로, 순차성에 집중할 필요가 없다. 해당 논문은 external graph processing의 성능 이슈에 대해 분석하고, global sequential IO를 완화하기 위한 vertex data를 분할할 것을 제안한다. 특히, 해당 논문은 모든 그래프 데이터가 스토리지에 저장되는 기존 external graph processing의 성능 문제와 확장성 문제를 해결한다. 이를 위해, 우리는 vertex data를 위한 partitioning technique를 창안한다. 해당 논문의 partitioning 기술을 사용하면, partition과 관련된 vertex 데이터를 SSD에서 메모리로 로드한 후, 업데이트를 하기 위해 필요한 subsequent 정보가 SSD로부터 메모리로 로드될 것이다. 따라서, fine-grained update들은 메모리에 있는 vertex 데이터에만 적용되므로 완벽한 sequentiality를 제공하기 위해 모든 intermediate update를 병합할 필요가 없다. 해당 기법은 기존 external graph processing 기술 대비 2배 향상된 성능을 보여준다.
2월 26일에는 포스터 발표가 있었다. 우리는 FAST ‘19에 투고했다가 reject된 논문을 포스터로 발표하였다. 논문의 제목은 “xF2FS: Supporting Multi-File Transaction in Log-Structured Filesystem”이다. 기존 F2FS에 Multi-File Transaction 기능을 추가한 것이다. 트랜잭션을 지원하는 파일시스템 주제는 많은 연구가 진행되었고 그만큼 많은 관심을 받는 주제이기 때문에 많은 사람들이 우리의 포스터에 관심을 가졌다.