Ученые нашли оптимальный баланс хранения данных и времени | Журнал Кванта

Около 70 лет назад инженер IBM по имени Ханс Петер Лун незаметно изменил курс информатики. Лун уже получил несколько патентов, в том числе один на устройство, которое может измерять количество нитей ткани, а другой на руководство, которое определяет, какие коктейли можно приготовить из ингредиентов, имеющихся на вашей кухне. Но во внутренней статье IBM 1953 года он предложил новый метод хранения и извлечения информации, который сейчас встроен практически во все вычислительные системы: хеш-таблицу.

Хэш-таблицы представляют собой основной класс структур данных. Они предлагают особенно удобный метод доступа и изменения информации в огромных базах данных. Но эта технология имеет неизбежный компромисс.

В 1957 бумаги опубликовано в Журнал исследований и разработок IBMУ. Уэсли Петерсон определил основную техническую проблему, которую создают хеш-таблицы: они должны быть быстрыми, а это означает, что они могут быстро получить необходимую информацию. Но они также должны быть компактными и использовать как можно меньше памяти. Эти двойные цели фундаментально противоречат друг другу. Доступ к базе данных и ее изменение можно выполнить быстрее, если в хеш-таблице больше памяти; и операции становятся медленнее в хеш-таблицах, которые занимают меньше места. С тех пор, как Петерсон поставил перед собой эту задачу, исследователи пытались найти наилучший баланс между временем и пространством.

Ученые-компьютерщики теперь математически доказали, что нашли оптимальный компромисс. Решение пришло от пара недавнего бумага которые дополняли друг друга. «Эти статьи решают давний открытый вопрос о наилучшем возможном пространственно-временном компромиссе, приводя к глубоко неожиданным результатам, которые, как я ожидаю, окажут значительное влияние на многие годы вперед», — сказал он. Майкл Митценмахер, ученый-компьютерщик из Гарвардского университета, не принимавший участия ни в одном исследовании.

«Я бы определенно сказал, что это большое дело», — добавил Расмус Пах, ученый-компьютерщик из Копенгагенского университета. «Многие люди работали над этой проблемой, пытаясь увидеть, насколько можно сжать пространство, одновременно выполняя операции с минимальными затратами времени. Это тот вопрос, который мне бы хотелось решить».

Создание хеша из этого

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

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

В качестве чрезвычайно упрощенного примера возьмем Оксфордский словарь английского языка, в котором есть определения более чем 600,000 XNUMX слов. Если цифровое издание использует хеш-таблицу, вы можете просто использовать данное слово в качестве ключа и сразу перейти к определению. Без хеш-таблицы словарь, скорее всего, будет использовать гораздо более медленный механизм поиска, использующий процесс исключения, чтобы в конечном итоге прийти к запрошенному определению. И хотя хеш-таблица может найти любое слово за постоянный промежуток времени (обычно за небольшую долю секунды), время поиска для других методов может увеличиваться по мере увеличения количества слов в словаре. Хэш-таблица также предлагает еще одно преимущество: она может сохранять словарь динамичным, что позволяет легко вставлять новые слова и удалять устаревшие.

Исследователи потратили десятилетия на создание хеш-таблиц, которые пытаются максимизировать скорость и минимизировать объем памяти. В 20-м веке решения, как правило, приносили значительную выгоду только в одном аспекте, во времени или пространстве. Затем в 2003 году исследователи показал что теоретически возможно совершить значительный скачок эффективности одновременно и во времени, и в пространстве. Однако исследователям потребуется еще два десятилетия, чтобы найти идеальный баланс между ними.

Перетасовка данных

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

Чтобы оценить хеш-таблицу, которую они придумали, группа построила кривую компромисса — график, на котором на одной оси отложено время на операцию (вставка или удаление), а на другой — пространство, занимаемое памятью. Но этот граф определяет пространство особым образом: из-за особенностей построения хеш-таблиц требуется больше памяти, чем минимум, необходимый для хранения заданного набора элементов. Ученые-компьютерщики называют это дополнительное пространство «потерянными битами», хотя на самом деле они не тратятся впустую и в некоторой степени необходимы. Пространственная ось на кривой компромисса измеряет количество потерянных бит на ключ.

Анализируя кривую компромисса, исследователи могут определить максимально возможное время для хеш-таблицы, занимающей заданный объем пространства. Они также могут перевернуть вопрос, чтобы определить наименьшее возможное пространство для заданного времени работы. Обычно небольшое изменение одной переменной приводит к небольшому изменению другой, сказал он. Уильям Кушмаул, ученый-теоретик в области информатики из Гарварда и соавтор статьи 2022 года. «Если вы удвоите время, возможно, вы вдвое сократите количество потерянных бит на ключ».

Но в случае с разработанной ими хеш-таблицей дело обстоит иначе. «Если вы немного увеличите время, количество потерянных битов на ключ уменьшится экспоненциально», — сказал Кушмаул. Кривая компромисса была настолько крутой, что буквально зашкаливала.

Команда построила свою хеш-таблицу из двух частей. У них была первичная структура данных, в которой элементы хранятся вообще без каких-либо лишних битов, и вторичная структура данных, которая помогает запросу запроса найти искомый элемент. Хотя группа не изобрела понятие вторичной структуры данных, они сделали важнейшее открытие, которое сделало возможной их сверхэффективную хеш-таблицу: общая эффективность использования памяти структуры зависит от того, как первичная структура организует свои хранимые элементы.

Основная идея заключается в том, что каждый элемент первичной структуры имеет предпочтительные места хранения — лучшее, второе, третье и так далее. Если элемент находится в лучшем месте, ему присваивается номер 1, и этот номер сохраняется во вторичной структуре данных. В ответ на запрос вторичная структура предоставляет только число 1, которое указывает точное местоположение элемента в первичной структуре.

Если элемент находится на 100-м месте, вторичная структура данных присоединяет число 100. А поскольку система использует двоичный код, она представляет число 100 как 1100100. Конечно, для хранения числа 1100100 требуется больше памяти, чем для хранения 1. — номер, присваиваемый предмету, когда он находится в лучшем месте. Подобные различия становятся существенными, если вы храните, скажем, миллион предметов.

Таким образом, команда поняла, что если вы постоянно перемещаете элементы первичной структуры данных в их более предпочтительные места, вы можете значительно сократить объем памяти, потребляемой вторичной структурой, без необходимости увеличения времени выполнения запросов.

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

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

Обречен на успех

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

Команда Ю применила новую стратегию, чтобы выяснить, верна ли эта догадка, рассчитав нижнюю границу на основе основных принципов. Во-первых, они рассудили, что для выполнения вставки или удаления хеш-таблица — или, по сути, любая структура данных — должна обращаться к памяти компьютера некоторое количество раз. Если бы они могли определить минимальное количество раз, необходимое для создания компактной хеш-таблицы, они могли бы умножить это время на время, необходимое для каждого доступа (константа), что дало бы им нижнюю границу времени выполнения.

Но если они ничего не знали о хеш-таблице (за исключением того, что она была компактной), как исследователи могли вычислить минимальное количество раз, необходимое для доступа к памяти? Они вывели его исключительно из теории, используя, казалось бы, несвязанную область, называемую теорией сложности коммуникации, которая изучает, сколько битов требуется для передачи информации между двумя сторонами. В конце концов, команде это удалось: они выяснили, сколько раз структура данных должна обращаться к своей памяти за одну операцию.

Это было их главное достижение. Затем они смогли установить нижнюю границу времени выполнения для любой компактной хеш-таблицы. И они увидели, что она точно соответствует хеш-таблице Бендера. «Мы думали, что [сначала] его можно улучшить», — сказал Чжоу. «Оказалось, что мы ошибались». Это, в свою очередь, означало, что проблема Петерсона наконец-то решена.

По словам Кушмауля, помимо ответа на вопрос, возникший десятилетия назад, в доказательстве Ю удивительной особенностью является его универсальность. «Их нижняя граница применима ко всем возможным структурам данных, включая те, которые еще не изобретены». Это означает, что ни один метод хранения данных никогда не сможет превзойти хэш-таблицу Бендера с точки зрения памяти и скорости.

Хэширование в будущее

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

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

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

Митценмахер надеется, что результат 2023 года может вскоре принести пользу другого рода: «Всякий раз, когда вы получаете новую нижнюю границу — особенно ту, которая включает в себя какие-то новые методы — всегда есть надежда, что вы сможете использовать их… для решения смежных задач».

«Есть также интеллектуальное удовлетворение, которое приходит от осознания того, что вы решили сложную и давнюю проблему», — сказал ученый-компьютерщик. Петр Индик Массачусетского технологического института. «Если вы уверены, что определенные структуры данных невозможно улучшить, это может помочь сосредоточить исследовательские усилия». Наконец, исследователи данных могут отвлечься от задачи Петерсона и сосредоточиться на новых проблемах теоретической информатики, недостатка в которых нет.