본문으로 건너뛰기

[Ray Serve] Pack 스케줄링 최적화: O(replicas x total_replicas)에서 O(replicas x nodes)로

PR 링크: ray-project/ray#60806 상태: Merged | 변경: +321 / -15

들어가며

Ray Serve의 pack 스케줄링 전략은 레플리카를 노드에 빈틈없이 배치하여 리소스 단편화를 최소화합니다. 문제는 _schedule_with_pack_strategy에서 레플리카를 배치할 때마다 _get_available_resources_per_node()와 _get_node_to_running_replicas()를 호출하고 있었다는 점입니다. 각 호출은 전체 launching + running 레플리카를 순회하므로, 2048개 레플리카 배치 시 O(replicas^2)의 작업이 발생했습니다.

핵심 코드 분석

기존: 레플리카마다 전체 재계산

Before:

def _schedule_with_pack_strategy(self):
    for scheduling_request in all_scheduling_requests:
        self._pack_schedule_replica(scheduling_request, all_node_labels)

def _pack_schedule_replica(self, scheduling_request, all_node_labels):
    for required_resources, required_labels in placement_candidates:
        target_node = self._find_best_fit_node_for_pack(
            required_resources,
            self._get_available_resources_per_node(),   # 매번 전체 재계산
            # ...
        )

변경: 사전 계산 + 증분 업데이트

After:

def _schedule_with_pack_strategy(self):
    # 한 번만 계산
    available_resources_per_node = self._get_available_resources_per_node()
    node_to_assigned_replicas = self._get_node_to_running_replicas()

    for scheduling_request in all_scheduling_requests:
        target_node = self._pack_schedule_replica(
            scheduling_request, all_node_labels,
            available_resources_per_node,
            node_to_assigned_replicas,
        )
        # 증분 업데이트
        if target_node and target_node in available_resources_per_node:
            available_resources_per_node[target_node] = (
                available_resources_per_node[target_node]
                - scheduling_request.required_resources
            )
        if target_node and target_node not in node_to_assigned_replicas:
            node_to_assigned_replicas[target_node] = set()
            node_to_assigned_replicas[target_node].add(
                scheduling_request.replica_id
            )

왜 이게 좋은가

  • 복잡도 개선: O(replicas x total_replicas)에서 O(replicas x nodes)로 줄어듭니다. 노드 수는 레플리카 수보다 훨씬 적으므로 실질적인 개선이 큽니다.
  • 벤치마크 결과: 2048개 레플리카/64노드 기준으로 수 초 -> 0.1초 미만으로 단축됩니다.
  • 보수적 근사: 증분 업데이트가 전체 재계산보다 약간 보수적(리소스를 더 적게 보고)이지만, 원래 _get_available_resources_per_node도 best-effort 방식이므로 의미 있는 차이가 없습니다.
  • idle/non-idle 노드 추적: node_to_assigned_replicas를 증분 업데이트하여 새로 배치된 레플리카도 non-idle 노드 판단에 반영됩니다.

참고 자료

댓글

관련 포스트

PR Analysis 의 다른글