매치 형성 개요
큐에 티켓을 제출하면 매치메이킹 서비스가 다른 대기 중인 티켓과 함께 배치합니다. 이 서비스는 호환되는 티켓을 매치로 그룹화하려고 시도하는 매치 루프를 지속적으로 실행합니다. 각 단계에서 발생하는 일은 다음과 같습니다.- 만료된 티켓 제거.
GiveUpAfterSeconds시간 초과를 초과하는 티켓이 취소됩니다. - 대기 시간별로 티켓 정렬: 가장 오래 기다린 티켓이 잠재적 매치의 시드 또는 시작 지점이 됩니다.
- 호환성별로 후보 순위 지정: 나머지 각 티켓은 큐의 규칙에 따라 그 특성이 시드 티켓과 얼마나 일치하는지에 따라 거리 점수를 받습니다.
- 그룹은 그리디하게 구축됨: 가장 가까운 후보부터 시작하여 티켓이
MaxMatchSize까지 한 번에 하나씩 그룹에 추가됩니다. - 각 추가 유효성 검사: 티켓이 추가될 때마다 모든 규칙이 후보가 지금까지의 그룹과 여전히 호환되는지 확인합니다. 어떤 규칙이라도 거부하면 후보가 건너뛰어집니다.
- 전체 그룹 유효성 검사: 그룹이
MinMatchSize에 도달하면 최종 유효성 검사 패스에서 그룹이 모든 규칙을 충족하는지 확인합니다. 통과하면 매치가 만들어집니다. - 역추적: 유효한 그룹을 형성할 수 없는 경우 서비스는 마지막으로 추가된 티켓을 제거하고 다음 후보를 시도합니다. 이 프로세스는 현재 시드를 포기하기 전에 대체 그룹화를 탐색합니다.
이 알고리즘은 가장 오래 기다린 티켓을 우선시합니다. 이 우선순위는 가장 오래 기다린 플레이어가 가장 먼저 매치를 받도록 합니다.
규칙이 매칭에 영향을 미치는 방식
규칙은 매치 형성 중에 두 가지 목적을 제공합니다. 필터링과 정렬입니다.필터링
규칙은 티켓이 그룹에 참여하는 것을 차단할 수 있습니다. 예를 들어 게임 빌드 버전에 대한StringEqualityRule은 빌드가 그룹의 빌드와 매치하지 않는 티켓을 거부합니다. 매치메이킹 서비스는 후보를 고려할 때마다 필터링을 확인합니다. 시작 시 일회성 확인이 아닙니다.
정렬(거리)
규칙은 또한 어떤 후보를 먼저 시도할지 결정하는 거리 점수에 기여합니다. 거리가 낮을수록 호환성이 높음을 의미합니다.- 특성 값이 동일한 티켓은 일반적으로 거리 0의 점수를 얻습니다.
- 규칙의 허용 범위 가장자리에 있는 티켓은 1에 가까운 거리 점수를 얻습니다.
- 허용 범위를 벗어난 티켓은 필터링되어 제외됩니다(사실상 무한한 거리).
유효성 검사
일부 제약 조건은 완전한 그룹이 형성된 후에만 확인할 수 있습니다. 예를 들어 팀 균형 규칙(TeamDifferenceRule, TeamSizeBalanceRule)은 팀의 균형이 맞는지 평가하기 전에 전체 그룹을 확인해야 합니다. 이러한 규칙은 최종 유효성 검사 단계로 실행됩니다.
확장 및 완화
티켓이 기다리면 규칙이 제약 조건을 완화하여 검색을 넓힙니다. 이 프로세스를 제어하는 두 가지 메커니즘이 있습니다.- 확장: 규칙이 시간이 지남에 따라 임계값을 점진적으로 조정합니다. 예를 들어 기술 임계값이 0.2인
DifferenceRule은 5초마다 0.1씩 확장되어 결국 0.5의 차이를 허용할 수 있습니다. - 선택 사항이 될 때까지의 시간(초): 구성된 시간이 지난 후에는 규칙이 필터링을 완전히 중지합니다. 규칙은 여전히 정렬(거리)에 기여하지만 더 이상 매치를 차단하지 않습니다.
완화가 매치 품질이 무시된다는 의미는 아닙니다. 규칙이 선택 사항이 되더라도 여전히 정렬 단계에 거리를 기여합니다. 규칙을 충족하는 후보가 그렇지 않은 후보보다 먼저 시도됩니다.
확장 및 파티셔닝
큐가 대량의 티켓을 받으면 서비스는 티켓을 독립적으로 평가하는 그룹으로 파티셔닝합니다. 파티셔닝은 자연스럽게 모집단을 분할하는 규칙 특성을 사용합니다. 예를 들어 게임 모드에 대한StringEqualityRule은 깔끔한 파티션 경계를 만듭니다.
부하가 감소하면 파티션이 다시 병합됩니다. 이 프로세스는 서비스에 더 큰 후보 풀을 제공하고 매치 품질을 향상시킵니다.
잘 확장되는 큐를 설계하는 방법에 대한 자세한 내용은 매치메이킹 확장을 참조하세요.