Phân vùng một đồ thị có hướng trọng (trên cơ sở dữ liệu/giá trị key)

Question

Chúng tôi muốn Shard một đồ thị có hướng trọng,

Người dùng có thể thêm các nút và các cạnh động, lúc đầu DB/Graph trống.

Chúng tôi giữ các nút và cạnh trong cơ sở dữ liệu khóa/giá trị (có thể là Redis): Đối với mỗi nút, chúng tôi sẽ có nodeId làm khóa và một tập hợp các khóa của các nút được tham chiếu điểm của mỗi nútId trong SortSet là trọng lượng của cạnh.

(Xem câu hỏi liên quan mà ở đây: Redis: Implement Weighted Directed Graph)

Chúng tôi không có một hạn chế cân bằng, các hành động phổ biến nhất trên đồ thị là Dijkstra, và chúng tôi đã muốn hạn chế tối đa I/O (mạng trong của chúng tôi trường hợp)

có thể giải pháp: mỗi máy chủ DB chứa một danh sách các máy chủ khác với địa chỉ IP:

chính: server1, giá trị: .... 250,1

chính: server2, giá trị: .... 250.2

chính: server3, giá trị: .... 250,3

và mỗi nodeID sẽ được serverX.originalNodeId

Điều gì sẽ là các thuật toán mà quyết định những nút đi đâu? chúng ta có nên hỗ trợ định vị lại một nút không?

Tôi đoán rằng cách tiếp cận ngây thơ sẽ là, thêm nút A để serverX nơi argmax (# các nút trong X server có cạnh với nút A), miễn là serverX không chiếm hoàn toàn ..

Answer 1

Kể từ xử lý xảy ra phía khách hàng, loại dữ liệu biểu đồ này không quá khó để phân đoạn - tất cả những gì bạn cần ở mỗi bước là một tập hợp được sắp xếp duy nhất, vì vậy không quan trọng nút nào được đặt từ đó. Việc đưa dữ liệu thực tế đi với nút xảy ra như là bước cuối cùng - đó sẽ là một MGET đơn giản nếu bạn chỉ có một nút và khá dễ dàng để chia tách trên nhiều nút.

Để xác định nút nào sẽ được lưu trữ, bạn nên sử dụng hàm băm thay vì cố gắng theo dõi chúng theo cách thủ công. Tôi sử dụng một bảng lập bản đồ một loạt các băm cho một nút cụ thể. Nó được lưu trữ trong redis cho sự kiên trì lâu dài nhưng thực sự là một phần của khách hàng. Để truy cập vào một khóa cụ thể, bạn chỉ cần lấy mã băm của khóa, tìm nó trong bảng và kết nối với nút đó. Sử dụng một bảng với hàng nghìn khe giúp dễ dàng di chuyển dữ liệu sang một nút khác - cập nhật bảng và các yêu cầu cho một vị trí cụ thể sẽ chuyển sang một nút khác. Điều này là khá giống với, mặc dù không chính xác giống như cách tiếp cận được sử dụng trong redis cluster.

Điều đó nói rằng, lý do của tôi cho việc thiết lập sharding không phải là dữ liệu đồ thị. Các bộ sắp xếp nhỏ chứa các ID không chiếm nhiều bộ nhớ - bạn sẽ có thể xử lý 100 triệu cạnh trên một nút đơn mà không gặp quá nhiều rắc rối.