디스크 스케줄링과 I/O 최적화

하드 디스크는 기계 장치입니다. 데이터를 읽으려면 헤드가 원하는 위치까지 물리적으로 움직이고, 원판이 돌아 데이터가 헤드 아래로 와야 합니다. 그래서 여러 프로세스가 동시에 디스크를 쓰려 할 때, 요청을 어떤 순서로 처리하느냐에 따라 성능이 크게 달라집니다. 이 글에서는 HDD의 접근 시간이 어디서 오는지 계산해 보고, 요청의 순서를 정하는 디스크 스케줄링 알고리즘을 비교한 뒤, SSD가 바꾼 것과 Linux에서 쓰는 I/O 최적화 방법을 살펴봅니다.

HDD의 구조와 접근 시간

HDD는 빠르게 도는 원판인 플래터(platter) 위를 헤드(head)가 오가며 데이터를 읽고 씁니다. 플래터 위의 동심원 하나를 트랙(track), 트랙을 나눈 가장 작은 기록 단위를 섹터(sector)라고 합니다. 섹터는 전통적으로 512바이트였고, 요즘 디스크는 4KiB 섹터를 씁니다. 여러 플래터에서 반지름이 같은 트랙들을 모은 것을 실린더(cylinder)라고 하며, 같은 실린더 안에서는 헤드를 움직이지 않고 읽을 수 있습니다.

운영체제는 디스크를 0번부터 이어지는 논리 블록 번호(LBA)로 다루고, 그것이 어느 트랙과 섹터에 놓이는지는 디스크 컨트롤러가 정합니다. 다만 번호가 가까운 블록은 대개 물리적으로도 가까이 있어서, 운영체제는 블록 번호의 차이를 헤드 이동 거리처럼 다룹니다.

디스크에서 블록 하나를 읽는 시간은 세 부분으로 나뉩니다.

다음 코드는 회전 속도와 평균 탐색 시간을 가정해 임의 위치를 한 번 읽는 데 걸리는 시간과, 초당 몇 번 읽을 수 있는지를 계산합니다.

# (회전 속도, 평균 탐색 시간으로 가정한 값 ms)
drives = [(5400, 12.0), (7200, 8.5), (15000, 3.5)]
TRANSFER_MS = 0.03                       # 4KiB를 읽어 내는 시간(약 150MB/s 가정)

for rpm, seek in drives:
    rotation = 60_000 / rpm / 2          # 평균 회전 지연은 반 바퀴
    access = seek + rotation + TRANSFER_MS
    print(f"{rpm:>5} RPM: 평균 회전 지연 {rotation:.2f}ms, 임의 읽기 한 번 {access:.2f}ms,"
          f" 초당 약 {1000 / access:.0f}회")

 5400 RPM: 평균 회전 지연 5.56ms, 임의 읽기 한 번 17.59ms, 초당 약 57회
 7200 RPM: 평균 회전 지연 4.17ms, 임의 읽기 한 번 12.70ms, 초당 약 79회
15000 RPM: 평균 회전 지연 2.00ms, 임의 읽기 한 번 5.53ms, 초당 약 181회

임의 읽기 시간의 거의 전부가 탐색과 회전이고, 데이터를 실제로 읽는 시간은 1%도 되지 않습니다. 그래서 HDD는 임의 위치를 초당 100번 안팎밖에 읽지 못하지만, 이어진 데이터를 순서대로 읽으면 초당 수백 MB를 읽습니다. 디스크 스케줄링은 이 중 탐색 시간을 줄이려는 것입니다.

디스크 스케줄링 알고리즘

트랙이 0번부터 199번까지 있는 디스크에서 헤드가 53번에 있고, 요청 큐에 [98, 183, 37, 122, 14, 124, 65, 67]이 이 순서로 들어와 있다고 합시다. 여섯 가지 알고리즘으로 이 요청들을 처리해 보고, 헤드가 움직인 거리를 비교합니다.

FCFS와 SSTF

FCFS(first-come, first-served)는 요청이 들어온 순서대로 처리합니다. 공평하지만 순서가 위치와 상관없으므로, 이 큐에서는 헤드가 98, 183, 37로 디스크를 가로지르며 오갑니다.

SSTF(shortest seek time first)는 지금 헤드 위치에서 가장 가까운 요청을 먼저 처리합니다. 53에서는 12만큼 떨어진 65가 가장 가깝고, 65에서는 67이 가깝습니다. 67에서는 37까지 30이 98까지 31보다 가까우므로 37로 갑니다. 이렇게 매번 현재 위치에서 다시 비교하므로, 처음에 한 번 정렬해 두는 방식과는 다릅니다. CPU 스케줄링의 SJF처럼 매 순간의 이동은 짧지만, 헤드 근처에 요청이 계속 들어오면 멀리 있는 요청은 끝없이 밀리는 기아(starvation)가 생길 수 있습니다.

SCAN과 LOOK

SCAN은 엘리베이터처럼 헤드가 한쪽 끝까지 가면서 지나는 길의 요청을 모두 처리하고, 끝에 이르면 방향을 바꿉니다. 헤드가 정해진 방향으로 디스크 전체를 쓸고 지나가므로, 어느 요청이든 늦어도 왕복 한 번 안에는 처리되어 기아가 생기지 않습니다. LOOK은 SCAN을 고친 것으로, 디스크의 끝까지 가지 않고 그 방향의 마지막 요청에서 방향을 바꿉니다.

C-SCAN과 C-LOOK

SCAN에서는 방향을 바꾼 직후 지나는 영역이 방금 처리한 곳이라 요청이 적고, 반대쪽 끝의 요청들이 오래 기다립니다. 가운데 트랙은 왕복할 때마다 두 번 지나가지만 양 끝은 한 번만 지나가기 때문입니다. C-SCAN(circular SCAN)은 한 방향으로만 처리하고, 끝에 이르면 요청을 처리하지 않고 반대쪽 끝으로 돌아가 같은 방향으로 다시 시작합니다. 이동 거리는 늘지만 위치에 따른 대기 시간의 차이가 줄어듭니다. C-LOOK은 C-SCAN을 LOOK처럼 고친 것으로, 마지막 요청에서 가장 안쪽의 요청으로 바로 돌아갑니다.

시뮬레이션으로 비교하기

다음 코드는 여섯 알고리즘으로 같은 큐를 처리합니다. 엘리베이터 계열은 모두 번호가 커지는 쪽으로 먼저 움직이고, C-SCAN과 C-LOOK이 처음으로 돌아가는 거리도 이동 거리에 넣었습니다. 경로에 나오는 199와 0은 요청이 아니라 디스크의 양 끝입니다.

REQUESTS = [98, 183, 37, 122, 14, 124, 65, 67]
HEAD, MAX_TRACK = 53, 199

def fcfs(reqs, head):
    return list(reqs)

def sstf(reqs, head):
    pending, order, pos = list(reqs), [], head
    while pending:
        nearest = min(pending, key=lambda t: abs(t - pos))   # 지금 위치에서 가장 가까운 요청
        pending.remove(nearest)
        order.append(nearest)
        pos = nearest
    return order

def split(reqs, head):
    up = sorted(t for t in reqs if t >= head)                 # 헤드보다 바깥쪽(번호가 큰 쪽)
    down = sorted(t for t in reqs if t < head)                # 헤드보다 안쪽
    return up, down

def scan(reqs, head):        # 끝 트랙까지 간 뒤 방향을 바꾼다
    up, down = split(reqs, head)
    return up + [MAX_TRACK] + down[::-1]

def look(reqs, head):        # 마지막 요청에서 방향을 바꾼다
    up, down = split(reqs, head)
    return up + down[::-1]

def c_scan(reqs, head):      # 끝 트랙까지 간 뒤 0번으로 돌아가 같은 방향으로
    up, down = split(reqs, head)
    return up + [MAX_TRACK, 0] + down

