클라우드 Mac에서 iOS LRU 캐시의 제거 순서와 용량 검증하기

목록을 여러 페이지 연속으로 넘겼더니 캐시가 예상 용량에 도달하지도 않았는데 방금 본 데이터가 제거되는 경우가 있습니다. 메모리부터 늘리지는 마세요. 읽을 때 접근 순서를 갱신하지 않거나, 같은 키를 업데이트하면서 중복 레코드를 남기는 문제가 더 흔합니다. 클라우드 Mac에서 캐시 로직을 독립 Swift Package로 분리하면 UI, 네트워크, 시뮬레이터 없이도 결과가 명확한 짧은 연산 시퀀스 몇 개로 문제를 재현할 수 있습니다.

캐시 계약 다섯 가지부터 명확히 정의하기

이 글에서는 항목 수로 용량을 제한하는 LRU를 검증합니다. 가장 오랫동안 사용하지 않은 항목부터 제거하며, 만료 시간과 디스크 영속성은 다루지 않습니다. 먼저 다음 다섯 가지 규칙을 확정합니다.

• 읽기가 적중하면 해당 키를 가장 최근에 사용한 위치로 옮깁니다.
• 읽기가 실패하면 기존 순서를 바꾸지 않습니다.
• 이미 있는 키에 쓰면 값과 사용 순서만 갱신하고, 항목 수는 늘리지 않습니다.
• 새 키를 쓴 뒤 용량을 초과하면 가장 오랫동안 사용하지 않은 키를 제거합니다.
• 용량이 0이면 데이터를 저장하지 않습니다. 음수 용량은 호출 오류로 간주합니다.

이 규칙은 구현 세부 사항에서 역으로 추론할 것이 아니라 팀에서 합의해야 합니다. 예를 들어 읽기가 항목의 생존 기간을 연장하지 않기를 원하는 비즈니스 요구사항도 있습니다. 이는 여기서 정의한 접근 정책과 다르므로 같은 기대 결과를 그대로 적용할 수 없습니다.

적중률은 운영 지표이고, 제거 순서는 기능 계약입니다. 적중률이 정상으로 보여도 같은 키의 중복 저장이나 잘못된 제거가 숨어 있을 수 있습니다.

독립 디렉터리에 상태를 관찰할 수 있는 모델 구현하기

노드에 전체 도구 체인을 설치한 뒤 별도의 작업 디렉터리에서 다음 두 명령을 실행합니다. 관리자 권한이나 그래픽 인터페이스 실행은 필요하지 않습니다.

mkdir LRUContract
cd LRUContract
swift package init --type library

Sources/LRUContract/LRUContract.swift를 다음 구현으로 교체합니다. 순서 배열은 검증하기 쉽도록 가장 오래된 키부터 가장 최근 키까지 정렬합니다. 대용량 캐시의 성능을 고려한 구현은 아닙니다.

public final class LRU<Key: Hashable, Value> {
    private let capacity: Int
    private var values: [Key: Value] = [:]
    public private(set) var oldestFirst: [Key] = []

    public init(capacity: Int) {
        precondition(capacity >= 0)
        self.capacity = capacity
    }

    public var count: Int { values.count }

    public func get(_ key: Key) -> Value? {
        guard let value = values[key] else { return nil }
        touch(key)
        return value
    }

    public func put(_ key: Key, _ value: Value) {
        guard capacity > 0 else { return }
        values.updateValue(value, forKey: key)
        touch(key)
        if values.count > capacity {
            let victim = oldestFirst.removeFirst()
            values.removeValue(forKey: victim)
        }
    }

    private func touch(_ key: Key) {
        oldestFirst.removeAll { $0 == key }
        oldestFirst.append(key)
    }
}

touch는 기존 위치를 먼저 삭제한 다음 새 위치에 추가하므로 같은 키가 순서 배열에서 두 자리를 차지하지 않습니다. 쓰기에는 updateValue를 사용해 딕셔너리 서브스크립트 대입의 삭제 의미가 갱신 로직에 섞이지 않도록 했습니다. 프로덕션 구현을 딕셔너리와 이중 연결 리스트 조합으로 바꾸더라도 이 글의 테스트는 유지할 수 있습니다. 다만 이 배열 버전의 시간 복잡도가 상수 시간이라고 주장해서는 안 됩니다.

짧은 시퀀스로 읽기 오류와 갱신 오류 구분하기

테스트 디렉터리에 자동 생성된 예제 테스트를 삭제하고, 다음 내용을 Tests/LRUContractTests/LRUContractTests.swift로 저장합니다. 초기화 템플릿에서 어떤 테스트 프레임워크를 선택했는지와 관계없이 XCTest를 명시적으로 사용합니다.

import XCTest
@testable import LRUContract

