Вчені знайшли оптимальний баланс зберігання даних і часу | Журнал Quanta

Приблизно 70 років тому інженер IBM Ганс Пітер Лун тихо змінив курс інформатики. Лун уже мав кілька патентів, у тому числі один на пристрій, який міг вимірювати кількість ниток тканини, а інший на посібник, який визначав, які змішані напої можна готувати з інгредієнтів на вашій кухні. Але у внутрішньому документі IBM 1953 року він запропонував нову техніку для зберігання та отримання інформації, яка тепер вбудована майже в усі обчислювальні системи: хеш-таблицю.

Хеш-таблиці — це основний клас структур даних. Вони пропонують особливо зручний спосіб для доступу та зміни інформації у масивних базах даних. Але ця технологія має неминучий компроміс.

У 1957 папір опубліковано в IBM Journal of Research and Development, В. Уеслі Петерсон визначив головну технічну проблему, яку створюють хеш-таблиці: вони повинні бути швидкими, тобто вони можуть швидко отримувати необхідну інформацію. Але вони також мають бути компактними, використовувати якомога менше пам’яті. Ці подвійні цілі принципово суперечать. Доступ до бази даних і її змінення можна виконувати швидше, якщо хеш-таблиця має більше пам’яті; і операції стають повільнішими в хеш-таблицях, які займають менше місця. Відколи Петерсон поставив це завдання, дослідники намагалися знайти найкращий баланс між часом і простором.

Комп’ютерні вчені тепер математично довели, що вони знайшли оптимальний компроміс. Рішення прийшло від а пара останніх документи що доповнювали одне одного. «Ці документи вирішують давнє відкрите питання щодо найкращих можливих компромісів між простором і часом, даючи глибоко дивовижні результати, які, я очікую, матимуть значний вплив протягом багатьох років», — сказав Міхаель Міценмахер, вчений з інформатики Гарвардського університету, який не брав участі в жодному дослідженні.

«Я б точно сказав, що це велика справа», — додав Расмус Паг, комп’ютерний науковець Копенгагенського університету. «Багато людей працювали над цією проблемою, намагаючись побачити, наскільки ви можете стиснути простір, водночас економлячи час. Це те, що я хотів би вирішити».

Створення хешу

Хеш-таблиці є одними з найстаріших, найпростіших, найшвидших і найбільш широко використовуваних структур даних сьогодні. Вони призначені для виконання трьох основних операцій: вставки, які додають нові елементи до бази даних; запити, які звертаються до елемента або перевіряють його існування; і видалення. Хеш-таблиця може бути ефемерною — існувати лише доки працює певна програма — або вона може бути постійною частиною операційної системи вашого комп’ютера. Веб-браузер, наприклад Chrome або Safari, може мати кілька вбудованих хеш-таблиць, призначених для відстеження різних типів даних.

Записи в хеш-таблиці зберігаються як пари, де елемент — сама інформація — пов’язана з ключем, який ідентифікує інформацію. Підключіть ключ до алгоритму запиту хеш-таблиці, і ви перейдете безпосередньо до елемента. Це може здатися не таким дивним, але для величезних баз даних це може заощадити час.

Для надзвичайно спрощеного прикладу розглянемо Оксфордський словник англійської мови, який містить визначення для понад 600,000 XNUMX слів. Якщо цифрове видання покладається на хеш-таблицю, ви можете просто використати задане слово як ключ і переходити безпосередньо до визначення. Без хеш-таблиці словник, швидше за все, покладався б на набагато повільніший механізм пошуку, використовуючи процес виключення, щоб врешті-решт зблизитися до запитуваного визначення. І хоча хеш-таблиця може знайти будь-яке слово за постійний проміжок часу (зазвичай крихітну частку секунди), час пошуку для інших методів може збільшуватися зі збільшенням кількості слів у словнику. Хеш-таблиця також пропонує ще одну перевагу: вона може підтримувати словник динамічним, полегшуючи вставлення нових слів і видалення застарілих.

Дослідники витратили десятиліття на створення хеш-таблиць, які намагаються максимізувати швидкість і мінімізувати пам’ять. У 20 столітті рішення, як правило, пропонували значні переваги лише в одному аспекті, часі чи просторі. Потім у 2003 році дослідники показав що теоретично можливо зробити великий стрибок ефективності як у часі, так і в просторі одночасно. Однак знадобиться ще два десятиліття, щоб дослідники з’ясували ідеальний баланс між ними.

