Masalah apa yang dipecahkan MapReduce?

Saya telah membaca tentang MapReduce untuk sementara waktu - tetapi yang saya tidak mengerti adalah bagaimana seseorang akan membuat keputusan untuk menggunakan (atau tidak menggunakan) MapReduce.

Maksud saya, apa pola masalah yang memberi sinyal bahwa MapReduce dapat digunakan.

Ini pada dasarnya masalah yang besar, tetapi tidak sulit. Travelling salesman sangat tergantung pada jarak antara setiap pasangan kota, jadi sementara itu dapat dipecah menjadi banyak bagian, hasil parsial tidak dapat digabungkan kembali sehingga solusi optimal global muncul (well, mungkin tidak; jika Anda tahu cara, silakan ajukan medali Fields Anda sekarang).

Di sisi lain, menghitung frekuensi kata dalam corpus raksasa dapat dipartisi secara trivial, dan dapat direkombinasi secara trivial (Anda hanya menjumlahkan vektor yang dihitung untuk segmen corpus), sehingga pengurangan peta adalah solusi yang jelas.

Dalam praktiknya, lebih banyak masalah cenderung mudah direkombinasi daripada tidak, sehingga keputusan apakah akan memaralelkan suatu tugas atau tidak lebih berkaitan dengan seberapa besar tugas itu, dan lebih sedikit dengan seberapa sulitnya.

Bisakah masalah dipecahkan secara efisien menggunakan komputasi terdistribusi?

Jika jawaban untuk pertanyaan ini adalah ya, maka Anda memiliki masalah kandidat untuk MapReduce. Itu karena pola masalah cocok untuk dipecah menjadi masalah-masalah kecil yang terisolasi.

Tugas Anda: Parsing buku ini

Contoh berfungsi dengan baik untuk menggambarkan ini. Anda memiliki dokumen besar ( Moby Dick oleh Herman Melville ) dan tugas Anda adalah melakukan analisis frekuensi dari semua kata yang digunakan di dalamnya.

Pendekatan berurutan

Anda dapat melakukan ini secara berurutan dengan mendapatkan mesin tercepat Anda (Anda punya banyak kebohongan) dan menjalankan teks dari awal hingga selesai mempertahankan peta hash dari setiap kata yang Anda temukan (kunci) dan menambah frekuensi (nilai) setiap kali Anda menguraikan kata. Sederhana, mudah dan lambat.

Pendekatan MapReduce

Mendekati ini dari perspektif yang berbeda, Anda perhatikan bahwa Anda memiliki semua mesin cadangan ini tergeletak di sekitar dan Anda dapat membagi tugas ini menjadi beberapa bagian. Berikan setiap mesin 1Mb blok teks untuk diurai menjadi peta hash dan kemudian susun semua peta hash dari masing-masing ke dalam satu hasil. Ini adalah solusi MapReduce berlapis.

Proses membaca satu baris teks dan mengumpulkan kata-kata adalah fase Peta (Anda membuat peta sederhana yang mewakili kata-kata dalam garis dengan frekuensi 1,2,3 dll), maka fase Reduce adalah ketika setiap mesin menyusun garis mereka peta menjadi satu peta agregat.

Solusi keseluruhan berasal dari fase Reduksi lebih lanjut di mana semua peta agregat dikumpulkan (kata itu lagi) menjadi peta akhir. Agak lebih kompleks, paralel secara masif dan cepat.

Ringkasan

Jadi, untuk meringkas, jika masalah Anda cenderung diwakili oleh kunci, nilai, operasi agregat pada nilai-nilai itu secara terpisah maka Anda memiliki masalah kandidat untuk MapReduce.

Pola MapReduce diambil dari dunia pemrograman fungsional. Ini adalah proses untuk menerapkan sesuatu yang disebut catamorphism di atas struktur data secara paralel. Pemrogram fungsional menggunakan katamorfisme untuk hampir setiap transformasi atau peringkasan sederhana.

