Salah satu contoh utama yang digunakan untuk mendemonstrasikan kekuatan MapReduce adalah tolok ukur Terasort . Saya kesulitan memahami dasar-dasar algoritme pengurutan yang digunakan di lingkungan MapReduce.
Bagi saya, pengurutan hanya melibatkan penentuan posisi relatif suatu elemen dalam hubungannya dengan semua elemen lainnya. Jadi penyortiran melibatkan membandingkan "segala sesuatu" dengan "semuanya". Algoritme pengurutan rata-rata Anda (cepat, gelembung, ...) melakukannya dengan cara yang cerdas.
Dalam pikiran saya, membagi dataset menjadi banyak bagian berarti Anda dapat mengurutkan satu bagian dan kemudian Anda masih harus mengintegrasikan bagian-bagian ini ke dalam dataset yang diurutkan sepenuhnya 'lengkap'. Mengingat kumpulan data terabyte yang didistribusikan ke ribuan sistem, saya berharap ini menjadi tugas yang sangat besar.
Jadi bagaimana ini benar-benar dilakukan? Bagaimana cara kerja algoritma pengurutan MapReduce?
Terima kasih telah membantu saya memahami.
Saya memiliki pertanyaan yang sama saat membaca makalah Google MapReduce. @Yuval F 's jawaban cukup banyak memecahkan teka-teki saya.
Satu hal yang saya perhatikan saat membaca makalah ini adalah keajaiban terjadi di partisi (setelah peta, sebelum dikurangi).
Makalah ini menggunakan
hash(key) mod R
sebagai contoh pemartisian, tetapi ini bukan satu-satunya cara untuk mempartisi data perantara untuk berbagai tugas pengurangan.Hanya menambahkan kondisi batas untuk @Yuval F 's jawaban untuk membuatnya lengkap: misalkan min (S) dan max (S) adalah kunci minimum dan kunci maksimum antara tombol sampel; semua kunci <min (S) dipartisi menjadi satu tugas pengurangan; sebaliknya, semua kunci> = max (S) dipartisi menjadi satu tugas pengurangan.
Tidak ada batasan tegas pada kunci sampel, seperti min atau maks. Hanya, lebih merata kunci R ini didistribusikan di antara semua kunci, lebih "paralel" sistem terdistribusi ini dan kecil kemungkinan operator yang mengurangi memiliki masalah kelebihan memori.
sumber
Hanya menebak...
Mengingat kumpulan data yang sangat besar, Anda akan mempartisi data menjadi beberapa potongan untuk diproses secara paralel (mungkin dengan nomor catatan yaitu catatan 1 - 1000 = partisi 1, dan seterusnya).
Tetapkan / jadwalkan setiap partisi ke node tertentu di cluster.
Setiap node cluster selanjutnya akan memecah (memetakan) partisi menjadi partisi mini sendiri, mungkin dengan urutan alfabet kunci. Jadi, di partisi 1, berikan saya semua hal yang dimulai dengan A dan keluarkan ke partisi mini A dari x. Buat A (x) baru jika saat ini sudah ada A (x). Gantikan x dengan nomor urut (mungkin ini adalah tugas penjadwal untuk melakukannya). Yaitu Beri saya ID unik A (x) berikutnya.
Serahkan (jadwal) pekerjaan yang diselesaikan oleh mapper (langkah sebelumnya) ke node cluster "kurangi". Reduce node cluster kemudian akan lebih menyempurnakan jenis masing-masing A (x) bagian yang akan terjadi ketika semua tugas mapper selesai (Tidak dapat benar-benar mulai menyortir semua kata mulai w / A ketika masih ada kemungkinan masih ada akan menjadi partisi mini lain dalam pembuatan). Keluarkan hasil dalam partisi terurut terakhir (yaitu Sorted-A, Sorted-B, dll.)
Setelah selesai, gabungkan lagi partisi yang diurutkan menjadi satu dataset. Pada titik ini, ini hanyalah penggabungan sederhana dari n file (di mana n bisa menjadi 26 jika Anda hanya melakukan A - Z), dll.
Mungkin ada langkah perantara di antara ... Saya tidak yakin :). Yaitu memetakan lebih lanjut dan mengurangi setelah langkah pengurangan awal.
sumber