B-WF2Q+란? BFQ가 순서를 정하는 페어 큐잉 알고리즘 분석

똑같이 예산을 배정받은 애플리케이션 두 개가 있다고 해서, 둘의 디스크 사용 순서까지 똑같이 결정되는 건 아니에요. BFQ 논문은 이 “다음엔 누구 차례인가”라는 문제를 BFQ의 예산 기반 스케줄링 위에 얹은 별도의 알고리즘, B-WF²Q+로 풀어요. 예산이 큰 애플리케이션이 디스크를 오래 붙잡고 있는데도 어떻게 다른 애플리케이션이 손해를 보지 않을 수 있을까요?

B-WF2Q+는 무엇인가

B-WF²Q+는 Worst-case Fair Weighted Fair Queueing+를 변형한 페어 큐잉 알고리즘으로, BFQ 안에서 각 애플리케이션에 고정된 가중치(weight)를 부여하고 그 가중치 비율대로 장기적인 디스크 처리량을 나눠주는 역할을 해요. 논문 원문 표현을 그대로 옮기면, 애플리케이션에 배정된 예산 크기와 무관하게, 각 애플리케이션은 장기적으로 자신의 가중치를 다른 경쟁 애플리케이션들의 가중치 합으로 나눈 비율만큼 디스크 처리량을 받도록 보장돼요. 특정 애플리케이션에 가중치가 명시적으로 지정되지 않으면 시스템 전역에서 쓰는 공통 기본값이 적용돼요.

큰 예산을 받으면 오히려 순번이 밀리는 이유

이 보장은 언뜻 직관에 어긋나 보여요. 예산이 큰 애플리케이션일수록 디스크 사용권을 얻은 뒤 더 오래 디스크를 붙잡고 있을 텐데, 그런데도 왜 처리량 비율은 여전히 가중치대로 유지될까요. B-WF2Q+는 예산이 클수록 그 애플리케이션의 다음 서비스 시점을 그만큼 더 뒤로 미루는 방식으로 이 불균형을 상쇄해요. 즉 한 번에 많이 가져가는 대신 다음 차례가 늦게 돌아오는 셈이라, 장기 평균을 보면 결국 가중치 비율로 수렴하게 돼요. 게다가 논문은 애플리케이션에 배정되는 예산 자체가 그 애플리케이션의 가중치와는 독립적으로 결정된다는 점도 함께 짚어요. 예산은 순전히 처리량과 지연 시간의 균형을 맞추기 위한 별도의 변수로 다뤄지는 거예요.

단기적으로는 얼마나 기다려야 하나

장기 처리량 비율과는 별개로, 개별 요청 하나가 얼마나 기다려야 하는지도 B-WF²Q+가 수학적으로 보장해요. 이상적인 완전 공정 시스템에서 그 요청이 처리 완료됐을 시점과 비교했을 때, BFQ가 보장하는 최악의 지연 시간은 두 요소의 합으로 표현돼요. 첫 번째 요소는 BFQ가 어떤 애플리케이션에든 배정할 수 있는 최대 예산에 비례하고, 두 번째 요소는 애플리케이션에 배정된 예산과 그 애플리케이션이 유휴 상태가 되기 전 실제로 소비한 섹터 수 사이의 최대 차이에 비례해요.

여기서 나오는 실무적인 결론이 하나 있어요. 애플리케이션에 배정하는 예산이 타이트할수록, 즉 실제 소비량에 가까울수록 두 번째 지연 요소가 줄어든다는 점이에요. 반대로 아예 작은 예산을 일괄적으로 배정하면 두 요소 모두 낮게 유지할 수 있지만, 그 대신 순차적인 요청 패턴을 살려 처리량을 극대화하기는 어려워져요. 이 트레이드오프를 어떻게 풀지가 바로 다음 문제로 이어지는데, BFQ는 이걸 예산을 매번 다시 계산하는 피드백-루프 알고리즘으로 해결해요.

결국 순서 문제는 예산 계산 문제로 넘어간다

B-WF²Q+ 자체는 “가중치대로 장기 처리량을 나누고, 예산 크기로 단기 지연을 조절한다”는 명확한 수학적 틀을 제공해요. 하지만 이 틀이 실제로 잘 작동하려면 각 애플리케이션에 배정하는 예산 값 자체를 얼마로 잡을지가 관건이 돼요. 너무 크게 잡으면 지연이 늘고, 너무 작게 잡으면 순차 읽기의 이점을 못 살려 처리량이 떨어지거든요. BFQ가 이 딜레마를 풀기 위해 만든 게 바로 매번 예산을 갱신하는 피드백-루프 알고리즘인데, 이 계산 로직을 들여다보면 왜 BFQ가 CFQ보다 최대 30% 높은 처리량을 냈는지가 훨씬 선명해져요.