Đối với các hệ thống nhỏ việc caching dữ liệu trong một hệ thống đơn node hoặc local-cache tại từng service là đủ, nhưng khi hệ thống lớn dần phải scale nhiều instance phương pháp này gặp nhiều thách thức:

• Khả năng mở rộng (Scalability): Làm thế nào để xử lý khối lượng dữ liệu khổng lồ cần được cache?

• Khả năng chịu lỗi (Fault Tolerance): Làm thế nào để đảm bảo tính sẵn sàng cao của dữ liệu cache nếu một node bị lỗi?

• Cân bằng tải (Load Balancing): Làm thế nào để xử lý một lượng lớn các yêu cầu đọc đồng thời, ví dụ như nguồn cấp dữ liệu Twitter được hàng triệu người dùng truy cập?

Caching phân tán giải quyết những thách thức này khi hệ thống mở rộng để phục vụ số lượng lớn người dùng và lượng dữ liệu lớn.

Trong một hệ thống caching phân tán, nhiều node cùng lưu trữ các bản sao của mỗi tập dữ liệu. Kiến trúc này tăng khả năng chịu lỗi, đảm bảo tính sẵn sàng cao đồng thời cho phép cân bằng tải các yêu cầu trên các nút, giúp hệ thống xử lý hiệu quả số lượng lớn read request.

Cách Caching Phân tán hoạt động

HÌnh trên minh họa các thành phần của một hệ thống cache phân tán và cách nó hoạt động:

• Cache Client – Khi caching dữ liệu, client sử dụng thuật toán hashing hoặc sharding để xác định node hoặc phân vùng (shard) thích hợp để lưu trữ dữ liệu.

• Cache Cluster – Một cụm nhiều noide chuyên dụng hoạt động với cấu hình master–slave để quản lý tất cả các thao tác đọc và ghi.

  • Dữ liệu được sao chép trên nhiều node để tăng khả năng chịu lỗi và đảm bảo tính sẵn sàng cao.

  • Tất cả các thao tác ghi được điều hướng đến master node, nơi quyết định cách phân phối dữ liệu tới các slave node.

  • Các cơ chế phối hợp, chẳng hạn như distributed locks hoặc consensus protocols, giữ cho các cache node đồng bộ, đặc biệt trong các tình huống nhiều node sửa đổi dữ liệu đồng thời.

• Sharding – Dữ liệu được chia thành các shard, mỗi shard được lưu trên một cache node khác nhau. Cách tiếp cận này giúp phân phối dữ liệu đồng đều và cho phép mở rộng theo chiều ngang.

• Caching Strategies – Các chiến lược cho hoạt động đọc và ghi phải được thiết lập để xác định cách dữ liệu được cập nhật giữa cơ sở dữ liệu và cache hoặc ngược lại.

• Eviction Policies – Cache triển khai các chiến lược loại bỏ như LRU, LFU hoặc TTL để xóa dữ liệu cũ hoặc ít được truy cập nhằm tạo không gian lưu trữ cho các dữ liệu mới.

Các loại thuật toán Sharding trong Caching Phân tán

Thuật toán sharding rất quan trọng trong việc phân phối dữ liệu trên nhiều node trong một hệ thống cache phân tán. Chúng quyết định nút nào sẽ được đọc hoặc ghi dữ liệu. Dưới đây là một số thuật toán thường được sử dụng ae có thể tham khảo.

1. Modulus Sharding

Modulus sharding gán một key vào shard dựa trên giá trị băm của key chia cho tổng số shard.

Ưu điểm:
- Phân phối đồng đều: Hàm modulus phân phối dữ liệu tương đối đồng đều trên các shard, tránh điểm nóng vì đầu ra hash ngẫu nhiên.
- Đơn giản: Dễ triển khai, chỉ cần một hàm hash đơn giản để xác định shard dựa trên key.

Nhược điểm:
- Khó mở rộng: Việc thêm hoặc xóa shard trở nên phức tạp vì cần phân phối lại các key, dẫn đến di chuyển dữ liệu lớn.
- Hạn chế với Range Queries: Vì sharding dựa trên hash của key, việc thực hiện truy vấn theo khoảng (ví dụ: lấy key từ 1000 đến 2000) trở nên kém hiệu quả và yêu cầu truy vấn nhiều shard (các key từ 1000 đến 2000 có thể nằm trên nhiều shard).

2. Range-based Sharding

Range-based sharding gán key cho các shard cụ thể dựa trên các khoảng giá trị key được định nghĩa trước.

Ưu điểm:
- Hiệu quả với Range Queries: Tối ưu hóa các truy vấn theo khoảng bằng cách lưu dữ liệu trong các shard cụ thể, giảm nhu cầu truy cập nhiều shard.
- Nhóm dữ liệu logic: Dữ liệu liên quan được lưu cùng nhau, tăng hiệu quả truy xuất.

Nhược điểm:
- Rủi ro mất cân bằng tải: nếu hành vi truy vấn thường tập trung vào một khoảng cụ thể.

Ví dụ: nếu key là userId, ta có thể chia như sau:

• Node A: 1 – 1.000.000

• Node B: 1.000.001 – 2.000.000

• Node C: 2.000.001 – 3.000.000

Như vậy, khi cần truy vấn userId = 1.234.567 thì ta biết ngay nó nằm trên Node B.

Ưu điểm

• Lookup nhanh: Chỉ cần so sánh giá trị key với range để biết node nào giữ dữ liệu → O(1).

• Phù hợp cho dữ liệu có thứ tự tự nhiên (như số thứ tự, ngày tháng).

Nhược điểm

• Khó scale linh hoạt: Khi thêm node mới, phải chia lại range → dẫn đến di chuyển dữ liệu nhiều.

Ví dụ khác:

Giả sử anh em xây một hệ thống cache cho log giao dịch ngân hàng theo ngày.

• Node 1: giữ dữ liệu từ 2025-01-01 đến 2025-03-31.

• Node 2: giữ dữ liệu từ 2025-04-01 đến 2025-06-30.

• Node 3: giữ dữ liệu từ 2025-07-01 đến 2025-09-30.

Nếu hôm nay là 26/09/2025, thì mọi request tra log của ae dev, ops, tester đều dồn về Node 3 → dễ nghẽn. Rõ ràng trường hợp này hành vi của người dùng truy vấn dữ liệu không theo tự nhiên mà thường tập trung vào một ngày hoặc một khoảng ngày và việc truy vấn này thường tập trung vào một node, như vậy thiết kế này khá là không tốt.

3. Consistent Hashing

3.1. Tiếp cận

Modulus và range-based sharding thì ae thấy rồi đó, dễ quản lý nhưng khó mở rộng. Khi một node ngừng hoạt động hoặc một node mới được thêm vào, các key phải được phân phối lại hoàn toàn, gây ra downtime và phức tạp.

Consistent hashing giải quyết vấn đề này bằng cách ánh xạ cả key và node vào một vòng tròn (ring) có kích thước cố định bằng một hàm hash. Phương pháp này giảm thiểu việc phân phối lại key khi các node thay đổi, cải thiện khả năng mở rộng và ổn định.

Cách hoạt động:

• Tất cả các node sẽ sẽ được hash thành một giá trị và đặt vào một vị trí cụ thể trên vòng tròn.

• Khi một key được yêu cầu, hệ thống áp dụng hàm hash để ánh xạ key đến một vị trí cụ thể trên vòng tròn.

• Hệ thống duyệt vòng theo chiều kim đồng hồ từ vị trí của key cho đến khi gặp node đầu tiên.

• Node đó chịu trách nhiệm lưu trữ dữ liệu liên quan đến key.

Xử lý khi node thất bại:

• Khi một node trong vòng bị lỗi, tất cả các key được gán cho node đó sẽ được gán lại cho node kế tiếp trong vòng, các key khác không bị ảnh hưởng.

Xử lý khi thêm node mới:

• Khi một node mới được thêm vào vòng, tất cả các key nằm giữa node mới và node trước đó sẽ được ánh xạ lại cho node mới, trong khi các key khác không bị ảnh hưởng.

Điểm mạnh: khi thêm hoặc bớt node, chỉ 1 phần nhỏ key phải di chuyển.

Điểm yếu: cần thêm virtual nodes để cân bằng.

3.2. Ví dụ luôn cho dễ hiểu

Bước 1: Tạo vòng tròn hash

Anh em hình dung một vòng tròn từ có 1000 điểm từ 0 → 999 (Ví dụ giả định là giá trị của hàm hash, hash thực tế thường dùng MD5/SHA1 rồi lấy modulo).

• Hash(Node A) → 100

• Hash(Node B) → 400

• Hash(Node C) → 700

Bước 2: Hash key và gán vào node gần nhất theo chiều kim đồng hồ

• Hash("user:101") = 150 → nằm sau 100, trước 400 → gán cho Node B.

• Hash("user:202") = 320 → vẫn trước 400 → gán cho Node B.

• Hash("user:303") = 520 → nằm sau 400, trước 700 → gán cho Node C.

• Hash("user:404") = 50 → nằm sau 0, trước 100 → gán cho Node A.

Kết quả:

• Node A: "user:404"

• Node B: "user:101", "user:202"

• Node C: "user:303"

Bước 3: Khi thêm node mới

Giả sử thêm Node D, hash(Node D) = 600.

• Trước đây "user:303" (520) thuộc Node C (700).

• Sau khi có Node D (600), key này chuyển sang Node D (vì nó nằm giữa 400 → 600).

→ Chỉ một phần nhỏ key bị di chuyển, không bị xáo trộn toàn bộ như modular hashing.

Bước 4: Virtual Nodes (giải quyết mất cân bằng)

Nếu chỉ có 3 node, phân bổ key có thể bị lệch (node nào gần nhau thì ít key, node nào cách xa thì nhiều key).
→ Giải pháp: mỗi node xuất hiện nhiều lần trên vòng tròn (virtual node).
Ví dụ Node A được hash ra 100, 250, 900 → giúp phân phối key đều hơn.

3.3. Tạo các virtual node như thế nào?

Để xác định các giá trị Virtual Node tương ứng với một node vật lý (physical node) trong Consistent Hashing, ae có thể tham khảo cách làm như sau:

Nguyên tắc

Mỗi node vật lý sẽ được ánh xạ thành n virtual nodes (số n tùy config, ví dụ 100 hoặc 200).
Để tạo ra các điểm hash khác nhau trên vòng tròn cho một node, ta sẽ thay đổi input của hàm hash bằng cách kết hợp:

• Tên node (hoặc ID node hoặc địa chỉ IP của node).

• Chỉ số index (0, 1, 2, …, n-1).

Công thức chung

hash(nodeId + "#" + i)   // i = 0..n-1

Ví dụ:

• Node A: 10.0.0.1:11211

• Tạo 3 virtual node:

  • hash("10.0.0.1:11211#0") = 123

  • hash("10.0.0.1:11211#1") = 456

  • hash("10.0.0.1:11211#2") = 890

Trên vòng tròn hash, Node A giờ có 3 vị trí 123, 456, 890.

Pseudo-code minh họa

int VIRTUAL_NODE_COUNT = 100;
String nodeId = "10.0.0.1:11211";
List<Integer> virtualNodes = new ArrayList<>();

for (int i = 0; i < VIRTUAL_NODE_COUNT; i++) {
    String virtualKey = nodeId + "#" + i;
    int hashValue = hashFunction(virtualKey); // ví dụ MD5 rồi lấy 32-bit
    virtualNodes.add(hashValue);
}

Kết quả: một node vật lý có 100 giá trị hash rải đều trên vòng tròn. Virtual nodes mang lại lợi ích:

• Giúp phân phối key đồng đều hơn.

• Khi thêm/bớt node vật lý, chỉ một lượng nhỏ key bị di chuyển.

3.4. Triển khai

Ví dụ hệ thống 3 node chính (physical nodes), mỗi node có 10 virtual nodes, và cách xác định node khi thêm dữ liệu.

Ý tưởng triển khai

1. Mỗi node chính (ví dụ: NodeA, NodeB, NodeC) sẽ có 10 virtual node.

   • Tạo bằng cách: "NodeA#0", "NodeA#1", … "NodeA#9".

   • Hash từng virtual node → đặt lên vòng tròn hash.

2. Khi cần lưu một key (ví dụ "user:101"):

   • Hash key.

   • Tìm virtual node đầu tiên trên vòng tròn có giá trị hash ≥ hash(key).

   • Nếu không có (hash vượt cuối vòng tròn) → quay vòng về virtual node đầu tiên.

   • Trả về node chính chứa virtual node đó.

import java.security.MessageDigest;
import java.util.*;

public class ConsistentHashingDemo {
    private static final int VIRTUAL_NODES = 10;
    private final SortedMap<Integer, String> circle = new TreeMap<>();

    public ConsistentHashingDemo(List<String> nodes) {
        for (String node : nodes) {
            addNode(node);
        }
    }

    // Hàm thêm node chính + các virtual node vào vòng tròn
    private void addNode(String node) {
        for (int i = 0; i < VIRTUAL_NODES; i++) {
            String virtualNodeId = node + "#" + i;
            int hash = getHash(virtualNodeId);
            circle.put(hash, node);
            System.out.println("Add virtual node: " + virtualNodeId + " hash=" + hash);
        }
    }

    // Hàm hash (MD5 -> lấy 4 byte đầu tiên thành int)
    private int getHash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(key.getBytes());
            return ((digest[0] & 0xFF) << 24) 
                 | ((digest[1] & 0xFF) << 16) 
                 | ((digest[2] & 0xFF) << 8) 
                 | (digest[3] & 0xFF);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    // Hàm tìm node chứa key
    public String getNode(String key) {
        int hash = getHash(key);
        // ceilingEntry = entry có key >= hash
        Map.Entry<Integer, String> entry = circle.ceilingEntry(hash);
        if (entry == null) {
            // nếu vượt cuối vòng tròn -> lấy node đầu tiên
            entry = circle.firstEntry();
        }
        return entry.getValue();
    }

    public static void main(String[] args) {
        List<String> nodes = Arrays.asList("NodeA", "NodeB", "NodeC");
        ConsistentHashingDemo ch = new ConsistentHashingDemo(nodes);

        // Test với một số key
        String[] keys = {"user:101", "user:202", "user:303", "user:404", "order:999"};
        for (String key : keys) {
            String node = ch.getNode(key);
            System.out.println("Key=" + key + " mapped to " + node);
        }
    }

Kết quả:

Add virtual node: NodeA#0 sh=123456789
Add virtual node: NodeA#1 hash=...
...
Key=user:101 mapped to NodeB
Key=user:202 mapped to NodeC
Key=user:303 mapped to NodeA
Key=user:404 mapped to NodeC
Key=order:999 mapped to NodeB

• Vòng tròn hash được tạo từ các virtual node.

• Khi thêm dữ liệu (user:101), ta hash key và tìm virtual node gần nhất theo chiều kim đồng hồ.

• Từ virtual node đó suy ra node chính (A, B, hoặc C).