Mengaplikasikan MapReduce untuk Mencari Mutual Friends ala Facebook

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].

Referensi: MapReduce by Steve Krenzel