طبقه بندی مکانیزم های کنترل همروندی

به چندین روش می توان الگوریتم های کنترل همروندی را دسته بندی کرد. نوع توزیع پایگاه داده مسلما یکی از عوامل دسته بندی خواهد بود. به عنوان مثال برخی از روش های کنترل همروندی نیاز به یک پایگاه داده کاملا تکرارپذیر دارند در حالی که برخی دیگر می توانند روی پایگاه داده های تقسیم شده هم کار کنند.

از دیدگاه دیگر الگوریتم های کنترل همروندی می توانند براساس توپولوژی شبکه ای که رویش کار می کنند دسته بندی شوند. به عنوان مثال الگوریتم هایی که به شبکه های پخش همگانی نیاز دارند یا الگوریتم هایی که روی شبکه هایی با مدل ستاره یا دوار کار می کنند.

اما دسته بندی اصلی که صورت می گیرد به صورت:

1.      الگوریتم هایی که براساس دسترسی انحصاری به پایگاه داده بنا شده اند مثل قفل گزاری

  1. الگوریتم هایی که تلاش می کنند به وسیله ی مجموعه قوانینی اجرای تراکنش ها را ترتیب گزاری کنند.

 

اگر بخواهیم از بالاتر به موضوع بنگریم می توانیم این الگوریتم را به دو گروه تقسیم کنیم:

1.      دیدگاه بدبینانه: بین بسیاری از تراکنش ها تصادم ایجاد خواهد شد.

  1. دیدگاه خوشبینانه: تعداد تراکنش هایی که با یکدیگر در تصادم خواهد بود آن قدر هم زیاد نیست.

 

در واقع الگوریتم های کنترل همروندی بدبینانه خیلی زود در مرحله اجرا به همزمان سازی تراکنش ها می اندیشند. در حالی که الگوریتم کنترل همروندی خوشبینانه تا مرحله پایانی تراکنش ها سعی می کنند این همزمان سازی را به تاخیر بیندازند. الگوریتم های خوشبینانه را می توانیم شامل الگوریتم های قفل گزاری، الگوریتم های بر پایه ترتیب گزاری و همچنین الگوریتم های ترکیبی درنظر بگیریم.

الگوریتم های بدبینانه هم باز می توانند شامل الگوریتم های قفل گزاری و ترتیب گزاری باشند.

 

مکانیزم های کنترل همروندی بر پایه قفل دو مرحله ای

قفل دو مرحله ای با تشخیص روشن تداخل بین عملیات های همروند و جلوگیری از آنها، بین عملیات های خواندن و نوشتن همزمانی به وجود می آورد. قبل از اینکه یک تراکنش X را بخواند باید یک قفل خواندن بر روی X قرار دهد و قبل از اینکه یک تراکنش روی داده X بنویسد، باید یک قفل نوشتن روی X قرار دهد. تصاحب قفل ها با توجه به دو قانون بدست می آید:

1.      تراکنش های مختلف نمی توانند قفل هایی که باعث ایجاد تداخل می شوند بدست آورند.

  1. زمانی که یک تراکنش شروع به آزاد کردن قفل های خود نمود، دیگر نمی تواند قفل دیگری بدست آورد.

 

قفل هایی که باعث تزاحم می شوند با توجه به نوع همزمان سازی مشخص و تعریف می شوند. برای حالت 1W دو قفل زمانی با هم تداخل دارند که دو شرط در آنها صدق کند:

1.      هر دو قفل بر روی یک داده واحد باشند.

  1. یکی قفل نوشتنی و دیگری قفل خواندنی باشد.

 

برای حالت WW دو قفل زمانی با هم تداخل دارند که دو شرط در آنها صدق می کند:

1.      هر دو قفل بر روی یک داده واحد باشند.

  1. هر دو قفل از نوع نوشتنی باشند.

 

قانون دوم ایجاب می کند که هر تراکنشی برای بدست آوردن قفل دو فاز را طی کند در فاز اول که فاز دستیابی به قفلهاست، تراکنش اقدام به بدست آوردن قفل های لازم می کند. در فاز دوم که فاز تخلیه است، تراکنش به مرور زمان قفل های خود را آزاد می کند. هنگامی که تراکنش خاتمه پیدا می کند که قفل ها رها می شوند.

روش های مختلفی برای الگوریتم های قفل دو مرحله ای پیشنهاد شده است. یکی از این روش ها این است که تراکنش قفل های موردنیاز را قبل از اجرای اصلی خود بدست آورد. این نسخه از قفل دو مرحله ای را پیش تعریف می نامند. برخی از سیستم های تراکنش ها را مجبور می کنند تا قفل های خود را تا پیش از خاتمه نگه دارند. قفل دو مرحله ای یک تکنیک صحیح ایجاد قابلیت توالی است. این امر با بررسی سیستم از لحاظ عدم وجود حلقه و دور در روابط rwr و ww مشخص است. ترتیب اجرای تراکنش ها با ترتیب بدست آوردن قفل ها مشخص می گردند. نقطه ای که در آن تراکنش تمامی قفل های موردنیاز خود را بدست آورده است را نقطه تصاحب قفل می نامند. روش های مختلفی برای ایجاد الگوریتم قفل دو مرحله ای در سیستم های توزیعی وجود دارد که در قسمت بعد مورد بررسی قرار می گیرد.

 

پیاده سازی پایه قفل دو مرحله ای

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

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

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

 

قفل دو مرحله‌اي با نسخه اوليه

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

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

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

 

قفل دو مرحله‌اي با راي گيري

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

براي فهم بهتر اين روش بهتر است آنرا در داخل روش 2pc توصيف كنيم. فرض كنيد يك تراكنش بخواهد بر روي داده x مقدار جديدي را بنويسد، در اينصورت درخواست قفل به تمامي نسخه هاي داده x ارسال شود.

در صورتيكه قفل قابل تخصيص باشد، DM دريافت كننده قفل بايستي يك پيام تخصيص قفل صادر نمايد. در صورتيكه قفل قابل تخصيص نباشد نيز يك پيام بلوكه شدن در خواست قفل ارسال مي‌گردد. در صورتيكه پيامها از dm هاي مختلف برگشت داده شد، حال tm ارسال كننده درخواست قفل اقدام به تصميم‌گيري مي‌نمايد.

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

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

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

 

قفل دو مرحله‌اي متمركز

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

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

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

 

الگوریتم های کنترل همروندی مبتنی بر مهر زمانی

برخلاف الگوریتم های مبتنی بر قفل گذاری، الگوریتم های کنترل همروندی مبتنی بر مهر زمانی تلاشی برای نگه داری قابلیت توالی به وسیله انحصار متقابل نمی کنند. در عوض آن ها از روش قیاس یک ترتیب متوالی را انتخاب می کنند و مطابق آن تراکنش ها را اجرا می کنند. برای پیاده سازی این روش مدیر تراکنش برای هر تراکنش Ti در شروع کارش یک مهر زمانی انحصاری مانند (Ti)ts تعیین می کند.

یک مهر زمانی در واقع یک شناسه ساده برای شناسایی هر تراکنش به صورت یکتاست و همچنین برای اجازه ترتیب بندی.

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

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

اگرچه مهر زمانی یک فرم دو بخشی دارد (مقدار شمارنده ملحی و شناسه سایت)، شایان ذکر است که شناسه سایت در محل کم ارزش تر قرار می گیرد. بنابراین برای دو تراکنشی که مقدار شمارنده محلی یکسانی داشته باشند می توان از شناسه های سایت به تنهایی استفاده کنیم.

شایان ذکر است که اگر هر سیستمی بتواند به ساعت سیستمش دسترسی داشته باشد می توان از آن به جای مقدارهای شمارنده استفاده کرد. با توجه به معلومات بالا ترتیب بندی اجرای تراکنش ها براساس مهر زمانیشان کار چندان دشواری به نظر نمی رسد.

 

قانون ترتیب مهر زمانی (TO)

برای دو عملیات Oij و Okl متعلق به تراکنش های Ti، Tk و Oij تنها و فقط تنها زمانی قبل از Oki اجرا می شود که . در این وضعیت Ti تراکنش پیرتر و Tk تراکنش جوانتر است.

یک زمانبند که قانون TO را به اجرا در بیاورد هر عملیات جدید را در مقابل عملیات های تصادم دار که اخیرا زمانبندی شده اند چک می کند. اگر عملیات جدید متعلق به تراکنشی باشد که جوانتر از همه استنتاج تصادم دارهای قبلی که (اخیرا زمانبندی شده اند) باشد، عملیات پذیرفته می شود. در غیراین صورت پذیرفته نمی شود.

که عدم پذیرش آن سبب می شود که تراکنش ورودی با یک مهر زمانی جدید وباره از نو شروع به کار کند. یک زمانبند ترتیبی مهر زمانی که در این مد کار می کند، ضمانت می کند که زمانبندی های متوالی را تولید کند.

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

اما در شرایط واقعی هر کدام از عملیات در زمان خاصی به زمانبر می رسند در چنین شرایطی لازم است که بتوان چک کرد که آیا عملیاتی خارج از ترتیبش رسیده است یا خیر. برای آسان کردن این چک کردن به هر قلم داده X دو مهر زمانی اختصاص داده می شود.

 

مهر زمانی خواندن

که بزرگترین مهر زمانی عملیات هایی است که x را می خوانند.

 

مهر زمانی نوشتن

که بزرگترین مهر زمانی عملیات هایی است که روی x نوشته اند.

 

حالا مقایسه ی مهر زمانی یک عملیات با مهرهای زمانی نوشتن و خواندن قلم داده ای (که برای دسترسی برای مشخص کردن این که آیا هیچ تراکنشی با مهر زمانی بزرگتر که اخیرا به همان قلم داده دسترسی پیدا کرده است یا نه) خیلی راحت تر به نظر می رسد.

از نظر معماری مسئولیت تخصیص یک مهر زمانی به هر تراکنش جدید و پیوست کردن این مهرهای زمانی به هر عملیات پایگاه داده ای که به زمانبند واگذار می شود بر عهده مدیر تراکنش است.