Friday, September 30, 2016

Penerapan Model Pemrograman MapReduce Menggunakan Java dan MongoDB untuk Mencari Mutual Friends ala Facebook

Pada artikel "Mengaplikasikan MapReduce untuk Mencari Mutual Friends ala Facebook" telah dijelaskan bagaimana menerapkan pola pemrograman MapReduce untuk mencari mutual friends atau friends in common pada hubungan pertemanan di jejaring sosial ala Facebook. Pada artikel ini akan dibahas implementasi atau penerapan pola pemrograman MapReduce tersebut menggunakan bahasa program Java dan database NoSQL MongoDB. Bagi yang masih asing dengan MongoDB, silakan menyimak artikel "MongoDB : Database NoSQL Berbasis Dokumen yang sedang Naik Daun di Era Big Data" untuk mengenal database berbasis dokumen MongoDB. Kemudian, untuk cara instal MongoDB dijelaskan dalam artikel "Web Crawling: Menyerap isi Website dan Membangun Mesin Pencari ala Google Menggunakan Apache Nutch, Elasticsearch, dan MongoDB-bagian 2/3". Jadi, disini kita akan langsung mulai mengoperasikan MongoDB melalui Mongo Shell dan dengan menggunakan bahasa program Java melalui MongoDB Java Driver.

Pada contoh kasus implementasi MapReduce kali ini, kita akan membuat sebuah daftar pertemanan atau friend list yang disimpan di database MongoDB. Friend list tersebut akan terdiri atas:
Annya -> [Brahm, Chieya, Dipa]
Brahm -> [Annya, Chieya, Dipa, Elsa]
Chieya -> [Annya, Brahm, Dipa, Elsa]
Dipa -> [Annya, Brahm, Chieya, Elsa]
Elsa -> [Brahm, Chieya, Dipa]
Sekarang kita simpan daftar pertemanan ini di MongoDB dalam sebuah collection bernama friendList.

> db.createCollection("friendList")
{ "ok" : 1 }

> db.friendList.insert({"name":"Annya", "friend":["Brahm", "Chieya", "Dipa"]})
WriteResult({ "nInserted" : 1 })
> db.friendList.insert({"name":"Brahm", "friend":["Annya", "Chieya", "Dipa", "Elsa"]})
WriteResult({ "nInserted" : 1 })
> db.friendList.insert({"name":"Chieya", "friend":["Annya", "Brahm", "Dipa", "Elsa"]})
WriteResult({ "nInserted" : 1 })
> db.friendList.insert({"name":"Dipa", "friend":["Annya", "Brahm", "Chieya", "Elsa"]})
WriteResult({ "nInserted" : 1 })
> db.friendList.insert({"name":"Elsa", "friend":["Brahm", "Chieya", "Dipa"]})
WriteResult({ "nInserted" : 1 })
> db.friendList.find().pretty()
{
 "_id" : ObjectId("57e4015224b826076341a42c"),
 "name" : "Annya",
 "friend" : [
  "Brahm",
  "Chieya",
  "Dipa"
 ]
}
{
 "_id" : ObjectId("57e4017024b826076341a42d"),
 "name" : "Brahm",
 "friend" : [
  "Annya",
  "Chieya",
  "Dipa",
  "Elsa"
 ]
}
{
 "_id" : ObjectId("57e4018424b826076341a42e"),
 "name" : "Chieya",
 "friend" : [
  "Annya",
  "Brahm",
  "Dipa",
  "Elsa"
 ]
}
{
 "_id" : ObjectId("57e4019a24b826076341a42f"),
 "name" : "Dipa",
 "friend" : [
  "Annya",
  "Brahm",
  "Chieya",
  "Elsa"
 ]
}
{
 "_id" : ObjectId("57e401b924b826076341a430"),
 "name" : "Elsa",
 "friend" : [
  "Brahm",
  "Chieya",
  "Dipa"
 ]
}
> 

Sampai disini, telah berhasil dibuat sebuah collection bernama friendList yang berisi daftar teman dari 5 orang user yaitu Annya, Brahm, Chieya, Dipa dan Elsa.

Selanjutnya, kita akan membuat dua Java class untuk mengakses data daftar pertemanan dalam collection friendList, yaitu: MongodbConfiguration.Java dan MapReduce.java. MongodbConfiguration.java digunakan untuk mengatur konfigurasi server database MongoDB tempat collection friendList disimpan. Sedangkan MapReduce.java adalah source code implementasi pola pemrograman MapReduce untuk mencari mutual friends dari daftar pertemanan yang disimpan dalam collection friendList. Langsung saja, berikut adalah source code kedua Java class tersebut.

MongodbConfiguration.java
package com.teknologibigdata.mongodb;

import com.mongodb.MongoClient;
import com.mongodb.client.MongoCollection;
import com.mongodb.client.MongoDatabase;
import org.bson.Document;

