Luận văn thạc sĩ estude et mise en oeuvre dun système adaptatif de placement de données

Luận văn thạc sĩ: Nghiên cứu và triển khai hệ thống thích ứng vị trí dữ liệu. Giải pháp tối ưu hóa lưu trữ và truy xuất dữ liệu hiệu quả.

• Tác giả: Trương Hữu Trâm
• Người hướng dẫn: Maria-Teresa Segarra
• Trường học: Ecole Nationale Supérieure Des Télécommunications De Bretagne (ENSTB)
• Chuyên ngành: Informatique
• Đề tài: Etude Et Mise En Œuvre D’un Système Adaptatif De Placement De Données
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2007
• Địa điểm: Hanoi

Mục lục chi tiết

• Lời cảm ơn
• Tóm tắt
• Tóm tắt tiếng Anh
• 1. CHƯƠNG 1: MỞ ĐẦU
• 1.1. Mục tiêu thực tập
• 1.2. Giả thuyết làm việc
• 1.3. Các kịch bản cơ sở
• 1.3.1. Máy ảnh đến với ảnh mới
• 1.3.2. Người dùng xóa ảnh
• 1.3.3. Máy tính xách tay « rời » khỏi nhà
• 1.3.4. Truy cập các ảnh mới của máy ảnh từ TV
• 1.3.5. Máy ảnh thiếu dung lượng bộ nhớ
• 2. CHƯƠNG 2: HIỆN TRẠNG NGHIÊN CỨU
• 2.1. Lĩnh vực Web
• 2.1.1. Thuật toán phân bổ
• 2.1.2. Thảo luận
• 2.2. Các mạng ngang hàng
• 2.2.1. Phân loại kiểu mạng ảo
• 2.2.2. Phân bổ dữ liệu trong mạng ngang hàng
• 3. CHƯƠNG 3: DỊCH VỤ PHÂN BỔ DỮ LIỆU THÍCH ỨNG
• 3.1. Kiến trúc dịch vụ
• 3.2. Các lớp thiết bị
• 3.3. Quyết định số lượng bản sao tối thiểu
• 3.4. Định vị bản sao và tài nguyên
• 3.5. Cấu trúc dữ liệu và giải thuật
• 4. CHƯƠNG 4: TRIỂN KHAI VÀ HIỆN THỰC HÓA
• 4.1. Trường hợp sử dụng
• 4.2. Biểu đồ tuần tự
• 4.3. Biểu đồ lớp
• 4.4. Giao diện SuperPeerInterface
• 4.5. Giao diện NodeInterface
• 4.6. Cấu trúc các gói và tệp mã nguồn
• 4.7. Lớp NodeSkipElement và DataSkipElement
• 4.8. Giao tiếp giữa các nút
• 4.8.1. Kết nối vào mạng của một nút
• 4.8.2. Truyền thông giữa các nút
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giải mã luận văn Hệ thống thích ứng đặt dữ liệu là gì

Luận văn thạc sĩ với chủ đề "Étude et mise en œuvre d'un système adaptatif de placement de données" là một công trình nghiên cứu khoa học chuyên sâu, thực hiện trong khuôn khổ dự án ReCoDEM, hợp tác với Orange (France Telecom - R&D). Trọng tâm của nghiên cứu này là thiết kế và triển khai một dịch vụ phân bổ dữ liệu thông minh, có khả năng tự động quyết định việc tạo và xóa các bản sao (replica) trong một môi trường gồm nhiều thiết bị kết nối. Mục tiêu chính là đảm bảo tính sẵn sàng của dữ liệu và tối ưu hóa hiệu năng truy cập. Một hệ thống thích ứng (adaptive system) như vậy hoạt động trong bối cảnh các hệ thống phân tán (distributed systems) hiện đại, nơi các thiết bị có thể di động, tạm thời mất kết nối và có cấu hình tài nguyên không đồng nhất. Ví dụ điển hình là môi trường nhà thông minh với máy tính, máy ảnh, TV... kết nối với nhau. Luận văn đề xuất một kiến trúc phần mềm độc lập với các thuật toán sắp xếp dữ liệu (data placement algorithm) cụ thể, tạo tiền đề cho sự phát triển và thích ứng động trong tương lai. Nghiên cứu giải quyết bài toán cốt lõi: làm thế nào để sao chép dữ liệu một cách hiệu quả để người dùng luôn có thể truy cập dữ liệu cần thiết, ngay cả khi thiết bị gốc chứa dữ liệu đó không khả dụng, đồng thời đảm bảo tốc độ truy xuất nhanh nhất. Đây là một vấn đề quan trọng trong lĩnh vực luận án thạc sĩ công nghệ thông tin, mở ra hướng tiếp cận mới cho việc quản lý dữ liệu phi tập trung.