final class LRUContractTests: XCTestCase {
    func testReadPromotesAndMissDoesNot() {
        let cache = LRU<String, Int>(capacity: 2)
        cache.put("a", 1)
        cache.put("b", 2)
        XCTAssertNil(cache.get("missing"))
        XCTAssertEqual(cache.oldestFirst, ["a", "b"])
        XCTAssertEqual(cache.get("a"), 1)
        XCTAssertEqual(cache.oldestFirst, ["b", "a"])
        cache.put("c", 3)
        XCTAssertNil(cache.get("b"))
        XCTAssertEqual(cache.oldestFirst, ["a", "c"])
        XCTAssertEqual(cache.count, 2)
    }

    func testUpdateDoesNotConsumeAnotherSlot() {
        let cache = LRU<String, Int>(capacity: 2)
        cache.put("a", 1)
        cache.put("b", 2)
        cache.put("a", 9)
        XCTAssertEqual(cache.count, 2)
        XCTAssertEqual(cache.oldestFirst, ["b", "a"])
        cache.put("c", 3)
        XCTAssertNil(cache.get("b"))
        XCTAssertEqual(cache.get("a"), 9)
    }

    func testZeroCapacityStoresNothing() {
        let cache = LRU<String, Int>(capacity: 0)
        cache.put("a", 1)
        XCTAssertEqual(cache.count, 0)
        XCTAssertTrue(cache.oldestFirst.isEmpty)
        XCTAssertNil(cache.get("a"))
    }
}

swift test를 실행합니다. 첫 번째 테스트가 실패하면 대개 읽기 시 순서 승격이나 캐시 미스의 부작용을 살펴봐야 합니다. 두 번째가 실패하면 같은 키를 갱신하는 로직부터 확인합니다. 세 번째는 용량이 0인데도 항목 하나가 남는 문제를 방지합니다. 최종 항목 수만 검증해서는 안 됩니다. 개수가 맞더라도 남아 있는 키는 완전히 잘못됐을 수 있습니다.

검증 동작 자체가 순서를 바꿀 수 있음에 주의하기

get은 상태를 바꾸지 않는 관찰용 인터페이스가 아닙니다. 값을 확인하려고 호출해도 다음에 제거될 대상이 바뀝니다. 따라서 위 예제에서는 순서를 먼저 확인한 뒤 값을 읽습니다. 테스트에서 무심코 모든 키를 순회하며 get을 호출하면 테스트 자체가 검증 대상 상태를 바꾸게 됩니다.

세 가지 테스트에서 시퀀스 기반 검증으로 확장하기

실제 캐시를 연결할 때는 용량이 1인 경우, 같은 키를 연속으로 덮어쓰는 경우, 캐시 미스가 연속으로 발생하는 경우, 제거한 키를 다시 삽입하는 경우의 네 가지 시퀀스를 추가합니다. 각 단계에서 항목 수가 용량을 넘지 않는지, 순서에 중복 키가 없는지, 순서 배열의 길이가 실제 항목 수와 같은지 확인합니다.

검증을 더 확장하려면 고정 시드의 의사 난수 연산을 사용할 수 있습니다. 다만 시드뿐 아니라 전체 연산 목록도 보관해야 합니다. 실패 기록에는 최소한 연산 번호, 키, 쓰는 값, 실행 전후 순서가 포함되어야 구현을 업그레이드한 뒤에도 재현할 수 있습니다.

프로덕션 버전이 연결 리스트를 사용한다면 단순한 배열 모델을 참조 구현으로 삼아 양쪽에 같은 시퀀스를 실행하고 결과를 비교합니다. 프로덕션 구현을 복사해 ‘정답’으로 사용하지 마세요. 그러면 같은 결함이 양쪽에서 모두 검증을 통과하기 쉽습니다.

iOS 프로젝트에 다시 연결할 때 지켜야 할 경계

이 예제에는 동기화 장치가 없습니다. 비동기 다운로드 작업이 두 개뿐이어도 이 객체를 그대로 공유해서는 안 됩니다. actor나 단일 직렬 진입점을 사용하고, 읽기에 따른 순서 승격과 쓰기, 제거를 모두 함께 보호해야 합니다. 쓰기에만 락을 걸면 여전히 순서가 망가질 수 있습니다.

항목 수 제한이 바이트 수 제한을 의미하지도 않습니다. 썸네일 열 장과 원본 이미지 열 장의 메모리 비용은 다릅니다. 비용 기반 용량 제한으로 바꾼다면 총비용, 같은 키의 비용 교체, 지나치게 큰 단일 항목의 거부 규칙을 별도로 정의해야 합니다. 기존 항목 수 테스트를 메모리 예산을 지킨다는 근거로 삼을 수는 없습니다.

마지막으로 테스트가 학습용 모델에만 머무르지 않도록 실제 서비스 캐시를 같은 계약에 맞춰 연결합니다. 순수 알고리즘 테스트를 통과한 뒤에는 소수의 통합 테스트로 다운로드 완료 후의 쓰기와 UI 읽기가 실제로 같은 인스턴스를 사용하는지 확인합니다. 실패한 시퀀스를 보관하는 편이 무작정 캐시 용량을 늘리는 것보다 문제 해결에 더 도움이 됩니다.

자주 묻는 질문