Leader Election pattern.md

‏Leader Election pattern

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

 

زمینه و مشکل

  یک cloud application معمولی وظایف زیادی دارد که به‌صورت هماهنگ عمل می‌کنند. این وظایف همگی می‌توانند نمونه‌هایی باشند که کد یکسانی را اجرا می‌کنند و نیاز به دسترسی به منابع یکسانی دارند یا ممکن است به طور موازی با همکار کنند تا بخش‌های جداگانه یک محاسبه پیچیده را انجام دهند.

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

 

مثلاً:

  -‏ در یک سیستم مبتنی برابری که مقیاس‌دهی افقی یا horizontal scaling را پیاده‌سازی می‌کند، چندین نمونه از یک تسک می‌توانند هم‌زمان با هر نمونه سرویسی با کاربرهای متفاوتی اجرا شوند. اگر این نمونه‌ها در یک منبع مشترک ذخیره‌سازی و نوشته می‌شوند پس لازم است اقدامات آنها هماهنگ‌سازی شود تا از بازنویسی یا ذخیره مجدد تغییرات ایجاد شده توسط سایر نمونه‌ها جلوگیری شود.

    -‏ اگر تسک‌های یکی از عناصر منفرد که محاسبات پیچیده را به‌صورت موازی انجام می‌دهند در این سیستم وجود داشته باشد آنگاه باید نتیجه‌ها پس از تکمیل‌شدن نتیجه همه موارد، تجمیع (aggregate) شوند.

  همین‌طور نمونه‌های هر تسک منحصربه‌فرد هستند، بنابراین یک رهبر وجود ندارد که بتواند به‌عنوان هماهنگ‌کننده (coordinator) یا جمع‌کننده (aggregator) عمل کند.

 

راه‌حل:

  فقط یک نمونه تسک باید انتخاب شود تا به‌عنوان رهبر عمل کند و این نمونه باید اقدامات سایر موارد زیرمجموعه را هماهنگ‌سازی کند. اگر همه تسک‌ها که یک کد را اجرا کنند بتوانند به‌عنوان رهبر عمل کنند؛ بنابراین، فرایند انتخابات (election) باید بادقت مدیریت شود تا از تصاحب هم‌زمان دو یا چند تسک به‌عنوان leader یا رهبر جلوگیری شود.

  سیستم باید مکانیزمی قوی برای انتخاب leader فراهم کند. این روش باید با رویدادهایی مانند قطع شبکه یا خرابی‌های در حین پردازش داده‌ها مقابله کند. در بسیاری از راه‌حل‌ها، نمونه تسک‌های وابسته می‌توانند leader را از طریق نوعی تکنیک heartbeat یا polling نظارت یا مانیتور کنند. اگر leader تعیین‌شده به طور غیرمنتظره‌ای خاتمه یابد یا خرابی شبکه رخ دهد آن‌گاه leader را برای نمونه تسک‌های وابسته از دسترس خارج می‌کند پس در نهایت لازم است که leader جدیدی انتخاب کنند.

  چندین راهبُرد برای انتخاب یک leader از میان مجموعه‌ای از وظایف در یک محیط توزیع شده وجود دارد، از جمله:

  -‏ انتخاب نمونه تسک (task instance) با کمترین instance rank یا process ID.

  -‏ مسابقه برای به‌دست‌آوردن یک mutex مشترک و توزیع شده. اولین نمونه وظیفه‌ای که mutex را به دست می‌آورد leader است. بااین‌حال، سیستم باید اطمینان حاصل کند که در صورت پایان یا قطع ارتباط leader با بقیه سیستم، mutex آزاد می‌شود تا به نمونه تسک دیگری اجازه دهد تا leader یا رهبر شود.

  -‏ پیاده‌سازی یکی از الگوریتم‌های رایج انتخاب رهبر مانند Bully Algorithm یا Ring Algorithm. این الگوریتم‌ها فرض می‌کنند که هر نامزد در انتخابات یک شناسه منحصربه‌فرد(unique ID) دارد و می‌تواند به طور قابل‌اعتماد با سایر نامزدها ارتباط برقرار کند.

 

مسائل و ملاحظات:

  هنگام تصمیم‌گیری در مورد نحوه اجرای این الگو به نکات زیر توجه کنید:

  -‏ فرایند انتخاب leader باید در برابر شکست‌های گذرا و مداوم، مقاوم باشد.

  -‏ تشخیص اینکه چه زمانی leader دچار خرابی شده است یا غیرقابل‌دسترسی شده (مثلاً به دلیل نقص ارتباطات) باید امکان‌پذیر باشد. سرعت تشخیص موردنیاز در این مورد به سیستم بستگی دارد. برخی از سیستم‌ها ممکن است بتوانند برای مدت کوتاهی بدون leader کار کنند که در طی آن ممکن است یک خطای گذرا برطرف شود. در موارد دیگر، ممکن است لازم باشد فوراً leader failure را تشخیص داده و یک انتخابات (election) جدید راه‌اندازی شود.

  -‏ در سیستمی که horizontal autoscaling را پیاده‌سازی می‌کند، اگر سیستم کوچک(scales back) شود و برخی از منابع محاسباتی را خاموش کند، leader می‌تواند terminated شود.

  -‏ استفاده از یک mutex مشترک و توزیع شده یک وابستگی به سرویس خارجی ارائه‌دهنده mutex ایجاد می‌کند. سرویس یک نقطه شکست واحد را تشکیل می‌دهد. اگر به هر دلیلی از دسترس خارج شود، سیستم قادر به انتخاب leader نخواهد بود.

  -‏ استفاده از یک فرایند اختصاصی واحد (single dedicated process) به‌عنوان leader یک رویکرد خیلی ساده بوده و بااین‌حال اگر process دچار خرابی شود، ممکن است تأخیر قابل‌توجهی در هنگام راه‌اندازی مجدد آن وجود داشته باشد. latency یا تأخیر حاصل می‌تواند بر کارایی و افزایش زمان پاسخ سایر فرایندها تأثیر بگذارد به‌خصوص اگر آنها منتظر leader برای هماهنگ‌سازی عملیات باشند.

  -‏ پیاده‌سازی یکی از leader election algorithmها به‌صورت دستی، بیشترین انعطاف‌پذیری را برای تنظیم و بهینه‌سازی کد فراهم می‌کند.

  چه زمانی از این الگو استفاده کنیم؟

  از این الگو زمانی استفاده کنید که تسک‌ها در یک اپلیکیشن توزیع شده، مانند راه‌حل cloud-hosted، نیاز به هماهنگی دقیق دارند و هیچ leader دقیقی وجود ندارد.

 

از تبدیل‌شدن leader به گلوگاه(bottleneck) در سیستم اجتناب کنید. هدف leader هماهنگ‌کردن subordinate task هاست و لزوماً لازم نیست که خود در این کار شرکت کند - اگرچه اگر task به‌عنوان leader انتخاب نشود باید بتواند این کار را انجام دهد.

  چه زمانی نباید از این الگو استفاده کنیم؟

  -‏ یک leader یا process اختصاصی وجود دارد که همیشه می‌تواند به‌عنوان leader عمل کند. برای مثال، ممکن است بتوان یک singleton process را پیاده‌سازی کرد که نمونه تسک‌ها را هماهنگ می‌کند. اگر این process به‌نوعی fail یا unhealthy شود، سیستم می‌تواند آن را خاموش کرده و دوباره راه‌اندازی کند.

  -‏ هماهنگی بین تسک‌ها را می‌توان با استفاده از روشی سبک‌تر به دست آورد. به‌عنوان‌مثال، اگر چندین نمونه تسک به‌سادگی نیاز به دسترسی هماهنگ به یک منبع اشتراکی یا shared resource دارند پس راه‌حل بهتر استفاده از optimistic or pessimistic locking برای کنترل دسترسی است.

  -‏ معمولاً راه‌حل‌های third-party مناسب‌تر است. به‌عنوان‌مثال، سرویس Microsoft Azure HDInsight (بر اساس Apache Hadoop) از سرویس ارائه شده توسط Apache Zookeeper برای هماهنگ‌کردن نگاشتی (coordinate the map) و کاهش تسک‌ها که باعث جمع‌آوری و خلاصه‌کردن داده‌ها می‌شود، استفاده می‌کند.

 

مثال:

  پروژه DistributedMutex در راه‌حل LeaderElection (نمونه‌ای که نشان می‌دهد این الگو در GitHub موجود است) نشان می‌دهد که چگونه می‌توان با استفاده از یک Azure Storage blob برای ارائه مکانیزمی برای اجرای یک mutex مشترک و توزیع‌شده استفاده کرد. این mutex می‌تواند برای انتخاب یک leader در میان گروهی از role instanceها در Azure cloud service استفاده شود. اولین role instance که lease را به دست می‌آورد، به‌عنوان leader انتخاب می‌شود و تا زمانی که lease را آزاد نکند یا نتواند مجوز را تمدید کند، leader باقی می‌ماند. درصورتی‌که leader دیگر در دسترس نباشد، سایر role instanceها می‌توانند به monitor کردن blob lease ادامه دهند.

 

 

یک blob lease یک قفل نوشتن انحصاری روی یک blob است. یک blob می‌تواند تنها موضوع یک lease در هر نقطه از زمان باشد. یک role instance می‌تواند یک lease را روی یک blob مشخص درخواست کند، و اگر هیچ role instance دیگری lease را روی همان blob lease نداشته باشد، به آن lease داده می‌شود. در غیر این صورت درخواست یک استثنا ایجاد می‌کند.

 

برای جلوگیری از یک role instance معیوب که lease را به طور نامحدود حفظ می‌کند، محدودیت مادام‌العمر را برای lease تعیین کنید. وقتی این مدت منقضی شد، lease در دسترس می‌شود. بااین‌حال، درحالی‌که یک role instance یک lease را نگه می‌دارد، می‌تواند درخواست تمدید lease را داشته باشد و lease برای مدت‌زمان بیشتری به آن اعطا می‌شود. اگر role instance بخواهد lease را حفظ کند، می‌تواند به طور مداوم این فرایند را تکرار کند. برای اطلاعات بیشتر در مورد نحوه lease a blob مقاله؛ Lease Blob (REST API) را ببینید.

  کلاس BlobDistributedMutex در مثال سی‌شارپ زیر حاوی متد RunTaskWhenMutexAcquired است که یک role instance را قادر می‌سازد تا توافق‌نامه را روی یک blob مشخص به دست آورد. هنگامی که شیء BlobDistributedMutex ایجاد می‌شود، جزئیات blob (نام، container و حساب ذخیره‌سازی) به سازنده در یک شی BlobSettings منتقل می‌شود (این شی یک ساختار ساده است که در کد نمونه گنجانده شده است). سازنده همچنین Task را می‌پذیرد که به کدی ارجاع می‌دهد که role instance باید اجرا کند درصورتی‌که توافق‌نامه را با موفقیت در blob به دست آورد و leader انتخاب شده است. توجه داشته باشید که کدی که جزئیات سطح پایین کسب توافق‌نامه را مدیریت می‌کند در یک کلاس کمکی جداگانه به نام BlobLeaseManager پیاده‌سازی شده است.

 

public class BlobDistributedMutex

