فصل ۷ — تراکنش‌ها

برخی نویسندگان ادعا کرده‌اند که two-phase commit عمومی برای پشتیبانی بیش از حد گران است، به‌خاطر مشکلات کارایی یا دسترس‌پذیری که به همراه دارد. ما معتقدیم بهتر است برنامه‌نویسان برنامه با مشکلات کارایی ناشی از استفادهٔ بیش از حد از تراکنش‌ها — وقتی گلوگاه‌ها پدید می‌آیند — مواجه شوند، تا اینکه همیشه به‌خاطر نبود تراکنش‌ها دور آن‌ها کدنویسی کنند.

— James Corbett و همکاران، Spanner: Google's Globally-Distributed Database (۲۰۱۲)

در واقعیت خشن سیستم‌های داده، بسیاری چیزها ممکن است اشتباه پیش برود:

• نرم‌افزار یا سخت‌افزار پایگاه داده ممکن است هر لحظه از کار بیفتد (حتی وسط یک عملیات نوشتن).
• برنامه ممکن است هر لحظه crash کند (حتی نیمهٔ راه یک سری عملیات).
• قطع‌شدن‌های شبکه ممکن است برنامه را به‌طور ناگهانی از پایگاه داده، یا یک گره پایگاه داده را از گره دیگر، جدا کند.
• چند کلاینت ممکن است همزمان به پایگاه داده بنویسند و تغییرات یکدیگر را بازنویسی کنند.
• یک کلاینت ممکن است داده‌ای بخواند که معنا ندارد، چون فقط بخشی از آن به‌روز شده است.
• race conditionها بین کلاینت‌ها ممکن است باگ‌های غافلگیرکننده ایجاد کنند.

برای قابل‌اعتماد بودن، سیستم باید با این خطاها کنار بیاید و مطمئن شود باعث شکست فاجعه‌بار کل سیستم نمی‌شوند. با این حال، پیاده‌سازی مکانیزم‌های تحمل خطا کار زیادی می‌خواهد. نیاز به فکر کردن دقیق دربارهٔ همهٔ چیزهایی دارد که ممکن است اشتباه پیش برود، و تست زیادی برای اطمینان از اینکه راه‌حل واقعاً کار می‌کند.

دهه‌هاست که تراکنش‌ها مکانیزم انتخابی برای ساده‌سازی این مسائل بوده‌اند. تراکنش راهی است برای گروه‌بندی چند خواندن و نوشتن در یک واحد منطقی. از نظر مفهومی، همهٔ خواندن‌ها و نوشتن‌های یک تراکنش به‌عنوان یک عملیات اجرا می‌شوند: یا کل تراکنش موفق می‌شود (commit) یا شکست می‌خورد (abort، rollback). اگر شکست بخورد، برنامه می‌تواند با خیال راحت دوباره تلاش کند. با تراکنش‌ها، مدیریت خطا برای برنامه بسیار ساده‌تر می‌شود، چون نیازی نیست نگران شکست جزئی باشد — یعنی حالتی که برخی عملیات‌ها موفق و برخی شکست می‌خورند (به هر دلیلی).

اگر سال‌ها با تراکنش‌ها کار کرده‌اید، شاید بدیهی به نظر برسند، اما نباید آن‌ها را مسلم بدانیم. تراکنش‌ها قانون طبیعت نیستند؛ با هدفی ساخته شده‌اند، یعنی ساده‌سازی مدل برنامه‌نویسی برای برنامه‌هایی که به پایگاه داده دسترسی دارند. با استفاده از تراکنش‌ها، برنامه آزاد است برخی سناریوهای خطای بالقوه و مسائل همزمانی را نادیده بگیرد، چون پایگاه داده به‌جای آن‌ها مراقب است (ما این‌ها را تضمین‌های ایمنی می‌نامیم).

هر برنامه‌ای به تراکنش نیاز ندارد، و گاهی تضعیف تضمین‌های تراکنشی یا کنار گذاشتن کامل آن‌ها مزیت دارد (مثلاً برای دستیابی به کارایی یا دسترس‌پذیری بالاتر). برخی ویژگی‌های ایمنی بدون تراکنش هم قابل دستیابی‌اند.

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

در این فصل، نمونه‌های زیادی از چیزهایی که ممکن است اشتباه پیش برود را بررسی می‌کنیم و الگوریتم‌هایی را که پایگاه‌های داده برای محافظت در برابر آن‌ها به کار می‌برند، کاوش می‌کنیم. به‌ویژه عمیق در زمینهٔ کنترل همزمانی (concurrency control) می‌رویم و انواع مختلف race condition و نحوهٔ پیاده‌سازی سطوح ایزولاسیون مانند read committed، snapshot isolation و serializability را بحث می‌کنیم.

این فصل هم به پایگاه‌های دادهٔ تک‌گره‌ای و هم توزیع‌شده اعمال می‌شود؛ در فصل ۸ بحث را روی چالش‌هایی متمرکز می‌کنیم که فقط در سیستم‌های توزیع‌شده پدید می‌آیند.

مفهوم لغزندهٔ تراکنش

تقریباً همهٔ پایگاه‌های دادهٔ رابطه‌ای امروز، و برخی غیررابطه‌ای‌ها، از تراکنش پشتیبانی می‌کنند. بیشتر آن‌ها از سبکی پیروی می‌کنند که در ۱۹۷۵ توسط IBM System R، اولین پایگاه دادهٔ SQL، معرفی شد [۱، ۲، ۳]. اگرچه برخی جزئیات پیاده‌سازی تغییر کرده، ایدهٔ کلی تقریباً ۴۰ سال ثابت مانده: پشتیبانی تراکنش در MySQL، PostgreSQL، Oracle، SQL Server و غیره به‌طرز عجیبی شبیه System R است.

در اواخر دههٔ ۲۰۰۰، پایگاه‌های دادهٔ غیررابطه‌ای (NoSQL) محبوب شدند. آن‌ها می‌خواستند بر وضعیت موجود رابطه‌ای بهبود دهند با ارائهٔ مدل‌های دادهٔ جدید (فصل ۲ را ببینید) و گنجاندن تکثیر (فصل ۵) و پارتیشن‌بندی (فصل ۶) به‌صورت پیش‌فرض. تراکنش‌ها قربانی اصلی این جنبش بودند: بسیاری از نسل جدید پایگاه‌های داده تراکنش را کاملاً رها کردند، یا واژه را بازتعریف کردند تا مجموعه‌ای بسیار ضعیف‌تر از تضمین‌هایی که قبلاً فهمیده می‌شد توصیف کند [۴].

با هیاهو پیرامون این موج جدید پایگاه‌های دادهٔ توزیع‌شده، باوری رایج پدید آمد که تراکنش‌ها ضد مقیاس‌پذیری‌اند و هر سیستم بزرگ باید تراکنش را رها کند تا کارایی و دسترس‌پذیری خوبی داشته باشد [۵، ۶]. از سوی دیگر، گاهی فروشندگان پایگاه داده تضمین‌های تراکنشی را به‌عنوان الزام «برنامه‌های جدی» با «دادهٔ ارزشمند» معرفی می‌کنند. هر دو دیدگاه اغراق‌آمیز است.

حقیقت ساده نیست: مانند هر انتخاب فنی دیگر، تراکنش‌ها مزایا و محدودیت دارند. برای فهم این trade-offها، به جزئیات تضمین‌هایی که تراکنش‌ها می‌دهند — هم در عمل عادی و هم در شرایط افراطی (اما واقع‌بینانه) — می‌پردازیم.

معنای ACID

تضمین‌های ایمنی که تراکنش‌ها ارائه می‌دهند اغلب با مخفف شناخته‌شدهٔ ACID توصیف می‌شوند که مخفف Atomicity، Consistency، Isolation و Durability است. این واژه در ۱۹۸۳ توسط Theo Härder و Andreas Reuter [۷] برای ایجاد اصطلاح دقیق دربارهٔ مکانیزم‌های تحمل خطا در پایگاه‌های داده ابداع شد.

با این حال، در عمل، پیاده‌سازی ACID یک پایگاه داده با دیگری برابر نیست. مثلاً همان‌طور که خواهیم دید، ابهام زیادی پیرامون معنای isolation وجود دارد [۸]. ایدهٔ سطح بالا درست است، اما شیطان در جزئیات است. امروز وقتی سیستمی «مطابق ACID» است، نامشخص است چه تضمین‌هایی واقعاً انتظار دارید. ACID متأسفانه بیشتر به اصطلاح بازاریابی تبدیل شده.

(سیستم‌هایی که معیارهای ACID را برآورده نمی‌کنند گاهی BASE نامیده می‌شوند که مخفف Basically Available، Soft state و Eventual consistency است [۹]. این حتی مبهم‌تر از تعریف ACID است. به نظر می‌رسد تنها تعریف معقول BASE این است که «نه ACID»؛ یعنی تقریباً هر چیزی که بخواهید می‌تواند باشد.)

بیایید تعاریف atomicity، consistency، isolation و durability را بررسی کنیم تا ایدهٔ تراکنش را دقیق‌تر کنیم.

اتمی بودن (Atomicity)

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

در مقابل، در زمینهٔ ACID، atomicity دربارهٔ همزمانی نیست. توصیف نمی‌کند اگر چند فرآیند همزمان بخواهند به همان داده دسترسی داشته باشند چه می‌شود، چون آن تحت حرف I، یعنی isolation، است (به «ایزولاسیون» در همین صفحه مراجعه کنید).

بلکه atomicity در ACID توصیف می‌کند اگر کلاینت بخواهد چند نوشتن انجام دهد اما پس از پردازش برخی نوشتن‌ها خطا رخ دهد — مثلاً فرآیند crash کند، اتصال شبکه قطع شود، دیسک پر شود، یا قید یکپارچگی نقض شود — چه می‌شود. اگر نوشتن‌ها در یک تراکنش atomic گروه‌بندی شوند و تراکنش به‌خاطر خطا نتواند تکمیل (commit) شود، تراکنش abort می‌شود و پایگاه داده باید هر نوشتنی که در آن تراکنش انجام داده را کنار بگذارد یا undo کند.

بدون atomicity، اگر خطا نیمهٔ راه چند تغییر رخ دهد، دشوار است بدانید کدام تغییرات اثر کرده و کدام نه. برنامه می‌تواند دوباره تلاش کند، اما خطر تکرار همان تغییر و ایجاد دادهٔ تکراری یا نادرست وجود دارد. atomicity این مسئله را ساده می‌کند: اگر تراکنش abort شد، برنامه مطمئن است چیزی تغییر نکرده و می‌تواند با خیال راحت دوباره تلاش کند.

توانایی abort کردن تراکنش در صورت خطا و کنار گذاشتن همهٔ نوشتن‌های آن تراکنش، ویژگی تعیین‌کنندهٔ atomicity در ACID است. شاید abortability اصطلاح بهتری بود، اما با atomicity می‌مانیم چون واژهٔ رایج است.

سازگاری (Consistency)

واژهٔ consistency به‌شدت بارگذاری شده:

• در فصل ۵ دربارهٔ سازگاری replica و مسئلهٔ eventual consistency در سیستم‌های تکثیرشدهٔ ناهمگام بحث کردیم (به «مشکلات تأخیر تکثیر» در صفحه ۱۶۱ مراجعه کنید).
• consistent hashing رویکردی برای پارتیشن‌بندی است که برخی سیستم‌ها برای rebalancing به کار می‌برند (به «Consistent Hashing» در صفحه ۲۰۴ مراجعه کنید).
• در قضیهٔ CAP (فصل ۹)، consistency به معنای linearizability است (به «Linearizability» در صفحه ۳۲۴ مراجعه کنید).
• در زمینهٔ ACID، consistency به مفهوم خاص برنامه‌ای از «حالت خوب» بودن پایگاه داده اشاره دارد.

متأسفانه همان واژه با حداقل چهار معنای متفاوت به کار می‌رود.

ایدهٔ consistency در ACID این است که گزاره‌هایی دربارهٔ داده (invariantها) دارید که همیشه باید درست باشند — مثلاً در سیستم حسابداری، مجموع بدهکار و بستانکار در همهٔ حساب‌ها همیشه متعادل است. اگر تراکنش با پایگاه داده‌ای معتبر طبق این invariantها شروع شود و هر نوشتنی در طول تراکنش اعتبار را حفظ کند، مطمئنید invariantها همیشه برقرارند.

با این حال، این ایده به مفهوم invariantهای برنامه وابسته است و مسئولیت تعریف درست تراکنش‌ها برای حفظ consistency بر عهدهٔ برنامه است. این چیزی نیست که پایگاه داده بتواند تضمین کند: اگر دادهٔ بد بنویسید که invariantها را نقض کند، پایگاه داده نمی‌تواند جلوگیری کند. (برخی invariantهای خاص را پایگاه داده می‌تواند بررسی کند، مثلاً با قیدهای foreign key یا یکتایی. اما به‌طور کلی، برنامه تعیین می‌کند چه داده‌ای معتبر یا نامعتبر است — پایگاه داده فقط ذخیره می‌کند.)

atomicity، isolation و durability ویژگی‌های پایگاه داده‌اند، در حالی که consistency (به معنای ACID) ویژگی برنامه است. برنامه ممکن است برای دستیابی به consistency به atomicity و isolation پایگاه داده تکیه کند، اما تنها به پایگاه داده محدود نمی‌شود. بنابراین حرف C واقعاً جایش در ACID نیست.

i. Joe Hellerstein گفته حرف C در ACID «برای درست شدن مخفف اضافه شد» در مقالهٔ Härder و Reuter [۷]، و در آن زمان مهم تلقی نمی‌شد.

ایزولاسیون (Isolation)

بیشتر پایگاه‌های داده همزمان توسط چند کلاینت دسترسی می‌شوند. اگر بخش‌های مختلف پایگاه را بخوانند و بنویسند مشکلی نیست، اما اگر به همان رکوردها دسترسی داشته باشند، ممکن است به مشکلات همزمانی (race condition) برخورید.

شکل ۷-۱ نمونهٔ ساده‌ای از این مسئله است. فرض کنید دو کلاینت همزمان شمارنده‌ای را که در پایگاه داده ذخیره شده یکی افزایش می‌دهند. هر کلاینت باید مقدار فعلی را بخواند، ۱ اضافه کند و مقدار جدید را بنویسد (فرض می‌کنیم عملیات increment داخلی در پایگاه داده وجود ندارد). در شکل ۷-۱ شمارنده باید از ۴۲ به ۴۴ برسد چون دو افزایش رخ داده، اما به‌خاطر race condition فقط به ۴۳ رسیده است.

شکل ۷-۱. race condition بین دو کلاینت که همزمان یک شمارنده را افزایش می‌دهند.

isolation به معنای ACID یعنی تراکنش‌های همزمان از یکدیگر جدا هستند: نمی‌توانند پای یکدیگر را لگد کنند. کتاب‌های کلاسیک پایگاه داده isolation را به‌صورت serializability رسمی می‌کنند: هر تراکنش می‌تواند وانمود کند تنها تراکنش در حال اجرا روی کل پایگاه داده است. پایگاه داده تضمین می‌کند وقتی تراکنش‌ها commit شدند، نتیجه همان است که گویی به‌صورت ترتیبی (یکی پس از دیگری) اجرا شده‌اند، حتی اگر در واقعیت همزمان اجرا شده باشند [۱۰].

با این حال، در عمل، isolation قابل‌serializable به‌ندرت استفاده می‌شود چون هزینهٔ کارایی دارد. برخی پایگاه‌های محبوب، مثل Oracle 11g، حتی آن را پیاده نمی‌کنند. در Oracle سطح ایزولاسیونی به نام «serializable» وجود دارد، اما در واقع چیزی به نام snapshot isolation پیاده می‌کند که تضمین ضعیف‌تری از serializability است [۸، ۱۱]. snapshot isolation و اشکال دیگر isolation را در «سطوح ایزولاسیون ضعیف» در صفحه ۲۳۳ بررسی می‌کنیم.

پایداری (Durability)

هدف سیستم پایگاه داده ارائهٔ مکانی امن برای ذخیرهٔ داده بدون ترس از گم شدن آن است. durability وعده‌ای است که وقتی تراکنش با موفقیت commit شد، هر داده‌ای که نوشته شده فراموش نمی‌شود، حتی اگر خطای سخت‌افزاری رخ دهد یا پایگاه داده crash کند.

در پایگاه دادهٔ تک‌گره‌ای، durability معمولاً یعنی داده روی ذخیره‌سازی غیرفرار مانند هارد یا SSD نوشته شده. معمولاً شامل write-ahead log یا مشابه آن هم می‌شود (به «قابل‌اعتماد کردن درخت‌های B» در صفحه ۸۲ مراجعه کنید) که بازیابی را در صورت خرابی ساختارهای داده روی دیسک ممکن می‌کند. در پایگاه دادهٔ تکثیرشده، durability ممکن است یعنی داده با موفقیت به تعدادی گره کپی شده. برای ارائهٔ تضمین durability، پایگاه داده باید تا تکمیل این نوشتن‌ها یا تکثیرها صبر کند قبل از گزارش موفقیت commit.

همان‌طور که در «قابلیت اطمینان» در صفحه ۶ بحث شد، durability کامل وجود ندارد: اگر همهٔ هاردها و همهٔ پشتیبان‌ها همزمان نابود شوند، پایگاه داده هم کاری نمی‌تواند بکند.

تکثیر و پایداری

تاریخاً، durability یعنی نوشتن روی نوار آرشیو. بعد فهمیده شد یعنی نوشتن روی دیسک یا SSD. اخیراً به معنای تکثیر هم تطبیق داده شده. کدام پیاده‌سازی بهتر است؟

حقیقت این است که هیچ‌چیز کامل نیست:

• اگر روی دیسک بنویسید و ماشین از کار بیفتد، داده گم نمی‌شود اما تا تعمیر ماشین یا انتقال دیسک به ماشین دیگر در دسترس نیست. سیستم‌های تکثیرشده می‌توانند در دسترس بمانند.
• خطای همبسته — قطع برق یا باگی که همهٔ گره‌ها را با ورودی خاصی crash می‌کند — می‌تواند همهٔ replicaها را همزمان از کار بیندازد (به «قابلیت اطمینان» در صفحه ۶ مراجعه کنید) و داده‌ای که فقط در حافظه است را از دست بدهد. نوشتن روی دیسک بنابراین برای پایگاه‌های دادهٔ in-memory همچنان مرتبط است.
• در سیستم تکثیرشدهٔ ناهمگام، نوشتن‌های اخیر ممکن است وقتی leader در دسترس نیست گم شوند (به «مدیریت خرابی گره» در صفحه ۱۵۶ مراجعه کنید).
• وقتی برق ناگهان قطع می‌شود، SSDها گاهی تضمین‌هایی را که باید بدهند نقض می‌کنند: حتی fsync هم تضمین کار درست نیست [۱۲]. firmware دیسک هم مثل هر نرم‌افزار دیگری می‌تواند باگ داشته باشد [۱۳، ۱۴].
• تعاملات ظریف بین موتور ذخیره‌سازی و پیاده‌سازی filesystem می‌تواند باگ‌هایی ایجاد کند که ردیابی‌شان سخت است و پس از crash فایل‌های دیسک را خراب کند [۱۵، ۱۶].
• داده روی دیسک ممکن است تدریجاً بدون تشخیص خراب شود [۱۷]. اگر مدتی خراب بوده، replicaها و پشتیبان‌های اخیر هم ممکن است خراب باشند. در این صورت باید از پشتیبان تاریخی بازیابی کنید.
• مطالعه‌ای روی SSDها نشان داد بین ۳۰٪ تا ۸۰٪ درایوها در چهار سال اول حداقل یک bad block پیدا می‌کنند [۱۸]. هاردهای مغناطیسی نرخ bad sector پایین‌تری دارند اما نرخ خرابی کامل بالاتری از SSDها.
• اگر SSD از برق جدا شود، بسته به دما ممکن است ظرف چند هفته شروع به از دست دادن داده کند [۱۹].

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

عملیات تک‌شیءی و چندشیءی

خلاصه کنیم: در ACID، atomicity و isolation توصیف می‌کنند پایگاه داده چه کند اگر کلاینت چند نوشتن در یک تراکنش انجام دهد:

اتمی بودن (Atomicity) اگر خطا نیمهٔ راه دنباله‌ای از نوشتن‌ها رخ دهد، تراکنش باید abort شود و نوشتن‌های تا آن لحظه کنار گذاشته شوند. یعنی پایگاه داده شما را از نگرانی شکست جزئی نجات می‌دهد با تضمین همه‌یا-هیچ.

ایزولاسیون (Isolation) تراکنش‌های همزمان نباید در کار یکدیگر اختلال ایجاد کنند. مثلاً اگر یک تراکنش چند نوشتن انجام دهد، تراکنش دیگر باید یا همه یا هیچ‌کدام از آن نوشتن‌ها را ببیند، نه زیرمجموعه‌ای.

این تعاریف فرض می‌کنند می‌خواهید چند شیء (سطر، سند، رکورد) را همزمان تغییر دهید. چنین تراکنش‌های چندشیءی اغلب لازم است اگر چند بخش داده باید همگام بمانند. شکل ۷-۲ نمونه‌ای از یک برنامهٔ ایمیل است.

برای نمایش تعداد پیام‌های خوانده‌نشده برای کاربر، می‌توانید چیزی شبیه این پرس‌وجو کنید:

SELECT COUNT(*) FROM emails WHERE recipient_id = 2 AND unread_flag = true

با این حال، اگر ایمیل زیاد باشد این پرس‌وجو ممکن است کند باشد و تصمیم بگیرید تعداد پیام‌های خوانده‌نشده را در فیلد جداگانه ذخیره کنید (نوعی denormalization). حالا هر پیام جدید باید شمارندهٔ خوانده‌نشده را هم افزایش دهد، و هر پیام خوانده‌شده باید آن را کاهش دهد.

در شکل ۷-۲، کاربر ۲ ناهنجاری می‌بیند: فهرست صندوق ورودی پیام خوانده‌نشده نشان می‌دهد، اما شمارنده صفر خوانده‌نشده نشان می‌دهد چون افزایش شمارنده هنوز رخ نداده. isolation این مسئله را با تضمین اینکه کاربر ۲ یا هم ایمیل درج‌شده و هم شمارندهٔ به‌روز را ببیند یا هیچ‌کدام — نه نقطهٔ ناسازگار نیمه‌راه — جلوگیری می‌کرد.

شکل ۷-۲. نقض isolation: یک تراکنش نوشتن‌های commit‌نشدهٔ تراکنش دیگر را می‌خواند («dirty read»).

ii. شاید شمارندهٔ نادرست در برنامهٔ ایمیل مسئلهٔ بحرانی نباشد. به‌جای آن به موجودی حساب مشتری و تراکنش پرداخت به‌جای ایمیل فکر کنید.

شکل ۷-۳ نیاز به atomicity را نشان می‌دهد: اگر خطایی در طول تراکنش رخ دهد، محتوای صندوق ورودی و شمارندهٔ خوانده‌نشده ممکن است ناهمگام شوند. در تراکنش atomic، اگر به‌روزرسانی شمارنده شکست بخورد، تراکنش abort می‌شود و ایمیل درج‌شده rollback می‌شود.

شکل ۷-۳. atomicity تضمین می‌کند اگر خطا رخ دهد، هر نوشتن قبلی از آن تراکنش undo شود تا از حالت ناسازگار جلوگیری شود.

تراکنش‌های چندشیءی به روشی برای تعیین اینکه کدام عملیات‌های خواندن و نوشتن به یک تراکنش تعلق دارند نیاز دارند. در پایگاه‌های دادهٔ رابطه‌ای، این معمولاً بر اساس اتصال TCP کلاینت به سرور پایگاه داده است: روی هر اتصال خاص، همهٔ چیز بین دستور BEGIN TRANSACTION و COMMIT بخشی از همان تراکنش تلقی می‌شود.

iii. این ایده‌آل نیست. اگر اتصال TCP قطع شود، تراکنش باید abort شود. اگر قطع شدن پس از درخواست commit از کلاینت و قبل از تأیید commit از سرور رخ دهد، کلاینت نمی‌داند تراکنش commit شده یا نه. برای حل این مسئله، مدیر تراکنش می‌تواند عملیات‌ها را با شناسهٔ یکتای تراکنش گروه‌بندی کند که به اتصال TCP خاصی گره نخورده باشد. در «استدلال end-to-end برای پایگاه‌های داده» در صفحه ۵۱۶ به این موضوع برمی‌گردیم.

از سوی دیگر، بسیاری از پایگاه‌های دادهٔ غیررابطه‌ای راهی برای گروه‌بندی عملیات ندارند. حتی اگر API چندشیءی وجود داشته باشد (مثلاً key-value store ممکن است عملیات multi-put داشته باشد که چند کلید را در یک عملیات به‌روز می‌کند)، لزوماً معنای تراکنش ندارد: دستور ممکن است برای برخی کلیدها موفق و برای برخی شکست بخورد و پایگاه داده را در حالت به‌روزشدهٔ جزئی بگذارد.

نوشتن تک‌شیءی

atomicity و isolation وقتی یک شیء تغییر می‌کند هم اعمال می‌شوند. مثلاً فرض کنید سند JSON به اندازهٔ ۲۰ کیلوبایت به پایگاه داده می‌نویسید:

• اگر اتصال شبکه پس از ارسال ۱۰ کیلوبایت اول قطع شود، آیا پایگاه داده آن قطعهٔ ۱۰ کیلوبایتی JSON غیرقابل parse را ذخیره می‌کند؟
• اگر برق هنگام بازنویسی مقدار قبلی روی دیسک قطع شود، آیا مقدار قدیمی و جدید به هم چسبیده می‌شوند؟
• اگر کلاینت دیگری سند را هنگام نوشتن بخواند، آیا مقدار به‌روزشدهٔ جزئی می‌بیند؟

این مسائل بسیار گیج‌کننده‌اند، بنابراین موتورهای ذخیره‌سازی تقریباً همه تلاش می‌کنند atomicity و isolation را در سطح یک شیء (مثل جفت کلید-مقدار) روی یک گره فراهم کنند. atomicity می‌تواند با log برای بازیابی پس از crash پیاده شود (به «قابل‌اعتماد کردن درخت‌های B» در صفحه ۸۲ مراجعه کنید)، و isolation می‌تواند با قفل روی هر شیء پیاده شود (فقط یک نخ در هر لحظه به شیء دسترسی داشته باشد).

برخی پایگاه‌های داده عملیات atomic پیچیده‌تری هم می‌دهند، مثلاً عملیات increment که نیاز به چرخهٔ read-modify-write مانند شکل ۷-۱ را حذف می‌کند. compare-and-set هم محبوب است که نوشتن را فقط وقتی اجازه می‌دهد مقدار همزمان توسط کس دیگری تغییر نکرده باشد (به «Compare-and-set» در صفحه ۲۴۵ مراجعه کنید).

این عملیات‌های تک‌شیءی مفیدند چون وقتی چند کلاینت همزمان به یک شیء می‌نویسند از به‌روزرسانی‌های ازدست‌رفته جلوگیری می‌کنند (به «جلوگیری از به‌روزرسانی‌های ازدست‌رفته» در صفحه ۲۴۲ مراجعه کنید). با این حال، آن‌ها تراکنش به معنای معمول واژه نیستند. compare-and-set و عملیات‌های تک‌شیءی دیگر «تراکنش سبک» یا حتی «ACID» برای بازاریابی نامیده شده‌اند [۲۰، ۲۱، ۲۲]، اما این اصطلاح‌گذاری گمراه‌کننده است. تراکنش معمولاً مکانیزمی برای گروه‌بندی چند عملیات روی چند شیء در یک واحد اجرا فهمیده می‌شود.

iv. از نظر دقیق، عبارت atomic increment از atomic به معنای برنامه‌نویسی چندنخی استفاده می‌کند. در زمینهٔ ACID باید isolated یا serializable increment نامیده شود. اما این جزئیات‌گیرانه است.

نیاز به تراکنش‌های چندشیءی

بسیاری از datastoreهای توزیع‌شده تراکنش‌های چندشیءی را رها کرده‌اند چون پیاده‌سازی آن‌ها در پارتیشن‌ها دشوار است و در سناریوهایی که دسترس‌پذیری یا کارایی بسیار بالا لازم است ممکن است مزاحم شوند. با این حال، چیزی اساساً مانع تراکنش در پایگاه دادهٔ توزیع‌شده نیست و پیاده‌سازی تراکنش‌های توزیع‌شده را در فصل ۹ بحث می‌کنیم.

اما آیا اصلاً به تراکنش‌های چندشیءی نیاز داریم؟ آیا می‌توان هر برنامه‌ای را فقط با مدل دادهٔ key-value و عملیات تک‌شیءی پیاده کرد؟

برخی use caseها با درج، به‌روزرسانی و حذف تک‌شیءی کافی‌اند. اما در بسیاری موارد دیگر نوشتن به چند شیء مختلف باید هماهنگ شود:

• در مدل دادهٔ رابطه‌ای، سطر یک جدول اغلب ارجاع foreign key به سطر جدول دیگر دارد. (در مدل گراف‌مانند هم رأس به رأس‌های دیگر یال دارد.) تراکنش‌های چندشیءی تضمین می‌کنند این ارجاع‌ها معتبر بمانند: هنگام درج چند رکورد که به یکدیگر ارجاع دارند، foreign keyها باید درست و به‌روز باشند وگرنه داده بی‌معنا می‌شود.
• در مدل دادهٔ سندی، فیلدهایی که باید با هم به‌روز شوند اغلب در همان سند هستند که به‌عنوان یک شیء تلقی می‌شود — برای به‌روزرسانی یک سند به تراکنش چندشیءی نیاز نیست. با این حال، پایگاه‌های دادهٔ سندی بدون قابلیت join اغلب denormalization را تشویق می‌کنند (به «پایگاه‌های دادهٔ رابطه‌ای در برابر سندی امروز» در صفحه ۳۸ مراجعه کنید). وقتی اطلاعات denormalize‌شده باید به‌روز شود، مثل مثال شکل ۷-۲، باید چند سند را یکجا به‌روز کنید. تراکنش‌ها در این موقعیت بسیار مفیدند تا دادهٔ denormalize‌شده ناهمگام نشود.
• در پایگاه‌های داده با ایندکس ثانویه (تقریباً همه به‌جز key-value storeهای خالص)، هر بار مقداری را تغییر می‌دهید ایندکس‌ها هم باید به‌روز شوند. این ایندکس‌ها از نظر تراکنش اشیاء متفاوتی از پایگاه داده‌اند: مثلاً بدون isolation تراکنش، ممکن است رکوردی در یک ایندکس باشد اما در ایندکس دیگر نباشد چون به‌روزرسانی ایندکس دوم هنوز رخ نداده.

چنین برنامه‌هایی را می‌توان بدون تراکنش هم پیاده کرد. اما مدیریت خطا بدون atomicity بسیار پیچیده‌تر می‌شود و نبود isolation می‌تواند مشکلات همزمانی ایجاد کند. آن‌ها را در «سطوح ایزولاسیون ضعیف» در صفحه ۲۳۳ بحث می‌کنیم و رویکردهای جایگزین را در فصل ۱۲ کاوش می‌کنیم.

مدیریت خطاها و abort

ویژگی کلیدی تراکنش این است که در صورت خطا می‌تواند abort شود و با خیال راحت دوباره تلاش کرد. پایگاه‌های دادهٔ ACID بر این فلسفه استوارند: اگر پایگاه داده در خطر نقض تضمین atomicity، isolation یا durability باشد، ترجیح می‌دهد کل تراکنش را رها کند تا نیمه‌کاره بماند.

همهٔ سیستم‌ها این فلسفه را دنبال نمی‌کنند. به‌ویژه datastoreهای با تکثیر leaderless (به «تکثیر بدون leader» در صفحه ۱۷۷ مراجعه کنید) بیشتر بر پایهٔ «بهترین تلاش» کار می‌کنند که می‌توان خلاصه کرد: «پایگاه داده هرچه می‌تواند انجام می‌دهد، و اگر به خطا خورد چیزی که انجام داده undo نمی‌کند» — پس بازیابی از خطا بر عهدهٔ برنامه است.

خطاها اجتناب‌ناپذیرند، اما بسیاری از توسعه‌دهندگان نرم‌افزار ترجیح می‌دهند فقط به مسیر شاد فکر کنند تا پیچیدگی‌های مدیریت خطا. مثلاً فریم‌ورک‌های ORM محبوب مانند ActiveRecord در Rails و Django تراکنش‌های abort‌شده را دوباره تلاش نمی‌کنند — خطا معمولاً به‌صورت exception بالا می‌آید، ورودی کاربر دور ریخته می‌شود و پیام خطا نمایش داده می‌شود. این تأسف‌بار است چون هدف abortها فعال‌سازی تلاش مجدد امن است.

اگرچه تلاش مجدد تراکنش abort‌شده مکانیزم ساده و مؤثر مدیریت خطاست، کامل نیست:

• اگر تراکنش واقعاً موفق شده اما شبکه هنگام تلاش سرور برای تأیید commit به کلاینت از کار افتاد (پس کلاینت فکر می‌کند شکست خورده)، تلاش مجدد باعث اجرای دوباره می‌شود — مگر مکانیزم deduplication در سطح برنامه داشته باشید.
• اگر خطا به‌خاطر overload باشد، تلاش مجدد مسئله را بدتر می‌کند. برای جلوگیری از حلقه‌های بازخورد، می‌توانید تعداد تلاش‌ها را محدود کنید، از exponential backoff استفاده کنید و خطاهای مربوط به overload را متفاوت از خطاهای دیگر مدیریت کنید (در صورت امکان).
• فقط پس از خطاهای گذرا (مثلاً به‌خاطر deadlock، نقض isolation، قطع موقت شبکه و failover) تلاش مجدد ارزش دارد؛ پس از خطای دائمی (مثلاً نقض قید) تلاش مجدد بی‌فایده است.
• اگر تراکنش اثرات جانبی خارج از پایگاه داده هم دارد، آن اثرات ممکن است حتی اگر تراکنش abort شود رخ دهند. مثلاً اگر ایمیل می‌فرستید، نمی‌خواهید هر بار تلاش مجدد ایمیل دوباره ارسال شود. اگر می‌خواهید چند سیستم مختلف با هم commit یا abort کنند، two-phase commit کمک می‌کند (در «Atomic Commit و Two-Phase Commit (2PC)» در صفحه ۳۵۴ بحث می‌کنیم).
• اگر فرآیند کلاینت هنگام تلاش مجدد از کار بیفتد، هر داده‌ای که می‌خواست به پایگاه داده بنویسد گم می‌شود.

سطوح ایزولاسیون ضعیف

اگر دو تراکنش به همان داده دست نزنند، می‌توانند با خیال راحت موازی اجرا شوند چون به یکدیگر وابسته نیستند. مسائل همزمانی (race condition) فقط وقتی پدید می‌آیند که یک تراکنش داده‌ای را بخواند که تراکنش دیگر همزمان تغییر می‌دهد، یا دو تراکنش همزمان بخواهند همان داده را تغییر دهند.

باگ‌های همزمانی با تست پیدا کردن سخت‌اند چون فقط با بدشانسی در timing فعال می‌شوند. چنین مسائل timing ممکن است بسیار به‌ندرت رخ دهند و بازتولیدشان معمولاً دشوار است. استدلال دربارهٔ همزمانی هم بسیار سخت است، به‌ویژه در برنامهٔ بزرگ که لزوماً نمی‌دانید کدام بخش‌های دیگر کد به پایگاه داده دسترسی دارند. توسعهٔ برنامه با یک کاربر هم سخت است؛ چند کاربر همزمان آن را بسیار سخت‌تر می‌کند چون هر بخشی از داده ممکن است هر لحظه به‌طور غیرمنتظره تغییر کند.

