Luận văn Thạc sĩ Khoa học máy tính: Ứng dụng máy trạng thái trong quản lý giao tác

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:71

Thêm vào BST

Báo xấu

19
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn tập trung nghiên cứu tìm hiểu khái quát cơ sở dữ liệu phân tán, các bài toán cập nhật nhiều bản sao. Ngoài ra, còn tìm hiểu về máy trạng thái và các nghi thức thỏa thuận. Từ đó xây dựng chương trình ứng dụng máy trạng thái để quản lý các giao tác một cách hiệu quả. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Ứng dụng máy trạng thái trong quản lý giao tác

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ĐÀM THỊ THANH HẰNG ỨNG DỤNG MÁY TRẠNG THÁI TRONG QUẢN LÝ GIAO TÁC LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2018
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ĐÀM THỊ THANH HẰNG ỨNG DỤNG MÁY TRẠNG THÁI TRONG QUẢN LÝ GIAO TÁC Chuyên ngành: Khoa học máy tính Mã số: 84 801 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS TSKH NGUYỄN XUÂN HUY THÁI NGUYÊN - 2018
i LỜI CAM ĐOAN Trong quá trình làm luận văn học viên hoàn toàn sử dụng những kiến thức đã tổng hợp được từ các nguồn tài liệu có xuất xứ rõ ràng và được trích dẫn hợp pháp. Học viên xin chịu trách nhiệm về những lời nói trên và nhận mọi hình thức kỷ luật theo quy định nếu như làm sai. Thái Nguyên, tháng 04 năm 2018 Học viên Đàm Thị Thanh Hằng
ii LỜI CÁM ƠN Để hoàn thành luận văn “Ứng dụng máy trạng thái trong quản lý giao tác” học viên đã nhận được sự hướng dẫn và giúp đỡ nhiệt tình của nhiều tập thể và cá nhân. Trước hết, học viên xin bày tỏ lòng biết ơn chân thành đến ban lãnh đạo cùng quý thầy cô trong khoa Công nghệ thông tin – Trường Đại học Công nghệ và truyền thông, Đại học Thái Nguyên đã tận tình dạy dỗ, truyền đạt kiến thức, kinh nghiệm và tạo điều kiện thuận lợi cho học viên trong suốt thời gian học tập và thực hiện đề tài. Đặc biệt, xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dẫn PGS TSKH. Nguyễn Xuân Huy, người đã gợi cho học viên những ý tưởng về đề tài, đã tận tình hướng dẫn và giúp đỡ để đề tài được thực hiện và hoàn thành. Xin trân trọng gửi đến gia đình, bạn bè và người thân những tình cảm tốt đẹp nhất đã giúp đỡ động viên trong suốt khóa học và hoàn thành luận văn. Thái Nguyên, tháng 04 năm 2018 Học viên Đàm Thị Thanh Hằng
iii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CÁM ƠN ............................................................................................................ ii MỤC LỤC ................................................................................................................. iii DANH MỤC HÌNH ....................................................................................................v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ............................................ vi MỞ ĐẦU .....................................................................................................................1 1. Lý do chọn đề tài .................................................................................................1 2. Đối tượng nghiên cứu .........................................................................................1 3. Bố cục của luận văn ...........................................................................................1 CHƯƠNG 1 TỔNG QUAN VỀ HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ BÀI TOÁN CẬP NHẬT NHIỀU BẢN SAO .....................................................................3 1.1. Cơ sở dữ liệu phân tán ...................................................................................3 1.2. Hệ quản trị cơ sở dữ liệu phân tán ..................................................................5 1.3. Vấn đề phân tán dữ liệu ..................................................................................6 1.3.1. Sự phân mảnh dữ liệu (Fragmentation) ...................................................7 1.3.2 Tạo bản sao (Replication) ..........................................................................9 1.4. Bài toán cập nhật nhiều bản sao .....................................................................10 CHƯƠNG 2 MÁY TRẠNG THÁI VÀ CÁC NGHI THỨC THỎA THUẬN PHÂN TÁN ...............................................................................................................12 2.1. Máy trạng thái ...........................................................................................12 2.2. Tổng quan về quản lý giao tác và các nghi thức thỏa thuận phân tán ...........22 2.2.1. Các tính chất của giao tác .....................................................................24 2.2.2. Thỏa thuận phân tán và nghi thức thỏa thuận đơn giản ........................26 2.2.3. Nghi thức thỏa thuận hai pha (Two-phase commit – 2PC) ....................31 2.2.4. Nghi thức thỏa thuận ba pha (Three-phase commit – 3PC) ...................35 2.3. Khôi phục trong thỏa thuận phân tán .............................................................41 2.3.1. Khôi phục trong thỏa thuận hai pha .......................................................41 2.3.2. Khôi phục trong thỏa thuận ba pha ........................................................41 CHƯƠNG 3 CÀI ĐẶT CHƯƠNG TRÌNH VÀ THỬ NGHIỆM ...........................45
iv 3.1. Tổ chức dữ liệu ............................................................................................45 3.2.1. Kịch bản dựng sẵn ..................................................................................45 3.2.2. Kịch bản ngẫu nhiên ...............................................................................46 3.2. Thử nghiệm và đánh giá ..............................................................................49 KẾT LUẬN ...............................................................................................................60 HƯỚNG PHÁT TRIỂN CỦA LUẬN VĂN.............................................................61 Tài liệu tiếng Việt: ................................................................................................63 Tài liệu tiếng Anh: ................................................................................................63
v DANH MỤC HÌNH Hình 1.1: Cấu trúc mẫu của một cơ sở dữ liệu phân tán ............................................3 Hình 2. 1. Sơ đồ trạng thái hoạt động của thang máy/cabin ...................................16 Hình 2. 2. Sơ đồ hoạt động của thang máy khi phát hiện có khói ............................17 Hình 2. 3. Sơ đồ trạng thái của việc thanh toán khi bán hàng .................................18 Hình 2. 4. Mô hình máy bán vé tự động ....................................................................20 Hình 2. 5. Trạng thái làm việc của máy bán vé tự động ...........................................21 Hình 2. 6. Sơ đồ trạng thái của thành viên trong thỏa thuận đơn giản ....................28 Hình 2. 7. Sơ đồ trạng thái của điều phối viên trong thỏa thuận đơn giản ..............29 Hình 2. 8. Sơ đồ trạng thái của thành viên trong thỏa thuận hai pha ......................33 Hình 2. 9. Sơ đồ trạng thái của điều phối viên trong thỏa thuận hai pha ................34 Hình 2. 10. Sơ đồ trạng thái của thành viên trong thỏa thuận ba pha .....................37 Hình 2. 11. Sơ đồ trạng thái của điều phối viên trong thỏa thuận ba pha ...............39
vi DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Từ tiếng Anh Nghĩa tiếng Việt Coordinator điều phối viên Participant thành viên Distributed commit thỏa thuận phân tán Initial trạng thái khởi đầu Deciding quyết định Begin-vote thông báo biểu quyết Vote-commit biểu quyết thỏa thuận Vote-abort biểu quyết hủy bỏ Willing-to-commit mong muốn thỏa thuận Commit/Committed: quyết định thỏa thuận/ đã được thỏa thuận Abort/Aborted quyết định hủy bỏ/ đã hủy bỏ Must Abort chắc chắn hủy bỏ Must Commit chắc chắn thỏa thuận Recover khôi phục Blocked phong tỏa Prepare-commit thông báo đồng ý chấp nhận thỏa thuận Ready to commit sẵn sàng thỏa thuận
1 MỞ ĐẦU 1. Lý do chọn đề tài Trong xu hướng toàn cầu hóa hiện nay, để phù hợp với nhu cầu phát triển, các tổ chức thường phân bố các chi nhánh phân tán trên nhiều vị trí địa lý khác nhau. Lúc này, việc sử dụng hệ cơ sở dữ liệu tập trung chỉ với duy nhất một hoặc một vài Sever phục vụ đa người dùng là không còn phù hợp. Bởi với một bài toán dữ liệu lớn sẽ gặp nhiều vấn đề khó khăn như hiệu năng khai thác không cao, dễ xảy ra ùn tắc, tốc độ chậm, không an toàn... Việc sử dụng cơ sở dữ liệu phân tán và hệ cơ sở dữ liệu phân tán là giải pháp phù hợp để giải quyết vấn đề nêu trên. Việc sử dụng nhiều Server đặt tại nhiều vị trí địa lý khác nhau không những giúp cho các Client truy xuất những dữ liệu tại vị trí của mình mà còn có thể truy cập đến dữ liệu tại các vị trí khác. Tuy nhiên, một trong những vấn đề khó khăn trong bài toán đặt ra đó là làm thế nào để có thể quản lý được các giao tác phân tán này một cách hiệu quả nhất, nhằm hạn chế tối đa những sự cố có thể xảy ra như: không nhất quán dữ liệu giữa các nút mạng khác nhau. Đó cũng là lí do mà học viên đã lựa chọn đề tài “Ứng dụng máy trạng thái trong quản lý giao tác” với mục đích tìm hiểu các khái niệm, các phương pháp và thuật toán để quản lý được các giao tác một cách hiệu quả. 2. Đối tượng nghiên cứu Trong luận văn tập trung nghiên cứu tìm hiểu khái quát cơ sở dữ liệu phân tán, các bài toán cập nhật nhiều bản sao. Ngoài ra, còn tìm hiểu về máy trạng thái và các nghi thức thỏa thuận. Từ đó xây dựng chương trình ứng dụng máy trạng thái để quản lý các giao tác một cách hiệu quả. 3. Bố cục của luận văn Phần mở đầu: Nêu lý do chọn đề tài, đối tượng nghiên cứu và bố cục của luận văn
2 Phần nội dung: gồm ba chương chính: Chương 1: TỔNG QUAN VỀ HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ BÀI TOÁN CẬP NHẬT NHIỀU BẢN SAO - Giới thiệu tổng quan về hệ cơ sở dữ liệu phân tán. - Bài toán cập nhật nhiều bản sao Chương 2: MÁY TRẠNG THÁI VÀ CÁC NGHI THỨC THỎA THUẬN PHÂN TÁN Giới thiệu về mô hình máy trạng thái và các nghi thức thỏa thuận phân tán Chương 3: CÀI ĐẶT CHƯƠNG TRÌNH VÀ THỬ NGHIỆM 3.1 Tổ chức dữ liệu 3.2 Thử nghiệm và đánh giá
3 CHƯƠNG 1 TỔNG QUAN VỀ HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ BÀI TOÁN CẬP NHẬT NHIỀU BẢN SAO Khái niệm hệ cơ sở dữ liệu phân tán ở đây bao gồm khái niệm cơ sở dữ liệu phân tán và hệ quản trị cơ sở dữ liệu phân tán. 1.1. Cơ sở dữ liệu phân tán Cơ sở dữ liệu phân tán là một tập hợp các cơ sở dữ liệu có quan hệ logic với nhau, được phân phối trên các máy tính khác nhau của một mạng máy tính (được gọi là các nút, trạm hay là site) nhưng vẫn đảm bảo tính nhất quán trên toàn bộ cơ sở dữ liệu và khai thác giống như trên cơ sở dữ liệu tập trung [1],[6] Đặc trưng của cơ sở dữ liệu phân tán là các cơ sở dữ liệu được phân bố trên mạng máy tính và có quan hệ với nhau về mặt logic. Cấu trúc chung của một cơ sở dữ liệu phân tán có dạng [2], [5] (Xem hình 1.1) Hình 1.1: Cấu trúc mẫu của một cơ sở dữ liệu phân tán
4 Lược đồ toàn cục: Xác định toàn bộ dữ liệu được lưu trữ trong cơ sở dữ liệu phân tán. Được định nghĩa như trong cơ sở dữ liệu tập trung. Trong mô hình quan hệ: lược đồ toàn cục là các quan hệ và mối liên kết giữa chúng. Lược đồ phân đoạn: Mỗi quan hệ tổng thể có thể được chia thành các phần không giao nhau gọi là phân đoạn (Fragment). Có nhiều cách khác nhau để phân đoạn: Phân đoạn dọc, phân đoạn ngang, phân đoạn hỗn hợp. Các đoạn được mô tả bằng tên của quan hệ tổng thể cùng với chỉ mục đoạn. Ví dụ Ri là đoạn thứ i của quan hệ toàn cục R. Lược đồ định vị: Xác định đoạn dữ liệu nào được định vị tại trạm nào trên mạng. Rij:Cho biết đoạn thứ i của quan hệ tổng thể R được định vị trên trạm j. Lược đồ ánh xạ địa phương: Ánh xạ các ảnh vật lý và các đối tượng được lưu trữ tại một trạm. Ưu điểm của cơ sở dữ liệu phân tán:  Phù hợp với cấu trúc của tổ chức.  Nâng cao khả năng chia sẻ và tính tự trị địa phương.  Tính sẵn sàng của hệ thống cao  Nâng cao tính tin cậy.  Nâng cao hiệu năng  Dễ mở rộng Nhược điểm của cơ sở dữ liệu phân tán:  Thiết kế cơ sở dữ liệu phức tạp hơn  Khó điều khiển tính nhất quán dữ liệu.  Xử lý: Truy vấn tập trung là đơn giản còn truy vấn phân tán phức tạp, khó phát hiện và khử lỗi.  Giá thành cao.  Vấn đề về bảo mật cơ sở dữ liệu được lưu trữ ở nhiều nơi nảy sinh vấn đề: đảm bảo an toàn dữ liệu khi truyền qua mạng.
5  Thiếu chuẩn mực.  Thiếu kinh nghiệm. 1.2. Hệ quản trị cơ sở dữ liệu phân tán Để quản lý cơ sở dữ liệu phân tán, người ta dùng hệ quản trị cơ sở dữ liệu phân tán (DDBMS – Distribute Database Management System). Hệ quản trị cơ sở dữ liệu phân tán là hệ thống phần mềm cho phép quản lý cơ sở dữ liệu phân tán, tạo nên sự phân tán rõ ràng cho người dùng và đảm bảo cho sự phân tán đó là trong suốt đối với người sử dụng [4],[7] Hệ quản trị cơ sở dữ liệu phân tán cung cấp công cụ như tạo lập và quản lý cơ sở dữ liệu phân tán. Hệ quản trị cơ sở dữ liệu phân tán có chức năng hỗ trợ việc tạo và bảo trì cơ sở dữ liệu phân tán, chúng có các thành phần tương tự như một hệ quản trị cơ sở dữ liệu tập trung và các thành phần hỗ trợ trong việc chuyển tải dữ liệu đến các trạm và ngược lại. Hệ quản trị cơ sở dữ liệu thường có các thành phần :  Cơ sở dữ liệu phân tán (distributed database): DDB  Quản trị dữ liệu (database management): DM.  Truyền thông dữ liệu (data communication): DC  Từ điển dữ liệu (data dictionary): DD dùng để mô tả thông tin về sự phân tán của dữ liệu trên mạng. Các dịch vụ của hệ thống trên bao gồm: • Các ứng dụng truy nhập cơ sở dữ liệu từ xa. • Cung cấp các mức trong suốt phân tán. • Hỗ trợ quản trị và điều khiển cơ sở dữ liệu, bao gồm các bộ công cụ, thu thập thông tin từ các trình tiện ích, cung cấp cách nhìn tổng quan về các file dữ liệu trên mạng. • Khả năng mở rộng với các hệ thống khác nhau. • Cung cấp khả năng điều khiển đồng thời và phục hồi các giao tác
6 phân tán. Các hệ quản trị cơ sở dữ liệu phân tán thường hỗ trợ về điều khiển tương tranh và khôi phục các tiến trình phân tán. Hệ quản trị cơ sở dữ liệu phân tán bao gồm hai loại như sau Loại thứ nhất: Hệ quản trị cơ sở dữ liệu phân tán thuần nhất. Trong loại này, cơ sở dữ liệu phân tán được hình thành bằng cách chia một cơ sở dữ liệu thành một tập các cơ sở dữ liệu cục bộ và được quản lý bởi cùng một hệ quản trị cơ sở dữ liệu, cơ sở dữ liệu phân tán có thuần nhất hay không được phụ thuộc bởi các yêu tố phần cứng, hệ điều hành và các hệ quản trị cơ sở dữ liệu cục bộ. Tuy nhiên, hạn chế quan trọng tại hệ quản trị cơ sở dữ liệu cục bộ, bởi vì nó phụ thuộc vào sự quản lý hệ điều hành mạng truyền thông Loại thứ hai: Hệ quản trị cơ sở dữ liệu phân tán không thuần nhất. Trong loại thứ hai, cơ sở dữ liệu phân tán không thuần nhất được tích hợp bởi một tập các cơ sở dữ liệu cục bộ được quản lý bởi các hệ quản trị cơ sở dữ liệu khác nhau. Hệ quản trị cơ sở dữ liệu phân tán không thuần nhất thêm việc chuyển đổi các mô hình dữ liệu của các hệ quản trị cơ sở dữ liệu khác nhau để thống nhất việc quản lý. Nếu việc phát triển cơ sở dữ liệu phân tán theo mô hình Top-down, không phụ thuộc vào hệ thống trước đó (hệ thống các cơ sở dữ liệu cục bộ), thì việc phát triển một hệ thuần nhất là tốt nhất. Tuy nhiên, trong một số trường hợp cần xây dựng cơ sở dữ liệu phân tán từ các cơ sở dữ liệu đã có thì đòi hỏi phải phát triển một hệ không thuần nhất. Phương pháp tốt nhất là tiếp cận từ dưới lên (Bottum-up). 1.3. Vấn đề phân tán dữ liệu Trong nhiều trường hợp các nhà thiết kế ứng dụng không biết dữ liệu phải phân tán ở đâu. Trong phần này chúng ta sẽ phác họa một vài vấn đề liên quan đến việc phân tán dữ liệu.
7 1.3.1. Sự phân mảnh dữ liệu (Fragmentation) Phần lớn các hệ cơ sở dữ liệu phân tán được thiết kế theo hướng từ trên xuống. Thiết kế phân mảnh dữ liệu là công việc đầu tiên phải thực hiện. Mục đích của việc phân mảnh dữ liệu là tạo ra các đơn vị cấp phát logic, sao cho chi phí để thực hiện truy vấn thông tin là thấp nhất. Trước tiên việc phân tán dữ liệu được thực hiện trên cơ sở cấp phát các tập tin cho các nút trên một mạng máy tính. Các nút mạng thường nằm ở các vị trí địa lý khác nhau trải rộng trên một diện tích lớn. Do vậy để tối ưu việc khai thác thông tin thì dữ liệu không thể để tập trung mà phải phân tán trên các nút của mạng. Hơn nữa một quan hệ không phải là một đơn vị truy xuất dữ liệu tốt nhất. Ví dụ như, nếu ứng dụng được thực hiện trên một bộ phận nhỏ các dữ liệu của quan hệ mà quan hệ đó nằm tại các vị trí khác nhau thì có thể gây ra những truy xuất thừa và hơn thế việc nhân bản các quan hệ làm tốn không gian bộ nhớ. Do vậy phân rã một quan hệ thành nhiều mảnh, mỗi mảnh được xử lý như một đơn vị sẽ cho phép thực hiện nhiều giao dịch đồng thời. Một câu truy vấn ban đầu có thể được chia ra thành một tập các truy vấn con, các truy vấn này có thể được thực hiện song song trên các mảnh sẽ giúp cải thiện tốc độ hoạt động của hệ thống. Tuy nhiên chúng ta cũng sẽ gặp những rắc rối của việc phân mảnh, ví dụ nếu các ứng dụng có những xung đột sẽ ngăn cản hoặc gây khó khăn cho việc truy xuất dữ liệu. Phân rã các mảnh nói chung làm tăng chi phí trong việc truy xuất dữ liệu. Một vấn đề nữa liên quan đến việc kiểm soát ngữ nghĩa và tính toàn vẹn dữ liệu. Thiết kế phân mảnh bằng cách nhóm một số bộ trong trường hợp phân mảnh ngang hay nhóm các thuộc tính trong trường hợp phân mảnh dọc có
8 cùng đặc tính theo quan điểm cấp phát. Các mảnh hình thành bằng các phương pháp phân mảnh tạo ra các đơn vị cấp phát dữ liệu khác nhau. Việc phân tán các mảnh dữ liệu của bảng mang lại nhiều thuận lợi. Trong thiết kế cơ sở dữ liệu phân tán, cần thiết phải thực hiện phân mảnh dữ liệu vì những lý do sau đây:  Trong các hệ quản trị cơ sở dữ liệu, các quan hệ được lưu trữ dưới dạng các bảng 2 chiều. Các thao tác đối với cơ sở dữ liệu được thực hiện trên các bảng.  Việc phân rã một quan hệ thành nhiều mảnh, mỗi mảnh được xử lý như một đơn vị dữ liệu, sẽ cho phép thực hiện nhiều giao dịch đồng thời. Hơn nữa kỹ thuật phân tán phải có khả năng cải thiện được thời gian và thực hiện được việc truy xuất dữ liệu từ xa. Thể hiện của các quan hệ chính là các bảng, vì thế vấn đề là tìm những cách khác nhau để chia một bảng thành nhiều bảng nhỏ hơn. Có hai phương pháp khác nhau: Chia bảng theo chiều dọc và chia bảng theo chiều ngang. Chia dọc ta được các quan hệ con mà mỗi quan hệ chứa một tập con các thuộc tính của quan hệ gốc – gọi là phân mảnh dọc. Chia ngang một quan hệ ta được các quan hệ con mà mỗi quan hệ chứa một số bộ của quan hệ gốc – gọi là phân mảnh ngang. Ngoài ra còn có một khả năng hỗn hợp, đó là phân mảnh kết hợp cách phân mảnh ngang và dọc. Một phương pháp thiết kế phân mảnh đúng đắn phải thỏa mãn ba ràng buộc sau [7]: - Tính đầy đủ: Toàn bộ dữ liệu của quan hệ tổng thể phải được ánh xạ vào các đoạn quan hệ và ngược lại. Điều này có nghĩa là, không tồn tại một mục dữ liệu nào thuộc vào quan hệ tổng thể mà không thuộc vào bất kỳ một đoạn nào. - Xây dựng lại: Quan hệ tổng thể có thể được xây dựng lại từ các đoạn mà nó đã tách ra. Điều kiện này là hiển nhiên, bởi vì trong thực tế chỉ có các đoạn
9 được lưu trữ trong cơ sở dữ liệu phân tán, và quan hệ tổng thể phải được xây dựng lại thông qua các đoạn khi cần thiết. - Tính rời nhau: các đoạn được tách ra từ quan hệ tổng thể phải là rời nhau. Vì vậy, việc tạo các bản sao phải rõ ràng với các đoạn được chia. Tuy nhiên, điều kiện này chỉ áp dụng chính vào việc phân đoạn ngang, trong khi việc phân đoạn dọc nhiều khi vẫn được phép vi phạm điều kiện này. 1.3.2 Tạo bản sao (Replication) Replication là một trong những kỹ thuật thường dùng nhất trong cơ sở dữ liệu phân tán. Việc sao chép dữ liệu ở nhiều nơi cung cấp thêm nhiều chức năng bởi vì dữ liệu vẫn có thể được truy xuất nếu một nơi nào đó bị hư hỏng. Nó có khả năng cải tiến được việc thực thi: Việc truy xuất dữ liệu được thực hiện có hiệu quả hơn vì dữ liệu được lấy tại nơi cục bộ hoặc từ một bản sao ở gần đó. Việc cập nhật dữ liệu thường bị chậm bởi vì ta phải cập nhật dữ liệu ở tất cả các bản sao. Do đó việc thực thi replication này thường được áp dụng cho những ứng dụng mà việc cập nhật xảy ra ít hơn truy vấn. Cơ sở dữ liệu được sao thành nhiều bản sao từng phần, hay đầy đủ và được đặt ở hai hay nhiều vị trí trên mạng. Nếu bản sao của cơ sở dữ liệu được lưu trữ tại mọi trạm, ta có trường hợp sao lặp đầy đủ. Phương thức này làm cực đại việc truy nhập tới dữ liệu ở mọi địa phương. Tuy nhiên, phương thức này nảy sinh nhiều vấn đề khi cập nhật dữ liệu (khi có thay đổi dữ liệu ở một cơ sở thì cần được xử lý lại và đồng bộ hóa dữ liệu cho tất cả các vị trí khác). Một kỹ thuật mới hơn cho phép tạo các bản sao không đầy đủ phù hợp với yêu cầu dữ liệu mỗi trạm lưu trữ và một bản sao đầy đủ ở máy dịch vụ. Sau mỗi thời gian, các bản sao được làm đồng bộ với bản chính ở máy dịch vụ bằng một công cụ phần mềm nào đó. Việc quản lý dữ liệu bằng phương pháp dùng nhiều bản sao của một đối tượng thông tin trong hệ phân tán giúp rút ngắn được thời gian truy cập trung bình vào thông tin.
10 1.4. Bài toán cập nhật nhiều bản sao Trong một hệ thống lớn có nhiều người truy nhập với các quyền sử dụng khác nhau và có thể ở mọi địa điểm, chi nhánh lại truy nhập vào cơ sở dữ liệu với mục đích khác nhau, có thể ở từng địa điểm có thể không cần phải dùng đến toàn bộ dữ liệu. Tạo bản sao có thể giải quyết được các vấn đề về hiệu năng (có thể phân tải, giảm băng thông, tăng tốc độ truy cập); Vấn đề về tính sẵn sàng có thể khắc phục nhanh chóng khi dịch vụ bị lỗi hoặc cơ sở dữ liệu bị lỗi. Chính vì vậy ta cần tạo bản sao trong cơ sở dữ liệu nói chung và cơ sở dữ liệu phân tán nói riêng. Sau đây là một số ví dụ về bài toán cập nhật bản sao thường gặp. Bài toán 1: Cập nhật số dư tài khoản ngân hàng A là đơn vị dữ liệu ghi nhận số dư của một khách hàng tại ngân hàng H. Trong đó ngân hàng H lại có nhiều điểm giao dịch (n điểm), tại mỗi điểm giao dịch đều có một bản sao của A. Khi khách hàng gửi thêm tiền vào tài khoản tại một điểm giao dịch i nào đó thì trị số của A trở thành A'. Yêu cầu đặt ra là mọi điểm giao dịch khác chứa bản sao của A đều phải được cập nhật thành A'. Bài toán 2: Bán vé máy bay Hiện nay để thuận tiện cho việc mua và đặt vé các hãng hàng không đều có hệ thống bán vé online hoặc bán vé qua các đại lý. Tại mỗi nút mạng đều chứa các bản sao của tình trạng bán vé của các chuyến bay. Để tiến hành mua hoặc đặt vé online, tại mỗi nút mạng khách hàng cần theo quy trình như sau: - Khách hàng chọn lựa các thông tin cho chuyến bay muốn mua vé: điểm đi, điểm đến, ngày đi, ngày đến sau đó bấm chọn tìm chuyến bay. - Hệ thống sẽ tự động tìm kiếm chuyến bay và đưa ra thông tin về các chuyến bay theo yêu cầu của khách hàng, bao gồm: thời gian bay, mã chuyến
11 bay, loại máy bay, giờ bay, điểm dừng, giá vé phổ thông, giá vé thương gia (thông báo kèm theo số ghế trống hoặc hết vé). Từ những thông tin có được đó khách hàng sẽ quyết định đặt mua vé hay không. Vì là hệ thống online nên tại một thời điểm, có thể có nhiều người cùng truy cập hệ thống và đặt mua vé cùng chuyến đi, cùng thời gian bay. Chính vì vậy danh sách và số ghế của một chuyến bay sẽ bị thay đổi. Tuy nhiên, trong thực tế đôi lúc vẫn xảy ra trường hợp một ghế được bán hai lần. Bài toán đặt ra trong trường hợp này là làm sao để có thể cập nhật dữ liệu cho tất cả các bản sao, để tránh sự cố bán vé trùng lặp như trên. Trong luận văn tập trung tìm hiểu và đưa ra một số thuật toán nhằm giải quyết những bài toán có dạng như trên.
12 CHƯƠNG 2 MÁY TRẠNG THÁI VÀ CÁC NGHI THỨC THỎA THUẬN PHÂN TÁN 2.1. Máy trạng thái Máy trạng thái hữu hạn (finite-state machine - FSM) hoặc máy tự động trạng thái hữu hạn (finite-state automaton - FSA), hoặc là máy tự động hữu hạn, hoặc gọi đơn giản là máy trạng thái, là một mô hình tính toán toán học. Nó là một máy trừu tượng luôn có trạng thái nằm trong tổng hữu hạn các trạng thái tại bất kỳ thời điểm nào. Máy trạng thái hữu hạn có thể chuyển từ trạng thái này sang trạng thái khác để phù hợp với đầu vào; sự thay đổi này được gọi là quá trình chuyển đổi. Máy trạng thái hữu hạn được xác định bởi danh sách các trạng thái của nó, trạng thái khởi đầu, và các điều kiện cho từng sự chuyển đổi trạng thái. Hành vi của máy trạng thái có thể được quan sát qua nhiều thiết bị hiện đại, đó là việc thực hiện một chuỗi các hành động định trước tùy vào chuỗi sự kiện mà chúng được lập trình. Máy trạng thái hữu hạn có công suất tính toán thấp hơn một số mô hình tính toán khác như máy Turing. Sự khác biệt năng lực tính toán cũng có nghĩa là có những bài toán mà máy Turing có thể thực hiện, nhưng máy trạng thái thì không. Nguyên nhân là do bộ nhớ của máy trạng thái bị giới hạn bởi số trạng thái. Máy trạng thái được nghiên cứu trong lĩnh vực tổng quát hơn thuộc lý thuyết tự động. Có thể nói tất cả các đối tượng đều có trạng thái; trạng thái là một trong các điều kiện có thể để đối tượng tồn tại, là kết quả của các hoạt động trước đó đã được đối tượng thực hiện và nó thường được xác định qua giá trị của các thuộc tính cũng như các nối kết của đối tượng với các đối tượng khác.