Apa hal baru di MapReduce?

68

Beberapa tahun yang lalu, MapReduce dipuji sebagai revolusi pemrograman terdistribusi. Ada juga kritikus tetapi pada umumnya ada hype antusiasme. Bahkan dipatenkan! [1]

Namanya mengingatkan mapdan reducedalam pemrograman fungsional, tetapi ketika saya membaca (Wikipedia)

Langkah peta: Node master mengambil input, membaginya menjadi sub-masalah yang lebih kecil, dan mendistribusikannya ke node pekerja. Node pekerja dapat melakukan ini lagi pada gilirannya, yang mengarah ke struktur pohon multi-level. Node pekerja memproses masalah yang lebih kecil, dan meneruskan jawabannya kembali ke node masternya.

Kurangi langkah: Master node kemudian mengumpulkan jawaban untuk semua sub-masalah dan menggabungkan mereka dalam beberapa cara untuk membentuk output - jawaban untuk masalah yang pada awalnya berusaha dipecahkan.

atau [2]

Internal MAP: [...] MAP membagi nilai input menjadi kata-kata. [...] MAP dimaksudkan untuk mengaitkan setiap pasangan kunci / nilai yang diberikan dari input dengan banyak pasangan kunci / nilai potensial.

Internal REDUCE: [...] [REDUCE] melakukan agregasi imperatif (katakanlah, reduksi): ambil banyak nilai, dan kurangi menjadi satu nilai.

Saya tidak bisa tidak berpikir: ini membagi & menaklukkan (dalam arti Mergesort), sederhana dan sederhana! Jadi, apakah ada kebaruan (konseptual) di MapReduce di suatu tempat, atau itu hanya implementasi baru dari ide-ide lama yang berguna dalam skenario tertentu?

US Patent 7.650.331: "Sistem dan metode untuk pemrosesan data skala besar yang efisien" (2010)
Model pemrograman Google MapReduce - Revisited by R. Lämmel (2007)

algorithms distributed-systems parallel-computing algorithm-design Raphael
sumber

7

Tidak ada hal baru. Saya tidak akan membuat jawaban ini, tetapi pendapat saya yang kuat bahwa tidak ada yang baru dalam perhitungan, atau bahkan komputasi terdistribusi ditemukan oleh MapReduce.

edA-qa mort-ora-y

@Aryabhata: Jika ada hal baru, pertanyaan ini memiliki jawaban yang baik dan konstruktif. Jika tidak ada, sedikit yang bisa dikatakan membuktikannya (kecuali mungkin mengurangi MapReduce ke teknik yang lebih lama secara eksplisit), benar. Tetapi jika Anda merasakan hal itu, pilihlah!

Raphael

@ edA-qamort-ora-y: Dalam hal ini, kita harus dapat mengekspresikan MapReduce dalam istilah yang lebih lama, dan itu akan menjadi jawaban yang bagus!

Raphael

1

@ Raphael, saya setuju, tapi saya tidak yakin saya bisa melakukan itu. Namun, saya dapat mengamati, bahwa seperti yang dijelaskan di sini (kutipan pertama), sort gabungan menggunakan metode peta / reduksi yang tepat. Memang, memang bisa didistribusikan dengan nol perubahan.

edA-qa mort-ora-y

47

Saya tidak bisa tidak berpikir: ini adalah memecah belah & menaklukkan, sederhana dan sederhana!

M / R tidak membagi & menaklukkan. Ini tidak melibatkan aplikasi algoritma yang diulang ke subset yang lebih kecil dari input sebelumnya. Ini adalah pipeline (fungsi yang ditentukan sebagai komposisi fungsi yang lebih sederhana) di mana tahapan-tahapan pipa berganti-ganti peta dan mengurangi operasi. Tahap yang berbeda dapat melakukan operasi yang berbeda.

Jadi, apakah ada kebaruan (konseptual) di MapReduce di suatu tempat, atau itu hanya implementasi baru dari ide-ide lama yang berguna dalam skenario tertentu?

MapReduce tidak membuka dasar baru dalam teori perhitungan - ia tidak menunjukkan cara baru untuk menguraikan masalah menjadi operasi yang lebih sederhana. Ini menunjukkan bahwa operasi sederhana tertentu praktis untuk kelas masalah tertentu.

Kontribusi makalah MapReduce adalah

mengevaluasi saluran pipa dari dua operator ortogonal yang dipahami dengan baik yang dapat didistribusikan secara efisien dan toleran terhadap masalah tertentu: membuat indeks teks dari corpus besar
benchmarking pengurangan peta pada masalah itu untuk menunjukkan berapa banyak data yang ditransfer antara node dan bagaimana perbedaan latensi dalam tahap-tahap mempengaruhi latensi keseluruhan
menunjukkan bagaimana membuat sistem toleran terhadap kesalahan sehingga kegagalan mesin selama perhitungan dapat dikompensasi secara otomatis
mengidentifikasi pilihan implementasi yang optimal dan optimalisasi

Beberapa kritik termasuk dalam kelas-kelas ini:

"Peta / pengurangan tidak membuka landasan baru dalam teori perhitungan." Benar. Kontribusi tulisan asli adalah bahwa operator yang dipahami dengan baik dengan serangkaian optimasi tertentu telah berhasil digunakan untuk memecahkan masalah nyata dengan lebih mudah dan toleransi kesalahan daripada solusi sekali saja.
"Perhitungan terdistribusi ini tidak mudah terurai menjadi peta & mengurangi operasi". Cukup adil, tetapi banyak yang melakukannya.
"Sebuah pipa n peta / tahap pengurangan membutuhkan latensi yang proporsional dengan jumlah langkah pengurangan dari pipa sebelum hasil apa pun dihasilkan." Mungkin benar. Operator pereduksi harus menerima semua inputnya sebelum dapat menghasilkan output yang lengkap.
"Peta / pengurangan berlebihan untuk kasus penggunaan ini." Mungkin. Ketika para insinyur menemukan palu baru yang mengilat, mereka cenderung mencari apa pun yang tampak seperti paku. Itu tidak berarti bahwa palu bukanlah alat yang dibuat dengan baik untuk ceruk tertentu.
"Peta / pengurangan adalah pengganti yang buruk untuk DB relasional." Benar. Jika DB relasional menskala ke kumpulan data Anda, maka bagus untuk Anda - Anda memiliki opsi.

Mike Samuel
sumber

Yah, mereka menyebut kertas asli "seminal" jadi saya mengharapkan sesuatu yang baru. Saya tidak mendapatkan paragraf pertama Anda: jelas ada banyak teknik algoritmik yang tidak membagi & menaklukkan . Jika MapReduce adalah "hanya" implementasi yang efisien dari d & c untuk set masalah tertentu, itu pasti tidak ada yang seminal atau layak paten dalam algoritme (imho). Itu tidak mengatakan itu bukan sistem yang baik. Perhatikan bahwa kritik saya kurang dengan MapReduce itu sendiri (saya kira itu baik untuk apa itu dibuat) daripada dengan penerimaannya oleh komunitas.

Raphael

1

@ Raphael, saya tidak berpikir M / R adalah membagi & menaklukkan dalam arti yang Anda tautkan. Itu tidak melibatkan pengulangan aplikasi suatu algoritma ke subset yang lebih kecil dari input asli. Ini adalah jalur pipa di mana tahap-tahap pipa bergantian peta dan mengurangi operasi.

Mike Samuel

Hah, benar. Saya menafsirkan "Node pekerja dapat melakukan ini lagi pada gilirannya, mengarah ke struktur pohon multi-level." dengan cara ini, tetapi itu tentu saja tidak menyiratkan bahwa hal yang sama terjadi pada setiap tingkatan.

Raphael

1

@ ex0du5, saya pikir Anda mungkin mengutuknya karena klaim itu tidak berhasil. "Banyak sistem telah menyediakan model pemrograman terbatas dan menggunakan batasan untuk memparalelkan perhitungan secara otomatis. ... MapReduce dapat dianggap sebagai penyederhanaan dan distilasi beberapa model ini berdasarkan pada pengalaman kami dengan perhitungan dunia nyata yang besar. ... Berbeda , sebagian besar sistem pemrosesan paralel hanya diimplementasikan pada skala yang lebih kecil dan meninggalkan detail penanganan kegagalan mesin kepada programmer. " Ini mengutip makalah oleh Rabin dan Valiant tentang itu, tetapi bukan kertas Liskov.

Mike Samuel

1

@ ex0du5, Cukup adil. Saya pikir "" Peta / pengurangan tidak membuka landasan baru dalam teori perhitungan. "Benar." sudah cukup jelas tetapi saya sudah menulis ulang daftar kontribusi.

