Эта статья представляет собой статью о MySQL на Medium, рекомендованную Zuoermouse, Некоторое исследование внутреннего устройства хранилища базы данных. Я думаю, что статья очень хорошая, поэтому я получил разрешение автора и перевел ее самостоятельно. Ссылка на исходный текст находится в конце статья. Эта статья является вступительным текстом, поэтому некоторые понятия не представлены подробно, такие как структура Sorted Strings Table и алгоритм фильтров Блума и другие профессиональные понятия. до статьи.
Я постоянно исследую и изучаю принцип внутреннего хранения базы данных. Я думаю, что эта тема огромна и сложна, и то, что я пытался изучить, составляет лишь одну из десяти миллионов. В этой статье я объясню некоторые внутренности хранилища базы данных, как база данных оптимизирована для обеспечения невероятной скорости, а также ее преимущества и недостатки.
Когда мы говорим о внутренней структуре хранения базы данных, люди будут думать о дереве B + B +, но мы не будем говорить о принципах этих структур данных здесь, мы покажем, почему эти структуры данных подходят как внутренняя структура хранения базы данных и используйте их. Целью структуры данных.
Традиционные реляционные данные хранят данные на диске в виде B-деревьев, и они также используют B-деревья для хранения индексов этих данных в оперативной памяти, чтобы обеспечить более высокую скорость доступа. Вставленные строки хранятся в листовых узлах B-дерева, а все промежуточные узлы используются для хранения исходных данных, используемых для оператора навигационного запроса. Поэтому, когда в базу данных вставляются миллионы данных, индекс и хранилище данных могут стать очень большими. Поэтому для быстрого доступа все данные нужно загрузить с диска в память, а оперативная память вообще не имеет такого большого места для хранения всех данных. Поэтому база данных должна считывать часть данных с диска. Этот сценарий загрузки данных показан на следующем рисунке:
Дисковый ввод-вывод занимает много времени и является одной из основных причин, влияющих на производительность базы данных. B-дерево — это структура данных, поддерживающая произвольное чтение и запись, замену на месте, очень компактная и самобалансирующаяся, но ограниченная скоростью дискового ввода-вывода. Случайные чтения означают, что при доступе к данным на диске головка должна перемещаться в указанное положение на цилиндре, поэтому на это уходит много времени.
B-деревья предназначены для хранения данных в блоках, поскольку операционная система считывает блок данных намного быстрее, чем отдельные байты данных. Размер блока механизма хранения MySQL InnoDB составляет 16 КБ. Это означает, что каждый раз, когда вы читаете или записываете данные, блок данных объемом 16 КБ будет загружаться с диска в ОЗУ, на него будут записываться новые данные, а затем он снова будет записываться на диск. Предположим, что каждая строка данных в таблице базы данных имеет размер 128 байт (фактический размер может отличаться), блок (конечный узел) имеет размер 16 КБ и хранится (16 * 1024)/128 = 128 строк данных. Высота B-дерева обычно меньше 10, но количество узлов в каждом слое велико, так что можно управлять десятками тысяч данных. Исходя из вышеперечисленных характеристик, B-дерево подходит в качестве внутренней структуры хранения данных.
Таким образом, операция чтения B-дерева выполняется относительно быстро, так как для операции требуется пройти всего несколько узлов и выполнить небольшое количество запросов ввода-вывода к диску. Кроме того, запросы диапазона выполняются быстрее, поскольку данные можно извлекать и обрабатывать блоками. Вы можете сделать следующее, чтобы ваша база данных на основе B-Tree работала лучше:
- Уменьшите количество узлов индекса: это обычная стратегия для повышения производительности реляционной базы данных. Больше индексов, количество индексов вставок и обновлений необходимо для управления. Когда данные выполнения базы данных дольше и дольше, нам нужно удалить старый или бесполезный индекс и тщательно добавить новый индекс. Но вы также должны обратить внимание, что меньше индекса означает, что производительность запросов хуже, вам необходимо компромисс (Примечание переводчика: рассмотрите базу данных. Соотношение к записи в записи) между производительностью запроса производительности вставки и обновления.
- Последовательная вставка: если вы можете последовательно вставлять большой объем данных в зависимости от размера первичного ключа, скорость вставки данных будет очень высокой. Поскольку блок, которому принадлежит вставленная строка, уже находится в памяти во время процесса вставки, база данных может напрямую вставить строку в структуру данных в памяти, а затем отправить ее на диск данных посредством одного дискового ввода-вывода. Конечно, все это зависит от конкретной реализации базы данных, но я думаю, что современные базы данных обычно имеют схожие оптимизации.
Но B-деревья не являются оптимальной структурой хранения для всех сценариев. Запись в структуры B-дерева выполняется плохо, даже хуже, чем случайное чтение, потому что база данных должна загрузить страницу, соответствующую данным с диска, затем изменить ее и сбросить на диск новые записи. Случайная запись в среднем составляет 100 байт в секунду, это ограничение связано с тем, как работают диски. На самом деле, просто полагаясь на использование кеша, поиск по индексу и больший объем памяти, можно справиться с большим количеством операций чтения, но большее количество операций записи создает больше проблем. Когда вам нужно записать или обновить большой объем данных, структура B-tree — не самый правильный выбор. В течение долгого времени традиционные базы данных подвергались значительной оптимизации, например, InnoDB пытается использовать буферизацию для сокращения операций дискового ввода-вывода. Конкретные операции заключаются в следующем:
Операции записи базы данных могут увеличить скорость за счет увеличения пропускной способности диска, но текущая реляционная база данных этого не делает. А системы управления реляционными базами данных, как правило, очень сложны, потому что они используют блокировки, параллелизм, ACID-транзакции и т. д., что усложняет операции записи.
В современный информационный век миллионы операций записи происходят каждый час в клиентоориентированных службах, таких как обмен сообщениями, чаты, мгновенные сообщения и Интернет вещей, а также в распределенных системах с огромными объемами неструктурированных данных. Следовательно, эти системы основаны на записи, и для удовлетворения потребностей этих систем база данных должна иметь возможность быстро вставлять данные. Типичные базы данных плохо подходят для подобных сценариев, поскольку они не могут удовлетворить требования высокой доступности, согласованности в конечном счете, гибкости неформатированных данных и малой задержке.
Появилось дерево LSM (дерево слияния с логарифмической структурой). LSM — это не структура данных, подобная B-дереву, а система. В системе LSM нет замены данных на месте; после записи данных на диск они никогда не изменяются. Очевидно, что это система записи только для добавления. Некоторые файловые системы с журнальной структурой, такие как ext3/4, используют аналогичный принцип. Таким образом, система ведет себя как последовательный журнал данных. По сути, LSM-системы используют преимущества последовательной записи. Традиционные жесткие диски могут записывать до 100 МБ/с, в то время как современные твердотельные накопители работают быстрее при последовательной записи. Фактически, SSD-накопители имеют некоторый встроенный параллелизм, который позволяет им одновременно записывать от 16 до 32 МБ данных. Характеристики LSM-дерева и SSD очень хорошо совпадают. Последовательная запись намного быстрее случайной записи.
Чтобы правильно понять приведенный выше сценарий, давайте кратко рассмотрим, как база данных Facebook Cassandra использует принципы LSM.
Cassandra или любая система LSM поддерживает одну или несколько структур данных в памяти (например, memtables на диаграмме выше), используемых для хранения данных перед записью на диск, таких как суббалансированные деревья (AVL), красно-черные деревья, B- деревья или пропустить столы. Эта структура данных в памяти поддерживает упорядоченный набор данных. Различные реализации LSM используют разные структуры данных для удовлетворения различных потребностей, и стандартной реализации LSM не существует. Когда данные, хранящиеся в памяти, превышают настроенный порог, данные, хранящиеся в памяти, помещаются в очередь, которая будет записана на диск. Чтобы сбросить данные, Cassandra последовательно записывает отсортированные данные на диск. На диске поддерживается структура данных под названием «SSTable» (таблица отсортированных строк), которая представляет собой упорядоченный снимок данных, записанных в файл.SSTable является неизменной. Система LSM может управлять несколькими файлами на диске.
Поэтому, если данные не найдены в памяти, Cassandra необходимо просканировать SSTables на всех дисках для поиска данных. Таким образом, операция чтения Cassandra выполняется относительно медленнее, чем операция записи, но есть несколько способов, с которыми вы можете справиться. Cassandra или другая система LSM, работающая в фоновом режиме, будет сжата, чтобы уменьшить количество SSTable. Программа сжатия для сортировки слиянием SSTable, чтобы обнаружить, что вставка новых данных SSTable новой сортировки и удаление старых SSTables. Но использование программы сжатия иногда не справляется с количеством операций обновления в базе данных миллионов.
Поэтому применяются некоторые вероятностные структуры данных, такие как фильтры Блума, чтобы быстро определить, существуют ли какие-либо данные в SSTable. Фильтры Блума очень подходят для оценки данных в памяти, поскольку для вероятностных оценок существования данных требуется большое количество случайных запросов. Алгоритм фильтров Блума может значительно снизить стоимость обхода и запросов SSTables. Таким образом, система LSM решает проблему, заключающуюся в том, что операции записи занимают много времени в больших данных. Системы LSM также имеют проблемы с усилением чтения — больше данных, чем на самом деле необходимо прочитать. Итак, есть ли решение между B Tree и LSM Tree, чтобы дать нам оптимальную (не обязательно точную) эффективность чтения и записи?
Fractal Tree Index — это структура данных, основанная на B-Tree. По словам разработчикаbenchmark, эта структура данных имеет лучшую производительность, чем B-Tree. Фрактальное дерево поддерживает кэширование информации на нелистовых узлах. Высокопроизводительный механизм хранения MySQL Tokudb использует фрактальное дерево.
Как показано на рисунке выше, в Fractal Tree любые выполняемые вами операции, такие как добавление столбцов, удаление столбцов, вставка, обновление и т. д., будут храниться в виде сообщений об операциях на неконечных узлах. Поскольку операции просто хранятся в кэше или любом вторичном индексном буфере, все операции выполняются быстро. Когда кэш узла заполнен, эти сообщения об операциях будут последовательно передаваться от корневого узла через нелистовые узлы к листовым узлам. Конечные узлы по-прежнему хранят реальные данные. При чтении операция чтения рассматривает все сообщения операции на узле пути запроса, чтобы получить реальное состояние данных. Но так как tokudb делает все возможное, чтобы кэшировать все нелистовые узлы в памяти, этот процесс тоже быстрый.
Блоки в tokubd могут иметь размер до 4 МБ вместо 16 КБ в InnoDB. Этот размер позволяет загружать или записывать больше данных за одну операцию ввода-вывода, что также помогает сжимать больше данных за раз, чтобы уменьшить размер хранилища данных на диске. Поэтому tokudb подчеркивает, что лучшее сжатие данных и меньше дисковых операций ввода-вывода могут быть достигнуты с большими размерами блоков. tokudb утверждает, что их механизм хранения работает быстрее, чем InnoDB, обеспечивая более высокую скорость чтения и записи, чем InnoDB, и tokudb также утверждает, что у него меньше проблем с фрагментацией, он также поддерживает многокластерные индексы и т. д. На следующем рисунке представлена соответствующая статистическая диаграмма эталона:
Только тесты в вашей системе могут помочь вам оценить правильные точки данных и решения для ваших нужд. Но механизм хранения MySQL будет продолжать совершенствоваться и удовлетворять возникающие потребности. Дерево LSM — это система для сценариев с большим количеством операций записи, а дерево B — для приложений с традиционными сценариями. Индексы фрактального дерева устраняют некоторые недостатки индексов B-дерева. Поэтому в будущем будут постоянные технологические инновации, включая технологии хранения баз данных, аппаратное обеспечение, дисковые накопители и операционные системы, давайте подождем и увидим.
Подпишитесь на последние статьи, добро пожаловать в мою публичную учетную запись WeChat