Efficient Key-Value Data Placement for ZNS SSD

 

 

Gijun Oh , Junseok Yang and Sungyong Ahn *

 

School of Computer Science and Engineering, Pusan National University, 2, Busandaehak-ro 63beon-gil, Geumjeong-gu, Busan 46241, Korea; kijunking@pusan.ac.kr (G.O.); junseokyang@pusan.ac.kr (J.Y.) * Correspondence: sungyong.ahn@pusan.ac.kr; Tel.: +82-51-510-2422

 

---

 

 

    LSM-Tree based key-value store는 sequential write 특성으로 인해 high I/O performance로 주목을 받고 있다. 그러나 compaction 때문에 발생하는 추가적인 write로 인해, SSD의 lifespan을 단축시킨다. 따라서, host가 data 배치를 결정할 수 있는 SSD인 Zoned Namespace ZNS를 사용해서 GC overhead를 줄이려는 여러 연구가 있다. 그러나 기존 연구에서는 key-value data의 lifetime이나 hotness를 고려하지 않아서 performance 향상에 한계가 있는 것 같음. 따라서, 본 논문에서는 SSD를 key-value data의 특성에 맞게 배열해서 space efficiency와 GC overhead를 최소화하는 방법을 제안. 이 방법은 RocksDB의 ZenFS를 수정해서 구현했고, 성능 평가 결과 space efficiency를 최대 75%까지 향상시킬 수 있었다.

 

    최근 key-value store는 high performance, flexibility and simplicity 같은 여러 장점때문에 deep learning, blockchain같은 기술에 널리 사용된다. 특히, RocksDB 나 LevelDB같은 LSM-Tree based key-value store는 out-place update로 인한 sequential write 특성으로 인해 NAND Flash memory based SSD에서 높은 성능을 얻을 수 있다. 그러나, compaction을 할 때 많은 write가 발생해서 SSD의 성능이나 수명이 단축된다. 그리고 legacy block interface SSD의 경우, FTL의 GC가 추가적으로 write amplification을 증가시킨다. 

    ZNS(zone namespace) SSD는 NAND flash memory 영역을 일정한 크기의 zone으로 분할하고 host가 직접 zone을 관리할 수 있는 새로운 zone based interface를 사용한다. 따라서 ZNS SSD는 data 배치를 host가 직접 수행하기 때문에 GC overhead와 WA를 최소화할 수 있다. 현재, ZNS SSD를 사용해서 LSM-Tree의 WA를 최소화하려는 연구가 진행되고 있다.

    Facebook에서 개발한 KV-Store인 RocksDB의 경우, ZNS SSD는 ZNS를 타겟으로한 간단한 FS인 ZenFS를 통해 사용할 수 있다. 하지만, 현재 ZenFS는 RocksDB의 정보를 효과적으로 활용하지 못해서 hotness가 다른 file이 같은 zone에 기록되고 공간이 비효율적으로 사용된다. 또한, 현재, ZenFS는 GC를 지원하지 않기 때문에, RocksDB는 ZNS SSD에 설정된 large Key-value Set을 관리할 수 없다.

   따라서, 본 논문에서는 LSM-tree based key-value store에 최적화된 zone based data placement를 통해 compaction 시에 빈 zone을 빠르게 확보하는 방법을 제시한다. 또한, WA를 최소화하기 위해 data의 lifetime을 고려한 GC 기법을 제안. 

 

    Each storage standard는 각자의 공간을 zone 단위로 나눈다. 각 zone의 I/O는 서로 독립적이고 zone은 그 안에 sequential writes만을 받아들인다. standard에서는 zone을 효율적으로 관리하기 위한 드라이브 관리방식, 호스트 관리방식 혹은 호스트 인식 방식을 제안한다. drive-managed method는 SSD의 FTL과 같은 software firmware를 사용해서 legacy block interface layer를 지원(FTL이 zone을 관리)한다. host-managed method는 host가 직접 zone을 관리할 수 있게 해주고 zone내에서 순차적으로 쓰는것만 허용. 이 때문에 host는 host 정보를 이용해서 disk의 적절한 위치에 data를 배치할 수 있다. 이를 통해 disk의 성능을 충분히 활용할 수 있다. host-aware method는 hybrid 방식으로 drive managed 및 host managed 특성을 갖는다. 따라서, zone에 data를 쓰는데 아무런 제약이 없고, host가 각 zone의 상태를 관리할 수 있다. 그러나, 이 방식은 가끔 long-tail latency를 발생시킨다. 

    일반적인 환경에서는 drive-managed method가 선호되지만, 성능이 뛰어난 환경에서는 host-managed method가 선호된다. 전자의 경우, 사용의 용이성과 일반적인 환경에서 충분한 성능을 제공하는 반면, 후자는 고성능이 요구되는 환경에서 더 나은 성능을 제공하기 위해 사용된다. 예를 들면 key-value store 성능을 최적화하기 위한 환경에서는 host system이 직접 storage zone을 관리해서 storage에 대한 더 세밀한 제어가 가능하고, 결과적으로 더 높은 i/o performance와 data 처리 속도를 얻는다.

    ZNS SSD는 NVMe와 함께 Zoned Namespace interface를 사용하는 SSD의 한 종류이다. 그림 1에서 볼수 있듯이, ZNS SSD는 공간 기반의 단위를 zone이라는 이름으로 추상화한다. 호스트는 이 추상화된 zone을 활용해서 I/O를 관리하고 실행한다. 이는 SSD에 매우 간단한 FTL만 필요하거나 FTL이 전혀 필요하지 않음을 의미한다. ZNS SSD zone도 일반적으로 공간을 sequential write만 허용한다. sequential writes 규정은 ZNS SSD의 nameless write를 가능하게 한다. L2P mapping table의 크기가 획기적으로 줄어들게 한다.

(nameless write는 ZNS SSD의 기술로, data의 physical location에 대한 명시적인 주소 지정없이 write operation을 수행하는 것을 말한다. 즉, data는 nameless로 sequential하게 zone에 저장된다.)

 

    또한, ZNS SSD는 host가 SSD의 latency를 예측할 수 있게 해준다. Conventional SSD는 복잡한 FTL을 가지고 있어서 vender에 의해서 완전한 black-box가 된다. 그러나 ZNS SSD는 매우 간단한 FTL만 필요하거나 FTL이 전혀 필요없어서 host는 zns ssd가 노출하는 정보를 활용해서 conventional ssd보다 zns ssd의 latency를 더 잘 예측할 수 있다. 또한, ZNS SSD는 data placement 위치를 선택할 수 있으므로, disk의 성능을 향상시킬 수 있다. 예를 들어, 그림 1a에서 볼 수 있듯이 conventional SSD data는 FTL에 의해 random하게 배치된다. 그러나 그림 1b에서 볼 수 있듯이, ZNS SSD data는 application을 기반으로 그룹화된다. Application 1이 very internsive workload를 생성한다고 가정하면, 이런 workload에서 conventional SSD는 block을 지우기 위해 write amplification이 생긴다. 반면 ZNS SSD에서는 workload data가 host별로 group화된다. 이는 SSD가 block을 지우기 위해 WA가 생기지 않는다는 것을 의미한다. 이런 장점으로 next-generation interface method로 주목받았고 NVMe 표준에 추가될 예정이다.

 

    Facebook은 LSM-Tree based opensource key-value store인 RocksDB를 개발했다. 다른 key-value store와 다른 점은 flush 와 compaction routine에서 multi-thread를 사용할 수 있다. LSM-Tree는 out-of-place update를 사용해서 random write의 비중을 줄이고 out-place update로 인해서 생성된 invalid data를 aggregate하는 compaction routine을 가진다. 이는 LSM-Tree가 key-value store의 backend인 주요 이유이자 다양한 key-value store backend에서 LSM-Tree를 채택하는 주요 이유이다.

    그림 2는 Memtable, WAL(Write-ahead log) file 및 SSTable(sorted sequence table) file로 구성된 RocksDB architecture이다. Memtable은 memory에 존재하는 write buffer로 buffer threshold에 도달할 때까지 user의 wirte I/O를 aggregate한다. buffering은 coarse-grained write I/O를 할 수 있게하고 disk를 더 많이 활용할 수 있게 한다. SSTable은 compaction 결과에 의해 생성된다. 이는 LSM-Tree가 포함된 RocksDB의 핵심이다. RocksDB compaction은 leveled compaction을 사용한다.  leveled compaction은 optimal read performance를 달성하기 위해 겹치는 table의 수를 제한한다. 그러나 sorted merge를 실행할 때 높은 write amplification problems 로 어려움을 겪게 된다. 따라서 level 1에 위치한 SSTable은 write amplification으로 인한 문제가 있다.

 

    ZenFS는 Western Digital에서 개발한 RocksDB용 file system plugin이다. RocksDB와 Linux Kernel 사이에 위치하고 있다. Posix(Portable Operating System Interface) 호환 I/O 기능을 사용하려면 libzbd를 사용해서 file discriptor를 얻어야 한다. file discriptor가 확보된 후 ZenFS는 POSIX 호환 기능을 가진 direct I/O 형태로 RocksDB data를 ZNS SSD에 flush할 수 있다. 각 zone에서 sequential write로 data를 기록해야하므로 I/O 순서를 확실하게 하기 위해 I/O 스케줄러를 변경해야 한다.

