ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Lớp Cao Học khóa 5 ngành Khoa Học Máy Tính
08.2012BÀI THU HOẠCH MÔN HỌC
Cơ sở dữ liệu nâng cao
Đề tài
MỘT MÔ HÌNH CẤP PHÁT TRONG
THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN
Giảng viên hướng dẫn: PGS-TS Đỗ Phúc
Người thực hiện: Trần Kim Hoàng Quốc (CH1001062)
1
Mục lục
1. Giới thiệu 3
2. Mô hình cấp phát 4
2.1 Vấn đề cấp phát 4
2.2 Yêu cầu thông tin 5
2.2.1 Thông tin cơ sở dữ liệu 5
2.2.2 Thông tin giao tác 5
2.2.3 Thông tin site 7
2.2.4 Thông tin mạng 7
2.3 Các công thức chi phí 8
3. Các giải thuật heuristic 9
3.1 Thuật toán 1 9
3.2 Thuật toán 2 12
4. Một số kết quả thử nghiệm 14
4.1 Các số liệu kết quả 14
4.2 Các kết quả thí nghiệm 17
5. Cài đặt 18

Mô hình cấp phát cần phải xem xét tần suất của các yêu cầu tại các site. Bởi vì các hành
vi giao tác ảnh hưởng đến các phương án cấp phát, các công thức chi phí phải được tính
toán dựa theo thông tin giao tác để giảm thiểu chi phí giao tác.
Mặc dù đã có nhiều nhà nghiên cứu đề nghị các mô hình và thuật toán cấp phát, hầu hết
các mô hình này đều rất phức tạp và khó hiểu nên khó áp dụng được trong thực tế. Mô
hình đề xuất trong bài này là một mô hình đơn giản, phản ánh hành vi giao tác trong hệ
cơ sở dữ liệu phân tán. Mô hình này cũng đã được thử và so sánh với các mô hình khác,
đã cho thấy phương án cấp phát tìm ra nhờ thuật toán này là gần tối ưu, tốt hơn so với
một số mô hình khác.
Phần 2 sẽ phân tích cách hành xử giao tác và đề nghị một mô hình cấp phát. Phần 3 sẽ
trình bày hai thuật toán heuristic để tìm phương án cấp phát gần tối ưu. Để kiểm tra các
công thức chi phí có phù hợp với chi phí thông tin trong thế giới thực, một số thử nghiệm
sẽ được trình bày trong phần 4. Phần cuối trình bày chương trình cài đặt cho thuật toán 1.
2. Mô hình cấp phát
2.1 Vấn đề cấp phát
Trước khi xem xét vấn đề cấp phát ta cần xác định vấn đề một cách rõ ràng. Ở đây ta chỉ
giải quyết trong môi trường WAN vì ảnh hưởng của việc lưu trữ các phân mảnh trong các
site của mạng LAN thì không đáng kể.
Giả sử có mạng WAN với m site:
S = {S
1
, S
2
, S
m
}
trong đó có một tập T các giao tác được thực hiện
T = {T
1
, T

2. Hiệu năng: Hai chiến lược nổi tiếng là giảm thiểu thời gian đáp ứng và tăng tối đa
thông lượng hệ thống tại từng site.
Trong mô hình này, chi phí tối thiểu sẽ được dùng làm số đo độ tối ưu. Hơn nữa, trong
môi trường WAN, với băng thông giới hạn ở 50Kbps thì các chi phí truy xuất I/O hay
thời gian xử lý của CPU không phải là yếu tố lớn cần xem xét để giảm chi phí tổng thể.
Do đó, vấn đề cấp phát chỉ đơn giản là phân bổ các bản sao của phân mảnh vào các site
sao cho tổng chi phí thông tin là thấp nhất.
2.2 Yêu cầu thông tin
Trước khi dẫn ra các công thức chi phí, một số thông tin cần được phân tích trước, đó là:
1. Dữ liệu về lượng của cơ sở dữ liệu.
2. Hành vi giao tác.
3. Thông tin site.
4. Thông tin mạng.
2.2.1 Thông tin cơ sở dữ liệu
Kích cỡ của từng mảnh, ký hiệu là size(F
j
), phải được định nghĩa vì nó đóng vai trò chủ
đạo khi tính chi phí thông tin.
2.2.2 Thông tin giao tác
Trong mô hình ta có hai ma trận truy cập RM và UM mô tả các hành vi đọc (retrieve) và
cập nhật (update) dữ liệu của tất cả các giao tác. Các phần tử r
ij
(hay u
ij
) trong RM (hay
1
UM) là tần số truy cập mảnh F
j
trong giao tác T
i

2
, 0.5% của F
4
.
Ngoài ra ta còn cần một ma trận tần suất FREQ để thể hiện tần suất thực thi của tất cả
giao tác trên các site.
1
Giao tác T
3
trong ma trận FREQ trên chạy 2 lần ở site S
1
và 1 lần ở site S
3
.
2.2.3 Thông tin site
Thông tin site trong mạng có thể là thông tin về dung lượng lưu trữ và tốc độ xử lý.
Thông tin này nói chung sẽ được xem như là những ràng buộc trong mô hình cấp phát.
Để đơn giản ta sẽ không xét đến thông tin này.
2.2.4 Thông tin mạng
Trong môi trường mạng WAN, chi phí thông tin để truyền gói dữ liệu kích thước m_size
từ site S
i
sang site S
j
được mô tả bằng một hàm tuyến tính như sau:
trong đó
- C
ini
: hằng số chi phí khởi tạo một gói dữ liệu kích thước p_size.
- CTR

proc
) (2)
Công thức chi phí thông tin bao gồm hai thành phần:
- CC
load
: chi phí dùng cho nạp dữ liệu.
- CC
proc
: chi phí dùng cho xử lý giao tác.
CC
load
là chi phí để nạp tất cả các bản sao của các mảnh vào các site trong mạng trước khi
giao tác được xử lý. Nó có thể được diễn đạt bằng công thức sau:
trong đó
- FAT là ma trận của bảng cấp phát mảnh. FAT
j,k
= 1 nếu mảnh Fj được cấp cho
site S
k
, ngược lại thì bằng 0.
- SI là site chủ có nhiệm vụ nạp tất cả các bản sao của các mảnh vào các site trong
mạng.
1
Kế đến, chi phí CC
proc
bao gồm 3 thành phần: giao tác đọc TR
i
, giao tác cập nhật TU
i
, và

.
3. Các giải thuật heuristic
Trong phần trước, ta đã xây dựng mô hình cấp phát tổng quát. Tìm kiếm một phương án
cấp phát tối ưu trong mô hình này là một bài toán NP-complete. Với n mảnh và m site, ta
sẽ có (2
m
-1)
n
cách cấp phát khác nhau. Do đó ta chỉ có thể tìm các giải thuật heuristic để
giải bài toán này. Phần này sẽ đề xuất 2 thuật toán heuristic để giảm chi phi thông tin đến
mức tối thiểu có thể được.
3.1 Thuật toán 1
Thuật toán thứ nhất có 3 bước. Bước đầu tiên sẽ khởi tạo bảng cấp phát mảnh bằng cách
chỉ quan tâm đến các giao tác đọc. Một yêu cầu đọc có thể được xử lý mà không tốn chi
phí thông tin nếu các mảnh đích của giao tác đọc được cấp phát vào đúng site mà giao tác
1
được khởi tạo. Từ ma trận RM và FREQ mô tả trong phần 2.2, ta có thể khởi tạo bảng
cấp phát mảnh FAT.
Với mảnh F
3
trong RM, chỉ các giao tác T
3
và T
4
có thể đọc nó. Vì các giao tác T
3
và T
4
chỉ được thực hiện ở site S
1