def c_look(reqs, head):      # 마지막 요청 뒤 가장 안쪽 요청으로 돌아가 같은 방향으로
    up, down = split(reqs, head)
    return up + down

def distance(path, head):
    total, pos = 0, head
    for track in path:
        total += abs(track - pos)
        pos = track
    return total

for name, policy in [("FCFS", fcfs), ("SSTF", sstf), ("SCAN", scan),
                     ("LOOK", look), ("C-SCAN", c_scan), ("C-LOOK", c_look)]:
    path = policy(REQUESTS, HEAD)
    print(f"{name:<6} 이동 {distance(path, HEAD):>3}: {path}")

FCFS   이동 640: [98, 183, 37, 122, 14, 124, 65, 67]
SSTF   이동 236: [65, 67, 37, 14, 98, 122, 124, 183]
SCAN   이동 331: [65, 67, 98, 122, 124, 183, 199, 37, 14]
LOOK   이동 299: [65, 67, 98, 122, 124, 183, 37, 14]
C-SCAN 이동 382: [65, 67, 98, 122, 124, 183, 199, 0, 14, 37]
C-LOOK 이동 322: [65, 67, 98, 122, 124, 183, 14, 37]

그림은 이 가운데 FCFS, SSTF, C-LOOK의 누적 거리를 단계별로 보여 줍니다. 이 큐에서는 SSTF가 가장 적게 움직였지만, SSTF가 언제나 최소 거리를 보장하는 것은 아닙니다. 매 순간 가장 가까운 요청을 고르는 탐욕적인 방법이어서, 전체로 보면 더 짧은 순서가 있을 수 있습니다. LOOK은 SCAN보다, C-LOOK은 C-SCAN보다 끝까지 가는 거리만큼 덜 움직였습니다.

이동 거리만으로 알고리즘을 고르면 안 됩니다. 이 비교는 요청이 처음에 한꺼번에 들어와 있고 새 요청이 없다는 가정 아래의 결과입니다. 실제로는 요청이 계속 들어오므로, 각 요청이 얼마나 기다리는지, 오래 기다리는 요청이 생기지 않는지도 함께 보아야 합니다. SSTF는 평균 이동이 짧지만 기아가 생길 수 있고, SCAN 계열은 조금 더 움직이는 대신 모든 요청이 정해진 시간 안에 처리됩니다.

SSD가 바꾼 것

SSD는 NAND 플래시 메모리에 데이터를 저장하므로 움직이는 부품이 없고, 탐색 시간과 회전 지연도 없습니다. 다음 표는 제품마다 다른 성능을 대략적인 크기로 비교한 것입니다.

SSD에서는 블록 번호가 가깝든 멀든 접근 시간이 거의 같으므로, 헤드 이동을 줄이려는 디스크 스케줄링은 의미가 크게 줄어듭니다. SSD의 지연은 앞 장에서 본 가비지 컬렉션이나 내부 캐시, 동시에 처리 중인 요청의 수에 따라 달라집니다.

NVMe는 SSD를 PCIe 버스에 바로 연결하기 위한 규격입니다. 하드 디스크 시절에 만든 SATA는 명령 큐가 하나뿐이고 큐에 명령을 32개까지 담지만, NVMe는 제출 큐와 완료 큐의 쌍을 여러 개 두고 큐마다 많은 명령을 담을 수 있습니다. Linux는 CPU마다 큐를 하나씩 배정해, 여러 CPU가 서로 잠금 없이 동시에 요청을 넣게 합니다. 초당 처리하는 I/O 요청 수, 곧 IOPS(I/O operations per second)가 수십만에 이르는 장치에서는 요청의 순서를 고르는 것보다 이렇게 요청을 막힘 없이 넣는 것이 중요합니다.

Linux의 I/O 스케줄러

Linux의 블록 계층은 장치마다 I/O 스케줄러를 고를 수 있게 합니다. 지금의 블록 계층(blk-mq)에서 쓸 수 있는 스케줄러는 다음과 같습니다.

