Chương 6 : Nhất quán và nhân bản
6.1 Đặt vấn đề.
Có hai lý do để sử dụng bản sao:
-Dùng bản sao để tăng độ tin cậy và tính sẵn sàng của HT: khi dữ liệu bị lỗi hay vì một nguyên nhân nào đó mà không thể dùng được, ta có thể dùng ngay bản sao dữ liệu đó để HT không phải dừng lại và tránh được tình trạng sử dụng các dữ liệu không chính xác.
-Dùng bản sao để tăng hiệu năng của HT: có thể tăng quy mô HT cả về số lượng lẫn phạm vi địa lý.
Tuy nhiên việc sử dụng nhân bản cũng phải trả giá, đó là tính nhất quán dữ liệu của HT bị suy giảm. Do sử dụng bản sao nên có thể xảy ra trường hợp có sự thay đổi trên một dữ liệu mà không cập nhật trên các bản sao của nó. Điều này sẽ gây ra các sai sót trong HT. Do đó phải tốn nhiều công sức để xây dựng các mô hình đảm bảo tính nhất quán của dữ liệu.
6.2 Các mô hình nhất quán lấy dữ liệu làm trung tâm.
6.2.1 Mô hình nhất quán chặt (Strict consistency).
Là mô hình thỏa mãn điều kiện sau: Thao tác đọc bất kỳ trên mục dữ liệu x đều trả về một giá trị tương ứng với kết quả của thao tác ghi gần nhất trên x đó.
Sử dụng khái niệm thời gian tuyệt đối. Thời gian tuyệt đối này là tổng thể cho cả HT để xác định đúng khái niệm “gần nhất”. Điều này là khó khả thi với HPT.
Mô hình này là không khả thi nên đưa ra mô hình giảm nhẹ hơn.
6.2.2 Mô hình nhất quán tuần tự và mô hình nhất quán tuyến tính.
a. Mô hình nhất quán tuần tự.
Là mô hình lỏng lẻo hơn, yếu hơn mô hình nhất quán chặt. Nó thỏa mãn các yêu cầu sau:
Kết quả của sự thực hiện bất kỳ là như nhau nếu thao tác đọc và ghi do các tiến trình thực hiện trên mục dữ liệu 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 chỉ ra bởi CT của nó.
Khi các tiến trình chạy đồng thời trên các máy khác nhau thì cho phép sự đan xen của các thao tác nhưng tất cả các tiến trình đều phải nhận biết được sự đan xen của các thao tác đó là như nhau.
b. Mô hình nhất quán tuyến tính.
Là mô hình yếu hơn mô hình nhất quán chặt nhưng mạnh hơn mô hình nhất quán tuần tự. Mô hình này thỏa mãn điều kiện 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 CT của nó.”
6.2.3 Mô hình nhất quán nhân quả.
Đây là mô hình lỏng lẻo hơn mô hình nhất quán tuần tự. Mô hình này phân biệt các sự kiện có quan hệ nhân quả và các sự kiện không có quan hệ nhân quả.
Nếu sự kiện b được gây ra hoặc bị tác động bởi một sự kiện a xảy ra sớm hơn thì tính nhân quả đòi hỏi mọi thực thể khác phải “nhìn” thấy a trước rồi mới thấy b sau.
Mô hình nhất quán nhân quả thỏa mãn các điều kiện sau: các thao tác ghi có quan hệ nhân quả tiềm năng phải được nhận biết bởi tất cả các tiến trình khác trong cùng một thứ tự. Các thao tác ghi đồng thời có thể nhận biết được theo thứ tự khác nhau trên các máy khác nhau.
6.2.4 Mô hình nhất quán FIFO .
Nhất quán FIFO còn được gọi là nhất quán PRAM. Đây là mô hình yếu nhất vì mô hình này bỏ qua giới hạn về trật tự của bất kì thao tác đồng thời nào. Nhất quán FIFO thỏa mãn : “Các thao tác ghi bởi một tiến trình đơn phải được tất cả các tiến trình khác nhìn thấy theo cùng một trật tự mà chúng đề ra. Nhưng thao tác ghi bởi nhiều tiến trình khác nhau có thể được thấy theo những trật tự khác nhau bởi các tiến trình khác nhau”.
6.2.5 Mô hình nhất quán yếu (Weak consistency).
Mô hình nhất quán yếu không tập trung vào các thao tác trên dữ liệu như các mô hình trên mà chúng quan tâm đến trật tự các nhóm lệnh bằng việc sử dụng các biến được đồng bộ.
Mô hình nhất quán yếu có ba đặc tính sau:
· Việc truy cập đến một biến đồng bộ hóa được kết hợp với kho dữ liệu là một nhất quán tuần tự.
· Không có thao tác nào lên các biến đồng bộ hóa được phép thực hiện cho đến khi tất cả các thao tác ghi trước đó được hoàn thành ở mọi nơi.
· Không có thao tác đọc hay ghi dữ liệu lên các mục dữ liệu nào được phép thực hiện cho đến khi tất cả các thao tác trước đó lên các biến đồng bộ hóa được thực hiện.
6.2.6 Mô hình nhất quán đi ra
Sử dụng thêm hai lệnh: lệnh acquired để báo muốn vào vùng tới hạn (critial region) và lệnh release để báo giải phóng vùng tới hạn. Hai lệnh này cũng có hai cách thực thi khác nhau như: bằng một biến hoặc bằng một lệnh đặc biệt. Hai thao tác này chỉ thực hiện với các dữ liệu dùng chung chứ không áp dụng cho tất cả các dữ liệu.
Mô hình nhất quán đi ra thỏa mãn các điều kiện sau:
- Trước khi thực hiện một thao tác đọc hay ghi lên dữ liệu chia sẻ thì tất cả các thao tác acquire do tiến trình này thực hiện trước đó phải hoàn tất.
- Trước khi một thao tác release được phép thực hiện thì tất cả các thao tác đọc và ghi do tiến trình này thực hiện trước đó phải được hoàn tất.
- Truy cập vào các biến đồng bộ hóa là nhất quán FIFO (Không yêu cầu nhất quán tuần tự).
6.2.7 Mô hình nhất quán đi vào
Cũng giống mô hình nhất quán đi ra, mô hình nhất quán đi vào cũng sử dụng hai lệnh acquired và release khi muốn sử dụng vào vùng tới hạn. Nhưng các lệnh này thao tác trên từng mục dữ liệu của vùng dữ liệu chia sẻ. Tiến trình nào muốn sử dụng mục dữ liệu thì phải đợi cho tất cả các tiến trình khác giải phóng mục dữ liệu đó.
Để ghi lên một mục dữ liệu, client phải có được biến đồng bộ hoá của mục đó trong chế độ dành riêng. Điều đó có nghĩa là không client nào khác có thể sử dụng biến đó. Khi client cập nhật xong mục dữ liệu, thì nó giải phóng biến đó .
Khi client muốn đọc một mục dữ liệu nào đó, nó phải có được biến đồng bộ hóa kết hợp ở chế độ không dành riêng. Nhiều client có thể giữ một biến đồng bộ hóa ở chế độ không dành riêng.
Khi thực hiện một thao tác acquire, client lấy về phiên bản mới nhất của mục dữ liệu từ tiến trình cuối cùng thực hiện thao tác acquire trên biến đó.
Nhất quán đi vào phải thỏa mãn các điều kiện sau:
- Một thao tác acquire để 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 mục dữ liệu 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.
6.3 Các mô hình nhất quán lấy người dùng làm trung tâm.
6.3.1 Nhất quán cuối cùng
Khi một dữ liệu có nhiều bản sao thì yêu cầu đưa ra là sau các thao tác cập nhật thì tất cả các bản sao cuối cùng là phải bằng nhau. 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.
Nếu các client là di động thì việc thực hiện yêu cầu trên gặp khó khăn hơn. Phải luôn đảm bảo rằng ngay cả khi client thay đổi về vị trí vật lý thì việc sử dụng các bản sao cũng phải chính xác. Tức là các bản sao luôn luôn là nhất quán.
6.3.2 Nhất quán đọc đều
Mô hình nhất quán đọc đều phải đảm bảo điều kiện sau:
Một tiến trình thực hiện thao tác đọc trên một mục dữ liệu thì phải đảm bảo bất kì thao tác đọc nào cũng đều cho cùng một kết quả hay kết quả gần đây nhất.
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.
Về bản chất thì mô hình này là phiên bản hướng người dùng của mô hình nhất quán FIFO (điểm khác biệt ở chỗ nó chỉ áp dụng đối với một client).
6.3.3 Nhất quán ghi đều (monotonic – read consistency).
Mô hình nhất quán đọc đều phải đảm bảo điều kiện sau:
Thao tác ghi trên mục dữ liệu x của một tiến trình phải được hoàn thành trước bất kỳ một thao tác ghi nào khác trên x bởi cùng một tiến trình.
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ự.
6.3.4 Nhất quán đọc kết quả ghi (Read – your – write consistency)
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 đó”.
6.3.5 Nhất quán ghi theo sau đọc (write – follow – read consistency).
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 đó”.
6.4 Các giao thức phân phối
6.4.1 Xếp đặt các bản sao (replica placement).
Có 3 kiểu bản sao:
Các bản sao thường trực: trong tiến trình hay trên máy luôn có một bản sao. Số lượng các bản sao thường xuyên này rất ít, thường được tập hợp lại thành nhóm các máy trạm (COWs) hoặc trong các HT phản chiếu (mirrored), thường là các Web server hay là các server có chứa cơ sở dữ liệu dự phòng.
Bản sao khởi đầu từ server: 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 sử dụng để định vị vị trí địa lý của các bản sao gần nhất khi họ cần.
Các bản sao khởi đầu từ client: 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.
6.4.2 Lan truyền các cập nhật
Có 3 khả năng lan truyền các cập nhật
Chỉ thông báo là có cập nhật: Thường dùng trong việc cache dữ liệu.Thông báo về việc mất hiệu lực của một giao thức.Phương pháp này tốt khi tỉ lệ các thao tác đọc so với thao tác ghi nhỏ.
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.
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 mỗi khi có một server khác yêu cầu.
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.
6.4.3 Các giao thức bệnh dịch
Đây là một giao thức có thể dùng để thực hiện mô hình nhất quán sau cùng.
Ý tưởng cơ bản của thuật toán bệnh dịch là:
- Giả sử rằng không xảy ra xung đột giữa các thao tác ghi – ghi.
- Các thao tác cập nhật ban đầu được thực hiện chỉ trên một hay một vài bản sao (càng ít càng tốt).
- Một bản sao chỉ gửi các cập nhật của nó tới một số hữu hạn các hàng xóm.
- Việc lan truyền các cập nhật xảy ra chậm chạp và không phải ngay lập tức.
- Cuối cùng thì mỗi cập nhật cũng đến được từng bản sao.
Dựa trên thuật toán bệnh dịch mà có các mô hình lan truyền cập nhật. Điều đáng lưu tâm trong mô hình này là các cập nhật được lan truyền tới các bản sao với càng ít thông điệp càng tốt và càng nhiều bản sao bị “nhiễm” các lan truyền càng nhanh thì càng tốt. Đến cuối cùng nếu bản sao nào mà không lan truyền được cập nhật của mình thì nó sẽ bị loại bỏ. Tuy nhiên việc loại bỏ có thể sẽ không dễ dàng.
Một trong những mô hình lan truyền cập nhật được gọi là: anti entropy. Trong mô hình này, mỗi bản sao cứ định kì lại chọn ngẫu nhiên một bản sao khác và trao đổi những trạng thái khác nhau của mình, sau một thời gian thì cả 2 phía sẽ có những trạng thái giống hệt nhau.
Một mô hình khác là gossiping. Trong mô hình này một bản sao đã được cập nhật sẽ “kể” cho một số bản sao khác về những cập nhật của mình vì thế sẽ làm cho những bản sao đó bị nhiễm những cập nhật của mình.
6.5 Các giao thức nhất quán.
6.5.1 Giao thức Primary-based
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 HT 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.
6.5. 2. 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án 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 Quorumbased
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.
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ị phát hiện 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 CT 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 CT 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 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.
Các thao tác ghi dữ liệu vào cache được tiến hành như sau:
- 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).
Bạn đang đọc truyện trên: Truyen2U.Pro