21/10/2026 · VietTechies · Biên tập
Chèn thêm dữ liệu gần đầu một tệp, phần nội dung không đổi phía sau sẽ dịch chuyển. Rsync, do Andrew Tridgell và Paul Mackerras phát hành năm 1996, có thể tìm ra những khối dữ liệu trùng khớp ở vị trí mới, giúp hai máy tính đồng bộ tệp mà không phải truyền lại toàn bộ phần nội dung ấy.
Mấu chốt là máy nhận không cần gửi lại toàn bộ tệp cũ để so sánh. Máy nhận chỉ gửi những mô tả ngắn gọn về các khối dữ liệu mình đã có. Máy gửi tìm các khối đó trong tệp mới rồi gửi lại chỉ dẫn để dựng lại tệp.
Cách này tiết kiệm dữ liệu truyền qua mạng bằng cách dùng tài nguyên ở những chỗ khác: tính tổng kiểm tra (checksum), tìm kiếm trong tệp nguồn và đọc dữ liệu sẵn có ở máy đích.
Truyền tệp mà không cần gom cả hai bản về một máy
Ngày 19/6/1996, Tridgell thông báo ông và Mackerras đã phát hành một gói phần mềm mang tên rsync. Thông báo mô tả một thuật toán cập nhật có thể gửi phần khác biệt giữa tệp nguồn và tệp đích mà không cần có sẵn cả hai bộ tệp ở cùng một đầu kết nối.
Điều này đặc biệt có ý nghĩa với đường truyền chậm. Nếu máy đích đã có phần lớn nội dung tệp, gửi lại phần đó chỉ tốn băng thông mà không bổ sung nội dung mới. Nhưng chỉ biết hai tệp tương tự nhau vẫn chưa đủ: máy gửi cần có cách xác định những phần sẵn có mà máy nhận có thể dùng lại.
Báo cáo kỹ thuật của hai tác giả mô tả lời giải qua hai tệp. Máy nhận giữ tệp cũ; máy gửi giữ phiên bản muốn chuyển đến máy nhận. Thay vì yêu cầu gửi toàn bộ tệp cũ, máy gửi nhận một danh sách tổng kiểm tra của các khối — những giá trị được tính từ nội dung từng khối.
Máy nhận mô tả khối, máy gửi tìm ở từng vị trí
Trong thuật toán của báo cáo, máy nhận chia tệp thành các khối có kích thước cố định, không chồng lấn; khối cuối có thể ngắn hơn. Với mỗi khối, máy nhận tính một tổng kiểm tra cuốn chiếu (rolling checksum) loại yếu và một tổng kiểm tra mạnh hơn, rồi gửi các giá trị đó cho máy gửi.
Điểm khác biệt quan trọng giữa hai phía nằm ở nơi máy gửi tìm kiếm. Máy gửi tìm phần trùng khớp tại bất kỳ vị trí byte nào trong tệp của mình, thay vì chỉ tìm tại những ranh giới khối dùng để chia tệp của máy nhận.
Thử xét một chỉnh sửa minh họa: chèn một đoạn văn mới gần đầu tài liệu. Nếu chỉ so sánh các khối ở cùng vị trí, phần nội dung cũ phía sau sẽ bị đem so với phần nội dung mới khác, vì đoạn chèn thêm đã đẩy nội dung dịch chuyển. Tìm ở những vị trí khác giúp máy gửi nhận ra các khối có thể dùng lại sau khi chúng dịch chuyển.
Ví dụ này giải thích cơ chế, chứ không phải kết quả đo hiệu năng hay lời hứa rằng mọi chỉnh sửa đều giữ nguyên mọi khối. Nội dung mới hoặc đã thay đổi vẫn cần được gửi đi, và khả năng tìm thấy phần trùng khớp phụ thuộc vào những khối sẵn có trong tệp cũ của máy nhận.
Tổng kiểm tra cuốn chiếu giúp việc tìm kiếm khả thi
Tìm ở mọi vị trí có thể có nghe rất tốn công nếu mỗi phần dữ liệu có khả năng trùng khớp đều đòi hỏi tính lại tổng kiểm tra trên cả một khối. Tổng kiểm tra cuốn chiếu giúp tránh lặp lại toàn bộ phép tính ấy mỗi khi cửa sổ tìm kiếm tiến thêm một byte.
Từ tổng kiểm tra hiện tại, byte rời khỏi cửa sổ và byte mới đi vào, thuật toán có thể tính tổng kiểm tra tiếp theo với ít phép tính. Nhờ vậy, thuật toán có thể quét dọc tệp nguồn mà vẫn duy trì tổng kiểm tra cho cửa sổ đang dịch chuyển.
Tổng kiểm tra yếu đóng vai trò bộ lọc ban đầu. Khi giá trị này khớp với mô tả một khối từ máy nhận, máy gửi tính tổng kiểm tra mạnh, vốn tốn công hơn, để kiểm tra kỹ hơn phần dữ liệu có khả năng trùng khớp. Báo cáo thời đó nêu tổng kiểm tra cuốn chiếu 32-bit và tổng kiểm tra MD4 (Message Digest 4) 128-bit; các chi tiết này mô tả thuật toán trong báo cáo, chứ không đại diện cho mọi bản triển khai về sau.
Bản triển khai độc lập của Norman Ramsey thể hiện rõ sự phân chia này: một giao diện cung cấp tổng kiểm tra cuốn chiếu ít tốn công tính toán, giao diện khác cung cấp dấu vân tay dữ liệu để kiểm tra các khối có khả năng trùng khớp. Tìm phần dữ liệu có thể khớp với ít công tính toán và kiểm tra phần đó kỹ hơn là hai công việc khác nhau.
Kết quả là một bộ chỉ dẫn dựng lại tệp
Khi đã tìm được các phần trùng khớp, máy gửi truyền một chuỗi chỉ dẫn. Mỗi chỉ dẫn hoặc tham chiếu đến một khối đã có trong tệp của máy nhận, hoặc chứa trực tiếp dữ liệu phải truyền qua kết nối.
Máy nhận làm theo các chỉ dẫn đó để dựng tệp mới theo đúng thứ tự. Với tham chiếu khối, máy nhận đọc phần dữ liệu sẵn có tương ứng. Với dữ liệu được gửi trực tiếp, máy nhận ghi các byte nhận được từ máy gửi.
Mô tả như vậy chính xác hơn cách nói rsync chỉ gửi những byte đã thay đổi. Dữ liệu truyền đi còn bao gồm mô tả khối và các tham chiếu, còn những phần không tìm được khối trùng khớp sẽ được gửi trực tiếp dưới dạng dữ liệu. Lượng dữ liệu tiết kiệm được đến từ việc thay nội dung trùng khớp bằng chỉ dẫn dùng lại nội dung ấy.
Bài tổng quan thực hành của dự án mô tả máy nhận dựng một tệp tạm từ hai nguồn dữ liệu đó, kiểm tra tệp đã dựng xong rồi thay thế phiên bản hiện có. Bài viết cũng lưu ý rằng phần giải thích đã giản lược các chi tiết triển khai và những trường hợp ngoại lệ.
Tiết kiệm đường truyền, tốn thêm công xử lý tại chỗ
Dùng lại dữ liệu cũ không có nghĩa là hết việc phải làm. Máy gửi phải tính tổng kiểm tra và tìm phần trùng khớp. Máy nhận phải đọc các khối trùng khớp từ tệp hiện có rồi ghi tệp đầu ra được dựng lại.
Bài tổng quan thực hành chỉ ra rằng việc tạo tổng kiểm tra và tìm kiếm đòi hỏi bộ xử lý làm khá nhiều việc. Ở phía nhận, vừa đọc các khối cũ vừa ghi tệp mới có thể trở nên tốn kém khi lượng dữ liệu đang xử lý vượt quá bộ nhớ đệm đĩa và đòi hỏi đầu đọc phải liên tục di chuyển để tìm dữ liệu.
Vì vậy, thiết kế này đánh đổi một loại tài nguyên lấy những loại khác. Với kết nối chậm, tránh được dữ liệu phải truyền đi là điều có giá trị; công tính toán và truy cập bộ lưu trữ tại chỗ quyết định một phần chi phí đánh đổi. Chỉ riêng cơ chế này chưa đủ để khẳng định rsync luôn có lợi thế về tốc độ.
Ý tưởng bền vững của rsync thể hiện ngay trong bộ chỉ dẫn dựng lại tệp: mô tả những gì máy bên kia đã có, tìm ra chúng ngay cả khi vị trí đã thay đổi, rồi gửi chỉ dẫn để dùng lại.
Bài liên quan
Đọc bằng ngôn ngữ khác: English
Nguồn
- Andrew Tridgell — First release of rsync: rcp replacement, June 1996
- Andrew Tridgell và Paul Mackerras — The rsync algorithm
- Andrew Tridgell và Paul Mackerras — Rolling checksum
- Dự án Rsync — How Rsync Works: A Practical Overview
- Norman Ramsey — The Rsync Algorithm: an independent implementation
- Ảnh đại diện: Mk2010; Wikimedia Commons; CC BY 4.0 (đã chỉnh sửa từ ảnh gốc)
