بررسی عمیق Consistent Hashing برای مصاحبه‌های طراحی سیستم

Consistent Hashing

در این فصل می‌بینیم Consistent Hashing چه مشکلی را حل می‌کند، چطور کار می‌کند و چطور می‌توانید در مصاحبه از آن استفاده کنید.

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

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

فهم Consistent Hashing با یک مثال

بیایید با یک مثال انگیزشی شهود خودمان را بسازیم.

فرض کنید سیستم فروش بلیت مثل TicketMaster طراحی می‌کنید. در ابتدا سیستم ساده است.

• یک پایگاه داده که همه داده‌های رویدادها را ذخیره می‌کند.
• کلاینت‌هایی که برای گرفتن اطلاعات رویداد درخواست می‌دهند.

اول همه‌چیز روان کار می‌کند. اما موفقیت چالش‌هایی هم می‌آورد. وقتی پلتفرم محبوب می‌شود و رویدادهای بیشتری میزبانی می‌کند، یک پایگاه داده دیگر نمی‌تواند بار را تحمل کند. باید داده‌ها را بین چند پایگاه داده توزیع کنید. این فرایند Sharding (افراز داده‌ها) نام دارد.

سوالی که باید جواب بدهیم این است: چطور بفهمیم کدام رویدادها را روی کدام نمونه پایگاه داده ذخیره کنیم؟

تلاش اول، Modulo Hashing ساده

ساده‌ترین راه برای توزیع داده بین چند پایگاه داده Modulo Hashing است.

1. شناسه رویداد را می‌گیریم و از یک تابع هش رد می‌کنیم که آن را به عدد تبدیل می‌کند.
2. آن عدد را می‌گیریم و عملیات مدول (%) را با تعداد پایگاه‌های داده انجام می‌دهیم.
3. نتیجه می‌گوید کدام پایگاه داده باید آن رویداد را ذخیره کند.

در کد این‌طور است:

database_id = hash(event_id) % number_of_databases

یک مثال ملموس با ۳ پایگاه داده:

Event #1234 -> hash(1234) % 3 = 1 -> Database 1
Event #5678 -> hash(5678) % 3 = 0 -> Database 0
Event #9012 -> hash(9012) % 3 = 2 -> Database 2

عالی است، این روش خوب کار می‌کند… تا وقتی که به چند مشکل بخورید.

مشکل اضافه کردن گره

مشکل اول وقتی پیش می‌آید که بخواهید نمونه چهارم پایگاه داده را اضافه کنید. ساده‌لوحانه فکر می‌کنید فقط کافی است عملیات مدول را به‌جای ۳ با ۴ انجام دهید.

database_id = hash(event_id) % 4

کد را عوض می‌کنید، روی production می‌فرستید، اما بعد فعالیت پایگاه داده از سقف می‌گذرد! نه فقط برای نمونه چهارم، بلکه برای همه آن‌ها.

اتفاقی که افتاد این بود که تغییر تابع هش، نه‌فقط روی داده‌هایی که باید در نمونه جدید ذخیره شوند اثر می‌گذارد، بلکه تقریباً مشخص می‌کند هر رویداد روی کدام نمونه ذخیره شود، یعنی جای تقریباً همه رویدادها عوض می‌شود.

مثلاً رویداد #1234 قبلاً به پایگاه داده ۱ نگاشت می‌شد، اما حالا hash(1234) % 4 = 0 است. پس داده باید از پایگاه داده ۱ به پایگاه داده ۰ منتقل شود. این فقط یک مورد استثنا نیست. بیشتر داده‌های شما باید بین همه نمونه‌های پایگاه داده جابه‌جا شوند و این جابه‌جایی عظیم و غیرضروری داده ایجاد می‌کند. نتیجه، جهش‌های بزرگ در بار پایگاه داده است و کاربران یا نمی‌توانند به داده دسترسی پیدا کنند یا زمان پاسخ کند را تجربه می‌کنند.

مشکل حذف گره

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

حالا تابع هش از database_id = hash(event_id) % 3 به database_id = hash(event_id) % 2 تغییر می‌کند و دقیقاً همان مشکل بازتوزیع قبلی پیش می‌آید.

واضح است که Modulo Hashing ساده کافی نیست. اینجاست که Consistent Hashing وارد می‌شود.

