Hammer's Blog

스케줄링: 네트워크, SQS, HTTP/2

스케쥴링이 쓰이는 다른 분야는?

Network Scheduling

네트워크 스케쥴링은 기본적으로 전송되어야 할 패킷의 전송 순서와 전송 속도를 제한하거나 폐기하는 것을 포함할 수 있다. 일반적인 Linux 송신 경로를 단순화하면 Application -> TCP/UDP + IP -> qdisc -> NIC Driver -> NIC의 하드웨어 TX 큐 -> 링크로 표현할 수 있다. 여기서 qdisc는 하드웨어 큐와 별개의 소프트웨어 스케쥴링 계층이다. 이 경로는 송신 측의 개략도이며, 모든 네트워크 장치의 송수신 경로가 동일하다는 의미는 아니다.

TCP 혼잡제어는 송신자가 네트워크 상태에 맞춰 얼마나 보낼지 결정하고, qdisc는 전달받은 패킷 중 무엇을 다음에 내보낼지, 기다리게 하거나 폐기할지를 결정한다. 역할은 다르지만 서로 영향을 준다. qdisc의 drop이나 ECN marking은 TCP 혼잡제어에 피드백을 주며, Linux의 fq qdisc는 TCP가 요구하는 pacing, 즉 패킷 사이의 전송 간격을 반영한다. fq와 fq_codel은 별개의 qdisc이므로, 아래의 DRR과 CoDel 설명은 fq_codel을 대상으로 한다. tc 문서, tc-fq 문서

qdisc(Queue Discipline)

리눅스에서 제공하는 알고리즘은 기본적으로 pfifo_fast, fq_codel 등이 있다. pfifo_fast 는 내부적으로 queue 를 3개 두어 스케쥴링하는 기법인데 자세히 다루지는 않겠다. fq_codel은 일부 Linux 배포판에서 기본값으로 채택하는 qdisc이며, Flow Queueing과 Controlled Delay를 결합한다. 실제 기본값과 적용된 qdisc는 배포판 설정 및 장치에 따라 달라진다.

Linux에서 sysctl net.core.default_qdisc로 기본 qdisc 설정을, tc qdisc show dev <인터페이스>로 해당 인터페이스에 실제 적용된 qdisc를 확인할 수 있다. 물리적인 다중 TX 큐 장치는 root qdisc가 mq이고, 그 하위 큐에 기본 qdisc가 적용될 수도 있다. Linux 커널 문서

FQ-CoDel의 Flow Queueing

FQ-CoDel의 큐 선택 부분은 변형된 DRR(Deficit Round Robin)을 사용한다. 각 활성 큐에 **바이트 단위의 credit(deficit)**을 부여하고, 패킷을 하나 내보낼 때마다 그 패킷의 바이트 수만큼 차감한다. Credit이 0 이하가 되면 quantum만큼 보충하고 다음 큐로 차례를 넘긴다.

예를 들어 quantum이 1500바이트이고 두 큐의 시작 credit이 각각 1500이라면, 500바이트 패킷을 담은 큐는 3개를, 1500바이트 패킷을 담은 큐는 1개를 내보낼 수 있다. 패킷 개수가 아니라 전송 바이트를 기준으로 공정성을 맞추는 것이다. 마지막 패킷을 내보내면서 credit이 음수가 될 수도 있는데, 이 초과분은 다음 차례에 반영된다. Credit이 500인 상태에서 1500바이트를 보내면 -1000이 되고, 다음에 quantum 1500을 보충해도 credit은 500만 남는다. RFC 8290 §3

FQ-CoDel은 활성 큐를 new_flows와 old_flows라는 두 목록으로 관리한다. new/old는 TCP 연결이나 HTTP 요청의 나이를 뜻하지 않는다. 비활성 큐에 패킷이 들어오면 new 목록에 추가되고, credit을 소진하면 old 목록으로 이동한다. 스케쥴러는 new 목록의 큐를 우선 선택한다.

이 방식은 큐를 지속적으로 쌓는 대량 전송보다, 간헐적으로 적은 패킷을 보내는 트래픽에 유리하다. 오래 유지된 SSH 연결도 큐가 비활성화되었다가 패킷이 다시 들어오면 new로 취급될 수 있다. 따라서 우대의 근거는 새 요청이라는 사실보다, 지속적인 backlog를 만들지 않는 트래픽이라는 점에 있다. ACK, DNS, SSH, VoIP 등이 이런 특성을 보이는 경우가 많다. 다만 기존 큐가 굶지 않도록, new 큐가 비었을 때도 즉시 목록에서 제거하는 대신 old 목록을 거치는 등의 장치가 있다. RFC 8290 §1.3, §4.2

CoDel

Flow 간 전송 기회를 공정하게 나눠도, 각 큐에 패킷이 지속적으로 쌓이면 지연이 커질 수 있다. Bufferbloat는 과도한 버퍼에 큐가 지속적으로 쌓여 불필요한 지연이 커지는 문제이다. 일시적인 큐는 정상적인 burst를 흡수하는 데 필요하므로, 패킷이 쌓였다는 사실만으로 문제가 되는 것은 아니다. CoDel은 이런 일시적인 큐와 지속적인 큐를 구분하려는 AQM이며, FQ-CoDel에서는 각 내부 큐에 별도의 CoDel 상태를 유지한다. RFC 8289 §1, RFC 8290 §1.3

CoDel은 큐 길이 자체보다 **패킷이 해당 큐에서 머무른 시간(Sojourn Time)**을 관찰한다. 핵심은 오래 기다린 패킷 하나가 있는지가 아니라, 관찰 구간 동안 최소 대기 시간조차 target보다 높은 상태가 지속되는지이다. 구현에서는 모든 측정값을 저장해 최솟값을 계산하는 대신, 대기 시간이 target보다 높은 상태가 얼마나 오래 이어지는지를 추적한다. 큐가 거의 비어 있을 때는 drop을 억제해 링크 이용률을 보호한다. RFC 8289 §3.1, §4.1

Linux fq_codel의 기본값은 target = 5 ms, interval = 100 ms이다. 예를 들어 burst 이후 큐가 빠르게 비워져 대기 시간이 target 아래로 내려가면, 높은 지연이 잠깐 관측되어도 지속적인 혼잡으로 취급하지 않는다. 반대로 target을 초과하는 상태가 interval 동안 지속되면 drop 또는 ECN marking으로 혼잡 신호를 보낸다. Target은 모든 패킷의 지연을 5 ms 이하로 보장하는 상한이 아니며, 5 ms를 넘긴 패킷을 즉시 모두 버린다는 뜻도 아니다. tc-fq_codel 문서

ECN과 TCP의 피드백

ECN(Explicit Congestion Notification)은 혼잡도를 수치로 전달하는 TCP 옵션이 아니라, 패킷에 혼잡 발생을 표시하는 방식이다. 기존 TCP ECN의 피드백 과정은 다음과 같다.

  1. 송신자가 ECN을 사용할 수 있는 패킷임을 IP 헤더의 ECT 코드포인트로 표시한다.
  2. 혼잡을 감지한 qdisc가 해당 IP 헤더를 CE(Congestion Experienced)로 표시한다.
  3. 수신자가 TCP ACK의 ECE(ECN-Echo) 플래그로 송신자에게 혼잡을 알린다.
  4. 송신자는 혼잡제어에 이를 반영해 혼잡 윈도우를 줄이고, CWR(Congestion Window Reduced) 플래그로 반응했음을 알린다.

즉, qdisc가 수신자에게 표시한 신호가 ACK를 통해 송신자로 돌아가야 송신량 조절로 이어진다. Drop을 사용하면 송신자가 손실을 감지해 혼잡제어에 반영한다. RFC 3168 §6

ECN marking을 사용하려면 qdisc의 ECN 설정뿐 아니라 패킷도 ECN 가능한 상태여야 한다. 그렇지 않으면 drop을 사용한다. 또한 ECN이 활성화되어 있어도 큐의 패킷 수나 메모리 한계를 초과하면 drop이 발생할 수 있다. tc-fq_codel 문서

qdisc가 제어할 수 있는 지연의 범위

CoDel이 측정하는 sojourn time은 자신이 관리하는 큐에서의 대기 시간이다. 패킷이 qdisc를 떠난 뒤 NIC의 하드웨어 큐나 이후 경로의 라우터에 오래 머무르면, 그 지연을 해당 qdisc의 CoDel이 직접 측정하거나 제거할 수는 없다.

따라서 FQ-CoDel을 적용했다는 사실만으로 전체 경로의 bufferbloat가 해결되지는 않는다. Linux의 BQL(Byte Queue Limits)은 드라이버가 하드웨어에 넘겨 둔 데이터량을 제한해 하위 큐에 과도하게 쌓이는 것을 억제한다. 실제 병목이 더 느린 하위 링크에 있는 경우에는 그 속도에 맞춘 shaping으로 패킷이 관리 가능한 소프트웨어 큐에 쌓이도록 구성하는 방법도 있다. RFC 8290 §5.6

SQS

CDN, HTTP/2 Streaming Scheduling

1. Dependency aware Scheduling

2. NGINX Structural Enhancements

#Os #Ostep #Scheduling #Network