[Python] 페이지네이션 경계 추정이 빗나갈 때: ID 밀도 점프와 지수이동평균 보정

목록 페이지가 1페이지부터 최신 항목을 역순으로 나열하고, 각 항목이 단조증가하는 정수 ID를 가지는 사이트에서 “이 ID보다 오래된 항목이 있는 페이지"를 찾아야 한다면, 가장 단순한 방법은 1페이지부터 순서대로 넘기며 매 페이지를 확인하는 것이다. 개인 iptorrents 크롤러에 “이전에 확인한 범위보다 오래된 항목 N개를 마저 확인한다"는 기능을 붙이면서 처음 택한 방법도 이것이었다. 문제는 목표 지점이 15–20페이지쯤 떨어져 있을 때다. 순차 스캔은 그만큼의 연속 요청을 발생시키고, 사이트가 짧은 시간에 몰린 요청을 레이트리밋으로 막을 위험이 커진다. 실제로 이 크롤러는 레이트리밋 응답을 파서가 “더 이상 항목 없음"으로 잘못 해석해 버리는 바람에, 매번 0건을 조용히 반환하는 사일런트 실패를 겪었다. 이 글은 순차 스캔을 점프 방식으로 바꾸면서 거쳐간 네 번의 설계 버전과, 그중 세 번이 왜 실측 데이터 앞에서 깨졌는지를 정리한다.

핵심 아이디어 — ID 밀도로 페이지를 추정하고, 어긋나면 실측값으로 다시 추정한다

1페이지에 나열된 항목들의 최상단 ID와 최하단 ID의 차이를 항목 개수로 나누면 “항목 하나당 ID가 몇 증가하는지"를 구할 수 있다. 여기에 페이지당 항목 수를 곱하면 “페이지당 ID 증가폭"이 나오고, 목표 ID가 1페이지 최상단 ID로부터 얼마나 떨어져 있는지를 이 값으로 나누면 목표 근처의 페이지 번호를 바로 계산해 그 페이지로 곧장 이동할 수 있다. 정렬된 배열에서 값의 분포로 위치를 어림잡아 뛰어드는 보간 탐색(interpolation search)과 같은 발상이다.

1
2
3
4
5
6
def estimate_page(target_id: int, top_id: int, items_per_page: int, id_density: float) -> int:
    """id_density: 실측된 '페이지당 ID 증가폭'. 1페이지 자체값 또는 저장된 캘리브레이션값."""
    offset = top_id - target_id
    if offset <= 0:
        return 1
    return max(1, round(offset / id_density) + 1)

다만 이 추정은 항상 정확하지 않다. 이유는 두 가지다. 첫째, 게시 빈도가 시간대나 구간마다 달라서 실제 페이지당 ID 밀도가 지점마다 다르다. 둘째, 1페이지 자체의 밀도는 최신 구간의 밀도이고, 크롤러가 찾으려는 오래된 구간의 밀도와 체계적으로 다를 수 있다. 실측 결과 1페이지 근처는 페이지당 약 1,485개, 15페이지 뒤쪽은 페이지당 약 1,785개로 20% 가까이 차이가 났다. 그래서 추정한 페이지에 도착한 뒤 실제로 목표 ID가 그 페이지 범위 안에 있는지 확인하고, 아니라면 보정해야 한다. 이 보정 로직을 만드는 과정에서 세 가지 버전이 차례로 깨졌다.

실패한 중간 버전 세 가지

버전	아이디어	왜 충분하지 않았는가
v1: 추정 페이지에서 멈춤	밀도로 계산한 페이지에 도착하면 그대로 그 페이지부터 수집 시작	추정이 빗나가면 경계가 아닌 지점에서 시작해, 목표보다 새 항목을 놓치거나 이미 확인한 항목을 다시 수집한다
v2: 한 페이지만 보정	추정이 빗나가면 앞/뒤로 딱 한 페이지만 이동해서 재확인	실측 데이터로 검증하니 추정이 2페이지 이상 벗어나는 경우가 있었고, 한 페이지만 보정하면 경계에 낀 항목 일부를 건너뛰는 버그가 실측으로 확인됐다
v3: 경계를 찾을 때까지 ±1페이지씩 계속 보정	목표 ID보다 전부 새 항목인 페이지와 전부 오래된 항목인 페이지 사이, 즉 신규·과거가 섞인 진짜 경계 페이지를 찾을 때까지 한 페이지씩 계속 이동	대부분 동작했지만, 요청 횟수에 직접 상한을 걸고 나니(아래 참고) 추정이 4페이지 이상 벗어나는 사례(52로 추정했는데 실제 경계는 48)에서 ±1페이지 보정이 상한 예산을 다 쓰고도 경계에 못 닿았다

v3까지는 “한 페이지씩 걸어서 접근한다"는 전제를 공유한다. 이 전제가 무너진 계기는 알고리즘을 더 똑똑하게 만드는 시도가 아니라, 뒤에서 다룰 안전장치(요청 횟수 상한)를 먼저 걸어둔 상태에서 실측 데이터를 돌린 결과였다. 상한이 없을 때는 v3도 결국 경계에 도달했겠지만, 요청 예산이 정해진 상태에서는 “한 페이지씩” 걷는 속도 자체가 문제가 된다.

