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

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

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

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

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

Структуры данных (Data structures) — это средства, с помощью которых программы хранят и извлекают данные. Эта книга посвящена структурам данных типа «ключ-значение», которые широко используются в высоконагруженных приложениях благодаря универсальности модели данных типа «ключ-значение». Структуры данных типа «ключ-значение» управляют коллекцией записей типа «ключ-значение» с тем свойством, что данный ключ связан только с одним значением, но одно и то же значение может быть связано со многими ключами. Часть значения записи данных может иметь произвольную семантику. Например, это может быть запись в реляционной базе данных или Pandas DataFrame, или произвольный набор полей, которые приложение умеет анализировать и использовать в системе NoSQL. В некоторых случаях, например, когда системы управляют данными для социальных сетей, значение может содержать ссылку на большой объект, такой как изображение или видео.

Физически структура данных «ключ-значение» состоит из (1) данных, физически хранящихся в некоторой памяти, (2) необязательных метаданных, облегчающих навигацию по данным, и (3) алгоритмов, поддерживающих операции хранения и извлечения данных (Hellerstein и др., 2007; Selinger и др., 1979; Idreos и др., 2018a). Другие термины, используемые в литературе для структур данных, включают «методы доступа», «контейнеры данных» и «поисковые структуры».

Системы данных, операционные системы, файловые системы, компиляторы и сетевые системы используют разнообразные структуры данных. Примеры в этой книге взяты в основном из области систем данных большого объёма, требующих вторичных устройств хранения, но основные аспекты анализа и проектирования применимы и к системам, работающим исключительно в памяти, где доступ к ОЗУ (памяти с произвольным доступом) намного медленнее, чем доступ к кэшу. Фактически, анализ применим к любой системе, в которой есть два или более уровней в иерархии памяти/хранилища.
Учитывая обилие приложений, которые можно смоделировать с помощью данных типа «ключ-значение», такие структуры данных обладают огромной общей полезностью. Например, определённая структура данных может быть использована для описания (1) доступа к метаданным в файлах, сетях и операционных системах (Bovet и Cesati, 2005; Rodeh, 2008), (2) доступа к данным в реляционных системах (Hellerstein и др., 2007), (3) доступа к данным в системах NoSQL и NewSQL (Idreos и Callaghan, 2020; Mohan, 2014), и (4) разработки признаков и структуры моделей в конвейерах машинного обучения (Wasay и др., 2021).

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

По мере появления и развития высоконагруженных приложений использование эффективных структур данных становится критически важным для жизнеспособности таких приложений, иногда приводя к изменению производительности на три порядка, как показано в работе Chatterjee и др. (2022). Причина в том, что перемещение данных является основным узким местом в высоконагруженных приложениях. Перемещение данных во многом зависит от способа их хранения, то есть от структуры данных. Таким образом, мы ожидаем, что по мере появления новых приложений, изменения аппаратного обеспечения и роста объёма данных будет постоянно возникать потребность в новых структурах данных. В настоящее время в научных и промышленных исследованиях каждый год появляется несколько новых структур данных, и ожидается, что этот темп будет расти.В то же время с ростом числа доступных новых структур данных усложнилась даже задача выбора готовой структуры данных, то есть той, которую можно найти в учебниках.

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

Каждая структура данных представляет собой определённый компромисс производительности, зависящий от рабочей нагрузки и аппаратного обеспечения (формализовано в работах Athanassoulis и др., 2016 и Idreos и др., 2018b). Для того чтобы выбрать существующую структуру данных или разработать новую структуру данных для конкретной рабочей нагрузки на конкретном оборудовании, необходимо чётко и формально понимать возможное пространство проектирования структур данных. Этому и посвящена настоящая книга. Чтобы мотивировать это обсуждение, давайте рассмотрим несколько примеров проектирования и компромиссов с учётом рабочей нагрузки (раздел 1.2.1), а также базового оборудования (раздел 1.2.2) и того, как они оба изменяются с течением времени.

Оптимизация под рабочую нагрузку. Рассмотрим рабочую нагрузку, состоящую из небольшого количества вставок и обновлений, а также большого количества запросов к точкам и диапазонам. Чтобы сбалансировать стоимость чтения и записи, многие приложения используют B+-деревья, первоначально предложенные Bayer и McCreight (1972), а затем рассмотренные Graefe (2011). B+-деревья имеют высокую разветвленность узлов, поэтому для перехода от корня к листу требуется мало обращений к вторичной памяти, а их верхние уровни кэшируются на более быстрых уровнях иерархии памяти (раздел 4.1). Кроме того, B+-дерево поддерживает запросы к диапазону, сохраняя все ключи отсортированными в узлах листьев и соединяя узлы листьев в связный список. Однако при увеличении числа вставок и обновлений узлы листьев должны реорганизовываться и, возможно, даже разделяться, что может стать узким местом в производительности.

Для обработки рабочих нагрузок с большим количеством вставок используется совершенно другой подход — структура данных, называемая лог-структурированным деревом слияния (LSM-дерево). LSM-деревья были первоначально представлены O’Neil и др. (1996), а их многочисленные варианты были рассмотрены Luo и Carey (2020). Как мы увидим в разделе 4.8, LSM-деревья помещают все обновления в общий буфер памяти, который сливается на диск, когда он переполняется. По мере накопления буферов они объединяются, образуя более крупные отсортированные коллекции данных. В этой конструкции используется политика обработки модификаций вне места, подробно рассмотренная в Sarkar и Athanassoulis (2022), когда в структуре может быть много пар ключ-значение с одинаковым ключом. (Для данного ключа k текущее значение имеет самая последняя вставленная пара ключ-значение для k).

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

Рисунок 1.1: Адаптивная организация данных с использованием последнего поиска в качестве подсказки. В этом примере запрос диапазона значений от 15 до 60 приводит к разбиению базовых данных на три непересекающихся раздела: один со значениями меньше 15, другой со значениями от 15 до 60 и третий со значениями больше 60.

Адаптация к рабочей нагрузке. Поскольку главной темой этой книги является проектирование структуры данных с учетом ожидаемой рабочей нагрузки, мы также рассмотрим проектирование структур данных, которые постепенно адаптируются к идеальному проектированию. Чтобы проиллюстрировать этот момент, рассмотрим, что B+-дерево и LSM-дерево, как они были первоначально разработаны, устанавливают отсортированный порядок в узлах, находящихся на диске, чтобы ответить на любой запрос точки или диапазона. Адаптивная структура данных может начать с одного или нескольких неотсортированных узлов, но постепенно отсортирует их незапрашиваемым образом, как показано на рис. 1.1. В главе 5 мы рассмотрим концепцию разделения базы данных, предложенную Idreos и др. (2007a) и далее расширенную в работах Idreos и др. (2007b) и Idreos и др. (2009). Интуитивно понятно, что при разделении используются шаблоны доступа входящих запросов для непрерывной и инкрементной физической реорганизации базовых данных с целью повышения производительности будущих запросов.

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

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

Изначально B+-деревья пытались минимизировать обращения к диску за счёт максимизации разветвления. Однако с ростом объёма памяти большая часть данных стала помещаться в память с произвольным доступом или энергонезависимую вторичную память. Это кардинально изменило компромиссы. Например, как показано в работе Kester и др. (2017), B+-деревья в памяти лучше всего работают при небольшом разветвлении.

Стена памяти. В то время как иерархия памяти расширяется благодаря таким технологиям, как память с высокой пропускной способностью, как описано в работе Pohl и др. (2020), ключевой тенденцией развития аппаратного обеспечения на протяжении нескольких десятилетий является растущее несоответствие между скоростью процессора и скоростью внечиповой памяти, названное Wulf и McKee (1995) стеной памяти (memory wall). С начала 2000-х годов операционные системы, о которых пишут Milojicic и Roscoe (2016), и системы управления данными, о которых пишут Johnson и др. (2009), были тщательно перепроектированы с учётом «стены памяти» путем оптимизации использования кэш-памяти.

Устройства хранения эволюционируют. Кроме того, вторичные системы хранения данных сами по себе достигли переломного момента. Традиционные жесткие диски уже давно достигли своего физического предела скорости (Athanassoulis, 2014), и их в основном заменили «черепичные» жесткие диски и устройства на основе флэш-памяти (Hughes, 2013). Черепичные жесткие диски увеличивают плотность хранения данных на магнитном носителе, что изменяет характеристики производительности дисков, поскольку меняется гранулярность чтения и записи (Hughes, 2013). Накопители на основе флэш-памяти обеспечивают значительно более высокую скорость чтения по сравнению с традиционными дисками, но страдают от относительно низкой скорости записи. Кроме того, флэш-накопители оснащены высокофункциональным слоем микропрограммы, называемым Flash Translation Layer (FTL), который можно переписать, чтобы добиться значительных изменений в производительности. Таким образом, производительность флеш-устройств зависит как от аппаратного, так и от встроенного программного обеспечения. Такие изменения приводят к необходимости создания новых структур данных для оптимизации под различные комбинации аппаратного и микропрограммного обеспечения.

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

В частности, мы предполагаем, что читатель уже знаком с такими базовыми структурами данных, как массивы, связанные списки, двоичные деревья, очереди, стеки, кучи и хэш-таблицы, которые изучаются во вводных курсах по структурам данных и алгоритмам (Cormen и др., 2009). Такие базовые структуры данных лежат в основе более сложных конструкций, которые мы описываем. Большинство примеров использования и представленных конструкций мотивированы высоконагруженными системами, поэтому они опираются на классические структуры данных, используемые в системах баз данных, такие как B+-деревья (Bayer и McCreight, 1972), открытое хэширование (Ramakrishnan и Gehrke, 2002) и LSM-деревья (O'Neil и др., 1996).
В остальном книга самодостаточна. Мы опишем все алгоритмы, используемые при навигации по сложным структурам данных, и расскажем, как сочетать различные проектные решения, которые мы представляем.

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

Вот краткое содержание нашей книги. Мы рекомендуем читать главы последовательно.

• В главе 2 представлены фундаментальные показатели производительности структур данных для наиболее важных операций с ключами-значениями и свойств оборудования.
• В главе 3 представлен основной набор принципов проектирования, в первую очередь основанных на характеристиках рабочей нагрузки, которыми в основном руководствуются при проектировании структур данных типа «ключ-значение».
• Глава 4 начинается с объяснения проектирования и характеристик производительности традиционных структур данных, основанного на принципах проектирования. Затем мы обсудим, как использовать принципы проектирования для разработки новых структур данных для произвольных рабочих нагрузок.
• В главе 5 обсуждаются необходимость и принципы проектирования адаптивных структур данных. Мы также иллюстрируем примеры использования, в которых адаптивность приводит к значительному повышению производительности.
• В главе 6 рассматривается использование структур данных в приложениях для работы с большими данными, включая базы данных, файловые системы и машинное обучение.
• В главе 7 обсуждаются дополнительные соображения, которые могут повлиять на детальное развёртывание структур данных, начиная от развёртывания структур данных в условиях параллельного выполнения, в контексте распределённых систем, до нового оборудования, рабочих нагрузок нового типа и новых требований к приложениям.