به همین دلیل، پایگاه‌های داده مدت‌ها تلاش کرده‌اند مسائل همزمانی را از توسعه‌دهندگان برنامه پنهان کنند با ارائهٔ isolation تراکنش. از نظر تئوری، isolation باید زندگی را آسان‌تر کند با وانمود کردن که همزمانی رخ نمی‌دهد: isolation قابل‌serializable یعنی پایگاه داده تضمین می‌کند تراکنش‌ها همان اثر اجرای ترتیبی (یعنی یکی‌یکی، بدون همزمانی) را دارند.

در عمل، isolation متأسفانه آن‌قدرها ساده نیست. isolation قابل‌serializable هزینهٔ کارایی دارد و بسیاری از پایگاه‌های داده نمی‌خواهند آن هزینه را بپردازند [۸]. بنابراین رایج است سیستم‌ها از سطوح ایزولاسیون ضعیف‌تر استفاده کنند که از برخی مسائل همزمانی محافظت می‌کنند اما نه همه. درک آن سطوح بسیار سخت‌تر است و می‌توانند به باگ‌های ظریف منجر شوند، اما در عمل استفاده می‌شوند [۲۳].

باگ‌های همزمانی ناشی از isolation تراکنشی ضعیف فقط مسئلهٔ تئوری نیستند. آن‌ها باعث از دست رفتن پول قابل‌توجهی شده‌اند [۲۴، ۲۵]، منجر به بررسی ممیزی مالی شده‌اند [۲۶] و دادهٔ مشتری را خراب کرده‌اند [۲۷]. واکنش رایج به افشای چنین مسائلی «اگر دادهٔ مالی مدیریت می‌کنید از پایگاه دادهٔ ACID استفاده کنید!» است — اما نکته را از دست می‌دهد. حتی بسیاری از پایگاه‌های دادهٔ رابطه‌ای محبوب (که معمولاً «ACID» تلقی می‌شوند) از isolation ضعیف استفاده می‌کنند، پس لزوماً از این باگ‌ها جلوگیری نمی‌کردند.

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

در این بخش چند سطح ایزولاسیون ضعیف (غیرقابل‌serializable) که در عمل استفاده می‌شوند را بررسی می‌کنیم و دقیقاً بحث می‌کنیم چه race conditionهایی ممکن است و نمی‌تواند رخ دهد تا بتوانید سطح مناسب برنامهٔ خود را انتخاب کنید. سپس serializability را به‌تفصیل بحث می‌کنیم (به «Serializability» در صفحه ۲۵۱ مراجعه کنید). بحث سطوح ایزولاسیون غیررسمی و با مثال است. اگر تعاریف و تحلیل‌های دقیق می‌خواهید، در ادبیات آکادمیک یافت می‌شوند [۲۸، ۲۹، ۳۰].

Read Committed

پایه‌ای‌ترین سطح isolation تراکنش read committed است. دو تضمین می‌دهد:

۱. هنگام خواندن از پایگاه داده، فقط دادهٔ commit‌شده را می‌بینید (بدون dirty read). ۲. هنگام نوشتن به پایگاه داده، فقط دادهٔ commit‌شده را بازنویسی می‌کنید (بدون dirty write).

بیایید این دو تضمین را دقیق‌تر بحث کنیم.

عدم dirty read

فرض کنید تراکنشی داده‌ای به پایگاه داده نوشته اما هنوز commit یا abort نکرده. آیا تراکنش دیگر می‌تواند آن دادهٔ commit‌نشده را ببیند؟ اگر بله، dirty read نامیده می‌شود [۲].

تراکنش‌های با سطح isolation read committed باید از dirty read جلوگیری کنند. یعنی نوشتن‌های یک تراکنش فقط وقتی برای دیگران قابل مشاهده می‌شوند که آن تراکنش commit کند (و آنگاه همهٔ نوشتن‌هایش یکجا دیده می‌شوند). این در شکل ۷-۴ نشان داده شده: کاربر ۱ مقدار x را ۳ گذاشته، اما get x کاربر ۲ هنوز مقدار قدیمی ۲ را برمی‌گرداند چون کاربر ۱ هنوز commit نکرده.

شکل ۷-۴. بدون dirty read: کاربر ۲ مقدار جدید x را فقط پس از commit تراکنش کاربر ۱ می‌بیند.

v. برخی پایگاه‌های داده سطح ایزولاسیون حتی ضعیف‌تری به نام read uncommitted پشتیبانی می‌کنند. dirty write را جلوگیری می‌کند اما dirty read را نه.

دلایلی که جلوگیری از dirty read مفید است:

• اگر تراکنش چند شیء را به‌روز کند، dirty read یعنی تراکنش دیگر ممکن است برخی به‌روزرسانی‌ها را ببیند اما نه همه. مثلاً در شکل ۷-۲، کاربر ایمیل خوانده‌نشدهٔ جدید را می‌بیند اما نه شمارندهٔ به‌روز. این dirty read ایمیل است. دیدن پایگاه داده در حالت به‌روزشدهٔ جزئی برای کاربران گیج‌کننده است و ممکن است تراکنش‌های دیگر را به تصمیم نادرست وادار کند.
• اگر تراکنش abort شود، هر نوشتنی که انجام داده باید rollback شود (مثل شکل ۷-۳). اگر پایگاه داده dirty read اجازه دهد، تراکنش ممکن است داده‌ای ببیند که بعداً rollback می‌شود — یعنی هرگز واقعاً commit نمی‌شود. استدلال دربارهٔ پیامدها سریعاً گیج‌کننده می‌شود.

عدم dirty write

اگر دو تراکنش همزمان بخواهند همان شیء را در پایگاه داده به‌روز کنند چه می‌شود؟ نمی‌دانیم نوشتن‌ها به چه ترتیبی رخ می‌دهند، اما معمولاً فرض می‌کنیم نوشتن بعدی نوشتن قبلی را بازنویسی می‌کند.

اما اگر نوشتن قبلی بخشی از تراکنشی باشد که هنوز commit نشده و نوشتن بعدی مقدار commit‌نشده را بازنویسی کند؟ این dirty write نامیده می‌شود [۲۸]. تراکنش‌های با سطح read committed باید از dirty write جلوگیری کنند، معمولاً با تأخیر انداختن نوشتن دوم تا تراکنش نوشتن اول commit یا abort شود.

با جلوگیری از dirty write، این سطح از برخی مشکلات همزمانی جلوگیری می‌کند:

• اگر تراکنش‌ها چند شیء را به‌روز کنند، dirty write می‌تواند نتیجهٔ بد بدهد. مثلاً شکل ۷-۵ سایت فروش خودروی دست‌دوم را نشان می‌دهد که Alice و Bob همزمان می‌خواهند همان خودرو را بخرند. خرید خودرو دو نوشتن به پایگاه داده می‌خواهد: به‌روزرسانی آگهی برای نشان دادن خریدار، و ارسال فاکتور به خریدار. در شکل ۷-۵، فروش به Bob می‌رسد (چون به‌روزرسانی برندهٔ جدول آگهی‌ها را انجام می‌دهد) اما فاکتور به Alice فرستاده می‌شود (چون به‌روزرسانی برندهٔ جدول فاکتورها را انجام می‌دهد). read committed از چنین اشتباهاتی جلوگیری می‌کند.
• با این حال، read committed از race condition بین دو افزایش شمارنده در شکل ۷-۱ جلوگیری نمی‌کند. در این مورد نوشتن دوم پس از commit تراکنش اول رخ می‌دهد، پس dirty write نیست. باز هم نادرست است، اما به دلیل دیگری — در «جلوگیری از به‌روزرسانی‌های ازدست‌رفته» در صفحه ۲۴۲ بحث می‌کنیم چگونه چنین افزایش شمارنده‌ای امن شود.

شکل ۷-۵. با dirty write، نوشتن‌های متعارض از تراکنش‌های مختلف می‌توانند در هم آمیخته شوند.

پیاده‌سازی read committed

read committed سطح isolation بسیار محبوبی است. تنظیم پیش‌فرض در Oracle 11g، PostgreSQL، SQL Server 2012، MemSQL و بسیاری پایگاه‌های دیگر است [۸].

رایج‌ترین روش جلوگیری از dirty write، قفل در سطح سطر است: وقتی تراکنش می‌خواهد شیء خاصی (سطر یا سند) را تغییر دهد، ابتدا باید قفل آن شیء را بگیرد و تا commit یا abort تراکنش نگه دارد. فقط یک تراکنش می‌تواند قفل هر شیء را داشته باشد؛ اگر تراکنش دیگر بخواهد همان شیء را بنویسد، باید صبر کند تا تراکنش اول commit یا abort شود و سپس قفل را بگیرد و ادامه دهد. این قفل‌گذاری در حالت read committed (یا سطوح قوی‌تر) به‌صورت خودکار انجام می‌شود.

چگونه از dirty read جلوگیری کنیم؟ یک گزینه استفاده از همان قفل و الزام تراکنش‌هایی که می‌خوانند به‌طور موقت قفل بگیرند و بلافاصله پس از خواندن رها کنند. این تضمین می‌کند خواندن هنگام مقدار dirty و commit‌نشده رخ ندهد (چون در آن زمان قفل نزد تراکنش نوشتن است).

با این حال، الزام قفل خواندن در عمل خوب کار نمی‌کند چون یک تراکنش نوشتن طولانی می‌تواند بسیاری از تراکنش‌های فقط-خواندن را مجبور به انتظار تا تکمیل تراکنش طولانی کند. این زمان پاسخ تراکنش‌های فقط-خواندن را خراب می‌کند و برای operability بد است: کندی در یک بخش برنامه می‌تواند اثر دومینو در بخش کاملاً متفاوت داشته باشد به‌خاطر انتظار برای قفل‌ها.

vi. در زمان نگارش، تنها پایگاه‌های دادهٔ رایج که برای read committed از قفل استفاده می‌کنند IBM DB2 و Microsoft SQL Server با پیکربندی read_committed_snapshot=off هستند [۲۳، ۳۶].

به همین دلیل، بیشتر پایگاه‌های داده dirty read را با رویکرد شکل ۷-۴ جلوگیری می‌کنند: برای هر شیء نوشته‌شده، پایگاه داده هم مقدار commit‌شدهٔ قدیمی و هم مقدار جدیدی که تراکنش دارای قفل نوشتن گذاشته را به خاطر می‌سپارد. در حین تراکنش، هر تراکنش دیگری که شیء را بخواند فقط مقدار قدیمی را می‌گیرد. فقط وقتی مقدار جدید commit شد، تراکنش‌ها به خواندن مقدار جدید می‌روند.

ایزولاسیون snapshot و repeatable read

اگر سطحی به read committed نگاه کنید، ممکن است ببخشید فکر کنید همهٔ نیازهای تراکنش را برآورده می‌کند: abort را اجازه می‌دهد (برای atomicity لازم است)، از خواندن نتایج ناقص تراکنش‌ها جلوگیری می‌کند و نوشتن‌های همزمان را در هم نمی‌آمیزد. این‌ها ویژگی‌های مفیدی‌اند و تضمین‌های بسیار قوی‌تری از سیستمی بدون تراکنش.

با این حال، هنوز راه‌های زیادی برای باگ‌های همزمانی با این سطح isolation وجود دارد. مثلاً شکل ۷-۶ مسئله‌ای را نشان می‌دهد که با read committed ممکن است رخ دهد.

شکل ۷-۶. read skew: Alice پایگاه داده را در حالت ناسازگار می‌بیند.

فرض کنید Alice ۱٬۰۰۰ دلار پس‌انداز در بانک دارد، بین دو حساب با ۵۰۰ دلار هر کدام. حالا تراکنشی ۱۰۰ دلار از یک حساب به دیگری منتقل می‌کند. اگر بدشانس باشد و در همان لحظهٔ پردازش آن تراکنش موجودی حساب‌ها را ببیند، ممکن است یک حساب را قبل از رسیدن پرداخت ورودی (موجودی ۵۰۰ دلار) و حساب دیگر را پس از انتقال خروجی (موجودی جدید ۴۰۰ دلار) ببیند. برای Alice حالا انگار فقط ۹۰۰ دلار دارد — گویی ۱۰۰ دلار ناپدید شده.

این ناهنجاری nonrepeatable read یا read skew نامیده می‌شود: اگر Alice دوباره در پایان تراکنش موجودی حساب ۱ را بخواند، مقدار متفاوتی (۶۰۰ دلار) می‌بیند نسبت به پرس‌وجوی قبلی. read skew تحت read committed قابل قبول است: موجودی‌هایی که Alice دید واقعاً در زمان خواندن commit شده بودند.

اصطلاح skew متأسفانه بارگذاری شده: قبلاً در معنای بارکاری نامتعادل با hot spot استفاده کردیم (به «بارکاری‌های skewed و تخفیف hot spot» در صفحه ۲۰۵ مراجعه کنید)، اینجا به معنای ناهنجاری timing است.

در مورد Alice این مسئلهٔ دائمی نیست چون احتمالاً چند ثانیه بعد با بارگذاری مجدد وب‌سایت بانک موجودی‌های سازگار می‌بیند. با این حال، برخی موقعیت‌ها چنین ناسازگاری موقتی را تحمل نمی‌کنند:

پشتیبان‌گیری گرفتن پشتیبان نیاز به کپی کل پایگاه داده دارد که روی پایگاه بزرگ ممکن است ساعت‌ها طول بکشد. در این مدت نوشتن‌ها ادامه می‌یابند. پس ممکن است بخشی از پشتیبان نسخهٔ قدیمی‌تر و بخشی نسخهٔ جدیدتر داده را داشته باشد. اگر از چنین پشتیبانی بازیابی کنید، ناسازگاری‌ها (مثل پول ناپدیدشده) دائمی می‌شوند.

پرس‌وجوهای تحلیلی و بررسی یکپارچگی گاهی می‌خواهید پرس‌وجویی اجرا کنید که بخش‌های بزرگی از پایگاه داده را اسکن کند. چنین پرس‌وجوها در analytics رایج‌اند (به «پردازش تراکنش یا تحلیل؟» در صفحه ۹۰ مراجعه کنید) یا بخشی از بررسی دوره‌ای یکپارچگی (نظارت بر فساد داده). اگر بخش‌های مختلف پایگاه را در نقاط زمانی متفاوت ببینند، احتمالاً نتایج بی‌معنا برمی‌گردانند.

snapshot isolation [۲۸] رایج‌ترین راه‌حل این مسئله است. ایده این است که هر تراکنش از snapshot سازگار پایگاه داده بخواند — یعنی همهٔ داده‌ای را ببیند که در شروع تراکنش commit شده بود. حتی اگر بعداً تراکنش دیگری داده را تغییر دهد، هر تراکنش فقط دادهٔ قدیمی از آن نقطهٔ زمانی خاص را می‌بیند.

snapshot isolation برای پرس‌وجوهای فقط-خواندن طولانی‌مدت مانند پشتیبان‌گیری و analytics نعمت است. اگر داده‌ای که پرس‌وجو روی آن کار می‌کند همزمان با اجرای پرس‌وجو تغییر کند، معنای پرس‌وجو را فهمیدن بسیار سخت است. وقتی تراکنش می‌تواند snapshot سازگار پایگاه داده را در نقطهٔ زمانی خاص ببیند، فهمیدن بسیار آسان‌تر است.

snapshot isolation ویژگی محبوبی است: PostgreSQL، MySQL با موتور InnoDB، Oracle، SQL Server و دیگران از آن پشتیبانی می‌کنند [۲۳، ۳۱، ۳۲].

پیاده‌سازی ایزولاسیون snapshot

مانند read committed، پیاده‌سازی‌های snapshot isolation معمولاً از قفل نوشتن برای جلوگیری از dirty write استفاده می‌کنند (به «پیاده‌سازی read committed» در صفحه ۲۳۶ مراجعه کنید)، یعنی تراکنش نوشتن می‌تواند پیشرفت تراکنش دیگری که به همان شیء می‌نویسد را مسدود کند. اما خواندن به قفل نیاز ندارد.

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

برای پیاده‌سازی snapshot isolation، پایگاه‌های داده از تعمیم مکانیزمی که برای جلوگیری از dirty read در شکل ۷-۴ دیدیم استفاده می‌کنند. پایگاه داده ممکن است چند نسخهٔ commit‌شدهٔ مختلف یک شیء را نگه دارد چون تراکنش‌های در حال انجام ممکن است به حالت پایگاه داده در نقاط زمانی متفاوت نیاز داشته باشند. چون چند نسخهٔ یک شیء را کنار هم نگه می‌دارد، این تکنیک multi-version concurrency control (MVCC) نامیده می‌شود.

اگر پایگاه داده فقط read committed می‌خواست نه snapshot isolation، نگه‌داشتن دو نسخه کافی بود: نسخهٔ commit‌شده و نسخهٔ بازنویسی‌شده‌اما-هنوز-commit‌نشده. با این حال، موتورهایی که snapshot isolation پشتیبانی می‌کنند معمولاً MVCC را برای read committed هم به کار می‌برند. رویکرد معمول این است که read committed برای هر پرس‌وجو snapshot جداگانه دارد، در حالی که snapshot isolation برای کل تراکنش همان snapshot را استفاده می‌کند.

شکل ۷-۷ نشان می‌دهد MVCC-based snapshot isolation در PostgreSQL [۳۱] چگونه پیاده می‌شود (پیاده‌سازی‌های دیگر مشابه‌اند). وقتی تراکنش شروع می‌شود، شناسهٔ تراکنش (txid) یکتا و همیشه‌افزایشی به آن داده می‌شود. هر بار تراکنش چیزی به پایگاه داده می‌نویسد، داده با txid نویسنده برچسب می‌خورد.

vii. دقیق‌تر، txidها عدد صحیح ۳۲ بیتی‌اند و پس از حدود ۴ میلیارد تراکنش سرریز می‌کنند. فرایند vacuum در PostgreSQL پاکسازی انجام می‌دهد تا سرریز روی داده اثر نگذارد.

شکل ۷-۷. پیاده‌سازی ایزولاسیون snapshot با اشیاء چندنسخه‌ای.

