Sistem Basisdata Pert25

Basisdata Paralel (Parallel Databases) –Konsep Basisdata Paralel (lanjt) –Perbandingan Basisdata Paralel dengan Terdistribusi 1

Basisdata Paralel Inter-query parallelism (scale-up) •Query-query/Transaksi-transaksi dijalankan secara paralel satu sama lain. •Meningkatkan throughput transaksi; digunakan utamanya untuk menambah (scale-up) sistem pemrosesan transaksi sehingga meningkatkan jumlah transaksi yang dapat diproses per satuan waktunya. •Merupakan bentuk paralelisme yang paling mudah diimplementasikan, khususnya pada basisdata paralel sharedmemory, karena pada dasarnya sistem basisdata sequensial (konvensional) pun mendukung pemrosesan concurrent. •Lebih rumit jika diterapkan pada arsitektur shared-disk atau shared-nothing – Locking dan logging harus dikoordinasikan dengan cara saling bertukar pesan antar prosesor. – Data pada local buffer mungkin sedang/telah di-update oleh prosesor yang lain. – Harus menjaga Cache-coherency— pembacaan dan penulisan terhadap data harus dilakukan pada versi 2 data paling akhir.

Basisdata Paralel Protokol Cache-Coherency •Contoh protokol cache coherency untuk sistem basisdata paralel shared-disk: – Sebelum membaca/menulis ke sebuah page, page tersebut harus di-lock dalam modus shared/exclusive. – Tepat setelah me-lock sebuah page, maka page tersebut di baca dari disk – Sebelum melepas lock (unlock) sebuah page, page harus dituliskan ke disk jika page tersebut diubah. •Terdapat protokol yang lebih kompleks yang dapat mengurangi pembacaan/penulisan disk. – Protokol ini tidak menulis ke suatu page jika exclusive lock sudah dilepaskan. – Jika suatu exclusive/shared lock sedang dipegang, maka akan dilakukan pengecekan apakah page yang sekarang dipegang oleh buffer pool merupakan versi paling akhir, jika ya maka pembacaan cukup dilakukan dari sana. •Protokol Cache coherency untuk arsitektur shared-nothing mempunyai karakteristik yang mirip dengan arsitektur shareddisk. Perbedaannya adalah pada masing-masing page database 3 ditunjuk sebuah home processor. Permintaan untuk mengakses/menulis sebuah page dikirim ke home processor.

Basisdata Paralel Intraquery Parallelism (speed-up) • Eksekusi sebuah query tunggal secara paralel pada beberapa prosesor/disk; penting untuk mempercepat (speed-up) query yang berjalan lama. • Terdapat dua bentuk yang saling melengkapi untuk paralelisme seperti ini: – Intraoperation Parallelism – memparalelkan eksekusi masing-masing operasi dalam sebuah query. – Interoperation Parallelism – mengeksekusi operasi-operasi yang berbeda dalam sebuah ekspresi query secara paralel. • Bentuk pertama dapat memberikan tingkat paralelisme yang lebih baik dari yang kedua, karena biasanya jumlah tupel yang diproses oleh masingmasing operasi lebih banyak daripada jumlah operasi dalam suatu query.

4

Basisdata Paralel Pemrosesan Paralel Terhadap Operasi-operasi Relasional •Dalam pembahasan mengenai algoritma-algoritma paralel ini terdapat beberapa asumsi: – Query yang dilakukan bersifat read-only – Menggunakan arsitektur shared-nothing – Terdapat n prosesor, dinyatakan oleh P0, ..., Pn-1, dan n disks D0, ..., Dn-1, di mana Di berasosiasi dengan prosesor Pi. •Jika sebuah prosesor mempunyai beberapa disk mereka dapat secara mudah diterapkan untuk mensimulasikan satu buah disk tunggal Di yang merupakan sekumpulan disk. •Arsitektur shared-nothing dapat secara efisien disimulasikan pada sistem berarsitektur shared-memory dan shared-disk, karena transfer data dapat dilakukan oleh shared-memory dalam arsitektur shared-memory dan shared-disk dalam arsitektur shared-disk. – Algoritma-algoritma untuk sistem-sistem sharednothing oleh karenanya dapat dijalankan pada sistem- 5 sistem berarsitektur shared-memory dan shared-disk

Basisdata Paralel Parallel Sort Untuk melakukan operasi pengurutan (sorting) secara paralel terdapat dua cara: – Range-Partitioning Sort – Parallel External Sort-Merge •Range-Partitioning Sort – Pilihlah prosesor P0, ..., Pm, di mana m ≤ n -1 untuk melakukan sorting. – Buatlah range-partition-vector dengan m anggota, pada atribut sorting – Distribusi ulang relasi menggunakan range-partitioning • Semua tuple yang berada di antara range ke-i dikirim ke prosesor Pi •Pi menyimpan tuple yang diterimanya sementara di disk Di. – Masing-masing prosesor Pi mengurutkan partisi relasi secara lokal. – Masing-masing prosesor melakukan operasi (sorting) yang sama secara paralel dengan prosesor yang lain, tanpa adanya interaksi satu sama lain (data parallelism). – Pada akhirnya operasi penggabungan hasil pengurutan tadi dilakukan dengan mudah: operasi range-partitioning menjamin bahwa, untuk 1<=i<=j<= m, nilai key dalam prosesor Pi semuanya

6

Basisdata Paralel •Parallel External Sort-Merge – Asumsi bahwa relasi telah dipartisi di antara disk-disk D0, ..., Dn-1 (dengan cara apapun). – Masing-masing prosesor Pi secara lokal mengurutkan data pada disk Di. – Hasil operasi pengurutan yang dilakukan di masing-masing prosesor kemudian digabungkan untuk mendapat hasil pengurutan akhir. – Untuk menggabungkan hasil pengurutan masing-masing prosesor tadi secara paralel dilakukan sebagai berikut: • Partisi-partisi yang sudah diurutkan di masing-masing prosesor Pi kemudian di-rangepartitioning ke seluruh prosesor P0, ..., Pm-1. • Masing-masing prosesor Pi melakukan pengabungan dengan serangkaian data yang sudah terurut tadi pada saat mereka diterima, untuk memperoleh satu rangkaian penuh yang terurut. • Rangkaian yang sudah terurut pada prosesor-prosesor P0,...,

7

Basisdata Paralel Parallel Join • Operasi join membutuhkan pasangan tuple-tuple untuk dites apakah mereka memenuhi kondisi join, dan jika mereka memenuhi kondisi tersebut, pasangan tersebut kemudian ditambahkan ke hasil join. • Algoritma parallel join mencoba memisahkan pasangan tersebut untuk dites di lebih dari satu prosesor. Masingmasing prosesor kemudian melakukan join secara lokal. • Pada langkah akhir, hasil dari masing-masing prosesor dapat digabungkan untuk memperoleh hasil akhir. • Parallel Join dilakukan dengan tiga cara: – Partitioned Join – Fragment and Replicate Join – Partitioned Parallel Hash Join 8 – Parallel Nested Loop Join

Basisdata Paralel Partitioned Join • Untuk equi-join dan natural join, dimungkinkan untuk memisahkan (mempartisi) dua relasi input di seluruh prosesor, dan menghitung join secara lokal di masing-masing prosesor. • Misalkan r dan s merupakan relasi-relasi input, dan kita ingin menghitung r r.A=s.B s. • r dan s masing-masing dipartisi menjadi n partisi, dinyatakan oleh r0, r1, ..., rn-1 dan s0, s1, ..., sn-1. • Dapat menggunakan baik range partitioning ataupun hash partitioning. • r dan s harus dipartisi berdasarkan join atributnya (r.A dan s.B), menggunakan range-partitioning vector yang sama atau fungsi hash yang sama. • Partisi-partisi ri dan si dikirim ke prosesor Pi, • Masing-masing prosesor Pi secara lokal menghitung ri ri.A=si.B si. Dapat menggunakan metode join standar apa pun.

9

Basisdata Paralel Partitioned Join (lanjt)

10

Basisdata Paralel Fragment-and-Replicate Join • Algoritma join yang dilakukan jika partitioned-join tidak bisa menangani join yang dimaksud – e.g., kondisi-kondisi non-equijoin, seperti r.A > s.B. • Untuk join di mana tidak bisa dilakukan algoritma partitioned-join ini join masih dapat diparalelkan dengan menerapakan teknik fragment and replicate – Digambarkan dalam slide berikut • Terdapat kasus khusus– asymmetric fragment-andreplicate: – Salah satu relasi, misalnya r, dipartisi; dapat menggunakan teknik partitioning yang manapun (termasuk round-robin) – Relasi yang lain, s, direplikasi ke seluruh prosesor. – Prosesor Pi kemudian secara lokal menghitung join ri dengan semua s menggunakan teknik join 11 apa pun.

Basisdata Paralel Fragment-and-Replicate Join (lanjt)

12

Basisdata Paralel Fragment-and-Replicate Join (lanjt) • Karakteristik umum: mengurangi ukuran relasirelasi yang di-join-kan di masing-masing prosesor. – r dipartisi menjadi n partisi, r0, r1, ..., r n-1; s dipartisi menjadi m partisi, s0, s1, ..., sm-1. – Dapat menggunakan teknik partitioning apa pun. – Harus ada sedikitnya m * n prosesor. – Beri nama prosesor-prosesor tersebut sebagai P0,0, P0,1, ..., P0,m-1, P1,0, ..., Pn-1m-1. – Pi,j menghitung join untuk ri dengan sj. Untuk melakukan hal ini, ri direplikasi ke Pi,0, Pi,1, ..., Pi,m-1, sementara si direplikasi menjadi P0,i, P1,i, ..., Pn-1,i – Dapat menggunakan teknik join apa pun di prosesor Pi,j tersebut.

13

Basisdata Paralel Fragment-and-Replicate Join (lanjt) • Kedua versi fragment-and-replicate (asymmetric & Symmetric/general) dapat bekerja dengan kondisi join apa pun, karena masing-masing tuple pada r dapat dites dengan semua tuple di s. • Biasanya memiliki cost yang lebih tinggi dari partitioned-join, karena salah satu relasi (pada asymmetric) atau kedua relasi (pada symmetric/general fragment-and-replicate) harus direplikasi. • Untuk beberapa kondisi tertentu asymmetric fragment-and-replicate lebih disukai dari partitionedjoin. – E.g., jika s merupakan relasi yang kecil dan r relasi yang berukuran besar, dan sudah dipartisi. Akan lebih murah untuk melakukan replikasi s ke seluruh prosesor, daripada mempartisi ulang r dan s berdasarkan atribut join.

14

Basisdata Paralel Partitioned parallel hash join: • Asumsi s lebih kecil dari r sehingga s dipilih sebagai build relation. • Sebuah fungsi hash h1 mengambil nilai join atribut untuk masing-masing tuple pada s dan memetakan tuple ini ke salah satu dari n prosesor. • Masing-masing prosesor Pi membaca tuple-tuple s yang ada pada disknya Di, dan mengirimkan masingmasing tuple ke prosesor yang bersesuaian berdasarkan fungsi hash h1. Misalkan si menyatakan tuple-tuple relasi s yang dikirim ke prosesor Pi. • Pada saat tuple-tuple s diterima oleh prosesorprosesor tujuan, mereka dipartisi lebih lanjut menggunakan fungsi hash yang lain, h2, yang digunakan untuk menghitung hash-join secara lokal.(lanjt.)

15

Basisdata Paralel Partitioned parallel hash join (lanjt) • Sekali tuple-tuple s telah didistribusikan, relasi yang lebih besar r didistribusi ulang ke seluruh m prosesor menggunakan fungsi hash h1 – Misalkan ri menyatakan tuple-tuple relasi r yang dikirim ke prosesor Pi. • Pada saat tuple-tuple r diterima di prosesor tujuan, mereka dipartisi ulang menggunakan fungsi h2 – (sebagaimana halnya probe relation dipartisi dalam algoritma hash-join sekuensial). • Masing-masing prosesor Pi mengeksekusi fase build dan probe dari algoritma hash-join pada partisi lokal ri dan si dari relasi r dan s untuk menghasilkan relasi akhir hashjoin. • Catatan: Optimisasi-optimisasi Hash-join dapat diterapkan pada kasus paralel – e.g., algoritma hybrid hash-join dapat digunakan untuk menampung (cache) beberapa tuple yang masuk ke 16 dalam memory dan mencegah ongkos menuliskan dan membaca mereka kembali.

Basisdata Paralel Parallel Nested-Loop Join • Asumsi bahwa – Relasi s jauh lebih kecil dari relasi r dan r disimpan dengan partitioning. – Terdapat indeks pada atribut join untuk relasi r pada masing-masing partisi relasi r. • Menggunakan asymmetric fragment-and-replicate, dengan relasi s merupakan relasi yang direplikasi, dan menggunakan partisi relasi r yang sudah ada. • Masing-masing prosesor Pj di mana sebuah relasi s disimpan membaca tupel-tupel relasi s yang disimpan di Dj, dan me-replikasi tupel-tupel ke setiap prosesor Pi. – Pada akhir fase ini, relasi s direplikasi di semua site yang menyimpan tupel-tupel relasi r. • Masing-masing prosesor Pi melakukan indexed 17 nested-loop join terhadap relasi s dengan partisi

Basisdata Paralel Cost Operasi Paralel • Jika tidak ada skew pada saat melakukan partitioning, dan tidak ada biaya tambahan karena evaluasi paralel, maka speed-up yang bisa diharapkan dari operasi paralel adalah 1/n • Jika skew juga biaya tambahan tadi diperhitungkan, waktu yang diambil oleh operasi paralel dapat diperkirakan sebagai Tpart + Tasm + max (T0, T1, …, Tn-1)

– Tpart adalah waktu untuk melakukan partitioning relasi – Tasm adalah waktu yang diperlukan untuk menyusun kembali (assemble) relasi hasil. – Ti adalah waktu yang digunakan untuk pemrosesan oleh masing-masing prosesor

18

Basisdata Paralel Interoperation Parallelism Terdapat dua bentuk interoperation parallelism: – Pipelined Parallelism – Independent Parallelism • Pipelined parallelism – Misalnya kita akan melakukan join terhadap empat relasi r1 r2 r 3 r4 – Buatlah sebuah pipeline yang menghitung ketiga join tersebut secara paralel • Misalnya P1 ditunjuk untuk menghitung temp1 = r1 r2 • Dan P2 ditunjuk untuk menghitung temp2 = temp1 r3 r4 • Dan P3 ditunjuk untuk menghitung temp2 – Masing-masing operasi ini dapat dijalankan secara paralel, mengirimkan tuple hasil yang dihitungnya ke operasi berikutnya bahkan pada saat sedang dihitung hasil untuk operasi berikutnya

19

Basisdata Paralel Faktor-faktor yang membatasi penggunaan Pipelined Parallelism • Pipeline parallelism berguna karena menghindari penulisan hasil antara ke disk • Berguna jika prosesor yang digunakan tidak terlalu banyak, tetapi tidak memberi hasil yang sebanding (scale-up) dengan penggunaan banyak prosesor. Salah satu alasannya adalah karena rantai pipeline tidak mencapai panjang yang cukup (terhadap jumlah prosesor yang digunakan). • Ada beberapa operator yang tidak menghasilkan keluaran sampai semua inputnya telah diakses (sehingga tidak bisa di-pipeline) contohnya, operasi aggregate dan sort.  • Peningkatan kecepatan yang tidak terlalu besar diperoleh (marginal speedup) karena ada salah satu operator yang ongkos eksekusinya jauh lebih tinggi 20 dari yang lain.

Basisdata Paralel • Independent parallelism – Misalnya kita akan melakukan join terhadap empat relasi r1 r2 r3 r4 • Misalkan P1 ditunjuk untuk menghitung temp1 = r1 r2 • Dan P2 ditunjuk untuk menghitung temp2 = r3 r4 • Dan P3 ditunjuk untuk menghiting temp1 temp2 • P1 dan P2 dapat bekerja paralel secara terpisah • P3 harus menunggu input dari P1 dan P2 – Dapat melakukan pipeline terhadap output P1 dan P2 ke P3, menggabungkan independent parallelism dan pipelined parallelism – Tidak memberikan derajat paralelisme yang tinggi • Berguna untuk derajat paralelisme rendah • Kurang berguna jika sistem merupakan sistem yang memiliki tingkat paralelisme tinggi.

21

Basisdata Paralel Parallel Query Optimization • Pendekatan umum: 2 tahap – Pilih sequential plan terbaik (algoritma System R) – Pilih tingkat paralelisme berdasarkan parameter sistem saat ini • “Lekatkan” masing-masing operator pada prosesor-prosesor – Buatlah query tree, beri tanda seperti pada gambar di bawah • Dilakukan pertama kali di Berkeley

Sites 1-8 Sites 1-4 A

Sites 5-8 B

R

S

22

Basisdata Paralel Perancangan Sistem Paralel Beberapa pokok permasalahan yang harus diperhatikan dalam merancang sistem paralel: • Pemasukan data secara paralel dari sumber eksternal diperlukan untuk menangani data masuk yang berukuran besar. • Ketahanan terhadap failure pada beberapa prosesor atau disk. – Kemungkinan beberapa disk atau prosesor tidak berfungsi (fail) lebih besar dalam sistem paralel. – Operasi (mungkin dengan performansi yang menurun) harus bisa dilakukan jika terjadi failure. – Redundancy diperoleh dengan cara menyimpan 23 ekstra copy untuk setiap data di prosesor lain.

Basisdata Paralel • Harus mendukung reorganisasi data dan skema secara on-line. – Sebagai contoh, pembangunan indeks dalam basisdata berukuran terabyte dapat memakan waktu berjam-jam atau bahkan berhari-hari pada sistem paralel. • Harus memungkinkan pemrosesan yang lain (insertion/deletion/update) untuk dilakukan bahkan pada saat indeks sedang dibangun. • Ide dasar: pada saat membangun indeks proses tersebut juga melacak perubahan-perubahan yang terjadi pada saat pembangunan tersebut kemudian di akhir perubahan tersebut diterpakan pada indeks yang baru saja dibangun. • Juga harus mendukung partisi ulang dan perubahanperubahan terhadap skema secara on-line (yang dieksekusi secara bersamaan dengan proses yang lain).

24

Basisdata Paralel

Perbandingan Basisdata Paralel dengan Terdistribusi

• Conclude your self you’re grown up guys!!!

25