Rebalancing Partitions & Request Routing — Hệ thống phân tán (DDIA) | Blog

Mở đầu

Ảnh: Pixabay — Pexels

Khi bạn có một hệ thống phân tán với dữ liệu được chia nhỏ thành nhiều partition, một câu hỏi quan trọng xuất hiện: làm sao để thêm hoặc bớt node mà không làm gián đoạn toàn bộ hệ thống? Và khi đã có partition rồi, client biết gọi vào node nào để lấy đúng dữ liệu mình cần?

DDIA Chapter 6 dành toàn bộ phần cuối để trả lời hai câu hỏi đó qua hai khái niệm: Rebalancing (cân bằng lại partition khi cluster thay đổi) và Request Routing (định tuyến yêu cầu đến đúng node). Đây là những vấn đề thực tế mà bất kỳ ai làm việc với distributed database, message queue, hay key-value store đều phải đối mặt.

Rebalancing Partitions — Bài toán khó của distributed storage

Ảnh: Pixabay — Pexels

Trong thế giới lý tưởng, bạn chỉ cần partition dữ liệu một lần và hệ thống chạy mãi mãi. Nhưng thực tế không như vậy:

Hiệu năng giảm dần theo thời gian → cần thêm node mới
Node hỏng → cần phân bổ lại dữ liệu từ node chết
Node dư thừa → cần bỏ bớt để tiết kiệm chi phí

Rebalancing là quá trình di chuyển dữ liệu (load) từ node cũ sang node mới sao cho thoả mãn 3 điều kiện:

Dữ liệu được chia đều giữa các node sau rebalance
Hệ thống vẫn nhận request trong quá trình rebalance
Di chuyển càng ít dữ liệu càng tốt — không phải xáo trộn toàn bộ

Tại sao hash mod N là ý tưởng tồi?

Cách đơn giản nhất để partition là dùng hash(key) mod N (với N là số node). Nhưng khi N thay đổi (thêm/bớt node), hầu hết các key sẽ được ánh xạ lại sang node khác — kéo theo một lượng lớn dữ liệu phải di chuyển.

Giả sử bạn có N=10 node, hash(key) mod 10. Thêm node thứ 11 → hash(key) mod 11 cho ra kết quả hoàn toàn khác cho hầu hết các key. Điều này gây ra di chuyển dữ liệu hàng loạt, tốn băng thông, CPU, và thời gian. Với hệ thống lớn (hàng TB dữ liệu), đây là thảm hoạ.

Giải pháp là dùng các chiến lược rebalance thông minh hơn: consistent hashing, dynamic partitioning, hay fixed number of partitions.

Chiến lược 1: Consistent Hashing

Consistent hashing là kỹ thuật kinh điển được dùng bởi Amazon Dynamo, Cassandra, Riak. Ý tưởng:

Hash range được biểu diễn thành một vòng tròn (ring), từ 0 đến 2^32 - 1
Cả partition key và node identifier đều được hash vào vòng tròn này
Mỗi key được gán cho node gần nhất theo chiều kim đồng hồ

Khi thêm node mới, chỉ cần di chuyển dữ liệu từ một vài node lân cận, không phải tất cả. Trung bình, chỉ cần di chuyển 1/N lượng dữ liệu (với N là số node), thay vì gần như toàn bộ.

Tuy nhiên, consistent hashing cơ bản có nhược điểm: nếu số node ít, phân phối dữ liệu có thể không đều. Cassandra giải quyết bằng cách dùng "virtual nodes" — mỗi physical node đại diện cho nhiều điểm trên ring.

Chiến lược 2: Dynamic Partitioning

Đây là cách HBase và MongoDB (trước phiên bản 5.0) sử dụng. Khi partition đạt đến một ngưỡng kích thước nhất định, nó tự động chia làm đôi. Ngược lại, khi dữ liệu ít đi, các partition nhỏ được gộp lại.

Ưu điểm: số partition tự động điều chỉnh theo dung lượng dữ liệu — không cần cấu hình trước. Nhược điểm: khi partition vừa được tách, có thể gây áp lực lên node chứa cả hai nửa; và cần cơ chế theo dõi kích thước partition (thường dùng ZooKeeper).

Một biến thể là HBase dùng HDFS để lưu dữ liệu, partition = region. Region được split/merge tự động dựa trên kích thước, và được assign vào region server.

Chiến lược 3: Fixed Number of Partitions

Cách tiếp cận của Kafka, Elasticsearch, và Voldemort: tạo sẵn nhiều partition hơn số node (ví dụ 10 node, 100 partition). Mỗi node chịu trách nhiệm nhiều partition. Khi thêm/bớt node, chỉ cần di chuyển một số partition từ node cũ sang node mới.

Ví dụ với 10 node và 100 partition:

Ban đầu: mỗi node quản lý 10 partition
Thêm 1 node mới → mỗi node (kể cả node mới) quản lý ~9 partition, di chuyển ~1 partition từ mỗi node cũ
Số partition giữ nguyên (100), chỉ thay đổi assignment

Đây là chiến lược được ưa chuộng nhất trong thực tế vì đơn giản, dễ hiểu, di chuyển dữ liệu tối thiểu. Tuy nhiên, nếu chọn sai số partition ban đầu (quá ít hoặc quá nhiều), có thể gặp vấn đề về hiệu năng hoặc quản lý.

Request Routing — Client biết gọi vào đâu?

Ảnh: ThisisEngineering — Pexels

Sau khi dữ liệu đã được partition, câu hỏi tiếp theo là: làm sao client biết node nào đang giữ partition mà nó cần? Có 3 cách tiếp cận chính:

Allow any node to forward — Client gọi random node. Nếu node đó không có dữ liệu, nó forward request đến node đúng. Cassandra dùng gossip protocol để mỗi node biết tất cả các node khác đang giữ partition nào.
Routing-tier / proxy — Client gọi vào một tầng trung gian (load balancer), tầng này biết partition assignment và forward request đến đúng node. Kafka dùng cách này.
Client-aware routing — Client tự biết partition assignment và gọi trực tiếp vào node đúng. ZooKeeper (hoặc etcd) được dùng để maintain partition assignment và notify khi có thay đổi. LinkedIn's Espresso, MongoDB dùng ZooKeeper.

Cả 3 cách đều có ưu nhược điểm riêng. Cách 1 đơn giản nhưng tăng latency (thêm một hop). Cách 2 tách biệt routing logic khỏi client nhưng thêm một tầng. Cách 3 nhanh nhất (zero hop) nhưng client phức tạp hơn và phụ thuộc vào ZooKeeper.

ZooKeeper — "Bộ não" của distributed coordination

Trong cả Cassandra (gossip) và các hệ thống dùng ZooKeeper, mỗi node đều biết partition assignment hiện tại. ZooKeeper lưu trữ mapping giữa partition và node, và notify tất cả node/client khi mapping thay đổi (thêm/bớt node, partition split).

HBase, Kafka, MongoDB đều dùng ZooKeeper hoặc etcd cho mục đích này. Đây là một trong những ứng dụng quan trọng nhất của distributed consensus trong thực tế — nó là "bộ não" đồng bộ trạng thái cluster.

Ảnh: Pixabay — Pexels
Key Takeaways

Hash mod N đơn giản nhưng không scale — thay đổi N gây di chuyển dữ liệu hàng loạt
Consistent hashing giảm thiểu dữ liệu di chuyển khi thêm/bớt node, nhưng cần virtual nodes để phân phối đều
Dynamic partitioning (HBase, MongoDB cũ) tự động split/merge partition theo kích thước, phù hợp với dữ liệu biến đổi
Fixed number of partitions (Kafka, Elasticsearch) — tạo sẵn nhiều partition hơn node, đơn giản và hiệu quả nhất trong thực tế
Request routing có 3 pattern: forward tại chỗ, proxy trung gian, hoặc client tự biết route (với ZooKeeper)
ZooKeeper/etcd là backbone cho distributed coordination — partition assignment, leader election, cluster membership

📋 Phụ lục thuật ngữ

Rebalancing	Quá trình di chuyển partition giữa các node khi cluster thay đổi
Consistent Hashing	Kỹ thuật hash trên vòng tròn, chỉ di chuyển dữ liệu node lân cận khi thay đổi
Virtual Nodes	Mỗi physical node đại diện cho nhiều điểm trên hash ring để phân phối đều
Dynamic Partitioning	Partition tự động split khi quá lớn, merge khi quá nhỏ
Request Routing	Cơ chế định tuyến request từ client đến đúng node chứa partition
ZooKeeper	Distributed coordination service dùng để quản lý partition assignment
Gossip Protocol	Cơ chế truyền tin peer-to-peer giữa các node trong cluster (Cassandra)

Kết

Rebalancing và request routing là những bài toán mà bất kỳ ai build distributed system đều phải giải quyết. Dù bạn chọn consistent hashing (Cassandra), dynamic partitioning (HBase), hay fixed number of partitions (Kafka), nguyên tắc chung luôn là: giảm thiểu dữ liệu di chuyển khi cluster thay đổi và đảm bảo client luôn tìm đúng node.

Phần tiếp theo sẽ nói về Secondary Indexes — một trong những vấn đề khó nhất khi partition dữ liệu. Follow series để không bỏ lỡ!