{

...

private readonly BlobSettings blobSettings;

private readonly Func<CancellationToken, Task> taskToRunWhenLeaseAcquired;

...

  

public BlobDistributedMutex(BlobSettings blobSettings,

Func<CancellationToken, Task> taskToRunWhenLeaseAcquired)

{

this.blobSettings = blobSettings;

this.taskToRunWhenLeaseAcquired = taskToRunWhenLeaseAcquired;

}

  

public async Task RunTaskWhenMutexAcquired(CancellationToken token)

{

var leaseManager = new BlobLeaseManager(blobSettings);

await this.RunTaskWhenBlobLeaseAcquired(leaseManager, token);

}

متد RunTaskWhenMutexAcquired در نمونه کد بالا روش RunTaskWhenBlobLeaseAcquired را که در نمونه کد زیر نشان‌داده‌شده است فراخوانی می‌کند تا در واقع توافق‌نامه را به دست آورد. متد RunTaskWhenBlobLeaseAcquired به‌صورت ناهم‌زمان اجرا می‌شود. اگر توافق با موفقیت به دست آید، role instance به‌عنوان leader انتخاب شده است. هدف از taskToRunWhenLeaseAcquired نماینده انجام کاری است که سایر role instance را هماهنگ می‌کند. اگر توافق‌نامه تملک نشود، role instance دیگری به‌عنوان رهبر انتخاب شده است و role instance فعلی تابع باقی می‌ماند. توجه داشته باشید که روش TryAcquireLeaseOrWait یک روش کمکی است که از شی BlobLeaseManager برای به‌دست‌آوردن توافق‌نامه استفاده می‌کند.

private async Task RunTaskWhenBlobLeaseAcquired(
    BlobLeaseManager leaseManager, CancellationToken token)
  {
    while (!token.IsCancellationRequested)
    {
      // Try to acquire the blob lease.
      // Otherwise wait for a short time before trying again.
      string leaseId = await this.TryAcquireLeaseOrWait(leaseManager, token);

      if (!string.IsNullOrEmpty(leaseId))
      {
        // Create a new linked cancellation token source so that if either the
        // original token is canceled or the lease can't be renewed, the
        // leader task can be canceled.
        using (var leaseCts =
          CancellationTokenSource.CreateLinkedTokenSource(new[] { token }))
        {
          // Run the leader task.
          var leaderTask = this.taskToRunWhenLeaseAcquired.Invoke(leaseCts.Token);
          ...
        }
      }
    }
    ...
  }

یک task آغاز شده توسط leader نیز به‌صورت ناهم‌زمان اجرا می‌شود. درحالی‌که این کار در حال اجرا است، متد RunTaskWhenBlobLeaseAcquired نشان‌داده‌شده در نمونه کد زیر به‌صورت دوره‌ای سعی می‌کند توافق‌نامه را تمدید کند. این کمک می‌کند تا اطمینان حاصل شود که role instance به‌عنوان leader باقی می‌ماند. در راه‌حل نمونه، تأخیر بین درخواست‌های تمدید کمتر از زمان مشخص شده برای مدت توافق‌نامه است تا از انتخاب role instance دیگری به‌عنوان توافق‌نامه جلوگیری شود. اگر تمدید به هر دلیلی ناموفق باشد، کار لغو می‌شود.

  اگر توافق‌نامه تمدید نشد یا کار لغو شد (احتمالاً در نتیجه خاموش‌شدن role instance ، توافق‌نامه آزاد می‌شود. در این مرحله، این یا role instance دیگری ممکن است به‌عنوان leader انتخاب شود. استخراج کد زیر این بخش از فرایند را نشان می‌دهد.

private async Task RunTaskWhenBlobLeaseAcquired(
    BlobLeaseManager leaseManager, CancellationToken token)
  {
    while (...)
    {
      ...
      if (...)
      {
        ...
        using (var leaseCts = ...)
        {
          ...
          // Keep renewing the lease in regular intervals.
          // If the lease can't be renewed, then the task completes.
          var renewLeaseTask =
            this.KeepRenewingLease(leaseManager, leaseId, leaseCts.Token);

          // When any task completes (either the leader task itself or when it
          // couldn't renew the lease) then cancel the other task.
          await CancelAllWhenAnyCompletes(leaderTask, renewLeaseTask, leaseCts);
        }
      }
    }
  }
  ...
}

متد KeepRenewingLease یکی دیگر از روش‌های کمکی است که از شی BlobLeaseManager برای تمدید lease استفاده می‌کند. متد CancelAllWhenAnyCompletes وظایف مشخص شده به‌عنوان دو پارامتر اول را لغو می‌کند. نمودار زیر استفاده از کلاس BlobDistributedMutex را برای انتخاب leader و اجرای task ای که عملیات را هماهنگ می‌کند، نشان می‌دهد.

 

