Hashing سازگار (Consistent Hashing)
Consistent Hashing: حل مشکل rehash در مقیاس‌پذیری؛ حلقه هش، Virtual Nodes و کاربرد در کش توزیع‌شده
مشکل: سرور اضافه شد!
کش توزیع‌شده با ۳ سرور و هش ساده:
server = hash(key) % 3سرور ۴ اضافه شد → % 4 → تقریباً همه کلیدها جابه‌جا! (۳/۴ داده = miss انبوه = کش سرد = فاجعه!)
راه‌حل: Consistent Hashing
حلقه هش: فضای هش را به‌صورت دایره (۰ تا ۲³²) تصور کن:
- هر سرور را هش کن → روی حلقه بگذار
- هر کلید را هش کن → روی حلقه
- کلید متعلق به: اولین سرور در جهت عقربه‌های ساعت
جادو: افزودن سرور
سرور جدید بین دو سرور موجود می‌نشیند → فقط کلیدهای بین آن‌ها جابه‌جا می‌شوند (~1/n) — نه همه!
| رویداد | هش ساده (mod n) | Consistent |
|---|---|---|
| سرور اضافه | ~همه جابه‌جا ✗ | ~1/n جابه‌جا ✓ |
| سرور حذف | ~همه جابه‌جا ✗ | فقط سهم او ✓ |
مشکل توزیع ناهمگن + Virtual Nodes
با چند سرور فیزیکی، حلقه ممکن است ناهمگن باشد (سروری سهم زیاد بگیرد). راه‌حل: هر سرور ۱۰۰-۲۰۰ نود مجازی روی حلقه → توزیع یکنواخت آماری!
کاربردهای واقعی
- کش توزیع‌شده: Memcached، Redis Cluster (ساختار حلقه‌گونه)
- CDN: توزیع محتوا بین لبه‌ها
- دیتابیس: Cassandra (پارتیشن‌بندی!)، DynamoDB
- LB هش‌محور: Session sticky هوشمند
نکته مصاحبه: «کش توزیع‌شده چطور طراحی می‌کنی؟» — «Consistent Hashing با virtual nodes» پاسخ استاندارد است؛ حتماً «چرا» (مشکل mod n) را هم بگویید!
جمع‌بندی
- mod n با تغییر n = فاجعه جابه‌جایی
- حلقه هش: کلید → اولین سرور ساعت‌گرد
- تغییر سرور = فقط سهم محلی جابه‌جا
- Virtual nodes = توزیع یکنواخت
این مبحث بخشی از دوره آموزش کامل طراحی سیستم (System Design) است.