헤드 오브 라인 블로킹

헤드 오브 라인 블로킹은 줄 맨 앞의 하나가 못 나가는 동안 뒤에 선 것들이 전부 같이 멈추는 고장입니다. 뒤엣것들은 나갈 준비를 이미 마쳤습니다. 앞엣것과 아무 상관도 없지만 앞이 풀릴 때까지 아무것도 못 합니다. 한 줄로 세워 순서를 지키는 곳이면 어디서든 납니다.

쉽고 빠른 이해

맨 앞이 막히면 뒤가 전부 서는 고장입니다. 한 차선짜리 도로에서 앞차가 멈추면 뒤차는 갈 길이 멀쩡해도 못 가는 것이 그런 경우입니다.

순서를 지켜 주려고 줄을 하나만 세웠기 때문에 생깁니다. 순서 보장은 받는 쪽의 일을 덜어 주는 대신, 앞엣것이 늦으면 그 늦음을 뒤가 같이 뒤집어씁니다.

이렇게 터집니다:

1. 서로 상관없는 것들이 한 줄에 같이 섭니다
2. 맨 앞의 하나가 곧바로 못 나갑니다
3. 뒤엣것들은 준비를 마쳤는데도 앞이 풀릴 때까지 못 나갑니다

막으려면 줄을 여럿으로 가르거나 순서 보장을 내줘야 합니다. 어느 쪽이든 받는 쪽이 할 일이 늘어납니다.

상세

이 고장은 줄 하나에 순서를 맡긴 곳이면 어디서든 납니다. 터지는 조건 셋을 세우고, 그 조건이 그대로 갖춰지는 연결 하나를 재료로 삼아 줄을 가르는 세 방법까지 봅니다.

무엇이 막히나

계산대가 하나뿐인 가게를 떠올려 봅시다. 값을 못 치르는 손님 한 명이 앞에 서면 뒤에 선 사람들은 카드만 대면 끝나는데도 다 같이 기다립니다. 줄이 하나라 앞질러 갈 길이 없기 때문입니다.

큐는 들어온 순서대로 하나씩 빼내는 대기 줄입니다. 먼저 들어온 것이 먼저 나간다는 규칙이 있어서, 줄 맨 앞의 하나가 곧 다음에 처리될 하나입니다.

헤드 오브 라인 블로킹은 그 맨 앞의 하나가 못 나가는 동안 뒤에 선 것들이 전부 멈추는 고장입니다. 이름은 줄 맨 앞을 뜻하는 HOL(head of line)에서 왔습니다. 줄여서 HOL 블로킹이라고도 부릅니다.

줄 하나를 세워 놓고 보면 이런 모양입니다.

flowchart TD
    subgraph 줄["줄"]
        R3["뒤 · 준비됨"] --> R2["뒤 · 준비됨"] --> R1["뒤 · 준비됨"] --> H["맨 앞 · 못 나감"]
    end
    H -.->|여기서 끊긴다| OUT["출구"]

뒤엣것은 갈 길이 멀쩡합니다. 그래도 앞이 풀릴 때까지 출구로 못 나갑니다.

막힌 쪽에는 오류가 안 남습니다. 요청은 받아들여졌습니다. 답도 오는 중입니다. 순서 때문에 못 올라갈 뿐이라 로그에는 실패 대신 늘어난 지연만 보입니다.

터지는 조건

셋이 모두 맞을 때만 납니다. 하나라도 빠지면 줄이 아무리 길고 앞엣것이 아무리 오래 걸려도 뒤가 같이 서지는 않습니다.

가운데 조건은 흔한 일입니다. 조각 하나가 오다 없어지거나 유난히 오래 걸리는 요청 하나가 앞에 서기만 해도 갖춰집니다. 이 고장을 가르는 것은 나머지 둘입니다. 줄이 하나라는 것과 뒤가 앞과 무관하다는 것이 없으면, 앞이 아무리 오래 걸려도 그냥 제 차례를 기다리는 것일 뿐입니다.

세 조건을 차례로 물으면 이렇게 갈립니다.

flowchart TD
    A["앞질러 갈 다른 줄이 있나"] -->|있다| N1["뒤는 그냥 나간다"]
    A -->|없다| B["맨 앞이 곧바로 나가나"]
    B -->|나간다| N2["줄이 흐른다"]
    B -->|못 나간다| C["뒤가 앞과 상관없이 준비됐나"]
    C -->|아니다| N3["어차피 기다릴 차례다"]
    C -->|그렇다| R["헤드 오브 라인 블로킹"]

세 갈림을 다 지나야 이 고장입니다. 막는 방법도 이 갈림을 거꾸로 밟습니다. 줄을 늘리거나, 맨 앞을 억지로 내보내거나 버립니다.

TCP 연결 하나에서 나는 막힘

제일 흔한 재현은 TCP(Transmission Control Protocol, 전송 제어 프로토콜) 연결입니다. TCP 는 보낸 순서 그대로 받게 해 주는 전송 규칙입니다.

중간 조각 하나가 없어지면 TCP 는 그 조각이 다시 올 때까지 뒤에 이미 도착한 조각을 위의 앱에 안 넘깁니다. 여기서 앱은 그 연결로 데이터를 받아 쓰는 프로그램을 말합니다. 순서를 지키려면 그 방법밖에 없습니다. 도착한 것을 먼저 올려 버리면 앱이 구멍 난 데이터를 받게 됩니다.

앞 조각이 사라지는 까닭은 여럿입니다. 중간 장비에 줄이 밀려 버려지기도 하고, 경로가 받아 주는 크기인 MTU(Maximum Transmission Unit, 최대 전송 단위)보다 커서 버려지기도 합니다. 어느 쪽이든 결과는 같습니다. 조각 하나가 없어지는 이 일을 패킷 손실이라고 부릅니다.

조각 넷 중 둘째가 사라지면 받는 쪽은 이것을 들고 있습니다.

block-beta
columns 4
  a["조각 1"] b["빠짐"] c["조각 3"] d["조각 4"]
  e["앱에 올라감"]:1 f["앱에 못 올라감"]:3

3 과 4 는 이미 받는 쪽 버퍼에 들어와 있습니다. 2 가 안 와서 못 올라갑니다. 2 가 재전송으로 다시 오는 순간 셋이 한꺼번에 올라갑니다.

그동안의 진행은 이렇게 갑니다.

sequenceDiagram
    participant S as 보내는 쪽
    participant T as 받는 쪽 TCP
    participant P as 받는 쪽 앱
    S->>T: 조각 1
    T->>P: 1 을 올린다
    S-xT: 조각 2 가 오다 사라진다
    S->>T: 조각 3 · 4
    Note over T,P: 2 가 올 때까지 3 · 4 를 안 올린다
    S->>T: 조각 2 를 다시 보낸다
    T->>P: 2 · 3 · 4 를 한꺼번에 올린다

3 과 4 는 제때 도착했습니다. 늦은 것은 2 하나입니다. 기다린 것은 셋입니다.

그래서 평균 응답 시간으로는 잘 안 보입니다. 오래 걸린 쪽 끝을 재는 꼬리 지연이 먼저 움직입니다.

통로를 여럿 둬도 남는다

웹에서 요청과 응답을 주고받는 규칙인 HTTP(HyperText Transfer Protocol, 하이퍼텍스트 전송 프로토콜)가 이 고장을 두 번 겪었습니다. 한 번은 응용 쪽 줄에서, 한 번은 그 아래 전송 쪽 줄에서 겪었습니다.

HTTP/1.1 은 한 연결로 요청을 하나씩 보내고 답을 받습니다. 요청을 답도 안 기다리고 연달아 밀어 넣는 파이프라이닝이라는 방법이 있었지만, 답은 보낸 순서대로 받아야 한다는 규칙이 남아 있었습니다. 앞 요청의 답이 오래 걸리면 뒤 요청의 답이 다 만들어져 있어도 못 나갔습니다.

HTTP/2 는 한 연결 안에 통로를 여럿 두어 응용 쪽의 이 줄을 없앴습니다. 그 통로를 스트림이라고 부르고, 한 연결에 스트림을 여럿 두어 요청을 겹쳐 보내는 방법을 멀티플렉싱이라고 부릅니다.

그런데 그 스트림들은 결국 TCP 연결 하나를 지납니다. 조각 하나가 사라지면 그것과 상관없는 스트림까지 같이 섰습니다. 응용 쪽에서 없앤 줄이 아래층에서 그대로 살아난 것입니다.

HTTP/3 은 그 아래를 QUIC 으로 바꿨습니다. QUIC 은 UDP(User Datagram Protocol, 사용자 데이터그램 프로토콜) 위에서 순서 맞추기와 재전송을 자기가 맡는 전송 규칙입니다. 순서 줄을 스트림마다 따로 두었기 때문에 한 스트림의 조각이 없어져도 다른 스트림은 계속 갑니다.

판마다 어느 층의 줄이 하나였는지를 맞대 보면 이렇습니다.

flowchart TD
    subgraph V1["HTTP/1.1"]
        A1["응용 쪽 · 줄 하나"] --> A2["전송 쪽 · 줄 하나"] --> A3["앞 요청이 늦으면 뒤도 선다"]
    end
    subgraph V2["HTTP/2"]
        B1["응용 쪽 · 스트림마다 줄"] --> B2["전송 쪽 · 줄 하나"] --> B3["조각 하나가 빠지면 다 선다"]
    end
    subgraph V3["HTTP/3"]
        C1["응용 쪽 · 스트림마다 줄"] --> C2["전송 쪽 · 스트림마다 줄"] --> C3["빠진 스트림만 선다"]
    end

막힘을 가르는 것은 스트림 수가 아니라 순서 줄의 수입니다. HTTP/2 는 스트림이 여럿이어도 전송 쪽 줄이 하나라 막힘이 번집니다. HTTP/3 은 그 줄까지 갈라서 막힘을 한 스트림 안에 가둡니다.

다만 같은 스트림 안에서는 여전히 순서를 지킵니다. 큰 파일 하나를 스트림 하나로 받는 중이라면 그 안의 막힘은 그대로 남습니다.

네트워크 밖에서도 난다

줄 하나에 순서를 맡기는 구조면 계층을 가리지 않고 같은 일이 납니다. 이름만 다를 뿐 모양이 같은 곳이 여럿입니다.

이 이름이 처음 쓰인 곳도 표의 첫 줄인 스위치입니다. 들어온 쪽마다 줄을 하나씩만 두면 맨 앞이 붐비는 출구를 향할 때 그 줄이 통째로 섭니다. 그 구조를 설명하려고 이 이름을 썼습니다.

그 스위치 한 입력의 줄만 떼어 보면 이렇습니다.

flowchart TD
    subgraph 입력["한 입력의 줄"]
        G2["뒤 프레임 · 출구 B 로 간다"] --> G1["맨 앞 프레임 · 출구 A 로 간다"]
    end
    G1 -.->|A 가 붐벼 못 간다| OA["출구 A · 붐빈다"]
    G2 -.->|앞이 막혀 못 간다| OB["출구 B · 한가하다"]

뒤 프레임이 갈 출구 B 는 한가합니다. 그래도 앞 프레임이 출구 A 를 못 뚫는 동안 같이 섭니다.

줄을 갈라 막는다

고칠 곳은 막힌 하나가 아니라 줄입니다. 방법은 셋입니다. 어느 것도 공짜가 아닙니다.

첫째가 제일 흔합니다. 연결을 여러 개 들고 돌려 쓰는 커넥션 풀, 데이터를 여러 덩이로 나눠 담는 샤딩, 한 스트림의 막힘을 그 스트림에 가두는 QUIC 이 전부 같은 수법입니다.

둘째는 순서가 애초에 필요 없을 때만 됩니다. 소리와 영상처럼 늦게 온 조각이 쓸모없어지는 데이터가 그렇습니다.

셋째는 타임아웃입니다. 앞엣것을 포기하면 뒤가 흐르지만 포기한 하나는 실패로 처리해야 합니다.

이 고장이 아닌 경우

줄 전체가 밀리는 것은 다른 고장입니다. 처리 능력이 모자라 모두가 같이 기다리는 것은 병목입니다. 이쪽은 줄을 갈라도 총량이 그대로라 안 풀립니다.

가르는 법은 하나입니다. 맨 앞의 하나를 치웠을 때 뒤가 바로 흐르면 헤드 오브 라인 블로킹입니다.

뒤가 앞의 결과를 써야 하는 경우도 아닙니다. 앞선 계산을 받아야 다음 계산을 하는 관계라면 기다리는 것이 맞습니다. 이때 뒤엣것은 준비를 마친 것이 아니라 아직 준비할 수가 없는 것이라, 앞의 조건 셋 가운데 셋째가 빠집니다.

한쪽만 계속 밀리는 기아와도 다릅니다. 기아는 차례를 고르는 규칙이 특정 흐름을 매번 뒤로 미뤄서 생깁니다. 헤드 오브 라인 블로킹은 규칙이 순서를 그대로 지키는데도 생깁니다. 밀리는 쪽이 정해져 있지 않다는 것이 갈림입니다.

관련 항목

이 막힘이 생기는 순서 보장 장치

TCP · 순서 보장 · 순서 번호 · 재전송 · 확인 응답 · 선택적 확인 응답 · 슬라이딩 윈도우 · 흐름 제어 · 신뢰성

이 막힘을 겪거나 비켜 간 프로토콜

HTTP · HTTP/2 · HTTP/3 · QUIC · UDP · SCTP · WebSocket · 파이프라이닝 · 멀티플렉싱

맨 앞을 못 나가게 만드는 원인

패킷 손실 · 혼잡 제어 · MTU · 재전송 타임아웃 · 지터 · 버퍼 블로트 · 백프레셔

이 막힘을 줄이려고 줄을 가르는 수단

커넥션 풀 · 도메인 샤딩 · 샤딩 · 파티션 · 가상 출력 큐 · 우선순위 큐 · 타임아웃

이 막힘이 드러나는 성능 지표

지연 · 꼬리 지연 · 처리량 · 응답 시간 · 큐 길이 · 대기 시간 · 병목

이 막힘과 나란히 나는 줄 고장

기아 · 데드락 · 라이브락 · 썬더링 허드 · 재시도 폭풍 · 캐스케이딩 장애

이 막힘이 나타나는 큐 구조

큐 · 선입선출 · 버퍼 · 메시지 큐 · 작업 큐 · 스레드 풀 · 이벤트 루프 · 프레임