클라우드 Mac에서 검증하는 iOS 안정 우선순위 큐

이미지 프리페치, 업로드 대기 목록, 로컬 작업의 실행 순서를 관리할 때는 우선순위 큐를 자주 사용합니다. 개발용 컴퓨터에서 작업 세 개를 연달아 넣고 차례로 꺼내 보면 쉽게 올바른 결과를 얻을 수 있습니다. 하지만 클라우드 Mac의 회귀 테스트에서 삽입과 추출을 번갈아 수행하면 우선순위가 같은 작업들의 순서가 뒤바뀌기도 합니다. 여기서는 완전한 스케줄러를 만드는 대신 Swift 이진 힙만 따로 구현해 정렬 계약을 항상 지키는지 검증합니다.

우선순위와 안정성의 의미부터 정의하기

이 글에서는 우선순위 값이 작을수록 먼저 꺼내고, 값이 같으면 먼저 넣은 항목을 먼저 꺼내기로 합니다. 작업 식별자는 업무 데이터일 뿐 비교에는 사용하지 않습니다. 같은 작업을 다시 넣더라도 새로운 항목으로 취급하고 새 삽입 순번을 부여합니다.

먼저 이 규칙들을 테스트 명세로 작성한 뒤 자료구조를 구현합니다. 배열 인덱스를 영구적인 순번으로 사용해서는 안 됩니다. 항목을 꺼내거나 교환하면 인덱스가 바뀌므로 안정성을 보장할 수 없습니다. 우선순위 값을 서로 빼서 대소를 판단하는 방식도 피해야 합니다. 정수의 극값에서는 오버플로가 발생할 수 있습니다.

안정성과 공정성은 다릅니다. 우선순위가 높은 작업이 계속 들어오면 우선순위가 낮은 작업은 여전히 오랫동안 기다릴 수 있습니다. 에이징과 할당량은 스케줄링 정책에 속하며, 힙의 비교 함수에 암묵적으로 섞어 넣어서는 안 됩니다.

아래 구현은 값 타입이며 직렬 접근만을 전제로 합니다. 동시성 코드에 연결할 때는 하나의 격리 경계에서 접근을 일괄 관리해야 합니다. 여러 태스크가 같은 인스턴스를 동시에 수정하게 해서는 안 됩니다.

삽입 순번을 포함한 최소 힙 구현하기

코드를 main.swift로 저장합니다. 비교 키는 우선순위와 단조 증가하는 순번으로 구성됩니다. 삽입할 때 위로 올리는 과정과 꺼낼 때 아래로 내리는 과정에서 반드시 같은 비교 함수를 사용해야 합니다. 두 경로가 어떤 항목을 앞에 둘지 서로 다르게 판단하지 않도록 하기 위해서입니다.

struct StableQueue<Value> {
    enum Failure: Error {
        case sequenceExhausted
    }

    private struct Entry {
        let value: Value
        let priority: Int
        let sequence: UInt64
    }

    private var entries: [Entry] = []
    private var nextSequence: UInt64 = 0

    private func precedes(_ a: Entry, _ b: Entry) -> Bool {
        if a.priority != b.priority {
            return a.priority < b.priority
        }
        return a.sequence < b.sequence
    }

    mutating func enqueue(_ value: Value, priority: Int) throws {
        guard nextSequence < UInt64.max else {
            throw Failure.sequenceExhausted
        }
        entries.append(Entry(
            value: value,
            priority: priority,
            sequence: nextSequence
        ))
        nextSequence += 1

        var child = entries.count - 1
        while child > 0 {
            let parent = (child - 1) / 2
            guard precedes(entries[child], entries[parent]) else {
                break
            }
            entries.swapAt(child, parent)
            child = parent
        }
    }

    mutating func dequeue() -> Value? {
        guard !entries.isEmpty else { return nil }
        if entries.count == 1 {
            return entries.removeLast().value
        }

        let result = entries[0].value
        entries[0] = entries.removeLast()
        var parent = 0

        while parent < entries.count / 2 {
            let left = parent * 2 + 1
            let right = left + 1
            var candidate = left
            if right < entries.count,
               precedes(entries[right], entries[left]) {
                candidate = right
            }
            guard precedes(entries[candidate], entries[parent]) else {
                break
            }
            entries.swapAt(parent, candidate)
            parent = candidate
        }
        return result
    }
}

순번이 상한에 도달하면 명시적으로 오류를 던집니다. 순번을 순환시키지 않으며, 큐를 비운 뒤에도 몰래 0으로 초기화하지 않습니다. 이 구현은 최댓값을 사용하지 않고 남겨 두어 배열을 수정하기 전에 실패하도록 합니다. 삽입 실패가 기존 항목의 순서를 바꾸지 않는지도 테스트해야 합니다.

삽입과 추출을 교차해 하향 조정 오류 찾기

다음 코드를 같은 파일 끝에 추가합니다. 최종 정렬 결과뿐 아니라 항목 하나를 꺼낸 뒤 같은 우선순위의 작업을 넣었을 때 기존 항목이 새 항목보다 앞에 남아 있는지도 확인합니다.

func requireEqual<T: Equatable>(_ actual: T, _ expected: T) {
    precondition(actual == expected, "Queue contract failed")
}

