Multi-queue block I/O scheduler

  • blk-mq(Multi-queue block I/O queueing mechanism)의 I/O scheduler
  • 리눅스 커널 5.0부터 multi-queue block I/O scheduler를 기본 I/O scheduelr로 사용
  • 리눅스 커널 5.3부터 기존의 single queue block I/O scheduler를 지원하지 않음
  • RHEL 8, Ubuntu 20부터 multi-queue block I/O scheduler를 기본 I/O scheduler로 사용

Multi-queue block I/O queueing

배경

  • 기존의 디자인은 single queue와 하나의 lock으로 block I/O 요청 관리
  • 멀티 프로세서 환경에서 단일 lock을 이용한 I/O 관리는 병목 현상 야기
    → 이러한 문제를 해결하기 위해서 multi-queue block I/O 고안
  • blk-mq API에서는 각 CPU별로 개별적인 큐를 할당하여 lock으로 인한 성능 저하 문제를 해결

구조

overview

  • blk-mq는 파일 시스템과 블록 I/O 디바이스 사이에서 동작
  • blk-mq는 소프트웨어 큐(software staging queues)와 하드웨어 큐(hardware dispatch queues)의 두 종류의 큐들로 구성
    • I/O 스케줄러가 있거나 I/O 요청을 합쳐야(merge)할 필요가 있는 경우 I/O 요청은 소프트웨어 큐로 보내짐
    • 그 외의 경우 하드웨어 큐로 바로 보내짐
    • 소프트웨어 큐에서 I/O 요청이 처리된 이후 하드웨어 큐로 보내짐
      • 하드웨어에 I/O 요청을 처리할 수 있는 충분한 리소스가 없는 경우, 처리 가능해질 때까지 임시 큐에 보관

소프트웨어 큐

  • 각각의 큐는 고유의 lock을 가지고 있고, 큐의 개수는 per-CPU나 per-node기반으로 결정
  • Staging queue는 인접한 섹터에 해당하는 요청들을 합치는 역할
    • ex. 3-6, 6-7, 7-9의 요청이 있으면 3-9의 하나의 요청으로 합침
  • 큐의 I/O 요청들은 I/O 스케줄러에 의해 재정렬될 수도 있음

하드웨어 큐

  • 하드웨어 큐는 디바이스 드라이버의 디바이스 서브미션 큐(device submission queue) 혹은 디바이스 DMA ring buffer와 매핑
  • 이 큐를 실행시키면 블록 레이어는 소프트웨어 큐에서 해당 요청들을 제거하고 하드웨어에 요청들을 디스패치
  • 하드웨어 큐의 개수는 하드웨어와 디바이스 드라이버가 지원하는 만큼 만들 수 있지만, 시스템의 코어 수를 넘지 않음
  • 재정렬 과정은 존재하지 않음 (I/O 스케줄러 사용하지 않음)
  • 각 소프트웨어 큐에는 요청을 보낼 하드웨어 큐 집합이 있음

Multi-queue block I/O scheduler의 종류

none

noop

  • single queue block I/O scheduler의 일종
  • I/O 요청에 대해서 별도의 정렬 조치를 취하지 않는 방식. no operation.
  • noop의 멀티 큐 버전
  • I/O 요청에 대해서 별도의 정렬 조치를 취하지 않는 방식
  • SSD나 고성능 스토리지 환경에서 CPU-bound 작업을 하는 경우에 적합
  • RHEL 8, Ubuntu 20에서 multi-queue device의 default I/O scheduler

mq-deadline

deadline

  • single queue block I/O scheduler의 일종
  • I/O의 마감(deadline)을 지정하고, 마감이 가까운 I/O부터 처리
  • 지연 시간에 예민한 프로세스들에게 유리
  • RHEL 7의 default I/O scheduler
  • deadline의 멀티 큐 버전
  • RHEL 8, Ubuntu 20에서 single queue device의 default I/O scheduler

