Thursday, February 18, 2010

ROAR: Optimasi Pencarian yang Terdistribusi


[Author: Nur Ibrahim] Untuk mencari suatu jaringan dengan cepat, mesin pencari memisahkan(mempartisi) index/daftar jaringan ke dalam banyak mesin, dan memeriksa setiap partisi saat menjawab pertanyaan. Figure 1 mengilustrasikan konsep dasar dari algoritma Rendezvous. Server dibagi kedalam cluster-cluster dan tiap data item yang dicari akan direplikasi ke semua mesin yang ada dalam satu cluster. Kemudian, pertanyaan dikirim ke satu mesin dari tiap cluster untuk meyakinkan bahwa pertanyaan tersebut berada pada/sesuai dengan indeks keseluruhan. Untuk meningkatkan throughput, replica dari mesin ini ditambahkan ke masing2 mesin. Parameter dari algoritma ini adalah trade-off antara proses replikasi dan proses mempartisi. Meningkatkan level partisi akan meningkatkan waktu untuk menyelesaikan pertanyaan karena semakin banyak server yang menangani pertanyaan, namun akan mendatangkan biaya awal yang tidak dapat diabaikan untuk masing-masing sub pertanyaan. Menemukan titik pengoperasian yang tepat dan mengadaptasikannya akan meningkatkan performansi secara signifikan dan akan mengurangi biaya.



Rendezvouz On a Ring (ROAR) adalah sebuah algoritma pendistribusian baru yang memungkinkan proses re-konfigurasi level partisi saat “masih mengudara”. ROAR dapat menambahkan dan mengurangi server yang ada tanpa harus menghentikan sistem terlebih dahulu, menanggulangi kerusakan pada server, dan memberikan keseimbangan beban trafik yang baik, meskipun dengan server yang banyak dan heterogen. ROAR menggunakan continuous circular ID space. Ide dasarnya adalah, jika diberikan level partisi p, ROAR menyimpan tiap objek pada server yang berada pada range yang berukuran 1/p pada ring (figure 2). Untuk proses mencari, ROAR memilih secara acak, titik awal pada ring dan meneruskan tiap pertanyaan ke titik-titik yang berjarak p pada ring. ROAR menyimpan data item pada ring yang memiliki r server. Hal ini akan memungkin kita untuk menggandakan routing pertanyaan dari server identifier.

    Share | Save

    Subscribe

1 comment:

Wahyu said...

pada suatu sistem terdistribusi, apalagi dengan database yang besar, pencarian dan indexing sering menjadi permasalahan utama. semakin besar database, pencarian akan memakan waktu yang lama. dengan adanya indexing, pencarian dapat dilakukan dengan lebih cepat, tetapi semakin besar index, beban sistem akan semakin besar, sehingga suatu saat kinerja sistem akan menjadi tidak optimal. dengan menggunakan ROAR hal ini mungkin dapat ditanggulangi. apakah dengan pengembangan lebih lanjut, algoritma ini dapat digunakan dalam managemen trafik? jadi aplikasinya tidak sebatas pada trafik pencarian saja.

Post a Comment