هر سطر در جدول فیلد created_by دارد که شامل txid تراکنشی است که این سطر را درج کرده. علاوه بر این، هر سطر فیلد deleted_by دارد که ابتدا خالی است. اگر تراکنشی سطر را حذف کند، سطر واقعاً از پایگاه داده حذف نمی‌شود بلکه با گذاشتن txid تراکنش درخواست‌کنندهٔ حذف در deleted_by برای حذف علامت می‌خورد. بعداً وقتی مطمئن شدیم هیچ تراکنشی دیگر به دادهٔ حذف‌شده دسترسی ندارد، فرایند garbage collection سطرهای علامت‌خورده را حذف و فضایشان را آزاد می‌کند.

به‌روزرسانی دروناً به حذف و ایجاد ترجمه می‌شود. مثلاً در شکل ۷-۷، تراکنش ۱۳ از حساب ۲ مبلغ ۱۰۰ دلار کسر می‌کند و موجودی را از ۵۰۰ به ۴۰۰ تغییر می‌دهد. جدول accounts در واقع دو سطر برای حساب ۲ دارد: سطری با موجودی ۵۰۰ که توسط تراکنش ۱۳ برای حذف علامت خورده، و سطری با موجودی ۴۰۰ که توسط تراکنش ۱۳ ایجاد شده.

قواعد دیدپذیری برای مشاهدهٔ snapshot سازگار

وقتی تراکنش از پایگاه داده می‌خواند، txidها تعیین می‌کنند کدام اشیاء قابل مشاهده و کدام نامرئی‌اند. با تعریف دقیق قواعد دیدپذیری، پایگاه داده snapshot سازگار به برنامه ارائه می‌دهد. این‌طور کار می‌کند:

۱. در شروع هر تراکنش، پایگاه داده فهرستی از همهٔ تراکنش‌های دیگر در حال انجام (هنوز commit یا abort نشده) در آن زمان می‌سازد. هر نوشتی که آن تراکنش‌ها انجام داده‌اند نادیده گرفته می‌شود، حتی اگر بعداً commit کنند. ۲. هر نوشتی که تراکنش‌های abort‌شده انجام داده‌اند نادیده گرفته می‌شود. ۳. هر نوشتی که تراکنش‌های با txid بالاتر (یعنی پس از شروع تراکنش فعلی شروع شده) انجام داده‌اند نادیده گرفته می‌شود، صرف‌نظر از commit بودن. ۴. همهٔ نوشتن‌های دیگر برای پرس‌وجوهای برنامه قابل مشاهده‌اند.

این قواعد هم برای ایجاد و هم حذف اشیاء اعمال می‌شوند. در شکل ۷-۷، وقتی تراکنش ۱۲ از حساب ۲ می‌خواند، موجودی ۵۰۰ دلار می‌بیند چون حذف موجودی ۵۰۰ دلار توسط تراکنش ۱۳ انجام شده (طبق قاعده ۳، تراکنش ۱۲ حذف تراکنش ۱۳ را نمی‌بیند) و ایجاد موجودی ۴۰۰ دلار هنوز قابل مشاهده نیست (با همان قاعده).

به عبارت دیگر، شیء قابل مشاهده است اگر هر دو شرط برقرار باشند:

• در زمان شروع تراکنش خواننده، تراکنشی که شیء را ایجاد کرده commit شده بود.
• شیء برای حذف علامت نخورده، یا اگر علامت خورده، تراکنش درخواست‌کنندهٔ حذف در زمان شروع تراکنش خواننده هنوز commit نشده بود.

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

ایندکس‌ها و ایزولاسیون snapshot

ایندکس‌ها در پایگاه دادهٔ چندنسخه‌ای چگونه کار می‌کنند؟ یک گزینه این است که ایندکس به همهٔ نسخه‌های یک شیء اشاره کند و پرس‌وجوی ایندکس نسخه‌هایی را که برای تراکنش فعلی قابل مشاهده نیستند فیلتر کند. وقتی garbage collection نسخه‌های قدیمی که دیگر برای هیچ تراکنشی قابل مشاهده نیستند را حذف می‌کند، ورودی‌های ایندکس متناظر هم حذف می‌شوند.

در عمل، جزئیات پیاده‌سازی زیادی کارایی MVCC را تعیین می‌کند. مثلاً PostgreSQL بهینه‌سازی دارد تا اگر نسخه‌های مختلف یک شیء در همان صفحه جا شوند از به‌روزرسانی ایندکس اجتناب کند [۳۱].

رویکرد دیگر در CouchDB، Datomic و LMDB استفاده می‌شود. آن‌ها هم از درخت B استفاده می‌کنند (به «درخت‌های B» در صفحه ۷۹ مراجعه کنید)، اما از گونهٔ append-only/copy-on-write استفاده می‌کنند که هنگام به‌روزرسانی صفحات درخت را بازنویسی نمی‌کند بلکه از هر صفحهٔ تغییریافته کپی جدید می‌سازد. صفحات والد تا ریشهٔ درخت کپی و به‌روز می‌شوند تا به نسخه‌های جدید فرزندان اشاره کنند. صفحاتی که نوشتن رویشان اثر ندارد نیازی به کپی ندارند و تغییرناپذیر می‌مانند [۳۳، ۳۴، ۳۵].

با درخت Bهای append-only، هر تراکنش نوشتن (یا دسته‌ای از تراکنش‌ها) ریشهٔ جدید درخت B می‌سازد و هر ریشه snapshot سازگار پایگاه داده در زمان ایجادش است. نیازی به فیلتر اشیاء بر اساس txid نیست چون نوشتن‌های بعدی نمی‌توانند درخت B موجود را تغییر دهند؛ فقط ریشه‌های جدید می‌سازند. اما این رویکرد به فرایند پس‌زمینه برای compaction و garbage collection هم نیاز دارد.

repeatable read و سردرگمی نام‌گذاری

snapshot isolation سطح isolation مفیدی است، به‌ویژه برای تراکنش‌های فقط-خواندن. با این حال، بسیاری از پایگاه‌های داده که آن را پیاده می‌کنند نام‌های متفاوتی دارند. در Oracle serializable نامیده می‌شود، و در PostgreSQL و MySQL repeatable read [۲۳].

دلیل این سردرگمی این است که استاندارد SQL مفهوم snapshot isolation را ندارد چون استاندارد بر تعریف ۱۹۷۵ System R از سطوح isolation استوار است [۲] و snapshot isolation هنوز ابداع نشده بود. به‌جای آن repeatable read تعریف می‌کند که ظاهراً شبیه snapshot isolation است. PostgreSQL و MySQL سطح snapshot isolation خود را repeatable read می‌نامند چون الزامات استاندارد را برآورده می‌کند و می‌توانند ادعای مطابقت با استاندارد کنند.

متأسفانه تعریف استاندارد SQL از سطوح isolation معیوب است — مبهم، نادقیق و به اندازهٔ یک استاندارد مستقل از پیاده‌سازی نیست [۲۸]. اگرچه چند پایگاه داده repeatable read پیاده می‌کنند، تفاوت‌های بزرگی در تضمین‌های واقعی دارند با وجود استاندارد بودن ظاهری [۲۳]. تعریف رسمی repeatable read در ادبیات پژوهشی وجود دارد [۲۹، ۳۰]، اما بیشتر پیاده‌سازی‌ها آن تعریف رسمی را برآورده نمی‌کنند. و IBM DB2 «repeatable read» را برای اشاره به serializability به کار می‌برد [۸].

نتیجه این است که کسی واقعاً نمی‌داند repeatable read یعنی چه.

جلوگیری از به‌روزرسانی‌های ازدست‌رفته

سطوح read committed و snapshot isolation که تا اینجا بحث کردیم عمدتاً دربارهٔ تضمین‌هایی بودند که تراکنش فقط-خواندن در حضور نوشتن‌های همزمان می‌تواند ببیند. مسئلهٔ دو تراکنش که همزمان می‌نویسند را عمدتاً نادیده گرفتیم — فقط dirty write (به «عدم dirty write» در صفحه ۲۳۵ مراجعه کنید)، یک نوع خاص تعارض نوشتن-نوشتن، را بحث کردیم.

چند نوع دیگر تعارض جالب بین تراکنش‌های نوشتن همزمان وجود دارد. شناخته‌شده‌ترین آن‌ها مسئلهٔ به‌روزرسانی ازدست‌رفته (lost update) است که در شکل ۷-۱ با مثال دو افزایش همزمان شمارنده نشان داده شد.

مسئلهٔ lost update وقتی رخ می‌دهد که برنامه مقداری از پایگاه داده بخواند، تغییر دهد و مقدار تغییریافته را بنویسد (چرخهٔ read-modify-write). اگر دو تراکنش این کار را همزمان انجام دهند، یکی از تغییرات ممکن است گم شود چون نوشتن دوم تغییر اول را شامل نمی‌شود. (گاهی می‌گوییم نوشتن بعدی نوشتن قبلی را می‌پوشاند.) این الگو در سناریوهای مختلف رخ می‌دهد:

• افزایش شمارنده یا به‌روزرسانی موجودی حساب (نیاز به خواندن مقدار فعلی، محاسبهٔ مقدار جدید و نوشتن مقدار به‌روز)
• تغییر محلی در مقدار پیچیده، مثلاً افزودن عنصر به لیست در سند JSON (نیاز به parse سند، تغییر و نوشتن سند تغییریافته)
• دو کاربر همزمان صفحهٔ ویکی را ویرایش می‌کنند و هر کدام با ارسال کل محتوای صفحه به سرور، هرچه در پایگاه داده است را بازنویسی می‌کند

چون این مسئله رایج است، راه‌حل‌های متنوعی توسعه یافته‌اند.

عملیات نوشتن اتمی

بسیاری از پایگاه‌های داده عملیات به‌روزرسانی اتمی ارائه می‌دهند که نیاز به پیاده‌سازی چرخهٔ read-modify-write در کد برنامه را حذف می‌کند. معمولاً بهترین راه‌حل‌اند اگر کد را بتوان با آن‌ها بیان کرد. مثلاً دستور زیر در بیشتر پایگاه‌های دادهٔ رابطه‌ای از نظر همزمانی امن است:

UPDATE counters SET value = value + 1 WHERE key = 'foo';

پایگاه‌های دادهٔ سندی مانند MongoDB عملیات اتمی برای تغییر محلی بخشی از سند JSON می‌دهند، و Redis عملیات اتمی برای تغییر ساختارهای داده مانند صف اولویت. همهٔ نوشتن‌ها را نمی‌توان به‌راحتی با عملیات اتمی بیان کرد — مثلاً به‌روزرسانی صفحهٔ ویکی شامل ویرایش متن دلخواه است — اما جایی که عملیات اتمی ممکن است، معمولاً بهترین انتخاب‌اند.

عملیات اتمی معمولاً با گرفتن قفل انحصاری روی شیء هنگام خواندن پیاده می‌شوند تا هیچ تراکنش دیگری تا اعمال به‌روزرسانی نتواند بخواند. این تکنیک گاهی cursor stability [۳۶، ۳۷] نامیده می‌شود. گزینهٔ دیگر اجبار اجرای همهٔ عملیات اتمی روی یک نخ است.

متأسفانه، فریم‌ورک‌های ORM به‌راحتی کدی می‌نویسند که به‌جای عملیات اتمی پایگاه داده، چرخهٔ ناامن read-modify-write انجام دهد [۳۸]. اگر بدانید چه می‌کنید مشکلی نیست، اما منبع بالقوهٔ باگ‌های ظریفی است که با تست پیدا کردن سخت است.

viii. بیان ویرایش سند متنی به‌صورت جریانی از جهش‌های اتمی ممکن است، اگرچه نسبتاً پیچیده است. به «حل تعارض خودکار» در صفحه ۱۷۴ برای اشاره‌ها مراجعه کنید.

قفل‌گذاری صریح

گزینهٔ دیگر برای جلوگیری از lost update، اگر عملیات اتمی داخلی پایگاه داده کافی نباشد، این است که برنامه صریحاً اشیائی را که قرار است به‌روز شوند قفل کند. سپس برنامه می‌تواند چرخهٔ read-modify-write انجام دهد و اگر تراکنش دیگری همزمان همان شیء را بخواند، مجبور به انتظار تا تکمیل چرخهٔ اول می‌شود.

مثلاً در بازی چندنفره‌ای که چند بازیکن می‌توانند همزمان همان مهره را جابه‌جا کنند، عملیات اتمی ممکن است کافی نباشد چون برنامه باید مطمئن شود حرکت بازیکن طبق قوانین بازی است که منطقی نیست به‌صورت پرس‌وجوی پایگاه داده پیاده شود. به‌جای آن می‌توانید از قفل استفاده کنید تا دو بازیکن همزمان همان مهره را جابه‌جا نکنند، همان‌طور که در مثال ۷-۱ نشان داده شده.

مثال ۷-۱. قفل‌گذاری صریح سطرها برای جلوگیری از به‌روزرسانی‌های ازدست‌رفته

BEGIN TRANSACTION;

SELECT * FROM figures
  WHERE name = 'robot' AND game_id = 222
  FOR UPDATE;

-- Check whether move is valid, then update the position
-- of the piece that was returned by the previous SELECT.
UPDATE figures SET position = 'c4' WHERE id = 1234;

COMMIT;

بند FOR UPDATE به پایگاه داده می‌گوید روی همهٔ سطرهای برگشتی از این پرس‌وجو قفل بگیرد.

این کار می‌کند، اما برای درست انجام دادن باید منطق برنامه را با دقت فکر کنید. آسان است جایی قفل لازم را فراموش کنید و race condition وارد کنید.

تشخیص خودکار به‌روزرسانی‌های ازدست‌رفته

عملیات اتمی و قفل‌ها با اجبار اجرای ترتیبی چرخه‌های read-modify-write از lost update جلوگیری می‌کنند. جایگزین این است که اجازه دهید موازی اجرا شوند و اگر مدیر تراکنش lost update تشخیص دهد، تراکنش را abort کند و مجبور به تلاش مجدد چرخهٔ read-modify-write کند.

مزیت این رویکرد این است که پایگاه داده می‌تواند این بررسی را به‌طور مؤثر همراه با snapshot isolation انجام دهد. در واقع، repeatable read در PostgreSQL، serializable در Oracle و snapshot isolation در SQL Server به‌طور خودکار lost update را تشخیص داده و تراکنش متخلف را abort می‌کنند. با این حال، repeatable read در MySQL/InnoDB lost update را تشخیص نمی‌دهد [۲۳]. برخی نویسندگان [۲۸، ۳۰] استدلال می‌کنند پایگاه داده باید از lost update جلوگیری کند تا تحت این تعریف snapshot isolation ارائه دهد، پس MySQL تحت این تعریف snapshot isolation نمی‌دهد.

تشخیص lost update ویژگی عالی است چون نیازی نیست کد برنامه از ویژگی‌های خاص پایگاه داده استفاده کند — ممکن است فراموش کنید قفل یا عملیات اتمی به کار ببرید و باگ وارد کنید، اما تشخیص lost update خودکار است و بنابراین مستعد خطای کمتر.

Compare-and-set

در پایگاه‌های داده بدون تراکنش، گاهی عملیات اتمی compare-and-set می‌یابید (قبلاً در «نوشتن تک‌شیءی» در صفحه ۲۳۰ ذکر شد). هدف این عملیات جلوگیری از lost update است با اجازهٔ به‌روزرسانی فقط اگر مقدار از آخرین خواندن شما تغییر نکرده باشد. اگر مقدار فعلی با آنچه قبلاً خوانده‌اید مطابقت ندارد، به‌روزرسانی اثری ندارد و چرخهٔ read-modify-write باید دوباره تلاش شود.

مثلاً برای جلوگیری از به‌روزرسانی همزمان صفحهٔ ویکی توسط دو کاربر:

-- This may or may not be safe, depending on the database implementation
UPDATE wiki_pages SET content = 'new content'
  WHERE id = 1234 AND content = 'old content';

اگر محتوا تغییر کرده و دیگر با 'old content' مطابقت ندارد، این به‌روزرسانی اثری ندارد و باید بررسی کنید آیا اثر کرده و در صورت لزوم دوباره تلاش کنید. با این حال، اگر پایگاه داده اجازه دهد بند WHERE از snapshot قدیمی بخواند، این دستور ممکن است از lost update جلوگیری نکند چون شرط ممکن است درست باشد در حالی که نوشتن همزمان دیگری در جریان است. قبل از تکیه، بررسی کنید عملیات compare-and-set پایگاه دادهٔ شما امن است.

حل تعارض و تکثیر

در پایگاه‌های دادهٔ تکثیرشده (فصل ۵)، جلوگیری از lost update بعد دیگری دارد: چون کپی داده روی چند گره دارند و داده ممکن است همزمان روی گره‌های مختلف تغییر کند، گام‌های اضافی برای جلوگیری از lost update لازم است.

قفل‌ها و compare-and-set فرض می‌کنند یک کپی به‌روز از داده وجود دارد. اما پایگاه‌های داده با تکثیر multi-leader یا leaderless معمولاً اجازه می‌دهند چند نوشتن همزمان رخ دهد و آن‌ها را ناهمگام تکثیر می‌کنند، پس نمی‌توانند تضمین کنند یک کپی به‌روز از داده وجود دارد. بنابراین تکنیک‌های مبتنی بر قفل یا compare-and-set در این زمینه اعمال نمی‌شوند. (در «Linearizability» در صفحه ۳۲۴ دوباره به این مسئله می‌پردازیم.)

به‌جای آن، همان‌طور که در «تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴ بحث شد، رویکرد رایج در چنین پایگاه‌های تکثیرشده این است که اجازه دهند نوشتن‌های همزمان چند نسخهٔ متعارض (sibling) از یک مقدار ایجاد کنند و از کد برنامه یا ساختارهای دادهٔ خاص برای حل و ادغام این نسخه‌ها بعداً استفاده شود.

