آموزش سیستم مدیریت پایگاه داده - کنترل همزمانی

در محیطی چندبرنامه‌ای که در آن چندین تراکنش می‌توانند به‌طور همزمان اجرا شوند، کنترل همزمانی تراکنش‌ها بسیار مهم است. ما برای تضمین صمیمیت (atomicity)، انزوایی (isolation) و قابل سریال‌سازی (serializability) تراکنش‌های همزمان، پروتکل‌های کنترل همزمانی داریم. پروتکل‌های کنترل همزمانی به طور کلی به دو دسته زیر تقسیم می‌شوند:

• پروتکل‌های مبتنی بر قفل (Lock based protocols)
• پروتکل‌های مبتنی بر نشان زمانی (Time stamp based protocols)

پروتکل‌های مبتنی بر قفل

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

• قفل دودویی (Binary Locks) - یک قفل روی یک مورد داده ممکن است در دو حالت قفل شده یا باز شده باشد.

• اشتراکی/اختصاصی (Shared/Exclusive) - این نوع مکانیسم قفل‌گذاری بر اساس استفاده‌های آن‌ها تفاوت قائل می‌شود. اگر قفلی روی یک مورد داده برای انجام عملیات نوشتن بگیریم، این یک قفل اختصاصی است. اجازه دادن به بیش از یک تراکنش برای نوشتن روی همان مورد داده باعث ورود پایگاه داده به حالت نامتعادل می‌شود. قفل‌های خواندن به اشتراک گذاشته می‌شوند زیرا هیچ مقدار داده‌ای تغییر نمی‌کند.

چهار نوع پروتکل قفل موجود است:

پروتکل قفل ساده (Simplistic Lock Protocol)

پروتکل‌های مبتنی بر قفل ساده به تراکنش‌ها اجازه می‌دهند تا قبل از انجام عملیات "نوشتن"، قفلی را بر روی هر شیء دریافت کنند. تراکنش می‌تواند پس از انجام عملیات "نوشتن"، قفل را رها کند.

پروتکل قبل از درخواست قفل (Pre-claiming Lock Protocol)

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

قفل دو مرحله‌ای (Two-Phase Locking 2PL)

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

قفل دو مرحله‌ای دارای دو فاز است؛ یکی فاز "رشد" است که در آن تراکنش تمام قفل‌ها را به دست می‌آورد و فاز دوم "کوچک شدن" است که قفل‌های در اختیار تراکنش را رها می‌کند.

برای درخواست قفل انحصاری (نوشتن)، یک تراکنش باید ابتدا یک قفل به اشتراک‌گذاری (خواندن) بگیرد و سپس آن را به قفل انحصاری ارتقاء دهد.

قفل دو مرحله‌ای سختگیرانه (Strict Two-Phase Locking)

فاز اول قفل‌گذاری دو مرحله‌ای سختگیرانه مشابه ۲PL است. پس از به دست آوردن تمام قفل‌ها در فاز اول، تراکنش به طور معمول ادامه می‌یابد. اما در مقابل ۲PL، قفل‌گذاری دو مرحله‌ای سختگیرانه پس از استفاده از قفل آن را رها نمی‌کند. قفل‌گذاری دو مرحله‌ای سختگیرانه تمام قفل‌ها را تا لحظه تایید (commit) نگه می‌دارد و در یک زمان همه قفل‌ها را رها می‌کند.

قفل دو مرحله‌ای سختگیرانه، شیوه لغو پیوندی را ندارد مانند ۲PL.

پروتکل‌های مبتنی بر برچسب زمانی (Timestamp-based Protocols)

پرتکل مبتنی بر برچسب زمانی پرکاربردترین پروتکل همروندی است. این پروتکل از زمان سیستمی یا شمارنده منطقی به عنوان برچسب زمانی استفاده می‌کند.

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

هر تراکنش دارای یک برچسب زمانی مرتبط با آن است و ترتیب آن توسط سن تراکنش تعیین می‌شود. یک تراکنش ایجاد شده در زمان ساعت ۰۰۰۲ مقدار سن تراکنش‌هایی است که بعد از آن ایجاد می‌شوند. به عنوان مثال، هر تراکنش "y" که در سیستم وارد شود در زمان ۰۰۰۴ دو ثانیه جوان‌تر است و اولویت به سن بالاتر داده می‌شود.

علاوه بر این، هر آیتم داده دارای برچسب زمانی آخرین خواندن و نوشتن است. این به سیستم اجازه می‌دهد بداند که آخرین عملیات "خواندن و نوشتن" روی آیتم داده کی انجام شده است.

پروتکل مرتب‌کننده برچسب زمانی (Timestamp Ordering Protocol)

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

• برچسب زمانی تراکنش T_i با TS(T_i) نشان داده می‌شود.
• برچسب زمانی خواندن آیتم داده X با R-timestamp(X) نشان داده می‌شود.
• برچسب زمانی نوشتن آیتم داده X با W-timestamp(X) نشان داده می‌شود.

پروتکل مرتب‌کننده برچسب زمانی به صورت زیر عمل می‌کند −

• اگر یک تراکنش Ti عملیات read(X) را صادر کند −

• اگر TS(Ti) < W-timestamp(X)
  • عملیات رد شده است.
• اگر TS(Ti) >= W-timestamp(X)
  • عملیات انجام می‌شود.
• همه برچسب‌های آیتم داده به‌روزرسانی می‌شوند.

• اگر یک تراکنش Ti عملیات write(X) را صادر کند −

• اگر TS(Ti) < R-timestamp(X)
• عملیات رد شده است.
• اگر TS(Ti) < W-timestamp(X)
• عملیات رد شده و Ti بازگشت داده می‌شود.
• در غیر این صورت، عملیات انجام می‌شود.

قاعده نوشتن توماس (Thomas' Write Rule)

این قاعده بیان می‌کند که اگر TS(Ti) < W-timestamp(X) باشد، آنگاه عملیات رد شده و T_i بازگشت داده می‌شود.

قوانین مرتب‌سازی برچسب زمانی می‌توانند تغییر یابند تا برنامه زمانبندی قابل سری‌پذیری را نمایش دهد.

به جای بازگرداندن T_i، عملیات 'نوشتن' خودش نادیده گرفته می‌شود.