mq-deadline은 요청마다 만료 시각을 두며, 기본값은 읽기 500ms, 쓰기 5초입니다. 만료된 요청이 있으면 정렬 순서보다 그 요청을 먼저 처리해 기아를 막습니다. 다만 커널 소스의 주석대로 이 시각은 목표일 뿐이어서, 장치가 그 안에 요청을 끝낸다는 보장은 아닙니다. 예전에 쓰이던 CFQ와 noop 같은 스케줄러는 Linux 5.0에서 옛 블록 계층과 함께 제거되었습니다. 자세한 구조는 blk-mq 문서에 있습니다.

cat /sys/block/sda/queue/scheduler                        # 쓸 수 있는 것들 가운데 [ ] 안이 현재 스케줄러
echo none | sudo tee /sys/block/nvme0n1/queue/scheduler   # NVMe SSD를 none으로
echo mq-deadline | sudo tee /sys/block/sda/queue/scheduler
iostat -xz 1 5                                            # 장치별 대기 시간, 처리량, 사용률

장치 이름은 시스템마다 다르므로 lsblk로 먼저 확인합니다. iostat의 r_await와 w_await는 요청이 큐에서 기다린 시간까지 포함한 평균 응답 시간입니다. %util은 장치가 바빴던 시간의 비율인데, iostat(1)에 적힌 대로 SSD처럼 요청을 병렬로 처리하는 장치에서는 100%라도 성능의 한계에 이르렀다는 뜻이 아닙니다.

I/O를 줄이는 실무 기법

제로 카피

웹 서버가 파일을 읽어 네트워크로 보내는 일을 read()와 write()로 하면, 데이터는 페이지 캐시에서 사용자 버퍼로 복사되었다가 다시 커널의 소켓 버퍼로 복사됩니다. 데이터를 손대지 않고 그대로 보낼 뿐인데도 사용자 공간을 거치는 복사가 두 번 생기고, 시스템 콜도 두 번 필요합니다.

sendfile(2)은 파일의 데이터를 커널 안에서 바로 소켓으로 보내, 사용자 공간을 거치는 복사를 없앱니다. 네트워크 카드가 지원하면 페이지 캐시에서 카드로 DMA가 바로 일어나 CPU의 복사가 더 줄어듭니다. 이렇게 CPU의 복사를 줄이는 기법을 제로 카피(zero-copy)라고 하며, nginx의 sendfile 설정이나 Kafka가 로그를 소비자에게 보낼 때 이 방식을 씁니다.

더 깊이: 사용자 버퍼를 그대로 보내는 MSG_ZEROCOPY

sendfile()의 입력은 mmap()처럼 다룰 수 있는 파일이어야 하므로, 프로그램이 메모리에서 만든 데이터를 보낼 때는 쓸 수 없습니다. 이런 경우를 위해 Linux에는 send()에 MSG_ZEROCOPY 플래그를 주는 방법이 있으며, MSG_ZEROCOPY 문서에 따르면 TCP, UDP, VSOCK 소켓에서 쓸 수 있습니다. 커널은 send()에 넘긴 모르는 플래그를 그냥 무시해 왔으므로, 이 플래그를 이미 실수로 넘기던 옛 프로그램에서 제로 카피가 켜지지 않도록 먼저 SO_ZEROCOPY 소켓 옵션으로 쓰겠다는 뜻을 밝혀야 합니다.

이 방식도 공짜는 아닙니다. 커널은 사용자 버퍼를 복사하는 대신 그 페이지를 네트워크 스택과 잠시 함께 쓰므로, 호출이 돌아온 뒤에도 프로그램은 버퍼를 바로 고칠 수 없습니다. 버퍼를 다시 써도 된다는 완료 알림은 소켓의 오류 큐에 쌓이고, 프로그램은 recvmsg()에 MSG_ERRQUEUE를 주어 이를 읽습니다. 문서는 바이트마다 드는 복사 비용이 페이지 관리와 완료 알림의 비용으로 바뀌는 것이어서, 대개 10KB 정도보다 큰 쓰기에서만 효과가 있다고 설명합니다.

요청 병합과 묶어 쓰기

