Здесь мы опишем основные метрики производительности, которые используются для характеристики структур данных ключ-значение. Поскольку метрики частично зависят от основного оборудования, мы начнём с рассмотрения иерархии памяти/хранилища и её важности для проектирования структур данных.

2.1 Иерархия памяти

Иерархия памяти — это последовательность устройств или уровней памяти, от самых быстрых — например, регистров и кэша — до самых медленных — например, памяти и диска (Manegold, 2009). Они дополняют друг друга по размеру, стоимости и скорости доступа. Как правило, хотя бы один уровень иерархии памяти и хранилища является постоянным (особенно у файловых систем и систем данных), поэтому данные не будут потеряны при потере питания или выключении машины. Кроме того, один уровень иерархии памяти достаточно велик, чтобы вместить все данные, необходимые для конкретного приложения. Данные передаются между уровнями туда и обратно по мере поступления запросов, вставки новых данных, удаления или обновления старых.

Поскольку разные типы памяти работают с совершенно разной скоростью, при перемещении данных к процессору из очень медленного слоя памяти, например с диска, общая стоимость использования определённой структуры данных уступает стоимости перемещения. Однако большие объёмы передачи данных из более медленной памяти в более быструю частично компенсируют разницу в скорости. Например, единица передачи данных из памяти в быструю кэш-память составляет несколько байт, в то время как единица передачи данных с диска в основную память может составлять несколько килобайт. Больший размер потенциально снижает необходимость в большом количестве пересылок с диска в память. Затраты на все остальные перемещения данных на более высоких (т. е. более быстрых) уровнях иерархии памяти по сравнению с этим ничтожна. Как правило, современный процессор, работающий на частоте более 1 ГГц, используется не полностью, поскольку ожидает данных из памяти с произвольным доступом (что может занимать десятки наносекунд) или с диска (что может занимать тысячи или миллионы наносекунд). Таким образом, выбор структуры данных направлен на минимизацию количества обращений к самому медленному уровню.

По этой причине при обсуждении моделирования и проектирования в этой книге учитываются эти свойства производительности и всегда предполагаются два абстрактных уровня иерархии памяти (Aggarwal и Vitter, 1988): один из них медленный, но может рассматриваться как имеющий по сути бесконечную ёмкость, а другой — гораздо более быстрый, но с ограниченной ёмкостью. Этот подход охватывает пару памяти с произвольным доступом и диска, но он также может охватывать любые два уровня памяти, которые имеют значительную разницу в задержке доступа и стоимости (например, на 1-3 порядка).

2.2 От Чтения/Обновления
к Чтению, Обновлению, Хранению:
затраты на память и пространство

Чтобы сравнить конструкции структур данных и решить, какую из них использовать в тех или иных условиях, сначала нужно определить соответствующие метрики. Наиболее распространёнными из них являются производительность чтения и производительность обновления (Brodal и Fagerberg, 2003; Yi, 2009; Yi, 2012).

Чтение и обновление. Стоимость чтения определяет, насколько быстро мы можем получить данные, а стоимость обновления описывает, насколько быстро мы можем вставить новые данные или изменить существующие. Таким образом, эти затраты в совокупности описывают сквозную производительность, которую обеспечивает конструкция структуры данных для данной рабочей нагрузки. Такие затраты можно измерить в терминах (ожидаемого) времени отклика или, как правило, в терминах количества данных, которые необходимо переместить для завершения операции. Сокращение любого из этих показателей часто также увеличивает пропускную способность (количество операций в секунду).

Чтение, обновление и память (RUM — read, update, memory). Размер данных — это дополнительная метрика, которая имеет решающее значение на практике. Эта метрика важна потому, что дисковое пространство или пространство памяти для хранения структур данных не является ни дешёвым, ни неограниченным.

Исторически сложилось так, что при проектировании структур данных учитывалась только производительность чтения и обновления, а размер данных игнорировался. Это предположение возникло в те времена, когда диск использовался в качестве вторичного хранилища и был настолько дешевле памяти, что стоимость хранения считалась несущественной, а главным фактором была производительность хранения (Gray и Putzolu, 1986). С тех пор иерархия хранения данных пополнилась различными устройствами, включая твердотельные диски (SSD), диски с черепичной магнитной записью (SMR), энергонезависимую память (NVM) и другие устройства. Новые носители информации могут быть либо дорогими в пересчёте на байт и быстрыми, либо дешёвыми, но медленными (Athanassoulis, 2014). Иногда за более высокую производительность приходится платить значительными энергозатратами (Shehabi и др., 2016). Твердотельные накопители на базе флэш-памяти демонстрируют асимметрию чтения/записи, когда запись обычно в 1-3 раза затратнее чтения. В то же время такие устройства могут поддерживать несколько одновременных доступов, прежде чем будет достигнута максимальная пропускная способность устройства (Papon и Athanassoulis, 2021a; Papon и Athanassoulis, 2021b). В современном мире, насыщенном датчиками, генерирование данных опережает скорость поставки устройств хранения, что приводит к нехватке ёмкости для хранения данных (Bhat, 2018; Hilbert и López, 2011; Spectra, 2017).

В целом всё более широкое использование систем хранения данных с более высокой ёмкостью и эффективным произвольным доступом сделало анализ соотношения памяти и производительности (затраты на чтение/обновление) важным фактором при проектировании и оптимизации структур данных (Athanassoulis и др., 2016; Dong и др., 2017; Zhang и др., 2016).

Хранение и память не бесплатны, поэтому при оценке эффективности структуры данных следует также учитывать её площадь и стоимость.

2.3 Затраты на производительность
операций чтения и обновления и память

Теперь мы формально определим затраты на чтение, обновление и память (ЧОП). Сначала мы определим три величины, которые помогут отразить затраты по отдельности. Они определяются как показатель роста стоимости по сравнению с минимально возможным.

Под затратами на чтение мы понимаем рост стоимости чтения при каждой операции поиска. Это соотношение между размером метаданных (обычно в индексе) и данных, с которыми должна работать операция, делённое на фактический размер необходимых данных. Другими словами, она отражает дополнительные данные, которые считываются при использовании конкретной структуры данных по сравнению с минимально возможными затратами, которую система могла бы достичь в идеальном мире, где система могла бы напрямую получить результат без каких-либо дополнительных усилий по поиску.
Под затратами на обновление мы понимаем рост стоимости записи при каждой операции обновления. Это соотношение между размером данных и метаданных, к которым был осуществлён доступ, и размером самих обновлённых данных.
Под затратами на память (хранение) мы понимаем рост стоимости пространства, используемое структурой данных. Это соотношение между суммарным размером данных, метаданных и потерянного из-за фрагментации пространства, делённое на размер базовых данных.

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

Рисунок 2.1: Пространство компромиссов ЧОП и широкая классификация проектов структур данных в соответствии с балансом ЧОП, который они поддерживают. Примитивы, лежащие в основе этих структур данных, обсуждаются в главе 3, а полные структуры описаны в главе 4.

Три вида накладных расходов ЧОП представляют собой трёхсторонний компромисс (Athanassoulis и др., 2016) между расходами на чтение, обновление и память (Brodal и Fagerberg, 2003; Yi, 2009; Yi, 2012; Hellerstein и др., 2002; Hellerstein и др., 1997; Wei и др., 2009).

На рисунке 2.1 концептуально показана широкая классификация конструкций структур данных в пространстве компромиссов ЧОП. Например, операция сканирования имеет высокую стоимость чтения, поскольку для возврата относительно небольшого количества данных требуется пройти всю таблицу — или хотя бы столбец (Abadi и др., 2013). Следовательно, рост стоимости чтения велика. Рост пространства, напротив, минимален или даже равен нулю, поскольку нет необходимости поддерживать метаданные.

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

В отличие от этого, типичный индекс с древовидной структурой (например, B+-дерево) использует дополнительное пространство для метаданных индекса, чтобы снизить стоимость чтения и обновления. Узлы индекса используются для перехода к узлу(ам) листа, в котором(ых) хранятся нужные данные. Кроме того, типичным является обмен места на эффективные обновления. Например, свободные места в листовых узлах B+-дерева, приводящие к среднему коэффициенту заполнения 67% (Ramakrishnan и Gehrke, 2002), увеличивают занимаемое пространство. Это гарантирует, что большинство вставок будут обновлять только одну страницу и не потребуют разбиения страницы на части. По сути, это обмен роста стоимости пространства на рост стоимости обновления. На рисунке 2.1 показаны аналогичные компромиссы, которые часто встречаются при проектировании структур данных, как описано в работах Athanassoulis и Idreos (2016) и Athanassoulis и др. (2016).

В целом, при проектировании структур данных каждый шаг является компромиссом. Каждая новая часть метаданных или любая структура, накладываемая на базовые данные, имеет прямое влияние на чтение, обновление или увеличение объёма памяти.

2.4 От ЧОП к сложному компромиссу

