MapReduce: Cara Sederhana untuk Memroses Data Besar

Internet merupakan pusat informasi yang besar. Tiap saat orang-orang mengirimkan fotonya ke Instagram, mengirimkan curhatan mereka ke Twitter, dan mencari referensi untuk makan malam di Google. Data yang mereka proses banyak sekali. Membutuhkan waktu yang lama dan ruang yang besar agar dapat memproses data dengan jumlah besar.

Muncullah ide dari engineer Google untuk mempercepat proses tersebut dan megurangi beban penyimpanan. Mereka menamai metode tersebut MapReduce. MapReduce adalah framework atau model pemrograman yang terdiri atas dua fungsi, yaitu fungs untuk memproses data key/value pair dan fungsi untuk menggabungkan hasilnya menjadi satu.

Ide ini terinspirasi dari fungsi map dan reduce milik Lisp dan beberapa bahasa pemrograman fungsional lainnya. Fungsi map bertugas untuk menerapkan suatu operasi terhadap seluruh elemen pada array dan fungsi reduce bertugas untuk mereduksi suatu data jika data tersebut memiliki key yang sama.

Secara umum, proses yang terjadi pada MapReduce adalah sebagai berikut:

1. Program menerima input dalam bentuk key/value pairs
2. Kemudian, fungsi map menyebar input tersebut ke tiap processor untuk diolah sehingga tiap processor menghasilkan data key/value pairs yang baru.
3. Selanjutnya, hasil data key/value pair dari tiap processor diterima oleh fungsi reduce untuk dicek dan menggabungkan data dengan key yang sama.

Pseudo-code penggunaan MapReduce pada kasus untuk menghitung frekuensi kemunculan suatu kata pada dokumen besar adalah seperti berikut:

map(String key, String value):

//key: document name

//value: document content

for each word w in value:

EmitIntermediate(w, “1”);

reduce(String key, Iterator values):

//key: a word

//values: a list of counts

int result = 0;

for each v in values:

result += ParseInt(v);

Emit(AsString(result));

Dari pseudo-code di atas, fungsi map akan menuliskan kata yang ditemuinya dan menghitung kemunculannya (pada contoh di atas hanya “1”). Kemudian fungsi reduce akan menjumlahkan semua kemunculannya dari tiap kata.

Beberapa contoh penggunaan MapReduce lainnya adalah distributed grep dan menghitung frekuensi akses suatu URL.

Untuk saat ini, MapReduce sudah tidak digunakan oleh Google. Kita bisa lihat implementasinya pada Hadoop, project open source milik Apache yang khusus menangani Big Data.

MapReduce milik Hadoop sedikit berbeda dari Google. MapReduce miliki Hadoop mendukung fungsi partitioning untuk mempartisi data yang diolah. Kemudian juga mendukung fungsi combiner untuk menggabungkan data dengan key yang sama di area lokal (penggabungan dilakukan oleh masing-masing processor).

Pengenalan Teori Komputasi dan Implementasinya

Teori komputasi adalah sebuah teori pada ilmu komputer yang menjelaskan tingkat efisiensi suatu model matematis dalam menyelesaikan suatu masalah. Teori ini dibagi menjadi tiga cabang utama, yaitu:

1. Teori bahasa dan otomata
2. Teori komputabilitas
3. Teori kompleksitas

Teori bahasa dan otomata membahas beberapa mesin abstrak dan masalah yang dapat diselesaikan oleh mesin tersebut. Mesin ini akan menerima sebuah input dan secara otomatis memproses input tersebut. Mesin inilah yang disebut otomata. Otomata sangat dekat dengan teori bahasa formal, karena dengan otomata, sebuah bahasa dapat dibangun.

Lalu, teori komputabilitas membahas sejauh mana sebuah masalah dapat diselesaikan dengan komputer dan teori kompleksitas membahas seberapa efisien suatu masalah diselesaikan.

Dalam implementasinya, ketiga teori ini saling berkaitan. Pertama, seorang ilmuan komputer akan menggunakan model abstrak matematis untuk menyelesaikan masalah yang ada. Umumnya model yang digunakan adalah Turing machine, karena Turing machine mudah untuk dibentuk, dapat dianalisa dan digunakan untuk membuktikan hasil yang didapat, serta dianggap sebagai model yang hebat.

Selanjutnya, ilmuan komputer mulai melakukan proses pemecahan masalah menggunakan model abstrak tersebut berdasarkan teori komputabilitas. Salah satu contoh kasusnya adalah masalah halting. Halting merupakan kondisi di mana sebuah program dengan suatu input harus berhenti atau berjalan selamanya. Masalah ini mudah untuk dianalisa dan tidak dapat dipecahkan dengan Turing machine.

Terakhir, ilmuan komputer akan menghitung seberapa efisien masalah tersebut diselesaikan. Aspek yang diperhatikan adalah, waktu dan ruang. Aspek waktu menunjukan berapa lama masalah tersebut diselesaikan. Aspek ruang menunjukan berapa besar tempat yang digunakan untuk memecahkan masalah tersebut.

Untuk menghitung kedua aspek tersebut, ilmuan komputer menuliskan solusi yang didapat menjadi sebuah fungsi dengan besar input dari suatu masalah. Sebagai contoh, pencarian suatu nilai di dalam larik membutuhkan waktu yang besar jika larik tersebut besar juga. Untuk memudahkan masalah tersebut, notasi Big O digunakan.

Kemudian, masalah seperti apa yang dapat diselesaikan? Pada bidang matematika, teori komputasi umum digunakan untuk permasalahan analisis numerik. Beberapa masalahnya adalah,

1. Pencarian akar suatu fungsi, seperti metode bisection, metode Newton, serta metode Secant
2. Interpolasi yaitu untuk mendapatkan data point baru dari beberapa data point yang sudah diketahui
3. Operasi pada matriks, seperti dot product, cross product
4. Aljabar linier.

Pada masalah pencarian akar suatu fungsi, metode yang digunakan dapat berupa metode iteratif menggunakan iterasi khusus. Iterasi tidak dilakukan pada fungsi yang diberikan, tetapi dilakukan pada fungsi tambahan dan mengaproksimasi nilai akar menggunakan fungsi tersebut. Sehingga proses iterasi tidak memakan waktu yang lama. Metode yang menggunakan iterasi adalah metode Newton dan metode Secant.

Tak hanya menggunakan iterasi, pencarian akar pun dapat dilakukan dengan membagi fungsi menjadi beberapa bagian. Ini dilakukan agar ruang yang digunakan tidak besar. Metode yang menggunakan proses ini adalah bisection dan regula falsi.