sistem basisdata pert25

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

Upload: api-3806259

Post on 07-Jun-2015

317 views

Category:

Documents


5 download

TRANSCRIPT

Page 1: Sistem Basisdata Pert25

1

Basisdata Paralel Basisdata Paralel (Parallel Databases)(Parallel Databases)Basisdata Paralel Basisdata Paralel

(Parallel Databases)(Parallel Databases)

–Konsep Basisdata Paralel (lanjt)–Perbandingan Basisdata Paralel dengan Terdistribusi

Page 2: Sistem Basisdata Pert25

2

Basisdata ParalelInter-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 shared-memory, 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 data paling akhir.

Page 3: Sistem Basisdata Pert25

3

Basisdata ParalelProtokol 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 shared-disk. Perbedaannya adalah pada masing-masing page database ditunjuk sebuah home processor. Permintaan untuk mengakses/menulis sebuah page dikirim ke home processor.

Page 4: Sistem Basisdata Pert25

4

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 masing-masing operasi lebih banyak daripada jumlah operasi dalam suatu query.

Page 5: Sistem Basisdata Pert25

5

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 shared-nothing oleh karenanya dapat dijalankan pada sistem-sistem berarsitektur shared-memory dan shared-disk

Page 6: Sistem Basisdata Pert25

6

Basisdata ParalelParallel SortUntuk 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 lebih kecil dari nilai key pada Pj.

Page 7: Sistem Basisdata Pert25

7

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,..., Pm-1 kemudian digabungkan untuk memperoleh hasil akhir.

Page 8: Sistem Basisdata Pert25

8

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. Masing-masing 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– Parallel Nested Loop Join

Page 9: Sistem Basisdata Pert25

9

Basisdata ParalelPartitioned 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.

Page 10: Sistem Basisdata Pert25

10

Basisdata Paralel

Partitioned Join (lanjt)

Page 11: Sistem Basisdata Pert25

11

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-and-replicate:– 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 apa pun.

Page 12: Sistem Basisdata Pert25

12

Basisdata Paralel

Fragment-and-Replicate Join (lanjt)

Page 13: Sistem Basisdata Pert25

13

Basisdata Paralel

Fragment-and-Replicate Join (lanjt) • Karakteristik umum: mengurangi ukuran relasi-

relasi 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.

Page 14: Sistem Basisdata Pert25

14

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 di-replikasi.

• Untuk beberapa kondisi tertentu asymmetric fragment-and-replicate lebih disukai dari partitioned-join.– 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.

Page 15: Sistem Basisdata Pert25

15

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 masing-masing 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 prosesor-prosesor tujuan, mereka dipartisi lebih lanjut menggunakan fungsi hash yang lain, h2, yang digunakan untuk menghitung hash-join secara lokal.(lanjt.)

Page 16: Sistem Basisdata Pert25

16

Basisdata ParalelPartitioned 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 hash-join.

• 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 dalam memory dan mencegah ongkos menuliskan dan membaca mereka kembali.

Page 17: Sistem Basisdata Pert25

17

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

nested-loop join terhadap relasi s dengan partisi ke-i dari relasi r.

Page 18: Sistem Basisdata Pert25

18

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

Page 19: Sistem Basisdata Pert25

19

Basisdata ParalelInteroperation ParallelismTerdapat dua bentuk interoperation parallelism:

– Pipelined Parallelism– Independent Parallelism

• Pipelined parallelism– Misalnya kita akan melakukan join terhadap empat

relasir1 r2 r3 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

• Dan P3 ditunjuk untuk menghitung temp2 r4

– 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

Page 20: Sistem Basisdata Pert25

20

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 dari yang lain.

Page 21: Sistem Basisdata Pert25

21

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.

Page 22: Sistem Basisdata Pert25

22

Basisdata ParalelParallel 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

A B R S

Sites 1-4 Sites 5-8

Sites 1-8

Page 23: Sistem Basisdata Pert25

23

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 ekstra copy untuk setiap data di prosesor lain.

Page 24: Sistem Basisdata Pert25

24

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 perubahan-perubahan terhadap skema secara on-line (yang dieksekusi secara bersamaan dengan proses yang lain).

Page 25: Sistem Basisdata Pert25

25

Basisdata Paralel

Perbandingan Basisdata Paralel dengan Terdistribusi

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