Manfaat Graf dalam Cloud Computing

Manfaat Graf dalam Cloud Computing Heri Fauzan - 13513028 Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia 1 [email protected]

Abstrak— Cloud Computing merupakan teknologi menarik pada abad-21. Penggunaannya yang massif dalam sharing data dan service dengan skala besar sangat dibutuhkan saat ini. Dikarenakan peningkatan jumlah pengguna komputer dan segala kompleksitasnya, kehadiran Cloud Computing menjadikan banyak kemudahan dalam banyak persoalan. Dalam makalah ini penulis ingin menjelaskan penggunaan graf dalam Cloud Computing, sehingga dapat mencontohkan penggunaan graf dalam teknologi masa kini. Index Terms—Cloud Computing, Graf Heterogen, Graf Database.

I. PENDAHULUAN A. Latar Belakang Penulis mengambil topik ini dikarenakan ketertarikan akan aplikasi graf yang begitu luas. Dalam makalah ini penulis menghubungkan teori graf dengan teknologi yang sedang berkembang yaitu Cloud Computing. Bukan tidak mungkin suatu saat nanti, semua orang akan beralih menggunakan Cloud Computing dikarenakan penggunaan data yang sudah sangat besar dan biaya yang mahal untuk membeli peralatan elektronik. Cloud Computing sangat dibutuhkan untuk menghemat penyimpanan memori pada peralatan komputer pribadi sehingga hanya perlu beberapa server saja yang digunakan untuk penggunaan servis atau data tertentu. Selain itu, Cloud Computing juga baik dalam aksesibilitas dan mudah digunakan dimanapun. Banyak teknologi pemrosesan dengan cara kerja menggunakan graf yang dalam Cloud Computing seperti model pemrograman Hadoop MapReduce dan HDFS (Hadoop Distributed File Sistem) dan lainnya. Semua pemodelan Cloud Computing pada umumnya menggunakan graf, karena itu penulis memilih Cloud Computing untuk disandingkan dengan graf. Banyak hal seharusnya yang dapat dijabarkan lebih luas lagi mengenai topik ini, karena waktu yang terbatas penulis tidak membahas secara panjang lebar namun lebih singkat tapi cukup mendetail. B. Tujuan Makalah ini dibuat untuk tujuan melengkapi tugas akhir mata kuliah Matematika Diskrit serta untuk menjabarkan beberapa aplikasi dan manfaat dari graf

dalam persoalan Cloud Computing. Penulis mencoba mencoba menuliskan mengenai penggunaan graf dalam aplikasi skala besar seperti Cloud Computing. Dengan demikian akan terlihat hubungan jelas antara teori matematika diskrit dengan aplikasi teknologi pada dunia nyata abad ini.

II. TEORI DASAR A. Definisi Graf Graf merupakan gabungan antara beberapa sisi dan beberapa simpul yang terhubung satu sama lain. Jumlah simpul minimum pada graf adalah satu, dan jumlah sisi minimum pada graf adalah nol. Graf (G) dapat diartikan pula sebagai himpunan simpul(V) dengan sisi(E). Secara matematis ditulis sebagai berikut:[1] G= {V, E} B. Definisi Graf Heterogen Pertama-tama kita definisikan Graf Heterogen: Misal V dapat dihitung sementara ZV and ZE adalah jumlah dari simpul V dan jumlah dari sisi E. Graf Heterogen dapat dinotasikan sebagai berikut: G = (V;E;ZV ;ZE; lV ; lE) V adalah himpunan simpul pada graf. E adalah himpunan sisi berarah pada sebuah graf.[4]

Gambar 1. Graf Heterogen [4] C. Pengenalan Dasar Cloud Cloud merupakan teknologi yang digunakan untuk penggunaan bersama atau parallel suatu layanan atau data. Cloud terdiri dari puluhan komputer setiap ribuan koneksi komputer. Salah satu perangkat lunak pemrosesan cloud adalah Pregel, merupakan proyek

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2014/2015

google yang terinspirasi dari model BSP(Bulk Sinchronous Parallel) yang digunakan untuk pemrosesan graf skala besar. Pemrosesan pada cloud pada bab tiga menggunakan Map Reduce yang digunakan untuk melakukan partisi dan pemetaan hasil partisi. HDFS(Hadoop Distributed File Sharing) digunakan untuk pengaturan file/layanan dalam skala besar, bisa berupa data besar dan lain sebagainya. Berikutnya adalah Acacia yang merupakan sistem database graf terdistribusi, dibuat untuk mengatur hibrida cloud.[2]

III. PENGGUNAAN GRAF DALAM CLOUD A. Graf Topologi Perusahaan Topology Graph/ETG)

