Sơ đồ phân trang nào có thể xử lý danh sách nội dung thay đổi nhanh chóng?

Question

Phân trang khó khi xếp hạng nội dung của bạn có thể thay đổi nhanh chóng và thậm chí khó hơn khi những thứ hạng này khác nhau cho mỗi người dùng. (Hãy xem cuộn vô hạn như một kiểu phân trang nơi các liên kết không nhìn thấy được.) Có hai vấn đề khó khăn: nội dung mới được thêm vào ở trên cùng và nội dung được kiểm tra lại.

Hãy quên nội dung mới thêm và chấp nhận rằng bạn sẽ phải làm mới trang 1 để xem nội dung đó. Chúng ta cũng giả vờ chúng ta đang làm thuần túy ORDER BY position; nếu bạn đang đặt hàng bởi một cái gì đó khác, bạn có thể phải sử dụng chức năng cửa sổ. Các trang của chúng tôi có 4 hàng động vật trên mỗi trang. Chúng bắt đầu:

+----+----------+-----------+ 
| 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 | 
+----+----------+-----------+ 

Sau khi tìm nạp trang 1 và trước khi tìm nạp trang 2, rất nhiều mục di chuyển xung quanh. DB bây giờ là:

+----+----------+-----------+ 
| 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 | 
+----+----------+-----------+ 

Có ba cách tiếp cận chung:

phương pháp offset/hạn

Đây là phương pháp ngây thơ tiêu biểu; trong Rails, đó là cách hoạt động của will_paginate và Kaminari. Nếu tôi muốn tìm nạp trang 2, tôi sẽ làm

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

được xếp hàng 5-8. Tôi sẽ không bao giờ thấy Voi, và tôi sẽ thấy Bò hai lần.

cuối nhìn thấy cách tiếp cận ID

Reddit có một cách tiếp cận khác nhau. Thay vì tính toán hàng đầu tiên dựa trên kích thước trang, ứng dụng khách sẽ theo dõi ID của mục cuối cùng mà bạn đã thấy, chẳng hạn như dấu trang. Khi bạn nhấn "tiếp theo", họ bắt đầu tìm kiếm từ dấu trang đó trở đi:

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

Trong một số trường hợp, điều này hoạt động tốt hơn so với trang/bù. Nhưng trong trường hợp của chúng tôi, Chó, bài viết được nhìn thấy lần cuối, đã phóng to sang phải # 1. Vì vậy, khách hàng gửi lên ?last_seen_id=4 và trang 2 của tôi là Dơi, Alpacas, Voi và Cáo. Tôi đã không bỏ lỡ bất kỳ động vật nào, nhưng tôi thấy Bats và Alpacas hai lần.

trạng thái Server side

HackerNews (và trang web của chúng tôi, ngay bây giờ) giải quyết này với continuations server-side; họ lưu trữ toàn bộ toàn bộ kết quả được đặt cho bạn (hoặc ít nhất một vài trang trước?) và liên kết "Thêm" liên quan đến việc tiếp tục đó. Khi tôi tìm nạp trang 2, tôi yêu cầu "trang 2 của truy vấn ban đầu của tôi". Nó sử dụng cùng một tính toán bù đắp/giới hạn, nhưng vì nó chống lại truy vấn ban đầu, tôi chỉ đơn giản là không quan tâm rằng mọi thứ bây giờ đã di chuyển xung quanh. Tôi thấy Voi, Cáo, Hươu cao cổ và Ngựa. Không có dups, không có mặt hàng bị mất.

Nhược điểm là chúng tôi phải lưu trữ nhiều trạng thái trên máy chủ. Trên HN, nó được lưu trong RAM, và trong thực tế những sự tiếp tục này thường hết hạn trước khi bạn có thể nhấn nút "Thêm", buộc bạn phải quay trở lại trang 1 để tìm một liên kết hợp lệ. Trong hầu hết các ứng dụng, bạn có thể lưu trữ nó trong memcached, hoặc thậm chí trong chính cơ sở dữ liệu (sử dụng bảng của riêng bạn, hoặc trong Oracle hoặc PostgreSQL, sử dụng các con trỏ có thể giữ). Tùy thuộc vào ứng dụng của bạn, có thể có một hit hiệu suất; trong PostgreSQL, ít nhất, bạn phải tìm cách để nhấn lại kết nối cơ sở dữ liệu đúng, đòi hỏi nhiều trạng thái dính hoặc một số định tuyến back-end thông minh.

Đây có phải là ba cách tiếp cận duy nhất có thể không? Nếu không, có khái niệm khoa học máy tính nào sẽ cho tôi nước ép Google đọc về điều này không? Có cách nào để ước tính phương pháp tiếp cận mà không lưu trữ toàn bộ tập kết quả không? Về lâu dài, có hệ thống sự kiện truyền trực tuyến/điểm-thời gian phức tạp, trong đó "tập hợp kết quả của thời điểm tôi tìm nạp trang 1" là vĩnh viễn có thể lấy được. Ngắn gọn ...?

Answer 1

Chúng tôi sẽ tiếp cận với phương pháp tiếp cận trạng thái phía máy chủ ngay bây giờ, lưu vào bộ nhớ cache toàn bộ kết quả trên truy vấn đầu tiên để chúng tôi luôn trả về danh sách nhất quán. Điều này sẽ làm việc miễn là truy vấn của chúng tôi đã trả về tất cả các hàng; cuối cùng chúng ta sẽ cần phải sử dụng một cách tiếp cận gần nhất hàng xóm và điều đó sẽ không hoạt động.

Nhưng tôi nghĩ rằng có một khả năng thứ tư, trong đó quy mô rất tốt, miễn là:

1. Bạn không cần một sự đảm bảo không có bản sao, chỉ có một khả năng cao
2. Bạn okay với thiếu một số nội dung trong cuộn, miễn là bạn tránh trùng lặp

giải pháp là một biến thể của "ID nhìn thấy lần cuối" giải pháp: có khách hàng giữ không o ne, nhưng 5 hoặc 10 hoặc 20 dấu trang - đủ ít để bạn có thể lưu trữ chúng một cách hiệu quả. Truy vấn kết thúc lên trông như:

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

Khi số lượng bookmark phát triển, tỷ lệ cược nhanh chóng giảm bớt rằng bạn là (a) bắt đầu tại một số điểm trong quá khứ tất cả n bookmark nhưng (b) nhìn thấy nội dung trùng lặp anyway vì họ được tất cả lại.

Nếu có lỗ hổng hoặc câu trả lời hay hơn trong tương lai, tôi sẽ vui vẻ không chấp nhận câu trả lời này.

Answer 2

Oracle xử lý điều này một cách độc đáo. Chừng nào con trỏ còn mở, bạn có thể tìm nạp nhiều lần khi cần thiết và kết quả của bạn sẽ luôn phản ánh thời điểm con trỏ được mở. Nó sử dụng dữ liệu từ các bản ghi hoàn tác cho các thay đổi rollback hầu như đã được cam kết sau khi con trỏ được mở.

Nó sẽ hoạt động miễn là dữ liệu rollback bắt buộc vẫn có sẵn. Cuối cùng, nhật ký được tái chế và dữ liệu rollback không còn khả dụng nữa, do đó có một số giới hạn, tùy thuộc vào không gian nhật ký, hoạt động của hệ thống, v.v.

Thật không may (IMO), tôi không biết bất kỳ DB nào khác hoạt động như thế này Các cơ sở dữ liệu khác mà tôi đã làm việc với các khóa sử dụng để đảm bảo tính nhất quán đọc, đó là vấn đề nếu bạn muốn đọc tính nhất quán trong thời gian rất ngắn.

Answer 3

Giải pháp 1: "giải pháp hacky"

Một giải pháp có thể bao gồm trong bạn theo dõi khách hàng giữ của đã thấy nội dung, một danh sách các ID ví dụ. Mỗi khi bạn cần một trang khác, bạn thêm danh sách ID này vào các tham số của cuộc gọi máy chủ của bạn. Sau đó, máy chủ của bạn có thể đặt hàng nội dung, xóa nội dung đã xem và áp dụng bù đắp để có được đúng trang.

Tôi sẽ không khuyên bạn nên mặc dù và tôi nhấn mạnh vào hacky. Tôi chỉ viết nó xuống đây vì nó nhanh và có thể phù hợp với một số nhu cầu.Đây là những điều tồi tệ mà tôi có thể nghĩ đến:

1) Cần một số công việc ở phía khách hàng để làm đúng (nghĩa là "đã thấy" có nghĩa trong câu trên, nếu tôi truy cập trang trước?)

2) Thứ tự kết quả không phản ánh đúng chính sách đặt hàng của bạn. Một nội dung có thể được hiển thị ở trang 2 mặc dù chính sách nên đặt nó ở trang 1. Nó có thể dẫn đến sự hiểu lầm của người dùng. Hãy lấy ví dụ về tràn ngăn xếp với chính sách đặt hàng trước đây của nó, điều đó có nghĩa là hầu hết các câu trả lời được upvoted trước tiên. Chúng tôi có thể có một câu hỏi với 6 upvotes đang ở trang 2 trong khi một câu hỏi với 4 upvotes sẽ ở trang 1. Điều này xảy ra khi 2 hoặc nhiều upvotes xảy ra trong khi người dùng vẫn còn trên trang 1. -> có thể gây ngạc nhiên cho người dùng .

Giải pháp 2: "giải pháp khách hàng"

Đó là về cơ bản là giải pháp tương đương client-side với một bạn gọi là "server-side nhà nước". Nó chỉ hữu dụng nếu việc theo dõi thứ tự đầy đủ ở phía máy chủ không đủ thuận tiện. Nó hoạt động nếu danh sách các mục không phải là vô hạn.

• Gọi máy chủ của bạn để có được đầy đủ (hữu hạn) danh sách theo thứ tự + số mục/trang
• Lưu nó về phía khách hàng
• Lấy mặt hàng trực tiếp thông qua các id nội dung của bạn.

Answer 4

Rất muộn cho bữa tiệc nhưng đây là điều chúng tôi đã thử nghiệm. Chúng tôi đang sử dụng tải liên tục, không phải các trang mà người dùng sẽ đi qua lại giữa.

Các khách hàng xây dựng một danh sách tất cả các ID nó đã hiển thị, vì vậy sau khi tập đầu tiên nó có thể là: 4,7,19,2,1,72,3

Khi chúng tôi tải nội dung chúng ta càng thực hiện cùng một truy vấn với cùng một loại nhưng thêm vào đó: WHERE id NOT IN (4,7,19,2,1,72,3)

Danh sách NOT IN có thể phát triển khá nhanh. Đối với chúng tôi, đây không phải là vấn đề vì công cụ nội bộ của chúng tôi thường không có nhiều kết quả.

Tôi muốn thêm ý tưởng khác. Có thể một phần bổ sung phía máy chủ có thể được áp dụng cho điều này. Khi người dùng tìm kiếm, hãy thêm tất cả các ID họ đã có vào một bảng có liên kết đến tìm kiếm của họ. Khi khách hàng muốn nhiều hơn nó chỉ phải cung cấp ID tìm kiếm (hoặc sử dụng trạng thái phía máy chủ) và truy vấn có thể tham gia với dữ liệu tìm kiếm của họ.