Bài giảng Hệ phân tán - Sao lặp và tính nhất quán

III. Sao lặp và tính nhất quán Hệ phân tán (NW605) Sao lặp Tính nhất quán Mô hình Giao thức Phát tán cập nhật Sắp đặt các replica Sao lặp Tạo các bản sao dịch vụ trên nhiều máy Tại sao? Độ tin cậy Dư thừa Hiệu năng Tăng năng lực xử lý Giảm liên lạc Tính mở rộng được (giảm tập trung) Ngăn chặn quá tải tại một server đơn (mở rộng về kích thước) Tránh độ trễ liên lạc (mở rộng về địa lý) Hai kiểu Sao lặp dữ liệu Sao lặp điều khiển Sao lặp dữ liệu Sao lặp server dữ liệu	 Caching tại trình duyệt Web Sao lặp điều khiển Sao lặp cả dữ liệu và điều khiển Sao lặp – các vấn đề Cập nhật Tính thống nhất (xử lý dữ liệu được cập nhật) Phát tán cập nhật Các bản sao Bao nhiêu bản sao? Đặt ở đâu? Định tuyến/chuyển tiếp Client nên dùng bản sao nào? Distributed data store Kho dữ liệu lưu trữ các phần tử dữ liệu Nhìn từ phía client Distributed data store Kho dữ liệu lưu trữ các phần tử dữ liệu Nhìn từ phía kho dữ liệu Distributed data store – Các thao tác Các thao tác cho data store: Read. Ri(x)bClient i đọc giá trị của phần tử dữ liệu x, được kết quả trả về là b Write. Wi(x)a Client i thực hiện thao tác gán giá trị x:=a Các thao tác không có tính chất tức thời: Thời điểm phát ra (khi client gửi yêu cầu) Thời điểm thực hiện (khi một bản sao thực hiện yêu cầu) Thời điểm hoàn thành (khi client nhận được kết quả trả lời) Sự hợp tác giữa các bản sao (replica) Distributed data store – Các thao tác Ví dụ: hai client truy nhập hai replica khác nhau của một data store Read: luôn được thực thi tại chỗ Write: thực thi tại chỗ, sau đó phát tán sang các bản sao khác Tính nhất quán Khi một bản sao được cập nhật, tất cả các bản sao khác phải được cập nhật theo. Tùy theo thứ tự và cách thức cập nhật → không nhất quán Hai loại không nhất quán: Staleness - Ì trệ : bản này được cập nhật chậm chễ so với bản kia Thứ tự thực thi các thao thác Thứ tự khác nhau ở các bản sao khác nhau Tính nhất quán Dữ liệu không phân tán: Thứ tự thực hiện các thao tác của mỗi client được giữ Tính gắn kết của dữ liệu được tôn trọng Các thao tác đọc và ghi xảy ra đồng thời có thể dẫn đến xung đột Các thao tác xung đột Đọc-ghi Ghi-ghi Tính nhất quán: Thứ tự thực thi của các thao tác xung đột có ảnh hưởng đến tính nhất quán Thứ tự bộ phận (partial order): thứ tự các thao tác của MỘT client Thứ tự đầy đủ (total order): thứ tự chung cho tất cả các thao tác xung đột Tính nhất quán Ví dụ về các thao tác xung đột và thứ tự thực thi: Client A: x = 1; x = 0; Client B: print (x); print (x); Các kết quả có thể thu được tại B: --, 11, 10, 00 Các mô hình nhất quán Hai loại mô hình nhất quán: Data-centric (lấy dữ liệu làm trung tâm) Một mô hình áp dụng cho toàn bộ data-store Mọi client đều thấy các thao tác được sắp thứ tự cùng kiểu Client-centric (lấy client làm trung tâm) Mỗi client có thể yêu cầu một mô hình nhất quán cụ thể Các client khác nhau thấy các thao tác được sắp thứ tự khác nhau. Data-centric consistency models Strong ordering – sắp thứ tự mạnh Với mọi client, thứ tự thực hiện các thao tác ghi là như nhau Ví dụ: tất cả các client đều thấy W(x)a W(x)b W(x)c Các mô hình Strict, Sequential, Causal, FIFO (PRAM) Weak ordering – sắp thứ tự yếu Sắp thứ tự các nhóm thao tác ghi thay vì sắp theo từng thao tác ghi Các chuỗi ghi tại một replica được gộp thành nhóm Chỉ phát tán kết quả của các nhóm thao tác ghi Ví dụ {W(x)a W(x)b W(x)c} == {W(x)b W(x)a W(x)c} Các mô hình Weak, Release, Entry Strict consistency 	Thao tác read đối với một phần tử dữ liệu x trả về giá trị tương ứng với kết quả của lần write gần đây nhất đối với x Thứ tự theo thời gian tuyệt đối của tất cả các lần truy nhập đến dữ liệu dùng chung Cái gì là gần đây nhất trong một hệ phân tán? Đòi hỏi thời gian chung toàn cục Đòi hỏi liên lạc tức thời atomic operation Bình thường đối với một máy đơn xử lý Bất khả thi đối với một data-store phân tán Sequential consistency Tất cả các thao tác được thực hiện theo một chuỗi nào đó Có nhiều hơn một cách sắp thứ tự đúng Tất cả các client đều thấy cùng một thứ tự Trật tự thực thi chương trình tại mỗi client được đảm bảo Không sắp thứ tự theo thời gian toàn cục Client-centric consistency models 	Đảm bảo về thứ tự thao tác cho một client Client di chuyển và truy nhập data-store tại các replica khác nhau (có sửa dữ liệu) Các client không dùng chung dữ liệu Các client khác nhau có thể thấy các kiểu sắp thứ tự khác nhau cho các thao tác Nói cách khác: Kết quả của một thao tác tùy theo client thực hiện nó Kết quả còn phụ thuộc vào lịch sử của các thao tác mà client đó thực hiện Client-centric consistency models Mô hình data-store cho client-centric consistency Các phần tử dữ liệu có chủ Không có xung đột write-write Monotonic reads 	Nếu một client đã thấy một giá trị của x tại thời điểm t, từ đó nó sẽ không bao giờ nhìn thấy một phiên bản cổ hơn của x Kí hiệu: xi[t]: phiên bản của x tại replica i tại thời điểm t WS(xi[t]): tập hợp các thao tác ghi tại replica i mà kết quả dẫn đến xi[t] WS(xi[t1]; xj[t2]): WS(xj[t2]) chứa các hoạt động giống như WS(xi[t1]) R(xi[t]): thao tác đọc x cho kết quả là xi[t] Monotonic writes 	Một thao tác ghi lên phần tử dữ liệu x được hoàn thành trước tất cả các thao tác ghi tiếp theo đối với x bởi cùng một client. Tất cả các thao tác ghi của cùng một client được sắp thành chuỗi. Read your writes 	Thao tác đọc x thấy hiệu ứng của thao tác ghi x trước đó do cùng một client thực hiện. Write follows reads 	Một thao tác ghi đối với x được thực hiện trên một bản sao của x với giá trị đã được cập nhật theo lần đọc gần nhất của cùng client. Các giao thức nhất quán Giao thức nhất quán: cài đặt một mô hình nhất quán Primary-based protocols – các giao thức ghi tại bản chính của dữ liệu Remote-write protocols –ghi từ xa Local-write protocols – ghi tại chỗ Replicated-Write protocols – các giao thức ghi tại bản sao Active replication – chủ động sao chép Quorum-Based protocols – bỏ phiếu Remote-Write Protocols Tất cả các lệnh ghi được thực hiện tại duy nhất 1 server Các cập nhật bị block cho đến khi đã được thực hiện tại tất cả các bản sao Local-Write Protocols 	Primary được chuyển chuyển đến replica mà client tại đó muốn thực hiện cập nhật. Active replication Các cập nhật (ghi) được gửi cho toàn bộ các replica Cần multicast thứ tự đầy đủ Hoặc sequencer/coordinator gắn số thứ tự trong chuỗi. Phát tán cập nhật Phát tán cái gì? Dữ liệu Tốn băng thông, có lợi khi dữ liệu được cập nhật nhỏ và ít khi cập nhật Thao tác cập nhật Các replica tự thực hiện thao tác tốn ít băng thông Thông báo rằng bản dữ liệu của các replica khác đã cũ Có lợi khi dữ liệu lớn và được thường xuyên cập nhật Push & pull Pull (client-based): Các cập nhật được lan truyền chỉ khi được yêu cầu Thích hợp: Ghi nhiều đọc ít Có thể có polling delay (replica phải kiểm tra xem đâu là phiên bản mới nhất trước khi thực hiện thao tác đọc) Push (server-based): Các cập nhật được lan truyền ngay Thích hợp: Ghi ít đọc nhiều; yêu cầu cao về mức độ tươi mới của dữ liệu đọc Nơi ghi phải biết về tất cả các replica → tính mở rộng được Hệ thống replica Hệ thống replica Replica cố định: Tập các replica khởi đầu Do chủ của data-store tạo và bảo trì Cho phép ghi Replica server (server-initiated replica) Tăng hiệu năng Không do chủ data-store bảo trì Đặt gần các nhóm client Thiết kế bằng tay hoặc tự động dựa theo các thông số về lượng dữ liệu, người sử dụng, tỷ lệ đọc/ghi Replica client (client-initiated replica) Cache ở client Có tính chất tạm thời Chủ data-store không biết về các replica này Đặt gần client