Mike Samuel

21

EDIT (Maret 2014) Saya harus mengatakan bahwa saya telah bekerja lebih banyak pada algoritma untuk model komputasi tipe MapReduce, dan saya merasa seperti saya menjadi terlalu negatif. Teknik Divide-Compress-Conquer yang saya bicarakan di bawah ini sangat serbaguna, dan dapat menjadi dasar dari algoritma yang menurut saya tidak mudah dan menarik.

Biarkan saya menawarkan jawaban yang akan jauh lebih rendah daripada Mike dalam hal kelengkapan, tetapi dari model sudut pandang teori komputasi / algoritma.

$O(n^\epsilon)$ $o(\log n)$

$O(1)$

Partisi contoh masalah (sering secara acak)
Lakukan beberapa perhitungan pada setiap partisi secara paralel dan mewakili hasil perhitungan dengan kompak
Gabungkan semua solusi subproblem yang direpresentasikan secara kompak pada satu prosesor dan selesaikan perhitungannya di sana

$n$ $O(\sqrt{n})$ $\sqrt{n}$

Sekarang, saya pikir ini sebenarnya adalah twist yang menarik pada divide dan conquer, twistnya adalah bahwa setelah tahap divide Anda perlu mengompres solusi subproblem sehingga sebuah prosesor tunggal dapat menaklukkan. Namun, sepertinya ini satu-satunya teknik yang kami buat sejauh ini. Gagal pada masalah dengan grafik jarang, seperti konektivitas jarang misalnya. Bandingkan ini dengan model streaming, yang menghasilkan banyak ide baru, seperti algoritma pengambilan sampel yang cerdik dari Flajolet dan Martin, algoritma pairing deterministik dari Misra dan Gries, kekuatan teknik sketsa sederhana, dll.

Sebagai paradigma pemrograman, pengurangan peta sangat berhasil. Komentar saya menganggap pengurangan peta sebagai model perhitungan yang menarik. Model teoritis yang baik agak aneh. Jika mereka mengikuti kenyataan terlalu dekat, mereka sulit digunakan, tetapi yang lebih penting, (meminjam istilah dari pembelajaran mesin) teorema terbukti untuk model yang terlalu spesifik tidak menggeneralisasi, yaitu tidak berlaku pada model lain. Itu sebabnya kami ingin mengabstraksi sedetail mungkin, sambil tetap menyisakan cukup untuk menantang kami untuk membuat algoritma baru. Akhirnya, ide-ide baru itu akhirnya bisa menemukan jalan kembali ke dunia nyata. PRAM adalah salah satu model yang tidak realistis yang menghasilkan ide-ide menarik tetapi ide-ide tersebut terbukti jarang berlaku untuk komputasi paralel dunia nyata. Di sisi lain, streaming juga tidak realistis, tapi itu menginspirasi ide-ide algoritmik yang sebenarnya digunakan di dunia nyata. Lihathitung-min sketsa . Teknik sketsa sebenarnya juga digunakan dalam sistem yang didasarkan pada pengurangan peta.

Sasho Nikolov
sumber

Namun bisa dibilang M / R adalah model yang lebih realistis (berguna) daripada PRAM atau stream. (Setidaknya untuk beberapa masalah yang cukup besar.)

Xodarap

"Anda perlu mengompres solusi subproblem sehingga satu prosesor dapat menaklukkan" - Anda tampaknya mengatakan bahwa set masalah yang dapat diselesaikan oleh M / R adalah subset dari mereka yang ada cache-tractable atau cache cache solusi -oblivious. Jika itu benar, maka menurut saya pernyataan ini berlaku sama baiknya dengan skema perhitungan yang paling banyak didistribusikan.

Mike Samuel

1

@Xodarap mungkin saja. di sini saya menggunakan sudut pandang teori algoritma murni: model berguna jika mengarah ke perspektif algoritmik baru. dengan ukuran itu, streaming tidak sepenuhnya realistis tetapi telah menyebabkan banyak teknik baru yang sebenarnya berguna dalam praktik. intinya adalah, apa abstraksi yang tepat yang mengarah pada pemikiran baru. abstraksi MR saat ini memiliki keberhasilan yang beragam (tetapi beberapa keberhasilan, saya kira)

Sasho Nikolov

1

@MikeSamuel "kebutuhan" dalam kalimat itu berarti bahwa inilah yang diperlukan teknik untuk bekerja, bukan itu satu-satunya hal yang mungkin dilakukan. tidak ada hasil negatif teoritis untuk MR yang saya tahu. Keluhan saya bukanlah bahwa MR benar-benar kurang kuat daripada CO. Itu karena kita belum melihat banyak pemikiran algoritmik baru yang terinspirasi oleh model (yang baik untuk sistem, tetapi mengecewakan untuk model perhitungan). di sisi lain ketidaktahuan cache itu sendiri adalah ide yang luar biasa imo

Sasho Nikolov

@SashoNikolov, Dipahami. Terima kasih telah menjelaskan.

Mike Samuel

6

Saya sangat setuju dengan Anda. Dari perspektif konseptual, tidak ada yang benar-benar baru: Map / Reduce awalnya dikenal dalam Parallel Computing sebagai model pemrograman data-flow. Namun, dari sudut pandang praktis, Map / Reduce seperti yang diusulkan oleh Google dan dengan implementasi open-source berikutnya juga telah memicu Cloud Computing dan sekarang cukup populer untuk dekomposisi dan pemrosesan paralel yang sangat sederhana. Tentu saja, itu tidak cocok untuk hal lain yang membutuhkan domain kompleks atau dekomposisi fungsional.

Massimo Cafaro
sumber

3

Saya pikir Anda sudah memukul kepala dengan komentar Anda.

Tidak benar bahwa dalam peta bahasa fungsional apa pun dapat diparalelkan - bahasanya harus murni . (Saya percaya Haskell adalah satu-satunya bahasa fungsional yang samar-samar secara umum. Lisp, OCaml, dan Scala semuanya tidak murni.)

Kami sudah tahu tentang manfaat kode murni sejak sebelum timesharing, ketika para insinyur pertama kali mem-pipel prosesor mereka. Jadi mengapa tidak ada yang menggunakan bahasa murni?

Ini sangat, sangat, sangat sulit. Pemrograman dalam bahasa murni sering terasa seperti pemrograman dengan kedua tangan terikat di belakang Anda.

Apa yang dilakukan MR adalah melonggarkan batasan kemurnian, dan menyediakan kerangka kerja untuk bagian-bagian lain (seperti fase acak) sehingga cukup mudah untuk menulis kode yang dapat didistribusikan untuk sebagian besar masalah.

$NC=P$

Xodarap
sumber

Saya tidak terbiasa dengan MapReduce, tetapi presentasi Anda tentang itu tidak terlihat berbeda dari apa yang saya ingat disajikan sebagai kasus ideal Paralelisme 101 pada abad sebelumnya.

Gilles 'SANGAT berhenti menjadi jahat'

@Gilles: Tujuan saya hanya untuk menunjukkan bahwa "bagilah & taklukkan"! = "Bagilah & taklukkan yang dapat didistribusikan ." M / R kurang sepele, meskipun bisa dibilang masih orisinal.

Xodarap

Dalam pemrograman fungsional, semua peta dapat diparalelkan (memalukan), jadi mengapa tidak berpegang pada paradigma itu? Saya tidak melihat bagaimana countvariabel yang dibagikan dalam kode semu Anda; cukup memberikan nilai saat ini untuk do_somethingbekerja. Bisakah Anda memberikan contoh algoritma d & c "nyata" (Mergesort, Quicksort, ...) yang mana panggilan rekursif bergantung satu sama lain (setelah panggilan dikeluarkan)?

Raphael

@Raphael: Saya telah menulis ulang jawaban saya untuk menanggapi komentar Anda dengan lebih baik. Saya bisa menambahkan contoh kapan kemurnian mengganggu, jika Anda masih mau.

Xodarap

1

@ Raphael: Saya setuju bahwa jawaban saya akan jauh lebih baik jika saya dapat mengutip beberapa makalah yang menunjukkan bahwa waktu pemrograman turun dari X jam ke Y dengan menggunakan M / R, atau meningkat dari A ke B dengan menerapkan kemurnian, tetapi saya pikir semua yang saya bisa lakukan adalah melambaikan tangan saya dengan marah dan bersikeras bahwa perbedaan itu tidak sepele.

Xodarap

Apa hal baru di MapReduce?

Jawaban: