Giải thích rsync cho trẻ 6 tuổi như thế nào?

algorithm

35

hardcore

18

Cẩm Huỳnh viết ngày 16/08/2017

Einstein có câu nói được quote khá nhiều.

Mình không hiểu vì sao Eistein lại nói thế (cũng không biết ông có thực sự nói không), với lại con nít sáu tuổi thì cũng chả biết Einstein là ông thần nào đâu. Cơ mà mình sẽ cố thử.

Bắt đầu với một câu chuyện cổ tích

Ngày xửa ngày xưa ở một vùng đất kia, có ba anh em nhà GRS (chắc cũng gốc gác đâu đó với GPRS ở Việt Nam).

Anh em họ rất thông minh và hay giúp dân làng nên trưởng làng rất ghét. Bàn mưu tính kế sao mà đến một ngày nọ, ông ta giao cho ba anh em nhiệm vụ trong vòng 24h phải đồng bộ hóa hai thư viện A và B trong vùng sao cho sách ở thư viện B tương đương với thư viện A (chú ý là không có chiều ngược lại), nếu không họ sẽ bị đuổi khỏi làng.

Một ý đồ hết sức thâm hiểm và độc ác của trưởng làng, bởi đó là một nhiệm vụ gần như bất khả thi!!! Bạn nghĩ xem mỗi thư viện phải có đến hàng nghìn cuốn sách, với cả triệu trang sách. Đương nhiên cách mà ai cũng biết là bỏ hết đống sách ở B đi và in lại toàn bộ sách ở A đem qua, nhưng mà ai chẳng biết ... cách đó lâu?! Tính nhẩm nếu mỗi phút chép được 10 trang thì họ sẽ mất vài tháng để đồng bộ hết sách.

Trưởng làng tưởng là phen này chắc sẽ trừ được cái gai trong mắt, nhưng đến ngày hôm sau bất ngờ đã xảy ra, thư viện B không chỉ được đồng bộ hoàn toàn, mà còn chính xác đến từng trang sách nữa chứ. Từ đó ông ta không bao giờ dám hoạnh họe ba anh em họ nữa.

Nhà GRS đã làm điều này thế nào?

Thuật toán

Anh em GRS nhận thấy rằng, sách ở hai thư viên đại đa phần giống nhau, chỉ có một số sách quá cũ nên bị mất chữ hoặc mất trang.

Để đỡ phải chép tay họ đã mua thêm máy photocopy, đồng thời một bác xe ôm cũng được thuê để làm nhiệm vụ liên lạc.

1. Generator

Generator sẽ duyệt hết toàn bộ sách trong thư viện A và với từng cuốn sách, anh sẽ nhắn tin với Receiver lúc này đang ở B.

• Cuốn nào B có mà A không có => Generator sẽ bảo Receiver quăng đi.

• Cuốn nào A có mà B không có => Generator sẽ bảo Receiver dùng máy photocopy in ra.

• Cuốn nào A và B đều có => Generator sẽ bảo Receiver tính toán dựa trên Bí Kíp™ (giải thích ở dưới) và ghi ra nháp ra một đống mã gọi là checksum có nội dụng như sau.

1-10: 99
2-11: 98
3-12: 55
4-13: 102
...
91-100: 123

Sau đó anh ta sẽ đưa đống mã này cho Sender.

2. Sender

Sau khi nhận được đống mã ở trên, Sender sẽ sử dụng kết quả đó và áp dụng Bí Kíp™ để tìm sự khác biệt trong hai phiên bản của cuốn sách ở hai thư viên.

Đầu tiên từ trang 1 - 10, Sender đếm nhanh số từ trong vùng trang này là 90, đem so với kết quả của Receiver cho trang 1 - 10 (99 trang) thì nó khác, Sender liền ghi số 1 vào giấy nháp và in trang 1 ra.

Lặp lại thao tác cho trang 2 - 11, kết quả lại khác so với tính toán của Receiver, Sender ghi tiếp số 2 vào nháp và cũng in trang 2.

Tiếp theo kết quả lại tiếp tục lệch cho trang số 3 - 12, 4 - 13 và 5 - 14, nên trang 3, 4 và 5 cũng được ghi vào nháp và in ra.

Nhưng đến vùng từ trang 6 - 15, Sender nhận ra số từ là giống nhau, lúc này anh ta sẽ nhảy thẳng sang trang 16 - 25 thay vì trang 7 - 16 như trước, đồng thời không ghi gì hay photocopy gì cả.

Cứ như thế thao tác được lặp lại cho đến khi hết cuốn sách, bây giờ thì giấy nháp của Sender có dãy số như sau.

1, 2, 3, 4, 5, 16, 101, 102, 103

và các bản photocopy của chúng.

Sau đó anh nhờ bác xe ôm mang dãy số và các trang sách đã photo qua cho Receiver rồi tiếp tục tính toán những cuốn sách khác.

3. Receiver

Nhận được dãy số của Sender, Receiver sẽ trả tiền xe ôm và bắt đầu đồng bộ hóa sách.

Dãy số cho biết rằng 1, 2, 3, 4, 5, 16, 101, 102, 103 là những trang đã bị thay đổi, nên Receiver sẽ xé những trang đó trong cuốn sách của mình, và dán những trang tương ứng vào.

Như thế, một cuốn sách đã được đồng bộ xong mà không cần phải tốn quá nhiều công sức để in hết hàng trăm trang trong sách.

Thực tế

Thật vậy. Mô tả ở trên chính là cách rsync hoạt động.

Thư viện A và B ở đây chính là thư mục nguồn và đích (source and destination), sách ở đây chính là các tập tin (file).

Bí Kíp™ ở đây là rolling checksum, chính là cái lõi của rsync. Thuật toán tính checksum tất nhiên sẽ không đơn giản như "đếm từ", bạn có thể đọc thêm về nó ở đây.

Checksum của rsync bao gồm hai loại: yếu và mạnh, nếu checksum yếu trùng khớp, sender sẽ kiểm tra thêm checksum mạnh để chắc chắn hai phần của hai tập tin là giống nhau.

Thực tế thì các receiver sẽ không thao tác trực tiếp trên tập tin gốc của mình mà sẽ ghi vào một tập tin tạm. Điều này giúp đảm bảo tập tin gốc không bị hư hại trong trường hợp nảy sinh lỗi. Sau khi hoàn tác, tập tin tạm này sẽ được đổi tên để thay thế cho tập gốc.

Như bạn đã thấy, mô hình vận hành như thế mang lại cho rsync sự hiệu quả.

1. Đồng bộ hóa hai tập tin mà không cần phải sao chép toàn bộ từ A sang B mọi lúc.
2. Các phần của GRS hoạt động độc lập và không cản trở nhau, mọi giao tác đều thông qua trao đổi (qua bác xe ôm).

Bài viết này được dịch từ bài How to explain rsync to a six year old đăng trên blog của mình.

Bài viết nằm trong tuyển tập hardcore or $10 của nhóm Ruby Vietnam, là một phong trào học nhóm nhằm tìm hiểu các vấn đề chuyên sâu về công nghệ và lập trình. Bạn có thể tham gia vào nhóm theo hướng dẫn tại đây.