[Ray] Autoscaler V2 스케줄링 최적화: 불가능한 리소스 요청 캐싱으로 O(N²M) 제거

PR 링크: ray-project/ray#61374 상태: Merged | 변경: +306 / -4

들어가며

Ray Autoscaler V2에서 수천 개의 동일한 리소스 요청이 들어오면, 스케줄러가 모든 요청을 모든 노드에 대해 개별적으로 평가하여 O(N²*M) 시간 복잡도가 발생합니다. 4000개 태스크를 제출하면 Autoscaler가 수 분간 멈추는 현상이 보고되었습니다. 이 PR은 두 가지 캐싱 전략으로 이 문제를 해결합니다.

핵심 코드 분석

Before: 모든 요청을 개별 평가

for r in requests:
    if not self._try_schedule_one(r, resource_request_source):
        unschedulable_requests.append(r)

N개의 요청이 M개의 노드에 대해 각각 _try_schedule_one을 호출하므로 총 O(N*M)의 비용이 발생합니다.

After: UnschedulableRequestCache

class UnschedulableRequestCache:
    def __init__(self):
        self.shapes = set()
        self.last_r_id = None
        self.last_shape_key = None

    def contains(self, request: ResourceRequest) -> bool:
        current_id = id(request)
        if current_id == self.last_r_id:
            shape_key = self.last_shape_key
        else:
            shape_key = request.SerializeToString(deterministic=True)
            self.last_r_id = current_id
            self.last_shape_key = shape_key
        return shape_key in self.shapes

한 노드에서 실패한 리소스 요청 형태를 캐싱합니다. 동일한 형태의 후속 요청은 비용이 큰 _try_schedule_one을 건너뜁니다. SerializeToString(deterministic=True)로 결정론적 해시를 생성하고, id() 기반 마지막 요청 캐싱으로 직렬화 비용도 최소화합니다.

After: NodeStateCache

class NodeStateCache:
    def was_seen_or_mark(self, node: "SchedulingNode") -> bool:
        if node.im_instance_status == Instance.RAY_RUNNING:
            return False  # 실행 중 노드는 개별 평가
        state_key = (
            node.node_type, node.node_kind,
            frozenset(node.total_resources.items()),
            frozenset(avail_res.items()),
            frozenset(node.labels.items()),
        )
        if state_key in self.seen_states:
            return True
        self.seen_states.add(state_key)
        return False

동일한 상태의 노드에 대한 중복 deepcopy와 시뮬레이션을 건너뜁니다. 실행 중인 노드는 고유 리소스(node ID 등)를 포함하므로 캐싱 대상에서 제외합니다.

왜 이게 좋은가

1. Anti-affinity 안전성

요청이 성공적으로 스케줄링되어 노드에 새 레이블이 추가되면, 캐시를 무효화합니다. 이로써 anti-affinity 규칙으로 인해 이전에 실패했던 요청이 다시 평가될 수 있습니다.

if len(self.labels) > num_labels_before:
    unfittable_cache.clear()

2. 지연 deepcopy

기존에는 모든 노드를 미리 deepcopy했지만, 이제 캐시 미스인 노드만 deepcopy합니다. 동일한 타입의 대기 노드가 100개 있어도 1번만 복사합니다.

3. 실측 효과

4000개 동일 CPU 태스크를 제출하는 테스트에서, 최초 1개 실패 후 나머지 3999개는 캐시 히트로 즉시 건너뛰어 스케줄링 시간이 극적으로 단축됩니다.

참고 자료

• Ray Autoscaler V2 설계 문서 — Autoscaler V2 아키텍처
• KubeRay Issue #3794 — 이 PR이 해결하는 원본 이슈