종량제 데이터베이스에서 커서 페이지네이션이 Skip보다 나은 이유

오프셋 페이지네이션은 청구서가 도착하기 전까지는 공짜처럼 느껴집니다. 문서를 읽을 때마다 요금이 부과되는 데이터베이스에서 skip(N)는 앞으로 건너뛰는 지름길이 아닙니다. 건너뛰는 모든 문서를 읽고 버리며, 각각에 대해 비용을 지불해야 합니다. 이 게시물에서는 실제 산술 계산을 통한 비용 차이, 오프셋을 완전히 대체하는 커서 기반 쿼리, 순서를 전체적으로 유지하는 동점 처리기(tie-breaker), 그리고 일반 skip가 여전히 올바른 선택인 한 가지 경우를 보여줍니다.

skip의 실제 동작 방식

skip(N)는 N번째 결과로 순간 이동하는 것처럼 보이지만, 데이터베이스는 처음 N개의 문서를 탐색하지 않고는 N번째 문서가 어디에 있는지 알 방법이 없습니다. 임의의 필터와 정렬에 대해 '380번째 일치하는 행'으로 바로 가는 인덱스는 없습니다. 따라서 엔진은 정렬된 결과 집합의 시작에서 N개의 문서를 건너뛴 다음, 비로소 사용자에게 행을 반환하기 시작합니다.

고정된 컬렉션에서는 페이지를 깊게 나누지 않으므로 아무도 눈치채지 못합니다. 비용은 컬렉션이 크고 사용자가 그 안으로 깊이 들어가는 두 가지가 동시에 해당될 때 발생합니다. 페이지 크기가 20일 때 20페이지에서 skip(380).limit(20)는 사용자에게 20개의 문서를 주기 위해 400개의 문서를 읽습니다. 나머지 380개는 사용자의 페이지가 시작되기도 전에 읽고, 수를 세고, 폐기됩니다. 사용자가 요청하지도 않았고 볼 수도 없는 문서들이지만, 종량제 데이터베이스에서는 이 모든 문서에 대해 요금이 청구됩니다.

숫자로 보는 비용

두 가지 전략을 나란히 놓고 비교해 보겠습니다. 중요한 열은 마지막 열인데, 실제 트래픽이 발생했을 때 청구서에 표시되는 내용이기 때문입니다.

skip 행은 페이지 깊이에 따라 증가합니다. cursor 행은 그렇지 않습니다. 3페이지에 있든 3,000페이지에 있든 매번 정확히 페이지 크기만큼 읽습니다. 그리고 사이트가 성장해도 둘 사이의 비율은 줄어들지 않고 오히려 벌어지는데, 컬렉션이 클수록 사람들이 더 깊이 페이지를 매기는 상황이 되기 때문입니다. skip의 최악의 경우는 바로 돈을 잃을 트래픽이 가장 많을 때 발생합니다.

비용 이야기와 비슷한 지연 시간 이야기가 있습니다. 380개의 문서를 읽고 버리는 것은 비용이 청구될 뿐만 아니라 속도도 느리고, 페이지가 깊어질수록 더 느려집니다. 커서 페이지네이션은 페이지당 일정한 작업을 수행하므로 지연 시간이 일정합니다.

이를 대체하는 커서 쿼리

오프셋 대신, 현재 페이지의 마지막 항목에 대한 정렬 키를 전달하고 다음 페이지에서는 그 뒤에 정렬된 행을 요청합니다. 어떤 것도 지나쳐서 세는 과정이 없습니다. 데이터베이스는 커서 위치의 인덱스로 바로 이동하여 페이지를 읽습니다.

// Carry the last item's sort key forward. Each page reads exactly what it
// returns, no matter how deep you are.
filter := bson.M{"published_at": bson.M{"$lt": cursor}}
opts := options.Find().
	SetSort(bson.D{{"published_at", -1}}).
	SetLimit(20)

rows, err := coll.Find(ctx, filter, opts)

커서는 페이지 번호가 아닙니다. 표시한 마지막 행의 정렬 필드 값이며, 여기서는 published_at입니다. 다음 요청은 "이 타임스탬프보다 오래된 가장 최신 행 20개를 주세요"라는 내용이며, published_at에 인덱스가 있기 때문에 엔진은 해당 지점으로 이동하여 앞으로 읽어 나갑니다. 페이지 깊이는 수행되는 작업과 관련이 없습니다.

순서를 완전하게 만드는 동점 처리 규칙

첫 번째 쿼리에는 버그가 숨어 있으며, 이는 모든 사람이 두 번째로 마주치는 버그입니다. 두 문서가 동일한 published_at를 공유하고 실제 시스템에서는 그럴 경우, "이 타임스탬프보다 오래된"이라는 조건은 모호해집니다. 타임스탬프에 대한 엄격한 $lt는 커서의 타임스탬프를 공유하는 행을 건너뛸 수 있고, 엄격하지 않은 $lte는 방금 보여준 행을 반복할 수 있습니다. 어느 쪽이든 페이지 경계가 잘못되어 사용자는 페이지 사이의 경계에서 정확히 중복되거나 누락된 항목을 보게 됩니다.

해결책은 고유한 동점 처리 규칙을 추가하여 정렬 순서를 완전하게 만들어 어떤 두 문서도 동일하게 비교되지 않도록 하는 것입니다. _id가 자연스러운 선택이며, ULID처럼 ID 자체가 의미 있게 정렬될 때 더욱 좋습니다. 커서는 한 쌍이 되고 비교는 복합 비교가 됩니다.

// Compound cursor: (published_at, _id). No two rows compare equal, so the
// page boundary is exact. Works because _id is unique and ULIDs sort by time.
filter := bson.M{
	"$or": []bson.M{
		{"published_at": bson.M{"$lt": cur.PublishedAt}},
		{"published_at": cur.PublishedAt, "_id": bson.M{"$lt": cur.ID}},
	},
}
opts := options.Find().
	SetSort(bson.D{{"published_at", -1}, {"_id", -1}}).
	SetLimit(20)

"엄격하게 더 오래된 모든 것, 그리고 동일한 타임스탬프 내에서는 더 작은 ID를 가진 모든 것"으로 읽으십시오. _id는 고유하므로 결합된 정렬은 완전하며, 따라서 모든 행은 정확히 하나의 위치를 가지며 N 페이지와 N+1 페이지 사이의 경계는 정확히 한 곳에 위치하게 됩니다. 경계에서 중복되는 행도, 누락되는 행도 없습니다. 이것이 바로 정렬 가능하고 고유한 ID를 제공하는 데이터베이스가 커서 페이지네이션과 잘 어울리는 이유입니다. ID가 무작위 ULID이거나 파생된 ID인 경우, 이미 필요한 동점 처리 규칙을 가지고 있는 것입니다. 안정적이고 정렬 가능한 ID의 파생에 대해서는 결정적 ULID에서 다룹니다.

이 쿼리에 필요한 인덱스

커서 페이지네이션은 정렬이 인덱스로 지원되는 경우에만 빠르며, 복합 커서는 정렬과 동일한 필드 순서의 복합 인덱스를 필요로 합니다. 그것이 없으면 엔진은 스캔으로 대체되며, 당신은 청구 문제를 지연 시간 문제와 맞바꾼 셈입니다.

// The sort is (published_at desc, _id desc), so the index must match.
{Keys: bson.D{{"published_at", -1}, {"_id", -1}}, Name: "published_at_id"}

규칙은 인덱스 키 순서가 정렬 키 순서를 반영한다는 것입니다. 그 순서 일치를 올바르게 맞추면 쿼리는 인덱스 탐색 후 정확히 한 페이지를 순차적으로 읽게 됩니다. 잘못 맞추면 데이터베이스는 조용히 스캔을 수행하며, 이는 종량제 엔진에서는 다른 가면을 쓴, 당신이 피하려던 바로 그 비싼 작업입니다.

포기해야 하는 것과 해결 방법

커서 페이지네이션에는 장단점이 있습니다. 가장 큰 단점은 임의의 페이지로 이동할 수 없다는 것입니다. 47페이지의 커서는 46페이지의 마지막 행인데, 그곳까지 가지 않으면 이 값을 알 수 없으므로 "47페이지로 이동"과 같은 기능은 불가능합니다. 고전적인 "1 2 3 ... 47" 페이저와 같은 번호가 매겨진 페이지 링크는 이 모델에 맞지 않습니다.

대부분의 최신 인터페이스에서는 이것이 괜찮은데, 지배적인 패턴이 다음 페이지(next-page)와 무한 스크롤(infinite scroll)이기 때문입니다. 이 두 가지 모두 바로 다음 페이지에 대한 커서만 필요합니다. 뒤로 이동해야 할 때는 현재 페이지의 첫 번째 행에 대한 두 번째 커서를 유지하고, 비교와 정렬을 반대로 하여 미러 이미지 쿼리를 실행합니다. 앞으로 가는 커서와 뒤로 가는 커서, 이 두 커서는 다음(next)과 이전(previous)을 처리하며, 이것이 실제 페이지네이션 UI가 사용하는 방식입니다.

진정으로 잃는 것은 저렴한 전체 개수, 따라서 저렴한 "Y 중 X 페이지" 표시입니다. 일치하는 모든 행을 세는 것은 대규모 컬렉션에서 계량 여부와 상관없이 그 자체로 비용이 많이 드는 쿼리입니다. 보통은 UI에서 전체 개수를 빼는 것이 정직한 방법입니다. 왜냐하면 "2,847 중 3 페이지"는 아무도 그에 따라 행동하지 않는 숫자이며, 이것을 표시하려면 매 페이지 로드마다 전체 개수를 세는 비용이 들기 때문입니다.

skip이 여전히 올바른 도구일 때

이 모든 것이 모든 곳에서 오프셋 페이지네이션이 잘못되었다는 것을 의미하지는 않습니다. 결코 깊게 페이지를 넘기지 않을 작고 한정된 컬렉션, 즉 수백 개의 행으로 이루어진 관리자 테이블이나 설정 목록의 경우, skip의 단순함이 더 좋으며 N이 결코 커지지 않기 때문에 비용은 무시할 수 있습니다. 그런 경우에 복합 커서와 일치하는 인덱스를 사용하는 것은 과도한 설계입니다.

경험 법칙은 크기만이 아니라 깊이에 관한 것입니다. 페이지 깊이가 제한적이고 작다면 skip는 괜찮고 더 간단합니다. 페이지 깊이가 무한하다면, 즉 사용자가 깊이 들어갈 수 있고 실제로 그렇게 할 것이라면 커서를 사용하십시오. 왜냐하면 바로 그런 상황에서 오프셋의 비용이 무한정 증가하고 종량제 데이터베이스는 그 증가를 청구 항목으로 바꾸기 때문입니다. 사람들이 실제로 얼마나 깊이 들어가는지에 따라 컬렉션별로 결정하면, 각 도구를 진정으로 더 저렴한 곳에 사용하게 될 것입니다.