Sao chép máy trạng thái

Sao chép máy trạng thái làm cho một dịch vụ có khả năng chịu lỗi bằng cách chạy các bản sao xác định thực hiện cùng một lệnh theo cùng một thứ tự, do đó các bản sao còn lại sẽ che giấu lỗi của các bản sao khác.

Definition

Sao chép máy trạng thái là một kỹ thuật trong đó một dịch vụ được mô hình hóa như một máy trạng thái xác định và được sao chép trên nhiều máy chủ mà tất cả đều áp dụng cùng một chuỗi lệnh được sắp xếp từ máy khách, đảm bảo rằng các bản sao không bị lỗi vẫn ở trạng thái giống hệt nhau và có thể thay thế cho các bản sao bị lỗi.

Scope

Chủ đề này bao gồm mô hình máy trạng thái của một dịch vụ, yêu cầu các bản sao phải có tính xác định, việc sử dụng phát sóng hoặc đồng thuận theo thứ tự tổng thể (nguyên tử) để thống nhất về chuỗi lệnh, và sự tương phản với sao chép chính-phụ (thụ động). Nó cũng đề cập đến việc xử lý tính không xác định, cấu hình lại bản sao và mở rộng sang các bản sao Byzantine.

Core questions

• Tại sao các bản sao phải có tính xác định và xử lý các lệnh theo cùng một thứ tự?
• Thứ tự lệnh đã được thống nhất được tạo ra như thế nào từ sự đồng thuận hoặc phát sóng nguyên tử?
• Sao chép chủ động (máy trạng thái) khác với sao chép chính-phụ thụ động như thế nào?

Key theories

Phương pháp máy trạng thái

Bất kỳ dịch vụ xác định nào cũng có thể được làm cho chịu lỗi bằng cách sao chép nó và cung cấp cho mỗi bản sao cùng một luồng lệnh được sắp xếp; miễn là số lượng bản sao bị lỗi ít hơn số lượng cho phép, dịch vụ vẫn hoạt động chính xác và khả dụng.

Sắp xếp thông qua đồng thuận

Thứ tự tổng thể cần thiết trên các lệnh chính xác là một phát sóng nguyên tử, tương đương với sự đồng thuận, vì vậy các máy trạng thái được sao chép thường được xây dựng trên một giao thức đồng thuận như Paxos hoặc Raft.

Sao chép máy trạng thái Byzantine

Việc mở rộng phương pháp này để chịu được các lỗi tùy ý đòi hỏi sự đồng thuận giữa hơn hai phần ba số bản sao và việc bỏ phiếu kết quả của máy khách, như đã được thực hiện trong sao chép chịu lỗi Byzantine thực tế.

Clinical relevance

Sao chép máy trạng thái là cách tiêu chuẩn để xây dựng một dịch vụ có tính sẵn sàng cao, nhất quán mạnh mẽ; các nhật ký được sao chép, dịch vụ điều phối và nhiều cơ sở dữ liệu phân tán là các máy trạng thái được điều khiển bởi một luồng lệnh được sắp xếp theo đồng thuận.

History

Bài báo về đồng hồ logic của Lamport đã phác thảo ý tưởng máy trạng thái được sao chép vào năm 1978; hướng dẫn của Schneider năm 1990 đã biến nó thành khuôn khổ chuẩn mực cho các dịch vụ chịu lỗi; và PBFT của Castro và Liskov năm 1999 đã mở rộng nó sang môi trường Byzantine, một hướng sau này đã ảnh hưởng đến các thiết kế blockchain.

Debates

Sao chép chủ động so với thụ động

Sao chép chủ động (máy trạng thái) thực thi các lệnh tại tất cả các bản sao để chuyển đổi dự phòng nhanh chóng nhưng lãng phí công việc và yêu cầu tính xác định; sao chép chính-phụ thụ động chỉ thực thi tại một bản sao chính và chuyển trạng thái, tiết kiệm công việc nhưng gây ra độ trễ chuyển đổi dự phòng và một điểm thực thi duy nhất.

Key figures

• Fred Schneider
• Leslie Lamport
• Miguel Castro
• Barbara Liskov

Seminal works

• schneider1990
• lamport1998
• castro1999

Frequently asked questions

Tại sao dịch vụ được sao chép phải có tính xác định?

Nếu các bản sao có thể đưa ra các lựa chọn khác nhau trên cùng một đầu vào—do tính ngẫu nhiên, thời gian hoặc lập lịch luồng—trạng thái của chúng sẽ phân kỳ mặc dù nhận được các lệnh giống hệt nhau. Tính xác định đảm bảo rằng cùng một luồng lệnh được sắp xếp sẽ tạo ra cùng một trạng thái ở mọi nơi.