В моей предыдущей статье я обсуждал некоторые внутренние механизмы хранения различных типов баз данных. LSM-дерево, фрактальное дерево и B-дерево были обсуждены на более широком уровне, чтобы мы могли познакомиться с общим дизайном, лежащим в основе таких популярных систем. Это действительно обширное поле для понимания и обсуждения работы с базами данных, здесь так много сложных вещей.

Сегодня я немного расскажу о другом методе, называемом Multi Version Concurrency Control, который используется в очень популярных системах баз данных, таких как PostGreSQL, Couch DB, LMDB и т. Д.

Итак, из самого названия довольно ясно, что такие системы поддерживают разные версии данных с идентификаторами, такими как rev_no или version_no и т. Д., И при запросе данных возвращается последняя версия. Это выглядит просто, но в этом есть много аспектов.

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

Системы MVCC также используют внутреннее дерево B-Tree. Но это не выполняется на месте обновления B-Tree, поскольку случайная запись очень затратна и менее эффективна для любого типа диска. Вместо этого он использует подход только с добавлением, такой как системы дерева LSM. Каждый & каждый раз, когда некоторые данные обновляются, создается копия исходного листового узла, которая добавляется в конец файла. Не только лист, но и весь путь от листа к корню воссоздается и добавляется в конец файла. Остальные узлы остаются нетронутыми. Корневой узел всегда записывается последним. Таким образом, обновление всегда выполняется снизу вверх.

Действия выглядят следующим образом:

Так как же нам найти корень в приведенном выше дереве? Поскольку в системе может быть несколько корней, должен быть какой-то способ, чтобы мы могли найти корень. Обычно в таких базах данных, как CouchDB или LMDB, используется специальный узел под названием meta, который всегда находится в конце файла и указывает на корень дерева. Итак, концептуально root - это не последний узел, записанный в файле базы данных, это мета-страница. Таким образом, когда файл считывается из последнего, мета-страница может быть получена, из корня мета-страницы определяется, из корня можно пройти по всему дереву.

Таким образом, по сути, добавлять или копировать только при записи. B-Tree - это система случайного чтения и последовательной записи. Случайное чтение все же лучше случайной записи: D.

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

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

Ниже приведены некоторые способы управления пространством -

  1. Запускайте процесс сжатия или сборку мусора в фоновом режиме - поддерживайте некоторые метаданные, такие как счетчики ссылок, для всех узлов в файле базы данных, периодически очищайте их, когда счетчик ссылок равен 0.
  2. Избавьтесь от идеальной многоверсионной концепции. LMDB использует этот подход. LMDB в основном поддерживает 2 корневые страницы. Каждая операция считывает обе страницы с конца файла. LMDB пытается управлять операциями только между двумя корнями. Но у этого подхода есть проблема. Могут быть некоторые длительные операции чтения, которые могут указывать на гораздо более старую версию дерева. В таких случаях поддержка двух страниц может оказаться неэффективной, если количество таких старых транзакций очень велико. Следует избегать столь длительных операций чтения. Это происходит, как показано ниже:

3. Третий способ - управлять списком бесплатных страниц. Список также может управляться в памяти. Таким образом, мы намерены максимально использовать уже освобожденные страницы. Таким образом, база данных может поддерживать стабильный размер. Таким образом, вы можете рассматривать это как базу данных со множеством использованных и неиспользуемых страниц. Если вы продолжите повторно использовать неиспользуемые страницы для новых операций обновления, вам может вообще не понадобиться сборка мусора. Таким образом, нет уплотнения / сборки мусора, нужно только управлять списком свободных / неиспользуемых узлов - небольшие накладные расходы на пространство, но оно того стоит.

Так что только добавление или CoW B-деревья очень выгодны:

  1. Только добавление очень и очень быстро работает на диске - магнитном жестком диске или твердотельном накопителе, что бы это ни было.
  2. Из-за природы только добавления база данных никогда не повреждается, потому что то, что уже записано на диск, неизменяемо.
  3. Вероятно, нет необходимости поддерживать WAL - Write Ahead Log. Потому что база данных никогда не будет повреждена. Никаких обновлений на месте, база данных всегда имеет непротиворечивое представление.
  4. Сделать резервную копию или сделать снимок очень просто. Обычно для операции резервного копирования вам необходимо отключить базу данных или заморозить ее или прекратить выполнение операций обновления на некоторое время, потому что во время резервного копирования, если происходит какая-либо операция обновления, это может повлиять на резервную копию или может не быть частью моментального снимка в все. Также могут возникнуть проблемы с блокировкой во время резервного копирования и т. Д. Только с добавлением таких накладных расходов нет, поскольку файл уже содержит неизменяемое состояние данных. Просто скопируйте файл на другой компьютер и готово. Даже если будет простой, он очень-очень маленький.
  5. В идеале блокировка отсутствует. Итак, писатели не блокируют читателей, читатели не блокируют писателя. Читатели всегда видят непротиворечивое представление о базе данных. Таким образом, вы можете идеально запустить один сериализованный писатель с несколькими читателями.
  6. После сбоя перестройка или переиндексация не требуется. Достаточно просто сделать резервную копию файла базы данных.
  7. Репликация также проста, как резервное копирование.

Некоторые недостатки:

  1. Большой объем используемого пространства - самая большая проблема. Все в мире имеет свою цену. Так что скорость таких систем зависит от таких накладных расходов.
  2. B-Tree - это очень компактная структура данных, т.е. внутренние узлы или узлы ветви содержат массив из сотен или тысяч ключей. Таким образом, это сводится к одинаковому количеству дочерних элементов на узел ветви. Таким образом, существуют тысячи и миллионы путей от листа к корню, которые можно практически скопировать в большом масштабе.

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

Быть в курсе.!