Trong bước cuối cùng, nếu một mảnh nào đó chưa được cấp phát vào site nào, và nó có
bị cập nhật bởi một số giao tác, ta sẽ tìm các site ứng cử viên để cấp phát mảnh này bằng
cách dựa vào ma trận UM và FREQ. Trong số các site ứng cử viên, chúng ta chỉ chọn
một site có chi phí thông tin thấp nhất để cấp phát. Ví dụ: mảnh F
5
trong RM không được
1
đọc bởi giao tác nào, tuy nhiên giao tác T
1
và T
4
có cập nhật nó (xem ma trận UM). Do
giao tác T
1
và T
4
chỉ thực hiện trên site S
2
, S
3
và S
4
, mảnh F
5
sẽ được cấp phát vào một
trong 3 site đó dựa theo chi phí thông tin.
Độ phức tạp thời gian của thuật toán 1 là O(nm
2
q) trong đó n (hay |F|) là số phân mảnh
khác nhau, m (hay |S|) là số site và q (hay |T|) là số giao tác. Chi tiết giải thuật như sau:

T1 =

Gọi n1 là site có độ trễ mạng thấp nhất tiếp theo từ S
k
khi S
k
thực hiện đọc frag;
T2 =

Cost = Cost + (T2 - T1);
end
1
end
return Cost;
End
Function:
MinDelay(frag) ; /* site có độ trễ thấp nhất để cấp phát mảnh frag */
Function:
NumFragCopy(frag); /* số bản sao của mảnh trong hệ thống */
Begin
Step 1 /* Khởi tạo giải pháp tốt nhất cho giao tác đọc */
For T
i
in T, F
j
in F, S
k
in S do
if (RM(T
i

,S
k
)) là lớn nhất;
if ((Benefit(F
j
,S
k
) - Cost(F
j
,S
k
)) > 0)
FAT(Fj,Sk) = 0
else
break;
end
Step 3 /* Nếu một mảnh chưa được cấp phát nhưng nó có bị cập nhật bởi một số giao tác, chọn site có độ
trễ thấp nhất để cấp phát mảnh. */
For F
j
in F do
if (NumFragCopy(F
j
) = 0 and UM(T
i
,F
j
) > 0)
begin
S

RM(trans,frag); /* ma trận Đọc */
UM(trans,frag); /* ma trận Cập nhật */
SEL(trans,frag); /* ma trận Chọn */
FREQ(trans,site); /* ma trận Tần suất */
CTR(site,site); /* ma trận Chi phí thông tin */
Output:
FAT(frag,site); /* bảng cấp phát mảnh */
Variable:
WT(frag, site); /* bảng trọng số */
Function:
Benefit(frag,site); /* chi phí tiết kiệm khi loại bỏ mảnh khỏi site */
/* giống thuật toán 1 */
Function:
Cost(frag,site); /* chi phí tăng thêm khi loại bỏ mảnh khỏi site */
/* giống thuật toán 1 */
Function:
MinDelay(frag) ; /* site có độ trễ thấp nhất khi mảnh frag được cấp phát */
Function:
NumFragCopy(frag); /* số bản sao của mảnh trong hệ thống */
Begin
Step 1 /* giống bước 1 thuật toán 1 */
Khởi tạo giải pháp tốt nhất cho giao tác đọc
Step 2 /* Tính giá trị trọng số */
For F
j
in F do
For S
k
in S do
WT(F

j
,S
k
) = 0;
end
Step 4 /* bước 3 trong thuật toán 1 */
Nếu một mảnh chưa được cấp phát nhưng nó có bị cập nhật bởi một số giao tác, chọn site có độ trễ thấp
nhất để cấp phát mảnh.
End
4. Một số kết quả thử nghiệm
Đầu tiên chúng ta tính các chi phí thông tin của phương án cấp phát tối ưu và 2 phương
án heuristic, sử dụng các công thức trong phần 2.3. Sau đó, chúng ta thẩm định khả năng
phản ánh chi phí thông tin trong thế giới thực của các công thức chi phí, bằng cách thực
hiện một số thí nghiệm.
4.1 Các số liệu kết quả
Trong phần 2 ta đã xác định ba thông số hằng, đó là:
- hằng số chi phí khởi tạo gói dữ liệu C
ini
- kích thước của gói dữ liệu p_size
- chi phí tạo mạch ảo VC
ini
Để phù hợp với môi trường thử nghiệm thực trong phần sau, các giá trị của các hằng số
này được cho như sau:
- C
ini
= 0.032 ms/byte
- p_size = 6250 bytes
- VC
ini
= 65.5676 ms

Do thiếu môi trường WAN nên thí nghiệm sau dùng mạng LAN để mô phỏng. Mạng
LAN gồm có 24 node máy SPARC 10s. Để giảm thời gian, thí nghiệm chỉ chọn một
trường hợp (trong 10 trường hợp trình bày ở phần trên) cho mỗi môi trường để chạy thử.
Thí nghiệm 1 khảo sát trường hợp 4 trong bảng 1, và thí nghiệm 2 khảo sát trường hợp 8
trong bảng 2.
So sánh kết quả tìm được từ các công thức chi phí và kết quả thu được từ thí nghiệm
(xem bảng 3 và 4), có thể thấy chi phí tính được dùng công thức khá gần so với chi phí
thực tế thí nghiệm.
Bảng 3: Thí nghiệm và công thức chi phí, trường hợp 4 bảng 1
1
Bảng 4: Thí nghiệm và công thức chi phí, trường hợp 4 bảng 1
5. Cài đặt
Thuật toán 1 đã được cài đặt thử bằng C# trong bài thu hoạch này. Chương trình đã hiện
thực một số giải thuật nhỏ chưa được đề cập chi tiết trong thuật toán 1, đó là:
- Độ trễ mạng thấp nhất
- MinDelay
Bản chất của hàm tính độ trễ mạng thấp nhất là tìm kiếm site S
B
trong số các site đã được
cấp phát mảnh F
i
, và chi phí truyền CTR từ site S
A
đến site S
B
là thấp nhất. Hàm nhận hai
thông số là site S
A
và mảnh F
i

#number of sites
site=4
#retrieval matrix RM(trans,frag)
RM=
2,3,0,0,0
2,0,0,1,0
0,0,3,0,0
3,0,2,0,0
#update matrix UM(trans,frag)
UM=
0,0,0,1,2
0,3,0,0,0
2,1,0,1,0
0,0,0,0,3
#selectivity matrix SEL(trans,frag)
SEL=
0.1,0.1,0,0.3,0.2
0.1,0.3,0,1,0
2,5,0.1,0.5,0
0.5,0,10,0,4
#frequency matrix FREQ(trans,site)
FREQ=
0,2,3,1
0,3,0,0
2,0,1,0
0,0,4,0
#cost of transmitting unit data from site to site CTR(site,site)
CTR=
0,0.32,0.48,0.16
0.32,0,0.64,0.32

T3 0 0 4 0
Transmission Cost CTR(site,site):
S0 S1 S2 S3
S0 0 0.32 0.48 0.16
S1 0.32 0 0.64 0.32
S2 0.48 0.64 0 0.64
S3 0.16 0.32 0.64 0
Allocating fragments to sites
FAT table after step 1
FAT S0 S1 S2 S3
F0 0 1 1 1
F1 0 1 1 1
F2 1 0 1 0
F3 0 1 0 0
F4 0 0 0 0
FAT table after step 2
FAT S0 S1 S2 S3
F0 0 0 1 0
F1 0 0 0 1
F2 1 0 1 0
F3 0 1 0 0
F4 0 0 0 0
FAT table after step 3
FAT S0 S1 S2 S3
F0 0 0 1 0
F1 0 0 0 1
F2 1 0 1 0
F3 0 1 0 0
F4 0 0 1 0
1