База данных всегда была центром приложения. Если вы создаете веб-приложение, база данных является важным компонентом вашего приложения. Вам нужно вывести данные из хранилища. Вам необходимо иметь механизм хранения, который хранит единый источник достоверной информации о состоянии вашего приложения. С огромным объемом данных, которые мы можем потреблять в Интернете, создание эффективного алгоритма для этого хранилища данных имеет важное значение.
В 1970 году исследователи базы данных оптимизировали алгоритм базы данных, чтобы минимизировать случайный доступ к диску. Пятьдесят лет спустя мы хотим оптимизировать механизм хранения на диске и уменьшить произвольный доступ к памяти. Поэтому, чтобы обеспечить удобство работы пользователей и более точное прогнозирование данных, мы хотим оптимизировать наш механизм хранения на основе определенных критериев.
По каким критериям мы обычно оптимизируем наш механизм хранения?
Когда я начал свой путь к распределенным системам, я увидел статью под названием «Гипотеза RUM». В статье говорится, что мы обычно хотим оптимизировать наш алгоритм и структуру данных для механизма хранения в разделах «Оптимизация для чтения», «Оптимизация для записи (обновления)» и «Оптимизация для памяти».
Хотя вы хотите иметь идеальное решение для повышения эффективности чтения, обновления и памяти в вашем механизме хранения, у нас не может быть всех трех. Нам нужно будет пойти на компромисс с нашим дизайном. Если мы хотим иметь механизм хранения, оптимизированный для чтения, мы жертвуем обновлением и памятью. Эта гипотеза похожа на знаменитую теорему CAP.
В этой статье я хочу подробнее рассказать о накладных расходах RUM (чтение, обновление, память) и некоторых примерах хранения данных, оптимизированных для одного из трех.
Прочитать заголовок
Накладные расходы на чтение - это общий объем данных для чтения ваших основных данных. Если место, где вы храните свои данные, случайно, вам нужно выполнить больше операций, чтобы найти данные. Если вы хотите оптимизировать чтение, вам нужно будет создать индекс вспомогательных данных для быстрого поиска. Эти вспомогательные данные являются причиной накладных расходов на чтение.
Если вы создаете QuadTree для более быстрого чтения в ближайшем месте, общий объем данных, которые вы читаете, будет состоять из всех четырехугольников, которые вы просматриваете, и соседних данных, которые вы получаете из базы данных. Вам необходимо прочитать все эти данные, чтобы получить это близлежащее местоположение. Накладные расходы на чтение можно измерить отношением всех данных к первичным данным, которые вы хотите найти.
Накладные расходы на обновление - это объем доступа, необходимый для обновления ваших первичных данных. Накладные расходы на обновление возникают, когда механизму хранилища необходимо выполнить запись в любое другое место данных, чтобы полностью обновить ваши предварительные данные. Например, если вы хотите обновить базу данных, содержащую индекс, вам необходимо выполнить обновление индекса вместе с вашей базой данных.
Накладные расходы на память
Накладные расходы на память - это объем памяти, занятой при хранении ваших первичных данных. Сюда входит необходимость хранить вспомогательные данные наряду с основными. Часто это компромисс в структуре данных между скоростью и памятью. Вы будете занимать память в результате оптимизации для более быстрого чтения и записи. Занятая вами память - это дополнительная память для хранения первичных данных.
Давайте подумаем о некоторых сценариях, почему мы не можем оптимизировать все три одновременно. Чтобы лучше проиллюстрировать компромисс между тремя, давайте рассмотрим системы и гипотезы, оптимизированные для всех трех спектров.
Оптимизировано для чтения
Оптимизированное для чтения обычно выполняло небольшие накладные расходы на чтение. Примером будет индекс на основе хэша. Вы можете создать индекс на основе хешей поверх своего механизма хранения, чтобы ускорить чтение. Для чтения вам нужно вызвать хеш-функцию, чтобы найти первичные данные. Однако вам также потребуется обновить ваши первичные данные и хеш-функцию, когда дело доходит до обновления. Иногда вам нужно перераспределить хэш-функцию, чтобы предотвратить любые коллизии. В этом случае пострадает обновление. Предположим, вы учитываете конфликты в своей хеш-функции. В этом случае вам нужно будет создать накладные расходы для вашей памяти, чтобы сохранить дополнительный пустой блок, чтобы уменьшить вероятность коллизии. В этом случае страдает и ваша память.
Некоторыми примерами системы хранения, оптимизированной для чтения, являются хэш-индекс для постоянного доступа на чтение, а также B-деревья и списки пропусков для логарифмического доступа по времени.
Оптимизация обновлений означает, что вы хотите, чтобы накладные расходы на обновление были как можно меньше. Чтобы уменьшить накладные расходы на обновление, мы можем хранить обновленные данные в некотором условном вспомогательном пространстве, таком как буфер, который в конечном итоге будет сброшен в объемные данные. Мы будем добавлять каждое обновление, эффективно формируя постоянно увеличивающийся журнал.
Хотя мы минимизируем накладные расходы на обновление, мы увеличиваем накладные расходы на чтение и объем памяти для хранения буфера. Если мы хотим прочитать наши данные, нам может потребоваться выполнить несколько слияний, чтобы получить текущее состояние данных. Нам также необходимо реорганизовывать наши данные каждый раз, когда буфер сбрасывается в основное хранилище. Если мы реорганизуем наши данные, чтобы минимизировать накладные расходы на чтение, мы увеличим накладные расходы на обновление.
Некоторыми примерами систем, оптимизированных для обновления, являются LSM Tree, Partitioned B Trees и FD Tree.
Оптимизирован для памяти
Как и оптимизация чтения и обновления, оптимизация памяти пытается уменьшить накладные расходы памяти за счет минимизации памяти, необходимой для доступа и обновления первичных данных. Система обычно пытается оптимизировать их, сжимая данные или сохраняя данные в плотном массиве. Чтобы выполнить чтение, нам нужно просмотреть все значения или распаковать данные. Чтобы выполнить обновление, нам нужно распаковать и обновить данные.
Некоторыми примерами приложений, оптимизирующих память, являются структуры индексов с потерями, такие как фильтры Блума, скетчи Count-min, кодирование с потерями и растровые изображения.
Если мы хотим оптимизировать все три, значит ли это, что мы обречены? Приложение становится более сложным, и потребность в доступе, обновлении и хранении данных выше, чем раньше.
Создание методов доступа к RUM
Хотя компромиссы существуют, многие приложения механизма хранения пытаются проявить творческий подход, уравновешивая компромиссы RUM с изменением оборудования, шаблонов рабочих нагрузок и приложений.
Таким образом, варианты методов управления данными, которые могут создать динамический способ оптимизации метода доступа. Например, мы можем построить стратегию множественного доступа, частично перемещаясь в пространстве RUM и охватывая все пространство в совокупности. Мы также можем настроить, чтобы уменьшить накладные расходы RUM в зависимости от шаблона доступа к данным.
Заключение
Хранение данных обычно оптимизируется на основе чтения, обновления и памяти. Вы можете использовать оптимизированную структуру данных, основанную на определенных свойствах, например, используя LSM Tree для оптимизации операции обновления и B-Tree для операции чтения. Однако вы не можете комбинировать эти три свойства для создания структуры данных, равной каждому аспекту RUM и всем накладным расходам.
Теперь, когда вы понимаете накладные расходы RUM, вы можете использовать эти знания для оценки баз данных, которые лучше всего подходят для вашего приложения и вашей рабочей нагрузки на данный момент. Гипотеза RUM дает вам основное эмпирическое правило для оценки накладных расходов на базу данных, которые вы будете использовать для своих новых приложений и их альтернатив.
Надеюсь, вы найдете объяснение полезным! Если у вас есть какие-либо другие вопросы, не стесняйтесь комментировать ниже, чтобы другие также могли у них поучиться. Если у вас есть какие-либо комментарии и другие новые открытия, пожалуйста, также упомяните их здесь, чтобы поучиться у вас!
Ресурс
Есть несколько отличных ресурсов о RUM Conjecture. Мы едва касаемся алгоритма, лежащего в основе современных систем хранения. Если вам интересно узнать больше, ознакомьтесь с приведенными ниже ресурсами!
Первоначально опубликовано на https://edward-huang.com.
