급변하는 콘텐츠 목록을 처리 할 수있는 페이지 매김 방식은 무엇입니까?

Question

콘텐츠 등급이 빠르게 변경 될 수있는 경우 페이지 매김이 어려우며 사용자 별 순위가 다를 때 페이지가 더 힘들어집니다. (무한한 스크롤을 링크가 보이지 않는 일종의 페이지 매김으로 취급합시다.) 두 가지 어려운 문제가 있습니다. 처음에 새로 추가 된 내용과 다시 읽은 내용입니다.

새로 추가 된 콘텐츠를 잊어 버리고 페이지 1을 새로 고침하여보아야합니다. 우리가 순수한 것을하는 척하자. ORDER BY position; 다른 명령으로 주문하는 경우 창 기능을 사용해야 할 수도 있습니다. 우리 페이지에는 페이지 당 4 행의 동물이 있습니다. 우리는 1 페이지를 가져

+----+----------+-----------+ 
| id | position^| animal | 
+----+----------+-----------+ 
| 1 |  1 | Alpacas | 
| 2 |  2 | Bats  | 
| 3 |  3 | Cows  | 
| 4 |  4 | Dogs  | 
| 5 |  5 | Elephants | 
| 6 |  6 | Foxes  | 
| 7 |  7 | Giraffes | 
| 8 |  8 | Horses | 
+----+----------+-----------+ 

후, 우리는 2 페이지를 가져 오기 전에 항목이 많이 이동할 : 그들은 시작합니다. DB를 지금 : 일반적인 세 ​​가지 방법이 있습니다

+----+----------+-----------+ 
| id | position^| animal | 
+----+----------+-----------+ 
| 4 |  1 | Dogs  | 
| 2 |  2 | Bats  | 
| 1 |  3 | Alpacas | 
| 5 |  4 | Elephants | 
| 6 |  5 | Foxes  | 
| 7 |  6 | Giraffes | 
| 3 |  7 | Cows  | 
| 8 |  8 | Horses | 
+----+----------+-----------+ 

:

오프셋/제한 접근

이 전형적인 순진 접근 방법이다; Rails에서는 will_paginate 및 Kaminari이 작동하는 방식입니다. 2면을 가져 오려면

SELECT * FROM animals 
ORDER BY animals.position 
OFFSET ((:page_num - 1) * :page_size) 
LIMIT :page_size; 

행이 5-8 행이됩니다. 나는 코끼리를 결코 보지 않을 것이다. 그리고 나는 암소를 두 번 볼 것이다.

마지막 ID 방식을

레딧 다른 접근 방식을 취를 본. 페이지 크기를 기반으로 첫 번째 행을 계산하는 대신 클라이언트는 북마크와 같이 본 마지막 항목의 ID를 추적합니다. "다음"을 클릭하면 그 북마크에서부터 검색을 시작합니다.

SELECT * FROM animals 
WHERE position > (
    SELECT position FROM animals 
    WHERE id = :last_seen_id 
) 
ORDER BY position 
LIMIT :page_size; 

경우에 따라 페이지/오프셋보다 잘 작동합니다. 그러나 우리의 경우, 마지막으로 본 포스트 인 Dogs는 # 1로 확대되었습니다. 그래서 클라이언트는 ?last_seen_id=4을 보내고 내 페이지 2는 박쥐, 알파카, 코끼리, 여우입니다. 나는 어떤 동물도 놓치지 않았다. 그러나 나는 Bats와 Alpacas를 두 번 본다.

서버 측 상태

HackerNews (지금 당장 사이트)이 서버 측에 연속성을 해결한다; 그들은 전체 결과 집합을 저장하거나 (적어도 몇 페이지를 미리 작성 했습니까?), "계속"링크는 해당 연속을 참조합니다. 2 페이지를 가져올 때 "원래 쿼리의 2 페이지"를 요청합니다. 그것은 동일한 오프셋/한계 계산을 사용하지만, 원래의 쿼리와는 반대이므로, 이제는 상황이 바뀌어도 상관하지 않습니다. 나는 코끼리, 여우, 기린, 말을 봅니다. 속임수도, 누락 된 아이템도 없습니다.

단점은 서버에 많은 상태를 저장해야한다는 것입니다. HN에 저장된 내용은 RAM에 저장되며, 실제로는 "계속"버튼을 누르기 전에 만료됩니다. 따라서 유효한 링크를 찾기 위해 페이지 1로 다시 이동해야합니다. 대부분의 응용 프로그램에서 memcached 또는 데이터베이스 자체에 저장할 수 있습니다 (자체 테이블 또는 Oracle 또는 PostgreSQL에서 유지 커서를 사용하여). 응용 프로그램에 따라 성능이 저하 될 수 있습니다. PostgreSQL에서 적어도 올바른 데이터베이스 연결을 다시 시작하는 방법을 찾아야합니다.이 방법은 끈적 끈적한 상태 또는 영리한 백엔드 라우팅이 많이 필요합니다.

유일한 방법은 있습니까? 그렇지 않다면, 이것에 관해 읽을만한 Google 주스를 줄 컴퓨터 과학 개념이 있습니까? 전체 결과 집합을 저장하지 않고 연속 접근법을 근사화하는 방법이 있습니까? 장기적으로 볼 때 복잡한 이벤트 스트리밍/포인트 인 타임 시스템이 있는데 "1 페이지를 가져온 순간의 결과 집합"은 영원히 파생됩니다. 그것의 짧은 ...?

Answer 1

우리는 항상 서버 측 상태 접근법을 사용하여 첫 번째 쿼리에서 전체 결과를 캐싱하므로 항상 일관된 목록을 반환합니다. 이것은 쿼리가 이미 모든 행을 반환하는 한 계속 작동합니다. 결국 우리는 가장 가까운 이웃 접근 방법을 사용할 필요가있을 것이고 그것은 작동하지 않을 것이다.

하지만만큼, 매우 잘 확장 네 번째 가능성이 있다고 생각 :

1. 당신은 보증없이 중복 필요하지 않습니다가 만 높은 가능성
2. 당신은있어 만큼 당신이 중복에게

솔루션을 피하고, 스크롤 중에 일부 콘텐츠를 누락 좋아 "마지막 본 ID"솔루션의 변형은 다음과 같습니다 클라이언트가 없습니다 계속 가지고 오 네,하지만 5 또는 10 또는 20 개의 북마크 - 당신이 효율적으로 저장할 수있는 몇 가지. 북마크의 수가 증가함에 따라 는, 확률이 빠르게의 (a) 모든 n 개의 북마크 과거의 어느 시점에서 시작하지만, (b)는 어쨌든 중복 콘텐츠를 보는 사람들 때문에 것을

SELECT * FROM posts 
WHERE id > :bookmark_1 
AND id > :bookmark_2 
... 
ORDER BY id 

감소 : 쿼리처럼 보이는 끝 모두 다 샀어.

미래에 구멍이 있거나 더 나은 답변이 있으면이 답변을 기꺼이 받아 들일 것입니다.

Answer 2

오라클은이를 능숙하게 처리합니다. 커서가 열려있는 한 필요한만큼 가져올 수 있으며 결과는 항상 커서가 열린 시점을 반영합니다. 실행 취소 로그의 데이터를 사용하여 커서가 열린 후 커밋 된 변경 사항을 사실상 롤백합니다.

필요한 롤백 데이터가 아직 사용 가능한 한 계속 작동합니다. 결국 로그가 재활용되고 롤백 데이터는 더 이상 사용할 수 없으므로 로그 공간, 시스템 활동 등에 따라 약간의 제한이 있습니다.

