تراکنش ها و مکانیسم های کنترل آنها

معاملات

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

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

تراکنش ها باید دارای ویژگی های ACID باشند

اتمی. معامله یا به طور کامل انجام می شود یا اصلا انجام نمی شود.

ثبات. هنگام تکمیل تراکنش، محدودیت های اعمال شده بر داده ها (مثلاً محدودیت های موجود در پایگاه داده) نباید نقض شود. سازگاری به این معنی است که سیستم از یک حالت صحیح به حالت صحیح دیگر منتقل می شود.

انزوا. تراکنش هایی که به صورت موازی اجرا می شوند نباید بر یکدیگر تأثیر بگذارند، به عنوان مثال، داده های استفاده شده توسط تراکنش دیگر را تغییر دهند. نتیجه اجرای تراکنش های موازی باید همان باشد که تراکنش ها به صورت متوالی انجام شده اند.

پایداری. پس از انجام، تغییرات نباید از بین بروند.

گزارش معاملات

گزارش تغییرات ایجاد شده توسط تراکنش ها را ذخیره می کند، اتمی بودن و پایداری داده ها را در صورت خرابی سیستم تضمین می کند.

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

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

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

سطوح عایق

متعهد را بخوانید

مشکل Dirty Read این است که یک تراکنش می تواند نتیجه میانی تراکنش دیگری را بخواند.

مثال. ارزش موجودی اولیه 0 دلار است. T1 50 دلار به موجودی شما اضافه می کند. T2 ارزش موجودی (50 دلار) را می خواند. T1 تغییرات را کنار گذاشته و خارج می شود. T2 با داده های موجودی نادرست به اجرا ادامه می دهد.

راه حل، خواندن داده های ثابت (Read Committed) است که خواندن داده های تغییر یافته توسط تراکنش را ممنوع می کند. اگر تراکنش A مجموعه خاصی از داده ها را تغییر داده باشد، تراکنش B، هنگام دسترسی به این داده ها، مجبور می شود منتظر تکمیل تراکنش A باشد.

خواندن تکراری

مشکل Lost Updates T1 تغییرات را در بالای تغییرات T2 ذخیره می کند.

مثال. ارزش موجودی اولیه 0 دلار است و دو تراکنش به طور همزمان موجودی را پر می کنند. T1 و T2 موجودی 0 دلار را خواندند. سپس T2 200 دلار به 0 دلار اضافه می کند و نتیجه را ذخیره می کند. T1 100 دلار به 0 دلار اضافه می کند و نتیجه را ذخیره می کند. نتیجه نهایی به جای 100 دلار، 300 دلار است.

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

مثال. T1 ارزش موجودی 0 دلار را می خواند. سپس T2 50 دلار به موجودی اضافه می کند و به پایان می رسد. T1 دوباره داده ها را می خواند و با نتیجه قبلی مغایرت پیدا می کند.

Repeatable Read تضمین می کند که خواندن دوم همان نتیجه را به دست خواهد آورد. داده های خوانده شده توسط یک تراکنش را نمی توان در تراکنش های دیگر تغییر داد تا زمانی که تراکنش کامل شود. اگر تراکنش A مجموعه خاصی از داده ها را خوانده باشد، تراکنش B هنگام دسترسی به این داده ها، مجبور می شود منتظر تکمیل تراکنش A باشد.

خواندن سفارشی (قابل سریال)

مشکل Phantom Reads دو پرس و جو که داده ها را بر اساس یک شرایط خاص انتخاب می کنند مقادیر متفاوتی را برمی گرداند.

مثال. T1 تعداد تمام کاربرانی را درخواست می کند که موجودی آنها بیشتر از 0 دلار اما کمتر از 100 دلار است. T2 1 دلار از کاربر با موجودی 101 دلار کسر می کند. T1 درخواست را دوباره صادر می کند.

خواندن سفارشی (قابل سریال). تراکنش ها به صورت کاملا متوالی انجام می شوند. به روز رسانی یا اضافه کردن رکوردهایی که در شرایط درخواست قرار می گیرند ممنوع است. اگر تراکنش A داده‌ها را از کل جدول درخواست کرده باشد، کل جدول برای سایر تراکنش‌ها مسدود می‌شود تا زمانی که تراکنش A کامل شود.

برنامه ریز

ترتیب انجام عملیات را در طول تراکنش های موازی تنظیم می کند.

سطح مشخصی از انزوا را فراهم می کند. اگر نتیجه عملیات به ترتیب آنها بستگی نداشته باشد، چنین عملیاتی جایگزین (Permutable) هستند. عملیات خواندن و عملیات روی داده های مختلف جابجایی هستند. عملیات خواندن-نوشتن و نوشتن-نوشتن جابجایی نیستند. وظیفه زمانبند این است که عملیات انجام شده توسط تراکنش های موازی را به هم بریزد به طوری که نتیجه اجرا معادل اجرای متوالی تراکنش ها باشد.

مکانیسم های کنترل مشاغل موازی (کنترل همزمان)

خوشبینانه مبتنی بر تشخیص و حل تعارضات است، بدبینانه مبتنی بر جلوگیری از بروز تعارض است.

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

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

قفل کردن

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

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

بن بست وضعیتی است که در آن تراکنش ها در حالت معلقی قرار می گیرند که به طور نامحدود ادامه می یابد.

مثال. اولین تراکنش منتظر می ماند تا داده های جمع آوری شده توسط دومی منتشر شود، در حالی که تراکنش دوم منتظر می ماند تا داده های جمع آوری شده توسط اولی منتشر شود.

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

بن بست ها در فواصل زمانی مشخص جستجو می شوند. یکی از روش های تشخیص زمان است، یعنی در نظر بگیرید که اگر تراکنش بیش از حد طول بکشد، بن بست رخ داده است. هنگامی که یک بن بست یافت می شود، یکی از تراکنش ها به عقب بازگردانده می شود و به سایر تراکنش های درگیر در بن بست اجازه می دهد تا تکمیل شوند. انتخاب قربانی می تواند بر اساس ارزش تراکنش ها یا قدمت آنها باشد (طرح های Wait-Die و Wound-Wit).

هر معامله T یک مهر زمانی اختصاص داده شده است TS حاوی زمان شروع معامله

صبر کن بمیر.

اگر TS (Ti) < TS (Tj)، و سپس Ti صبر می کند، در غیر این صورت Ti به عقب برمی گردد و دوباره با همان مهر زمانی شروع می شود.

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

زخم - انتظار.

اگر TS (Ti) < TS (Tj)، و سپس Tj به عقب برمی گردد و دوباره با همان مهر زمانی شروع می شود، در غیر این صورت Ti در انتظار.

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

یک راه حل بدبینانه برای مشکل بن بست اجازه نمی دهد که تراکنش در صورت وجود خطر بن بست اجرا شود.

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

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

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

یک commit دو مرحله ای تضمین می کند که commit بر روی تمام کپی های پایگاه داده اجرا می شود

هر پایگاه داده اطلاعاتی را در مورد داده هایی که در لاگ تغییر خواهند کرد وارد می کند و به هماهنگ کننده OK (مرحله رای گیری) پاسخ می دهد. پس از اینکه همه پاسخ مثبت دادند، هماهنگ کننده سیگنالی را ارسال می کند که همه را ملزم به تعهد می کند. پس از commit کردن، سرورها OK پاسخ می دهند؛ اگر حداقل یکی از آنها OK پاسخ ندهد، هماهنگ کننده سیگنالی برای لغو تغییرات به همه سرورها ارسال می کند (فاز تکمیل).

روش مهر زمانی

تراکنش قدیمی‌تر هنگام تلاش برای دسترسی به داده‌های مربوط به تراکنش جوان‌تر بازگردانده می‌شود

به هر تراکنش یک مهر زمانی اختصاص داده می شود TS مطابق با زمان شروع اجرا اگر Ti مسن تر Tj، و سپس TS (Ti) < TS (Tj).

هنگامی که یک تراکنش به عقب بازگردانده می شود، یک زمان جدید به آن اختصاص داده می شود. هر شی داده Q درگیر در معامله با دو برچسب مشخص شده است. W-TS (Q) - مهر زمانی جوانترین تراکنش که با موفقیت یک رکورد را تکمیل کرد Q. R-TS (Q) - مُهر زمانی جوان‌ترین تراکنش که رکورد خواندن روی آن انجام شده است Q.

هنگام معامله T درخواست خواندن داده ها Q دو گزینه وجود دارد.

اگر TS (T) < W-TS (Q)، یعنی داده ها توسط یک تراکنش جوان تر و سپس تراکنش به روز شد T به عقب می چرخد.

اگر TS (T) >= W-TS (Q)، سپس قرائت انجام می شود و R-TS (Q) در حال تبدیل شدن است MAX(R-TS(Q)، TS(T)).

هنگام معامله T تغییرات داده ها را درخواست می کند Q دو گزینه وجود دارد.

اگر TS (T) < R-TS (Q)، یعنی داده ها قبلاً توسط یک تراکنش جوان تر خوانده شده است و اگر تغییری ایجاد شود، تضاد ایجاد می شود. معامله T به عقب می چرخد.

اگر TS (T) < W-TS (Q)، یعنی تراکنش سعی می کند یک مقدار جدیدتر را بازنویسی کند، تراکنش T برگشت داده می شود. در موارد دیگر، تغییر انجام می شود و W-TS (Q) برابر می شود TS (T).

نیازی به ساخت گراف انتظار گران قیمت نیست. تراکنش های قدیمی تر به تراکنش های جدیدتر بستگی دارند، بنابراین هیچ چرخه ای در نمودار انتظار وجود ندارد. هیچ بن‌بستی وجود ندارد زیرا تراکنش‌ها منتظر نمی‌مانند، بلکه فوراً به عقب برمی‌گردند. برگشت های آبشاری امکان پذیر است. اگر Ti دور زد و Tj داده هایی را که تغییر دادم خواندم Ti، و سپس Tj همچنین باید به عقب برگردد. اگر در همان زمان Tj قبلاً مرتکب شده است، در این صورت اصل ثبات نقض خواهد شد.

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

قانون نوشتن توماس - تغییری از روش مهر زمانی که در آن داده‌های به‌روزرسانی شده توسط یک تراکنش جوان‌تر از بازنویسی توسط تراکنش قدیمی‌تر منع می‌شود.

معامله T تغییرات داده ها را درخواست می کند Q. اگر TS (T) < W-TS (Q)، یعنی تراکنش سعی می کند یک مقدار جدیدتر را بازنویسی کند، تراکنش T مانند روش مهر زمانی به عقب بازگردانده نمی شود.

منبع: www.habr.com