Mengaplikasikan MapReduce untuk Mencari Mutual Friends ala Facebook

FacebookMutualFriends
Facebook Mutual Friends
Facebook telah dikenal sebagai salah satu perusahaan web service yang sukses mengambil hati lebih dari satu miliar pengguna Internet di dunia. Guna tetap dapat memberikan layanan yang optimal kepada tiap usernya, Facebook telah menerapkan sejumlah teknologi Big Data seperti Apache Hadoop ( HDFS + MapReduce) dan Apache HBase ( yang dikenal sebagai database Big Data ) untuk memproses aliran data dari para usernya tersebut. Dikatakan bahwa Facebook telah dibanjiri oleh sekitar 1,1 miliar pengguna aktif per-bulannya pada Maret 2013. Dalam artikel ini kita akan membahas bagaimana mengaplikasikan MapReduce untuk mencari Mutual Friends dari network pertemanan dalam Facebook.

Bagi mereka yang sudah mengenal MapReduce, pasti sudah akrab dengan program Wordcount, sebuah contoh program aplikasi MapReduce, yang boleh dianggap sebagai "Hello World!"-nya MapReduce. Aplikasi Wordcount, sesuai dengan namanya, berfungsi untuk menghitung kemunculan tiap kata dalam satu atau sekumpulan text file. Memahami aplikasi Wordcount adalah langkah pertama untuk mengerti cara kerja MapReduce.

Seperti telah dinyatakan diatas, kali ini kita akan membahas sebuah contoh use case MapReduce dalam dunia nyata, yaitu: Mencari jumlah Mutual Friendsdari network pertemanan dalamFacebook dengan menggunakan MapReduce. Bagi para pengguna Facebook, pastinya sudah sangat familiar dengan istilah Mutual Friends ini. Lalu, bagaimana Facebook dapatmenghitung dan meng-update jumlah Mutual Friends dari tiap usernya yang jumlahnya sudah melebihi satu miliar dan masih terus bertambah itu?


Facebook memiliki daftar pertemanan ( list of friends), dan perlu dicatat bahwa friends atau pertemanan dalam Facebook bersifat dua arah : jika aku adalah temanmu maka kamu adalah temanku juga. Facebookjuga memiliki server penyimpanan data yang sangat besar dan melayani ratusan juta permintaan akses setiap harinya. Berkaitan dengan hal ini, Facebook telah memutuskan untuk melakukan komputasi pendahuluan/ pre-computation ( jika memungkinkan ) untuk mempersiapkanjawaban / responses terhadap permintaan akses yang jumlahnya ratusan juta tersebut. Hal ini diharapkan dapat memberikan respon yang lebih cepat terhadap suatu permintaan daripada melakukankomputasisetiap kali permintaan akses itu datang. Salah satu permintaan penghitungan yang sangat umum adalah Mutual Friends. Sebagai contoh, saat saya melihat profile Facebook milik Henny, saya dapat mengetahui berapa jumlah Mutual Friends antara saya dan Henny : "Kamu dan Henny memiliki 54 teman yang sama". Kemudian saya juga akan dapat mengetahui siapa saja yang termasuk dalam 54 orang tersebut. Jumlah teman yang sama atau Mutual Friends ini tentu saja tidak setiap saat berubah, jadi akan sangat mubazir jika Facebook harus selalu menghitung kembali setiap kali saya melihat profile-nya Henny.

Dalam kasus ini, kita akan menggunakan MapReduceuntuk menghitung jumlah teman yang sama atau Mutual Friends dari setiap pengguna Facebook sekali sehari dan menyimpan hasilnya dalam bentuk Key Value Store ( Apache HBase ). Dengan demikian, setiap kali ada seorang pengguna yang melihat profile pengguna yang lain, maka jumlah teman yang sama atau Mutual Friends dari kedua orang ini dapat langsung diketahui daridatabase Key Value Storetanpa menghitungnya lagi.

Bagaimana algoritmanya? Kita dapatmenyimpan daftar pertemanan dari seluruh user Facebook dalam bentuk pasangan Key->Value : Orang->[Daftar Teman]. Sebagai contoh, daftar pertemanan tersebut akan terlihat seperti berikut :

Annya -> [Brahm, Chieya, Dipa]
Brahm -> [Annya, Chieya, Dipa, Elsa]
Chieya -> [Annya, Brahm, Dipa, Elsa]
Dipa -> [Annya, Brahm, Chieya, Elsa]
Elsa -> [Brahm, Chieya, Dipa]

Setiap baris, yang merupakan pasangan key->value, akan menjadi argument dari sebuah Mapper dalam MapReduce. Mapper tersebut akan menghasilkan satu pasang key->value dari setiap teman dalam "Daftar Teman".Yang menjadi key adalah seorang teman dari "Daftar Teman" dan "Orang". Sedangkan yang menjadi value adalah "Daftar Teman". Kemudian, key akan diurut berdasarkan urutan alfabet (abjad).

Setelah proses Mapper selesai, maka daftar pertemanan diatas akan menjadi seperti berikut ( key diurut berdasar abjad sehingga semua pasangan pertemanan dari key yang samaakan diproses lanjut oleh Reducer yang samapula dalam MapReduce) :

For map(Annya -> [Brahm, Chieya, Dipa]), hasilnya :
(Annya Brahm) -> [Brahm, Chieya, Dipa]
(Annya Chieya) -> [Brahm, Chieya, Dipa]
(Annya Dipa) -> [Brahm, Chieya, Dipa]

For map(Brahm -> [Annya, Chieya, Dipa, Elsa]), hasilnya : (pada bagian key dapat dilihat Annya ditulis lebih dahulu daripada Brahm)
(Annya Brahm) -> [Annya, Chieya, Dipa, Elsa]
(Brahm Chieya) -> [Annya, Chieya, Dipa, Elsa]
(Brahm Dipa) -> [Annya, Chieya, Dipa, Elsa]
(Brahm Elsa) -> [Annya, Chieya, Dipa, Elsa]

For map(Chieya -> [Annya, Brahm, Dipa, Elsa]), hasilnya:
(Annya Chieya) -> [Annya, Brahm, Dipa, Elsa]
(Brahm Chieya) -> [Annya, Brahm, Dipa, Elsa]
(Chieya Dipa) -> [Annya, Brahm, Dipa, Elsa]
(Chieya Elsa) -> [Annya, Brahm, Dipa, Elsa]

For map(Dipa -> [Annya, Brahm, Chieya, Elsa]), hasilnya:
(Annya Dipa) -> [Annya, Brahm, Chieya, Elsa]
(Brahm Dipa) -> [Annya, Brahm, Chieya, Elsa]
(Chieya Dipa) -> [Annya, Brahm, Chieya, Elsa]
(Dipa Elsa) -> [Annya, Brahm, Chieya, Elsa]

For map(Elsa -> [Brahm, Chieya, Dipa]), hasilnya:
(Brahm Elsa) -> [Brahm, Chieya, Dipa]
(Chieya Elsa) -> [Brahm, Chieya, Dipa]
(Dipa Elsa) -> [Brahm, Chieya, Dipa]

Sebelum pasangan key->value ini diproses lanjut oleh tiap Reducer-nya, kita akan mengelompokkannya berdasarkan key-nya masing-masing seperti berikut:

(Annya Brahm) -> [Annya, Chieya, Dipa, Elsa] [Brahm, Chieya, Dipa]
(Annya Chieya) -> [Annya, Brahm, Dipa, Elsa] [Brahm, Chieya, Dipa]
(Annya Dipa) -> [Annya, Brahm, Chieya, Elsa] [Brahm, Chieya, Dipa]
(Brahm Chieya) -> [Annya, Brahm, Dipa, Elsa] [Annya, Chieya, Dipa, Elsa]
(Brahm Dipa) -> [Annya, Brahm, Chieya, Elsa] [Annya, Chieya, Dipa, Elsa]
(Brahm Elsa) -> [Annya, Chieya, Dipa, Elsa] [Brahm, Chieya, Dipa]
(Chieya Dipa) -> [Annya, Brahm, Chieya, Elsa] [Annya, Brahm, Dipa, Elsa]
(Chieya Elsa) -> [Annya, Brahm, Dipa, Elsa] [Brahm, Chieya, Dipa]
(Dipa Elsa) -> [Annya, Brahm, Chieya, Elsa] [Brahm, Chieya, Dipa]

Tiap baris, yang merupakan pasangan key->[list of value] akan menjadi argument dari sebuah Reducer. Kemudian reduce function akan mengambil perpotongan / interseksi darivalue yang terdapat dalam [list of value]. Output dari reduce function adalah key dan value ( yang tak lain adalah hasil dari interseksi tersebut): key -> [hasil interseksi]. Sebagai contoh, reduce((Annya Brahm) -> [Annya, Chieya, Dipa, Elsa] [Brahm, Chieya, Dipa]) menghasilkan (Annya Brahm) -> [Chieya Dipa]yang berarti Annya dan Brahm memiliki 2 teman yang sama (Mutual Friends) yaitu Chieya dan Dipa.

Hasil dari dari seluruh proses Reducer adalah sebagai berikut:

(Annya Brahm) -> [Chieya Dipa]
(Annya Chieya) -> [Brahm Dipa]
(Annya Dipa) -> [Brahm Chieya]
(Brahm Chieya) -> [Annya Dipa Elsa]
(Brahm Dipa) -> [Annya Chieya Elsa]
(Brahm Elsa) -> [Chieya Dipa]
(Chieya Dipa) -> [Annya Brahm Elsa]
(Chieya Elsa) -> [Brahm Dipa]
(Dipa Elsa) -> [Brahm Chieya]


Nah, sekarang ketika Dipa melihat profile Brahm, kita dapat dengan cepat menunjuk pada key (Brahm Dipa) dan melihat bahwa mereka memiliki 3 teman yang sama ( Mutual Friends ) yaitu [Annya Chieya Elsa].

Komentar

Posting Komentar

Postingan populer dari blog ini

Metode Analisis PIECES

Menurut Wukil Ragil (2010:17), metode PIECES adalah metode analisis sebagai dasar untuk memperoleh pokok-pokok permasalahan yang lebih spesifik. Dalam menganalisis sebuah sistem, biasanya akan dilakukan terhadap beberapa aspek antara lain adalah kinerja, informasi, ekonomi, keamanan aplikasi, efisiensi dan pelayanan pelanggan. Analisis ini disebut dengan PIECES Analysis ( Performance, Information, Economy, Control, Eficiency and Service ). Analisis PIECES ini sangat penting untuk dilakukan sebelum mengembangkan sebuah sistem informasi karena dalam analisis ini biasanya akan ditemukan beberapa masalah utama maupun masalah yang bersifat gejala dari masalah utama. Metode ini menggunakan enam variable evaluasi yaitu : 1.       Performance (kinerja) Kinerja merupakan variable pertama dalam metode analisis PIECES . Dimana memiliki peran penting untuk menilai apakah proses atau prosedur yang ada masih mungkin ditingkatkan kinerjanya, dan melihat sejauh mana dan seberapa handalkah suatu siste
Baca selengkapnya

Aritmetika Bilangan Jam dan Operasi Hitungnya

Gambar
Aritmetika Bilangan Jam dan Operasi Hitungnya          Materi pelajaran matematika yang akan dijabarkan pada postingan Rumus Matematika Dasar kali ini adalah mengenai Bilangan Jam. Bilangan jam adalah sebuah konsep perhitungan yang didasarkan kepada bilangan atau angka-angka yang diletakkan pada sebuah jam dengan aturan tertentu. Jika pada umumnya kita melihat angka pada sebuah jam berjumlah 12 dimulai dari angka 1 sampai dengan 12 maka pada bilangan jam jumlah angkanya berbeda-beda bergantung pada bentuk bilangan dari jam tersebut. Angkanya pun tidak dimulai dari 1 (satu) melainkan dimulai dari 0 (nol). Untuk lebih jelasnya coba perhatikan gambar tiga buah jam berikut ini:       Dari ketiga gambar jam di atas, kita dapat melihat bahwa pada jam empatan, hanya terdapat empat buah angka dimana angka terendah adalah 0 dan angka tertinggi adalah 3, sehingga anggota himpunan pada jam empatan adalah {0, 1, 2, 3).     Kemudian pada jam enaman, ada enam buah dimulai dari an
Baca selengkapnya

Kerajaan Singasari

Gambar
Kerajaan Singasari berdiri pada tahun 1222. Kerajaan ini didirikan oleh Ken Arok. Ia mendirikan Singasari setelah mengalahkan Kerajaan Kediri pada pertempuran di Ganter. Kerajaan Singasari terletak di antara Kota Lawang - Malang, Jawa Timur. Ken Arok adalah pembentuk dinasti Rajasa sebagai raja yang memiliki pengaruh di kerajaannya. Ia berusaha mempertahankan keberadaan Singasari atas keturunannya sendiri. Tohjoyo direncanakan sebagai penggantinya. Namun, sebelum rencananya terwujud terjadi kemelut dalam kerajaan. Anusapati (anak Tunggul Ametung) membunuh Ken Arok melalui orang upahan. Setelah mengetahui bapaknya dibunuh, Tohjoyo lalu membunuh Anusapati pada tahun 1248. Rencana balas dendam antar keturunan terus berlanjut. Tohjoyo pun mengalami nasib yang sama. Ia dibunuh oleh keturunan Anusapati. Akhirnya, pada tahun 1268 Wisnuwardhana memerintah di Kerajaan Singasari. Mulai masa itulah kerajaan ini berhenti bertikai dengan bantuan Mahesa Campaka. Mahesa Cempaka adalah saudara seayah
Baca selengkapnya