از انواع جدول‌های درهم‌سازی: جدول سوئیسی

روش‌های مرسوم رفع تصادم (collision) توی hashmap رو تو درس ساختمان داده خوندیم:

1- open addressing 2- chaining 3- hybrid

خیلی خلاصه بخوام هرکدوم رو مرور کنم اینطور میشه:

در open addressing اینطور عمل می‌کنیم که وقتی تصادم رخ داد، اینقدر توی آرایه‌ی wrap شده جلو می‌ریم تا به اولین خونه‌ی خالی برسیم و item رو اونجا بذاریم.

در روش chaining هر خونه‌ی آرایه‌ی ما یک عنصر نگه می‌داره و یک پوینتره به یک ساختمان‌داده‌ی دیگه که می‌تونه یک linked list باشه یا یک درخت متوازن مثل red-black یا AVL. در صورتی که توی اون خونه‌ی آرایه از قبل داده‌ای وجود داشته باشه، آیتم جدید رو push می‌کنیم توی اون ساختمان‌داده‌ای که اون خونه بهش اشاره می‌کنه.

در روش سوم، یکی از روش‌های اول و دوم رو با مکانیزم هش‌چندباره ترکیب می‌کنیم. به این صورت که چند الگوریتم هش متفاوت رو در نظر می‌گیریم. در صورتی که با هش آیتم مدنظرمون تصادم رخ داد، یک الگوریتم هش جدید رو انتخاب می‌کنیم. مکانیزم انتخاب الگوریتم هش هم می‌تونه هرچی باشه. ما ساده و round robin در نظر می‌گیریم. این کار رو تا زمانی ادامه می‌دیم که تمام الگوریتم‌های هش‌مون رو تست کرده باشیم و همشون منجر به تصادم شده باشن. بعد با استفاده از یکی از روش‌های ۱ یا ۲ اقدام به ذخیره کردن آیتم می‌کنیم.

تمام این قصه‌ها چیزهایی هست که تا اینجا می‌دونیم و مرسومه. ولی واقعاً چقدر از این روش‌ها استفاده میشه؟ آیا میشه پا رو فراتر گذاشت و عملکرد رو از این هم بهتر کرد؟

توی جاهایی مثل Cloudflare که عملکرد در حد میکروثانیه مهمه، گاهی باید پا رو فراتر گذاشت. گاهی ساده‌ترین جزئیات می‌تونن تفاوت چندبرابری در سرعت ایجاد کنن. انگار یه نوع amplification رخ میده؛ بهینه‌سازی کوچیک که باعث میشه کل سیستم خیلی سریع‌تر به‌نظر بیاد.

یکی از ایده‌هایی که دقیقاً با همین ذهنیت طراحی شده، ساختار Swiss Tableه. گوگل با در نظر گرفتن چالش کش سرور‌ها دست به طراحی این ساختار زده. زبان‌هایی مثل Rust هم از همین ساختار برای پیاده‌سازی پیش‌فرض HashMap خودشون استفاده می‌کنن. گوگل تو کنفرانس CppCon 2017 هم درباره‌ی طراحی و بهینه‌سازی این ساختار ارائه‌ای داشت که دیدنش خالی از لطف نیست:

CppCon 2017: Matt Kulukundis – Designing a Fast, Efficient Hash Table

Swiss Table در اصل هنوز از ایده‌ی open addressing استفاده می‌کنه؛ یعنی داده‌ها مستقیماً در یک آرایه ذخیره می‌شن و وقتی تصادم رخ بده، دنبال خونه‌ی بعدی می‌گردیم تا جایی برای درج پیدا کنیم. ولی تفاوت اصلیش اینه که چطور این آرایه bucket‌ بندی میشه و چطور CPU ازش استفاده می‌کنه.

در Swiss Table، آرایه‌ی اصلی به چند bucket تقسیم میشه. هر bucket معمولاً چند تا slot داره (مثلاً 8 تا)، یعنی هر bucket خودش می‌تونه تا 8 تا عنصر نگه داره. در کنارش یه آرایه‌ی کوچیک‌تر از metadata داریم که برای هر slot فقط یه بایت اطلاعات ذخیره می‌کنه. توی این بایت، یه تیکه از هش کلید (مثلاً 7 بیت از اون) نگه داشته میشه تا CPU بتونه سریع‌تر بفهمه کدوم slot احتمالاً مربوط به کلید مورد نظره.

وقتی می‌خوایم دنبال یه کلید بگردیم یا کلید جدیدی وارد کنیم، Swiss Table با استفاده از SIMD (Single Instruction, Multiple Data) چند بایت metadata رو با هم می‌خونه (مثلاً 16 تا در یک لحظه) و در عرض یک دستور CPU بررسی می‌کنه که آیا هش کوچیک ذخیره‌شده توی اون‌ها با هش کلید ما یکیه یا نه. بعد اگه یکی از اون‌ها match کرد، تازه می‌ره سراغ داده‌ی واقعی و بررسی دقیق‌تر انجام میده.

Swiss Table تنها نمونه‌ی چنین طراحی‌ای نیست. بعد از گوگل، پروژه‌های بزرگ دیگه مثل Facebook’s F14
ایده‌های مشابه استفاده کردن. زبان‌هایی مثل Rust و Go هم با الهام از همین طراحی، نسخه‌های خودشون رو ساختن.

در پیاده‌سازی Go، تیم توسعه با یه چالش جدی روبه‌رو شد که به‌طور مفصل توی این پست توضیح داده شده:

The Go Blog – Swiss Table

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

این فرایند در سیستم‌های عادی چندان مشکلی ایجاد نمی‌کنه، ولی در سرورهای کش که چند ترابایت دیتا داخل مموری دارن، این resize می‌تونه به شدت زمان‌بر و کند باشه. راه‌حلی که گولنگ برای این موضوع ارائه داد، استفاده از hashmapهای چند‌لایه (multi-level) بود. به‌جای resize کامل، داده‌های جدید در یک لایه‌ی بالاتر ذخیره می‌شن و به‌صورت تدریجی داده‌های قدیمی جابه‌جا می‌شن. اینطوری عملیات resize به بخش‌های کوچیک تقسیم میشه و فشار ناگهانی از روی سیستم برداشته میشه.

این پست رو هم از دست ندین:

A new fast hash table in response to Google’s new fast hash table