Sistem Basisdata Pert24

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

Basisdata Paralel Latar Belakang •Dewasa ini mesin yang bekerja secara paralel sudah cukup lumrah dengan harga yang terjangkau – Terjadi penurunan harga terhadap perangkat keras utama komputer seperti microprocessor, memori dan disk •Sementara database tumbuh menjadi besar dengan cepat – Data transaksi yang berukuran besar dikumpulkan dan disimpan untuk kemudian dianalisis – Objek-objek multimedia seperti gambar semakin banyak yang disimpan di database •Sistem basisdata berskala besar kebanyakan digunakan untuk: – Menyimpan data berukuran besar – Memroses query decission-support yang memakan waktu lama (speed-up) – Menyediakan throughput yang tetap tinggi dengan response time yang tetap untuk pemrosesan 2 transaksi (scale-up)

Basisdata Paralel Kenapa mengakses data secara paralel? 1,000 x paralel hanya 1.5 menit untuk baca

pada 10 MB/s 1.2 hari untuk baca

Ba 1 Terabyte

nd

wi dt

1 Terabyte

h

10 MB/s Paralelisme:

membagi permasalahan besar menjadi beberapa yang lebih kecil untuk dipecahkan secara paralel 3

Basisdata Paralel Paralelisme Dalam Database • Data dapat dipecah ke dalam beberapa disk untuk melakukan paralel I/O. • Operasi-operasi relasional individual (misal., sort, join, aggregation) dapat dijalankan secara paralel – Data dapat dipartisi dan masing-masing prosesor dapat bekerja secara independen hanya pada partisi-nya saja

• Query yang berbeda dapat dijalankan secara paralel satu sama lain. Concurrency control harus menjaga agar tidak terjadi konflik. 4

Basisdata Paralel Paralelisme Dalam Database •

Paralelisme merupakan sesuatu yang lumrah (alami) dalam pemrosesan di DBMS – Pipeline parallelism: banyak mesin dengan masing-masing melakukan satu step (langkah) dalam proses yang multi-step. – Partition parallelism: banyak mesin melakukan hal yang sama terhadap data yang berbeda – Keduanya merupakan hal yang wajar dalam DBMS

Pipeline Partition

Any Sequential Program

Sequential Any Sequential Sequential Program

Any Sequential Program

Any Sequential Program

output dipecah dengan N cara, input digabung dengan M cara

5

Basisdata Paralel Paralelisme dalam Database • Mengurangi waktu yang dibutuhkan untuk meperoleh suatu relasi dari disk dengan melakukan pembagian (pemecahan) relasi pada beberapa disk • Partitioning Hanya dilakukan dengan Horizontal partitioning – tupel-tupel dari sebuah relasi dibagi-bagi di antara banyak disk sedemikian sehingga masing-masing tupel terletak pada satu disk • Teknik-teknik partitioning (Dik. banyaknya disk yang digunakan = n): Round-robin: – Mengirim tupel ke-i yang di-insert ke dalam suatu relasi ke disk i mod n Hash partitioning: – Pilih satu atau lebih atribut sebagai partiotioning atribut – Pilih fungsi hash h dengan kisaran nilai 0…n - 1 – Misalkan i menyatakan hasil fungsi hash h yang dilakukan terhadap sebuah tupel. Kirim tuple tersebet ke disk i. • Range partitioning: – Pilih salah satu atribut sebagai partitioning attribute. – Kemudian buat sebuah partitioning vector dalam bentuk [vo, v1, ..., vn-2] – Misalkan v merupakan nilai patitioning atribut untuk sebuah tuple. Tupel-tupel di mana vi ≤ vi+1 disimpan di disk I + 1. tupel-tupel dengan v < v0 disimpan di disk 0 dan tupel-tupel dengan v ≥ vn-2 disimpan di disk n-1. E.g., dengan partitioning vector [5,11], sebuah tupel dengan nilai partitioning atribut 2 akan masuk ke disk 0, sebuah tupel dengan nilai 8 akan masuk ke disk 1, dan tupel dengan nilai 20 akan masuk ke disk 2.

6

Basisdata Paralel Perbandingan Teknik-teknik partitioning •Untuk membandingkan teknik-teknik partitioning dilakukan dengan sejauh mana mereka dapat mendukung tiga tipe akses terhadap data: 1. Pembacaan (scan) seluruh relasi 2. Mencari lokasi sebuah tupel yang bersesuaian dengan kondisi tertentu – point query. • E.g., r.A = 25. 3. Mencari semua tupel yang berada dalam suatu kisaran (range) nilai tertentu – range query. • E.g., 10 ≤ r.A < 25. •Round robin: – Keuntungan • Sangat cocok untuk pembacaan sekuensial seluruh relasi pada masing-masing query • Semua disk hampir semuanya mempunyai jumlah tupel yang sama; pekerjaan pengambilan data sehingga dapat diseimbangkan di masing-masing disk. – Kerugian: Range query sangat susah diproses • Tidak ada clustering (pengelompokan) – tupel-tupel berserakan di semua disk 7