Configurable parameter

  • async_depth
    • default value: 1
  • fifo_batch
    • default value: 16
    • 배치에 속하는 요청의 최대값
    • 레이턴시와 처리량의 트레이드-오프
      • 1으로 설정시 낮은 레이턴시
      • 높은 값은 높은 처리량
  • front_merges
    • default value: 1
    • 1은 enable, 0은 disable
  • write_expire
    • default value: 5000
    • write의 데드라인 (ms 단위)
  • writes_starved
    • default value: 2
    • 얼마만큼 read를 write보다 우대하는지

bfq(Budget Fair Queueing)

cfq(Completely Fair Queueing)

  • single queue block I/O scheduler의 일종
  • 모든 프로세스가 I/O를 균등하게 처리하는 방식
  • 각 프로세스가 I/O queue를 가지고, round robin 방식으로 정해진 time slice 내에 I/O 처리
  • ubuntu 18의 default I/O scheduler
  • 각 프로세스마다 작업 큐를 가지고 있지만, cfq처럼 round robin 방식을 사용하지는 않음
  • 각 프로세스마다 I/O budget이 부여되고, 이 budget은 스토리지 접근 기회를 부여받았을 때 프로세스가 몇 개의 섹터만큼 데이터를 전송할 수 있는지를 나타냄
  • 데스크톱이나 interactive한 작업에 적합

bfq1

  • bfq의 budget 계산

bfq2 bfq3

Configurable parameter

  • back_seek_max
    • default value: 16384
    • backward seeking의 최대값 (KB 단위)
  • back_seek_penalty
    • default value: 2
    • backward seeking 계산에 사용되는 값

Backward seek
Disk head의 뒤에 위치한 블록을 탐색하는 것으로 bfq는 해당 탐색에 패널티를 부여

  • fifo_expire_async
    • default value: 250
    • 비동기 요청의 타임아웃 (ms 단위)
  • fifo_expire_sync
    • default value: 125
    • 동기 요청의 타임아웃 (ms 단위)
  • low_latency
    • default value: 1
    • 1은 enable, 0은 disable
  • max_budget
    • default value: 0
    • budget의 최대값
    • 0으로 설정된 경우 BFQ는 내부적으로 timeout_sync를 이용하여 최대값을 구함
  • slice_idle
    • default value: 8
    • 비어있는 큐에서 다음 요청을 위해서 기다릴 수 있는 최대 시간 (ms 단위)
  • slice_idle_us
    • default value: 8000
    • slice_idle과 같으나 마이크로초 단위
  • strict_guarantees
    • default value: 0
    • 1은 enable, 0은 disable
    • 1로 설정되었을 경우 (a) 서비스 큐가 비어있으면 항상 대기하고, (b) 디바이스가 한 번에 하나의 I/O 요청을 처리하도록 강요
  • timeout_sync
    • default value: 125
    • 태스크(큐)가 선택된 후 서비스되는 최대 시간 (ms 단위)

kyber

  • 빠른 멀티 큐 스토리지 장치를 대상으로 디자인
  • SSD나 고성능 스토리지 환경에서 CPU-bound 작업을 하는 경우에 적합
  • I/O 지연시간에 초점을 맞춘 스케줄러
    • 블록 I/O 레이어에 submit 된 모든 I/O의 지연시간을 계산하여 지연시간에 대한 목표를 달성할 수 있도록 조정하는 스케줄러
    • I/O 접근 요청의 도메인 별 지연시간 목표를 설정할 수 있음
  • 도메인 별 설정

kyber

  • 도메인 별 발생한 지연시간은 히스토그램으로 기록하여 계산에 사용

Configurable parameter

  • read_lat_nsec
    • default value: 2000000
    • read 지연시간 목표값
  • write_lat_nsec
    • default value: 10000000
    • write 지연시간 목표값

참고자료

  • [I/O schedulers] https://wiki.ubuntu.com/Kernel/Reference/IOSchedulers
  • [bfq] https://lwn.net/Articles/601799/
  • [kyber] https://lwn.net/Articles/720071/
  • [kyber] https://www.phoronix.com/news/Linux-4.12-BFQ-Kyber