1.1. Mục tiêu cốt lõi của nghiên cứu trong luận án thạc sĩ

Mục tiêu chính của luận án là thiết kế và hiện thực hóa một dịch vụ phân bổ dữ liệu có khả năng thích ứng. Dịch vụ này phải tự động đưa ra quyết định tạo hoặc xóa các bản sao dữ liệu để đáp ứng hai yêu cầu then chốt: đảm bảo tính sẵn sàng (availability) và tối ưu hóa hiệu suất truy cập. Theo tài liệu gốc, công việc này "consiste à concevoir et mettre en œuvre le service de placement identifié dans le cadre de ReCoDEM". Điểm đột phá là dịch vụ được thiết kế để độc lập với các thuật toán placement cụ thể, cho phép hệ thống dễ dàng phát triển và tích hợp các phương pháp mới trong tương lai để đạt được khả năng "l’adaptation dynamique".

1.2. Bối cảnh ứng dụng thực tiễn của hệ thống thích ứng

Bối cảnh giả định của nghiên cứu là một môi trường không đồng nhất, ví dụ như một ngôi nhà thông minh. Môi trường này bao gồm nhiều thiết bị như tủ lạnh, máy ảnh, TV, máy tính xách tay... được trang bị bộ nhớ, bộ xử lý và kết nối mạng chất lượng tốt. Trong đó, một số thiết bị có tính di động cao (máy ảnh, laptop), thường xuyên kết nối và ngắt kết nối, khiến tài nguyên của chúng tạm thời không khả dụng. Ngược lại, các thiết bị khác lại ổn định hơn. Hệ thống tập trung vào dữ liệu đa phương tiện không thay đổi (non-modifiable) để tạm thời bỏ qua các vấn đề phức tạp về quản lý tính nhất quán, cho phép tập trung hoàn toàn vào bài toán định vị dữ liệu và sao chép dữ liệu.

II. Thách thức phân bổ dữ liệu trong hệ thống phân tán di động

Việc quản lý dữ liệu trong một hệ thống phân tán có tính di động cao đặt ra nhiều thách thức đáng kể mà các phương pháp truyền thống khó giải quyết triệt để. Vấn đề lớn nhất là đảm bảo tính sẵn sàng của dữ liệu. Khi một thiết bị chứa bản sao duy nhất của một tệp tin (ví dụ: máy ảnh chứa ảnh mới chụp) rời khỏi mạng, dữ liệu đó sẽ trở nên không thể truy cập. Một thách thức khác là tối ưu hóa hiệu năng truy cập. Việc truy xuất dữ liệu từ một thiết bị có cấu hình yếu (bộ xử lý chậm, băng thông thấp) sẽ gây ra độ trễ lớn, ảnh hưởng tiêu cực đến trải nghiệm người dùng. Luận văn đã phân tích các giải pháp hiện có trong lĩnh vực Web, mạng ngang hàng (P2P) và mạng lưu trữ (SAN). Kết quả cho thấy các hệ thống này còn nhiều hạn chế: các thuật toán trên Web thường giả định một môi trường tĩnh; các mạng P2P phi cấu trúc không đảm bảo tìm thấy dữ liệu; các mạng P2P cấu trúc gặp vấn đề "tìm kiếm chính xác"; và SAN thiếu tính linh hoạt, phụ thuộc nhiều vào quản trị viên. Những hạn chế này cho thấy sự cần thiết của một hệ thống thích ứng mới, có khả năng giải quyết đồng thời các bài toán về tính sẵn sàng, hiệu năng và tính động của môi trường cơ sở dữ liệu phân tán.

2.1. Vấn đề sẵn sàng dữ liệu khi thiết bị ngắt kết nối

Thách thức cơ bản nhất được luận văn nhấn mạnh là duy trì tính sẵn sàng của dữ liệu. Kịch bản một chiếc máy tính xách tay "sort de la maison" (ra khỏi nhà) là một minh họa rõ ràng. Nếu máy tính này chứa các bản sao ảnh mà không tồn tại trên các thiết bị khác, dữ liệu sẽ bị mất tạm thời. Do đó, hệ thống phân bổ dữ liệu phải có khả năng dự đoán tính di động của thiết bị để chủ động tạo ra các bản sao dự phòng trên những nút mạng (node) ổn định hơn, đảm bảo dữ liệu luôn có thể được truy cập bởi các thành viên khác trong mạng.

2.2. Hạn chế của các thuật toán sắp xếp dữ liệu hiện có

