Sistem Basisdata Pert23

Basisdata Terdistributsi (Distributed Databases) –Pemrosesan Query Terdistribusi

1

Basisdata Terdistribusi Pemrosesan 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 2 local cost dan shipping cost

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.

3

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.

4

Basisdata Terdistribusi Distributed 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 • 5

Basisdata Terdistribusi Optimisasi 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 masingmasing site – Jika sebuah site dapat memperbaiki suggested-local-plan, maka site tersebut bebas melakukannya.

6

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.

7

Basisdata Terdistribusi Distributed 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 8 lama)

Basisdata Terdistribusi Two-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: – Coordinator mengirimkan prepare msg ke masing-masing subordinat – Subordinate menuliskan sebuah abort atau prepare log record dan mengirim sebuah no atau yes msg ke coordinator. – 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. – Subordinate menuliskan abort/commit log record berdasarkan msg yang mereka terima, kemudian mengirimkan ack msg ke coordinator. – Coordinator menuliskan end log record setelah mendapatkan semua ack.

9

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 10

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.

11