گروه‌بندی سریع کاربران با استفاده از Consistent Hashing

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

یک مثال دیگه. فرض کنید ترافیک کاربر ها به سایت خیلی زیاده. میخوایم بگیم اطلاعات ۵۰ درصد کاربرها توی یک سرور و اطلاعات ۵۰ درصد دیگه ی کاربر‌ها توی یک سرور دیگه ذخیره شه. چطور این کارو انجام بدیم؟

راهی سریع با دقت بالا.

نکته‌ایی که هست جواب معمولی ایی که به ذهن اکثریت میرسه اینه خب یک دیتابیس داشته باشیم که بیاد بگه هر آی دی توی کدوم دیتابیس ذخیره شده (یعنی دیتابیس اول key value هست) و در نهایت با توجه به اطلاعات اون دیتابیس وصل شیم به دیتابیس اصلی‌ایی که دیتاهای کاربر توش ذخیره شده.

یا برای مثال اول بیایم یه کوئری بزنیم رندوم ۲۰ درصد کاربر هامون رو انتخاب کنه. یک جدول هم داشته باشیم که مشخص کنیم هر کاربر آیا فلان فیچر براش فعال هست یا نه؟

این دو تا راه حل توی شرایط خاص خودشون به کار میان اما ۲ تا مشکل دارن. دیتای زیادی داریم ذخیره میکنیم، ریکوئست های زیادی به دیتابیس هامون میزنیم و برای یک سیستم لبه (edge) که قراره صرفا درخواست های کاربر ها رو بین چند تا سیستم توزیع کنه یکم بار اضافی داره.

استفاده از Consistent Hashing

بخوام خلاصه بگم Consistent Hashing یا هش ثابت! چیه؟ فرض کنید یک تابع هش داریم که بهش میتونیم یک id به صورت string یا هر چیزی بدیم و در نهایت به ما خروجی یک عدد بده. مثلا آی‌دی کاربر من یک uuid به شکل 71be0578-6c6c-11eb-9439-0242ac130002 هست. ما این آی‌دی رو به این تابع میدیم و به ما خروجی یک عدد میده (مثلا ۲۹۳۲۰).

حالا ما میدونیم کلا ۲ تا سرور داریم و اطلاعات این کاربر توی یکی از این دو سروره. با خودمون قرارداد میکنیم که اگه خروجی تابع هش ما زوج بود اطلاعات این کاربر توی سرور یک و اگر فرد بود توی سرور دوم هست. پس اطلاعات 71be0578-6c6c-11eb-9439-0242ac130002 توی سرور اول هست. پس وصلش میکنیم به سرور اول.

حالا نکته قشنگ این کار کجاست؟ اگر یک تابع هش سریع داشته باشیم که بدونیم توزیع یکنواخت داره، میتونیم به صورت یک نواختی بار رو بین چندین سرور پخش کنیم، یا مسئله اول (A/B تست) رو بدون نیاز به ذخیره اطلاعات اضافی حل کنیم.

حل مسئله اول: این مسئله که یکی از استفاده های A/B تست هست داره میگه ما میخوایم یک فیچر رو برای یک درصد خاصی از کاربران فعال کنیم. کافیه چیکار کنیم؟

• آی‌دی هر کاربر رو بگیریم و بدیم به تابع هشمون.
• خروجی تابع هش رو باقیمانده تقسیم بر ۱۰۰ (mod 100) بگیریم.
• حالا اگر قراره به N درصد کاربران اون فیچر رو نشون بدیم، اگر باقیمانده تقسیم کمتر از N بود به کاربر نشون میدیم درغیراینصورت نشون نمیدیم.

حل مسئله دوم: این مسئله که یکی از کاربرد های sharding هست (که دیتابیس های مختلف این رو خیلی خوب پیاده کردن) هم مثل مسئله اول هست. برای مثال اگر ۵ تا دیتابیس داریم، برای اینکه تصمیم بگیریم اطلاعات کاربر قراره کجا ذخیره بشه کافیه باقیمانده تقسیم خروجی تابع هش رو بر ۵ بگیریم. این عدد شناسه سرور رو به ما میده.

تابع هش fnv

هش فانکشنی که نیاز داریم برای این کار باید چند تا خصوصیت داشته باشه:

• سریع باشه
• توزیع یکنواخت داشته باشه
• روی سرورهای مختلف (سیستم عامل های ۳۲ یا ۶۴ بیت ایی) خروجی یکسان داشته باشه.

یکی از این توابع، تابع fnv هست که ورژن ۳۲ بیتیش هم به شدت سریعه هم کار مارو راه میندازه.

من یک نمونه تست براش با go نوشتم که هم سرعتش رو چک کنیم هم یکنواختیش رو.

تست اول: توی این تست میخوایم سرعت این تابع رو بررسی کنیم:

func HashFunction(str string, serverCount int) int {
   h := fnv.New32()
   h.Write([]byte(str))
   return int(int(h.Sum32()) % serverCount)
}

با استفاده از Go یک بنچ مارک هم نوشتم که بررسی کنه سرعت این کد رو:

func BenchmarkHashFunction(b *testing.B) {
   for i := 0; i < b.N; i++ {
      str := &quotuserid&quot + strconv.Itoa(i)
      HashFunction(str, 10)
   }
}

خروجی:

BenchmarkHashFunction-8         10057630               118 ns/op
PASS
ok      hello   1.307s

همونطوری که می‌بینید اجرای تابعمون فقط ۱۱۸ نانوثانیه طول میکشه. حالا اگر برای این کار از دیتابیس و ... استفاده میکردیم در بهترین حالت چند صد میکروثانیه بود. (به علاوه استفاده زیاد از IO)

تست دوم: توی این تست یکنواختی توزیع تابع رو بررسی میکنیم:

func main() {
   m := make(map[int]int)
   for i := 0; i < 100000; i++ {
      id := &quotuser&quot + strconv.Itoa(i)
      m[HashFunction(id, 5)]++
   }
   fmt.Println(m)
}

کد رو اجرا میکنم:

map[0:20033 1:19996 2:19944 3:19984 4:20043]

همونطوری که توی خروجی میبینید به شکل قابل قبولی خروجی یکنواخت بوده.