Đề cương ôn tập Hệ thống phân tán
1) Gọi thủ tục từ xa (RPC) và RPC trong mô hình client-server
a. Tổng quan về RPC (Remote procedure call)
Khi một tiến trình trên máy A muốn thực hiện một thủ tục nào đó nằm trên một máy B khác thì nó sẽ thực hiện một lời gọi thủ tục từ xa tới máy B. Thủ tục đó sẽ được thực hiện ở máy B dựa trên các tham số được truyền đến từ máy A và kết quả sẽ được truyền trở lại cho máy A tương ứng.
Trong mô hình client – server thì lời gọi thủ tục từ xa được thực hiện qua các bước sau:
− Tiến trình muốn thực hiện thủ tục ở máy client sẽ gọi client stub.
− Client stub sẽ tạo một bản tin và có lời gọi đến hệ điều hành của client đó.
− Hệ điều hành của máy client sẽ gửi bản tin đó tới hệ điều hành của máy server.
− Hệ điều hành của máy server sẽ gửi bản tin đó tới server stub.
− Server stub lấy các thông tin của gói tin và gọi server tương ứng.
− Server thực hiện công việc được yêu cầu và trả kết quả về cho server stub.
− Server stub đóng gói kết quả vào bản tin rồi gọi hệ điều hành của server đó.
− Hệ điều hành của máy server này sẽ gửi bản tin kết quả đó đến hệ điều hành của máy client.
− Hệ điều hành của máy client sẽ gửi bản tin cho client stub.
− Client stub sẽ mở gói tin kết quả và trả về cho client.
Trong đó, client stub và server stub ở máy client và server là thành phần nhằm giảm nhẹ công việc cho client và server, làm cho hệ thống hoạt động một cách trong suốt hơn.
b. Các thao tác gọi thủ tục từ xa RPC
· Đóng gói các tham số: việc đóng gói các tham số để chuẩn bị truyền đi do client stub thực hiện. Client stub sẽ sắp xếp các tham số và đưa vào hàng đợi và quá trình này được gọi là parameter marshaling. Các tham số được truyền đi giúp cho server hiểu được công việc mình cần thực hiện tương ứng là gì để xác định lời gọi thủ tục thích hợp.
· Truyền tham số: việc truyền tham số từ client tới. Có 2 cách truyền: truyền tham biến và truyền tham trị.
− Truyền tham trị: các tham số được truyền đi là các giá trị cụ thể. Các thủ tục được gọi đến sẽ coi các tham biến được truyền kiểu tham trị như là các biến được khởi tạo cục bộ, có thể thay đổi giá trị nhưng lại không ảnh hưởng tới giá trị gốc trong lần gọi sau. Vấn đề đặt ra khi truyền tham trị là yêu cầu giữa các máy phải có sự đồng nhất về việc biểu diễn dữ liệu và các kiểu dữ liệu.
− Truyền tham biến: các tham số được truyền đi là con trỏ hay biến chứa địa chỉ của nơi chứa giá trị thực của chúng. Các thủ tục được gọi sẽ cắn cứ vào địa chỉ này để tham chiếu đến giá trị khi tính toán. Khi giá trị này bị thay đổi trong khi thực hiện thủ tục thì sẽ được thông báo cho client và các lần gọi sau sẽ dùng giá trị mới đó.
c. Các mô hình gọi thủ tục từ xa RPC mở rộng
· Gọi thủ tục từ xa dị bộ (Asynchronous RPC)
Tư tưởng thực hiện là : client gửi tới server lời gọi thủ tục và chờ bản tin chấp nhận từ server. Phía server sẽ gửi bản tin chấp nhận về cho client thông báo đã nhận được yêu cầu và bắt đầu thực hiện yêu cầu RPC đó. Lúc này client sẽ tiếp tục thực hiện công việc của mình mà không chờ kết quả từ server như ở RPC truyền thống.
· Gọi thủ tục từ xa đồng bộ trễ (Deferred synchronous RPC)
Thực hiện hai lời gọi, một từ client và một từ server.
Client gửi tới server lời gọi thủ tục và chờ bản tin chấp nhận từ server. Phía server sẽ gửi bản tin chấp nhận về cho client thông báo đã nhận được yêu cầu và bắt đầu thực hiện yêu cầu gọi thủ tục từ xa RPC đó. Lúc này client sẽ tiếp tục thực hiện công việc của mình. Khi thực hiện thủ tục xong, server sẽ thực hiện lời gọi tới client báo nhận lấy kết quả. Client thực hiện ngắt, nhận kết quả và gửi lại cho server bản tin thông báo đã nhận kết quả thành công.
· Gọi thủ tục từ xa đơn tuyến (one-way RPC)
Sau khi thực hiện lời gọi thủ tục từ xa tới server, client không chờ đợi thông báo nhận yêu cầu thành công từ server mà tiếp tục thực hiện ngay các công việc khác của mình. Đó là RPC đơn tuyến.
2) Truyền thông đồng bộ và truyền thông không đồng bộ
a. Truyền thông đồng bộ (Synchronous communication)
Khi trạm gửi đi một bản tin thì nó sẽ ở trạng thái khóa (block) cho đến khi nhận được thông báo bản tin đó đã đến đích thành công.
b. Truyền thông không đồng bộ (Asynchronous commnunication)
Khi trạm gửi đi bản tin, nó sẽ tiếp tục thực hiện công việc của mình. Điều này cũng có nghĩa là bản tin đó được lưu lại trên bộ nhớ đệm của trạm gửi hoặc của server cục bộ.
3) Biểu diễn không gian tên
a. Tên (name)
Là xâu các bit hoặc kí tự dùng để tham chiếu đến một thực thể trong hệ phân tán.
b. Địa chỉ (address)
Khi truy cập đến thực thể ta sử dụng điểm truy cập (access point). Các điểm truy cập này cũng phải được đặt tên và tên đó chính là địa chỉ của nó. Như vậy địa chỉ của thực thể chính là tên của điểm truy cập thực thể tương ứng.
c. Định danh (identifiers)
Đây cũng là một kiểu tên đặc biệt. Việc định danh một tên phải thỏa mãn 3 tính chất sau:
− Mỗi thực thể chỉ được tham chiếu bởi duy nhất một định danh ID.
− Mỗi ID tham chiếu tới một thực thể.
− ID đó không được gán cho một thực thể khác.
d. Không gian tên (name space)
Dùng để biểu diễn tất cả các tên. Nếu xét về mặt hình học thì đây là một đồ thị có hướng, gồm các nút và các cung, gọi là đồ thị tên (naming graph).
Đồ thị có cấu trúc: mỗi nút lá miêu tả một thực thể. Mỗi nút directory gắn với nhiều nút khác; lưu trữ trong bảng directory, bảng này là tập các cặp (label, indetifier).
e. Tên thân thiện (human-friendly name)
Là các tên được đặt một cách dễ hiểu, thân thuộc với con người.
4) Độ phân giải tên, cơ chế closure cho URL
a. Độ phân giải tên
Không gian tên đưa ra kĩ thuật lưu trữ và tìm kiếm các tên trên nó một cách dễ dàng. Một trong những phương pháp hay dùng là sử dụng đường dẫn tên (path name). Quá trình tiềm kiếm tên trong không gian tên được gọi là phân giải tên (name resolution). Quá trình phân giải tên trả về định danh một nút.
Tên đường dẫn: N: <label1, label2,…., labeln>
Tên đường dẫn tuyệt đối: nút đầu tiên là root
Tên đường dẫn tương đối: nút đầu tiên bất kỳ
Closure machanism: là kĩ thuật cho ta biết quá trình tiềm kiếm tên được bắt đầu như thế nào và bắt đầu ở đâu.
Linking: kĩ thuật này sủ dụng bí danh_tên giống với tên của thực thể
Với kĩ thuật này cho phép nhiều đường dẫn cùng tham chiếu đến cùng 1 nút trên đồ thị.Một cách tiếp cận khác là dùng 1 nút lá không pải để lưu trữ địa chỉ hay trạng thái của thực thể mà để lưu trữ đường dẫn tuyệt đối tới thực thể đó.
Mounting: là kĩ thuật được thực hiện khi tìm kiếm trên hai không gian tên.
Một nút thư mục được gọi là một mount point (điểm gắn kết) lưu giữ id (hoặc các thông tin cần thiết cho việc xác định và truy nhập) của một nút thư mục bên phía không gian tên cần gắn kết (mounting point)
• Có 2 không gian tên NS1, NS2. Để mount 1 thực thể bên ngoài, ta cần:
– Tên của giao thức truy cập (được xác định để thực hiện giao thức truyền thông)
– Tên của server(xác định địa chỉ server)
– Tên của mounting point (xác định id của nút trong không gian tên bên ngoài)
– Ví dụ về mouting 1 không gian tên từ xa nhờ 1 giao thức truy cập
b. Cơ chế closure cho URL (Địa chỉ của các files/resources trên mạng)
− Extract định danh từ URL, ex. chuỗi ftp:
− Tham chiếu chuỗi trong bảng để tìm giao diện tới việc thực hiện giao thức FTP cục bộ
− Extract host name từ URL (ex. www.uct.edu.vn) và chuyển nó đến local DNS name server
− Phần cuối cùng của URL (file) sẽ được chuyển đến identified host
5) Phân phối không gian tên
Trong hệ phân tán, việc quản lý tên được thực hiện bằng cách phân thành các mức:
· Mức Global: chứa những nút thư mục ở mức gốc cao (gốc và con của nó). Trong lớp này các nút thư mục ít thay đổi. Khả năng sẵn sàng ở lớp Global được yêu cầu cao hơn so với các lớp còn lại. Nếu name server của lớp này bị lỗi thì việc phân giải tên không thể thực hiện.
· Mức Administrational: chứa những nút thư mục ở mức trung gian, nó có thể được nhóm thành các nhóm, và mỗi nhóm có thể được chia cho những khu vực quản trị khác nhau. Các nút ở trong nhóm này cũng ít khi thay đổi. Khả năng sẵn sàng của name server trong lớp administrational là rất quan trọng đối với các client do name server quản lý. Vì nếu server này lỗi thì có rất nhiều các tài nguyên không thể truy cập.
· Mức Managerial: chứa những nút thư mục ở mức thấp. Các nút trong mức này thay đổi khá thường xuyên. Ví dụ như các host trong một mạng Lan. Yêu cầu đổi tính sẵn sàng của name server của lớp managerial ít khắt khe hơn so với 2 lớp trên. Song về hiệu năng thì yêu cầu đối với lớp này cao hơn do phải thường xuyên cập nhật thay đổi.
Không gian tên được chia thành các thành phần không chờm nhau gọi là zones, mỗi zone được thực hiện bởi các name server tách biệt
6) Thực hiện phân giải tên (tương tác và đệ quy)
a. Phân giải tên tương tác (interactive name resolution):
Server chỉ phân giải các label tương ứng với lớp và xác định địa chỉ server tiếp theo
b. Phân giải tên đệ quy (recursive name resolution):
Name server sẽ gửi kết quả đến name server tiếp theo mà nó tìm thấy… và tiếp tục…
7) Đồng bộ bằng giải thuật Berkeley và giải thuật trung bình
a. Giải thuật Berkeley
Tư tưởng giải thuật
• Server sẽ chủ động cho các máy khác biết thời gian chuẩn của mình CUTC sau đó sẽ yêu cầu thông tin về thời gian của các client.
• Client sẽ trả lời khoảng thời gian chênh lệch giữa nó và server
• Server sẽ tính khoảng thời gian mà các client so với thời gian chuẩn của server lúc đó (trung bình) và gửi cho các máy khách cách điều chỉnh thời gian cho phù hợp.
b. Giải thuật trung bình
Giải thuật này thực hiện Chia thời gian thành những khoảng đồng bộ cố định.
Khoảng thời gian I sẽ bắt đầu từ thời điểm (To + i.R) và chạy đến khi To+(i+1)R
Với To là thời điểm xác định trước và R là một biến hệ thống
Vào thời điểm bắt đầu của mỗi lần đồng bộ tất cả các máy của mạng sẽ broadcast thời gian của mình
Sau khi broadcast nó sẽ bắt đầu thu thập thời gian mà các máy khác gửi đến trong khoảng thời gian S. Sau đó bỏ đi giá trị lớn nhất và nhỏ nhất rồi tính trung bình của các giá trị thời gian còn lại
8) Các giải thuật bầu chọn (giải thuật áp đảo, giải thuật vòng, giải thuật tập trung, giải thuật phân tán)
Khi tiến trình điều phối gặp lỗi thì sẽ phải có quá trình bầu chọn để chọn ra 1 tiến trình khác làm điều phối thay cho nó.
a. Giải thuật áp đảo( Bully Algorithm)
• Giả thiết
− Mỗi một tiến trình đều có một ID duy nhất
− Tất cả các tiến trình khác đều có thể biết được số ID và địa chỉ của mỗi tiến trình trong hệ thống
− Chọn một tiến trình có ID cao nhất làm khóa .Tiến trình sẽ khởi động việc bầu chọn nếu như nó khôi phục lại sau quá trình xảy ra lỗi hoặc tiến trình điều phối bị trục trặc
• Các bước của giải thuật
− P gửi thông điệp ELEC đến tất cả các tiến trình có ID cao hơn
− Nếu không có tiến trình nào phản hồi thì P sẽ trở thành tiến trình điều phối
− Nếu có một tiến trình có ID cao hơn phản hồi thì nó sẽ đảm nhiệm vai trò điều phối
Ví dụ theo giải thuật áp đảo
b. Giải thuật vòng
• Giả thiết
Các tiến trình có một ID duy nhất và được sắp xếp trên 1 vòng tròn Logic. Mỗi một tiến trình có thể nhận biết được tiến trình bên cạnh mình
• Các bước thuật toán:
− Một tiến trình bắt đầu gửi thông điệp ELEC tới các nút còn tồn tại gần nhất, quá trình gửi theo 1 hướng nhất định. Thăm dò liên tiếp trên vòng cho đến khi tìm được 1 nút còn tồn tại.
− Mỗi một tiến trình sẽ gắn ID của mình vào thông điệp gửi.
− Cuối cùng sẽ chọn ra 1 tiến trình có ID cao nhất trong số các tiến trình còn hoạt động và gửi thông điệp điều phối cho tiến trình đó
c. Giải thuật tập trung
· Giả thiết
Mỗi tiến trình có 1 số ID duy nhất.Tiến trình được bầu chọn làm điều phối là tiến trình có số hiệu ID cao nhất.1 tiến trình được chọn là coordinator
· Nội dung thuật toán
Khi một tiến trình muốn truy cập tài nguyên…
− Nó gửi thông báo yêu cầu tới coordinator cho biết tài nguyên mà nó muốn truy cập
− Nếu không có tiến trình nào đang truy cập tài nguyên
§ Cho phép truy cập
− Trường hợp có tiến trình khác đang truy cập tài nguyên
§ Coordinator trì hoãn reply – blocking tiến trình (chờ reply)
§ Hoặc có thể gửi thông báo permission denied
§ Chuyển thông báo vào hàng đợi
− Khi tiến trình kia kết thúc truy cập tài nguyên
§ Coordinator lấy request (đầu tiên) từ hàng đợi và gửi thông báo cho phép truy cập đến tiến trình yêu cầu
− Shortcoming ….(coordinator crash)
Sách khác viết: Nội dưng thuật toán:
− Khi 1 tiến trình nào đó cần vào vùng giới hạn nó sẽ gửi 1 thông điệp xin cấp quyền.Nếu không có 1 tiến trình nào đang trong vùng giới hạn thì tiến trình điều phối sẽ gửi phản hồi cho phép.CÒn nếu có 1 tiến trình khác đang ở trong vùng tới hạn rồi thì tiến trình điều phối sẽ gửi thông điệp từ chối và đưa tiến trình này vào hàng đợi cho đến khi không có tiến trình nào trong vùng tới hạn nữa
− Khi 1 tiến trình rời khỏi vùng giới hạn nó sẽ gửi 1 thông điệp đến tiến trình điều phối thông báo trả lại quyền truy cập.Lúc này tiến trình điều phối sẽ gửi quyền truy cập cho tiến trình đầu tiên trong hành đợi truy cập
Đánh giá:
− Thuật toán này có đảm bảo sự tồn tại duy nhất 1 tiến trình trong vùng tới hạn và chỉ cần 3 thông điệp để thiết lập:Request-Grant-Release.
− Nhược điểm duy nhất là nếu tiến trình điều phối bị hỏng thì hệ thống sẽ sụp đổ.Vì nếu 1 tiến trình đang trong trạng thái Block nó sẽ không thể biết được tiến trình điều phối có bị Dead hay không.Trong 1 hệ thống lớn nếu chỉ có 1 tiến trình điều phối sẽ xuất hiện hiện tượng thắt cổ chai.
d. Giải thuật phân tán
• Tiến trình muốn truy cập tài nguyên thì
– Nó tạo thông báo chứa tên tài nguyên, số hiệu tiến trình và thời gian logic của nó
– Gửi thông báo tới các tiến trình khác
• Khi tiến trình khác nhận được thông báo ,sẽ xảy ra 3 tình huống:
– Nếu bên nhận không truy cập tài nguyên à reply ok(gửi thông điệp OK cho bên gửi)
– Nếu bên nhận đang truy cập tài nguyên à không reply (cho vào hàng đợi yêu cầu này)
– Nếu bên nhận chuẩn bị truy cập tài nguyên à nó sẽ so sánh time stamp ,ai thấp hơn sẽ thắng
• Sau khi gửi thông báo, tiến trình sẽ chờ nhận permission ( đợi cho đến khi có trả lời càng sớm càng tốt)
• Khi thực hiện xong à gửi thông báo ok cho các tiến trình khác và xóa các tiến trình trong hàng đợi đi
Ví dụ theo giải thuật phân tán
9) Cơ chế khôi phục 2-phase commit
· Hệ thống bao gồm coordinator and cohorts
− Coordinator gửi các thông báo Commit_Request, Commit, and Abort
− Cohorts gửi thông báo Agreed to commit và Abort
· Coordinator
− Gửi thông báo Commit_Request messages tới tất cả cohorts and và chờ replies
− Nếu tất cả corhots trả lời Agreed à coordinator writes COMMIT log à gửi thông báo Commit tới tất cả các cohort và chờ Acknowledgement
− Nếu bất cứ cohort nào trả lời Abort, nó sẽ gửi Abort tới tất cả các cohort và bỏ qua
− Khi tất cả cohort chấp nhận thông báo Commit à nó sẽ write COMPLETE log
− Nếu nó không nhận được reply à gửi lại request
· Cohorts
− Trên cơ sở nhận được Commit_Request reply (Agree hay Abort) à và chờ reply từ coordinator
− Nếu coordinator trả lời Commit à cohort sẽ commit
− Nếu coordinator trả lời Abort, nó update và bỏ qua
− Trong cả hai trường hợp nó sẽ gửi ACK tới coordinator
· Nếu một trong hai bị lỗi hoặc mất thông báo à transaction không Abort hoặc commit
10)Distributed file system
• NFS (network file system): hoạt động trên Virtual File System
Ví dụ: Google file system
• Chia file vào các chunks 64MB và replicate/distribute các chunks qua các server
– Master chỉ chứa bảng (tên file, chunk server) trong bộ nhớ chính
Bạn đang đọc truyện trên: Truyen2U.Pro