/**
 *
 * @author Wayan M. Wijaya
 */
public class MongodbConfiguration {
    
    static final String host = "localhost";
    static final int port = 27017;
    static final String dbName = "teknologi-bigdata";
   
    final MongoClient mongoClient;
    final MongoDatabase mongoDatabase;
    
    
    public MongodbConfiguration(){
        mongoClient = new MongoClient(host, port);
        mongoDatabase = mongoClient.getDatabase(dbName);
    }
    
    
}


MapReduce.java
package com.teknologibigdata.mongodb;

import com.mongodb.client.FindIterable;
import com.mongodb.client.MongoCollection;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import org.bson.Document;

/**
 *
 * @author Wayan M. Wijaya
 */
public class MapReduce {
    
    public final MongoCollection&ltDocument&gt rawCollection;
    //public final MongoCollection&ltDocument&gt resultCollection;
    
    public MapReduce(MongodbConfiguration config){
        rawCollection = config.mongoDatabase.getCollection("friendList");
    }

    private ArrayList&ltDocument&gt map(ArrayList&ltDocument&gt friendList){
        ArrayList&ltDocument&gt mapResult = new ArrayList&lt&gt();
        
        for(Document personFriend:friendList){
            ArrayList&ltDocument&gt mapFriend = new ArrayList&lt&gt();
            String name = personFriend.getString("name");
            ArrayList friends = (ArrayList)personFriend.get("friend");
            
            for(int i=0; i&ltfriends.size(); i++){
                ArrayList key = new ArrayList();
                key.add(name);
                key.add(friends.get(i));
                Document kv = new Document();
                kv.append("key", key);
                kv.append("value", friends);
                Collections.sort(key);
                mapFriend.add(kv);
            }
            
            mapResult.addAll(mapFriend);
            
        }
        
        return mapResult;
    }
    
    private Map&ltArrayList, ArrayList&ltArrayList&gt&gt group(ArrayList&ltDocument&gt mapResult){
        Map&ltArrayList, ArrayList&ltArrayList&gt&gt groupResult = new HashMap&lt&gt();
        
        for(Document kv:mapResult){
            groupResult.put((ArrayList)kv.get("key"), new ArrayList&ltArrayList&gt());
        }
        
        for(Document kv:mapResult){
            groupResult.get((ArrayList)kv.get("key")).add((ArrayList)kv.get("value"));
        }
        
        return groupResult;
    }
    
    private Map&ltArrayList, ArrayList&gt reduce(Map&ltArrayList, ArrayList&ltArrayList&gt&gt groupResult){
        Map&ltArrayList, ArrayList&gt reduceResult = new HashMap&lt&gt();
        
        for(Map.Entry kv:groupResult.entrySet()){
            ArrayList key = (ArrayList)kv.getKey();
            ArrayList&ltArrayList&gt value = (ArrayList)kv.getValue();
            
            ArrayList&ltString&gt result = value.get(0);
            for(int i=1; i&ltvalue.size(); i++){
                result = intersection(value.get(i), result);
            }
            reduceResult.put(key, result);
        }
        
        return reduceResult;
    }
    
    private ArrayList&ltString&gt intersection(ArrayList&ltString&gt list1, ArrayList&ltString&gt list2){
        ArrayList&ltString&gt result = new ArrayList&lt&gt(list1);
        result.retainAll(list2);
        
        return result;
    }
    public static void main(String[] args) {
        
        MongodbConfiguration config = new MongodbConfiguration();
        MapReduce mapReduce = new MapReduce(config);
        FindIterable&ltDocument&gt friendList = mapReduce.rawCollection.find();
        ArrayList&ltDocument&gt friends = new ArrayList&lt&gt();
        for(Document friend:friendList){
            friends.add(friend);
        }
        
        ArrayList&ltDocument&gt mapResult = mapReduce.map(friends);
        Map&ltArrayList, ArrayList&ltArrayList&gt&gt groupResult = mapReduce.group(mapResult);
        Map&ltArrayList, ArrayList&gt reduceResult = mapReduce.reduce(groupResult);
        
        
        System.out.println("------Friend List------------------");
        for(Document f:friends){
            String name = f.getString("name");
            ArrayList&ltString&gt friend = (ArrayList)f.get("friend");
            System.out.println(name+":"+friend.toString());
        }
        
        System.out.println("------Map Result------------------");
        for(Document kv:mapResult){
            ArrayList key = (ArrayList)kv.get("key");
            ArrayList value = (ArrayList)kv.get("value");
            System.out.println(key.toString()+":"+value.toString());
            
        }
        
        System.out.println("------Group Result------------------");
        for(Map.Entry kv:groupResult.entrySet()){
            ArrayList key = (ArrayList)kv.getKey();
            ArrayList&ltArrayList&gt value = (ArrayList)kv.getValue();
            System.out.println(key.toString()+":"+value.toString());
        }
        
        System.out.println("------Reduce Result------------------");
        for(Map.Entry kv:reduceResult.entrySet()){
            ArrayList key = (ArrayList)kv.getKey();
            ArrayList value = (ArrayList)kv.getValue();
            System.out.println(key.toString()+":"+value.toString());
        }
        
    }
    
}


Setelah itu kita compile dan execute program MapReduce.java dengan menggunakan IDE pilihan masing-masing. Dalam hal ini saya menggunakan NetBeans Java IDE. Hasil eksekusinya adalah sebagai berikut:
------Friend List------------------
Annya:[Brahm, Chieya, Dipa]
Brahm:[Annya, Chieya, Dipa, Elsa]
Chieya:[Annya, Brahm, Dipa, Elsa]
Dipa:[Annya, Brahm, Chieya, Elsa]
Elsa:[Brahm, Chieya, Dipa]
------Map Result------------------
[Annya, Brahm]:[Brahm, Chieya, Dipa]
[Annya, Chieya]:[Brahm, Chieya, Dipa]
[Annya, Dipa]:[Brahm, Chieya, Dipa]
[Annya, Brahm]:[Annya, Chieya, Dipa, Elsa]
[Brahm, Chieya]:[Annya, Chieya, Dipa, Elsa]
[Brahm, Dipa]:[Annya, Chieya, Dipa, Elsa]
[Brahm, Elsa]:[Annya, Chieya, Dipa, Elsa]
[Annya, Chieya]:[Annya, Brahm, Dipa, Elsa]
[Brahm, Chieya]:[Annya, Brahm, Dipa, Elsa]
[Chieya, Dipa]:[Annya, Brahm, Dipa, Elsa]
[Chieya, Elsa]:[Annya, Brahm, Dipa, Elsa]
[Annya, Dipa]:[Annya, Brahm, Chieya, Elsa]
[Brahm, Dipa]:[Annya, Brahm, Chieya, Elsa]
[Chieya, Dipa]:[Annya, Brahm, Chieya, Elsa]
[Dipa, Elsa]:[Annya, Brahm, Chieya, Elsa]
[Brahm, Elsa]:[Brahm, Chieya, Dipa]
[Chieya, Elsa]:[Brahm, Chieya, Dipa]
[Dipa, Elsa]:[Brahm, Chieya, Dipa]
------Group Result------------------
[Brahm, Dipa]:[[Annya, Chieya, Dipa, Elsa], [Annya, Brahm, Chieya, Elsa]]
[Chieya, Elsa]:[[Annya, Brahm, Dipa, Elsa], [Brahm, Chieya, Dipa]]
[Dipa, Elsa]:[[Annya, Brahm, Chieya, Elsa], [Brahm, Chieya, Dipa]]
[Brahm, Chieya]:[[Annya, Chieya, Dipa, Elsa], [Annya, Brahm, Dipa, Elsa]]
[Brahm, Elsa]:[[Annya, Chieya, Dipa, Elsa], [Brahm, Chieya, Dipa]]
[Annya, Dipa]:[[Brahm, Chieya, Dipa], [Annya, Brahm, Chieya, Elsa]]
[Chieya, Dipa]:[[Annya, Brahm, Dipa, Elsa], [Annya, Brahm, Chieya, Elsa]]
[Annya, Chieya]:[[Brahm, Chieya, Dipa], [Annya, Brahm, Dipa, Elsa]]
[Annya, Brahm]:[[Brahm, Chieya, Dipa], [Annya, Chieya, Dipa, Elsa]]
------Reduce Result------------------
[Brahm, Dipa]:[Annya, Chieya, Elsa]
[Chieya, Elsa]:[Brahm, Dipa]
[Brahm, Chieya]:[Annya, Dipa, Elsa]
[Dipa, Elsa]:[Brahm, Chieya]
[Brahm, Elsa]:[Chieya, Dipa]
[Annya, Dipa]:[Brahm, Chieya]
[Annya, Brahm]:[Chieya, Dipa]
[Annya, Chieya]:[Brahm, Dipa]
[Chieya, Dipa]:[Annya, Brahm, Elsa]

Berdasarkan hasil Reduce Result diatas, kita dapat mengetahui mutual friends antara Brahm dan Dipa adalah Annya, Chieya, dan Elsa; mutual friends antara Chieya dan Elsa adalah Brahm dan Dipa; ... dan seterusnya.

Demikian, implementasi model pemrograman MapReduce menggunakan bahasa program Java untuk mencari mutual friend ala Facebook dari daftar pertemanan yang disimpan dalam database NoSQL MongoDB.

Semoga bermanfaat.
Silakan share pengalaman, pertanyaan, maupun tanggapan Anda di kolom comment dibawah. Terima Kasih.

No comments: