DISTRIBUTED TRANSACTIONS. Willy Sudiarto Raharjo

SISTEM TERDISTRIBUSI

DISTRIBUTED  TRANSACTIONS Willy Sudiarto Raharjo TEKNIK INFORMATIKA UKDW

Distributed Transactions ●

●

●

●

●

Proses transaksi (flat / nested) yang  mengakses object yang dikelola oleh beberapa  server Konsep atomicity tetap berlaku (all or nothing) Diperlukan sebuah coordinator untuk  memastikan konsep atomicity  Menggunakan protokol yang sudah disepakati  sejak awal (two­phase commit protocol) Memerlukan concurrency control TEKNIK INFORMATIKA UKDW

Flat Transaction (1) ●

●

●

Sebuah client melakukan request pada lebih  dari satu server Sebuah transaksi diselesaikan dahulu sebelum  meminta ke server berikutnya (sequential) Jika menggunakan konsep locking, maka  sebuah transaksi hanya bisa menunggu satu  obyek saja

TEKNIK INFORMATIKA UKDW

Flat Transaction (2) X

T Y T

Client

Z

TEKNIK INFORMATIKA UKDW

Nested Transactions (1) ●

●

●

Top level transaction bisa membuat sub  transaksi  Sub transaksi pada level yang sama bisa  berjalan secara concurrent (parallel) Mampu memanfaatkan utilitas prosessor (pada  kasus multi processor)

TEKNIK INFORMATIKA UKDW

Nested Transactions (2) M T

11

X Client

T

N

1

T T T T

12

21

2

Y P T

22

TEKNIK INFORMATIKA UKDW

CONTOH TRANSAKSI BANK (1) X Client

T

1

A

a.withdraw(10)

B

b.withdraw(20)

C

c.deposit(10)

D

d.deposit(20)

T Y

T = openTransaction openSubTransaction a.withdraw(10); openSubTransaction b.withdraw(20); openSubTransaction c.deposit(10); openSubTransaction d.deposit(20); closeTransaction

T

2

Z T T

3

4

TEKNIK INFORMATIKA UKDW

CONTOH TRANSAKSI BANK (2) join

openTransaction closeTransaction

participant A

.

a.withdraw(4);

join BranchX T Client

participant b.withdraw(T, 3);

T = openTransaction a.withdraw(4); c.deposit(4); b.withdraw(3); d.deposit(3); closeTransaction

B

b.withdraw(3);

BranchY

join

participant C

 Note: the coordinator is in one of the servers, e.g. BranchX

TEKNIK INFORMATIKA UKDW

D BranchZ

c.deposit(4); d.deposit(3);

PROSES TRANSAKSI ●

●

●

Client mengirimkan request openTransaction  pada coordinator pada sembarang server Coordinator yang dituju mengembalikan  identifier transaction yang unik pada client Client bekerjasama dengan coordinator dengan  commit protocol

TEKNIK INFORMATIKA UKDW

Coordinator (1) ●

●

●

●

Sebuah host/system yang menjadi “mandor”  untuk menyelesaikan sebuah transaksi  terdistribusi Bertanggung jawab untuk mengambil  keputusan commit/abort  Selama terjadi transaksi, coordinator mencatat  daftar referensi dari partisipan dan vice versa Coordinator tahu semua daftar peserta dan vice  versa TEKNIK INFORMATIKA UKDW

Coordinator (2)

TEKNIK INFORMATIKA UKDW

Atomic Commit Protocols ●

●

●

●

Dikembangkan awal 1970an Bertujuan untuk memastikan bahwa setiap  perubahan terjadi pada semua system atau  tidak sama sekali (all or nothing) Terdapat tiga jenis –

One phase commit protocol

–

Two phase commit protocol

–

Three phase commit protocol

Berakhir setelah transaksi di commit/abort TEKNIK INFORMATIKA UKDW

One Phase Commit Protocol ●

●

●

●

