Chương 1 : Tổng quan về hệ phân tán. Định nghĩa

3. 
   Các giao thức bệnh dịch (epidemic protocol).
   

Ý tưởng cơ bản của thuật toán bệnh dịch là:

• 
  Giả sử rằng không xảy ra xung đột giữa các thao tác ghi – ghi.
  
• 
  Các thao tác cập nhật ban đầu được thực hiện chỉ trên một hay một vài bản sao (càng ít càng tốt).
  
• 
  Một bản sao chỉ gửi các cập nhật của nó tới một số hữu hạn các hàng xóm.
  
• 
  Việc lan truyền các cập nhật xảy ra chậm chạp và không phải ngay lập tức.
  
• 
  Cuối cùng thì mỗi cập nhật cũng đến được từng bản sao.
  

Một trong những mô hình lan truyền cập nhật được gọi là: anti entropy. Trong mô hình này, mỗi bản sao cứ định kì lại chọn ngẫu nhiên một bản sao khác và trao đổi những trạng thái khác nhau của mình, sau một thời gian thì cả 2 phía sẽ có những trạng thái giống hệt nhau.

Một mô hình khác là gossiping. Trong mô hình này một bản sao đã được cập nhật sẽ “kể” cho một số bản sao khác về những cập nhật của mình vì thế sẽ làm cho những bản sao đó bị nhiễm những cập nhật của mình.

5. 
   Các giao thức nhất quán.
   

Với giao thức này, tất cả các thao tác ghi được thực hiện chỉ trên một server từ xa. Giao thức này thường được kết hợp với các hệ thống chủ khách truyền thống.

Một dạng giao thức ghi từ xa là giao thức Primary-Backup.

Nhược điểm của giao thức này là vấn đề hiệu năng. Tất cả các thao tác ghi trong giao thức đều chiếm khá nhiều thời gian, đặc biệt là khi có giao thêm giao thức ghi theo khối được sử dụng.

Ưu điểm của giao thức này là

• 
  Sử dụng giao thức ghi không theo khối để xử lý các cập nhật.
  
• 
  Tất cả các thao tác ghi có thể được gửi đến các bản sao dự phòng theo cùng một thứ tự, điều này tạo điều kiện thuận lợi khi thực thi mô hình nhất quán tuần tự.
  

Trong giao thức này một bản sao của mục dữ liệu được duy trì. Khi có yêu cầu thao tác ghi, mục dữ liệu được nhân bản từ server ở xa chuyển đến server cục bộ. Việc này được gọi là tiếp cận theo kiểu di trú hoàn toàn.

Một vấn đề được đặt ra cho các tiến trình sử dụng giao thức này để đọc hoặc ghi lên các mục dữ liệu là: thời gian để thật sự định vị được một mục dữ liệu có thể còn lớn hơn cả thời gian tiến trình sử dụng nó.

Một dạng của giao thức ghi cục bộ là là giao thức Primary-backup. Trong giao thức này bản chính được di trú đến tiến trình đang muốn thực hiện việc cập nhật, rồi sau đó bản dự phòng sẽ được cập nhật.

Trong các giao thức này, thao tác ghi có thể được tiến hành tại bất kì bản sao nào.

Ví dụ:

Một tiến trình đặc biệt sẽ mang các thao tác cập nhật tới từng bản sao. Một tem thời gian Lamport có thể được sử dụng để lấy các thao tác về, tuy nhiên phương pháp này không được linh hoạt cho các hệ phân tán.

Trong giao thức này, các thao tác ghi được truyền đến tất cả các bản sao, trong khi các thao tác đọc được thực hiện cục bộ. Giao thức ghi có thể được truyền sử dụng giao tiếp point-to-point hay multicast. Ưu điểm của giao thức này là tất cả các bản sao đều nhận được các thao tác cùng lúc và theo cùng một trật tự, và nó cũng không cần đánh dấu một bản chính hay phải gửi tất cả các thao tác tới một server.

Tuy nhiên giao thức này lại đòi hỏi phải truyền theo kiểu multicast động hoặc phải có một bộ sắp xếp dãy tập trung mà cả 2 phương pháp này đều khó có thể tiếp cận một cách linh hoạt.

Trong giao thức này có một vấn đề cần quan tâm là “triệu gọi bản sao”. Để tránh cho một bản sao bị gọi quán nhiều lần, một bộ điều phối được gắn ở mỗi bên (client và server), điều này đảm bảo cho việc chỉ có một lời gọi và một lời đáp được gửi đi.

Với giao thức này, các thao tác ghi được thực hiện trên một tập nhỏ nhất các bản sao. Khi thực hiện một thao tác đọc, người dùng cũng phải liên hệ với một tập các bản sao để tìm ra phiên bản mới nhất của dữ liệu.

Trong giao thức này tất cả các mục dữ liệu được kết hợp với một số phiên bản (version number). Mỗi lần một mục bị sửa đổi thì số phiên bản của nó cũng được tăng lên.

Giao thức này định nghĩa ra số đại biểu đọc và số đại biểu ghi, hai đại biểu này sẽ xác định số bản sao phải được liên hệ trước khi thực hiện thao tác đọc và ghi. Số đại biểu đọc phải lớn hơn ½ tổng số bản sao, vì thế tổng của số đại biểu đọc và ghi phải lớn hơn tổng số bản sao. Bằng cách này, một người muốn thực hiện một thao tác đọc thì phải đảm bảo việc liên hệ với ít nhất một bản sao có chứa phiên bản mới nhất của mục dữ liệu. Việc lựa chọn số lượng đại biểu dựa vào tỉ lệ giữa thao tác đọc và ghi cùng với cost (bandwidth…) khi thực hiện phương pháp giao tiếp giữa các nhóm.

Cache là một dạng đặc biệt của nhân bản, nó được điều khiển bởi client thay vì được điều khiển bởi server. Có nhiều giải pháp cho việc cache dữ liệu.

Với chiến lược phát hiện sự cố kết, là chiến lược để xác định khi nào thì sự không nhất quán thật sự bị phát hiện và từ đó loại bỏ những dữ liệu gây ra sự không nhất quán, thì có 2 giải pháp khác nhau.

• 
  Với giải pháp tĩnh, tại thời điểm biên dịch chương trình thì những chỉ thị phụ sẽ được thêm vào để phát hiện những dữ liệu không nhất quán.
  
• 
  Với giải pháp động thì tại thời điểm chạy chương trình thì có những đoạn mã để kiểm tra tính không nhất quán của dữ liệu cache với dữ liệu của server.
  

• 
  Để cho server gửi đi một thông điệp về sự không hợp lệ mỗi khi dữ liệu bị thay đổi.
  
• 
  Cập nhật các kĩ thuật lan truyền.
  

• 
  Với cache chỉ đọc ra (Read-only Cache) thì các cập nhật được thực hiện bởi server (bằng giao thức đẩy) hoặc bởi client (bằng giao thức kéo mỗi khi client nhận thấy dữ liệu cache đã cũ).
  
• 
  Với cache ghi thẳng (Write-Through Cache) thì client sẽ thay đổi nội dung của cache, sau đó sẽ gửi các cập nhật đến cho server.
  
• 
  Với cache ghi lại (Write-Back Cache) thì client trì hoãn sự lan truyền các cập nhật, cho phép nhiều cập nhật được tạo ra cục bộ sau đó gửi những cập nhật mới nhất cho server (việc này có khả năng ảnh hưởng mạnh đến hiệu năng).
  

1. 
   Chịu lỗi và một số khái niệm liên quan
   
   1. 
      Một số khái niệm cơ bản.
      

1. 
   Các khái niệm.
   

Tính chịu lỗi còn có liên quan tới khái niệm điều khiển lỗi (Fault control). Điều khiển lỗi bao gồm ngăn ngừa lỗi, loại bỏ lỗi và dự báo lỗi với mục tiêu xây dựng thành công khả năng chịu lỗi cho hệ thống.

2. 
   Phân loại lỗi.
   

Cách khắc phục: sử dụng bộ sửa lỗi cho hệ thống (fault doctor) để khắc phục lỗi.

2. 
   Các mô hình lỗi.
   

Lỗi khi nhận thông điệp gửi tới: gặp lỗi này, server không nhận được yêu cầu ngay cả từ client gần nó nhất và mặc dù kết nối giữa server với client đã được thiết lập. Lỗi khi nhận thông điệp chỉ làm cho server không nhận biết được các thông điệp gửi tới nó mà không hề ảnh hưởng đến trạng thái của server.

Lỗi khi gửi thông điệp: server vẫn nhận được các yêu cầu, vẫn hoàn thành yêu cầu đó nhưng vì một lý do nào đó lại không thể gửi kết quả tới máy đã yêu cầu. Một trong những lý do thường gặp là do bộ nhớ đệm gửi đầy. Trong trường hợp gặp lỗi này, server cần chuẩn bị tình huống clien sẽ gửi lại yêu cầu đã gửi đó .

Lỗi thời gian (timing failure): là lỗi xảy ra khi server phản ứng lại quá chậm, sau cả thời gian cho phép. Trong một hệ thống luôn có các ràng buộc về mặt thời gian. Nếu bên gửi gửi đến bên nhận nhanh quá, bộ nhớ đệm của bên nhận không đủ để chứa thì sẽ gây ra lỗi. Tương tự, server phản ứng lại chậm quá, vượt quá khoảng timeout quy định sẵn cũng sẽ gây ra lỗi, ảnh hưởng đến hiệu năng chung của hệ thống.

