Thuật toán phân tán là tập hợp các quy tắc và chỉ thị tính toán được thiết kế để thực thi đồng thời trên nhiều nút xử lý độc lập kết nối qua mạng truyền thông, phối hợp cùng nhau để giải quyết một bài toán chung mà không cần phụ thuộc vào một bộ nhớ chia sẻ hay một đồng hồ phần cứng trung tâm duy nhất. Lĩnh vực này là nền tảng cốt lõi của điện toán đám mây, cơ sở dữ liệu phân tán quy mô lớn và công nghệ chuỗi khối (blockchain).
Bản chất và các thách thức căn bản của tính toán phân tán
Khác với các thuật toán tuần tự hoặc song song trên kiến trúc bộ nhớ chia sẻ (shared memory), thuật toán phân tán phải vận hành trong môi trường truyền thông điệp (message passing) với nhiều bất định nội tại:
- Thiếu trạng thái toàn cục tức thời (Lack of Global State): Không có một nút đơn lẻ nào nắm giữ bức tranh toàn diện và tức thời về trạng thái của toàn bộ hệ thống tại cùng một thời điểm thực.
- Độ trễ và mất gói tin trên mạng: Mạng truyền thông có độ trễ biến động, các thông điệp có thể bị đảo trật tự, truyền lặp lại hoặc bị gián đoạn hoàn toàn (phân vùng mạng - network partition).
- Sự cố nút mạng đa dạng: Các nút có thể gặp sự cố dừng hoạt động đột ngột (crash-stop), tự phục hồi sau sự cố (crash-recovery) hoặc nguy hiểm hơn là phát tín hiệu sai lệch và lừa dối (lỗi Byzantine).
Các vấn đề bài toán cốt lõi trong thuật toán phân tán
Khoa học máy tính phân tán tập trung giải quyết các lớp bài toán nền tảng sau:
1. Thứ tự sự kiện và đồng hồ logic của Leslie Lamport (1978)
Theo Leslie Lamport (1978), trong một hệ thống không có đồng hồ vật lý đồng bộ tuyệt đối, thứ tự nhân quả của các sự kiện được xác định thông qua quan hệ "xảy ra trước" (happened-before relation). Lamport timestamps và sau này là Vector Clocks cho phép gán nhãn logic cho từng sự kiện, đảm bảo tính nhất quán về nhân quả trong việc ghi log và xử lý giao dịch phân tán.
2. Bài toán đồng thuận phân tán và Định lý bất khả FLP (1985)
Đồng thuận (Consensus) là việc tất cả các nút mạng không bị lỗi cùng thống nhất một giá trị duy nhất trong tập các giá trị đề xuất. Fischer, Lynch và Paterson (1985) đã chứng minh định lý bất khả nổi tiếng (FLP Impossibility Theorem): trong một hệ thống phân tán hoàn toàn bất đồng bộ (asynchronous system), không có bất kỳ thuật toán đồng thuận xác định nào có thể đảm bảo đồng thời tính an toàn (Safety) và tính khả dụng (Liveness) nếu tồn tại dù chỉ một nút gặp sự cố dừng.
3. Thuật toán chịu lỗi Byzantine (BFT) của Castro và Liskov (2002)
Khi các nút mạng có nguy cơ bị tấn công, gửi dữ liệu giả mạo hoặc thông đồng phá hoại, hệ thống cần đến các thuật toán chịu lỗi Byzantine. Theo Castro và Liskov (2002), thuật toán PBFT (Practical Byzantine Fault Tolerance) giải quyết bài toán đồng thuận trong môi trường mạng bán đồng bộ với độ phức tạp thông điệp đa thức, cho phép hệ thống vận hành an toàn chừng nào số nút lỗi không vượt quá một phần ba tổng số nút mạng.
Phân loại các thuật toán phân tán tiêu biểu
Tùy theo mục đích sử dụng, các thuật toán phân tán được phân chia thành nhiều nhóm nghiệp vụ:
| Nhóm thuật toán | Bài toán giải quyết | Thuật toán tiêu biểu | Ứng dụng thực tế |
|---|---|---|---|
| Đồng thuận chịu lỗi dừng (CFT) | Thống nhất trạng thái máy nhân bản khi các nút bị sập nhưng không gian lận. | Paxos, Raft, Zab | etcd trong Kubernetes, Apache ZooKeeper, CockroachDB. |
| Đồng thuận chịu lỗi Byzantine (BFT) | Đồng thuận trong mạng công cộng có nút độc hại và tấn công giả mạo. | PBFT, Tendermint, Proof-of-Work (Nakamoto) | Mạng lưới blockchain (Bitcoin, Ethereum, Hyperledger). |
| Loại trừ tương hỗ (Mutual Exclusion) | Đảm bảo chỉ một tiến trình được truy cập tài nguyên găng tại một thời điểm. | Ricart-Agrawala, Maekawa, Token Ring | Khóa phân tán (Distributed Locks) trong Redlock/Chubby. |
| Bầu cử trưởng nhóm (Leader Election) | Tự động chọn một nút điều phối mới khi nút lãnh đạo hiện tại gặp sự cố. | Bully Algorithm, Ring Algorithm | Bầu chọn Master trong Elasticsearch, Kafka Controller. |
Mô hình tính toán và xử lý dữ liệu lớn phân tán
Bên cạnh các bài toán kiểm soát trạng thái, thuật toán phân tán còn thúc đẩy năng lực xử lý dữ liệu quy mô siêu lớn:
- Mô hình MapReduce và tính toán đồ thị: Phân chia tập dữ liệu khổng lồ thành các mảnh nhỏ xử lý song song trên hàng nghìn máy tính (Map) sau đó tổng hợp kết quả (Reduce), hiện thực hóa trong Apache Spark và Hadoop.
- Bảng băm phân tán (Distributed Hash Tables - DHT): Cung cấp dịch vụ tra cứu khóa-giá trị phi tập trung hiệu quả cao dựa trên cấu trúc liên kết mạng hình học như Chord, Kademlia (sử dụng trong giao thức BitTorrent và IPFS).
- Cấu trúc dữ liệu hội tụ phi xung đột (CRDTs): Cho phép nhiều người dùng cùng chỉnh sửa tài liệu đồng thời ngoại tuyến và tự động hợp nhất trạng thái nhất quán khi có kết nối mạng mà không cần khóa trung tâm.
Ứng dụng thực tiễn tại Việt Nam
Tại Việt Nam, các thuật toán phân tán đang được ứng dụng sâu rộng trong hạ tầng công nghệ thông tin quốc gia:
- Hệ thống thanh toán điện tử và ngân hàng số: Đảm bảo tính toàn vẹn giao dịch tài chính ACID phân tán (thông qua chuẩn 2PC/3PC và giao thức Raft) cho các cổng thanh toán Napas, Viettel Money, VNPay và Momo.
- Hạ tầng đám mây và viễn thông: Vận hành các cụm máy chủ lớn phục vụ hàng chục triệu người dùng đồng thời tại các doanh nghiệp viễn thông và công nghệ như Viettel IDC, VNPT, FPT Telecom và VNG.