Luận Văn Hệ cơ sở dữ liệu phân tán và ứng dụng trong máy tìm kiếm

Khóa luận tốt nghiệp
Đề tài: CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ ỨNG DỤNGTRONG MÁY TÌM KIẾM
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Định dạng file word và PDF




Mục lục:
Tóm tắt . - 2 -
Danh sách các hình - 6 -
Chương 1: Giới thiệu hệ cơ sở dữ liệu phân tán - 7 -
Nhu cầu về hệ phân tán . - 7 -
Định nghĩa hệ CSDL phân tán - 7 -
Ưu điểm của hệ CSDL phân tán . - 8 -
Nhược điểm của hệ CSDL phân tán . - 9 -
Chương 2: Dữ liệu máy tìm kiếm và cơ sở dữ liệu Bigtable . - 10 -
2.1. Giới thiệu về Bigtable và dữ liệu máy tìm kiếm . - 10 -
Mô hình dữ liệu . - 11 -
2.2.1. Hàng . - 11 -
2.2.2. Họ cột . - 12 -
2.2.3. Nhãn thời gian - 13 -
Giao diện lập trình ứng dụng API . - 13 -
Xây dựng các khối - 15 -
Thực thi . - 15 -
2.5.1. Định vị bảng phụ - 16 -
2.5.2. Chỉ định bảng phụ - 18 -
2.5.3. Phục vụ bảng phụ . - 19 -
2.5.4. Nén . - 20 -
Lọc - 21 -
Ước lượng hiệu năng - 25 -
Chương 3: Hệ thống quản lý file phân tán Hadoop . - 28 -
3.1. Khái niệm cơ bản về hệ thống Hadoop - 28 -
3.1.1. Kiến trúc của Hadoop - 28 -
3.1.2. Job Tracker và Task Tracker: các máy MapReduce - 30 -
3.2. Cơ chế MapReduce . - 32 -
3.2.1. Giới thiệu . - 32 -
3.2.2. Các thành phần logic - 33 -
3.2.2.1. Map . - 33 -
3.2.2.2. Reduce . - 33 -
3.2.3. Mô hình luồng dữ liệu - 35 -
3.2.4. Đánh giá . - 37 -
3.3. Ứng dụng của Hadoop - 38 -
3.3.1. Hadoop trong máy tìm kiếm Yahoo - 38 -
3.3.2. Hadoop trên các dịch vụ Amazon EC2/S3 - 38 -
3.3.3. Hadoop với Sun Grid Engine . - 39 -
Chương 4: Kiến trúc HBase . - 40 -
4.1. Giới thiệu HBase . - 40 -
Mô hình dữ liệu . - 40 -
4.2.1. Khung nhìn khái niệm - 40 -
4.2.2. Khung nhìn lưu trữ vật lý . - 41 -
4.3. Kiến trúc và thực thi . - 43 -
4.3.1. HBaseMaster - 43 -
4.3.2. HRegionServer . - 44 -
4.3.3. HBase Client - 46 -
Chương 5: Cài đặt thực nghiệm và đánh giá hiệu năng . - 47 -
5.1. Môi trường thử nghiệm . - 47 -
5.2. Cài đặt cụm Hadoop phân tán quy mô 3 máy . - 47 -
Chạy thử và đánh giá hiệu năng - 52 -
Kết luận - 55 -
Tài liệu tham khảo . - 56 -



Tóm tắt

Đi đôi với sự phát triển ngày càng nhanh của khoa học, kỹ thuật đó là sự phát triển
của công nghệ cơ sở dữ liệu. Các hệ cơ sở dữ liệu truyển thống, quản lý dữ liệu theo
phương thức tập trung đôi khi đã không còn phù hợp với các hệ thống hiện đại. Hệ phân
tán, tối ưu hơn đã ngày càng được sử dụng rộng rãi và phổ biến.

Khóa luận tốt nghiệp với đề tài “Hệ cơ sở dữ liệu phân tán và ứng dụng trong máy
tìm kiếm” tập trung tìm hiểu về kiến trúc, cách thức hoạt động của hệ thống lưu trữ lớn
Bigtable, hệ thống quản lý dữ liệu phân tán Hadoop. Khóa luận cũng tiến hành cài đặt thử
nghiệm hệ thống Hadoop lưu trữ phân tán với cụm máy tính để bàn kết nối trên mạng
LAN ứng dụng cho máy tìm kiếm mã nguồn mở Nutch.

Chương 1: Giới thiệu hệ cơ sở dữ liệu phân tán

1.1. Nhu cầu về hệ phân tán

Công nghệ cơ sở dữ liệu (CSDL) đã trải qua một quá trình hình thành và phát triển
khá lâu dài. Ban đầu, các hệ CSDL thường gắn liền với ứng dụng, nghĩa là mỗi ứng dụng
định nghĩa và duy trì dữ liệu của riêng chúng. Phát triển hơn, dữ liệu được quản lý một
cách tập trung, nhiều ứng dụng khác nhau có thể truy vấn vào CSDL tập trung đó. Việc
xây dựng những hệ CSDL tập trung này có nhiều lợi ích, một lợi ích điển hình đó là tính
độc lập dữ liệu. Độc lập dữ liệu được hiểu là nếu chúng ta có thay đổi về tổ chức logic
hay tổ chức vật lý của dữ liệu thì cũng không ảnh hưởng gì đến các ứng dụng sử dụng dữ
liệu đó và ngược lại. Tuy nhiên, CSDL tập trung cũng tồn tại nhiều khuyết điểm, có thể
kể đến đó là khi trung tâm dữ liệu có sự cố thì toàn hệ thống sẽ ngừng hoạt động, hay tình
trạng tắc nghẽn khi có quá nhiểu yêu cầu truy xuất vào CSDL.

Hệ CSDL phân tán ra đời đã phần nào khắc phục được những điểm yếu của CSDL
tập trung. Là kết quả của sự hợp nhất của hai hướng tiếp cận đối với quá trình xử lý dữ
liệu: công nghệ CSDL và công nghệ mạng máy tính. CSDL phân tán gồm nhiều CSDL
tích hợp lại với nhau thông qua mạng máy tính để trao đổi dữ liệu, thông tin. CSDL được
tổ chức và lưu trữ ở những vị trí khác nhau trong mạng máy tính và chương trình ứng
dụng làm việc trên cơ sở truy cập dữ liệu ở những điểm khác nhau đó.

Có thể thấy nguyên lý phân tán cũng tương tự như nguyên lý “chia để trị” đã phổ
biến rất rộng rãi. Một bài toán lớn và phức tạp được chia thành nhiều bài toán nhỏ và đơn
giản hơn, giao cho nhiều đơn vị thực hiện sau đó tổng hợp kết quả lại. Xét trên khía cạnh
người dùng, đặc biệt là các công ty, xí nghiệp, thì việc xử lý phân tán đáp ứng tốt hơn với
việc phân bố ngày càng rộng rãi của các tổ chức này.
1.2. Định nghĩa hệ CSDL phân tán.
M. Tamer Ozsu và Patrick Valduriez[1] định nghĩa một CSDL phân tán là “một tập
hợp nhiều CSDL có liên đới logic và được phân bố trên một mạng máy tính”. Từ đó hai
tác giả đã định nghĩa hệ quản trị CSDL phân tán là một hệ thống phần mềm cho phép
quản lý các hệ CSDL phân tán và làm cho các hệ phân tán trở nên “vô hình” đối với
người sử dụng.
Hai điểm quan trọng được nêu ra trong định nghĩa là:
Phân bố trên một mạng máy tính: Dữ liệu không cư trú trên một vị trí. Điều này
giúp phân biệt một CSDL phân tán với một CSDL tập trung, đơn lẻ.

Liên đới logic: Dữ liệu có một số các thuộc tính ràng buộc chúng với nhau, điều
này giúp chúng ta phân biệt một CSDL phân tán với một tập hợp CSDL cục bộ
hoặc các tệp cư trú tại các vị trí khác nhau trong một mạng máy tính.

Ưu điểm của hệ CSDL phân tán

Về tổ chức và tính kinh tế: Ngày càng xuất hiện nhiều tổ chức với quy mô lớn, các
chi nhánh của những tổ chức này phân bố ở nhiều nơi có vị trí địa lý rất xa nhau.
Việc sử dụng một hệ tập trung với những tổ chức như này là không hợp lý, phân
tán là giải pháp phù hợp. Cùng với sự phát triển của kinh tế thương mại hiện nay,
các trung tâm máy tính tập trung cũng không còn phù hợp, việc phân tán trở thành
nhu cầu cần thiết.

Tận dụng, liên kết những CSDL sẵn có: có thể tạo nên một CSDL phân tán từ
những CSDL cục bộ đã có sẵn. Tiến trình này có thể yêu cầu phải sửa đổi các
CSDL cục bộ.

Thuận lợi cho việc mở rộng: Các tổ chức có thể mở rộng, thêm vào các đơn vị mới
một cách dễ dàng, đơn vị mới vừa có tính tự trị vừa có kết nối với tổ chức. Với
CSDL tập trung, cũng có thể ước lượng khởi tạo một kích thước lớn để mở rộng
về sau, tuy nhiên việc này là rất khó khăn, nếu khởi tạo quá lớn mà không dùng
hết thì lãng phí tài nguyên, khởi tạo kích thước nhỏ thì có thể không đủ dùng.

Giảm chi phí truyền thông: Trong hệ phân tán, một chương trình ứng dụng tại địa
phương có thể giảm bớt được chi phí truyền thông nếu sử dụng bản sao dữ liệu có
tại địa phương.

Cải thiện hiệu suất: Hệ CSDL phân tán có thể tăng số lượng công việc thực hiện
qua áp dụng nguyên lý xử lý song song với hệ thống xử lý đa nhiệm. Hệ CSDL
phân tán cũng có lợi trong việc phân tán dữ liệu, tạo ra các chương trình ứng dụng
chạy tại nhiều máy trong mạng. Các nơi xử lý có thể hỗ trợ lẫn nhau, xung đột
giữa các bộ vi xử lý là tối thiểu. Tải được chia sẻ giữa các bộ vi xử lý, do đó giảm
được hiện tượng tắc nghẽn do thắt cổ chai trong mạng.
Tính tin cậy và sẵn sàng: Độ tin cậy và tính sẵn sàng là một trong những mục đích
của hệ CSDL phân tán. Tuy nhiên để đạt được điều này không dễ dàng. Khả năng
tự trị tại các vị trí khác nhau khiến cho tính tính tin cậy cao của toàn bộ hệ thống
khó được đảm bảo. Sự cố trong hệ phân tán có thể thường xuyên xảy ra hơn trong
hệ tập trung, do cấu trúc thành phần phức tạp hơn, nhưng hậu quả của sự cố chỉ
giới hạn ở mức cục bộ, sự sụp đổ của toàn bộ hệ thống là rất hiếm khi xảy ra.

Nhược điểm của hệ CSDL phân tán

Tuy có những ưu điểm vượt trội so với CSDL tập trung, CSDL phân tán có những
điểm yếu cần cân nhắc khi sử dụng mà có thể tóm gọn lại trong 4 vấn đề sau:

Tính phức tạp: Hệ phân tán phức tạp hơn hệ tập trung, ngoài các vấn đề cần giải
quyết như tập trung, còn có các vấn đề khác như về mạng hay về đồng bộ hóa.

Chi phí: một hệ phân tán đòi hỏi phải có thêm các thiết bị phần cứng mới (thiết bị
truyền thông .), các phần mềm và phương pháp truyền thông phức tạp hơn, và
đặc biệt là chi phí về nhân lực. Vì thế cần phải phân tích cẩn thận giữa những lợi
ích mà nó mang lại với chi phí để thiết kế, sử dụng và bảo trì nó.

Phân tán quyền điều khiển: điều khiển phân tán là một trong những ưu điểm của
hệ CSDL phân tán. Tuy nhiên sự phân tán phải đi kèm với quá trình đồng bộ hóa.
Việc điều khiển phân tán có thể trở thành một gánh nặng nếu không có những
chiến lược phù hợp để giải quyết chúng.

Tính an ninh (bảo mật): Trong CSDL tập trung, người quản trị có thể kiểm soát
được các truy xuất dữ liệu. An ninh dễ dàng được kiểm soát ở trung tâm. Tuy
nhiên đối với hệ phân tán, các máy được kết nối qua mạng máy tính, việc đảm bảo
an ninh trong môi trường mạng là phức tạp hơn.



Tài liệu tham khảo
Tiếng Việt
[1]. M. Tamer Ozsu, Patrick Valduriez - Nguyên lý các hệ cơ sở dữ liệu phân
tán . Nhà xuất bản thống kê 1999, biên dịch : Trần Đức Quang
[2]. TS. Nguyễn Bá Tường. Lý thuyết cơ sở dữ liệu phân tán.
Tiếng Anh
[3]. Bentley, J., L., and Mcilroy, M., D. Data compression using long common
strings. In Data Compression Conference (1999), pp. 287-295.
[4]. Bloom, B., H. Space/time trade-offs in hash coding with allowable errors.
CACM 13, 7 (1970), 422-426.
[5]. Burrows, M., The Chubby lock service for lossely coupled distributed
systems. In Proc, of the 7th OSDI (Nov, 2006).
[6]. Chandar, T., Griesemer, R., and Redstone, J. Paxos made live – An
engineering perspective. In Proc. of PODC (2007).
[7]. Comer, D. Ubiquitous B-tree. Computing Surveys 11,2 (June, 1979) 121-
[8]. Dean, J., and Ghemawat, S., MapReduce: Simplified data processing on
large clusters. In Proc. Of the 6th OSDI (Dec. 2004), pp. 137-150.
[9]. Dewitt, D. J., and Gray, J. Parallel database systems: The future of high
performance database systems. CACM 35,6 (June 1992), 85-88.
[10]. Dewitt, D., Katz, R., Olken, F., Sharipo, L., Stonebraker, M., and Wood, D.
Implementation techniques for main memory database systems. In Proc, of
SIGMOD (June 1984), pp, 1-8.
[11]. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C.Hsieh, Deborah
A.Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber
Bigtable : A Distributed Storage System for Structured Data. OSDI‟06:
Seventh Symposium on Operating System Design and Implementation,Seattle,
WA, November, 2006.
[12]. Gawlick, D., and Kinkade, D. Varieties of concurrency control in IMS/VS
fast path. Database Engineering Bulletin 8, 2 (1985), 3-10.
[13]. Ghemawat, S., Gobioff, H., and Leung, S. – T. The Google filesystem. In
Proc, of the 19th ACM SOSP (Dec. 2003), pp. 29-43.
[14]. Mccarthy, J. Recursive funtions of symbolic expressions and their
computation by machine. CACM 3,4 (Apr. 1960) , 184-185.
[15]. Pike, R., Dorward, S., Griesemer, R., and Quinlan, S. Interpreting the data:
Parallel analysis with Sawzall. Scientific Programming Journal 13, 4 (2005), 227-
298.
[16]. Salmen, D., Malyuta, T., Fetters, R, and Antunes, R. Cloud data structure
Diagramming Techniques and Degisn Patterns.
[17]. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google File
System. 19th ACM Symposium on Operating Systems Principles, Lake George,
NY, October, 2003.
[18]. Zhao, Z., and Pjesivac-Grbovic, J. MapReduce- The programming Model
and Practice.
[19] Hadoop wike: http://en.wikipedia.org/wiki/Hadoop
[20] Hadoop homepage: http://hadoop.apache.org/
[21] Nutch homepage: http://nutch.apache.org/
[22] Nutch wiki: http://wiki.apache.org/nutch