Tài liệu Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn

Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Tiểu luận Hệ Phân Tán LỜI NÓI ĐẦU Hệ phân tán là lĩnh vực kiến thức tiên tiến nhằm giúp cho các chuyên viên công nghệ thông tin trong công tác nghiên cứu, phân tích và thiết kế các hệ thống tin học. Đây là lĩnh vực có tầm ứng dụng cao đang trên đà phát triển nhanh chóng và đã đạt được những thành tựu ứng dụng đáng kể. Thành phần của hệ phân tán bao gồm các hệ thống cục bộ (mạng hay máy đơn), trong đó một (hay nhiều) hệ thống phát các yêu cầu thông tin còn các hệ thống khác trả lời các yêu cầu có liên quan đến phần dữ liệu của mình. Các hệ thống truyền thống như hệ rời rạc hay tập trung không thể đáp ứng chính xác và nhanh chóng các yêu cầu thông tin từ xa với lưu lượng thông tin lớn. Các thao tác chuẩn của hệ phân tán bao gồm :
Tiếp nhận và ghi yêu cầu chỉ dẫn.
Dịch yêu cầu để có thể tìm thông tin cần thiết. Thực hiện một số việc riêng của hệ thống cục bộ như : kiểm tra quyền truy cập thông tin …
Gửi kết quả cho hệ thống đã phát yêu cầu. Các đặc điểm cơ bản của tất cả các hệ thống tin học phân tán là :
Thời hạn truyền thông tin trong hệ thống không giống nhau, các thông điệp có thể bị mất trong quá trình chuyển tải, các thông điệp có thể được truyền kép và hệ thống có thể rơi vào sự cố bất cứ lúc nào.
Một (hay nhiều) máy tính cấu thành của hệ phân tán có thể bị sự cố và hoạt động của toàn hệ trở nên bị đình trệ hoặc kém hiệu quả. Quản lý nhiều bản sao (multicopies) là giải pháp kỹ thuật bao gồm tập hợp các thông tin được nhân bản từ một đối tượng thông tin và các chương trình quản lý chúng trong môi trường phân tán. Nội dung quản lý nhiều bản sao là các giải pháp cho phép tự động hóa các công việc kiểm tra tính hợp thức của truy cập thông tin, khôi phục thông tin, cập nhật thông tin, an toàn cho các bản sao, sử dụng các bộ nhớ, đĩa, lưu lịch sử, mở/ghi lịch sử, chuyển các bản loại bỏ vào vùng có thể khôi phục,...Trong các nội dung nêu trên, vấn đề quan trọng nhất là cập nhật tự động thông tin vào các bản sao. Trong giới hạn của một báo cáo tiểu luận kết thúc môn học “Hệ phân tán”, báo cáo này trình bày những nội dung sau: Về phần lý thuyết + Giải quyết vấn đề nhiều bản sao. Về phần bài tập Hãy trình bày và giải thích bằng sơ đồ thuật toán xử lý : 1. Các thao tác đọc. 2. Các thao tác đọc-ghi. Do thời gian và kiến thức còn hạn chế, tiểu luận này chắc chắn còn những thiếu sót, tôi rất mong nhận được sự góp ý chân thành của Thầy giáo Lê Văn Sơn và các bạn trong lớp. Cho phép tôi được bày tỏ lòng biết ơn chân thành Thầy giáo Lê Văn Sơn và các bạn trong lớp đã giúp đỡ tôi hoàn thành công việc này. Trân trọng cám ơn! GVHD: PGS.TS. Lê Văn Sơn Trang 1 HVTH: Lê Quốc Dũng -KHMT K16 Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Tiểu luận Hệ Phân Tán A. PHẦN LÝ THUYẾT CHƯƠNG I: TỔNG QUAN VỀ HỆ PHÂN TÁN I. Hệ phân tán (Distributed System): Hệ tin học phân tán là một hệ thống đa dạng, nhiều thành phần và phức tạp về mặt cấu trúc, là vùng tri thức hiện đại đang được các chuyên gia công nghệ thông tin đặc biệt quan tâm nghiên cứu và đỗi mới một cách nhanh chóng. Trong điều kiện đó, đứng trên một quan điểm khác nhau người ta đã đưa ra các định nghĩa khác nhau về hệ phân tán như sau: Theo định nghĩa của Andrew Tanenbanum: Hệ phân tán là một tập hợp các máy tính độc lập mà xuất hiện đối với các người sử dụng như một máy tính đơn. Với các đặc điểm:  Nhiều bộ phận.  Kết nối thông qua mạng truyền thông.  Chia xẻ các tài nguyên. Hình 1.1. Ví dụ về hệ phân tán - Một Intranet tiêu biểu Nói chung, một định nghĩa phổ biến và khá đầy đủ về hệ phân tán được trình bày trong tài liệu [1] như sau: “Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán (Distributed System) là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý hoặc bộ vi xử lý nằm các tại các vị trí khác nhau và được liên kết với nhau thông qua phương tiện viễn thông dưới sự điều khiển thống nhất của một hệ điều hành.” Mục tiêu của hệ phân tán: GVHD: PGS.TS. Lê Văn Sơn Trang 2 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn  Tăng tốc độ bình quân trong tính toán, xử lý.  Cải thiện tình trạng luôn luôn sẵn sàng của các loại tài nguyên.  Tăng độ an toàn cho dữ liệu.  Đa dạng hóa các loại hình dịch vụ tin học  Đảm bảo tính toàn vẹn của thông tin. II.Các mô hình hệ phân tán: 1.Các lớp dịch vụ phần mềm và phần cứng: Các lớp phần mềm: Kiến trúc phần mềm: cấu trúc của phần mềm như là các lớp và các module trong các thuật ngữ của các dịch vụ đưa ra và yêu cầu giữa các tiến trình trên cùng hoặc trên các máy tính khác nhau. Platform (hệ nền): phần cứng mức thấp nhất và các lớp phần mềm (hệ điều hành). Middleware: một lớp của phần mềm mà mục đích của nó là đánh dấu heterogeneity và để cung cấp một mô hình lập trình cho các ứng dụng, như: CORBA, RMI (Remote Method Invocation), DCOM (Distributed Component Object Model),... 2.Kiến trúc hệ thống phân tán: 2.1.Mô hình Client/Server: Một WebServer thường là một client của một File Server cục bộ. Các WebServer và các Server của Internet khác là các client của một DNS Server cái mà dịch các tên miền Internet thành các địa chỉ mạng. GVHD: PGS.TS. Lê Văn Sơn Trang 3 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Một máy tìm kiếm là một Server, nhưng nó chạy chương trình được gọi là Web Crawlers cái mà truy cập các Web server thông qua Internet cho thông tin yêu cầu.  Dịch vụ cung cấp bởi nhiều server: Nhiều Server có thể:
Mỗi phần là một tập hợp các đối tượng.
Duy trì các bản copy của toàn bộ tập hợp các đối tượng trên một vài máy.  Ví dụ Web Proxy Server: Web Proxy Server cung cấp một bộ nhớ cache chia xẻ cho các máy client tại một site hoặc băng qua một vài site khác nhau. 2.2.Mô hình kiến trúc hệ phân tán ngang hang Đặc điểm nổi bật của hệ thống này là dữ liệu được tổ chức ở các nút có chức năng như nhau. Đồng thời sự tổ chức dữ liệu ở các nút này lại có thể rất khác nhau, từ đó cần phải có: GVHD: PGS.TS. Lê Văn Sơn Trang 4 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán
Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Định nghĩa dữ liệu tại mỗi vị trí : tại mỗi phút phải xây dựng lược đồ dữ liệu cục bộ LIS (local Internal Schema)
Mô tả cấu trúc logic toàn cục: Lược đồ khái niệm toàn cục GCS(Global Conceptual Schema)
Mô tả cấu trúc logic tại mỗi vị trí , điều nảy xảy ra do nhân bản và phân mảnh , gọi là lược đồ khái niệm cục bộ LCS (Local Conceptual Schema)
Mô tả cấu trúc dữ liệu của các ứng dụng gọi là lược đồ ngoại giới ES (External Schema) Cấu trúc hệ thống bao gồm hai thành phần chính : Bộ tiếp nhận người dùng (User Processor) và bộ phận xử lý dữ liệu (Data Processor).Hai modul này được đặt chung trên mỗi máy chứ không tách biệt như hệ thống khách đại lý . Các chức năng cơ bản của từng modul như sau :
User Interface Handler – Giao tiếp người sử dụng : Diễn dịch yêu cầu , định dạng kết quả .
Semantic Data Controler – Kiểm soát dữ liệu ngữ nghĩa. Dựa vào lược đồ khái niệm toàn cục để kiểm tra câu truy vấn tin có thực hiện được hay không
Global Query Optimizer – Tối ưu hóa câu hỏi toàn cục : Định ra chiến lược thực thi tốt nhất trên các nút .
Global Execution Monitor – Điều khiển thực thi câu truy vấn toàn cục .
Local Query Processor – Xử lý câu truy vấn cục bộ .
Local Recovery Manager – Quản lý khôi phục cục bộ : Quản lý sự nhất quán khi có sự cố
Run-time Support Processor – Bộ hận hỗ trợ thực thi : Quản lý truy xuất cơ sở dữ liệu. GVHD: PGS.TS. Lê Văn Sơn Trang 5 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn 2.3.Mô hình tương tác trong hệ phân tán:  Thực hiện truyền thông:
Sự tiềm ẩn (Latency): Sự trì hoãn lan truyền: thời gian cần thiết để một bit đầu tiên của một thông điệp truyền đến được đích. • Sự trì hoãn truyền: là khoảng thời gian giữa sự truyền bit đầu tiên và bit sau cùng của một thông điệp. • • Sự trì hoãn xử lý: là thời gian cần để hệ điều hành xử lý/gữi/nhận thông điệp. GVHD: PGS.TS. Lê Văn Sơn Trang 6 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Sự trì hoãn xếp hàng: thời gian cần để một thông điệp xếp hàng ở cuối máy chủ hoặc ở các node trung gian đợi để truyền đi. •
Băng thông (bandwidth): Tổng số thông tin có thể được truyền đi trong một thời gian đã cho.
Sự biến đống tạp (Jitter): thời gian khác nhau giữa các sự trì hoãn ảnh hưởng bởi các thông điệp khác nhau.  Đồng hồ và thứ tự các sự kiện:
Không có khái niệm toàn cục của thời gian.
Nhịp độ đồng hồ trôi: nhịp độ tương đối ở một đồng hồ máy tính trôi dạt ra khỏi từ một đồng hồ tham chiếu hoàn hảo.
Đồng bộ hóa đồng hồ:
Hệ thống định vị toàn cầu (GPS): một ít máy tính có thể sử dụng máy thu radio để nhận thời gian đọc từ GPS với độ chính xác là 1 micro-giây. Chúng có thể gữi các thông điệp thời gian đến các máy tính khác trong mạng tương ứng của chúng.
Các đồng hồ logic: mỗi thông điệp là thời gian đóng dấu lên với một số nối tiếp mà phản chiếu thứ tự lôgic của chúng. GVHD: PGS.TS. Lê Văn Sơn Trang 7 HVTH: Lê Quốc Dũng -KHMT K16 Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Tiểu luận Hệ Phân Tán CHƯƠNG II: GIẢI QUYẾT VẤN ĐỀ NHIỀU BẢN SAO I.Đặt vấn đề Tại sao sử dụng bản sao? Có hai lý do sau đây: - Tăng độ tin cậy và tính sẵn sàng của hệ thống: 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 đó để hệ thống 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. - Tăng hiệu năng của hệ thống: có thể tăng quy mô hệ thống 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 hệ thống 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 hệ thống. 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. II.Các mô hình nhất quán lấy dữ liệu làm trung tâm 1. Mô hình nhất quán chặt 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 đó. Mô hình này khó áp dụng cho hệ phân tán. 2. Mô hình nhất quán tuần tự và mô hình nhất quán tuyến tính 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. 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 chương trình của nó 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ự. 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ó. Thêm vào đó, nếu tsop1(x) < tsop2(y) thì thao tác op1(x) phải được thực hiện trước op2(y) trong chuỗi thao tác. 3. Mô hình nhất quán 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. 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. 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. 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 GVHD: PGS.TS. Lê Văn Sơn Trang 8 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn 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. 5. Mô hình nhất quán yếu 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ộ. - 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. Mô hình nhất quán đi ra - 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ự). 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 đó. - 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. III. Các mô hình nhất quán lấy client làm trung tâm 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.. 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. 2. Nhất quán đọc đều 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. Client sẽ luôn nhìn thấy những dữ GVHD: PGS.TS. Lê Văn Sơn Trang 9 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn 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 đó. 3. Nhất quán ghi đều 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. 4. Nhất quán đọc thao tác ghi 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 đó. 5. Nhất quán ghi theo sau đọc 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 đó. IV. Các giao thức phân phối 1. Phân loại bản sao Có 3 loại 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 hệ thống 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. 2. Lan truyền cập nhật Có 3 cách 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. GVHD: PGS.TS. Lê Văn Sơn Trang 10 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Hai các tiếp cận lan truyền cập nhật: Đẩ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. V. Phân tích vấn đề Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý hoặc bộ vi xử lý nằm tại các vị trí khác nhau và được liên kết với nhau thông qua hệ thống viễn thông dưới sự điều hành thống nhất của một hệ điều hành. Hệ phân tán được xây dựng nhằm mục đích phân tán hoá các quá trình xử lý thông tin và thực hiện công việc đó trên các trạm xa nhau. Đó là những cơ sở căn bản cho việc xây dựng các ứng dụng lớn như thương mại điện tử, giáo dục điện tử, thư viện điện tử số, xây dựng các cơ sở dữ liệu tìm kiếm… Thời gian truy cập trung bình vào thông tin trong hệ phân tán có thể được rút ngắn, nhờ vào phương pháp nhân nhiều bản và được gọi là nhiều bản sao của một đối tượng thông tin. Trong các hệ loại này, từng hệ thống cục bộ đều có lưu trữ một bản sao của tất cả các thông tin liên quan đang có ở tất cả các hệ cục bộ. Ưu điểm nổi bậc của kiểu tổ chức này là: 1. Dễ dàng thực hiện việc truy cập thông tin cần thiết cho các yêu cầu ngay tại hệ thống cục bộ của mình. 2. Cho kết quả truy cập một cách nhanh chóng. Tuy nhiên, kiểu truy vấn này chỉ cho kết quả tương đối chính xác và phụ thuộc rất nhiều vào phương pháp và thời hạn cập nhật thông tin trong các cơ sở dữ liệu cục bộ. Sự tồn tại nhiều bản sao trong hệ phân tán có thể dẫn đến các hệ quả sau : 1. Cập nhật thông tin diễn (gần hoặc xa) hoặc sự thay đổi thông tin cục bộ trên một hệ cục bộ nào đó cần phải được tiến hành cho tất cả các hệ thống cục bộ và không được phép bỏ sót hệ nào cả. Trong khoảng thời gian làm tươi thông tin phải đảm bảo sao cho việc truy vấn dữ liệu cho kết quả kịp thời hoặc đặt truy vấn trong trạng thái treo. 2. Cần phải tránh trường hợp các thao tác trên hai bản sao khác nhau nhưng chứa cùng thông tin được truy cập bởi hai hay nhiều yêu cầu dẫn đến không gắn bó . Ví dụ : một mặt hàng nào đó đã cung cấp cho khách hàng rồi thì không được phép cung cấp cho khách hàng tiếp theo nữa. Hai vấn đề vừa nêu trên xác định về các ràng buộc đối với đề gắn bó dữ liệu . Nhằm đảm bảo sự gắn bó này điều kiện đủ là bắt buộc tuân thủ trình tự nào đó cho tất cả các bản sao, các cập nhật thông tin. Biện pháp hàng đầu là áp dụng cơ chế then cài nhằm thực hiện việc loại trừ tương hỗ tổng quát trên tập hợp các bản sao, biện pháp này có mặt hạn chế là không cho phép các chương trình thực hiện song song. Một biện pháp khác là cho phép thực hiện các giao dịch trên tất cả các bản sao và thực hiện cùng một trình tự cho mỗi hệ thống cục bộ. Khó khăn trong việc triển khai trình tự tổng quát có thể GVHD: PGS.TS. Lê Văn Sơn Trang 11 HVTH: Lê Quốc Dũng -KHMT K16 Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Tiểu luận Hệ Phân Tán so sánh với khó khăn của biện pháp đầu tiên đã nêu, nhưng lại cho phép các chương trình hoạt động song song. Trong môi trường phân tán, sơ đồ vị trí của các bản sao và việc cập nhật chúng có thể mô tả trong hình vẽ sau đây. Các bản sao có thể đặt trên các server S1, S2,...,Sn trên các tập tin hay vùng nhớ đặc biệt eij, i=1..n, j=1..m, trong đó i chỉ server, j chỉ bản sao, n là số lượng server được mắc nối trong mạng, m là số lượng các bản sao cần phải cập nhật. Mỗi server có thể quản lý một mạng con. Ngoài ra, các bản sao có thể được bố trí trên các trạm thể hiện bằng các tk, k=1..q, k là trạm và q là số trạm được mắc nối. Nếu ta có n bản sao của đối tượng e nào đó, thì ràng buộc toàn vẹn phải là: Trên bản sao của 1 đối tượng e1=e2=e3=...=en Trên các bản sao của toàn bộ các đối tượng e11=e21=...=en1 e12=e22=...=en2 ... e1m=e2m=...=enm Để tham chiếu đến đối tượng e, cần thực hiện giao dịch sau (áp dụng thuật toán then cài): V_doc(ei) Doc(ei) Giai_phong(ei) Để thực hiện việc cập nhật vào các bản sao , ta cần phải cài then chúng như sau (áp dụng thuật toán then cài): Để cho i:=1 đến n thực hiện V_viet(ei) < thực hiện các cập nhật và chép lại chúng vào tất cả các bản > Để cho i:=1 đến n thực hiện Giai_phong(ei) GVHD: PGS.TS. Lê Văn Sơn Trang 12 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Để tránh bế tắc diễn ra, việc cài then các bản sao luôn luôn phải được thực hiện trong cùng một trật tự. Nói cách khác, hoặc là đối tượng đang trong quá trình cập nhật và tất cả các bản sao của nó được dự trữ cho tiến trình thực hiện cập nhật, hoặc là tất cả các bản sao được truy cập chỉ để đọc và giống nhau hoàn toàn. Gọi M là cực đại của các cập nhật có thể diễn ra đồng thời, thì M có thể tính theo công thức M=n x m. Căn cứ vào nội dung thông tin cần phải đảm bảo sự gắn bó mà người ta chia ra hai loại giải thuật: • Giải thuật toán gắn bó mạnh • Giải thuật toán gắn bó yếu. Hệ thống viễn thông là đối tượng có thể diễn ra các sự cố kỹ thuật và ùn tắt đường truyền, ta có số lần truy cập bản sao trên thực tế sẽ lớn hơn M rất nhiều; hiệu năng hoạt động của hệ trong trường hợp này sẽ bị giảm. Một trong những giải pháp khắc phục vấn đề vừa nêu là áp dụng kỹ thuật đánh dấu bản điều khiển và căn cứ vào hệ thống tín hiệu này, người ta có thể chọn các giải thuật cập nhật thích hợp, rút ngắn được tốc độ cập nhật bình quân. GVHD: PGS.TS. Lê Văn Sơn Trang 13 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn CHƯƠNG III: MỘT SỐ THUẬT TOÁN QUẢN LÝ NHIỀU BẢN SAO I.Thuật toán đảm bảo sự gắn bó yếu nhờ dấu 1.Nguyên lý Tập hợp các yêu cầu cập nhật được sắp xếp theo cùng một kiểu trên tất cả các trạm nhờ cơ chế dấu. Theo đó mỗi một yêu cầu được phát đi cho tập hợp các trạm. Trên mỗi trạm, tồn tại một tiến trình Server đảm nhận nhiệm vụ tiếp nhận các yêu cầu theo trật tự của dấu. Điều đó cho phép có được một sự gắn bó yếu giữa các bản sao. 2.Triển khai hệ ổn định Các giao dịch cần xét là các khả năng đọc, ghi hay cập nhật. Cập nhật được xác định như là một dãy các thao tác đọc và ghi, thao tác kiểm tra đọc tức thì trạng thái hiện hành của một bản sao. Mỗi một server tiếp nhận các yêu cầu ghi đến từ trạm cục bộ ở thời điểm cho trước. Nó tiếp nhận các yêu cầu và tính toán trên cơ sở dấu theo tiêu chí lâu nhất. Khi trạm i truyền các thông điệp cho trạm j, Trật tự nhận các thông điệp tại j là hoàn toàn giống với trật tự của các thông điệp phát đi. Giả thiết này được kiểm tra trong các mạng thông thường. Việc xác định các yêu cầu cần xử lý trên một trạm là hoàn toàn có thể . Có 2 trường hợp cần xem xét: STT Trường hợp 1 Tập hợp các yêu cầu ghi khi chờ chứa các yêu cầu từ tất cả các trạm khác. Trong trường hợp này các yêu cầu đi qua, nếu chúng tồn tại, là mới hơn so với các yêu cầu đã đi qua. Nói cách khác, yêu cầu lâu nhất chính là yêu cầu đang chờ. 2 Tồn tại các trạm mà không có bất kỳ yêu cầu nào được truyền đến. Ta được đưa các trường hợp trước đây bằng cách truyền cho tất cả các trạm một thông điệp yêu cầu và bắt buột phải xác nhận. Do vây, sau một khoảng thời gian, theo giả thiết về độ ổn định, ta sẽ nhận hoặc là các yêu cầu đi qua, hoặc là các trả lời cho thông điệp yêu cầu. Lúc này, ta có được các thông điệp đến từ tất cả các trạm. 3. Các hành vi ngoài chế độ bình thường Hai vấn đề mở rộng hơn đối với thuật toán này cho phép rút ra hay chen vàotùy ý một trạm nào đó. Ngược lại, thuật toán chỉ sống trong trường hợp có sự cố, nếu các điều kiện sau đây được tôn trọng: Điều kiện STT 1 Việc đột nhiên biến mất đi một trạm nào đó phải được các trạm khác nhận biết tự động. 2 Việc phát một thông điệp là một phép toán không chia cắt được nữa. Đó là một thông điệp hoặc là tất cả đều phải nhận được hoặc là không trạm nào nhận được cả. GVHD: PGS.TS. Lê Văn Sơn Trang 14 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Vì vậy, việc tuân thủ hai điều kiện trên đặt ra cho chúng ta tình hình là nếu điều kiện đầu tiên có thể được khống chế, thì điều kiện thứ hai rất khó đảm bảo II.Thuật toán đảm bảo sự gắn bó yếu nhờ bộ tuần tự tuần hoàn. 1.Nguyên lý Trước khi phát một yêu cầu, một trạm nào đó cần phải kết hợp với nó một số thứ tự được cấp từ bộ tuần tự tuần hoàn. Các yêu cầu được tiếp nhận tại mỗi trạm theo cùng một trật tự thống nhất. Điều đó giúp ta có được một sự gắn bó yếu. Cần quan tâm rằng cơ chế phân phối các số dựa trên nền tảng tổ chức các trạm theo kiểu vòng tròn ảo. 2.Triển khai hệ ổn định Bộ tuần hoàn tự cung cấp cho mỗi một yêu cầu số sắp tới còn chưa dùng, giả sử đó là T. Khi đến phiên của trạm nhận bộ tuần tự, nó yêu cầu một số lượng n số đúng bằng số lượng các yêu cầu cập nhật đang chờ trên trạm này. Các số này là: T, T + l , … , T + n - 1 Nó tiếp tục chuyển bộ tuần tự cho trạm kề liền sau nó và số sắp tới chưa dùng đến là T+n. Khi một trạm đã có số, nó phát yêu cầu cập nhật cùng với số này. Trên mỗi trạm, các cập nhật được thực hiện bằng cách tiếp nhận các yêu cầu cùng các số liên tiếp nhau. Để xác định yêu cầu sắp đến cần phải xử lý, mỗi trạm một duy trì một biến chứa số V được phối hợp với yêu cầu xử lý cuối cùng. Các yêu cầu mang số lớn hơn V + 1 được lưu trữ trong khi chờ xử lý yêu cầu V+1. Chú ý 1: Việc phát đi các yêu cầu có thể sử dụng trong vòng tròn, nhưng điều đó không phải là bắt buộc. Chú ý 2: Một trạm khi đã rút một lượng số cần phải được sử dụng hết khi nó đến lượt tiếp theo tiếp nhận bộ tuần tự, nếu không các trạm khác sẽ phải chờ. 3.Các hành vi ngoài chế độ bình thường Hiện tại, người ta đã chế tạo thành công và đưa vào sử dụng một cách ổn định trong mạng một số giao thức cho phép tái sinh bộ tuần tự khi bộ này bị mất và đặt cấu hình vòng tròn ảo trở lại theo kiểu tự động. Các giao thức này hoạt động trong điều kiện giả định là mạng viễn thông cho phép phát hiện các sự cố của một trạm và cần phải được bổ khuyết đầy đủ nhằm duy trì trật tự toàn phần cần thiết cho việc gắn bó: 1. Việc tái sinh bộ tuần tự cần phải tiến hành song song với việc tính toán số sắp đến có sẵn để dùng. 2. Khi ta phát hiện có một trạm bị sự cố, ta cần phải xác định các số mà trạm này đã lấy và các số còn chưa sử dụng, rồi gửi các yêu cầu có mang các số này. 3. Việc cho hội nhập một trạm vào lại trong vòng tròn cần phải tiến hành song song với việc cập nhật lại bản sao của nó. Sử dụng các số liên tục cho phép tránh được hiện tượng một vài cập nhật bị mất và các lần mất mà không được phát hiện. Việc triển khai một bộ tuần tự tuần hoàn cũng làm cho ta gặp phải một số khó khăn của nó. Trên thực tế, các trạm bị sự cố không thể nào phục vụ số được, bộ cung cấp cần phải tìm lại số lượng và giá trị của các số đó. Để thực hiện được điều đó, cần phải hội thoại với các trạm khác. GVHD: PGS.TS. Lê Văn Sơn Trang 15 HVTH: Lê Quốc Dũng -KHMT K16 Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Tiểu luận Hệ Phân Tán III.Thuật toán đảm bảo sự gắn bó mạnh 1.Nguyên lý Tập hợp bao gồm các trạm được tổ chức theo kiểu vòng tròn ảo. Các cập nhật được thực hiện theo hai thì: 1. Thống nhất giữa các trạm 2. Thực hiện cập nhật Do vậy, thuật toán này đảm bảo một sự gắn bó mạnh. Nếu có nhiều yêu cầu cập nhật diễn ra đồng thời thì ta phải có quy tắc để có thể quyết định yêu cầu nào được tiếp nhận và thỏa mãn. Nhằm phục vụ cho ý tưởng đó, ta thường hay sử dụng dấu phối hợp cho mỗi cập nhật và ta xử lý yêu cầu có thời gian dấu lâu nhất. 2.Triển khai hệ ổn định Trạng thái có thể của mỗi trạm là: STT Trạng thái Giải thích 1 Nghỉ ngơi Trạm không thực hiện cập nhật nào cả. 2 Hoạt động Trạm đã nhận một yêu cầu cập nhật cục bộ mà yêu cầu này đã được truyền cho các trạm khác để kiểm tra. 3 Thụ động Trạm đã đồng ý cho một cập nhật và chờ trật tự tương ứng. Cập nhật Trạm đang trong tình trạng chuyển của cập nhật, trong khi đó tất cả các yêu cầu khác truyền đến đều được lưu trữ. Chúng sẽ được xử lý khi quay về một trong các trạng thái khác. 4 Lúc khởi sự, tất cả các trạm đều trong trạng thái nghỉ ngơi. Trạm khởi sự việc cập nhật, đầu tiên, cần phải gửi một yêu cầu cho phép cập nhật, nó chỉ làm được công việc đó trong trạng thái nghỉ ngơi. Lúc này nó được nhận dấu và được gửi vào vòng tròn, trạm khởi sự chuyển trạng thái từ nghỉ ngơi sanhg hoạt động. Nếu chỉ có một yêu cầu duy nhất được đưa vào vòng tròn, nó đi qua tất cả các trạm để chuyển các trạm này từ nghỉ ngơi sang thụ động, Khi nó đã trở về nơi khởi sự thì việc thống nhất coi như hoàn tất. Việc cập nhật nói riêng lúc này được gởi đi và mỗi trạm sau khi thực hiện lại trở về trạng thái nghỉ ngơi. Nếu có nhiều yêu cầu được đưa ra đồng thời trong vòng tròn, thì tình hình đó dễ dàng diễn ra xung đột. Lúc này, ta phải chọn một yêu cầu có thời gian dấu lâu nhất. Để tiến hành công việc đó, ta nêu bật vai trò của "bộ chắn đường" (barrage) cho các trạm khởi sự. Một trạm nào đó trong trạng thái nghỉ ngơi hay thụ động phải chuyển toàn bộ yêu cầu đã đến với nó; một trạm trong trạng thái hoạt động chỉ phải chuyển các yêu cầu có thời gian lâu hơn các yêu cầu mà chính nó đã phát đi; các yêu cầu khác đều bị dừng lại và được lưư trữ. Các yêu cầu bị lưu lại sẽ được gửi tiếp vào vòng tròn, khi trạm lưư trữ chúng hoàn thành việc cập nhật riêng của mình. GVHD: PGS.TS. Lê Văn Sơn Trang 16 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn 3.Các hành vi ngoài chế độ bình thường Các giao thức đặt lại cấu hình vòng tròn theo kiểu tự động được sử dụng nhằm rút ra hay cho vào tùy ý một số trạm nhất định. Các sự cố kỹ thuật là rất khó khăn phát hiện trong các chiến lược mà ở đó các yêu cầu không được ghi lại khắp nơi trong mạng. GVHD: PGS.TS. Lê Văn Sơn Trang 17 HVTH: Lê Quốc Dũng -KHMT K16 Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Tiểu luận Hệ Phân Tán CHƯƠNG III: KỶ THUẬT ĐÁNH DẤU BẢN ĐIỀU KHIỂN I.Kỹ thuật đánh dấu bản điều khiển Kỹ thuật đánh dấu bản điều khiển gọi tắt là TOMCP (Technique Of Marking the Control Panel) là một hệ thống bao gồm các chương trình, danh sách tài nguyên cần thiết để thực hiện các lệnh và tổ hợp các tín hiệu cho phép nhận biết trạng thái của toàn bộ các bản sao đang được sử dụng trong hệ. Thành phần cơ bản của TOMCP có thể mô tả trong hình vẽ sau đây: Chương trình quản lý TOMCP được xây dựng dưới dạng thủ tục tiện ích với chức năng chủ yếu là kiểm tra tính hợp thức của việc truy cập vào bản, dò tìm thông tin, cập nhật các tín hiệu và yêu cầu được cung cấp tài nguyên theo danh sách,... Thủ tục này là một trong những thành phần cơ bản của tác tử. Danh sách các tài nguyên cần thiết là tổ hợp các các thiết bị, chương trình và dữ liệu phục vụ cho việc quản lý TOMCP. Hệ thống các tín hiệu nhận dạng là tập hợp các chuẩn hình thành trong quá trình thiết kế hệ phục vụ cho việc nhận biết tự động trạng thái của hệ quản lý nhiều bản sao và xác định GTl cần thực hiện. Nội dung cơ bản của kỹ thuật này là tại mỗi tác tử di động, trạng thái các bản sao trên toàn bộ hệ thống được thể hiện một cách chính xác và nhờ đó các tác tử biết cần phải hành động như thế nào là tối ưu nhất. Mỗi khi cập nhật, thay vì phải kích hoạt một trình điều khiển như mô hình Client/Server chứa sẵn trên Server và gửi toàn bộ các yêu cầu thay đổi, thì kỹ thuật này cho phép chỉ gửi những chi tiết cần thay đổi là đủ. Việc làm tươi thông tin trong bản điều khiển sẽ do các tác tử thực hiện tự động căn cứ vào dữ liệu mà nó có được. Những thông tin này có khối lượng không lớn và được các tác tử trao đổi với nhau bằng thông điệp. Hai tác tử quan trọng trong tiến trình truy cập bản để đọc và ghi bản là tác tử gửi thông điệp (tác tử yêu cầu) và tác tử nhận thông điệp (tác tử đáp ứng yêu cầu). II.Cấu trúc của các thông điệp. Cấu trúc của các thông điệp trao đổi giữa các tác tử có thể mô tả trong hình vẽ dưới đây. GVHD: PGS.TS. Lê Văn Sơn Trang 18 HVTH: Lê Quốc Dũng -KHMT K16 Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn Tiểu luận Hệ Phân Tán Các trường của thông điệp trao đổi là: 1 START Bắt đầu Giá trị 8 bít cho phép bắt đầu thông điệp. Địa chỉ tác tử gửi thông điệp với độ dài từ 8 bít đến 16 bít đủ để biểu diễn số lượng địa chỉ của các tác tử trong các hệ thống lớn. 2 SOURCE Địa chỉ nguồn 3 TARGET Địa chỉ đích Địa chỉ của tác tử nhận với độ dài của trường từ 8 bít đến 16 bít. Mã sử dụng để nhận biết phép toán trên bản với độ dài là 8 bít. 4 CODE Mã 5 INFORMATION Thông tin Thông tin cần thiết để truy cập vào các bản sao. Kiểm tra Trường kiểm tra phục vụ cho việc truyền dữ liệu qua mạng và các giá trị được quy ước cho từng loại mạng cụ thể. Kết thúc Giá trị 8 bít cho phép kết thúc thông điệp. 6 CONTROL 7 END Giá trị các bít của trường CODE được thể hiện trong hình dưới đây. Ưu điểm căn bản của kỹ thuật đánh dấu bản điều khiển là: 1 Gắn bó 2 Tin cậy Đảm bảo tính gắn bó thông tin. Hệ thống hoạt động với kỹ thuật này chịu đựng được trạng thái lỗi của mạng nói chung, trong đó có lỗi của hệ thống đường truyền. 3 Nhạy Phản ứng được với các tình huống sinh lỗi. 4 Liên tục Cho phép phân phối động các tài nguyên cần cập nhật. 5 Phát hiện sự cố Phát hiện các lỗi phát sinh trong quá trình vận hành. 6 Thống kê Biết được trạng thái cập nhật ở mọi thời điểm. GVHD: PGS.TS. Lê Văn Sơn Trang 19 HVTH: Lê Quốc Dũng -KHMT K16 Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn B. PHẦN BÀI TẬP THUẬT TOÁN XỬ LÝ CÁC THAO TÁC ĐỌC – GHI I.Trình tự thực hiện cập nhật bản điều khiển Các thông điệp trao đổi được sử dụng với các mục đích khác nhau căn cứ vào nội dung của trường CODE. Tác tử gửi ghi thông tin yêu cầu dưới dạng mã vào trường này, còn tác tử nhận sẽ căn cứ vào mã đó để nhận biết sẽ phải hành động như thế nào trên bản sao. Việc xử lý trạng thái điều khiển do tác tử nhận tiến hành trên cơ sở tham chiếu thông tin trong bản điều khiển và theo yêu cầu thể hiện trong hình sau đây. Sau khi hoàn thành trọn vẹn công việc, tác tử nhận tiến hành phát thông điệp đến toàn bộ các tác tử của hệ thống để cập nhật vào bản điều khiển, đồng thời tự động cập nhật vào bản cục bộ của mình. II.Sơ đồ tổng quát xử lý nhiều bản sao Các bước thể hiện công việc xử lý thông tin điều khiển được tiến hành tuần tự như sau: GVHD: PGS.TS. Lê Văn Sơn Trang 20 HVTH: Lê Quốc Dũng -KHMT K16