(Enterprise

Graf Topologi Perusahaan (ETG) merupakan salahsatu bentuk formal penggambaran sebuah Cloud yang melingkupi seluruh sistem pada sebuah perusahaan. ETG mencakup setiap entitas pada perusahaan IT hubungan antar entitas secara fisik, logika, dan fungsi. [3] Bentuk model konsep ETG dapat dilihat pada gambar dibawah ini:

Gambar 2.Bentuk Model Konsep ETG[3] Setiap ETG tersusun dari banyak entitas-entitas. Masingmasing entitas boleh terdiri atas beberapa propertiproperti sesuai dengan realitas. Sementara node dan edge adalah berupa pohon yang didefinisikan secara global. Contoh node dan edge:

Gambar 4.Contoh ETG: RDBMS[3]

B. Graf Heterogen dan Model Partisi Graf

Gambar 5.Sistem Arsitektur yang Digunakan[4] Kita menggunakan Map Reduce dan HDFS untuk mempartisi graf heterogen dan mengatur query eksekusinya. Gambar empat merupakan sistem arsitektur yang akan digunakan dalam partisi graf heterogen. Bagian Graph Partitioner untuk mempartisi graf besar yang diterima oleh HDFS yang kemudian akan dibagibagi menuju slave. Vertex Generator akan mengembalikan vertex dari HDFS menggunakan Map Reduce . Vertex Allocator akan mengalokasi pada slave letak masing-masing vertex yang telah digenerasi. Mesin Query Execution untuk mempercepat pemrosesan query.Master nantinya akan memanggil slave yang yang digunakan untuk mengintegrasi/menyatukan partisi-partisi yang telah tersimpan pada slave saat dipanggil.

Gambar 3. Tipe Node dan Edge[3] Segment adalah upagraf dari ETG yang berfungsi untuk mengurangi kompleksitas algoritma yang akan diimplementasikan. Berikut adalah contoh ETG yaitu RDBMS(Relational Database Mangement Sistem).

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2014/2015

Gambar 6. Penyatuan dua buah vertex hasil partisi[4] Dua buah vertex jika dipanggil akan digabung oleh master seperti pada gambar di atas. Sebelah kiri merupakan partisi yang ada pada slave dan sebelah kanan merupakan hasil kombinasi vertex dari kedua slave.

Sementara itu propagasi atau lebih dikenal dengan iteratif propagasi mengirimkan informasi masing-masing vertex ke sisi tetangga secara iteratif. Propagasi terdiri dari dua buah fungsi yaitu fungsi transfer dan combine: [6]

C. Pemrosesan Graf Skala Luas dalam Cloud Pada pemrosesan graf skala luas ada dua cara pemrosesan yaitu dengan Map Reduce dan Propagasi. Ada dua langkah yang dilakukan pada iteratif propagasi : [6] 1. Transfer: Pemanggilan fungsi transfer pada setiap vertex dan sisi tetangganya. Setelah itu mengembalkan hasil menengah. 2. Kombinasi: Fungsi combine dipanggil ketika hasil menengah telah didapatkan. Algoritma implementasi Propagasi dalam partisi graf adalah sebagai berikut: [6]

Gambar 7.Partisi Graf dalam Map Reduce[6] Seperti pada gambar di atas, cara kerja Map Reduce adalah dengan membagi-bagi graf menjadi beberapa bagian, yang masing-masing bagian itu akan disimpan pada slave. Partisi secara optimal dilakukan secara membagi menjadi dua bagian setiap bagiannya.

D. Mesin Database Graf Terdistribusi Sistem yang digunakan pada bagian ini adalah Acacia. Selain Acacia ada juga Trinity yang memiliki fungsi dasar yang sama dengan Acasia, namun memiliki bisa digunakan juga dalam Graf skala besar. Acacia merupakan perangkat lunak mesin database yang sering digunakan secara luas.

Gambar 7. Metode pemataan(mapping) Map Reduce[6] Algoritma implementasi Map Reduce dalam partisi graf adalah sebagai berikut: [6]

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2014/2015

Gambaran umum Acacia dapat dilihat pada gambar berikut:

Gambar 8. Gambaran Umum Acacia[5] Acacia pertama-tama mempartisi graf menjadi sebanyak n worker. Setiap worker berdiri sendiri / independent, tidak melakukan pendistribuasian graf. Hanya Master yang melakukan partisi graf dan mendistribusikannya menjadi beberapa bagian yang disimpan oleh worker. Untuk pempartisi graf digunakn METIS. Struktur Arsitektur Acacia adalah sebagai berikut:

Gambar 10.Komponen Acacia[5] Komponen utama Acacia terdiri dari Master dan Worker. Front end merupakan GUI yang digunakan pada master saat pengelolaan Database. Perintah master akan diterjemahkan dengan graf algoritma yang ada pada worker, seperti perintah menghapus graf, menambah graf , pembentukan upagraf , penempatan upagraf dan lain-lain. Berikut adalah salah satu contoh algoritma penempatan upagraf: [5]

Gambar 9.Struktur Arsitektur Acacia[5] HSQLDB (Hadoop SQL Database) digunakan untuk menjalankan semua operasional database yang dilaksanakan pada Acacia. Kendali Instansi pada Cloud Publik direpresentasikan oleh Java Virtual Machine (JVM). JVM ini nantinya akan digunakan jika dibutuhkan. Metis dan Hadoop secara bersamaan menggantikan fungsi Map Reduce yang sebelumnya kita gunakan.

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2014/2015

V. KESIMPULAN Graf dapat diaplikasikan dalam berbagai bidang terutama pada bidang teknologi informasi. Penggunaan graf banyak digunakan pada sistem-sistem yang menyangkut jaringan seperti Cloud. Banyak bagian dari Cloud yang dapat dijabarkan dengan graf, bahkan metode pemrosesan dat pada Cloud juga menggunakan graf.

SUMBER [1] [2] [3] [4]

[5] [6]

Munir, Rinaldi. 2005. Matematika Diskrit. Bandung: Penerbit Informatika. https://net.educause.edu/ir/library/pdf/EST0902.pdf Diakses pada 10 Desember 2014. Binz, Tobias dkk. 2012. Formalizing the Cloud trough Enterprise Topology Graph . Stuttgart: IAAS Universitat of Stuttgart. K.Lee , “Efficient Data Partitioning Model for Heterogeneous Graphs in the Cloud,” IEEE Graph Partitioning., submitted for publication. Dayarathna, “Toward Scalable Ditributed Graph Database Engine for Hybrid Clouds, ”NTU Data Cloud., submitted for publication. Rischen Chen,“Improving Large Graph Processing on Prtitioned Graph in the Cloud”.

PERNYATAAN Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain, dan bukan plagiasi. Bandung, 27 November 2014

Heri Fauzan , 13513028

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2014/2015