Bài giảng Hệ phân tán - Chịu lỗi

VI. Chịu lỗi Hệ phân tán (NW605) Sự cố / thất bại – failure (Coulouris 2.3.2) Process resillience Liên lạc đáng tin cậy – reliable communication Khôi phục – recovery Độ tin tưởng - dependability Availability (độ sẵn có): xác xuất hệ thống hoạt động đúng tại một thời điểm bất kì và sẵn sàng thực hiện các chức năng của mình. ví dụ availability 99,999% có nghĩa là hệ thống sẽ hoạt động đúng trong 99,999% thời gian. Reliability (độ tin cậy): năng lực của hệ thống trong việc chạy liên tục mà không gặp sự cố. Lưu ý rằng reliability không giống availability. Safety (độ an toàn): khi một hệ thống (tạm thời) không thể chạy đúng, không có hậu quả gì nghiêm trọng xảy ra. Ví dụ bộ phận điều khiển một nhà máy điện hạt nhân đòi hỏi mức độ an toàn cao Maintainability (khả năng bảo trì): một hệ thống trục trặc có thể sửa chữa dễ dàng đến đâu. Điều này đặc biệt hữu ích nếu muốn có sự hồi phục tự động sau sự cố. Và nó cũng dẫn đến availability cao. Sự cố - failure Thuật ngữ: Failure – Sự cố: Một hệ thống gặp sự cố khi nó không thỏa mãn cam kết và không cung cầp dịnh vụ theo cách được tả rõ. Error - Sai: phần trạng thái hệ thống dẫn đến sự cố (nghĩa là nó khác với giá trị mà đáng ra nó phải có) Fault - Lỗi: nguyên nhân của sai (kết quả của sai lầm trong thiết kế, lỗi chế tạo, suy thoái, hay nhiễu từ bên ngoài) Đệ qui: Sự cố có thể là một lỗi Lỗi chế tạo dẫ đến sự cố đĩa Sự cố đĩa là một lỗi dẫn đến sự cố cơ sở dữ liệu Sự cố cơ sở dữ liệu là một lỗi dẫn đến sự cố của dịch vụ email Sự cố toàn phần/bộ phận Sự cố toàn phần: 	Tất cả các thành phần của một hệ thống bị trục trặc Điển hình ở hệ thống không phân tán Sự cố bộ phận: 	Một vài (nhưng không phải toàn bộ) các thành phần của hệ thống gặp trục trặc. Một số thành phần bị ảnh hưởng Một số thành phần khác hoàn toàn không Được xem là một lỗi đối với toàn bộ hệ thống Fault tolerance – chịu lỗi Chịu lỗi: Hệ thống có thể cung cấp dịch vụ ngay cả khi đang có lỗi. Mục tiêu: Tự động phục hồi từ sự cố bộ phận. Hiệu năng toàn cục không bị ảnh hưởng nặng Kĩ thuật: Ngăn chặn: ngăn chặn hoặc giảm số lần xuất hiện lỗi Đoán: đoán các lỗi có thể xảy ra và xử lý chúng Che dấu: che dấu các lần xuất hiện của lỗi Khôi khục: khôi phục từ một trạng thái có lỗi tới một trạng thái không có lỗi. Các loại lỗi và sự cố Lỗi: Transient fault – lỗi nhất thời: xảy ra một lần rồi thôi Intermittent fault – thỉnh thoảng xảy ra rồi biến mât Permanent fault – luôn có mặt cho đến khi thành phần có lỗi được thay thế Sự cố: Process failure - sự cố tiến trình: tiến trình chạy đúng hoặc sai Storage failure – sự cố nơi lưu trữ: không thể truy nhập thiết bị lưu trữ thứ cấp ‘bền vững’ Communication failure - Sự cố liên lạc: liên lết liên lạc hoặc một nút gặp sự cố. Các mô hình sự cố Crash Failure: server treo (chạy đúng cho đến khi treo). Fail-stop: các tiến trình khác có thể phát hiện tình trạng treo Fail-silent: các tiến trình khác không thể phát hiện tình trạng Omission Failure: Receive Omission: thông điệp đến nơi nhưng receiver không nhận Send Omission: sender thực hiện send, nhưng thông điệp không được gửi Timing Failure: phản ứng server ngoài khoảng thời gian định trước Response Failure: server trả lời sai. Value Failure: kết quả trả lời có giá trị sai State Transition Failure: server không chuyển trạng thái đúng Arbitrary Failure (Byzantine failure): server phản ứng tùy tiện vào các thời điểm tùy tiện Phát hiện sự cố Các hệ đồng bộ: Timeout Failure detector gửi probe để phát hiện sự cố treo Các hệ không đồng bộ Timeout không đảm bảo gì Failure detector có thể theo dõi các tiến trình được nghi là có sự cố Kết hợp kết quả từ nhiều detector Làm thế nào để phân biệt giữa sự cố liên lạc và sự cố tiến trình? Che dấu sự cố 	Cố gắng không để sự cố gây ảnh hưởng tới các tiến trình khác Redundancy - Dư thừa: Dư thừa thời gian: cho phép một hành động được thực hiện nhiều lần nếu cần, khắc phục sự cố Dư thừa thông tin: dữ liệu có thông tin thừa để khi cần có thể dùng để khôi phục dữ liệu bị mât Dư thừa vật lý: sao lặp tài nguyên (tiến trình, dữ liệu…), sao lặp thành phần vật lý của hệ thống Process resiliencekhả năng khôi phục của tiến trình 	Sao lặp để bảo vệ trước các sự cố tiến trình Nhóm: Tổ chức các tiến trình giống nhau thành các nhóm Các nhóm tiến trình có tính động Tiến trình có thể là thành viên của nhiều nhóm Cơ chế quản lý nhóm và thành viên Client giao tiếp với cả nhóm như thể với 1 tiến trình Nhóm phẳng/cây Nhóm phẳng: các quyết định do tập thể đưa ra Nhóm cây: quyết định do điều phối viên / nhóm trưởng đưa ra Sao lặp Tạo nhóm sao lặp Primary-Based: Một primary (thành phần chính) và các thành phần back-up Nhóm có cấu trúc cây Nếu primary treo thì chọn một primary mới Replicated-Write: Chủ động sao lặp Nhóm phẳng Sắp thứ tự các yêu cầu (bài toán multicast toàn vẹn-atomic) k Fault Tolerance: Có thể chịu được sự cố tại k thành phần mà vẫn hoạt động đúng theo đặc tả Cần k+1 replica nếu các sự cố thuộc loại fail-silence/fail-stop Cần 2k+1 replica nếu các sự cố thuộc loại byzantine Đồng thuận Ví dụ: bầu cử, commit/abort giao tác, phân công công việc, mutual exclusion Các thuật toán trước đều giả thiết rằng không có sự cố Chuyện gì xảy ra khi Có sự cố tiến trình? Có sự cố liên lạc? Có thể có sự cố byzantine? Bài toán 2 cánh quân – tiến trình không lỗi, liên lạc lỗi Bài toán các vị tướng byzantine – tiến trình lỗi Mong muốn: tất cả các tiến trình không có lỗi đều đạt được đồng thuận (sau một số bước hữu hạn) Liên lạc đáng tin cậy Các kênh liên lạc cũng có thể có sự cố Chú trọng che crash failure và omission failure Liên lạc điểm-tới-điểm đáng tin cậy Giao thức tầng giao vận đáng tin cậy (vd. TCP) Che được omission failure, không che crash failure Ví dụ RPC và các sự cố có thể xảy ra Client không thể định vị server Thông điệp yêu cầu gửi cho server bị thất lạc Server treo sau khi nhận một yêu cầu Thông điệp trả lời bị thất lạc Client treo sau khi gửi yêu cầu Xử lý như thế nào? Liên lạc nhóm đáng tin cậy Cách tiếp cận cơ bản đối với multicast đáng tin cậy Liên lạc nhóm đáng tin cậy Multicast theo cây Failure Recovery – Khắc phục sự cố Khôi phục từ một trạng thái sai tới một trạng thái không có lỗi Vấn đề: Tái chiếm tài nguyên: khóa, bộ nhớ đệm giữ tại các nút khác Tính nhất quán: Lùi các thao tác đang thực hiện dở dang trước khi khởi động lại Hiệu quả: tránh khởi động lại toàn bộ hệ thống Khắc phục tiến và khắc phục lùi Khắc phục tiến – forward recovery Sửa lỗi mà không quay về một trạng thái cũ Xóa lỗi khỏi trạng thái hiện tại Không thực hiện lại các tính toán Đôi khi bất khả thi Khắc phục lùi – backward recovery Sửa lỗi bằng cách quay về một trạng thái cũ đúng Ví dụ: gửi lại một gói tin bị mất Thực hiện lại các tính toán Lỗi có thể tái xuất Có thể có những thành phần không thể khôi phục Khắc phục lùi Cách tiếp cận tổng quát: Khôi phục tiến trình về điểm khôi phục – recovery point Khôi phục hệ thống bằng cách khôi phục tất cả các tiến trình active Các cách tiếp cận cụ thể: Operation-based recovery – khôi phục theo thao tác Ghi nhật trình (log) tất cả các thao tác Khôi phục về điểm khôi phục bằng cách lùi các thay đổi State-based recovery – khôi phục theo trạng thái: Lưu trạng thái đầy đủ tại các điểm kiểm soát – checkpoint Khôi phục tiến trình từ checkpoint. Nhật trình hoặc các checkpoint được ghi tại nơi lưu trữ bền vững Khắc phục lùi - Khôi phục theo thao tác Khôi phục theo thao tác – nhật trình thao tác: Cập nhật tại chỗ kèm theo ghi nhật trình trước đó Mỗi thay đổi (cập nhật) dữ liệu đều được ghi lại trong một nhật trình, trong đó có: Tên phần tử dữ liệu (định danh) Trạng thái cũ của phần tử dữ liệu (để undo) Trạng thái mới của phần tử dữ liệu (để redo) Nhật trình undo được ghi trước khi sửa đổi được thực hiện (write-ahead log) Khắc phục lùi - Khôi phục theo trạng thái Khôi phục theo trạng thái – checkpoint: Thường xuyên lập các checkpoint trong khi chạy Dùng checkpoint: Bi quan/lạc quan: Bi quan: cho rằng sự cố hay xảy ra, tối ưu hóa cho khôi phục sự cố Lạc quan:cho rằng sự cố ít khi xảy ra, cực tiểu hóa chi phí checkpoint Độc lập/phối hợp Phối hợp: các tiến trình cùng lập checkpoint Độc lập: mỗi tiến trình lập các checkpoint địa phương độc lập với các tiến trình khác Đồng bộ/không đồng bộ: Đồng bộ: tính toán phân tán bị khóa trong khi lập checkpoint Không đồng bộ: tính toán phân tán vẫn tiếp diễn trong khi lập checkpoint Khắc phục lỗi trong hệ phân tán Tiến trình gặp sự cố có thể gây ảnh hưởng nhân-quả đến các tiến trình khác Khi khôi phục tiến trình bị sự cố, phải undo hiệu ứng của nó đối với các tiến trình khác Phải roll back tất cả các tiến trình bị ảnh hưởng Mọi tiến trình phải thiết lập các điểm khôi phục Phải roll back về một trạng thái toàn cục nhất quán Khắc phục lỗi trong hệ phân tán Hiệu ứng Domino: P1 thất bại → roll back: P1 R13 P2 thất bại → P2 R23 Thông điệp mồ côi m được nhận nhưng chưa được gửi → P1 R12 P3 thất bại → P3 R32 → P2 R21 → P1 R11, P3 R31 Các quan hệ phụ thuộc của gửi nhận thông điệp cộng với checkpoint độc lập có thể buộc hệ thống phải roll back về trạng thái khởi đầu. Khắc phục lỗi trong hệ phân tán Thông điệp bị thất lạc: Sự cố P2 → P2 R21 Thông điệp m được ghi nhận là đã được gửi (bởi P1) nhưng không được nhận (bởi P2), và sau khi roll back m sẽ không bao giờ được nhận. m bị thất lạc m thất lạc do roll back hoặc do kênh liên lạc là không thể phân biệt được! Giải quyết như thế nào? Khắc phục lỗi trong hệ phân tán Livelock: P2↓ → P2 R21 → P1 R11. n1 đang trên đường truyền Thông điệp trước khi roll back, n1, được nhận sau roll back Buộc phải roll back lần nữa, P2 R21 → P1 R11 Với thời gian căn thích hợp, roll-back có thể lặp lại vô hạn Checkpoint nhất quán Lát cắt nhất quán: