Algoritma Rsync
by Andrew Tridgell
rsync adalah program utilitas yang berfungsi untuk mensinkronkan dua buah file yang terdapat pada dua buah tempat (komputer) yang terhubung dengan koneksi low bandwith dan high latency. Rsync hanya akan mengirim perubahan data saja dari suatu file terhadap file yang akan disinkronkan.
Jika terpadat dua komputer yang terhubung yaitu A dan B. Terdapat file dengan byte-byte ai pada A dan file dengan byte-byte bi pada B. Dengan asumsi 0<=i<=n, sehingga ukuran masing2 file adalah n.
Dasar algoritmanya dapat dijelaskan sebagai berikut:
Satu hal yang penting dalam algoritma rsync yaitu, pencocokan blok harus dapat di lakukan walaupun terjadi perpindahan offset dari blok file pertama pada file kedua. Hal ini dimaksudkan agar apa bila terjadi penyisipan byte, block signature yang telah dihasilkan tetap dapat dicarikan kesesuainya, sehingga kasus penyisipan byte tidak akan mengakibatkan dianggapnya terjadi berubahan pada seluruh isi file.
Dengan menggunakan dua macam block signature tersebut, algoritma rsync dapat dijelaskan secara lebih detail sebagai berikut, jika R dan H adalah block signature:
Terdapat penjelasan lagi tentang algoritma yang digunakan untuk menghasilkan dua jenis signature, cepat dan kuat, serta pencarian kecocokan blok. Selengkapnya dapat di lihat di thesis Andrew.
Pertanyaannya apakah algoritma ini dapat digunakan untuk sinkronisasi database ?? Seperti yang pernah ku bayangkan itu.
rsync adalah program utilitas yang berfungsi untuk mensinkronkan dua buah file yang terdapat pada dua buah tempat (komputer) yang terhubung dengan koneksi low bandwith dan high latency. Rsync hanya akan mengirim perubahan data saja dari suatu file terhadap file yang akan disinkronkan.
Jika terpadat dua komputer yang terhubung yaitu A dan B. Terdapat file dengan byte-byte ai pada A dan file dengan byte-byte bi pada B. Dengan asumsi 0<=i<=n, sehingga ukuran masing2 file adalah n.
Dasar algoritmanya dapat dijelaskan sebagai berikut:
- B mengirim beberapa data S berdasarkan bi ke A.
- A mencocokkan S dengan ai, kemudian mengirim D ke B.
- B membuat file baru menggunakan bi, S dan D.
Satu hal yang penting dalam algoritma rsync yaitu, pencocokan blok harus dapat di lakukan walaupun terjadi perpindahan offset dari blok file pertama pada file kedua. Hal ini dimaksudkan agar apa bila terjadi penyisipan byte, block signature yang telah dihasilkan tetap dapat dicarikan kesesuainya, sehingga kasus penyisipan byte tidak akan mengakibatkan dianggapnya terjadi berubahan pada seluruh isi file.
Dengan menggunakan dua macam block signature tersebut, algoritma rsync dapat dijelaskan secara lebih detail sebagai berikut, jika R dan H adalah block signature:
- B membagi bi dalam N blok dengan ukuran yang sama b'j, kemudian menghitung Rj dan Hj untuk setiap blok. Dua signature ini dikirim ke A.
- Untuk setiap offset byte i pada ai di A dihitung R'i pada blok yang dimulai dari i.
- A memcocokkan R'i yang sesuai untuk setiap Rj yang diterima dari B.
- Untuk setiap j yang R'i cocok dengan Rj, A menghitung H'i dan membandingkannya dengan Hj.
- Jika H'i sama dengan Hj maka A mengirim pesan ke B menunjukkan blok mana yang cocok dan dimana letaknnya,jika tidak ada kecocokan A mengirimkan byte literalnya ke B.
- B menerima byte literal dan token dari A dan menggunakannya untuk membuat ai.
- Algoritma penghasil signature cepat harus benar-benar cepat dan tidak memakan banyak sumber daya komputer.
- Signature kuat, harus memiliki probabilitas yang rendah untuk terjadinya kemungkinan dua blok data yang berbeda tetapi menghasilkan signature yang sama.
- Algoritma pencarian dan pencocokan blok harus cepat dan efesien.
Terdapat penjelasan lagi tentang algoritma yang digunakan untuk menghasilkan dua jenis signature, cepat dan kuat, serta pencarian kecocokan blok. Selengkapnya dapat di lihat di thesis Andrew.
Pertanyaannya apakah algoritma ini dapat digunakan untuk sinkronisasi database ?? Seperti yang pernah ku bayangkan itu.
