[Ray Serve] 레플리카 라우팅 데이터 구조 최적화: O(n) 스캔을 O(1) 딕셔너리 룩업으로 교체

PR 링크: ray-project/ray#60139 상태: Merged | 변경: +213 / -56

들어가며

Ray Serve의 요청 라우터는 들어오는 요청을 적절한 레플리카에 배분합니다. 기존 구현에서는 대기 요청 조회, 레플리카 선택, 메트릭 업데이트 등에서 O(n) 선형 스캔과 불필요한 객체 생성이 반복되었습니다. 이 PR은 5가지 최적화를 통해 라우팅 핫 패스의 성능을 대폭 개선합니다.

핵심 코드 분석

1. O(1) 대기 요청 조회

# Before: O(n) 선형 스캔
def _get_pending_request_matching_multiplexed_model_id(self, request_metadata):
    for pr in self._pending_requests_to_fulfill:
        if not pr.future.done() and pr.metadata.multiplexed_model_id == ...:
            return pr

# After: O(1) 딕셔너리 룩업 + lazy cleanup
def _get_pending_request_matching_multiplexed_model_id(self, request_metadata):
    model_id = request_metadata.multiplexed_model_id
    candidates = self._pending_requests_by_model_id.get(model_id)
    while candidates:
        pr = candidates[0]
        if not pr.future.done():
            return pr
        candidates.popleft()  # O(1) lazy cleanup
    return None

2. Lazy 해시 캐싱

@dataclass(frozen=True)
class DeploymentID:
    name: str
    app_name: str = SERVE_DEFAULT_APP_NAME

    def __hash__(self):
        try:
            return self._hash
        except AttributeError:
            h = hash((self.name, self.app_name))
            object.__setattr__(self, "_hash", h)
            return h

frozen=True dataclass의 해시를 한 번만 계산하고 캐싱합니다. __getstate__로 직렬화 시 캐시를 제외하여 프로세스 간 해시 시드 차이를 안전하게 처리합니다.

3. Power-of-2 라우터 최적화

# Before: random.sample으로 리스트 생성 + 딕셔너리 생성
chosen_ids = random.sample(list(candidate_replica_ids), k=min(2, len(...)))
replica_id_to_replica_map = {r.replica_id: r for r in candidate_replicas}

# After: 직접 인덱싱으로 ~1.9x 빠른 선택
i = random.randrange(n)
j = random.randrange(n - 1)
if j >= i:
    j += 1
chosen_ids = [candidates[i], candidates[j]]
return [[self._replicas[chosen_id] for chosen_id in chosen_ids]]

왜 이게 좋은가

1. 복합적 최적화 효과

단일 변경이 아니라 데이터 구조, 알고리즘, 캐싱, 메트릭 쓰로틀링을 종합적으로 개선하여, 라우팅 경로 전체의 CPU 사용량을 줄입니다.

2. 레플리카 리스트 캐싱

self._replicas_list: List[RunningReplica] = []

매 라우팅 호출마다 dict.values()를 리스트로 변환하는 O(n) 비용을 제거하고, 레플리카 변경 시에만 캐시를 갱신합니다.

3. 메트릭 쓰로틀링

RAY_SERVE_ROUTER_QUEUE_LEN_GAUGE_THROTTLE_S = 0.1  # 100ms

라우터 큐 길이 게이지 업데이트를 100ms 간격으로 쓰로틀링하여 핫 패스에서의 메트릭 오버헤드를 줄입니다.

참고 자료

• Power of Two Choices 알고리즘 — 2-choice 로드 밸런싱의 이론적 배경
• Ray Serve 아키텍처 — Ray Serve의 라우팅 구조