Nghiên cứu chỉ ra rằng các thuật toán sắp xếp dữ liệu trong các lĩnh vực khác không hoàn toàn phù hợp. Các thuật toán cho Web Cache thường dựa trên hàm chi phí (cost function) với các tham số cố định như số lượng bản sao và topology mạng, không thích ứng với sự thay đổi của các nút mạng. Các distributed systems dựa trên mạng P2P, dù linh hoạt, lại có nhược điểm riêng. Gnutella (phi cấu trúc) không đảm bảo tính sẵn sàng, trong khi Chord (cấu trúc) bị giới hạn trong việc tìm kiếm chính xác (exact search) và không hỗ trợ truy vấn theo dải giá trị. Điều này thúc đẩy việc tìm kiếm một giải pháp lai ưu việt hơn.

2.3. Yêu cầu tối ưu hóa tài nguyên và hiệu năng truy cập

Ngoài tính sẵn sàng, tối ưu hóa hiệu năng là một yêu cầu quan trọng. Kịch bản truy cập ảnh từ TV vào máy ảnh minh họa điều này. Máy ảnh là một thiết bị "chậm" với bộ xử lý yếu. Nếu TV truy cập trực tiếp, trải nghiệm sẽ rất tệ. Do đó, dịch vụ placement phải đủ thông minh để quyết định tạo một bản sao của các bức ảnh trên một thiết bị mạnh hơn (ví dụ: một máy chủ media tại gia). Quyết định này giúp giảm độ trễ và tối ưu hóa tài nguyên hệ thống, đảm bảo rằng các tác vụ nặng được xử lý bởi các thiết bị có đủ năng lực.

III. Phương pháp xây dựng hệ thống thích ứng đặt dữ liệu tối ưu

Để giải quyết các thách thức đã nêu, luận văn đề xuất một kiến trúc dịch vụ phân bổ dữ liệu gồm nhiều module chức năng phối hợp chặt chẽ. Cốt lõi của phương pháp này là một hệ thống thích ứng có khả năng ra quyết định dựa trên thông tin thu thập từ môi trường. Kiến trúc này bao gồm các thành phần: phân tích đặc tính thiết bị, tính toán số lượng bản sao tối thiểu/tối đa, dự đoán truy cập, định vị dữ liệu và tài nguyên, và cuối cùng là module ra quyết định tạo/xóa bản sao. Một trong những sáng kiến quan trọng nhất là phân loại các thiết bị trong mạng dựa trên mức độ ổn định và di động. Cách tiếp cận này cho phép data placement algorithm ưu tiên lưu trữ các bản sao quan trọng lên những thiết bị ổn định nhất, từ đó giảm thiểu số lần sao chép không cần thiết và tăng cường độ tin cậy. Thêm vào đó, nghiên cứu đưa ra một công thức toán học dựa trên xác suất để tính toán số lượng bản sao tối thiểu cần thiết, đảm bảo một mức độ sẵn sàng do người quản trị định trước. Cách tiếp cận có hệ thống và dựa trên dữ liệu này giúp tối ưu hóa tài nguyên lưu trữ và mạng lưới một cách hiệu quả.

3.1. Phân loại thiết bị dựa trên tính di động để sao chép dữ liệu

Giải pháp đề xuất phân loại các thiết bị thành nhiều lớp (class) dựa trên mức độ di động, do người quản trị xác định. Ví dụ, một mạng có thể có ba lớp: lớp trung tâm gồm các thiết bị ổn định nhất (tủ lạnh, máy giặt), lớp trung gian và lớp ngoài cùng gồm các thiết bị di động nhất (PDA, laptop). Khi cần sao chép dữ liệu, hệ thống sẽ ưu tiên chọn các nút mạng trong lớp ổn định nhất có đủ dung lượng lưu trữ. Chiến lược này giúp tăng cường tính sẵn sàng của dữ liệu một cách thông minh và hạn chế các hoạt động sao chép do sự biến động của các thiết bị di động.

3.2. Công thức tính toán số lượng bản sao dữ liệu tối thiểu

Để đảm bảo tính sẵn sàng, luận văn đề xuất một mô hình xác suất. Giả sử xác suất không sẵn sàng của một bản sao trong lớp thiết bị i là p_i, và có n_i bản sao trong lớp đó. Xác suất sẵn sàng toàn cục của dữ liệu được tính bằng công thức 1 - Πp_i^n_i. Hệ thống cần đảm bảo 1 - Πp_i^n_i ≥ P, với P là xác suất sẵn sàng mong muốn do quản trị viên thiết lập. Để đơn giản hóa, hệ thống sẽ cố gắng tạo đủ số bản sao trong cùng một lớp. Công thức rút gọn thành 1 - p_i^n_i ≥ P, từ đó có thể tính được số n_i tối thiểu. Cách tiếp cận này cung cấp một cơ sở định lượng cho việc tối ưu hóa tài nguyên.

IV. Bí quyết dùng Super Peer và Skip List để định vị dữ liệu

Để hiện thực hóa module định vị dữ liệu và tài nguyên một cách hiệu quả, luận văn đã lựa chọn một kiến trúc mạng lai và một cấu trúc dữ liệu tiên tiến. Giải pháp được chọn là mô hình mạng Super-Peer, một sự kết hợp giữa kiến trúc client-server và mạng ngang hàng (P2P). Trong mô hình này, các nút mạng mạnh và ổn định nhất sẽ đóng vai trò là Super-Peer, chịu trách nhiệm lập chỉ mục (indexing) và điều phối các yêu cầu tìm kiếm cho một nhóm các peer thông thường. Kiến trúc này mang lại hiệu quả tìm kiếm cao và khả năng mở rộng tốt của hệ thống phân tán. Để quản lý các chỉ mục này, nghiên cứu đã sử dụng một cấu trúc dữ liệu đặc biệt gọi là Skip List (danh sách nhảy). Skip List là một cấu trúc dữ liệu xác suất cho phép thực hiện các thao tác tìm kiếm, chèn, xóa với tốc độ rất nhanh (trung bình O(log n)). Ưu điểm lớn của Skip List so với các cấu trúc như Bảng băm phân tán (DHT) là nó hỗ trợ hiệu quả các truy vấn theo dải giá trị, giải quyết được vấn đề "tìm kiếm chính xác" của nhiều hệ thống P2P cấu trúc. Sự kết hợp giữa Super-Peer và Skip List tạo nên một cơ chế định vị dữ liệu và tối ưu hóa hiệu năng tìm kiếm mạnh mẽ cho hệ thống thích ứng.

4.1. Vai trò của mạng Super Peer trong hệ thống phân tán

Mô hình Super-Peer được chọn vì nó tận dụng được sự không đồng nhất của các thiết bị. Các nút ổn định, mạnh mẽ (ví dụ: máy tính để bàn) được chọn tự động để làm Super-Peer. Mỗi Super-Peer quản lý một danh sách các peer cấp dưới, lưu trữ siêu dữ liệu (metadata) về dữ liệu và tài nguyên của chúng. Khi một peer cần tìm kiếm, nó chỉ cần gửi yêu cầu đến Super-Peer của mình thay vì phải truyền tin quảng bá khắp mạng. Điều này giúp giảm đáng kể lưu lượng mạng và tăng tốc độ phản hồi, là một yếu tố quan trọng trong việc tối ưu hóa hiệu năng của các distributed systems.

4.2. Cấu trúc dữ liệu Skip List và thuật toán tìm kiếm hiệu quả

Skip List được sử dụng để xây dựng hai chỉ mục chính trên mỗi Super-Peer: một cho dữ liệu và một cho tài nguyên (các nút mạng). Đây là một danh sách liên kết được sắp xếp, trong đó mỗi phần tử có nhiều con trỏ ở các cấp độ khác nhau. Các con trỏ ở cấp cao hơn cho phép "nhảy" qua nhiều phần tử, giúp tăng tốc độ tìm kiếm. Luận văn đề xuất sử dụng mức độ ổn định của thiết bị để xác định số cấp độ của một phần tử trong Skip List. Ví dụ, một bản sao trên thiết bị ở lớp ổn định nhất sẽ có số cấp độ cao nhất. Đây là một thuật toán sắp xếp dữ liệu và lập chỉ mục rất hiệu quả.

4.3. Ứng dụng predicate để giải quyết bài toán tìm kiếm phức tạp

Để khắc phục nhược điểm "tìm kiếm chính xác" của các hệ thống P2P cấu trúc, luận văn đề xuất sử dụng các predicate (vị từ) cho các truy vấn. Một predicate là một bộ ba (thuộc tính, giá trị, toán tử). Ví dụ, để tìm "tất cả các bài hát của Céline Dion trong năm 2005", người dùng có thể tạo hai predicate: (Tên ca sĩ, Céline Dion, =) và (Năm, 2005, =). Nhờ cấu trúc được sắp xếp của Skip List, hệ thống có thể xử lý hiệu quả các truy vấn phức hợp này, mang lại sự linh hoạt cao hơn nhiều so với các hệ thống dựa trên băm. Cách tiếp cận này có tiềm năng ứng dụng trong mô hình học máy để phân tích truy vấn.

V. Hướng dẫn triển khai prototype hệ thống đặt dữ liệu thực tế

Luận văn không chỉ dừng lại ở lý thuyết mà còn trình bày chi tiết việc triển khai một prototype hoạt động, chứng minh tính khả thi của kiến trúc đề xuất. Prototype này hiện thực hóa các module cốt lõi của dịch vụ phân bổ dữ liệu, bao gồm quyết định tạo/xóa bản sao, định vị dữ liệu/tài nguyên, và tính toán số lượng bản sao tối thiểu. Hệ thống được phát triển bằng ngôn ngữ Java, sử dụng RMI (Remote Method Invocation) cho giao tiếp giữa các nút mạng. Các ca sử dụng chính như tạo dữ liệu mới, xóa dữ liệu, và khôi phục không gian lưu trữ được mô tả chi tiết thông qua các biểu đồ tuần tự. Thử nghiệm được tiến hành trên một mạng các máy tính tại phòng thí nghiệm của ENST Bretagne, mô phỏng môi trường một ngôi nhà với nhiều thiết bị. Kết quả thử nghiệm cho thấy prototype đã đáp ứng được các yêu cầu đặt ra, xử lý thành công các kịch bản như một nút mạng ngắt kết nối hay thay đổi vai trò từ peer thành Super-Peer. Việc triển khai thành công prototype là một minh chứng quan trọng cho giá trị của công trình nghiên cứu khoa học này, đặt nền móng cho các phát triển trong lĩnh vực cơ sở dữ liệu phân tán và hệ thống thích ứng.

5.1. Phân tích các ca sử dụng chính của hệ thống SAPLAD

Prototype, được gọi là SAPLAD (Système adaptatif de placement de données), cung cấp các chức năng chính cho người dùng và quản trị viên. Người dùng có thể tạo dữ liệu mới, yêu cầu khôi phục không gian bộ nhớ trên thiết bị của mình, và xóa dữ liệu (hệ thống sẽ tự động xóa tất cả các bản sao liên quan). Quản trị viên có thể thiết lập các tham số hệ thống như xác suất không sẵn sàng của từng lớp thiết bị và xác suất sẵn sàng toàn cục mong muốn. Các ca sử dụng này bao quát những hoạt động cơ bản nhất trong một hệ thống phân tán quản lý dữ liệu.

5.2. Chi tiết triển khai kỹ thuật và môi trường thử nghiệm

Hệ thống được lập trình bằng Java trên nền tảng Eclipse. Giao tiếp giữa các nút mạng được thực hiện thông qua Java RMI. Mỗi nút mạng (thiết bị) khi khởi động sẽ gửi một tin nhắn broadcast để thông báo sự hiện diện. Các Super-Peer sẽ nhận tin nhắn này và quyết định vai trò cho nút mới (peer hoặc Super-Peer) dựa trên các thuộc tính của nó. Prototype đã được thử nghiệm thành công trên mạng ADSL của phòng thí nghiệm, chứng tỏ khả năng hoạt động ổn định với các loại dữ liệu như hình ảnh và âm thanh.

VI. Tương lai của hệ thống thích ứng tối ưu hóa tài nguyên

Phần cuối của luận văn đưa ra những kết luận quan trọng và vạch ra các hướng phát triển trong tương lai cho hệ thống thích ứng đặt dữ liệu. Công trình đã đề xuất thành công một kiến trúc phần mềm hoàn chỉnh, giải quyết được những hạn chế của các hệ thống hiện có. Giải pháp phân loại thiết bị và sử dụng Skip List đã chứng tỏ hiệu quả trong việc đảm bảo tính sẵn sàng và tối ưu hóa hiệu năng. Tuy nhiên, nghiên cứu cũng thừa nhận một số giới hạn. Hệ thống hiện tại chỉ xử lý dữ liệu không thể sửa đổi để tránh bài toán đồng bộ phức tạp. Ngoài ra, yếu tố băng thông mạng chưa được xem xét là một tiêu chí chính trong việc ra quyết định phân bổ dữ liệu. Hướng phát triển trong tương lai rất hứa hẹn, bao gồm việc quản lý dữ liệu có thể sửa đổi, đưa ra quyết định placement dựa trên cả băng thông, và quan trọng nhất là tích hợp các thuật toán data placement algorithm một cách động. Xa hơn, hệ thống có thể được cải tiến bằng cách áp dụng mô hình học máy để dự đoán hành vi người dùng và trạng thái mạng, cũng như tích hợp với các nền tảng điện toán đám mây để tối ưu hóa tài nguyên lưu trữ trên quy mô lớn hơn.

6.1. Hạn chế của nghiên cứu và các vấn đề cần giải quyết

Những hạn chế chính được chỉ ra bao gồm: việc chỉ hỗ trợ dữ liệu không sửa đổi (non-modifiable data) và chưa xem xét băng thông mạng là một yếu tố quyết định. Vấn đề băng thông rất quan trọng, vì ngay cả khi một nút mạng chứa dữ liệu đang trực tuyến, nếu đường truyền đến người dùng quá yếu, dữ liệu đó thực chất vẫn không sẵn sàng. Giải quyết những vấn đề này sẽ là bước tiếp theo để hoàn thiện hệ thống.