عملیات اتمی در زمینهٔ تکثیر می‌تواند خوب کار کند، به‌ویژه اگر commutative باشند (یعنی روی replicaهای مختلف به ترتیب متفاوت اعمال شوند و نتیجهٔ یکسان بدهند). مثلاً افزایش شمارنده یا افزودن عنصر به مجموعه عملیات commutative‌اند. این ایدهٔ پشت datatypeهای Riak 2.0 است که lost update را بین replicaها جلوگیری می‌کنند. وقتی مقداری همزمان توسط کلاینت‌های مختلف به‌روز می‌شود، Riak به‌روزرسانی‌ها را طوری ادغام می‌کند که هیچ به‌روزرسانی گم نشود [۳۹].

از سوی دیگر، روش حل تعارض last write wins (LWW) مستعد lost update است، همان‌طور که در «last write wins (دور انداختن نوشتن‌های همزمان)» در صفحه ۱۸۶ بحث شد. متأسفانه LWW پیش‌فرض بسیاری از پایگاه‌های دادهٔ تکثیرشده است.

Write skew و phantom

در بخش‌های قبلی dirty write و lost update را دیدیم، دو نوع race condition که وقتی تراکنش‌های مختلف همزمان می‌خواهند به همان اشیاء بنویسند ممکن است رخ دهند. برای جلوگیری از فساد داده، این race conditionها باید جلوگیری شوند — یا خودکار توسط پایگاه داده، یا با محافظت‌های دستی مانند قفل یا عملیات نوشتن اتمی.

با این حال، این پایان فهرست race conditionهای بالقوه بین نوشتن‌های همزمان نیست. در این بخش نمونه‌های ظریف‌تری از تعارض‌ها می‌بینیم.

برای شروع، این مثال را تصور کنید: برنامه‌ای برای پزشکان می‌نویسید تا شیفت‌های on-call در بیمارستان را مدیریت کنند. بیمارستان معمولاً تلاش می‌کند چند پزشک همزمان on-call باشند، اما حتماً باید حداقل یک پزشک on-call باشد. پزشکان می‌توانند شیفت را رها کنند (مثلاً اگر خودشان بیمارند)، به شرطی که حداقل یک همکار در آن شیفت on-call بماند [۴۰، ۴۱].

حالا فرض کنید Alice و Bob دو پزشک on-call یک شیفت خاص هستند. هر دو احساس ناخوشی می‌کنند و تصمیم می‌گیرند مرخصی بخواهند. متأسفانه تقریباً همزمان دکمهٔ off-call را می‌زنند. آنچه بعد می‌آید در شکل ۷-۸ نشان داده شده.

شکل ۷-۸. نمونهٔ write skew که باعث باگ برنامه می‌شود.

در هر تراکنش، برنامه ابتدا بررسی می‌کند دو پزشک یا بیشتر on-call هستند؛ اگر بله، فرض می‌کند امن است یک پزشک off-call شود. چون پایگاه داده از snapshot isolation استفاده می‌کند، هر دو بررسی ۲ برمی‌گردانند، پس هر دو تراکنش به مرحلهٔ بعد می‌روند. Alice رکورد خود را به‌روز می‌کند و off-call می‌شود، و Bob هم رکورد خود را به‌روز می‌کند. هر دو تراکنش commit می‌شوند و حالا هیچ پزشکی on-call نیست. الزام شما مبنی بر حداقل یک پزشک on-call نقض شده است.

مشخص کردن write skew

این ناهنجاری write skew [۲۸] نامیده می‌شود. نه dirty write است نه lost update، چون دو تراکنش دو شیء متفاوت (رکوردهای on-call Alice و Bob) را به‌روز می‌کنند. کمتر آشکار است که تعارضی رخ داده، اما قطعاً race condition است: اگر دو تراکنش پشت سر هم اجرا می‌شدند، پزشک دوم از off-call شدن منع می‌شد. رفتار ناهنجار فقط به‌خاطر اجرای همزمان تراکنش‌ها ممکن بود.

می‌توانید write skew را تعمیم مسئلهٔ lost update بدانید. write skew وقتی رخ می‌دهد که دو تراکنش همان اشیاء را بخوانند و سپس برخی از آن اشیاء را به‌روز کنند (تراکنش‌های مختلف ممکن است اشیاء متفاوتی به‌روز کنند). در حالت خاص که تراکنش‌های مختلف همان شیء را به‌روز کنند، ناهنجاری dirty write یا lost update (بسته به timing) می‌گیرید.

دیدیم راه‌های مختلفی برای جلوگیری از lost update وجود دارد. با write skew، گزینه‌های ما محدودترند:

• عملیات اتمی تک‌شیءی کمکی نمی‌کند چون چند شیء درگیر است.
• تشخیص خودکار lost update در برخی پیاده‌سازی‌های snapshot isolation متأسفانه کمکی نمی‌کند: write skew در repeatable read PostgreSQL، repeatable read MySQL/InnoDB، serializable Oracle یا snapshot isolation SQL Server به‌طور خودکار تشخیص داده نمی‌شود [۲۳]. جلوگیری خودکار از write skew به isolation واقعاً قابل‌serializable نیاز دارد (به «Serializability» در صفحه ۲۵۱ مراجعه کنید).
• برخی پایگاه‌های داده اجازه می‌دهند قیدها را پیکربندی کنید که پایگاه داده اعمال می‌کند (مثلاً یکتایی، foreign key یا محدودیت روی مقدار خاص). اما برای مشخص کردن اینکه حداقل یک پزشک on-call باشد، به قیدی نیاز دارید که چند شیء را درگیر کند. بیشتر پایگاه‌های داده پشتیبانی داخلی از چنین قیدهایی ندارند، اما بسته به پایگاه داده ممکن است با trigger یا materialized view پیاده کنید [۴۲].
• اگر نمی‌توانید از سطح isolation قابل‌serializable استفاده کنید، دومین گزینهٔ بهتر در این مورد احتمالاً قفل‌گذاری صریح سطرهایی است که تراکنش به آن‌ها وابسته است. در مثال پزشکان:

BEGIN TRANSACTION;

SELECT * FROM doctors
  WHERE on_call = true
  AND shift_id = 1234 FOR UPDATE;

UPDATE doctors
  SET on_call = false
  WHERE name = 'Alice'
  AND shift_id = 1234;

COMMIT;

همان‌طور که قبل، FOR UPDATE به پایگاه داده می‌گوید روی همهٔ سطرهای برگشتی از این پرس‌وجو قفل بگیرد.

نمونه‌های بیشتر از write skew

write skew در ابتدا ممکن است مسئلهٔ عجیبی به نظر برسد، اما وقتی آگاه شدید، موقعیت‌های بیشتری می‌بینید که ممکن است رخ دهد. چند نمونهٔ دیگر:

سیستم رزرو اتاق جلسه فرض کنید می‌خواهید اجرا کنید که نتوان دو رزرو برای همان اتاق جلسه در یک زمان وجود داشته باشد [۴۳]. وقتی کسی می‌خواهد رزرو کند، ابتدا رزروهای متعارض را بررسی می‌کنید (رزرو همان اتاق با بازهٔ زمانی همپوشان) و اگر پیدا نشد، جلسه را ایجاد می‌کنید (مثال ۷-۲ را ببینید).

مثال ۷-۲. سیستم رزرو اتاق جلسه تلاش می‌کند از double-booking جلوگیری کند (تحت snapshot isolation امن نیست)

BEGIN TRANSACTION;

-- Check for any existing bookings that overlap with the period of noon-1pm
SELECT COUNT(*) FROM bookings
  WHERE room_id = 123 AND
    end_time > '2015-01-01 12:00' AND start_time < '2015-01-01 13:00';

-- If the previous query returned zero:
INSERT INTO bookings
  (room_id, start_time, end_time, user_id)
  VALUES (123, '2015-01-01 12:00', '2015-01-01 13:00', 666);

COMMIT;

متأسفانه snapshot isolation از درج همزمان جلسهٔ متعارض توسط کاربر دیگر جلوگیری نمی‌کند. برای تضمین نداشتن تعارض زمان‌بندی، دوباره به isolation قابل‌serializable نیاز دارید.

ix. در PostgreSQL می‌توانید با range typeها این کار را زیباتر انجام دهید، اما در پایگاه‌های دیگر پشتیبانی گسترده‌ای ندارند.

بازی چندنفره در مثال ۷-۱ از قفل برای جلوگیری از lost update استفاده کردیم (یعنی دو بازیکن نتوانند همزمان همان مهره را جابه‌جا کنند). با این حال، قفل از جابه‌جایی دو مهرهٔ مختلف به یک موقعیت روی صفحه یا حرکت دیگری که قوانین بازی را نقض کند جلوگیری نمی‌کند. بسته به نوع قانونی که اعمال می‌کنید، شاید بتوانید از قید یکتایی استفاده کنید، وگرنه در برابر write skew آسیب‌پذیرید.

ثبت نام کاربری در وب‌سایتی که هر کاربر نام کاربری یکتا دارد، دو کاربر ممکن است همزمان بخواهند با همان نام کاربری حساب بسازند. ممکن است از تراکنش برای بررسی گرفته بودن نام و در صورت آزاد بودن ایجاد حساب استفاده کنید. اما مانند نمونه‌های قبلی، تحت snapshot isolation امن نیست. خوشبختانه قید یکتایی راه‌حل ساده‌ای است (تراکنش دوم که می‌خواهد نام کاربری را ثبت کند به‌خاطر نقض قید abort می‌شود).

جلوگیری از double-spending سرویسی که به کاربران اجازهٔ خرج پول یا امتیاز می‌دهد باید بررسی کند کاربر بیش از موجودی‌اش خرج نکند. ممکن است با درج آیتم خرج موقت در حساب کاربر، فهرست همهٔ آیتم‌ها و بررسی مثبت بودن مجموع پیاده کنید [۴۴]. با write skew ممکن است دو آیتم خرج همزمان درج شوند که مجموعاً موجودی را منفی کنند، اما هیچ تراکنشی دیگری را متوجه نشود.

phantomهایی که باعث write skew می‌شوند

همهٔ این نمونه‌ها الگوی مشابهی دارند:

۱. پرس‌وجوی SELECT بررسی می‌کند آیا الزامی با جستجوی سطرهایی که شرط جستجو را برآورده می‌کنند برقرار است (حداقل دو پزشک on-call هستند، رزرو موجودی برای آن اتاق در آن زمان نیست، موقعیت روی صفحه مهرهٔ دیگری ندارد، نام کاربری گرفته نشده، هنوز پول در حساب است). ۲. بسته به نتیجهٔ پرس‌وجوی اول، کد برنامه تصمیم می‌گیرد چگونه ادامه دهد (شاید عملیات را انجام دهد، شاید خطا به کاربر گزارش دهد و abort کند). ۳. اگر برنامه تصمیم به ادامه گرفت، نوشتنی (INSERT، UPDATE یا DELETE) به پایگاه داده انجام می‌دهد و تراکنش را commit می‌کند. اثر این نوشتن پیش‌شرط تصمیم گام ۲ را تغییر می‌دهد. به عبارت دیگر، اگر پس از commit نوشتن، پرس‌وجوی SELECT گام ۱ را تکرار کنید، نتیجهٔ متفاوتی می‌گیرید چون نوشتن مجموعهٔ سطرهای منطبق با شرط جستجو را تغییر داده (حالا یک پزشک on-call کمتر است، اتاق جلسه برای آن زمان رزرو شده، موقعیت روی صفحه توسط مهرهٔ جابه‌جاشده اشغال شده، نام کاربری گرفته شده، پول کمتری در حساب است).

گام‌ها ممکن است ترتیب متفاوتی داشته باشند. مثلاً ابتدا نوشتن، سپس پرس‌وجوی SELECT و در نهایت تصمیم abort یا commit بر اساس نتیجهٔ پرس‌وجو.

در مثال پزشک on-call، سطری که در گام ۳ تغییر می‌کند یکی از سطرهای برگشتی در گام ۱ بود، پس می‌توانستیم با قفل‌گذاری سطرها در گام ۱ (SELECT FOR UPDATE) تراکنش را امن و از write skew جلوگیری کنیم. اما چهار نمونهٔ دیگر متفاوت‌اند: آن‌ها نبود سطرهای منطبق با شرط جستجو را بررسی می‌کنند و نوشتن سطری منطبق با همان شرط اضافه می‌کند. اگر پرس‌وجوی گام ۱ هیچ سطری برنگرداند، SELECT FOR UPDATE چیزی برای قفل‌گذاری ندارد.

این اثر، جایی که نوشتن در یک تراکنش نتیجهٔ پرس‌وجوی جستجو در تراکنش دیگر را تغییر می‌دهد، phantom [۳] نامیده می‌شود. snapshot isolation از phantom در پرس‌وجوهای فقط-خواندن جلوگیری می‌کند، اما در تراکنش‌های read-write مانند نمونه‌هایی که بحث کردیم، phantomها می‌توانند به موارد به‌ویژه پیچیدهٔ write skew منجر شوند.

مادی‌سازی تعارض‌ها

اگر مسئلهٔ phantomها این است که شیئی برای قفل‌گذاری وجود ندارد، شاید بتوانیم مصنوعاً شیء قفل به پایگاه داده معرفی کنیم؟

مثلاً در مورد رزرو اتاق جلسه می‌توانید جدولی از بازه‌های زمانی و اتاق‌ها تصور کنید. هر سطر این جدول به اتاق خاصی برای بازهٔ زمانی خاص (مثلاً ۱۵ دقیقه) مربوط است. سطرها را از قبل برای همهٔ ترکیب‌های ممکن اتاق و بازهٔ زمانی ایجاد می‌کنید، مثلاً برای شش ماه آینده.

حالا تراکنشی که می‌خواهد رزرو ایجاد کند می‌تواند سطرهای جدول متناظر با اتاق و بازهٔ زمانی موردنظر را قفل کند (SELECT FOR UPDATE). پس از گرفتن قفل‌ها، رزروهای همپوشان را بررسی و رزرو جدید را مانند قبل درج می‌کند. توجه کنید جدول اضافی برای ذخیرهٔ اطلاعات رزرو نیست — صرفاً مجموعه‌ای از قفل‌هاست که از تغییر همزمان رزرو همان اتاق و بازهٔ زمانی جلوگیری می‌کند.

این رویکرد materializing conflicts نامیده می‌شود چون phantom را به تعارض قفل روی مجموعهٔ مشخصی از سطرهای موجود در پایگاه داده تبدیل می‌کند [۱۱]. متأسفانه، فهمیدن نحوهٔ materialize کردن تعارض‌ها می‌تواند سخت و مستعد خطا باشد و زشت است که مکانیزم کنترل همزمانی به مدل دادهٔ برنامه نشت کند. به همین دلایل، materializing conflicts باید آخرین راه‌حل در نظر گرفته شود اگر جایگزین ممکن نباشد. سطح isolation قابل‌serializable در بیشتر موارد بسیار ترجیح دارد.

Serializability

در این فصل نمونه‌های زیادی از تراکنش‌های مستعد race condition دیدیم. برخی race conditionها با سطوح read committed و snapshot isolation جلوگیری می‌شوند، اما برخی نه. با write skew و phantom به مثال‌های به‌ویژه پیچیده‌ای برخوردیم. وضعیت تأسف‌باری است:

• سطوح isolation فهمیدن‌شان سخت است و در پایگاه‌های دادهٔ مختلف ناهمگون پیاده می‌شوند (مثلاً معنای «repeatable read» به‌طور قابل‌توجهی متفاوت است).
• اگر به کد برنامه نگاه کنید، دشوار است بفهمید اجرا در سطح isolation خاصی امن است — به‌ویژه در برنامهٔ بزرگ که ممکن است از همهٔ چیزهایی که همزمان رخ می‌دهند آگاه نباشید.
• ابزار خوبی برای تشخیص race condition نداریم. از نظر تئوری، تحلیل ایستا ممکن است کمک کند [۲۶]، اما تکنیک‌های پژوهشی هنوز به کار عملی نرسیده‌اند. تست مسائل همزمانی سخت است چون معمولاً غیرقطعی‌اند — مشکلات فقط با بدشانسی در timing رخ می‌دهند.

این مسئلهٔ جدیدی نیست — از دههٔ ۱۹۷۰، وقتی سطوح isolation ضعیف معرفی شدند، همین‌طور بوده [۲]. پاسخ پژوهشگران همیشه ساده بوده: از isolation قابل‌serializable استفاده کنید!

isolation قابل‌serializable معمولاً قوی‌ترین سطح isolation تلقی می‌شود. تضمین می‌کند حتی اگر تراکنش‌ها موازی اجرا شوند، نتیجهٔ نهایی همان است که گویی یکی‌یکی و بدون همزمانی اجرا شده‌اند. پس پایگاه داده تضمین می‌کند اگر تراکنش‌ها به‌تنهایی درست رفتار کنند، هنگام اجرای همزمان هم درست بمانند — یعنی پایگاه داده از همهٔ race conditionهای ممکن جلوگیری می‌کند.

اما اگر isolation قابل‌serializable این‌قدر بهتر از آشفتگی سطوح isolation ضعیف است، چرا همه از آن استفاده نمی‌کنند؟ برای پاسخ باید گزینه‌های پیاده‌سازی serializability و کارایی آن‌ها را ببینیم. بیشتر پایگاه‌های داده‌ای که امروز serializability می‌دهند از یکی از سه تکنیک استفاده می‌کنند که در ادامهٔ این فصل بررسی می‌کنیم:

• اجرای واقعاً ترتیبی تراکنش‌ها (به «اجرای واقعاً ترتیبی» در صفحه ۲۵۲ مراجعه کنید)
• قفل‌گذاری دوفازی (2PL) (به «قفل‌گذاری دوفازی (2PL)» در صفحه ۲۵۷ مراجعه کنید) که چند دهه تنها گزینهٔ عملی بود
• تکنیک‌های کنترل همزمانی خوش‌بینانه مانند serializable snapshot isolation (به «ایزولاسیون snapshot قابل‌serializable (SSI)» در صفحه ۲۶۱ مراجعه کنید)

فعلاً این تکنیک‌ها را عمدتاً در زمینهٔ پایگاه‌های دادهٔ تک‌گره‌ای بحث می‌کنیم؛ در فصل ۹ بررسی می‌کنیم چگونه به تراکنش‌های چندگره‌ای در سیستم توزیع‌شده تعمیم یابند.

