Bagaimana Facebook Mencari Mutual Friends Kita?

Facebook Mutual Friends

Facebook telah dikenal sebagai salah satu perusahaanweb serviceyang 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 teknologiBig Dataseperti Apache Hadoop (HDFS+MapReduce) danApache 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 mencariMutual Friendsdari network pertemanan dalam Facebook.

Bagi mereka yang sudah mengenalMapReduce, 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 contohuse caseMapReduce dalam dunia nyata, yaitu: Mencari jumlahMutual Friendsdari network pertemanan dalamFacebook dengan menggunakan MapReduce. Bagi para pengguna Facebook, pastinya sudah sangat familiar dengan istilahMutual Friendsini. Lalu, bagaimana Facebookdapatmenghitung dan meng-updatejumlahMutual Friendsdari tiap usernya yang jumlahnya sudah melebihi satu miliar dan masih terus bertambahitu?

Facebook memiliki daftar pertemanan (list of friends), dan perlu dicatat bahwafriendsatau 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 / responsesterhadap permintaan akses yang jumlahnya ratusan juta tersebut. Hal ini diharapkan dapat memberikan respon yang lebih cepat terhadap suatu permintaan daripadamelakukankomputasisetiap kalipermintaan akses itu datang. Salah satu permintaan penghitungan yang sangat umum adalahMutual Friends.Sebagai contoh, saat saya melihat profile Facebook milik Henny, saya dapat mengetahui berapa jumlahMutual Friendsantara 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 atauMutual Friendsini 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 atauMutual Friendsdari setiap pengguna Facebook sekali sehari dan menyimpan hasilnya dalam bentukKey Value Store( Apache HBase ). Dengan demikian, setiap kali ada seorang pengguna yang melihat profile pengguna yang lain, maka jumlah teman yang sama atauMutual Friendsdari kedua orang ini dapat langsung diketahui daridatabaseKey Value Storetanpa menghitungnya lagi.

Bagaimana algoritmanya?Kitadapatmenyimpan daftar pertemanan dari seluruh user Facebook dalam bentuk pasanganKey->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 pasangankey->value, akan menjadiargumentdari sebuah Mapperdalam MapReduce.Mapper tersebut akan menghasilkan satu pasangkey->valuedari setiap teman dalam"Daftar Teman".Yang menjadikeyadalah seorang teman dari "Daftar Teman" dan "Orang". Sedangkan yang menjadivalueadalah "Daftar Teman". Kemudian,keyakan diurut berdasarkan urutan alfabet (abjad).

Setelah proses Mapper selesai, maka daftar pertemanan diatas akan menjadi seperti berikut(keydiurut berdasar abjad sehingga semua pasangan pertemanan darikeyyang samaakan diproses lanjut oleh Reducer yang samapuladalam 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 bagiankeydapat 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 pasangankey->valueini diproses lanjut oleh tiap Reducer-nya, kita akan mengelompokkannya berdasarkankey-nyamasing-masingseperti 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 pasangankey->[list of value]akan menjadiargumentdari sebuah Reducer. Kemudianreduce functionakan mengambil perpotongan / interseksi darivalueyang terdapat dalam [list of value].Output darireduce functionadalahkeydanvalue(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 padakey(Brahm Dipa) dan melihat bahwa mereka memiliki 3 teman yang sama (Mutual Friends) yaitu [Annya Chieya Elsa].

Referensi:MapReduce : Mencari Mutual Friends Facebook