طرح آماری الگوريتمهاي كنترل همروندي

پروژه آماري الگوريتمهاي كنترل همروندي در 16 صفحه ورد قابل ويرايش

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

در اين گزارش بر روي درستي و ساختار الگوريتمها متمركز خواهيم شد. در اين راستا براي ساختار پايگاه داده توزيعي يك سطحي از انتزاع را در نظر مي‌گيريم تا مساله تا حد ممكن ساده سازي شود.



1. مقدمه : كنترل همروندي فرآيندي است كه طي آن بين دسترسي هاي همزمان به يك پايگاه داده در يك سيستم مديريت پايگاه داده چند كاربره هماهنگي بوجود مي‌آيد. كنترل همروندي به كاربران اجازه مي‌دهد تا در يك حالت چند برنامگي با سيستم تعامل داشته باشند در حاليكه رفتار سيستم از ديدگاه كاربر به نحو خواهد بود كه كاربر تصور مي‌كند در يك محيط تك برنامه در حال فعاليت است. سخت ترين حالت در اين سيستم مقابله با بروز آوري هاي آزار دهنده اي است كه يك كاربر هنگام استخراج داده توسط كاربر ديگر انجام مي‌دهد. به دو دليل ذيل كنترل همروندي در پايگاه داده هاي توزيعي از اهميت بالايي برخوردار است:

كاربراان ممكن است به داده هايي كه در كامپيوترهاي مختلف در سيستم قرار دارند دسترسي پيدا كنند.
يك مكانيزم كنترل همروندي در يك كامپيوتر از وضعيت دسترسي در ساير كامپيوترها اطلاعي ندارد.

مساله كنترل همروندي در چندين سال قبل كاملا مورد بررسي قرار گفته است و در خصوص پايگاه‌داده‌هاي متمركز كاملا شناخته شده است. در خصوص اين مسال در پايگاه داده توزيعي با توجه به اينكه مساله در حوزه مساله توزيعي قرار مي‌گيرد بصورت مداوم راهكارهاي بهبود مختلف عرضه مي‌شود. يك تئوري رياضي وسيع براي تحليل اين مساله ارائه شده و يك راهكار قفل دو مرحله اي به عنوان راه حل استاندارد در اين خصوص ارائه شده است. بيش از 20 الگوريتم كنترل همروندي توزيعي ارائه شده است كه بسياري از آنها پياده سازي شده و در حال استفاده مي‌باشند.اين الگوريتمها معمولا پيچيده هستند و اثبات درستي آنها بسيار سخت مي‌باشد. يكي از دلايل اينكه اين پيچيدگي وجود دارد اين است كه آنها در اصطلاحات مختلف بيان مي‌شوند و بيان هاي مختلفي براي آنها وجود دارد. يكي از دلايل اينكه اين پيچدگي وجود دارد اين است كه مساله از زير قسمتهاي مختلف تشكيل شده است و براي هر يك از اين زير قسمتها يك زير الگوريتم ارائه مي‌شود. بهترين راه براي فائق آمدن بر اين پيچدگي اين است كه زير مساله ها و الگوريتمهاي ارائه شده براي هر يك را در ي.ك سطح از انتزاع نگاه داريم.

با بررسي الگوريتمهاي مختلف مي‌توان به اين حقيقت رسيد كه اين الگوريتمها همگي تركيبي از زير الگوريتمهاي محدودي هستند. در حقيقت اين زير الگوريتمها نسخه‌هاي متفاوتي از دو تكنيك اصلي در كنترل همروندي توزيعي به نامهاي قفل دو مرحله اي و ترتيب برچسب زماني مي‌باشند.

همانطور كه گفته شد، هدف كنترل همروندي مقابله با تزاحمهايي است كه در اثر استفاده چند كاربر از يك سري داده واحد براي كاربران بوجود مي‌آيد است. حال ما با ارائه دو مثال در خصوص اين مسائل بحث خواهيم نمود. اين دو مثال از محك معروف TPC_A مقتبس شده اند. در اين مثالها، يك سيستم اطلاعات را از پايگاه داده ها استخراج كرده و محاسبات لازم را انجام داده و در نهايت اطلاعات را در پايگاه داده ذخيره مي‌نمايد.

حالت اول را مي‌توان بروزآوري از دست رفته ناميد. حالتي را تصور كنيد كه دو مشتري از دو سيستم مجزا بخواهند از يك حساب مالي برداشت نمايند. در اين حالت فرض كنيد در غياب سيستم كنترل همروندي، هر دو با هم اقدام به خواندن اطلاعات و درج اطلاعات جديد در سيستم ميكنند. در اين حالت در غياب سيستم كنترل همروندي تنها آخرين درج در سيستم ثبت مي‌شود. اين حالت در شكل 1 نشان داده شده‌ است.





6-قفل دو مرحله‌اي با نسخه اوليه : قفل دو مرحله‌اي با نسخه اوليه يك تكنيك از نوع قفله دو مرحله‌اي است كه كه به افزونگي داده توجه خاصي دارد. يك كپي از هر داده منطقي به عنوان يك كپي يا نسخه اوليه از داده مزبور مطرح مي‌شود. قبل از دسترسي به هر گونه كپي از داده هاي منطقي، قفل صحيح بايد از كپي اوليه اخذ شود.

براي قفلهاي خواندني اين روش تعامل و ارتباطات بيشتري را نياز دارد.فرض كنيد كه ‏T يك تراكنش باشد كه بخواهد داده x را بخواند. در اينصورت اگر X1 كپي اوليه از x باشد و xi براي خواندن توسط تراكنش در دسترس باشد، تراكنش بايستي با x1 كه كپي اوليه داده است تعامل داشته و قفل خود را بدست آورد و پس از آن نيز با تعامل با xi داده مورد نظر خود را از Xi بخواند. براي قفلهاي نوشتني بر عكس پياده سازي پايه قفل دو مرحله اي تراكنش احتياجي به تعامل بيشتر با ساير dm ها ندارد. در پياده سازي پايه قفل دو مرحله اي، اگر يك تراكنش مي‌خواست داده x را بروز كند، لازم بود تا بر تمامي نسخه هاي x قفل نوشتني بزند و سپس عمل نوشتن را بر روي تمامي نسخه هاي x انجام دهد اما در اينجا فقط لازم است كه تراكنش قفل نوشتن را بر روي كپي اوليه قرار دهد و در صورت بدست آوردن قفل، بايد عمليات نوشتن را مانند روش قبل بر روي تمامي نسخه هاي x انجام دهد.

6-قفل دو مرحله‌اي با راي گيري : قفل دو مرحله اي با راي گيري پياده‌سازي ديگري از روشهاي قفل دو مرحله اي است كه در آن افزونگي داده بيشتر مد نظر قرار گرفته است. اين روش شكل تغيير يافته الگوريتم توافق اكثريت توماس است و تنها براي همزمان سازيهاي ww مناسب است.

براي فهم بهتر اين روش بهتر است آنرا در داخل روش two phase commit توصيف كنيم. فرض كنيد يك تراكنش بخواهد بر روي داده x مقدار جديدي را بنويسد، در اينصورت درخواست قفل به تمامي نسخه هاي داده x ارسال شود. در صورتيكه قفل قابل تخصيص باشد، DM دريافت كننده قفل بايستي يك پيام تخصيص قفل صادر نمايد. در صورتيكه قفل قابل تخصيص نباشد نيز يك پيام بلوكه شدن در خواست قفل ارسال مي‌گردد. در صورتيكه پيامها از dm هاي مختلف برگشت داده شد، حال tm ارسال كننده درخواست قفل اقدام به تصميم‌گيري مي‌نمايد. در صورتيكه تعداد قفلهاي اخذ شده داراي اكثريت باشند، آنگاه tm دقيقا مانند حالتي عمل ميكند كه قفلهاي لازم را بر روي نسخه داده اي مزبور بدست آورده است. در اين حالت tm باقي عمليات يعني نوشتن بر روي داده مزبور را انجام مي‌دهد. در صورتيكه قفلهاي لازم بر روي داده مورد نظر به تعداد اكثريت نباشد، Tm منتظر دريافت پاسخ تخصيص قفل از dm هايي كه پاسخ بلوكه شدن قفل را ارسال نمودند، مي‌شود. در اين حالت با دريافت پاسخ جديد از dm هايي كه قبلا درخواست را بلوكه كردند، tm تعداد قفلهاي لازم را بررسي مي‌كند. در صورت اخذ اكثريت آرا، اجراي خود را ادامه مي‌دهد. از آنجائيكه فقط يك تراكنش مي‌تواند در هر لحظه اكثريت قفلهاي نوشتن را بدست آورد در نتيجه فقط در هر لحظه فقط بك تراكنش مي‌تواند بر روي اطلاعات تغييرات اعمال نمايد. در هر لحظه فقط يك تراكنش مي‌تواند در فاز نوشتن خود قرار داشته باشد. در نتيجه تمامي نسخه هاي x داراي يك ترتيب مشخص و مشترك از مقادير مي‌باشند. نقطه قفل يك تراگنش جايي است كه يك تراكنش توانسته است اكثريت قفلهاي لازم را براي نوشتن براي هر آيتم داده‌اي در مجموعه نوشتاري خود بدست آورد. براي بروز آوري هاي با حجم بالا ، تراكنش بايستي اكثريت قفلهاي نوشتن را بر روي تمامي آيتمهاي داده اي نوشتني خود قبل از ارسال دستورات نوشتن بدست آورد.

در حقيقت، قفل دو مرحله اي با راي گيري مي‌تواند براي همزمان سازي عمليات هاي rw سازگار شود. براي اينكار براي خواندن يك نسخه داده‌اي بايستي قفل خواندن از تمامي نسخه هاي داده اي درخواست شود. در صورتيكه اكثريت قفل خواندن از dm ها بدست آيد مي‌تواند اطلاعات مورد نظر را بخواند. اين روش روش بسيار خوب و قدرتمندي است ولي در اين روش براي خواندن يك آيتم داده اي بايستي از تمامي سايتهايي كه داراي يك نسخه از آيتم داده‌اي مذكور هستند قفل خواندن اخذ شود كه عملا سيستم را بسيار كند مي‌كند.

7- قفل دو مرحله‌اي متمركز : بجاري توزيع نمودن زمانبندها بر روي سايتهاي مختلف، همه زمانبندها را بر روي يك سايت متمركز خواهيم نمود. در اين خالت اگر يك تراكنش بخواهد به يك داده x دسترسي پيدا كند بايد از سايت مذكور درخواست قفل مناسب بر روي داده مذكور نمايد. در اين وضعيت داده ممكن است بر روي يك سايت غير از سايت زمانبند مركزي قرار داشته باشد.

فرض كنيد تراكنشt بخواهد داده x را بخواند در اينصورت بايستي t يك قفل خواندن را از سايت مركزي درخواست نمايد. در اين حالت اگر قفل تخصيص داده شود تراكنش مي‌تواند اطلاعات را از يكي از سايتهايي كه داراي xهستند درخواست نمايد. در غير اينصورت بايد منتظر دريافت مجوز تخصيص ثقفل خواندن از سوي سايت زمانبند مركزي باشد. در حالتي كه داده x بر روي سايت مركزي زمانبند نيز باشد، درخواست قفل و داده بطور مشترك به سايت مركزي ارسال مي‌شود، در صورتيكه قفل قابل تخصيص باشد، عمليات خواندن به همراه تخصيص قفل انجام مي‌شود. براي عمليات بروز آوري و نوشتن نيز فرآيند تخصيص قفل به همين نحو است با اين تفاوت كه بعد از تخصيص قفل و اعلام به درخواست كننده از سوي سايت مركزي زمانبندي، سايت درخواست كننده موظف است تمامي كپي هاي نسخه هاي اطلاعاتي را بروز نمايد. اين روش نيز مانند قفل دو مرحله‌اي كپي اوليه مستلزم نقل و انتقال مضاعف پيام مي‌باشد.