Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
BÀI TIỂU LUẬN
MÔN LẬP TRÌNH MẠNG
Đề tài 29:
ÁP DỤNG THUẬT TOÁN ELLIS ĐẢM BẢO GẮN BÓ
DỮ LIỆU TRONG CÁC CƠ SỞ DỮ LIỆU PHÂN TÁN
GVHD : PGS.TS Lê Văn Sơn
Học viên : Phí Thị Lệ Tho
LỚP : Cao học Khoa học máy tính – K24
Đà Nẵng, tháng 5 năm 2012
HVTH: Phí Thị Lệ Tho trang 1
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
LỜI NÓI ĐẦU
Ngày nay hầu hết các ứng dụng tin học đều được xây dựng để thực hiện trên
mạng máy tính, các ứng dụng client-server đang ngày càng được sử dụng phổ biến.
Nhưng khi quy mô và mức độ của các ứng dụng tăng lên và yêu cầu về chất lượng, tốc
độ xử lý và độ phức tạp cũng tăng theo thì trên thực tế, một xu hướng kỹ thuật mới ra
đời – xu hướng phân tán các thành phần tạo nên hệ tin học theo hướng tiếp cận nơi sử
dụng và sản xuất thông tin. Song để khai thác có hiệu quả toàn hệ, vấn đề quan trọng
hàng đầu cần phải tính đến là các tài nguyên nói chung, đặc biệt là tài nguyên thông tin
nói riêng và chiến lược khai thác, sử dụng chúng một cách tối ưu nhất.
Với môi trường mạng phân tán này sẽ có nhiều Server đặt ở những nơi
khác nhau người ta gọi là môi trường đa Server. Trong môi trường đa Server
và việc truy cập từ xa có thể truy xuất đồng thời đảm bào toàn vẹn dữ liệu vì
dữ liệu có thể lưu trữ dự phòng trên nhiều Server khác nhau.
Đây là hệ thống đa Server rất phức tạp nhưng hệ thống đảm bảo gắn bó
dữ liệu giữa các Server đồng thời không làm phức tạp việc truy xuất dữ liệu.
Với những thông tin trên nhóm chúng em trình bày chủ đề:
1. Thuật toán Ellis đảm bảo gắn bó dữ liệu trong các CSDL phân tán

này không dẫn đến điều kia. Và vẫn có thể tích hợp mà không cần tập trung hóa.
Đây chính là mục tiêu của công nghệ cơ sở dữ liệu phân tán.
1.2. Định nghĩa cơ sở dữ liệu phân tán
Một cơ sở dữ liệu phân tán là một tập nhiều cơ sở dữ liệu có liên đới logic và
được phân bố trên một mạng máy tính. Vậy hệ quản trị cơ sở dữ liệu phân tán được
định nghĩa là một hệ thống phần mềm cho phép quản trị các hệ cơ sở dữ liệu phân
tán và làm cho việc phân tán trở nên “vô hình” đối với người sử dụng. Hai thuật
HVTH: Phí Thị Lệ Tho trang 3
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
ngữ quan trọng trong định nghĩa này là “liên đới logic’ và “phân bố trên một mạng
máy tính”.
Một hệ cơ sở dữ liệu phân tán (distributed database system, viết tắt là DDBS)
không phải là một “tập các tập tin” lưu riêng lẻ tại mỗi nút của một mạng máy tính.
Để tạo ra một hệ cơ sở dữ liệu phân tán, các tập tin không những có liên đới logic
mà chúng còn phải có cấu trúc và được truy xuất qua một giao diện chung.
Ngoài ra, một hệ cơ sở dữ liệu phân tán không phải là hệ thống trong đó dù
có sự hiện diện của một mạng máy tính, cơ sở dữ liệu chỉ nằm tại một nút của
mạng. Cơ sở dữ liệu này được quản lý tập trung tại một hệ thống máy tính và tất cả
mọi yêu cầu đều chuyển đến vị trí đó. Điều cần xem xét là độ chậm trễ khi truyền
dữ liệu. Tất nhiên sự tồn tại của một mạng máy tính hoặc một tập các tập tin không
đủ để tạo ra một hệ cơ sở dữ liệu phân tán. Điều chúng ta quan tâm là một môi
trường trong đó dữ liệu được phân tán trên một số vị trí.
HVTH: Phí Thị Lệ Tho trang 4
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
Trong hệ thống cơ sở dữ liệu phân tán, cơ sở dữ liệu chứa trong vài máy tính.
Các máy tính liên lạc với nhau qua nhiều phương tiện truyền thông, như bus tốc độ
cao hay đường điện thoại. Chúng không chia sẻ bộ nhớ chính, cũng không dùng
chung đồng hồ.
Các bộ xử lý trong hệ thống phân tán có kích cỡ và chức năng khác nhau.
Chúng có thể gồm các bộ vi xử lý, trạm làm việc, máy tính mini, hay các máy tính

