IF Notes

Multiple Granularity

6 min read

Back to IF3140 Sistem Basis Data

1.3: Multiple Granularity

Questions/Cues

  • Apa itu Granularity?

  • Apa trade-off granularitas?

  • Apa solusi trade-off ini?

  • Apa itu Intention Lock?

  • Apa saja jenis Intention Lock?

  • Apa itu Intention Shared (IS)?

  • Apa itu Intention Exclusive (IX)?

  • Apa itu Shared Intention Exclusive (SIX)?

  • Bagaimana Matriks Kompatibilitas MG?

  • Apa aturan Protokol Hirarki?

Reference Points

  • Slides “11 - Concurrency Control - 2.pdf” (Hal 10-16)

Apa itu Granularity (Granularitas)?

Granularitas mengacu pada “ukuran” dari item data yang dapat kita kunci. Dalam basis data, data diorganisir dalam sebuah hirarki.

Hirarki Granularitas (dari kasar ke halus):

  1. Basis Data (Keseluruhan)

  2. Tabel

  3. Halaman (Page) atau Blok Fisik

  4. Baris (Row) atau Tupel

  5. Atribut (Field)

Trade-off Granularitas

Memilih tingkat granularitas yang “tepat” adalah sebuah trade-off antara biaya overhead dan tingkat konkurensi.

  1. Granularitas Kasar (Coarse)

    • Contoh: Mengunci seluruh Tabel.
    • Overhead: Rendah. Jika transaksi T butuh 1000 baris, ia hanya butuh 1 lock (di level tabel).
    • Konkurensi: Rendah. Selama T mengunci tabel, tidak ada transaksi lain yang bisa mengakses baris apapun di tabel itu, meskipun barisnya berbeda.
    • Cocok untuk: Transaksi batch yang mengakses >50% data tabel.

  2. Granularitas Halus (Fine)

    • Contoh: Mengunci per Baris.
    • Overhead: Tinggi. Jika T butuh 1000 baris, ia butuh 1000 lock terpisah, yang memakan memori dan waktu Lock Manager.
    • Konkurensi: Tinggi. T1 dan T2 bisa bekerja pada baris yang berbeda di dalam tabel yang sama secara bersamaan.
    • Cocok untuk: Transaksi OLTP singkat (misal, transfer uang, update 1 data).

Solusi: Multiple Granularity (MG)

Ide-nya adalah mengizinkan sistem untuk mengunci pada level manapun yang paling efisien, tergantung kebutuhan transaksi.

  • Masalah: Bagaimana jika T1 mengunci seluruh Tabel (lock-X), lalu T2 mencoba mengunci Baris 5 di tabel itu? Lock Manager harusnya tahu bahwa Baris 5 sudah terkunci (secara implisit) oleh T1. Mengecek seluruh hirarki ke atas setiap kali ada permintaan lock sangatlah lambat.

  • Solusi: Kita butuh lock jenis baru.

Intention Locks (Kunci Niat)

Intention Lock adalah lock penanda yang ditempatkan pada node atas (kasar) untuk menandakan bahwa ada lock eksplisit (S atau X) yang sedang atau akan dipasang pada node bawah (halus).

  • Tujuannya: Efisiensi. Jika T2 mau lock-X di Tabel, ia cukup cek lock di level Tabel. Jika ada IS atau IX di sana, ia tahu ada lock di bawah dan harus tunggu. Ia tidak perlu scan jutaan baris.

Jenis-Jenis Kunci dalam Protokol MG:

  1. Shared (S): Kunci baca (seperti biasa).

  2. Exclusive (X): Kunci tulis (seperti biasa).

  3. Intention Shared (IS): Niat untuk memasang lock-S di level yang lebih rendah. (Contoh: Pasang IS di Tabel, lalu pasang S di beberapa Baris).

  4. Intention Exclusive (IX): Niat untuk memasang lock-X di level yang lebih rendah. (Contoh: Pasang IX di Tabel, lalu pasang X di beberapa Baris).

  5. Shared Intention Exclusive (SIX):

    • Ini adalah lock hibrida yang kuat.

    • Artinya: Transaksi ini membaca seluruh sub-hirarki (setara S di level ini) DAN berniat meng-update beberapa item di bawah (setara IX).

    • Contoh Skenario: “Scan seluruh tabel Gaji (S di tabel) dan beri kenaikan gaji (X di baris) untuk 10 orang”.

Matriks Kompatibilitas Multiple Granularity

Matriks ini jauh lebih kompleks.

(T1 holds)ISIXSSIXX
ISBolehBolehBolehBolehTunggu
IXBolehBolehTungguTungguTunggu
SBolehTungguBolehTungguTunggu
SIXBolehTungguTungguTungguTunggu
XTungguTungguTungguTungguTunggu

Logika Penting:

  • IS vs IX (Boleh): Niatnya tidak konflik. Konflik sesungguhnya (jika ada) akan ditangani di level baris.

  • IX vs S (Tunggu): S sedang membaca seluruh tabel, sementara IX berniat menulis di salah satu baris. Ini konflik.

  1. X (Exclusive) selalu konflik dengan apapun (kecuali tidak ada lock).

  2. S (Shared) hanya boleh barengan sama yang punya unsur “Baca” (IS dan S lainnya).

  3. IX (Intention Exclusive) hanya boleh barengan sama sesama “Intention” (IS dan IX lainnya).

  4. SIX itu egois karena dia gabungan S dan IX. Dia cuma kasih izin buat orang yang mau baca sedikit (IS).

Protokol Locking Hirarki MG

  1. Semua transaksi harus mematuhi Matriks Kompatibilitas.

  2. Permintaan lock harus dilakukan secara Top-Down (dari akar/database ke daun/baris).

  3. Pelepasan lock harus dilakukan secara Bottom-Up (dari daun/baris ke akar/database).

Aturan Request (Top-Down):

  • Untuk mendapat lock-S atau IS pada node N, transaksi harus sudah memegang IS atau IX pada parent(N).

  • Untuk mendapat lock-X, IX, atau SIX pada node N, transaksi harus sudah memegang IX atau SIX pada parent(N).

Contoh Alur:

Transaksi T mau lock-X pada Baris R di dalam Tabel Tbl.

  1. T minta lock-IX di Database. (Diberikan).

  2. T minta lock-IX di Tabel Tbl. (Harus cek kompatibilitas di Tbl. Diberikan).

  3. T minta lock-X di Baris R. (Harus cek kompatibilitas di R. Diberikan).

Summary

Granularitas adalah ukuran data yang dikunci (misal, Tabel vs Baris), yang memiliki trade-off antara overhead dan konkurensi (Kasar: overhead rendah, konkurensi rendah; Halus: sebaliknya). Solusinya adalah Multiple Granularity (MG), yang mengizinkan lock di berbagai level. Agar efisien, MG menggunakan Intention Lock (kunci niat) di level atas sebagai penanda (seperti IS - niat baca, IX - niat tulis, SIX - baca semua & tulis sebagian). Protokol ini mengharuskan lock diminta secara Top-Down (dari Database ke Baris) dan dilepas secara Bottom-Up, sambil mematuhi Matriks Kompatibilitas yang baru.

Graph View

Backlinks