اجرای واقعاً ترتیبی

ساده‌ترین راه جلوگیری از مسائل همزمانی حذف کامل همزمانی است: اجرای فقط یک تراکنش در هر لحظه، به‌صورت ترتیبی، روی یک نخ. با این کار کاملاً از مسئلهٔ تشخیص و جلوگیری از تعارض بین تراکنش‌ها دور می‌زنیم: isolation حاصل به‌تعریف serializable است.

اگرچه این ایدهٔ بدیهی به نظر می‌رسد، طراحان پایگاه داده فقط نسبتاً اخیراً — حدود ۲۰۰۷ — تصمیم گرفتند حلقهٔ تک‌نخی برای اجرای تراکنش‌ها عملی است [۴۵]. اگر همزمانی چندنخی برای کارایی خوب در ۳۰ سال قبل ضروری تلقی می‌شد، چه تغییری اجرای تک‌نخی را ممکن کرد؟

دو تحول باعث این بازنگری شد:

• RAM آن‌قدر ارزان شد که برای بسیاری use caseها نگه‌داشتن کل مجموعهٔ دادهٔ فعال در حافظه عملی است (به «نگه‌داشتن همه‌چیز در حافظه» در صفحه ۸۸ مراجعه کنید). وقتی همهٔ داده‌ای که تراکنش نیاز دارد در حافظه باشد، تراکنش‌ها بسیار سریع‌تر از انتظار برای بارگذاری از دیسک اجرا می‌شوند.
• طراحان پایگاه داده فهمیدند تراکنش‌های OLTP معمولاً کوتاه‌اند و تعداد کمی خواندن و نوشتن انجام می‌دهند (به «پردازش تراکنش یا تحلیل؟» در صفحه ۹۰ مراجعه کنید). در مقابل، پرس‌وجوهای تحلیلی طولانی‌مدت معمولاً فقط-خواندن‌اند و می‌توانند روی snapshot سازگار (با snapshot isolation) خارج از حلقهٔ اجرای ترتیبی اجرا شوند.

رویکرد اجرای ترتیبی تراکنش‌ها در VoltDB/H-Store، Redis و Datomic پیاده شده [۴۶، ۴۷، ۴۸]. سیستمی که برای اجرای تک‌نخی طراحی شده گاهی بهتر از سیستمی که همزمانی پشتیبانی می‌کند عمل می‌کند چون از سربار هماهنگی قفل‌ها اجتناب می‌کند. با این حال، throughput به سرعت یک هستهٔ CPU محدود است. برای بهره‌برداری از آن نخ، تراکنش‌ها باید ساختار متفاوتی از شکل سنتی داشته باشند.

کپسوله‌سازی تراکنش‌ها در stored procedureها

در روزهای اولیهٔ پایگاه‌های داده، قصد این بود که تراکنش پایگاه داده کل جریان فعالیت کاربر را در بر بگیرد. مثلاً رزرو بلیط هواپیما فرایند چندمرحله‌ای است (جستجوی مسیر، کرایه و صندلی؛ انتخاب برنامهٔ سفر؛ رزرو صندلی هر پرواز؛ وارد کردن اطلاعات مسافر؛ پرداخت). طراحان پایگاه داده فکر می‌کردند خوب است کل این فرایند یک تراکنش باشد تا به‌صورت atomic commit شود.

متأسفانه، انسان‌ها برای تصمیم‌گیری و پاسخ دادن بسیار کندند. اگر تراکنش پایگاه داده منتظر ورودی کاربر بماند، پایگاه داده باید تعداد بسیار زیادی تراکنش همزمان را پشتیبانی کند که بیشترشان بیکارند. بیشتر پایگاه‌های داده این را به‌طور مؤثر نمی‌توانند، پس تقریباً همهٔ برنامه‌های OLTP با اجتناب از انتظار تعاملی برای کاربر در تراکنش، تراکنش‌ها را کوتاه نگه می‌دارند. در وب یعنی تراکنش در همان درخواست HTTP commit می‌شود — تراکنش چند درخواست را در بر نمی‌گیرد. هر درخواست HTTP جدید تراکنش جدیدی شروع می‌کند.

اگرچه انسان از مسیر بحرانی خارج شده، تراکنش‌ها همچنان به سبک تعاملی client/server و دستور به دستور اجرا می‌شوند. برنامه پرس‌وجو می‌کند، نتیجه را می‌خواند، شاید بسته به نتیجهٔ اول پرس‌وجوی دیگری می‌کند و غیره. پرس‌وجوها و نتایج بین کد برنامه (روی یک ماشین) و سرور پایگاه داده (روی ماشین دیگر) رد و بدل می‌شوند.

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

به همین دلیل، سیستم‌های با پردازش ترتیبی تک‌نخی تراکنش‌های تعاملی چنددستوری را اجازه نمی‌دهند. به‌جای آن، برنامه باید کل کد تراکنش را از قبل به پایگاه داده به‌عنوان stored procedure بدهد. تفاوت این رویکردها در شکل ۷-۹ نشان داده شده. اگر همهٔ دادهٔ موردنیاز تراکنش در حافظه باشد، stored procedure می‌تواند بسیار سریع بدون انتظار برای شبکه یا I/O دیسک اجرا شود.

شکل ۷-۹. تفاوت تراکنش تعاملی و stored procedure (با مثال تراکنش شکل ۷-۸).

مزایا و معایب stored procedureها

stored procedureها مدتی در پایگاه‌های دادهٔ رابطه‌ای وجود دارند و از ۱۹۹۹ بخشی از استاندارد SQL (SQL/PSM) هستند. شهرت نسبتاً بدی دارند، به دلایل مختلف:

• هر فروشندهٔ پایگاه داده زبان خود برای stored procedure دارد (Oracle PL/SQL، SQL Server T-SQL، PostgreSQL PL/pgSQL و غیره). این زبان‌ها با پیشرفت زبان‌های برنامه‌نویسی عمومی همگام نشده‌اند، پس از دید امروز زشت و کهنه به نظر می‌رسند و اکوسیستم کتابخانه‌ای که در بیشتر زبان‌ها هست ندارند.
• کد در حال اجرا در پایگاه داده مدیریتش سخت است: نسبت به سرور برنامه، debug سخت‌تر، نگه‌داری در version control و deploy ناجورتر، تست دشوارتر و یکپارچگی با سیستم جمع‌آوری metrics برای نظارت سخت‌تر است.
• پایگاه داده اغلب نسبت به سرور برنامه حساس‌تر به کارایی است چون یک نمونهٔ پایگاه داده اغلب بین چند سرور برنامه به‌اشتراک گذاشته می‌شود. stored procedure بدنوشت (مثلاً مصرف زیاد حافظه یا CPU) در پایگاه داده می‌تواند دردسر بیشتری از کد بد معادل در سرور برنامه ایجاد کند.

با این حال، این مسائل قابل‌غلبه‌اند. پیاده‌سازی‌های مدرن stored procedureها PL/SQL را رها کرده‌اند و از زبان‌های برنامه‌نویسی عمومی موجود استفاده می‌کنند: VoltDB از Java یا Groovy، Datomic از Java یا Clojure، Redis از Lua.

با stored procedureها و دادهٔ in-memory، اجرای همهٔ تراکنش‌ها روی یک نخ عملی می‌شود. چون نیازی به انتظار I/O ندارند و از سربار مکانیزم‌های دیگر کنترل همزمانی اجتناب می‌کنند، می‌توانند throughput خوبی روی یک نخ داشته باشند.

VoltDB هم از stored procedure برای تکثیر استفاده می‌کند: به‌جای کپی نوشتن‌های تراکنش از یک گره به گره دیگر، همان stored procedure را روی هر replica اجرا می‌کند. بنابراین VoltDB می‌خواهد stored procedureها deterministic باشند (روی گره‌های مختلف نتیجهٔ یکسان بدهند). اگر تراکنش به تاریخ و زمان فعلی نیاز دارد، باید از APIهای deterministic ویژه استفاده کند.

پارتیشن‌بندی

اجرای ترتیبی همهٔ تراکنش‌ها کنترل همزمانی را بسیار ساده می‌کند، اما throughput تراکنش پایگاه داده را به سرعت یک هستهٔ CPU روی یک ماشین محدود می‌کند. تراکنش‌های فقط-خواندن ممکن است جای دیگر با snapshot isolation اجرا شوند، اما برای برنامه‌های با throughput نوشتن بالا، پردازشگر تراکنش تک‌نخی می‌تواند گلوگاه جدی شود.

برای مقیاس به چند هستهٔ CPU و چند گره، می‌توانید داده را پارتیشن کنید (فصل ۶ را ببینید) که VoltDB پشتیبانی می‌کند. اگر راهی برای پارتیشن‌بندی مجموعه داده پیدا کنید که هر تراکنش فقط در یک پارتیشن بخواند و بنویسد، هر پارتیشن می‌تواند نخ پردازش تراکنش مستقل خود را داشته باشد. در این صورت به هر هستهٔ CPU یک پارتیشن می‌دهید و throughput تراکنش خطی با تعداد هسته‌ها مقیاس می‌یابد [۴۷].

با این حال، برای هر تراکنشی که به چند پارتیشن دسترسی نیاز دارد، پایگاه داده باید تراکنش را در همهٔ پارتیشن‌های لمس‌شده هماهنگ کند. stored procedure باید در همهٔ پارتیشن‌ها lock-step اجرا شود تا serializability در کل سیستم تضمین شود.

چون تراکنش‌های بین‌پارتیشنی سربار هماهنگی اضافی دارند، بسیار کندتر از تراکنش‌های تک‌پارتیشنی‌اند. VoltDB throughput حدود ۱٬۰۰۰ نوشتن بین‌پارتیشنی در ثانیه گزارش می‌دهد که چند مرتبه کمتر از throughput تک‌پارتیشنی است و با افزودن ماشین بیشتر قابل افزایش نیست [۴۹].

اینکه تراکنش‌ها تک‌پارتیشنی باشند یا نه به‌شدت به ساختار دادهٔ مورد استفادهٔ برنامه بستگی دارد. دادهٔ key-value ساده اغلب به‌راحتی پارتیشن می‌شود، اما داده با چند ایندکس ثانویه احتمالاً به هماهنگی زیاد بین‌پارتیشنی نیاز دارد (به «پارتیشن‌بندی و ایندکس‌های ثانویه» در صفحه ۲۰۶ مراجعه کنید).

خلاصهٔ اجرای ترتیبی

اجرای ترتیبی تراکنش‌ها در محدودیت‌های خاصی راه عملی دستیابی به isolation قابل‌serializable شده:

• هر تراکنش باید کوچک و سریع باشد، چون فقط یک تراکنش کند کافی است تا کل پردازش تراکنش متوقف شود.
• به use caseهایی محدود است که مجموعهٔ دادهٔ فعال در حافظه جا شود. دادهٔ به‌ندرت دسترسی‌یافته شاید به دیسک منتقل شود، اما اگر در تراکنش تک‌نخی لازم شود، سیستم بسیار کند می‌شود.
• throughput نوشتن باید آن‌قدر پایین باشد که یک هستهٔ CPU کفایت کند، یا تراکنش‌ها باید بدون نیاز به هماهنگی بین‌پارتیشنی پارتیشن شوند.
• تراکنش‌های بین‌پارتیشنی ممکن‌اند، اما محدودیت سختی در میزان استفاده از آن‌ها وجود دارد.

x. اگر تراکنش به داده‌ای نیاز دارد که در حافظه نیست، بهترین راه‌حل ممکن است abort تراکنش، واکشی ناهمگام داده به حافظه در حین پردازش تراکنش‌های دیگر و سپس راه‌اندازی مجدد تراکنش پس از بارگذاری داده باشد. این رویکرد anti-caching نامیده می‌شود، همان‌طور که قبلاً در «نگه‌داشتن همه‌چیز در حافظه» در صفحه ۸۸ ذکر شد.

قفل‌گذاری دوفازی (2PL)

حدود ۳۰ سال، تنها الگوریتم پرکاربرد برای serializability در پایگاه‌های داده قفل‌گذاری دوفازی (2PL) بود.

2PL همان 2PC نیست

توجه کنید اگرچه two-phase locking (2PL) بسیار شبیه two-phase commit (2PC) به نظر می‌رسد، کاملاً چیزهای متفاوتی‌اند. 2PC را در فصل ۹ بحث می‌کنیم.

قبلاً دیدیم قفل‌ها اغلب برای جلوگیری از dirty write به کار می‌روند (به «عدم dirty write» در صفحه ۲۳۵ مراجعه کنید): اگر دو تراکنش همزمان بخواهند همان شیء را بنویسند، قفل تضمین می‌کند نویسندهٔ دوم باید صبر کند تا اولی تراکنشش را تمام کند (abort یا commit) قبل از ادامه.

2PL مشابه است، اما الزامات قفل را بسیار سخت‌تر می‌کند. چند تراکنش می‌توانند همزمان همان شیء را بخوانند تا وقتی کسی ننویسد. اما به‌محض اینکه کسی بخواهد بنویسد (تغییر یا حذف)، دسترسی انحصاری لازم است:

• اگر تراکنش A شیء را خوانده و تراکنش B بخواهد بنویسد، B باید صبر کند تا A commit یا abort کند (تا B نتواند پشت سر A شیء را غیرمنتظره تغییر دهد).
• اگر تراکنش A شیء را نوشته و تراکنش B بخواهد بخواند، B باید صبر کند تا A commit یا abort کند (خواندن نسخهٔ قدیمی شیء، مثل شکل ۷-۱، تحت 2PL قابل قبول نیست).

در 2PL، نویسندگان فقط نویسندگان دیگر را مسدود نمی‌کنند؛ خوانندگان را هم مسدود می‌کنند و بالعکس. snapshot isolation شعار «خوانندگان هرگز نویسندگان را مسدود نمی‌کنند و نویسندگان هرگز خوانندگان را مسدود نمی‌کنند» دارد (به «پیاده‌سازی ایزولاسیون snapshot» در صفحه ۲۳۹ مراجعه کنید) که این تفاوت کلیدی بین snapshot isolation و 2PL را نشان می‌دهد. از سوی دیگر، چون 2PL serializability می‌دهد، از همهٔ race conditionهای بحث‌شده از جمله lost update و write skew محافظت می‌کند.

پیاده‌سازی قفل‌گذاری دوفازی

2PL در سطح isolation serializable در MySQL (InnoDB) و SQL Server، و سطح repeatable read در DB2 استفاده می‌شود [۲۳، ۳۶].

xi. گاهی strong strict two-phase locking (SS2PL) نامیده می‌شود تا از انواع دیگر 2PL متمایز شود.

مسدود شدن خوانندگان و نویسندگان با داشتن قفل روی هر شیء در پایگاه داده پیاده می‌شود. قفل می‌تواند در حالت shared یا exclusive باشد. قفل این‌طور به کار می‌رود:

• اگر تراکنش بخواهد شیء را بخواند، ابتدا باید قفل را در حالت shared بگیرد. چند تراکنش می‌توانند همزمان قفل shared داشته باشند، اما اگر تراکنش دیگری قفل exclusive روی شیء دارد، باید صبر کنند.
• اگر تراکنش بخواهد بنویسد، ابتدا باید قفل را در حالت exclusive بگیرد. هیچ تراکنش دیگری نمی‌تواند همزمان قفل داشته باشد (نه shared نه exclusive)، پس اگر قفل موجودی باشد، تراکنش باید صبر کند.
• اگر تراکنش ابتدا بخواند و سپس بنویسد، ممکن است قفل shared را به exclusive ارتقا دهد. ارتقا مانند گرفتن مستقیم قفل exclusive کار می‌کند.
• پس از گرفتن قفل، تراکنش باید تا پایان تراکنش (commit یا abort) قفل را نگه دارد. از اینجا نام «دوفازی» می‌آید: فاز اول (حین اجرای تراکنش) گرفتن قفل‌ها و فاز دوم (پایان تراکنش) رها کردن همهٔ قفل‌ها.

چون قفل‌های زیادی در حال استفاده‌اند، به‌راحتی ممکن است تراکنش A منتظر رها شدن قفل تراکنش B بماند و بالعکس. این وضعیت deadlock نامیده می‌شود. پایگاه داده deadlock بین تراکنش‌ها را خودکار تشخیص داده و یکی را abort می‌کند تا بقیه پیشرفت کنند. تراکنش abort‌شده باید توسط برنامه دوباره تلاش شود.

کارایی قفل‌گذاری دوفازی

نقطهٔ ضعف بزرگ 2PL و دلیلی که از دههٔ ۱۹۷۰ همه از آن استفاده نکرده‌اند، کارایی است: throughput تراکنش و زمان پاسخ پرس‌وجوها تحت 2PL به‌طور قابل‌توجهی بدتر از isolation ضعیف است.

این تا حدی به سربار گرفتن و رها کردن همهٔ آن قفل‌ها مربوط است، اما مهم‌تر به کاهش همزمانی است. از طراحی، اگر دو تراکنش همزمان کاری انجام دهند که ممکن است به هر شکلی race condition ایجاد کند، یکی باید منتظر تکمیل دیگری بماند.

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

به همین دلیل، پایگاه‌های داده با 2PL می‌توانند latency ناپایدار داشته باشند و در percentileهای بالا (به «توصیف کارایی» در صفحه ۱۳ مراجعه کنید) در بارکاری با contention بسیار کند باشند. ممکن است فقط یک تراکنش کند، یا تراکنشی که به دادهٔ زیاد دسترسی دارد و قفل‌های زیادی می‌گیرد، باعث شود کل سیستم متوقف شود. این ناپایداری برای عملیات قوی مشکل‌ساز است.

اگرچه deadlock با سطح isolation read committed مبتنی بر قفل ممکن است رخ دهد، تحت isolation serializable با 2PL بسیار مکررتر است (بسته به الگوهای دسترسی تراکنش‌های شما). این می‌تواند مشکل کارایی اضافی باشد: وقتی تراکنش به‌خاطر deadlock abort می‌شود و دوباره تلاش می‌شود، باید کل کار را از نو انجام دهد. اگر deadlockها مکرر باشند، این یعنی تلاش هدررفتهٔ قابل‌توجه.

