파이프라이닝

파이프라이닝은 앞 일이 끝나기를 기다리지 않고 다음 일을 시작하는 방법입니다. 그렇게 여러 일을 겹쳐서 같은 시간에 더 많은 일을 끝냅니다. 통신에서는 답을 기다리지 않고 요청을 연달아 보내는 일을 이렇게 부릅니다. 프로세서에서는 명령어 처리를 여러 단계로 나눠 단계마다 다른 명령어를 동시에 다루는 일을 이렇게 부릅니다.

쉽고 빠른 이해

파이프라이닝은 기다리는 시간에 다음 일을 밀어 넣는 방법입니다. 서버에 요청 열 개를 보낼 때 답을 하나씩 기다리지 않고 열 개를 연달아 보내는 것이 그렇습니다.

이게 없으면 답이 오가는 동안 연결이 놉니다. 요청이 많을수록 그 기다림이 그만큼 쌓입니다.

어떻게 도나:

1. 일 하나를 여러 단계로 봅니다
2. 앞 일이 다음 단계로 넘어가면 비워진 단계가 곧바로 다음 일을 받습니다
3. 단계마다 서로 다른 일을 동시에 처리합니다

서로 기대지 않는 일이 많을 때 효과가 큽니다. 일 자체보다 기다림이 길 때 더 그렇습니다.

대가도 있습니다. 일 하나가 끝나는 시간은 줄지 않습니다. 앞 일이 늦으면 뒤 일이 다 되어 있어도 기다리는 줄서기가 생깁니다. 다음 일이 앞 일의 결과를 써야 하면 겹칠 수 없습니다.

상세

이 절은 빨래 비유로 시작해 통신과 프로세서를 차례로 봅니다. 끝으로 겹칠 수 없는 일과 겹쳐서 잃는 것을 봅니다.

빨랫감이 세 바구니 있습니다. 첫 바구니를 세탁기에 돌립니다. 다 되면 건조기로 옮깁니다. 건조기가 도는 동안 세탁기는 비어 있으니 둘째 바구니를 넣습니다. 세탁기와 건조기가 서로 다른 바구니를 맡아 함께 돌아갑니다.

노는 단계를 다음 일로 채우기

빨래에서 세탁기와 건조기가 단계입니다. 바구니 하나하나가 일입니다. 이제 이 둘을 숫자로 옮겨 봅니다.

일 하나가 단계 셋을 거친다고 해 봅니다. 단계마다 1초가 걸리고 일은 A·B·C·D 넷입니다. 한 일을 끝까지 마친 뒤에 다음 일을 시작하면 일 하나에 3초, 넷이면 12초가 듭니다. 그동안 한 단계가 일하면 나머지 두 단계는 놉니다.

파이프라이닝은 이 노는 시간에 다음 일을 밀어 넣습니다. A 가 둘째 단계로 넘어가는 순간 첫째 단계는 비고, 거기에 B 가 들어갑니다. 아래 표는 초마다 어느 단계가 어느 일을 맡고 있는지 보입니다.

표를 대각선으로 읽으면 일 하나가 지나간 길이 보입니다. A 는 3초에 끝납니다. 그 뒤로 B·C·D 가 1초마다 하나씩 끝납니다. 넷이 다 끝나는 데 12초가 아니라 6초가 걸렸습니다.

단계 수를 k, 일의 수를 n 이라 하면 차례로 할 때는 n × k 단계 시간이 듭니다. 겹치면 k + n − 1 단계 시간이면 끝납니다. 일이 많아질수록 한 단계 시간마다 일 하나씩 끝나는 속도에 가까워집니다.

처리량과 지연

겹쳐도 A 하나가 시작부터 끝까지 걸린 시간은 3초로 같습니다. 달라진 것은 같은 시간 안에 끝나는 일의 수입니다. 이 둘을 따로 부르는 이름이 있습니다.

처리량은 정해진 시간 안에 끝내는 일의 수입니다. 지연은 일 하나가 시작부터 끝까지 걸리는 시간입니다. 파이프라이닝은 처리량을 올리는 방법입니다. 일 하나의 지연을 줄이는 방법이 아닙니다.

단계마다 걸리는 시간이 다르면 시간이 가장 오래 걸리는 단계가 전체 속도를 정합니다. 빨리 끝낸 단계는 다음 단계가 비어야 일을 넘길 수 있습니다. 그때까지 손을 놓고 기다립니다. 그래서 파이프라이닝을 설계할 때는 단계를 되도록 고른 길이로 나눕니다.

파이프라인과 병렬성

파이프라인은 처리를 여러 단계로 나누고 앞 단계의 출력을 다음 단계의 입력으로 이어 붙인 구조입니다. 파이프라이닝은 그 단계들을 서로 다른 일로 동시에 채워 돌리는 방법입니다. 단계가 나뉘어 있어도 한 번에 일 하나만 흘려보내면 파이프라이닝이 아닙니다.

병렬성은 여러 일을 같은 시각에 함께 처리하는 것입니다. 파이프라이닝에서도 여러 단계가 같은 시각에 일합니다. 그래서 파이프라이닝은 병렬성의 한 갈래입니다.

병렬성의 다른 갈래와 견주면 차이가 보입니다. 데이터 병렬성은 같은 작업을 데이터 조각마다 여럿이 나눠 맡습니다. 파이프라이닝은 단계마다 맡는 작업이 다릅니다. 일이 그 단계들을 차례로 지나갑니다.

요청 파이프라이닝

통신에서 요청 하나는 세 구간을 지납니다. 요청이 서버까지 가는 길, 서버가 처리하는 시간, 답이 돌아오는 길입니다. 요청 하나를 보내고 답이 올 때까지 기다리면 그 사이 연결은 비어 있습니다.

그 기다림에서 오가는 길에 드는 시간이 RTT(Round-Trip Time, 왕복 시간)입니다. 요청이 가는 길과 답이 돌아오는 길을 더한 시간입니다. 서버가 처리하는 시간은 넣지 않습니다. 요청 열 개를 하나씩 주고받으면 서버 처리 시간을 빼고도 RTT 의 열 배가 듭니다.

먼저 답을 기다리는 방식을 그리면 이렇습니다.

sequenceDiagram
    participant 클 as 클라이언트
    participant 서 as 서버
    클->>서: 요청 1
    서-->>클: 응답 1
    클->>서: 요청 2
    서-->>클: 응답 2
    클->>서: 요청 3
    서-->>클: 응답 3

요청 하나마다 왕복이 한 번씩 붙습니다. 아래 그림은 같은 세 요청을 파이프라이닝으로 보낸 것입니다.

sequenceDiagram
    participant 클 as 클라이언트
    participant 서 as 서버
    클->>서: 요청 1
    클->>서: 요청 2
    클->>서: 요청 3
    서-->>클: 응답 1
    서-->>클: 응답 2
    서-->>클: 응답 3

클라이언트는 세 요청을 연달아 보내고 답을 몰아서 받습니다. 왕복은 사실상 한 번으로 줄어듭니다. 앞의 열 개짜리 예라면 서버 처리 시간을 빼고 왕복 한 번 남짓이면 끝납니다.

이렇게 하려면 클라이언트가 어느 답이 어느 요청의 것인지 가릴 수 있어야 합니다. 답에 몇 번째 요청의 것인지 적는 칸이 없으면 서버는 받은 순서대로 답해야 합니다. 클라이언트는 첫 답을 첫 요청의 것으로, 둘째 답을 둘째 요청의 것으로 읽습니다.

HTTP/1.1 의 줄서기

HTTP(HyperText Transfer Protocol, 하이퍼텍스트 전송 프로토콜)는 웹에서 요청과 응답을 주고받는 규칙입니다. 이 절은 그 가운데 HTTP/1.1 을 봅니다.

HTTP/1.1 은 연결 하나를 열어 두고 여러 요청에 다시 쓰는 것을 기본으로 삼습니다. 이것이 지속 연결입니다. 요청마다 연결을 새로 여는 비용을 아끼려는 것입니다. 그 연결 위에서 요청을 파이프라이닝으로 보내는 것도 허용합니다.

HTTP/1.1 의 응답에는 그 칸이 없습니다. 그래서 서버는 받은 순서대로 답해야 합니다. 앞 요청의 처리가 오래 걸리면 뒤 요청의 응답은 다 만들어 놓고도 못 나갑니다.

sequenceDiagram
    participant 브 as 브라우저
    participant 서 as 서버
    브->>서: 큰 그림을 달라
    브->>서: 작은 아이콘을 달라
    Note over 서: 아이콘 응답은 먼저 준비됐다
    서-->>브: 큰 그림
    서-->>브: 작은 아이콘

줄 맨 앞의 것이 안 나가서 뒤가 전부 서는 이 현상을 헤드 오브 라인 블로킹이라고 부릅니다. 그림에서 아이콘 응답은 먼저 준비됐지만 큰 그림 응답이 다 나갈 때까지 기다립니다.

실패도 다루기 어렵습니다. 요청 셋을 보낸 뒤 연결이 끊기면 서버가 어디까지 처리했는지 클라이언트는 알기 어렵습니다. 다시 보내도 결과가 같은 요청, 곧 멱등성이 있는 요청이 아니면 함부로 다시 보낼 수 없습니다.

이런 까닭에 브라우저는 대개 HTTP/1.1 파이프라이닝을 쓰지 않았습니다. 대신 서버 하나에 연결을 여러 개 열어 요청을 나눠 보냈습니다.

순서를 푸는 멀티플렉싱

HTTP/2 는 한 연결 안에 스트림을 여럿 엽니다. 스트림은 요청 하나와 그 응답이 오가는 논리적 통로입니다. 스트림마다 번호가 붙습니다. 응답에도 같은 번호가 붙으므로 서버는 먼저 준비된 응답부터 보낼 수 있습니다.

여러 스트림의 요청과 응답은 조각으로 나뉘어 한 연결 안에서 섞여 오갑니다. 받는 쪽은 번호를 보고 조각을 다시 모읍니다. 이것이 멀티플렉싱입니다. 파이프라이닝에서 「답을 기다리지 않고 보낸다」는 살리고 「받은 순서대로 답한다」는 뗀 방법입니다.

그래도 헤드 오브 라인 블로킹이 다 사라지지는 않습니다. HTTP/2 는 TCP(Transmission Control Protocol, 전송 제어 프로토콜) 위에서 동작합니다. TCP 는 보낸 바이트를 보낸 순서 그대로 받는 쪽에 건네는 전송 규칙입니다. 그래서 앞 조각 하나를 잃으면 그 조각이 다시 올 때까지 다른 스트림의 조각까지 전부 기다립니다.

명령 파이프라이닝과 배치

데이터베이스나 캐시 서버의 클라이언트에도 같은 방법이 있습니다. 명령 여러 개를 답을 기다리지 않고 보내 놓고 답을 몰아서 읽습니다. 키 백 개를 하나씩 읽을 때 드는 왕복 백 번이 거의 한 번으로 줄어듭니다. Redis 같은 키-값 저장소가 이 방법을 흔히 씁니다.

배치와는 묶는 단위가 다릅니다. 배치는 여러 일을 요청 하나에 담아 한 번에 보냅니다. 명령 파이프라이닝은 명령을 하나하나 따로 둡니다. 없애는 것은 기다림뿐입니다. 그래서 명령마다 제 답이 따로 돌아옵니다.

파이프라이닝으로 보낸 명령들은 한꺼번에 실행된다는 보장이 없습니다. 명령 사이에 다른 클라이언트의 명령이 끼어들 수 있습니다. 여러 명령이 전부 되거나 전부 안 되는 성질, 곧 원자성이 필요하면 트랜잭션처럼 따로 마련된 수단을 씁니다.

전송 계층의 파이프라이닝

TCP 처럼 데이터를 패킷으로 나눠 나르는 규칙들을 묶어 전송 계층이라고 합니다. 여기에도 같은 선택이 있습니다. 받는 쪽은 패킷을 잘 받았다고 확인 응답을 돌려보냅니다. 보내는 쪽은 이 답을 보고 패킷이 닿았는지 압니다.

패킷 하나를 보내고 확인 응답을 기다린 뒤 다음을 보내는 방식이 정지 대기입니다. 요청마다 답을 기다리는 앞의 방식과 같은 꼴이라 왕복마다 연결이 놉니다.

파이프라이닝 방식은 확인 응답을 기다리지 않고 여러 패킷을 먼저 내보냅니다. 이때 확인 응답을 아직 못 받은 패킷 번호의 구간에 길이 상한을 둡니다. 앞쪽 패킷의 확인 응답이 오면 그 구간을 뒤 번호 쪽으로 옮깁니다. 이 방법이 슬라이딩 윈도입니다.

중간 패킷을 잃었을 때 무엇을 다시 보내느냐로 두 갈래가 나뉩니다. Go-Back-N 은 잃은 패킷부터 그 뒤를 전부 다시 보냅니다. 선택적 반복은 잃은 패킷만 다시 보냅니다.

명령어 파이프라이닝

CPU(Central Processing Unit, 중앙 처리 장치)는 프로그램의 명령어를 하나씩 읽어 실행하는 부품입니다. CPU 는 클럭 사이클이라는 일정한 박자에 맞춰 일합니다. 박자 한 번이 사이클 하나입니다.

명령어 하나를 처리하는 일도 여러 단계로 나뉩니다. 단계는 명령어 처리를 나눈 조각입니다. 단계 하나는 한 사이클에 끝나도록 나눕니다. 명령어 처리는 흔히 다섯 단계로 나눠 설명합니다.

표에 나오는 레지스터는 CPU 안에 있는 작은 저장 칸입니다. 메모리까지 가지 않고 곧바로 읽고 씁니다. 계산에 쓸 값과 계산한 결과를 여기에 둡니다.

단계마다 한 사이클이 걸리므로 명령어 하나는 다섯 사이클 만에 끝납니다. 차례로 하면 명령어 열 개에 쉰 사이클이 듭니다. 앞의 A·B·C·D 표에서 단계가 셋이던 것이 다섯이 된 것과 같습니다.

파이프라이닝을 하면 첫 명령어가 해독으로 넘어가는 사이클에 둘째 명령어의 인출이 시작됩니다. 다섯 단계가 모두 차고 나면 사이클마다 명령어 하나씩 끝납니다. 명령어 하나의 지연은 여전히 다섯 사이클이지만 처리량은 다섯 배 가까이 오릅니다.

파이프라인을 멈추게 하는 해저드

다음 명령어를 다음 사이클에 시작할 수 없는 상황이 해저드입니다. 다음 명령어가 앞 명령어의 계산 결과를 곧바로 써야 할 때가 그렇습니다.

해저드가 생기면 파이프라인은 한두 사이클을 비워 둔 채 기다립니다. 이렇게 멈추는 것이 파이프라인 스톨입니다. 비워 둔 사이클은 빈 채로 단계를 따라 흘러가므로 버블이라고도 합니다.

해저드는 원인에 따라 셋으로 나뉩니다. 아래 표는 무엇이 다음 명령어를 막는지와 흔히 쓰는 대응을 견줍니다.

분기 예측이 틀리면 짐작해서 미리 시작한 명령어를 전부 버리고 맞는 곳에서 다시 인출합니다. 단계 수가 많을수록 버리는 양이 많아집니다.

겹칠 수 없는 일

통신과 프로세서에서 파이프라이닝을 막는 원인은 같습니다. 다음 일이 앞 일의 결과를 써야 하면 앞 일이 끝나기 전에는 다음 일을 시작할 수 없습니다. 프로세서의 데이터 해저드가 이것입니다.

통신에서도 마찬가지입니다. 첫 요청의 답으로 받은 주문 번호를 넣어야 둘째 요청을 만들 수 있다면 둘째 요청은 첫 답을 기다려야 합니다. 이런 요청들은 파이프라이닝으로 겹칠 수 없습니다.

그래서 파이프라이닝은 서로 기대지 않는 작은 일이 많을 때 효과가 큽니다. 일 자체보다 기다림이 길 때도 그렇습니다. 반대로 일이 몇 개 안 되면 얻는 것이 적습니다. 일마다 앞 일의 결과에 기댈 때와 일 하나의 지연을 줄이는 것이 목표일 때도 마찬가지입니다.

겹쳐서 잃는 것

파이프라이닝은 처리량을 얻는 대신 몇 가지를 내줍니다. 아래 표는 통신과 프로세서에서 각각 무엇을 내주는지 견줍니다.

관련 항목

파이프라이닝이 속하는 상위 개념

병렬성 · 동시성 · 데이터 병렬성 · 명령어 수준 병렬성 · 파이프라인

파이프라이닝이 올리고 줄이는 지표

처리량 · 지연 · 왕복 시간 · 꼬리 지연

요청 파이프라이닝을 허용하는 프로토콜과 제품

HTTP · HTTP/1.1 · 지속 연결 · Keep-Alive · SMTP · IMAP · Redis

요청 파이프라이닝을 대신하는 수단

멀티플렉싱 · HTTP/2 · HTTP/3 · QUIC · 스트림 · 커넥션 풀 · 도메인 샤딩 · 배치 처리

요청 파이프라이닝의 안전을 가르는 성질

멱등성 · 원자성 · 트랜잭션 · 재시도

파이프라이닝에서 생기는 막힘

헤드 오브 라인 블로킹 · 해저드 · 데이터 해저드 · 제어 해저드 · 구조 해저드 · 파이프라인 스톨

명령어 파이프라인을 이루는 구성 요소

CPU · 클럭 사이클 · 레지스터 · 명령어 인출 · 명령어 해독 · 파이프라인 레지스터

명령어 파이프라인의 멈춤을 줄이는 기법

포워딩 · 분기 예측 · 비순차 실행 · 추측 실행 · 슈퍼스칼라

전송 계층에서 파이프라이닝을 구현하는 방식

슬라이딩 윈도 · 정지 대기 · Go-Back-N · 선택적 반복 · 확인 응답 · TCP