Basisdata Paralel Perbandingan Teknik-teknik partitioning (lanjt) • Hash partitioning – Keuntungan • Cocok untuk akses sekuensial – Jika diasumsikan fungsi hash yang digunakan cukup “baik”, dan partitioning atribut membentuk sebuah key, maka tupel-tupel akan terdistributsi secara seimbang di antara semua disk – Pekerjaan pengambilan data (pembacaan) akan terbagi secara seimbang di antara disk-disk tersebut. • Cocok untuk melakukan point query pada partitioning atribut – Dapat mencari hanya pada satu disk, meninggalkan yang lainnya untuk menjawab query yang lain. – Indeks pada partitioning atribut dapat dilakukan secara lokal terhadap disk yang bersangkutan, sehingga membuat pembacaan dan update lebih efisien. – Kerugian: Tidak ada clustering, sehingga sulit menjawab range query

8

Basisdata Paralel Perbandingan Teknik-teknik partitioning (lanjt) • Range partitioning – Keuntungan • Menyediakan data clustering oleh nilai partitioning atribut. • Cocok untuk akses sekuensial • Cocok untuk point query pada partitioning atribut: hanya satu disk yang perlu di akses. • Untuk melakukan range query pada partitioning atribut, hanya perlu mengakses satu sampai beberapa buah disk − Sehingga disk yang lain masih bisa digunakan untuk menjawab query yang lain. − Cocok jika tupel hasil terdapat di satu sampai beberapa block. − Kerugian: Jika block yang diakses berjumlah banyak, maka tetap saja mereka diakses dari satu atau lebih disk, dan potensi paralelisme pada disk terbuang karena hanya satu/beberapa disk (partisi) saja yang terlibat dalam pemrosesan – Disebut sebagai execution skew.

9

Basisdata Paralel Penanganan Skew (kemiringan distribusi) • Distribusi tupel-tupel ke disk bisa terjadi tidak seragam/miring (skew) — yaitu, beberapa disk dapat mempunyai lebih banyak tupel, sementara yang lain hanya memiliki lebih sedikit tupel. • Tipe Skew: – Attribute-value skew. • Beberapa nilai muncul sebagai partitioning atribut untuk lebih dari satu tupel; semua tupel dengan nilai yang sama untuk partitioning atribut akan berakhir di partisi yang sama. • Dapat terjadi pada range-partitioning dan hashpartitioning. – Partition skew. • Dengan range-partitioning, salah pilih partition vector akan menyebabkan terlalu banyak tupel berada pada beberapa partisi sementara terlalu sedikit tupel pada partisi yang lain. • Hal yang sama juga akan terjadai pada hashpartitioning jika fungsi hash yang dipilih tidak “baik”

10

Basisdata Paralel Menangani Skew Dalam Range-Partitioning • Untuk membuat partitioning vector yang seimbang (balanced partitioning vector) (misalkan partitioning atribut membentuk sebuah key pada relasi): – Urutkan relasi berdasarkan partitioning atribut. – Bangun partition vector dengan membaca relasi secara berurutan sebagai berikut. • Setelah setiap 1/ke-n relasi telah dibaca, nilai partitioning atribut tupel berikutnya ditambahkan ke partition vector – n menyatakan banyaknya partisi yang akan dibangun. – Nilai yang sama atau ketidakseimbangan akan muncul jika terdapat nilai yang sama pada partitioning atribut • Teknik alternatif dilakukan dengan menggunakan histogram

11

Basisdata Paralel Menangani Skew Menggunakan Histogram • Partitioning vector yang seimbang dapat dibangun dari histogram dengan cara yang relatif langsung – Asumsi distribusi uniform untuk masing-masing range histogram • Histogram dapat dibangun dengna membaca relasi, atau melakukan sampling (blok yang mengandung) tupel-tupel relasi

12

Basisdata Paralel Menangani Skew Menggunakan Virtual Processor Partitioning • Skew dalam range partitioning dapat ditangani dengan cara yang elegan menggunakan virtual processor partitioning: – Buatlah partisi dalam jumlah besar (katakan 10 sampai 20 kali jumlah prosesor) – Buatlah partisi masing-masing virtual prosesor dengan cara round-robin atau berdasarkan ongkos perkiraan masing-masing partisi virtual • Ide utama: – Jika distribusi yang normal akan miring (skewed), sangat mungkin kemiringan tersebut tersebar di beberapa partisi virtual – Partisi virtual yang miring tadi tersebar di beberapa prosesor, sehingga pekerjaan terdistribusi secara 13 seimbang.

Basisdata Paralel Arsitektur Basisdata Paralel

Shared Nothing

CLIENTS

Teradata: 400 nodes Tandem: 110 nodes IBM / SP2 / DB2: 128 nodes Informix/SP2 48 nodes ATT & Sybase ? nodes CLIENTS

Shared Disk Oracle DEC Rdb

Shared Memory Informix RedBrick

170 nodes 24 nodes CLIENTS

9 nodes ? nodes

Processors Memory

14

Basisdata Paralel Tipe-tipe Paralelisme • Intra-query parallelism (speed-up) Menjalankan satu query secara paralel di lebih dari satu prosesor dan disk – Intra-operator parallelism • Semua mesin mengerjakan satu operasi yang diberikan (scan, sort, join) – Inter-operator (inter-query) parallelism • Masing-masing operasi yang berbeda berjalan secara bersamaan pada tempat yang berbeda (memanfaatkan pipelining) • Inter-query parallelism (scale-up) – Query yang berbeda berjalan pada prosesor dan disk yang berbeda

15