بررسي ويژگي هاي الگوريتمهاي كنترل همروندي توزيعي

دسته بندي : علوم پایه » ریاضی
چكيده : در اين گزارش ما به بررسي ويژگي هاي الگوريتمهاي كنترل همروندي توزيعي كه بر پايه مكانيزم قفل دو مرحله اي(2 Phase Locking) ايجاد شده اند خواهيم پرداخت. محور اصلي اين بررسي بر مبناي تجزيه مساله كنترل همروندي به دو حالت read-wirte و write-write مي‌باشد. در اين مقال، تعدادي از تكنيكهاي همزمان سازي براي حل هر يك از قسمتهاي مساله بيان شده و سپس اين تكنيكها براي حل كلي مساله با يكديگر تركيب مي‌شوند.
در اين گزارش بر روي درستي و ساختار الگوريتمها متمركز خواهيم شد. در اين راستا براي ساختار پايگاه داده توزيعي يك سطحي از انتزاع را در نظر مي‌گيريم تا مساله تا حد ممكن ساده سازي شود.

1. مقدمه : كنترل همروندي فرآيندي است كه طي آن بين دسترسي هاي همزمان به يك پايگاه داده در يك سيستم مديريت پايگاه داده چند كاربره هماهنگي بوجود مي‌آيد. كنترل همروندي به كاربران اجازه مي‌دهد تا در يك حالت چند برنامگي با سيستم تعامل داشته باشند در حاليكه رفتار سيستم از ديدگاه كاربر به نحو خواهد بود كه كاربر تصور مي‌كند در يك محيط تك برنامه در حال فعاليت است. سخت ترين حالت در اين سيستم مقابله با بروز آوري هاي آزار دهنده اي است كه يك كاربر هنگام استخراج داده توسط كاربر ديگر انجام مي‌دهد. به دو دليل ذيل كنترل همروندي در پايگاه داده هاي توزيعي از اهميت بالايي برخوردار است:
1. كاربراان ممكن است به داده هايي كه در كامپيوترهاي مختلف در سيستم قرار دارند دسترسي پيدا كنند.
2. يك مكانيزم كنترل همروندي در يك كامپيوتر از وضعيت دسترسي در ساير كامپيوترها اطلاعي ندارد.
مساله كنترل همروندي در چندين سال قبل كاملا مورد بررسي قرار گفته است و در خصوص پايگاه‌داده‌هاي متمركز كاملا شناخته شده است. در خصوص اين مسال در پايگاه داده توزيعي با توجه به اينكه مساله در حوزه مساله توزيعي قرار مي‌گيرد بصورت مداوم راهكارهاي بهبود مختلف عرضه مي‌شود. يك تئوري رياضي وسيع براي تحليل اين مساله ارائه شده و يك راهكار قفل دو مرحله اي به عنوان راه حل استاندارد در اين خصوص ارائه شده است. بيش از 20 الگوريتم كنترل همروندي توزيعي ارائه شده است كه بسياري از آنها پياده سازي شده و در حال استفاده مي‌باشند.اين الگوريتمها معمولا پيچيده هستند و اثبات درستي آنها بسيار سخت مي‌باشد. يكي از دلايل اينكه اين پيچيدگي وجود دارد اين است كه آنها در اصطلاحات مختلف بيان مي‌شوند و بيان هاي مختلفي براي آنها وجود دارد. يكي از دلايل اينكه اين پيچدگي وجود دارد اين است كه مساله از زير قسمتهاي مختلف تشكيل شده است و براي هر يك از اين زير قسمتها يك زير الگوريتم ارائه مي‌شود. بهترين راه براي فائق آمدن بر اين پيچدگي اين است كه زير مساله ها و الگوريتمهاي ارائه شده براي هر يك را در ي.ك سطح از انتزاع نگاه داريم.
با بررسي الگوريتمهاي مختلف مي‌توان به اين حقيقت رسيد كه اين الگوريتمها همگي تركيبي از زير الگوريتمهاي محدودي هستند. در حقيقت اين زير الگوريتمها نسخه‌هاي متفاوتي از دو تكنيك اصلي در كنترل همروندي توزيعي به نامهاي قفل دو مرحله اي و ترتيب برچسب زماني مي‌باشند.
همانطور كه گفته شد، هدف كنترل همروندي مقابله با تزاحمهايي است كه در اثر استفاده چند كاربر از يك سري داده واحد براي كاربران بوجود مي‌آيد است. حال ما با ارائه دو مثال در خصوص اين مسائل بحث خواهيم نمود. اين دو مثال از محك معروف TPC_A مقتبس شده اند. در اين مثالها، يك سيستم اطلاعات را از پايگاه داده ها استخراج كرده و محاسبات لازم را انجام داده و در نهايت اطلاعات را در پايگاه داده ذخيره مي‌نمايد.
حالت اول را مي‌توان بروزآوري از دست رفته ناميد. حالتي را تصور كنيد كه دو مشتري از دو سيستم مجزا بخواهند از يك حساب مالي برداشت نمايند. در اين حالت فرض كنيد در غياب سيستم كنترل همروندي، هر دو با هم اقدام به خواندن اطلاعات و درج اطلاعات جديد در سيستم ميكنند. در اين حالت در غياب سيستم كنترل همروندي تنها آخرين درج در سيستم ثبت مي‌شود. اين حالت در شكل 1 نشان داده شده‌ است.
حالت دوم حالتي است كه در آن اطلاعات صحيح از پايگاه داده استخراج نمي‌شود. در اين حالت فرض كنيد دو مشتري بخواهند كارهاي ذيل را انجام دهند.
• مشتري 1: بخواهد يك چك 1 ميليوني را به حساب X واريز و از حساب Y برداشت نمايد.
• مشتري 2: بخواهد بيلان حساب مالي X و Y شامل كل موجودي را نمايش دهد.
در غياب كنترل همروندي همانطور كه در شكل 2 نشان داده شده‌است، تزاحم بين پروسس ها بوجود خواهد آمد. فرض كنيد در زماني كه مشتري 1 اطلاعات را از حساب Y خوانده و اطلاعات حساب X را دريافت نموده و 1 ميليون از حساب Y برداشت نموده ولي هنوز 1 ميليون به حساب X و اريز نكرده مشتري 2 اطلاعات كل دو حساب را دريافت نموده و نتيجه را چاپ نمايد. در اين حالت مشتري شماره 2 اطلاعاتي را كه به عنوان بيلان نمايش مي‌دهد 1 ميليون از مقدار واقعي كمتر است. اين حالت يك فرق اساسي با حالت اول دارد و آن اين است كه در اين حالت نتيجه نهايي در پايگاه داده درست خواهد بود در حاليكه اطلاعات دريافت شده بصورت موقت غلط خواهند بود.
مساله كنترل همروندي در پايگاه داده هاي توزيعي تا حدودي شبيه مساله دوبه‌دو ناسزگاري در سيستم عامل مي‌باشد. در مساله دوبه‌دو ناسازگاري، هماهنگي جهت دسترسي به منابع سيستم ائم از حافظه، ابزارهاي ورودي و خروجي و CPU و .... بوجود مي‌آيد. در اين حالت راه حلهاي گوناگوني ائم از قفلها، سمافورها، مونيتورها و ... پيشنهاد شده است.
كنرتل همروندي و دوبه‌دو ناسگاري از اين جهت كه هر دو دسترسي به منابع مشترك را كنترل ميكنند با هم شباهت دارند. با اين حال راه حلي كه براي يكي بكار مي‌رود قابل بهره برداري براي ديگري نيست. فرض كنيد پردازه هاي P1 و P2 بخواهند از نقاط مختلف كدهاي خود به منابع R1 و R2 دسترسي پيدا كنند. در سيستم عامل دسترسي مجزاي ذيل قابل قبول است. P2 از R1 استفاده كند، P2 از R1 استفاده كند، P2 از R2 استفاده نموده و سپس P1 از R2 استفاده نمايد. در پايگاه داده اين روند اجرا مورد قبول نيست و مشكلاتي را ايجاد مي‌كند. فرض كنيد P1 بخواهد از R1 مبلغي را به R2 انتقال دهد. در اين حالت اگر P2 مقادير R1 وR2 را چك كند مقادير غير صحيح را دريافت مي‌كند.
2. مدل پردازش تراكنش: براي اينكه روند اجراي عمليات در سيستمهاي پايگاه داده هاي توزيعي براي خواننده مشخص شود ما در اينجا يك مدل از پايگاه داده‌هاي توزيعي را ارائه مي‌دهيم. سپس نحوه عملكرد مكانيزم كنترل همروندي را در اين مدل بيان خواهيم نمود. در اين مدل پايگاه داده، يك پايگاه داده توزيعي مجموعه از سايتهاست كه توسط يك شبكه به هم متصل شده‌اند. هر سايت يك كامپيوتر است كه يكي يا هر دوي برنامه هاي ذيل را اجرا مي‌كند. برنامه‌ها شامل يك مدير تراكنش يا TM و يك مدير داده يا DM است. TM مسئول مديريت تعامل كاربر با پايگاه داده است و DM مسئول نگهداري داده‌ها است. شبكه نيز يك وسيله ارتباطي كامپيوتر – كامپيوتر است. فرض بر اين است كه شبكه كاملا امن مي‌باشد و پيامها را با همان ترتيبي كه وارد سيستم مي‌شوند به مقصد ارسال مي‌شود. فرض بر اين است كه تعداد داده هاي موجود در سيستم شامل X ، Y و Z است كه داده هاي منطقي موجود در سيستم را تشكيل مي‌دهند. داده هاي ذكر شده فقط واحد داده هاي منطقي هستند و ما با سايز و قالب و جزئيات آنها كاري نخواهيم داشت. هر پايگاه داده در اين سيستم يك نسبت دهي مقادير بصورت منطقي به اين داده هاي منطقي است. هر داده منطقي مي‌تواند در يك يا بيشتر از يك DM ذخيره شود. افزونگي داده در اثر ذخيره داده در چندين DM براي افزايش دسترسي به داده‌ها است. هر كپي از داده ذخيره شده آيتم داده ناميده مي‌شود. نسخه هاي متعدد داده X را بصورت X1,X2,... نشان داده مي‌شوند. كاربران با DDBMS از طريق اجراي تراكنشها تعامل دارند. تراكنشها مي‌توانند پرس و جو هاي ON-LINE باشند كه با زبان استاندارد پرس و جو ارسال شده اند. از طرفي تراكنشها مي‌توانند عملياتي باشند كه از طريق برنامه هاي نوشته شده به سيستم داده مي‌شوند. الگوريتمهاي كنترل همروندي، كاري با نوع تراكنشهاي موجود در سيستم ندارند و محاسبات انحام شده در اين تراكنشها تاثيري در روند اين الگوريتمها ندارد. بر خلاف اينها اين الگوريتمها تمام تصميم گيري هاي خود را بر اساس داده هايي كه اين تراكنشها به آنها دسترسي پيدا مي‌كنند انجام مي‌دهند. دسترسي ها مي‌توانند از نوع خواندن يا نوشتن باشند. فرض بر اين است كه محاسبات در تراكنشها كامل بوده و اگر تراكنش در يك پايگاه داده به تنهايي اجرا شود، پايگاه داده در حالت صحيح و مانا قرار گرفته و نتايج كاملا صحيحي در بر خواهد داشت. مجموعه منطقي خواندني يك تراكنش مجموعه اي از آيتمهاي داده اي است كه تراكنش مي‌خواند. اين امر در شكل 3 نمايش داده شده است.