1

Basisdata Terdistributsi Basisdata Terdistributsi (Distributed Databases)(Distributed Databases)Basisdata Terdistributsi Basisdata Terdistributsi (Distributed Databases)(Distributed Databases)

–Pemrosesan Query Terdistribusi

2

Basisdata TerdistribusiPemrosesan Query Terdistribusi•Dalam basisdata terdistribusi query sederhana sekalipun (tidak melibatkan join) perlu penanganan khusus.•E.g.

SELECT AVG(S.age) FROM Sailors S WHERE S.rating > 3 AND S.rating < 7

•Query di atas diproses dengan tiga cara yang berbeda bergantung pada kondisi data.•Jika

– Data di-fragmentasi secara horisontal, misal tuple dengan rating < 5 di Shanghai dan tuple >= 5 di Tokyo• Untuk menghitung SUM(age), COUNT(age) dilakukan di dua

site.• Jika kondisi WHERE hanya menghasilkan tuple dengan

s.rating>6, hanya dilakukan di satu site (Tokyo)– Data di-fragmentasi vertikal: misal sid dan rating di Shanghai,

sname dan age di Tokyo, tid di keduanya.• Harus merekonstruksi kembali relasi dengan melakukan join

pada tid, kemudian baru mengevaluasi query– Di-replikasi: Tabel sailor ada di dua site.

• Pilihan site mana yang mengeksekusi query berdasar pada local cost dan shipping cost

3

Basisdata Terdistribusi

Distributed Join•Misal kita punya dua buah relasi Sailors= 500 page terdapat di London, Reserves=1000 page terdapat di Paris•Jika akan dilakukan distributed join, maka dapat dilakukan dengan empat pendekatan:

• Fetch as Needed • Ship to One site• Semijoin• Bloomjoin

• Fetch as Needed, misalnya dilakukan dengan page nested-loop join, sailors sebagai outer:

– Cost: 500 D + 500 * 1000 (D+S) (nr * Bs + br)– D adalah cost untuk membaca/menulis page; S adalah

cost untuk mengirimkan (ship) page– Jika query tidak dilakukan di London maka harus

ditambah biaya untuk mengirimkan hasilnya ke tempat query tersebut dilakukan

– Dapat juga dilakukan dengan Indeks Nested Loop join di London, mengambil tuple Reserves yang cocok dari Paris ke London ketika diperlukan.

4

Basisdata Terdistribusi

Distributed Join• Ship to One Site: kirimkan (ship) Reserves ke London, lakukan join

di sana, misalnya dilakukan dengan sort merge join– Cost: 1000 S (cost shipping) + 3*(500+1000) (cost join)

(br+bs+cost sorting) – Jika relasi yang akan dihasilkan berukuran sangat besar, lebih

baik jika mengirimkan kedua relasi ke result site (site yang melakukan query) kemudian melakukan join di sana.

• Semi Join: Dilakukan dalam beberapa tahap– Di London, lakukan operasi project pada relasi Sailors terhadap

join-columns dan kirimkan hasilnya ke Paris.– Di Paris, lakukan operasi join terhadap hasil proyeksi Sailors tadi

dengan Reserves.– Hasilnya disebut sebagai relasi Reserves yang sudah direduksi oleh Sailors.

– Kirimkan kembali relasi yang sudah direduksi tersebut ke London.

– Di London, lakukan operasi join antara Sailors dengan Reserves yang sudah direduksi tadi.

– Idenya adalah menghitung tradeoff cost komputasi dan shipping proyeksi dengan cost mengirimkan seluruh relasi Reserves secara full.

– Terutama berguna jika ada operasi seleksi pada Sailors, dan jawaban diinginkan di London.

5

Basisdata TerdistribusiDistributed Join (lanjt)• Bloom Join, dilakukan dalam beberapa tahap:• Di London, hitung suatu nilai bit-vector untuk nilai k tertentu:

– Lakukan operasi hashing terhadap join-columns ke dalam nilai yang berkisar antara 0 sampai k-1.

– Jika beberapa tuple setelah dilakukan hash cocok dengan nilai yang ada dalam I, set bit I ke 1 (I berada dalam kisaran 0 sampai k-1)

– Kirimkan bit-vector ke Paris.• Di Paris, lakukan operasi hash masing-masing tuple Reserves

dengan cara yang sama, dan musnahkan tuple-tuple yang mempunyai nilai bit-vector 0, lakukan operasi join untuk kedua bit-vector tersebut.–Dari hasil join bit-vector tersebut, didapatkan relasi Reserves yang sudah direduksi dengan melihat bit-vector hasil join.

• Kirimkan Reserves yang sudah direduksi ini kembali ke London.• Di London, lakukan operasi Join Sailors dengan Reserves yang

sudah dikurangi tersebut• Secara umum cost-nya lebih murah dari Semijoin

6

Basisdata TerdistribusiOptimisasi Query Terdistribusi • Dilakukan dengan pendekatan Cost-based;

memperhitungkan semua plan, memilih yang paling murah, mirip dengan optimisasi pada basisdata terpusat (konvensional). Tetapi terdapat beberapa perbedaan:– Perbedaan 1: ongkos komunikasi harus ikut

dipertimbangkan– Perbedaan 2: Otonomi masing-masing lokal site harus

diperhitungkan– Perbedaan 3: Terdapat metode-metode baru dalam

distributed join• Site yang melakukan query membangun global plan,

dengan dilengkapi oleh suatu suggested-local-plan yang menggambarkan pemrosesan secara detail pada masing-masing site – Jika sebuah site dapat memperbaiki suggested-local-plan,

maka site tersebut bebas melakukannya.

7

Basisdata Terdistribusi

Distributed Locking • Bagaimana kita mengatur lock untuk objek-objek yang tersebar di banyak tempat (site)?•Terdapat tiga pendekatan:

– Centralized– Primary Copy– Fully Distributed

•Centralized: Satu site bertanggung jawab untuk melakukan semua locking, sangat rentan terhadap single site failure •Primary Copy: Semua locking untuk suatu objek dilakukan di primary copy site untuk objek ini. •Fully Distributed: Locking dilakukan di tempat di mana copy (data) tersebut disimpan.

8

Basisdata TerdistribusiDistributed Deadlock Detection• Masing-masing site memelihara local waits-for

graph.• Global deadlock bisa terjadi bahkan jika tidak

terdapat cycles di local graph

• Terdapat tiga solusi untuk mendeteksi deadlock: – Cetralized (mengirim semua local graph ke satu site)– Hierarchical (mengatur site-site menjadi suatu hierarki dan

mengirim local graph ke site yang merupakan parent di hierarki tersebut)

– Timeout (lakukan abort jika transaksi menunggu terlalu lama)

9

Basisdata TerdistribusiTwo-Phase Commit (2PC)• Pada saat terjadi suatu transaksi site di mana transaksi

berawal di sebut coordinator, dan site yang lain yang terlibat karena transaksi tersebut disebut subordinat

• Terdapat langkah-langkah yang dilakukan jika suatu transaksi akan commit:1. Coordinator mengirimkan prepare msg ke masing-

masing subordinat2. Subordinate menuliskan sebuah abort atau prepare

log record dan mengirim sebuah no atau yes msg ke coordinator.

3. Jika coordinator mendapat suara sepakat yes, maka tuliskan commit log record dan kirim commit msg ke semua subordinat. Jika tidak, tuliskan abort log record, dan kirimkan abort msg.

4. Subordinate menuliskan abort/commit log record berdasarkan msg yang mereka terima, kemudian mengirimkan ack msg ke coordinator.

5. Coordinator menuliskan end log record setelah mendapatkan semua ack.

10

Basisdata Terdistribusi

Komentar Mengenai 2PC• Terdapat dua rentetan komunikasi: pertama,

voting; kemudian, pemutusan. Keduanya diawalai oleh coordinator.

• Site manapun dapat memutuskan abort terhadap suatu transaksi.

• Setiap msg mencerminkan sebuah keputusan dari pengirimnya; untuk menjaga agar keputusan ini tetap ada walaupun terjadi failure, maka pertama kali keputusan ini dituliskan di local log.

• Semua log record untuk suatu transaksi mengandung id-transaksi dan id-coordinator. Record abort/commit coordinator juga mengandung semua id sub-ordinat-nya

11

Basisdata Terdistribusi

Recovery Setelah Terjadi Failure pada Satu Site• Jika kita mempunyai sebuah commit atau abort log

record untuk transaksi T, tetapi tidak mempunyai end record, maka harus dilakukan undo/redo terhadap T.– Jika site ini adalah coordinator untuk T, maka teruslah mengirim commit/abort msg ke semua subordinat sampai semua ack diterima

• Jika kita mempunyai sebuah prepare log record untuk transaksi T, tetapi tidak mempunyai commit/abort, maka site ini adalah subordinate untuk T– Secara berulang-ulang hubungi coordinator untuk

menemukan status transaksi T, kemudian tulis commit/abort log record; redo/undo T; dan tulis end log record.

• Jika kita tidak mempunyai bahkan sebuah prepare log record untuk T, langsung lakukan abort dan undo terhadap T.