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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

کنترل همروندی چندنسخه‌ای (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 بود، هر کدام از آنها هنوز به عنوان یک نرم افزار تجاری فعال هستند.


جستارهای وابسته[ویرایش]


منابع[ویرایش]

  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.