Làm cách nào để bạn triển khai phân loại và phân trang trên dữ liệu được phân phối?

Question

Đây là vấn đề tôi đang cố giải quyết:

Tôi cần có khả năng hiển thị bảng được phân loại, sắp xếp dữ liệu được lưu trữ trên nhiều phân đoạn cơ sở dữ liệu.

Phân trang và phân loại là các vấn đề được biết rõ mà hầu hết chúng ta có thể giải quyết bằng bất kỳ cách nào khi dữ liệu đến từ một nguồn duy nhất. Nhưng nếu bạn đang chia nhỏ dữ liệu của mình trên các phân đoạn hoặc sử dụng cơ sở dữ liệu tài liệu DHT hoặc phân phối hoặc bất kỳ mùi vị nào của NoSQL bạn thích, mọi thứ trở nên phức tạp hơn.

Đây là một hình ảnh đơn giản của một bộ dữ liệu thực sự nhỏ:

Shard | Dữ liệu
1 | A
1 | D
1 | G
2 | B
2 | E
2 | H
3 | C
3 | F
3 | Tôi

Sắp xếp thành các trang (Kích thước trang = 3):

Trang | Dữ liệu
1 | A
1 | B
1 | C
2 | D
2 | E
2 | F
3 | G
3 | H
3 | Tôi

Và nếu chúng ta muốn hiển thị các trang người dùng 2, chúng tôi muốn trở lại:

D
E
F

Nếu kích thước của bảng trong câu hỏi là một cái gì đó như 10 triệu hàng hoặc 100 triệu, bạn không thể kéo tất cả dữ liệu xuống máy chủ web/ứng dụng để sắp xếp và trả lại đúng trang. Và bạn rõ ràng không thể để từng phân loại cá nhân phân loại và phân đoạn dữ liệu của riêng nó vì các mảnh vỡ không biết về nhau.

Để làm phức tạp vấn đề, dữ liệu tôi cần trình bày không thể quá xa, vì vậy việc tính trước một tập hợp các loại hữu ích trước thời hạn và lưu trữ kết quả để truy xuất sau này không thực tế.

Answer 1

Có một số giải pháp, một số trong đó có thể không khả thi cho bạn, nhưng có lẽ một trong số họ sẽ dính:

1. Làm sharding bởi dao động đầu vào cho giá trị này (ví dụ, mảnh 1 chứa AC, shard 2 DF, v.v.) Cách khác, sử dụng một bảng khác với các khóa ngoài vào bảng này làm chỉ mục và phân đoạn bảng chỉ mục bằng cách sử dụng hệ thống này. Bằng cách đó bạn có thể dễ dàng xác định vị trí và tìm nạp phạm vi được chỉ định. Giải pháp này có lẽ là tốt nhất về hiệu suất, nếu bạn có thể làm điều đó (nó giả định rằng số lượng mảnh là tĩnh và các mảnh là đáng tin cậy).
2. Xác định các mục trang theo tìm kiếm nhị phân. Ví dụ: giả sử bạn muốn các mục từ 100 đến 110. Đối với mỗi phân đoạn, hãy đếm số lượng giá trị theo từ điển bên dưới "M".Nếu tổng các số trên 100, hãy giảm điểm pivot, nếu không sẽ tăng lên (bằng cách sử dụng tìm kiếm nhị phân). Sau khi bạn xác định mục thứ 100 (mục đầu tiên trên trang của bạn), hãy lấy các mục 9 (10 - 1) hàng đầu lớn hơn mục đó từ mọi phân đoạn, tìm nạp chúng, sắp xếp toàn bộ danh sách, đi đầu 9 từ danh sách, thêm mục đầu tiên và có trang của bạn! Cách tiếp cận này khó thực hiện hơn và sẽ yêu cầu các truy vấn O(log(n)) do đó nó chậm hơn (1), nhưng vẫn có thể nhanh chóng hợp lý nếu tải không quá nặng.
3. Lưu trữ số trang với mỗi giá trị. Điều này sẽ cung cấp cho bạn đọc nhanh chóng, nhưng viết chậm khủng khiếp, do đó, nó chỉ hoạt động trong kịch bản mà có rất ít viết (hoặc chỉ nối thêm về biến thứ tự).