پیشرفت نظری و آکادمیک می‌تواند سرعت ذخیره‌سازی داده‌ها را افزایش دهد

روش جدید کشف شده در MIT CSAIL در مورد کاوش بر جداول هش خطی (linear-probing hash) می‌تواند منجر به ذخیره‌سازی و بازیابی کارآمدتر داده‌ها در رایانه‌ها شود.

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

یافته‌های این تیم مربوط به اصطلاح “جدول هش کاوش خطی” است که در سال ۱۹۵۴ معرفی شد و یکی از قدیمی‌ترین، ساده‌ترین و سریع‌ترین ساختارهای داده‌های امروزی است. ساختارهای داده راه‌هایی برای سازماندهی و ذخیره‌سازی داده‌ها در کامپیوتر ارائه می‌دهند که جداول هش یکی از متداول‌ترین این رویکردها است. در این جدول، موقعیت‌های که اطلاعات در آن می‌توانند ذخیره شوند در امتداد یک آرایه خطی قرار دارند.

به گفته کوزمائول « فرض کنید که پایگاه داده‌ای برای ذخیره شماره‌های تامین اجتماعی ۱۰۰۰۰ نفر طراحی شده است. “ما شماره تامین اجتماعی شما، x را در نظر می‌گیریم و سپس تابع هش  x، h(x) را محاسبه می‌کنیم، که یک عدد تصادفی بین یک تا ۱۰۰۰۰ به شما می‌دهد. مرحله بعدی این است که آن عدد تصادفی، h(x) را بگیرید، به موقعیت آن در آرایه بروید و x که شماره تامین اجتماعی شما بود را در آن نقطه قرار دهید.

کوزمائول می‌گوید: اگر داده‌ای قبلاً آن نقطه را اشغال کرده باشد، «شما فقط به سوی موقعیت آزاد بعدی حرکت کنید و داده‌ی خود را در آن جای خالی قرار دهید. این همان جایی است که اصطلاح “کاوش خطی” از آنجا می آید، زیرا شما تا زمانی که یک نقطه باز پیدا کنید به صورت خطی به جلو حرکت می کنید. برای اینکه بعداً آن شماره تأمین اجتماعی، x را بازیابی کنید، فقط به نقطه تعیین شده، h(x) بروید و اگر آنجا نباشد، به جلو حرکت می کنید تا زمانی که x را پیدا کنید یا به یک موقعیت آزاد برسید و نتیجه بگیرید که x در پایگاه داده شما نیست.

همیشه یک پروتکل متفاوت برای حذف یک item، مانند شماره تامین اجتماعی وجود دارد. اگر پس از حذف اطلاعات، فقط یک نقطه خالی در جدول هش رها کردید، وقتی بعداً بخواهید داده دیگری پیدا کنید ممکن است باعث سردرگمی شما شود، زیرا ممکن است جای خالی به اشتباه نشان دهد که موردی که شما به دنبال آن هستید در هیچ کجای پایگاه داده پیدا نمی‌شود. کوزمول توضیح می‌دهد که برای جلوگیری از این مشکل «شما می‌توانید به نقطه‌ای بروید که item حذف شده سپس یک نشانگر کوچک به نام «tombstone» در آن‌جا قرار دهید که نشان می‌دهد قبلاً عنصری در اینجا وجود داشته اما الان از بین رفته است.».

این رویه کلی بیش از نیم قرن است که دنبال می‌شود. اما در تمام این مدت تقریباً همه کسانی که از جداول هش کاوشگر خطی استفاده می‌کنند، فکر می‌کردند که اگر به Database اجازه دهید بیش از حد پر شوند، بخش‌های طولانی از نقاط اشغال شده در کنار هم قرار می‌گیرند و «خوشه‌ها» را تشکیل می‌دهند. در نتیجه، زمان لازم برای یافتن یک نقطه خالی به طور چشمگیری افزایش می یابد. در واقع این کار آ‌ن‌ قدر طول می‌کشد که در حقیقت غیرعملی باشد. در نتیجه، افراد برای کار با جدول‌های هش با ظرفیت کم آموزش دیده‌اند. روشی که می‌تواند با تأثیر بر میزان توان سخت‌افزاری شرکت، هزینه‌های اقتصادی داشته باشد.

اما این اصل دیرینه که مدت‌هاست در برابر عوامل بار مبارزه می‌کند، با کار کوزمول و همکارانش، مایکل بندر از دانشگاه استونی بروک و بردلی کوزمول از گوگل، کاملاً تغییر کرده است. آنها فهمیدند که در  برنامه‌هایی که تعداد delete و insert تقریباً یکسان است و مقدار داده‌های اضافه شده تقریباً برابر با داده‌های حذف شده است. جدول‌های هش کاوش خطی (linear-probing hash) می‌توانند در ظرفیت‌های ذخیره‌سازی با حجم بالا و بدون کاهش سرعت کار کنند.

علاوه بر این، تیم یک استراتژی جدید به نام «هش کردن قبرستان(graveyard hashing)» ابداع کرده است که شامل افزایش تعداد tombstone است، تا زمانی که حدود نیمی از نقاط آزاد را اشغال کنند و در یک آرایه قرار می‌گیرند، سپس این tombstone ها فضاهایی را ذخیره می‌کنند که می‌تواند برای درج رکورد‌های بعدی استفاده شود.

Kuszmaul می‌گوید رویکرد او که برخلاف آنچه معمولاً به مردم گفت شده است، می‌تواند به عملکرد بهینه در جداول هش کاوش خطی منجر شود. همانطور که او و همکارانش در مقاله خود می گویند: «استفاده مناسب از سنگ قبرها (tombstone) ها می‌تواند به طور کامل چشم انداز رفتار کاوشگر خطی را تغییر دهد».

Kuszmaul این یافته‌ها را با Bender l در مقاله‌ای که در اوایل سال جاری در Foundations of Computer Science (FOCS) Symposium in Boulder در کلرادو ارائه خواهد شد،به طور کامل مطرح کرده است.

استاد مشاور پایان نامه دکترای کوزمول، استاد علوم کامپیوتر MIT، چارلز لیزرسون (که در این تحقیق شرکت نکرد)، با این ارزیابی موافق است. Leiserson می‌گوید: «این نتایج جدید و شگفت‌انگیز یکی از قدیمی‌ترین روش‌های مرسوم در مورد رفتار جدول هش را باطل می‌کند. این درس‌ها سال‌ها در میان نظریه‌پردازان بازتاب خواهند داشت.»

او همچنین در مورد نتایج، کوزمائول خاطرنشان می‌کند: «مطالعات زیادی در ساخت جدول هش وجود دارد. ما این موضوع را به طور قابل توجهی از نقطه نظر تئوریک پیش بردیم، و  تازه شروع به کشف جنبه تجربی آن کرده‌ایم.» 

این پست ترجمه شده مقاله Theoretical breakthrough could boost data storage است

نویسنده: تیم مارکتینگ آسا