Tài liệu Hệ thống file phân tán: ... Ebook Hệ thống file phân tán
58 trang |
Chia sẻ: huyen82 | Lượt xem: 3954 | Lượt tải: 3
Tóm tắt tài liệu Hệ thống file phân tán, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Phần 1: Các nguyên lý của hệ phân tán
Chương 1 : Giới thiệu chung
Hệ thống máy tính đang ở trong một cuộc cách mạng lớn. Từ năm 1945 khi mà kỉ nguyên của máy tính hiện đại ra đời cho tới tận những năm 1985, những chiếc máy tính vẫn rất cồng kềnh và đắt. Tuy nhiên đến giữa những năm 1980 sự phát triển của công nghệ đã thay đổi hoàn toàn bộ mặt của kỉ nguyên máy tính, sự phát minh ra những bộ vi xử lý và mạng máy tính tốc độ cao. Chúng cho phép hàng trăm nghìn máy tính có thể kết nối với nhau và cùng nhau chia xẻ thông tin .
Kết quả của những công nghệ đó là ngày nay một cách dễ dàng chúng ta có thể kết nối máy tính trong một mạng tốc độ cao. Và chúng được gọi là mạng máy tính hay còn gọi là hệ phân tán .Có rất nhiều định nghĩa về hệ phân tán
Định nghĩa 1: Hệ phân tán là tập hợp các máy tính tự trị được kết nối với nhau bởi một mạng máy tính và được cài đặt phần mềm hệ phân tán.
Định nghĩa 2: Hệ phân tán là một hệ thống có chức năng và dữ liệu phân tán trên các trạm (máy tính) được kết nối với nhau bởi một mạng máy tính.
Định nghĩa 3: Hệ phân tán là một tập các máy tính độc lập giao tiếp với người dùng như một hệ thống thống nhất, toàn vẹn.
Như vậy, có thể nói : Hệ phân tán = mạng máy tính + phần mềm hệ phân tán
Mục đích của hệ phân tán kết nối người sử dụng với tài nguyên trong hệ thống, có tính trong suốt, tính mở và tính co giãn nghĩa là thích nghi với sự thay đổi quy mô của hệ thống.một hệ thống được thiết kế là một hệ thống phân tán có các tính chất: chịu lỗi, xuyên dụng, mở rộng được, mở.Chính vì thế hệ phân tán phải thỏa mãn các nguyên lý trong thiết kế. Khi xây dựng bất kỳ một hệ phân tán nào cúng phải dựa trên các nguyên lý đó. Đó là các nguyên lý về truyền thông (communication), tiến trình (processes), naming, đồng bộ hóa (synchronization), nhất quán và nhân bản (consistency and replication), chịu lỗi (foult tolerance) và bảo mật (security)
Chương 2: Comunication
Comunication đa tiến trình là trái tim của tất cả các hệ phân tán, đó là cách mà các tiến trình trong các máy khác nhau có thể trao đổi thông tin.Comunication trong một hệ thống phân tán luôn dựa trên việc truyền gửi các thông điệp ở các tầng thấp ở trong mạng.
Trong phần này chúng ta sẽ thảo luận về các giao thức trên các tầng, và bốn mô hình communication hay dùng nhất trong thực tế: RPC – Remote Procedure Protocol, Remote Object Invocation, Message Oriented Communication, và luồng – stream.
2.1 Giao thức trên các tầng
Mô hình OSI (Open Systems Interconnection Reference Model, viết ngắn là OSI Model hoặc OSI Reference Model) - tạm dịch là Mô hình tham chiếu kết nối các hệ mở- là một thiết kế dựa vào nguyên lý tầng cấp, lý giải một cách trừu tượng kỹ thuật kết nối truyền thông giữa các máy vi tính và thiết kế giao thức mạng giữa chúng. Mô hình này được phát triển thành một phần trong kế hoạch kết nối các hệ mở do ISO và IUT-T khởi xướng. Nó còn được gọi là mô hình bảy tầng của OSI. Mô hình OSI 7 tầng trong đó mỗi tầng có một giao thức riêng và hoạt động độc lập, trong suốt so với các tầng khác. Điều này được thực hiện thông qua việc sử dụng phần header của các message. Khi một tầng gửi một thông điệp, nó sẽ thực hiện việc gắn thêm phần header của tầng đó, tùy theo giao thức sử dụng, rồi chuyển xuống tầng thấp hớn. Khi tầng đó nhận được thông điệp, nó sẽ thực hiện phân tích vùng header đã được gắn bởi tầng tương ứng phía gửi, đọc thông điệp và gửi cho tầng ở trên. Các hệ thống phân tán thường sử dụng tầng transport – tầng giao vận, để thực hiện việc communication. Nó là tầng có thể cung cấp những thông tin phù hợp và đủ để các ứng dụng có thể sử dụng một cách tốt nhất, hơn nữa các giao thức ở tầng này có thể hoạt động trên nhiều mạng khác nhau.
2.1.1 Các giao thức ở tầng thấp
Tầng vật lý (physical), tầng liên kết dữ liệu (data link), tầng mạng (network) là 3 tầng thấp nhất giao thức OSI, chúng cùng nhau thực thi các chức năng cơ bản của một mạng máy tính.
Tầng vật lý: tầng vật lý là tầng liên quan tới việc truyền gửi các bit 0 và bit 1. Nó ịnh nghĩa tất cả các đặc tả về điện và vật lý cho các thiết bị.
Tầng liên kết dữ liệu: Tầng này sử dụng các thông điệp điều khiển (control) và thông điệp dữ liệu (data) để truyền thông điệp, tầng này sẽ liên quan đến các khái niệm frame, ACK, CRC...
Tầng mạng: Tầng này thực hiện việc định địa chỉ cho các phần tử trong mạng, đảm bảo thông điệp có thể được gửi đến đúng nơi cần nhận. Giao thức thường dùng ở tầng này là IP (internet protocol)
2.1.2 Giao thức tầng giao vận
Chức năng của tầng giao vận: Đảm bảo các gói tin đến đủ và thực hiện việc ghép các gói tin thành thông tin như được gửi đi khi chưa phân chia, cung cấp thông tin đó cho tầng trên (thường là các ứng dụng, nếu trong mô hình TCP-IP)
Mô hình Client-Server trong TCP
Khác với UDP, TCP luôn cố gắng để đảm bảo nhận đủ các gói tin, nếu trong quá trình truyền, nhận bị thất lạc một số gói tin, nó sẽ gửi các yêu cầu truyền lại cho đến khi nhận đủ
2.1.3 Giao thức các tầng cao hơn
Các tầng cao trông mô hình OSI gồm có tầng phiên (session) tầng biểu diễn (presentation) tầng ứng dụng (application)
Tầng phiên: Tầng sát trên tâng TCP, đảm bảo các phiên làm việc
Tầng biểu diến: Tầng đảm bảo việc chuyển đổi dữ liệu thành các dạng đặc biệt tùy theo yêu cầu của từng loại ứng dụng.
Hình 1: Mô hình TCP/IP
Giao thức middleware
Do những đặc thù riêng nên trong các hệ phân tán, dưới tầng ứng dụng thường còn một tầng middware, tầng này có nhiệm vụ hỗ trợ cho tầng ứng dụng và chứa các giao thức chung, những giao thức cần đảm bảo có một tầng riêng, độc lập với các tầng khác, ví dụ như các giao thức chứng thực, giao thức commit, giao thức khóa.
2.2 Remote Procedure Call (RPC)
RPC có thể được hiểu đơn giản là lời gọi thủ tục được đưa ra từ một máy nhưng lại được thực hiện trên một máy khác, trong một không gian địa chỉ khác, sau đó kết quả (nếu có) sẽ được chuyển về cho nơi đã gọi.
2.2.1 Các thao tác RPC cơ bản
Trong các lời gọi thủ tục, tham số truyền vào có hai dạng tham trị - call by value và tham biến, call by reference. Một trong những điểm khó nhất của RPC là thực hiện các lời gọi tham biến, vì không gian địa chỉ giữa nơi gọi và nơi thực hiện là khác nhau.
Client and Server Stubs
Client Stub và Server Stub là các thành phần làm nhiệm vụ chuyển các lời gọi hàm và kết quả trả về thành dạng message có thể truyền và nhận được.
Các thao tác trong RPC có thể tổng kết như sau:
Client chuyển lời gọi cho client stub theo cách thông thường
Client stub đóng gói thành message và chuyển message cho hệ điều hành
Hệ điều hành chuyển message cho hệ điều hành tại nơi đươc gọi
Hệ điều hành nơi nhận nhận message và chuyển lên cho server stub
Server stub mở gói message để nhận được tham số và lời gọi hàm
Server thực hiện lời gọi hàm đó với tham số nhận được và trả kết quả cho server stub
Server stub đóng gói kết quả thành message và chuyển cho hệ điều hành
Hệ điều hành phía server chuyển message cho hệ điều hành phía client
Hệ điều hành phía client đưa message lên cho client stub
Client stub mở gói message và đọc kết quả nhận được rồi chuyển cho client
2.2.2 Truyền tham số
Có hai loại truyền tham số, theo tham trị và tham biến.
Truyền theo tham trị (passing value parametters)
Việc đóng gói và mở gói để đọc các giá trị có thể được thực hiện bởi client và server stub.
Truyền theo tham biến (passing reference parametters)
Truyền cả vùng không gian được trỏ đến và đóng gói nó trong message gửi đi. Việc này khiến call-by-reference được thay thế bởi call-by-copy/restore.
Đặc tả tham số và việc sinh stub
Một vấn đề nữa là sự khác nhau có thể xảy ra giữa client và server trong việc qui ước các cấu trúc dữ liệu cơ sở. Ví dụ như số byte cho một sô nguyên, cách biểu diễn số thực, boolean...
Đối tượng liên quan đến vấn đề này là client stub và server stub, vì thế để chúng có hiểu được nhau cần một thành phần trung gian định nghĩa giao diện chung, gọi là IDL (interface define language).
Một giao diện được định nghĩa bởi người dùng (ở đây hiểu những người xây dựng các ứng dụng dựa trên RPC) định nghĩa các lời gọi cũng như tham số sử dụng sẽ là đầu vào cho IDL thực hiện việc biên dịch thành các client và server stub.
Các mô hình RPC mở rộng
Một sô mô hình RPC mở rộng như Door, Ansynchronuos PRC.
Door: Là một hình thức RPC trong đó sử dụng việc đăng ký door(register_door) và gán các thủ tục xử lý cho một door với một tên xác định(attach). Sau đó phía client sẽ sử dụng tên này và thủ tục open_door, để thực hiện RPC.
Ansynchronuos PRC: sự không đồng bộ thể hiện ở chỗ: client sẽ chỉ chờ server chấp nhận, sau khi được châp nhận nó thực hiện tiếp các công việc khác mà không chờ cho đến khi nhận được kết quả từ server. Khi nào nhận được kết quả nó sẽ ngừng công việc đang thực hiện và quay sang xử lý kết quả nhận được.
Hình 2: Mô hình RPC
2.3 Remote Object Invoce
Kỹ thuật hướng đối tượng đã tỏ ra rất hiệu quả và giá trị trong các hệ thống không phân tán. Một trong các khía cạnh quan trọng nhất của phương pháp này là dựa trên các đối tượng đóng kín và khi nhìn từ ngoài chỉ thấy thông qua một giao diện được định nghĩa trước. Cách tiếp cận này tạo nên một khả năng lắp ghép và thay thế linh hoạt, cũng như làm tăng sự độc lập ít bị ràng buộc giữa các module.
RPC đã được xây dựng để thực hiện communication trong các hệ phân tán với các thủ tục và người ta nhận thấy ý tưởng này hoàn có thể áp dụng với các đối tượng.
2.3.1 Đối tượng phân tán
Một trong các đặc tính quan trọng nhất của một đối tượng là những dữ liệu được đóng kín bên trong – gọi là state, các thao tác tác động trên các dữ liệu đó gọi là phương thức – method, và các method được nhìn thấy và có thể gọi từ ngoài đối tượng gọi là giao diện
Trong một hệ phân tán, đối tượng được chia làm hai phần, một phần nằm trên server chứa đầy đủ thông tin trạng thái state, cách thức hoạt động các phương thức, và interface, phần thứ hai nằm trên client chỉ có interface, còn phần lõi làm nhiệm vụ giống như client stub – gọi là proxy. Thành phần có nhiệm vụ tương tự server stub là skeleton.
Hình 3:Cấu trúc chung của đối tượng từ xa với proxy client
2.3.2 Kết nối một client với một object
Một điều thú vị khác với hệ thống sử dung RPC là trong các hệ thống sử dụng đối tượng phấn tán, các đôi tượng vừa có thể là chủ thể vừa có thể là tham số truyền vào, vì vậy tùy từng trường hợp để xác định khi nào liên kết object với con trỏ trỏ đến proxy, khi nào thì thực hiện gọi phương thức từ xa.
2.3.3 RMI tĩnh và động
Một lời gọi tĩnh được thực hiện thông qua một object, theo cách thông thường. Ví dụ
object.method(prameter);
trong khi đó lời gọi động sử dụng một hàm bên ngoài để gọi một phương thức bên trong object ( gần tương tự như reflection)
invoke(object, id(method), parameter);
2.3.4 Truyền tham số
Hình 4: Truyền đối tượng bởi tham chiếu và giá trị
Bởi vì trạng thái một đối tượng có thể chứa tham chiếu đến nhiều đối tượng khác, mà trong một hệ thống phân tán, các đối tượng này có thể nằm tại những vùng khác nhau. Ví dụ object O1 nằm tại machine A sử dụng một reference đến object O2 tại machine B, như vậy khi chuyển O1 cho machine C vẫn phải đảm bảo reference đến O2 trên machine B không thay đổi.
2.4 Message Oriented Communication
Một cách tiếp cận khác cho communication trong hệ phân tán là sự dụng việc truyề gửi các thông điệp dựa trên MPI (Message Passing Interface), thường dùng trong các hệ thống phân tán cần các thao tác xử lý song song.
2.4.1 Liên tục và đồng bộ
Là một trong những vấn đề đáng quan tâm nhất khi thực hiện communication hướng thông điệp.
Có 6 dạng tất cả:
Giao tiếp không đồng bộ bền Giao tiếp đồng bộ bền
Giao tiếp không đồng bộ tạm thời Giao tiếp đồng bộ tạm thời
Giao tiếp đồng bộ tạm thời dựa trên phân phát giao tiếp đồng bộ tạm thời dựa trên phản hồi
Chương 3: Process
3.1. Thread.
3.1.1 Một số khái niệm cơ bản
Processor: là điểm hành động mà hiểu được một tập hợp các lệnh, và có khả năng thực hiện những lệnh này.
Virtual processor: một bộ xử lý khi thực hiện một chương trình, hệ điều hành tạo ra một số virtual processor ( hay còn gọi là process), mỗi một bộ xử lý ảo thực hiện một chương trình khác nhau.
Virtual processors phải đảm bảo tính trong suốt người dung về tính tương tranh.
Process table: do hệ thống tạo ra để lưu vết các virtual process.
Để đảm bảo tính trong suốt tương tranh rất khó khăn do việc tạo process, chuyển ngữ cảnh CPU (giá trị thanh ghi, con trỏ chương trình, con trỏ ngăn xếp) tốn thời gian CPU.
Thread: tương tự như process nhưng nó tập trung vào hiệu năng của hệ thống. Do vậy hệ thống các thread chỉ lưu giữ thông tin tối thiểu cho phép CPU có thể được chia xẻ giữa các thread.
Process: đảm bảo tính trong suốt tương tranh, nên không gian địa chỉ từng process là riêng biệt, giảm hiệu năng hệ thống.
Thread: việc bảo vệ dữ liệu là do chương trình ứng dụng đảm nhiệm.
3.1.2.Thực thi các Thread.
Trong các hệ thống hỗ trợ đa luồng, luôn tồn tại các thao tác như tạo và huỷ bỏ nhiều tiến một cách đồng bộ. Có 3 giải pháp chính như sau:
Giải pháp không gian người dùng (User space): do chương trình đảm nhận.
Ưu điểm: dễ dàng tạo và huỷ các thread do tất cả cá việc quản lý tất cả các thread đều đượcgiữ trong không gian địa chỉ người dùng ( thông qua stack).
Nhược điểm: khi triệu gọi các hàm dừng của hệ thống thì toàn bộ tiến trình chứa thread đó sẽ bị dừng
Giái pháp không gian nhân
Ưu điểm: Tính song song cao, tiến trình không bị dừng khi một luồng gọi hàm dừng của hệ thống như các thao tác vào ra…
Nhược điểm: Việc chuyển ngữ cảnh trả giá cao, việc chuyển ngữ cảnh của thread sẽ như là chuyển ngữ cảnh của tiến trình. Thiếu sự linh hoạt , do phụ thuộc vào hệ điều hành.
Giải pháp dung hoà: Sủ dụng cách tiếp cận luồng 2 mức : lightweight process (LWP)
3.1.3. Threads in Distributed System.
Ta xem xét những ngữ cảnh chung của chương trình phân tán: multithreaded clients và multithread server. Và xem xét tính trong suốt phân tán, các cách sử dụng luồng như việc thực thi luồng dữ diệu và thực thi phi tập trung (peer-to-peer)
Multithread Clients: Vấn đề chủ yếu là che giấu hạ tầng kỹ thuật.
Multithreaded Web client: Trình duyệt web quét trang HTML đến, và tìm các file cần thiết để tải về, mỗi file được tải bởi một luồng riêng biệt, mỗi luồng thực hiện một yêu cầu dừng http và hi các files được tải xong, trình duyệt sẽ hiển thị chúng.
Multiple RPCs/RMIs : Một client thực hiện RPCs tại cùng thời điểm, mỗi lời gọi thực hiển bời một thread riêng biệt, sau đó đợi cho đến khi tất cả các két quả được trả về. Nếu dùng lời gọi thủ tục từ xa tới các server khác nhau, chúng ta có thể có tăng tốc theo hàm tuyến tính khi thực hiện RPC bới số thread dùng.
Multithread Sever: Vấn đề quan trọng của nó là tăng hiệu năng và cấu trúc chương trình. Ta xem xét 2 vấn đề
Tăng hiệu năng ở server: Việc bắt đầu handle một yêu cầu đến là “rẻ” hơn nhiều cho việc bắt đầu một tiến trình mới, multithreading dễ dàng cho việc phát triển các sever theo hướng song song, tăng hiệu năng của hệ thống.
Cấu trúc chương trình ở server tốt hơn: Các chương trình đa luồng có xu hướng nhỏ hơn và dễ hiểu hơn nhằm đơn giản luồng điều khiển, và nó phản ánh cấu trúc song song. Tất cả các request của từ client đều qua luồng dispatcher (bộ phân phối), sau khi kiểm tra request, luồng này chọn một luồng còn rỗi để xử lý luồng phân phối
server
hệ điều hành
luồng thực hiện
Yêu cầu phân phối thực hiện
Yêu cầu đến từ mạng
Hình 5: Multithreaded server được thực hiện mô hình dispatcher/worker
3.2 Clients
3.2.1 User Interfaces
Một phần chính của phần mềm phía client là tập trung vào giao diện người dùng. Trong đó UI sử dụng :
các tài liệu kết hợp: để là làm cho ứng dụng giao diện người dung cho phép giao tiếp nội tại ứng dụng
Drag-and-drop: di chuyển các đối tượng đến các vị trí trên màn hình, có thể thực hiện viện dẫn ứng dụng khác.
Chỉnh sửa tức thời: tích hợp một vài ứng dụng ở mức giao diện người dung ( xử lý văn bản + tiện ích vẽ).
Sử dụng như single desktop nó coa tác dụng trong suốt giao diện người dùng và che giấu các thao tác của mạng.
3.2.2 Client-Side Software
Yêu cầu của nó đó là tính tập trung vào cung cấp tính trong suốt của sự phân tán, cụ thể đó là tring suốt tính nhân bản và trong suốt về tính lỗi.
3.3. Server
3.3.1 Những đặc điểm thiết kế chung:
Mô hình cơ bản bao gồm một server là một tiến trình mà đợi các yêu cầu dịch vụ tại một địa chỉ truyền riêng và trong thực tế thì có sự ánh xạ 1-1 giữa một cổng và một dịch vụ.
Trong đó Super Server là Server mà lắng nghe một vài cổng cung cấp một số dịch vụ độc lập. thực tế khi một yêu cầu dịch vụ đến, chúng bắt đầu một tiến trình để kiểm soát yêu cầu.
Một vấn đề cần được xem xét đó là: có thể xảy ra ngắt một dịch vụ khi nó đã chấp chập một yêu cầu dịch vụ? khi đó ta sử dụng các cổng riêng để dữ liệu “nóng” ( yêu cầu có phản hồi ngay) hay sử dụng các tính năng out-of-band communication ở tầng vận chuyển (TCP cho phép làm điều này).
3.3.2. Object Sever
Ta xem xét một số khái niệm: servant, skeleton, object adapter.
Servant( sự trưng bày): object server tự nó không chứa một dịch cụ thể. Các dịch vụ cụ thể được thực thi bởi các đối tượng bên trong server.
Skeleton ( khung ): stub phía server cho việc handle vào ra mạng.
Object adapter: quản lý tập hợp các đối tượng
Kiểm tra các yêu cầu đến
Đảm bảo đối tượng được tham chiếu được hoạt động
Chuyển các yêu cầu đến skeleton thích hợp thông qua các chính sách hoạt đột.
Chịu trách nhiệm tạo ra các tham chiếu đối tượng.
3.4. Di trú mã
3.4.1 Các phương pháp tiếp cận di trú mã :
Lý do cần phải di trú mã: để tăng hiệu năng và độ linh hoạt của hệ thống do việc di chuyển của các tiến trình đang thực hiện là rất khó khăn.
Một tiến trình bao gồm :
Phần mã (Code Segment): chứa tập các lệnh của tiến trình đang thực hiện.
Phần tài nguyên (Resource Segment): chứa các tham chiếu đến tất cả các tài nguyên bên ngoài mà tiến trình đang cần
Phần thực thi (Execution segment): chứa các trạng thái thực thi hiện hành của tiến trình.
Các mô hình di trú mã:
Hình 6 Các mô hình di trú mã.
Weak mobility: chỉ truyền phần mã và một số các dữ liệu khởi động của tiến trình. Đặc tính của mô hình này là một chương trình được truyền đi luôn được bắt đầu từ trạng thái khởi động, chỉ yêu cầu máy đích có thể thực thi yêu cầu (code) đó
Strong mobility: truyền cả phần mã và phần thực thi. Đặc điểm của mô hình này là một tiến trình đang chạy có thể được dừng lại rồi chuyển đến một máy khác và tiếp tục thực hiện tiếp tiến trình đó →khó thực thi hơn.
Sender initiated migration (di trú được khởi tạo từ phía gửi) : Di trú được khởi động từ máy mà phần code của tiến trình được lưu trữ hoặc đang thực hiện. Di trú này hoàn thành khi upload chương trình.
Receiver initiated migration (di trú được khởi tạo từ phía nhận) : Di trú mã ban đầu từ máy tính.
Di trú được khởi tạo từ phía nhận thực thi đơn giản hơn di trú được khởi tạo từ phía gửi.
3.4.2 Di trú và quản lý các tài nguyên cục bộ :
Cách thức kết nối đối tượng tới tài nguyên
Bởi định danh/ tham chiếu: đối tượng cần một thể hiện cụ thể của một tài nguyên.
Bởi giá trị: đối tượng yêu cầu giá trị của một tài nguyên.
Bởi kiểu: đối tượng yêu cầu kiểu của tài nguyên là sẵn dùng.
Giao thức cho việc quản lý tài nguyên cục bộ.
Có 4 giao thức đề cập GR, MV, CP, RB
GR và MV là các giao thức kiểu stateful
CP là giao thức kiểu stateless
RB là giao thức cho điểm truy cập có thể là stateful nhưng trạng thái tổng thể không
3.4.3. Di trú trên các hệ thống không đồng nhất
Vấn đề chính mà ta cần giải quyết đó là: Trên máy đích có thể không thích hợp thực thi các mã đã di trú.và định nghĩa ngữ cảnh của tiến trình/luồng/bộ xử lý có tính độc lập cao với phần cứng, hệ hiều hành và hệ thống chạy
Giải pháp được đưa ra đó là sử dụng máy ảo mà được thực thi trên nhiều nền khác nhau.
Các giải pháp hiện tại:
Ngôn chữ phiên dịchchạy trên máy ảo (Java/JVM; Mozart virtual machine)
Các ngôn ngữ (C hay Java) cho phép di trú tại điểm “có thể vận chuyển” riêng, ngay trước khi một lời gọi hàm (weak mobility).
3.5 Software agent
3.5.1 Khái niệm tác tử phần mềm
Định nghĩa: Tác tử là một tiến trình tự trị có khả năng phản ứng, trao đổi, cộng tác với các tác tử khác trong môi trường của nó.
Các loại tác tử:
Tác tử cộng tác: công tác với các tác tử khác trong hệ thống đa tác tử.
Tác tử di động: có thể di chuyển giữa các máy.
Tác tử giao diện: trợ giúp mức giao diện người dùng.
Tác tử thông tin: quản lý thông tin về những tài nguyên vật lý khác nhau.
Phân loại theo khái niệm di trú hóa:
Tác tử di động (mobie agent): là một tác tử đơn giản có khả năng di chuyển giữa các máy khác nhau. Trong di trú mã, các tác tử di động thường yêu cầu hỗ trợ cho mô hình di động mạnh mặc dù là không cần thiết. Yêu cầu này đến từ thực tế là các tác tử là tự trị và có ảnh hưởng lẫn nhau và với môi trường của chúng. Sự di chuyển một tác tử đến máy khác khó có thể được thực hiện nếu không xét đến trạng thái thực thi của nó. Tính di động là đặc tính chung của các tác tử.
Tác tử thông minh (Intelligent agent): là tác tử dùng để quản lý thông tin từ nhiều nguồn khác nhau. Việc quản lý thông tin bao gồm việc sắp xếp, lọc, thu thập… Vì các tác tử này thao tác trên thông tin từ những nguồn vật lý khác nhau nên chúng đóng vai trò rất quan trọng.
3.5.2 Kỹ thuật tác tử.
Thành phần quản lý: lưu vết vị trí của các tác tử trên các nên ( ánh xạ định danh tác tử và cổng) (White pages)
Thành phần thư mục: ánh xạ các thuộc tính tên/ dịch vụ của tác tử đến định danh của tác tử (Yellow pages)
ACC(Agent Communication Channel): kênh truyền thông tác tử, được sử dụng để truyền thông với các nền khác.
Ngôn ngữ truyền thông tác tử (ACL – Agent Communication Languages)
ACL là giao thức tầng ứng dụng làm nhiệm vụ phân biệt giữa mục đích và nội dung của thông điệp.
Chương 4: Naming
Name đóng một vai trò quan trọng trong tất cả các hệ thống máy tính. Chúng được sử dụng để chí xẻ nguồn tài nguyên, để định danh một thực thể một cách duy nhất, để truy vấn tới địa chỉ và rất nhiều chức năng khác nữa. Vấn đề quan trọng của naming đó là name có thể quyết định hay đại diện cho thực thể mà nó tham chiếu tới, nó cho phép một tiến trình truy nhập tới thực thể được đặt tên đó,và nó cần thực thi một hệ thống naming. Và sự khác biệt về naming giữa hệ thống phân tán và không phân tán phụ thuộc vào cách mà hệ thống naming được thực thi.
Trong hệ phân tán , sự thực thi của hệ thống naming là tự nó được phân tán qua các máy. Và ở trong chương này chúng ta sẽ tập trung vào 3 cách quan trọng mà name được sử dụng trong hệ phân tán.
4.1 Các thực thể định danh (Naming Entities)
Đầu tiên chúng ta sẽ xem xét các loại khác nhau của tên và cách chúng được tổ chức trong không gian tên , sau đó sẽ là tại sao tên lại đạu diện được cho thực thể.
4.1.1 Một số khái niệm
Name: xâu các bit hoặc kí tự dùng để tham chiếu đến các thực thể trong hệ phân tán.
Access point: để thao tác trên các thực thể, mỗi thực thể sẽ phải có một điểm truy nhập (access point)
Address: Là một dạng đặc biệt của tên, nó thể hiện điểm truy cập (access point) của một thực thể
Identifier (định danh): là một tên đặc biệt có các tính chất
Mỗi định danh được tham chiếu tới nhiều nhất một thực thể
Mỗi thực thể được tham chiếu bởi nhiều nhất một định danh
Một định danh luôn tham chiếu tới cùng một thực thể
Việc dùng định danh là một cách đơn giản để tránh nhập nhằng trong việc thể hiện một thực thể.
4.1.2. Không gian tên
Các tên (names) trong HPT được tổ chức lại thành một cái gọi là không gian tên. Không gian tên có thể được biểu diễn như một đồ thị có hướng được gán nhãn và có hai loại nút:
Nút thư mục (directory node): là nút có các nút con.
Nút lá (leaf node): là thực thể đã được định danh, thường lưu trữ thông tin đủ để một máy khách có thể truy nhập tới (chẳng hạn như nó lưu chính địa chỉ của thực thể)
Hình 7: Không gian tên
Ví dụ như hình trên thì nút n0 chỉ có đường ra mà không có đường vào và nó được gọi là nút gốc, và trong một đồ thị có thể có nhiều nút gốc.
4.1.3 Phân giải tên (name resolution)
Không gian tên là một có chế cho phép lưu trữ và truy vấn thông tin về thực thể thông qua tên, nói một cách chung chung thì quá trình tìm kiếm một tên gọi là không gian tên. Để cụ thể ta xem xét với một đường dẫn tên như:
N:
thì quá trình phân giải tên sẽ bắt đầu từ nút gốc N, tìm định danh của label-1 rồi label-2 và tiếp tục cho đến label-n (nếu đường dẫn thực sự tồn tại). Nút lá cuối cùng sẽ trả về nội dung của nó.
Một vấn đề cần giải quyết đó là làm sao để có thể có nhiều tên cho một thực thể. Những cái tên khác được gọi là bí danh (alias). Có hai phương pháp để thực hiện công việc này:
Các liên kết cứng (hard links): có nhiều đường dẫn tới một nút lá (như nút n5 trong hình 13).
Các liên kết biểu tượng (symbolic links): có một số nút lá thay vì lưu trữ địa chỉ hay trạng thái của thực thể chúng lại lưu trữ một đường dẫn tuyệt đối tới nút khác
Có hai phương pháp để có thể trộn các không gian tên với nhau. Phương pháp thứ nhất là sử dụng cách lắp ráp (mounting) không gian tên. Phương pháp này sử dụng các nút thư mục mà thông tin nó lưu trữ lại là tên của một thực thể nào đó của không gian tên khác
Phương pháp thứ hai là cho các nút gốc của những không gian tên trở thành con của một nút gốc mới. DEC’s Global Name Service (GNS) sử dụng phương pháp này:
Hình 8: Tổ chức của dịch vụ tên DEC
4.1.4. Thực thi một không gian tên
Ở các hệ phân tán lớn, có rất nhiều thực thể và chúng được trải ra ở một không gian địa lý rộng lớn. Do vậy, cần phải phân tán việc thực thi một không gian tên ra nhiều máy chủ định danh.
Các không gian tên cho một hệ phân tán lớn thường được tổ chức thành một hệ phân cấp và thường có 3 lớp:
Lớp tổng thể (global layer): chứa các nút thư mục ở mức cao, chúng được quản lý đồng thời bởi những người quản trị khác nhau.
Lớp quản trị (administrational layer): chứa các nút thư mục ở mức trung bình, chúng được nhóm lại để chia cho những người quản trị riêng lẻ.
Lớp quản lý (managerial layer): chứa các nút thư mục ở mức thấp, mỗi nút được ánh xạ tới một máy chủ định danh cục bộ.
Thực thi phân giải tên:
Có hai phương pháp thực thi phân giải tên. Phương pháp phân giải tên lặp (iterative name resolution) đòi hỏi ở mỗi bước bộ phân giải tên của máy khách phải giao tiếp với máy chủ định danh để nhận được định danh của một nút. Trong khi đó ở phương pháp phân giải tên đệ quy (recursive name resolution) thì bộ phân giải tên ở máy khách chỉ cần gửi yêu cầu một lần, máy chủ định danh sẽ tự xác định các định danh ở từng nút và gửi về cho máy khách một lần duy nhất.
4.2 Định vị các thực thể di động (Locating Mobile Entities)
Các hệ thống định danh truyền thống không phù hợp cho các thực thể di động. Do vậy, đòi hỏi phải có những cơ chế để định vị những thực thể di động này.
4.2.1 Định danh và định vị các thực thể di động.
Mục tiêu đặt ra cho việc định vị các thực thể di động là làm sao cho các máy khách biết được địa chỉ hiện thời của các thực thể mà nó cần tham chiếu tới.
Để có thể ánh xạ được tên tới địa chỉ của mỗi thực thể, có thể sử dụng ánh xạ một mức và ánh xạ hai mức:
Hình 15: (a) Ánh xạ trực tiếp, một mức giữa tên và địa chỉ
(b) Ánh xạ hai mức sử dụng các định danh (identifiers)
4.2.2. Các giải pháp đơn giản
Broadcasting và Multicasting
Broadcasting: khi cần xác định địa chỉ của một thực thể, một thông điệp mang nội dung là định danh (identifier) của thực thể sẽ được gửi tới tất cả các máy khác. Chỉ những máy biết điểm truy nhập tới thực thể mới phản hồi một thông điệp chứa địa chỉ của thực thể.
Multicasting: thay vì gửi thông điệp trên toàn bộ mạng, ở giải pháp này sẽ chỉ có yêu cầu tới một lượng hạn chế các máy chủ.
4.2.3 Các cách tiếp cận dựa trên gốc (Home-Based Approachs)
Một cách tiếp cận phổ biến để hỗ trợ cho các thực thể di động trong một mạng lớn là dùng một vị trí gốc (home location). Vị trí gốc sẽ luôn lưu trữ vị trí hiện thời của thực thể.
Lược đồ bậc một (single-tiered scheme):
Một địa chỉ gốc của thực thể sẽ được đăng kí với một máy chủ định danh.
Gốc sẽ đăng kí địa chỉ ngoài cho thực thể.
Các máy khách cần phải liên hệ với gốc trước sau đó mới liên hệ tới vị trí bên ngoài.
Lược đồ bậc hai (two-tiered sheme):
Khi bắt đầu một kết nối tới thực thể di động, máy khách sẽ kiểm tra trong đăng kí nội bộ có thực thể đó không. Nếu không có thì sẽ liên hệ với vị trí gốc để tìm vị trí hiện thời của thực thể.
4.2.4 Các cách tiếp cận phân cấp
Ở lược đồ phân cấp, một mạng sẽ được chia thành tập các miền. Có một miền cao nhất chứa toàn bộ mạng. Mỗi miền lại được chia thành những miền con. Miền thấp nhất được gọi là miền lá, tương ứng với một mạng LAN.
Việc phân chia này sẽ tạo nên một cây. Và việc tìm kiếm địa chỉ của một thực thể là một phép tìm kiếm trên cây bắt đầu từ một miền lá đến miền lá chứa thực thể. Mỗi miền đều có thông tin là thực thể đó có nằm trong nó không. Do vậy, khi một thực thể di chuyển từ miền lá này tới miền lá khác, nó cần thông báo lên các miền tổ tiên để cập nhật lại thông tin ở những miền đó.
4.3 Xóa bỏ các thực thể không được tham chiếu
Trong nhiều hệ thống, xóa bỏ một thực thể được thực hiện một cách chính xác. Tuy nhiên quản lý xóa bỏ thực thể trong hệ phân tán lại rất khó, cụ thể là ta không biết liệu thực thể đó được lưu trữ những đâu trong hệ phân tán hay là sẽ có truy nhập tới thực thể đó sau khi thực thể bị xóa đi và khi đó sẽ xuất hiện lỗi. Nhưng cúng sẽ là không thể chấp nhận được nếu ta không bao giờ xóa bỏ đi thực thể chỉ vì những khó khăn đó. Chính vì thế với những thực thể không cần dùng nữa ta sẽ xóa đi. Và ta sẽ xóa đi các thực thể mà trong một thời gian dài không được dùng đến và nó được biết đến với một cái tên đó là bộ thu dọn rác của hệ phân tán (distributed garbage collector)
4.3.1 Vấn đề với những thực thể không được tham chiếu
Trong các hệ thống, khi có một thực thể nào đó không còn được tham chiếu hay được sử dụng nữa thì nó nên được loại bỏ. Tuy vậy, việc loại bỏ một thực thể trong hệ phân tán lại không hề đơn giản. Vì có thể có một tham chiếu được lưu ở một nơi nào đó trong hệ thống để tham chiếu sau. Nếu loại bỏ thực thể đi thì khi tham chiếu được thực hiện, sẽ có lỗi xảy ra.
Tuy vậy, không vì thế mà không loại bỏ các thực thể không được tham chiếu, vì những thực thể như vậy được coi là rác và cần phải loại bỏ đi. Một trong những cách để người ta loại bỏ các đối tượng không được tham chiếu là sử dụng bộ thu gom rác phân tán (Distributed Garbag Collector).
Có hai vấn đề cần đặt ra cho việc loại bỏ các thực thể không được tham chiếu:
Làm sao chúng ta biết khi nào một thực thể không được tham chiếu nữa?
Ai là ngư._.ời có trách nhiệm phải loại bỏ những thực thể không được tham chiếu.
4.3.2 Đếm các tham chiếu
Một phương thức phổ biến trong các hệ thống đơn bộ xử lý để kiểm tra xem một đối tượng có thể được xóa hay không là đếm số tham chiếu tới đối tượng này.
Trong các hệ phân tán, việc đếm các tham chiếu sẽ nảy sinh ra một số vấn đề.
Vấn đề 1: có thể mất hoặc lặp thông điệp dẫn đến việc đếm sai. Vấn đề này có thể giải quyết bằng cách tạo thêm một bản sao của tham chiếu tới tiến trình khác.
Vấn đề 2: có thể lặp tham chiếu. Đó là trường hợp khi tiến trình P1 thông báo cho P2 rằng phải tham chiếu tới O, sau đó P1 xóa tham chiếu của nó tới O. Nếu P2 không kịp gửi tham chiếu trước khi P1 xóa tham chiếu thì rất có thể O sẽ bị loại bỏ trước khi nhận tham chiếu của P2. Để giải quyết vấn đề này thì P1 cần phải nói với O rằng nó sẽ chuyển tham chiếu cho P2. O sẽ liên hệ ngay với P2 và đảm bảo sẽ không bị loại bỏ đi trước khi được thừa nhận đã nhận được tham chiếu.
Một giải pháp nữa cho phép tránh việc tăng hay giảm số thông điệp. Đó là mỗi đối tượng chỉ cho phép một lượng tối đa tham chiếu tới nó. Mỗi khi có một tham chiếu mới, một nửa hạn mức sẽ được gán cho tiến trình tham chiếu. Và khi có thông báo một tham chiếu bị hủy thì tổng số trọng số ở đối tượng sẽ bị giảm đi. Khi con số này giảm đến 0 thì có nghĩa sẽ không còn tham chiếu nào nữa, và đối tượng có thể được loại bỏ.
4.3.3 Ghi danh sách các tham chiếu
Một cách tiếp cận khác để quản lý các tham chiếu là ghi lại danh sách tất cả các proxy trỏ tới đối tượng. Việc thêm một proxy chỉ có tác dụng khi chưa có proxy đó trong danh sách và cũng chỉ loại bỏ một proxy nếu có nó trong danh sách.
Việc ghi danh sách này không đòi hỏi độ tin cậy của việc truyền thông, cũng như không cần phải phát hiện và loại bỏ những thông điệp lặp. Đây là một ưu điểm vượt trội so với phương pháp đếm số lượng tham chiếu.
Chương 5. Đồng bộ hóa
Trong chương này, chúng ta sẽ tìm hiểu cách thức các process có thể làm việc đồng bộ với nhau, điều này sẽ rất quan trọng khi sử dụng các tài nguyên dùng chung hoặc khi phải xứ lý các sự kiện mà trong đó, trình tự xử lý là cố định không được phép thay đổi.
5.1 Đồng bộ đồng hồ
Trong các hệ thống tập trung, thời gian thời gian thường không dóng vai trò rõ ràng, khi cần biết về thời gian, nó sẽ gọi và nhận kết quả từ hệ thống, phần nhân – kernel sẽ làm việc đó.Nếu một tiến trình A hỏi trước tiến trình B thì thời gian A nhận được sẽ sơm hơn B một chút. Điều đó thật hiển nhiên trong một hệ thống tập trung. Nhưng với hệ thống phân tán thì không đơn giản như vậy.
Trong một hệ thống phân tán, mỗi thành phần phân tán có một hệ thống đếm giờ riêng và nó hoàn toàn không giống nhau, thậm chí cả về tốc độ. Do đó một vấn đề đặt ra là phải thực hiện việc đồng bộ hóa trên toàn bộ hệ thống, sao cho các thành phần có thể làm việc với nhau một cách nhịp nhàng.
Một giải pháp đưa ra là dùng một hệ đo chuẩn sao cho tại các thành phần khác nhau thì thời gian đo được là như nhau.
5.1.1 Đồng hồ vật lý
Sử dụng đồng hồ vật lý là một giải pháp, đó là phương pháp sử dụng cách chúng ta vẫn làm để đo thời gian, dựa vào góc quay của trái đất quanh mặt trời và góc quay riêng của trái đất quanh trục của nó. Mặc dừ vậy, vẫn có sự sai lệch do trái đất đang quay chậm lại, dù là rất rất nhỏ. Ba trăm triệu năm về trước thời gian 1 năm là 400 ngày, trong khi bây giờ là hơn 365 ngày ¼ ngày một chút.
Theo phương pháp này chúng ta có hai hệ đo, TAI và UTC. TAI – international Atomic Time có đơn vị chia không đổi dựa vào sự dao động của nguyên tử, trong khi UTC lại dựa vào vong quay của trái đất quanh mặt trời. Và để đảm bảo khớp với TAI, UTC phải có những đoạn chia không đều.
5.1.2 Các giải thuật đồng bộ theo đồng hồ vật lý
Ý tưởng cơ bản của phương pháp này là tất cả các thành phần sẽ cùng quan sát một đồng hồ chung và điều chỉnh đồng hồ của mình theo đồng hồ chung này. Có thể điều chỉnh nhanh hơn hoặc chậm đi, tùy tình huống.
Có một số giải thuật sau:
Giải thuật Cristian: Sử dụng một time server, các thành phần trong hệ phân tán sẽ request tới đó để hỏi giờ. Tuy nhiên để tính đung thời gian nhận được, phía client phải thực hiện một số tính toán trừ đi quãng thời gian xử lý trên server (I) và thời gian truyền ( (T1 – T0 –I) / 2 ).
Giải thuật Berkeley: một thành phần là time deamon sẽ thực hiện đồng bộ giờ cho các thành phần khác. Theo định kỳ nó sẽ gửi thời gian của nó cho các thành phần, các thành phần này so sánh với giờ của mình và gửi lại độ sai khác cho time deamon. Sau đó time deamon sẽ gửi lại các thành phần khoảng thời gian cần điều chỉnh của nó, tính cả quãng thời gian xử lý trên time deamon và thời gian truyền gửi thông điệp.
Giải thuật thời gian trung bình: Nếu như hai phương pháp trên là phải xử lý tập trung thì phương pháp này có thể tránh được điều đó. Sau mỗi khoảng thời gian nhất định, tất cả các thành phần trong hệ phân tán thực hiện broadcast giờ của mình, và sau đó tính lại giờ theo giá trị trung bình mà nó nhận được từ các thành phần khác.
5.2 Đồng hồ lôgic
Trong thực tế việc sử dụng đồng hồ vật lý không đảm bảo độ chính xác và phải thực hiện phức tạp. Do vậy khái niệm đông hồ logic được đưa ra.
5.2.1 Lamport timestamps
Lamport định nghĩa như sau:
Nếu a xảy ra trước b thì a ® b
Nếu a là sự kiện gửi thông điệp, b là sự kiên nhận thông điệp đó thì a ® b
Mối quan hệ này có tính bắc cầu, nếu a ® b và b ® c thì a ® c. Để thực hiện được điều này, chúng ta định nghĩa một nhãn thời gian C cho mỗi sự kiện trong hệ thống. Sao cho nếu a ® b thì C(a) < C(b).
Thuật toán lamport thực hiện như sau:
For Pi: (initially Tsi = 0)
On event e:
Case e is send(m), where m is a message
TSi = TSi + 1
m.TS = TSi
Case e is receive(m), where m is a message
TSi = max(TSi, m.TS)
TSi = TSi + 1
Case e is any other event
TSi = TSi + 1
e.TS = Tsi /* timestamp e */
Giải pháp ở đây là sử dụng nhãn thời gian theo thuật toán Larmport. Không thực hiện ngay các thông điệp nhận được mà đưa chúng vào queue, sau đó thực hiện sắp xếp theo nhãn thời gian. Vì thuật toán này đảm bảo mỗi thông điệp chỉ có một nhãn thời gian duy nhất nên thứ tự sẽ giống nhau tại các thành phần khác nhau của hệ phân tán.
5.2.2 Vector timestamps
Giải thuật của Lamport chỉ đảm bảo rằng
Nếu sự kiện a xảy ra trước sự kiện b thì C(a) < C(b)
Mỗi Pi có một vector VTi[], được gọi là vector timestamp, định nghĩa như sau
VTi[i] = số sự kiên mà Pi đã gán nhãn
VTi[j] = số sự kiên mà Pi biết Pj đã gán nhãn (i ¹ j)
Sau đó khi Pi có một sự kiện nó sẽ xử lý như sau:
Pi: (initially VTi = [0,
, 0])
On event e:
Case e is send(m), where m is a message
VTi[i] = VTi[i] + 1
m.VT = VTi
Case e is receive(m), where m is a message
for j = 1 to N /* vector length */
VTi[j] = max(VTi[j], m.VT[j])
VTi[i] = VTi[i] + 1
Case e is any other event
VTi[i] = VTi[i] + 1
e.VT = Vti /* timestamp e */
Thuật toán này đảm bảo
Nếu a ® b thì VT(a) < VT(b)
Và ngược lại nếu VT(a) < VT(b) thì a ® b
5.3 Giải thuật lựa chọn
Trong các giải thuật phân tán, thường phải sử dụng một tiến trình đứng ra điều phối hoạt động. Trong một số hệ thống, tiến trình này được chọn cố định nhưng nhìn chung thì không phải như thế. Nghĩa là chúng ta sẽ sử dụng một giải thuật để tìm ra một tiến trình có thể hoạt động như một tiển trình điều phối trong tập những tiến trình đang hoạt động. Các thuật toán đó sẽ được trình bày sau đây.
Thuật toán Bully
Khi các tiến trình không nhận được phản hồi từ tiến trình điều phối, chúng sẽ thực hiện việc lựa chọn một tiến trình điều phối khác như sau. Với mỗi tiến trình P, nếu được ứng cử sẽ thực hiện:
Gửi thông điệp ứng cử (ELECTION) đến các tiến trình có số hiệu cao hơn
Nếu không có tiến trình nào trả lời chứng tỏ P là tiến trình có số hiệu cao nhất con hoạt động. Vì thế chính la tiến trình cần lựa chọn
Nếu có một tiến trình có số hiệu cao hơn phản hồi, nhiệm vụ của P kết thúc.
Thuật toán xoay vòng
Trong thuật toán này, mỗi tiến trình có một tiến trình kế tiếp duy nhất và tạo thành một vòng khép kín (ring). Nếu tiến trình nào nhận thấy tiến trình điều phối không hoạt động nữa, nó sẽ gửi thông điệp ELECTION cho tiến trình kế tiếp nó, đồng thời gắn sô hiệu của nó vào thông điệp. Nếu tiến trình kế tiếp không phản hồi, nó sẽ bỏ qua và gửi thông điệp cho tiếp trình tiếp theo nữa trong vòng. Khi một tiến trình nhận được thông điệp ELECTION nó tiến hành thêm sô hiệu của mình vào thông điệp và tiếp tục gửi theo vòng. Cho đến khi quay trở về tiến trình đầu tiên.
Khi đó tiến trình này sẽ chọn tiến trình có số hiệu cao nhất trong các số hiệu đã đính kèm vào thông điệp và gửi thông điệp COODINATOR cho tiến trình kế nó kèm theo sô hiệu của tiến trình được chọn. Một tiến trình khi nhận được thông điệp COORDINATOR sẽ tiếp tục gửi cho tiếp trình kế tiếp nó cho đến khi được một vòng.
5.4 Loại trừ lẫn nhau
Một trong những vấn đề phải xử lý trong hệ thống phân tán là những xung đột khi nhiều tiến trình yêu cầu sử dụng miền găng. Việc điều phối các tiến trình này sử dụng miền găng một cách hợp lý hiệu quả là không đơn giản.
Sau đây là một số thuật toán.
5.4.1 Thuật toán tập trung
Thuật toán này sử dụng một tiến trình điều phối chung. Khi một tiến trình muốn sử dụng miền găng, nó phải xin phép tiến trình điều phối, nếu miền găng đang rỗi và queue rỗng, nó cho phép tiến trình này vào, còn nếu không, nó đặt lời gọi của tiến trình này vào queue và không trả lời. Cho đến khi miền găng được trả lại trạng thái rỗi, tiến trình điều phối mới thực hiện việc chọn lựa tiến trình tiếp theo trong queue cho vào miền găng, đồng thời trả lời OK, thông báo cho tiến trình này đã được phép sử dụng miền găng.
Thuật toán này là một thuật toán tập trung nên sẽ có nhược điểm là tập trung quá nhiều xử lý trên một tiến trình, gây ra hiện tượng thắt cổ chai, đồng thời nếu tiến trình này lỗi, và không hoạt động nữa sẽ gây ảnh hưởng đến toàn hệ thống.
5.4.2 Thuật toán phân tán
Thuật toán này không sử dụng một tiến trình điều phôi chung. Các tiến trình sẽ tự hỏi lẫn nhau để xác định tiến trình được phép vào miền găng.
Khi một tiến trình muốn vào miền găng nó sẽ gửi một thông điệp chứa tên miền găng cần dùng, thời gian hiện tại và số hiệu của nó, sau đó gửi cho tất cả các tiến trình khác, trừ bản thân nó.
Khi một tiến trình nhận được thông điệp này sẽ có các tình huống sau đây:
Nếu tiến trình nhận không phải đang sử dụng miền găng và không muôn dùng miền này, nó sẽ gửi lại thông điệp OK
Nếu tiến trình nhận đang sử dụng miền găng, nó không trả lời và xếp số hiệu tiến trình gọi vào queue.
Nếu tiến trình nhận hiện không sử dụng miền găng nhưng cũng muốn dùng miền này, nó sẽ so sánh thời gian trên thông điệp gửi đến và thời gian trên thông điệp xin dùng miền găng mà nó đã gửi đi. Nếu thời gian trên thông điệp nhận được sớm hơn trên thông điệp của nó, nó sẽ trả lời OK. Còn không thì thôi.
Thuật toán phân tán có ưu điểm vì nó phân tán, tránh được hiện tượng thắt cổ chai và không bị phụ thuộc vào một tiến trình cụ thể nào. Tuy nhiện nó lại châm hơn, phức tạp hơn và tốn kém hơn.
5.4.3 Thuật toán dùng token-ring
Trong thuật toán này, một vòng (ring) logic được tạo ra, trong đó mỗi tiến trình có một tiến trình kế tiếp nó. Một thẻ token sẽ được sử dụng để truyền đi trong vòng. Ban đầu khi vòng được khởi tạo, tiến trình 0 sẽ giứ token. Nếu một tiến trình không cần sử dụng miền găng, nó sẽ chuyển token cho tiến trình kế tiếp. Do vậy khi không có tiến trình nào cần dùng miền găng, token sẽ được xoay liên tục trong vòng.
Vấn đề của thuật toán này là các token có thể bị mất trong quá trình truyền, dẫn đến việc phải tạo lại token. Tuy nhiện việc xác định một token bị mất là khó.
5.5 Giao tác phân tán
5.5.1 Mô hình giao tác
Khi sử các tài nguyên dùng chung được truy cập và sử chữa bởi nhiều đối tượng, chúng ta cần xây dựng khái niệm giao tác, là tập hợp các thao tác tác động lên tài nguyên dùng chung, đảm bảo tính ACID (Atomic:Consistent:Isolated:Duarable)
5.5.2 Phân loại các giao tác
Có thể phân giao tác thành các loại: giao tác phẳng, giao tác lồng, giao tác phân tán.
Giao tác phẳng : Là các giao tác không cho phép thực hiện commit hay abort từng phần.
Giao tác lồng: Là các giao tác trong đó, một giao tác có thể có chứa nhiều giao tác con với các thao tác commit và abort từng phần
Giao tác phân tán: đóng vai trò quan trọng trong các hệ thống phân tán. Nó giống như giao tác lồng nhưng trong đó các giao tác con câp thấp nhất – các giao tác phẳng sẽ phải thực hiện các thao tác trên một cơ sở dữ liệu phân tán, thông qua nhiều máy khác nhau.
5.5.3 Thực hiện
Để thực hiện mô hình giao tác, trong các hệ thống phân tán thường sử dụng hai phương pháp: Dùng không gian làm việc riêng (private workspace) và WAL (writeahead log)
Private workspace: Khi có những tác động thay đổi đến tài nguyên dùng chung, những khối bị thay đổi sẽ được copy vào private workspace, và thực hiện các thay đổi trên bản sao. Khi giao tác hoàn thàn (Commit), các thay đổi này mới thực sự được áp dụng, thông qua việc đổi lại con trỏ trong bang index trỏ đến khối mới thay vì khối cũ. Đồng thời giải phóng các khối cũ. Các khối mới tạo thêm trong quá trình thực hiện giao tác gọi là shadow block.
Writeahead log: Là phương pháp sử dụng việc khi lại các thao tác trong một thao tác vào log, các thông tin được ghi lại sao cho có thể thực hiện rollback khi giao tác không hoàn thành hoặc redo khi giao tác hoàn thành nhưng chưa được cập nhật vào cơ sở dữ liệu
5.5.4 Điều khiển đồng thời
Khi có nhiều giao tác cũng can thiệp vào một tài nguyên dùng chung, sẽ phải sử dụng khóa và lập lịch thực hiện cho các giao tác này.
Việc lập lịch đảm bảo các giao tác sẽ sử dụng tài nguyên dùng chung tuần tự, không xung đột.
Để hạn chế deadlock, việc thực hiện khóa dữ liệu trong giao tác được thực hiện theo phương pháp khóa hai pha 2PL – Two phase locking. Phương pháp này dồn tất cả các thao tác khóa lên trước là mở khóa ra sau, tránh hiện tượng tiến trình 1 giữ khóa A chờ mở khóa B còn tiến trình 2 giữ khóa B và chờ mở khóa A. Cụ thể như sau:
1. Khi bộ lập lịch nhận được thao tác oper(T,x), nó sẽ kiểm tra xem thao tác này có xung đột với các thao tác khác hiện đang dùng x hay không, nếu có thao tác này phải chờ (và vì thế giao tác T cũng phải chờ). Nếu không có xung đột, nó sẽ khóa x và cho phép thao tác thực hiện
2. Bộ lập lịch sẽ không mở khóa cho x, cho đến khi thao tác thực hiện xong
3. Khi một khóa đã được mở sẽ không có khóa nào được cấp phát cho giao tác T nữa.
Trong nhiều hệ thống, khi thực hiện rollback có thể phải can thiệp vào những phần đã mở khóa, nên các thao tác mở khóa được dồn đến tận cuối cùng của giao tác, gọi là strict 2PL
2PL còn được chia làm 2 loại, TPL tập trung và TPL phân tán tùy theo cách thức điều khiển khóa và mở khóa là tập trung hay phân tán.
Chương 6: Nhất quán và nhân bản
6.1. Các lí do tạo bản sao
Có 2 nguyên nhân chính cho tạo bản sao: đó là tính tin cậy và hiệu năng hệ thống.
Tạo ra nhiều bản sao của một tệp giúp cho việc truy nhập vào tệp đó ổn định, vì nếu bản gốc bị hỏng ta có thể thay thế bằng một bản sao của nó.
Khi hệ thống mở rộng về số lượng hoặc trải ra trên một phạm vi địa lý rộng, việc tạo bản sao dữ liệu giúp cải thiện hiệu năng.
Tạo bản sao đem lại nhiều lợi ích nhưng có một nhược điểm là việc giữ nhiều bản sao sẽ rất khó đảm bảo được nhất quán. Mặc dù tạo bản sao và cache là các phương pháp hữu hiệu để tăng hiệu năng nhưng nó yêu cầu băng thông lớn cho đồng bộ hoá các bản sao.
6.2. Các mô hình nhất quán lấy dữ liệu làm trung tâm
Các mô hình nhất quán loại này đặt ngữ cảnh là có một bản sao dữ liệu được truy nhập đồng thời bởi nhiều tiến trình khác nhau, làm sao để kết quả cuối cùng của các thao tác của tất cả các tiến trình là nhất quán cho tất cả các tiến trình.
6.2.1. Nhất quán chặt (Strict consistency)
Mô hình thoả mãn điều kiện sau:
Mọi thao tác đọc trên khoản mục dữ liệu x đều trả về kết quả của thao tác ghi gần nhất trên x.
Hình 9 (a) Kho dữ liệu nhất quán chặt (b) Kho dữ liệu không nhất quán chặt.
Trong đó :Wi(x)a: Tiến trình Pi ghi giá trị a vào khoản mục dữ liệu x.
Ri(x)b: Tiến trình Pi đọc giá trị khoản mục dữ liệu x thu được kết quả b.
6.2.2. Nhất quán tuần tự và nhất quán tuyến tính
Mô hình nhất quán tuần tự yếu hơn mô hình nhất quán chặt. Nó thoả mãn điều kiện sau:
Kết quả của bất kì sự thực hiện nào cũng giống nhau nếu các thao tác (đọc, ghi) bởi tất cả tiến trình trong kho dữ liệu được thực hiện theo một thứ tự tuần tự nào đó và các thao tác của một tiến trình riêng biệt xuất hiện theo đúng thứ tự được chỉ rõ bởi chương trình.
Điều này có nghĩa là có nhiều thứ tự thực hiện thao tác được chấp nhận nhưng các tiền trình phải có thứ tự thực hiện thao tác giống nhau.
Hình 10 (a) Kho dữ liệu nhất quán tuần tự (b) Kho dữ liệu không nhất quán tuần tự.
Mô hình nhất quán tuyến tính yếu hơn mô hình nhất quán chặt nhưng mạnh hơn mô hình nhất quán tuần tự. Ngoài thoả mãn các điều kiện của nhất quán tuần tự, nó bổ sung thêm điều kiện:
Nếu tsop1(x) < tsop2(y) thì thao tác op1(x) phải được thực hiện trước op2(y) trong chuỗi thao tác (tsop1(x) là nhãn thời gian của thao tác op1(x)).
6.2.3. Nhất quán nhân quả (Causal consistency)
Mô hình này lỏng lẻo hơn mô hình nhất quán tuần tự. Nó đòi hỏi thứ tự thực hiện của các thao tác nhân quả phải giống nhau đối với tất cả các tiến trình. Khái niệm nhân quả được hiểu như sau: Nếu sự kiện b được gây ra hoặc bị tác động bởi một sự kiện a xảy ra sớm hơn thì quan hệ nhân quả đòi hỏi mọi thực thể khác phải “nhìn” thấy a trước rồi thấy b. Điều kiện của nhất quán nhân quả:
Các thao tác ghi có quan hệ nhân quả phải được nhìn thấy bởi tất cả các tiến trình khác theo một thứ tự. Các thao tác ghi đồng thời có thể nhìn thấy theo thứ tự khác nhau trên các máy khác nhau.
Hình 11. (a) Kho dữ liệu nhất quán nhân quả (b) Kho dữ liệu không nhất quán nhân quả.
6.2.4. Nhất quán FIFO (FIFO consistency)
Nhất quán FIFO lỏng lẻo hơn các mô hình kể trên. Nó chỉ đòi hỏi đảm bảo thứ tự thực hiện các thao tác của một tiến trình đơn. Nó thoả mãn điều kiện sau:
Các thao tác ghi của một tiến trình đơn phải được tất cả các tiến trình khác nhìn thấy theo cùng một trật tự mà nó đề ra. Nhưng các thao tác ghi bởi nhiều tiến trình khác nhau có thể được nhìn thấy theo những trật tự khác nhau bởi các tiến trình khác nhau.
Hình 12. Một chuỗi sự kiện của nhất quán FIFO.
6.2.5. Nhất quán yếu (Weak consistency)
Mô hình nhất quán yếu chỉ đảm bảo tính nhất quán tại thời điểm ngay sau các điểm đồng bộ hoá. Mô hình này có ba đặc điểm sau:
Việc truy cập đến một biến đồng bộ hóa được liên kết với kho dữ liệu nhất quán tuần tự.
Không có thao tác nào trên các biến đồng bộ hóa được phép thực hiện cho đến khi tất cả các thao tác ghi trước đó được hoàn thành ở mọi nơi.
Không có thao tác đọc hay ghi dữ liệu lên các mục dữ liệu nào được phép thực hiện cho đến khi tất cả các thao tác trước đó trên các biến đồng bộ hóa được thực hiện.
Hình 13 (a)Chuỗi sự kiện nhất quán yếu (b) Chuỗi sự kiện không nhất quán yếu.
6.2.6. Nhất quán đi ra (Release consistency)
Bổ sung thêm hai lệnh: lệnh acquire để khai báo muốn vào vùng găng (critial region) và lệnh release để khai báo muốn đi ra khỏi vùng găng. Hai lệnh này có hai cách thực thi khác nhau như: bằng biến hoặc bằng lệnh đặc biệt. Hai thao tác này chỉ thực hiện với các dữ liệu dùng chung chứ không áp dụng cho tất cả các dữ liệu.
Mô hình nhất quán đi ra thỏa mãn các điều kiện sau:
Trước khi thực hiện một thao tác đọc hay ghi lên dữ liệu chia sẻ thì tất cả các thao tác acquire do tiến trình này thực hiện trước đó phải hoàn tất.
Trước khi một thao tác release được phép thực hiện thì tất cả các thao tác đọc và ghi do tiến trình này thực hiện trước đó phải được hoàn tất.
Truy cập vào các biến đồng bộ hóa là nhất quán FIFO (Không yêu cầu nhất quán tuần tự).
Hình 14: Trình tự sự kiện theo mô hình nhất quán đi ra.
6.3. Các mô hình nhất quán lấy client làm trung tâm
Các mô hình nhất quán loại này đặt ngữ cảnh là một tiến trình cần phải thao tác trên nhiều bản sao khác nhau của kho dữ liệu, khi đó cần phải làm gì để đảm bảo được tính nhất quán của các bản sao này.
6.3.1. Nhất quán cuối cùng (Eventual consistency)
Trong phần này, ta giả định rằng kho dữ liệu không có các cập nhật đồng thời, hoặc nếu có thì cũng có thể dễ dàng giải quyết, đồng thời các tiến trình chủ yếu chỉ thực hiện thao tác đọc dữ liệu. Khi đó, nếu trong một khoảng thời gian dài không có cập nhật, các kho dữ liệu sẽ tiến tới trạng thái nhất quán nhờ việc lan truyền cập nhật giữa các bản sao. Loại nhất quán này gọi là nhất quán cuối cùng (eventual consistency). Loại nhất quán này chỉ đảm bảo được cho từng client riêng biệt, nghĩa là trong các thời điểm khác nhau, client sẽ truy cập vào các bản sao khác nhau của kho dữ liệu, nhất quán cuối cùng đảm bảo client thấy được sự nhất quán giữa các bản sao đó. Không thể đảm bảo được các truy cập đồng thời của các client khác nhau cũng nhất quán.
6.3.2. Nhất quán đọc đều (Monotonic Reads consistency)
Nhất quán đọc đều phải đảm bảo điều kiện sau:
Một tiến trình thực hiện thao tác đọc trên một khoản mục dữ liệu x thì phải đảm bảo bất kì thao tác đọc nào trên x của tiến trình đó cũng đều cho cùng một kết quả hay kết quả mới hơn.
Nhất quán đọc đều đảm bảo rằng một client sẽ luôn nhìn thấy những dữ liệu hiện hành hoặc mới hơn và không phải nhìn thấy những dữ liệu cũ hơn những gì mà họ đã đọc trước đó. Điều đó có nghĩa là khi một client thực hiện một thao tác đọc trên một bản sao rồi sau đó lại đọc trên một bản sao khác thì bản sao thứ hai kia ít nhất cũng phải được ghi giống với bản sao đầu tiên. Mô hình này chính là nhất quán FIFO nhưng giới hạn chỉ áp dụng đối với một client.
Hình 15. (a) Kho dữ liệu nhất quán đọc đều (b) Kho dữ liệu không nhất quán đọc đều.
6.3.3. Nhất quán ghi đều (Monotonic Writes consistency)
Nhất quán ghi đều phải đảm bảo điều kiện sau:
Thao tác ghi trên mục dữ liệu x của một tiến trình phải được hoàn thành trước bất kỳ một thao tác ghi nào khác trên x cũng bởi tiến trình đó.
6.3.4. Nhất quán đọc thao tác ghi (Read your writes consistency)
Trong mô hình này, người dùng được đảm bảo luôn nhìn thấy những kết quả ghi mới nhất:
Tác động của một thao tác ghi của một tiến trình lên khoản mục dữ liệu x sẽ luôn được nhìn thấy bởi một thao tác đọc tiếp theo trên x cũng của tiến trình đó.
Hình 16. (a) Kho dữ liệu nhất quán đọc kết quả ghi (b) Kho dữ liệu không nhất quán đọc kết quả ghi.
6.3.5. Nhất quán ghi theo sau đọc (Writes follow reads consistency)
Mô hình này thoả mãn điều kiện:
Một thao tác ghi của một tiến trình trên khoản mục dữ liệu x theo sau một thao tác đọc x của tiến trình đó, được đảm bảo là xảy ra trên giá trị bằng hoặc mới hơn giá trị của x đã đọc.
6.4. Các giao thức phân phối
6.4.1 Đặt các bản sao (replica placement)
Phân loại theo phương pháp xếp đặt, có 3 loại bản sao:
Các bản sao thường trực.
Bản sao khởi đầu từ server:
Các bản sao khởi đầu từ client:
6.4.2 Lan truyền cập nhật
Cập nhật đẩy (Push-based approach):Trong giao thức này server là chủ động, mỗi khi có cập nhật, server sẽ đẩy các dữ liệu cập nhật về cho client. Nhược điểm của phương pháp này là server cần phải giữ danh sách các client để lan truyền khi có cập nhật.
Cập nhật kéo (Pull-based approach):Giao thức này thường được sử dụng kết hợp với client caches. Client luôn luôn chủ động hỏi server có cập nhật nào hay không. Khi có cập nhật, client sẽ lấy dữ liệu cập nhật về và bổ sung vào client caches.
Truyền thông điểm - điểm (unicast) và điểm - nhiều điểm (multicast):Truyền thông điểm – điểm phù hợp với lan truyền cập nhật kéo, khi đó client là phía chủ động tạo kết nối. Truyền thông điểm – nhiều điểm phù hợp với lan truyền cập nhật kéo, nhờ có cơ chế broadcast của phần cứng, tốc độ lan truyền cập nhật nhanh không kém truyền thông điểm – điểm.
6.4.3 Các giao thức bệnh dịch
Ý tưởng cơ bản của giao thức 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.
6.5 Các giao thức nhất quán
6.5.1. Primary-based protocols
a. Các giao thức ghi từ xa
Trong 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. 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. Ưu điểm của giao thức này là 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ự.
b. Các giao thức ghi cục bộ
Trong giao thức này một bản sao của khoản mục dữ liệu được duy trì. Khi có yêu cầu thao tác ghi, khoản mục dữ liệu được nhân bản từ server từ xa chuyển đến server cục bộ. Một vấn đề đặt ra cho các tiến trình sử dụng giao thức này 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.
6.5. 2. Các giao thức Replicated-write.
a. Giao thức nhân bản chủ động
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 truyền thông điểm – điểm hay điểm – nhiều điểm. Ư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. 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 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 chỉ có một yêu cầu và một phản hồi được gửi đi.
b. Giao thức Quorumbased
Trong 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.
Tất cả các khoản mục dữ liệu được kết hợp với một số hiệu phiên bản (version number). Mỗi lần một mục bị sửa đổi thì số hiệu 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 diện đọc và số đại diện ghi, hai số đại diện này sẽ xác định số lượng bản sao phải được liên hệ trước khi thực hiện thao tác đọc và ghi. Số đại diện đọc phải lớn hơn ½ tổng số bản sao, vì thế tổng của số đại diện đọc và ghi phải lớn hơn tổng số bản sao. 6.5.3. Cache-coherence protocols
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. Với chiến lược phát hiện sự cố kết, có 2 giải pháp khác nhau.
Chương 7: Chịu lỗi
Một trong các đặc điểm của các hệ thống phân tán phân biệt so với các hệ thống máy đơn là khái niệm lỗi một phần. Lỗi một phần xảy ra khi một thành phần của hệ thống bị lỗi, nhưng lỗi này có thể tác động đến việc vận hành của hệ thống, thậm chí là toàn bộ các ứng dụng. Do đó mục tiêu của hệ thống phân tán là có thể phục hồi hệ thống từ các lỗi một phần mà không tác động nghiêm trọng đến hiệu năng chung. Phần này sẽ giới thiệu các kỹ thuật dung lỗi cho hệ thống phân tán.
7.1 Giới thiệu dung lỗi
Kỹ thuật chủ chốt để kiểm soát lỗi là tính dư thừa.
7.1.1 Các khái niệm cơ bản
Dung lỗi nghĩa là một hệ thống có thể cung cấp các dịch vụ của nó ngay cả khi có sự hiện diện của lỗi.
Phân loại lỗi:
Lỗi tạm thời: xảy ra một lần rồi biến mất
Lỗi không thường xuyên: thi thoảng xuất hiện, biến mất rồi sau đó lại xuất hiện lại.
Lỗi cố định: tiếp tục tồn tại cho đến khi thành phần lỗi được sửa.
7.1.2 Các mô hình lỗi
Để đánh giá mức độ nghiêm trọng của lỗi, một số cách phân loại lỗi được phát triển. Một trong số đó như bảng sau
Kiểu lỗi
Mô tả
Lỗi sụp đổ
Máy chủ dừng hoạt động nhưng trước đó vẫn làm việc đúng đắn
Lỗi bỏ sót
Bỏ sót nhận
Bỏ sót gửi
Máy chủ không trả lời yêu cầu gửi đến
Máy chủ không nhận được thống điệp gửi đến
Máy chủ không gửi thông điệp
Lỗi thời gian
Phản hồi của máy chủ nằm ngoài khoảng thời gian được chỉ ra
Lỗi phản hồi
Lỗi giá trị
Lỗi chuyển trạng thái
Phản hồi của máy chủ không đúng
Giá trị phản hồi sai
Máy chủ chệch khỏi luồng điều khiển đúng
Lỗi tùy tiện (Byzantine)
Máy chủ có thể tự ý phản hồi vào thời điểm tùy ý
Hình 17: Các kiểu lỗi khác nhau
7.1.3 Che lỗi bằng dư thừa
Có ba kiểu dư thừa:
Dư thừa dữ liệu: thêm các bit vào để phục hồi các bit lỗi
Dư thừa thời gian: thực hiện lại một hành động khi có lỗi, hữu ích trong giao dịch
Dư thừa vật lý:thêm thiết bị và tiến trình khi một số thành phần hoạt động sai hệ thống vẫn hoạt động tốt
7.2 Độ hồi phục tiến trình
Để khắc phục lỗi tiến trình, các tiến trình được nhân bản thành các nhóm.
7.2.1 Vấn đề thiết kế
Một vài tiến trình giống nhau được tổ chức thành các nhóm. Khi thông điệp được gửi tớ, tất cả các thành viên đều nhận được để khi một tiến trình bị lỗi, tiến trình khác có thể khôi phục lại. Một tập các nhóm như là một trừu tượng hóa đơn và các nhóm tiến trình có thể là động, được sinh ra và hủy đi.
Cấu trúc nhóm:
Nhóm ngang hàng
Nhóm phân cấp
7.2.2 Che lỗi và nhân bản
Tùy thuộc loại lỗi và mức độ che lỗi để xác định số nhân bản cần thiết. Che lỗi xảy ra bởi k thành phần thì cần k+1 bản sao.Với lỗi Byzantine thì cần 2k+1 bản sao.
7.2.3 Thỏa thuận trong các hệ thống lỗi
Khi có lỗi xảy ra các tiến trình cần trao đổi với nhau để đi đến một thỏa thuận vì lúc đó các tiến trình không nhất quán..
Với lỗi Byzantine, Lamport đề xuất thuật toán đệ quy để giải quyết.
Hình 18: Lỗi Byzantine với 3 tướng trung thành, 1 tướng lừa dối.
(a) Các tướng công bố sức mạnh quân đội. (b) các vector thu thập dựa trên (a). (c) Vector mà mỗi tướng nhận được
7.3 Giao tiếp khách - chủ tin cậy
7.3.1 Giao tiếp điểm – điểm
Dùng các giao thức tin cậy như TCP. Khi xảy ra đứt đường truyền, trình khách được thông báo
7.3.2 Ngữ nghĩa RPC t._.
Các file đính kèm theo tài liệu này:
- DAN268.doc