Hệ thống phân tán

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 22)

Hệ thống phân tán

Bully Algorithm for Leader Election

Thời gian (Time) O(N^2)
Không gian (Space) O(1)

Mô tả nguyên lý

Thuật toán bầu chọn nút lãnh đạo trong hệ thống phân tán dựa trên ID lớn nhất.

Cài đặt mẫu (Implementation)

// Node có ID lớn nhất phát thông điệp áp đảo các node nhỏ hơn để giành quyền leader.
Hệ thống phân tán

Bully Election Algorithm

Thời gian (Time) O(N^2)
Không gian (Space) O(1)

Mô tả nguyên lý

Bầu chọn leader trong hệ thống phân tán bằng cách gửi thông điệp thách thức đến các node có ID cao hơn.

Cài đặt mẫu (Implementation)

// Node có ID lớn nhất sẽ ép các node nhỏ hơn từ bỏ quyền tranh cử và nhận vị trí điều phối.
Hệ thống phân tán

Chandy-Lamport Snapshot Algorithm

Thời gian (Time) O(V + E)
Không gian (Space) O(V + E)

Mô tả nguyên lý

Chụp ảnh trạng thái toàn cục của hệ thống phân tán bất đồng bộ mà không cần dừng hệ thống.

Cài đặt mẫu (Implementation)

// Gửi thông điệp đánh dấu (marker) qua các kênh truyền để ghi lại trạng thái node và kênh.
Hệ thống phân tán

Chandy-Misra-Haas Deadlock Detection

Thời gian (Time) O(E)
Không gian (Space) O(V)

Mô tả nguyên lý

Thuật toán phát hiện bế tắc (deadlock) phân tán dựa trên việc truyền thông điệp thăm dò (probe messages).

Cài đặt mẫu (Implementation)

// Kiểm tra chu trình phụ thuộc tài nguyên giữa các node phân tán qua thông điệp (initiator, sender, receiver).
Hệ thống phân tán

Consistent Hashing

Thời gian (Time) O(log n)
Không gian (Space) O(n)

Mô tả nguyên lý

Phân tán khóa trên vòng băm giúp giảm thiểu dịch chuyển dữ liệu.

Cài đặt mẫu (Implementation)

// Ánh xạ máy chủ và dữ liệu lên vòng tròn giá trị băm từ 0 đến 2^32 - 1.
Hệ thống phân tán

Distributed Lock with Redis Redlock

Thời gian (Time) O(N servers)
Không gian (Space) O(1)

Mô tả nguyên lý

Thuật toán khóa phân tán an toàn trên nhiều thực thể Redis độc lập.

Cài đặt mẫu (Implementation)

// Lấy khóa tuần tự trên đa số các instance Redis kèm theo kiểm tra thời gian hiệu lực (lease).
Hệ thống phân tán

Distributed Snapshot (Mattern Algorithm)

Thời gian (Time) O(V + E)
Không gian (Space) O(State)

Mô tả nguyên lý

Thuật toán chụp ảnh trạng thái toàn cục sử dụng vector thời gian thay cho thông điệp marker.

Cài đặt mẫu (Implementation)

// Gắn vector đồng hồ vào mỗi thông điệp để xác định biên cắt trạng thái hợp lệ.
Hệ thống phân tán

HoneyBadgerBFT Asynchronous Consensus

Thời gian (Time) O(N^3 tin nhắn)
Không gian (Space) O(State)

Mô tả nguyên lý

Giao thức đồng thuận bất đồng bộ chịu lỗi Byzantine không phụ thuộc vào giới hạn thời gian mạng.

Cài đặt mẫu (Implementation)

// Kết hợp mã hóa ngưỡng và thỏa thuận chung cậy (reliable broadcast).
Hệ thống phân tán

Lease-Based Synchronization Protocol

Thời gian (Time) O(1)
Không gian (Space) O(1)

Mô tả nguyên lý

Cấp phát quyền sở hữu độc quyền tài nguyên phân tán trong một khoảng thời gian giới hạn.

Cài đặt mẫu (Implementation)

// Tránh tình trạng treo khóa vô thời hạn khi node sở hữu khóa bị ngắt kết nối đột ngột.
Hệ thống phân tán

Leased-Based Distributed Locking

Thời gian (Time) O(1)
Không gian (Space) O(1)

Mô tả nguyên lý

Cơ chế cấp phát khóa phân tán có thời hạn (lease) giúp tránh tình trạng khóa treo vĩnh viễn khi node chết.

Cài đặt mẫu (Implementation)

// Server cấp quyền sở hữu tài nguyên trong một khoảng thời gian hữu hạn, tự động thu hồi khi hết hạn.
Hệ thống phân tán

Multi-Paxos Protocol

Thời gian (Time) O(1) ổn định
Không gian (Space) O(State)

Mô tả nguyên lý

Phiên bản tối ưu của Paxos cho phép thống nhất chuỗi log liên tục với một Leader cố định.

Cài đặt mẫu (Implementation)

// Bỏ qua giai đoạn chuẩn bị cho các instance sau khi đã bầu được Leader.
Hệ thống phân tán

Paxos Consensus Algorithm

Thời gian (Time) Phụ thuộc mạng
Không gian (Space) O(1)

Mô tả nguyên lý

Giao thức đạt được sự đồng thuận giữa các node phân tán.

Cài đặt mẫu (Implementation)

// Giai đoạn chuẩn bị (Prepare) và giai đoạn chấp nhận (Accept).
Hệ thống phân tán

Paxos Made Simple Algorithm

Thời gian (Time) O(1) ổn định
Không gian (Space) O(State)

Mô tả nguyên lý

Giao thức đồng thuận cổ điển kinh điển đạt sự nhất quán trong cụm máy chủ phân tán không đồng bộ.

Cài đặt mẫu (Implementation)

// Giai đoạn chuẩn bị (Phase 1a/1b) và giai đoạn chấp nhận (Phase 2a/2b) qua đa số phiếu bầu (quorum).
Hệ thống phân tán

Raft Consensus Algorithm

Thời gian (Time) Phụ thuộc mạng
Không gian (Space) O(1)

Mô tả nguyên lý

Giao thức đồng thuận phân tán quản lý qua Leader Election và Log Replication.

Cài đặt mẫu (Implementation)

// Leader quản lý toàn bộ việc nhân bản log đến các follower.
Hệ thống phân tán

Raft Joint Consensus Configuration Change

Thời gian (Time) O(1)
Không gian (Space) O(Log Size)

Mô tả nguyên lý

Cơ chế thay đổi cấu hình cụm máy chủ an toàn trong thuật toán Raft mà không bị chia cắt não (split-brain).

Cài đặt mẫu (Implementation)

// Chuyển đổi qua cấu hình trung gian kết hợp cụm cũ và cụm mới (C_old,new) trước khi áp dụng cấu hình mới hoàn toàn.
Hệ thống phân tán

Raft Log Compaction & Snapshotting

Thời gian (Time) O(Log Size)
Không gian (Space) O(State Size)

Mô tả nguyên lý

Cơ chế nén lịch sử nhật ký (log) trong thuật toán đồng thuận Raft để tiết kiệm bộ nhớ.

Cài đặt mẫu (Implementation)

// Lưu trạng thái hiện tại thành snapshot và loại bỏ các bản ghi log cũ đã cam kết.
Hệ thống phân tán

Raft Membership Joint Consensus

Thời gian (Time) O(1)
Không gian (Space) O(Log State)

Mô tả nguyên lý

Cơ chế cập nhật danh sách thành viên cụm trong thuật toán Raft thông qua cấu hình trung gian.

Cài đặt mẫu (Implementation)

// Đảm bảo không xảy ra trường hợp hai leader cùng tồn tại trên hai cấu hình khác nhau trong một nhiệm kỳ.
Hệ thống phân tán

Three-Phase Commit Protocol (3PC)

Thời gian (Time) O(N tin nhắn)
Không gian (Space) O(State)

Mô tả nguyên lý

Cải tiến của 2PC thêm giai đoạn tiền cam kết để tránh tình trạng treo hệ thống khi coordinator chết.

Cài đặt mẫu (Implementation)

// Thêm trạng thái Pre-Commit trước khi thực hiện cam kết chính thức.
Hệ thống phân tán

Two-Phase Commit Protocol (2PC)

Thời gian (Time) O(N tin nhắn)
Không gian (Space) O(State)

Mô tả nguyên lý

Giao thức cam kết phân tán đảm bảo tính nhất quán ACID trên nhiều node cơ sở dữ liệu.

Cài đặt mẫu (Implementation)

// Giai đoạn chuẩn bị (Prepare phase) và giai đoạn cam kết/hủy bỏ (Commit/Abort phase).
Hệ thống phân tán

Vector Clock Causality Tracking

Thời gian (Time) O(N)
Không gian (Space) O(N)

Mô tả nguyên lý

Theo dõi quan hệ nhân quả của các sự kiện trong hệ thống phân tán không dùng đồng hồ vật lý chung.

Cài đặt mẫu (Implementation)

// Mỗi tiến trình duy trì mảng đếm sự kiện và cập nhật giá trị lớn nhất khi nhận thông điệp tương tác.
Hệ thống phân tán

Vector Clocks Causality Tracking

Thời gian (Time) O(N nodes)
Không gian (Space) O(N)

Mô tả nguyên lý

Theo dõi quan hệ nguyên nhân - kết quả giữa các sự kiện trong hệ thống phân tán bất đồng bộ.

Cài đặt mẫu (Implementation)

// Mỗi node duy trì mảng đồng hồ logic đếm số sự kiện của từng thành viên trong cụm.
Hệ thống phân tán

Viewstamped Replication (VSR)

Thời gian (Time) O(N tin nhắn)
Không gian (Space) O(Log State)

Mô tả nguyên lý

Giao thức nhân bản nhật ký trạng thái phân tán tương tự Raft nhưng ra đời sớm hơn trong lý thuyết.

Cài đặt mẫu (Implementation)

// Quản lý các view hoạt động của primary và backup nodes qua số hiệu view tăng dần.