    مثال کد زیر نحوه استفاده از کلاس BlobDistributedMutex را در نقش worker نشان می‌دهد. این کد بر روی bolb به نام MyLeaderCoordinatorTask در lease's container در development storage، مجوز می‌گیرد و مشخص می‌کند که اگر role instance به‌عنوان leader انتخاب شود، کد تعریف‌شده در متد MyLeaderCoordinatorTask باید اجرا شود.

var settings = new BlobSettings(CloudStorageAccount.DevelopmentStorageAccount,
  "leases", "MyLeaderCoordinatorTask");
var cts = new CancellationTokenSource();
var mutex = new BlobDistributedMutex(settings, MyLeaderCoordinatorTask);
mutex.RunTaskWhenMutexAcquired(this.cts.Token);
...

// Method that runs if the role instance is elected the leader
private static async Task MyLeaderCoordinatorTask(CancellationToken token)
{
  ...
}

در مورد کد نمونه بالا به نکات زیر توجه کنید:

    -‏ یک blob یک نقطه به‌شدت محتمل خرابی است. اگر سرویس blob در دسترس نباشد، یا غیرقابل‌دسترسی باشد، leader نمی‌تواند توافق‌نامه را تمدید کند و هیچ role instance دیگری نمی‌تواند توافق‌نامه را به دست آورد. در این صورت، هیچ role instance نمی‌تواند به‌عنوان leader عمل کند. بااین‌حال، سرویس blob به‌گونه‌ای طراحی شده است که انعطاف‌پذیر باشد، بنابراین شکست کامل سرویس blob بسیار بعید در نظر گرفته می‌شود.

  -‏ اگر تسکی که توسط leader انجام می‌شود متوقف شود، leader ممکن است به تمدید توافق‌نامه ادامه دهد و از گرفتن توافق‌نامه و به‌عهده‌گرفتن نقش leader به‌منظور هماهنگ‌کردن تسک‌ها جلوگیری کند. در دنیای واقعی، درست کارکردن leader باید در فواصل زمانی مکرر بررسی شود.

  -‏ روند انتخابات(election) غیرقطعی است. شما نمی‌توانید هیچ فرضی در مورد اینکه کدام role instance در نهایت توافق‌نامه blob را به دست می‌آورد و leader می‌شود را ندارید.

  -‏ همیشه blob مورداستفاده به‌عنوان هدف توافق‌نامه blob نباید برای هیچ هدف دیگری استفاده شود. اگر یک role instance تلاش کند داده‌ها را در این blob ذخیره کند پس این داده‌ها قابل‌دسترسی نخواهند بود مگر اینکه role instance یک leader باشد و blob lease را نگه دارد.

   

مراحل بعدی:

  راهنمایی زیر ممکن است هنگام اجرای این الگو نیز مرتبط باشد:

  -‏ این الگو دارای نمونه کاربردی قابل دانلود است.

  -‏ راهنمای Autoscaling Guidance. با تغییر load روی برنامه، می‌توان نمونه‌های task host را شروع و متوقف کرد. Autoscaling می‌تواند به حفظ توان و عملکرد در زمان اوج پردازش کمک کند.

  -‏ راهنمای پارتیشن‌بندی(Compute Partitioning Guidance را محاسبه کنید. این راهنما نحوه allocate task به hostها در یک سرویس وب گونه‌ای که به‌حداقل‌رساندن هزینه‌های جاری و حفظ scalability، performance، در availability و امنیت سرویس کمک می‌کند.

  -‏ الگوی Task-based Asynchronous pattern.

  -‏ مثالی که Bully Algorithm را نشان می‌دهد.

  -‏ مثالی که Ring Algorithm را نشان می‌دهد.

  -‏ استفاده از Apache Curator یک کتابخانه client برای Apache ZooKeeper.

  -‏ مقاله Lease Blob (REST API) در MSDN.