کنترل همروندی چندنسخه‌ای

کنترل همروندی چندنسخه‌ای (Multiversion Control Concurrency)، در زمینه پایگاه داده علوم رایانه، یک روش کنترل همروندی است که معمولاً توسط سامانه‌های مدیریت پایگاه داده برای ارائه دسترسی همروند به پایگاه داده استفاده می‌شود، و همچنین در زبان‌های برنامه‌نویسی برای پیاده‌سازی حافظه تراکنشی به کار می‌رود.

بدون کنترل همروندي، اگر کسی در حال خواندن از یک پایگاه داده باشد و همزمان شخص دیگری در آن بنویسد، ممکن است خواننده یک قطعه داده‌اي كه كامل نوشته نشده یا متناقض است را ببیند. به‌طور مثال، هنگام انتقال داده بین دو حساب بانکی اگر خواننده، زمانی که پول از حساب اصلی حذف شده و قبل از ذخيره شدن در حساب مقصد، ميانگين حساب را از بانك بخواند، به نظر می‌رسد که پول در بانك ناپديد شده‌است. انزوا (isolation) يك ويژگي است كه دسترسيهاي همروند به داده را تضمین مي‌كند. انزوا با استفاده از معنا و مفهوم پروتکلهاي کنترل همروندي پياده سازي می‌شود. ساده‌ترین راه این است که همه خوانندگان منتظر بمانند تا نوشتن انجام شود، که به عنوان یک قفل خواندن - نوشتن شناخته می‌شود. قفل‌ها باعث ایجاد درگيري مي‌شوند به خصوص بین تراكنشهاي خواندن طولانی و تراكنشهاي به روز رساني. هدف MVCC، حل مشکل با نگه داشتن چندین نسخه از هر یک از داده‌ها است. بدین ترتیب، هر کاربری که به پایگاه داده متصل است، یک تصوير (snapshot) از پایگاه داده را در یک لحظه خاص در زمان می‌گیرد. هر گونه تغییری که توسط یک نویسنده ایجاد شده، توسط سایر کاربران پایگاه داده تا زمانی که تغییرات تکمیل نشده باشد (یا در شرایط پایگاه داده: تا زمانی که تراکنش كامل شود) مشاهده نمی‌شود.

هنگامی که یک پایگاه داده MVCC یک قطعه از داده را به روز رسانی مي‌كند، داده اصلي را با داده جديد جايگزين نخواهد كرد بلكه يك نسخه جديد از آن داده ايجاد مي‌كند. بنابراین چندین نسخه از داده ذخیره مي‌شود. نسخه ای که هر تراکنش مشاهده می‌کند به سطح انزواي اجرا شده (isolation level) بستگی دارد. شایع‌ترین سطح جداسازی با MVCC، جداسازي فوري (snapshot isolation) است. با سطح جداسازي فوري، یک تراکنش وضعیت داده را به عنوان زمان انجام تراكنش تراكنش مشاهده می‌کند. MVCC چالش چگونگی حذف نسخه‌هایی را که منسوخ شده و هرگز خوانده نخواهد شد معرفی می‌کند. در بعضی موارد، یک فرآیند به صورت دوره ای از طریق حذف و حذف نسخه‌های منسوخ اجرا می‌شود. این اغلب یک فرآیند توقف كلي است که یک جدول کامل را پردازش می‌کند و آن را با آخرین نسخه هر یک از آیتم‌های داده بازنویسی می‌کند. PostgreSQL با استفاده از فرآیند VACUUM حذف نسخه هاي منسوخ شده را انجام مي‌دهد.

پایگاه‌های داده‌های دیگر بلوک‌های ذخیره‌سازی را به دو قسمت تقسیم می‌کنند: بخش داده و Undo log . بخش داده همیشه آخرین نسخه كامل شده را نگه می‌دارد. Undo log امکان بازسازی نسخه‌های قدیمی تر داده‌ها را فراهم می‌کند. محدودیت اصلی ذاتی این رویکرد دوم این است که وقتی باركاري بروزرسانی بيشتري وجود دارد، بخشی از undo log نمي تواند اجرا شود و پس از آن تراكنش‌ها به دلیل عدم توانايي در گرفتن تصوير از پايگاه داده قطع می‌شوند. برای یک پایگاه داده سند-گرا همچنین اجازه می‌دهد تا سیستم به منظور بهینه سازی اسناد با نوشتن تمام اسناد به بخش‌های مجاور دیسک، هنگامی که به روز شده، کل سند قابل بازنويسي مي شود به جاي آن كه بيتها و تكه‌ها جدا شوند يا در ساختار پايگاه داده پيوسته مرتبط نگهداري شوند.

MVCC دیدگاه‌های سازگار با زمان لحظه اي فراهم می‌کند . تراكنشهاي خواندن تحت MVCC برای تعیین وضعیتي از بانک اطلاعاتی كه بايد خوانده شود، به‌طور معمول از یک نشانگر زمان (time stamp)یا شناسه تراکنش استفاده می‌کنند و اين نسخه از داد ه‌ها را مي خوانند. بنابراین، تراكنشهاي خواندن و نوشتن بدون نیاز به قفل شدن از یکدیگر جدا می شوند. با این حال، علیرغم ضروري نبودن قفل، در بعضی از پایگاه‌های داده MVCC مانند اوراکل استفاده می‌شود. نوشتن، یک نسخه جدیدتر ایجاد می‌کند در حالی که خواندن همزمان با آن، به یک نسخه قدیمی دسترسی پیدا می‌کند.

پیاده سازی

MVCC از نشانگر زماني (TS) و افزایش شناسه‌های تراکنش برای دستیابی به یکپارچگی تراكنش‌ها استفاده می‌کند. MVCC با حفظ چندین نسخه از شی، تضمین می‌کند که تراکنش (T) براي خواندن یک شی پایگاه داده‌اي (P) هرگز منتظر نماند. هر نسخه از شیء P داراي هر دو نشانگر زماني خواندن (RTS) و نشانگر زماني نوشتن (WTS) است که به یک تراكنش خاص Ti اجازه می‌دهد آخرین نسخه از شیء را که قبل از نشانگر زماني خواندن RST (Ti) است، بخواند.

اگر تراكنش Ti بخواهد روي شي P بنويسد و همچنین یک تراکنش دیگر (TK) روي همان شي كاري انجام دهد، بايد نشانگر زماني خواندن RTS (Ti) قبل از نشانگر زماني خواندن RTS (Tk) باشد، یعنی RTS (Ti) <RTS (Tk)

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

برای بازنویسی؛ هر جسم (P) با نشانگر زمانی (TS) در نظر بگیرید، اگر تراکنش Ti بخواهد روی یک شیء بنویسد و تراکنش با نشانگر زمانی (TS) که قبل از نشانگر زمانی خواندن فعلی شیء است داشته باشیم، (TS(Ti)<RTS(P، پس تراکنش قطع (abort) و راه اندازی مجدد می‌شود. (زیرا که تراکنش دوم به مقدار قدیمی وابسته است.) در غیر این صورت، Ti یک نسخه جدید از شی P ایجاد می‌کند و نشانگر زمانی TS خواندن/نوشتن نسخه جدید را برابر با نشانگر زمانی تراکنش قرار می‌دهد (TS = TS (Ti.

اشکال این سیستم، هزینه ذخیره چندین نسخه از اشیاء در پایگاه داده است. از سوی دیگر، خواندن‌ها هرگز مسدود نمی‌شوند، که می‌تواند برای بار کاری که بیشتر شامل خواندن مقادیر از پایگاه داده است، مهم باشد. MVCC برای اجرای سطح انزوای فوری (snapshot isolation) دقیق ماهرانه عمل می‌کند، چیزی که سایر روش‌های کنترل همروندی اغلب به صورت ناقص یا با هزینه‌های عملکردی بالا انجام می‌دهند.

مثالها

خواندن - نوشتن همزمان

در زمان = 1، وضعیت پایگاه داده:

زمان	شیء1	شیء2
0	"Foo" توسط T0	"Bar" توسط T0
1	"Hello" توسط T1

T0 شیء 1 را برابر با "Foo" و شیء 2 را برابر با "Bar" نوشته است. پس از آن، T1 مقدار شیء1 را برابر با "Hello" قرار می‌دهد و مقدار شیء2 را تغییر نمی‌دهد. برای تمام تراکنشهایی که بعد از کامل شدن T1 شروع می‌شوند، مقدار جدید شیء1 جایگزین مقدار قبلی آن (مقدار در زمان 0) می‌شود و نسخه اولیه برای شیء1 می‌تواند دور ریخته شود.

اگر تراکنش طولانی مدت T2 عملیات خواندن شیء1 و شی‌ء2 را پس از کامل شدن T1 انجام دهد و یک تراکنش به روزرسانی همزمان T3 وجود داشته باشد که شیء 2 را حذف می‌کند و شیء3 برابر با مقدار "Foo-Bar" را اضافه می‌کند، وضعیت پایگاه داده مانند زمان 2 خواهد بود:

زمان	شیء1	شیء2	شیء3
0	"Foo" توسط T0	"Bar" توسط T0
1	"Hello" توسط T1
2		(deleted) توسط T3	"Foo-Bar" توسط T3

در زمان 2، یک نسخه جدید برای شیء 2 با علامت مشخصه deleted و و یک شیء جدید با عنوان شیء3 وجود دارد. از آنجا که T2 و T3 همزمان اجرا می‌شوند، T2 نسخه قبل از زمان 2 از پایگاه داده را می‌بیند یعنی قبل از این که T3 نوشتن را کامل کند و البته T2 شیء2 برابر با "Bar" و شیء1 برابر با "Hello" را می‌خواند. بدین صورت، کنترل همروندی چند نسخه‌ای (MVCC) امکان خواندن با انزوای فوری را بدون هیچ گونه قفل انجام می‌دهد.

تاریخچه

کنترل همروندی چند نسخه‌ای در مقاله‌‌ای در سال 1981 با عنوان "کنترل همروندی در سیستم های پایگاه داده توزیع شده" توسط Phil Bernstein و Nathan Goodman با برخی جزئیات عنوان شد سپس توسط شرکت کامپیوتری آمریکا مورد استفاده قرار گرفت. مقاله ذکر شده از پایان نامه David P. Reed مربوط به سال 1978، که MVCC را به عنوان یک فعالیت اصلی توضیح داده بود، اتخاذ شد.

نخستین محصول نرم افزاری MVCC نرم افزار تجاری Digital's VAX Rdb/ELN بود. دومین مورد InterBase بود، هر کدام از آن‌ها هنوز به عنوان یک نرم افزار تجاری فعال هستند.

جستارهای وابسته

منابع

↑ refs. Clojure. Retrieved on 2013-09-18.
↑ Ramakrishnan, R., & Gehrke, J. (2000). Database management systems. Osborne/McGraw-Hill.
↑ Bernstein, Philip A.; Goodman, Nathan (1981). "Concurrency Control in Distributed Database Systems". ACM Computing Surveys.
↑ Reed, David P. (September 21, 1978). "Naming and Synchronization in a Decentralized Computer System". MIT dissertation. Archived from the original on 25 October 2005. Retrieved 9 December 2018.

[1] refs. Clojure. Retrieved on 2013-09-18.

[2] Ramakrishnan, R., & Gehrke, J. (2000). Database management systems. Osborne/McGraw-Hill.

[3] Bernstein, Philip A.; Goodman, Nathan (1981). "Concurrency Control in Distributed Database Systems". ACM Computing Surveys.

[4] Reed, David P. (September 21, 1978). "Naming and Synchronization in a Decentralized Computer System". MIT dissertation. Archived from the original on 25 October 2005. Retrieved 9 December 2018.