Consistent Hashing

Consistent Hashing تکنیکی است که مشکل بازتوزیع داده را هنگام اضافه یا حذف یک نمونه در سیستم توزیع‌شده حل می‌کند. ایده کلیدی این است که هم داده‌ها و هم پایگاه‌های داده را روی یک فضای دایره‌ای بچینیم، که اغلب «حلقه هش» (hash ring) نامیده می‌شود.

طرز کارش این است.

1. اول یک حلقه هش با تعداد ثابتی نقطه می‌سازیم. برای ساده ماندن، فرض کنید ۱۰۰ نقطه.
2. بعد پایگاه‌های داده را به‌طور مساوی روی حلقه هش توزیع می‌کنیم. اگر ۴ پایگاه داده داریم، می‌توانیم آن‌ها را در نقطه‌های ۰، ۲۵، ۵۰ و ۷۵ بگذاریم.
3. برای فهمیدن این‌که رویدادی باید روی کدام پایگاه داده ذخیره شود، اول شناسه رویداد را مثل قبل هش می‌کنیم. اما به‌جای مدول گرفتن، مقدار هش را روی حلقه پیدا می‌کنیم و در جهت عقربه‌های ساعت حرکت می‌کنیم تا به یک نمونه پایگاه داده برسیم.

در واقعیت، حلقه هش معمولاً فضای هش 0 تا 2^32 - 1 دارد، نه 0 تا 100. اما مفهوم همان است.

این روش مشکل ما را چطور حل کرد؟ ببینیم وقتی پایگاه داده اضافه یا حذف می‌کنیم چه می‌شود.

اضافه کردن پایگاه داده (DB5): فرض کنید پایگاه داده پنجم را در موقعیت ۹۰ حلقه اضافه می‌کنیم. حالا:

• فقط رویدادهایی که هش‌شان بین موقعیت ۷۵ و ۹۰ می‌افتد باید جابه‌جا شوند.
• این رویدادها قبلاً به DB1 (در موقعیت ۰) می‌رفتند.
• همه رویدادهای دیگر دقیقاً همان‌جا می‌مانند که بودند.

قبلاً تقریباً همه داده‌ها باید دوباره توزیع می‌شدند. اما با Consistent Hashing فقط حدود ۶۰٪ از رویدادهای DB1 جابه‌جا می‌شوند، یعنی تقریباً ۱۵٪ از کل رویدادها.

حذف پایگاه داده: به‌طور مشابه، اگر پایگاه داده ۲ (در موقعیت ۲۵) خراب شود:

• فقط رویدادهایی که به پایگاه داده ۲ نگاشت شده‌اند باید جابه‌جا شوند.
• این رویدادها حالا به پایگاه داده ۳ (در موقعیت ۵۰) نگاشت می‌شوند.
• بقیه‌چیز سر جای خودش می‌ماند.

گره‌های مجازی (Virtual Nodes)

پیشرفت خوبی داشته‌ایم، اما هنوز یک مشکل مانده است. در مثال بالا، که پایگاه داده ۲ را حذف کردیم، مجبور شدیم همه رویدادهای ذخیره‌شده روی آن را به پایگاه داده ۳ منتقل کنیم. حالا پایگاه داده ۳ دو برابر بار پایگاه داده ۱ و ۴ را دارد. ترجیح می‌دهیم بتوانیم بار را یکنواخت پخش کنیم تا پایگاه داده ۳ بیش از حد زیر بار نرود.

راه‌حل استفاده از چیزی است که «گره مجازی» نام دارد. به‌جای این‌که هر پایگاه داده را فقط در یک نقطه از حلقه بگذاریم، آن را با هش کردن چند نسخه مختلف از نامش در چند نقطه قرار می‌دهیم.

مثلاً به‌جای هش کردن «DB1» برای گرفتن موقعیت ۰، عبارت‌های «DB1-vn1»، «DB1-vn2»، «DB1-vn3» و مانند آن‌ها را هش می‌کنیم. ممکن است موقعیت‌های ۱۵، ۲۵، ۴۰ و غیره به ما بدهند. این کار را برای هر پایگاه داده می‌کنیم و نتیجه این است که گره‌های مجازی به‌طور طبیعی دور حلقه با هم قاطی می‌شوند.

حالا وقتی پایگاه داده ۲ از کار می‌افتد:

• رویدادهای نگاشت‌شده به «DB2-vn1» به پایگاه داده ۱ بازتوزیع می‌شوند.
• رویدادهای نگاشت‌شده به «DB2-vn2» به پایگاه داده ۳ می‌روند.
• رویدادهای نگاشت‌شده به «DB2-vn3» به پایگاه داده ۴ می‌روند.
• و همین‌طور بقیه.

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

Consistent Hashing در دنیای واقعی

مثال ما روی مقیاس دادن یک پایگاه داده متمرکز بود، اما Consistent Hashing در هر سناریویی کاربرد دارد که باید داده را بین مجموعه‌ای از سرورها توزیع کنید. این مجموعه البته می‌تواند پایگاه داده باشد، اما می‌تواند کش، message broker یا حتی فقط مجموعه‌ای از سرورهای اپلیکیشن هم باشد.

Consistent Hashing را در بسیاری از سیستم‌های بزرگ‌مقیاس می‌بینیم که به آن تکیه زیادی دارند. مثلاً:

• Apache Cassandra: برای توزیع داده روی حلقه از Consistent Hashing استفاده می‌کند.
• Amazon DynamoDB: در پشت صحنه از Consistent Hashing استفاده می‌کند.
• شبکه‌های توزیع محتوا (CDN): برای تعیین این‌که کدام سرور edge باید محتوای مشخصی را کش کند، از Consistent Hashing استفاده می‌کنند.

چه زمانی در مصاحبه از Consistent Hashing استفاده کنیم

بیشتر سیستم‌های توزیع‌شده مدرن Sharding و توزیع داده را برای شما انجام می‌دهند. وقتی سیستمی با DynamoDB، Cassandra و مانند آن‌ها طراحی می‌کنید، معمولاً کافی است بگویید این سیستم‌ها در پشت صحنه از Consistent Hashing (یا شکلی از آن) برای مدیریت مقیاس‌دهی استفاده می‌کنند.

با این حال، Consistent Hashing در مصاحبه‌های متمرکز بر زیرساخت، جایی که از شما می‌خواهند سیستم توزیع‌شده را از صفر طراحی کنید، موضوع حیاتی می‌شود. سناریوهای رایج این‌هاست.

• طراحی یک پایگاه داده توزیع‌شده.
• طراحی یک کش توزیع‌شده.
• طراحی یک message broker توزیع‌شده.

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

• باید توضیح دهید چرا Consistent Hashing نسبت به رویکردهای ساده Sharding مبتنی بر مدول مزیت دارد.
• باید آماده باشید درباره این‌که گره‌های مجازی چطور به توزیع بهتر بار در سیستم کمک می‌کنند صحبت کنید.
• باید استراتژی‌های مدیریت خرابی گره و اضافه شدن گره به خوشه را توضیح دهید.
• باید درک خودتان را از نحوه برخورد با hot spot و اجرای استراتژی‌های مؤثر rebalancing داده نشان دهید.

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

جمع‌بندی

Consistent Hashing یکی از الگوریتم‌هایی است که با حل یک مسئله ظاهراً ساده، سیستم‌های توزیع‌شده را متحول کرد. مسئله این بود که داده را چطور بین سرورها توزیع کنیم و وقتی تعداد سرورها تغییر می‌کند، کمترین بازتوزیع را داشته باشیم.

جزئیات پیاده‌سازی می‌تواند پیچیده شود، اما ایده اصلی زیبا و ساده است: همه‌چیز را روی یک دایره بچین و در جهت عقربه‌های ساعت حرکت کن. این راه‌حل ظریف حالا در بسیاری از سیستم‌های توزیع‌شده‌ای که هر روز استفاده می‌کنیم، از DynamoDB تا Cassandra، به کار رفته است.

در مصاحبه طراحی سیستم بعدی‌تان یادتان باشد که معمولاً لازم نیست Consistent Hashing را خودتان پیاده‌سازی کنید. فقط بدانید کجا در پشت صحنه استفاده می‌شود و بررسی عمیق آن را برای سوال‌های زیرساختی نگه دارید که واقعاً اهمیت دارند.