Two-Phase Locking

Back to IF3140 Sistem Basis Data

1.2: Two-Phase Locking (2PL)

Questions/Cues

• Mengapa locking saja tidak cukup?

• Apa itu Two-Phase Locking (2PL)?

• Apa 2 fase dalam 2PL?

• Apa itu Growing Phase?

• Apa itu Shrinking Phase?

• Apa itu Lock Point?

• Apakah 2PL menjamin serializability?

• Apakah 2PL bebas deadlock?

• Apa itu Cascading Rollback?

• Apa itu Strict 2PL?

• Apa itu Rigorous 2PL?

• Hubungan 2PL, Strict, & Rigorous?

Reference Points

• Slides “11 - Concurrency Control - 1.pdf” (Hal 11-16, 19)

Masalah: Locking Saja Tidak Cukup

Menggunakan lock dan unlock secara sembarangan tidak menjamin serializability.

Contoh Anomali

Misal A = 1000, B = 2000. Total = 3000.

1. T3 (Transfer 50 dari B ke A)
2. T4 (Cek Total Saldo)
3. T3 (Lanjut)

T3	T4
lock-X(B)
read(B) (B=2000)
B = B - 50 (B=1950)
write(B)
unlock(B)
	lock-S(A)
	read(A) (A=1000)
	lock-S(B)
	read(B) (B=1950)
	unlock(A)
	unlock(B)
	print(A+B) (Hasil: 2950. SALAH!)
lock-X(A)
read(A) (A=1000)
A = A + 50 (A=1050)
write(A)
unlock(A)

Masalah: T4 melihat kondisi basis data yang tidak konsisten (B sudah dikurangi, A belum ditambah). Ini terjadi karena T3 melepaskan kunci (unlock(B)) terlalu cepat.

Definisi: Two-Phase Locking (2PL)

Ini adalah protokol yang memastikan serializability. Aturannya adalah:

“Setiap transaksi harus melakukan operasi lock dan unlock dalam dua fase yang terpisah.”

Fase 1: Growing Phase (Fase Tumbuh)

• Ini adalah fase pertama dari transaksi.

• Selama fase ini, transaksi hanya boleh meminta (acquire) kunci.

• Transaksi tidak boleh melepaskan (release) kunci sama sekali.

• Transaksi boleh melakukan lock-S, lock-X, dan lock upgrade (S ke X).

Fase 2: Shrinking Phase (Fase Susut)

• Ini adalah fase kedua, yang dimulai segera setelah transaksi melepaskan kunci pertamanya.

• Selama fase ini, transaksi hanya boleh melepaskan (release) kunci.

• Transaksi tidak boleh meminta (acquire) kunci baru sama sekali.

• Transaksi boleh melakukan unlock dan lock downgrade (X ke S).

Lock Point

Lock Point adalah satu titik waktu spesifik di mana transaksi telah mendapatkan kunci terakhirnya (yaitu, akhir dari growing phase).

• Urutan serializability dari transaksi-transaksi ditentukan oleh urutan lock point mereka.

Jaminan dan Masalah 2PL

• Jaminan: 2PL menjamin conflict serializability. Ini menyelesaikan masalah anomali seperti pada contoh T3 dan T4.

• Masalah 1: Tidak Bebas Deadlock. 2PL tidak mencegah deadlock. (Contoh: T1 lock-S(A), T2 lock-S(B), lalu T1 minta lock-X(B) (tunggu T2), dan T2 minta lock-X(A) (tunggu T1) → Saling tunggu selamanya).

• Masalah 2: Bisa Terjadi Cascading Rollback.

Masalah: Cascading Rollback

Ini adalah masalah di mana kegagalan satu transaksi (misal abort) menyebabkan transaksi-transaksi lain yang “tidak bersalah” juga harus ikut di-rollback (dibatalkan).

Skenario:

1. T1: lock-X(A), write(A) (A jadi “kotor” / dirty).

2. T1: unlock(A) (T1 masuk shrinking phase).

3. T2: lock-X(A), read(A) (T2 membaca data kotor T1), write(A).

4. T2: unlock(A).

5. T1: Tiba-tiba ABORT (gagal).

Konsekuensi: Karena T1 abort, perubahannya pada A harus dibatalkan. TAPI, T2 sudah terlanjur membaca nilai A yang kotor. Maka, T2 juga WAJIB di-rollback. Jika T3 sudah baca dari T2, T3 juga harus rollback, dan seterusnya. Ini sangat tidak efisien.

Solusi: Strict Two-Phase Locking (Strict 2PL)

Ini adalah variasi 2PL yang lebih ketat untuk mencegah cascading rollback.

• Aturan Sama: Punya growing dan shrinking phase.

• Aturan Tambahan: Sebuah transaksi tidak boleh melepaskan lock-X (Exclusive) apapun sampai setelah ia commit (berhasil) atau abort (gagal).

Keuntungan: Ini mencegah cascading rollback. Kenapa? Karena tidak ada transaksi lain (seperti T2) yang diizinkan membaca atau menulis data yang “kotor” (belum di-commit). T2 baru bisa dapat lock di A setelah T1 commit atau abort.

Solusi: Rigorous Two-Phase Locking (Rigorous 2PL)

Ini adalah versi yang lebih ketat lagi dan paling umum digunakan di sistem basis data komersial.

• Aturan Tambahan: Sebuah transaksi tidak boleh melepaskan SEMUA kunci (baik lock-X maupun lock-S) sampai setelah ia commit atau abort.

Keuntungan: Sangat mudah diimplementasikan (tidak perlu melacak kapan shrinking phase mulai, cukup lepaskan semua kunci saat commit/abort). Juga mencegah cascading rollback.

Hubungan: Rigorous 2PL adalah subset dari Strict 2PL, dan Strict 2PL adalah subset dari 2PL. Semua jadwal Rigorous 2PL pasti Strict 2PL, dan semua jadwal Strict 2PL pasti 2PL.

Summary

Menggunakan lock saja tidak cukup karena bisa menyebabkan anomali (data tidak konsisten). Two-Phase Locking (2PL) adalah protokol yang menjamin serializability dengan membagi eksekusi transaksi menjadi dua fase: Growing Phase (hanya boleh minta lock) dan Shrinking Phase (hanya boleh lepas lock). Titik akhir growing phase disebut Lock Point dan menentukan urutan serialisasi. Walaupun 2PL menjamin serializability, ia tidak bebas deadlock dan bisa menyebabkan Cascading Rollback. Untuk mengatasinya, digunakan Strict 2PL (menahan lock-X sampai commit) atau Rigorous 2PL (menahan semua kunci sampai commit), yang merupakan standar implementasi di banyak DBMS.

Additional Information

Pendalaman: Mengapa 2PL Menjamin Serializability?

2PL menjamin serializability karena urutan lock point dari transaksi-transaksi yang conflicting (berkonflik) memaksa sebuah urutan serial yang setara.

Bayangkan Precedence Graph (Graf Ketergantungan). Sebuah edge (panah) T1 -> T2 dibuat jika T1 dan T2 punya operasi yang berkonflik, dan operasi T1 terjadi lebih dulu. Jadwal serializable jika dan hanya jika precedence graph-nya tidak memiliki siklus (acyclic).

1. Asumsikan ada konflik antara T1 dan T2 (misal, T1 write(A) dan T2 read(A)).

2. Agar ini terjadi, T1 harus punya lock-X(A) dan T2 harus punya lock-S(A).

3. Pasti ada urutan. Entah T1 dapat lock-X dulu, atau T2 dapat lock-S dulu.

4. Kasus 1: T1 lock-X(A), lalu T1 unlock(A), lalu T2 lock-S(A).

   • Ini berarti Lock Point T1 (akhir growing phase-nya) pasti terjadi sebelum Lock Point T2 (karena T2 masih growing saat T1 sudah shrinking). Ini menciptakan edge T1 -> T2.

5. Kasus 2: T2 lock-S(A), lalu T2 unlock(A), lalu T1 lock-X(A).

   • Ini berarti Lock Point T2 terjadi sebelum Lock Point T1. Ini menciptakan edge T2 -> T1.

Tidak mungkin terjadi siklus (misal T1 -> T2 dan T2 -> T1 sekaligus) karena lock point adalah titik waktu yang terurut. 2PL secara esensial memaksa semua konflik untuk “setuju” pada satu urutan linear, yaitu urutan lock point.

Eksplorasi Mandiri: 2PL dalam SQL

Di banyak sistem basis data (seperti SQL Server atau PostgreSQL), level isolasi tertinggi yang bisa Anda minta adalah SERIALIZABLE.

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN TRANSACTION;
-- Operasi SQL Anda...
COMMIT;

Ketika Anda meminta level SERIALIZABLE, DBMS seringkali akan mengimplementasikannya menggunakan Rigorous Two-Phase Locking secara otomatis di balik layar.