الگوریتم Consistent Hashing

سلام بعد چند وقت خواستم یکی از الگوریتم های مورد علاقه ام اینجا توضیح بدم.

hash کردن یک راه توزیع پذیری پردازش و داده بین چند سرور هستش
الگوریتم hash و تقسیم توسط باقی مانده:
فرض کنید ما 4 تا سرور داریم و می خواهیم داده به صورت یکسان بین 4 تا سرور تقسیم بشه:

  val availableNodes= List("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4")

  def hash(key: String): Int = MurmurHash3.stringHash(key)

  def findNodeFor(hashKey: Int): String = availableNodes(hashKey % availableNodes.size)

  //Usage
  findNodeFor(hash("abcd")) // 192.168.0.2

این برای یک مثال ساده کار می کنه اما با اضافه یا حذف شدن یک سرور جای تمام کلید ها عوض میشه و باید کل داده یا state جابجا بشه که در محیط production
اصلا مطلوب نیست
الگوریتم Consistent Hashing برای رفع این مشکل به وجود اومد که در مقاله dynamo توضیح داده شده و توسط database های دیگه مثل cassandra هم استفاده میشه

الگوریتم CH از بازه بین ۰-۱ دایره تشکیل می ده

و ساعت گرد همه سرور هارو بین این بازه تقسیم میکنه

با استفاده از hash خوب داده به صورت تصادفی و یکسان بین سرور ها تقسیم میشه با hash هر کلید اولین سرور که ساعت گرد بهش می رسیم به سرور می فرستیم

حالا با اضافه/حذف شدن هر سرور فقط بازه های کوچک بین دو سرور باید داده رو جابجا کنند

لینک به مقاله dynamo

9 Likes

جالبه. اینطوری هم میشه با جابجایی سرورها توی این بازه، شانس dispatch شدن بهشون را تنظیم کرد.