دانشمندان تعادل بهینه ذخیره سازی داده ها و زمان را پیدا کردند | مجله کوانتا

حدود 70 سال پیش، یک مهندس در IBM به نام هانس پیتر لون بی سر و صدا مسیر علوم کامپیوتر را تغییر داد. لون قبلا چندین حق ثبت اختراع داشت، از جمله یکی برای دستگاهی که می‌توانست تعداد نخ‌های پارچه را اندازه‌گیری کند و دیگری برای راهنمایی که تعیین می‌کرد چه نوشیدنی‌هایی را می‌توانید از مواد موجود در آشپزخانه خود تهیه کنید. اما در مقاله داخلی IBM در سال 1953، او تکنیک جدیدی را برای ذخیره و بازیابی اطلاعات پیشنهاد کرد که اکنون تقریباً در تمام سیستم های محاسباتی تعبیه شده است: جدول هش.

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

در 1957 مقاله منتشر شده در مجله تحقیق و توسعه IBMW. Wesley Peterson چالش فنی اصلی را که جداول هش ایجاد می کند شناسایی کرد: آنها باید سریع باشند، به این معنی که می توانند به سرعت اطلاعات لازم را بازیابی کنند. اما آنها همچنین باید فشرده باشند و تا حد امکان از حافظه کمتری استفاده کنند. این اهداف دوگانه اساساً در تضاد هستند. هنگامی که جدول هش حافظه بیشتری داشته باشد، دسترسی و اصلاح یک پایگاه داده می تواند سریعتر انجام شود. و عملیات در جداول هش که فضای کمتری مصرف می کنند کندتر می شوند. از زمانی که پیترسون این چالش را مطرح کرد، محققان سعی کردند بهترین تعادل را بین زمان و مکان پیدا کنند.

دانشمندان کامپیوتر اکنون به صورت ریاضی ثابت کرده اند که به بهترین حالت مبادله ای دست یافته اند. راه حل از a جفت از اخیر اوراق که مکمل یکدیگر بودند گفت: "این مقالات سوال طولانی مدت در مورد بهترین معاوضه فضا-زمان ممکن را حل می کند و نتایج بسیار شگفت انگیزی را به همراه دارد که انتظار دارم برای سال های آینده تأثیر قابل توجهی داشته باشد." مایکل میزنماخر، دانشمند کامپیوتر در دانشگاه هاروارد که در هیچ یک از این مطالعات شرکت نداشت.

وی افزود: "قطعاً می گویم این یک معامله بزرگ است." راسموس پاگ، دانشمند کامپیوتر در دانشگاه کپنهاگ. بسیاری از مردم روی این مشکل کار کرده‌اند و سعی کرده‌اند ببینند که شما چقدر می‌توانید فضا را فشرده کنید، در حالی که عملیات‌های با زمان کارآمدی نیز دارند. این همان چیزی است که من دوست داشتم حلش کنم.»

ساخت هش از آن

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

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

برای مثالی بسیار ساده، دیکشنری انگلیسی آکسفورد را در نظر بگیرید که بیش از 600,000 کلمه تعاریف دارد. اگر یک نسخه دیجیتال به جدول هش متکی است، می توانید به سادگی از یک کلمه به عنوان کلید استفاده کنید و مستقیماً به تعریف بروید. بدون جدول هش، فرهنگ لغت احتمالاً بر مکانیسم جستجوی بسیار کندتری تکیه می‌کند و از فرآیند حذف استفاده می‌کند تا در نهایت به تعریف درخواستی همگرا شود. و در حالی که یک جدول هش می تواند هر کلمه ای را در یک زمان ثابت (معمولا کسری از ثانیه) پیدا کند، زمان جستجو برای روش های دیگر می تواند با افزایش تعداد کلمات در فرهنگ لغت افزایش یابد. جدول هش مزیت دیگری نیز دارد: می‌تواند فرهنگ لغت را پویا نگه دارد و درج کلمات جدید و حذف کلمات قدیمی را آسان کند.

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

ترکیب داده ها

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

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

با تجزیه و تحلیل یک منحنی مبادله، محققان می توانند سریع ترین زمان ممکن را برای جدول هش که از مقدار مشخصی فضا استفاده می کند، کشف کنند. آن‌ها همچنین می‌توانند سؤال را به دور خود برگردانند تا کوچک‌ترین فضای ممکن را برای یک زمان عملیات معین کشف کنند. معمولاً یک تغییر کوچک در یک متغیر منجر به تغییر کوچکی در متغیر دیگر می شود ویلیام کوزمول، دانشمند نظری کامپیوتر در هاروارد و یکی از نویسندگان مقاله 2022. "اگر زمان را دو برابر کنید، شاید تعداد بیت های تلف شده در هر کلید را به نصف کاهش دهید."

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

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

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

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

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

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

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

مقید به موفقیت

سال بعد، تیمی به رهبری هواچنگ یویک دانشمند کامپیوتر در دانشگاه پرینستون، سعی کرد جدول هش تیم Bender را بهبود بخشد. گفت: «ما واقعاً سخت کار کردیم و نتوانستیم این کار را انجام دهیم رنفی ژو، دانشجوی دانشگاه Tsinghua در پکن و یکی از اعضای تیم یو. "در آن زمان بود که ما شک کردیم که کران بالایی آنها [همچنین] یک کران پایینی است" - بهترین چیزی که می توان به آن دست یافت. "وقتی کران بالا با کران پایین برابر شد، بازی تمام می شود و شما پاسخ خود را دارید." مهم نیست چقدر باهوش هستید، هیچ جدول هش نمی تواند بهتر از این کار کند.

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

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

این دستاورد کلیدی آنها بود. سپس آنها توانستند یک کران پایین در زمان اجرا برای هر جدول هش فضا کارآمد ایجاد کنند. و دیدند که دقیقاً با جدول هش Bender مطابقت دارد. ژو گفت: "ما در ابتدا فکر می کردیم که می توان آن را بهبود بخشید." "معلوم شد که ما اشتباه کرده ایم." این به نوبه خود به این معنی بود که مشکل پیترسون بالاخره حل شده بود.

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

هش به آینده

علیرغم کارایی بی سابقه جدول هش جدید، هیچ کس احتمالاً به این زودی سعی در ساخت آن ندارد. ساختن آن خیلی پیچیده است. ژو گفت: «الگوریتمی که در تئوری سریع است، لزوماً در عمل سریع نیست.

کوزمول گفت که این شکاف‌ها بین تئوری و عمل برای مدتی طولانی باقی نمی‌مانند، زیرا نظریه‌پردازان تمایل دارند عوامل ثابت را نادیده بگیرند. زمان لازم برای انجام یک عملیات معمولاً در یک عدد ضرب می شود، مقداری ثابت که مقدار دقیق آن ممکن است از نقطه نظر نظری بی اهمیت باشد. او گفت: "اما در عمل، ثابت ها واقعا مهم هستند." "در دنیای واقعی، ضریب 10 یک پایان بازی است."

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

Mitzenmacher امیدوار است که نتیجه 2023 به زودی مزایای دیگری را به همراه داشته باشد: "هر زمان که یک کران پایینی جدید به دست می آورید - به خصوص یکی که شامل تکنیک های جدید است - همیشه این امید وجود دارد که بتوانید از آنها برای مشکلات مرتبط استفاده کنید."

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