Перемішування даних

Перший важливий крок до цієї мети було зроблено у 2022 році о велика конференція з інформатики в Римі. Там команда запропонувала хеш-таблицю з новими функціями, які могли б забезпечити найкраще поєднання ефективності часу та простору з тих, що були раніше. Першим автором статті (за алфавітом) був Майкл Бендер з Університету Стоні Брук, тому її зазвичай називають Bender et al. хеш-таблиця. Хоча команда не намагалася побудувати функціонуючу хеш-таблицю, вони довели, що в принципі її можна побудувати з описаними ними функціями.

Щоб оцінити хеш-таблицю, яку вони придумали, група створила криву компромісу — графік, який відкладає час на операцію (вставлення чи видалення) на одній осі та простір, зайнятий пам’яттю, на іншій. Але цей графік особливим чином визначає простір: через те, як вони побудовані, хеш-таблицям потрібно більше пам’яті, ніж просто мінімум, необхідний для зберігання певного набору елементів. Комп’ютерні спеціалісти називають цей додатковий простір «марно витраченими бітами», хоча вони насправді не витрачаються марно і певною мірою є необхідними. Вісь простору на кривій компромісу вимірює кількість втрачених бітів на ключ.

Аналізуючи криву компромісу, дослідники можуть визначити найшвидший можливий час для хеш-таблиці, яка використовує заданий обсяг простору. Вони також можуть перевернути питання, щоб визначити найменший можливий простір для певного часу роботи. Як правило, невелика зміна однієї змінної призводить до невеликої зміни іншої Вільям Кушмаул, вчений-теоретик з Гарварду та співавтор статті 2022 року. «Якщо ви подвоїте час, можливо, ви вдвічі зменшите кількість втрачених бітів на ключ».

Але це не стосується розробленої ними хеш-таблиці. «Якщо ви трохи збільшите час, марно витрачені біти на клавішу експоненціально зменшаться», — сказав Кушмаул. Крива компромісу була настільки крутою, що буквально зашкалювала.

Команда створила хеш-таблицю з двох частин. Вони мали первинну структуру даних, у якій елементи зберігаються без будь-яких зайвих бітів, і вторинну структуру даних, яка допомагає запиту знайти потрібний елемент. Хоча група не винайшла поняття вторинної структури даних, вони зробили важливе відкриття, яке зробило можливою їх гіперефективну хеш-таблицю: загальна ефективність пам’яті структури залежить від того, як первинна структура впорядковує свої збережені елементи.

Основна ідея полягає в тому, що кожен елемент у первинній структурі має бажані місця зберігання — найкраще розташування, друге найкраще, третє найкраще тощо. Якщо елемент знаходиться в найкращому місці, до нього приставляється номер 1, і цей номер зберігається у вторинній структурі даних. У відповідь на запит вторинна структура надає лише число 1, яке вказує точне розташування елемента в первинній структурі.

Якщо елемент знаходиться у своєму 100-му найкращому місці, вторинна структура даних приєднує число 100. І оскільки система використовує двійковий код, вона представляє число 100 як 1100100. Звичайно, для зберігання числа 1100100 потрібно більше пам’яті, ніж 1 — номер, призначений предмету, коли він знаходиться в найкращому місці. Такі відмінності стають значними, якщо ви зберігаєте, скажімо, мільйон предметів.

Отже, команда зрозуміла, що якщо ви постійно переміщуєте елементи в первинній структурі даних у більш бажані розташування, ви можете значно зменшити пам’ять, споживану вторинною структурою, без збільшення часу запиту.

«До цієї роботи ніхто не здогадувався, що можна ще більше стискати структуру даних, переміщуючи інформацію», — сказав Паг. «Це було велике розуміння статті Бендера».

Автори показали, що їхній винахід встановив нову верхню межу для найефективніших хеш-таблиць, що означає, що це найкраща структура даних, яка була розроблена з точки зору ефективності часу та простору. Але залишалася ймовірність, що хтось інший може зробити ще краще.

Обов’язаний успіхом

Наступного року колектив під керівництвом в Хуачен Ю, фахівець з інформатики Прінстонського університету, намагався вдосконалити хеш-таблицю команди Бендера. «Ми дуже важко працювали, але не змогли цього зробити», — сказав Реньфей Чжоу, студент Університету Цінхуа в Пекіні та член команди Ю. «Тоді ми запідозрили, що їхня верхня межа [також] є нижньою межею» — найкраще, чого тільки можна досягти. «Коли верхня межа дорівнює нижній, гра закінчена, і у вас є відповідь». Незалежно від того, наскільки ви кмітливі, жодна хеш-таблиця не зможе зробити краще.

Команда Ю застосувала нову стратегію, щоб з’ясувати, чи було це передчуття правильним, обчисливши нижню межу з початкових принципів. По-перше, вони міркували, що для виконання вставки або видалення хеш-таблиця — або, насправді, будь-яка структура даних — має отримати доступ до пам’яті комп’ютера певну кількість разів. Якби вони змогли визначити мінімальну кількість разів, необхідних для використання простору, вони могли б помножити це на час, необхідний для доступу (константа), даючи їм нижню межу часу виконання.

Але якщо вони нічого не знали про хеш-таблицю (окрім того, що вона була ефективною), як дослідники могли визначити мінімальну кількість разів, необхідних для доступу до пам’яті? Вони вивели це виключно з теорії, використовуючи, здавалося б, непов’язану область під назвою теорія складності зв’язку, яка вивчає, скільки бітів потрібно для передачі інформації між двома сторонами. Зрештою команда досягла успіху: вони з’ясували, скільки разів структура даних має звертатися до своєї пам’яті за операцію.

Це було їхнє головне досягнення. Потім вони змогли встановити нижню межу часу виконання для будь-якої просторово-ефективної хеш-таблиці. І вони побачили, що це точно відповідає хеш-таблиці Бендера. «Ми [спочатку] думали, що це можна покращити», — сказав Чжоу. «Виявилося, що ми помилялися». Це, у свою чергу, означало, що проблема Петерсона нарешті була вирішена.

Окрім відповіді на запитання десятиліть давності, Кушмаул сказав, що дивовижною річчю доказу Ю є його загальність. «Їхня нижня межа стосується всіх можливих структур даних, у тому числі тих, які ще не винайшли». Це означає, що жоден метод зберігання даних не зможе перевершити хеш-таблицю Бендера з точки зору пам’яті та швидкості.

Занурившись у майбутнє

Незважаючи на безпрецедентну ефективність нової хеш-таблиці, навряд чи хтось найближчим часом спробує її створити. Його просто надто складно побудувати. «Алгоритм, швидкий у теорії, не обов’язково швидкий на практиці», — сказав Чжоу.

Кушмаул сказав, що такі розриви між теорією та практикою зберігаються протягом тривалого часу, тому що теоретики схильні ігнорувати постійні фактори. Час, потрібний для виконання операції, зазвичай множиться на число, певну константу, точне значення якої може бути несуттєвим з теоретичної точки зору. «Але на практиці константи дійсно мають значення», — сказав він. «У реальному світі коефіцієнт 10 є завершенням гри».

Фактичні хеш-таблиці все ще вдосконалюються в істотних аспектах, навіть якщо вони далеко не відповідають теоретичному ідеалу. Наприклад, нова хеш-таблиця називається АйсбергHT, побудований Бендером, Кушмаулом та іншими, набагато кращий за своїх попередників. За словами Кушмаула, вона вдвічі швидша за найбільш ефективну хеш-таблицю, доступну на сьогодні, і використовує втричі менше місця, ніж найшвидша хеш-таблиця.

Мітценмахер сподівається, що результат 2023 року незабаром може дати ще один вид вигоди: «Щоразу, коли ви отримуєте нову нижню межу — особливо ту, яка включає деякі нові методи — завжди є надія, що ви можете використовувати їх … для пов’язаних проблем».

Існує також інтелектуальне задоволення, яке приходить від усвідомлення того, що ви розв’язали складну та давню проблему, сказав комп’ютерний вчений Петро Індик Массачусетського технологічного інституту. «Коли ви переконаєтеся, що певні структури даних не можна вдосконалити, це може допомогти зосередити дослідницькі зусилля». Нарешті дослідники даних можуть відвернути свою увагу від виклику Петерсона та зосередитися на нових проблемах у теоретичній інформатиці, яких не бракує.