var queue = StableQueue<String>()
requireEqual(queue.dequeue(), Optional<String>.none)

try queue.enqueue("A", priority: 2)
try queue.enqueue("B", priority: 1)
try queue.enqueue("C", priority: 2)
requireEqual(queue.dequeue(), Optional("B"))

try queue.enqueue("D", priority: 2)
try queue.enqueue("E", priority: Int.min)
requireEqual(queue.dequeue(), Optional("E"))
requireEqual(queue.dequeue(), Optional("A"))
requireEqual(queue.dequeue(), Optional("C"))
requireEqual(queue.dequeue(), Optional("D"))
requireEqual(queue.dequeue(), Optional<String>.none)

클라우드 Mac의 작업 디렉터리에서 실행합니다.

set -eu
mkdir -p .build
xcrun swiftc -Onone main.swift -o .build/queue-check
.build/queue-check

성공하면 아무것도 출력하지 않으며, 실패하면 0이 아닌 종료 코드로 작업을 중단합니다. 최적화 빌드에서 검사가 제거되지 않도록 여기서는 assert를 사용하지 않습니다. 또한 컴파일 성공만으로 실행 검증을 대신하지 않습니다.

결정적 테스트를 세 그룹 더 추가합니다. 모든 항목의 우선순위가 같을 때 입력 순서를 유지하는지, 우선순위 값을 내림차순으로 모두 넣은 뒤 오름차순으로 꺼내는지, 요소가 두 개뿐일 때 하나를 꺼낸 다음 삽입과 추출을 연속으로 수행해도 정상인지 확인합니다. 마지막 그룹은 오른쪽 자식이 없을 때 발생하는 인덱스 범위 초과 오류를 특히 잘 드러냅니다.

기준 모델로 테스트 범위 넓히기

직접 작성한 테스트는 계약을 설명하기에는 좋지만, 가능한 모든 힙 형태를 다루기는 어렵습니다. 기준 모델은 배열에 작업 번호, 우선순위, 삽입 순번을 저장하고 항목을 꺼내기 전에 뒤의 두 값을 기준으로 정렬하는 방식이면 충분합니다. 속도는 느리지만 구현이 단순해 소규모 테스트의 판정 기준으로 적합합니다.

삽입과 추출이 교차하는 연산을 생성할 때는 항목을 넣을 때마다 모델에도 같은 항목을 기록합니다. 항목을 꺼낼 때마다 양쪽의 옵셔널 작업 번호를 비교하고, 모든 연산이 끝나면 남은 항목도 전부 꺼냅니다. 우선순위만 비교해서는 부족합니다. 같은 우선순위의 작업끼리 순서가 바뀌는 것도 결함이기 때문입니다.

재현할 수 없는 난수 생성 방식에 직접 의존하지 말고, 시드를 지정할 수 있는 의사 난수 생성기를 사용합니다. 실패 기록에는 최소한 시드, 연산 인덱스, 실패 지점까지의 전체 연산열, 양쪽 결과를 포함해야 합니다. 원인을 좁힐 때는 실패한 연산열에서 구간별로 연산을 제거해, 여전히 실패하는 가장 짧은 연산열을 남깁니다.

기준 모델을 구현과 독립적으로 유지하기

기준 모델에서 힙의 비교 함수를 재사용해서는 안 됩니다. 같은 오류가 양쪽에 들어가면 잘못된 결과도 비교를 통과할 수 있습니다. 모델은 우선순위를 먼저 비교하고, 같을 때만 가장 먼저 들어온 항목을 선택하는 방식으로 업무 규칙을 직접 표현하면 됩니다.

회귀 테스트에 통합하고 검증 범위 명확히 하기

커밋 전에는 빈 큐, 단일 요소, 동일 우선순위의 안정성, 정수 극값, 교차 연산 테스트를 항상 실행합니다. 그다음 고정 시드 묶음으로 모델 비교 테스트를 수행합니다. 새롭게 실패를 일으킨 시드는 장기 회귀 테스트 집합에 추가해야 합니다. 단순히 무작위 테스트 횟수만 늘려 다시 실행하는 데 그쳐서는 안 됩니다.

순번 소진은 일반적인 삽입 횟수로는 테스트할 수 없습니다. 실제 모듈에는 테스트 전용 내부 초기화 경로를 두어 카운터를 상한 직전으로 설정할 수 있습니다. 이를 통해 마지막으로 허용되는 삽입과 그다음 거부되는 삽입의 경계를 확인하되, 운영 상태를 수정할 수 있는 공개 인터페이스를 만들지는 않아야 합니다.

Swift 툴체인 버전, 커밋 식별자, 실패한 연산열만 보관하면 되며 업무 페이로드까지 저장할 필요는 없습니다. 최종 검증 결과에는 이 테스트가 직렬 큐의 순서와 경계 동작을 검증할 뿐, 스레드 안전성이나 작업 실행 성공률, 스케줄링 공정성까지 보장하지는 않는다는 점을 명확히 밝혀야 합니다. 이 경계를 분명히 적어 두어야 나중에 실행기를 연결할 때 자료구조 테스트를 전체 시스템에 대한 보장으로 오해하지 않습니다.

자주 묻는 질문