Khi có cuộc giao tiếp giữa 2 bên thông qua điện thoại, mỗi bên có một bản copy của một cuốn sách. Bây giờ, giả sử 2 bản copy có thể khác nhau ở một vài chỗ nào đó. Bằng cách nào chúng ta có thể tìm ra 2 cuốn sách có giống nhau hay không, và nếu không thì chúng khác nhau ở chỗ nào và khác nhau như thế nào, mà không cần đọc hết toàn bộ cuốn sách qua điện thoại?
Câu trả lời của câu hỏi đầu tiên rất đơn giản, bằng cách dùng hàm checksum (MD5 chẳng hạn) và so sánh checksum của 2 cuốn sách, như thế nó sẽ xác định được 2 cuốn sách có giống nhau hay không. Câu trả lời cho câu hỏi thứ 2 thì khó hơn một chút. Một hướng nghiên cứu ban đầu là người ta chia cuốn sách thành 2 nửa, nửa đầu và nửa cuối, sau đó sẽ thực hiện checksum trên mỗi nửa, cho tới khi vị trí khác nhau được tìm ra. Tuy nhiên, hướng nghiên cứu này sẽ bị sai trong một trường hợp hết sức đơn giản, khi một cuốn sách chứa thêm một số từ vào đầu, khi đó nó sẽ phá huỷ sự sắp thẳng hàng của tất cả các đường bao khối giữa 2 cuốn sách. Do đó, một hướng nghiên cứu khác, mạnh hơn là cần thiết mặc dù ý tưởng cơ bản vẫn là sử dụng checksum trên các khối.
Chúng ta sẽ mô tả và chọn lọc thuật toán rsync. Ý tưởng cơ bản là giải quyết vấn đề về sự sắp xếp thẳng hàng bằng cách tìm checksum khối do file tham chiếu, và so sánh các checksum này với các checksum khối tương ứng của file hiện thời, và với checksum của tất cả các vị trí có thể của các khối trong file hiện thời. Kết quả là, server biết được đoạn nào của file hiện thời đã tồn tại trong file tham chiếu, và phần nào mới cần giao tiếp với client. Để đạt được hiệu quả, 2 checksum khác nhau sẽ được truyền thông với server, tuy
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
nhanh nhưng không đáng tin cậy, muốn đạt được sự tin cậy hơn thì cần đắt hơn nhiều.
1. Tại client:
(a) Phần fold trong các khối Bi = fold [ib,(i+1)b-1] của kích thước b được xác định sau
(b) Với mỗi khối Bi, tính 2 checksum, ui = hu (Bi) và ri = hr (Bi) và truyền chúng tới server. Ở đây, hu là hàm checksum không đáng tin cậy nhưng nhanh, và hr thì đáng tin cậy nhưng đắt.
2. Tại server:
Với mỗi cặp checksum nhận được (ui,ri), thêm một thực thể (ui,ri,i) vào cấu trúc dữ liệu từ điển, sử dụng ui như một giá trị khoá.
(c) Thực hiện một bước trong fnew, bắt đầu tại vị trí j=0, và liên quan tới các bước sau:
Tính hàm checksum không đáng tin cậy hu(fnew [j, j+b-1]) trên khối bắt đầu tại j.
Kiểm tra từ điển xem có khối nào có checksum không tin cậy phù hợp không
Nếu tìm thấy, và nếu có checksum đáng tin cậy cũng phù hợp, truyền một con trỏ tới chỉ số của khối phù hợp trong fold tới client, j tiến tới vị trí b, và tiếp tục.
Nếu không tìm thấy, hoặc nếu checksum tin cậy không phù hợp, truyền ký tự fnew[j] tới client, tăng j thêm 2 và tiếp tục.
Tại client:
Sử dụng dòng dữ liệu và con trỏ với khối trong fold để xây dựng lại fnew.
Checksum nhanh và không tin cậy được sử dụng để tìm ra sự phù hợp, và các checksum tin cậy sau đó được dùng để xác nhận sự phù hợp đó.
Checksum phù hợp được thi hành bằng cách sử dụng MD4 (128 bit).
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Checksum không tin cậy có 32bit, nó cho phép chuyển một cách hiệu quả các đường bao khối
bởi 1 ký tự, chẳng hạn, checksum cho f[j+1,j+b] có thể được tính trong thời gian không đổi từ f[j,j+b-1].
Rõ ràng, việc lựa chọn một kích thước khối tốt là tiêu chuẩn để thực hiện thuật toán. Sự lựa chọn tốt nhất lại phụ thuộc lớn vào sự giống nhau giữa 2 file – các file càng giống nhau thì chúng ta càng có thể chọn kích thước khối lớn. Hơn nữa, vị trí của các thay đổi trong file thì cũng rất quan trọng. Nếu một ký tự đơn được thay đổi trong mỗi khối của fold, thì không có sự phù hợp nào sẽ được tìm thấy tại server và rsync sẽ không thể hoàn thành một cách hiệu quả được; mặt khác, nếu tất cả các thay đổi được phân thành một vài vùng trên file, rsync sẽ làm rất tốt thậm chí với một kích thước khối lớn. Tuy nhiên, rsync không có sự thi hành tốt với không gian khoảng cách file.
Tất nhiên, thông thường kích thước khối thậm chí có thể thay đổi trong một file. Trong thực hành, rsync bắt đầu với một kích thước khối hàng trăm byte, và sử dụng các phép heuristic để chỉnh sửa sau đó. Một sự tuỳ chỉnh khác trong rsync cho phép server nén tất cả các ký tự được truyền cho các phần không có sự phù hợp của file – đó là thuật toán nén LZ; nó sẽ đem lại những lợi ích khác như được trình bày dưới đây.
2.4.2. Đánh giá thuật toán qua thực thi rsync
Chúng ta sẽ đưa ra một vài kết quả về sự thi hành của rsync so với nén delta.
Các kết quả sử dụng tập dữ liệu gcc và emacs. Chúng ta tổng kết 5 con số cho rsync: số lượng dữ liệu được gửi từ client tới server(request), số lượng dữ liệu được gửi từ server tới client (reply), số lượng dữ liệu được gửi từ server tới client với tùy chọn nén đã bật (reply compressed), và tổng số cho cả 2 hướng trong trường hợp không nén (total) và đã nén (total compressed).
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Bảng 2.2. kết quả nén cho gcc và emacs bộ dữ liệu trong KB
Bảng 2.3. Kết quả nén cho emacs với kích thước block khác nhau trong KB