Hệ phân tán - Chương 7: Nhân bản và nhất quán

Chương 7 : NHÂN BẢN VÀ NHẤT QUÁN Chương này đề cập đến 1 vấn đề quan trọng trong hệ phân tán đó là các bản sao của dữ liệu . Dữ liệu nói chung trong hệ phân tán được nhân lên thành nhiều bản để tăng thêm tính tin cậy và tăng hiệu năng . Vấn đề chính của các bản sao là sự nhất quán giữa các bản sao khi một hoặc 1 số bản sao bị thay đổi . Chương này sẽ : giới thiệu về xem tại sao bản sao lại tốt và tập trung vào tính nhất quán của các bản sao Vấn đề về nhất quán mới là ½ toàn bộ nôi dung cần chú ý . chúng ta cần quan tâm xem nó hoạt động thế nào : 2 vấn đề : quản lý bản sao và giữ các bản sao được nhất quán . 7.1 Giới thiệu 7.1.1 Có 2 lý do chính để thực hiện việc nhân bản dữ liệu. Để tăng tín tin cậy cho hệ thống : Trong quá trình đọc hoặc ghi dữ liệu , nếu một bản sao bị hỏng hoặc vì lý do nào đấy nó không sẵn sàng để dùng thì ta có thể sử dụng một bản khác. Tránh việc sử dụng dữ liệu sai lạc, không chính xác. Để tăng hiệu năng của hệ thống : Tăng quy mô của hệ thống cả về số lượng lẫn phạm vi địa lý. Ví dụ như nếu số lượng máy tăng => tải trên mỗi máy trong hệ phân tán cũng ko tăng lên nhiều hơn . phạm vi địa lý tăng => có thể sử dụng các bản nhân bản gần khu vực địa lý đó . Một cái giá phải trả cho việc nhân bản dữ liệu đấy là phải chắc chắn rằng khi một bản sao được cập nhật thì tất cả những bản còn lại cũng phải được cập nhật theo để đảm bảo tính nhất quán của dữ liệu. Điều này ảnh hưởng rất lớn đến hiệu năng của hệ thống. Ví dụ : khi sử dụng các chương trình xem web => dữ liệu được ghi vào bộ nhớ máy tính ( bản sao ) , nếu trang web nội dung thay đổi . người dùng vẫn chỉ xem nội dung trên máy => cũ . Vấn đề đồng bộ dữ liệu trên máy khách và trên máy chủ Có 2 hướng tiếp cận cho việc nhân bản đối tượng. Ứng dụng tự chịu trách nhiệm nhân bản. Do đó ứng dụng cần giải quyết được vấn đề nhất quán. Hệ thống (middleware) đảm trách việc nhân bản. Vì thế vấn đề nhất quán do middleware đảm trách. Hướng này đơn giản hóa cho việc phát triển ứng dụng nhưng lại khiến các giải pháp đặc tả đối tượng trở nên phức tạp hơn. 7.1.2 Nhân bản như 1 kỹ thuật mở rộng Các bản sao có thể tăng hiệu năng của hệ thống vì chúng giúp làm giảm các trễ truy cập. Tuy nhiên chúng lại là nguyên nhân gây khó khăn cho việc duy trì tính nhất quán của dữ liệu. Các bản sao được phân tán trên diện rộng , vấn đề đặt ra là làm sao xác định được bản sao ở đâu đang được cập nhật 1 cách nhanh chóng nhất . Nếu các bản sao ở xa thì rõ ràng là việc cập nhật 1 bản được update sẽ gây ra tốn đường truyền trong mạng ( đồng bộ toàn bộ các bản sao ) mà việc thực hiện nhân bản này nhằm tăng hiệu năng của hệ thống => nếu đồng bộ không hợp lý thì sẽ làm giảm hiệu năng của toàn hệ thống : “The cure may be worse than the disease. “ . Đồng bộ từng phần tử rồi lan truyền sang các phần tử kế bên , việc này sẽ làm tăng hiệu năng nhưng sẽ dẫn đến việc có những thời điểm các bản sao là ko giống nhau Trong một số trường hợp ta cần phải nới lỏng những ràng buộc về tính nhất quán dựa trên: Tần suất truy cập và cập nhật dữ liệu. Mục đích sử dụng. 7.2. Các mô hình nhất quán lấy dữ liệu làm trung tâm. Mô hình nhất quán được sử dụng rộng rãi nhất là mô hình lấy dữ liệu làm trung tâm. Trong mô hình này, bất kì người sử dụng nào truy cập vào kho dữ liệu cũng sẽ nhìn thấy các thao tác được sắp xếp theo mô hình. Điều này trái ngược với các mô hình lấy client làm trung tâm nơi client được yêu cầu một mô hình nhất quán cụ thể và các client khác nhau sẽ nhìn thấy các thao tác theo những trật tự khác nhau. Kho dữ liệu có thể được đọc hay ghi bởi bất cứ tiến trình nào trong một hệ phân tán. Tuy nhiên dữ liệu ghi vào một bản sao cục bộ phải đảm bảo cũng được truyền tới tất cả các bản sao ở xa. Vì nguyên nhân này mà các mô hình nhất quán đã ra đời, mục đích là để giúp chúng ta có thể hiểu rõ về các cơ chế khác nhau được sử dụng để thực hiện phần việc này. Một mô hình nhất quán có thể được coi là một bản hợp đồng giữa một kho dữ liệu của hệ phân tán với các các tiến trình của nó. Nếu các tiến trình đồng ý với các điều khoản của hợp đồng thì kho dữ liệu sẽ hoạt động đúng như tiến trình mong muốn. 7.2.1 Nhất quán tuyến tính Phương pháp này hoạt động dựa trên việc xác định xem việc ko nhất quán nào là có thể chấp nhận được dựa vào việc xác định các thông tin sau : Độ lệch bằng số giữa các bản sao Độ lệch theo trạng thái giữa các bản sao Độ lệch trong thứ tự các lần cập nhật Như vậy trong hệ thống sẽ quy định một độ lệch giữa các bản sao . Nếu một phiên bản được cập nhật mà độ lệch chưa đạt tới giá trị quy định thì giữa bản sao đó và các bản sao khác vẫn được coi là nhất quán và ko phải thực hiện cập nhật . Độ lệch bằng số giữa các bản sao : thường sử dụng với các chương trình có dữ liệu là số . Có 2 dạng của độ lệch này là độ lệch tương đối và độ lệch tuyệt đối .Có thể xác định số này có thể xác định là số lượng bản cập nhật cho 1 bản sao nào đó . Độ lệch về trạng thái giữa các bản sao : liên quan đến thời gian cuối cùng 1 bản sao đã được cập nhật . Với 1 số ứng dụng thì nó có thể chấp nhận dữ liệu cũ , miễn là ko quá cũ . vd : trong dự báo thời tiết , máy chủ liên tục nhận được các thông tin về thời tiết nhưng chỉ đồng bồ 30’ 1 lần … Độ lệch trong thứ tự cập nhật : thứ tự cập nhật được phép khác nhau ở các bản khác nhau khi sự khác nhau vẫn trong giới hạn . Khi nhận được yêu cầu cập nhật , thì bản sao tạm thời cập nhật và chờ sự đồng ý của các bản sao khác về quá trình cập nhật . Như vậy cần có thêm 1 bản sao phụ để nếu không nhận được sự đồng ý cập nhật của các bản sao khác thì quay lại bản cũ . Có thể sau nhiều lần cập nhật tạm thời thì bản sao mới được cập nhật lâu dài Tóm lại , các bản sao có thể vẫn được sử dụng nếu sự khác nhau vẫn nằm trong giới hạn được chấp thuận . Một cách khác nữa là khi 1 bản sao được cập nhật thì nó sẽ chờ để được xác nhận trước khi cập nhật lên tất cả các bản sao khác . => thứ tự cập nhật rắc rối . Cách làm này cần lưu trữ thêm 1 bản để có thể quay lại nếu bản cập nhật không được chấp thuận . Conit : Consistent Unit 7.2.2 Nhất quán theo thứ tự thực hiện Các mô hình nhất quán ở mục này sẽ đề cập đến : khi 1 bản sao cập nhật tạm cần được đồng bộ ở 1 bản sao , nó sẽ yêu cầu 1 sự đồng ý ở trên “ thứ tự cập nhật chung “ hoặc cần sự đồng ý cho sự cập nhật của mình ( thứ tự cập nhật của bản này ) a.Nhất quán tuần tự Một kho dữ liệu được gọi là nhất quán tuần tự nếu nó thỏa mãn yêu cầu sau : “Kết quả của bất kì sự thực hiện nào là như nhau nếu các thao tác (đọc và ghi) của tất cả các tiến trình lên dữ liệu được thực hiện môt cách tuần tự và các thao tác của mỗi tiến trình xuất hiện trong chuỗi thao tác này phải theo thứ tự đã được chỉ ra trong chương trình của nó” Vd : với 2 tiến trình Với 4 tiến trình : b.Mô hình nhất quán nhân quả Nhất quán nhân quả là mô hình yếu hơn nhất quán tuần tự, mô hình này chỉ quan tâm đến các thao tác ghi có quan hệ nhân quả với nhau. “Các thao tác ghi có quan hệ nhân quả tiềm năng phải được nhìn thấy bởi tất cả các tiến trình theo cùng một trật tự, còn các thao tác ghi đồng thời có thể được nhận biết theo thứ tự khác nhau trên những máy khác nhau”. Hai thao tác ghi được coi là có quan hệ nhân qủa với nhau nếu việc thực hiện một thao tác có khả năng gây ảnh hưởng đến dữ liệu được ghi bởi thao tác kia. Đặc biệt, hai thao tác bất kì được coi là có quan hệ nhân quả với nhau nếu: Một thao tác đọc có quan hệ nhân quả với thao tác ghi cung cấp dữ liệu cho nó. Một thao tác ghi có quan hệ nhân quả với một thao tác đọc xảy ra trước nó trong cùng một tiến trình. Nếu write1 ® read và read ® write2 thì write1 ® write2. Nếu các thao tác không có quan hệ nhân quả với nhau thì chúng được coi là xảy ra đồng thời. Các thao tác đọc đồng thời có thể được thực hiện theo bất kì trật tự nào miễn là chúng tuân theo trình tự của chương trình. c. Nhóm hoạt động Một thao tác yêu cầu để truy cập vào một biến đồng bộ hóa không được phép thực hiện trong một tiến trình cho đến khi tất cả các cập nhật lên dữ liệu bị gác trong tiến trình đó được thực hiện. Trước khi một truy cập trong chế độ dành riêng của một tiến trình tới một biến đồng bộ hóa được phép thực hiện thì không tiến trình nào khác còn được giữ các biến đồng bộ hóa, trong chế độ không dành riêng thì không cần yêu cầu như vậy. Sau khi một truy cập trong chế độ dành riêng lên một biến đồng bộ hóa được thực hiện thì bất kì sự truy cập của tiến trình nào khác trong chế độ không dành riêng lên biến đó cũng không được thực hiện cho đến khi chủ nhân của biến đồng bộ thực hiện xong việc truy cập của mình. Điều kiện đầu tiên nói rằng : Khi 1 tiến trình nào đó có 1 yêu cầu thì yêu cầu này có thể không được thực hiện cho đến khi tất cả các cập nhật được thực hiện trên các dữ liệu chia sẻ . Nói cách khác là các dữ liệu phải được đồng bộ trước khi thực hiện 1 yêu cầu nào đó . Điều kiện thứ 2 nói rằng trong quá trình cập nhật thì tiến trình thực hiện cập nhật sẽ chuyển sang 1 chế độ độc quyền để không cho phép bất kỳ tiến trình nào khác có thể can thiệp vào quá trình cập nhật ( tiến trình cập nhật khác … ) Điều kiện thứ ba nói rằng nếu một quá trình muốn vào một khu vực quan trọng trong chế độ không độc quyền, nó trước tiên phải kiểm tra với chủ sở hữu của biến đồng bộ hóa đang bảo vệ khu vực quan trọng để lấy các bản sao gần đây nhất của chia sẻ dữ liệu bảo vệ. 7.3 Nhất quán hướng người dùng Tất cả các mô hình nhất quán hướng dữ liệu đều cho rằng số thao tác đọc là xấp xỉ với số thao tác ghi và các thao tác ghi đồng thời thì xảy ra thường xuyên. Trái lại, các mô hình nhất quán hướng người dùng lại cho rằng client thực hiện các thao tác đọc thường xuyên hơn các thao tác ghi và có rất ít các thao tác ghi xảy ra đồng thời. Mục đích của nhất quán hướng người dùng là tập trung vào những gì mà client muốn chứ không phải những gì do server đề ra. Các mô hình này cũng cho phép người dùng linh động trong việc có thể kết nối tới nhiều bản sao khác nhau trong quá trình thực hiện của mình. Trong phần này chúng ta cũng được làm quen với khái niệm tập các thao tác ghi (WS-write set). Một tập các thao tác ghi chứa lịch sử các thao tác ghi mà dẫn đến một giá trị các định của một mục dữ liệu xác định trên một bản sao xác định. Ở mục này chúng ta sẽ xem xét 1 lớp đặc biệt của lưu trữ dữ liệu phân tán . Yêu cầu về sự nhất quán là yếu , nó xẩy ra rất nhiều sự không nhất quán . Các mô hình nhất quán hướng người dùng tương đối rẻ để xây dựng trong thực tế. 7.3.1 Nhất quán cuối cùng Yêu cầu duy nhất của mô hinh này là tất cả các bản sao cuối cùng rồi sẽ phải giống nhau. Tất cả các cập nhật phải đảm bảo là cuối cùng cũng sẽ được truyền tới tất cả các bản sao khác. Yêu cầu này sẽ được thực hiện tốt nếu mỗi client luôn chịu khó cập nhật cho các bản sao. Nhưng vấn đề sẽ xẩy ra nếu quá trình đó diễn ra liên tục và sẽ làm ảnh hưởng đến hiệu năng của hệ thống => giải pháp là chỉ áp dụng với các hệ phân tán chỉ đọc và ít cập nhật . Các bản cập nhật sẽ được cập nhật tuy nhiên tiến trình của người dùng sẽ truy cập được vào bản cập nhật này sau 1 thời gian nhất định , để đảm bảo ko có vấn đề lỗi khi 1 tiến trình đang ghi trong lúc 1 tiến trình khác đọc . Tuy nhiên mô hinh này sẽ gặp một chút khó khăn nếu các client là di động. Khi người dùng cập nhật tại 1 địa điểm ( ghi dữ liệu vào database chẳng hạn ) ( Trong 1 khoảng thời gian đủ ngắn ) Rồi đến 1 địa điểm khác , truy cập vào dữ liệu đó . Người đó sẽ tương tác với 1 cơ sở dữ liệu khác , và sẽ thấy rằng công việc mình làm hôm nay biến mất . 7.3.2 Nhất quán chỉ đọc : Mô hình 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 mới hơn và không bao giờ phải nhìn thấy những dữ liệu cũ hơn những gì mà mình đã đọ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 tiếp theo 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. Vd : Hòm mail , thì mô hình này đảm bảo nếu ở nhà mà mở ra được 10 cái thư , thì đến cơ quan ít nhất vẫn mở ra được 10 cái thư đó ( nếu chưa có thư nào thêm và ko xóa thư đi ) Để đảm bảo đây là nhất quán chỉ đọc , thì tất cả các hoạt động ghi WS(x1) ở L1 cần phải được chuyển sang L2 trước khi thực hiện quá trình đọc . Việc WS(x1) đã được chuyển sang L2 thể hiện qua WS(x1;x2) . Ở đây chỉ có 1 tiến trình P đọc dữ liệu từ x ở L1 và L2 . (b) không có gì đảm bảo là WS(x2) có chứa các cập nhật ở L1 => đây không phải là nhất quán chỉ đọc . 7.3.3 Nhất quán chỉ ghi Mô hình nhất quán ghi đều đảm bảo rằng một thao tác ghi lên một mục dữ liệu xác định sẽ được hoàn tất trước khi có bất kì tao tác ghi nào khác lên mục dữ liệu đó bởi cùng một client. Nói cách khác thì các thao tác ghi lên một mục dữ liệu sẽ được sắp xếp một cách có trật tự. Hình (a) Kho dữ liệu theo mô hình nhất quán ghi đều (b) Kho dữ liệu không theo mô hình nhất quán ghi đều. Giống như nhất quán chỉ đọc , nhất quán chỉ ghi cần đảm bảo rằng các thao tác cập nhật trên L1 cần được chuyển sang L2 trước khi P thực hiện tiếp thao tác ghi W(x2) . 7.3.4 Nhất quán đọc kết quả ghi Trong mô hình nhất quán này, người dùng được đảm bảo rằng sẽ luôn được 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 mục dữ liệu x sẽ luôn được nhìn thấy bởi một thao tác đọc lần lượt trên x của cùng tiến trình đó”. Tiến trình nhận nhiệm vụ ghi thì sẽ đảm trách luôn việc đọc như vậy thì quá trình ghi bắt buộc sẽ phải hoàn tất trước khi việc đọc được thực hiện => người dùng sẽ nhìn thấy kết quả ghi mới nhất . Vd : đồng bộ mật khẩu hoặc xem 1 trang web ( khi web browser sử dụng cache ) 7.3.5 Nhất quán ghi theo sau đọc Mô hình nhất quán này ngược với nhất quán đọc kết quả ghi, nó đảm bảo rằng một người dùng sẽ luôn thực hiện thao tác ghi lên một phiên bản dữ liệu mà ít nhất cũng phải mới bằng phiên bản cuối cùng của nó. “Tác động bởi một thao tác ghi của một tiến trình lên mục dữ liệu x sẽ luôn được nhìn thấy bởi một thao tác đọc liên tiếp lên x của cùng tiến trình đó”. Hình (a) Kho dữ liệu theo mô hình nhất quán ghi theo sau đọc (b) Kho dữ liệu không theo mô hình ghi theo sau đọc. 7.4 Quản lý các bản sao Một vấn đề hết sức quan trọng đối với các hệ phân tán sử dụng bản sao là việc quyết định xem ở đâu , khi nào và ai sẽ là người thiết lập ra các bản sao . Việc này chia ra làm 2 vấn đề nhỏ hơn : Đặt bản sao ở đâu ( địa điểm nào là tốt để tìm ra dữ liệu nhanh ) Nội dung bản sao như thế nào ( vẫn là đỉa điểm để sao cho nội dung bản sao sẽ được sử dụng hiệu quả nhất ) 7.4.1 Sắp xếp các bản sao máy chủ Có nhiều cách để tính toán vị trí tốt nhất cho các máy chủ đặt bản sao , nhưng tất cả các cách này đều phải giải quyết chung 1 vấn đề đó là vấn đề về hiệu năng khi chọn k vị trí trong N vị trí có thể đặt bản sao . Vd : Giải pháp của họ là chọn một máy chủ tại một thời điểm nào đó sao cho khoảng cách trung bình giữa các máy chủ và khách hàng là tối thiểu trong khi trong hệ thống đã có k máy chủ được đặt . tuy nhiên , cách này có chi phí lớn về mặt thời gian , độ phức tạp tính toán . Thuật toán : các nút được giả định vị trí trong một không gian m chiều , chúng ta đã thảo luận ở chương trước . Ý tưởng cơ bản là phát hiện ra k cụm và phân 1 nút cho mỗi cụm để nhân bản nội dụng . Để phát hiện ra cụm này , toàn bộ không gian được phân thành các tế bào . K tế bào dầy đặc nhất được chọn đặt máy chủ nhân bản . Một tế bào là một khối hình siêu lập phương m chiều . Cho không gian 2 chiều thì nó là 1 hình chữ nhật . Kích thước của các tế bào này là rất quan trọng , như trong hình mỗi tế bào được chọn quá rộng , nhiều cụm các nút bị chứa trong cùng 1 tế bào . trong trường hợp này , quá ít máy chủ đã được đặt cho cụm đó . Tuy nhiên , chọn các tế bào nhỏ lại dẫn đến trường hợp 1 cụm lại đặt trên nhiều tế bào dẫn đền việc chọn nhiều máy chủ nhân bản . 7.4.2 Nội dung bản sao và sắp xếp Bỏ qua chuyện vị trí của bản sao . h sẽ tập trung vào nội dung của bản sao . Có 3 kiểu bản sao: Các bản sao thường xuyên Bản sao thường xuyên có thể coi là 1 tập các bản sao tạo thành 1 kho lưu trữ dữ liệu phân tán . Thông thường thì số lượng các bản sao thường xuyên này là nhỏ . Ví dụ : Phan tán của các trang web có thể chia làm 2 dạng sau : 1 bản sao của website có thể được đặt trong 1 giói số lượng giới hạn máy chủ trong cùng 1 địa điểm . khi mà 1 yêu cầu tới nó sẽ chuyển tới 1 trong các máy chủ đó , đây sử dụng cơ chế round-robin . Dạng thứ 2 là bản phụ ( mirror ) Bản sao do server khởi tạo Các bản sao này được sử dụng để làm tăng hiệu năng. Các bản sao này được xếp đặt động dựa vào yêu cầu của server khác. Một ví dụ điển hình là chúng được các công ty web hosting nhận được các yêu cầu từ một vị trí xa , họ sẽ tạo ra 1 bản sao tạm thời ở vùng mà yêu cầu đến . Việc đưa ra các máy chủ bản sao như vậy sẽ đơn giản hơn việc phải tạo tìm ra vị trí để đặt bản sao . Đặc điểm Giảm tải trên máy chủ Các tệp tin được chỉ định sẽ được đưa tới các vị trí gần với máy khách hơn Mỗi máy chủ theo dõi việc truy cập vào các tệp tin ( đếm ) và vị trí mà yêu cầu đến từ . Ví dụ như , mỗi máy chủ có thể biết được máy khách nào là gần với 1 máy chủ nào đó nhất , nếu có 2 máy trạm cùng chung 1 máy chủ gần nhất nào đó thì tất cả các yêu cầu tới máy chủ ban đầu sẽ được chuyển tới máy chủ đó . Nếu như số yêu cầu tới máy chủ ban đầu mà giảm xuống dưới 1 giá trị nào đó thì tệp tin đó sẽ bị xóa khỏi máy chủ đó . Điều đó sẽ làm giảm số lượng các bản sao và làm tăng các yêu cầu tới các bản sao khác . Tuy nhiên vẫn phải đảm bảo rằng ít nhất còn có 1 bản sao tồn tại Các bản sao do client khởi tạo Một loại bản sao quan trọng là bản sao được tạo ra bởi máy khách , nó có thong thường được gọi là bộ nhớ đệm ( cache ) . Các bản sao này được tạo ra từ yêu cầu của client, chẳng hạn như việc cache dữ liệu của một trình duyệt. Chúng được xếp đặt động dựa vào yêu cầu của client. Bộ nhớ đệm của máy khách được sử dụng để tăng thời gian truy cập dữ liệu . Thông thường , khi máy khách muốn truy cập 1 số dữ liệu nào đó nó kết nối tới bản sao gần nhất của dữ liệu đó và lấy dữ liệu nó cần về để đọc và lưu trữ dữ liệu mà nó mới thay đổi . Nếu các thao tác đều là đọc dữ liệu thì hiệu năng có thể tăng lên nhờ để máy trạm lưu trữ dữ liệu trong bộ nhớ tạm . Các dữ liệu này được giữ trong bộ nhớ tạm trong 1 thời gian nhất định nào đó . Thông thường bộ nhớ tạm nằm ngay trên máy client . 7.4.3 Phân tán nội dung ( lan truyền cập nhật ) Có 3 khả năng lan truyền các cập nhật Chỉ lan truyền thông báo về cập nhật tới các bản sao khác. Thông báo về việc mất hiệu lực của một giao thức. Tức là việc nó truyền đi 1 thông báo rằng các bản sao khác đã không nhất quán với bản sao hiện tại Thực hiện tốt khi tỉ lệ các thao tác đọc so với thao tác ghi nhỏ. ( ghi nhiều ) Truyền dữ liệu cập nhật từ bản sao này tới một bản sao khác. Thực hiện tốt khi có nhiều thao tác đọc. Ghi lại các thay đổi và tập hợp các cập nhật lại để truyền đi (chỉ truyền đi các thay đổi chứ không truyền cả dữ liệu đã bị thay đổi, vì thế tiết kiệm được băng thông). Lan truyền các thao tác cập nhật tới các bản sao khác (nhân bản chủ động). Tốn ít băng thông nhưng đòi hỏi năng lực xử lý cao vì trong nhiều trường hợp thì các thao tác là rất phức tạp. Trong 3 phương pháp tiếp cận trên thì không phương pháp nào có thể coi là tốt nhất vì nó còn tuỳ thuộc vào băng thông sẵn có cũng như tỉ lệ các thao tác đọc so với thao tác ghi lên các bản sao. Các giao thức kéo và đẩy Đẩy cập nhật: là giao thức do server khởi tạo, trong giao thức này các cập nhật được lan truyền tới các bản sao khác mà không cần các bản sao này yêu cầu cập nhật . Giao thức này làm việc tốt khi tỉ lệ đọc/ghi là cao . Kéo cập nhật: là giao thức do client khởi tạo khi client muốn được cập nhật. Giao thức này làm việc tốt khi tỉ lệ đọc/ ghi là nhỏ . 7.5 Các giao thức nhất quán. Các giao thức nhất quán mô tả việc thực thi những mô hình nhất quán xác định. Ở đây chúng ta chỉ tập trung vào mô hình nhất quán tuần tự. 7.5.1 Nhất quán tuyến tính Bounding Numerical Deviation : Đầu tiên ,chúng ta tập trung vào một trong những giải pháp để giữ cho các sai số trong giới hạn. Chúng ta tập trung vào việc ghi dữ liệu vào 1 đối tượng x . mỗi lần ghi dữ liệu sẽ có 1 trọng số nhất định đại diện cho số mà x đã cập nhật Bounding Staleness Deviations Bounding Ordering Deviations 7.5.2 Giao thức Primary-based ( có 1 bản sao làm trung tâm ) Được sử dụng trong các hệ chủ khách truyền thống mà không hỗ trợ nhân bản. Thường được sử dụng trong các hệ cơ sở dữ liệu phân tán và các hệ thống file không yêu cầu cao về tính chịu lỗi. Các bản sao thường được đặt trên cùng một mạng LAN. Giao thức này được sử dụng chỉ trên hệ thuần phân tán, kho dữ liệu không nhân bản. Dùng trong hệ thống bộ nhớ chia sẻ phân tán, nhưng tính toán linh hoạt trong chế độ không kết nối. Giao thức Primary-based có 2 loại là: Giao thức ghi từ xa và giao thức ghi cục bộ. a) Các giao thức ghi từ xa Với 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. Giao thức này thường được kết hợp với các hệ thống chủ khách truyền thống. Một dạng giao thức ghi từ xa là giao thức Primary-Backup. - 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, đặc biệt là khi có giao thêm giao thức ghi theo khối được sử dụng. - Ưu điểm của giao thức này là Sử dụng giao thức ghi không theo khối để xử lý các cập nhật. 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 mục dữ liệu được duy trì. Khi có yêu cầu thao tác ghi, mục dữ liệu được nhân bản từ server ở xa chuyển đến server cục bộ. Việc này được gọi là tiếp cận theo kiểu di trú hoàn toàn. Một vấn đề được đặt ra cho các tiến trình sử dụng giao thức này để đọc hoặc ghi lên các mục dữ liệu 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. 7.5.3 Các giao thức Replicated-write. Trong các giao thức này, thao tác ghi có thể được tiến hành tại bất kì bản sao nào. 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 giao tiếp point-to-point hay multicast. Ư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. Tuy nhiên giao thức này lại đòi hỏi phải truyền theo kiểu multicast động hoặc phải có một bộ sắp xếp dãy tập trung mà cả 2 phương pháp này đều khó có thể tiếp cận một cách linh hoạt. 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 quá 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 cho việc chỉ có một lời gọi và một lời đáp được gửi đi. Giao thức Quorum­based Với 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. Trong giao thức này tất cả các mục dữ liệu được kết hợp với một số phiên bản (version number). Mỗi lần một mục bị sửa đổi thì số 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 biểu đọc và số đại biểu ghi, hai đại biểu này sẽ xác định số bản sao phải được liên hệ trước khi thực hiện thao tác đọc và ghi. Số đại biểu đọc phải lớn hơn ½ tổng số bản sao, vì thế tổng của số đại biểu đọc và ghi phải lớn hơn tổng số bản sao. Bằng cách này, một người muốn thực hiện một thao tác đọc thì phải đảm bảo việc liên hệ với ít nhất một bản sao có chứa phiên bản mới nhất của mục dữ liệu. Việc lựa chọn số lượng đại biểu dựa vào tỉ lệ giữa thao tác đọc và ghi cùng với cost (bandwidth…) khi thực hiện phương pháp giao tiếp giữa các nhóm. 7.5.4 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. Có nhiều giải pháp cho việc cache dữ liệu. - Với chiến lược phát hiện sự cố kết, là chiến lược để xác định khi nào thì sự không nhất quán thật sự bị xẩy ra và từ đó loại bỏ những dữ liệu gây ra sự không nhất quán, thì có 2 giải pháp khác nhau. Với giải pháp tĩnh, tại thời điểm biên dịch chương trình thì những chỉ thị phụ sẽ được thêm vào để phát hiện những dữ liệu không nhất quán. Với giải pháp động thì tại thời điểm chạy chương trình thì có những đoạn mã để kiểm tra tính không nhất quán của dữ liệu cache với dữ liệu của server. - Với chiến lược ép buộc sự cố kết, là chiến lược để xác định xem dữ liệu cache được giữ nhất quán với dữ liệu lưu trên server như thế nào, thì có 2 cách để buộc giữ liệu phải cố kết với nhau. Đó là: Để cho máy trạm đảm bảo về sự nhất quán của dữ liệu Để cho server gửi đi một thông điệp về sự không hợp lệ mỗi khi dữ liệu bị thay đổi. Cập nhật các kĩ thuật lan truyền. Vậy việc thực hiện các thao tác ghi dữ liệu vào cache được tiến hành như thế nào? Với cache chỉ đọc ra (Read-only Cache) thì các cập nhật được thực hiện bởi server (bằng giao thức đẩy) hoặc bởi client (bằng giao thức kéo mỗi khi client nhận thấy dữ liệu cache đã cũ). Với cache ghi thẳng (Write-Through Cache) thì client sẽ thay đổi nội dung của cache, sau đó sẽ gửi các cập nhật đến cho server. Với cache ghi lại (Write-Back Cache) thì client trì hoãn sự lan truyền các cập nhật, cho phép nhiều cập nhật được tạo ra cục bộ sau đó gửi những cập nhật mới nhất cho server (việc này có khả năng ảnh hưởng mạnh đến hiệu năng). 7.5.5 Thực hiện nhất quán lấy người dùng làm trung tâm Naive Implementation ( thực hiện đơn giản ) Trong cách thức này , mỗi thao tác ghi được đặt 1 ID duy nhất toàn cục , ID này được máy chủ thiết lập mỗi khi mà các thao tác ghi được thực hiện . Chúng ta theo dõi 2 tập các thao tác . Tập thao tác ghi và tập thao tác đọc . Mô hình nhất quán chỉ đọc : Khi 1 máy khách thực hiện 1 thao tác đọc ở một máy chủ , máy chủ đó sẽ giữ lại thao tác đọc đó trong tập đọc và kiểm tra xem tất cả các thao tác ghi đã được thực hiện chưa ( locally ) . Nếu chưa thì thực hiện hết trước khi thao tác đọc được thực hiện . Mô hình nhất quán chỉ ghi : tương tự như thế nhưng với thao tác là thao tác ghi . Nâng cao hiệu quả Rất dễ nhận ra rằng các tập đọc và ghi ở mỗi máy trạm có thể trở nên rất lớn . để giữ cho chúng có thể quản lý được thì các thao tác đọc và ghi thường được nhóm thành các phiên . Một phiên thông thường tương tác với 1 ứng dụng nào đó : mở ra khi ứng dụng bắt đầu và kết thúc khi ứng dụng đóng lại . Vector Tem thời gian ?? 7.6 Tổng kết Có 2 lý do chủ yếu để nhân bản dữ liệu : tăng độ tin cậy và tăng hiệu năng của hệ thống . Nhân bản gây ra 1 số vấn đề về sự nhất quán : mỗi khi 1 bản sao được cập nhật thì nó sẽ khác với các bản sao khác . Để giữ bản sao phù hợp thì chúng ta cần phổ biến cập nhật để những điều không nhất quán tạm thời được che dấu . Tuy nhiên điều này làm giảm hiệu suất , đặc biệt là với quy mô hệ thống lớn . Giải pháp duy nhất cho vấn đề này là nới rộng các yêu cầu về nhất quán . Có nhiều mô hình nhất quán khác nhau . Với nhất quán tuyến tính , mục tiêu là thiết lập giới hạn độ lệch giữa các bản sao , độ lệch giữa tình trạng cũ và mới , độ lệch trong thứ tự hoạt động . Độ lệch nói đến giá trị của các bản sao có thể khác nhau . Loại độ lệch này thường sử dụng trong các ứng dụng phụ thuộc ví dụ như trong việc nhân bản cổ phiếu . Độ lệch với trạng thái cụ đề cập đến thời gian mà mỗi bản sao vẫn được coi là phù hợp , dù rằng bản cập nhật có thể đã diễn ra trước đó 1 thời gian . Độ lệch trạng thái thường được sử dụng trong lưu trữ web . Cuối cùng ,độ lệch về thứ tự ám chỉ tới số lượng lớn nhất các yêu cầu ghi có thể được thực hiện ở 1 máy chủ nào đó mà không có sự đồng bộ với các máy chủ khác . Nhất quán theo thứ tự từ lâu đã được hình thành dựa trên nhiều mô hình nhất quán . Nhiều biến có thể tồn tại nhưng chỉ một số ít có vẻ được các nhà phát triển ứng dụng sử dụng . Nhất quán tuần tự về cơ bản đáp ứng được các mong đợi của người lập trình : tất cả việc ghi đều được xem bởi tát cả mọi người theo thứ tự như nhau . Ít được sử dụng , nhưng có liên qua đó là quan hệ nhân quản , trong đó phản ánh rằng hoạt động tiềm năng phụ thuộc vào nhau được thực hiện theo thứ tự phụ thuộc đó . Các mô hình nhất quán yếu xem xét một loạt các hoạt động đọc và ghi . Cụ thể , chúng cho rằng mỗi dòng là thích hợp để đóng khung bằng cách đi kèm theo với hoạt động ở các biến đồng bộ như là khóa /Mặc dù điều này đòi hỏi sự cố gắng hơn nữa của các lập trình viên , mô hình này thường dễ dàng hơn để thực hiện hiệu quả . Trái ngược với mô hình này , là mô hình lấy người dùng làm trung tâm , mô hình này không quan tâm đến việc dữ liệu có thể được chia sẻ bởi người dùng mà thay vào đó là tập trung vào nhất quán đối với từng cá nhân , đảm bảo rằng người dùng đươc jkeets nối tới một bản sao mới nhất . Để truyền thông tin cập nhật , các kỹ thuật khác nhau đã được áp dụng . Cần phải xác định xem truyền cái gì , ở đâu và ai là người truyền . Chúng ta cần phải quyết định lan truyền thông báo , hoạt động hay trạng thái . Hơn nữa , không phải tất cả các bản sao đều yêu cầu cập nhật ngay lập tức . Giao thức nhất quán mô tả cụ thể việc triển khai các mô hình nhất quán . Đối với mô hình nhất quán tuần tự và các biến thể của nó , một sự phân biệt có thể được nhận thấy giữa Primary-based protocol và giao thức ghi nhân bản . Trong giao thức primary – based tất cả các hoạt động cập nhật đều được chuyển tới một bản gh chính để đảm bảo cập nhật theo thứ tự và chuyển tiếp . Trong giao thức ghi bản sao , cập nhật đươc chuyển tới một vài bản sao cùng 1 thời điểm , trong trường hợp nàu thì thứ tự thực hiện khó hơn nhiều .