Dengan asumsi data Anda adalah pohon, faktor penentu adalah apakah Anda dapat menghitung nilai untuk sebuah node hanya menggunakan data yang terkandung dalam node itu dan nilai yang dihitung untuk anak-anaknya.

Misalnya Anda dapat menghitung ukuran pohon menggunakan katamorfisme; Anda akan menghitung jumlah nilai yang dihitung untuk semua anak ditambah satu.

WPI ini - Aplikasi Pengurangan Peta (ppt) mungkin menarik bagi Anda. Ini membahas aplikasi MR yang berbeda, dan sebagai salah satu kasus yang dibahas, ini menunjukkan bagaimana Menggunakan 100 EC2 instance dan 24 jam, New York Times dapat mengkonversi 4TB artikel yang dipindai menjadi 1,5 TB dokumen PDF.

Seperangkat contoh lain di mana MR membantu dalam mempercepat kinerja adalah di: Aster - SQL Map Reduce menunjukkan beberapa studi kasus teknologi SQL-Map Reduce termasuk Deteksi Penipuan, Transformasi, dan lainnya.

Peta / Mengurangi adalah bentuk khusus dari jenis algoritma tertentu. Anda menggunakannya untuk mengubah satu set data besar menjadi set data lain. (Dataset hasil mungkin besar atau tidak.) Jika Anda tidak ingin output data statis ditetapkan sebagai hasil input data statis, maka Peta / Perkecil tidak sesuai. Peta / Perkecil dapat dengan mudah memberi tahu Anda berapa banyak John Smiths di buku telepon Manhattan, tetapi tidak cocok untuk membangun server web.

Cara Map / Reduce bekerja adalah:

• Peta mengambil pasangan kunci (k1) dan nilai (v1) dan memetakannya ke dalam kumpulan kunci baru (k2) dan nilai (v2).
• Reduce mengambil semua nilai v2 dengan kunci k2 yang sama dan menghasilkan nilai baru (v3).

Hasilnya adalah daftar (k1, v1) pasangan ditransformasikan menjadi daftar (v3) s. (Tentu saja, nilai "v3" dapat berupa komposit yang mencakup k2, yang dapat didefinisikan sama dengan k1.)

Jadi, Anda menggunakannya:

1. Jika Anda memiliki begitu banyak data untuk memulai dengan menjalankan semuanya secara berurutan melalui satu atau dua server akan memakan waktu terlalu lama, dan

2. Anda dapat membayangkan data keluaran sebagai daftar nilai atau pasangan nilai kunci (umumnya tidak terlalu sulit ketika Anda mengingat "kunci" hanya berarti "label unik"), dan

3. Apa pun hubungannya, Anda yakin bahwa setiap data input hanya memengaruhi nilai output untuk satu kunci output.

Jika semua data Anda dapat diproses secara berurutan oleh satu server, maka karena itulah paradigma komputasi yang dominan (yang digunakan untuk server dan pemrogram dilatih), gunakan satu server.

Tahap peta harus mempartisi semua data input dengan kunci output. Itu tidak harus menghasilkan nilai output yang terkait dengan kunci output (yang dilakukan oleh tahap pengurangan), tetapi harus unik menetapkan setiap pasangan nilai kunci input untuk berkontribusi paling banyak nilai kunci output satu. Jika data terlalu saling terkait maka pengurangan peta mungkin tidak dapat menangani masalah. Di sisi lain, mungkin saja Anda perlu menggunakan beberapa putaran peta / perkecil.

Jika Anda tidak tahu cara mengubah transformasi data Anda menjadi peta / kurangi, maka tentu saja itu bukan solusi.

Ada seni nyata untuk mencari tahu jika masalah dapat diuraikan menjadi sesuatu yang bisa ditangani Peta / Kurangi. Misalnya v1 dan v2 mungkin tidak sama sekali dalam input atau output data set. Jika Anda hanya ingin menghitung item unik dalam data input, maka k1 = k2 = item dan v1 = v2 = 1 atau 0 atau benar-benar apa saja. Reduce hanya menghasilkan v3 sebagai jumlah dari jumlah k2 yang diberikan.

Jadi sulit untuk mengatakan dengan pasti bahwa transformasi data tidak dapat dilakukan menggunakan Map / Reduce, tetapi hal di atas memberi Anda beberapa petunjuk.

MapReduce berfungsi pada masalah apa pun yang terdiri dari tepat 2 fungsi di beberapa level abstraksi. Fungsi pertama diterapkan ke masing-masing item dalam set input, dan fungsi kedua mengumpulkan hasilnya.

Jadi, setiap kali Anda ingin mendapatkan (1) hasil dari (n) input, dan semua input dapat diperiksa / digunakan oleh (1) fungsi, Anda dapat menggunakan MapReduce. Sekali lagi, ini pada tingkat abstraksi tertentu. Fungsi (1) mungkin beberapa fungsi pengelompokan yang memeriksa input dan memutuskan mana dari beberapa fungsi lain yang akan digunakan.

Ini berguna ketika Anda tidak tahu sebelumnya berapa banyak input yang akan Anda miliki, ketika Anda perlu membagikan "unit" kerja secara diam-diam, atau ketika Anda ingin pengembalian tunggal untuk mewakili seluruh hasil (IE menjalankan lima ribu unit tes , dan jika kurang dari x% gagal, kembalikan sukses).

Sebagian besar jawaban di sini tampaknya merupakan variasi menjelaskan apa yang dilakukan pengurangan peta, yang valid. Tetapi untuk menjawab pertanyaan, pola mana yang akan memberi sinyal di mana Anda mungkin dapat menggunakan pengurangan peta tidak benar-benar ditangani oleh itu.

Jika implementasi masalah yang Anda lihat naif, tidak fungsional, melibatkan pengulangan atas sesuatu dan kemudian memperbarui sesuatu di luar pengulangan dengan beberapa keadaan dari dalam pengulangan, kemungkinan Anda memiliki sesuatu yang port-nya perlu dipetakan dengan baik. Terutama jika Anda dapat menggeneralisasi pembaruan negara pusat ke fungsi yang hanya berfungsi dengan dua parameter dan dapat menjamin fungsi ini komutatif dan asosiatif.

Alasan Anda mungkin ingin menggunakan pengurangan peta jika itu benar adalah dua kali lipat: 1) mungkin sedikit lebih bersih dan lebih mudah untuk menguji dan men-debug jika Anda memecah sesuatu menjadi peta dan mengurangi fungsi. 2) fungsi pengurangan peta tidak memiliki kewarganegaraan dan dapat dijalankan secara bersamaan, yang mempercepat segalanya jika Anda memiliki beberapa CPU yang tersedia dan sesuatu seperti hadoop atau percikan yang memanfaatkannya untuk menjalankan berbagai hal dalam sebuah cluster.

Ini bagus jika Anda mengulang banyak hal, tetapi jarak tempuh Anda dapat bervariasi tergantung pada seberapa kompleks peta Anda / pengurangannya. Sangat umum untuk berakhir dengan rantai sekuensial atau pohon pengurangan peta di mana pada akhirnya semuanya masih mengalami hambatan pada beberapa langkah reduksi kompleks di ujung rantai. Sebagai contoh, banyak algoritma grafik yang sulit untuk diukur secara efisien hanya dengan pengurangan peta.

Contoh paling sederhana yang bekerja dengan baik pada pengurangan peta, adalah menghitung barang, yang merupakan pengurangan yang sangat murah. Inilah sebabnya mengapa jumlah kata adalah contoh yang sering digunakan untuk pengurangan peta. Anda dapat mengharapkan skalabilitas linier untuk kinerja dengan penggunaan tersebut: setiap CPU yang Anda tambahkan membuatnya lebih cepat.

Jika Anda melakukan banyak pemrograman fungsional, Anda mulai mengalami situasi yang memerlukan peta umum dan mengurangi. Anda mungkin bahkan melihatnya dalam pemrograman imperatif, tetapi tidak mengenalinya di balik topeng loop dan akumulator.

Sebagai contoh yang muncul untuk saya baru-baru ini, saya telah mengerjakan parser di Haskell. Untuk menguji parser saya, saya memompa daftar fragmen string melalui parser, dan kemudian saya ingin mendapatkan string tunggal yang dapat saya hasilkan dari hasil saya untuk melihat apakah parsingnya benar. Jadi itu terlihat seperti:

--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]

--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input

--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t

--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings

--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))

Tentu saja, ini hanya pedagogis. Kode saya sebenarnya terlihat sedikit berbeda, dan menggunakan fungsi internal yang lebih (seperti fold concattidak diperlukan karena Haskell sudah termasuk unlinesyang melakukan [String]->String). Poin utama saya adalah bahwa saya tidak mengantisipasi menggunakan peta / mengurangi ketika saya mulai, itu hanya selaras dengan kebutuhan saya. Saya ingin melakukan beberapa hal dengan daftar, lalu mengubah daftar saya menjadi satu elemen output. Penggunaan peta / reduksi muncul secara alami.

Pemrosesan string (seperti penguraian) adalah salah satu penggunaan pengurangan peta yang sangat jelas, pemetaan adalah penerapan berbagai transformasi pada teks input, dan menguranginya dengan menyatukan kembali teks hasil sebagai output. Demikian juga, kompiler bisa serupa, menggunakan lipatan untuk mengubah aliran elemen Pohon Sintaks Abstrak menjadi bentuk yang lebih baik (mengoptimalkan).

Apakah bisa diparalel?

Setiap masalah yang dapat diperbaiki pada dasarnya adalah peta dan lipatan; sebaliknya, langkah peta secara inheren parallelisable (dan langkah lipatan mungkin, tergantung pada struktur yang dilipat), jadi ini adalah properti dua arah.

Katakanlah Anda sedang mencari sekelompok server dan satu tidak dapat merespons pada saat itu. Apa yang akan dilakukan mapReduce adalah karena ia tidak dapat mengakses simpul pohon ke Peta yang lebih besar apakah itu akan menjadwal ulang untuk nanti dan melakukan baik Peta atau Mengurangi itu. Pada dasarnya ia mencoba untuk menjamin semua informasi tersedia dengan ketidakpastian perangkat lunak dan perangkat keras di lingkungan.

Inilah pertanyaan utama yang saya gunakan untuk menyelidiki keputusan untuk menggunakan (atau tidak menggunakan) MapReduce.

• Apakah mencapai kinerja eksekusi paralel yang wajar dengan upaya programmer minimal penting untuk masalah yang diberikan?
• Apakah saya memiliki sejumlah besar (ratusan) elemen eksekusi paralel yang tersedia?
• Apakah ada bandwidth / throughput komunikasi yang sangat baik di antara elemen-elemen eksekusi paralel?
• Apakah saya perlu memproses sejumlah besar data (TB)?

• Apakah masalah yang saya coba pecahkan terurai menjadi operasi Map and Reduce?

  • Peta: Jalankan operasi yang sama pada semua data.
  • Reduce: Jalankan operasi yang sama pada setiap kelompok data yang dihasilkan oleh Peta.

pada dasarnya, ini adalah pola "divide and conquer" yang umum, sehingga solusi untuk mendistribusikan perhitungan dapat ditulis secara umum.

contoh sederhana seperti dokumen besar. masalahnya adalah Anda ingin menghitung jumlah huruf dalam dokumen itu. alih-alih berjalan pada satu mesin, Anda dapat memecahnya menjadi array dari semua kata dalam dokumen. maka Anda dapat memproses setiap kata satu per satu, dan hasilnya kembali bersamaan.

polanya berguna, karena begitu Anda mendapatkan peta generik / mengurangi implementasi yang berfungsi, Anda dapat menyelesaikan masalah apa pun dengan menggunakan lapisan perangkat lunak yang sama, Anda hanya perlu mengekspresikan masalah Anda.