Luận văn Ứng dụng hệ phân tán để tối ưu thời gian xử lý cho máy tìm kiếm

99 trang phuongnguyen 2090

Download

Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Ứng dụng hệ phân tán để tối ưu thời gian xử lý cho máy tìm kiếm", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

luan_van_ung_dung_he_phan_tan_de_toi_uu_thoi_gian_xu_ly_cho.pdf

Nội dung text: Luận văn Ứng dụng hệ phân tán để tối ưu thời gian xử lý cho máy tìm kiếm

i BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG LÊ V ĂN TIÊN ỨNG D ỤNG H Ệ PHÂN TÁN ĐỂ T ỐI ƯU TH ỜI GIAN X Ử LÝ CHO MÁY TÌM KI ẾM LU ẬN VĂN TH ẠC SĨ KỸ THU ẬT ĐÀ NẴNG – Năm 2011
ii LỜI CAM ĐOAN Tơi xin cam đoan đây là cơng trình nghiên c ứu c ủa riêng tơi d ưới s ự h ướng dẫn khoa h ọc c ủa PGS. TS. Lê V ăn S ơn. Các s ố li ệu và kết qu ả nêu trong lu ận là trung th ực và ch ưa t ừng được ai cơng b ố trong b ất k ỳ cơng trình nào khác. Ng ười cam đoan Lê V ăn Tiên
iii MỤC L ỤC LỜI CAM ĐOAN i MỤC L ỤC iii DANH M ỤC CÁC T Ừ VI ẾT T ẮT vi DANH M ỤC CÁC B ẢNG vii DANH M ỤC CÁC HÌNH vii MỞ ĐẦU 1 CH ƯƠ NG 1: T ỔNG QUAN V Ề MÁY TÌM KI ẾM 5 1.1 Gi ới thi ệu m ột s ố máy tìm ki ếm thơng d ụng 5 1.2 Ki ến trúc và c ơ ch ế ho ạt động c ủa máy tìm ki ếm 9 1.3 Bộ thu th ập thơng tin – Crawler 10 1.3.1 Các th ủ thu ật tìm ki ếm c ủa Crawler 11 1.3.2 Tính n ăng b ắt bu ộc crawler ph ải tuân theo 13 1.3.3 Tính n ăng crawler nên tuân theo 13 1.3.4 Vấn đề c ơ b ản c ần gi ải quy ết c ủa Crawler 14 1.3.5 Xây d ựng Crawler 15 1.3.6 Vấn đề c ần tránh 17 1.4 Bộ l ập ch ỉ m ục – Index 18 1.5 Bộ tìm ki ếm thơng tin – Search Engine 20 1.5.1 Tìm ki ếm theo t ừ khĩa 20 1.5.2 Tìm theo ng ữ ngh ĩa 21 1.6 Cấu trúc l ưu tr ữ d ữ li ệu index files 22 1.7 Kết lu ận 23 CH ƯƠ NG 2: H Ệ PHÂN TÁN CHO MÁY TÌM KI ẾM 25 2.1 Định ngh ĩa và các tính ch ất h ệ phân tán 25 2.1.1 Định ngh ĩa 25 2.1.2 Tính ch ất 27 2.2 Truy ền thơng trong h ệ phân tán 32
iv 2.2.1 Mơ hình client – server 33 2.2.2 Mơ hình RPC(Remote Procedure Call: g ọi th ủ t ục t ừ xa) 34 2.2.3 Truy ền thơng điệp (MOM) 36 2.2.4 Truy ền thơng h ướng dịng (SOM) 37 2.2.5 Truy ền thơng đa điểm (MultiCast) 37 2.3 Đồng b ộ hĩa ti ến trình 38 2.3.1 Đặt v ấn đề 38 2.3.2 Các gi ải pháp đồng b ộ ti ến trình 39 2.3.3 Kết lu ận 47 CH ƯƠ NG 3: ỨNG DỤNG H Ệ PHÂN TÁN T ỐI ƯU TH ỜI GIAN X Ử LÝ CHO MÁY TÌM KI ẾM 48 3.1 Phân tích máy tìm ki ếm trên h ệ t ập trung 48 3.1.1 Phân tích ho ạt động c ủa máy tìm ki ếm trên h ệ t ập trung 48 3.1.2 Một s ố h ạn ch ế c ủa máy tìm ki ếm trên h ệ t ập trung 48 3.1.3 Các y ếu t ố ảnh h ưởng đến th ời gian x ử lý c ủa máy tìm ki ếm 49 3.1.4 Hướng gi ải quy ết v ấn đề 50 3.2 Đề xu ất ph ươ ng th ức ho ạt động c ủa máy tìm ki ếm trên h ệ phân tán 52 3.2.1 Ph ươ ng th ức ho ạt động t ổng th ể c ủa h ệ th ống 52 3.2.2 Ph ươ ng th ức liên k ết các tr ạm trong h ệ th ống 53 3.2.3 Ph ươ ng th ức ho ạt động t ại các tr ạm c ủa h ệ th ống 54 3.2.4 Ph ươ ng th ức l ưu tr ữ file index c ủa h ệ th ống 57 3.3 Các v ấn đề phát sinh và cách gi ải quy ết 58 3.3.1 Ch ọn l ựa server x ử lý chính 58 3.3.2 Vấn đề đồng b ộ các ti ến trình 61 3.3.3 Vấn đề s ự c ố đường truy ền 64 3.3.4 Vấn add, remove các tr ạm 66 3.4 Phân tích h ệ th ống 69 3.4.1 Danh sách các tác nhân h ệ th ống 69 3.4.2 Sơ đồ tác nhân (UC) 70
v 3.4.3 Bi ểu đồ tu ần t ự 72 3.4.4 Bi ểu đồ ho ạt động (activity) 74 3.4.5 Sơ đồ l ớp 77 3.4.6 Các b ảng d ữ li ệu c ủa h ệ th ống file index 77 3.4.7 Xây d ựng h ệ th ống 79 3.4.8 Đề mơ ch ươ ng trình 84 KẾT LU ẬN 87 TÀI LI ỆU THAM KH ẢO 89 QUY ẾT ĐỊNH GIAO ĐỀ TÀI LU ẬN V ĂN TH ẠC S Ĩ (B ẢN SAO).
vi DANH M ỤC CÁC T Ừ VI ẾT T ẮT SE Máy tìm ki ếm DS Hệ phân tán DNS Hệ th ống tên mi ền MON Truy ền thơng h ướng thơng điệp SOM Truy ền thơng th ướng dịng RPC Gọi th ủ t ục t ừ xa MDR Nh ịp trơi l ớn nh ất c ủa đồng h ồ WWV Th ời gian qu ốc t ế UTC Gi ờ ph ối h ợp qu ốc t ế P Ti ến trình
vii , DANH M ỤC CÁC B ẢNG Bảng 1.1. B ảng x ếp h ạng search engine n ăm 2009 5 Bảng 3.1. B ảng tiêu chí t ối ưu máy tìm ki ếm 50 Bảng 3.2. B ảng tiêu chí ch ọn server t ối ưu 59 Bảng 3.3. B ảng phân tích độ r ỗi khác nhau c ủa các server trong h ệ 59 Bảng 3.4. B ảng d ữ li ệu tbl_document 77 Bảng 3.5. B ảng t ừ khĩa tbl_key_word 78 Bảng 3.6. B ảng ch ủ đề tbl_topics 78 Bảng 3.7. B ảng lo ại d ữ li ệu tbl_data_type 78
viii DANH M ỤC CÁC HÌNH Hình 1.1 B ảng x ếp h ạng search engine n ăm 2009 1 Hình 1.2 Giao di ện c ủa google search engine 6 Hình 1.3 Giao di ện c ủa xalo.vn search engine 8 Hình 1.4 Mơ hình ho ạt động c ủa máy tìm ki ếm 9 Hình 1.5 Bi ểu đồ tr ạng thái c ủa m ột liên k ết 17 Hình 1.6 Quá trình đánh ch ỉ m ục 18 Hình 1.7 Các b ước phân tích tài li ệu 19 Hình 1.8 C ấu trúc l ưu tr ữ files index [12] 23 Hình 1.9 C ấu trúc d ữ li ệu inverted index [11] 23 Hình 2.1 H ệ th ống máy đơn 25 Hình 2.2 Các th ực th ể c ủa h ệ phân tán 26 Hình 2.3 Mơ hình Client – Server 33 Hình 2.4 Mơ hình Synchronous RPC 35 Hình 2.5 Mơ hình Asynchronos RPC 36 Hình 2.6 Mơ hình MOM 36 Hình 2.7 Mơ hình multicast many-to-many 38 Hình 2.8 Mơ hình tr ật t ự t ừng ph ần 44 Hình 2. 9 Th ứ t ự các s ự ki ện t ại c ủa các ti ến trình t ại các tr ạm phát nh ận 45 Hình 2. 10 Các thời gian đánh d ấu Lamport (Lamport timestamps) 46 Hình 2. 11 Ví d ụ th ời gian logic Lamport 47 Hình 3. 1 Mơ hình ho ạt động c ủa pha x ử lý yêu c ầu ng ười dùng 50 Hình 3. 2 Các b ước ho ạt động c ủa máy tìm ki ếm ứng d ụng h ệ phân tán 51 Hình 3.3 Mơ hình ho ạt động t ổng th ể máy tìm ki ếm ứng d ụng h ệ phân tán 52 Hình 3. 4 Mơ hình liên k ết các tr ạm trong h ệ th ống 54 Hình 3. 5 Mơ hình ho ạt động c ủa tr ạm các tr ạm con trong h ệ th ống 54 Hình 3. 6 Thu ật tốn x ử lý c ủa crawler 56 Hình 3. 7 Mơ hình l ưu trữ h ệ th ống files index t ại m ỗi tr ạm 57
ix Hình 3. 8 H ệ th ống index file theo mơ hình cây 58 Hình 3. 9. S ơ đồ ch ọn server t ối ưu 60 Hình 3. 10 Mơ hình khơng đồng b ộ c ủa hai ti ến trình gi ữa hai tr ạm 61 Hình 3. 11.K ết qu ả sau khi đồng b ộ ti ến trình theo thu ật tốn lamport 63 Hình 3. 12 Thu ật tốn ki ểm tra tình tr ạng URL 64 Hình 3. 13 Mơ hình s ự c ố đường truy ền 65 Hình 3. 14 C ấu trúc giao ti ếp 2PC tuy ến tính 66 Hình 3. 15 Thu ật tốn x ử lý tr ạm remove kh ỏi h ệ 68 Hình 3. 16 Thu ật tốn x ử lý vi ệc add các tr ạm 69 Hình 3. 17 bi ểu đồ UC c ủa ng ười s ử d ụng 70 Hình 3. 18 Bi ểu đồ UC c ủa admin 71 Hình 3. 19 Bi ểu đồ tu ần t ự x ử lý yêu c ầu ng ười dùng 72 Hình 3. 20 Bi ểu đồ tu ần t ự truy tìm thơng tin t ự động 73 Hình 3. 21 Bi ểu đồ tu ần t ự l ập ch ỉ m ục t ự động 73 Hình 3. 22 Bi ểu b ồ ho ạt động x ử lý yêu c ầu ng ười dùng 74 Hình 3. 23 Bi ểu đồ ho ạt động truy tìm thơng tin t ự động 75 Hình 3. 24 Bi ểu đồ ho ạt động l ập ch ỉ m ục t ự động 76 Hình 3. 25 Mơ hình quan h ệ gi ữa các b ảng d ữ li ệu 79
1 MỞ ĐẦU 1. Lý do ch ọn đề tài Hơn 40 n ăm k ể t ừ khi internet ra đời cho đến nay, nĩ mang l ại r ất nhi ều ti ện ích h ữu d ụng cho ng ười s ử d ụng điển hình nh ư h ệ th ống th ư điện t ử ( email ), trị chuy ện tr ực tuy ến ( chat ), máy truy tìm d ữ li ệu ( search engine ), các d ịch v ụ th ươ ng mại, chuy ển ngân và các d ịch v ụ v ề y t ế giáo d ục Đi kèm v ới s ự bùng n ổ các d ịch vụ trên internet là s ự dùng n ổ v ề s ố l ượng website trên internet, hi ện t ại s ố l ượng website đã lên con s ố hàng t ỉ và khơng ng ừng t ăng lên theo th ời gian, đứng đầu là tên mi ền cĩ đuơi .com , theo th ống kê m ới nh ất đã lên t ới 84.000.000 tên mi ền. Tên mi ền cĩ đuơi .vn c ũng đã lên t ới 140.000 tên mi ền. Chính s ự bùng n ổ v ề s ố l ượng website trên internet đã b ổ sung cho kho thơng tin càng ngày càng kh ổng l ồ h ơn và ngày nay h ầu nh ư m ọi ki ến th ức c ủa m ọi l ĩnh v ực đều cĩ th ể tìm th ấy trên internet. Vấn đề đặt ra ở đây là làm th ế nào để tìm ki ếm m ột m ẫu thơng tin trong kho tàng thơng tin kh ổng l ồ nh ư v ậy m ột cách chính xác và nhanh nh ất, l ời gi ải cho câu hỏi đĩ là s ử d ụng máy tìm ki ếm ( search engine ) và hi ện nay nhi ều nhà d ịch v ụ đã sử d ụng nĩ r ất thành cơng, điển hình nh ư: Google, Yahoo, Mirosoft Máy tìm ki ếm đã xu ất hi ện và được đư a vào s ử d ụng t ừ r ất s ớm, nh ưng để t ối ưu hĩa sao cho th ời gian tr ả l ời k ết qu ả tìm ki ếm nhanh nh ất và chính xác nh ất thì các chuyên gia c ũng đang ngày càng hồn thi ện. Trong th ời gian g ần đây nh ờ s ự phát tri ển v ượt b ậc c ủa l ĩnh v ực ph ần c ứng CNTT và truy ền thơng, nh ờ v ậy mà m ột gi ải pháp m ới cho các ứng d ụng CNTT được ra đời và đang được các chuyên gia đánh giá cao v ề l ợi ích mà mĩ mang l ại đĩ là “ Hệ phân tán - Distributed Systems ”. 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 đượ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 nh ằm t ăng t ốc độ
2 bình quân trong tính tốn x ử lý, c ải thi ện tình tr ạng luơn s ẵn sàng c ủa các lo ại tài nguyên, t ăng độ an tồn cho d ữ li ệu, đa d ạng hĩa các lo ại hình d ịch v ụ tin h ọc, b ảo đảm tính tồn v ẹn c ủa thơng tin. Xuất phát t ừ nhu c ầu và các ti ền đề trên, vi ệc t ối ưu hĩa máy tìm ki ếm thơng tin, mà đặc bi ệt là t ối ưu th ời gian tìm ki ếm thơng tin c ủa máy tìm ki ếm là v ấn đề rất cĩ ý ngh ĩa trong giai đoạn CNTT hi ện nay và t ươ ng lai. Chính vì v ậy tơi ch ọn hướng nghiên c ứu này và áp d ụng “ hệ phân tán ” để t ối ưu th ời gian x ử lý cho máy tìm ki ếm và l ấy tên đề tài là “ứng d ụng h ệ phân tán để t ối ưu th ời gian x ử lý cho máy tìm ki ếm” . 2. M ục đích và nghi ệm v ụ nghiên c ứu c ủa đề tài Mục đích c ủa đề tài là nghiên c ứu áp d ụng h ệ phân tán vào máy tìm ki ếm nh ằm gi ải quy ết 3 yêu c ầu đặt ra nh ư sau: Một: Gi ảm th ời gian tìm ki ếm cho máy tìm ki ếm: cĩ 3 nguyên nhân chính + Gi ảm t ải l ượng truy c ập vào tài nguyên chung + Rút ng ắn kho ảng cách v ật lý gi ữa ng ười dùng và server + Tăng t ốc độ tính tốn – x ử lý Hai: Tăng độ an tồn cho d ữ li ệu cho máy tìm ki ếm: cĩ 3 nguyên nhân chính + Dữ li ệu được đặt t ại nhi ều server khác nhau và cĩ kh ả n ăng ph ục h ồi + Đảm b ảo tính đồng b ộ d ữ li ệu gi ữa các server + Đảm b ảo được tính tồn v ẹn c ủa d ữ li ệu Ba: Đảm b ảo h ệ th ống luơn ho ạt động thơng su ốt: cĩ 3 nguyên nhân chính + Tính co giãn c ủa h ệ th ống cao + Tính ch ịu l ỗi c ủa h ệ th ống cao + Tính m ở c ủa h ệ th ống cao
3 3. Đối t ượng và ph ạm vi nghiên c ứu - Nghiên c ứu mơ hình ho ạt động t ổng th ể c ủa máy tìm ki ếm và m ột s ố gi ải pháp tìm ki ếm thơng d ụng - Nghiên c ứu h ệ phân tán đa server + Xây d ựng h ệ phân tán đa server + Lưu tr ữ, truy xu ất d ữ li ệu trên h ệ phân tán đa server - Nghiên c ứu, ứng d ụng h ệ phân tán vào máy tìm ki ếm - Nghiên c ứu và áp d ụng b ộ định tuy ến ưu tiên yêu c ầu ( Request ) ng ười dùng - Ngơn ng ữ l ập trình Java, Lucene - Hệ qu ản tr ị c ơ s ở d ữ li ệu My SQL 4. Gi ả thi ết nghiên c ứu - Hi ểu được quá trình ho ạt động và m ột s ố gi ải pháp xây d ựng máy SE - Hi ểu được b ản ch ất c ủa h ệ phân tán và quá trình trao đổi thơng tin gi ữa các thành ph ần trong h ệ - Hi ểu thêm ngơn ng ữ l ập trình Java, Lucene và h ệ qu ản tr ị c ơ s ở d ữ li ệu My SQL - Hi ểu và v ận d ụng được gi ải pháp ứng d ụng h ệ phân tán để t ối ưu th ời gian tìm ki ếm cho máy SE 5. Ph ươ ng pháp nghiên c ứu - Thu th ập, tìm hi ểu, phân tích các tài li ệu và thơng tin cĩ liên quan đến lu ận văn - Phân tích, n ắm rõ quá trình ho ạt động c ủa máy tìm ki ếm - Nắm rõ cách xây d ựng, truy xu ất và l ưu tr ữ d ữ li ệu trên h ệ phân tán
4 - Phân tích, tìm h ướng gi ải quy ết cho các v ấn đề n ảy sinh khi áp d ụng h ệ phân tán vào máy SE - Tri ển khai xây d ựng ch ươ ng trình ch ạy trên h ệ phân tán - Tri ển khai xây d ựng ch ươ ng trình ch ạy trên h ệ t ập trung - Ki ểm th ử, đánh giá k ết qu ả và rút ra k ết lu ận 6. Ý ngh ĩa khoa h ọc và th ực ti ễn c ủa đề tài - Nghiên c ứu, n ắm v ững ph ươ ng pháp th ực hi ện c ủa máy tìm ki ếm - Nghiên c ứu, n ắm v ững b ản ch ất và ph ươ ng pháp ho ạt động c ủa h ệ phân tán đa server - Nghiên c ứu, xây d ựng m ột mơ hình l ưu tr ữ thơng tin m ới cho máy tìm ki ếm - Gi ảm đáng k ể th ời gian th ực hi ện cho máy tìm ki ếm - Tăng độ an tồn cho d ữ li ệu - Đảm b ảo h ệ th ống luơn thơng su ốt - Mang l ại l ợi ích ứng d ụng r ất l ớn
5 CH ƯƠ NG 1: TỔNG QUAN V Ề MÁY TÌM KI ẾM Máy tìm ki ếm ( ti ếng Anh: search engine ), hay cịn được g ọi v ới ngh ĩa r ộng hơn là cơng c ụ tìm ki ếm ( search tool ), nguyên thu ỷ là m ột ph ần m ềm nh ằm tìm ra các trang web trên m ạng Internet cĩ n ội dung theo yêu c ầu ng ười dùng d ựa vào các thơng tin mà chúng cĩ. Tr ữ l ượng thơng tin này c ủa cơng c ụ tìm ki ếm th ực ch ất là một lo ại cơ s ở d ữ li ệu ( database ) c ực l ớn. Vi ệc tìm các tài li ệu s ẽ d ựa trên các từ khĩa ( keyword ) được ng ười dùng gõ vào và tr ả v ề m ột danh m ục c ủa các trang Web cĩ n ội dung ch ứa t ừ khĩa mà nĩ tìm được. Máy tìm ki ếm ho ạt động d ựa vào 3 b ộ chính: - Bộ thu th ập thơng tin – Robot - Bộ l ập ch ỉ m ục – Index - Bộ tìm ki ếm thơng tin – Search Engine 1.1 Gi ới thi ệu m ột s ố máy tìm ki ếm thơng d ụng Bảng 1.2. Bảng x ếp h ạng search engine n ăm 2009
6 Th ế gi ới google.com Hình 1.1 Giao di ện c ủa google search engine Google là b ộ máy tìm ki ếm (Search Engine) hi ện đang được đánh giá là “vơ địch” trên Internet, v ới trên 4,2 t ỷ trang Web đã được l ập ch ỉ m ục và cĩ t ốc độ tìm ki ếm c ực nhanh. Google khơng ch ỉ là cơng c ụ tìm ki ếm được h ầu h ết nh ững ng ười lướt Web s ử d ụng do h ỗ tr ợ t ới 97 ngơn ng ữ, đây cịn là ti ện ích tìm ki ếm được nhúng vào r ất nhi ều website ( một d ịch v ụ được Google cung c ấp d ưới nhi ều hình th ức và cho nh ững đối t ượng khác nhau ). Các b ộ tìm ki ếm c ủa google Google khơng ng ừng tìm ki ếm và c ập nh ật các trang m ới để thêm vào ch ỉ m ục của b ạn. Cĩ ch ươ ng trình ph ụ trách v ấn đề này được g ọi là các robot hay b ọ tìm ki ếm (Googlebot). Các Googlebot được g ọi ch ươ ng trình tìm ki ếm cĩ nhi ệm v ụ duy
7 nh ất là để thu th ập tài li ệu web để xây d ựng m ột c ơ s ở d ữ li ệu được s ử d ụng b ởi các cơng c ụ tìm ki ếm c ủa nĩ. Các Googlebot s ử d ụng m ột quy trình d ựa trên thu ật tốn xác định các trang web để thu th ập d ữ li ệu, t ần s ố và s ố l ượng trang để tìm n ạp t ừ m ỗi trang web. Danh sách này các trang web tồn di ện để xác định các liên k ết đến các trang khác. Bộ l ập ch ỉ m ục c ủa google Đánh ch ỉ m ục là m ột quá trình quét qua các trang web và t ạo ra ch ỉ s ố cĩ s ử dụng Google để cho k ết qu ả khi b ạn tìm ki ếm. Th ực t ế, các robot các phân tích và đư a ra m ột ch ỉ m ục c ủa t ất c ả các t ừ h ọ xem và v ị trí c ủa h ọ. Và vi ệc trang web cĩ được Google đánh ch ỉ hay khơng luơn là m ối quan tâm hàng đầu c ủa các nhà thi ết kế web hi ện nay. Các lo ại dữ li ệu google cĩ th ể tìm ki ếm Khơng h ẳn v ậy, Google c ũng trích xu ất thơng tin ch ỉ m ục ho ặc nhi ều lo ại t ập tin khác nhau: PDF, PS (Adobe PostScript), Excel (xls), tài li ệu, v ăn b ản MW, DOC, WRI, RTF, ANS, TXT, thuy ết trình PowerPoint (ppt) các t ập tin, Microsoft Works (wks, wps, Wdb) và swf. Điều này được th ực hi ện để cung c ấp cho Google nhi ều k ết qu ả h ơn, trên th ực tế, trong quá trình th ực hi ện tìm ki ếm b ạn c ũng cĩ th ể th ấy hi ển th ị m ột s ố lo ại t ập tin khác html, ví d ụ: file .doc hay .pdf Bộ pageRank c ủa google Google PageRank là m ột h ệ th ống cĩ nhi ệm v ụ x ếp h ạng các trang web, được phát tri ển b ởi Larry Page và Sergey Brin thu ộc Đại h ọc Stanford. Trong khi hi ện nay Google cĩ r ất nhi ều k ỹ s ư làm vi ệc để c ải thi ện v ề m ọi m ặt c ủa Google hàng ngày, PageRank ti ếp t ục đĩng m ột vai trị trung tâm trong nhi ều cơng c ụ tìm ki ếm web c ủa Google.
8 Vi ệt Nam xalo.vn Hình 1.2 Giao di ện c ủa xalo.vn search engine Xalo.vn là m ột Máy tìm ki ếm (search engine) được Tinhvân Media phát tri ển với tham v ọng Xalo.vn s ẽ tr ở thành cơng c ụ tìm ki ếm ti ếng Vi ệt hàng đầu c ủa Vi ệt Nam. Xalo.vn hi ện t ại đang cung c ấp 7 d ịch v ụ tìm ki ếm bao g ồm: - Tìm ki ếm Web: d ịch v ụ tìm ki ếm thơng tin t ổng h ợp trên d ữ li ệu g ần 100 tri ệu trang v ăn b ản ti ếng Vi ệt hi ện cĩ trên các Website c ủa Vi ệt Nam - Tìm ki ếm Tin t ức: d ịch v ụ t ổng h ợp tin t ức và tìm ki ếm thơng tin trên d ữ li ệu dạng tin t ức được t ổng h ợp t ừ g ần 70 trang tin điện t ử hàng đầu c ủa Vi ệt Nam
9 - Tìm ki ếm Di ễn đàn: d ịch v ụ tìm ki ếm cho phép ng ười dùng tìm ki ếm thơng tin từ h ơn 100 di ễn đàn l ớn nh ất c ủa Vi ệt Nam hi ện t ại. - Tìm ki ếm Ảnh: d ịch v ụ tìm ki ếm hình ảnh trên s ố l ượng h ơn 20 tri ệu hình ảnh được ng ười dùng Vi ệt Nam đư a lên Internet. - Tìm ki ếm Blog: d ịch v ụ tìm ki ếm cho phép ng ười dùng tìm ki ếm thơng tin trên hầu h ết các m ạng xã h ội được cung c ấp b ởi Vi ệt Nam c ũng nh ư trên th ế gi ới mà ng ười Vi ệt Nam hay s ử d ụng - Tìm ki ếm Nh ạc: d ịch v ụ tìm ki ếm d ữ li ệu Nh ạc t ừ các Website nghe nh ạc tr ực tuy ến l ớn nh ất Vi ệt Nam hi ện t ại. - Tìm ki ếm Rao v ặt: d ịch v ụ t ổng h ợp và tìm ki ếm thơng tin rao v ặt t ừ h ơn 20 Website mua bán rao v ặt l ớn nh ất Vi ệt Nam Với các d ịch v ụ cung c ấp và tính n ăng khác bi ệt cho t ừng d ịch v ụ, Xa L ộ đang khơng ng ừng được hồn thi ện để cĩ th ể ph ục v ụ t ốt nh ất nhu c ầu tìm ki ếm c ủa ng ười dùng Internet Vi ệt Nam và tr ở thành máy tìm ki ếm ti ếng Vi ệt hàng đầu c ủa Vi ệt Nam. 1.2 Ki ến trúc và c ơ ch ế ho ạt động c ủa máy tìm ki ếm Crawler Hình 1.3 Mơ hình ho ạt động c ủa máy tìm ki ếm
10 Máy tìm ki ếm chi thành 2 ph ần chính Front-end và ph ần Back-end - Front- end: Bao g ồm giao di ện ng ười s ử d ụng ( Search engine interface ); bộ s ắp x ếp ( ranking ) và b ộ x ử lý yêu c ầu ng ười dùng ( query parser ) Khi ng ười s ử d ụng gửi m ột yêu c ầu tìm ki ếm m ột m ẫu thơng tin, máy tìm ki ếm sẽ phân tích yêu c ầu và gửi đến server, server th ực hi ện so kh ớp yêu c ầu v ới dữ li ệu trong kho index files và s ắp x ếp k ết qu ả tìm được theo th ứ t ự t ừ cao đến c ủa độ chính xác, cu ối cùng là hi ển th ị k ết qu ả cho ng ười dùng. - Back-end: Bao g ồm b ộ thu th ập thơng tin ( Crawler ) và b ộ l ập ch ỉ m ục (indexer ) Bộ Crawler d ựa vào các robot tìm ki ếm s ẽ t ự động tìm ki ếm thơng tin trên internet và chuy ển thơng tin qua b ộ indexer l ập ch ỉ m ục và l ưu vào kho d ữ li ệu index files. Các thành ph ần này s ẽ được phân tích c ụ th ể ở ph ần sau. 1.3 Bộ thu th ập thơng tin – Crawler Từ m ột hay nhi ều các liên k ết ban đầu, Crawler lên đường th ực hi ện cơng vi ệc “lùng s ục” Internet c ủa mình. Crawler t ải v ề n ội dung các trang web t ừ các liên k ết đã nh ận ban đầu và truy xu ất các liên k ết m ới n ằm trong n ội dung c ủa các trang này. Các liên k ết m ới này s ẽ được n ạp vào m ột trình điều khi ển (Crawler Manager). Crawler Manager s ẽ quy ết định các liên k ết nào s ẽ được vi ếng th ăm k ế ti ếp, Crawler Manager s ẽ n ạp chúng vào hàng đợi để ch ờ x ử lý. Các liên k ết này s ẽ được qu ản lý trong c ơ s ở d ữ li ệu để thu ận ti ện cho cơng vi ệc c ập nh ật thơng tin m ới. Trong m ột l ần th ực hi ện thì các liên k ết ph ải ch ỉ được truy c ập m ột l ần để t ăng kh ả năng ho ạt động và tránh trùng l ặp n ội dung. M ột crawler đi qua b ốn b ước c ơ b ản: • Bắt đầu t ừ m ột hay nhi ều liên k ết • Tải n ội dung
11 • Phân tích nội dung, tìm liên k ết, đi theo các liên k ết • Theo dõi liên k ết, tránh trùng l ặp Cĩ nhi ều ch ế độ làm vi ệc cho crawler th ực hi ện nhi ệm v ụ truy tìm thơng tin. Các ch ế độ được phân bi ệt theo nhi ều cách. Các đặc điểm phân bi ệt cĩ th ể là: • Batch Mode • Incremental Mode Batch mode Crawler s ẽ đánh ch ỉ m ục liên t ục các trang web và khơng t ải n ội dung v ề để l ưu tr ữ. Cách này n ội dung luơn được c ập nh ật nh ưng ch ỉ phù h ợp cho lượng trang web nh ỏ cĩ gi ới h ạn. Ch ẳng h ạn nh ư m ục tiêu c ủa crawler được định ra là th ực hi ện trên m ột s ố website c ụ th ể nào đấy. Crawler ch ỉ cĩ nhi ệm v ụ liên t ục ch ạy qua các wesiste này để c ập nh ật các n ội dung m ới. Incremental Mode ho ạt động ở ch ế độ này crawler s ẽ khơng bao gi ờ xĩa các n ội dung l ưu tr ữ. Khi g ặp m ột tài li ệu được cho là đã vi ếng th ăm thì crawler s ẽ tuân theo chi ến l ược c ập nh ật n ội dung đã được cài đặt. Ở ch ế độ này thì crawler cần ph ải cĩ kho l ưu tr ữ tài li ệu th ật l ớn. • Breadth-first(Tìm ki ếm theo chi ều r ộng) • Depth-first(Tìm ki ếm theo chi ều sâu) 1.3.1 Các th ủ thu ật tìm ki ếm c ủa Crawler 1.3.1.1 Chi ến thu ật tìm ki ếm theo chi ều sâu (Depth-first) Từ m ột danh sách ch ứa các liên k ết c ần duy ệt, th ực hi ện các b ước sau : (1) Cho danh sách = {trang đầu tiên} (2) L ấy trang đầu tiên trong danh sách. * N ếu cĩ qua (3) * N ếu khơng qua (5)
12 (3) Trang này đã xét t ới ch ưa ? * N ếu r ồi, quay l ại (2) * N ếu ch ưa, qua (4) (4) Đánh d ấu đã t ới r ồi. Phân tích và tìm xem liên k ết cĩ trong trang đĩ khơng? (4a) N ếu cĩ, thêm liên k ết này vào đầu danh sách. Quay l ại (4) (4b) N ếu khơng, quay l ại (2). (5) K ết thúc. 1.3.1.2 Chi ến thu ật tìm ki ếm theo chi ều r ộng Từ m ột danh sách ch ứa các liên k ết c ần duy ệt, th ực hi ện các b ước sau : (1) Cho danh sách = {trang đầu tiên} (2) L ấy trang đầu tiên trong danh sách. * N ếu cĩ qua (3) * N ếu khơng qua (5) (3) Trang này đã xét t ới ch ưa ? * N ếu r ồi, quay l ại (2) * N ếu ch ưa, qua (4) (4) Đánh d ấu đã t ới r ồi. Phân tích và tìm xem liên k ết cĩ trong trang đĩ khơng? * (4a) N ếu cĩ, thêm liên k ết này vào cu ối danh sách. Quay l ại (4) * (4b) N ếu khơng, quay l ại (2). (5) K ết thúc. 1.3.1.3 Chi ến thu ật tìm ki ếm theo ng ẫu nhiên Từ m ột danh sách ch ứa các liên k ết c ần duy ệt, th ực hi ện các b ước sau : (1) Cho danh sách = {trang đầu tiên} (2) L ấy ng ẫu nhiên m ột trang trong danh sách. * N ếu cĩ qua (3) * N ếu khơng qua (5)
13 (3) Trang này đã xét t ới ch ưa ? * N ếu r ồi, quay l ại (2) * N ếu ch ưa, qua (4) (4) Đánh d ấu đã t ới r ồi. Phân tích và tìm xem liên k ết cĩ trong trang đĩ khơng? * (4a) N ếu cĩ, thêm liên k ết này vào cu ối danh sách. Quay l ại (4) * (4b) N ếu khơng, quay l ại (2). (5) K ết thúc. 1.3.2 Tính n ăng b ắt bu ộc crawler ph ải tuân theo - Robustness: Các crawler ph ải được thi ết k ế chính xác và ho ạt động ổn định. Nhiều website cĩ t ạo ra ch ức n ăng đánh l ừa các crawler. T ức là d ẫn các crawler vào các vịng l ặp khơng cĩ k ết thúc. Crawler c ần ph ải được thi ết k ế sao cho cĩ th ể nh ận ra “b ẫy” và quay tr ở ra. Khơng ph ải “cái b ẫy” nào c ũng t ạo ra nh ằm đánh l ừa các crawler mà đơi khi là vơ tình b ởi trang web thi ết k ế b ị l ỗi. - Politeness : Các website s ẽ cĩ các chính sách cho phép các crawler truy c ập vào trang web mình theo m ột c ấp độ nào đĩ. Crawler c ần ph ải tuân th ủ các chính sách này. 1.3.3 Tính n ăng crawler nên tuân theo Distributed : Các crawler c ần được thi ết k ế theo mơ hình phân tán để cĩ th ể th ực thi trên nhi ều máy tính. Scalable : Crawler c ần được thi ết k ế cĩ kh ả n ăng t ăng t ần xu ất ho ạt động b ằng nhi ều cách. Ch ẳng h ạn nh ư thêm nhi ều máy tính ho ặc t ăng dung l ượng b ăng thơng. Performance and efficiency : Crawler c ần được thi ết k ế hi ệu th ật hi ệu qu ả trong vi ệc s ử d ụng các tài nguyên h ệ th ống nh ư b ộ x ử lý, dung l ượng l ưu tr ữ và băng thơng m ạng.
14 Freshness : Crawler c ần ph ải được c ập nh ật n ội dung m ới m ột cách liên t ục. Crawler c ần ph ải cĩ t ần xu ất truy c ập trang web x ấp x ĩ v ới t ần xu ất thay đổi n ội dung c ủa trang web. Extensible : Crawler c ần được thi ết k ế sao cho d ễ dàng m ở r ộng theo nhi ều hướng. Ch ẳng h ạn nh ư t ăng định d ạng cho n ội dung truy c ập hay thêm giao th ức truy c ập Internet. Để được nh ư v ậy crawler c ần được chia thành các ph ần nh ỏ (các mudole) để ti ện cho vi ệc duy trì và nâng c ấp. 1.3.4 Vấn đề c ơ b ản c ần gi ải quy ết c ủa Crawler Nh ững trang web nào nên được t ải v ề? Tải v ề t ất c ả các trang web đĩ là m ột vi ệc làm khơng t ưởng vì v ậy c ần phải cĩ chi ến l ược l ựa ch ọn các trang web quan tr ọng để t ải v ề. Các trang web được nhi ều truy c ập, các trang web cung c ấp n ội dung cĩ giá tr ị và ph ổ bi ến thì nên được v ị trí ưu tiên trong hàng đợi. Làm th ế nào để c ập nh ật n ội dung? Trên Internet các trang web c ập nh ật th ường xuyên n ội dung c ủa nĩ. Cĩ trang c ập nh ật liên t ục cĩ trang c ập nh ật trong th ời gian lâu h ơn. Làm th ế nào để quy ết định các trang web nào nên được truy c ập lại và nh ững trang web nào c ần b ỏ qua. C ũng nh ư cơng vi ệc trên ta khơng th ể c ập nh ật l ại tồn b ộ các trang web m ột cách th ường xuyên. C ần ph ải cĩ chi ến l ược l ựa ch ọn. Làm th ế nào để t ải n ội dung trang web t ối ưu nh ất. Trong khi crawler th ực hi ện cơng vi ệc thu th ập tài li ệu s ẽ tiêu t ốn tài nguyên nh ư CPU hay tài nguyên mạng. N ếu crawler chi ếm quá nhi ều tài nguyên m ạng thì nĩ cĩ th ể b ị ng ười qu ản tr ị các website lo ại tr ừ. C ần ph ải cĩ chi ến l ược để nâng cao kh ả n ăng ho ạt động sao cho ít t ốn tài nguyên nh ất. Làm th ế nào để x ử lý song song. Tài li ệu trên Internet là vơ cùng l ớn c ần ph ải cĩ nhiều crawler ho ạt động đồng th ời. Làm th ế nào để các crawler khác nhau s ẽ khơng truy c ập cùng m ột website ở các th ời điểm khác nhau.
15 Kh ả n ăng l ưu tr ữ: Yêu c ầu t ổng quan c ủa m ột cơng c ụ tìm ki ếm và sao chép nội dung web bao hàm tính n ăng t ải file, giao di ện tr ực quan d ễ m ở r ộng, b ảo m ật gi ữa server và trình duy ệt web, trình di ễn các thành ph ần động, và ph ản ảnh giao di ện web m ột cách chính xác. M ục đích trong vi ệc sao chép m ột trang web là ph ải ph ản ảnh l ại chính xác giao di ện c ủa trang web, t ải t ừng hình ảnh, liên k ết c ũng nh ư thành ph ần động. Đây là m ột nhi ệm v ụ khĩ h ầu h ết b ởi vì kh ả n ăng phân tích mã JavaScript c ủa crawler cịn th ấp. Ph ạm vi ho ạt động c ủa crawler ph ụ thu ộc vào cách trình bày c ủa các trang web ngu ồn. Ví d ụ c ần ph ải cĩ thu ật tốn để crawler truy l ục hết các tài li ệu trên cùng m ột website tr ước khi đi theo các liên k ết đi ra các website khác. Hình ảnh n ằm ở các website bên ngồi được tham chi ếu t ới b ởi website này thì l ại khác, t ất c ả các hình ảnh ph ải được l ưu tr ữ để ph ục v ụ cho vi ệc l ưu các trang web trong cache. HTTP header chuy ển h ướng (HTTP header redirect) n ằm ở v ị trí Location c ủa HTTP header ph ải được l ần theo. Các liên k ết n ằm hai server nh ưng trên cùng m ột mi ền thì c ần ph ải theo. Ví d ụ nh ư mail.yahoo.com và quote.yahoo.com. Nhi ều liên kết và các dịng chuy ển h ướng th ường được vi ết d ưới mã JavaScript, các liên k ết này c ần ph ải l ần theo. C ũng c ần ph ải định ngh ĩa tr ước gi ới h ạn độ sâu c ủa liên k ết. 1.3.5 Xây dựng Crawler Cĩ hai c ấu trúc mà crawler cĩ th ể được xây d ựng. Th ứ nh ất là xây d ựng crawler nh ư là m ột ch ươ ng trình đệ quy. Th ứ hai là xây d ựng crawler theo c ấu trúc dữ li ệu s ử d ụng hàng đợi. Ch ươ ng trình đệ quy là m ột k ỹ thu ật l ập trình mà các ph ươ ng th ức t ự g ọi l ại chính nĩ. Ch ươ ng trình đệ quy phù h ợp cho các d ự án mà các cơng vi ệc được th ực thi l ặp l ại m ột cách h ệ th ống và thơng tin mà cơng vi ệc trong t ươ ng lai c ũng được bi ết tr ước s ẽ gi ống nh ư cơng vi ệc đang được th ực hi ện hi ện t ại. Ch ươ ng trình đệ quy ch ỉ nên dùng cho crawler mà bi ết tr ước s ẽ cĩ s ố ít các trang web vì m ỗi khi ch ươ ng trình ch ạy s ẽ l ưu d ữ li ệu vào ng ăn x ếp v ới s ố l ượng trang web l ớn thì ng ăn xếp s ẽ r ất l ớn và cĩ th ể gây tràn ng ăn x ếp nguyên nhân ng ăn ch ặn khơng cho
16 ch ươ ng trình cĩ th ể ho ạt động. Lý do n ữa là ta s ẽ khơng th ể th ực hi ện kh ả n ăng đa lu ồng cho crawler đệ quy, b ởi khi ta đệ quy s ẽ t ạo ra nhi ều ti ến trình. M ỗi ti ến trình đĩng vai trị là m ột crawler, m ỗi ti ến tình l ại cĩ m ột ng ăn x ếp riêng m ỗi khi ch ươ ng trình g ọi l ại chính nĩ thì s ẽ t ạo ra m ột ng ăn x ếp m ới điều này khơng phù h ợp vì c ần ph ải dùng m ột chung m ột ng ăn xếp cho m ột ch ươ ng trình crawler. Khi xây d ựng crawler s ử d ụng c ấu trúc d ữ li ệu hàng đợi, đầu tiên crawler s ẽ nh ận được liên k ết c ủa trang web g ốc. Crawler s ẽ n ạp liên k ết này vào hàng đợi. Khi crawler tìm th ấy các liên k ết m ới thì nĩ c ũng đư a các liên k ết này vào hàng đợi. Khi x ử lý xong m ột liên k ết crawler s ẽ l ấy m ột liên k ết trong hàng đợi ra và ti ếp t ục truy c ập. Cơng vi ệc s ẽ k ết thúc khi khơng cịn m ột liên k ết nào trong hàng đợi. Nh ư mơ t ả thì m ột crawler ch ỉ c ần m ột hàng đợi là cĩ th ể th ực thi, Nh ưng thơng th ường ta dùng b ốn hàng đợi để l ưu tr ữ các liên k ết để theo dõi các tr ạng thái của nĩ. • Waiting Queue trong hàng đợi này thì các liên k ết đang ch ờ để được xử lý và liên k ết m ới s ẽ được n ạp vào hàng đợi này khi chúng được tìm th ấy. • Running Queue liên k ết được chuy ển t ới hàng đợi này khi crawler b ắt đầu x ử lý nĩ. M ột điều quan tr ọng c ần tránh là m ột liên k ết ph ải ch ỉ được x ử lý một l ần để tránh lãng phí tài nguyên. Khi m ột liên k ết đã được x ử lý thì ho ặc nĩ được chuy ển t ới Error Queue ho ặc Complete Queue. • Error Queue khi cĩ l ỗi x ảy ra trong quá trình x ử lý liên k ết thì liên k ết này s ẽ được chuy ển t ới Error Queue. M ột khi đã vào đây thì liên k ết s ẽ khơng chuy ển đi đâu n ữa và c ũng s ẽ khơng được x ử lý l ần nào n ữa. • Complete Queue khi x ử lý thành cơng thì các liên k ết s ẽ được chuy ển tới đây và c ũng s ẽ khơng chuy ển t ới đâu n ữa. Một liên k ết s ẽ ch ỉ ở m ột hàng đợi t ại m ột th ời điểm. Vì v ậy m ỗi th ời điểm cĩ th ể được coi là m ỗi tr ạng thái c ủa liên k ết. Ch ươ ng trình máy tính th ường được
17 mơ t ả theo bi ểu đồ tr ạng thái trong đĩ s ẽ bi ểu di ễn lu ồng di chuy ển c ủa liên k ết t ừ tr ạng thái này sang tr ạng thái khác. Tìm thấy liên kết Waiting queue Running queue Error queue Complete queue Hình 1.4 Bi ểu đồ tr ạng thái c ủa m ột liên k ết 1.3.6 Vấn đề c ần tránh Quá t ải m ạng và server: S ử d ụng robot, m ột điều tiên quy ết ph ải chú ý đĩ là tài nguyên m ạng ph ải l ớn. Nhi ều robot ho ạt động s ẽ gây t ốn m ột l ượng l ớn b ăng thơng cũng nh ư các tài nguyên m ạng khác, t ốc độ x ử lý, dung l ượng b ộ nh ớ v.v Cập nh ật quá m ức: Khĩ cĩ th ể ki ểm sốt được t ốc độ c ập nh ật m ới c ủa trang web. C ập nh ật thơng tin là quan tr ọng. Nh ưng ph ải cĩ chi ến l ược c ập nh ật phù h ợp sao cho t ốc độ c ập nh ật x ấp x ỉ v ới t ốc độ thay đổi n ội dung c ủa m ột trang web sao cho khơng quá th ường xuyên gây t ốn kém tài nguyên, hay quá r ời r ạc d ữ li ệu khơng được c ập nh ật cho ng ười dùng. Nh ững tình hu ống khơng mong đợi khác: Robot khơng th ể nh ận ra các url khác nhau v ề tên nh ưng cùng d ẫn v ề m ột địa ch ỉ. Ch ẳng h ạn nh ư DSN và IP. Robot c ũng cĩ th ể đi vào nh ững vịng l ặp vơ h ạng khi các trang cĩ s ử d ụng sessionId. M ỗi phiên
18 làm vi ệc s ẽ t ạo ra m ột Id, id này cĩ th ể là tham s ố c ủa liên k ết. Các liên k ết c ứ t ạo ra liên t ục nh ư v ậy. Robot theo các liên k ết này s ẽ khơng cĩ điểm d ừng. M ột tình hu ống khơng mong đợi n ữa là trong các website cĩ s ử d ụng l ịch (calendars) thành ph ần l ịch này s ử d ụng các trang web động cùng v ới các liên k ết c ứ liên t ục ch ỉ đến nh ững ngày, hay n ăm trong t ươ ng lai. Spider đi theo các liên k ết này c ũng s ẽ khơng cĩ điểm d ừng. 1.4 Bộ l ập ch ỉ m ục – Index Các trang Web sau khi thu th ập v ề s ẽ được phân tích, trích ch ọn nh ững thơng tin c ần thi ết để l ưu tr ữ trong c ơ s ở d ữ li ệu nh ằm ph ục v ụ cho nhu c ầu tìm ki ếm sau này. Ba b ước c ơ b ản trong quá trình l ập ch ỉ m ục: Hình 1.5 Quá trình đánh ch ỉ m ục Lập ch ỉ m ục là quá trình phân tích tài li ệu c ần đánh ch ỉ m ục thành các t ừ, cụm t ừ thích h ợp quan tr ọng cĩ kh ả n ăng ph ản ánh đúng n ội dung c ủa tài li ệu. B ởi vậy c ần ph ải cĩ gi ải pháp để chi ết l ọc thơng tin m ột cách chính xác và ph ải t ự động vì l ượng tài li ệu là vơ cùng l ớn khơng th ể làm th ủ cơng. Thơng tin được chi ết l ọc ph ải đủ n ội dung để tr ả v ề k ết qu ả tìm ki ếm cho ng ười dùng và c ũng khơng được d ư th ừa gây t ốn kém dung l ượng l ưu tr ữ c ũng nh ư tr ả v ề k ết qu ả khơng chính xác cho ng ười dùng. Quá trình phân tích tài li ệu được chia thành các b ước nh ỏ h ơn:
19 Hình 1.6 Các b ước phân tích tài li ệu Bước th ứ nh ất chuy ển các d ạng tài li ệu thành text hay cịn g ọi là plaintext tạm d ịch là v ăn b ản thu ần túy. Vì tài li ệu ngày nay t ồn t ại ở nhi ều định d ạng khác nhau nh ư pdf, doc, xml, rtf, html, v.v Khơng th ể phân tích ngay trên các định d ạng này được mà c ần ph ải chuy ển t ất c ả thành v ăn b ản thu ần túy sau đĩ m ới ti ếp t ục các bước phân tích ti ếp theo. Bước th ứ hai chuy ển v ăn b ản thành đơ n v ị t ừ v ựng (Tokenization). T ức là tách v ăn b ản thành các đơ n v ị t ừ. Trong Ti ếng Anh thì c ần d ựa vào các d ấu kho ảng tr ắng ta cĩ th ể phân tích v ăn b ản thành các token. Cịn trong Ti ếng Vi ệt thì khĩ h ơn. Ví d ụ nh ư ta cĩ câu Th ầy giáo này r ất g ươ ng m ẫu n ếu d ựa vào kho ảng tr ắng ta phân tích s ẽ thành 6 token sau : th ầy, giáo, này, r ất, g ươ ng, m ẫu nh ư th ế s ẽ khơng thích h ợp mà k ết qu ả ta c ần ph ải được là 4 token th ầy giáo, này, r ất, g ươ ng m ẫu. Bước th ứ hai là lo ại b ỏ các stopword. Stopwords là các t ừ mà nĩ xu ất hi ện trong v ăn b ản nh ưng khơng mang ngh ĩa ch ẳng h ạn trong Ti ếng Vi ệt các stopword nh ư: thì, là, và, nh ưng v.v cịn trong Ti ếng Anh các stopwords nh ư: a, the, but, and v.v Các stopword thì khơng c ần thi ết trong vi ệc đánh ch ỉ m ục cho tài li ệu, nĩ
20 khơng ph ản ánh n ội dung c ủa v ăn b ản và h ầu nh ư trong v ăn b ản nào c ũng xu ất hi ện chúng vì th ế chúng c ần ph ải được lo ại b ỏ. Bước th ứ ba là lo ại b ỏ h ậu t ố. Ph ần này trong Ti ếng Vi ệt khơng cĩ vì Ti ếng Vi ệt là ngơn ng ữ đơ n th ể. Trong Ti ếng Anh m ột t ừ ngồi t ừ g ốc cịn cĩ th ể cĩ ti ền tố và h ậu t ố. Ti ền t ố cĩ làm thay đổi ngh ĩa c ủa t ừ nên được gi ữ nguyên. H ậu t ố ch ỉ thay đổi t ừ lo ại c ủa t ừ mà khơng thay đổi ngh ĩa nên c ần ph ải được đư a v ề thành t ừ gốc. Bước cu ối cùng là tính tr ọng s ố c ủa các t ừ cĩ trong tài li ệu. Trong v ăn b ản thì cĩ nhi ều t ừ s ẽ xu ất hi ện th ường xuyên, các t ừ đĩ ph ản ảnh n ội dung c ủa tài li ệu. Cần ph ải tính tr ọng s ố c ủa các t ừ để lo ại b ỏ các t ừ mang tr ọng s ố th ấp.[1] 1.5 Bộ tìm ki ếm thơng tin – Search Engine Tìm sách trong th ư vi ện là m ột ví d ụ điển hình cho t ầm quan tr ọng c ủa cơng vi ệc tìm ki ếm. Khi ta c ần tìm m ột quy ển sách, ta vào th ư vi ện tìm trong danh sách ch ỉ m ục để tìm ra v ị trí c ủa sách. N ếu khơng cĩ ch ỉ m ục, ta khơng th ể tìm ra v ị trí của sách trong m ột th ư vi ện l ớn hay cĩ tìm ra thì t ốn th ời gian r ất nhi ều. T ươ ng t ự nh ư v ậy đối v ới tài li ệu trên Internet, ta c ần ph ải l ập m ột kho ch ỉ m ục tr ước khi tìm ki ếm. Ứng d ụng web là b ước cu ối dùng trong xây d ựng m ột máy tìm ki ếm. Nhi ệm vụ c ủa ứng d ụng web là t ạo giao di ện giao ti ếp gi ữa ng ười dùng và máy tìm ki ếm. Nh ận câu truy v ấn t ừ ng ười dùng, sau đĩ tr ả v ề k ết qu ả truy v ấn cho ng ười dùng. 1.5.1 Tìm ki ếm theo t ừ khĩa Tìm ki ếm theo t ừ khĩa là cách tìm ki ếm mà d ựa trên các t ừ được cho là quan tr ọng nh ất trong tài li ệu. Nh ư đã đề c ập các t ừ cĩ tr ọng s ố cao nh ất trong tài li ệu là các t ừ xu ất hi ện th ường xuyên và cĩ kh ả n ăng ph ản ảnh m ột ph ần n ội dung mà tài li ệu đề c ập t ới. Ví d ụ các t ừ khĩa, c ụm t ừ khĩa h ữu d ụng trong ch ủ để máy tìm ki ếm nh ư "tìm ki ếm", "cơng c ụ tìm ki ếm", "ph ươ ng pháp tìm ki ếm", "thu ật tốn tìm ki ếm", "x ếp h ạng" " độ t ươ ng đồng", "k ết qu ả tìm ki ếm", v.v Nh ững t ừ khĩa, c ụm từ khĩa trên ph ản ảnh được n ội dung c ủa ch ủ đề này. Các trang web ngày nay
21 th ường li ệt kê t ất c ả các t ừ khĩa c ủa website mình để t ăng tính chính xác khi các máy tìm ki ếm đánh ch ỉ m ục cho website c ũng nh ư ph ục v ụ cho cơng vi ệc tìm ki ếm của ng ười dùng d ễ dàng h ơn. Trong tài li ệu tác gi ả c ũng th ường định ngh ĩa các t ừ khĩa cho tài li ệu mình nh ằm ph ục v ụ cho máy tìm ki ếm đánh ch ỉ m ục d ễ dàng và chính xác h ơn. Trong các trang html thì các t ừ khĩa được định ngh ĩa trong th ẻ ở đầu trang trong ph ần . Ví d ụ: Các t ừ khĩa được li ệt kê trong thu ộc tính content. Ngo ại tr ừ nh ững tài li ệu trên, các t ừ khĩa hồn tồn ph ụ thu ộc vào cách phân tích tài li ệu c ủa máy tìm ki ếm. Ch ẳng h ạn nh ư các máy tìm ki ếm th ường để ý đến t ựa đề c ủa trang web, n ơi mà s ẽ ch ứa n ội dung liên quan đến ch ủ đề mà trang web mu ốn đề c ập đến nhi ều nh ất. Hay các máy tìm ki ếm c ũng th ường phân tích các câu đầu c ủa m ột tài li ệu, đây là các câu mang n ội dung tr ọng tâm mà tài li ệu mu ốn nĩi đến. Các câu này được xem nh ư là câu chính trong m ột đoạn v ăn mang n ội dung cốt lõi. Ngồi ra các máy tìm ki ếm cịn phân tích các t ừ được l ặp đi l ặp l ại nhi ều l ần trong tài li ệu. Các t ừ đĩ c ũng ph ản ảnh n ội dung c ủa tài li ệu. Các khĩ kh ăn c ủa chi ến l ược tìm ki ếm theo t ừ khĩa là làm sao ph ải x ử lý các từ đồng âm khác ngh ĩa. Vì các t ừ đồng âm khác ngh ĩa mà các máy tìm ki ếm cĩ khi sẽ tr ả v ề k ết qu ả ch ẳng liên quan gì đến m ục đích c ủa ta. Khĩ kh ăn th ứ hai là mà các máy tìm ki ếm ph ải gi ải quy ết là v ấn đề đư a các t ừ v ề thành t ừ g ốc ( stemming, vấn đề này ch ỉ cĩ trong Ti ếng Anh ). Ch ẳng h ạng khi ta nh ập vào t ừ “big” thì k ết qu ả tr ả v ề cĩ th ể là “bigger”. M ột khĩ kh ăn n ữa là máy tìm ki ếm ch ưa tr ả v ề được các kết qu ả theo t ừ đồng ngh ĩa. Ch ẳng h ạn khi ta truy v ấn v ới t ừ “giáo viên” thì k ết qu ả tr ả v ề s ẽ khơng tr ả v ề các tài li ệu cĩ các t ừ “th ầy giáo” hay “cơ giáo”.[1] 1.5.2 Tìm theo ng ữ ngh ĩa Thơng tin v ề tìm ki ếm theo ng ữ ngh ĩa đã c ũ và hi ện nay nĩ c ũng khơng cịn tồn t ại. Nh ưng thơng tin v ề cách tìm ki ếm theo ng ữ ngh ĩa s ẽ cĩ giá tr ị cho các nhà nghiên c ứu.
22 Tìm ki ếm theo ng ữ ngh ĩa là cách tìm ki ếm mà đốn ý c ủa ng ười s ử d ụng thơng qua câu truy v ấn. Cách này ph ải gom nhĩm tài li ệu thành ch ủ đề, d ựa vào lý thuy ết trí tu ệ nhân t ạo để phân tích câu truy v ấn c ủa ng ười dùng. Ch ẳng h ạn nh ư trong tài li ệu cĩ t ừ trái tim. Cĩ hai l ĩnh v ực chính mà t ừ trái tim thu ộc đĩ là y h ọc và tình yêu. Ch ỉ v ới t ừ trái tim thì ch ưa đủ tri th ức để máy tìm ki ếm l ựa ch ọn ch ủ đề để sắp x ếp cho tài li ệu này. Máy tìm ki ếm d ựa vào các t ừ đi cùng t ừ trái tim ch ẳng h ạn nh ư nh ịp đập, huy ết áp v.v thì cĩ th ể bi ết tài li ệu h ướng đến ch ủ đề y h ọc. Cịn t ừ trái tim đi v ới các t ừ nh ư th ổn th ức, tan v ỡ, ng ọt ngào v.v thì máy tìm ki ếm cĩ th ể đốn nh ận ng ười dùng đang h ướng đến ch ủ đề tình yêu.[1] 1.6 Cấu trúc l ưu tr ữ d ữ li ệu index files Bộ crawler c ăn c ứ vào các liên k ết, chúng t ải t ất c ả các thơng tin mà chúng b ắt gặp v ề máy, m ột kh ối thơng tin h ổn độn khơng tuân theo b ất k ỳ m ột quy t ắc nào. Nh ư đã phân tích t ại m ục 1.4, b ộ indexer cĩ nhi ệm v ụ trích l ọc các thơng tin của b ộ clawler t ải v ề thành các đơ n v ị t ừ v ựng, chúng ti ếp t ục lo ại b ỏ các stopword, lo ại b ỏ hậu t ố và các t ừ cĩ tr ọng s ố th ấp. Cu ối cùng chúng l ưu các đơ n v ị t ừ v ựng vào h ệ th ống index file. Một bộ index được chia thành nhi ều sub index. M ỗi sub index cĩ c ấu trúc và ch ức n ăng ch ỉ m ục riêng c ủa nĩ. Mỗi Sub index được chia ra nhi ều segments, các segments cĩ th ể là m ột ho ặc nhi ều t ập tin. M ột segment được xem nh ư m ột ch ức n ăng ch ỉ m ục đầy đủ ch ứa d ữ li ệu inverted index.
23 Compass index Segments [segment 1] [segment 2] Sub index 1 . . . [segment N] Sub index 2 Sub index N Hình 1.7 Cấu trúc l ưu tr ữ files index [12] Hình 1.8 Cấu trúc d ữ li ệu inverted index [11] 1.7 Kết lu ận Qua quá trình tìm hi ểu c ấu trúc và mơ hình ho ạt động c ủa máy tìm ki ếm cho ta th ấy vi ệc truy v ấn c ủa ng ười dùng ch ỉ th ực hi ện trên files index, nh ư v ậy vi ệc t ổ
24 ch ức l ưu tr ữ h ệ th ống files index ảnh h ưởng tr ực ti ếp đến s ố l ượng, ch ất l ượng và th ời gian tr ả v ề c ủa k ết qu ả truy v ấn. - Nếu h ệ th ống index file đặt t ập trung t ại m ột server + Vi ệc l ưu tr ữ hệ th ống index file kh ổng l ồ là m ột v ấn đề khơng th ể th ực hi ện được. + Số lượng ng ười dùng l ớn cùng truy v ấn vào m ột segment c ủa h ệ th ống index files d ẫn đến vi ệc truy xu ất thơng tin tr ở nên quá t ải m ột server khơng th ể đáp ứng được. + Vi ệc x ử lý một l ượng thơng tin quá l ớn c ủng là v ấn đề khơng th ể tri ển khai được Máy tìm ki ếm tri ển khai trên h ệ t ập trung ch ỉ cĩ th ể dùng để nghiên cứu, nĩ khơng tri ển khai ứng d ụng ra cơng chúng được. - Nếu h ệ th ống index file phân tán t ại nhi ều server khác nhau + Phân tải ra nhi ều server tránh được vi ệc truy c ập t ập trung. + Tăng t ốc độ x ử lý cho máy tìm ki ếm (vì t ất c ả các server trong h ệ th ống đều làm vi ệc ph ục v ụ cho máy SE ) Phân tán h ệ th ống index files s ẽ gi ảm được th ời gian x ử lý cho máy SE
25 CH ƯƠ NG 2: HỆ PHÂN TÁN CHO MÁY TÌM KI ẾM 2.1 Định ngh ĩa và các tính ch ất h ệ phân tán 2.1.1 Định ngh ĩa - Hệ t ập trung: Tiêu bi ểu là h ệ th ống máy đơ n, là máy khơng k ết n ối v ật lý và logic v ới các máy khác nh ư hình v ẽ sau: U1 U2 Bộ nh ớ trong . Un Hình 2.1 Hệ th ống máy đơ n Ở m ột th ời điểm nh ất định, máy đơ n được điều hành b ởi m ột h ệ điều hành duy nh ất. H ệ th ống nh ư v ậy được g ọi là h ệ tin h ọc t ập trung, thích h ợp v ới các máy tính lo ại trung và lo ại l ớn. Tĩm l ại, h ệ tin h ọc t ập trung bao g ồm m ột h ệ th ống máy đơ n được điều khi ển bởi m ột h ệ điều hành duy nh ất và qu ản lý tồn b ộ thơng tin trên thi ết b ị nh ớ c ục b ộ của mình. - Hệ phân tán:
26 Hệ tin h ọc phân tán (Distributed System) là h ệ th ống khơng chia s ẻ b ộ nh ớ và đồng h ồ, khác v ới xu h ướng phân tán các tính tốn trên nhi ều b ộ x ử lý c ủa h ệ th ống đa x ử lý. Nh ư v ậy, h ệ tin h ọc phân tán địi h ỏi h ệ th ống ph ần c ứng c ủa mình ph ải trang b ị b ộ nh ớ c ục b ộ, các b ộ x ử lý trao đổi thơng tin v ới nhau thơng qua các h ệ th ống đường truy ền nh ư cáp chuyên d ụng, đường điện tho ại, cáp quang. . . Nh ư v ậy, h ệ tin h ọc phân tán cĩ th ể bao g ồm b ốn th ực th ể nh ư sau: Ph ần Ph ần cứng mềm Dữ liệu Truy ền thơng Hình 2.2 Các th ực th ể c ủa h ệ phân tán Một t ư t ưởng l ớn c ủa h ệ tin h ọc phân tán là phân tán hố 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 khác nhau. Đĩ là 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 ử, chính ph ủ điện t ử, th ư vi ện điện t ử, . . . Hi ện nay, đứng trên nh ững ph ươ ng di ện khác nhau, cĩ th ể cĩ các định ngh ĩa khác nhau v ề h ệ tin h ọc phân tán, nh ưng ph ổ bi ến h ơn c ả là định ngh ĩa sau: Hệ tin h ọc phân tán (h ệ phân tán) là h ệ th ống x ử lý thơng tin bao g ồm nhi ều b ộ xử lý hay 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 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[2]. Từ định ngh ĩa trên, h ệ phân tán cĩ các ưu điểm c ăn b ản so v ới h ệ t ập trung, nh ư sau:
27 - Tăng t ốc độ bình quân trong tính tốn, x ử lý. - Cải thi ện tình tr ạng luơn s ẵn sàng c ủa các lo ại tài nguyên. - Tăng độ an tồn cho d ữ li ệu. - Đa d ạng hố các lo ại hình d ịch v ụ tin h ọc. - Đảm báo tính tồn v ẹn c ủa thơng tin. 2.1.2 Tính ch ất Thơng th ường h ệ phân tán bao g ồm các đặc tính c ơ b ản sau đây: 2.1.2.1 Tính chia s ẽ tài nguyên (Resource Sharing): Các tài nguyên cĩ th ể chia s ẻ trong h ệ phân tán là: Tài nguyên v ật lý, tài nguyên logic. Đối v ới h ệ phân tán, bài tốn chia s ẻ tài nguyên ph ức t ạp h ơn vì b ản thân các máy tính t ự tr ị c ũng cĩ tài nguyên riêng c ủa nĩ. Tuy nhiên, ta s ẽ khơng đề cập đến v ấn đề chia s ẻ các tài nguyên dùng riêng này mà ch ủ y ếu đi vào chia sẻ tài nguyên dùng chung. Cụ th ể h ơn, bài tốn chia s ẻ tài nguyên trong h ệ phân tán cĩ hai đối t ượng chính: - Tập các tài nguyên dùng chung: Các tài nguyên này là phân tán, chúng là hữu h ạn và cĩ kh ả n ăng b ổ sung được (ví d ụ nh ư hi ệu n ăng c ủa CPU ). Tuy nhiên, chúng ta khơng th ể b ổ sung các tài nguyên này m ột cách tùy ý, tùy ti ện được. - Tập các ng ười s ử d ụng ( user ): T ập này cĩ đặc điểm là phân tán, h ữu h ạn và cĩ t ốc độ t ăng tr ưởng r ất nhanh. Từ đĩ, chúng ta d ễ dàng nh ận th ấy, l ượng tài nguyên trong h ệ phân tán thì hữu h ạn mà s ố l ượng ng ười s ử dụng l ại càng nhi ều. Điều đĩ d ẫn t ới v ấn đề chia s ẻ tài nguyên ngày càng tr ở nên c ăng th ẳng, nĩ cĩ th ể gây ra xung đột, t ắc ngh ẽn trong h ệ phân tán. Và h ệ phân tán s ẽ ph ải đảm b ảo làm th ế nào để vi ệc
28 chia s ẻ tài nguyên tr ở nênhi ệu qu ả nh ất. Nh ư v ậy, m ột bài tốn chia s ẻ tài nguyên c ần đảm b ảo gi ải quy ết các yêu c ầu sau: - Mức m ột: Tránh các hi ện t ượng x ấu (tắc ngh ẽn ) x ảy ra - Mức hai: Đảm b ảo vi ệc chia s ẻ tài nguyên m ột cách hi ệu quá. 2.1.2.2 Tính m ở (Openness): Thơng th ường, m ột h ệ th ống nào đĩ th ường cung c ấp nhi ều d ịch v ụ khác nhau cho các đối t ượng ng ười dùng khác nhau. Đối v ới h ệ phân tán, nĩ được gọi là cĩ tính m ở n ếu nh ư khi ta b ổ sung m ột d ịch v ụ m ới, thì d ịch v ụ này cĩ kh ả n ăng chung s ống bình th ường v ới các d ịch v ụ tr ước đĩ. Và bài tốn chia sẻ tài nguyên v ẫn được gi ải quy ế tm ột cách h ợp lý. Một s ố đặc tr ưng: - Interoperability: Các thành ph ần khác nhau trên các h ệ th ống khác nhau cĩ th ể cùng t ồn t ại và làm vi ệc v ới nhau. - Portability: Các ứng d ụng được tri ển khai trên h ệ phân tán A c ũng cĩ th ể được th ực thi mà ko c ần ch ỉnh s ửa trên m ột hệ phân tán B khác cĩ cùng giao di ện nh ư hệ phân tán A. - Extensible: D ễ dàng thêm các thành ph ần m ới, thay th ế các thành ph ần c ũ mà ko h ề ảnh h ưởng đến ph ần cịn l ại c ủa h ệ phân tán. 2.1.2.3 Tính đồng th ời (Concurrency): Theo định ngh ĩa thì h ệ phân tán bao g ồm nhi ều b ộ x ử lý ho ặc vi x ử lý n ằm tại nhi ều trí khác nhau được liên k ết v ới nhau thơng qua đường truy ền vi ễn thơng, do đĩ các ti ến trình x ử lý được th ực hi ện m ột cách độc l ập và đồng th ời. Điều này giúp cho làm t ăng t ốc độ x ử lý cơng vi ệc lên đáng k ể. Vi ệc x ử lý đồng th ời di ễn ra khi m ột yêu c ầu ( Request ) c ủa ng ười dùng (user ) được gửi đến h ệ yêu c ầu x ử lý m ột v ấn đề c ụ th ể. Ngay l ập t ức, h ệ phân tán request ng ười dùng đến x ử lý t ại các bộ x ử lý riêng bi ệt trong h ệ và k ết qu ả
29 (result ) được t ập h ợp t ừ t ất c ả các k ết qu ả c ủa t ừng b ộ x ử lý riêng bi ệt trong hệ. 2.1.2.4 Tính co giãn (Scalability): Tính co dãn là m ột tính ch ất quan tr ọng trong h ệ phân tán. M ột h ệ th ống được g ọi là cĩ th ể co dãn (scalable ) n ếu nĩ cĩ th ể ki ểm sốt được vi ệc gia tăng c ủa tài nguyên, c ũng nh ư ng ười s ử d ụng mà khơng làm ảnh h ưởng t ới hi ệu năng, c ũng nh ư làm t ăng độ ph ức t ạp c ủa h ệ th ống. Hay nĩi cách khác, điều này liên quan đến vi ệc xây d ựng m ộth ệ phân tán sao cho trong b ất c ứ tr ường h ợp thay đổi nào, thì ph ần m ềm h ệ phân tán c ủa chúng ta ph ải cĩ kh ả năng đáp ứng được. Thơng th ường, vi ệc co dãn th ường liên quan đến s ự gia t ăng kích th ước của h ệ phân tán theo ba khía c ạnh chính sau: - Size: S ố l ượng ng ười s ử d ụng và s ố l ượng tài nguyên, ứng v ới s ự gia t ăng này, h ệ th ống cĩ th ể đối m ặt v ới nguy cơ b ị quá t ải ( do nĩ ph ải x ử lý nhi ều user request h ơn). T ươ ng t ự nh ư v ậy, do h ệ th ống ph ải qu ản lý m ột s ố l ượng tài nguyên l ớn h ơn, nĩ c ũng cĩ th ể b ị quá t ải. - Geography: H ệ phân tán c ũng cĩ th ể phát tri ển theo kho ảng cách địa lý, đĩ là kho ảng cách v ật lý th ực t ế gi ữa nh ững ng ười s ử d ụng, nh ững tài nguyên v ới nhau. V ấn đề liên quan đến s ự m ở r ộng v ề địa lý, chính là v ấn đề v ề truy ền thơng ( kho ảng cách càng xa thì độ tr ễ truy ền thơng càng l ớn, và nguy c ơ x ảy ra l ỗi c ũng càng cao ) - Administration: H ệ phân tán được phát tri ển và m ở r ộng theo nhi ều l ĩnh vực hành chính khác nhau. V ấn đề liên quan đến vi ệc m ở r ộng này, đĩ là s ự xung đột các chính sách gi ữa các t ổ ch ức trong quá trình đảm b ảo vi ệc s ử dụng, qu ản lý và b ảo v ệ tài nguyên m ột cách đúng đắn.
30 2.1.2.5 Tính ch ịu l ỗi (Fault Tolerance): Hệ bao g ồm nhi ều b ộ x ử lý k ết n ối v ới nhau. N ếu cĩ m ột b ộ x ử lý trong h ệ phát sinh l ỗi, ngay l ập t ức cơng vi ệc s ẽ được chuy ển cho các b ộ x ử lý khác trong h ệ s ẽ đảm nh ận, đảm b ảo hệ th ống luơn ho ạt động bình th ường. Thơng th ường h ệ th ống phân tán s ẽ phát sinh các l ỗi sau đây: - Lỗi s ụp đổ ( crash failure ): khi server g ặp l ỗi này thì nĩ s ẽ b ị treo, tr ước đĩ server v ẫn ho ạt động t ốt cho đến khi ng ừng ho ạt động. Khi server g ặp lỗi này, nĩ s ẽ khơng th ể làm gì được n ữa. M ột ví d ụ hay g ặp l ỗi này là h ệ điều hành c ủa các máy cá nhân. Khi h ệ điều hành ng ừng ho ạt động thì ch ỉ cịn cách duy nh ất là kh ởi động l ại. - Lỗi b ỏ sĩt ( omission failure ): là l ỗi mà m ột server khơng th ể đáp ứng được yêu c ầu g ửi t ới nĩ. Ng ười ta chia nĩ thành hai lo ại: + Lỗi khi nh ận thơng điệp g ửi t ới: g ặp l ỗi này, server khơng nh ận được yêu c ầu ngay c ả t ừ client g ần nĩ nh ất và m ặc dù k ết n ối gi ữa server v ới client đã được thi ết l ập. L ỗi khi nh ận thơng điệp ch ỉ làm cho server khơng nh ận bi ết được các thơng điệp g ửi t ới nĩ mà khơng h ề ảnh h ưởng đến tr ạng thái c ủa server. + Lỗi khi g ửi thơng điệp: server v ẫn nh ận được các yêu c ầu, v ẫn hồn thành yêu c ầu đĩ nh ưng vì m ột lý do nào đĩ l ại khơng th ể g ửi k ết qu ả t ới máy đã yêu c ầu. M ột trong nh ững lý do th ường g ặp là do b ộ nh ớ đệm g ửi đầy. Trong tr ường h ợp g ặp l ỗi này, server c ần chu ẩn b ị tình hu ống clien s ẽ gửi l ại yêu c ầu đã g ửi đĩ . - Lỗi th ời gian ( timing failure ): là l ỗi x ảy ra khi server ph ản ứng l ại quá ch ậm, sau c ả th ời gian cho phép. Trong m ột h ệ th ống luơn cĩ các ràng bu ộc v ề mặt th ời gian. N ếu bên g ửi g ửi đến bên nh ận nhanh quá, b ộ nh ớ đệm c ủa bên nh ận khơng đủ để ch ứa thì s ẽ gây ra l ỗi. T ươ ng t ự, server ph ản ứng l ại ch ậm quá, v ượt quá kho ảng timeout quy định s ẵn c ũng s ẽ gây ra l ỗi, ảnh h ưởng đến hi ệu n ăng chung c ủa h ệ th ống.
31 - Lỗi đáp ứng ( Response failure ): là l ỗi khi server tr ả l ời khơng đúng. Đây là m ột ki ểu l ỗi r ất ngiêm tr ọng và được phân chia thành hai lo ại: + L ỗi v ề m ặt giá tr ị: là l ỗi khi server tr ả l ời l ại yêu c ầu c ủa client v ới giá tr ị khơng chính xác. Ví d ụ khi s ử d ụng các máy tìm ki ếm, k ết qu ả tr ả v ề khơng h ề liên quan gì t ới yêu c ầu c ủa ng ười s ử d ụng. + Lỗi v ề chuy ển tr ạng thái: là l ỗi khi server ho ạt động tr ệch h ướng kh ỏi lu ồng điều khi ển. Cĩ ngh ĩa là server tr ả l ời các yêu c ầu được g ửi t ới m ột cách khơng theo nh ư mong đợi. - Lỗi b ất kì ( Arbitrary failure ): m ột server cĩ th ể t ạo ra m ột l ỗi b ất kì ở b ất kì th ời gian nào. Đây là lo ại l ỗi nguy hi ểm nh ất. Cĩ th ể cĩ hai kh ả n ăng x ảy ra: + Th ứ nh ất: m ột server t ạo ra m ột k ết qu ả sai mà khơng th ể phát hi ện ra được. + Th ứ hai: server b ị l ỗi cĩ liên k ết v ới các server khác t ạo ra m ột k ết qu ả sai. 2.1.2.6 Tính trong su ốt (Transparency): Hệ phân tán dù cĩ hồn h ảo, t ốt đẹp đến bao nhiêu thì b ản ch ất c ủa nĩ v ẫn là r ời r ạc, và ng ười thi ết k ể ph ải làm th ế nào để che gi ấu, làm gi ảm ảnh h ưởng, khi ếm khuy ết c ủa h ệ phân tán đối v ới ng ười s ử d ụng. Nh ư v ậy, tính trong su ốt được hi ểu là s ự che gi ấu s ự phân tách, r ời r ạc c ủa các thành phân trong h ệ phân tán đối v ới ng ười s ử d ụng. Qua đĩ, ng ười s ử dụng s ẽ coi h ệ th ống nh ư là m ột h ệ th ống th ống nh ất. Tính trong su ốt là mộttính ch ất r ất m ạnh, và c ũng r ất khĩ để đạt được. Thơng th ường, cĩ m ột vài dạng tính trong su ốt chính sau: - Access Transparency: Tài nguyên tồn c ục và c ục b ộ cùng được truy c ập theo cách gi ống h ệt nhau. - Location Transparency: Ng ười s ử d ụng s ẽ khơng nh ận bi ết được v ị trí v ật lý th ực t ế c ủa tài nguyên mà h ọ đang dùng
32 - Migration Transparency : Tài nguyên cĩ th ể được di chuy ển t ừ n ơi này sang n ơi khác mà ng ười s ử d ụng khơng nh ận ra s ự thay đổi - Replication Transparency: Ng ười s ử d ụng khơng nh ận ra s ự t ồn t ại c ủa nhi ều b ản sao c ủa tài nguyên trong h ệ th ống Failure Transparency: Ng ười s ử dụng khơng nh ận ra h ệ th ống mà h ọ đang s ử d ụng đang cĩ l ỗi ở m ột thành ph ần nào đĩ. - Concurrency Transparency: Ng ười s ử d ụng khơng h ề bi ết h ọ đang chia s ẻ tài nguyên dùng chung v ới r ất nhi ều ng ười s ử d ụng khác. 2.2 Truy ền thơng trong h ệ phân tán Truy ền thơng làm m ột y ếu t ố t ối quan tr ọng trong h ệ phân tán. S ẽ là vơ ích khi chúng ta tìm hi ểu v ề h ệ phân tán mà l ại khơng quan tâm đến cách th ức các ti ến trình trong các máy khác nhau trao đổi thơng tin. Các thành ph ần c ủa m ột h ệ phân tán cĩ th ể phân chia thành 2 nhĩm: nhĩm các đồi t ượng v ật lý và nhĩm các đồi t ượng logic, để cĩ th ể t ươ ng tác l ẫn nhau, các thành ph ần này ph ải được n ối k ết vởi nhau thơng qua các kênh truy ền thơng. H ệ th ống phân tán và các ứng d ụng bao g ồm các thành ph ần ph ần m ềm t ươ ng tác v ới nhau để th ực hi ện các tác v ụ. Các thành ph ần yêu c ầu ho ặc cung c ấp s ự truy c ập tài nguyên trong h ệ phân tán thì được th ực hi ện nh ư nh ững tr ạm. Trong h ệ th ống client/server, m ột tr ạm client ph ải t ươ ng tác v ới một máy server khi cĩ nhu c ầu truy c ập đến m ột tài nguyên khơng thu ộc quy ền qu ản lý c ủa nĩ (cĩ th ể là ph ần c ứng, ph ần m ềm hay d ữ li ệu). Truy ền thơng gi ữa hai tr ạm bao g ồm hai thao tác g ửi và nh ận các gĩi tin nh ằm đạt được hai k ết qu ả: - Truy ền d ữ li ệu t ừ n ơi phát đến n ơi thu. - Trong m ột vài thao tác truy ền thơng, cĩ s ự đồng b ộ gi ữa thu và phát, quá trình thu ho ặc phát s ẽ được ti ếp di ễn cho đến khi cĩ s ự can thi ệp c ủa m ột ti ến trình khác nh ằm gi ải phĩng nĩ.
33 Để điều th ứ nh ất được th ực hi ện, các ti ến trình ph ải chia s ẻ kênh truy ền thơng để d ữ li ệu cĩ th ể truy ền d ẫn gi ữa điểm phát và thu. Điều th ứ hai là m ột ng ầm định trong vi ệc l ập trình truy ền thơng nguyên m ẫu. Khuơn d ạng c ủa gĩi tin g ửi và nh ận được quy định trong l ập trình, nh ứng khuơn dạng này t ạo ra các thơng điệp ( message ) hành động gi ữa các tr ạm thu và phát. M ối thơng điệp bao g ồm m ột t ập các đơ n v ị d ữ li ệu được tr ạm phát g ủi thơng qua các c ơ cấu truy ền thơng ( cổng, kênh truy ền) để đến tr ạm thu. Các c ơ ch ế truy ền thơng cĩ th ể là đồng b ộ ho ặc blocking, t ức là phía g ửi sau khi g ửi m ột thơng điệp s ẽ ch ờ cho đến khi phía thu nh ận được và th ực hi ện thao tác tr ả l ời, hay c ũng cĩ th ể là khơng đồng b ộ, t ức là các thơng điệp được x ếp vào m ột hàng đợi và ch ờ đến khi phía thu đồng ý nh ận thì l ập t ức được g ửi đi. Thơng th ường ng ười ta s ử d ụng b ốn mơ hình ph ổ bi ến để truy ền thơng tin, đĩ là mơ hình client-server, mơ hình RPC ( Remote Procedure Call ), mơ hình MOM ( Message – Oriented Middleware ) và mơ hình SOM ( Stream – Oriented Middleware ). 2.2.1 Mơ hình client – server Client Server Waiting Processing Hình 2.3 Mơ hình Client – Server Một trao đổi trong mơ hình khách ch ủ bao g ồm ba b ước:
34 Bước 1: Client g ửi m ột yêu c ầu đến Server. Bước 2: Server th ực hi ện yêu c ầu Bước 3: Server gửi thơng điệp tr ả l ời đến Client. Mỗi phiên giao d ịch nh ư v ậy c ần ph ải th ực hi ện m ột gửi m ột thơng điệp, nh ận thơng điệp và địi h ỏi ph ải cĩ s ự đồng b ộ gi ữa Client và Server. Khi client g ửi m ột thơng điệp yêu c ầu đến server, server ti ếp nh ận và x ử lý thơng điệp, sau đĩ g ởi k ết qu ả l ại cho client. Trong khi server x ử lý k ết qu ả client ph ải ng ưng t ất c ả các giao dịch và ch ờ cho đến khi nh ận được kêt qu ả t ừ server m ới th ực hi ện các giao d ịch khác. 2.2.2 Mơ hình RPC(Remote Procedure Call: gọi th ủ t ục t ừ xa) Th ực hi ện ch ủ y ếu theo mơ hình Client/Server. Khi m ột ti ến trình trên máy client (A) g ọi m ột th ủ t ục trên máy server (B), ti ến trình g ọi trên A s ẽ b ị treo, và quá trình th ực thi th ủ t ục được g ọi di ễn ra trên máy B. Thơng tin được truy ền từ phía g ọi A sang phía nh ận B trong các tham s ố, và được tr ả v ề d ưới d ạng k ết qu ả c ủa th ủ t ục. Ph ươ ng pháp này được g ọi là l ời g ọi th ủ t ục t ừ xa ( RPC – Remote Procedure call ). Trong khi ý t ướng c ủa ph ươ ng pháp là đơ n gi ản nh ư v ậy, thì trong th ực t ế, v ẫn cịn tồn t ại nhi ều v ấn đề liên quan đến nĩ. - Th ứ nh ất, do phía g ọi và phía b ị g ọi n ằm ở hai máy tính khác nhau, nên chúng s ẽ được th ực thi trên nh ững khơng gian địa ch ỉ khác nhau, và điều này gây ra s ự ph ức t ạp khơng nh ỏ. - Th ứ hai, tham s ố và k ết qu ả tr ả v ề cũng ph ải được truy ền đi, điều này cũng gây ra s ự ph ức t ạp n ếu nh ư hai máy là khơng t ươ ng t ự nhau. - Cu ối cùng, trong quá trình th ực hi ện, cĩ th ể m ột trong hai máy x ảy ra l ỗi, và l ỗi này cĩ th ể gây ra m ột s ố v ấn đề khác n ữa. Tuy nhiên, các khĩ kh ăn này đều đã được kh ắc ph ục ph ần nào, và RPC v ẫn đang là m ột trong nh ững k ĩ thu ật ph ổ bi ến được s ử d ụng b ởi nhi ều h ệ phân tán.
35 Ng ười ta phân RPC ra làm hai lo ại : Synchronous RPC (RPC đồng b ộ) và Asynchronos RPC ( RPC Khơng đồng b ộ). Synchronous RPC: A B Hình 2.4 Mơ hình Synchronous RPC Với truy ền thơng đồng b ộ, sau khi client đư a ra request, nĩ s ẽ ph ải ch ờ ph ản h ồi từ phía server. Trong th ời gian đĩ, nĩ khơng làm gì c ả, và đĩ c ũng chính là m ột nh ược điểm c ủa vi ệc truy ền đồng b ộ. Điều này s ẽ d ẫn t ới vi ệc ch ờ đợi vơ ích c ủa ti ến trình g ọi trên client, nh ất là khi l ời g ọi khơng cĩ k ết qu ả tr ả v ề, trong khi nĩ cĩ th ể th ực hi ện m ột s ố cơng vi ệc h ữu ích khác. M ột s ố ví d ụ v ề vi ệc ti ến trình g ọi khơng c ần ph ải đợi k ết qu ả tr ả v ề, đĩ là vi ệc thêm một entry vào c ơ s ở d ữ li ệu, kh ởi động m ột d ịch v ụ t ừ xa, x ử lý hàng lo ạt ( batch processing )
36 Asynchronos RPC A B Hình 2.5 Mơ hình Asynchronos RPC Với truy ền thơng khơng đồng b ộ, sau khi server nh ận được request, nĩ s ẽ gửi một tín hi ệu ACK v ề cho client để báo nh ận. Khi client nh ận được tín hi ệu ACK này, nĩ cĩ th ể th ực hi ện các cơng vi ệc khác trong th ời gian server x ử lý request kia. 2.2.3 Truy ền thơng điệp (MOM) Messaging Provider A Client P Msg1 Msg1 A P Client I Destination I Send Receive Hình 2.6 Mơ hình MOM Trong nhi ều tr ường h ợp, RPC t ỏ ra khơng phù h ợp, nĩ địi h ỏi c ả bên g ửi và bên nh ận cùng ph ải s ẵn sàng ( active ) t ại th ời điểm di ễn ra truy ền thơng. Tuy nhiên, đơi khi chúng ta khơng th ể bi ết được li ệu bên nh ận yêu c ầu cĩ đang s ẵn sàng (active ) hay khơng. Chúng ta cĩ th ể gi ải quy ết v ấn đề này thơng qua h ệ th ống messages hàng đợi, ho ặc Messages – Oriented Middleware ( MOM ). H ệ th ống
37 Messages hàng đợi cung c ấp h ỗ tr ợ r ộng rãi cho các giao ti ếp khơng đồng b ộ liên tục. B ản ch ất c ủa các h ệ th ống này là chúng cung c ấp dung l ượng l ưu tr ữ cho, mà khơng địi h ỏi m ột trong hai ng ười g ửi ho ặc nh ận được ho ạt động trong quá trình truy ền messages. 2.2.4 Truy ền thơng h ướng dịng (SOM) Với các hình th ức truy ền thơng MOM, chúng ta ch ỉ quan tâm đến vi ệc trao đổi thơng tin, mà khơng h ề quan tâm c ụ thể r ằng vi ệc trao đổi thơng tin s ẽ di ễn ra t ại một th ời điểm c ụ th ể nào và c ũng khơng h ề quan tâm đến vi ệc th ời gian truy ền là nhanh hay ch ậm. Hay nĩi khác đi, trong các mơ hình truy ền thơng bên trên, th ời gian khơng h ề ảnh h ưởng t ới tính đúng đắn c ủa vi ệc truy ền tin. Với hình th ức truy ền thơng h ướng dịng ( Stream - Oriented Middleware ), th ời gian đĩng m ột vai trị c ự kì quan tr ọng. Ví d ụ, n ếu m ột đoạn âm thanh được phát l ại với t ần s ố khác v ới t ần s ố l ấy m ẫu c ủa đoạn âm thanh ban đầu, nĩ cĩ th ể cho ra k ết quả khácv ới đoạn âm thanh g ốc. T ươ ng t ự nh ư v ậy, n ếu chúng ta mu ốn xem m ột b ộ phim tr ực tuy ến trên m ạng, n ếu th ời gian truy ền c ủa d ữ li ệu là quá ch ậm, b ộ phim cĩ th ể b ị gián đoạn. Nh ư v ậy, hình th ức truy ền thơng này được cung cấp nh ằm t ạo điều ki ện thu ận l ợi cho vi ệc trao đổi các thơng tin ph ụ thu ộc vào th ời gian, t ức là, th ời gian s ẽ ảnh hưởng đến tính đúng đắn c ủa thơng tin được trao đổi. 2.2.5 Truy ền thơng đa điểm (MultiCast) Truy ền thơng đa điểm chính là kh ả n ăng g ửi d ữ li ệu t ừ m ột điểm t ới nhi ều điểm nh ận. V ới mơ hình này, chúng ta cĩ hai tr ường h ợp: - Từ m ột điểm truy ền đến nhi ều điểm: T ừ m ột điểm, chúng ta s ẽ truy ền đồng th ời đến m ột nhĩm các điểm th ỏa mãn m ột tiêu chí nào đĩ. - Từ m ột điểm truy ền đến t ất c ả các điểm: broadcast ( qu ảng bá ). T ừ m ột điểm, chúng ta sẽ truy ền đến t ất c ả các điểm cịn l ại cĩ kh ả n ăng ti ếp nh ận, điều này là rất cĩ ích và nĩ được th ực hi ện khá nhi ều trong b ối c ảnh h ệ phân tán. Ví d ụ, n ếu chúng ta cĩ m ột ti ến trình, n ếu ta mu ốn đư a ra m ột th ống nh ất, m ột chu trình
38 nào đĩ mà ph ải tham kh ảo tất c ả các ti ến trình cịn l ại. Trong tr ường h ợp này chúng ta s ẽ s ử d ụng broadcast. - Từ nhi ều điểm truy ền đến nhi ều điểm: bao g ồm tươ ng tác học t ập t ừ xa, ch ơi game nhi ều ng ười, h ội ngh ị đa ph ươ ng ti ện, chat nhĩm, ch ỉnh s ửa và chia s ẻ các cơng c ụ cộng tác, tính tốn song song, cũng nh ư phân ph ối mơ ph ỏng tươ ng tác. Sender Sender Receivers Hình 2.7 Mơ hình multicast many-to-many 2.3 Đồng b ộ hĩa ti ến trình 2.3.1 Đặt v ấn đề + Nhìn chung, các ti ến trình k ể các ti ến trình xu ất phát t ừ các ứng d ụng độc l ập mu ốn truy c ập vào các tài nguyên v ới s ố l ượng v ốn r ất h ạn ch ế hay truy c ập vào thơng tin dùng chung cùng m ột lúc. Tr ường h ợp này g ọi là truy c ập t ươ ng tranh. Vì v ậy, t ươ ng tranh là nguyên nhân chính c ủa các xung đột gi ữa các ti ến trình mu ốn truy c ập vào tài nguyên dùng chung đây là m ột trong nh ững nguyên nhân ph ải th ực hi ện c ơ ch ế đổng b ộ hố các ti ến trình. + Các ti ến trình c ủa cùng m ột h ệ ứng d ụng ho ạt động theo ki ểu h ợp l ực để gi ải quy ết các bài tốn đặt ra và cho k ết qu ả nhanh chĩng nh ất. Điều này cho phép tăng hi ệu n ăng s ử d ụng thi ết b ị và hi ệu qu ả ho ạt động c ủa ch ươ ng trình. Đây là m ột trong nh ững nguyên nhân ph ải th ực hi ện c ơ ch ế đồng b ộ hố các ti ến trình.
39 Điều này, được minh h ọa c ụ th ể qua bài tốn bãi để xe [2, tr 157], bài tốn ng ười s ản xu ất – ng ười tiêu th ụ [2, tr 162] và các v ấn đề khơng g ắn bĩ d ữ li ệu phát sinh khi v ận hành h ệ th ống, làm cho k ết qu ả b ị sai l ệch mà nguyên nhân chính đĩ là đồng h ồ th ời gian gi ữa các máy trong h ệ khơng đồng b ộ v ới nhau và độ tr ễ c ủa vi ệc truy ền tin c ũng khơng nh ất quán. Trong các h ệ th ống phân tán, vi ệc đồng b ộ hố ch ỉ đặt ra duy nh ất v ấn đề thi ết lập m ột tr ật t ự gi ữa các s ự ki ện. Gi ữa các tr ạm khác nhau, tr ật t ự đĩ ch ỉ cĩ th ể hi ện được thơng qua vi ệc trao đổi các thơng điệp v ới nhau. 2.3.2 Các giải pháp đồng b ộ ti ến trình 2.3.2.1 Đồng b ộ hĩa theo th ời gian v ật lý Trong h ệ phân tán, m ỗi b ộ x ử lý cĩ m ột b ộ định th ời riêng (m ột đồng h ồ riêng). Các b ộ định th ời trơi theo th ời gian th ực trong nh ịp khác nhau. Nh ịp trơi l ớn nh ất (MDR – Max Drift Rate) c ủa m ột đồng h ồ ph ụ thu ộc vào đặc tính c ủa đồng h ồ và mơi tr ường xung quanh. S ự khác nhau l ớn nh ất c ủa hai đồng h ồ v ới MDR t ươ ng t ự là: 2*MDR. Ci(t): là th ời gian đọc được t ừ ph ần m ềm đồng h ồ i khi th ời gian th ực là t. Đồng b ộ hĩa ngồi: Cho m ột gi ới h ạn đồng b ộ hĩa D>0, và ngu ồn S c ủa th ời gian UTC, | S(t) – C i(t) | 0, | C i(t) – C j(t) | < D v ới i, j=1, 2, ,n và v ới t ất c ả th ời gian th ực t trong I. Các đồng h ồ C i đồng ý trong ranh gi ới D.
40 • Gi ải thu ật NTP(Network Time Protocol): gi ải thu ật Cristian Gi ả s ử trong h ệ phân tán cĩ m ột máy cĩ WWV ( gọi là Time server ) và chúng ta s ẽ ti ến hành đồng b ộ các máy khác v ới máy này.Trong kho ảng th ời gian δ/2p m ỗi máy s ẽ g ửi m ột thơng điệp đến máy ch ủ h ỏi th ời gian hi ện t ại. Máy ch ủ nhanh s ẽ ph ản h ồi b ằng m ột thơng điệp mang giá tr ị th ời gian C(utc). Bên g ửi nh ận được ph ản h ồi nĩ s ẽ thi ết l ập l ại clock thành C(uct). Máy ch ủ ở tr ạng thái b ị động ( ch ờ h ỏi) Đánh giá: Giải thu ật này cĩ 2 v ấn đề - Một là n ếu clock bên g ửi ch ạy nhanh thì lúc này C(uct) s ẽ nh ỏ h ơn th ời gian hiên t ại C c ủa bên g ửi Cĩ th ể gi ải quy ết b ằng cách thay đổi nh ịp ng ắt l ại nhanh h ơn ho ặc ch ậm h ơn cho đến lúc kh ớp nhau. - Hai là s ự chênh l ệch t ừ lúc C(uct) được g ửi cho đến lúc nh ận được cĩ th ể gây l ỗi. Gi ải quy ết b ằng cách ghi nh ận kho ản th ời gian gi ữa lúc g ửi và nh ận • Gi ải thu ật Berkeley Nếu nh ư trong gi ải thu ật Cristian, server th ời gian đĩng vai trị b ị động, ch ỉ tr ả lời yêu c ầu c ủa client khi được h ỏi thì trong gi ải thu ật Berkeley, nĩ l ại đĩng vai trị ch ủ động: server th ời gian ( time deamon ) ch ủ động h ỏi th ời gian hi ện t ại trên các máy khác, tính tốn độ chênh l ệch so v ới th ời gian hi ện t ại trên server. Sau đĩ nĩ tính trung bình độ chênh l ệch v ề thời gian để điều ch ỉnh đồng h ồ trên máy mình, cũng nh ư g ửi đến các máy client yêu c ầu ch ỉnh nhanh ho ặc ch ậm đồng h ồ cho phù hợp v ới máy server. Ở đây, khơng c ần thi ết ph ải cĩ b ất k ỳ máy nh ận UTC ( Universal Coordinated Time: Gi ờ ph ối h ợp quốc t ế ) nào: th ời gian trên máy server được thi ết l ập b ằng các thao tác theo chu k ỳ. M ột điểm c ần l ưu ý khác là các máy trong h ệ th ống ch ỉ cĩ th ời gian gi ống nhau, ch ứ khơng nh ất thi ết đều ph ải cĩ th ời gian gi ống nh ư th ời gian trong th ực t ế.
41 1. Time deamon h ỏi các máy khác v ề giá tr ị đồng h ồ c ủa chúng 2. Các máy này tr ả l ời 3. Time deamon ch ỉ cho các máy bi ết cách ch ỉnh l ại đồng h ồ cho phù h ợp • Gi ải thu ật RBS (rate- based sequential) Gi ải thu ật này khơngyêu c ầu trên h ệ th ống cĩ node ch ứa th ời gian chu ẩn ( khi so sánh v ới th ời gian chu ẩn th ực t ế). Do đĩ, thay vì h ướng t ới đồng b ộ hĩa v ới th ời gian UTC, nĩ ch ỉ đồng b ộ trong n ội b ộ h ệ th ống, nh ư v ới gi ải thu ật Berkeley. M ặt khác, trong các gi ải thu ật tr ước đĩ, chúng ta c ố g ắng đồng b ộ hĩa c ả phía g ửi và phía nhận, nh ưng RBS ch ỉ để phía nh ận đồng b ộ hĩa. Cụ th ể h ơn, trong RBS, phía g ửi qu ảng bá m ột thơng điệp tham chi ếu, thơng điệp này cho phép phía nh ận cĩ th ể ch ỉnh đồng h ồ c ủa nĩ. M ột đặc điểm quan tr ọng, đĩ là trong m ạng sensor, th ời gian để lan truy ền tín hi ệu t ới các node khác gần nh ư là h ằng s ố, Th ời gian lan truy ền trong tr ường h ợp này được tính b ắt đầu khi thơng điệp r ời kh ỏi giao di ện m ạng ( network interface ) c ủa phía g ửi. Chính vì th ế, hai nguyên nhân chính gây ra chênh l ệnh th ời gian đã b ị lo ại b ỏ, đĩ là, kho ảng th ời gian t ạo ra thơng điệp và kho ảng th ời gian tiêu t ốn để cĩ th ể truy c ập vào m ạng (time spent to access the network ) 2.3.2.2 Đồng b ộ hĩa theo th ời gian logic • Khái ni ệm tem th ời gian: Định ngh ĩa quan h ệ “x ảy ra tr ước” happens – before. Kí hi ệu : a b Một quan h ệ được g ọi là “x ảy ra tr ước khi nĩ th ỏa mãn hai tình hu ống: 1. Nếu a và b là các s ự ki ện trong cùng m ột ti ến trình và a x ảy ra tr ước b thì quan h ệ a b là đúng.
42 2. Nếu a và b là hai s ự ki ện thu ộc hai ti ến trình khác nhau, trong đĩ a là m ột sự ki ện g ửi thơng điệp đi à b là s ựki ện nh ật thơng điệp đĩ thì quan h ệ ab là đúng. Quan h ệ a b cĩ tính ch ất b ắc c ầu, t ức là n ếu a b; b c thì a c. Trên c ơ s ở quan h ệ x ảy ra tr ước đĩ, chúng ta định ngh ĩa khái ni ệm tem th ời gian Với m ỗi s ự ki ện x, tem th ời gian c ủa x, kí hi ệu là C(x) được định ngh ĩa th ỏa mãn các điều ki ện sau: 1. Nếu a và b là hai s ự ki ện x ảy ra trong cùng m ột ti ến trình và a b thì C(a) < C(b) 2. Nếu a là s ự ki ện g ửi m ột thơng điệp c ủa m ột ti ến trình nào đĩ, b là s ự ki ện nh ận thơng điệp đĩ c ủa ti ến trình khác thì C(a) < C(b) Chú ý: Quan h ệ này m ới ch ỉ là m ột chi ều, t ức là n ếu a b thì C(a) < C(b) nh ưng điều ng ược l ại ch ưa ch ắc đãđúng, t ức là n ếu C(a) < C(b) thì ch ưa ch ắc chúng ta cĩ a b • Khái ni ệm tem th ời gian vector Trong khái ni ệm v ề tem th ời gian, n ếu s ự ki ện a x ảy ra tr ước s ự ki ện b thì C(a) < C(b). Tuy nhiên, chúng ta khơng th ể nĩi tr ước điều gì v ề quan h ệ gi ữa a và b n ếu ch ỉ bi ết C(a) < C(b), hay nĩi cách khác, n ếu C(a) < C(b), chúng ta s ẽ khơng th ể nĩi rằng a x ảy ra tr ước b. Nh ư v ậy, v ấn đề ở đây là khái ni ệm v ề tem th ời gian khơng cĩ tính ch ất nhân qu ả ( causality ). Do đĩ, khái ni ệm tem th ời gian vector ( vector clock ) đã được đư a ra. Với khái ni ệm này, m ột vector th ời gian VC(a) được gán cho m ột s ự ki ện a cĩ tính ch ất sao cho n ếu VC(a) <VC(b) thì s ự ki ện a s ẽ x ảy ra tr ước s ự ki ện b.
43 • Gi ải pháp tr ật t ự t ừng ph ần Gi ả s ử r ằng ta cĩ th ể xác định m ột tr ật t ự gi ữa các s ự ki ện c ủa h ệ phân tán nh ờ vào quan h ệ được ký hi ệu là → và g ọi là “cĩ tr ước” hay “ ở ngay tr ước”. Quan h ệ này t ối thi ếu ph ải thỗ mãn được ràng bu ộc th ể hi ện trong b ảng sau đây : C1 : N ếu A và B là hai s ự ki ện c ủa cùng m ột tr ạm và n ếu A được th ực hi ện tr ước B thì theo tr ật t ự c ục b ộ c ủa tr ạm ta cĩ A → B. C 2 : N ếu A là phát thơng điệp b ởi m ột tr ạm nào đĩ và n ếu B là thu c ủa thơng điệp này thì ta cĩ A → B. Hình 2.8 sau đây cho ta ví d ụ v ề tr ật t ự hĩa t ừng ph ần c ủa các s ự ki ện trong h ệ th ống. Theo hình v ẽ ta cĩ th ể bi ểu tr ật t ự t ừng ph ần nh ư sau: - Tr ật t ự của các s ự ki ện A1 A2 A3 A4 A5 B1 B2 B3 B4 - Trao đổi thơng điệp A1 B2; B3 A4 - Chuy ển qua A1 A2 B2 B3 B4 B1 B2 B3 A4 A5 A1 A2 B2 B3 A4 A5
44 A1 B1 A2 B2 A3 B3 A4 B4 A5 B5 Hình 2.8 Mơ hình tr ật t ự t ừng ph ần • Thu ật tốn Lamport - đồng b ộ hĩa đồng h ồ logic: Các ký hi ệu: Một ch ươ ng trình phân tán được t ạo thành b ởi t ập h ợp n ti ến trình độc l ập và khơng đồng b ộ P1, P2, ,Pn. Các ti ến trình này khơng chia x ẻ m ột đồng h ồ chung. Mỗi ti ến trình cĩ th ể x ử lý m ột s ự ki ện t ự động; khi g ửi m ột thơng điệp, nĩ khơng ph ải đợi vi ệc phân phát hồn thành. 0 1 x Vi ệc x ử lý c ủa m ỗi ti ến trình Pi, s ản sinh ra m ột dãy s ự ki ện e i , e i , , e i , x+1 ei , Tập h ợp các s ự ki ện được s ản sinh ra b ỡi Pi cĩ m ột t ổng th ứ t ự được xác định x x+1 bởi dãy các s ự ki ện e i e i x x+1 Chúng ta nĩi r ằng e i xảy ra tr ước e i i j Quan h ệ x ảy ra tr ước cĩ tính b ắc c ầu: e i e i v ới m ọi i<j. Các s ự ki ện x ảy ra gi ữa hai ti ến trình đồng th ời nĩi chung khơng quan h ệ, ngo ại tr ừ hai ti ến trình đĩ cĩ liên quan theo quan h ệ nh ư sau: x Đối v ới m ỗi thơng điệp m trao đỗi gi ữa hai ti ến trình Pi và Pj, chúng ta cĩ e i = y x y send(m), e j = receive(m) và e i e j .
45 Các s ự ki ện trong m ột s ự x ử lý phân tán là được s ắp x ếp riêng bi ệt. - Các s ự ki ện c ục b ộ là t ổng th ể được s ắp đặt. - Các s ự ki ện nguyên nhân là t ổng th ể được s ắp đặt. - Tất c ả các s ự ki ện khác là khơng được s ắp đặt. Cho b ất k ỳ hai s ự ki ện e 1 và e 2 trong m ột s ự x ử lý phân tán, cĩ th ể là: (i) e1 e 2 (ii) e2 e 1 (iii) e1 || e 2 (e 1 và e 2 là đồng th ời). Ví d ụ: Nh ững s ự ki ện nào là quan h ệ ? Nh ững s ự ki ện nào là đồng th ời ? Hình 2. 9 Th ứ t ự các s ự ki ện t ại c ủa các ti ến trình t ại các tr ạm phát nh ận 1. Nh ững điều ki ện đồng h ồ: Trong m ột h ệ th ống các đồng h ồ logic, các ti ến trình riêng bi ệt cĩ m ột đồng h ồ logic mà được áp d ụng theo m ột giao th ức. Mỗi s ự ki ện được gán m ột timestamp (th ời gian đánh d ấu) trong cách th ức mà thõa mãn điều ki ện b ền ch ặt đồng h ồ: n ếu e 1 e 2 thì C(e 1) < C(e 2). Trong đĩ: C(e i) là timestamp (th ời gian đánh d ấu) được gán cho s ự ki ện e i.
46 Nếu giao th ức thõa mãn các điều ki ện theo sau n ữa, thì đồng h ồ được nĩi r ằng bền ch ặt m ạnh: n ếu C(e 1) 0, th ường d=1) R3 : M ỗi thơng điệp mang giá tr ị đồng h ồ c ủa ng ười g ửi nĩ t ại th ời điểm g ửi. Khi Pi nh ận m ột thơng điệp v ới timestamp (th ời gian đánh d ấu) C msg , nĩ x ử lý nh ư sau: 1.Ci = Max(C i, C msg ) 2.X ử lý R2. 3.Phát thơng điệp. Đồng h ồ logic t ại b ất k ỳ ti ến trình nào là ngày càng t ăng đơ n gi ản. Hình 2. 10 Các th ời gian đánh d ấu Lamport (Lamport timestamps)
47 Th ời gian v ật lý 2 8 Tr ạm 1 0 1 7 1 Tr ạm 2 0 2 3 Tr ạm 3 4 9 10 0 3 5 Tr ạm 4 6 7 0 5 Các s ự ki ện logic đồng th ời n Giá tr ị đồng h ồ. timestamp Thơng điệp Hình 2. 11 Ví d ụ th ời gian logic Lamport 2.3.3 Kết lu ận Trong h ệ th ống phân tán, th ời gian truy ền thơng tin c ủa các thơng điệp là khơng cố định, bên c ạnh đĩ s ố l ượng c ủa các tr ạm ra quy ết định l ớn, điều này d ẫn đến h ệ th ống phân tán cĩ th ể b ị s ự c ố b ất c ứ lúc nào. Các bi ện pháp đồng b ộ hĩa các ti ến trình, mà c ốt lõi là đồng b ộ th ời gian x ử lý của các ti ến trình trong h ệ giúp các ti ến trình được x ử lý theo tr ật t ự c ố định. Đây là điều ki ện giúp h ệ th ống t ồn t ại và cĩ th ể đư a vào s ử d ụng được.
48 CH ƯƠ NG 3: ỨNG D ỤNG H Ệ PHÂN TÁN TỐI ƯU TH ỜI GIAN XỬ LÝ CHO MÁY TÌM KI ẾM 3.1 Phân tích máy tìm ki ếm trên h ệ t ập trung 3.1.1 Phân tích ho ạt động c ủa máy tìm ki ếm trên h ệ t ập trung Máy tìm ki ếm ho ạt động d ựa trên 3 b ộ ph ận chính đĩ là b ộ Crawler, b ộ index và b ộ Search engine ( xem m ục 1.2 ). - Bộ Crawler cĩ nhi ệm v ụ nh ư m ột robot t ự động tìm thơng tin trên internet và l ưu tr ữ v ề máy theo m ột c ấu trúc nh ất định ( thơng tin thơ ). - Bộ Index cĩ nhi ệm v ụ l ập ch ỉ m ục các file thơng tin c ủa b ộ Crawler tải về thành h ệ th ống file index ( thơng tin tinh l ọc) và t ập trung t ại m ột kho d ữ li ệu ( dữ li ệu index file ). - Bộ Search engine cĩ nhi ệm v ụ truy v ấn dữ li ệu trong kho d ữ li ệu index file, s ắp x ếp k ết qu ả và tr ả k ết qu ả cho ng ười dùng. 3.1.2 Một s ố h ạn ch ế c ủa máy tìm ki ếm trên h ệ t ập trung Theo nh ư mơ hình trình bày t ại m ục 1.2 và theo phân tích ho ạt động của máy tìm ki ếm trình bày ở trên thì tất c ả các x ử lý c ủa hệ th ống máy tìm ki ếm được t ập trung t ại 1 server, do đĩ khi hệ th ống vận hành s ẽ phát sinh các h ạn ch ế sau: 1. Dung l ượng c ủa h ệ th ống file index quá kh ổng l ồ. Trên th ế gi ới hi ện t ại ước tính kho ảng 200 tri ệu tên mi ền được đă ng ký và m ỗi n ăm t ăng thêm 19%. Mỗi tên ni ềm trung bình cĩ kho ảng 800 liên k ết ch ứa d ữ li ệu. Nh ư v ậy s ố thơng tin c ần l ưu tr ữ c ủa quá l ớn khơng th ể tri ển khai trên server đơ n được. 2. Số l ượng ng ười truy c ập t ập trung t ại m ột server quá l ớn. 3. Số l ượng thơng tin x ử lý quá l ớn. 4. Băng thơng đường truy ền quá t ải. Máy tìm ki ếm khơng th ể tri ển khai được trên h ệ t ập trung.
49 3.1.3 Các y ếu t ố ảnh h ưởng đến th ời gian x ử lý c ủa máy tìm ki ếm Ta xét quá trình th ực hi ện và x ử lý c ủa h ệ th ống t ừ khi yêu c ầu ng ười dùng được g ởi đi đến khi ng ười dùng nh ận được k ết qu ả ( hình 3.1 ) g ồm các cơng đoạn nh ư sau: i. Máy cá nhân ng ười dùng ( máy local ) x ử lý ii. Chuy ển thơng tin yêu c ầu ng ười dùng đến h ệ th ống iii. Hệ th ống x ử lý yêu c ầu ng ười dùng iv. Hệ th ống chuy ển k ết qu ả đếm máy local c ủa ng ười dùng v. Máy local c ủa ng ười dùng x ử lý và hi ển th ị k ết qu ả Nh ư v ậy ta t ạm chia th ời gian x ử lý c ủa quá trình thành hai ph ần chính: T ổng th ời gian x ử lý, truy ền thơng c ủa các cơng đoạn n ằm ngồi h ệ th ống (T nht ) và t ổng th ời gian xử lý, truy ền thơng c ủa các cơng đoạn nằm trong h ệ th ống (T tht ). Ta cĩ cơng th ức nh ư sau: T= Tnht + Ttht Các cơng đoạn x ử lý nằm ngồi h ệ th ống chúng ta khơng th ể can thi ệp ho ặc cải thi ệp, do đĩ ta khơng xét. Nh ư v ậy để t ối ưu th ời gian x ử lý c ủa máy tìm ki ếm chính là t ối ưu th ời gian x ử lý T tht Các y ếu t ố ảnh h ưởng đến th ời gian x ử lý T tht - Th ời gian truy ền thơng điệp: Ph ụ thu ộc s ố l ượng, dung l ượng gĩi tin và băng thơng, kho ảng cách đường truy ền. - Th ời gian xử lý thơng tin: + C ấu hình máy server + S ố l ượng thơng tin c ần x ử lý + Dung l ượng và c ấu trúc kho d ữ li ệu + Độ ph ức t ạp thu ật tốn
50 query Search Query results Engine parser results search Ranking Index file Hình 3. 1 Mơ hình ho ạt động c ủa pha x ử lý yêu c ầu ng ười dùng Nh ư v ậy, để t ối ưu th ời gian x ử lý thơng tin c ủa máy tìm ki ếm chúng ta th ực hi ện t ối ưu sáu tiêu chí sau: Bảng 3.1. B ảng tiêu chí t ối ưu máy tìm ki ếm STT Tiêu chí t ối ưu 1 Số l ượng và dung l ượng gĩi tin c ần truy ền 2 Băng thơng và kho ảng cách đường truy ền 3 Cấu hình server 4 Số l ượng thơng tin c ần x ử lý 5 Dung l ượng và c ấu trúc kho d ữ li ệu 6 Độ ph ức t ạp thu ật tốn 3.1.4 Hướng gi ải quy ết v ấn đề 3.1.4.1 Đặt v ấn đề Theo định ngh ĩa và các tính ch ất c ủa h ệ phân tán ( Trình bày t ại ch ươ ng 2 ), h ệ phân tán g ồm nhi ều server kết n ối v ới nhau thơng qua đường truy ền vi ễn thơng. Ưu điểm l ớn nh ất c ủa h ệ phân tán đa server đĩ là ta cĩ th ể chia s ẽ tài nguyên gi ữa các tr ạm và t ăng kh ả n ăng x ử lý đồng th ời. Điều này s ẽ làm gi ảm th ời gian x ử lý thơng tin rất nhi ều.
51 Gi ả s ử ta chia máy tìm ki ếm ra thành nhi ều máy tìm ki ếm nh ỏ đặt t ại các server trong h ệ th ống phân tán. Kho d ữ li ệu index file cũng được chia nh ỏ và phân tán t ại các tr ạm. Khi m ột yêu c ầu ng ười dùng được chuy ển t ới, h ệ th ống s ẽ thơng báo cho tất c ả các tr ạm th ực hi ện truy v ấn vào kho index file riêng c ủa mình và g ửi k ết qu ả lại cho h ệ th ống, h ệ th ống s ẽ t ổng h ợp, s ắp x ếp k ết qu ả và chuy ển cho ng ười dùng. Beging Send request SE (1) SE (2) SE (n) Ranking Display result End Hình 3. 2 Các b ước ho ạt động c ủa máy tìm ki ếm ứng d ụng h ệ phân tán 3.1.4.2 Kết lu ận Nh ư v ậy, th ời gian x ử lý c ủa h ệ th ống s ẽ t ỉ l ệ ngh ịch v ới s ố l ượng các tr ạm trong h ệ th ống, s ố l ượng các tr ạm càng t ăng thì th ời gian x ử lý càng gi ảm. Ứng dụng h ệ phân tán đa server vào máy tìm ki ếm ta cĩ th ể gi ải quy ết được các v ấn đề sau:
52 i. Kho d ữ li ệu index file được phân tán t ại t ất c ả các tr ạm trong h ệ dung lượng kho d ữ li ệu index file t ại m ỗi tr ạm gi ảm xu ống t ươ ng ứng v ới s ố lượng tr ạm trong h ệ. ii. Tất c ả các tr ạm đồng th ời cùng tham gia vào vi ệc x ử lý thơng tin T ăng cấu hình c ủa h ệ th ống lên t ươ ng ứng v ới s ố l ượng tr ạm trong h ệ. iii. Tăng b ăng thơng, t ối ưu kho ảng cách đường truy ền c ủa h ệ th ống iv. Gi ảm s ố l ượng và dung l ượng gĩi tin c ần truy ền t ại m ỗi tr ạm. Nh ư v ậy ứng d ụng h ệ phân tán đa server s ẽ gi ảm th ời gian x ử lý c ủa máy tìm ki ếm m ột cách đáng k ể. 3.2 Đề xu ất ph ươ ng th ức ho ạt động c ủa máy tìm ki ếm trên h ệ phân tán 3.2.1 Ph ươ ng th ức ho ạt động t ổng th ể c ủa h ệ th ống Front-end query Search Query results Engine parser search Back-end Ranking Hệ phân tán request Crawler Indexer www Web pages Web pages Hình 3.3 Mơ hình ho ạt động tổng th ể máy tìm ki ếm ứng d ụng h ệ phân tán
53 Trên h ệ th ống t ập trung, m ọi x ử lý c ủa máy tìm ki ếm được t ập trung th ực hi ện tại m ột server, do đĩ th ời gian x ử lý yêu c ầu ng ười dùng quá l ớn, th ậm chí quá t ải khơng th ực hi ện được m ọi ho ạt động. Do v ậy, chúng ta ph ải th ực hi ện phân tán máy tìm ki ếm ra thành nhi ều máy tìm ki ếm nh ỏ và các máy tìm ki ếm nh ỏ này ho ạt động nh ư m ột máy tìm ki ếm th ực th ụ v ới đầy đủ các ch ức n ăng. Trong h ệ th ống t ập trung, m ọi quá trình x ử lý được th ực hi ện t ại m ột server. Trong h ệ th ống ứng d ụng phân tán, quá trình x ử lý được chia nh ỏ và được th ực hi ện xử lý đồng th ời t ại nhi ều server khác nhau và k ết qu ả được t ập h ợp t ừ các tr ạm trong h ệ th ống. Xử lý yêu c ầu ng ười dùng: Khi m ột yêu c ầu ( request ) c ủa ng ười dùng g ửi t ới hệ th ống, hệ th ống s ẽ ti ếp nh ận yêu c ầu và d ựa trên m ột s ố tiêu chí (các tiêu chí s ẽ được trình bày ở ph ần sau ) nĩ ủy quy ền cho m ột tr ạm c ụ th ể ch ịu trách nhi ệm x ử lý chính. Tr ạm được ủy quy ền này s ẽ g ởi yêu c ầu đến các trạm khác trong h ệ. Tại m ỗi tr ạm s ẽ x ử lý riêng bi ệt và g ởi k ết qu ả l ại cho tr ạm được ủy quy ền. Tr ạm này cĩ nhi ệm v ụ t ập h ợp k ết qu ả, s ắp x ếp theo th ứ t ự gi ảm d ần c ủa độ chính xác v ới t ừ khĩa ng ười dùng và hi ển th ị k ết qu ả cho ng ười s ử d ụng. Thu th ập thơng tin: Tất c ả các tr ạm x ử lý trong h ệ th ống đều gi ống nhau. T ại mỗi tr ạm đều cĩ b ộ crawler và b ộ indexer riêng bi ệt, m ỗi tr ạm t ự động l ấy thơng tin và l ập ch ỉ m ục, l ưu tr ữ h ệ th ống index file riêng và luơn đảm b ảo s ự duy nh ất c ủa thơng tin trong h ệ th ống. 3.2.2 Ph ươ ng th ức liên k ết các tr ạm trong h ệ th ống Hệ th ống g ồm n server tr ạm tươ ng t ự nhau, chúng liên k ết v ới nhau qua đường truy ền vi ễn thơng và giao ti ếp v ới nhau b ằng thơng điệp. Mỗi server là m ột máy tìm ki ếm và cĩ kh ả n ăng liên k ết v ới t ất c ả các server cịn l ại trong h ệ th ống.
54 Server n Server 3 Server 2 Server 1 Hình 3. 4 Mơ hình liên k ết các tr ạm trong h ệ th ống Mỗi server cĩ m ột h ệ th ống thu th ập thơng tin và kho d ữ li ệu index file riêng. Dữ li ệu c ủa kho index file t ại m ỗi server là duy nh ất. Khi m ột server trong h ệ th ống nh ận được thơng điệp yêu c ầu truy xu ất d ữ li ệu, nĩ s ẽ thơng báo cho các server cịn l ại. Và quá trình x ử lý s ẽ được chia nh ỏ t ại t ất c ả các server trong h ệ. Các tr ạm trong h ệ th ống là m ột máy tìm ki ếm, chúng c ũng cĩ đầy đủ 4 b ộ ph ận chính nh ư m ột máy tìm ki ếm thơng th ường ( hình 3.3 ), chúng ho ạt động độc l ập v ới nhau. 3.2.3 Ph ươ ng th ức ho ạt động t ại các tr ạm c ủa h ệ th ống query Server x Search Query results Engine parser search Index file request Crawler Indexer www Web pages Web pages Hình 3. 5 Mơ hình ho ạt động c ủa tr ạm các tr ạm con trong h ệ th ống
55 Nh ư đã trình bày t ại m ục 3.1.2.3, tại m ỗi tr ạm là m ột máy tìm ki ếm thơng th ường, chúng t ự động tìm thơng tin trên internet, t ự động l ập ch ỉ m ục và l ưu tr ữ vào h ệ th ống index file. Khi server x ( server được quy ền x ử lý chính ) g ửi thơng điệp request t ới các tr ạm yêu c ầu truy xu ất thơng tin, bộ query parser tại các tr ạm phân tích câu truy v ấn và truy xu ất t ới n ơi ch ứa thơng tin c ần tìm. Bộ ph ận crawler ho ạt động h ơi khác so v ới b ộ ph ận crawler c ủa máy tìm ki ếm trên h ệ t ập trung. Do m ỗi tr ạm cĩ m ột b ộ crawler ho ạt động độc l ập, điều này d ẫn đến s ự trùng l ặp thơng tin gi ữa các tr ạm. Để tránh tr ường h ợp các crawler c ủa các tr ạm t ải thơng tin trùng nhau, sau khi truy xu ất các URL trong n ội dung trang web, crawler ngồi vi ệc ki ểm tra các URL đĩ đã crawl ch ưa cịn ph ải g ởi thơng điệp nh ờ tất c ả các tr ạm khác trong h ệ th ống ki ểm tra xem URL đĩ đã cĩ tr ạm mào ki ểm tra hay ch ưa, n ếu cĩ b ất k ỳ tr ạm nào crawl r ồi thì crawler s ẽ lo ại b ỏ URL đĩ ra khơng xử lý.
56 Begin Đư a liên k ết g ốc vào hàng đợi Số liên k ết > 0 sai End đúng Lấy URL trong hàng đợi sai Ki ểm tra định dạng URL đúng Đọc n ội dung trang web, đư a URL vào danh sách đã duy ệt khơng Ki ểm tra n ội dung cĩ Truy xu ất URL Rồi ki ểm tra URL Đư a vào hàng đợi đã crawl ch ưa ch ưa ch ưa Gởi thơng điệp ki ểm tra URL đã Kết qu ả ki ểm crawl ch ưa tra t ại các tr ạm Rồi Hình 3. 6 Thu ật tốn x ử lý c ủa crawler
57 3.2.4 Ph ươ ng th ức l ưu tr ữ file index c ủa h ệ th ống video pic Webs files Server i Hình 3. 7 Mơ hình l ưu tr ữ h ệ th ống files index t ại m ỗi tr ạm Tại m ỗi tr ạm h ệ th ống files index được l ưu tr ữ theo mơ hình nh ư đã trình bày tại m ục 1.6, đồng th ời hệ th ống file index được phân lo ại theo nhi ều lo ại d ữ li ệu khác nhau nh ư webs, videos, files, picture Và t ại các lo ại d ữ li ệu ta ti ếp t ục phân lo ại theo các ch ủ đề khác nhau để ti ện cho vi ệc truy xu ất và tìm ki ếm thơng tin theo từng lo ại d ữ li ệu. Mục đích c ủa vi ệc chia nh ỏ thơng tin thành t ừng lo ại d ữ li ệu và t ừng ch ủ đề c ụ th ể giúp vi ệc truy v ấn d ữ li ệu được chính xác và nhanh chĩng h ơn. Ví d ụ, t ại kho d ữ li ệu webs ta cĩ th ể chia ra thành các ch ủ để nh ư giáo d ục, văn hĩa, xã h ội, kinh t ế, chính tr ị T ại các ch ủ đề này ta cĩ th ể ti ếp t ục chia nh ỏ thành các ch ủ đề con nh ư b ộ giáo d ục, m ầm non, ti ểu h ọc, trung h ọc, đại h ọc, cao đẳng và c ứ th ế chia nh ỏ theo mơ hình cây quan h ệ. Các nút lá c ủa cây quan h ệ là các segments ch ứa thơng tin tinh l ọc c ủa b ộ indexer trích l ọc được t ừ thơng tin thơ c ủa b ộ crawler t ải v ề. Mỗi segments là m ột hệ th ống các t ừ v ựng và các mã c ủa url ch ứa t ừ v ựng đĩ. URL g ồm cĩ hai lo ại url trên web và url trên máy local. Url trên máy local là địa ch ỉ các file ch ứa các t ừ vựng đĩ. M ục đích c ủa url trên máy local giúp cho ng ười dùng truy xu ất được thơng tin c ủa các url trên web đã b ị ng ưng k ết n ối vì lý do gì đĩ.
58 Index files Data type 1 Data type 2 Data type n Topic 1 Topic 2 Topic n Topic 11 Topic 12 Topic 1n segment segment segment Hình 3. 8 H ệ th ống index file theo mơ hình cây Dựa vào cách l ưu tr ữ này, b ộ query parser s ẽ phân tích thơng tin ng ười dùng và th ực hi ện truy v ấn tr ực ti ếp và các segment cĩ liên quan. Do v ậy, k ết qu ả tìm ki ếm chính xác và nhanh chĩng h ơn. 3.3 Các v ấn đề phát sinh và cách gi ải quy ết 3.3.1 Ch ọn l ựa server x ử lý chính 3.3.1.1 Đặt v ấn đề Hệ th ống g ồm nhi ều server t ươ ng t ự nhau, cĩ ch ức n ăng giống nhau, t ại m ỗi th ời điểm m ỗi server cĩ độ “r ỗi” khác nhau. Khi m ột yêu c ầu ng ười dùng được g ởi đến h ệ th ống, h ệ th ống s ẽ l ựa ch ọn server nào t ối ưu nh ất để giao quy ền x ử lý chính nh ằm t ối ưu th ời gian x ử lý cho máy tìm ki ếm là v ấn đề c ần thi ết. Độ “r ỗi” c ủa server t ại m ột th ời điểm được định ngh ĩa d ựa trên th ời gian x ử lý một đơ n v ị thơng tin c ủa server t ại th ời điểm đĩ. M ột server A cĩ độ r ỗi cao h ơn server B, điều này cĩ ngh ĩa server A cĩ tốc độ x ử lý trên m ột đơ n v ị thơng tin cao hơn tốc độ x ử lý trên m ột đơ n v ị thơng tin c ủa server B.
59 3.3.1.2 Gi ải quy ết v ấn đề Căn c ứ b ảng tiêu chí t ối ưu (xem t ại m ục 3.2.1 ), g ồm cĩ sáu tiêu chí để t ối ưu th ời gian x ử lý cho máy tìm ki ếm. Trong h ệ th ống, các server được cài đặt chung một ch ươ ng trình x ử lý gi ống nhau, do đĩ độ ph ức t ạp c ủa thu ật tốn c ủa các server là nh ư nhau. T ổng quá lên ta cĩ hai tiêu chí chính để ch ọn m ột server t ối ưu t ại m ột th ời điểm T là th ời gian x ử lý m ột đơ n v ị thơng tin c ủa server đĩ và th ời gian truy ền một đơ n v ị thơng tin t ừ server đĩ đến client t ại th ời điểm T . Nh ư v ậy, để ch ọn server t ối ưu ta d ựa vào hai tiêu chí chính đĩ là: Bảng 3.2. B ảng tiêu chí ch ọn server t ối ưu STT Tiêu chí ĐV tính 1 Th ời gian x ử lý m ột đơ n v ị thơng tin ms 2 Th ời gian truy ền m ột đơ n v ị thơng tin t ừ server đến client ms Gi ả s ử h ệ th ống g ồm b ốn server k ết n ối v ới nhau. Ta xét trong kho ảng th ời gian t, gi ả s ử thơng s ố c ủa các y ếu t ố ảnh h ưởng đến th ời gian x ử lý t ại các tr ạm nh ư sau. Bảng 3.3. B ảng phân tích độ r ỗi khác nhau c ủa các server trong h ệ Server Th ời gian x ử lý Th ời gian truy ền thơng tin Tổng thời xử lý 1 0,005 ms 0,02 ms 0.025 ms 2 0,003 ms 0,05 ms 0.053 ms 3 0,004 ms 0,1 ms 0.104 ms 4 0,0025 ms 0,015 ms 0.0175 ms Dựa vào tổng th ời gian x ử lý c ủa t ừng server ta cĩ th ể xác định được server t ối ưu ( server cĩ t ổng th ời gian x ử lý nh ỏ nh ất) để giao quy ền x ử lý chính.
60 Các y ếu t ố ảnh h ưởng đến th ời gian x ử lý c ủa m ột server: - Tốc độ x ử lý c ủa CPU. - Dung l ượng b ộ nh ớ t ạm RAM và Bus c ủa RAM. - Tốc độ quay và ch ất l ượng c ủa đĩa c ứng. - FSB ( Front Side Bus ) c ủa Main (xa l ộ truy ền d ữ li ệu). Các y ếu t ố ảnh h ưởng đến th ời gian truy ền thơng tin: - Tốc độ đường truy ền. - Kho ảng cách điểm ngu ồn và điểm đích. - Tốc độ các thi ết b ị trung gian. Tr ước khi submit câu truy v ấn c ủa ng ười dùng đến h ệ th ống, client g ởi m ột thơng điệp đến t ất c ả các tr ạm yêu c ầu các tr ạm tr ả l ời tổng th ời gian x ử lý (T) c ủa mình. Sau khi nh ận được th ời gian T c ủa t ất c ả các tr ạm, client th ực hi ện ch ọn server cĩ T nh ỏ nh ất làm server x ử lý chính và g ởi câu truy v ấn c ủa ng ười đến server đĩ yêu c ầu x ử lý. Hình 3. 9. S ơ đồ ch ọn server t ối ưu
61 3.3.2 Vấn đề đồng b ộ các ti ến trình 3.3.2.1 Đặt v ấn đề Gi ả thi ết: - Gi ả s ử h ệ th ống g ồm cĩ 2 server tr ạm được liên k ết v ới nhau thơng qua đường truy ền vi ễn thơng và giao ti ếp v ới nhau b ằng h ệ th ống thơng điệp. Các tr ạm cùng ti ến hành cơng vi ệc thu th ập thơng tin. - Gi ả s ử h ệ th ống th ực hi ện giao ti ếp v ới nhau bằng 2 lo ại thơng điệp: check(a) dùng để ki ểm tra URL a cĩ crawl ch ưa và result(a) dùng tr ả k ết qu ả ki ểm tra của URL a. Tr ạm 1 Tr ạm 2 T1 check(a) Thơng điệp yêu T2 cầu ki ểm tra T3 check(a) Thơng điệp tr ả T4 lời k ết qu ả result(a) T5 Xử lý T6 Ghi d ữ li ệu result(a) T7 T8 T9 Hình 3. 10 Mơ hình khơng đồng b ộ của hai ti ến trình gi ữa hai tr ạm - Gi ả s ử t ại th ời điểm t 1 tr ạm 2 g ửi m ột thơng điệp yêu c ầu tr ạm 1 ki ểm tra url a đã được tr ạm 1 crawl ch ưa và đến th ời điểm t 3 tr ạm 1 m ới nh ận được thơng điệp. Trong khi đĩ t ại th ời điểm t 2 tr ạm 1 cũng g ửi thơng điệp yêu c ầu tr ạm 2 ki ểm tra url a và đến th ời điểm t 5 tr ạm 2 m ới nh ận được thơng điệp. Trong kho ảng th ời gian t 3 đến t 4, t ại tr ạm 1 url a ch ưa cĩ trong c ơ s ở d ữ li ệu, do đĩ k ết qu ả result(a) = NO và được g ửi qua tr ạm 2. T ại th ời điểm t 5, t 6 tr ạm 2 ch ưa nh ận được k ết qu ả t ừ
62 tr ạm 1 g ửi đến, do đĩ url a c ũng ch ưa được ghi vào c ơ s ở d ữ li ệu c ủa tr ạm 2 và k ết qu ả result(a) =NO. Điều này d ẫn t ới 2 tr ạm đều ghi url a vào c ơ s ở d ữ li ệu c ủa mình. Kết lu ận: Dữ li ệu t ại các tr ạm s ẽ b ị trùng, khơng nh ất quán. Điều này, d ẫn t ới dữ li ệu b ị d ư th ừa. Nguyên nhân c ủa điều này chính là s ự khơng đồng b ộ gi ữa các ti ến trình c ủa các tr ạm. 3.3.2.2 Gi ải quy ết v ấn đề Ph ươ ng pháp đồng b ộ hĩa ti ến trình Vấn đề được đề c ập bên trên t ươ ng t ự nh ư bài tốn bãi để xe [2, tr 157] và bài tốn ng ười s ản xu ất – ng ười tiêu th ụ [2, tr 162]. Vi ệc khơng đồng b ộ gi ữa các ti ến trình tại các tr ạm trong h ệ th ống d ẫn đến các v ấn đề sai l ệch k ết qu ả trong quá trình vận hành, mà nguyên nhân chính đĩ là th ứ t ự th ực hi ện c ủa các ti ến trình khơng đồng b ộ do độ tr ễ c ủa các thơng điệp ( trình bày t ại m ục 2.3.2 ). Gi ải quy ết v ấn đề này chính là gi ải quy ết đồng b ộ hĩa ti ến trình (trình bày t ại mục 2.3.2 ). Trong n ội dung thơng điệp ta đính kèm thêm nhãn th ời gian logic, địa ch ỉ ngu ồn c ủa thơng điệp và d ựa vào đồng h ồ logic này ta xác định thơng điệp c ủa tr ạm nào được ưu tiên x ử lý. Thơng điệp nào cĩ đồng h ồ logic nh ỏ h ơn thì thơng điệp đĩ được ưu tiên x ử lý, thơng điệp cịn l ại b ị h ủy. Thu ật tốn được th ực hi ện như sau: Gán đồng h ồ logic T i = 0 cho t ất c ả các tr ạm Khi m ột tr ạm th ực hi ện g ởi thơng điệp, tr ạm đĩ t ự động t ăng đồng h ồ logic c ủa mình lên m ột đơ n v ị T i=T i + 1 r ồi g ắn số hi ệu đồng hồ logic C i c ủa mình vào n ội dung thơng điệp và g ởi cho tr ạm đích.
63 Khi nh ận được m ột thơng điệp, tr ạm c ập nh ật s ố hi ệu đồng h ồ logic b ằng cách lấy giá tr ị l ớn nh ất c ủa s ố hi ệu đồng h ồ logic tr ạm g ởi và s ố hi ệu đồng h ồ logic c ủa mình T i=max(T i , C k). Khi tr ạm nh ận được đầy đủ thơng điệp tr ả l ời c ủa các tr ạm, ngay l ập t ức tr ạm so sánh đồng h ồ logic c ủa mình v ới các tr ạm khác, n ếu nh ỏ h ơn thì tr ạm th ực hi ện x ử lý ti ếp và g ởi thơng báo cho các tr ạm cịn l ại h ủy vi ệc x ử lý. Tr ạm 1 Tr ạm 2 Tr ạm 3 T1 (c,3,1,a) (c,3,1,a) T2 T (c,1,1,a) (c,1,1,a) 3 T4 T5 (r,2,2,a) (r,3,2,a) T6 (r,1,3,a) T7 (r,2,4,a) T8 T9 Hình 3. 11.Kết qu ả sau khi đồng b ộ ti ến trình theo thu ật tốn lamport Nh ược điểm c ủa ph ươ ng pháp này là l ượng thơng điệp c ần g ởi đi x ử lý t ăng lên rất nhi ều, m ỗi l ần ki ểm tra h ệ th ống ph ải g ởi l ượng thơng điệp là (n-1)*2 trong đĩ n là s ố tr ạm trong h ệ th ống, do đĩ ảnh h ưởng nhi ều đến th ời gian x ử lý. Ph ươ ng pháp l ưu nh ật ký Tại m ỗi tr ạm chúng ta t ổ ch ức m ột h ệ th ống l ưu d ữ t ất c ả các URL c ủa t ất c ả các tr ạm đã được crawler. Khi m ột URL được l ấy trong danh sách ra ki ểm tra, thay vì g ởi thơng điệp đi yêu c ầu t ừng tr ạm m ột ki ểm tra tình tr ạng c ủa URL thì tr ạm đĩ ki ểm tra tr ực ti ếp t ại h ệ th ống nh ật ký đã được l ưu tr ữ c ủa mình.
64 Ph ươ ng pháp này khơng c ần ph ải g ởi thơng điệp, nh ưng thay vào đĩ t ại tất c ả các tr ạm ph ải th ực hi ện l ưu nh ật ký c ủa t ất c ả URL đã được crawler. Begin Lấy url t ừ danh sách Tồn t ại Ki ểm tra Ch ưa t ồn t ại Xử lý, ghi vào nh ật ký Gởi thơng điệp đến các tr ạm ghi vào nh ật ký end Hình 3. 12 Thu ật tốn ki ểm tra tình tr ạng URL 3.3.3 Vấn đề s ự c ố đường truy ền 3.3.3.1 Đặt v ấn đề Nh ư đã trình t ại m ục 2.2, truy ền thơng là y ếu t ố t ối quan tr ọng trong h ệ phân tán, h ệ phân tán s ẽ khơng t ồn t ại n ếu khơng cĩ truy ền thơng. Th ế nh ưng trong th ực tế truy ền thơng r ất khơng ổn định, cĩ th ể m ất k ết n ối b ất c ứ lúc nào, thơng điệp cũng cĩ th ể th ất l ạc khơng đến được n ơi nh ận. Nếu đường truy ền b ị h ỏng, ngồi v ấn đề làm m ất các thơng báo tuy ền qua, nĩ cũng cĩ th ể phân c ắt m ạng thành hai ho ặc nhi ều nhĩm tách r ời. Tình hu ống này
65 được g ọi là phân ho ạch m ạng, lúc đĩ các v ị trí trong m ỗi phân ho ạch cĩ th ể v ẫn ti ếp tục ho ạt động. Khi đĩ vi ệc th ực hi ện các giao d ịch c ần truy xu ất đến nhi ều phân ho ạch tr ở thành m ột v ấn đề quan tr ọng. Gi ả s ử tr ạm 1 g ởi thơng điệp yêu c ầu ki ểm tra (C,1,2,“url a”) và thơng điệp này được ưu tiên x ử lý, nh ưng thơng điệp tr ả l ời k ết qu ả c ủa m ột tr ạm trong h ệ th ống khơng g ởi đến được tr ạm 1 (do đường truy ền b ị gián đoạn) . Điều này làm cho ti ến trình crawl url a c ủa tr ạm 1 ở tr ạng thái ch ờ v ĩnh vi ễn (ti ến trình ch ết) . T ươ ng t ự nh ư v ậy các tr ạm s ẽ t ồn t ại r ất nhi ều ti ến trình ch ết. Tr ạm 1 Tr ạm 2 Ch ờ đợi vĩnh vi ễn Hình 3. 13 Mơ hình s ự c ố đường truy ền 3.3.3.2 Gi ải quy ết v ấn đề Xét trong kho ảng th ời gian α (α: là h ằng s ố), kết qu ả c ủa sự c ố đường truy ền tạm chia ra hai lo ại: Th ất l ạc thơng điệp và phân ho ạch m ạng Ở đây ta đư a ra gi ải thu ật hai pha tuy ến tính (Linear two phase commit - 2PC). Trong đĩ các thành viên cĩ th ể trao đổi v ới nhau. Chúng ta gi ả thi ết r ằng th ứ t ự gi ữa các v ị trí cĩ tham gia vào vi ệc th ực hi ện m ột giao d ịch là 1, 2, ,N v ới điều ph ối viên là v ị trí đầu tiên gi ải thu ật này ho ạt động nh ư sau: Điều ph ối viên g ửi thơng điệp prepare đến thành viên 2. N ếu thành viên 2 ch ưa sẵn sàng ủy thác giao d ịch, nĩ g ửi thơng điệp bi ểu quy ết h ủy b ỏ Vote-abort (VA) đến thành viên 3 và giao d ịch b ị h ủy t ại th ời điểm này (h ủy b ỏ đơ n ph ươ ng c ủa 2). Ng ược l ại n ếu thành viên 2 đồng ý ủy thác, nĩ g ửi thơng điệp vote-commit (VC) cho thành viên 3 r ồi chuy ển sang tr ạng thái READY. Quá trình này ti ếp t ục cho đến
66 khi m ột bi ểu quy ết u ỷ thác đến được thành viên N. Đến đây k ết thúc pha đầu tiên. Nếu N quy ết định ủy thác nĩ g ửi tr ở l ại cho thành viên N-1 thơng báo global- commit (GC); b ằng khơng, nĩ g ửi m ột thơng điệp h ủy b ỏ tồn c ục global-abort (GA). Theo đĩ các thành viên chuy ển sang tr ạng thái thích h ợp (COMMIT ho ặc ABORT) và làm lan truy ền thơng điệp tr ở v ề điều ph ối viên Pha 1 prepare VC/VA VC/VA VC/VA VC/VA 1 2 3 4 5 N GC/GA GC/GA GC/GA GC/GA GC/GA Pha 2 Hình 3. 14 Cấu trúc giao ti ếp 2PC tuy ến tính Nh ư v ậy theo gi ải thu ật 2PC tuy ến tính, gi ả s ử cĩ m ột tr ạm trong h ệ th ống bị s ự cố khơng ti ếp nh ận được thơng điệp, ngay l ập t ức h ệ th ống g ởi thơng điệp thơng báo cho các tr ạm cịn l ại để các tr ạm xác định l ại tr ạm “ hàng xĩm” c ủa mình. M ặt khác h ệ th ống g ửi thơng điệp thơng báo vi ệc gia nh ập tr ở l ại c ủa các tr ạm b ị s ự c ố cho các tr ạm được bi ết. 3.3.4 Vấn add, remove các tr ạm 3.3.4.1 Đặt v ấn đề Theo quan điểm trình bày t ại m ục 3.3,2, n ếu các tr ạm trong h ệ th ống g ởi thơng điệp ki ểm tra l ần th ứ hai và đã ch ờ trong kho ảng th ời gian α mà v ẫn khơng cĩ ph ản hồi, điều này, cĩ ngh ĩa tr ạm đích đĩ đã b ị lo ại b ỏ kh ỏi h ệ th ống ( remove ). Sau khi kh ắc ph ục s ự c ố ta ph ải th ực hi ện add tr ạm này vào l ại h ệ th ống.
67 Vì lý do đường truy ền và s ự c ố t ại các tr ạm nên h ệ th ống luơn cĩ tình tr ạng remove ho ặc add (thêm tr ạm vào h ệ thơng) c ủa các tr ạm trong h ệ th ống. 3.3.4.2 Gi ải quy ết v ấn đề Gi ải quy ết vấn đề add – remove các tr ạm trong h ệ th ống phân tán, ta t ập trung gi ải quy ết 3 v ấn đề chính đĩ là: i. Thơng báo cho h ệ th ống bi ết vi ệc add – remove c ủa mình. ii. Cập nh ật l ại đồng h ồ logic. iii. Gi ải quy ết vi ệc nh ất quán d ữ li ệu. Dữ li ệu c ủa h ệ th ống được phân tán t ại m ỗi tr ạm, khi m ột tr ạm b ị đứt ra kh ỏi h ệ th ống đồng ngh ĩa v ới vi ệc m ột ph ần d ữ li ệu c ủa hệ b ị m ất theo, nh ưng khi v ận hành các tr ạm trong h ệ ph ải luơn ki ểm tra d ữ li ệu c ủa nhau để đảm b ảo d ữ li ệu c ủa h ệ luơn được nh ất quán. Nh ư v ậy, chúng ta ph ải làm th ế nào để khơng ảnh h ưởng đến ho ạt c ủa h ệ khi m ột hay nhi ều tr ạm b ị đứt ra kh ỏi h ệ. Để gi ải quy ết v ấn đề, ta đư a ra hai ph ươ ng án nh ư sau: i. Ph ục h ồi nh ờ h ệ th ống backup Tại m ỗi tr ạm ta xây d ựng thêm m ột tr ạm backup ( là b ản sao c ủa tr ạm chính ) hai tr ạm này ho ạt động đồng th ời v ới nhau. N ếu m ột trong hai tr ạm b ị s ự c ố thì tr ạm cịn l ại v ẫn ho ạt động bình th ường. N ếu tr ạm b ị s ự c ố sau khi kh ắc ph ục và gia nh ập lại h ệ th ống thì chúng th ực hi ện sao chép l ại tồn b ộ d ữ li ệu c ủa tr ạm cịn l ại. Để th ực hiện ph ươ ng án này, chúng ta ph ải xây d ựng thêm m ột h ệ th ống t ươ ng tự ph ục v ụ vi ệc backup. Nh ư v ậy, địi h ỏi m ột kho ản chi phí g ấp đơi để xây d ựng h ệ th ống. Tính v ề m ặt kinh t ế thì ph ươ ng án này khơng kh ả thi. ii. Ph ục h ồi nh ờ nh ật ký Mọi ho ạt động c ủa t ừng tr ạm trong h ệ th ống được bản thân m ỗi tr ạm ghi chép lại thành file nh ật ký ch ứa thơng tin c ủa t ất c ả các URL đã được crawler.
68 Hệ th ống file nh ật ký g ồm t ập h ợp các file v ới tên file trùng v ới tên các tr ạm trong h ệ th ống. M ỗi file l ưu tr ữ thơng tin url c ủa m ỗi tr ạm đã clawler được và đồng hồ logic c ủa t ừng tr ạm. H ệ th ống file nh ật ký c ủa các tr ạm gi ống nhau hồn tồn c ả về c ấu trúc và thơng tin. Khi m ột url được crawler và m ỗi l ần c ập nh ật đồng logic chúng ph ải th ực hi ện ghi vào file nh ật ký c ủa t ất c ả các tr ạm. Khi m ột tr ạm b ị s ự c ố, “ hàng xĩm ” c ủa tr ạm đĩ s ẽ thơng báo cho t ất c ả các tr ạm trong h ệ được bi ết. Các tr ạm s ẽ ch ấm d ứt m ọi giao d ịch v ới tr ạm b ị s ự c ố ngay t ức kh ắc. Vi ệc ki ểm tra url s ẽ đươ c th ực hi ện tr ực ti ếp trên file nh ật ký. Khi m ột tr ạm I mu ốn gia nh ập vào l ại h ệ th ống, nĩ g ửi m ột thơng điệp nh ờ tr ạm “hàng xĩm ” g ởi l ại đồng h ồ logic cho tr ạm I, Tr ạm I th ực hi ện c ập nh ật đồng h ồ logic, đồng th ời g ửi m ột thơng điệp sẳn sàng thơng báo cho các tr ạm trong h ệ bi ết. Begin Tr ạm I lan truy ền thơng điệp cho tr ạm G Thơng điệp khơng đến đư ợc G Tr ạm I thơng báo cho t ất c ả các tr ạm về tình tr ạng c ủa G Ch ấm d ứt giao d ịch, ki ểm tra tr ực ti ếp vào file nh ật ký end Hình 3. 15 Thu ật tốn x ử lý tr ạm remove kh ỏi h ệ