1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

TRƯƠNG LÊ QUÂN

ỨNG DỤNG ĐỘ TƯƠNG ĐỒNG CHUỖI TRONG CHỐNG TRÙNG LẶP
CHO CÁC TẬP DỮ LIỆU VĂN BẢN CÓ CẤU TRÚC DẠNG BẢNG

Ngành: Công nghệ Thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60.48.01.03

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: Tiến sĩ Hoàng Xuân Tùng

Hà Nội – 2015


2
Lời cảm ơn
Tôi xin chân thành cảm ơn TS Hoàng Xuân Tùng, người đã tận tình hướng dẫn tôi
trong suốt quá trình làm luận văn. Những ý kiến đóng góp và sự chỉ bảo của thầy trong
quá trình này là kim chỉ nam giúp tôi hoàn thành mục tiêu nghiên cứu của mình.
Tôi xin cảm ơn tập thể thầy cô giáo trường Đại học Công nghệ - Đại học Quốc gia
Hà Nội đã giảng dạy và tạo điều kiện tốt nhất cho tôi trong thời gian tôi học tập tại
trường cũng như khi nghiên cứu và làm luận văn
Tôi cũng xin được gửi lời cảm ơn tới những người đàn anh cùng thầy hướng dẫn
những người đã cho tôi những lời khuyên cần thiết và sự động viên của mọi người trong
quá trình làm luận văn của mình.

cả khi không xảy ra lỗi nhập liệu thì hiệu suất của phương pháp mới cũng ngang bằng
với phương pháp cũ. Điểm yếu là thời gian chạy, tôi chưa thể thực nghiệm những
phương pháp có thể giải quyết được vấn đề thời gian đã nêu trong lý thuyết.
Để có thể đánh giá được một cách công bằng nhất cần những thử nghiệm lớn hơn
với những phương pháp tối ưu hơn. Tuy nhiên tôi vẫn có thể kết luận được trong luận
văn này chính là: Phương pháp chống trùng lặp ứng dụng độ tương đồng chuỗi đã phần
nào giải quyết được những khó khăn khi xử lý dữ liệu trên các tập văn bản có cấu trúc.


5
Mục Lục
DANH MỤC CÁC TỪ VIẾT TẮT ........................................................................7
DANH SÁCH HÌNH VẼ ........................................................................................8
DANH SÁCH BẢNG .............................................................................................9
Chương 1: Trùng lặp dữ liệu và các phương pháp chống trùng lặp .....................10
1.1

Các vấn đề trùng lặp dữ liệu ..................................................................10

1.2

Chống trùng lặp dữ liệu .........................................................................11

1.2.1 Khái niệm ...........................................................................................11
1.2.2 Lợi ích của chống trùng lặp dữ liệu....................................................12
1.3

Ứng dụng của chống trùng lặp dữ liệu ..................................................13

1.3.1 Backup dữ liệu ....................................................................................13


6
3.1
Vấn đề của các phương pháp chống trùng lặp cho các tập dữ liệu văn bản
có cấu trúc dạng bảng .................................................................................................31
3.2

Ứng dụng của độ tương đồng chuỗi vào chống trùng lặp .....................32

3.2.1 Sử dụng khoảng cách chuỗi................................................................32
3.2.2 Phương pháp sử dụng phân cụm k-means ..........................................36
3.2.3 Phương pháp sử dụng thuật toán LSH (locality sensitive hashing) ...39
Chương 4 Thực nghiệm và đánh giá kết quả ........................................................42
4.1

Tổng quan về thử nghiệm ......................................................................42

4.2

Thử nghiệm 1 .........................................................................................43

4.3

Thử nghiệm 2 .........................................................................................46

4.4

Đánh giá kết quả ....................................................................................48

4.5


Tên đầy đủ
Local Area Network
Wide Area Network
Network Attached Storage
Storage Area Network
Internet Protocol
Fibre Channel
Locality Sensitive Hash


8
DANH SÁCH HÌNH VẼ
Hình 1.1 Chống trùng lặp dữ liệu [3]....................................................................12
Hình 1.2 Lưu trữ dữ liệu khi không sử dụng chống trùng lặp [3] ........................15
Hình 1.3 Lưu trữ dữ liệu khi sử dụng chống trùng lặp [3] ...................................15
Hình 2.1 File Base Compare .................................................................................17
Hình 2.2 Quy trình hoạt động của File Level Hashing .........................................18
Hình 2.3 Quy trình làm việc của Block Level Hashing ........................................19
Hình 2.4 Chia nhỏ File ..........................................................................................19
Hình 2.5 Dữ liệu sau khi xóa block/sub-block .....................................................20
Hình 2.6 Inline ......................................................................................................24
Hình 2.7 Post-process ...........................................................................................25
Hình 2.8 Client Base .............................................................................................25
Hình 2.9 Target-base.............................................................................................26
Hình 2.10 NAS-Based ..........................................................................................26
Hình 2.11 SAN-based ...........................................................................................27
Hình 2.12 Global...................................................................................................28
Hình 2. 13 Chia các đoạn có chiều dài cố định [1] ...............................................29
Hình 2. 14 Chia các đoạn có độ dài linh hoạt [1] .................................................29

lý. Chính vì thế mà dữ liệu – thứ tạo nên những thông tin cần phải được quản lý một
cách tốt nhất và được bảo vệ một cách hiệu quả, tuy nhiên khi lượng dữ liệu càng lớn
thì yêu cầu của nó về không gian lưu trữ và việc quản lý nó cũng ngày một gia tăng. Sự
gia tăng của dữ liệu dẫn tới một vấn đề hết sức nghiêm trọng khác, đó chính là sự trùng
lặp dữ liệu.
Trùng lặp dữ liệu là việc những dữ liệu có nội dung giống nhau nhưng vì nhiều
nguyên nhân khác nhau mà bị lưu lại nhiều lần. Một trong những hậu quả mà trùng lặp
dữ liệu gây ra chính là hao phí cho không gian lưu trữ. Dữ liệu trùng lặp càng lớn thì
hao phí càng nhiều. Ví dụ như một người bán hàng gửi 1 bản giới thiệu sản phẩm khoảng
10mb cho khoảng 500 người mỗi bản báo cáo phải chứa trong 1 file khác nhau cho dù
nội dung của chúng phần lớn là giống nhau, lúc này dung lượng phải lưu trữ chỉ khoảng
5gb, đương nhiên đó không phải một con số lớn thế nhưng nếu phải gửi 10 bản giới
thiệu, 100 bản giới thiệu thì sao, đó chắc chắn không phải là con số nhỏ nữa. Hơn nữa
phần lớn dữ liệu là giống nhau khiến cho việc lưu trữ dữ liệu trở nên hoang phí, những
block giống nhau lại được lưu trữ nhiều lần không những khiến chi phí cho không gian
lưu trữ tăng lên nhanh chóng mà còn khiến cho chi phí khi backup dữ liệu tăng lên tới
mức chóng mặt. (Chi tiết có thể xem trong [1])
Theo [2] thì không chỉ trong những công ty lớn xảy ra việc trùng lặp dữ liệu mà
trên cả những đám mây. Đám mây là những hồ dữ liệu lớn nơi các dữ liệu được lưu trữ.
Thay vì việc phải sử dụng một hay nhiều máy chủ thì tất cả dữ liệu trong đám mây đều
được ảo hóa thông qua internet. Điểm mạnh của việc lưu trữ đám mây chính là ở tính
mềm dẻo, khả năng tính toán, tính đàn hồi và co giãn tài nguyên, người sử dụng không
cần phải tính toán dung lượng lưu trữ mà chỉ cần trả tiền là sẽ có dung lượng cần thiết.
Chính vì thế mà việc trùng lặp dữ liệu xảy ra trong đám mây lại càng nhiều. Lấy ví dụ
đơn giản một ông A yêu thích nhạc cổ điển, ông ta đưa một file X lên đám mây, ta lại
có thêm một ông B cũng rất yêu thích nhạc cổ điển trùng hợp là ông ta cũng yêu thích
bài X và cũng đưa nó lên đám mây. Hiện giờ trong đám mây sẽ có 2 bài X và cùng phải
lưu trữ hai bài này. Như vậy chi phí cho cùng một file, cùng một dữ liệu sẽ tốn gấp đôi,
chưa kể tới việc số người dùng đám mây càng lúc càng nhiều, số lượng dữ liệu trùng lặp
càng lúc càng lớn, không phải là gấp đôi nữa mà là gấp ba, gấp bốn thậm chí là gấp hàng


56
[16] K. E. D. B. Mark Lillibridge, Improving Restore Speed for Backup Systems
that Use Inline, 2013.
[17] Y. J. D. H. D. Guanlin Lu, Frequency Based Chunking for Data DeDuplication, 2010.
[18] L. Whitehouse, HP StoreOnce Deduplication Software, 2010.
[19] S. S. J. L. Biplob Debnath, ChunkStash: Speeding up Inline Storage
Deduplication using Flash Memory, 2010.
[20] L. D. R. Amatruda, Back up and recovery: accelerating efficiency and
driving down IT cost using data deduplication, 2010.
[21] P. Bille, Asurvey on tree edit distance and related problems, 2004.