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 Friends
dari network pertemanan dalam
Facebook dengan menggunakan MapReduce. Bagi para pengguna Facebook,
pastinya sudah sangat familiar dengan istilah Mutual
Friends ini. Lalu, bagaimana
Facebook dapat
menghitung 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. Facebook
juga 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 mempersiapkan
jawaban / responses terhadap
permintaan akses yang jumlahnya ratusan juta tersebut. Hal ini
diharapkan dapat memberikan respon yang lebih cepat terhadap suatu
permintaan daripada melakukan
komputasi
setiap 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 MapReduce
untuk 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 dari
database Key Value Store
tanpa menghitungnya lagi.
Bagaimana
algoritmanya? Kita dapat
menyimpan 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 sama
akan diproses lanjut oleh Reducer yang sama
pula 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 dari
value 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
Comments