Tài liệu Thiết kế và phân tích giải thuật duy trì dữ liệu chung phân tán

ĐẠI HỌC CÔNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI ĐỖ HIỀN THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT DUY TRÌ DỮ LIỆU CHUNG PHÂN TÁN LUẬN VĂN THS CÔNG NGHỆ THÔNG TIN Người hướng dẫn TS :NGUYỄN ĐẠI THỌ Hà nội: 2007 MỤC LỤC LỜI CẢM ƠN .......................................................................................................................... 1 MỤC LỤC ................................................................................................................................ 2 CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT ............................................................................... 4 DANH SÁCH CÁC HÌNH VẼ ............................................................................................... 6 MỞ ĐẦU .................................................................................................................................. 7 CHƢƠNG 1. HỆ PHÂN TÁN ............................................................................................... 9 1.1. Khái niệm hệ phân tán....................................................................................... 9 1.2. Vai trò của hệ phân tán ...................................................................................... 9 1.3. Đặc trƣng của các hệ phân tán ......................................................................... 11 1.4. Mô hình hóa các hệ phân tán ........................................................................... 12 1.4.1. Mô hình chuyển thông báo ........................................................................ 13 1.4.2. Mô hình với bộ nhớ dùng chung ............................................................... 13 1.4.3. Mô hình xen kẽ ......................................................................................... 14 1.4.4. Thực hiện và những tính chất của thực hiện .............................................. 14 1.5. Đánh giá độ phức tạp ...................................................................................... 16 1.6. Khả năng kháng lỗi và tính tự ổn định ............................................................. 17 1.6.1. Khả năng kháng lỗi................................................................................... 17 1.6.2. Tính chất tự ổn định.................................................................................. 17 1.6.3. Vai trò của tự ổn định ............................................................................... 18 1.6.4. Đánh giá độ phức tạp ............................................................................... 19 CHƢƠNG 2. CÁC GIẢI THUẬT SƠ ĐẲNG ................................................................... 21 2.1. Giới thiệu ........................................................................................................ 21 2.2. Bài toán........................................................................................................... 23 2.3. Đánh giá độ phức tạp ...................................................................................... 24 2.4. Giải thuật Phát tỏa Đầy đủ .............................................................................. 25 2.5. Giải thuật Cập nhật Tăng trƣởng [4] ................................................................ 27 2 CHƢƠNG 3. GIẢI THUẬT CẬP NHẬT VỚI TRI THỨC BỘ PHẬN [3] ...................... 32 3.1. Tƣ tƣởng ......................................................................................................... 32 3.2. Giải thuật ........................................................................................................ 33 3.3. Tính đúng đắn và độ phức tạp ......................................................................... 37 3.4. Ví dụ một thực hiện ........................................................................................ 38 CHƢƠNG 4. GIẢI THUẬT AS CẢI TIẾN ........................................................................ 44 4.1. Đặt vấn đề ....................................................................................................... 45 4.2. Thực hiện cải tiến............................................................................................ 45 4.3. Tính đúng đắn và độ phức tạp ......................................................................... 49 4.4. Ví dụ một thực hiện ........................................................................................ 52 CHƢƠNG 5. GIẢI THUẬT DUY TRÌ DỮ LIỆU CHUNG PHÂN TÁN ÁP DỤNG TRONG THỰC TIỄN ........................................................................................................... 58 5.1. Hệ thống động với tôpô bất kỳ ........................................................................ 58 5.2. Dữ liệu chung phân tán ................................................................................... 59 5.3. Độ dài dữ liệu không cố định .......................................................................... 59 5.4. Khả năng kháng lỗi và tính tự ổn định ............................................................. 60 KẾT LUẬN ............................................................................................................................ 63 TÀI LIỆU THAM KHẢO ..................................................................................................... 64 3 CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT TT Tiếng Việt Tiếng Anh Ý nghĩa 1 Bộ xử lý Processor Một thực thể trong mạng 2 Cập nhật Tăng Incremental Cập nhật đƣợc thực hiện lần lƣợt trên trưởng Update từng bộ xử lý Cập nhật Tăng trưởng theo Phân đoạn Dữ Incremental Updates with Data segments Thực hiện nhiều Cập nhật Tăng trƣởng đồng thời, mỗi Cập nhật Tăng trƣởng cho một đoạn dữ liệu. Configuration Trạng thái toàn cục của hệ thống bao gồm trạng thái của các thực thể và trạng thái của các kênh truyền giữa các thực 3 liệu 4 Cấu hình thể 5 Cây bao trùm Spanning tree Cây bao gồm tất cả các nút của một đồ thị, và mỗi nút xuất hiện duy nhất một lần. 6 Đồ thị phụ thuộc Dependency graph Độ thị có hƣớng không chu trình có thêm các phụ thuộc hàm 7 Dẫn ống Khi nhận đƣợc thông báo từ bộ xử trƣớc Pipeline thì chuyển ngay thông báo này cho bộ xử lý liền sau. 8 Dữ liệu chung Common data Dữ liệu đƣợc nhìn nhận nhƣ nhau bởi mọi thực thể trong hệ thống 9 Hệ phân tán Distributed system Hệ thống bao gồm các thiết bị tính riêng rẽ có thể giao tiếp với nhau 10 Khứ lỗi Fault tolerance Khả năng hệ thống bỏ qua một số hữu 4 hạn lỗi để những bộ phận chƣa bị lỗi vẫn hoạt động bình thƣờng 11 Phát tỏa Gửi thông tin đến tất cả các bộ xử lý Broadcast trong thành phần liên thông 12 Phát tỏa Đầy đủ Full Broadcast Phát tỏa mọi thông tin có 13 Phát tỏa với Tri thức Bộ phận Broadcast with Partial Knowledge Phát tỏa chỉ những phần dữ liệu thay đổi với mục đích sửa lỗi tại các bộ xử lý nhận 14 Sai khác cục bộ Local Số bít trong dữ liệu riêng khác với dữ discrepancy liệu nguồn 15 Sai khác tổng Total discrepancy Tổng tất cả các sai khác cục bộ 16 Tiến trình Process Một chƣơng trình đang thực thi 17 Trạm Site Một thực thể trong mạng 18 Tự ổn định Self-stabilizing Tính chất của hệ thống có thể xuất phát từ trạng thái bất kỳ luôn thể hiện đƣợc hành vi hợp lệ mong muốn. 19 Khung nhìn View “Hình ảnh” mà một bộ xử lý nhận đƣợc từ một bộ xử lý khác 20 Nguồn Source Bộ xử lý nguồn 5 DANH SÁCH CÁC HÌNH VẼ Hình 1.1 Mô hình tổng quát hệ thống phân tán (12) Hình 1.2 Mô hình chuyển thông báo (13) Hình 1.3 Mô hình với bộ nhớ dùng chung (14) Hình 2.1 Ví dụ minh họa bài toán Duy trì dữ liệu chung trong hệ phân (24) tán. Trong ví dụ này, có n+1 = 5 bộ xử lý duy trì một khung nhìn với m = 4 mục. Nguồn là bộ xử lý 0. Các mục sai so với nguồn được gạch chân. Độ sai khác cục bộ là số mục gạch chân tại một bộ xử lý. Độ sai khác tổng là ∆ = 7 Hình 2.2 Một thực hiện của giải thuật Phát tỏa Đầy đủ (n = 4, m =4, (27) ∆ = 7) Hình 2.3 Sửa lỗi cho hai bộ xử lý đầu trong một thực hiện của giải thuật Cập nhật Tăng trưởng (n = 4, m =4, ∆ = 7) (28) Hình 3.1 Một trạng thái của hệ thống khi thực hiện giải thuật AS (33) Hình 3.2 Vùng quét của bộ xử lý Q (34) Hình 3.3 Hình chữ nhật của các tiến trình con của tiến trình Q (35) Hình 3.4 Hoạt động của một tiến trình (mũi tên biểu diễn thông báo sửa lỗi ) (36) Hình 3.5 Một thực hiện của giải thuật AS (vùng chữ nhật đầu tiên). (39) Hình 4.1 Giải thuật AS cải tiến (48) Hình 4.2 Một thực hiện của giải thuật AS cải tiến (vùng chữ nhật đầu tiên). (53) Hình 5 Khung chung cho các phiên bản tự ổn định của các giải thuật Cập nhật Tăng trưởng, giải thuật AS, và giải thuật AS cải tiến. (61) 6 MỞ ĐẦU Trong tính toán phân tán có rất nhiều công việc liên quan đến việc duy trì khung nhìn (view) đến các đối tƣợng chung tại các trạm (sites) khác nhau của hệ thống phân tán. Với đối tƣợng chung là tôpô của hệ thống ta có yêu cầu cập nhật tôpô, hay nếu đối tƣợng chung là một tài nguyên cụ thể đƣợc lƣu trữ trên một trạm nào đó ta có yêu cầu liệt kê danh sách tài nguyên trên mỗi trạm, hoặc một cơ sở dữ liệu tổng quát. Các đối tƣợng này bị tác động bởi những thay đổi, ví dụ liên kết giữa hai nút mạng đƣợc thêm mới hay mất đi làm thay đổi tôpô mạng, một tài nguyên đƣợc chiếm dụng rồi giải phóng, một bản ghi cơ sở dữ liệu đƣợc sửa đổi. Nhƣ vậy, vấn đề đặt ra ở đây là cần có một cơ chế hiệu quả cho việc cập nhật khung nhìn về đối tƣợng chung tại các trạm khác nhau. Mục tiêu của luận văn này là xem xét, đánh giá một số giải thuật cập nhật “khung nhìn” về đối tƣợng chung đó, đồng thời đƣa ra đề xuất cải tiến các giải thuật đã xem xét nếu có thể. Các giải thuật duy trì dữ liệu chung trong hệ phân tán, và đặc biệt phƣơng pháp Phát tỏa với Tri thức Bộ phận, đƣợc tìm hiểu trong luận văn này bao gồm Phát tỏa Đầy đủ, Cập nhật Tăng trưởng [4], giải thuật AS [3]. Từ các tìm hiểu về giải thuật trên, tác giả luận văn đã đƣa ra một đề xuất cải tiến giải thuật AS. Cải tiến này đƣợc thực hiện bằng cách cắt bỏ các thông báo dƣ thừa đƣợc sử dụng trong giải thuật AS. Kết quả cải tiến đƣợc tác giả luận văn đánh giá và chứng minh. Ngoài ra, trong luận văn này, tác giả đã quan tâm đến các khía cạnh thực tế khi áp dụng những giải thuật đƣợc xem xét hoặc đề xuất, trong đó khả năng kháng lỗi với tính tự ổn định [7] đƣợc đặc biệt chú ý. Với mỗi giải thuật đã đƣợc xem xét hoặc đề xuất, tác giả đã chỉ ra một phiên bản tự ổn định của nó. Luận văn đƣợc trình bày trong năm chƣơng với nội dung mỗi chƣơng nhƣ sau: Chương 1 giới thiệu hệ phân tán, các mô hình hệ phân tán, vai trò, đặc trƣng của các hệ phân tán, các khái niệm cơ bản về cấu hình, thực hiện và phƣơng pháp đánh giá 7 độ phức tạp của giải thuật phân tán [1], [8], [9]. Phần cuối chƣơng trình bày các vấn đề về khả năng kháng lỗi với tính chất tự ổn định [7]. Tiếp theo, Chương 2 trình bày bài toán duy trì dữ liệu chung trong hệ phân tán và các giải thuật sơ đẳng, bao gồm giải thuật Phát tỏa Đầy đủ và giải thuật Cập nhật Tăng trưởng [4]. Mô hình bài toán, tiêu chuẩn đánh giá độ phức tạp đƣợc trình bày. Với mỗi giải thuật, sau phần xem xét và trình bày giải thuật, tác giả đều đƣa ra một ví dụ minh họa thực hiện của giải thuật. Chương 3 trình bày giải thuật cập nhật với tri thức bộ phận, giải thuật AS [3]. Sau phần trình bày tƣ tƣởng và chi tiết giải thuật là phần chứng minh tính đúng đắn và đánh giá các độ phức tạp. Một ví dụ đƣợc tác giả đƣa ra để minh họa cho hoạt động của giải thuật AS. Trong Chương 4, tác giả đƣa ra một đề xuất cải tiến giải thuật AS bằng cách cắt bỏ các thông báo không cần thiết trong giải thuật AS. Hiệu quả tiết kiệm thời gian và thông báo của giải thuật AS cải tiến so sánh với giải thuật gốc đƣợc phát biểu và chứng minh. Giải thuật cũng đƣợc mô tả bằng mã hình thức.Cuối cùng là minh hoạ một thực hiện của giải thuật AS cải tiến. Chương 5 bàn về các thay đổi cần thực hiện để các giải thuật duy trì dữ liệu có thể thực thi đƣợc trong một số vấn đề hiện thực của hệ phân tán, đó là các vấn đề về Hệ thống với tôpô bất kỳ, Dữ liệu chung phân tán, Độ dài dữ liệu thay đổi, Khả năng kháng lỗi và tự ổn định. Chắc chắn, luận văn còn có những thiếu sót trong nội dung cũng nhƣ trong trình bày. Tác giả của luận văn rất mong nhận đƣợc sự đóng góp ý kiến của các thầy cô giáo và của các anh/chị học viên. 8 CHƯƠNG 1. HỆ PHÂN TÁN 1.1. Khái niệm hệ phân tán Có rất nhiều khái niệm khác nhau về hệ phân tán. Một cách tổng quan, hệ phân tán là tập hợp các thiết bị tính riêng rẽ có thể giao tiếp với nhau. Đây là một khái niệm hết sức tổng quát, bao trùm một phạm vi rộng các hệ thống máy tính ngày nay, từ các bộ chíp VLSI đến các bộ đa xử lý, các mạng cục bộ, và Internet. Nếu nhƣ hệ song song phối hợp nhiều bộ xử lý nhằm giải quyết một vấn đề cho trƣớc một cách nhanh nhất thì hệ phân tán bao gồm một tập các bộ xử lý có chƣơng trình làm việc riêng bán độc lập, vì những lý do gì đó, ví dụ chia sẻ tài nguyên, tăng tính sẵn sàng, khứ lỗi, các bộ xử lý cần phối hợp hành động với nhau. Ta có thể thấy các hệ phân tán ở khắp mọi nơi. Điển hình, các hệ phân tán đƣợc sử dụng để chia sẻ tài nguyên và chia sẻ dữ liệu. Các máy tính kết nối mạng với nhau có thể dùng chung máy in, máy quét, chia sẻ các tệp tài liệu, chƣơng trình… Tính toán ngang hàng là một kiểu thực hiện của hệ phân tán ngày càng trở nên phổ biến cho việc cung cấp các thiết bị và dịch vụ tính toán. Các hệ phân tán nhiều tham vọng hơn cho hiệu năng hoạt động cao bằng cách kết hợp giải các bài toán con một cách song song, đồng thời tăng tính sẵn sàng của hệ thống trong trƣờng hợp một số thiết bị gặp lỗi. 1.2. Vai trò của hệ phân tán Ngày nay hệ phân tán đang trở nên phổ biến vì những vai trò ứng dụng quan trọng của chúng. Trƣớc hết, phải kể đến đó là vai trò trao đổi thông tin. Các hệ phân tán cho khả năng chia sẻ thông tin rộng rãi và tức thời. Lấy ví dụ, thông tin từ hệ thống máy tính đặt tại Sở giao dịch chứng khoán TPHCM có thể đƣợc sử dụng bởi hệ thống máy tính đặt tại trụ sở của các công ty chứng khoán thành viên hay cũng có thể chia sẻ đến tận các nhà đầu tƣ. Các thông tin chứng khoán cũng luôn yêu cầu phải có tính chính xác cũng nhƣ tức thời rất cao, và hệ phân tán cũng có thể cung cấp những khả năng đảm bảo đƣợc điều này. Hệ phân tán cũng cho khả năng chia sẻ thông tin giữa các thiết bị hỗn tạp. Một máy tính có thể "nói chuyện" với các máy tính khác loại, các điện thoại cố định, di động, 9 các PDA, … Các hệ phân tán cho khả năng chia sẻ tài nguyên cả phần cứng lẫn phần mềm. Các máy tính kết nối mạng có thể dùng chung máy in, có thể chia sẻ các tệp dữ liệu, các tệp chƣơng trình. Thứ hai, bằng việc sao lặp, nhân bản, các hệ phân tán cho độ tin cậy cao. Nếu toàn bộ dữ liệu của một chi nhánh ngân hàng lƣu trong máy tính đột nhiên biến mất, ngƣời ta có thể khôi phục lại bằng cách sao phần nhân bản đã đƣợc lƣu tại một nơi khác trên hệ thống máy tính của ngân hàng. Thứ ba, thông qua song song hóa, các thực thể trong hệ phân tán có thể chia sẻ công việc, thực hiện đồng thời công việc chung, do vậy làm tăng hiệu suất hoạt động của hệ thống. Thứ tư, hệ phân tán làm đơn giản việc thiết kế các hệ thống phức tạp. Ngƣời ta thƣờng phân một hệ thống phức tạp thành các hệ thống con chuyên dụng và hợp tác với nhau. Làm nhƣ vậy, không những việc thiết kế đơn giản mà việc thực hiện cũng đơn giản. Các ƣu điểm của hệ phân tán so với máy tính cá nhân và so với hệ tập trung đƣợc chỉ ra ngắn gọn trong các bảng sau. Bảng 1.1. Ưu điểm của hệ phân tán so với máy tính cá nhân. Ưu điểm Mô tả Chia sẻ dữ liệu Cho phép nhiều người dung cùng truy cập vào một cơ sở dữ liệu chung Chia sẻ thiết bị Cho phép nhiều người dung dung chung các thiết bị đắt tiền như máy in màu, máy quét, ... Truyền thông Giúp truyền thông giữa người với người dễ dàng hơn, ví dụ bằng thư điện tử Mềm dẻo Phân công việc cho bất kỳ máy nào sẵn sàng 10 Bảng 1.2. Ưu điểm của hệ phân tán so với hệ tập trung. Ưu điểm Mô tả Hiệu năng Máy tính đa bộ xử lý có hiệu năng cao hơn máy tính mainframe Tốc độ Tổng năng lực tính toán của một hệ phân tán có thể cao hơn máy tính mainframe Phân tán Một số ứng dụng chạy trên nhiều máy tính xa nhau về mặt không gian Tính tin cậy Khi một máy gặp lỗi, toàn bộ hệ thống vẫn có thể làm việc Mở rộng Năng lực tính toán có thể được nâng lên nhờ them các bộ xử lý bình thường Mặc dù các hệ phân tán có những hạn chế nhƣ hiện tại có ít phần mềm cho chúng, đòi hỏi an ninh và tính bảo mật cao nhƣng những ƣu điểm lớn kể trên làm cho vai trò của các hệ phân tán ngày càng trở nên quan trọng. 1.3. Đặc trưng của các hệ phân tán Ba đặc trƣng, và cũng là những khó khăn điển hình khi thiết kế, của hệ phân tán là: không đồng bộ, thiếu thông tin toàn cục, và không có cơ chế phát hiện sự cố chính xác. Một hệ phân tán không có đồng hồ chung. Ta cũng không thể đồng bộ hóa đồng hồ của các bộ xử lý khác nhau vì không biết chắc độ trễ truyền thông. Để đạt đƣợc tính đồng bộ, ta không thể dùng đồng hồ vật lý mà phải vận dụng các khái niệm và giải thuật nhân quả. Tƣơng tự, một hệ phân tán không có bộ nhớ toàn cục chung. Các bộ xử lý không thể biết đƣợc trạng thái toàn cục của hệ thống. "Hiểu biết" của mỗi bộ xử lý chỉ có tính cục bộ. Do vậy, ngƣời thiết kế hệ phân tán, cụ thể là ngƣời xây dựng giải thuật phân tán phải xây dựng cơ chế đánh giá các tính toàn cục. Ngoài ra, chúng ta không có cơ chế phát hiện sự cố chính xác trong hệ phân tán vì không thể phân biệt đƣợc bộ xử lý chậm hay bị sự cố. Khi một bộ xử lý gặp sự cố, các bộ xử lý còn lại vẫn 11 phải tiếp tục làm việc để đạt đƣợc kết quả nhƣ mong muốn. Những đặc trƣng này thực sự là những khó khăn khi thiết kế các hệ phân tán. 1.4. Mô hình hóa các hệ phân tán Trong một hệ phân tán, mỗi thực thể (máy tính, bộ xử lý, tiến trình) chạy một chƣơng trình riêng bao gồm tập các lệnh. Khi thực hiện lệnh, thực thể thay đổi trạng thái cục bộ của nó. Ta có thể mô hình hóa sự thay đổi này bằng cách xem mỗi thực thể là một máy trạng thái. Một hệ phân tán đƣợc mô hình hóa bằng tập n máy trạng thái. Ký hiệu máy thứ i là Pi. Truyền thông giữa các thực thể có thể thực hiện bằng cách chuyển thông báo hay sử dụng bộ nhớ dùng chung. Truyền thông bằng cách ghi vào và đọc ra từ bộ nhớ dùng chung thƣờng hạn chế hệ thống với các thực thể gần nhau về mặt địa lý, ví nhƣ hệ thống đa bộ xử lý hay các máy tính đa nhiệm. Truyền thông theo cách chuyển thông báo không có giới hạn nhƣ vậy, có thể thực hiện trong cả hệ thống mà các thực thể rất xa nhau về mặt địa lý nhƣ các mạng máy tính. Hình 1.1. dƣới đây là minh họa mô hình tổng quát của các hệ thống phân tán. Hinh 1.1. Mô hình tổng quát hệ thống phân tán. Tùy theo phƣơng pháp truyền thông đƣợc sử dụng, ta có mô hình chuyển thông báo hay mô hình với bộ nhớ dùng chung. 12 1.4.1. Mô hình chuyển thông báo Trong mô hình chuyển thông báo, các láng giềng trao đổi thông tin cho nhau bằng cách gửi và nhận thông báo. Liên kết giữa các thực thể có thể đơn hoặc lƣỡng hƣớng. Liên kết đơn hƣớng từ thực thể Pi đến thực thể Pj đƣợc sử dụng để chuyển thông báo từ Pi đến Pj. Ta có thể trừu tƣợng hóa liên kết đơn hƣớng trên bằng hàng đợi FIFO q i, j chứa tất cả các thông báo đƣợc Pi gửi cho Pj nhƣng Pj chƣa nhận đƣợc. Mỗi khi P i gửi cho Pj một thông báo m, m đƣợc đƣa vào hàng đợi q i,j. Pj có thể nhận m khi nó trên đỉnh hàng đợi qi,j. Liên kết lƣỡng hƣớng giữa Pi và Pj có thể đƣợc mô hình hóa bằng hai hàng đợi: qi,j cho hƣớng từ Pi đến Pj và qj,i cho hƣớng từ Pj đến Pi. Trạng thái của hệ thống phân tán chuyển thông báo tại một thời điểm cụ thể đƣợc xác định bởi trạng thái của các bộ xử lý và nội dung của các hàng đợi chứa thông báo tại thời điểm đó. Cấu hình hệ thống (hay cấu hình) đƣợc dùng để chỉ trạng thái này. Một cấu hình đƣợc ký hiệu c = (s1, s2, …, sn, q1,2 q1,3, …, qi,j, …., qn, n-1), trong đó si, 1 ≤ i ≤ n , là trạng thái của P i và qi, j, i  j, là hàng đợi chứa thông báo Pi gửi cho Pj nhƣng Pj chƣa nhận đƣợc. Sau đây là minh họa mô hình chuyển thông báo. Hình 1.2. Mô hình chuyển thông báo. 1.4.2. Mô hình với bộ nhớ dùng chung Trong mô hình với bộ nhớ dùng chung, các bộ xử lý trao đổi thông tin cho nhau bằng cách sử dụng chung các ô nhớ. Các bộ xử lý có thể ghi vào một tập các ô nhớ và 13 đọc ra từ một tập các ô nhớ khác. Cấu hình hệ thống bao gồm trạng thái của các bộ xử lý và nội dung của các ô nhớ dùng chung. Một cấu hình của hệ thống gồm n bộ xử lý và m ô nhớ dùng chung đƣợc ký hiệu c = (s1, s2, …, sn,, r1, r2, …, rm), trong đó si, 1 ≤ i ≤ n, là trạng thái của Pi, rj, 1 ≤ j ≤ m, là nội dung của ô nhớ dùng chung thứ j. Hình 1.3. Mô hình với bộ nhớ dùng chung. 1.4.3. Mô hình xen kẽ Mô hình xen kẽ đƣợc sử dụng để lý giải hành vi của hệ thống phân tán. Trong mô hình này, tại mỗi thời điểm có duy nhất một bộ xử lý thực hiện một bƣớc tính (còn gọi là bƣớc nguyên tử). Mỗi bƣớc nguyên tử bao gồm một số phép tính bên trong bộ xử lý, hay còn gọi là sự kiện tính, và một phép giao, hay còn gọi là sự kiện giao - một phép gửi hoặc nhận trong hệ thống chuyển thông báo hay một phép ghi hoặc đọc trong hệ thống sử dụng bộ nhớ dùng chung. 1.4.4. Thực hiện và những tính chất của thực hiện Trong một hệ thống phân tán, các bộ xử lý có thể thực hiện các bƣớc tính một cách đồng thời; tuy nhiên, chúng ta giả thiết bƣớc tính này không ảnh hƣởng đến bƣớc tính khác. Điều này đúng trong mô hình chuyển thông báo vì một thông báo đƣợc gửi đi không thể nhận đƣợc bởi thao tác nhận xảy ra đồng thời với thao tác gửi. Trong mô hình bộ nhớ dùng chung, chúng ta giả thiết kiến trúc bộ nhớ dùng chung đảm bảo tuần tự hóa: có thể sắp xếp các thao tác đọc và ghi theo thứ tự hoàn toàn để kết quả của 14 thao tác đọc từ một ô nhớ là giá trị đƣợc ghi vào ô nhớ tại lần ghi cuối cùng vào ô nhớ trƣớc thao tác đọc. Trong các phần sau đây, chúng ta sử dụng thuật ngữ bước cho bƣớc nguyên tử và ký hiệu một bƣớc (cùng với định danh của bộ xử lý thực hiện bƣớc tính) là a. Cấu hình c2 đƣợc gọi là đến được trực tiếp từ cấu hình c1, ký hiệu là c1 a c2, nếu tồn tại một bƣớc tính a để từ cấu hình c1, thực hiện bƣớc a, ta đƣợc cấu hình c2. Cấu hình c’ đƣợc gọi là đến được từ cấu hình c, ký hiệu c  c’, nếu tồn tại các cấu hình c i, 0 ≤ i ≤ n, và các bƣớc aj, 0 ≤ j < n, để c = c0 a0 c1 a1 c2  … cn-1an-1 cn = c’. Bƣớc tính a’ đƣợc gọi là áp dụng được trên cấu hình c nếu tồn tại cấu hình c’ để c a' c’. Một thực hiện E = (c1, a1, c2, a2, …) là một dãy xen kẽ các cấu hình và bƣớc tính trong đó ci-1 ai-1 ci (i > 1); nói cách khác, cấu hình ci (i > 1) đến đƣợc trực tiếp từ cấu hình ci-1 bằng việc áp dụng bƣớc tính ai-1. Ví dụ, trong mô hình với bộ nhớ dùng chung, nếu tại bƣớc ai, bộ xử lý Pj ghi giá trị x vào ô nhớ dùng chung rk, thì chỉ hai thành phần có giá trị khác nhau trong ci và ci+1 là Pj và rk. Một thực hiện đƣợc gọi là thỏa đáng nếu trong thực hiện đó mọi bƣớc tính áp dụng đƣợc vô hạn lần đƣợc thực hiện vô hạn lần. Nói cách khác, nếu một bộ xử lý có một bƣớc để thực hiện thì bộ xử lý sẽ thực hiện bƣớc tính đó. Trong các hệ thống phân tán chuyển thông báo, một thông báo có thể bị mất trong khi thực hiện giải thuật. Các mã phát hiện lỗi đƣợc sử dụng để nhận biết và loại bỏ các thông báo bị ngắt, những thông báo này đƣợc xem là thông báo bị mất. Để mô hình hóa các hệ thống này, chúng ta mở rộng định nghĩa bƣớc tính để bao hàm sự kiện mất thông báo (sự kiện môi trƣờng) dạng lossi, j(m) – thông báo m đƣợc Pi gửi cho Pj nhƣng bị mất và Pj không nhận đƣợc. Sự kiện lossi, j(m) áp dụng đƣợc trên cấu hình ck nếu trong ck, qi,j chứa m. Kết quả áp dụng lossi, j(m) trên ck đƣợc cấu hình ck+1 trong đó m bị loại khỏi qi,j còn các thành phần khác không thay đổi so với trong ck. Khác với các sự kiện tính đƣợc thực hiện bởi các bộ xử lý, trong các thực hiện thỏa đáng, chúng ta không yêu cầu các sự kiện môi trƣờng áp dụng đƣợc trên vô hạn lần phải xảy ra vô hạn lần. Nói cách khác, ta không yêu cầu tính thỏa đáng phải áp dụng đối với các sự kiện môi trƣờng. 15 Một thực hiện thỏa đáng kéo dài vô hạn không có nghĩa là các chƣơng trình cục bộ không bao giờ kết thúc. Để mô hình hóa tính kết thúc của giải thuật, chúng ta định ra một số trạng thái kết thúc của các bộ xử lý. Đây là trạng thái của các bộ xử lý mà một khi đạt đƣợc, các bộ xử lý sẽ không bao giờ thay đổi, không gửi/nhận thông báo (đối với mô hình chuyển thông báo) hoặc không làm thay đổi nội dung các biến dùng chung (đối với mô hình với bộ nhớ dùng chung). Cấu hình trong đó tất cả các bộ xử lý không lỗi ở trạng thái kết thúc và không có thông báo treo (đã đƣợc gửi nhƣng chƣa đƣợc nhận) nào (với mô hình chuyển thông báo) đƣợc gọi là cấu hình kết thúc. Một thực hiện kết thúc khi nó đạt đến cấu hình kết thúc. Các hệ thống phân tán đƣợc mô tả ở trên thuộc lớp không đồng bộ. Trong thực tế, tồn tại một lớp các hệ phân tán đồng bộ. Các thành phần trong hệ phân tán đồng bộ thƣờng gần nhau về mặt địa lý và đƣợc điều khiển bởi một đồng hồ sung. Các bộ xử lý thực hiện các phép tính đồng bộ theo nhịp sung đồng hồ. Tuy nhiên, chúng ta không quan tâm đến cấu trúc vật lý của hệ thống mà chỉ quan tâm đến tính đồng bộ của nó. Vì tất cả các bộ xử lý thực hiện các phép tính đồng thời nên một thực hiện của hệ thống phân tán đồng bộ đơn giản đƣợc ký hiệu là E = (c1, c2, …) và hoàn toàn đƣợc xác định từ cấu hình ban đầu, c1. 1.5. Đánh giá độ phức tạp Rõ ràng, để xây dựng các hệ phân tán, chúng ta cần xây dựng các giải thuật phân tán. Thực hiện của giải thuật phân tán diễn ra phân tán trên nhiều bộ xử lý. Cũng nhƣ các giải thuật khác, giải thuật phân tán đƣợc đánh giá độ phức tạp trên hai khía cạnh: độ phức tạp tính toán và độ phức tạp bộ nhớ. Thoạt nhìn, việc đánh giá độ phức tạp tính toán dƣờng nhƣ trái ngƣợc với tính không đồng bộ của hệ thống phân tán. Theo định nghĩa về các hệ thống không đồng bộ, không có giới hạn trên về thời gian xử lý/truyền thông báo. Tuy nhiên, để có thể đánh giá và so sánh các giải thuật với nhau, ngƣời ta sử dụng số vòng không đồng bộ để đánh giá độ phức tạp của một thực hiện cụ thể. Vòng không đồng bộ (hay vòng) thứ nhất trong thực hiện E là tiền tố ngắn nhất E’ của E sao cho mỗi bộ xử lý thực hiện ít nhất một bƣớc trong E’. Gọi E’’ là hậu tố của E theo liền sau E’, E=E’E’’. Vòng thứ hai của E là vòng thứ nhất của E’’, vv… Số 16 vòng trong thực hiện của một giải thuật phân tán đƣợc dùng để đánh giá độ phức tạp thời gian của giải thuật. Một cách trực quan, định nghĩa vòng không đồng bộ bỏ qua tốc độ của các bộ xử lý bằng việc kéo dài vòng đủ dài để trong mỗi vòng, bộ xử lý có tốc độ chậm nhất cũng thực hiện đƣợc một bƣớc tính. Độ phức tạp thời gian của một hệ thống đồng bộ là số sung trong thực hiện (bằng số vòng). Độ phức tạp bộ nhớ của một giải thuật là tổng số bit nhớ (dùng chung và cục bộ) đƣợc sử dụng để cài đặt giải thuật. Độ phức tạp thông báo là tổng số thông báo (hoặc tổng kích thƣớc các thông báo) đƣợc gửi/nhận khi thực hiện giải thuật. 1.6. Khả năng kháng lỗi và tính tự ổn định 1.6.1. Khả năng kháng lỗi Khả năng kháng lỗi là một trong những đặc tính quan trọng của bất cứ hệ thống nào, không chỉ các hệ phân tán. Khả năng kháng lỗi của một hệ thống đƣợc thể hiện ở số lƣợng và số loại lỗi mà hệ thống có thể gặp phải nhƣng có thể khắc phục để hoạt động bình thƣờng trở lại sau khi gặp lỗi. Nhƣ vậy, một hệ thống thực sự tin cậy phải có khả năng kháng lỗi tốt. Có nhiều phƣơng pháp kháng lỗi, trong đó phƣơng pháp lý tƣởng nhất là làm cho hệ thống có tính tự ổn định để sau khi hệ thống gặp bao nhiêu, bất kỳ loại lỗi gì cũng có thể tự trở lại trạng thái bình thƣờng và tiếp tục hoạt động tốt. 1.6.2. Tính chất tự ổn định Khái niệm tự ổn định đƣợc Dijkstra đƣa ra đầu tiên năm 1973 trong bài báo nổi tiếng “Self-stabilizing systems in spite of distributed control” [7]. Tự ổn định, sau đó, đƣợc nghiên cứu nhƣ một chuyên ngành thuộc tính toán phân tán. Một hệ tự ổn định có thể xuất phát từ một cấu hình bất kỳ, luôn đảm bảo sẽ thể hiện được hành vi “hợp lệ” mong muốn. Nói cách khác, với thực hiện bất kỳ, sau hữu hạn lần biến đổi cấu hình, ta có chuỗi cấu hình hợp lệ. 17 Ta định nghĩa hành vi hợp lệ mong muốn bằng tập các thực hiện hợp lệ đƣợc ký hiệu là LE. Một tập các thực hiện hợp lệ đƣợc xác định cho một hệ thống cụ thể và một bài toán cụ thể. Mọi thực hiện của hệ thống tự ổn định có hậu tố xuất hiện trong LE. Ví dụ, với bài toán loại trừ lẫn nhau, thực hiện hợp lệ là thực hiện trong đó tại mọi cấu hình, có nhiều nhất một bộ xử lý nằm trong đoạn găng, và trong đó mọi bộ xử lý đƣợc vào đoạn găng vô hạn lần. Một cấu hình c đƣợc gọi là an toàn đối với tập thực hiện hợp lệ LE và một giải thuật A nếu mọi thực hiện thỏa đáng của giải thuật A xuất phát từ c đều thuộc LE. Một giải thuật đƣợc gọi là tự ổn định đối với tập thực hiện hợp lệ LE nếu mọi thực hiện thỏa đáng của giải thuật đều đạt đến một cấu hình an toàn đối với giải thuật và LE. 1.6.3. Vai trò của tự ổn định Một hệ thống tự ổn định có thể bỏ qua mọi lỗi. Ta tƣởng tƣợng, lỗi xuất hiện đẩy hệ thống về một trạng thái nào đó. Nhờ khả năng tự ổn định, sau lần xuất hiện lỗi cuối cùng, và sau hữu hạn bƣớc chuyển trạng thái nữa, hệ thống trở lại trạng thái hợp lệ và hoạt động bình thƣờng. Tính tự ổn định đặc biệt hữu ích đối với các hệ thống động (các bộ xử lý và liên kết có thể đƣợc thêm mới, mất chức năng, đƣợc khôi phục lại). Tự ổn định cho chúng ta một cách giải quyết triệt để trong khắc phục lỗi. Một hệ thống không thể tránh đƣợc lỗi. Lỗi có thể do phần cứng, phần mềm, do ngƣời sử dụng thiết lập hay nhập liệu sai, … Cách khắc phục lỗi truyền thống là liệt kê ra các lỗi, đồng thời, đƣa ra cách giải quyết cho mỗi lỗi. Tuy nhiên, cách này chỉ giải quyết đƣợc một số lỗi thƣờng gặp. Chúng ta không thể kể ra tất cả các lỗi tiềm tàng, do vậy không thể đảm bảo hệ thống không còn lỗi. Một khi, hệ thống gặp lỗi lạ, tức là lỗi không có trong danh sách lỗi, nó không biết giải quyết nhƣ thế nào và mãi mãi trong trạng thái nhƣ vậy. Một cách giải quyết khác là khứ lỗi [AS04, Lyn97]. Tuy nhiên, cách này cũng chỉ khắc phục đƣợc hữu hạn lỗi. Khi số lỗi vƣợt quá hệ số kháng lỗi, hệ thống rơi vào trạng thái lỗi và không thể hoạt động bình thƣờng trừ khi nó đƣợc khởi động lại. 18 1.6.4. Đánh giá độ phức tạp Cũng nhƣ các giải thuật phân tán khác, giải thuật tự ổn định đƣợc đánh giá độ phức tạp thời gian dựa trên số vòng không đồng bộ. Số vòng trong thực hiện của một giải thuật tự ổn định đƣợc dùng để đánh giá độ phức tạp thời gian của giải thuật. Giải thuật tự ổn định không bao giờ kết thúc, và các bộ xử lý phải tiếp tục liên lạc với các láng giềng của chúng. Trong mô hình với bộ nhớ dùng chung, các bộ xử lý phải tiếp tục đọc các ô nhớ dùng chung của các láng giềng. Trong mô hình chuyển thông báo, các bộ xử lý phải tiếp tục gửi và nhận thông báo. Tính chất không kết thúc của giải thuật tự ổn định đƣợc giải thích nhƣ sau: giả sử các bộ xử lý kết thúc, P i kết thúc ở trạng thái si. Theo tính chất tự ổn định của giải thuật, hệ thống phải đạt đến cấu hình an toàn xuất phát từ bất kỳ cấu hình nào. Khi hệ thống đƣợc bắt đầu từ cấu hình c tại đó bộ xử lý Pi có trạng thái si, không có bộ xử lý nào thực hiện bất kỳ bƣớc nào, nhƣ vậy c là một cấu hình an toàn. Do vậy, nhiệm vụ của giải thuật đã đạt đƣợc khi mỗi bộ xử lý Pi chỉ có duy nhất một trạng thái si. Rõ ràng, nhiệm vụ này không yêu cầu bất kỳ liên lạc nào giữa các bộ xử lý và giải thuật đƣợc sử dụng không phải là một giải thuật phân tán. Tính không kết thúc của giải thuật dễ ràng đƣợc nhận ra từ mã của giải thuật: mã của giải thuật thƣờng bao gồm một vòng lặp vô hạn chứa các thao tác liên lạc với các láng giềng. Ví dụ, trong mô hình với bộ nhớ dùng chung, mã của giải thuật cho một bộ xử lý Pi thƣờng bắt đầu với các thao tác đọc các ô nhớ dùng chung của láng giềng, theo đó là các thao tác ghi vào các ô nhớ dùng chung cục bộ. Số bƣớc cần thiết để thực hiện một lần lặp của vòng lặp vô hạn trong ví dụ này là O(∆), trong đó ∆ là cận trên bậc (số láng giềng) của Pi. Chúng ta mở rộng khái niệm vòng không đồng bộ để có khái niệm chu kỳ không đồng bộ (hay là chu kỳ). Chu kỳ thứ nhất của thực hiện E là tiền tố ngắn nhất E’ của E sao cho mỗi bộ xử lý hoàn thành ít nhất một lần lặp của vòng lặp vô hạn trong E’. Gọi E’’ là hậu tố của E liền tiếp sau E’, E = E’E’’. Chu kỳ thứ hai của E là chu kỳ thứ nhất của E’’, vv… 19 Lƣu ý rằng nếu mỗi lần lặp của vòng lặp vô hạn bao gồm các thao tác đọc ô nhớ dùng chung của láng giềng, tính toán cục bộ, và ghi vào các ô nhớ dùng chung cục bộ, thì mỗi chu kỳ kéo dài O(∆) vòng. Độ phức tạp thời gian của một hệ thống đồng bộ là số sung trong thực hiện (bằng số vòng). Độ phức tạp bộ nhớ của một giải thuật là tổng số bit nhớ (dùng chung và cục bộ) đƣợc sử dụng để cài đặt giải thuật. Độ phức tạp thông báo là tổng số thông báo (hoặc tổng kích thƣớc các thông báo) đƣợc gửi/nhận khi thực hiện giải thuật. 20