Структуры данных для высоконагруженных приложений: компромиссы и рекомендации
по проектированию

(Data Structures for
Data-Intensive Applications:
Tradeoffs and Design Guidelines)

Исходный текст, 2023 / Перевод, 2024

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

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

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

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

Чтобы сравнить конструкции структур данных и решить, какую из них использовать в тех или иных условиях, сначала нужно определить соответствующие метрики. Наиболее распространёнными из них являются производительность чтения и производительность обновления (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).

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

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

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

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

Три вида накладных расходов ЧОП представляют собой трёхсторонний компромисс (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).

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

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

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

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

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

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

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

Характеристика запросов с коротким диапазоном. Для того чтобы классифицировать запрос как запрос короткого диапазона, мы рассматриваем компромисс между случайным и последовательным доступом. В частности, мы считаем, что при случайном доступе точечный запрос получает доступ примерно к одной странице данных, в то время как запрос короткого диапазона затрачивает примерно столько же времени на последовательный доступ к данным. Следуя анализу 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 для количественной оценки того, насколько данные (или единицы памяти, такие как страницы, строки кэша и т. д.) могут быть доступны последовательно за то же время, которое необходимо для выполнения точечного запроса. Таким образом, такой объём данных характеризует запрос малого радиуса действия.

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

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

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

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

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

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

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

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

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