با سلام خدمت همه دوستای عزیزم و همراهای همیشگی
توی این پست میخوایم با هم یک مقدار الگوریتم MapReduce که یه مدل توسعه فراگیر شده هست رو بررسی کنیم. در واقع MapReduce برای اولین بار توسط جف دین و سانجی گماوات در گوگل توسعه داده شد و بعدها متن باز و به بنیاد آپاچی برای توسعه سپرده شد.
گوگل این الگوریتم رو برای رتبه بندی صفحات وب در نتایج جستجو توسعه داده.
در واقع MapReduce قادر به انجام محاسبات توزیع شده بر روی داده های کلان به صورت موازی بر روی نود های پردازش متععد هست.هر جاب توی MapReduce توی دو ست تسک به نام های Map و Reduce انجام میشه که عمدتاً برای جستجو و انتخاب داده ها در سیستم فایل توزیع شده هادوپ (HDFS) استفاده می شن.
اما MapReduce چطور کار میکنه؟
قبل از همه چیز باید بدونیم که ساختار داده شکل دهنده MapReduce به صورت Key Value هست. این الگوریتم حجم زیاده داده رو دریافت میکنه و بعد از پردازش خروجی رو به شکل جفت های Key, Value به ما میده. توی MapReduce توسعه دهنده توی دو فاز یه Mapper و یه Reducer رو به صورت زیر توسعه میده.
فاز Mapping:
توی این فاز MapReduce یک دیتاست بسیار بزرگ رو که میخوایم روش پردازش انجام بدیم رو دریافت میکنه و در اولین قدم که Splitting بهش میگیم این دیتا ست بزرگ رو به تیکه های کوچیک تر میشکنه. برای درک بهتر همه چیز با یه مثال جلو میریم:
فکر کنید همراه اول میخواد ببینه توی ۱۰۰۰ روز گذشته هر شماره موبایل چند تا اس ام اس ارسال کرده. شاید این موضوع خیلی ساده باشه ولی برای مثال گزینه مناسبه.
توی قدم اول MapReduce این دیتا ست هزار روزه رو مثلا به ۱۰ تیکه ۱۰۰ روزه میشکنه. این قدم یعنی Splitting جزوی از فانکشن مپ نیست ولی توی فاز مپینگ قرار میگیره.
توی قدم بعدی یعنی قدم Mapping هر کدوم از تیکه های ورودی به یک سری ست Key, Value تبدیل میشن . مثلا (۰۹۱۲۰۰۰۰۰۰۰, ۱) و (۰۹۱۲۰۰۰۰۰۰۱, ۱) و (۰۹۱۲۰۰۰۰۰۰۰, ۱) و ….. و برای فاز Reducing آماده میشن.
فاز Reducing:
قبل از رسیدن به Reducer قدم های متعددی برداشته میشه. اولین قدم بعد از تولید مپ ها عملیاتی تحت نام Combining هست که روی این جفت های Key, Value اتفاق میوفته. دوستانی که با MapReduce کار کرده باشن میدونن که Combining از کلاس Reduce ارث بری میکنه و انگار داره یه reduce کوچیک لوکال روی نودی که map رو تولید کرده ران میکنه و همه مقادیر رو با توجه به کلیدشون Aggregate میکنه. مثلا میشه (۰۹۱۲۰۰۰۰۰۰۰, ۲) و ….. هر چند که اجرای این قدم کاملا اختیاریه و میتونید اصلا این یک قدم رو انجام ندید.
توی قدم بعدی عملیات Partitioning اتفاق میفوته. توی Partitioning چه شما عملیات Combine رو انجام داده باشید چه نداده باشید الزامی هست. توی این قدم کلید های خروجی فاز Map به تسک های Reduce اختصاص داده میشن. این فرآیند با استفاده از یک HashPartitioner اتفاق میوفته که شما هم میتونید خودتون Hashing پیشفرضش رو تغییر بدین یا از خود Hashing Algorithm پیشفرض MapReduce استفاده کنید.
مرحله سوم Shuffling & Sorting هست که اولین قدم از فاز Reduce هست. توی این مرحله همه key/value ها با کلید یکسان به یک Reducer اختصاص داده میشن و چون ممکنه بیشتر از یک کلید به یک Reducer اختصاص داده بشه عملیات سورتینگ هم اتفاق میوفته و اگر دوست دارید بدونید از چه الگوریتمی برای سورت استفاده میکنه الگوریتم مرج سورت هست.
در مرحله نهایی تمامی مقادیر یک کلید با هم جمع شده و در نهایت یک کلید با جمع کلیه مقادیر میسازه و یک جفت key value نهایی رو تشکیل میده چرا که ممکنه شما توی خروجی هر ۱۰ نود Mapper تون یک کلید داشته باشید و در نهایت جمع همه این مقادیر برای این کلید رو میخواید.
استفاده از Combiner به اندازه ای بار Reducer رو کم میکنه و از طرفی بار Mapper رو افزایش میده چرا که Combiner روی نود Mapper به صورت لوکال ران میشه.
نکته حائز اهمیت دیگه هم اینه که این فاز ها و قدم ها به صورت متوالی اتفاق میوفتن و تا یک قدم تموم نشه قدم بعدی شروع نمیشه یعنی تا فاز mapper تموم نشده فاز reducer شروع نمیشه.
نوشتن برنامه MapReduce چه شکلیه؟
یه برنامه MapReduce شامل کد های Mapper و Reducer به علاوه یه سری تنظیمات مثل اینی که دیتاسورس کجاست، کجا خروجی رو ذخیره کنه و … هست. شما به عنوان یه برنامه نویس کد هارو مینویسید و جاب رو به یه نود کلاستر یا گرید ارسال میکنید و فریمورک خودش زحمت بقیه چیزا رو میشکه که شامل تیکه کردن داده، برنامه ریزی تسک ها و کارایی که باید انجام بشه توی کلاستر یا گرید، COLOCATE کردن کد و داده های ورودی و خروجی های هر قدم، همگام سازی های مورد نیاز توی کلاستر یا گرید، ارور هندلینگ و ….. هست.
راستی چند بار گفتیم کلاستر و گرید! فرقشون چیه؟
اگر همه نود های Map و Reduce توی یک دیتا سنتر باشن بهشون اصطلاحا میگیم کلاستر و اگر در مناطق مختلف جغرافیایی باشن بهشون میگیم گرید.
چرا از MapReduce استفاده میکنیم؟
وقتی با داده های با حجم خیلی بالا معمولا چند ده ترابایت تا چند پتابایت سروکار داریم معمولا دیتابیس های سنتی دچار مشکلات عدیده و پدیده ای میشن بخواین روی یه همچین حجم داده ای Query & Select بزنید و ممکنه چند روز یا حتی بیشتر دیتابیس مشغول پردازش باشه. یا از طرفی امکان ذخیره این حجم داده معمولا به صورت یک جا وجود نداره و شارد شده باشه. یا برای پردازش سرور های یا حتی mainframe های خیلی گرون قیمتی نیاز داریم بتونن این پردازش هارو انجام بدن. بنابراین میایم از MapReduce استفاده میکنیم تا بتونیم این پردازش هارو توی زمان کوتاه تری و روی سخت افزار های کاملا معمولی به صورت موازی انجام بدیم.
همچنین سیستم فایل توزیع شده عملکرد اجرای این فرآیند هارو بهتر میکنه چرا که مسئول سازماندهی محاسبات به صورتیه که داده ها به سریالی توی نود های مختلف پردازش بشن و از دسترسی های تصادفی به داده ها اجتناب بشه.
کجا ها از MapReduce میشه استفاده کرد؟
دوستان MapReduce رو هر جایی که مسئله شما با پارادایمش همخوانی داشته باشه و حجم داده هاتون وحشتناک زیاد باشه میتونید استفاده کنید. برای یوز کیس هایی مثل Distributed grep، Count Access Frequency، Reverse Graph، Inverted Index و ….. هم زیاد استفاده میشه.
شاید یه نمونه شبه کد ببینیم جالب باشه.
نمونه شبه کد برای شمردن تعداد اس ام اس های هر شماره موبایل شبیه زیر میشه:
Function Map (number a, logs b):
—–For all number t ∈ logs b do
———-Emit (number t, count 1);
—–End
Function Reduce (number t, counts [c1, c2, c3 ,…..]):
—–Sum = 0;
—–For all count c ∈ counts[c1, c2, c3, …] do
———-Sum = sum + c;
———-Emit (number t, count sum);
—–End
توی این شبه کد mapper به ازای هر شماره تلفن یک جفت کلید میسازه و هر شماره یک کلید و یک عدد صحیح به عنوان تکرار مقدار (اگر کمباین نکنید تا خروجی reducer این مقدار همیشه ۱ هست) میسازه و بعدش reducer تمام value های مرتبط با هر شماره تلفن رو جمع میکنه و جفت کلید خروجی نهایی رو میسازه که شامل شماره تلفن و تعداد اس ام اس هاش توی ۱۰۰۰ روز گذشته هستند.
امیدوارم براتون مفید واقع شده باشه.
دیدگاه خود را بنویسید