[uvicorn] Uvicorn의 리로드 패턴 최적화: O(N²)에서 O(N log N)으로의 성능 개선

PR 링크: Kludex/uvicorn#3184 상태: Merged | 변경: +19 / -9

들어가며

Python의 고성능 ASGI 서버인 Uvicorn은 개발 환경에서 코드 변경을 감지하여 서버를 자동으로 재시작하는 reload 기능을 제공합니다. 하지만 최근 이슈(#2389)에 따르면, .venv와 같이 수많은 하위 디렉토리를 포함하는 경로를 리로드 패턴에 포함할 경우, 서버 시작 단계에서 수 분이 소요되는 심각한 성능 저하가 보고되었습니다. 본 글에서는 이 문제를 해결하기 위해 Uvicorn이 어떻게 알고리즘을 개선했는지 살펴봅니다.

코드 분석

uvicorn/config.py: 알고리즘 개선

기존의 resolve_reload_patterns 함수는 모든 디렉토리 쌍을 비교하여 중첩된 디렉토리를 제거하는 방식을 사용했습니다. 이는 전형적인 O(N²) 복잡도를 가지며, 디렉토리 개수가 늘어날수록 연산량이 기하급수적으로 증가합니다.

Before:

children = []
for j in range(len(directories)):
    for k in range(j + 1, len(directories)):
        if directories[j] in directories[k].parents:
            children.append(directories[k])
        elif directories[k] in directories[j].parents:
            children.append(directories[j])
directories = list(set(directories).difference(set(children)))

After:

kept: set[Path] = set()
for directory in sorted(directories, key=lambda path: len(path.parts)):
    if not any(parent in kept for parent in directory.parents):
        kept.add(directory)
directories = list(kept)

개선된 코드는 디렉토리를 경로 깊이(path.parts) 기준으로 정렬한 뒤, 상위 디렉토리가 이미 kept 세트에 존재하는지 확인합니다. 정렬은 O(N log N)이며, 이후 순회는 O(N * M) (M은 경로의 깊이)으로, 전체적인 성능이 비약적으로 향상되었습니다.

tests/test_config.py: 테스트 케이스 추가

변경 사항의 정확성을 보장하기 위해 중첩된 디렉토리 구조를 검증하는 테스트가 추가되었습니다.

def test_reload_nested_subdirs_removal(tmp_path: Path) -> None:
    root = tmp_path.resolve()
    nested = [root / "a" / "x" / "y", root / "a" / "x", root / "a", root / "b" / "z", root / "c" / "d" / "e"]
    # ... (생략)
    assert frozenset(config.reload_dirs) == frozenset([root / "a", root / "b" / "z", root / "c" / "d" / "e"])

왜 이게 좋은가

이번 최적화의 핵심은 '불필요한 중복 비교 제거'입니다. 기존 방식은 모든 디렉토리를 서로 비교했지만, 새로운 방식은 '가장 얕은 디렉토리부터 처리'함으로써 상위 디렉토리가 이미 포함되었는지 확인하는 것만으로 하위 디렉토리의 중복 여부를 즉시 판단할 수 있습니다.

실제 벤치마크 결과는 다음과 같습니다:

• 500개 디렉토리: 5.3초 → 0.09초
• 2000개 디렉토리: 120초 → 0.39초

이 사례는 복잡도가 높은 알고리즘을 단순한 정렬과 세트(Set) 자료구조를 활용한 선형 탐색으로 전환함으로써, 대규모 데이터셋에서 얼마나 큰 성능 향상을 얻을 수 있는지 보여주는 좋은 교훈을 줍니다.

결론

Uvicorn은 이번 PR을 통해 개발자 경험(DX)을 크게 개선했습니다. 특히 대규모 프로젝트나 복잡한 가상 환경을 사용하는 경우, 서버 시작 속도가 수 초 내로 단축되어 생산성 향상에 기여할 것입니다.

참고 자료

• https://docs.python.org/3/library/pathlib.html#pathlib.PurePath.parents
• https://docs.python.org/3/library/stdtypes.html#set

⚠️ 알림: 이 분석은 AI가 실제 코드 diff를 기반으로 작성했습니다.