+ posix는 os간 이식가능한 application interface를 제공하는 표준이다. file system, process management, networking 등을 포함한 다양한 system resource에 대한 API를 정의한다.

+ file discriptor는 열려있는 file, socket, pipe등을 식별하는 데 사용되는 정수 값이다. posix based system에서 file discriptor는 i/o operation을 위한 주요 interface 역할을 한다.

+ libzbd는 zoned block device를 지원하는 library이다. zone에 data를 순차적으로 쓰도록 하는 storage를 위한 interface를 제공한다. libzbd를 사용해서 zoned block device에 접근하고 조작하기 위해서는 해당 장치는 file discriptor가 필요하다.

 

    그림 3은 ZenFS가 journal 영역과 data 영역을 구분해서 각 zone을 관리하고 있는 것을 보여준다. journal 영역의 zone 수는 compile 시 정적으로 정의된다. 이에 비해 data 영역의 zone 수는 전체 zone 수에서 journal 영역 zone 수를 뺀 값으로 정의한다.

 

Figure 3. Overal architecture of ZenFS

 

    journal area는 ZenFS superblock 및 zonefile metadata를 포함한다. superblock area는 ZenFS 생성 정보를 가진다. 저널 영역의 나머지 영역은 WAL (write ahead log) 및 SSTable mapping zone 정보같은 zonefile metadata를 가진다. zonefile metadata는 file id, file size, file name and extent metadata의 배열을 포함한다. 

    Zonefile은 RocksDB file을 처리하기 위한 ZenFS용 abstracted file이다. system이 충돌할 때 복구를 위해 metadata가 memory에 업로드되고 journal area에 기록된다. data는 data area에 대한 extent 단위로 기록된다. extent에는 zone file data의 연속적인 부분이 있다. extent에서 start는 data가 처음 기록될 때 zone에서 wirte pointer의 위치를 나타내고 length는 zone에서 연속적으로 기록된 크기를 나타낸다.

    그림 4는 ZenFS에서 Zone의 할당을 묘사한 것이다. 그림에서 L3 data는 Zone을 요청한다. 이 경우 Zone allocator는 ZNS SSD에서 모든 Zone을 확인하고 유효하지 않은 data만 있는 zone을 찾는다. Zone allocator가 유효하지 않는 데이터만 포함된 zone을 찾으면 발견된 zone은 모두 지워진다. 예를 들어, 그림에서 zone #2는 유효하지 않은 데이터만 가지고 있다. 따라서 zone #2 는 삭제 대상으로 선택되어 지워진다. zone allocator는 모든 zone을 지운 후 요청된 데이터와 가장 작은 level 차이를 가지는 zone을 찾는다. 그림에서 zone allocator는 zone #1 이 요청된 데이터와 가장 작은 level difference를 가지는 것을 발견한다. 그 결과 zone allocator는 zone #1을 반환하여 요청된 데이터를 쓴다. 게다가, allocation 결과는 zone file metadata에 기록된다.

 

 

 

 

    ZenFS는 host 정보를 활용하지 않고 GC logic이 없다는 걸 발견했다. 이 사실을 확인하기 위해 ZNS SSD emulation 환경을 만들었고 ZenFS의 현재 상태를 평가했다. emulation된 zns ssd의 zone size는 16MiB, zone의 수는 512개, 총 크기는 8GiB였다. ZenFS를 평가하기 위해 RocksDB의 내부 benchmark program인 db_bench를 사용했다. 워크로드는 실험을 위해 "fillseq + overwrite" 사용했다. fillseq는 값이 있는 sequential keys를 생성하고 overwrite는 이전 키 범위에서 키와 값을 무작위로 생성한다. 실험은 400만개 및 500만 개 key-value pairs로 각각 수행됐다. 

    실험 결과는 figure 5에 나와있다. 그림을 보면 4M 개의 key-value pairs의 삽입에는 문제가 없었음을 알 수 있다. 그러나 5M 개의 key-value pairs는 overwrite가 끝날 때까지 workload를 실행하지 못하는 것을 확인했다. 결과에 따르면 이는 ZenFS가 ZNS SSD의 공간을 효율적으로 활용하지 못했음을 나타낸다.

 

    게다가, figure 5에서 4M 개의 key-value pairs의 삽입 결과를 보면 ZenFS가 overwrite를 시작할 때 사용 가능한 소수의 zone만 예약할 수 있음을 알 수 있었다. ZenFS의 zone allocation method로 인해 zone file의 수명을 제대로 고려하지 않아 효율적으로 zone을 reclaim하지 못했기 때문이다.

 

    Figure 6는 logical deletion과 physical deletion(삭제)의 average interval time을 보여준다. data의 lifetime에 따라 short, medium, extreme으로 데이터를 분류하고 있다. logical deletion은 ZenFS에 의해 data가 삭제되어 invalid로 표시되는 것을 의미한다. physical deletion은 ZNS SSD에서 데이터가 물리적으로 삭제되는 것을 의미한다. Figure 6은 zone에 data가 삽입된 후 삭제되는 데까지 걸리는 평균 시간을 보여준다. 그림에 따르면 medium과 extreme은 logical deletion 후 바로 physical deletion으로 이어졌다. 이 결과에 따라 수명이 짧은 data는 동일한 zone을 공유하는 수명이 긴 data로 인해 physical deletion이 중단되는 것을 알 수 있었다. 결과적으로 figure 5에서 data가 overwrite 시작했을 때, 사용가능한 zone은 소수에 불과하다.

 

    따라서, ZenFS는 자신의 공간을 효율적으로 활용할 수 없을을 알 수 있었다. 또한, data의 lifetime에 따라 data placement를 분할해야한다. 따라서 본 논문은 ZNS SSD에서의 key-value store를 위한 lifetime based zone allocation method and garbage collection method를 제안한다.

 

DESIGN

    제안된 방법의 architecture는 그림 7과 같다. zone allocator가 GC 와 allocation을 담당하는 기존 ZenFS와 달리, proposed method는 GC를 담당하는 부분을 Garbage collector에게 이전한다. 이는 zone allocator가 zone 할당만을 담당하도록 만든다.