قفل‌های predicate

در توصیف قبلی قفل‌ها، جزئیات ظریف اما مهمی را نادیده گرفتیم. در «phantomهایی که باعث write skew می‌شوند» در صفحه ۲۵۰ مسئلهٔ phantom را بحث کردیم — یعنی تراکنشی نتیجهٔ پرس‌وجوی جستجوی تراکنش دیگر را تغییر می‌دهد. پایگاه داده با isolation serializable باید از phantom جلوگیری کند.

در مثال رزرو اتاق جلسه یعنی اگر یک تراکنش رزروهای موجود برای اتاق در بازهٔ زمانی خاص را جستجو کرده (مثال ۷-۲ را ببینید)، تراکنش دیگر نباید همزمان رزرو دیگری برای همان اتاق و بازهٔ زمانی درج یا به‌روز کند. (درج رزرو برای اتاق‌های دیگر یا همان اتاق در زمان دیگری که روی رزرو پیشنهادی اثر ندارد، مشکلی نیست.)

چگونه پیاده‌سازی کنیم؟ از نظر مفهومی به predicate lock [۳] نیاز داریم. مشابه قفل shared/exclusive که قبلاً توصیف شد کار می‌کند، اما به شیء خاصی (مثلاً یک سطر) تعلق ندارد؛ به همهٔ اشیائی که شرط جستجویی را برآورده می‌کنند تعلق دارد، مثل:

SELECT * FROM bookings
  WHERE room_id = 123 AND
    end_time   > '2018-01-01 12:00' AND
    start_time < '2018-01-01 13:00';

predicate lock دسترسی را این‌طور محدود می‌کند:

• اگر تراکنش A بخواهد اشیائی منطبق با شرطی بخواند، مثل آن SELECT، باید predicate lock در حالت shared روی شرط پرس‌وجو بگیرد. اگر تراکنش B قفل exclusive روی هر شیء منطبق با آن شرایط دارد، A باید صبر کند تا B قفل را رها کند.
• اگر تراکنش A بخواهد شیئی درج، به‌روز یا حذف کند، ابتدا باید بررسی کند آیا مقدار قدیمی یا جدید با predicate lock موجودی مطابقت دارد. اگر predicate lock متناظر توسط تراکنش B گرفته شده، A باید صبر کند تا B commit یا abort کند.

ایدهٔ کلیدی این است که predicate lock حتی روی اشیائی که هنوز در پایگاه داده وجود ندارند اما ممکن است در آینده اضافه شوند (phantom) اعمال می‌شود. اگر 2PL شامل predicate lock باشد، پایگاه داده از همهٔ اشکال write skew و race conditionهای دیگر جلوگیری می‌کند و isolation آن serializable می‌شود.

قفل‌های محدودهٔ ایندکس

متأسفانه، predicate lockها کارایی خوبی ندارند: اگر قفل‌های زیادی توسط تراکنش‌های فعال وجود داشته باشد، بررسی قفل‌های منطبق زمان‌بر می‌شود. به همین دلیل، بیشتر پایگاه‌های داده با 2PL در واقع index-range locking (که next-key locking هم نامیده می‌شود) را پیاده می‌کنند که تقریب ساده‌شدهٔ predicate locking است [۴۱، ۵۰].

ایمن است predicate را با منطبق کردن با مجموعهٔ بزرگ‌تری از اشیاء ساده کنیم. مثلاً اگر predicate lock برای رزروهای اتاق ۱۲۳ بین ظهر و ۱ بعدازظهر دارید، می‌توانید آن را با قفل‌کردن رزروهای اتاق ۱۲۳ در هر زمان، یا قفل‌کردن همهٔ اتاق‌ها (نه فقط ۱۲۳) بین ظهر و ۱ بعدازظهر تقریب بزنید. این ایمن است چون هر نوشتنی که با predicate اصلی مطابقت دارد حتماً با تقریب‌ها هم مطابقت دارد.

در پایگاه دادهٔ رزرو اتاق احتمالاً ایندکس روی ستون room_id و/یا ایندکس روی start_time و end_time دارید (وگرنه پرس‌وجوی قبلی روی پایگاه بزرگ بسیار کند است):

• فرض کنید ایندکس روی room_id است و پایگاه داده از این ایندکس برای یافتن رزروهای موجود اتاق ۱۲۳ استفاده می‌کند. حالا پایگاه داده می‌تواند قفل shared به ورودی ایندکس بچسباند که نشان می‌دهد تراکنشی رزروهای اتاق ۱۲۳ را جستجو کرده.
• یا اگر پایگاه داده از ایندکس مبتنی بر زمان برای یافتن رزروهای موجود استفاده کند، می‌تواند قفل shared به بازه‌ای از مقادیر در آن ایندکس بچسباند که نشان می‌دهد تراکنشی رزروهایی با بازهٔ زمانی همپوشان با ظهر تا ۱ بعدازظهر ۱ ژانویه ۲۰۱۸ را جستجو کرده.

در هر صورت، تقریبی از شرط جستجو به یکی از ایندکس‌ها چسبانده می‌شود. حالا اگر تراکنش دیگری بخواهد رزروی برای همان اتاق و/یا بازهٔ زمانی همپوشان درج، به‌روز یا حذف کند، باید همان بخش ایندکس را به‌روز کند. در این فرایند به قفل shared برخورد می‌کند و مجبور به انتظار تا رها شدن قفل می‌شود.

این از phantom و write skew به‌طور مؤثر محافظت می‌کند. قفل‌های محدودهٔ ایندکس به‌دقت predicate lock نیستند (ممکن است بازهٔ بزرگ‌تری از اشیاء را قفل کنند که برای حفظ serializability لزوماً لازم نیست)، اما چون سربار کمتری دارند، سازش خوبی‌اند.

اگر ایندکس مناسبی برای چسباندن range lock نباشد، پایگاه داده می‌تواند به قفل shared روی کل جدول برگردد. این برای کارایی خوب نیست چون همهٔ تراکنش‌های نوشتن دیگر را متوقف می‌کند، اما موقعیت fallback امنی است.

ایزولاسیون snapshot قابل‌serializable (SSI)

این فصل تصویر تیره‌ای از کنترل همزمانی در پایگاه‌های داده ترسیم کرد. از یک سو، پیاده‌سازی‌های serializability داریم که کارایی خوبی ندارند (2PL) یا خوب مقیاس نمی‌شوند (اجرای ترتیبی). از سوی دیگر، سطوح isolation ضعیف با کارایی خوب اما مستعد race conditionهای مختلف (lost update، write skew، phantom و غیره). آیا isolation قابل‌serializable و کارایی خوب اساساً در تضادند؟

شاید نه: الگوریتمی به نام serializable snapshot isolation (SSI) بسیار امیدوارکننده است. serializability کامل می‌دهد اما فقط جریمهٔ کارایی کوچکی نسبت به snapshot isolation دارد. SSI نسبتاً جدید است: اولین بار در ۲۰۰۸ توصیف شد [۴۰] و موضوع پایان‌نامهٔ دکترای Michael Cahill است [۵۱].

امروز SSI هم در پایگاه‌های دادهٔ تک‌گره‌ای (سطح isolation serializable در PostgreSQL از نسخهٔ ۹.۱ [۴۱]) و هم در پایگاه‌های توزیع‌شده (FoundationDB از الگوریتم مشابهی استفاده می‌کند) به کار می‌رود. چون SSI در مقایسه با مکانیزم‌های دیگر کنترل همزمانی جوان است، هنوز کارایی‌اش را در عمل ثابت می‌کند، اما امکان دارد به‌اندازهٔ کافی سریع شود تا در آینده پیش‌فرض جدید شود.

کنترل همزمانی بدبینانه در برابر خوش‌بینانه

2PL مکانیزم کنترل همزمانی بدبینانه‌ای است: بر اصل اینکه اگر هر چیزی ممکن است اشتباه پیش برود (با نشانهٔ قفل نگه‌داشته‌شده توسط تراکنش دیگر)، بهتر است صبر کنید تا وضعیت دوباره امن شود. شبیه mutual exclusion که برای محافظت از ساختارهای داده در برنامه‌نویسی چندنخی به کار می‌رود.

اجرای ترتیبی، به‌نوعی، بدبینانه در حد افراط است: اساساً معادل این است که هر تراکنش قفل انحصاری روی کل پایگاه داده (یا یک پارتیشن) برای مدت تراکنش دارد. بدبینی را با سریع اجرا کردن هر تراکنش جبران می‌کنیم تا فقط مدت کوتاهی «قفل» را نگه دارد.

در مقابل، serializable snapshot isolation تکنیک کنترل همزمانی خوش‌بینانه است. خوش‌بینانه در این زمینه یعنی به‌جای مسدود کردن وقتی چیز خطرناکی ممکن است رخ دهد، تراکنش‌ها به هر حال ادامه می‌دهند و امیدوارند همه‌چیز درست پیش برود. وقتی تراکنش می‌خواهد commit کند، پایگاه داده بررسی می‌کند آیا چیز بدی رخ داده (یعنی isolation نقض شده)؛ اگر بله، تراکنش abort و باید دوباره تلاش شود. فقط تراکنش‌هایی که به‌صورت serializable اجرا شده‌اند اجازهٔ commit دارند.

کنترل همزمانی خوش‌بینانه ایدهٔ قدیمی است [۵۲] و مزایا و معایبش مدت‌ها بحث شده [۵۳]. در contention بالا (تراکنش‌های زیادی که به همان اشیاء دسترسی دارند) بد عمل می‌کند چون نسبت زیادی از تراکنش‌ها باید abort شوند. اگر سیستم نزدیک حداکثر throughput باشد، بار اضافی تراکنش‌های دوباره‌تلاش‌شده می‌تواند کارایی را بدتر کند.

با این حال، اگر ظرفیت اضافی کافی باشد و contention بین تراکنش‌ها خیلی بالا نباشد، تکنیک‌های خوش‌بینانه معمولاً بهتر از بدبینانه عمل می‌کنند. contention را می‌توان با عملیات اتمی commutative کاهش داد: مثلاً اگر چند تراکنش همزمان بخواهند شمارنده را افزایش دهند، ترتیب افزایش‌ها مهم نیست (تا وقتی شمارنده در همان تراکنش خوانده نشود)، پس افزایش‌های همزمان می‌توانند بدون تعارض اعمال شوند.

همان‌طور که از نامش پیداست، SSI بر snapshot isolation استوار است — یعنی همهٔ خواندن‌ها در یک تراکنش از snapshot سازگار پایگاه داده انجام می‌شوند (به «ایزولاسیون snapshot و repeatable read» در صفحه ۲۳۷ مراجعه کنید). این تفاوت اصلی با تکنیک‌های قبلی کنترل همزمانی خوش‌بینانه است. روی snapshot isolation، SSI الگوریتمی برای تشخیص تعارض‌های serialization بین نوشتن‌ها و تعیین تراکنش‌هایی که باید abort شوند اضافه می‌کند.

تصمیم‌گیری بر پایهٔ فرض منسوخ

وقتی write skew را در snapshot isolation بحث کردیم (به «Write skew و phantom» در صفحه ۲۴۶ مراجعه کنید)، الگوی تکرارشونده‌ای دیدیم: تراکنش داده‌ای از پایگاه داده می‌خواند، نتیجهٔ پرس‌وجو را بررسی می‌کند و بر اساس نتیجه‌ای که دید تصمیم می‌گیرد عملی انجام دهد (نوشتن به پایگاه داده). با این حال، تحت snapshot isolation، نتیجهٔ پرس‌وجوی اصلی ممکن است تا زمان commit تراکنش دیگر به‌روز نباشد چون داده در این فاصله تغییر کرده.

به عبارت دیگر، تراکنش بر پایهٔ فرضی (واقعیتی که در ابتدای تراکنش درست بود، مثلاً «الان دو پزشک on-call هستند») عمل می‌کند. بعداً وقتی تراکنش می‌خواهد commit کند، دادهٔ اصلی ممکن است تغییر کرده باشد — فرض دیگر درست نیست.

وقتی برنامه پرس‌وجو می‌کند (مثلاً «الان چند پزشک on-call هستند؟»)، پایگاه داده نمی‌داند برنامه چگونه از نتیجه استفاده می‌کند. برای امنیت، پایگاه داده باید فرض کند هر تغییری در نتیجهٔ پرس‌وجو (فرض) یعنی نوشتن‌های آن تراکنش ممکن است نامعتبر باشند. به عبارت دیگر، ممکن است وابستگی علی بین پرس‌وجوها و نوشتن‌های تراکنش وجود داشته باشد. برای ارائهٔ isolation serializable، پایگاه داده باید موقعیت‌هایی را تشخیص دهد که تراکنش ممکن است بر فرض منسوخ عمل کرده باشد و در آن صورت تراکنش را abort کند.

پایگاه داده چگونه می‌داند نتیجهٔ پرس‌وجو ممکن است تغییر کرده باشد؟ دو حالت:

• تشخیص خواندن نسخهٔ کهنهٔ MVCC (نوشتن commit‌نشده قبل از خواندن رخ داده)
• تشخیص نوشتن‌هایی که خواندن‌های قبلی را تحت‌تأثیر می‌گذارند (نوشتن پس از خواندن رخ می‌دهد)

تشخیص خواندن‌های MVCC کهنه

یادآوری کنید snapshot isolation معمولاً با MVCC پیاده می‌شود (شکل ۷-۱۰ را ببینید). وقتی تراکنش از snapshot سازگار در پایگاه دادهٔ MVCC می‌خواند، نوشتن‌های تراکنش‌های دیگری که هنوز در زمان گرفتن snapshot commit نشده بودند را نادیده می‌گیرد. در شکل ۷-۱۰، تراکنش ۴۳ Alice را با on_call = true می‌بیند چون تراکنش ۴۲ (که وضعیت on-call Alice را تغییر داده) commit نشده. با این حال، تا زمان commit تراکنش ۴۳، تراکنش ۴۲ commit شده. یعنی نوشتنی که هنگام خواندن از snapshot سازگار نادیده گرفته شد حالا اثر کرده و فرض تراکنش ۴۳ دیگر درست نیست.

شکل ۷-۱۰. تشخیص زمانی که تراکنش مقادیر کهنه را از snapshot MVCC می‌خواند.

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

چرا تا commit صبر کنیم؟ چرا تراکنش ۴۳ را بلافاصله هنگام تشخیص خواندن کهنه abort نکنیم؟ اگر تراکنش ۴۳ فقط-خواندن بود، نیازی به abort نبود چون خطر write skew نیست. هنگام خواندن تراکنش ۴۳، پایگاه داده هنوز نمی‌داند آیا بعداً می‌نویسد. علاوه بر این، تراکنش ۴۲ ممکن است هنوز abort شود یا هنگام commit تراکنش ۴۳ commit نشده باشد، پس خواندن شاید کهنه نبوده. با اجتناب از abortهای غیرضروری، SSI پشتیبانی snapshot isolation از خواندن‌های طولانی از snapshot سازگار را حفظ می‌کند.

تشخیص نوشتن‌هایی که خواندن‌های قبلی را تحت‌تأثیر می‌گذارند

حالت دوم وقتی است که تراکنش دیگری پس از خوانده شدن داده را تغییر دهد. این حالت در شکل ۷-۱۱ نشان داده شده.

شکل ۷-۱۱. در serializable snapshot isolation، تشخیص زمانی که یک تراکنش خواندن‌های تراکنش دیگر را تغییر می‌دهد.

در زمینهٔ 2PL دربارهٔ index-range lock بحث کردیم (به «قفل‌های محدودهٔ ایندکس» در صفحه ۲۶۰ مراجعه کنید) که به پایگاه داده اجازه می‌دهد دسترسی به همهٔ سطرهای منطبق با پرس‌وجوی جستجو، مثل WHERE shift_id = 1234، را قفل کند. می‌توانیم تکنیک مشابهی اینجا به کار ببریم، اما قفل‌های SSI تراکنش‌های دیگر را مسدود نمی‌کنند.

در شکل ۷-۱۱، تراکنش‌های ۴۲ و ۴۳ هر دو پزشکان on-call در شیفت ۱۲۳۴ را جستجو می‌کنند. اگر ایندکس روی shift_id باشد، پایگاه داده می‌تواند از ورودی ایندکس ۱۲۳۴ برای ثبت اینکه تراکنش‌های ۴۲ و ۴۳ این داده را خوانده‌اند استفاده کند. (اگر ایندکس نباشد، این اطلاعات در سطح جدول ردیابی می‌شود.) این اطلاعات فقط مدتی لازم است: پس از اتمام تراکنش (commit یا abort) و اتمام همهٔ تراکنش‌های همزمان، پایگاه داده می‌تواند فراموش کند چه داده‌ای خوانده شده.

وقتی تراکنش به پایگاه داده می‌نویسد، باید در ایندکس‌ها به‌دنبال تراکنش‌های دیگری بگردد که اخیراً دادهٔ تحت‌تأثیر را خوانده‌اند. این فرایند شبیه گرفتن write lock روی بازهٔ کلید تحت‌تأثیر است، اما به‌جای مسدود کردن تا commit خوانندگان، قفل مانند سیم تله عمل می‌کند: فقط به تراکنش‌ها اطلاع می‌دهد داده‌ای که خوانده‌اند ممکن است دیگر به‌روز نباشد.

در شکل ۷-۱۱، تراکنش ۴۳ به تراکنش ۴۲ اطلاع می‌دهد خواندن قبلی‌اش منسوخ شده و بالعکس. تراکنش ۴۲ اول commit می‌شود و موفق است: اگرچه نوشتن تراکنش ۴۳ روی ۴۲ اثر گذاشته، ۴۳ هنوز commit نشده پس نوشتن هنوز اثر نکرده. با این حال، وقتی تراکنش ۴۳ می‌خواهد commit کند، نوشتن متعارض ۴۲ قبلاً commit شده، پس ۴۳ باید abort شود.

کارایی ایزولاسیون snapshot قابل‌serializable

همان‌طور که همیشه، جزئیات مهندسی زیادی بر کارایی الگوریتم در عمل اثر می‌گذارد. مثلاً یک trade-off دقت ردیابی خواندن‌ها و نوشتن‌های تراکنش‌ها است. اگر پایگاه داده فعالیت هر تراکنش را با جزئیات زیاد ردیابی کند، می‌تواند دقیقاً مشخص کند کدام تراکنش‌ها باید abort شوند، اما سربار bookkeeping قابل‌توجه می‌شود. ردیابی کمتر جزئیات سریع‌تر است اما ممکن است تراکنش‌های بیشتری از آنچه لازم است abort شوند.

در برخی موارد، خواندن اطلاعاتی که توسط تراکنش دیگر بازنویسی شده مشکلی ندارد: بسته به آنچه دیگر رخ داده، گاهی می‌توان ثابت کرد نتیجهٔ اجرا باز هم serializable است. PostgreSQL از این نظریه برای کاهش abortهای غیرضروری استفاده می‌کند [۱۱، ۴۱].

در مقایسه با 2PL، مزیت بزرگ SSI این است که یک تراکنش نیازی ندارد منتظر قفل‌های نگه‌داشته‌شده توسط تراکنش دیگر بماند. مانند snapshot isolation، نویسندگان خوانندگان را مسدود نمی‌کنند و بالعکس. این اصل طراحی latency پرس‌وجو را بسیار قابل‌پیش‌بینی‌تر و کمتر متغیر می‌کند. به‌ویژه، پرس‌وجوهای فقط-خواندن می‌توانند روی snapshot سازگار بدون قفل اجرا شوند که برای بارکاری‌های read-heavy جذاب است.

در مقایسه با اجرای ترتیبی، SSI به throughput یک هستهٔ CPU محدود نیست: FoundationDB تشخیص تعارض‌های serialization را بین چند ماشین توزیع می‌کند و به throughput بسیار بالا مقیاس می‌یابد. اگرچه داده ممکن است بین چند ماشین پارتیشن شود، تراکنش‌ها می‌توانند در چند پارتیشن بخوانند و بنویسند در حالی که isolation serializable تضمین می‌شود [۵۴].

نرخ abort به‌طور قابل‌توجهی بر کارایی کلی SSI اثر می‌گذارد. مثلاً تراکنشی که در مدت طولانی داده می‌خواند و می‌نویسد احتمالاً به تعارض برخورد کرده و abort می‌شود، پس SSI می‌خواهد تراکنش‌های read-write نسبتاً کوتاه باشند (تراکنش‌های فقط-خواندن طولانی ممکن است مشکلی نداشته باشند). با این حال، SSI احتمالاً نسبت به 2PL یا اجرای ترتیبی به تراکنش‌های کند حساس‌تر نیست.

خلاصه

تراکنش‌ها لایهٔ انتزاعی‌اند که به برنامه اجازه می‌دهند وانمود کند برخی مسائل همزمانی و برخی انواع خطاهای سخت‌افزاری و نرم‌افزاری وجود ندارند. طیف بزرگی از خطاها به abort سادهٔ تراکنش کاهش می‌یابد و برنامه فقط باید دوباره تلاش کند.

در این فصل نمونه‌های زیادی از مسائلی که تراکنش‌ها کمک می‌کنند جلوگیری شوند دیدیم. همهٔ برنامه‌ها در برابر همهٔ آن مسائل آسیب‌پذیر نیستند: برنامه با الگوی دسترسی بسیار ساده، مثل خواندن و نوشتن فقط یک رکورد، احتمالاً بدون تراکنش هم می‌تواند مدیریت کند. با این حال، برای الگوهای دسترسی پیچیده‌تر، تراکنش‌ها می‌توانند تعداد موارد خطای بالقوه‌ای که باید به آن‌ها فکر کنید را به‌شدت کاهش دهند.

بدون تراکنش، سناریوهای خطای مختلف (crash فرآیند، قطع شبکه، قطع برق، پر شدن دیسک، همزمانی غیرمنتظره و غیره) یعنی داده می‌تواند به روش‌های مختلف ناسازگار شود. مثلاً دادهٔ denormalize‌شده به‌راحتی با دادهٔ منبع ناهمگام می‌شود. بدون تراکنش، استدلال دربارهٔ اثر دسترسی‌های پیچیده و متقابل به پایگاه داده بسیار دشوار می‌شود.

در این فصل به‌ویژه عمیق در موضوع کنترل همزمانی رفتیم. چند سطح isolation پرکاربرد را بحث کردیم، به‌ویژه read committed، snapshot isolation (گاهی repeatable read نامیده می‌شود) و serializable. این سطوح را با نمونه‌های مختلف race condition مشخص کردیم:

Dirty read یک کلاینت نوشتن‌های کلاینت دیگر را قبل از commit می‌خواند. سطح read committed و سطوح قوی‌تر از dirty read جلوگیری می‌کنند.

Dirty write یک کلاینت داده‌ای را بازنویسی می‌کند که کلاینت دیگر نوشته اما هنوز commit نکرده. تقریباً همهٔ پیاده‌سازی‌های تراکنش از dirty write جلوگیری می‌کنند.

Read skew (nonrepeatable read) یک کلاینت بخش‌های مختلف پایگاه داده را در نقاط زمانی متفاوت می‌بیند. این مسئله معمولاً با snapshot isolation جلوگیری می‌شود که به تراکنش اجازه می‌دهد از snapshot سازگار در یک نقطهٔ زمانی بخواند. معمولاً با MVCC پیاده می‌شود.

Lost update دو کلاینت همزمان چرخهٔ read-modify-write انجام می‌دهند. یکی نوشتن دیگری را بدون لحاظ تغییراتش بازنویسی می‌کند و داده گم می‌شود. برخی پیاده‌سازی‌های snapshot isolation این ناهنجاری را خودکار جلوگیری می‌کنند، برخی دیگر به قفل دستی (SELECT FOR UPDATE) نیاز دارند.

Write skew تراکنش چیزی می‌خواند، بر اساس مقداری که دید تصمیم می‌گیرد و تصمیم را به پایگاه داده می‌نویسد. اما تا زمان نوشتن، فرض تصمیم دیگر درست نیست. فقط isolation serializable از این ناهنجاری جلوگیری می‌کند.

Phantom read تراکنش اشیائی را می‌خواند که شرط جستجویی را برآورده می‌کنند. کلاینت دیگر نوشتنی انجام می‌دهد که نتایج آن جستجو را تحت‌تأثیر می‌گذارد. snapshot isolation از phantomهای ساده در پرس‌وجوهای فقط-خواندن جلوگیری می‌کند، اما phantom در زمینهٔ write skew نیاز به برخورد ویژه دارد، مثل index-range lock.

سطوح isolation ضعیف از برخی این ناهنجاری‌ها محافظت می‌کنند اما بقیه را به شما، توسعه‌دهندهٔ برنامه، واگذار می‌کنند (مثلاً با قفل صریح). فقط isolation serializable از همهٔ این مسائل محافظت می‌کند. سه رویکرد مختلف برای پیاده‌سازی تراکنش‌های serializable بحث کردیم:

اجرای واقعاً ترتیبی تراکنش‌ها اگر هر تراکنش را بسیار سریع اجرا کنید و throughput تراکنش آن‌قدر پایین باشد که روی یک هستهٔ CPU پردازش شود، این گزینهٔ ساده و مؤثری است.

قفل‌گذاری دوفازی دهه‌ها استاندارد پیاده‌سازی serializability بوده، اما بسیاری از برنامه‌ها به‌خاطر ویژگی‌های کارایی از آن اجتناب می‌کنند.

ایزولاسیون snapshot قابل‌serializable (SSI) الگوریتم نسبتاً جدیدی که از بیشتر معایب رویکردهای قبلی اجتناب می‌کند. رویکرد خوش‌بینانه دارد و به تراکنش‌ها اجازه می‌دهد بدون مسدود شدن پیش بروند. وقتی تراکنش می‌خواهد commit کند بررسی می‌شود و اگر اجرا serializable نبوده abort می‌شود.

نمونه‌های این فصل از مدل دادهٔ رابطه‌ای استفاده کردند. با این حال، همان‌طور که در «نیاز به تراکنش‌های چندشیءی» در صفحه ۲۳۱ بحث شد، تراکنش‌ها ویژگی ارزشمند پایگاه داده‌اند، صرف‌نظر از مدل داده.

در این فصل ایده‌ها و الگوریتم‌ها را عمدتاً در زمینهٔ پایگاه داده‌ای که روی یک ماشین اجرا می‌شود کاوش کردیم. تراکنش‌ها در پایگاه‌های دادهٔ توزیع‌شده مجموعهٔ جدیدی از چالش‌های دشوار باز می‌کنند که در دو فصل بعد بحث می‌کنیم.

منابع

[۱] Donald D. Chamberlin, Morton M. Astrahan, Michael W. Blasgen, et al.: "A History and Evaluation of System R," Communications of the ACM, volume 24, number 10, pages 632–646, October 1981. doi:10.1145/358769.358784

[۲] Jim N. Gray, Raymond A. Lorie, Gianfranco R. Putzolu, and Irving L. Traiger: "Granularity of Locks and Degrees of Consistency in a Shared Data Base," in Modelling in Data Base Management Systems: Proceedings of the IFIP Working Conference on Modelling in Data Base Management Systems, edited by G. M. Nijssen, pages 364–394, Elsevier/North Holland Publishing, 1976. Also in Readings in Database Systems, 4th edition, edited by Joseph M. Hellerstein and Michael Stonebraker, MIT Press, 2005. ISBN: 978-0-262-69314-1

[۳] Kapali P. Eswaran, Jim N. Gray, Raymond A. Lorie, and Irving L. Traiger: "The Notions of Consistency and Predicate Locks in a Database System," Communications of the ACM, volume 19, number 11, pages 624–633, November 1976.

[۴] "ACID Transactions Are Incredibly Helpful," FoundationDB, LLC, 2013.

[۵] John D. Cook: "ACID Versus BASE for Database Transactions," johndcook.com, July 6, 2009.

[۶] Gavin Clarke: "NoSQL's CAP Theorem Busters: We Don't Drop ACID," theregister.co.uk, November 22, 2012.

[۷] Theo Härder and Andreas Reuter: "Principles of Transaction-Oriented Database Recovery," ACM Computing Surveys, volume 15, number 4, pages 287–317, December 1983. doi:10.1145/289.291

[۸] Peter Bailis, Alan Fekete, Ali Ghodsi, et al.: "HAT, not CAP: Towards Highly Available Transactions," at 14th USENIX Workshop on Hot Topics in Operating Systems (HotOS), May 2013.

[۹] Armando Fox, Steven D. Gribble, Yatin Chawathe, et al.: "Cluster-Based Scalable Network Services," at 16th ACM Symposium on Operating Systems Principles (SOSP), October 1997.

[۱۰] Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987. ISBN: 978-0-201-10715-9, available online at research.microsoft.com.

[۱۱] Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil, et al.: "Making Snapshot Isolation Serializable," ACM Transactions on Database Systems, volume 30, number 2, pages 492–528, June 2005. doi:10.1145/1071610.1071615

[۱۲] Mai Zheng, Joseph Tucek, Feng Qin, and Mark Lillibridge: "Understanding the Robustness of SSDs Under Power Fault," at 11th USENIX Conference on File and Storage Technologies (FAST), February 2013.

[۱۳] Laurie Denness: "SSDs: A Gift and a Curse," laur.ie, June 2, 2015.

[۱۴] Adam Surak: "When Solid State Drives Are Not That Solid," blog.algolia.com, June 15, 2015.

[۱۵] Thanumalayan Sankaranarayana Pillai, Vijay Chidambaram, Ramnatthan Alagappan, et al.: "All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications," at 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI), October 2014.

[۱۶] Chris Siebenmann: "Unix's File Durability Problem," utcc.utoronto.ca, April 14, 2016.

[۱۷] Lakshmi N. Bairavasundaram, Garth R. Goodson, Bianca Schroeder, et al.: "An Analysis of Data Corruption in the Storage Stack," at 6th USENIX Conference on File and Storage Technologies (FAST), February 2008.

[۱۸] Bianca Schroeder, Raghav Lagisetty, and Arif Merchant: "Flash Reliability in Production: The Expected and the Unexpected," at 14th USENIX Conference on File and Storage Technologies (FAST), February 2016.

[۱۹] Don Allison: "SSD Storage – Ignorance of Technology Is No Excuse," blog.korelogic.com, March 24, 2015.

[۲۰] Dave Scherer: "Those Are Not Transactions (Cassandra 2.0)," blog.foundationdb.com, September 6, 2013.

[۲۱] Kyle Kingsbury: "Call Me Maybe: Cassandra," aphyr.com, September 24, 2013.

[۲۲] "ACID Support in Aerospike," Aerospike, Inc., June 2014.

[۲۳] Martin Kleppmann: "Hermitage: Testing the 'I' in ACID," martin.kleppmann.com, November 25, 2014.

[۲۴] Tristan D'Agosta: "BTC Stolen from Poloniex," bitcointalk.org, March 4, 2014.

[۲۵] bitcointhief2: "How I Stole Roughly 100 BTC from an Exchange and How I Could Have Stolen More!," reddit.com, February 2, 2014.

[۲۶] Sudhir Jorwekar, Alan Fekete, Krithi Ramamritham, and S. Sudarshan: "Automating the Detection of Snapshot Isolation Anomalies," at 33rd International Conference on Very Large Data Bases (VLDB), September 2007.

[۲۷] Michael Melanson: "Transactions: The Limits of Isolation," michaelmelanson.net, March 20, 2014.

[۲۸] Hal Berenson, Philip A. Bernstein, Jim N. Gray, et al.: "A Critique of ANSI SQL Isolation Levels," at ACM International Conference on Management of Data (SIGMOD), May 1995.

[۲۹] Atul Adya: "Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions," PhD Thesis, Massachusetts Institute of Technology, March 1999.

[۳۰] Peter Bailis, Aaron Davidson, Alan Fekete, et al.: "Highly Available Transactions: Virtues and Limitations (Extended Version)," at 40th International Conference on Very Large Data Bases (VLDB), September 2014.

[۳۱] Bruce Momjian: "MVCC Unmasked," momjian.us, July 2014.

[۳۲] Annamalai Gurusami: "Repeatable Read Isolation Level in InnoDB – How Consistent Read View Works," blogs.oracle.com, January 15, 2013.

[۳۳] Nikita Prokopov: "Unofficial Guide to Datomic Internals," tonsky.me, May 6, 2014.

[۳۴] Baron Schwartz: "Immutability, MVCC, and Garbage Collection," xaprb.com, December 28, 2013.

[۳۵] J. Chris Anderson, Jan Lehnardt, and Noah Slater: CouchDB: The Definitive Guide. O'Reilly Media, 2010. ISBN: 978-0-596-15589-6

[۳۶] Rikdeb Mukherjee: "Isolation in DB2 (Repeatable Read, Read Stability, Cursor Stability, Uncommitted Read) with Examples," mframes.blogspot.co.uk, July 4, 2013.

[۳۷] Steve Hilker: "Cursor Stability (CS) – IBM DB2 Community," toadworld.com, March 14, 2013.

[۳۸] Nate Wiger: "An Atomic Rant," nateware.com, February 18, 2010.

[۳۹] Joel Jacobson: "Riak 2.0: Data Types," blog.joeljacobson.com, March 23, 2014.

[۴۰] Michael J. Cahill, Uwe Röhm, and Alan Fekete: "Serializable Isolation for Snapshot Databases," at ACM International Conference on Management of Data (SIGMOD), June 2008. doi:10.1145/1376616.1376690

[۴۱] Dan R. K. Ports and Kevin Grittner: "Serializable Snapshot Isolation in PostgreSQL," at 38th International Conference on Very Large Databases (VLDB), August 2012.

[۴۲] Tony Andrews: "Enforcing Complex Constraints in Oracle," tonyandrews.blogspot.co.uk, October 15, 2004.

[۴۳] Douglas B. Terry, Marvin M. Theimer, Karin Petersen, et al.: "Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System," at 15th ACM Symposium on Operating Systems Principles (SOSP), December 1995. doi:10.1145/224056.224070

[۴۴] Gary Fredericks: "Postgres Serializability Bug," github.com, September 2015.

[۴۵] Michael Stonebraker, Samuel Madden, Daniel J. Abadi, et al.: "The End of an Architectural Era (It's Time for a Complete Rewrite)," at 33rd International Conference on Very Large Data Bases (VLDB), September 2007.

[۴۶] John Hugg: "H-Store/VoltDB Architecture vs. CEP Systems and Newer Streaming Architectures," at Data @Scale Boston, November 2014.

[۴۷] Robert Kallman, Hideaki Kimura, Jonathan Natkins, et al.: "H-Store: A High-Performance, Distributed Main Memory Transaction Processing System," Proceedings of the VLDB Endowment, volume 1, number 2, pages 1496–1499, August 2008.

[۴۸] Rich Hickey: "The Architecture of Datomic," infoq.com, November 2, 2012.

[۴۹] John Hugg: "Debunking Myths About the VoltDB In-Memory Database," voltdb.com, May 12, 2014.

[۵۰] Joseph M. Hellerstein, Michael Stonebraker, and James Hamilton: "Architecture of a Database System," Foundations and Trends in Databases, volume 1, number 2, pages 141–259, November 2007. doi:10.1561/1900000002

[۵۱] Michael J. Cahill: "Serializable Isolation for Snapshot Databases," PhD Thesis, University of Sydney, July 2009.

[۵۲] D. Z. Badal: "Correctness of Concurrency Control and Implications in Distributed Databases," at 3rd International IEEE Computer Software and Applications Conference (COMPSAC), November 1979.

[۵۳] Rakesh Agrawal, Michael J. Carey, and Miron Livny: "Concurrency Control Performance Modeling: Alternatives and Implications," ACM Transactions on Database Systems (TODS), volume 12, number 4, pages 609–654, December 1987. doi:10.1145/32204.32220

[۵۴] Dave Rosenthal: "Databases at 14.4MHz," blog.foundationdb.com, December 10, 2014.