خانه --> بسترهای پردازش توزیع شده --> روش تحلیل و پردازش گراف های بزرگ

روش تحلیل و پردازش گراف های بزرگ

در قسمت های پیشین با تئوری گراف و تئوری شبکه اجتماعی آشنا شدیم. در این قسمت به روشهای معمول که در پردازش گراف های بزرگ مورد استفاده قرار میگیرد میپردازیم. این موارد را برای این بررسی میکنیم تا در زمان بررسی ابزار ها و فناوری های پردازش گراف های بزرگ مانند گرافچی و تایتان با ادبیات موضوع آشنا باشیم. سه رویکرد مهم در تحلیل و پردازش گراف های بزرگ عبارتند از:

  • روش پردازش گراف Vertex-Centrice (راس محور)
  • روش برنامه نویسی MapReduce (نگاشت/ کاهش)
  • روش حافظه اشتراکی

لازم به ذکر است که ابزار های یا تکنولوژی های تحلیل گراف ممکن است یک یا بیش از یکی از این روش ها را همزمان برای پردازش گراف های بزرگ استفاده کنند.

روش پردازش گراف Vertex-Centrice (راس محور)

نام دیگر این رویکرد Pregel است که توسط گوگل ارائه شده است. و از مدل برنامه نویسی Bulk Synchronous Parallel الگو گرفته شده است. این روش با انجام گام هایی از فعالیت های تکراری بر روی گره های گراف انجام میشود که هر گام به عنوان Superstep شناخته میشود. این گام ها برای هر نود تا زمانی ادامه مییابد تا آن گره به هدف رسیده و غیر فعال شود.

روش عملکرد به این صورت است که در ابتدا تابعی توسط کاربر تعریف شده و در هر گام بر روی نود های گراف اجرا میشود و نتیجه رفتار آن گره ها بعد از اعمال تابع بدست می آید. این گام ها برای هر نود تا زمانی ادامه مییابد تا آن گره به هدف تابع تعریف شده توسط کاربر رسیده باشد و غیر فعال شود. به عبارتی گره های فعال زمانی غیر فعال میشوند که به هدف رسیده باشند و دیگر از سایر گره های پیامی دریف نکنند (ممکن است گره ای که در یک گام غیر فعال بوده دوباره در گام های بعد با دریافت پیام فعال شود). بعد از اعمال تایع بر روی گره نتیجه ی آن در گام بعدی به گره های اطراف یا هر گره دیگری که مشخص شده باشد ارسال میشود. گره ها با حرف V و گام ها با حرف S مشخص میشوند. رفتار گره V در گام S مشخص است. نتیجه اعمال تابع در گام S-1 گرفته شده و به عنوان ورودی به تابع در گام S تحویل و اعمال می شود و سپس بعد از اجرای گام فعلی، نتیجه اجرای تابع به گام S+1 برای تکرار بعدی ارسال میگردد. کار پردازش زمانی تمام است که تمامی گره های غیر فعال شده  باشند یا به عبارتی دیگر همه گره ها به هدف رسیده باشند. برنامه های مانند Graphchi و GraphLab  با مدل Vetrex-Centric نوشته شده اند.

به عنوان مثال میخواهیم با این روش در گراف زیر بزرگترین مقدار گره را در کل گراف تشخیص دهیم. هر گره با توجه به جهت گراف مقدار خود را به گره کناری جهت مقایسه مقادیر ارسال میکند. هر گره ای که مقدار آن از مقدار دریافت شده کوچکتر باشد مقدار خود را با مقدار بزرگتر جایگزین میکند و هر گره ای که مقدار دریافتی از گره کناری از مقدار خود کمتر باشد غیر فعال میگردد. این عمل انقدر تکرار میشود که تمامی گره های غیر فعال شده  باشند. یا به عبارتی تمامی گره بزرگترین مقدار را نشان دهند. به این ترتیب بزرگترین مقدار کشف میشود. شکل زیر به سادگی این مراحل را نشان می دهد. از نوع روش نوضیح داده شده مشخص است که این کار را میتوان به سرعت خیلی زیاد و به طور موازی انجام داد.

Vertex centric (Pregel Exampl)e
Vertex centric (Pregel Exampl)

http://backstopmedia.booktype.pro/big-data-dictionary/pregel/

روش برنامه نویسی MapReduce (نگاشت/ کاهش)

