نمایش مبدأ برای حد نصاب (در سیستم‌های توزیع شده)

'''حد نصاب''' حداقل تعداد آرایی است که یک عملیات در سیستم توزیع شده باید کسب کند تا به  تایید برسد. یک تکنیک مبتنی بر حد نصاب برای اجرای عملیات سازگار در یک سیستم توزیع شده پیاده سازی می شود.

== تکنیک حد نصاب در پایگاه‌داده‌های توزیع شده ==
رأی‌گیری مبتنی بر نصاب به عنوان یک روش کنترل تکرار {{به انگلیسی|Replica Control}} استفاده شود، و همچنین به عنوان روشی برای تعهد به منظور اطمینان از اتمی بودن تراکنش‌ها در شبکه تقسیم شده به کار می‌رود.<ref name="ozsu2">{{cite book|last1=Ozsu|first1=Tamer M|last2=Valduriez|first2=Patrick|title=Principles of distributed database systems|edition=2nd|isbn=978-0-13-691643-7|year=1991|publisher=Prentice-Hall, Inc.|location=Upper Saddle River, NJ|chapter=12}}</ref>

=== رأی‌گیری مبتنی بر نصاب در پروتکل‌های تعهد ===
در یک سیستم پایگاه داده توزیع‌شده، یک تراکنش ممکن است عملیات خود را در چندین سایت اجرا کند. از آنجا که ویژگی اتمی بودن نیاز دارد که هر تراکنش توزیع‌شده به صورت اتمی انجام شود، تراکنش باید در تمام سایت‌ها سرنوشت یکسانی (تأیید یا لغو) داشته باشد. در صورت بروز تقسیم شبکه، سایت‌ها به بخش‌هایی تقسیم می‌شوند که ممکن است نتوانند با یکدیگر ارتباط برقرار کنند. اینجاست که یک تکنیک مبتنی بر نصاب وارد عمل می‌شود. ایده اصلی این است که یک تراکنش زمانی اجرا می‌شود که اکثریت سایت‌ها به اجرای آن رأی دهند.

به هر سایت در سیستم یک رأی Vi اختصاص داده می‌شود. فرض کنیم که مجموع تعداد کل رأی‌ها در سیستم V باشد و نصاب‌های لغو و تأیید به ترتیب Va و Vc باشند. سپس قوانین زیر در پیاده‌سازی پروتکل تعهد باید رعایت شوند:

# V<sub>a</sub> + V<sub>c</sub> > V, where 0 < V<sub>c</sub>, V<sub>a</sub> <math>\le</math> V.
# پیش از تأیید یک تراکنش، باید نصاب تأیید Vc کسب شود.  مجموع حداقل یک سایت که آماده تأیید است و صفر یا بیشتر سایت‌های منتظر باید  بزرگتر مساوی V<sub>c</sub> باشد.<ref>{{cite web|last=Skeen|first=Dale|title=A Quorum-based Commit Protocol|url=https://ecommons.cornell.edu/bitstream/handle/1813/6323/82-483.pdf?sequence=1|publisher=Cornell University ECommons Library|access-date=10 February 2013}}</ref>
# پیش از لغو یک تراکنش، باید نصاب لغو Va کسب شود. مجموع صفر یا بیشتر سایت‌هایی که آماده لغو هستند یا هر سایت منتظر باید بزرگتر مساوی Va باشد.

قانون اول تضمین می‌کند که یک تراکنش نمی‌تواند به طور همزمان تأیید و لغو شود. دو قانون بعدی نشان می‌دهند که چه تعداد رأی باید برای خاتمه دادن به تراکنش در یکی از این دو حالت کسب شود.

=== رأی‌گیری مبتنی بر نصاب برای کنترل تکرار ===
در پایگاه‌های داده تکرارشده، یک شیء داده دارای نسخه‌هایی در چندین سایت است. برای اطمینان از ترتیب‌پذیری، نباید به دو تراکنش اجازه داده شود که به طور همزمان یک آیتم داده را بخوانند یا بنویسند. در مورد پایگاه‌های داده تکرارشده، می‌توان از یک پروتکل کنترل تکرار مبتنی بر نصاب استفاده کرد تا اطمینان حاصل شود که هیچ دو نسخه از یک آیتم داده به طور همزمان توسط دو تراکنش خوانده یا نوشته نمی‌شوند.

رأی‌گیری مبتنی بر نصاب برای کنترل تکرار، ایده‌ای است که توسط '''گیفورد<ref>{{Cite conference|first=David K.|last=Gifford|title=Weighted voting for replicated data|conference=SOSP '79: Proceedings of the seventh ACM symposium on Operating systems principles|year=1979|pages=150–162|place=Pacific Grove, California, United States|publisher=ACM|doi=10.1145/800215.806583|citeseerx=10.1.1.12.6256}}</ref>''' در سال 1979 ارائه شد. به هر نسخه از یک آیتم داده تکرارشده یک رأی اختصاص داده می‌شود. هر عملیات باید برای خواندن یا نوشتن یک آیتم داده، به ترتیب، نصاب خواندن (Vr) یا نصاب نوشتن (Vw) را کسب کند. اگر یک آیتم داده تعداد کل V رأی داشته باشد، نصاب‌ها باید از قوانین زیر تبعیت کنند:

# V<sub>r</sub> + V<sub>w</sub> > V
# V<sub>w</sub> > V/2

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

== منابع ==
{{پانویس}}