Graph-Based Protocol

Back to IF3140 Sistem Basis Data

1.4: Graph-Based Protocol

Questions/Cues

• Apa alternatif selain 2PL?

• Apa itu Graph-Based Protocol?

• Bagaimana data diorganisir?

• Apa itu Tree Protocol?

• Bagaimana aturan Tree Protocol?

• Apakah Tree Protocol menjamin serializability?

• Apakah Tree Protocol bebas deadlock?

• Kapan Tree Protocol melepaskan lock?

• Apa bedanya dengan 2PL?

• Kelebihan & Kekurangan Tree Protocol?

Reference Points

• Slides “11 - Concurrency Control - 2.pdf” (Hal 4-9)

Motivasi: Alternatif Selain 2PL

Two-Phase Locking (2PL) adalah protokol yang paling umum, tetapi ia memiliki kelemahan utama: bisa terjadi deadlock. Selain itu, 2PL menahan lock untuk waktu yang lama (sampai shrinking phase), yang bisa mengurangi konkurensi.

Graph-Based Protocol adalah keluarga protokol alternatif yang memanfaatkan struktur data yang diketahui untuk menghindari deadlock.

Ide Dasar: Struktur Data

Protokol ini mengasumsikan kita dapat memetakan semua item data ke dalam sebuah struktur graf, misalnya Pohon (Tree) atau Directed Acyclic Graph (DAG).

• Setiap item data (misal, baris, tabel) adalah sebuah node di pohon.

• Kita mendefinisikan urutan parsial berdasarkan hirarki pohon ini.

Definisi: Tree Protocol (Protokol Pohon)

Ini adalah varian Graph-Based Protocol yang paling populer dan sederhana.

Aturan Main Tree Protocol:

1. Hanya lock-X: Protokol ini umumnya (dalam versi dasarnya) hanya mempertimbangkan lock-X (Exclusive).

2. Lock Pertama: Lock pertama dari sebuah transaksi T dapat dilakukan pada sembarang node (item data) di pohon.

3. Lock Berikutnya: Untuk meminta lock-X(Y), transaksi T harus sudah memegang lock-X pada induk (parent) dari Y, yaitu parent(Y).

   • Pengecualian: Aturan ini tidak berlaku untuk node pertama yang di-lock (aturan #2).

4. Aturan Pelepasan (Unlock): Ini adalah bagian yang paling membedakannya dari 2PL.

   • Sebuah lock pada node X dapat dilepaskan (unlock(X)) kapan saja (tidak harus menunggu shrinking phase).

   • TAPI: Setelah T melepaskan unlock(X), T tidak boleh lagi meminta lock pada node X tersebut atau node manapun di subtree (cabang) di bawah X.

Contoh Operasi (Slide 8-9)

• T1 ingin akses (tulis) B, E, L:

  • Urutan lock WAJIB: lock-X(B), lalu lock-X(E), lalu lock-X(L).

• T2 ingin akses (tulis) D, H:

  • Urutan lock WAJIB: lock-X(A), lalu lock-X(D), lalu lock-X(H).

Skenario Konkuren:

1. T1: lock-X(B).

2. T2: lock-X(A). (Boleh, A dan B tidak saling parent/child).

3. T1: lock-X(E).

4. T2: lock-X(D). (Boleh).

5. T1: Selesai dengan B, melakukan unlock(B). (BOLEH, meskipun T1 masih memegang lock di E). Ini BUKAN 2PL!

6. T1: lock-X(L).

7. T2: lock-X(H).

Jaminan Tree Protocol

1. Menjamin Conflict Serializability. (Urutan lock pada akar pohon menentukan urutan serialisasi yang setara).

2. DIJAMIN BEBAS DEADLOCK. Mengapa? Karena semua transaksi “dipaksa” meminta lock dalam urutan yang sama (dari atas ke bawah pohon). Tidak mungkin terjadi siklus tunggu (T1 tunggu T2, T2 tunggu T1).

Perbandingan dengan 2PL

Fitur	Two-Phase Locking (2PL)	Tree Protocol (TP)
Serializability?	Ya, dijamin.	Ya, dijamin.
Bebas Deadlock?	Tidak. (Butuh deadlock handling).	Ya, dijamin.
Kapan Boleh Unlock?	Hanya di Shrinking Phase.	Kapan saja (setelah selesai).
Konkurensi?	Baik, tapi lock ditahan lama.	Potensial lebih baik (karena unlock lebih awal).
Cascading Rollback?	2PL dasar: Ya. (Butuh Strict 2PL).	Ya. (Karena unlock lebih awal).
Fleksibilitas?	Sangat fleksibel.	Tidak fleksibel (tergantung struktur pohon).

Summary

Graph-Based Protocol (seperti Tree Protocol) adalah alternatif untuk 2PL yang memanfaatkan struktur data (pohon) untuk mengatur urutan request lock. Aturan utamanya adalah lock diminta secara top-down (dari induk ke anak). Protokol ini memiliki keunggulan besar yaitu dijamin bebas deadlock dan menjamin serializability. Selain itu, lock bisa dilepas lebih awal (meningkatkan konkurensi) dibandingkan 2PL. Namun, kelemahannya adalah ia kurang fleksibel (harus tahu struktur pohon) dan masih rentan terhadap cascading rollback (karena unlock lebih awal).

Additional Information

Pendalaman: Mengapa Tree Protocol Bebas Deadlock?

Deadlock terjadi ketika ada siklus tunggu (T1 tunggu T2, T2 tunggu T3, …, Tn tunggu T1). Tree Protocol mencegah siklus ini dengan memberlakukan urutan parsial (partial order) pada semua item data.

1. Semua lock diminta dalam urutan top-to-bottom sesuai struktur pohon.

2. Asumsikan terjadi deadlock antara T1 dan T2.

3. Ini berarti T1 memegang lock pada item X, dan T2 memegang lock pada item Y.

4. Lalu T1 meminta lock pada Y (harus tunggu T2), dan T2 meminta lock pada X (harus tunggu T1).

5. Mari kita analisis berdasarkan aturan Tree Protocol:

   • Jika T1 minta Y: Berdasarkan aturan, Y haruslah anak dari X (Y = child(X)).

   • Jika T2 minta X: Berdasarkan aturan, X haruslah anak dari Y (X = child(Y)).

6. Ini adalah sebuah kontradiksi logis. Tidak mungkin Y adalah anak dari X, dan X adalah anak dari Y dalam sebuah struktur pohon (yang acyclic).

7. Oleh karena itu, situasi deadlock (siklus tunggu) secara struktural tidak mungkin terjadi jika semua transaksi mematuhi Tree Protocol.

Kekurangan: Kapan Tree Protocol Tidak Cocok?

Tree Protocol gagal total jika sebuah transaksi perlu mengakses data dalam urutan yang “aneh”.

• Contoh: Transaksi T butuh akses lock(L) lalu lock(H).

• Urutan TP:

  • Untuk lock(L): T harus lock(B) -> lock(E) -> lock(L).

  • Untuk lock(H): T harus lock(A) -> lock(D) -> lock(H).

• Ini memaksa T untuk me-lock node parent (B, E, A, D) yang sebenarnya tidak ia butuhkan, hanya untuk mematuhi protokol. Ini menurunkan konkurensi.

• Lebih buruk lagi, jika T butuh lock(L) lalu lock(A). T harus lock(B) -> lock(E) -> lock(L). Lalu T harus unlock(L) -> unlock(E) -> unlock(B)… baru bisa lock(A). Ini sangat tidak efisien. 2PL jauh lebih baik untuk kasus akses ad-hoc seperti ini.