تحمل پذیری خرابی در سیستم های توزیع شده با استفاده از ساختمان داده های هم جوشی

 

Fault Tolerance in Distributed Systems Using Fused Data Structures

Abstract

Replication is the prevalent solution to tolerate faults in large data structures hosted on distributed servers. To tolerate f crash faults (dead/unresponsive data structures) among n distinct data structures, replication requires f þ 1 replicas of each data structure, resulting in nf additional backups. We present a solution, referred to as fusion that uses a combination of erasure codes and selective replication to tolerate f crash faults using just f additional fused backups. We show that our solution achieves OðnÞ savings in space over replication. Further, we present a solution to tolerate f Byzantine faults (malicious data structures), that requires only nf þ f backups as compared to the 2nf backups required by replication. We explore the theory of fused backups and provide a library of such backups for all the data structures in the Java Collection Framework. The theoretical and experimental evaluation confirms that the fused backups are space-efficient as compared to replication, while they cause very little overhead for normal operation. To illustrate the practical usefulness of fusion, we use fused backups for reliability in Amazon’s highly available key-value store, Dynamo. While the current replication-based solution uses 300 backup structures, we present a solution that only requires 120 backup structures. This results in savings in space as well as other resources such as power.

 

دانلود رایگان مقاله انگلیسی                 1.89 MB

 

چکیده
تکرار راه حل رایجی برای تحمل خرابی ها در ساختمان داده های بزرگ به میزبانی سرورهای توزیع شده است. برای تحمل f خرابی فروپاشی (ساختمان داده های مرده/بی مسئولیت) میان n ساختمان داده متمایز، تکرار نیاز به f+1 کپی از هر ساختمان داده دارد که منجر به nf پشتیبان اضافی می شود. راه حلی را ارائه می کنیم که هم جوشی نامیده می شود و از ترکیب کدهای پاک شدگی و تکرار انتخابی برای تحمل f خرابی فروپاشی با استفاده از تنها f پشتیبان هم جوشی (فیوز) اضافی استفاده می کند. نشان می دهیم که راه حل ما بهO(n) صرفه جویی در فضا روی تکرار دست می یابد. بعلاوه، راه حلی برای تحمل f خرابی بیزانسی ارائه می کنیک که نیاز به تنها nf+f پشتیبان در مقایسه با 2nf پشتیبان مورد نیاز برای تکرار دارد. به کاوش نظریه پشتیبان های هم جوشی پرداخته و کتابخانه ای از چنین پشتیبان ها برای تمام ساختمان داده های موجود در چارچوب جمع آوری جاوا ارائه می کنیم. ارزیابی نظری و تجربی تایید می کند که پشتیبان های هم جوشی در مقایسه با تکرار، موثر در فضا می باشند، در حالیکه منجر به سربار خیلی کم برای عملیات نرمال می شوند. برای نمایش سودمندی عملی هم جوشی، از پشتیبان های هم جوشی برای قابلیت اطمینان در فروشگاه با ارزش کلیدی با قابلیت دستیابی بالای آمازون به نام Dynamo استفاده می کنیم. در حالیکه راه حل مبتنی بر تکرار کنونی از 200 ساختار پشتیبان استفاده می کند، راه حلی ارائه می کنیم که تنها به 120 ساختار پشتیبان نیاز دارد. که منجر به صرفه جویی هایی در فضا همانند سایر منابع مانند توان می شود.
کلمات کلیدی: سیستم های توزیع شده، تحمل پذیری خرابی، ساختمان داده ها.

 

تعداد صفحات مقاله انگلیسی: 15 صفحه
تعداد صفحات مقاله فارسی: 50 صفحه

اضافه کردن نظر