6.2. Hướng phát triển Quản lý dữ liệu có thể sửa đổi

Một hướng đi quan trọng là mở rộng hệ thống để hỗ trợ dữ liệu có thể sửa đổi. Điều này đòi hỏi phải tích hợp các cơ chế quản lý tính nhất quán (coherence management) giữa các bản sao. Việc ra quyết định sao chép dữ liệu sẽ trở nên phức tạp hơn, vì cần cân bằng giữa lợi ích của việc có nhiều bản sao (tăng hiệu năng đọc) và chi phí để duy trì sự nhất quán giữa chúng (tăng độ phức tạp khi ghi).

6.3. Tiềm năng tích hợp điện toán đám mây và học máy

Trong tương lai, kiến trúc này có thể phát triển theo hướng "adaptation dynamique", nơi hệ thống có thể tự động lựa chọn thuật toán sắp xếp dữ liệu phù hợp nhất dựa trên bối cảnh hiện tại. Việc tích hợp mô hình học máy có thể giúp dự đoán các mẫu truy cập dữ liệu hoặc khả năng một thiết bị sẽ ngắt kết nối. Hơn nữa, việc kết hợp với các dịch vụ điện toán đám mây sẽ cung cấp một lớp lưu trữ bền vững và khả năng mở rộng gần như vô hạn, giúp tối ưu hóa tài nguyên một cách toàn diện.

Trích đoạn nội dung tài liệu

th) es Bretagne NST Institut de la Francophonie Ecole Nationale Supérieure des pour |’Inforamtique (IFT) Télécommunications de Bretagne (ENSTB) MEMOIRE DE FIN D’ETUDES MASTER D’INFORMATIQUE ETUDE ET MISE EN GUVRE D’UN SYSTEME ADAPTATIF DE PLACEMENT DE DONNEES Réalisé par TRUONG HUU Tram Encadré par Maria-Teresa SEGARRA & Jean-Marie GILLIOT ENST - Bretagne, Département Informatique Hanoi, 21 octobre 2007 Remerciements Je voudrais tout d’abord remercier Maria-Teresa SEGARRA pour m/’avoir accueilli dans son équipe de recherche de l’Ecole Nationale Supérieure des Télécommunications de Bre- tagne (ENST Bretagne). Je tiens 4 remercier tout particuliérement Maria-Teresa SEGARRA et Jean-Marie GIL- LIOT pour m’avoir encadré pendant ces six mois. Je les remercie de leur contact chaleureux, leurs conseils et encouragements, leur soutien permanent et la liberté de recherche qu’ils ont bien voulu me laisser. Mes plus sincéres remerciements vont également 4 tous les professeurs et les personnels de l’Institut de la Francophonie pour |’Informatique (IFI) pour m’avoir donné des cours de trés bonne qualité et pour leur soutien tout au long de mes études 4 VIF.

Un grand merci aux thésards et aux autres stagiaires 4 VENST Bretagne pour une ambiance de travail particuliérement favorable. Je remercie chaleureusement mes camarades de la promotion XI pour leur amitié sans faille et je leur souhaite bonne chance pour la soutenance. Merci enfin 4 mes parents, ma famille et mes amis pour leur soutien et leur encouragement a tout l’instant. Résumé Les systémes de réplication de données tirent parti des ressources disponibles sur des terminauz pour améliorer la disponibilité des données et/ou la performance globale du sys- téme.

Ces données peuvent appartenir a un utilisateur (qui peut avoir plusieurs terminaua personnels ou non) et/ou & une communauté. Elles peuvent étre mises en ceuvre sur des serveurs fixes et/ou sur des terminaux qui peuvent étre mobiles et travailler en mode dé- connecté et se synchroniser avec les bases de données sur le réseau. Dans ce cadre, le projet ReCoDEM, mené en partenariat avec Orange ( France Télécom - R & D ) se propose de construire un systéme de réplication tenant compte du contexte d’exécution des applications afin de décider de la création/suppression de répliques des données et de leur cohérence. Ce systéme compose de trois parties : placement de données, localisation de répliques et gestion de cohérence.

Ce stage de fin d’études consiste & concevoir et mettre en ceuvre le service de placement de données identifié dans le cadre de ReCoDEM. II s’agit de proposer une architecture logicielle d’un systéme de placement de données qui décide de la création et suppression de répliques pour assurer la disponibilité et tenant compte de la performance d’accés aus données. Ce service doit étre indépendant des algorithmes de placement de données afin de faciliter sa future évolution ver Vadaptation dynamique. Dans un premier temps, ce service est mis en ceuvre au sein d’une maison qui est constt- tuée d’un ensemble de dispositifs ( frigidaire, appareil photo, téléviseur, ordinateur,.

) munis de ressources mémoire ( volatile, disque, processeur ) et étant interconnectés par un réseau de bonne qualité. MOTS-CLES : Systémes distribués, réplication de données, liste a saut. Abstract The data replication systems benefit from the available resources on terminals to improve the availability of the data and/or the total performance of the system. These data can belong to a user (who can have several personal terminals or not) and/or at a community.

They can be carried out on servers fited and/or on terminals which can be mobile and work in disconnected mode and to synchronize itself with the data bases on the network. Within this framework, the project ReCoDEM, carried out in partnership with Orange (France Telecom R & D ) proposes to build a replication system taking into account of the execution context of the applications to decide replicas creation/suppression and their coherence. This system composes of three parts : data placement, replicas localization and coherence management. This intership consists to conceive and carry out the data placement service identified in the framework of ReCoDEM.

It is about proposing a software architecture of a data placement system which decides replicas creation and suppression to ensure the availabi- lity and taking into account of the access performance to the data. This service must be independent of the data placement algorithms to facilitate its evolution future worm the dynamic adaptation. Initially, this service is carried out within a house which is incorporated of a set of devices ( refrigerator, camera, television, computer,. ) provided with the resources memory ( volatile, disc, processor ) and being inter-connected by a network of good quality.

KEYWORDS : Distributed system, data replication, skip list. Table des matiéres Remerciements Résumé Abstract 1 Introduction 1.1 Objectifs de stage.2 Hypothése de travail .3 Scénarios de base.1 Appareil photo arrive avec de nouvelles photos .2 Utilisateur efface une photo .3 Ordinateur portable « sort » delamaison.4 Accés aux nouvelles photos de l’appareil photo 4 partir de la TV 1.5 Appareil photo manque d’espace mémoire. Etat de Part 13 2.1 Algorithme de placement .2 Les réseaux DpAIT-À-DAIT.1 Classification de type du réseau virtuel.2 Placement de données dans le domaine du pair-a-pair. ee 21 Service adaptatif de placement de données 22 3.Ặ eee ee ee 22 3.2 Classes de dispositifs.

Q Q Q Q HQ nà Tà xa 23 3.3 Décision de nombre minimal de rếplques.4 Localisation de répliques et de ressources. Ặ HQ HQ HQ SH 24 3.2 Structure de données et algorithmique .2 Diagrammes de séquence. HH HH HH HQ kg 4.3 Diagramme de classes. HQ HQ HH HH TK kia “N °:.

HQ HQ HH ng kg kg kia 4. Q Q Q Q Q HQ HQ HQ ng v2 32 4. Q Q Q Q HQ HQ HQ nu cà cv cv ng k k v k va 32 4.5 Interface SuperPeerlnterface et Nodelnterfacc .7 Classe NodeSkipElement et DataSkipElement .41 Connexion au réseau dunnœud .2 Communication entre lesnœuds. Q Q Q Q Q Q HQ uc cà cà cv cà cv vn v vn v v v.v v v k v xa 39 5_ Conclusion et perspectives 40 hìn 9o) 9a sẽ [I ee 40 DA x.

“ốẽ6ố ee 40 Bibliographie 42 Table des figures 1.2 Effacement de photos dans la mémoire de l’appareil photo .3 Ordinateur portable « sort » delamaison .4 Accés aux photos de l’appareil photo a partirdela TV .5 Appareil photo manque d'espace mếmoire .1 Un exemple de la topologle du réseau. Le poids du nœud et de l’aréte est sous la forme (W(¡),D(,j)). HQ HQ HH HH va 14 2.2 Exemple de recherche sur Gnultela.3 Chord : Cercle d’identificateur et opération de recherche .4 Tapestry : Publication et réplication d’objet .9 Ráseau de SUD@T-DpAIT. CO Q LH HQ Hà 2 19 2.6 SẠN: Système de stockage.

HQ HQ kia 20 3.2 Classes de disposSlliÍSs. LH HH nu v vn va 23 3.3 Liste à saut et recherche dans une liste à saut.4 Liste à saut den@œuds. LH Q HQ HQ HQ 22 26 3.9 Pseudo-code de la recherche de ressources .6 Liste 4 saut de données.1 Cas d’utilisation du service de placement de données .2 Diagramme de séquence de la création de répliques d’une nouvelle donnée .3 Diagramme de séquence de la création de répliques lorsqu’un dispositif «sort » 29 4.4 Diagramme de séquence de la récupération d’espace mémoire .5 Diagramme de séquence de la suppression de données.6 Diagramme de classes .7 5tructure de paquets et des fichiers du code .8 Communication entre les nods.L Disponibilité de la bande passante .00 00000 2 ee ee 41 Liste des tableaux 2.1 Comparaison des réseaux palr-à-DAIT.4 Classe Super Peerlnier [GC€. Q Q Q HQ Q HQ HQ n và cà kg k và xa 32 4.5 Classe NodeInter face 2.

aaaT aaă ra 33 4.7 Classe NodeSkipElement et DataSkipElement .1 Objectifs de stage Ce stage se situe dans le cadre du projet ReCoDEM [BGAS06], un canevas de réplica- tion adaptative de données. Dans ce canevas, un service de placement des répliques a été identifié qui doit décider de la création ou suppression de répliques. Mon travail de stage consiste & concevoir et mettre en ceuvre le service de placement identifié dans le cadre de ReCoDEM. II s’agit d’un service qui décide de la création et suppression de répliques pour assurer la disponibilité et tenant compte de la performance d’accés aux données.

Ce service doit étre indépendant des algorithmes de placement de données afin de faciliter sa future évolution vers l’adaptation dynamique.2 Hypothése de travail Nous supposons un environnement constitué d’un ensemble de dispositifs munis de res- sources mémoire ( volatile, disque ), processeur et interconnectés par un réseau ( filaire ou radio ) de bonne qualité. Un exemple d’un tel environnement peut étre une maison, les dispositifs étant frigidaire, appareil photo, téléviscur, ordinateur, etc. Sur cet environ- nement, certains dispositifs sont amenées a4 entrer et sortir de la maison, leurs ressources étant donc temporairement indisponibles, tandis que d’autres ne disparaitront que lors- qu’ils sont en panne ou remplacés par des nouveaux. De plus, la « qualité » des dispositifs ( vitesse de traitement, capacité de mémoire ) est différente ce qui produit une différence de performance d’accés aux données.

En ce qui concerne les données, il s’agit de données multimédia non modifiables afin de nous abstraire des problémes liés 4 la gestion de la cohérence des répliques. La prise en compte de données multimédia implique le besoin de gérer de données de taille importante. Enfin, nous supposons l’existence d’un service de surveillance de l’environnement qui informe notre service sur l’état des noeuds ( espace mémoire, bande passante des liens, vitesse de traitement,. Scénarios de base Afin d’illustrer le fonctionnement de notre service et identifier clairement nos besoins, nous avons travaillé sur cing scénarios de base qui sont présentés par la suite.1 Appareil photo arrive avec de nouvelles photos Un appareil photo ayant de nouvelles photos « entre » dans la maison.

Le service de placement de données doit s’assurer qu’au moins une réplique de chaque nouvelle photo est présente dans la maison ( disponibilité ). Il doit donc décider combien et sur quels noeuds les nouvelles photos seront stockées.réptiques s o* ° o*®” g5 Nouvelle | anal. 5 a gee” Pp hoto Fic.1 — Nouvelle photo Donc, le service de placement de données doit connaitre l’état global de la ressource mémoire pour décider de ces créations.2 Utilisateur efface une photo La suppression d’une photo par l|’utilisateur entraine la suppression de toutes les ré- pliques existantes de celle-ci. | - Fi (@ fell xỀ Suppression de replique Ss Fic.2 — Effacement de photos dans la mémoire de I|’appareil photo Donc, le service de placement de données doit connaitre la localisation des différentes répliques d’une donnée afin d’effectuer les suppression.3 Ordinateur portable « sort » de la maison Lorsqu’un dispositif contenant des répliques de photos qui n’existent pas sur les autres dispositifs sort de la maison, le service de placement de données doit répliquer celles-ci sur d’autres noeuds afin de s’assurer de la disponibilité de données.

aos , ` Repliques : Sortir Fig.3 — Ordinateur portable « sort » de la maison Donc, le service de placement de données doit étre capable de prédire la mobilité des dispositifs afin de prendre des décisions de création de données pour assurer leur disponi- bilités.4 Accés aux nouvelles photos de l’appareil photo a partir de la TV L’appareil photo étant un dispositif « lent » ( faible capacité processeur ), le service de placement de données peut décider de créer une réplique des photos qu'il contient sur d’autre dispositif performant pour ne pas pénaliser |’utiliser lors de l’accés a celles-ci. Donc, le service de placement de données doit étre capable de prédire les accés aux données afin de prendre des décisions de création de répliques.4 — Accés aux photos de l’appareil photo a partir de la TV 11 1.5 Appareil photo manque d’espace mémoire Fic.5 — Appareil photo manque d’espace mémoire Ce scénario de base représente le cas ot!