블록 계층은 이웃한 블록에 대한 요청들을 하나로 합칩니다. 4KiB 요청 네 개가 이어진 블록을 가리킨다면 16KiB 요청 하나로 만들어, 장치에 보내는 명령의 수와 HDD의 탐색 횟수를 줄입니다. 응용 프로그램도 작은 쓰기를 모아 큰 쓰기로 보내면 시스템 콜과 장치 명령이 줄어듭니다. 데이터베이스가 로그를 모아서 한 번에 쓰고 fsync()하는 그룹 커밋(group commit)이 그 예입니다.

ionice

ionice는 프로세스의 I/O 우선순위를 정합니다. 우선순위는 실시간(realtime), 최선(best-effort), 유휴(idle)의 세 클래스로 나뉘고, 최선 클래스 안에서는 0부터 7까지의 단계가 있어 숫자가 작을수록 우선입니다. 백업처럼 급하지 않은 작업을 유휴 클래스로 돌리면, 다른 프로세스가 디스크를 쓰지 않을 때만 디스크를 씁니다. 우선순위가 실제로 반영되는지는 쓰고 있는 I/O 스케줄러에 따라 다르며, BFQ는 이를 반영합니다.

ionice -c 3 rsync -a /data /backup              # 유휴 클래스로 백업
sudo ionice -c 2 -n 0 -p "$(pidof mysqld)"      # 실행 중인 DB 프로세스를 최선 클래스의 가장 높은 단계로
ionice -p "$(pidof mysqld)"                     # 현재 I/O 우선순위 확인

정리

• HDD의 임의 읽기 시간은 대부분 탐색 시간과 회전 지연이어서, 7200RPM 디스크는 임의 위치를 초당 100번 안팎밖에 읽지 못합니다.
• FCFS는 공평하지만 헤드가 많이 움직이고, SSTF는 이동이 짧지만 기아가 생길 수 있습니다. SCAN과 LOOK은 엘리베이터처럼 한 방향으로 쓸고 지나가며, C-SCAN과 C-LOOK은 한 방향으로만 처리해 대기 시간의 차이를 줄입니다.
• 알고리즘은 이동 거리뿐 아니라 요청이 계속 들어올 때의 대기 시간과 공평함으로도 비교해야 합니다.
• SSD에는 탐색과 회전이 없어 디스크 스케줄링의 의미가 줄고, NVMe는 큐를 여러 개 두어 병렬로 요청을 넣는 데 집중합니다.
• Linux에서는 장치마다 none, mq-deadline, bfq, kyber 가운데 스케줄러를 고르며, 제로 카피, 요청 병합, ionice로 I/O 비용과 간섭을 줄입니다.

연습 문제

1. 작은 큐로 비교하기

트랙이 0번부터 99번까지 있고 헤드가 50번에 있으며, 요청 큐가 [40, 60]입니다. SSTF, 번호가 커지는 쪽으로 먼저 가는 C-LOOK, 같은 방향의 SCAN으로 처리할 때의 방문 순서와 이동 거리를 구하세요. SSTF에서 두 요청까지의 거리가 같다면 어떻게 정해야 할까요?

2. SSTF의 기아

헤드가 50번 근처에서 일하는 동안, 다른 프로세스들이 45번에서 55번 사이의 블록을 쉬지 않고 요청합니다. 190번 트랙에 요청을 넣은 프로세스는 SSTF와 SCAN에서 각각 어떻게 되나요?

3. 스케줄러 고르기

같은 서버에 7200RPM HDD 하나와 NVMe SSD 하나가 있습니다. 각 장치에 어떤 I/O 스케줄러가 어울리는지 이유와 함께 고르세요. NVMe SSD의 iostat 결과에서 %util이 100%로 나온다면 장치가 한계에 이르렀다고 볼 수 있나요?

다음 장의 보호의 원리에서는 운영체제가 프로세스와 사용자 사이에서 자원을 보호하는 원리와, 누가 무엇을 할 수 있는지 표현하는 방법을 살펴봅니다.