Kỹ thuật bảng băm phân tán trên mạng ngang hàng: giải pháp kiến trúc mở và ứng dụng

- MẠC VĂN VIÊN KỸ THUẬT BẢNG BĂM PHÂN TÁN TRÊN MẠNG NGANG HÀNG: GIẢI PHÁP KIẾN TRÚC MỞ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ KHOA HỌC NGÀNH: CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học: TS.
- NGUYỄN KHÁNH VĂN HÀ NỘI 2009 Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 1 Mạc Văn Viên Mục lục PHẦN MỞI ĐẦU.
- MẠNG NGANG HÀNG VÀ CÁC HỆ THỐNG DHTs.
- Hệ thống ngang hàng.
- 11 1.1.2 Quá trình phát triển của các hệ thống P2P.
- Phân loại ứng dụng trên mạng ngang hàng.
- Các ứng dụng trên mạng ngang hàng.
- Tìm hiểu DHT- Bảng băm phân tán.
- Giới thiệu một số DHT.
- 60 Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 2 Mạc Văn Viên 2.1.5 DHT Storage.
- 62 2.1.6 DHT chia sẻ giữa các ứng dụng.
- 70 2.2.2 Các giao diện.
- 101 Phần III: ỨNG DỤNG MINH HỌA.
- 102 3.2.1 Các API được sử dụng.
- 111 3.3 Triển khai ứng dụng và đánh giá.
- 123 Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 3 Mạc Văn Viên PHẦN MỞI ĐẦU Mạng internet đã làm thay đổi thế giới với sự ra đời của các trang thông tin, các dịch vụ tìm kiếm, kinh doanh điện tử… Nó đã ảnh hưởng lớn đến đời sống thường nhật của mọi cư dân trên hành tinh.
- Trên mạng internet người ta có thể đặt vé máy bay, rao bán nhà đất, tìm hướng dẫn chỉ đường hay tìm đọc nhanh nhất các thông tin thời sự quốc tế… Chính sự phát triển và phổ biến của các giao dịch internet đã tạo nên những thách thức mới cho các nhà cung cấp (NCC) dịch vụ.
- NCC phải đảm bảo hệ thống vẫn đứng vững khi có số lượng người truy cập lớn.
- Muốn vậy, hệ thống đó phải là một hệ thống xử lý phân tán, có một cơ chế quản lý tài nguyên thông minh và có một số khả năng khác như dưới đây.
- Đầu tiên, thiết kế của hệ thống đó phải Scalable (khả năng mở rộng về quy mô).
- Đó là một hệ thống mà kích cỡ của hệ thống luôn tương ứng với khả năng đáp ứng của nó.
- Hệ thống càng mở rộng thì khả năng phục vụ người dùng/số giao dịch càng nhiều.
- Hệ thống cũng không phụ thuộc vào bất kỳ một thành phần nào đó, để tránh hiện tượng nghẽn cổ chai dẫn đến giảm hiệu năng của hệ thống và nó cũng tránh cho hệ thống bị sụp đổ khi thành phần đó bị lỗi.
- Với một hệ thống có thiết kế Scalable thì ta có thể tăng kích cỡ khi khi hệ thống có nhưu cao hoặc giảm kích cỡ khi hệ thống có nhưu cầu thấp.
- Thứ hai, hệ thống đó phải self-managing (khả năng tự quản lý).
- Hệ thống đó phải có khả năng tự động cân bằng tải, đảm bảo an toàn dữ liệu hệ thống.
- Trong trường hợp như trên khi ta tăng kích cỡ của hệ thống thì nó sẽ phải tự nhận biết các thành phần Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 4 Mạc Văn Viên thêm vào và chia sẻ tải cho những phần mới thêm đó.
- Ngược lại khi giảm kích cỡ của hệ thống thì nó cũng tự động khôi phục lại giữ liệu mà phần bị tháo đi đã mang đi.
- Với một hệ thống lớn và động thì thuộc tính này là hết sức quan trọng.
- Thứ ba, hệ thống đó phải có khả năng fault-tolerant (khả năng chịu lỗi).
- Với một hệ thống lớn thì xác suất xảy ra lỗi tại các bộ phận là rất lớn, hệ thống vẫn phải hoạt động tốt khi số lượng bộ phận bị lỗi nằm trong một tỉ lệ cho phép.
- Hiện này, mạng ngang hàng là một trong những hướng tiếp cận rất tốt để thỏa mãn các thuộc tính trên.
- Đó là một kiến trúc mà các thành phần trong mạng có chức năng và khả năng như nhau.
- Do đó khi càng nhiều máy tham gia thì khả năng tổng thể của hệ thống mạng càng lớn.
- Tính chất phân tán của mạng ngang hàng giúp cho mạng hoạt động tốt khi một số máy gặp sự cố.
- Sự tiến hóa về cấu trúc mạng đã làm cho mạng ngang hàng ngày càng trở lên mạnh mẽ.
- Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng.
- Hiện nay có rất nhiều giải pháp khác nhau để xây dựng một DHT, người ta phân chia các giải pháp đó theo cấu trúc mạng và thuật toán định tuyến.
- Có một số cấu trúc nổi tiếng bao gồm Chord, CAN, Kademlia, Pastry, Tapestry và Bamboo [10].
- Mỗi node đều có thuật toán duy trì số lượng con trỏ đến các node hàng xóm là hàm logarithmic của kích cỡ mạng, như vậy Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 5 Mạc Văn Viên kích cỡ mạng có thể tăng rất nhanh mà băng thông để lưu trữ con trỏ các node hàng xóm tăng không đáng kể.
- Người ta chứng minh mạng vẫn hoạt động tốt, không bị mất dữ liệu ngay cả khi số lượng node trên mạng bị lỗi khá cao hoặc tốc độ các nodes tham gia và rời khỏi mạng cao.
- Bamboo cũng là một hệ thống đáng tin cậy, với hiệu năng lưu trữ lớn đã triển khai 200-300 nodes trên PlanetLab[1].
- OpenDHT [1] là một dịch vụ DHT công cộng được thiết kế để dễ dàng phát triển, triển khai và duy trì các ứng dụng DHT.
- Nó khắc phục được nhược điểm khó phát triển của các ứng dụng DHT truyền thống bằng cách sử dụng một mạng DHT có sẵn để cung cấp dịch vụ cho nhiều ứng dụng khác nhau.
- Do đó các ứng dụng OpenDHT chỉ cần truy cập dịch vụ này thông qua các giao diện đơn giản mà không phải triển khai DHT cho riêng mình.
- Hơn nữa, với các ứng dụng OpenDHT còn cho phép truyền thông vượt qua NAT hoặc Firewall.
- OpenDHT còn bảo đảm sự công bằng trong chia sẻ lưu trữ giữa các client trong hệ thống.
- Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 6 Mạc Văn Viên Nhiệm vụ của luận văn Thứ nhất, tìm hiểu và khảo sát các khái niệm liên quan, cấu trúc mạng và các thuật toán trong bảng băm phân tán.
- Tìm hiểu một số hệ thống bảng băm phân tán đã được phát triển và triển khai trên thực tế.
- Qua đó đánh giá, nhận xét các ưu và nhược điểm của của kiến trúc bảng băm phân tán.
- Thứ hai, tìm hiểu về cấu trúc mạng, cơ chế hoạt động của OpenDHT (giải pháp mở của bảng băm phân tán).
- Tìm hiểu sâu các khía cạnh kỹ thuật của hệ thống.
- Đánh giá khả năng ứng dụng so với hệ thống bảng băm phân tán truyền thống.
- Kết hợp tìm hiểu một hệ thống cụ thể.
- Cài đặt một ứng dụng minh họa dựa trên kiến trúc mở của bảng băm phân tán.
- Phần 1: Mạng ngang hàng và các hệ thống DHT.
- Ở đây trình bày một cách tổng quát nhất về mạng ngang hàng bao gồm khái niệm chung, quá trình phát triển, các kiến trúc và ứng dung tiêu biểu.
- Sau đó đi sâu vào một kiến trúc của mạng ngang hàng đó là DHT, tìm hiểu kiến trúc và cơ chế làm việc chung của DHT, các loại ứng dụng, ưu và nhược điểm.
- Tìm hiểu các mạng DHT tiêu biểu đang được sử dụng trên thực tế.
- Phần 2: Tìm hiểu về Bamboo và OpenDHT.
- Sau đó ta tìm hiểu về OpenDHT đây là nội dung chính của luận văn, ta sẽ đi sâu vào các vấn đề của một mạng OpenDHT là sự chia sẻ (về hiệu năng và về bộ nhớ) của các node trong mạng.
- Phần 3: Xây dựng một ứng dụng dựa trên OpenDHT.
- Ứng dụng mà ta xây dựng ở đây là ứng dụng multicast.
- Trong đó trình bày việc thiết kế xây dựng một ứng Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 7 Mạc Văn Viên dụng OpenDHT.
- Mục đích là đánh giá khả năng triển khai thực tế một ứng dụng OpenDHT, tìm hiểu xâu hơn các APIs để sử dung khi xây dựng một ứng dụng OpenDHT.
- Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 8 Mạc Văn Viên Lời cảm ơn Trước tiên, tôi xin bày tỏ lòng cảm ơn đến thầy giáo hướng dẫn TS.
- Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 9 Mạc Văn Viên Danh mục thuật ngữ Tiếng Anh Tiếng Việt Peer-to-peer Mạng ngang hàng Node Một thiết bị nối mạng (một peer) item Một đơn vị dữ liệu Structured Có cấu trúc Overlay Mạng được xây dựng trên các mạng khác Hash table Bảng băm Distributed hash table Bảng băm phân tán Join Gia nhập (mạng ngang hàng) Leave Rời khỏi (mạng ngang hàng) Failure Lỗi Churn rate Số lượng peer rời khỏi/gia nhập mạng trong một khoảng thời gian.
- put Lưu trữ dữ liệu vào bảng băm get Truy cập dữ liệu từ bảng băm Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 10 Mạc Văn Viên Phần I.
- MẠNG NGANG HÀNG VÀ CÁC HỆ THỐNG DHTs Nội dung chính của phần này là tìm hiểu các khái niệm của mạng ngang hàng, bảng băm phân tán.
- Qua đó ta hiểu được lịch sử hình thành cũng như biết được thế nào là một bảng băm phân tán, các thuộc tính quan trong của một bảng băm phân tán, cơ chế hoạt động chung của nó thế nào.
- Phần này cũng tìm hiểu cấu trúc của một số DHT nổi tiếng, qua đó ta có cái nhìn toàn diện hơn về hệ thống Bamboo mà ta sẽ tìm hiểu ở phần sau.
- Hệ thống ngang hàng Mạng ngang hàng là một kiểu mạng được thiết kế cho các thiết bị trong đó có chức năng và khả năng của các thiết bị đó là như nhau.
- Mạng ngang hàng (Peer-to-Peer – P2P) bắt đầu xuất hiện từ 1999 và đã thu hút sự quan tâm của giới CNTT trong những năm gần đây.
- Đặc biệt việc áp dụng các mô hình P2P trong việc xây dựng những ứng dụng chia sẻ file (file sharing), điện thoại trên nền Internet (Internet-based telephony) đã đạt được nhiều thành công.
- Hiện nay các ứng dụng P2P chiếm khoảng 50% (thậm chí 75%) băng thông trên Internet.
- Mô hình client/server và mô hình P2P Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 11 Mạc Văn Viên 1.1.1 Overlay network Là mạng máy tính được xây dựng trên nền của một mạng khác.
- 1.1.2 Quá trình phát triển của các hệ thống P2P Peer-to-Peer là thuật ngữ tương đối mới trong lĩnh vực mạng và các hệ thống phân tán.
- Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 12 Mạc Văn Viên Thế hệ thứ nhất Thế hệ P2P đầu tiên bắt đầu với sự xuất hiện của ứng dụng chia sẻ file Napster.
- Napster và các ứng dụng khác trong thế hệ thứ nhất sử dụng mô hình centralized directory.
- Đây là mô hình hybrid P2P trong đó hầu hết các peer trong hệ thống có vai trò như nhau, một số peer có vai trò lớn hơn và được gọi là các server.
- Trong mô hình này, các peer muốn chia sẻ file với các peer khác sẽ thông báo với server về các file này.
- Mô hình centralized directory Đóng góp chính của thế hệ thứ nhất là đã đưa ra kiến trúc mạng không xem các máy tính như client và server mà xem chúng như các máy cung cấp và sử dụng tài nguyên Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 13 Mạc Văn Viên với vai trò tương đương nhau.
- Đồng thời các hệ thống sử dụng mô hình này, điển hình là Napster còn gặp vấn đề về bản quyền các tài nguyên.
- Thế hệ thứ hai Thế hệ thứ hai bắt đầu với các ứng dụng như Gnutella, Freenet làm việc mô hình flooded requests.
- Mô hình này không có bất kỳ server nào, các peer bình đẳng như nhau.
- Các hệ thống peer to peer thế hệ thứ hai là các hệ thống peer to peer thuần túy.
- Hình 1.3 biểu diễn một mô hình flooding request.
- Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 14 Mạc Văn Viên Hình 1.3.
- Mô hình flooding request Thế hệ thứ hai xóa bỏ được một số điểm xử lý tập trung trong mạng nhưng tính khả mở còn kém hơn do mạng sử dụng thuật toán flooding sinh ra quá nhiều traffic.
- Thêm nữa, các mạng làm việc theo mô hình này không đảm bảo sẽ tìm được dữ liệu có trên mạng do phạm vi tìm kiếm bị giới hạn.
- Một số mạng trong thế hệ thứ hai đưa ra một số cải tiến.
- Kazza, Gnutella sử dụng khái niệm super peer trong đó một số node hoạt động như directory service, giảm lượng flooding trong mạng.
- Thế hệ thứ ba Sự đơn giản trong giải pháp và khả năng xóa bỏ điểm tập trung, chuyển trách nhiệm pháp lý về phía người sử dụng cũng như hạn chế về tính khả mở do lưu lượng quá lớn đã thu hút cộng đồng nghiên cứu về mạng và các hệ thống mở.
- Bài toán đặt ra cho Kỹ thuật bảng băm phân tán trên mạng ngang hàng: Giải pháp kiến trúc mở và ứng dụng 15 Mạc Văn Viên cộng đồng nghiên cứu là xây dựng một mạng P2P overlay khả mở không có điểm điều khiển tập trung.
- Mỗi peer trong hệ thống có một ID thu được từ việc băm các đặc thuộc tính đặc trưng của peer đó như địa chỉ IP hay public key.
- Các DHT được xây dựng nhằm mục đích cho phép các peer hoạt động như một cấu trúc dữ liệu phân tán với hai hàm chính Put(key,value) và Get(Key).
- Giải pháp DHT đảm bảo cho mạng có tính khả mở và khả năng tìm thấy thông tin cao trong khi vẫn hoàn toàn phân tán.
- DHT đang được xem như là cách tiếp cận hợp lý cho vấn đề định vị và định tuyến trong các hệ thống P2P.
- Phân loại ứng dụng trên mạng ngang hàng Các ứng dụng p2p có thể chia vào bốn nhóm: Chia sẻ file (file sharing): lưu trữ và chia sẻ nội dung là ứng dụng thành công nhất của công nghệ p2p.
- Các ứng dụng chia sẻ file tập trung vào việc lưu trữ thông tin trên các

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt