предисловие
Операции запросов большинства проектов составляют большую часть обработки данных, и оптимизация запросов стала центром внимания многих баз данных. Текущие продукты баз данных будут использовать технологию индексирования, такую как MySql, Oracle, SqlServer, Hive и т. д., поскольку это связано с запросом очень больших данных базы данных, существуют разные схемы реализации для соответствия различным функциям продукта и сценариям приложений.
Вообще говоря, целью индекса является повышение скорости запросов.В различных базах данных хорошо инкапсулированы технические детали индекса, что полностью прозрачно для разработчиков или сопровождающих в практических приложениях. Однако автор считает, что глубокое понимание технологии запросов является необходимым процессом для крупномасштабной обработки данных для разработчиков; для архитекторов полное понимание технологии индексации часто может быть использовано для всестороннего анализа выбора решений по обработке данных и сделать хорошее суждение.
В этом документе рассматриваются ключевые проблемы, связанные с запросом на уровне операционной системы в сочетании с аппаратным процессом ввода-вывода, чтобы расширить идею проектирования технологии индексных запросов.Весь процесс будет анализировать технические детали индекса. на уровне ввода-вывода.
Знание ввода-вывода
После десятилетий развития производительность компьютеров значительно улучшилась во всех аспектах, но всегда есть фактор, ограничивающий высокоскоростную работу компьютеров, а именно проблема ввода-вывода.
Многие разработчики, кажется, не имеют преднамеренного понимания ввода-вывода, но это неизбежная тема в области обработки данных.Википедия объясняет ввод-вывод следующим образом:
I/O(Английский:Input/Oвыход), то естьввод, вывод, обычно ссылаясь на данные ввнутренняя памятьВвод и вывод во внешнюю память или другие периферийные устройства и из них. Ввод-вывод — это связь между системой обработки информации (например, компьютером) и внешним миром (возможно, человеком или другой системой обработки информации). Входы — это сигналы или данные, полученные системой, а выходы — это сигналы или данные, отправленные из нее.
Прежде чем понять ввод-вывод, нам нужно понять, что в современных компьютерах диски и память всегда играли важную роль.Большинство постоянных данных будут выбирать диски с большей емкостью и меньшей стоимостью, а память используется в качестве кэша.Роль обеспечивает поддержка памяти для компьютера. В запросе данных ввод-вывод можно понимать как процесс чтения данных с диска или из памяти.При анализе производительности запроса необходимо иметь определенную чувствительность к стоимости ввода-вывода.
Какова стоимость ввода-вывода?
Существенное улучшение производительности компьютера неотделимо от постоянного улучшения скорости обработки памяти и ЦП, но скорость повышения производительности вызвала определенный разрыв между ЦП и памятью.Скорость обработки ЦП в обычных компьютерах достигается с 1980 года. , 10 000-кратное улучшение, в то время как диск улучшился только примерно в 30 раз. Это вызвало явление, что большую часть времени ЦП должен ждать работы диска.Для полного процесса обработки данных диск часто занимает основное время работы.Здесь мы можем понимать стоимость ввода-вывода как стоимость каждого раза с диска, потребление времени чтения памяти.
Предыдущая статья【понимать существование процесса】Автор анализирует основной процесс операций обработки ЦП.Из миллиардов тактов в секунду ЦП у нас есть определенное восприятие, то есть скорость обработки ЦП значительно превышает общепринятое понимание.Насколько это быстро? Тактовый цикл текущего 4-ядерного ЦП достиг примерно 0,4 нс, что означает, что операция инструкции может выполняться каждые 0,4 нс, а время доступа к памяти составляет около 9 нс (рекомендуется понимать временной разрыв между нс и мс). ), хотя это примерно в 20 раз хуже, но, кажется, все еще на том же уровне величины. Диск возмутителен.Механический диск по-прежнему поддерживает время доступа 29 мс, что является огромной разницей порядка миллионов и десятков миллионов по сравнению с памятью и процессором! Почему диск так плохо справляется с вводом-выводом по сравнению с памятью? Обратитесь к предыдущей статье【Базовые понятия о диске и памяти], мы можем понять из принципа хранения памяти и носителя.
Поэтому узкое место обработки данных часто лежит в вводе-выводе, а узкое место ввода-вывода — в процессе управления жесткими дисками. представление.
Чтобы было ясно, низкая производительность ввода/вывода диска не означает, что он не может быть принят рынком. Поскольку стоимость производства дисков имеет огромное преимущество по сравнению с другими высокоскоростными запоминающими устройствами, ввод-вывод дисков по-прежнему остается проблемой, с которой необходимо бороться в течение длительного времени.
Просмотр процесса дискового ввода-вывода с уровня ОС
С аппаратной точки зрения мы признаем ограничения, связанные с самой памятью, поэтому в большинстве сценариев оптимизация запросов будет в основном выполняться на программном уровне.Различные операционные системы имеют хорошую поддержку ввода-вывода на нижнем уровне, и количественные затраты на ввод-вывод должны быть тщательно изучены на уровне операционной системы.
В ранних компьютерных системах есть только три уровня хранения: регистры ЦП, основная память DRAM (память) и дисковое хранилище. ОС оптимизирована для этих трех носителей данных. Из-за увеличивающегося разрыва в производительности между ЦП и памятью в процессе разработки , текущий компьютер Между регистром и памятью размещается многослойная кэш-память, а в некоторых случаях между памятью и диском размещается SSD (твердотельный накопитель). Текущая ОС использует определенный алгоритм, чтобы хорошо справляться с попаданиями в кэш и максимально повышать общую производительность ввода-вывода, но это не мешает нашему анализу основной проблемы.В большинстве случаев проблема, которая нужна ОС для решения по-прежнему данные с диска.В процессе перехода к памяти, чтобы упростить модель анализа, мы думаем о задаче как из памяти, так и с диска.
На диске данные управляются блоками, и каждый блок обычно имеет размер 4 КБ.Мы можем абстрагироваться от того, что диск представляет собой структуру хранения, в которой многие блоки расположены в порядковых номерах:
Когда ОС необходимо получить определенные данные с диска, будет сгенерировано прерывание ввода-вывода.Это прерывание ввода-вывода принесет определенный номер блока для привода диска для выполнения операций поиска и чтения блоков данных.Эти операции основаны на в определенном блоке.Начнем с того, что минимальная единица считываемых данных также составляет 4 КБ, а это означает, что если данные, которые вы получаете, меньше 4 КБ или данные размещены по определенному смещению в блоке, диск все равно будет передать все содержимое блока в память, начиная с этого блока.
Для данных менее 4 КБ, если они помещаются в определенный блок, часто необходимо один раз прогнать диск, то есть процесс ввода-вывода, но если данные занимают всего два блока, то их нужно прогнать диск для чтения Есть два блока данных (целевое содержимое запроса на следующем рисунке должно читать блок N, блок N+1):
Следовательно, мы должны попытаться избежать описанной выше ситуации и выровнять целевые данные по блокам, что может уменьшить количество чтений блоков при дисковом вводе-выводе.
Но что, если сами целевые данные большие и должны занимать несколько блоков? Очевидно, если предположить, что целевые данные последовательно занимают N блоков, то диск выполнит N операций чтения:
Но если целевые данные хранятся не последовательно, а разбросаны по различным блочным областям:
Выполняются те же три операции блочного чтения, но с точки зрения физической структуры диска диск должен выполнять две операции блочного позиционирования, то есть процесс позиционирования головки в вводе-выводе. Перед тем, как диск прочитает целевые данные, магнитная головка должна быть расположена в начале заданного блока.Если промежуточные целевые данные разбросаны по разным участкам блока, магнитная головка должна совершить определенное расстояние физического вращения, которое очевидно, занимает время чтения, а также это ключевое различие между последовательным чтением и случайным чтением! Следовательно, идеальная ситуация состоит в том, что позиция хранения целевых данных на диске не только выровнена по блокам, но и постоянно сохраняется, по крайней мере, для управления степенью дискретности данных на диске до низкого уровня.
Когда ЦП выполняет какую-либо инструкцию, всякий раз, когда задействован дисковый ввод-вывод, ОС предварительно считывает данные в пространство кэш-памяти.Благодаря приведенному выше введению, цикл доступа к памяти и цикл обработки ЦП не слишком велики в Существует большая разница, поэтому в том, как база данных управляет данными, больше энергии тратится на сокращение дискового ввода-вывода.
Управление данными и поиск
В базе данных будет специальное управление файлами для разных таблиц.Файл можно понимать как последовательность записей.Файловая организация разных таблиц на диске может быть разной. Вообще говоря, реляционная база данных, такая как mysql, представляет собой базу данных строк, каждая запись в таблице может пониматься как строка, и содержимое различных полей в каждой строке хранится на диске последовательно, а позиции разных строк на диска разные, не обязательно по порядку, возможно, разбросаны блоками по разным регионам.
Рассмотрим создание пользовательской таблицы user в базе данных:
CREATE TABLE `user` (
`id` varchar(20),
`name` varchar(20),
`age` numeric(3,0)
)Предполагая, что база данных выделяет максимальную емкость для каждого поля, а именно id (20 байт), name (20 байт), age (2 байта), мы создаем следующие 3 записи:
| запись 1 | 1 | cary | 25 |
| запись 2 | 2 | harry | 26 |
| запись 3 | 3 | marry | 23 |
Мы знаем, что каждая строка записей занимает фиксированный размер 42 байта, и три записи хранятся последовательно в начале:
Когда мы выполняем операцию запроса:
select * from user where id=2;Очевидно, что этот запрос загружает содержимое соответствующего блока в память и начинает обрабатывать его построчно, отфильтровывая все данные с id = 2. Модель выполнения ЦП выглядит следующим образом:
do begin
for each row in user {
if row.id=2 {
select row;
}
}
endСложность ввода-вывода всего процесса составляет O(1), а вычислительная сложность процессора — O(3). Теперь предположим, что каждая строка данных по-прежнему хранится по порядку, но количество строк увеличено до 1 миллиона строк:
| запись 1 | 1 | cary | 25 |
| запись 2 | 2 | harry | 26 |
| запись 3 | 3 | marry | 23 |
| ....... ....... ....... |
|||
| запись 999999 | 999999 | joke | 28 |
| запись 1000000 | 1000000 | zerui | 26 |
Без учета выравнивания блоков 1 миллион строк данных будет занимать блоки max(1000000*42Byte/4Kb)=42000. В случае выполнения вышеуказанного SQL-запроса сложность ввода-вывода составляет O(42000), а ЦП вычислительная сложность O(1000000). При таких условиях величины вычислительная нагрузка машины значительно возрастет, а при постоянном увеличении табличных данных сложность будет возрастать линейно, что абсолютно недопустимо!
Следовательно, должна быть технология для решения проблемы извлечения большого количества данных.Мы сосредоточимся на двух основных требованиях: одно — уменьшить ввод-вывод диска, а другое — уменьшить сложность обработки ЦП. , и появился индекс.
Введение в индексирование
Теперь у нас есть базовая концепция стоимости запроса данных. Эта стоимость отражается на операциях ввода-вывода и ЦП. Как индекс решает эти две проблемы?
В структуре данных пользовательской таблицы в приведенном выше примере мы предполагаем, что данные строки хранятся на диске в порядке идентификатора.Когда мы извлекаем данные в соответствии с условием идентификатора, самый простой способ — добавить структуру данных для поиска Целевой диапазон. :
| значение идентификатора | номер блока целевой записи |
| 1 | N |
| 10000 | N+K |
| 20000 | N+2K |
| ... | |
| 1000000 | N+100K |
Эта структура описывает условие сопоставления. Слева — значение атрибута идентификатора таблицы, а справа — номер блока, записанного на диске. Когда мы хотим запросить запись с идентификатором = 100000, мы можем предсказать, что целевая запись размещается в блоке диска через таблицу сопоставления.Интервал составляет [N+10K, N+11K], поэтому ОС нужно только управлять диском для чтения блоков до 1K, сложность ввода-вывода всего процесса составляет не более O(1K), а сложность обработки ЦП не более O(10000), производительность обработки улучшена в 10000 раз!
Структура данных с таким простым дизайном называется последовательным индексом, а информация индекса также помещается в управление дисковым пространством.Каждый раз, когда поле id извлекается, база данных будет отдавать приоритет поиску целевого блока из индексной таблицы и затем извлеките целевую информацию из целевого блока. Согласно структуре индекса, разработанной апелляцией, степень детализации интервального деления составляет 10000. Видно, что всего строк 100. Предположим, что мы установили 10 байт пространства для каждой строки записей, вся структура индекса будет занимать 1000 байт. , менее 1 КБ, поэтому иногда мы можем напрямую. Структура индекса предварительно загружается в память, поэтому процесс запроса индекса не будет включать потребление ввода-вывода на диске, что дает нам новую идею для оптимизации запроса скорость!
Однако простота структуры последовательного индекса поддерживается строгим требованием хранения записей строк на диске, а записи строк должны храниться на диске в порядке, соответствующем значению идентификатора. В реальной бизнес-среде данные имеют высокую сложность и частоту изменения.Некоторые строки данных будут удалены, а освободившееся место будет занято другими последовательно вставленными строками.Последующие вставленные записи также могут отображаться на диске случайным образом. А раз целевые данные строк хранятся не по порядку, деление последовательного индекса на блочный интервал будет бессмысленным!
| запись 1 | 1 | cary | 25 | |
| запись 2 | 2 | harry | 26 | |
| запись 3 | 897 | karry | 24 | Исходная запись с идентификатором = 3 была удалена, а запись с идентификатором 897 впоследствии была вставлена. |
Здесь мы вводим новую структуру данных: двоичное дерево, Когда целевые данные хранятся в дискретном случайном состоянии на диске, мы все еще надеемся добиться быстрого поиска.
На основе бинарного дерева добавим следующие условия: левый дочерний узел меньше корневого узла, а правый дочерний узел больше или равен корневому узлу Допустим, в пользовательской таблице есть записи с id 2, 3, 5, 6, 7 и 8, то будет следующая форма:
Построенная таким образом структура индекса включает в себя все значения атрибута id. Для 1 миллиона строк данных структура индекса имеет 1 миллион узлов, и каждый узел также содержит конкретное местоположение идентификатора, записанного на диске. запись с id=3, мы обнаруживаем, что после оценки корневого узла левый указатель просто указывает на содержимое узла 3, так что можно получить окончательное расположение записи на диске.
Итак, как проанализировать проблему стоимости, связанную со структурой индекса двоичного дерева? Благодаря этому структурному правилу это фактически эквивалентно выполнению операции дихотомии над записью.С математической точки зрения каждое суждение представляет собой поиск по порядку величины половины числа. В приведенном выше примере всего 6 записей, нам нужно сделать не болееlog2N= 6 - количество суждений N = 3. Для структуры индекса из 1 миллиона узлов нам нужно запросить идентификатор не болееlog2N= 1000000, то есть получение узла N = 20, то есть максимальная сложность дискового ввода-вывода составляет O (20). Предполагая, что целевая запись увеличивается до 10 миллионов строк, сложность ввода-вывода составляет всего O ( 23) Ввод-вывод Экспоненциальная зависимость между сложностью и количеством целевых строк записи значительно смягчает растущую тенденцию затрат на ввод-вывод!
Существует прямая зависимость между сложностью ввода/вывода и высотой бинарного дерева.Для построения бинарного дерева высотой до 20 слоев необходимо миллион узлов.Предполагается, что содержимое каждого узла содержит: левый указатель (4 байта), значение идентификатора (8 байт), правый указатель (4 байта), указатель целевой записи (4 байта), занимают в общей сложности 20 байт, тогда индекс будет занимать не менее 20 байт * 1000000 = 20 МБ дискового пространства, идеальная ситуация загружать структуру индекса непосредственно в память, так что только потребление памяти O (20), но отличается от производительности разных машин, 20 МБ все еще немного экстравагантно для драгоценных ресурсов памяти.Может ли количество операций ввода-вывода в уровень индекса будет уменьшен на диске?
В нашей конструкции индекса бинарного дерева стоимость каждого ввода-вывода дает половину эффекта фильтрации данных, Исходя из этого, мы надеемся максимизировать величину более низкой фильтрации. Мы распространяем идею на n-арное дерево, для n-арного дерева мы можем получитьlognNЭкспоненциальная модель , где n представляет количество подчиненных указателей каждого узла, предполагая, что n = 10, тогдаlog10N=1000000 имеет сложность N=5 или O(5), что в 4 раза больше производительности ввода-вывода по сравнению с O(20).Что касается количества n ответвлений, мы разработали следующую форму:
Каждый узел будет иметь четыре указателя, и каждый указатель также следует правилам установки бинарного дерева апелляции: левый указатель значения id указывает на подчиненный диапазон, меньший, чем значение id, а правый указатель значения id указывает на подчиненный диапазон больше, чем значение идентификатора. Все n-арное дерево интуитивно более «толстое», что означает, что после ввода-вывода узла мы можем сделать большее подразделение целевых данных! Из введения дискового ввода-вывода выше мы узнали, что диск использует каждый блок как наименьшую единицу работы, поэтому многие современные продукты баз данных намеренно используют размер блока как размер конечного узла при проектировании n-арного дерева. Занятость различных элементов листового узла следующая: левый и правый указатели занимают по 4 байта, значение идентификатора равно 8 байтам, а указатель целевой записи равен 4 байтам, тогда блок диска размером 4 КБ может вместить примерно 250 указателей более низкого уровня, и нужно только 1 миллион строк целевых записейlog250N= 1000000, то есть число операций ввода-вывода N = 3, что полностью улучшает утилиту извлечения, приносимую каждым вводом-выводом узла!
Следовательно, понимая структуру индекса, используемую текущей таблицей базы данных, мы можем хорошо провести анализ затрат для некоторых запросов в реальном проекте с помощью математических задач, особенно в среде больших данных, мы можем хорошо оценить время запроса. представление.
В настоящее время различные продукты баз данных учитывают реальные сценарии приложений при проектировании индексов.Метод хранения файлов таблиц базы данных на диске определяет, какую структуру индекса необходимо использовать. Для целевых данных, хранящихся на диске по порядку, быстрое извлечение часто может быть достигнуто за счет последовательного индексирования. Например, некоторые продукты для работы с большими данными сами по себе ориентированы на производительность запросов, а табличные данные могут только добавляться без поддержки операций удаления и изменения. когда данные таблицы удаляются и модифицируются. Изменения должны быть глобально отформатированы, чтобы обеспечить упорядоченное хранение данных на диске. Транзакционные базы данных, такие как mysql, больше ориентированы на рутинные бизнес-операции, и добавление, удаление и изменение данных должны полностью поддерживаться, распределение данных на диске более сложное, а структура индекса часто принимает древовидную структуру.
послесловие
Разработка индекса — относительно сложный процесс, и в этой статье мы надеемся построить модель анализа затрат на ввод-вывод при запросе данных в мозгу. Индекс значительно повышает скорость запроса данных базы данных, но мы также должны четко осознавать, что обслуживание самой структуры индекса — это не маленький проект, сложность различных структур индекса напрямую связана с процессом обслуживания самой структуры индекса. Для информации о сложности ввода-вывода и вычислительной сложности ЦП, которые необходимо предпринять, вы можете обратиться к соответствующей информации для создания и обслуживания индекса.