Coordinator mengirimkan pesan commit atau  abort pada semua partisipan Proses diulang terus menerus sampe semua  sudah membalas Masalah : Tidak mungkin melakukan abort  setelah ada permintaan untuk commit Solusi : Two Phase Commit TEKNIK INFORMATIKA UKDW

Two Phase Commit Protocol (1) ●

Fase 1 (voting) –

Coordinator mengirimkan request canCommit pada  setiap partisipan

–

Partisipan memilih yes/no dan mengirim balik pada  coordinator. Jika yes, maka menyimpan obyek pada  penyimpanan permanen. Jika tidak, abort

TEKNIK INFORMATIKA UKDW

Two Phase Commit Protocol (2) ●

Fase 2 –

Coordinator mengumpulkan hasil voting

–

Jika semua setuju, coordinator memutuskan  commit dan mengirimkan doCommit pada semua  partisipan

–

Selain itu, coordinator memutuskan abort dan  mengirimkan doAbort pada semua partisipan yang  memilih yes

–

Partisipan yang memilih yes menunggu doCommit/ doAbort dari coordinator TEKNIK INFORMATIKA UKDW

Two Phase Commit Protocol (3) ●

●

Setelah menerima salah satu dari pesan diatas,  partisipan menjalankan perintah sesuai dengan  pesan yang diterima Jika dilakukan perintah commit, maka  partisipan mengirimkan pesan haveCommitted  pada coordinator sebagai konfirmasi bahwa  proses sudah dilaksanakan

TEKNIK INFORMATIKA UKDW

Two Phase Commit Protocol (4) Coordinator

Participant

step

step

status

2

prepared to commit

1

status prepared to commit (waiting for votes)

3

committed

canCommit? Yes

(uncertain)

doCommit haveCommitted

4

done

TEKNIK INFORMATIKA UKDW

committed

Masalah pada Two Phase Commit ●

●

●

Susah memastikan semua partisipan sudah  melakukan vote dan mendapatkan hasil yang  sama Jika proses mengalami kegagalan (terjadi  network partitioning), maka tidak akan  didapatkan konsensus, karena partisipan yang  lain akan saling menunggu (blocking) Solusi : three phase commit TEKNIK INFORMATIKA UKDW

Three Phase Commit ●

●

●

●

Mencoba mengatasi masalah blocking Menggunakan asumsi tidak lebih dari k site fail  (k adalah angka yang sudah disetujui) Coordinator memastikan bahwa paling tidak k  site lain tahu bahwa coordinator akan  melakukan commit Jika coordinator fail, site yang lain melakukan  election coordinator baru dan melihat status  terakhir dan menentukan aksi (commit/abort) TEKNIK INFORMATIKA UKDW

Masalah pada Three Phase Commit  ●

●

●

Susah implementasinya Harus memastikan bahwa state harus tetap  konsisten meskipun terdapat perbedaan hasil  (transaksi di­commit di satu site dan abord di  site yang lain sebagai akibat dari network  partitioning) Terlalu banyak overhead

TEKNIK INFORMATIKA UKDW

Concurrency Control ●

●

●

Setiap server mengelola sekumpulan obyek  dan bertanggung jawab untuk memastikan  tetap konsisten ketika diakses oleh transaksi  concurrent Jenis –

Locking

–

Timestamp ordering concurrency control

–

Optimistic concurrency control

Baca materi minggu kemarin TEKNIK INFORMATIKA UKDW

Distributed Locking (1) ●

●

●

Lock pada obyek dikendalikan secara lokal oleh  local lock manager –

Memberikan akses untuk lock

–

Membuat transaksi yang meminta request  menunggu

Tidak bisa melepas lock sampai ada kepastian  abort/commit pada semua server Bisa menimbulkan distributed deadlock TEKNIK INFORMATIKA UKDW

Distributed Locking (2) U d.deposit(10)

V lock D b.deposit(10)

a.deposit(20)

W

lock A at X

lock B at Y c.deposit(30)

b.withdraw(30) wait at Y c.withdraw(20)

lock C at Z

wait at   Z a.withdraw(20) wait at  X

TEKNIK INFORMATIKA UKDW

Distributed Locking (3) W Held by

D

C

A X

Z Waits for

W

Waits for

V

Held by

Held by V

U Waits for

B Held by Y

TEKNIK INFORMATIKA UKDW

U

Phantom Deadlock (1) ●

●

Deadlock yang terdeteksi tetapi bukan  merupakan sebuah deadlock Terjadi karena adanya delay pada saat  pengiriman informasi deadlock pada jaringan

 local wait­for graph

T

U X

local wait­for graph

V

global deadlock detector

T

T Y

TEKNIK INFORMATIKA UKDW

U

V

Phantom Deadlock (2) ●

Transaksi U melepas obyek pada server X

●

Transaksi U meminta V pada server Y

●

Asumsi –

Server Y diterima terlebih dahulu dibandingkan  server X

●

T ­> U ­> V ­> T

●

T ­> U sudah tidak ada lagi TEKNIK INFORMATIKA UKDW

Transaction Recovery ●

●

Proses pemulihan dengan menggunakan versi  terakhir dari obyek yang sudah di­commit dari  media penyimpanan permanen Dilakukan oleh recovery manager –

Menyimpan obyek pada storage permanen

–

Restore obyek server setelah crash

–

Mengorganisasi ulang file recovery untuk  meningkatkan performa dari recovery

–

Reclaim storage space TEKNIK INFORMATIKA UKDW

Intention List ●

●

●

Berisi daftar obyek aktif yang diakses oleh client  selama transaksi (termasuk yang mengalami  perubahan selama transaksi) Digunakan untuk melihat obyek mana yang  terkena efek perubahan setelah commit Jika commit, maka nilai baru disimpan pada  storage. Jika abort, data dari intention list  digunakan untuk membatalkan perubahan dan  melakukan rollback ke data lama TEKNIK INFORMATIKA UKDW

Logging ●

Semua transaksi yang commit dicatat pada log

●

Urutan entry menggambarkan urutan transaksi

●

Setelah crash, semua transaksi yang tidak  memiliki status committed akan dibatalkan

P0 P1 P2 P3 Object: A Object: B Object: C Object: A Object: B  Trans: T 100  200 300 80 220  prepared < B, P2> P0

P4 P5 P6 P7  Trans: T Object: C  Object: B  Trans: U  committed 278 242   prepared < C, P5> < B, P6> P3 P4

Checkpoint

End of log

TEKNIK INFORMATIKA UKDW

Contoh pada 2PC

Trans: T

Coord’r: T

prepared part’pant list: . . .  intentions list

Trans: T

Trans: U

  committed  prepared

Part’pant: U Trans: U

Trans: U

  Coord’r: . .   uncertain  committed

Intention       list s

TEKNIK INFORMATIKA UKDW

Recovery pada 2PC Role

Status

    Action of recovery manager

Coordinator prepared           No decision had been reached before the server failed. It sends               to all the servers in the participant list and adds the   abortTransaction    transaction status                 in its recovery file. Same action for state     aborted           . If there is no participant list, the participants will eventually aborted      timeout and abort the transaction. Coordinator committed           A decision to commit had been reached before the server failed.  It sends a doCommit             to all the participants in its participant list (in case             it had not done so before) and resumes the two­phase protocol at step 4 Participant

            message to the coordinator (in committed   The participant sends a      haveCommitted            case this was not done before it failed). This will allow the coordinator             to discard information about this transaction at the next checkpoint. Participant uncertain            The participant failed before it knew the outcome of the transaction. It             cannot determine the status of the transaction until the coordinator        informs it of the decision. It will send a             to the coordinator      getDecision             to determine the status of the transaction. When it receives the reply it      will commit or abort accordingly. Participant prepared           The participant has not yet voted and can abort the transaction. Coordinator done     No action is required.

TEKNIK INFORMATIKA UKDW

Recovery Pada Oracle (1)

TEKNIK INFORMATIKA UKDW

Recovery Pada Oracle (2)

TEKNIK INFORMATIKA UKDW

Minggu Depan ●

Replication

TEKNIK INFORMATIKA UKDW