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

V. Đồng bộ hóa và phối hợp(phần 2) Hệ phân tán (NW605) Multicast Bầu cử – election Giao tác – transaction Multicast 11.4, Coulouris Multicast Tiến trình gửi (sender) thực hiện một lệnh send() Gửi tới một nhóm các tiến trình nhận (receiver) Broadcast: gửi tới tất cả các tiến trình trong hệ thống Multicast – Ví dụ Chịu lỗi – fault tolerance: Các server sao lặp Tính nhất quán cao: các thao tác được multicast Tìm kiếm dịch vụ - service discovery Gửi yêu cầu tìm kiếm dịch vụ bằng multicast Tiến trình cung cấp dịch vụ trả lời Lan truyền sự kiện/thông báo – event/notification propagation Các thành viên trong nhóm quan tâm đến một số sự kiện cụ thể Ví dụ: dữ liệu cảm ứng (sensor data), cập nhật giá chứng khoán, tình trạng mạng Multicast – tính chất Nhóm tĩnh/động: Tĩnh: danh sách thành viên không thay đổi trong khi chạy Động: có thể thay đổi Nhóm mở/đóng: Mở: ai cũng có thể gửi tới Đóng: chỉ có các thành viên mới gửi được Độ tin cậy: Thất bại do liên lạc / thất bại do xử lý Đảm bảo giao nhận: Tất cả các thành viên hoặc không thành viên nào (atomic – tính không chia cắt) Tất cả các thành viên hiện đang hoạt động bình thường Thứ tự: Đảm bảo thứ tự giao nhận FIFO, nhân-quả, thứ tự toàn bộ Các vấn đề khác Hiệu năng: Băng thông Thời gian trễ Hiệu quả: Tránh gửi một thông điệp nhiều lần qua 1 liên kết Cây phân tán Hỗ trợ của phần cứng (vd. Ethernet broastcast) Tầng mạng và tầng ứng dụng: Thiết bị định tuyến (router) hiểu multicast Ứng dụng (hoặc middleware) gửi unicast tới các thành viên của nhóm Multicast tầng mạng Ethernet Broadcast: Gửi tới tất cả các máy trong mạng nội bộ Dùng địa chỉ MAC: FF:FF:FF:FF:FF:FF IP multicast: Nhóm multicast: dùng địa chỉ Internet lớp D 4 bit đầu tiên: 1110 (224.0.0.0 – 239.0.0.255) Các nhóm cố định: (224.0.0.1 – 224.0.0.255) định tuyến Gia nhập nhóm theo Internet Group Management Protocol (IGMP) Thiết lập cây phân tán: Protocol Independent Multicast (PIM) Mô hình hệ thống multicast tầng ứng dụng Giả thiết: Các kênh one-to-one đáng tin cậy Không có thất bại Một nhóm nhận đóng Multicast cơ bản Không đảm bảo về độ tin cậy Không đảm bảo thứ tự Multicast thứ tự FIFO Giữ thứ tự của mỗi tiến trình gửi Multicast thứ tự FIFO Multicast thứ tự FIFO Multicast thứ tự nhân-quả Giữ thứ tự giữa hai sự kiện gửi có quan hệ nhân-quả 1 và A, 2 và B được coi là song song/đồng thời 1 xảy ra trước B Multicast thứ tự nhân-quả Multicast thứ tự toàn bộ Đảm bảo các thông điệp được giao cho các tiến trình theo cùng một thứ tự Multicast thứ tự toàn bộ Sequencer-based: Sender gửi thông điệp Sequencer tính và gửi số thứ tự Thông điệp được bàn giao theo số thứ tự Agreement-based: Sender gửi thông điệp Các receiver tính số thứ tự và gửi đề xuất cho sender Sender chọn số cao nhất và gửi lại cho các receiver Bầu cử 11.5, Coulouris Bầu cử Xác định một điều phối viên (coordinator) Một số thuật toán dựa vào một tiến trình điều phối riêng biệt Điều phối viên phải được cùng quyết định Cũng có thể thay điều phối viên trong khi đang chạy Giả sử mỗi nút đều có ID khác nhau Bầu cử: thống nhất về tiến trình đang chạy có ID lớn nhất Đòi hỏi: một tiến trình hoặc không biết điều phối viên hoặc biết ID của tiến trình có ID lớn nhất một tiến trình rồi cũng sẽ hoặc treo hoặc biết điều phối viên là tiến trình nào Thuật toán Lớn trị bé – Bully algorithm Ba loại thông điệp: Election: phát động bầu cử Answer: hồi đáp thông báo bầu cử Coordinator: công bố điều phối viên đã được bầu Thuật toán: Một tiến trình phát động bầu cử khi nó thấy điều phối viên có vẻ đã hỏng (timeout), hoặc nhận được một thông điệp Election. Khi nhận được Election, tiến trình trả lời bằng Answer Tiến trình phát động bầu cử bằng cách gửi Election tới các tiến trình có ID cao hơn mình rồi đợi nhận Answer từ các tiến trình đó Nếu không nhận được Answer, tiến trình trở thành điều phối viên mới và gửi Coordinator tới tất cả các tiến trình khác để thông báo kết quả Nếu nhận được Answer, tiến trình đợi Coordinator để biết kết quả bầu điều phối viên mới Thuật toán Lớn trị bé Thuật toán vòng Các nút sắp xếp thành vòng (lôgic) Một nút phát động bầu cử bằng cách gửi Election tới nút tiếp theo. Nếu nút đó đang hỏng, thông điệp được chuyển cho nút tiếp theo sau đó Tiến trình gắn ID của mình vào thông điệp trước khi gửi đi. Khi thông điệp quay lại tiến trình phát động bầu cử, tất cả các nút đều đã tham gia bầu cử. Nút phát động gửi thông điệp Coordinator chứa danh sách các tiến trình đang hoạt động quanh vòng. Tiến trình có ID cao nhất trong đó được chọn làm điều phối viên Giao tác 12, 13, Coulouris Giao tác Một giao tác là một chuỗi các thao tác đối với CSDL Mô hình giao tác: Thao tác: Ví dụ: giao tác ngân hàng BeginTransaction EndTransaction Commit Abort Read Write Tính chất ACID Atomic – không thể phân chia: hoặc toàn bộ giao tác được giao kết (commit) hoặc toàn bộ bị hủy bỏ (abort) Consistent – nhất quán: các giao tác song song không tạo ra kết quả không nhất quán Isolated – phân lập: các giao tác không đan xen lẫn nhau (không nhìn thấy trạng thái trung gian của nhau). Durable – bền vững: sau khi commit, kết quả được lưu lại bền vững (kể cả nếu server hoặc phần cứng gặp sự cố) Giao tác phân tán Giao tác đơn Giao tác lồng nhau