Checkpointing và Khôi phục

Checkpointing định kỳ lưu trạng thái của hệ thống để sau khi xảy ra lỗi, hệ thống có thể quay lại một điểm nhất quán và tiếp tục, thay vì khởi động lại từ đầu.

Definition

Checkpointing ghi lại trạng thái của một hoặc nhiều tiến trình vào bộ nhớ ổn định; khôi phục quay lui sử dụng các điểm kiểm tra này, có thể kèm theo các tin nhắn đã ghi nhật ký, để khôi phục hệ thống về trạng thái toàn cục nhất quán—một đường khôi phục—sau khi xảy ra lỗi và phát lại từ đó.

Scope

Chủ đề này bao gồm khôi phục quay lui dựa trên điểm kiểm tra (checkpoint-based) và dựa trên nhật ký (log-based): checkpointing không phối hợp, phối hợp và do giao tiếp gây ra; hiệu ứng domino mà các điểm kiểm tra không phối hợp có thể gây ra; và ghi nhật ký tin nhắn lạc quan, bi quan và nhân quả cho phép khôi phục vượt ra ngoài điểm kiểm tra cuối cùng. Nó kết nối với lý thuyết cắt nhất quán của các ảnh chụp toàn cục.

Core questions

• Làm thế nào để các điểm kiểm tra trên các tiến trình có thể được kết hợp thành một đường khôi phục nhất quán?
• Hiệu ứng domino là gì và sự phối hợp ngăn chặn nó như thế nào?
• Khi nào việc ghi nhật ký tin nhắn cho phép khôi phục vượt qua điểm kiểm tra gần đây nhất?

Key theories

Checkpointing phối hợp

Các tiến trình phối hợp để các điểm kiểm tra của chúng cùng nhau tạo thành một trạng thái toàn cục nhất quán, đảm bảo một đường khôi phục có thể sử dụng được và tránh các lần quay lui theo tầng với chi phí đồng bộ hóa.

Checkpointing không phối hợp và hiệu ứng domino

Nếu các tiến trình kiểm tra độc lập, việc khôi phục có thể yêu cầu quay lui từng tiến trình để tìm một tập hợp nhất quán, có khả năng lan truyền ngược trở lại đến tận đầu (hiệu ứng domino), điều mà sự phối hợp hoặc ghi nhật ký được thiết kế để tránh.

Ghi nhật ký tin nhắn

Ghi nhật ký các tin nhắn mà một tiến trình nhận được (một cách bi quan, lạc quan hoặc nhân quả) cho phép một tiến trình đang khôi phục phát lại chúng một cách xác định và tiến xa hơn điểm kiểm tra cuối cùng của nó, khôi phục công việc gần đây mà không cần quay lui toàn cục.

Clinical relevance

Checkpoint/khởi động lại giúp các tính toán hiệu năng cao và khoa học chạy dài hạn có khả năng phục hồi trước các lỗi nút, và checkpointing không đồng bộ mang lại cho các hệ thống xử lý luồng hiện đại khả năng đảm bảo khôi phục lỗi chính xác một lần.

History

Dựa trên lý thuyết ảnh chụp nhất quán của Chandy và Lamport, Koo và Toueg đã chính thức hóa checkpointing phối hợp vào năm 1987, và hàng thập kỷ nghiên cứu về ghi nhật ký và các sơ đồ không phối hợp đã được tổng hợp trong khảo sát năm 2002 của Elnozahy và các đồng nghiệp, tài liệu tham khảo tiêu chuẩn về khôi phục quay lui.

Debates

Checkpointing phối hợp so với không phối hợp

Checkpointing phối hợp đảm bảo một đường khôi phục rõ ràng nhưng làm tăng chi phí đồng bộ hóa và phối hợp toàn cục; checkpointing không phối hợp rẻ hơn tại thời điểm kiểm tra nhưng có nguy cơ gây ra hiệu ứng domino và khôi phục phức tạp, vì vậy lựa chọn đúng đắn phụ thuộc vào tỷ lệ lỗi và quy mô.

Key figures

• K. Mani Chandy
• Leslie Lamport
• Sam Toueg
• Lorenzo Alvisi

Seminal works

• elnozahy2002
• koo1987
• chandy1985

Frequently asked questions

Hiệu ứng domino trong khôi phục quay lui là gì?

Khi các tiến trình kiểm tra mà không có sự phối hợp, việc quay lui một tiến trình có thể buộc một tiến trình phụ thuộc cũng phải quay lui, điều này có thể lan truyền ngược trở lại toàn bộ quá trình tính toán—có khả năng đến tận đầu. Checkpointing phối hợp hoặc ghi nhật ký tin nhắn được sử dụng để ngăn chặn điều này.