Lỗi đáp ứng (Response failure): là lỗi khi server trả lời không đúng. Đây là một kiểu lỗi rất ngiêm trọng và được phân chia thành hai loại:

Lỗi về mặt giá trị: là lỗi khi server trả lời lại yêu cầu của client với giá trị không chính xác. Ví dụ khi sử dụng các máy tìm kiếm, kết quả trả về không hề liên quan gì tới yêu cầu của người sử dụng.

Lỗi về chuyển trạng thái: là lỗi khi server hoạt động trệch hướng khỏi luồng điều khiển. Có nghĩa là server trả lời các yêu cầu được gửi tới một cách không theo như mong đợi.

Lỗi bất kì (Arbitrary failure): một server có thể tạo ra một lỗi bất kì ở bất kì thời gian nào. Đây là loại lỗi nguy hiểm nhất. Có thể có hai khả năng xảy ra:

Thứ nhất: một server tạo ra một kết quả sai mà không thể phát hiện ra được.

Thứ hai: server bị lỗi có liên kết với các server khác tạo ra một kết quả sai.

Ta có thể xét một vào lỗi bất kì hay gặp sau : lỗi fail-stop, lỗi fail-silent và lỗi fail-safe. Với fail-stop, server bị treo, ngừng hoạt động và có thông báo tới các tiến trình khác. Với fail-silent, server đột ngột hoạt động chậm lại vì thế làm cho các tiến trình không thể kết thúc được, ảnh hưởng đến hiệu năng của hệ thống. Lỗi fail-safe là lỗi mà khi server tạo ra kết quả ngẫu nhiên nhưng các tiến trình nhận dạng các kết quả này là không có giá trị.

2. 
   Các phương pháp che giấu lỗi.
   

1. 
   Che giấu lỗi bằng dư thừa.
   

1. 
   Khôi phục tiến trình.
   

1. 
   Các vấn đề khi thiết kế.
   

Số lượng các nhóm là không cố định: có thể tạo thêm hay hủy bỏ một nhóm.

Số lượng các tiến trình trong cùng một nhóm là không cố định: một tiến trình có thể gia nhập hay rời khỏi nhóm.

Một tiến trình có thể là thành viên của nhiều nhóm trong cùng thời điểm.

• 
  Tất cả các tiến trình trong nhóm là ngang hàng nhau.
  
• 
  Khi thực hiện một công việc nào đó sẽ phải có một quá trình bầu cử (vote) để xác định xem tiến trình nào phù hợp để thực hiện công việc đó.
  
• 
  Ưu điểm: khi một tiến trình bị lỗi thì chỉ làm cho kích thước của nhóm giảm đi chứ không ảnh hưởng đến hoạt động của cả nhóm.
  
• 
  Nhược điểm: do phải có quá trình bầu cử nên tốn thời gian (delay &overhead).
  

Hình 46. Nhóm ngang hàng.

• 
  Trong mỗi nhóm sẽ có một tiến trình giữ vai trò quản lý gọi là coordinator, còn các tiến trình khác đóng vai trò thực hiện (worker). Các tiến trình thực hiện chịu sự điều khiển của coordinator.
  
• 
  Khi có yêu cầu gửi đến nhóm, yêu cầu này sẽ được gửi tới coordinator. Coordinator sẽ quyết định xem tiến trình nào trong nhóm đảm nhiệm công việc đó một cách phù hợp nhất và chuyển yêu cầu nhận được đến tiến trình đó.
  
• 
  Ưu điểm: không bị trễ như kiến trúc ngang hàng.
  
• 
  Nhược điểm: khi coordinator gặp sự cố thì toàn bộ hoạt động của nhóm sẽ bị dừng lại.
  

Hình 47. Nhóm ngang hàng

Server này chứa tất cả các thông tin về các nhóm và các thành viên của từng nhóm.

Ưu điểm: hiệu quả, dễ sử dụng

Nhược điểm: nếu server bị lỗi thì không thể quản lý được toàn bộ hệ thống và các nhóm có thể phải xây dựng lại từ đầu các công việc mình đã thực hiện.

Khi tiến trình muốn gia nhập hay rời khỏi nhóm thì nó phải gửi bản tin thông báo tới tất cả các tiến trình khác.

Khi một tiến trình gia nhập nhóm nó sẽ nhận tất cả các bản tin từ nhóm đó.

Khi một tiến trình rời khỏi nhóm thì nó sẽ không được nhận bất kì bản tin nào từ nhóm đó nữa và không một thành viên nào của nhóm cũ nhận được các bản tin từ nó

2. 
   Che giấu lỗi và nhân bản.
   

3. 
   Che giấu lỗi trong truyền thông client/server tin cậy.
   

Trong hệ phân tán, truyền thông điểm – điểm tin cậy được thiết lập bằng cách sử dụng các giao thức truyền tin cậy như TCP. TCP che giấu được lỗi bỏ sót bằng cách dùng cơ chế thông báo ACK/NACK và việc thực hiện truyền lại. TCP không che giấu được lỗi sụp đổ. Khi xảy ra lỗi sụp đổ thì kết nối TCP sẽ bị hủy. Chỉ có một cách để che giấu lỗi sụp đổ là hệ thống phải có khả năng tự động tạo một kết nối mới.

Với hệ thống RPC, năm lớp lỗi có thể xảy ra là:

• 
  Client không thể định vị được server: Nguyên nhân gây lỗi là do server và client dùng các phiên bản khác nhau hoặc do chính server bị lỗi. Khắc phục bằng cách sử dụng các ngoại lệ (exception) để bắt lỗi như ở ngôn ngữ java và điều khiển tín hiệu (signal handle) như ở ngôn ngữ C. Hạn chế của phương pháp này là không phải ngôn ngữ nào cũng hỗ trợ ngoại lệ hay điều khiển tín hiệu. Nếu tự viết một ngoại lệ hay điều khiển tín hiệu thì sẽ phá hủy tính trong suốt.
  
• 
  Bị mất bản tin yêu cầu từ client gửi đến server: Đây là loại lỗi dễ xử lý nhất: hệ điều hành hay client stub kích hoạt một bộ đếm thời gian (timer) khi gửi đi một yêu cầu. Khi timer đã trở về giá trị 0 mà không nhận được bản tin phản hồi từ server thì nó sẽ gửi lại yêu cầu đó. Nếu bên client nhận thấy có quá nhiều yêu cầu phải gửi lại thì nó sẽ xác nhận rằng server không hoạt động và sẽ quay lại thành kiểu lỗi “không định vị được server”
  
• 
  Server bị lỗi ngay sau khi nhận được yêu cầu từ client: Lúc này lại phân chia thành hai loại:
  

Loại 2: Vừa nhận được yêu cầu từ client server đã bị lỗi ngay. Phương pháp khắc phục: client chỉ cần truyền lại yêu cầu cho. Vấn đề đặt ra lúc này là client không thể nói cho server biết yêu cầu nào là yêu cầu được gửi lại.

Khi gặp lỗi kiểu này, ở phía máy server sẽ thực hiện theo 3 kĩ thuật sau:

Còn ở client thì có thể thực hiện theo 4 chiến lược sau:

• 
  Mất bản tin phản hồi từ server gửi trả về client: Phương pháp khắc phục: thiết kế các yêu cầu có đặc tính không thay đổi giá trị (idempotent). Client đánh số thứ tự cho các yêu cầu, server sẽ nhận ra được đâu là yêu cầu đã được gửi lại nhờ các số tứ tự này. Do đó server sẽ không thực hiện lặp lại các yêu cầu. Tuy nhiên server vẫn phải gửi trả về bản tin thông báo yêu cầu nào bị thất lạc. Hoặc ta có thể sử dụng một bit ở phần header của yêu cầu để phân biệt yêu cầu nào là yêu cầu đã được gửi lại.
  
• 
  Client bị lỗi ngay sau khi gửi yêu cầu tới server: Client gửi yêu cầu tới server rồi bị lỗi trước khi nhận được trả lới từ server gửi về. Công việc mà server thực hiện nhưng không có đích nào đợi để nhận được gọi là một “orphan”. Như thế sẽ gây lãng phí chu kì CPU.
  

3. 
   
   Каталог: nguoidung
   nguoidung -> CHƯƠng 1 TỔng quan về KỸ thuật truyền số liệU
   nguoidung -> CÂU 1: Mạng máy tính là gì? A./ Các máy tính trao đổi thông tin với nhau tuân theo tập giao thức. B./ Các máy tính kết nối với nhau bằng đường truyền vật lý. C./ Các máy tính kết nối với nhau chia sẻ nguồn thông tin chung
   nguoidung -> TRƯỜng tcn thá[ MƯỜi khoa công nghệ thông tin
   nguoidung -> Tin hoc văn phòng
   nguoidung -> Virus máy tính có thể không phá hoại gì mà chỉ nhân bản. Virus
   nguoidung -> BÀi thực hành môn lập trình mạng gv trưƠng vĩnh hảo I. Mục đích
   nguoidung -> CÁc phưƠng pháp xuất nhập winsock I. Cài đặt Winsock
   nguoidung -> 4. Phần mềm Explorer – của HĐh windows xp
   nguoidung -> Tr­êng cao ®¼ng nghÒ ®ång th¸p Khoa c ng nghÖ th ng tin
   nguoidung -> MÔn học công nghệ MẠng không dâY
   
   
   
   tải về 1.6 Mb.
   
   Chia sẻ với bạn bè của bạn: