Lưu ảnh và phục hồi

29 Chương 3 Lưu ảnh và phục hồi 3.1 Một số vấn đề cơ bản 3.1.1 Sơ lược về lưu ảnh Khi chạy các ứng dụng trong một thời gian dài, một vấn đề được quan tâm là làm sao để giảm khối lượng công việc xử lý bị mất khi có sự cố xảy ra. Việc chạy lại ứng dụng từ đầu là điều không mong muốn. Một cách giải quyết là làm sao lưu lại được các trạng thái trung gian của chương trình, của ứng dụng trong quá trình chạy để khi có sự cố thì chạy lại chương trình hay ứng dụng từ trạng thái trung gian đó. Đây là ý tưởng của phương pháp lưu ảnh. Để lưu ảnh một chương trình phục vụ yêu cầu chịu lỗi (fault tolerance) thì cần phải lưu đủ những thông tin cần thiết lên một vùng nhớ ổn định. Khi chương trình gặp sự cố, các trạng thái tạm thời của chương trình mấy đi, thì chương trình vẫn có thể phục hồi lại từ những thông tin đã được lưu đó. Hình 3.1 là thể hiện một ví dụ của quá trình lưu ảnh và phục hồi. Hình 3.1: Các ảnh lưu được lấy định kỳ cho kháng lỗi [17] 30 Trong kỹ thuật phục hồi quay lui (rollback-recovery), chương trình dược xem như là một tập hợp các tiến trình. Lưu ảnh sẽ được thực hiện trên các tiến trình để lưu giữ trạng thái trung gian của các tiến trình. Tập hợp các ảnh lưu này chính là ảnh toàn cục của chương trình. Đối với một số giải thuật phục hồi thì những ảnh lưu này cung cấp chưa đủ thông tin cần thiết để phục hồi chương trình. Một số thông tin khác như sự tương tác với thiết bị nhập xuất, các sự kiện xảy ra với các tiến trình hay các thông điệp trao đổi giữa các tiến trình là cần thiết để phục hồi chương trình. Chúng ta có thể lưu ảnh cho một tiến trình, cho một chương trình, hay thậm chí cho một hệ thống. Tùy vào đối tượng cần lưu ảnh (checkpoint) khác nhau mà các thông tin cần thiết phải lưu trữ trong một lần lưu và phương pháp lưu ảnh sẽ phức tạp khác nhau. 3.1.2 Ứng dụng của lưu ảnh Không chỉ là một công cụ hỗ trợ cho yêu cầu chịu lỗi (fault tolerance) của các hệ thống, lưu ảnh còn là một công cụ hữu ích trong rất nhiều công việc khác. Có thể nêu ra đây một số ứng dụng khác của quá trình lưu ảnh như: Hoán đổi công việc (job-swapping): Với công cụ lưu ảnh, chúng ta có thể tạm dừng một chương trình đang chạy (swap off) bằng cách lưu ảnh chương trình sau đó hủy các tiến trình tương ứng của chương trình. Việc chạy một chương trình khác thay thế (swap on) là một trường hợp đơn giản của phục hồi. Di dời tiến trình (process migration): Với công cụ lưu ảnh, một tiến trình có thể được di dời từ máy này sang máy khác bằng cách lưu ảnh tiến trình trên máy thứ nhất sau đó phục hồi tiến trình này trên máy thứ hai. Thực ra, việc lưu ảnh để hoán đổi công việc hay để chịu lỗi đều là các trường hợp của di dời tiến trình, chỉ có điều việc di dời diễn tra trên cùng một máy nhưng tiến trình được phục hồi ở thời điểm khác. Sự mở rộng của di dời tiến trình là di dời chương trình (program migration). Điểm khác biệt ở đây là một chương trình có thể bao gồm nhiều tiến trình chạy trên cùng một máy hay trên các máy khác nhau. Với công cụ lưu ảnh, chúng ta có thể lưu ảnh cho tất cả các tiến trình trong một chương trình, sau đó di dời chương trình 31 này đến các máy khác tương ứng hay trên cùng một máy nhưng phục hồi ở thời điểm khác. Tìm lỗi (debugging): Thông tin được lưu trữ trong một ảnh lưu tương tự như thông tin được lưu trữ trong một tập tin nhân (core file) tiêu biểu. Nếu nhiều ảnh lưu thay vì chỉ một ảnh lưu mới nhất được lưu trữ thì người sử dụng có thể chạy lại chương trình của họ tại bất kỳ thời điểm nào nhằm phát hiện nguyên nhân gây lỗi. Phương pháp tìm lỗi này được gọi là playback debugging. Playback debugging đặc biệt hữu ích trong phương pháp lập trình song song, lập trình phân bố. Những chương trình song song hay phân bố chứa nhiều yếu tố bất định (non-determinism) hơn trong chương trình tuần tự, do đó những điều kiện gây ra lỗi có thể không được sinh ra nếu như chúng ta chạy lại chương trình từ đầu. Playback debugging còn rất hiệu quả trong việc gỡ rối các ứng dụng chạy trong thời gian dài, khi mà người sử dụng không có nhiều thời gian để chạy lại chương trình và tìm ra chỗ sai sót. 3.1.3 Trạng thái lưu ảnh Trạng thái tiến trình (process state): bao gồm các giá trị của các thanh ghi trong CPU, giá trị của bộ nhớ (memory) và trạng thái của hệ điều hành. Thông thường, bộ nhớ của một tiến trình gồm có: mã thực thi (executable code), biến toàn cục (global variables), ngăn xếp (heap) và chồng (stack). Trạng thái hệ thống (system state): trạng thái của hệ thống truyền thông điệp gồm tập hợp tất cả các trạng thái của các tiến trình tham gia vào hệ thống và trạng thái của các kênh truyền (communication channels). Trạng thái nhất quán của hệ thống (consistent system state): là trạng thái mà với mỗi thông điệp được ghi nhận là đã nhận ở một tiến trình nào đó thì thông điệp cũng phải được ghi nhận là đã được gởi. Sau đây là hai ví dụ minh họa. 32 Hình 3.2: Trạng thái (a) nhất quán và (b) không nhất quán của hệ thống [13] Hình 3.2 (a) cho thấy một trạng thái nhất quán của hệ thống. Đường biểu diễn trạng thái của hệ thống cắt qua thông điệp m1, tức là thông điệp m1 đã được gởi nhưng chưa được nhận, nhưng đây là một trạng thái nhất quán do không vi phạm các ràng buộc trong định nghĩa. Hình 3.2 (b) biểu diễn một trạng thái không nhất quán vì trạng thái của tiến trình P2 cho thấy tiến trình P2 đã nhận m2 nhưng trạng thái của P1 lại cho thấy thông điệp m2 chưa được gởi. Các phương pháp rollback- recovery phải đảm bảo đưa hệ thống về trạng thái nhất quán cho dù có xảy ra lỗi, nhưng không nhất thiết phải đưa hệ thống về trạng thái nhất quán ngay trước khi xảy ra lỗi mà chỉ cần đưa về một trạng thái nhất quán nào đó mà hệ thống đã trải qua trước khi xảy ra lỗi. Thông điệp đang truyền (in-transit message): Một thông điệp đã được gửi đi nhưng chưa được nhận gọi là thông điệp đang truyền (in-transit). Thông điệp m1 trong hình 3.2 (a) là một ví dụ. Các thông điệp đang truyền không làm cho trạng thái hệ thống trở nên không nhất quán. Các thông điệp đang truyền trong hệ thống có được ghi nhận vào trạng thái nhất quán của hệ thống hay không phụ thuộc vào mô hình của hệ thống sử dụng giao thức truyền nhận tin cậy hay không tin cậy. 33 Hình 3.3: Hiện thực rollback recovery (a) trên giao thức truyền-nhận tin cậy (b) trực tiếp trên giao thức truyền-nhận không tin cậy [13] Trong hình 3.3 (a), giao thức rollback-recovery được xây dựng trên giao thức truyền nhận tin cậy. Nếu các tiến trình hoạt động một cách bình thường, không có lỗi xảy ra, thì giao thức truyền-nhận bên dưới sẽ chịu trách nhiệm xử lý các mất mát, hư hỏng của thông điệp trên đường truyền nhằm bảo đảm các thông điệp đang truyền sẽ luôn tới đích. Nhưng khi có lỗi xảy ra ở các tiến trình thì các lỗi truyền- nhận phải được xử lý bởi chính giao thức rollback-recovery. Để làm được công việc quản lý lỗi, giao thức rollback-recovery phải xem các thông điệp đang truyền như là một phần trong trạng thái nhất quán của hệ thống. Nếu giao thức rollback-recovery được xây dựng trên một giao thức truyền nhận không tin cậy như trong hình 3.3 (b), thì ngay cả khi không có lỗi xảy ra trong hệ thống thì vẫn có thể xảy ra hiện tượng mất các thông điệp đang truyền do kênh truyền không tin cậy. Chính vì vậy trong mô hình này không thể phân biệt được các thông điệp đang truyền bị mất do lỗi của kênh truyền hay do lỗi của giao thức rollback-recovery. Trong trường hợp này, giao thức rollback-recovery không cần phải xử lý việc các thông điệp đang truyền bị mất và có thể không xem các thông điệp đang truyền như là một phần trong trạng thái của hệ thống. Giao tiếp của hệ thống với bên ngoài: Hệ thống truyền thông điệp thường giao tiếp với bên ngoài để nhận các yêu cầu dịch vụ, các dữ liệu đầu vào cũng như xuất các kết quả tính toán. Để đơn giản trong việc biểu diễn việc giao tiếp của hệ thống 34 với bên ngoài thì thế giới bên ngoài được mô hình như là một tiến trình OWP (outside world process). Tiến trình này có đặc điểm không bị lỗi, không chứa thông tin để phục hồi hệ thống cũng như không tham gia vào quá trình phục hồi hệ thống. Tuy nhiên khi hệ thống xảy ra lỗi và được phục hồi về một trạng thái nào đó, có thể xảy ra những tình huống không mong muốn liên quan đến OWP. Từ những phân tích trên, rõ ràng cần phải có một cơ chế đặc biệt cho việc giao tiếp giữa hệ thống với thế giới bên ngoài. Nói cách khác, cần có một cơ chế đặc biệt trong giao tiếp với tiến trình OWP. Cơ chế đó là trước khi gởi thông điệp ra OWP, hệ thống phải đảm bảo có thể phục hồi hệ thống về trạng thái ngay trước khi thông điệp được gởi. Vấn đề này thường được gọi là output commit. Và vì các dữ liệu nhập không thể được tái sản sinh nên hệ thống cũng phải lưu trữ các thông điệp nhận được từ OWP (dữ liệu nhập, yêu cầu…) để sau này sử dụng trong quá trình phục hồi hệ thống. Thực hiện các công việc trên sẽ dẫn đến các vấn đề sau: thời gian trì hoãn của các dữ liệu xuất nhập và sự giảm hiệu xuất của hệ thống khi thực hiên xuất nhập. Thời gian trì hoãn của các dữ liệu xuất nhập ở đây được định nghĩa là thời gian từ khi hệ thống gởi thông điệp cho OWP đến khi thông điệp được nhận bởi OWP hay thời gian từ khi OWP gởi thông điệp đến hệ thống và hệ thống có thể nhận thông điệp đó để xử lý. 3.1.4 Vùng nhớ ổn định (stable storage) Rollback-recovery sử dụng một nơi lưu trữ ổn định để lưu trữ các ảnh tiến trình, ghi nhận các thông tin về các sự kiện và những thông tin khác cần thiết cho việc phục hồi. Vùng nhớ ổn định trong rollback-recovery chỉ là một khái niệm trừu tượng và thường hay bị nhầm lẫn với các thiết bị lưu trữ cụ thể để hiện thực nó. Vùng nhớ ổn định phải đảm bảo rằng các dữ liệu phục hồi không bị mất khi sự cố xảy ra cũng như trong các quá trình phục hồi. Yêu cầu này có thể được đáp ứng bằng nhiều cách hiện thực lưu trữ khác nhau: 35 - Trong những hệ thống chỉ chịu được duy nhất một tiến trình gặp sự cố thì vùng nhớ ổn định có thể là bộ nhớ tạm thời (volatile memory) trên các tiến trình khác. - Trong những hệ thống mà mục tiêu là chịu được những lỗi nhất thời (transitent falure – những lỗi chỉ xảy ra một lần và sau đó biến mất) với số lượng bất kỳ, vùng nhớ ổn định có thể là một đĩa nhớ cục bộ trên mỗi máy. - Trong những hệ thống chịu được những lỗi không nhất thời (non-transitent), vùng nhớ ổn định phải là một thiết bị nhớ lâu dài, nằm bên ngoài các máy đang chạy tiến trình. Một hệ thống tập tin nhân bản có thể là một cách hiện thực trong trường hợp này. 3.1.5 Dọn rác (garbage collection) Lưu ảnh là sự ghi nhận thông tin về các sự kiện (event logs) nên sẽ phải sử dụng tài nguyên lưu trữ. Khi ứng dụng đang được tiến hành và thông tin phục hồi được lưu trữ ngày càng nhiều, một số thông tin phục hồi được lưu trữ có thể trở nên không cần thiết cho sự phục hồi. Dọn rác là công việc nhằm bỏ đi các thông tin không cần thiết đó. Một phương pháp phổ biến để dọn rác đó là xác định một tập các ảnh lưu nhất quán gần nhất, gọi là đường phục hồi (recovery line). Tất cả những thông tin liên quan đến các tiến trình hay các sự kiện nằm trước đường phục hồi đều bị loại bỏ. Dọn rác tuy không được quan tâm nhiều về lý thuyết nhưng nó lại có ảnh hưởng rất lớn đến các giao thức rollback-recovery bởi vì chạy một giải thuật đặc biệt để dọn rác có thể làm tăng tổng chi phí (overhead). Hơn nữa, các giao thức phục hồi khác nhau ở khối lượng cũng như tính chất của các thông tin phục hồi cần được lưu trữ. Do đó độ phức tạp của các giải thuật dọn rác cũng như tần suất thực hiện giải thuật dọn rác của các giao thức phục hồi khác nhau là khác nhau. 36 3.2 Các cấp độ lưu ảnh Trong quá trình thực hiện các công cụ lưu ảnh, tùy vào sự tham gia của người lập trình, người sử dụng cũng như mức độ xâm nhập vào hệ điều hành mà ta chia sự hiện thực thành nhiều cấp độ khác nhau. 3.2.1 Lưu ảnh cấp hệ điều hành (OS checkpointing) Ở cấp độ hiện thực này thì việc lưu ảnh sẽ được đảm nhiệm bởi hệ điều hành. Thông thường thì bất cứ chương trình nào cũng có thể được lưu ảnh bởi hệ điều hành mà không cần sự can thiệp từ phía người lập trình hay người sử dụng. Tuy nhiên hầu hết các hệ điều hành đều không hiện thực việc lưu ảnh mà chủ yếu quả lý việc định thời các tiến trình. Có một số ngoại lệ như Unicos, KeyOS và fault- tolerance March là những hệ điều hành có hiện thực rollback-recovery hay Sprite là một hệ điều hành phân bố có hỗ trợ việc di dời tiến trình như là một tác vụ cơ bản. 3.2.2 Lưu ảnh trong suốt cấp người dùng (user-level transparent checkpointing) Ở cấp độ hiện thực này thì việc lưu ảnh được thực hiện bởi các chương trình. Tính trong suốt thường được thực hiện bằng cách biên dịch chương trình với một thư viện lưu ảnh đặc biệt, hay bằng một số cách hiện thực khác, chẳng hạn như viết lại tập tin thực thi (executable file). Do việc lưu ảnh được thực hiện ở cấp chương trình chứ không phải ở cấp hệ điều hành nên khả năng phục hồi lại trạng thái của hệ điều hành là một vấn đề quan trọng, cần phải quan tâm. Chẳng hạn như các hệ điều hành thường cấp cho mỗi tiến trình một số nhận dạng (process id) và quá trình cấp số nhận dạng này là không thể phục hồi. Hơn nữa, hệ điều hành thường không cho phép chương trình người sử dụng lưu ảnh trạng thái của hệ thống tập tin (file system). Điều này có thể khắc phục được bằng cách giới hạn chương trình được lưu ảnh để nó chỉ có thể lấy được một số thông tin có thể phục hồi được của hệ thống. Ví dụ như một số chương trình có sử dụng tập tin chỉ đọc, chỉ ghi hay đọc-ghi tuần tự có thể được lưu ảnh bằng cách lưu lại tên tập tin cũng như con trỏ tập tin tại thời điểm lưu ảnh. Hơn nữa, 37 chương trình phải giả định rằng các tiến trình của nó có các số nhận dạng thay đổi trong suốt quá trình lưu ảnh và phục hồi. Những giới hạn trên không ảnh hưởng đến phần lớn các ứng dụng cần sử dụng kỹ thuật lưu ảnh. Hiện nay có nhiều công cụ lưu ảnh được xây dựng ở mức độ hiện thực này. 3.2.3 Lưu ảnh không trong suốt cấp người dùng (user-level non-transparent checkpointing) Ở cấp độ hiện thực này, người lập trình sẽ chủ động kết hợp việc lưu ảnh vào trong chương trình của họ, thông thường là với sự giúp đỡ của các thư viện lập trình hay các bộ tiền xử lý (preprocessor). Cách lưu ảnh theo kiểu này hiển nhiên sẽ tạo ra nhiều vấn đề cần giải quyết, nhiều trách nhiệm hơn cho người lập trình. Những trách nhiệm này bao gồm tính đúng đắn (correctness), đây là điều mà người lập trình khi sử dụng công cụ lưu ảnh theo kiểu trong suốt không cần phải quan tâm. Những ưu điểm của phương pháp này là sự hiệu quả (performance) cũng như độ linh động (flexibility). Người lập trình có thể đặc tả những thông tin chính xác, cần thiết cho việc phục hồi, do đó thông tin lưu trữ khi lưu ảnh sẽ ít hơn so với phương pháp trong suốt. Hơn nữa, với kiểu lưu ảnh không trong suốt này, người lập trình có thể lưu giữ các ảnh tiến trình theo một định dạng độc lập với máy tính. Sự độc lập này cho phép thông tin về lưu ảnh có thể được lưu trữ trên nhiều máy tính có kiến trúc khác nhau. Điều này không thể hiện thực được với phương pháp lưu ảnh trong suốt. Hiện nay cũng có rất nhiều hệ thống hiện thực công cụ lưu ảnh theo kiểu không trong suốt này. 3.3 Các tiêu chí đánh giá Một trong những tiêu chí quan trọng của một công cụ lưu ảnh (checkpointer) đó là tốc độ. Người sử dụng thường không muốn sử dụng những công cụ lưu ảnh làm chậm chương trình của họ cho dù công cụ đó có thể giúp chương trình của họ có thể chịu lỗi. Do đó, khi xây dựng một công cụ lưu ảnh thì cần phải đặc biệt quan tâm đến tốc độ của giải thuật. Trong việc lưu ảnh thì tốc độ được đánh giá bằng ba 38 tiêu chí: thời gian lưu ảnh (checkpoint time), tổng chi phí (checkpoint overhead) và sự trì hoãn (latency). 3.3.1 Thời gian lưu ảnh (Checkpoint time) Checkpoint time (thời gian lưu ảnh) là tổng thời gian cần thiết cho một công cụ lấy một ảnh chụp của tiến trình. Đây là một sự đo lường thời gian chạy của một công cụ lưu ảnh cũng như để tính xem có bao nhiêu ảnh có thể lấy trong một khoảng thời gian. Checkpoint time bị giới hạn bởi tốc độ ghi lên các nơi lưu trữ ổn định (stable storage). Ví dụ như một tập tin ảnh có kích thước là 5MB thì checkpoint time ít nhất là bằng với thời gian cần thiết để ghi tập tin này lên một nơi lưu trữ ổn định. Tăng tốc độ ghi của thiết bị lưu trữ hay giảm kích thước của tập tin ảnh là những cách để làm giảm checkpoint time. 3.3.2 Tổng chi phí lưu ảnh (Checkpoint overhead) Checkpoint overhead là tổng thời gian cộng thêm vào thời gian chạy của chương trình ứng dụng như là một chi phí khi sử dụng lưu ảnh. Lưu ý rằng checkpoint overhead có thể nhỏ hơn tổng của các checkpoint time nếu như việc ghi của chương trình ứng dụng. Đây là một sự đo lường mức độ chiếm dụng chương trình của công cụ lưu ảnh cũng như để đo lường mức độ song song, độ đồng thời của một giải thuật lưu ảnh. Chúng ta có thể định nghĩa độ đồng thời bằng công thức sau: Một trong những mục tiêu của các giải thuật lưu ảnh là cực đại hóa độ đồng thời, từ đó giảm tổng chi phí đến mức thấp nhất có thể được. 3.3.3 Độ trễ (Latency) Độ trễ là sự đo lường khả năng tương tác thời gian thực (real-time behavior). Nó được định nghĩa là tổng thời gian mà chương trình đích bị gián đoạn do việc sử dụng lưu ảnh. Giảm độ trễ là một yêu cầu quan trọng, đặc biệt trong những ứng 39 dụng có tính tương tác. Một công cụ lưu ảnh được gọi là thành công trong một ứng dụng có tính tương tác ở các tiêu chí latency nếu người sử dụng không nhận ra được chương trình đang được lưu ảnh. Hay nói cách khác, công cụ lưu ảnh chỉ làm gián đoạn chương trình trong một khoản thời gian rất nhỏ. Ngoài yếu tố tốc độ cao, khi phân tích và đánh giá các giải thuật lưu ảnh cũng như trong quá trình hiện thực các giải thuật, ta cần phải quan tâm đến một số yếu tố khác. Chẳng hạn như việc sử dụng và truy cập bộ nhớ, các thông điệp cần phải thêm vào trong quá trình lưu ảnh hay các thông tin cần phải lồng vào trong các thông điệp ứng dụng. Những yếu tố này cũng sẽ ảnh hưởng đến hiệu suất chung của các giải thuật lưu ảnh. 3.4 Kỹ thuật lưu ảnh tiến trình đơn và một số cải tiến Trước khi tìm hiểu về các giải thuật lưu ảnh trên một chương trình hay trên một hệ thống thì sự tìm hiểu việc lưu ảnh trên một tiến trình là cần thiết. Nó giúp chúng ta nắm được cấu trúc của một ảnh lưu cũng như cách thức tiến hành lưu ảnh. Trong phần này trình bày phương pháp lưu ảnh trên một tiến trình và các cải tiến của phương pháp này. Hình 3.4: Lưu ảnh một tiến trình [17] 40 Khi một chương trình đang thực thi thì trạng thái của nó bao gồm các giá trị trong bộ nhớ (memory), trong các thanh ghi (CPU registers) và trạng thái của hệ điều hành (bao gồm trạng thái tập tin). Thông thường, bộ nhớ được chia thành bốn phần: mã thực thi (executable code), biến toàn cục (global variables), ngăn xếp (heap) và chồng (stack). Trong bốn phần này, biến toàn cục, ngăn xếp và chồng cần được lưu trữ cùng với những thanh ghi trong một ảnh tiến trình. Mã thực thi thường không thay đổi trong tập tin thực thi của chương trình đó do đó có thể phục hồi lại từ tập tin thực thi khi có lỗi xảy ra. Quá trình lưu ảnh có thể được thể hiện như hình 3.4. Nếu như công cụ lưu ảnh được thực hiện ở cấp hệ điều hành thì tất cả những thông tin thể hiện góc nhìn từ chương trình về hệ thống tại thời điểm lưu ảnh có thể được lưu trữ. Nếu công cụ lưu ảnh được hiện thực ở cấp người sử dụng thì nó không có khả năng lưu ảnh tất cả thông tin trạng thái của hệ điều hành, thay vào đó là một số thông tin mà hệ điều hành cho phép. Các thông tin này sẽ được lưu trữ vào một vùng nhớ tạm gọi là ASL (a storage location). Tùy theo yêu cầu của phương pháp lưu ảnh trên toàn bộ hệ thống mà ASL có thể là vùng nhớ tạm thời (violatile memory) hay vùng nhớ ổn định (stable storage). Cách đơn giản nhất để lấy thông tin