ارتقاء سرعت پایگاه‌های داده آنلاین
 

ذخیره داده کارآمدتر می‌شود جدول درهم سازی کاوش خطی

«جدول‌های درهم‌سازی کاوش خطی» که در سال ۱۹۵۴ ابداع شدند، در زمره قدیمی‌ترین، ساده‌ترین و سریع‌ترین داده ساختارهایی هستند که امروزه در دسترس کاربرها قرار دارند. داده ساختارها راه مناسبی برای سازماندهی و ذخیره داده‌های رایانه‌ای در اختیار کاربرها قرار می‌دهند. در حال حاضر، استفاده از جدول‌های درهم‌سازی یکی از رایج ترین رویکردها در سامان بخشیدن به داده‌های رایانه‌ای است. در یک جدول درهم‌سازی کاوش خطی، موقعیت‌هایی که اطلاعات در آنها ذخیره می‌شوند در یک آرایه خطی در کنار هم قرار می‌گیرند.

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

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

***

درهم‌سازی(hashing) یک عملیات مهم در بیشتر پایگاه‌های داده آنلاین از جمله یک کاتالوگ کتابخانه یا یک وب سایت تجارت الکترونیک است. در درهم‌سازی از توابع هش استفاده می‌شود. توابع هش توابعی در ریاضیات هستند که می‌توان از آنها برای نگاشت داده‌های دیجیتالی با حجم متغیر و نیز داده‌های دیجیتالی با حجم ثابت استفاده کرد. آنها حجم زیادی از داده را به اعداد طبیعی تبدیل می‌کنند. یک تابع هش یا تابع چکیده‌ساز کدهایی می‌سازد که جایگزین داده‌های ورودی می‌شوند. از آنجا که این کدها کوتاه‌تر از داده‌های حقیقی هستند و به طور معمول طول ثابتی دارند، راحت‌تر می‌توان اطلاعات اصلی را پیدا و بازیابی کرد.

با این‌حال، چون توابع هَش سنتی به طور تصادفی کدسازی می‌کنند، گاهی وقت‌ها دو داده می‌توانند با یک مقدار مشابه در‌هم‌سازی شوند. این امر موجب تصادف یا برخورد می‌شود؛ یعنی وقتی کاربر به دنبال یک داده مشخص می‌گردد، داده‌های بسیاری با مقدار هش ثابت در مقابلش قرار می‌گیرند. زمان بسیار بیشتری لازم است تا داده مورد نظرش پیدا شود؛ در نتیجه، سرعت جستجو کم می‌شود و عملکرد نیز کاهش می‌یابد.

برخی از انواع توابع هش که به آنها «توابع هش کامل» می‌گویند به منظور مرتب‌سازی داده‌ها بدون آن‌که برخوردی رخ دهد طراحی شده‌اند. اما لازم است برای هر مجموعه داده یک تابع هش متفاوت به طور خاص و جداگانه ساخته شود. زمان محاسبه نیز بیشتر از توابع هش سنتی خواهد بود.

از آنجا که درهم‌سازی کاربردهای زیادی دارد، از نمایه‌سازی پایگاه‌های داده گرفته تا فشرده‌سازی داده‌ها و رمزنگاری، وجود تابع‌های هش سریع و کارآمد ضروری است. از این رو پژوهشگرهای «مؤسسه فناوری ماساچوست» (MIT)امکان استفاده از یادگیری ماشین را برای ساختن تابع‌های هش بهتر مورد بررسی قرار دادند.

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

این پژوهش که در کنفرانس سالانه بین المللی Very Large Databasesارائه خواهد شد نشان می‌دهد چگونه می‌توان یک تابع هش طراحی کرد که سرعت جستجو در یک پایگاه داده بزرگ را به میزان قابل توجهی بالا ببرد. برای مثال، این تکنیک می‌تواند سرعت سیستم‌های محاسباتی را که دانشمندان برای ذخیره‌سازی و تحلیل DNA، توالی‌های آمینواسید یا اطلاعات بیولوژیکی دیگر استفاده می‌کنند بالا ببرد.

وقتی به یک تابع هش سنتی داده وارد می‌شود؛ یعنی به آن کلید داده می شود، یک عدد یا کد تصادفی می سازد که منطبق با سلولی است که کلید در آن ذخیره خواهد شد. به عنوان یک مثال ساده، اگر ۱۰ کلید باشند که باید درون ۱۰ سلول قرار گیرند، تابع یک عدد صحیح تصادفی بین ۱ تا ۱۰ برای هر داده ورودی خواهد ساخت. بسیار محتمل است که دو کلید در یک سلول واحد قرار گیرند که این باعث برخورد می‌شود.

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

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

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

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

آزمایش‌ها نشان دادند‌که وقتی داده‌ها به طرز قابل پیش‌بینی توزیع شدند، مدل‌های آموخته توانستند نسبت کلیدهایی که با هم برخورد داشتند را از ۳۰ درصد به ۱۵ درصد کاهش دهند. همچنین، حاصل کار این مدل‌ها بهتر از توابع هش کامل بود. در بهترین حالت‌ها، مدل‌های آموخته زمان انجام عملیات را تا حدود ۳۰ درصد کمتر کردند.

پژوهشگرهای مطالعه حاضر کاربردهای مدل‌های آموخته را بررسی کرده‌اند. هر مدل آموخته متشکل از مدل‌های خطی کوچک‌تری است که به توزیع داده نزدیک هستند. هر چه خُرد مدل‌ها بیشتر باشند، مدل آموخته تقریب دقیق‌تری ارائه می‌دهد؛ اگر چه در این صورت زمان بیشتری نیز مورد نیاز خواهد بود. وقتی تعداد خُردمدل‌ها به آستانه معینی برسد، به قدر کافی اطلاعات به دست خواهد آمد که تقریب مورد نیاز برای تابع هش ساخته شود. اما پس از آن، دیگر تغییری در کاهش برخوردها ایجاد نخواهد شد.

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

code

نسخه مناسب چاپ