Как Cassandra хранит данные: исследование лог-структурированных деревьев слияния

Хранение базы данных – важнейший аспект любого приложения, интенсивно использующего данные. Способы хранения, организации и доступа к данным могут существенно повлиять на производительность, масштабируемость и надежность системы. В этой статье мы рассмотрим лог-структурированные деревья слияния, которые используют SSTables и Memtables для обеспечения быстрого и надежного хранения. Мы рассмотрим каждый компонент по очереди и поймем, как они работают вместе.

Модель данных

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

Вот пример таблицы данных о сотрудниках.

| Отдел (ключ раздела) | Год присоединения (кластерный столбец) | Имя | |----|----|----| | Бухгалтерский учет | 2022 | Джон | | Инжиниринг | 2021 | Джек | | Инжиниринг | 2022 | Джеймс | | Продажи | 2020 | Сэм |

В любой базе данных SQL строка однозначно идентифицируется первичным ключом.

В Cassandra и Scylla первичный ключ также служит единственным способом доступа к строке. Первичный ключ в Cassandra может быть простым или составным.

* Простой первичный ключ состоит только из ключа раздела. * Cassandra — это распределенная база данных, работающая на нескольких узлах. Хэш ключа раздела определяет, какой узел (или узлы) будет хранить строку. * С простым первичным ключом (т. е. только с ключом раздела) наша таблица действует как хранилище ключей и значений. Мы можем получить содержимое строки, предоставив ключ Cassandra.

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

• Столбцы кластеризации позволяют выполнять запросы диапазона по строкам с одинаковым значением ключа раздела.

  • Выберите * из «Сотрудников», где отдел = «Инженерный», «Год» >2020 и «Год» < 2022 г.;

В распределенной базе данных, такой как Cassandra, каждый узел хранит только часть строк таблицы.

Далее рассмотрим, как Memtables и SSTables хранят эти строки.

Memtables

Memtables — это таблицы памяти. Это структура данных в памяти, в которой хранятся данные до того, как они будут сброшены на диск в виде SSTable. Memtable — это, по сути, хэш-карта.

Memtables имеют несколько преимуществ:

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

Memtables также имеют некоторые недостатки:

• Они нестабильны, так как могут быть потеряны в случае сбоя питания или сбоя системы. Для обеспечения надежности Memtables поддерживаются журналом упреждающей записи (WAL), в котором записываются все мутации перед их применением к Memtable.
• Они ограничены объемом памяти, поскольку не могут хранить больше данных, чем доступно в памяти. Чтобы предотвратить исчерпание памяти, Memtables сбрасываются на диск, когда они достигают определенного размера или когда сброс запускается вручную или по другим причинам.

SSTables

SSTables означает таблицу отсортированных строк. Это постоянный формат файла, в котором данные хранятся на диске в отсортированном и неизменном виде. SSTable состоит из нескольких блоков данных, каждый из которых содержит набор пар ключ-значение. Ключи сортируются в порядке возрастания внутри каждого блока, а блоки сортируются по их первому ключу. Каждая SSTable также имеет индексный файл, который сопоставляет каждый ключ с соответствующим расположением блока, что позволяет выполнять быстрый поиск.

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

SSTables имеют несколько преимуществ:

• Они быстро записываются, так как только добавляют данные на диск, не перезаписывая существующие данные.
• Они удобны для чтения, поскольку используют двоичный поиск для поиска ключей в блоках и индексные файлы для поиска блоков в таблицах SSTable.
• Их легко объединить, так как они уже отсортированы по ключу. Это позволяет эффективно собирать мусор и сжимать старые или избыточные SSTables. Слияние SSTables может быть выполнено с временной сложностью O(n) с использованием шага слияния сортировки слиянием.

SSTables также имеют некоторые недостатки:

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

Структурированное дерево слияния журналов

Дерево LSM – это дерево или набор таблиц Memtable и SSTable. Самый верхний уровень состоит из одной Memtable. Второй уровень и ниже представляют собой одну или несколько таблиц SSTable. По мере роста уровней увеличивается количество SSTables или размеры SSTables (это зависит от стратегии уплотнения). Основной рабочий процесс выглядит следующим образом:

Написать

Когда данные вставляются в дерево LSM, происходит следующее.

• Запись данных в Memtable и журнал упреждающей записи
• После достижения порога Memtable (размера или времени) очистить memtable, чтобы создать SSTable уровня 1.
• Если на уровне L слишком много SSTable, объедините две или более SSTable для создания новой SSTable на уровне L+1 в процессе, который называется уплотнением. Две объединенные таблицы удаляются.

Читать

• При поступлении операции чтения она сначала проверяется в текущей Memtable. Если ключ не найден или значение устарело, оно затем проверяется в недавно созданных таблицах SSTable в порядке убывания времени создания, пока не будет найдено самое последнее значение или пока не будут исчерпаны все таблицы SST.
• Количество уровней, которые мы должны пройти, чтобы построить строку, напрямую влияет на производительность запроса на чтение.

Сжатие

По мере роста количества SSTables мы наблюдаем следующие тенденции

• Неиспользуемое пространство на диске: каждая SSTable содержит набор обновлений или изменений строк. Некоторые из этих обновлений являются избыточными, поскольку более новая таблица SSTable содержит самое последнее значение.
• Производительность чтения падает по мере увеличения количества SSTables, которые нам нужно прочитать.

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

Существует множество различных стратегий уплотнения. Размер Многоуровневое и Уровневое уплотнение — две наиболее популярные стратегии:

* Размер Многоуровневое уплотнение: * В стратегии многоуровневого уплотнения размера размер SSTable растет по мере того, как мы спускаемся по уровням. Просто когда у нас есть фиксированное количество SSTables на уровне 1, все они объединяются для создания большего SSTable на уровне 2. SSTables на уровне 1 удаляются. Когда на уровне 2 собрано предопределенное количество таблиц SST, они снова объединяются/уплотняются для создания еще большей таблицы SST на уровне 3.

• Сжатие уровней
• Сжатие уровней гарантирует, что каждый ключ появляется только один раз на заданном уровне. При сжатии таблица SSTable уровня L-1 объединяется со всеми таблицами SSTable уровня L, имеющими общий диапазон ключей. Количество SSTables на каждом уровне растет экспоненциально. Это основано на LevelDB.
• LevelDB — это полезный ресурс для получения дополнительной информации о LSM. Термин БД вводит в заблуждение, так как LevelDB — это не база данных, а библиотека, обеспечивающая функциональность LSM.

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

Заключение

Структурированное дерево слияния журналов, Memtables и SSTables — это распространенные концепции хранения баз данных, которые используются некоторыми базами данных NoSQL, такими как Apache Cassandra и ScyllaDB, для хранения данных на диске и в памяти соответственно. Они предлагают компромисс между производительностью и надежностью, а также обеспечивают масштабируемость и отказоустойчивость в распределенных системах. Однако они также создают некоторые проблемы, которые требуют тщательного выбора дизайна и реализации.

Ссылки

1: MemtableSSTable — CASSANDRA2 — Apache Software Foundation 2: Двигатель памяти | Документация по Apache Cassandra 3 : Memtable & SSTable (таблица отсортированных строк) | Маурисио Поппе 4: Что такое SSTable? Определение и усилитель; Часто задаваемые вопросы | ScyllaDB

5: https://www.scylladb.com/2018. /01/31/compaction-series-leveled-compaction/

:::информация Главное изображение для этой статьи было создано генератором изображений HackerNoon AI Image Generator с помощью подсказки «дерево с компьютерными плодами»

:::