Bài giảng Hệ phân tán - Đồng bộ hóa và phối hợp

 / thuật toán phân tán Đồng hồ vật lý / đồng hồ lôgic Có tính tương đối Đồng hồ Đồng hồ máy tính: Các dao động tinh thể với tần số biết trước Các dao động gây ra các ngắt đồng hồ Ngắt đồng hồ cập nhật đồng hồ Clock skew – lệch giờ Tại cùng một thời điểm, đồng hồ ở các máy khác nhau báo giờ khác nhau Timestampt – nhãn thời gian Dùng để ghi lại thời điểm một sự kiện xảy ra Lôgic / vật lý Đồng hồ vật lý Đồng bộ hóa bằng đồng hồ vật lý Ví dụ: Thực hiện hành động tại một thời điểm chính xác (tắt/bật đèn, đóng/mở cổng) Ghi nhật trình các sự kiện (phục vụ bảo mật, tìm lỗi, xây dựng hồ sơ) Theo dõi (các camera khác nhau để theo dõi một vật thể đang di chuyển) make (lập trình tại máy này, dịch tại máy khác) Dựa vào thời gian thực Cp(t): giờ hiện hành (tại thời điểm t giờ UTC) tại máy p Lý tưởng: Cp(t) = t Đồng hồ chạy nhanh/chậm → phải định kì đồng bộ theo UTC Đồng bộ hóa đồng hồ vật lý Đồng bộ ngoài – external synchronization Đồng hồ chỉnh giờ theo một nguồn ngoài Chỉnh giờ theo UTC sau mỗi khoảng thời gian dài δ giây Chính xác trong phạm vi δ Đồng bộ trong - internal synchronization Các đồng hồ trong một hệ thống chỉnh giờ theo nhau Đồng bộ với nhau nhưng có thể cùng lệch giờ với bên ngoài Dùng time server Server có giờ đúng Server tính ra giờ đúng Thuật toán Cristian Time server Có thiết bị nhận giờ từ nguồn UTC Bị động Thuật toán Client định kỳ gửi yêu cầu hỏi giờ t + Không chỉnh lùi đồng hồ Tính đến độ trễ truyền tin và xử lý ngắt (T1 – T0)/2, hoặc Đo một loạt và lấy trung bình độ trễ Thuật toán Berkeley master slave Network Time Protocol (NTP) Mạng các server cấu trúc thành cây Server sơ cấp có đồng hồ UTC Server cấp 2 nối với server sơ cấp, chỉnh theo server sơ cấp v.v.. Các kiểu đồng bộ hóa: Multicast: server định kì gửi giờ cho các server chạy tại các máy khác trong mạng LAN độ chính xác thấp Procedure call: tương tự thuật toán Cristian, độ chính xác tương đối Symmetric: đồng bộ hóa giữa các cặp server ngang hàng, độ chính xác cao nhất Đồng hồ lôgic Thứ tự của các sự kiện quan trọng hơn thời gian vật lý Các sự kiện (VD: thay đổi trạng thái) trong một tiến trình được sắp thứ tự Các tiến trình cần thống nhất về thứ tự của các sự kiện có quan hệ nhân quả với nhau (vd: gửi và nhận thông điệp) Thứ tự địa phương: Hệ thống có N tiến trình pi, i thuộc {1,…,N} Thứ tự sự kiện địa phương →i: nếu pi thấy e trước e’, ta có e →i e’ Thứ tự toàn cục: Quan hệ xảy-ra-trước (kí hiệu →) của Leslie Lamport Nếu tồn tại pi thấy e →i e’, thì ta có e → e’ Với mỗi thông điệp m, send(m) → receive(m) Tính bắc cầu: e → e’ và e’ → e” kéo theo e → e” Đồng hồ lôgic (2) Quan hệ → là một thứ tự bộ phận: Nếu a → b thì a dẫn đến b về mặt nhân quả các sự kiện không được sắp thứ tự được coi là các sự kiện đồng thời Ví dụ: Đồng hồ Lamport Đồng hồ lôgic Lamport: Con đếm phần mềm tính quan hệ xảy-ra-trước → Mỗi tiến trình pi giữ một đồng hồ lôgic Li Lamport timestampt: Li(e): nhãn thời gian của sự kiện e tại pi L(e): nhãn thời gian của e tại tiến trình mà nó xảy ra Thuật toán: Trước khi gắn nhãn một sự kiện tại chỗ, pi chạy Li := Li + 1 Mỗi khi một thông điệp m được gửi từ pi đến pj: pi chạy Li := Li + 1 và gửi Li cùng m pj nhận Li cùng m và chạy Lj := max( Li ,Li ) + 1, receive(m) được gắn với Lj Tính chất: a → b kéo theo L(a) < L(b) L(a) < L(b) chưa chắc có nghĩa a → b Đồng hồ lôgic sắp thứ tự toàn bộ Ví dụ: Thứ tự toàn bộ: Hoàn chỉnh thứ tự bộ phận thành thứ tự toàn bộ bằng cách gắn thêm định danh tiến trình Cho trước các timestampt địa phương Li của e và Li của e’, ta định nghĩa timestampt toàn cục (Li, i) và (Li, j) Thứ tự từ điển: (Li, i) < (Li, j) khi và chỉ khi Li < Li, hoặc Li = Li và i<j Đồng hồ Lamport Nhược điểm chính của đồng hồ Lamport: L(a) < L(b) chưa chắc có nghĩa a → b không thể rút ra quan hệ phụ thuộc nhân quả từ các nhãn thời gian L1(E11) < L3(E33), nhưng không có E11 → E33 Tại sao? Đồng hồ tăng một cách độc lập hoặc qua các thông điệp Lí do tăng con đếm đồng hồ không được lưu lại Đồng hồ vector Tại mỗi tiến trình: 01 đồng hồ cho mỗi tiến trình khác mỗi đồng hồ Vi là một vector kích thước N Vi[j] chứa kiến thức của i về đồng hồ của j Thuật toán: Khởi tạo: Vi[j] := 0 với i,j thuộc {1,…, N} Trước khi pi gắn timestampt một sự kiện, Vi[i] := Vi[i] + 1 Mỗi khi một thông điệp m được gửi từ pi đến pj: pi chạy Vi[j] := Vi[j] + 1 và gửi Vi với m. pj nhận Vi với m và trộn với đồng hồ vector của mình: Kết quả: a → b khi và chỉ khi V(a) < V(b) Trạng thái toàn cục 10.5, Coulouris Trạng thái toàn cục Xác định tính chất toàn cục Ví dụ: Distributed garbage collection Còn tồn tại tham chiếu đến một đối tượng cho trước? Distributed deadlock detection Các tiến trình có đợi nhau theo vòng tròn không? Distributed termination detection Các tiến trình đã ngừng mọi hoạt động chưa? Lát cắt nhất quán Xác định các tính chất toàn cục: Kết hợp thông tin địa phương từ các nút khác nhau Không có giờ toàn cục, làm sao biết các thông tin đó là nhất quán? Thông tin trạng thái địa phương lấy tại các thời điểm tùy ý thường không nhất quán Điều kiện nào để một tập hợp các thông tin địa phương được gọi là nhất quán về toàn cục? Lát cắt nhất quán (2) Lịch sử địa phương: N tiến trình pi, i thuộc {1,…,N} Với mỗi pi, Chuỗi sự kiện hi = {ei0, ei1, ei2,…} là lịch sử của pi Chuỗi có thể hữu hạn hoặc vô hạn eij là một sự kiện địa phương hoặc một sự kiện liên lạc Kí hiệu hik là chuỗi tiền-tố-k của hi: {ei0,…,eik-1, eik} Trạng thái của tiến trình: sik: trạng thái của tiến trình ngay trước sự kiện eik sik ghi lại tất cả các sự kiện có trong lịch sử hik-1 Do đó, si0 mô tả trạng thái khởi đầu của pi Lát cắt nhất quán (3) Lịch sử và trạng thái toàn cục: Sử dụng một cách sắp thứ tự toàn bộ, ta có thể hợp nhất tất cả các lịch sử địa phương thành lịch sử toàn cục Tương tự, ta có thể kết hợp một tập các trạng thái địa phương thành một trạng thái toàn cục: 	S = (s1,…,sN) Cách kết hợp nào của các trạng thái địa phương thì được coi là nhất quán? Lát cắt nhất quán (4) Lát cắt: Tương tự với lịch sử toàn cục, ta có thể định nghĩa các lát cắt dựa trên các tiền-tố-k: Lát cắt C tương ứng với trạng thái 	 Các sự kiện cuối cùng trong một lát cắt là biên của nó: Lát cắt nhất quán (5) Lát cắt nhất quán: Một lát cắt C được gọi là nhất quán khi và chỉ khi 	với mọi sự kiện e’ thuộc C, e → e’, thì e thuộc C Một trạng thái toàn cục được coi là nhất quán nếu nó tương ứng với một lát cắt nhất quán Chuỗi thực thi của một hệ thống có thể được xem như là một chuỗi các trạng thái toàn cục nhất quán Chandy & Lamport’s snapshot Thuật toán xác định một trạng thái toàn cục của hệ phân tán Ghi lại trạng thái địa phương của các tiến trình Xét đến các thông điệp đang được truyền Kết hợp lại là trạng thái toàn cục nhất quán Hữu ích cho việc đánh giá các tính chất toàn cục Tương tranh Tương tranh trong hệ không phân tán Các vấn đề điển hình của hệ điều hành và lập trình đa luồng Ngăn chặn các tình huống chạy đua (race condition) Đoạn mã truy nhập tài nguyên dùng chung (critical section) Loại trừ lẫn nhau (mutual exclusion) Khóa Semaphore Monitor Phải áp dụng các cơ chế một cách đúng đắn Deadlock - Đợi nhau thành chu trình Starvation – một tiến trình phải đợi vô hạn Tương tranh trong hệ phân tán Thêm thách thức: Không có tài nguyên trực tiếp dùng chung Không có trạng thái toàn cục Không có đồng hồ toàn cục Không có thuật toán tập trung Nhiều tương tranh hơn Loại trừ lẫn nhau trong hệ phân tán Truy nhập đồng thời đến các tài nguyên phân tán Phải ngăn chặn race condition tại các critical section Đòi hỏi: An toàn: tại mỗi thời điểm có tối đa 01 tiến trình chạy critical section Không phải đợi vĩnh viễn: yêu cầu vào và ra critical section chắc chắn thành công Thứ tự: các yêu cầu được xử lý theo thứ tự xảy-ra-trước Phương pháp 1: Server trung tâm Cách đơn giản nhất: Các yêu cầu vào và ra các critical section được gửi tới một server khóa Tiến trình được quyền vào khi nhận được một token Khi ra khỏi critical section, token được trả lại cho server Đặc điểm: Dễ thực hiện Khó mở rộng Server trung tâm có thể thất bại Phương pháp 2: Token ring Các tiến trình được xếp trong một cấu trúc vòng (lôgic) Một thông điệp token được chuyển dần cho nhau quanh vòng Trước khi vào critical section, tiến trình phải đợi token đến Phải giữ token cho đến khi ra khỏi critical section Tính chất: Độ trễn trung bình N/2 chặng Token chiếm băng thông Vòng vỡ khi nút hỏng hoặc kênh hỏng Phương pháp 3: dùng multicast và đồng hồ lôgic Thuật toán của Ricart & Agrawala: Mỗi tiến trình giữ một đồng hồ Lamport và có thể liên lạc theo từng cặp Tiến trình ở một trong ba trạng thái: Thả: ở ngoài critical section Muốn: đợi vào critical section Giữ: đang ở trong critical section Phương pháp 3: dùng multicast và đồng hồ lôgic Ứng xử của tiến trình: Nếu một tiến trình pi muốn vào critical process, nó multicast thông điệp (Li, pi) và đợi cho đến khi nhận được trả lời từ tất cả các tiến trình khác Nếu một tiến trình ở trạng thái Thả, nó lập tức trả lời tất cả các yêu cầu vào critical section Nếu một tiến trình ở trạng thái Giữ, nó không trả lời cho đến khi hoàn tất critical section Nếu một tiến trình ở trạng thái Muốn, nó lập tức trả lời yêu cầu nếu timestampt của yêu cầu đó nhỏ hơn timestamp của yêu cầu của chính nó Phương pháp 3: dùng multicast và đồng hồ lôgic Tính chất: Multicast dẫn đến chi phí cao về đường truyền Dễ thất bại do lỗi Đánh giá các thuật toán phân tán Các tính chất tổng quan: Hiệu năng: Số thông điệp được trao đổi Thời gian phản ứng/đợi Độ trễ Thông lượng (thoughput): 1/(độ trễ + thời gian chạy) Độ phức tạp tính toán O() Hiệu quả: Lượng tài nguyên sử dụng: bộ nhớ, CPU, v.v.. Khả năng mở rộng Độ tin cậy Số điểm thất bại (càng ít càng tốt) So sánh các thuật toán loại trừ Thông điệp trao đổi: (Số thông điệp cho mỗi lần vào/ra critical section) Trung tâm: 3 Vòng: 1 → ∞ Multicast: 2(n – 1) Độ trễ: (Thời gian trễ trước khi vào critical section) Trung tâm: 2 Vòng: 0 → n – 1 Multicast: 2(n – 1) Độ tin cậy: (Các vấn đề có thể xảy ra) Trung tâm: server trung tâm hỏng Vòng: token bị mất, tiến trình hỏng Multicast: tiến trình hỏng