불행히도 (IMO), 나는 다른 DB에 대해 알지 못합니다. 이런 식으로 일합니다. 필자가 작업 한 다른 데이터베이스는 읽기 일관성을 보장하기 위해 잠금을 사용합니다. 매우 짧은 기간 동안 읽기 일관성을 유지하려는 경우 문제가됩니다.

Answer 3

해결 방법 1 : "해키 솔루션은"

해결책은 예를 들어 ID의 이미 본 콘텐츠 목록의 클라이언트 유지 트랙으로 구성 될 수있다. 다른 페이지가 필요할 때마다이 ID 목록을 서버 호출의 매개 변수에 추가합니다. 그런 다음 서버는 컨텐츠를 주문하고 이미 본 컨텐츠를 제거하고 오프셋을 적용하여 올바른 페이지를 얻을 수 있습니다.

나는 그것을 추천하지 않으며 나는 hacky을 고집합니다. 나는 그것이 빨리이고 약간 필요로 적합 할 수 있었기 때문에 다만 여기에서 적는다.여기에 내가 생각할 수있는 나쁜 것들이 있습니다 :

1) 클라이언트 측에서 올바르게 작동하려면 약간의 작업이 필요합니다 (위의 문장에서 "이미 본 것"은 이전 페이지로 이동하면 어떻게됩니까?)

2) 결과 주문에 귀하의 실제 주문 정책이 반영되지 않습니다. 정책은 페이지 1에 표시해야하지만 컨텐츠는 페이지 2에 표시 될 수 있습니다. 사용자 오해로 이어질 수 있습니다. 스택 오버 플로우의 예를 이전 주문 정책과 함께 취해 봅시다. 이는 대부분의 상향 된 응답을 먼저 의미합니다. 우리는 2 페이지에 6 개의 upvotes가있는 질문을 가질 수 있습니다. 4 개의 upvotes가있는 질문은 1 페이지에있을 것입니다. 이것은 사용자가 여전히 1 페이지에있을 때 2 개 이상의 upvotes가 발생했을 때 발생합니다. -> 사용자에게 놀랄 수 있습니다. .

해결 방법 2 : "클라이언트 솔루션"그것은 기본적으로 당신이 "서버 측 상태"라고 부르는 하나의 클라이언트 측 상응하는 솔루션입니다

. 서버 측에서 전체 주문을 추적하는 것이 충분히 편리하지 않은 경우에만 유용합니다. 항목 목록이 무한하지 않으면 작동합니다.

• 는
• 직접 콘텐츠의 식별자를 통해 항목을 검색 클라이언트 측에 저장을 전체 (유한) 순서 목록 + 항목의 수/페이지
• 를 얻기 위해 서버를 호출합니다.

Answer 4

파티에 매우 늦었지만 여기서 실험 해 보았습니다. 우리는 사용자가 앞뒤로왔다 갔다하는 페이지가 아닌 지속적인로드를 사용하고 있습니다.

클라이언트는 표시 한 모든 ID의 목록을 작성, 그래서 첫 세트 후는 다음과 같을 수 있습니다 4,7,19,2,1,72,3

우리가 더 많은 콘텐츠를로드 할 때 우리 같은 종류의 동일한 쿼리를 수행하지만 다음과 같이 추가하십시오. 어디 있지 않은가 (4,7,19,2,1,72,3)

NOT IN 목록이 빠르게 커질 수 있습니다. 우리의 내부 도구는 대개 수 많은 결과를 가져 오지 않으므로 이는 문제가되지 않습니다.

다른 아이디어를 추가하고 싶습니다. 어쩌면 서버 측 추가가이 작업에 적용될 수 있습니다. 사용자가 검색 할 때 모든 ID를 검색에 대한 링크가있는 테이블에 추가합니다. 클라이언트가 더 필요로 할 때 검색 ID를 제공하거나 서버 측 상태를 사용해야 만 쿼리가 검색 데이터에 참여할 수 있습니다.