2007: Amazon DynamoDB צריכה להחליט איך לחלק data בין nodes. הבעיה הידועה: hash % N הוא טוב כשמספר ה-nodes קבוע. אבל Amazon צריך להוסיף ולהסיר nodes כל הזמן - failover, scaling, maintenance. עם hash % N, כל שינוי ב-N מחייב rehashing של רוב ה-data. ל-million-record database - זה catastrophic. Consistent Hashing הוא הפתרון ש-DynamoDB, Cassandra, Redis Cluster ו-Memcached השתמשו בו.
Consistent Hashing הוא אלגוריתם שמחלק data בין nodes כך שכשמוסיפים או מסירים node - רק K/N records (K = total keys, N = number of nodes) צריכים להיעתק. לא רוב ה-data - רק החלק שה-node הזה אחראי עליו.
ה-algorithm נוצר ב-1997 ע"י David Karger ועמיתיו ב-MIT - ב-paper שנכתב בהקשר של web caching, לא database. הם חיפשו algorithm שיאפשר להוסיף ולהסיר cache servers בלי ש-80% מה-cache יהפוך ל-invalid. ה-paper הוביל ישירות ל-implementations ב-Akamai CDN. לאחר מכן Amazon ו-LinkedIn השתמשו ברעיון ל-distributed databases. זו אחת ה-algorithms שמגיעות מאקדמיה ישר ל-production ב-scale.
האינטואיציה מאחורי הבעיה: ב-cache cluster עם 10 servers, כש-server נופל gracefully - תרצו שרק ה-keys שהיו עליו יצריכו fetch מחדש מ-DB. לא 90% מה-cache אחר. עם hash % 10 → hash % 9, המתמטיקה עובדת נגדכם: hash("user:123") % 10 = 3 ≠ hash("user:123") % 9 = 4. ה-key שהיה על server 3 עכשיו צריך להיות על server 4. לא רק ה-keys מ-server שנפל - גם keys שהיו על servers אחרים עכשיו במיפוי שגוי.
Akamai ב-1997 הייתה CDN שגדלה במהירות - כל שבוע הוסיפו edge servers חדשים. בלי Consistent Hashing, כל הוספת server ב-CDN דרשה ל-reroute 80%+ מה-cache. זה ה-thundering herd על origin servers. ה-paper של Karger פתר את זה: עם Consistent Hashing, הוספת server ל-100-node cluster פירושה שרק 1% מה-keys זזים, לא 80%+. Akamai בנתה אחד מה-largest production deployments של Consistent Hashing בהיסטוריה.