Стоимость ЧОП предлагают высокоуровневую метрику того, как ведут себя широкие классы структур данных. Чтобы получить более полную картину, которая необходима для проектирования структур данных с учетом аппаратных и рабочих нагрузок, нам нужно уточнить эти метрики. Для этого мы рассмотрим все возможные операции, которые могут составлять рабочую нагрузку структуры данных. В частности, производительность чтения зависит от точного шаблона доступа. Точечный запрос, запрашивающий значение, связанное с одним ключом, отличается от запроса диапазона, запрашивающего набор ключевых значений от младшего ключа до старшего. Аналогично, при записи операция вставить отличается от обновить или удалить. Хотя ЧОП классифицирует все модификации как обновления, затраты на них могут отличаться в разных структурах данных. Например, в B+-дереве операция вставить должна хранить новую пару ключ-значение, что может вызвать операцию сортировки в узле листа, в то время как обновить может изменить значение без нарушения порядка ключей, а удалить может просто пометить ключ как логически удаленный.

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

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

Точечный запрос: В точечном запросе необходимо получить одну запись данных по заданному ключу. Общая стоимость страниц включает не только страницу, содержащую целевую запись данных, но и все индексированные страницы данных, которые нам нужно прочитать из-за проектирования структуры данных. Аналогично, если структура данных не дает прямого доступа к целевым страницам данных, то, скорее всего, сначала нужно прочитать дополнительные страницы данных, чтобы найти целевую запись данных. Эти компоненты включены в общую стоимость чтения.

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

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

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

- Полное сканирование требует доступа ко всем страницам данных. Они могут выиграть от специального типа индексирования, называемого фильтрацией (раздел 3.3.2), который позволяет частично пропускать данные. Кроме того, на них влияет проектировочный выбор размещения базовых данных, и они могут быть улучшены за счет низкоуровневых инженерных оптимизаций для максимально быстрого потребления данных. К таким оптимизациям относятся векторизация (Boncz и др., 2008), предварительная выборка (Ramakrishnan и Gehrke, 2002) или использование инструкций ОКМД (одиночный поток команд, множественный поток данных) (SIMD — single instruction/multiple data) (Polychroniou и др., 2015; Willhalm и др., 2009).

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

Удалить: Операция удаления удаляет запись типа «ключ-значение», заданную входным ключом. Удаление записи значения ключа может привести к фрагментации, что, в свою очередь, требует наличия механизма для возврата места, занятого удаленными данными. Такое отложенное удаление может привести к дополнительному увеличению пространства, а также к проблемам с конфиденциальностью, если недействительные данные не будут физически удалены.

Обновить: операция обновления изменяет значение конкретной записи ключа-значения. Обновления часто занимают меньше времени, чем вставки или удаления, поскольку организация ключей не меняется.

Характеристика запросов с коротким диапазоном. Для того чтобы классифицировать запрос как запрос короткого диапазона, мы рассматриваем компромисс между случайным и последовательным доступом. В частности, мы считаем, что при случайном доступе точечный запрос получает доступ примерно к одной странице данных, в то время как запрос короткого диапазона затрачивает примерно столько же времени на последовательный доступ к данным. Следуя анализу Kester и др. (2017), мы считаем, что задержка случайного доступа к странице размером P составляет L единиц времени, а пропускная способность последовательного чтения — BW. Если предположить, что точечный запрос выполняет один случайный доступ, а его задержка равна L, то запрос диапазона будет считаться коротким, если он имеет такую же стоимость.

Объем данных, которые мы можем последовательно прочитать за L единиц P времени, равен BW⋅L, что занимает (BW⋅L)/P страниц. Например, если принять размер страницы 4 КБ, который распространён в современных системах, то при работе в режиме памяти с пропускной способностью чтения 100 ГБ/с и задержкой доступа 180 нс, запрос короткого диапазона будет иметь доступ к (100 ГБ/с) – 180нс/4КБ ≈ 4,7 страницам памяти (за 180 нс), или (100 ГБ/с) – 180 нс/64 Б ≈ 300 строкам кэша (по 64 байта). Если мы рассмотрим твердотельный накопитель с пропускной способностью чтения 1 ГБ/с, задержкой 50 мкс и размером страницы 2 КБ, то соответствующий короткий интервал составит (1 ГБ/с) – 50 мкс/2 КБ ≈ 26 страниц (за 50 мкс). Наконец, для традиционного жесткого диска с пропускной способностью чтения 150 МБ/с, задержкой доступа 4 мс и размером страницы 4 КБ, короткая дальность составляет (150 МБ/с) – 4 мс/4 КБ ≈ 150 страниц за 4 мс. Поскольку устройства развиваются, можно использовать эмпирическое правило (BW⋅L)/P для количественной оценки того, насколько данные (или единицы памяти, такие как страницы, строки кэша и т. д.) могут быть доступны последовательно за то же время, которое необходимо для выполнения точечного запроса. Таким образом, такой объём данных характеризует запрос малого радиуса действия.

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

2.5 Краткое содержание главы

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

2.6 Вопросы

Чем операция обновления отличается от операции чтения по количеству перемещений данных, если предположить, что данные находятся в медленной памяти (например, на диске)?

Набросок ответа: Мы предполагаем, что соответствующие данные находятся на одной странице. И операция чтения, и операция обновления должны прочитать страницу данных. Однако операция обновления может потребовать реорганизации страницы данных. Кроме того, обновленная страница в конечном итоге должна быть записана на диск, чтобы обновление сохранилось.

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

2. Переходя от метрик производительности ЧОП к метрикам сложного компромисса, мы различаем вставки, удаления и обновления. Как эти различные модификации могут по-разному обрабатываться в отсортированном массиве?

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

3. Для отсортированного массива запросы короткого диапазона и точечные запросы имеют схожие характеристики затрат на вычисления и перемещения данных? А как насчёт несортированных массивов?

Набросок ответа: Любая отсортированная структура данных будет иметь схожие затраты на запросы к точке и диапазону, потому что, скорее всего, весь короткий диапазон будет присутствовать в одной и той же секции массива (и, следовательно, на одной и той же странице). Для несортированного массива запрос короткого диапазона может потребовать сканирования всего массива.

2.7 Дополнительные материалы

Управление данными на новом оборудовании хранения данных. В этой главе мы обсуждаем взаимодействие методов доступа к данным с аппаратным обеспечением и, в частности, с иерархией памяти. Более глубокое понимание можно получить, изучив учебные пособия и опросы, в которых обсуждается влияние новых устройств хранения на управление данными и индексирование флэш-устройств, авторы Koltsidas и Viglas (2011), а также более широкий класс энергонезависимой памяти, автор Viglas (2015). Более того, устройства хранения можно настроить для поддержки конкретных характеристик рабочей нагрузки, написав их код с помощью приложения, как описано в руководстве Lerner и Bonnet (2021).
Примеры. Athanassoulis и Ailamaki (2014), Na и др. (2011), Roh и др. (2011), и Thonangi и др. (2012) предложили древовидные индексы, использующие базовый параллелизм устройств хранения, а Jin и др. (2011), Li и др. (2010), а также Papon и Athanassoulis (2023) предлагают способы решения проблемы асимметрии чтения/записи флэш-накопителей, а Kang и др. (2007) стремятся агрессивно эксплуатировать местонахождение.

Кроме того, Athanassoulis и др. (2015), Debnath и др. (2010), Lim и др. (2011) и Nath и Kansal (2007) предложили хранилища данных с ключами-значениями, адаптированные к флэш-памяти за счет использования параллелизма и эффективного случайного доступа, при этом соблюдая ограничения, связанные с затратами на запись и более высокой стоимостью по сравнению с традиционными дисками. Другие примеры управления данными на флеш-устройствах были рассмотрены в работе Athanassoulis (2010).
Управление данными на новом вычислительном оборудовании.Помимо эволюции оборудования хранения данных, кардинально меняется и вычислительное оборудование. Исследования по многоядерным процессорам и глубоким иерархиям памяти (Ailamaki и др., 2017; Ross, 2021), графическим процессорам для управления данными (Paul и др., 2021), специализированному аппаратному обеспечению на базе FPGA для управления данными (Fang и др., 2020); Istvánи др., 2020) и системы хранения в эпоху RDMA (Remote Direct Memory Access) (Ma и др., 2022) могут помочь понять влияние новых тенденций в области аппаратного обеспечения на методы доступа к данным, их хранение и управление данными.
Примеры. Ailamaki и др. (1999) обнаружили, что системы, ориентированные на строки, сталкиваются с очень большим количеством зависаний данных в кэш-памяти. Основываясь на этом выводе, Ailamaki и др. (2002) представили новую схему плетеной страницы, которая уменьшает количество задержек в кэш-памяти за счет группировки элементов, принадлежащих одному столбцу. Boncz и др. (1999) и Boncz и др. (2005) предложили новую вертикально фрагментированную компоновку физических данных для решения проблемы узкого места в памяти. Кроме того, Chen и др. (2001) предложили предварительную выборку из кэша как метод оптимизации индексов для основной памяти, Ross (2004) улучшил условия выбора, избежав дорогостоящих операторов if, а Manegold и др. (2002a) построили модель затрат для резидентного выполнения в кэше. Другие работы по буферизации, доступу на основе блоков и другим оптимизациям следуют аналогичным принципам (Lam и др., 1991; Manegold и др., 2002b; Manegold и др., 2004; Zhou и Ross, 2004). Главная цель — сохранить полезные данные на самом быстром уровне иерархии памяти.