Гипотеза RUM утверждает, что мы не можем разработать метод доступа к системе хранения, который был бы оптимален во всех следующих трех аспектах — чтение, обновление и память. Гипотеза предполагает, что мы всегда должны торговать одним, чтобы сделать два других оптимальными, и это делает три составляющих конкурирующего треугольника, очень похожего на известную теорему CAP.
Метод доступа
Доступ к данным относится к возможности доступа и извлечения данных, хранящихся в системе хранения, управляемой дополнительным механизмом хранения. Как правило, система хранения разрабатывается так, чтобы быть оптимальной для обслуживания нишевого варианта использования, и достигается это путем тщательного и разумного определения требований к памяти и дисковому хранилищу, определения хорошо структурированного шаблона доступа и извлечения, проектирования структур данных для первичных и вспомогательных данных и выбора. дополнительные методы, такие как сжатие, шифрование и т. д. Эти решения определяют и в некоторой степени ограничивают возможные способы чтения и обновления данных в системе механизмом хранения.
РУМ Накладные расходы
Идеальной системой хранения будет та, которая имеет метод доступа, обеспечивающий наименьшие накладные расходы на чтение, минимальную стоимость обновления и не требующий дополнительной памяти или места для хранения по сравнению с основными данными. В реальном мире добиться этого почти невозможно, и это то, что продиктовано этой гипотезой.
Чтение служебных данных
Накладные расходы на чтение возникают, когда механизм хранения выполняет чтение вспомогательных данных для получения требуемых основных данных. Обычно это происходит, когда мы используем вспомогательную структуру данных, такую как вторичный индекс, для ускорения чтения. Чтения, происходящие в этой вспомогательной структуре, составляют накладные расходы на чтение.
Накладные расходы чтения измеряются с помощью усиления чтения и определяются как отношение между общим объемом считанных данных (основные + вспомогательные) и объемом основных данных, предназначенных для чтения.
Обновить накладные расходы
Издержки обновления возникают, когда механизм хранения выполняет запись вспомогательных данных или некоторых немодифицированных основных данных вместе с предполагаемыми обновлениями основных данных. Типичным примером накладных расходов на обновление являются записи, которые происходят во вспомогательной структуре, такой как вторичный индекс, наряду с записью, происходящей в предполагаемых основных данных.
Накладные расходы обновления измеряются с помощью расширения записи и определяются как отношение между общим объемом записанных данных (основные + вспомогательные) и объемом основных данных, предназначенных для обновления.
Накладные расходы памяти
Накладные расходы памяти возникают, когда система хранения использует вспомогательную структуру данных для ускорения чтения, записи или обслуживания общих шаблонов доступа. Это хранилище является дополнением к потребностям хранения основных данных.
Накладные расходы памяти измеряются с помощью увеличения пространства и определяются как соотношение между пространством, используемым для вспомогательных и основных данных, и пространством, используемым основными данными.
Гипотеза
Гипотеза RUM формально утверждает, что
Метод доступа, который может установить верхнюю границу для двух из накладных расходов на чтение, обновление и память, также устанавливает нижнюю границу для третьего накладных расходов.
Это не жесткое правило, которому следуют, и, следовательно, это не теорема, а гипотеза — широко наблюдаемая, но не доказанная. Но мы можем смело помнить об этом при проектировании следующей большой системы хранения, обслуживающей прецедент.
Классификация систем хранения
Теперь, когда мы рассмотрели накладные расходы RUM и гипотезу RUM, мы рассмотрим примеры систем хранения, которые относятся к одному из трех типов.
Чтение оптимизировано
Системы хранения, оптимизированные для чтения, предлагают очень низкие накладные расходы на чтение, но требуют некоторого дополнительного вспомогательного пространства для достижения необходимой производительности, что опять же достигается за счет обновлений, необходимых для синхронизации вспомогательных данных с основными данными, что увеличивает накладные расходы на обновление. Когда обновления основных данных становятся частыми, производительность системы хранения, оптимизированной для чтения, падает.
Прекрасным примером системы хранения, оптимизированной для чтения, является та, которая поддерживает точечные индексы, также называемые индексами на основе хэшей, предлагая постоянный доступ во времени. В эту категорию также попадают системы, обеспечивающие доступ к логарифмическому времени, такие как B-Tree и Skiplists.
Обновление оптимизировано
Системы хранения, оптимизированные для обновления, предлагают очень низкие накладные расходы на обновление, поскольку обычно используют вспомогательное пространство, содержащее разностные данные (дельта), и сбрасывают их поверх основных данных в массовой операции. Необходимость наличия вспомогательных данных для отслеживания дельты для выполнения массового обновления увеличивает нагрузку на память.
Несколькими примерами систем, оптимизированных для обновления, являются LSM-деревья, разделенные B-деревья и FD-дерево. Эти структуры предлагают очень хорошую производительность для системы с большим количеством обновлений, но страдают от повышенных накладных расходов на чтение и пространство. При чтении данных из дерева LSM движку необходимо выполнить чтение на всех уровнях, а затем выполнить разрешение конфликтов, а поддержка самих уровней данных требует огромных накладных расходов.
Оптимизация памяти
Память Оптимизированные системы хранения предназначены для минимизации дополнительной памяти, необходимой для доступа и обновления основных данных. Для оптимизации памяти системы обычно используют сжатие основных данных и вспомогательных хранилищ или допускают некоторую частоту ошибок, таких как ложные срабатывания.
Несколько примеров систем с оптимизацией памяти — это структуры индексов с потерями, такие как Фильтры Блума, Скетчи с минимальным количеством, кодирование с потерями и разреженные индексы. Сохраняя основные или вспомогательные данные в сжатом виде, чтобы эффективно использовать память, система оказывает негативное воздействие на операции записи и чтения, поскольку теперь они дополнительно выполняют сжатие и распаковку, добавляя накладные расходы на обновление и чтение.
Примеры системы хранения для гипотезы RUM
Блочное кластерное индексирование
Кластерное индексирование на основе блоков удобно располагается между этими тремя типами оптимизированных систем. Он не эффективен для чтения, но также эффективен для обновлений и памяти. Он строит очень короткое дерево для своих вспомогательных данных, сохраняя несколько указателей на страницы, и, поскольку данные кластеризуются, т.е. сами основные данные хранятся в индексе, система не переходит к извлечению основных данных из основного хранилища и следовательно, обеспечивает минимальные накладные расходы на чтение.
Быть адаптивным RUM
Системы хранения всегда были жесткими в отношении того, на какие варианты использования они нацелены. приложение, рабочая нагрузка и аппаратное обеспечение должны определять, как мы получаем доступ к нашим данным, а не ограничения наших систем. Системы хранения могут быть спроектированы как адаптивные для RUM, и они должны обладать возможностью настройки для уменьшения накладных расходов на RUM в зависимости от схемы доступа к данным и знаний о вычислениях. RUM Адаптивные системы хранения — это часть обсуждения, о которой мы поговорим в другой раз.
Вывод
Всегда будут компромиссы между чтением, обновлением и памятью при выборе одной системы хранения вместо других; Гипотеза RUM облегчает и в какой-то степени формализует весь процесс. Хотя это всего лишь предположение, оно все же помогает нам устранить неоднозначность и принять обоснованное, лучшее и жизнеспособное решение, которое будет иметь большое значение.
Это эссе в значительной степени основано на оригинальной исследовательской работе, посвященной гипотезе RUM.