v4(최종) — 보정 중 실측 밀도로 재추정

v3의 실패를 고친 방법은 한 페이지씩 걷는 대신, 보정할 때마다 “1페이지부터 방금 확인한 페이지까지의 실측 ID 밀도"로 추정식을 다시 계산해 한 번에 더 정확한 지점으로 재점프하는 것이다.

1
2
3
4
5
def correct_estimate(target_id: int, top_id: int, checked_page: int, checked_top_id: int) -> int:
    """checked_page에서 실제로 관측한 ID로 밀도를 다시 계산해 재점프한다."""
    observed_density = (top_id - checked_top_id) / (checked_page - 1)
    offset = top_id - target_id
    return max(1, round(offset / observed_density) + 1)

52페이지로 추정했다가 실제 경계가 48페이지였던 사례에서, v4는 52 → 48(재추정으로 한 번에 도달) → 49(배치 채우기) 순서로 같은 요청 예산 안에 문제를 해결하는 것을 실측으로 확인했다. v3라면 52 → 51 → 50 → 49 → 48로 최소 네 번의 보정 요청이 필요했을 자리를, v4는 재추정 한 번으로 줄인 것이다. 핵심은 “빗나간 방향으로 한 걸음씩 가는 것"과 “빗나간 정도 자체를 새로운 정보로 써서 추정식을 다시 푸는 것"의 차이다.

실행 간 지속되는 보정값 — 지수이동평균 캘리브레이션

1페이지 자체의 밀도만으로 추정하면, 앞서 말한 “최신 구간과 오래된 구간의 밀도 차이” 때문에 매 실행마다 같은 방향으로 추정이 빗나간다. 해결책은 실행이 끝날 때마다 “이번에 실제로 경계를 찾은 위치"로 역산한 밀도값을 history.json에 저장해두고, 다음 실행에서는 1페이지 자체 밀도 대신 이 저장된 값을 우선 사용하는 것이다. 갱신은 단순 덮어쓰기가 아니라 지수이동평균(exponential smoothing)으로 처리해, 어쩌다 한 번 튄 관측값이 추정치를 급격히 흔들지 않고 완만하게 수렴하도록 했다.

1
2
3
4
def update_calibration(old_density: float | None, observed_density: float, alpha: float = 0.3) -> float:
    if old_density is None:
        return observed_density
    return old_density * (1 - alpha) + observed_density * alpha

캘리브레이션이 없을 때는 매 실행 목록 페이지 요청이 4회 필요했다(추정이 매번 같은 방향으로 초과했기 때문이다). 캘리브레이션이 한 번 쌓인 뒤로는 2회로 줄어 그대로 유지됐다. 이후 반복 실행에서도 캘리브레이션 값이 1,673.9 → 1,693.1 → … 식으로 좁은 범위 안에서 완만하게 수렴하는 것을 history.json 변화로 확인했다.

안전장치의 위치 — “페이지 번호 상한"에서 “요청 횟수 상한"으로

초기 구현은 폭주 방지용 안전장치로 MAX_PAGES(초기 40, 이후 500으로 완화)라는 페이지 번호 상한을 뒀다. 그런데 이 크롤러는 “신규 항목이 있으면 신규만 수집하고, 없을 때만 과거 항목을 본다"는 조건 분기를 갖고 있었다. 새 글이 자주 올라오는 시기에는 신규 모드가 계속 이기고 과거 수집이 오래 실행되지 않는 사이, “확인한 최신 ID"와 “확인한 최오래된 ID” 사이의 간격(백로그)이 계속 벌어질 수 있다. 백로그가 커지면 경계 페이지 번호 자체가 커지는데, 페이지 번호 상한은 이 백로그 크기와 무관하게 고정돼 있으므로 언젠가부터 부족해져 경계에 닿기도 전에 막혀 0개만 수집되는 버그가 실제로 발생했다.

해법은 안전장치를 보호하려는 대상 자체에 직접 상한을 거는 것이었다. 페이지 번호가 아니라 실제 목록 페이지 요청 횟수(MAX_LIST_REQUESTS = 3)를 제한하면, 점프 방식의 특성상 목표 페이지가 아무리 멀어도 필요한 요청 수는 산술적으로 적게 유지되므로 백로그 크기와 무관하게 안전하다. 예산을 다 쓰면 이번 실행은 포기하고, 다음 실행이 갱신된 캘리브레이션 값으로 다시 시도한다. 이는 간접 지표(페이지 번호)에 안전장치를 거는 대신, 실제로 보호하려는 자원(요청 횟수)에 직접 상한을 건다는 일반화 가능한 설계 원칙의 구체적인 사례다 — 재시도 로직에서 “재시도 횟수"가 아니라 “누적 대기 시간"에 상한을 거는 것과 같은 방향의 판단이다.

남은 근본 원인 — 조건부로만 실행되는 유지보수 작업

요청 횟수 상한과 재추정 로직을 고친 뒤에도, 반복 크롤링에서 신규 항목이 계속 우선되는 한 과거 백로그 자체는 줄지 않는 근본 문제가 남아 있었다. 최종 해결은 알고리즘을 더 정교하게 만드는 대신 조건 분기 자체를 없애는 것이었다. 첫 실행이 아닌 이상 “신규가 없을 때만 과거를 본다"는 배타적 조건 대신, 매 실행마다 신규와 과거를 모두 확인해서 두 결과를 합치도록 바꿨다.

1
2
3
4
def collect_targets(state) -> list:
    new_items = fetch_new_items(state.last_seen_id)
    older_items = fetch_older_items(state.oldest_checked_id)  # 더 이상 신규 여부에 조건부가 아니다
    return new_items + older_items

새 글이 아무리 자주 올라와도 과거 백로그가 매 실행 같이 줄어들게 되어, 반복됐던 “간격이 계속 벌어지는” 현상의 근본 원인이 해소됐다. 대신 한 실행에서 확인하는 항목 수가 최대 100개까지 늘어 실행 시간이 다소 길어지는 트레이드오프는 남는다. 이 마지막 수정이 주는 교훈은, “언제 실행할지"를 조건으로 감싼 유지보수 작업은 그 조건이 계속 거짓이 되는 상황에서 무기한 미뤄질 수 있다는 것이다 — 알고리즘이 아무리 정교해져도, 애초에 실행되지 않으면 소용이 없다.

자주 하는 실수

한 페이지씩 걸어서 보정하는 방식을 “안전한 재시도"로 착각한다. 추정이 몇 페이지나 벗어날 수 있는지 실측하지 않은 채 ±1페이지 보정을 설계하면, 벗어나는 폭이 보정 스텝 수보다 커지는 순간 요청 예산을 다 쓰고도 경계에 못 닿는다. 벗어나는 폭의 실측 분포를 먼저 확인해야 한다.
안전장치를 보호 대상이 아니라 간접 지표에 건다. 페이지 번호 상한은 “요청이 너무 많아지는 것"을 막으려는 목적이었지만, 정작 상한을 건 지표(페이지 번호)는 크롤러 내부 상태(백로그 크기)에 따라 필요한 값 자체가 달라진다. 보호하려는 자원(요청 횟수, 대기 시간 등)에 직접 상한을 걸어야 백로그 변화와 무관하게 안전하다.
레이트리밋 응답을 파서가 “결과 없음"으로 오인하는 경로를 방치한다. HTTP 상태 코드나 응답 본문을 구분하지 않고 “항목 목록이 비어 있음"으로만 처리하면, 레이트리밋으로 차단된 요청과 실제로 더 이상 항목이 없는 상황이 코드 상에서 구별되지 않는다. 이 경우 매번 0건만 조용히 반환되는 사일런트 실패가 발생하며, 사용자가 “왜 새 항목이 안 늘어나냐"고 묻기 전까지 눈에 띄지 않는다.
조건부로만 실행되는 유지보수 작업을 그대로 둔다. “다른 조건이 거짓일 때만” 실행되도록 짠 로직은, 그 다른 조건이 계속 참으로 유지되는 상황(이 경우 신규 항목이 꾸준히 올라오는 것)에서 무기한 밀릴 수 있다. 배타적 조건을 없애고 매번 함께 실행하는 편이 근본적으로 더 안전하다.

요약

이 크롤러는 “밀도 기반 추정으로 근처까지 점프 → 실제 경계를 찾을 때까지 실측 밀도로 재추정하며 보정 → 이번에 찾은 실측 밀도를 다음 실행을 위해 지수이동평균으로 영구 저장 → 안전장치는 페이지 번호가 아니라 실제 요청 횟수에 직접 걸기 → 신규·과거 수집을 배타적 조건이 아니라 항상 둘 다 실행"이라는 다섯 요소가 조합되어야 완성됐다. 어느 하나만 있으면 위 표의 실패 사례들처럼 다시 깨진다. 사이트의 레이트리밋을 유발하지 않는 것(요청 횟수 최소화)과 항목을 하나도 빠뜨리지 않는 것(경계에 낀 항목을 건너뛰지 않는 것)이 최우선 제약이었고, 실행 시간이나 코드 복잡도는 후순위로 다뤘다. 다만 캘리브레이션은 과거 관측치의 이동평균이므로, 사이트의 게시 패턴이 갑자기 크게 바뀌면 재수렴하는 데 몇 차례의 실행이 걸린다는 트레이드오프는 남아 있다.

참고 자료

Wikipedia, “Interpolation search” — 정렬된 데이터에서 값의 분포로 위치를 추정해 점프하는 탐색 기법의 개념: https://en.wikipedia.org/wiki/Interpolation_search
Wikipedia, “Exponential smoothing” — 최근 관측값에 더 큰 가중치를 주며 완만하게 수렴하는 이동평균 기법: https://en.wikipedia.org/wiki/Exponential_smoothing
본문의 알고리즘·수치(요청 횟수 4회→2회, 밀도 1,485/1,785/1,693 등)는 외부 문헌 인용이 아니라 이 프로젝트 자체의 iptorrents.com 대상 실측 검증 결과다.