ứng tổng quát của chúng sẽ là hiệu ứng của dãy (A;B) hoặc
là (B;A)
Ở mức hệ thống, ta có thể nói rằng các tác động là phần tử nhỏ nhất không
thể chia cắt được nữa.
Cho một tập hợp giao dịch M={T
1
, T
2
…, T
n
} lần lượt được thực hiện bởi các
tiến trình độc lập p
1
, p
2
,…,p
n
. Việc thực hiện tuần tự có nghĩa là thực hiện tất cả các
giao dịch của M theo kiểu nối đuôi nhau và tuân thủ một trật tự nào đó. Sự gắn bó
của hệ được bảo toàn, theo định nghĩa, bằng việc thực hiện riêng biệt từng giao
dịch. Do vậy, nó cũng được bảo toàn trong chế độ thực hiện tuần tự của M.
HVTH: Phí Thị Lệ Tho trang 6
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
Nếu, vì lý do hiệu quả, nhiều giao dịch được thực hiện song song, thì sự gắn
bó không còn đảm bảo được nữa.
Một yêu cầu khác nữa rất quan trọng là trong quá trình thực hiện hệ phải
đảm bảo cho các tác động không bị ngắt quãng.
2.2 Trật tự hóa các tác động
Trở lại với tập hợp giao dịch M = {T
1

= (a
21
, a
22
, a
23
). Một trật tự hóa (T
1
, T
2
) được
thể hiện như sau:
S = a
21
, a
11
, a
12
, a
22
, a
13
, a
23
, a
14
Trong số các trật tự hóa của một tập hợp các giao dịch, điều rất quan trọng là
phải tách ra cho được những cái phục vụ trạng thái gắn bó dữ liệu và chúng được
gọi là trật tự hóa gắn bó.
Như vậy, đặc tính quan trọng của trật tự hóa là: các trật tự hóa tương ứng

 Giao dịch hai pha: 1. Toàn bộ đối tượng bị cài then vẫn ở trong tình trạng
cài then cho đến cuối giao dịch và 2. Không có then cài nào có thể diễn ra tiếp
theo một then cài khác trong cùng một giao dịch.
Bây giờ ta tưởng tượng rằng các đối tượng được phân tán trên nhiều trạm
khác nhau và được nối với nhau thông qua hệ thống viễn thông và rằng các tiến
trình diễn ra trên các trạm khác nhau. Hệ thống viễn thông cho phép các tiến trình
trên các trạm khác nhau có thể trao đổi các thông điệp với nhau. Ta giả định rằng
các tiến trình và các phương tiện truyền thông là các đối tượng có thể rơi vào sự cố.
Một hệ quản lý tập hợp thông tin phân tán bao gồm:
STT Cơ chế
1
Cơ chế cho phép sắp xếp một cách tổng quát các tác động của
cùng một giao dịch, ngay cả khi các tác động này diễn ra trên các
trạm khác nhau.
2
Cơ chế điều khiển các tranh chấp truy cập cục bộ vào các đối
tượng đảm bảo tôn trọng tính toàn vẹn của các đối tượng truy cập
cục bộ này.
3
Cơ chế có khả năng xử lý các bế tắc và thiếu thốn vô hạn, hậu quả
của việc hủy bỏ các giao dịch.
4 Cơ chế phục hồi các giao dịch đã hủy bỏ hay xử lý các sự cố.
Cơ chế xử lý sự cố
STT Phải thực hiện
HVTH: Phí Thị Lệ Tho trang 8
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
1 Giao dịch T bắt buộc phải thực hiện một cách trọn vẹn
2 Nếu có sự cố xảy ra thì phải quay lại điểm xuất phát.
Muốn thực hiện những điều vừa nêu ở trên, người ta đòi hỏi giao dịch phải
có các đặc tính toàn vẹn như sau:

S
i
, các tác động được thực hiện trên các trạm khác nhau có thể tiến hành theo kiểu
song song.
Các phương pháp để quản lý gắn bó các giao dịch như: Phương pháp dự
phòng để chống bế tắc, phương pháp dựa vào việc hạn chế các khả năng diễn ra
bằng cách phát hiện bế tắc có tính chất động, điều đó dẫn đến hủy bỏ các giao dịch.
HVTH: Phí Thị Lệ Tho trang 9
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
CHƯƠNG III
XÂY DỰNG THUẬT TOÁN ELLIS ĐẢM BẢO GẮN BÓ MẠNH
3.1. Thuật toán Ellis đảm bảo gắn bó mạnh
3.1.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ì:
- Thống nhất giữa hai trạm
- 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à thoả 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.
3.1.2. Triển khai hệ ổn định
Mỗi trạm có thể có các trạng thái sau:
- Nghỉ ngơi: Trạm không thực hiện cập nhật nào cả.
- 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.
- 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.

nhà phát triển Java trung bình với một mô hình phát triển hoàn toàn mới – công nghệ
lập trình phân tán. Trong phần này, tôi sẽ giới thiệu sâu về kĩ thuật này lập trình mạng
phân tán này.
3.2.1. Kiến trúc Java RMI
Mục tiêu thiết kế cho kiến trúc của RMI là để tạo một mô hình đối tượng phân tán
Java mà tích hợp một cách tự nhiên vào ngôn ngữ lập trình Java và mô hình đối tượng
cục bộ. Kiến trúc RMI đã thành công, trong việc xây dựng một hệ thống kế thừa khả
năng an toàn và tin cậy của kiến trúc Java sang môi trường lập trình phân tán.
HVTH: Phí Thị Lệ Tho trang 11
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
3.1.2. Giao tiếp: trái tim của RMI
Kiến trúc RMI dựa trên một lý thuyết quan trọng: định nghĩa và sự triển khai của
thuộc tính là các khái niệm tách biệt. RMI cho phép mã nguồn định nghĩa hành vi và
mã nguồn triển khai hành vi đó được duy trì tách biệt và chạy trên các JVM tách biệt
nhau.
Điều này phù hợp với nhu cầu của các hệ phân tán trong đó các client được liên
quan với nhau về mặt định nghĩa của một dịch vụ và các server được tập trung vào
cung cấp các dịch vụ đó.
Trong RMI, việc định nghĩa của một dịch vụ từ xa được mã hóa sử dụng một giao
tiếp Java. Việc triển khai cho một dịch vụ từ xa được mã hóa trong một lớp đối tượng.
Chính vì thế điểm quan trọng để hiểu RMI là nhớ về giao tiếp định nghĩa hành vi và
các lớp định nghĩa triển khai cho các hành vi đó.
Sơ đồ sau mô tả cho sự tách biệt này,
Chú ý rằng một giao tiếp Java không chứa mã thực thi. RMI hỗ trợ hai lớp triển
khai cho cùng một giao tiếp. Lớp thứ nhất là triển khai của hành vi, và chạy trên server.
Lớp thứ hai hoạt động như một ủy quyền cho dịch vụ từ xa và chạy trên client. Điều
này được thể hiện trong sơ đồ sau đây:
Một chương trình client tạo các lời gọi phương thức trên đối tượng proxy, RMI
gửi yêu cầu đến cho JVM ở xa, và chuyển nó đến để triển khai. Bất kì giá trị trả về
HVTH: Phí Thị Lệ Tho trang 12

đối tượng được xuất ra, RMI tạo một dịch vụ lắng nghe chờ đợi client kết nối đến và
yêu cầu dịch vụ này. Sau khi xuất xong, server đăng kí đối tượng đó dưới một tên
chung.
Ở phía client, bộ đăng kí RMI được truy cập thông qua phương thức tĩnh Naming.
Nó cung cấp phương thức lookup() mà client sử dụng để truy vấn một đăng kí. Phương
thức lookup() chấp nhận một URL xác định tên server và tên dịch vụ được yêu cầu.
Phương thức đó trả về một tham chiếu từ xa cho đối tượng dịch vụ. URL này có dạng
rmi://<host_name>
[:<name_service_port>]
/<service_name>
Trong đó host_name là tên được ghi nhận trên một mạng nội bộ (LAN) hay là
một tên DNS trên Internet. name_service_port chỉ cần được xác định chỉ nếu dịch vụ
tên được chạy trên một port khác với port 1099.
HVTH: Phí Thị Lệ Tho trang 14
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
CHƯƠNG IV
DEMO CHƯƠNG TRÌNH ỨNG DỤNG JAVA
4.1. Đặt vấn đề
Trong một hệ phân tán có độ ổn định tốt, ta muốn duy trì sự gắn bó mạnh
giữa các bản sao của một đối tượng đặt trên các server khác nhau.
Thuật toán như sau : Trước khi thực hiện cập nhật, một server nào đó cần
phải yêu cầu và thống nhất với các server khác. Khi đó, server này tiến hành cập
nhật; điều này phải tiến hành trên tất cả các bản sao; đối tượng không thể truy cập
chừng nào các bản sao còn chưa cập nhật hết.
Vậy với điều kiện hệ phân tán không ổn định (luôn có sự cố kỹ thuật) các
Server sẽ cập nhật như thế nào?
4.2 Chương trình Java
4.2.1. Giả lập 03 Server và 01 Client
Phần này tôi chọn lập trình Client/Server bằng RMI của Java để mô phỏng quá
trình cập nhật dữ liệu khi rút tiền từ ATM:

* Mã nguồn tập tin Client.java
import java.io.*;
import java.rmi.*;
public class Client{
static Server1 obj1 = null;
String mkh;
String solg;
HVTH: Phí Thị Lệ Tho trang 17
SERVER 1
SERVER 2 SERVER 3
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
static Server2 obj2 = null;
static Server3 obj3 = null;
public static void main (String argv[]) throws Exception{
try{
Client sv = new Client();
DataInputStream stream = new DataInputStream(System.in);
System.out.println(" RUT TIEN THE ATM ");
try{
System.out.print("NHAP VAO MA KHACH HANG = ");
sv.mkh = stream.readLine();
System.out.print("NHAP SO TIEN CAN RUT = ");
sv.solg = stream.readLine();
}catch(IOException e){
System.out.println("loi nhap du lieu");
}
obj1 = (Server1)Naming.lookup("rmi://localhost:2001/Server1");
obj2 = (Server2)Naming.lookup("rmi://localhost:2002/Server2");
obj3 = (Server3)Naming.lookup("rmi://localhost:2003/Server3");
obj1.capnhat(sv.mkh,sv.solg);

catch(java.lang.Exception exception) {
java.lang.System.out.println("Create registry failed " +
exception.getMessage());
java.lang.System.exit(0); }}}
* Server1Impl.java
import java.io.*;
import java.rmi.*;
import java.sql.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.lang.Math;
HVTH: Phí Thị Lệ Tho trang 19
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
import java.util.*;
import java.util.StringTokenizer;
public class Server1Impl extends java.rmi.server.UnicastRemoteObject
implements Server1 {
int so,so1;
public Server1Impl()
throws java.rmi.RemoteException {
java.lang.System.out.println("Starting Server1 "); }
public void listkhachhang()throws java.rmi.RemoteException,SQLException
{ String smakh,stenkh,ssotien;
try{
Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");
}catch (ClassNotFoundException e) {
System.out.println("Khong nap duoc lop Driver");
return;
}

where MaKH='"+mkh+"'");
rs.next();
so = Integer.parseInt(rs.getString("SoTien"));
so1 = Integer.parseInt(solg);
stmt.addBatch("Update khachhang Set SoTien='"+String.valueOf(so-
so1)+"' where MaKH='"+mkh+"'");
int[] upcounts = stmt.executeBatch();
con.commit();
stmt.close();
con.close();
}catch(SQLException se){
System.out.println("Loi o SQL : " + se.getMessage());
se.printStackTrace(System.out);}}}
HVTH: Phí Thị Lệ Tho trang 21
Tiểu luận lập trình mạng GVHD: PGS.TS Lê Văn Sơn
KẾT LUẬN
Một trong các tiêu chí đặt ra trong việc phát triển các chương trình ứng dụng
hiện nay, là phải hoạt động hiệu quả trên môi trường mạng, đáp ứng được các yêu
cầu của đối tượng sử dụng. Đòi hỏi các nhà thiết kế hệ thống, người lập trình phải
có tư duy và khả năng và nắm bắt kịp thời các công nghệ ứng dụng trong lập trình
mạng .
Qua quá trình nghiên cứu bài giảng của thầy giáo PGS.TS Lê Văn Sơn và
các tài liệu liên quan để áp dụng thực hiện tiểu luận này, tôi đã hiểu được rõ thêm
bản chất của hệ tin học phân tán, nhất là quá trình gắn bó dữ liệu bằng phương pháp
trật tự hóa trên hệ thống đa Server thông qua việc gửi và nhận thông điệp giữa
Client/Server, giữa các Server.
Nội dung tiểu luận đã khái quát sơ lược lý thuyết về hệ Cơ sở dữ liệu phân
tán, sự gắn bó dữ liệu bằng phương pháp trật tự hóa, các kỹ thuật lập trình phân tán
trong ngôn ngữ lập trình Java. Xây dựng giao diện trao đổi thông điệp giữa Client
và hai server, từ đó xây dựng các Client/Server có monitoring theo dõi quá trình gửi

3.1. Thuật toán Ellis đảm bảo gắn bó mạnh 10
3.2. Giới thiệu hệ thống phân tán sử dụng công nghệ RMI 11
3.2.1. Kiến trúc Java RMI 11
3.1.2. Giao tiếp: trái tim của RMI 12
3.2.1. Lớp truyền vận 13
4.2.1. Giả lập 03 Server và 01 Client 15
KẾT LUẬN 22
MỤC LỤC
HVTH: Phí Thị Lệ Tho