پروتکلهای کنترل همروندی
پروتکلهای کنترل همروندی روشهایی هستند — قفلگذاری، ترتیبدهی بر اساس برچسب زمانی، اعتبارسنجی خوشبینانه، و چندنسخهایسازی — که تراکنشهای همروند را بهگونهای زمانبندی میکنند که نتیجه معادل یک اجرای ترتیبی باشد.
Definition
پروتکل کنترل همروندی مجموعهای از قوانین است که نحوه دسترسی تراکنشهای همروند به دادهها را تنظیم میکند تا هر زمانبندی مجاز قابل ترتیبیسازی باشد (یا سطح ایزولهسازی ضعیفتر انتخابی را برآورده کند)، و بدین ترتیب ایزولهسازی را بدون اجبار تراکنشها به اجرا به صورت یک به یک حفظ میکند.
Scope
این موضوع پروتکلهایی را پوشش میدهد که قابلیت ترتیبیسازی را تحت همروندی اعمال میکنند: قفلگذاری دو فازی و نوع سختگیرانه آن، همراه با تشخیص و پیشگیری از بنبست؛ پروتکلهای ترتیبدهی بر اساس برچسب زمانی؛ کنترل همروندی خوشبینانه با فازهای خواندن-اعتبارسنجی-نوشتن؛ و کنترل همروندی چندنسخهای، شامل ایزولهسازی اسنپشات. این مبحث به چگونگی تضمین زمانبندیهای صحیح توسط هر پروتکل و مبادلات بین مسدودسازی، لغو، و توان عملیاتی میپردازد. تعریف خود قابلیت ترتیبیسازی و مکانیزمهای بازیابی که مکمل کنترل همروندی هستند، از این بحث مستثنی شدهاند.
Core questions
- قفلگذاری دو فازی چگونه زمانبندیهای قابل ترتیبیسازی را تضمین میکند؟
- بنبستها چگونه شناسایی، پیشگیری یا حل میشوند؟
- پروتکلهای ترتیبدهی بر اساس برچسب زمانی و خوشبینانه چه تفاوتی با قفلگذاری دارند؟
- کنترل همروندی چندنسخهای چگونه به خوانندگان اجازه میدهد از مسدود کردن نویسندگان اجتناب کنند؟
- مبادلات توان عملیاتی بین روشهای بدبینانه و خوشبینانه چیست؟
Key concepts
- قفلگذاری دو فازی
- 2PL سختگیرانه و دقیق
- قفلهای مشترک و انحصاری
- تشخیص و پیشگیری از بنبست
- ترتیبدهی بر اساس برچسب زمانی
- کنترل همروندی خوشبینانه
- کنترل همروندی چندنسخهای
- ایزولهسازی اسنپشات
Key theories
- قفلگذاری دو فازی
- اگر هر تراکنش تمام قفلهای خود را قبل از آزاد کردن هر یک (یک فاز رشد و به دنبال آن یک فاز انقباض) به دست آورد، تمام زمانبندیهای حاصله قابل ترتیبیسازی از نظر تضاد هستند؛ قفلگذاری دو فازی سختگیرانه علاوه بر این، قفلهای نوشتن را تا زمان کامیت نگه میدارد تا قابلیت بازیابی را تضمین کند.
- کنترل همروندی خوشبینانه
- تراکنشها بدون قفلگذاری اجرا میشوند و در زمان کامیت در برابر تراکنشهای همروند اعتبارسنجی میشوند؛ تراکنشهای متضاد لغو شده و دوباره امتحان میشوند، که در صورت کم بودن رقابت عملکرد خوبی دارد.
- کنترل همروندی چندنسخهای
- با نگهداری چندین نسخه از هر آیتم داده، سیستم به خواندنها اجازه میدهد به یک اسنپشات سازگار دسترسی پیدا کنند بدون اینکه نوشتنها را مسدود کنند؛ ایزولهسازی اسنپشات یک طرح چندنسخهای پرکاربرد است، اگرچه میتواند ناهنجاریهای غیرقابل ترتیبیسازی خاصی را مجاز کند.
Clinical relevance
پروتکلهای کنترل همروندی تعیین میکنند که یک پایگاه داده تحت بار چگونه رفتار میکند: قفلگذاری قوی است اما میتواند باعث بنبست و رقابت شود، روشهای خوشبینانه و چندنسخهای امکان همروندی بالای خواندن را فراهم میکنند، و انتخاب پروتکل مستقیماً توان عملیاتی و تأخیر سیستمهای تراکنشی با ترافیک بالا را شکل میدهد.
History
قفلگذاری دو فازی و قفلهای گزارهای توسط اسواران و همکارانش در System R در سال 1976 رسمی شدند؛ کونگ و رابینسون کنترل همروندی خوشبینانه را در سال 1981 معرفی کردند؛ و تکنگاری برنستاین، هادیلاکوس، و گودمن در سال 1987 این نظریه را یکپارچه کرد. روشهای چندنسخهای و ایزولهسازی اسنپشات بعدها به دلیل رفتار دوستانه با خواندن، در سیستمهای پایگاه داده پرکاربرد غالب شدند.
Debates
- ایزولهسازی اسنپشات در مقابل قابلیت ترتیبیسازی
- ایزولهسازی اسنپشات با اجازه دادن به خوانندگان برای دیدن یک اسنپشات سازگار، همروندی بالایی را فراهم میکند، اما ناهنجاریهایی مانند انحراف نوشتن را مجاز میکند که قابلیت ترتیبیسازی کامل از آن جلوگیری میکند؛ متخصصان در مورد اینکه چه زمانی تضمین ضعیفتر آن قابل قبول است و چه زمانی انواع قابل ترتیبیسازی مورد نیاز هستند، بحث میکنند.
Key figures
- Jim Gray
- Philip Bernstein
- H. T. Kung
Related topics
Seminal works
- eswaran1976
- kung1981
- bernstein1987
Frequently asked questions
- چه چیزی باعث بنبست میشود و چگونه با آن برخورد میشود؟
- بنبست زمانی رخ میدهد که دو یا چند تراکنش هر کدام قفلی را نگه دارند که دیگری به آن نیاز دارد، بنابراین هیچ کدام نمیتوانند ادامه یابند. سیستمها با آن یا از طریق تشخیص — ساخت یک گراف انتظار، یافتن یک چرخه، و لغو یک تراکنش قربانی — یا از طریق طرحهای پیشگیری که ترتیب کسب قفل را تعیین میکنند یا از برچسبهای زمانی برای تصمیمگیری در مورد اینکه کدام تراکنش منتظر میماند یا لغو میشود، برخورد میکنند.
- چه زمانی کنترل همروندی خوشبینانه انتخاب خوبی است؟
- روشهای خوشبینانه زمانی که تضادها نادر هستند، میدرخشند، زیرا تراکنشها بدون سربار قفلگذاری اجرا میشوند و فقط گهگاه در اعتبارسنجی شکست میخورند و دوباره امتحان میشوند. تحت رقابت بالا، آنها کار را با لغو و تلاش مجدد هدر میدهند، بنابراین قفلگذاری بدبینانه یا روشهای چندنسخهای معمولاً برای بارهای کاری سنگین نوشتن و مستعد تضاد ترجیح داده میشوند.