Abstract

Most existing parallel database systems achieve fault tolerance by aborting unfinished queries upon a failure and restart the entire from the beginning. This is inefficient for long running queries of OLAP workloads. To solve this problem, this paper presents a selective checkpointing mechanism which materializes the outputs of some necessary operators, enabling to resume queries from middle of the execution upon failures. Each query is represented by a DAG of relational operators in which data are typically pipelined between operators. The goal of the mechanism is to find a set of operators whose outputs are worth being checkpointed to minimize the expected runtime of the whole query. It firstly provides a cost model to estimate the expected runtime of a whole query plan under a given failure probability for each operator. Then a divide-andconquer algorithm is proposed to find a close-to-optimal solution to the problem. The algorithm divides the query plan into subplans with smaller search spaces. For a given query plan with n operators, the algorithm runs in O(n) time. The mechanism is implemented in a shared-nothing parallel database system called ParaLite which provides a coordination layer to glue many SQLite instances together, and parallelizes SQL queries across them. The experimental results indicate that different fault-tolerant strategies affect the overall runtimes of queries. Our selective checkpointing mechanism can choose reasonable operators to be checkpointed and outperforms other faulttolerant strategies. In addition, the divide-and-conquer algorithm taken by our mechanism has a smaller overhead than brute-force approach while keeping a similar effectiveness

چکیده

اکثر سیستم‌های پایگاه داده موازی در هنگام شکست پرس وجوهای تمام نشده را رها کرده و همه را از ابتدا شروع می‌کنند. این امر تحمل خطا را ممکن می‌سازد، ولی برای اجرای طولانی پرس وجوهای بارهای کاری OLAP ناکارآمد است. برای حل این مسئله، این مقاله، مکانیسم نقطه وارسی انتخابی ارائه می‌کند که خروجی‌های برخی عملگرهای موردنیاز را خودکار ساخته و در صورت شکست، ادامه دادن پرس وجو را از اواسط اجرا ممکن می‌سازد. هرپرس وجو با DAG عملگرهای رابطه ای نمایش داده می‌شود که در آن، معمولا داده‌ها بین عملگرها خط لوله می‌شوند. هدف این مکانیسم یافتن مجموعه عملگرهایی است که خروجی آن‌ها ارزش نقطه وارسی شدن دارند تا زمان اجرای مورد انتظار کل پرس وجو حداقل شود. در ابتدا، مدل هزینه برای تخمین زمان اجرای مورد انتظار کل طرح پرس وجو تحت احتمال شکست برای هرعملگر معرفی می‌شود. سپس الگوریتم تقسیم و غلبه ای پیشنهاد می‌شود تا راه حل نزدیک به بهینه ای برای مسئله پیدا کند. این الگوریتم طرح پرس وجو را به زیرطرح‌هایی با فضای جستجوی کوچکتر تقسیم می‌کند. برای طرج پرس وجویی با n عملگر، الگوریتم دارای پیچیدگی زمانی O(n) است. این مکانیسم در سیستم پایگاه داده موازی بدون اشتراکی با نام ParaLite پیاده سازی می‌شود که برای به هم چسباندن نمونه‌های SQLite زیادی و موازی سازی پرس وجوهای SQL در آن‌ها، یک لایه هماهنگ سازی فراهم می‌کند. نتایج آزمایشات نشان می‌دهد که استراتژی‌های تحمل خطای مختلف زمان اجرای کلی پرس وجوها را تحت تاثیر قرار می‌دهد. مکانیسم نقطه وارسی انتخابی ما می‌تواند عملگرها را منطقی انتخاب کند تا نقطه وارسی شده و کارآیی بیشتری نسبت به استراتژی‌های تحمل خطای دیگر نشان دهد. به علاوه، الگوریتم تقسیم و غلبه مورد استفاده مکانیسم سربار کمتری نسبت به روش brute-force داشته و در عین حال کارآیی مشابهی نشان می‌دهد.

1-مقدمه

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