Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняЧасть 10 распределенных темВ статье продолжим разговор о структуре данных LSMT.
LSMT — это структура данных, которая широко используется в распределенных системах и имеет интуитивно понятный и простой принцип. В предыдущей статье мы подробно обсуждали, что студенты, которые забыли или недавно заинтересовались, могут щелкнуть ссылку ниже, чтобы просмотреть содержание предыдущей лекции.
Распределенный - Огромная пропускная способность, носитель Hbase LSMT
Введение в leveldb
В предыдущей статье мы представили самую базовую версию LSMT, а в этой статье мы специально рассмотрим использование и оптимизацию LSMT в levelDB, классическом механизме базы данных KV.
leveldb, поскольку он называется db, очевидно, связан с базой данных. В отличие от общей реляционной базы данных, все ее внутренние данные хранятся в форме KV, то есть ключ-значение, и не поддерживает структурированный SQL для запроса данных, только вызовы API. Другими словами, это типичная библиотека механизма обработки данных noSQL, о которой мы часто говорим. Это был первыйgoogleразработан и открыт,FacebookНа основе этой оптимизации была запущена более популярная RocksDB, а позже на leveldb был основан нижний слой различных распределенных баз данных noSQL, в том числе и TiDB.
Неважно, если вы никогда не слышали о вышеперечисленных терминах, для этих библиотек легко их использовать, но сложно понять принципы. Как только вы поймете принцип, а затем начнете его использовать, вы не только станете проще, но и получите больше опыта.
схема leveldb
Это диаграмма архитектуры leveldb, которая немного сложнее, чем диаграмма голой архитектуры LSMT, представленная ранее, но основная суть та же самая, давайте рассмотрим их одну за другой.
Во-первых, верхний уровень — это MemTable и Immutable MemTable. Мы все знаем MemTable, на самом делеПо сути, это структура данных, хранящаяся в памяти.. Это может быть SkipList или красно-черное дерево или другое сбалансированное дерево (в leveldb используется SkipList), нам нужно только убедиться, что оно хранится в памяти. Immutable MemTable на самом деле является MemTable, предыдущий Immutable означает неизменяемый. Как мы уже говорили, когда содержимое в MemTable превышает определенный порог, нам нужно записать содержимое в файл SSTable. В настоящее время используется эта ImmuTable MemTable.
Когда MemTable преобразуется в ImmuTable MemTable до того, как она начнет сохраняться, это можно рассматривать как непреложное ограничение. Кроме того, для обслуживания службы будет создана новая таблица MemTable. Затем запишите ImmuTable MemTable в файл SSTable.
Например, MemTable похож на кассовый аппарат в кассовом аппарате: когда мы открываем магазин, нам, очевидно, нужен кассовый аппарат для хранения денег, уплаченных покупателями. Когда касса почти заполнена, нам нужно положить деньги в банк. Но в этом много денег, и есть клиенты, которые постоянно платят, и мы потеряем деньги, если позволим этому остановиться на некоторое время. Так что мы собрали всю кассу вместе, для безопасности добавили замок снаружи, заперли и отправили в банк вместе с кассиром. Но кассирша без кассира не может быть, поэтому нам тоже нужно вывезти новую кассу, чтобы кассирша собирала деньги.
В этом примере касса, которая отвечала за сбор денег, в начале была MemTable, а после добавления блокировки стала Immutable MemTable. Может быть, не очень уместно, но это должно быть легко понять в сравнении.
Второй — файл .log, который легко понять, этот файл также был включен в предыдущую версию LSMT для хранения измененных данных.Аналогично binlog в базе данных, который используется для восстановления данных при сбое и перезапуске системы.
Затем давайте посмотрим на SSTable. В исходном LSMT SSTable хранится последовательно, поэтому мы запрашиваем данные последовательно. Когда мы обнаружим, что в первой SSTable нет контента, который мы хотим запросить, мы будем запрашивать файл. . И в leveldb,SSTables хранятся иерархически, первый уровень level0, второй уровень level1 и так далее, уровень постепенно увеличивается. Вот почему leveldb получил свое название.
Ранее мы говорили о том, что сущностью SSTable является список последовательностей ключ-значение, и ключи в нем упорядочены. Поскольку ключи в SSTable упорядочены, очевидно, что есть максимальное и минимальное значения. Записав максимальное и минимальное значения, мы можем быстро определить, в каких таблицах SSTable может находиться ключ, который мы хотим запросить, тем самым сэкономив время и повысив эффективность.
Файл, который записывает минимальный ключ и максимальный ключ в файле SSTable, является манифестом.В дополнение к минимальному и максимальному ключам он также записывает такую информацию, как уровень, к которому принадлежит SSTable, и имя файла. Мы можем использовать следующий рисунок в качестве ссылки:
Наконец, есть файл Current.С точки зрения имени Current похоже на имя указателя. Действительно, Current — это указатель. Потому что в реальной работе находится более одного файла манифеста, потому что с нашим сжатием и другими операциями будет сгенерирован новый манифест. Нам нужен указатель для записи, который является последним файлом манифеста, который легко найти. Да и данных в манифесте не мало, поэтому мы не можем хранить все это в памяти, и лучше всего поместить их в файл и использовать указатель для ссылки.
Добавляйте, удаляйте, изменяйте и проверяйте leveldb
запись leveldb
в leveldbОперации записи, удаления и изменения в основном такие же, как и у простого LSMT., разделенный на следующие шаги.
Сначала измененные данные записываются в файл .log. Это необходимо для сохранения данных, когда простои системы приводят к потере данных.
При успешной записи в файл .log запишите в MemTable. Так как MemTable в leveldb реализована с помощью SkipList, скорость записи будет очень быстрой, примерно
сложность. Если емкость MemTable достигает порогового значения или превышает его, будут инициированы дальнейшие записи в SSTable. В этом письме MemTable сначала будет преобразована в неизменяемую MemTable, а затем будет создана пустая MemTable для обработки последующих запросов.Когда выдается команда дампа, неизменяемая MemTable будет записана в файл SSTable для хранения.
Описанный выше процесс похож на LSMT, но с некоторыми незначительными отличиями. Кроме того, строго говоря, leveldb не поддерживает операции модификации.Его можно преобразовать во вставку новых данных или удаление старых данных перед вставкой.По сути, это одно и то же, и они будут объединены в последующем процессе сжатия данных.
читать leveldb
Операция чтения leveldb немного отличается от операции LSMT Давайте подробно рассмотрим следующую картинку.
Во-первых, когда мы выполняем команду find, мыВо-первых, он будет искать в MemTable и Immutable MemTable.. Это легко понять, потому что и MemTable, и Immutable MemTable — это хорошо зарекомендовавшие себя структуры данных, поддерживающие быстрый поиск. Некоторым ученикам может показаться странным, что в файл не записывается Immutable MemTable, как его еще искать. Это связано с тем, что при преобразовании MemTable в Immutable MemTable перед записью на диск будет время ожидания, которое не выполняется немедленно. Перед выполнением записи в Immutable MemTable могут быть остатки данных, и их необходимо искать.
Если он не найден в MemTable и Immutable MemTable, то мы будем читать данные на диске, чтобы найти.
В отличие от простого LSMT, который последовательно ищет SSTables один за другим, leveldb сначала прочитает файл манифеста и найдет возможные файлы SSTable в соответствии с диапазоном ключей, записанных в файле манифеста.
Для того же ключа,Может появляться в SSTables разных уровней одновременно, а потому, что leveldb следует принципу, что чем позже записываются данные, тем новее они при записи в SSTable. то естьЧем меньше номер уровня, тем новее данные, поэтому, если найдено более одного значения, первым возвращается результат верхнего уровня.
Чтение и запись всего leveldb можно рассматривать как оптимизацию, добавленную к исходному LSMT, Там не так много вещей, которые трудно понять, и это относительно кратко и прямолинейно. В некоторых сценариях наших ресурсов памяти относительно достаточно, и есть определенные требования к поиску, мы можем кэшировать манифест в памяти, что может сократить время чтения файла манифеста и сыграть роль в ускорении. Но в то же время это также влечет за собой затраты на обслуживание кеша, которые будут подробно описаны в статье, посвященной кешу позже.
Стратегия сжатия leveldb
Наконец, давайте взглянем на стратегию сжатия leveldb, которая также является сущностью leveldb.
в гугле есть статьяBigtable: A Distributed Storage System for Structured DataЭту статью можно считать теоретической основой leveldb. В статье BigTable упоминаются три стратегии сжатия.
Первая стратегия называетсяminor Compaction, эта стратегия очень проста, то есть просто импортируйте данные из MemTable в SSTable.
Вторая стратегия называетсяmajor Compaction, эта стратегия объединит файлы SSTable разных уровней, а это означает, что основное уплотнение уменьшит количество уровней.
Последняя стратегия называетсяfull Compaction, эта стратегия объединит все файлы SSTable.
В leveldb реализованы первые две стратегии сжатия, малое уплотнение и большое уплотнение, подробно рассмотрим его ниже.
minor Compaction
Minor Compaction очень прост.Как я только что сказал, он фактически записывает данные из MemTable, то есть SkipList, на диск для создания файлов SSTable.
SkipList был представлен в нашей предыдущей статье, и его сущностью является упорядоченный связанный список. И SSTable, который мы хотим сгенерировать, как раз в порядке. Так что нам просто нужно пройти записи в последовательности. Учащиеся, которые заинтересованы в SkipList или хотят ознакомиться с ним, могут щелкнуть ссылку ниже, чтобы просмотреть:
Распределенный — список переходов SkipList [с кодом]
В соответствии с принципом, согласно которому серийный номер сгенерированного позже уровня SSTable меньше, а уровень выше, наш последний сгенерированный SSTable имеет уровень0. После этого нам нужно записать индекс во вновь сгенерированную SSTable, чтобы завершить операцию записи. Следует отметить, что в ходе этого процесса мыДанные не будут удалены. Причина тоже очень проста, потому что мы не знаем, на каком уровне SSTable находятся удаляемые данные, а их поиск и удаление принесут много времени. Поэтому мы все равно запишем его как есть и дождемся последующих слияний для обработки этих удалений.
Кроме того,В конце файла информация о значении ключа будет храниться в виде индекса.. Поскольку мы читаем файл в обратном порядке, сначала будет прочитана индексная информация. Мы можем быстро заблокировать данные в SSTable в соответствии с прочитанной информацией индекса, не читая весь файл.
major Compaction
Далее мы рассмотрим основное уплотнение. Это также является ядром механизма расслоения leveldb, иначе вставка в SSTable будет только level0, и об иерархической структуре говорить будет невозможно.
Прежде чем углубляться в детали, нам нужно прояснить одно понимание. Для файлов SSTable других уровней в leveldb все они генерируются с помощью основного уплотнения. Мы можем гарантировать, что SSTables одного и того же уровня не имеют перекрывающихся элементов, но отличается уровень 0. SSTables уровня 0 генерируются незначительным уплотнением, поэтомуможет перекрываться.
Существует более одной ситуации, которая вызывает серьезное уплотнение в leveldb.В дополнение к наиболее часто упоминаемому уплотнению размера существует два типа: одно — ручное сжатие, а другое — сжатие поиска. Вот краткое введение.
ручное уплотнение хорошо понятно, т.е.Ручной ручной триггер, вручную активируйте его для выполнения уплотнения через вызов интерфейса. Уплотнение размера эквивалентно операции балансировки, которая запускается, когда система обнаруживает, что количество SSTables в определенном слое превышает пороговое значение. Последним является поиск уплотнения, который является более умным, leveldb будет записывать процент промахов каждого файла SSTable на каждом уровне. То есть, когда обнаружится, что данные в каком-то файле всегда отсутствуют, а значение найдено в файле следующего слоя, в это время leveldb подумает, что файл недостоин находиться в этом слое, и объединить его с данными следующего слоя, чтобы уменьшить потребление ввода-вывода.
Конечно, среди трех вышеперечисленных ситуаций, вызывающих уплотнение, наиболее распространенным является уплотнение размера, т.е.Когда leveldb обнаружит, что данные SSTable определенного слоя или размера превышают пороговое значение, он выполнит операцию сжатия..
При основном уплотнении предполагается, что leveldb выбирает файлы уровня i для слияния. В настоящее время это необходимо обсуждать в каждом конкретном случае, если i=0, это означает, что мы хотим объединить данные уровня 0. Как упоминалось выше, данные разных файлов на уровне 0 перекрываются, на этот разВсе файлы с перекрывающимися значениями ключей необходимо включить в набор для слияния. При выборе набора для слияния leveldb запишет максимальное значение ключа, когда сжатие было запущено в последний раз, и на этот раз для начала сжатия будут выбраны файлы, размер которых превышает это значение ключа.
То есть leveldb разработал механизм вращения,Убедитесь, что каждый файл на уровне может быть объединен.
Когда наш выбор файлов уровня i закончен, следующим шагом будет выбор файлов уровня i+1 для слияния. Критерии выбора также очень просты, мы выберем все файлы с перекрывающимися значениями ключей в наборе для объединения для объединения.
Процесс слияния, по сути, представляет собой многосторонний процесс слияния, как показано на следующем рисунке:
Поскольку значения ключей во всех файлах упорядочены, начнем с их заголовков. Для каждого ключа мы будем судить, следует ли его сохранить или выбросить. Логика суждения тоже очень проста, для определенного ключа, если этот ключ появился на более низком уровне, значит, есть обновленное значение, и нам нужно его отбросить.
Когда уплотнение завершено, все файлы, участвующие в слиянии, становятся бесполезными и могут быть удалены.
По сути, этот процесс слияния аналогичен голому принципу LSMT, но с добавленной иерархией.
Это еще не конец, помните, что у нас есть запись всех индексов SSTablemanifestфайл? Независимо от того, какое уплотнение происходит, структура всего уровня будет изменена, поэтому нам нужно генерировать новый файл манифеста после каждого уплотнения, а затем записывать изменения файла, вызванные этим уплотнением. Наконец, укажите Current на только что сгенерированный манифест.
Таким образом, весь наш процесс связан воедино.
Суммировать
Когда мы рассмотрим весь процесс, мы обнаружим, что, хотя добавления, удаления, изменения и уплотнения добавили много деталей, ноБазовая структура на самом деле LSMTэтот набор. Поскольку основной принцип тот же, что и в чистом LSMT, SSTable в leveldb также можно оптимизировать с помощью фильтра Блума.Кроме того, имеется гибкое использование кеша, что может еще больше повысить эффективность запросов.
Кроме того, следует отметить, что leveldb строго говоряПросто механизм базы данных, а не настоящая система баз данных. На основе leveldb мы можем разработать относительно полную систему баз данных, но она обеспечивает только основу для базовых служб добавления, удаления, модификации и запросов в нижней части. В дополнение к основным функциям зрелая система баз данных также должна разрабатывать множество деталей и выполнять большую оптимизацию. На сегодняшний день существует множество механизмов баз данных, разработанных на основе leveldb.Но полноценных систем баз данных очень мало., ведь он долго развивается и накапливается.
Если мы просто разделим распределенную систему наРаспределенные вычислительные системы и распределенные системы храненияЕсли да, то вы обнаружите, что суть распределенной системы хранения составляет большинство из них. Распределенную систему хранения можно рассматривать просто какбазовые структуры данныхКроме того, верхний слой решает проблемы непротиворечивости, вызванные распределением.протокол консенсуса. В распределенных системах хранения существует всего несколько общих базовых структур данных, поэтому наше понимание и изучение этих структур данных является основой для глубокого понимания распределенных систем в будущем. Для квалифицированного и отличного системного архитектора нормально решать распределенные проблемы в бизнес-сценариях, и суть способности решать проблемы заключается в понимании и применении этих базовых базовых знаний.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.