IV. HASIL DAN PEMBAHASAN IV.l. Algoritlna ROCCM Teorema yang diketnukaltan oleh Shi dan Perrizo (2004), mengungkapkan bahwa R O C C menghasilkan eksekusi transaksi yang serializable. Karena jika terdapat eksekusi yang tidak serializable, maka ada cycle dalam serialization
graph (SG) dalam RC-queue. Sebagai asumsi, terdapat sebuah cycle dala~nRCqt~ezleyang terdiri dari TI 3Tz ...T,,+TI, ~ n a k adalam transaksi-transaksi tersebut, terdapat konflik antara TI darl T2, sel-ta terdapat konflik antara T, dan T,. Algorit~navalidasi illtel-vening yang terdapat pada ROCC, akan ~nembatalkan transaksi yang lne~npunyaidua elemen yang keduatlya konflik dengan elemen transaksi lain yang terletak di antara elelnen yang konflik tersebut. Dengall demikian, cycle aka11dihentikan, karena transaksi yang dibatalkan akan dilakukan
restart.
Ga~nbar10 RC-qztelre dengan eksekusi serializable pada R O C C
Garnbar 1 1 Acyclic SG,
Dari hasil penelitian yang telah dilakukan, terdapat keadaan RC-quetre dengan eksekusi serializable, tetapi terdapat transaksi yang Inengalami restart pada saat dilakukan proses validasi oleh ROCC, seperti yang diilustrasikan pada Gambar
18 10. Pada Gambar 10, transaksi yang datang pertama kali adalah TI yang aka11 ~nengakses item data x (rl')),
item data y (r,(y), dan item data z (rl(z,).
Selanjutnya setelah transaksi TI terdapat transaksi
fi yang telah dilakukan validasi
dimana transaksi TZ terselmt melakukan perubahan nilai item data x yaitu wz6). Setelah transaksi T2 terdapat transaksi T3 yang hanya ingin mengakses item datay (r30). Akhirnya transkasi TI akan melakukan perubahan nilai item data z hv&)).
Proses validasi dimulai dari elemen read pertama kali untuk transaksi TI ("First'?, yang menemukan operasi elenien yang konflik yaitu item data x dari
operasi w&) pada transaksi T2. Kerena ditemukan elemen yang konflik dengan "First" dari transaksi Tz, maka proses validasi selanjutnya dimulai dari bagian
bawah dengan membandingkan elemen coniniit ("Second'? dari transaksi TI dengan transaksi sebelumnya. Penelusuran dari "Second", menemukan elemen yang konflik, yaitu operasi read untuk item data z, dari transaksi T3 (I-3(~)).Pada kondisi ini transaksi TI mengalami restart, padahal eksekusi transaksi adalah merupakan eksekusi yang serializable. SG pada Gambar 11 merupakan ilustrasi dari eksekusi transaksi untuk RCqueue pada Gambar 10. Dari Gambar 11 tersebut dapat diketahui bahwa tidak
terdapat cycle dalam SG tersebut, yang menunjukkan bahwa eksekusi lransaksinya bersifat serializable. Perbaikan algoritma ROCC menjadi ROCCM, dilakukan dengan mengubah cara validasi yang dilakukan oleh algoritma validasi intervening. Proses validasi pada algoritma ROCCM akan diuraikan dalam penjelasan di bawah ini. "First" adalah elemen operasi read dari transaksi yang melakukan conimit. "Conibine" adalah kumpulan elemen yang operasinya konflik dengan elemen coninzit ("Second'y maupun operasinya konflik dengan elemen "Combine "
sebelumnya. Sebagai inisialisasi awal "Cornbine"
=
(1. Langkah-langkah untuk
melakukan validasi setelah suahi transaksi mengirimkan coniniit request, pada ROCCM selengkapnya adalah sebagai berikut : 1. Bandingkan "First" dengan elemen dari transaksi lain yang terdapat di
antara "First" sampai elemen contniit. Bila pada saat penelusuran ditemukan elemen read dari transaksi yang sama (first-down reached
19 elentet~l)maka gabungkan elemen "Firsi" ke dalam elemen transaksi
yang sama berikutnya. Kemudian bandingkan
"First" hasil gabungan
tersebut, dengan elemen dari transaksi lain yang terdapat di antara "First" sampai elemen coninzit. Proses penelusuran dilakukan terus untuk menemukan elemen yang konflik atau elemen read berikutnya. Bila dari transaksi transaksi berikutnya yang ditemukan, adalab elemen cor~zn~it yang sama, dan tidak terdapat konflik maka validasi dinyatakan sukses. 2. Jika "First" konflik dengan elemen dari transaksi lain, pindahkan elemen "First" ke posisi transaksi sebeluln elemen dari transaksi lain yang
konflik. Hapus elemen "First" yang asli dari RC-qzceue. 3. Bandingkan "Second" atau "Con~bine" dengan elemen dari transaksi lain
yang terdapat di antara "Second" sampai ditemukan elemen dari transaksi yang sama ("First-up reached elenzent'y. Setiap elemen yang konflik, lakukan insert ke "Con~bine". 4. Bandingkan "Conzbine " dengan "First-zip reached element" Jika terdapat
konflik maka validasi dinyatakan gaga]. Jika tidak terdapat konflik lakukan pengecekan apakah "First-up reached elenzenl" adalah "First", jika merupakan "First maka validasi dinyatakan sukses, tetapi jika bukan elemen "First" lanjutkan langkah 5. 5. Gabungkan "SeconG' dengan
"First-up reached element" hapus
"Second" asli dari RC-quezre. Lanjutkan langkah 3. Pseudocode algoritma validasi pada ROCCM selengkapnya terdapat pada
urian di bawah ini. Pada algoritma validasi ROCCM, tersebut, proses penelusuran dari elemen "First" sama dengan aigoritma validasi pada ROCC. Perbedaannya terdapat pada proses penelusuran dari elemen con~njityaitu terdapat proses membandingkan antara elemen corlzn~itatau elemen "Combine" dengan elemen yang terdapat di antara elemen commit tersebut sarnpai ditemukan elemen transaksi yang sama rFirst-up reached elenlent'?. Jika ditemukan elemen yang konflik dengan elemen conlmit atau "Combine" maka elemen dari transaksi lain yang terdapat konflik, akan dilakukan insert ke "Conlbine ". Kemudian dilakukan pembandingan "Con~bine"dengan "First-up reached element" Jika terdapat
20
konflik maka validasi dinyatakan gagal. Jika tidak terdapat konflik lakukan pengecekan apakah "First-zip reached element" adalah "First", jika merupakan "First" maka validasi dinyatakan sukses, tetapi jika bukan elemen "First ", maka "Second"
digabungkan dengan
"First-zip reached elentent"
dun proses
penelusuran berjalan terus untuk menemukan elemen yang operasinya konflik dengan "Second" atau "Con~bine",sampai ditemukan elemen dari transaksi yang sama. Algoritma selengkapnya adalah sebagai berikut : "First" = NULL; "Second" =NULL; "Conzbine "=NULL; Locate the transaction 'sfirst read element in the RC-queue; If(notfound) return validated =true.. "First" = the first read elentent; While (1) J Conzpare "First" wifh all the elenzents ofother transaction behind it until it reached an elernent of the sanze transaction first-down-reached elenzent); If(T1~ereis no elenzent conflict)//nzoving down to lookfor tipper side conflict {Merge the "First" elenzent with the first-down-reached elemet; . Rernove the "First" elenzent from the RC-Q~ceue; If(Tlzefirst-down-reached element is the commit elenzent) Return validated = true; Else "First" = the first-down-reached-elert~ent;
I
Else // There is liper-sided-conflict; {Insert "First" into the RC-queue right before the conflicting element; Rmnove the original "First"fr0rn the RC-queue; "Second" = Conzmit elenzent; While (I) /hzzoving up to lookfor the lower-sided conflict; {Con~pare"Second" wirfz all the elenlent of other transactions before it until it reaches an elenzent of the same transaction first-lip-reached element); Insert elerncnt conflict with "Second" or Contbine" to "Cotnbine; {Conzparefirst-up-reachen eletizcnt" with "Combirze"; If(There is no elernent co~zflict) {Merge the "Second" element ~viththe first-up-reached element; Remove the "Second" elementfronz the RC-qzieue; I f the first-up-reached elenzent is the "First'y Return validated =hue; Else "Second" = the first-up-reached elernent;
I
Else //there is also Lo)ver-sided-conflict, the validationfails. {Remove all elenzents of the transaction~omthe RC-queue Return validated=false;
I
I
Pada algoritma validasi ROCCM di atas, yang tercetak tebal merupakan bagian modifikasi dari algoritma sebelumnya. Ilustrasi inlplementasi algorit~naROCCM, untuk beberapa kondisi RC-queue diperlihatkan pada Gambar 12.a, 12.b, dan 12.c. Pada Gambar 12.a diperlihatkan keadaan RC-queue dengan empat transaksi yang terdapat pada queue. Transaksi yang terdapat pada urutan pertama adalah TI dengan operasi rl'),
r,(yl, r&).
Kemudian disusul dengan transaksi T2 yang telah dilakukan validasi dengan operasi-operasi r2(w), r2(u), dan wz(x), berikutnya adalah transaksi T3 juga telah sukses dilakukan validasi dengan operasi-operasi r&), I&), w~(v).
(c) Gambar 12 RC-queue pada algoritma ROCCM: (a) hasil validasi tidak restart, (b) dan (c) hasil validasi restart.
Akhirnya TI mengirim col~znzitrequest untuk mengubah item data z yaitu wle). Langkah melakukan validasi pada RC-quezie Gambar 12.a, dimulai dari bagian atas pant) yaitu dengan cara mencari transaksi yang operasi elemennya konflik dengan "First". Penelusuran dari "First" menemukan elemen dari transaksi lain yang operasinya konflik yaitu operasi write item data x, dari transaksi T2 (102()1). Kemudian proses validasi dilanjutkan dari bagian bawah. "Second" adalah elemen conmit. "Second" dibandingkan dengan elemen dari transaksi lain, yang menemukan operasi item data yang konflik, yaitu operasi read item data z dari transaksi T3, sehingga elemen yang disalin ke "Combine" adalah item data dari operasi readtransaksi T3 yaitu 2,s dan item data pada operasi write dari transaksi T3 yaitu v, sehingga elemen-elemen serta operasinya yang terdapat pada "Con7bilie" adalah r3(z), r3(s), w3(v). Penelusuran berikutnya metnbandingkan
"Second" dengan transaksi di
atasnya, karena tidak ada operasi elemen yang konflik dengan "Second" maka kemudian dibandingkan dengan "Combine yang juga tidak menemukan konflik. "
Karena tidak ada operasi elelnen yang konflik berikutnya yang ditemukan, sampai ditemukan elemen "First", maka akhirnya "Cornbine" dibandingkan dengan "First" yang juga tidak rnenemukan konflik sehingga proses validasi untuk keadaan RC-qrtezie Gambar 12.a dinyatakan sukses, dengan T/ dapat melakukan operasi perubahan item data z. Hasil validasi yang dilakukan pada RC-queue Gambar 12.b, berhasil menemukan konflik dengan "First" untuk transaksi TI, yaitu operasi item data x (M~(x))
dari transaksi TI. Selanjutnya proses validasi dari elemen cornnzit untuk
transaksi TI, berhasil menemukan konflik yaitu operasi item data y (w4(y)) dari transaksi T4, sehingga 1v4(yl disalin ke "Conzbine". Terakhir "Combine" dibandingkan dengan "First" yang berhasil menemukan konflik yaitu operasi item data y (,vl(y), yang konflik dengan r&),
sehingga transaksi TI mengalami
restart. Proses validasi pada RC-queue Gambar 12.c dimulai dari "Firsf" yang dibandingkan dengan elemen dari transaksi lain yang terdapat di antara "First" sampai elemen conzr~ityang lnenemukan elemen konflik yaitu operasi read item
data x (rz(x)) dari transaksi T2. Ke~nudianproses validasi dilanjutkan dari bawah dengan lnelnbandingkan "Second" dengan transaksi lain, yang dalam ha1 ini mene~nukankonflik yaitu operasi read item data z (r&) dari transaksi T4, maka seluruh elemen pada transaksi T4, yaitu elemen read z (r4(4))dan elemen write u 'v4(u)) akan disalin dan digabungkan ke "Combine". Penelusuran berikutnya membandingkan
"Second" dengan transaksi di
atasnya, dalam ha1 ini karena tidak ada elemen yang konflik dengan "Second" kemudian operasi elemen transaksi tersebut dibandingkan dengan "Combine" yang menemukan konflik, yaitu operasi read item data tr pada transaksi T3 (r3(u)). Elemen-elemen dari transaksi tersebut (elemen read u ( r 3 0 ) dan elemen write (w3(1v)))disalin dan digabungkan ke dalam "Coinbine". Penelusuran terhadap elemen transaksi berikutnya tidak menemukan konflik dengan "Second" tetapi mene~nukan operasi elemen yang konflik dengan "Coiitbine!' yaitu item data iv dari operasi rzfiv) transaksi T2, sehingga dalam ha1 ini elemen r2(1v), r2(v), dun wz6) disalin dan digabungkan ke "Cornbine" sehingga elemen "Combine" ~nenjadi (rdfir), w4(z); r3(u), w3(w); r2(w), rz(v), 1v2($) Akhirnya "First" dibandingkan dengan "Cornbine" yang menemukan konflik yaitu operasi item data x (w2(x)konflik dengan UJ/(X)) , sehingga transaksi
TI pada RC-queue Ga~nbar12.c mengalami restart. IV.2. Pelaksanaan Simulasi IV.2.1. Asurnsi-asumsi simulasi
Simulator yang digunakan untuk mengukur kinerja CC tersebut, menggunakan model antrian tertutup pada suatu sistem basis data terpusat, seperti diperlihatkan pada Gambar 13 dan Gambar 14. Pada simulator terdapat sejumlah terminal, untuk membangkitkan transaksi. Selanjutnya terdapat batasan transaksi yang aktif pada suatu saat di dalam sistem (ntpl). Apabila transaksi yang dibangkitkan oleh sejumlah terminal melebihi batasan transaksi yang diijinkan oleh sistem (melebihi nlpl), maka transaksi tersebut diletakkan dalam ready queue untuk menunggu transaksi dalam sistem selesai atau ada yang dilakukan abort. Sebaliknya apabila transaksi yang aktif dalam sistem tidak melebihi mpl, maka transaksi yang dibangkitkan oleh terminal masuk ke cc queue (concurrency control queue) dan
24 membuat permintaan operasi akses basis data melalui CC. Jika 1010s dari operasi yang dilakukan oleh CC, selanjutnya transaksi tersebut mengakses data. Jika data tersebut ada di b~rJferniaka eksekusi dilanjutkan ke CPU. Tetapi jika data tersebut tidak terdapat di bzrJfer maka eksekusi akan dilewatkan ke disk untuk mengakses data untuk seterusnya dilanjutkan ke CPU. Untuk mengakses disk serta diproses pada cpu harus melalui antrian di disk serta CPU yaitu disk-queue dan cpu- qzleue. Pada simulasi diasumsikan juga, bahwa sebuah transaksi melakukan operasi read terlebih dahulu sebelum melaksanakan operasi write. Diasumsikan juga jaringan yang digunakan adalah jaringan Local Area Nehvork (LAN) dalam keadaan handal pada saat transmisi data dari terminal ke server. Jalur think nlemberikan nilai random delay pada waktu mengakses item data. Pada Strict
2PL, jika hasil dari CC memutuskan bahwa suatu transaksi harus di block maka .transaksi tersebut dimasukkan dalam block qzlelre sampai permintaan akses data dapat diproses. Jika CC menetapkan untuk melakukan restart suatu transaksi, maka transaksi tersebut akan dilakukan restart dan selanjutnya dimasukkan ke dalam ready queue. Jika suatu transaksi telah kornplit (selesai) maka CC akan succes Itlessage ke terminal. memberikan co~i~nzit
IV.2.2. Model Simulasi Pada simulator terdapat dua model logical queuing yaitu yang pertama model antrian untuk ROCCM dan ROCC yang diambil dari penelitian sebelumnya (Shi & Perrizo 2004), serta yang kedua model antrian untuk Strict 2PL. Gambar 13 di
bawah ini memperlihatkan model antrian yang pertama pada simulator. Pada
Gambar
13
diperlihatkan
terdapat
sejumlah
terminal
untuk
membangkitkan transaksi. Ketika suatu transaksi baru diinisialisasi, sistem akan melewatkan transaksi pada ready queue untuk diteruskan ke cc queue. Transaksi yang 1010s validasi akan dilanjutkan untuk mengakses data di bzcfer atau disk. Setelah mendapatkan data operasi transaksi diteruskan ke cpu. Setelah dieksekusi oleh cpu terdapat pemberian nilai int-think dan ext-think Transaksi yang gagal validasi akan dilakukan restart dan kembali masuk ready queue. Eksekusi transaksi yang telah komplit akan dilaporkan ke terminal.
Gambar 13 Model logical queuing untuk ROCCM dan ROCC pada simulator (Shi & Perrizo 2004). Gambar 14 memperlihatkan model antrian untuk Strict 2PL pada simulator. Model tersebut merupakan modifikasi dari model logical qziezring penelitian sebelumnya dan ditambahkan dengan jalur transaksi yang mengalami blocked serta blocked queue untuk menampung transaksi yang mengalami blocked. Eksekusi antrian hampir sama dengan model antrian pada ROCC dan ROCCM. Perbedaannya pada model antrian Strict 2PL adalah terdapat block queue untuk menalnpung transaksi yang mengalami blocked untuk kemudian diteruskan ke cc qzreue. Parameter input defaut yang digunakan pada pelaksanaan simulasi diperlihatkan pada Tabel 3.
Gambar 14 Model logical queuing untuk Strict 2PL pada simulator (modifikasi dari model Shi dan Perrizo (2004)). Tabel 3 Nilai parameter input default pada pelaksanaan silnulasi No
Parameter
Nilai
1
db-size
1000 pages
2
mar_trar?s
10 pages
3
rrzi~z-trans
4 pages
4
~vritegrob
0,25
5
int-think
I ms
6
ext-think
1 ms
7
max-reg
3
8
mean-time
5
9
corrtrrzit-nurn
800
10
hit-ratio
0,s
11
obj-io
35 ms
12
obj-cpu
15 ms
13
nzirrz_cpzr
4
14
n~ini-disk
8
15
nlpl
5,10,25,50,75,100,200
27
IV.3. Hasil Simulasi Pelaksanaan simulasi dengan parameter input seperti pada Tabel 3, dimaksudkan untuk mengetahui kinerja ketiga algoritma yang diuji, berdasarkan nilai parameter daii penelitian sebelu~llnya(Shi & Perrizo 2004). Hasil simulasi pada fhrorighput dapat dilihat pada Gambar 15.a serta Tabel 4. Melalui Gambar 15.a tersebut, dapat diketahui bahwa ROCCM mempunyai nilai yang lebih tinggi, bila dibandingkan dengan algoritma ROCC dan Strict
2PL. Uji t-student pada sainple dengan derajat bebas (d' = (n1+n2-2)yang melniliki
.. rata-rata x dan y, serta variance s? dan sz 2 d~hitung dengan persamaan di bawah ini :
Pada pengujian dengan menggunakan derajat bebas 8 (5
+
5 -2) dan 95 %
con$dence interval, jika -1.86 < t < 1.86 maka perbedaan tidak nyata. Hasil pengujian dengan uji t-student menunjukkan bahwa perbedaan fhroughput antara
ROCC dan ROCCM, cukup nyata pada tizpl di atas 50 (Lampiran 3). Dari Gambar 15.a juga dapat diketahui bahwa throz~glipritStrict 2PL ada pada posisi terendah. Hasil simulasi pada restart ratio, dapat dilihat pada Gambar 15.b maupun Tabel 4. Gambar 15.b memperlihatkan perbedaan restart ratio ketiga algoritma yang diuji. Dari gambar tersebut, dapat diketahui bahwa resturt ratio ROCC berada pada posisi tertinggi terutama pada nip1 = 200. Gambar 15.c, memperlihatkan hasil simulasi dalam ha1 response time. Melalui gambar tersebut, dapat diketahui bahwa response titile antara ROCCM dan
ROCC, secara umum ha~npirsama pada berbagai ii7pl. Pada Tabel 4, ditunjukkan rekapitulasi kinerja algoritma pada throughput,
restart ratio dan response tiiiie. Pada tabel tersebut T adalah throughput, RR adalah response time, dan RT adalah restart ratio. Melalui tabel tersebut, juga dapat diketahui bahwa perbedaan nilai kinerja antara ROCC dan ROCCM pada
28
nzpl = 10 me~npunyainilai yang kecil. Tetapi nilai-nilai tersebut akan selnakin jauh berbeda seiring dengan naiknya jumlah mpl.
Gambar 15 Hasil simulasi: (a) throughput, (b) restart ratio, (c) response finze.
29
Tabel 4 Rekapitulasi hasil simulasi
IV.4. Evalusi kinerja algoritma Bargava (1999) mengemukakan bahwa salah satu cara untuk evaluasi terhadap kinerja sebuah algoritma CC adalah
melakukan
dengan melakukan
evaluasi terhadap throzrghptit, response tinie, dun restart ratio. Dari hasil simulasi yang ditampilkan pada eksperimen ini, dapat jelaskan bahwa algoritma ROCCM mempunyai troughput yang lebih tinggi. Sernentara itu restart ratio berada di bawah ROCC. Selain itu ROCCM mempunyai response tiwe yang hampir sama dengan ROCC. Throughput ROCC secara umurn berada tepat di bawah ROCCM. Sementara
itu ROCC mempunyai angka restart ratio yang lebih tinggi. Dari hasil penelitian yang telah dilakukan dapat dikemukakan bahwa angka response tirtze ROCC hampir sama dengan ROCCM yang mempunyai response tittle lebih cepat bila dibandingkan dengan Strict 2PL. Sementara itu, Strict 2PL mempunyai throughput yang lebih rendah bila dibandingkan dengan ROCCM dan ROCC. Restart ratio pada algoritma ini cukup rendah.
