Resolver 내부 동작¶

Tip

이 문서는 uv의 resolver 내부 동작에 초점을 맞춘다. uv 사용법은 resolution 개념 문서를 참조한다.

리졸버¶

교과서에서 정의한 바에 따르면, 리졸루션(resolution) 또는 주어진 요구사항 집합에서 설치할 버전 집합을 찾는 문제는 SAT 문제와 동등하며, 따라서 NP-완전 문제다. 최악의 경우 모든 패키지의 모든 버전 조합을 시도해야 하며, 일반적이고 빠른 알고리즘은 존재하지 않는다. 그러나 실제로는 여러 이유로 이 설명이 오해의 소지가 있다:

uv에서 리졸루션의 가장 느린 부분은 패키지와 버전 메타데이터를 로드하는 작업이다. 캐시가 있더라도 마찬가지다.
가능한 해결책이 많지만, 그중 일부가 다른 것보다 선호된다. 예를 들어 일반적으로 최신 버전의 패키지를 사용하는 것을 선호한다.
패키지 의존성은 복잡하다. 연속적인 버전 범위가 존재하며, 임의의 불리언 포함/제외가 아니다. 인접한 릴리스는 종종 동일하거나 유사한 요구사항을 가진다.
대부분의 리졸루션에서 리졸버는 백트래킹할 필요가 없다. 버전을 반복적으로 선택하는 것으로 충분하다. 이전 리졸루션에서 버전 선호도가 있다면 거의 추가 작업이 필요하지 않다.
리졸루션이 실패할 때, 단순히 해결책이 없다는 메시지보다 더 많은 정보가 필요하다. 대신 리졸버는 이해하기 쉬운 오류 추적을 생성해 어떤 패키지가 충돌에 관여했는지 사용자가 충돌을 해결할 수 있도록 알려줘야 한다.
성능과 사용자 경험을 위한 가장 중요한 휴리스틱은 결정을 내리는 순서를 우선순위에 따라 정하는 것이다.

uv는 PubGrub의 Rust 구현인 pubgrub-rs를 사용한다. PubGrub은 증분 버전 솔버로, uv에서 다음과 같은 단계로 작동한다:

선택된 패키지 버전과 결정되지 않은 패키지를 선언하는 부분 해결책으로 시작한다. 초기에는 가상 루트 패키지만 결정된다.
결정되지 않은 패키지 중 가장 높은 우선순위의 패키지를 선택한다. 대략적으로 URL(파일, git 등)이 포함된 패키지가 가장 높은 우선순위를 가지며, 그다음으로 더 정확한 지정자(== 등)가 있는 패키지, 그다음으로 덜 엄격한 지정자가 있는 패키지 순이다. 각 카테고리 내에서 패키지는 처음 본 순서(파일 내 순서)에 따라 정렬되어 리졸루션을 결정적으로 만든다.
선택된 패키지에 대해 버전을 선택한다. 이 버전은 부분 해결책의 요구사항에서 모든 지정자와 호환되어야 하며, 이전에 호환되지 않음으로 표시된 버전이 아니어야 한다. 리졸버는 락파일(uv.lock 또는 -o requirements.txt)과 현재 환경에 설치된 버전을 선호한다. 버전은 높은 것부터 낮은 것 순으로 확인된다(대체 리졸루션 전략을 사용하지 않는 한).
선택된 패키지 버전의 모든 요구사항이 결정되지 않은 패키지에 추가된다. uv는 성능을 향상시키기 위해 이들의 메타데이터를 백그라운드에서 미리 가져온다.
충돌이 감지되지 않는 한 다음 패키지로 이 과정을 반복한다. 충돌이 감지되면 리졸버는 백트래킹한다. 예를 들어, 부분 해결책에 a 2와 b 2가 포함되어 있고, 요구사항이 a 2 -> c 1과 b 2 -> c 2인 경우, 호환되는 c 버전을 찾을 수 없다. PubGrub은 이 문제가 a 2와 b 2에 의해 발생했음을 판단하고 {a 2, b 2}라는 비호환성을 추가한다. 즉, 둘 중 하나가 선택되면 다른 하나는 선택할 수 없다. 부분 해결책은 a 2로 복원되고, 리졸버는 b의 새 버전을 선택하려고 시도한다.

결국 리졸버는 모든 패키지에 대해 호환되는 버전을 선택하거나(성공적인 리졸루션), 사용자가 요청한 버전을 정의하는 가상 "루트" 패키지를 포함한 비호환성이 발생한다. 루트 패키지와의 비호환성은 루트 의존성과 그 전이적 의존성의 어떤 버전을 선택하더라도 항상 충돌이 발생할 것임을 나타낸다. PubGrub에서 추적된 비호환성에서 오류 메시지를 구성해 관련된 패키지를 열거한다.

Tip

PubGrub 알고리즘에 대한 자세한 내용은 PubGrub 알고리즘의 내부를 참고한다.

PubGrub의 기본 알고리즘 외에도, 두 패키지가 너무 많이 충돌하는 경우 백트래킹하고 순서를 바꾸는 휴리스틱도 사용한다.

포킹¶

기존 Python 리졸버는 백트래킹을 지원하지 않았고, 백트래킹이 가능하더라도 특정 아키텍처, 운영체제, Python 버전, Python 구현에 한정된 단일 환경에서만 동작했다. 일부 패키지는 서로 다른 환경에 대해 모순된 요구사항을 가진다. 예를 들면 다음과 같다:

numpy>=2,<3 ; python_version >= "3.11"
numpy>=1.16,<2 ; python_version < "3.11"

Python은 각 패키지의 단일 버전만 허용하기 때문에, 단순한 리졸버는 여기서 오류를 발생시킨다. Poetry에서 영감을 받은 uv는 포킹 리졸버를 사용한다: 서로 다른 마커를 가진 패키지에 대해 여러 요구사항이 있을 때마다, 리졸루션을 분할한다.

위 예제에서 부분 해결책은 python_version >= "3.11"과 python_version < "3.11"에 대해 두 개의 리졸루션으로 분할된다.

마커가 겹치거나 마커 공간의 일부가 누락된 경우, 리졸버는 추가로 분할한다. 즉, 패키지당 많은 포크가 발생할 수 있다. 예를 들어 다음과 같다:

flask > 1 ; sys_platform == 'darwin'
flask > 2 ; sys_platform == 'win32'
flask

sys_platform == 'darwin', sys_platform == 'win32', 그리고 sys_platform != 'darwin' and sys_platform != 'win32'에 대해 포크가 생성된다.

포크는 중첩될 수 있다. 예를 들어, 각 포크는 이전에 발생한 포크에 의존적이다. 동일한 패키지를 가진 포크는 병합되어 포크 수를 줄인다.

Tip

포킹은 uv lock -v 로그에서 Splitting resolution on ..., Solving split ... (requires-python: ...), Split ... resolution took ...를 찾아 관찰할 수 있다.

포킹 리졸버의 한 가지 어려움은 분할이 발생하는 지점이 패키지가 보이는 순서에 의존한다는 점이다. 이 순서는 uv.lock과 같은 선호도에 따라 달라진다. 따라서 리졸버가 특정 포크로 요구사항을 해결하고 이를 락파일에 기록한 후, 리졸버를 다시 호출할 때 선호도가 다른 포크 지점을 발생시켜 다른 해결책을 찾을 수 있다. 이를 방지하기 위해 각 포크와 포크 간에 분기된 각 패키지의 resolution-markers를 락파일에 기록한다. 새로운 리졸루션을 수행할 때 락파일의 포크를 사용하여 리졸루션의 안정성을 보장한다. 요구사항이 변경되면 새로운 포크가 저장된 포크에 추가될 수 있다.

Wheel 태그¶

uv의 해결 방식은 환경 마커와 관련해 보편적이지만, wheel 태그에는 적용되지 않는다. wheel 태그는 Python 버전, Python 구현체, 운영체제, 아키텍처를 인코딩할 수 있다. 예를 들어, torch-2.4.0-cp312-cp312-manylinux2014_aarch64.whl은 CPython 3.12에서만 동작하며, arm64 Linux와 glibc>=2.17(manylinux2014 정책에 따라) 환경에서만 호환된다. 반면 tqdm-4.66.4-py3-none-any.whl은 모든 Python 3 버전과 인터프리터, 운영체제, 아키텍처에서 동작한다. 대부분의 프로젝트는 호환 가능한 wheel이 없을 때 사용할 수 있는 보편적으로 호환되는 소스 배포판을 제공하지만, torch와 같은 일부 패키지는 소스 배포판을 제공하지 않는다. 이 경우 Python 3.13, 드문 운영체제, 또는 아키텍처에서 설치를 시도하면 호환되는 wheel이 없다는 오류가 발생할 수 있다.

마커와 wheel 태그 필터링¶

모든 포크에서 가능한 마커를 알고 있다. 비보편적 해결 방식에서는 정확한 값을 알고 있다. 보편적 모드에서는 최소한 파이썬 요구사항에 대한 제약 조건을 알고 있다. 예를 들어 requires-python = ">=3.12"는 importlib_metadata; python_version < "3.10"이 설치될 수 없으므로 제외할 수 있다. 추가로 tool.uv.environments가 설정되어 있다면, 해당 환경과 일치하지 않는 마커가 있는 요구사항을 필터링할 수 있다. 각 포크 내에서는 포크 마커를 기준으로 추가 필터링을 할 수 있다.

마커 표현식에는 일부 중복이 존재한다. 하나의 마커 필드 값이 다른 필드의 값을 암시하는 경우가 있다. 내부적으로 python_version과 python_full_version, 그리고 알려진 platform_system과 sys_platform 값을 공통의 표준 표현으로 정규화하여 서로 매칭할 수 있게 한다.

로컬 태그가 있는 버전(예: 1.2.3+localtag)을 선택했을 때, wheel이 Windows, Linux, macOS를 지원하지 않고, 태그가 없는 기본 버전(예: 1.2.3)이 누락된 플랫폼을 지원한다면, 플랫폼에 따라 로컬 태그가 있는 버전과 없는 버전을 모두 사용하여 플랫폼 지원을 확장하려고 포크를 시도한다. 이는 torch와 같이 로컬 태그를 다른 하드웨어 가속기용으로 사용하는 패키지에 도움이 된다. wheel 태그와 마커 사이에 1:1 매핑은 없지만, Windows, Linux, macOS와 같은 잘 알려진 플랫폼에 대해서는 매핑을 할 수 있다.

Requires-python¶

requires-python = ">=3.9"와 같은 조건이 포함된 Python 버전에서 실제로 설치 가능한지 확인하기 위해, uv는 모든 의존성이 동일한 최소 Python 버전을 요구하도록 한다. 예를 들어 requires-python = ">=3.10"과 같이 더 높은 최소 Python 버전을 선언한 패키지 버전은 Python 3.9에서 설치할 수 없기 때문에 거부된다. 단순화와 향후 호환성을 위해 requires-python의 하한만 고려한다. 예를 들어, 패키지가 requires-python = ">=3.8,<4"를 선언하면 <4 마커는 전체 해결에 전파되지 않는다.

이 기본 설정은 numpy와 같이 CPython의 버전 의존적인 C API를 사용하는 패키지에 문제가 된다. 각 numpy 릴리스는 4개의 Python 마이너 버전을 지원한다. 예를 들어, numpy 2.0.0은 CPython 3.9부터 3.12까지의 휠을 제공하고 requires-python = ">=3.9"를 선언한다. 반면 numpy 2.1.0은 CPython 3.10부터 3.13까지의 휠을 제공하고 requires-python = ">=3.10"를 선언한다. 이는 requires-python = ">=3.9"를 가진 프로젝트에서 numpy>=2,<3 요구 사항을 해결할 때 numpy 2.0.0을 해결하고, 락파일이 Python 3.13 이상에서 설치되지 않음을 의미한다. 이를 완화하기 위해, 너무 높은 Python 요구 사항으로 인해 버전을 거부할 때마다 해당 Python 버전에서 분기한다. 이 동작은 --fork-strategy로 제어된다. 예시의 경우, numpy 2.1.0을 만나면 Python 버전 >=3.9,<3.10와 >=3.10로 분기하고 두 가지 다른 numpy 버전을 해결한다:

numpy==2.0.0; python_version >= "3.9" and python_version < "3.10"
numpy==2.1.0; python_version >= "3.10"

우선순위 설정¶

우선순위 설정은 성능과 더 나은 해결책을 위해 중요하다.

많은 버전을 시도하다가 나중에 폐기해야 한다면, 해결 속도가 느려진다. 불필요한 메타데이터를 읽어야 하고, 폐기된 하위 트리에 대한 많은 (충돌) 정보를 추적해야 하기 때문이다.

uv가 어떤 해결책을 선택할지에 대한 기대가 있다. 버전 제약이 여러 해결책을 허용하더라도 일반적으로 바람직한 해결책은 간접 의존성보다 직접 의존성에 대해 최신 버전을 우선적으로 사용하고, 매우 오래된 버전으로 되돌아가는 것을 피하며, 대상 머신에 설치할 수 있는 것을 선호한다.

내부적으로 uv는 주어진 패키지 이름을 가진 각 패키지를 여러 가상 패키지로 표현한다. 예를 들어, 활성화된 추가 기능, 의존성 그룹, 또는 마커가 있는 경우 각각 하나의 패키지로 표현한다. PubGrub은 각 가상 패키지에 대해 버전을 선택해야 하지만, uv의 우선순위 설정은 패키지 이름 수준에서 작동한다.

패키지에 대한 요구사항을 만날 때마다, 이를 우선순위에 매칭한다. 루트 패키지와 URL 요구사항이 가장 높은 우선순위를 가지며, 그 다음으로 == 연산자를 사용한 단일 요구사항이 버전을 직접 결정할 수 있으므로 높은 우선순위를 가진다. 그 다음으로 높은 충돌 가능성이 있는 패키지, 마지막으로 나머지 모든 패키지가 뒤따른다. 각 카테고리 내에서 패키지는 처음 만난 순서대로 정렬되며, 이는 직접 의존성(워크스페이스 의존성 포함)을 전이 의존성보다 우선하는 너비 우선 탐색을 생성한다.

흔한 문제는 패키지 A가 패키지 B보다 높은 우선순위를 가지고 있는데, B가 A의 오래된 버전과만 호환되는 경우다. 이 경우 패키지 A의 최신 버전을 결정한다. 패키지 B의 버전을 결정할 때마다 A와의 충돌로 인해 즉시 폐기된다. B의 모든 가능한 버전을 시도해야 하며, 가능한 범위를 모두 소진할 때까지(느림), A에 의존하지 않는 매우 오래된 버전을 선택하지만 프로젝트와도 호환되지 않을 가능성이 높거나(나쁨), 매우 오래된 버전을 빌드하지 못하는 경우(나쁨)가 발생한다. 이러한 충돌이 다섯 번 발생하면 A와 B를 특별한 높은 충돌 우선순위 수준으로 설정하고, B를 A보다 먼저 결정하도록 한다. 그런 다음 A를 결정하기 전 상태로 수동으로 되돌아가 다음 반복에서 A 대신 B를 결정한다. 실제 사례를 포함한 더 자세한 설명은 #8157과 #9843을 참고한다.