ار دیگر روش های پردازش گراف های بزرگ مپ ردیوس است. توسط چارچوب محاسباتی MapReduce می­توان حجم عظیمی از داده ­ها را بصورت توزیع شده و موازی پردازش کرد. MapReduce، مدل برنامه نویسی جهت پردازش و تولید مجموعه­ های داده ه­ای عظیم است. در محاسبه، مجموعه ­ای از جفت­ های کلید/مقدار ورودی، دریافت و مجموعه­ ای از جفت­ های کلید/مقدار خروجی، تولید می­شود. توسعه دهنده توسط مدل برنامه­ نویسی نگاشت/کاهش، محاسبه موردنظر خود را می­تواند به عنوان دو تابع نگاشت و کاهش بیان کند. تابع نگاشت که توسط کاربر نوشته می­شود، یک جفت ورودی می­گیرد و مجموعه­ ای از جفت­ های کلید/مقدار میانی را تولید می­کند. کتابخانه نگاشت/کاهش، تمام مقادیر میانی مرتبط با همان کلید میانی I را با هم گروه ­بندی می­کند و آن­ها را به تابع کاهش می ­سپارد. تابع کاهش نیز توسط کاربر نوشته می­شود و یک کلید میانی I و مجموعه ­ای از مقادیر برای آن کلید را می ­پذیرد. این تابع سپس این مقادیر را با هم ادغام می­کند تا مجموعه­ ای از مقادیر کوچک­تر را تشکیل دهد. معمولا فقط صفر یا یک مقدار خروجی در هر فراخوانی نگاشت ایجاد می­شود.

مپ-ردیوس یا نگاشت-کاهش، یک چارچوبی برای نوشتن برنامه­ هایی است که نیاز به پردازش بر روی داده ­های بسیار زیادی (چندین ترابایت از مجموعه داده ­ها) دارند بطوریکه این پردازش ­ها بصورت موزای با قابلیت اعتماد و تحمل پذیری بالا روی خوشه‌هایی با سخت­ افزارهای معمولی اجرا شوند. عملکرد در مپ-ردیوس شبیه سیستم خط لوله‌ای (pipeline) یونیکس است.

UNIX pipeline: cat input | grep | sort | uniq –c | cat > output

MapRedue: Input | Map |Shuffle & Sort | Reduce | Output

در مپ-ردیوس معمولاً داده­ های ورودی به تکه ­های مستقلی تقسیم می­شوند. این تکه­ ها توسط گره ­های نگاشت بصورت کاملاً موازی پردازش می­شود. سپس خروجی نتایج نگاشت‌ها به عنوان ورودی به گره­ های کاهنده داده می­شود(خروجی نتایج مپ ممکن است برحسب نیاز مرتب شوند). ورودی­ها و خروجی­های مراحل نگاشت-کاهش، به فرمت «کلید، مقدار» هستند. چارچوب مپ-ردیوس مسئول زمانبندی وظیفه ­ها، مانیتور کردن آن‌ها و اجرای دوباره وظیفه­ های شکست خورده است. مدل محاسباتی مپ-ردیوس در شکل زیر نمایش داده شده است.

مپ ردیوس
MapReduce Workflow
Map Reduce Job Tracker and Tasl Tracker
Map Reduce Job Tracker and Tasl Tracker

مپ-ردیوس شامل یک JobTracker رئیس و چندین TaskTracker مرئوس است. هر کار جدیدی که ایجاد می­شود یک JobTracker آن کار را به چندین TaskTracker می‌شکند. هر TaskTracker بر روی یک ماشین مجزا اجرا می­شود. هر TaskTracker قسمتی از کار را انجام می­دهد و JobTracker مسئول زمانبندی و تقسیم وظایف است. در صورتیکه یک TaskTracker با خطا مواجه شد، توسط JobTracker یک TaskTracker دیگر آن وظیفه را دوباره اجرا می­کند. شمای کلی JobTracker و TaskTracker در شکل زیر آمده است. در زیر انواع نگاشت کاهش نمایش داده شده است.

انواع نگاشت کاهش
انواع نگاشت کاهش

روش حافظه اشتراکی

در این روش گراف بزرگ توسط سیستم های پردازشی به اشتراک گذاشته می شود تا پروسه های بر روی ماشین های پردازشی مختلف به بخش های مورد نیاز خود از گراف بزرگ دسترسی پیدا کنند تا عملیات مورد نیاز را بر روی گراف انجام دهند ویا داده ها را ویرایش کنند. در این روش ممکن است در عمل حافظه RAM استفاده نشود و در عوض بخشی از فضای دیسک را به نحوی پیکربندی کرد که رفتار حافظه RAM را از خود نشان دهد(RAM Disk). این روش پردازش به غیر از حوزه گراف در موارد دیگر نیز کاربرد دارد. فقط نکته مهم آن است که پردازه ها باید بلد باشند که داده های متناسب با نیاز خود را از حافظه واکشی کنند. این روش شاید مقیاس پذیری و انعطاف مطلوب برای افزایش ماشین های پردازشی را نداشته باشد.

حافظه اشتراکی
Shared Memory
روش حافظه اشتراکی برای پردازش گراف های بزرگ
روش حافظه اشتراکی برای پردازش گراف های بزرگ
نمونه ای از یک معماری سامانه با روش حافظه اشتراکی برای پردازش کراف های حجیم
نمونه ای از یک معماری سامانه با روش حافظه اشتراکی برای پردازش کراف های حجیم

آدرس کانال تلگرام سایت بیگ دیتا:

t.me/bigdata_channel

آدرس کانال سروش ما:
https://sapp.ir/bigdata_channel

جهت دیدن سرفصل های دوره های آموزشی بر روی اینجا کلیک کنید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *