Đồng bộ hóa dữ liệu

Đồng bộ hóa dữ liệu là quá trình trao đổi giữa các thông tin với nhau và đồng bộ hóa thông tin giữa hai nguồn dữ liệu theo thời gian. Ứng dụng của đồng bộ hóa dữ liệu rất đa dạng và phong phú, có thể là đồng bộ hóa tập tin, đồng bộ hóa cho PDA hay việc đồng bộ hóa đối với máy chủ khóa công cộng với nhau,...

PDA

Đối với các thiết bị cầm tay, quá trình đồng bộ hóa được thực hiện khi hai thiết bị được kết nối với nhau qua một giao diện như cổng USB, hoặc Bluetooth, cổng hồng ngoại, WLAN...

Sau khi kết nối, hai thiết bị sẽ tiến hành trao đổi dữ liệu để các dữ liệu đã được chọn sẽ đồng bộ như nhau. Nếu lần đầu, quá trình này khá lâu do phải chuyển nhiều dữ liệu. Các lần sau, phần mềm sẽ chỉ tìm kiếm để đồng bộ các thay đổi mà thôi.

Các phần dữ liệu hay được đồng bộ: danh bạ, lịch, ghi chú cá nhân, tập tin, v.v.

Để phục vụ cho quá trình đồng bộ hóa đối với các thiết bị cầm tay sử dụng hệ điều hành Windows Mobile, Microsoft luôn có các phần mềm miễn phí có thể tải từ trang chủ của hãng là ActiveSync, nay là MobileCentre (cho Windows Vista).

Cơ sở lý thuyết

Một số mô hình thuyết về đồng bộ hóa dữ liệu đã được công bố trong một số nghiên cứu khoa học, và vấn đề cơ bản của việc đồng bộ hóa liên quan đến bài toán mã hóa Slepian-Wolf của ngành lý thuyết thông tin. Các mô hình lý thuyết này được phân loại tùy theo việc chúng xem xét dữ liệu được đồng bộ hóa như thế nào.

Dữ liệu không có thứ tự

Bài toán đồng bộ hóa dữ liệu không có thứ tự (còn gọi là bài toán hòa hợp tập hợp - set reconciliation problem) được mô hình hóa thành cách tính mức chênh lệch đối xứng $S_{A}\oplus S_{B}=(S_{A}-S_{B})\cup (S_{B}-S_{A})$ giữa hai tập xa nhau $S_{A}$ và $S_{B}$ các số $b$ -bit.^[1] Một số cách xử lý tiêu biểu là:

Chuyển toàn bộ (wholesale transfer): Trong trường hợp này toàn bộ dữ liệu được truyền tới một nơi để tiến hành so sánh cục bộ.
Đồng bộ hóa theo dấu thời gian (timestamp synchronization): Trong trường hợp này mọi thay đổi đối với các dữ liệu được đánh dấu bằng các dấu thời gian (timestamp). Việc đồng bộ hóa được tiến hành bằng cách chép các dữ liệu có dấu thời gian mới nhất so với lần đồng bộ hóa trước đó.^[2]
Đồng bộ hóa kiểu toán học (mathematical synchronization): Trong trường hợp này dữ liệu được xem như những đối tượng toán học và đồng bộ hóa tương ứng với một quá trình xử lý toán học.^[1]^[3]^[4]

Dữ liệu được xếp thứ tự

Trong trường hợp này, hai chuỗi xa nhau $\sigma _{A}$ và $\sigma _{B}$ cần được hòa hợp với nhau. Thông thường, các chuỗi này được giả định là khác nhau tới một số cố định các sửa đổi nào đó (tức là các thao tác thêm, xóa, sửa các ký tự). Sau đó quá trình đồng bộ hóa dữ liệu là việc giảm dần khoảng cách sửa đổi giữa $\sigma _{A}$ và $\sigma _{B}$ , cho đến khi khoảng cách sửa đổi bằng không. Một số hướng đi cho vấn đề này có thể kể đến:

Microsoft Sync Framework
rsync
tách chuỗi (shingling) - tách các chuỗi thành các chuỗi con để đưa bài toán này về bài toán đồng bộ hóa dữ liệu không theo thứ tự.^[5]

Chú thích

^ ^a ^b Minsky, Y. (2003). Trachtenberg, A.; Zippel, R. “Set reconciliation with nearly optimal communication complexity”. Information Theory, IEEE Transactions on. 49 (9): 2213–2218. doi:10.1109/TIT.2003.815784. ISSN 0018-9448. Truy cập ngày 27 tháng 7 năm 2007.
^ “Palm developer knowledgebase manuals”. Bản gốc lưu trữ ngày 11 tháng 3 năm 2002. Truy cập ngày 3 tháng 9 năm 2008.
^ A. Trachtenberg. “Fast PDA Synchronization Using Characteristic Polynomial Interpolation” (PDF). IEEE INFOCOM 2002. D. Starobinski and S. Agarwal. doi:10.1109/INFCOM.2002.1019402.
^ Y. Minsky and A. Trachtenberg, Scalable set reconciliation, Allerton Conference on Communication, Control, and Computing, Oct. 2002
^ S. Agarwal (2006). V. Chauhan and A. Trachtenberg. “Bandwidth efficient string reconciliation using puzzles” (PDF). IEEE Transactions on Parallel and Distributed Systems. 17 (11): 1217–1225. doi:10.1109/TPDS.2006.148. Truy cập ngày 23 tháng 5 năm 2007.

Liên kết ngoài

[minksy-trachtenberg-zippel-1] Minsky, Y. (2003). Trachtenberg, A.; Zippel, R. “Set reconciliation with nearly optimal communication complexity”. Information Theory, IEEE Transactions on. 49 (9): 2213–2218. doi:10.1109/TIT.2003.815784. ISSN 0018-9448. Truy cập ngày 27 tháng 7 năm 2007.

[2] “Palm developer knowledgebase manuals”. Bản gốc lưu trữ ngày 11 tháng 3 năm 2002. Truy cập ngày 3 tháng 9 năm 2008.

[3] A. Trachtenberg. “Fast PDA Synchronization Using Characteristic Polynomial Interpolation” (PDF). IEEE INFOCOM 2002. D. Starobinski and S. Agarwal. doi:10.1109/INFCOM.2002.1019402.

[4] Y. Minsky and A. Trachtenberg, Scalable set reconciliation, Allerton Conference on Communication, Control, and Computing, Oct. 2002

[5] S. Agarwal (2006). V. Chauhan and A. Trachtenberg. “Bandwidth efficient string reconciliation using puzzles” (PDF). IEEE Transactions on Parallel and Distributed Systems. 17 (11): 1217–1225. doi:10.1109/TPDS.2006.148. Truy cập ngày 23 tháng 5 năm 2007.

[1]

[2]

[3]

[4]

[5]