Часто бывает неожиданным, как мало мы знаем о том, как работают базы данных, учитывая, что они хранят почти все состояния наших приложений. Тем не менее они являются фундаментом успеха большинства систем. Итак, сегодня я объясню две наиболее важные темы при работе с индексами и транзакциями РСУБД.
Не вдаваясь в подробности особенностей базы данных, я расскажу все, что вы должны понимать об индексах РСУБД. Я кратко коснусь транзакций и уровней изоляции и того, как они могут повлиять на ваше мнение о конкретных транзакциях.
Что такое РСУБД?
Реляционная база данных – это цифровая база данных, основанная на модели реляционных данных, предложенной Э.Ф. Коддом в 1970 году. Для обслуживания реляционных баз данных используется система управления реляционными базами данных (СУБД). Многие системы реляционных баз данных имеют возможность использовать SQL (Язык структурированных запросов) для запроса и сопровождения базы данных. Примерами могут служить MySQL и PostgreSQL.
Что такое индекс?
Индексы — это структура данных, которая помогает сократить время поиска запрошенных данных. Индексы достигают этого за счет дополнительных затрат на хранение, память и поддержание их в актуальном состоянии (более медленная запись), что позволяет нам пропустить утомительную проверку каждой строки таблицы.
Подобно указателю в конце учебника он помогает вам попасть на нужную страницу. Я не большой поклонник аналогии с книгой, так как сравнение быстро перестает быть корректным, когда мы углубляемся в индексы базы данных, но тем не менее аналогия позволяет отлично понять тему.
Зачем нужны индексы?
Небольшие объемы данных поддаются управлению (подумайте о списке посещаемости для небольшого класса), но когда они становятся больше (подумайте о реестре рождений для большого города), они становятся менее управляемыми. Все, что раньше было быстрым, становится медленным, слишком медленным.
Подумайте, как изменилась бы ваша стратегия, если бы вам пришлось искать что-то на одной странице, а не на тысяче страниц имен. Нет, серьезно, остановитесь на секунду и подумайте.
По мере роста, системы собирают и хранят больше данных, что в конечном итоге приводит к описанной выше проблеме.
Как работают индексы?
Таким образом, ответ на вопрос, который часто задается выше, заключается в том, чтобы логически хранить эти данные в зависимости от того, как вы будете их искать. Это означает, что если вы хотите искать в списке по имени, вы должны отсортировать список по имени. Есть несколько проблем с этой стратегией. Я озвучу их в виде вопросов для читателей:
- Что делать, если вы хотите искать данные несколькими способами?
- Как бы вы справились с добавлением новых данных в список? Данный способ быстрый?
- Что бы вы сделали с обновлениями?
- Что такое O-нотация в этих задачах?
Есть о чем подумать. Независимо от вашей первоначальной стратегии, нам определенно нужен способ поддерживать порядок, чтобы мы могли быстро получать релевантные неупорядоченные данные (подробнее об этом позже).
Возьмем пример ниже.
+─────+─────────+──────────────+
| id | name | city |
+─────+─────────+──────────────+
| 1 | Mahdi | Ottawa |
| 2 | Elon | Mars |
| 3 | Jeff | Orbit |
| 4 | Klay | Oakland |
| 4 | Klay | Oakland |
| 5 | Lebron | Los Angeles |
+─────+─────────+──────────────+
Базовые данные распределяются по хранилищу беспорядочно и распределяются явно случайным образом. В настоящее время большинство производственных серверов поставляются с твердотельными накопителями, но в некоторых случаях вам понадобятся вращающиеся диски (жесткие диски), но, честно говоря, их становится все меньше и меньше, поскольку цены на твердотельные накопители значительно снижаются.
SSD vs. HDD
Основное различие между твердотельным накопителем (SSD) и жестким диском (HDD) заключается в том, как данные хранятся и как к ним осуществляется доступ. Жесткие диски используют механические вращающиеся диски и движущуюся головку чтения/записи для доступа к данным (задержка), в то время как твердотельные накопители используют гораздо более быстрые чипы памяти, особенно при чтении большого количества небольших файлов. Поэтому, если цена не является проблемой, твердотельные накопители — лучший вариант, тем более что современные твердотельные накопители почти так же надежны, как и жесткие диски.
Теперь чтение этого небольшого объема данных в памяти выполняется довольно быстро и относительно легко сканируется. Что, если данные, которые мы ищем, не могут быть полностью кэшированы в памяти? или время чтения всех данных с диска занимает слишком много времени?
+──────────+─────────+───────────────────+
| id | name | city |
+──────────+─────────+───────────────────+
| 1 | Mahdi | Ottawa |
| 2 | Elon | Mars |
| 3 | Jeff | Orbit |
| 4 | Klay | Oakland |
| 5 | Lebron | Los Angeles |
| ... | ... | ... |
| 1000000 | Steph | San Francisco |
| 1001000 | Linus | Portland |
+───────+─────────+──────────────────────+
Итак, я видел эту проблему раньше. Вот как действует большинство разработчиков: нам нужен словарь (хеш-мэп) и способ добраться до конкретной строки, которую мы ищем, без необходимости сканировать медленный диск, считывая тонны блоков, чтобы увидеть, есть ли нужные нам данные.
Это так называемые листовые узлы индекса, которым дается определенный столбец для индексации и которые могут хранить расположение соответствующих строк.
Эти конечные узлы индекса представляют собой сопоставление между индексированным столбцом и тем местом, где на диске находится соответствующая строка. Это дает нам быстрый способ добраться до определенной строки, если вы ссылаетесь на нее по индексированному столбцу. Сканирование индекса может быть намного быстрее, так как это компактное представление (меньше байтов) столбца, по которому вы ищете. Это экономит ваше время на чтение множества блоков в поисках запрошенных данных и гораздо удобнее кэшируется, что еще больше ускоряет весь процесс.
Масштаб данных часто работает против вас, и сбалансированные деревья — первый инструмент в вашем арсенале против него.
Листовые узлы этих индексов имеют одинаковый размер, и мы пытаемся сохранить как можно больше таких конечных узлов в каждом блоке. Поскольку эта структура требует сортировки (логически, а не физически на диске), нам нужно решить проблему быстрого добавления и удаления данных. Старый добрый связанный список управляет этим точнее, чем двусвязный список.
Блоки
В вычислительной технике блоки представляют собой группу байтов, которые обычно содержат фиксированное количество записей, которые ограничены общей длиной (длиной блока). Таким образом, если бы мы рассчитали количество байт, которое потребуется для хранения строки, деленное на длину блока, результат показал бы нам, сколько строк можно прочитать из определенного блока.
На очень низком уровне вы можете использовать это, чтобы рассуждать о том, насколько производительными могут быть ваши системы. Quick Maths™ может быть очень эффективным при планировании производственных мощностей.
Преимуществ здесь в два раза больше: это позволяет нам читать конечные узлы индекса как вперед, так и назад, и быстро перестраивать структуру индекса, когда мы удаляем или добавляем новые строки, поскольку мы просто модифицируем указатели — короче, мощная штука.
Связанный список
Связанный список – это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый фрагмент указывает на следующий. Это структура данных, состоящая из набора узлов, представляющих последовательность вместе. В своей самой простой форме каждый узел содержит данные и ссылку на следующий узел в ряду.
Поскольку эти конечные узлы физически не расположены на диске по порядку (помните, что указатели поддерживают сортировку в двусвязном списке), нам нужен способ добраться до нужных конечных узлов индекса.
Сбалансированные деревья (B-Tree)
Таким образом, вы можете задаться вопросом, где вы сделали серьезную ошибку, читая о B-деревьях, которые вы ненавидели со школы. Я понимаю, что эти вещи скучны, но они высокоэффективны и заслуживают вашего внимания.
B+Tree позволяет нам построить древовидную структуру, в которой каждый промежуточный узел указывает на наивысшее значение узла соответствующих конечных узлов. Это дает нам четкий путь для поиска конечного узла индекса, который будет указывать на необходимые данные.
Эта структура строится снизу вверх так, что промежуточный узел покрывает все конечные узлы, пока мы не достигнем корневого узла наверху. Эта древовидная структура получила название «сбалансированная», потому что глубина одинакова по всему дереву.
B-Tree vs. B+Tree
Основное отличие, которое демонстрируют деревья B+, заключается в том, что промежуточные узлы не хранят на них никаких данных. Вместо этого, все ссылки на данные связаны с конечными узлами, что позволяет улучшить кэширование древовидной структуры.
Во-вторых, конечные узлы связаны, поэтому, если вам нужно выполнить сканирование индекса, вы можете выполнить один линейный проход, а не обходить все дерево вверх и вниз и загружать больше индексных данных с диска.
Логарифмическая масштабируемость
Я хочу сделать здесь небольшое отступление, чтобы показать всю мощь этой структуры. Конечно, большинство разработчиков знают об экспоненциальном росте данных и, в идеале, об оценках вашей компании. Но к сожалению, масштаб данных часто работает против вас, и сбалансированные деревья — первый инструмент в вашем арсенале.
В зависимости от количества элементов, на которые могут ссылаться промежуточные узлы (M), плюс общая глубина дерева (N), мы можем ссылаться M на N объектов.
Вот таблица, иллюстрирующая концепцию со значением M, равным 5.
Так как количество конечных узлов индекса увеличивается экспоненциально, высота дерева растет невероятно медленно (логарифмически) относительно количества конечных узлов индекса. Это в сочетании со сбалансированной высотой дерева позволяет почти мгновенно идентифицировать соответствующие конечные узлы индекса, которые указывают на фактические данные на диске.
Разве это не потрясающе!
Что такое транзакция?
Транзакция – это группа последовательных операций, которая представляет собой логическую единицу работы с данными. Поэтому операция должна либо произойти в полной мере, либо не произойти вовсе. Я бы сказал, что большинству систем не нужно управлять транзакциями вручную, но бывают ситуации, когда повышенная гибкость играет важную роль в достижении желаемого эффекта. Транзакции в основном касаются I в ACID – Isolation (изолированности).
Что такое ACID?
В информатике ACID (атомарность, согласованность, изолированность, надежность) – это набор свойств транзакций базы данных, предназначенных для обеспечения достоверности данных, несмотря на ошибки, сбои питания и другие сбои.
- Атомарность предотвращает частичное обновление базы данных, что может вызвать более серьезные проблемы, чем полное исключение всей серии.
- Согласованность гарантирует, что транзакция может перемещать базу данных из одного допустимого состояния в другое. Это позволяет соответствовать всем определенным правилам базы данных, а также предотвращать сбои в результате некорректных транзакций.
- Изолированность определяет, как конкретное действие отображается другим пользователям системы.
- Надежность – это свойство, которое гарантирует, что транзакции, которые были совершены, будут сохраняться постоянно.
Эти свойства, как правило, хорошо понятны, но их определения могут не совпадать от системы к системе в зависимости от системы базы данных. Поэтому обязательно ознакомьтесь с каждым из них для вашей производственной базы данных.
Это может быть сделано автоматически, чтобы вы даже не знали, что они совершаются, или вы можете создать их вручную следующим образом:
-- Manual transaction with commit.
BEGIN;
SELECT * FROM people WHERE id =1;
COMMIT or ROLLBACK;
Мы сосредоточимся на времени между BEGIN и COMMIT или ROLLBACK и на том, что происходит с различными другими транзакциями, воздействующими на те же данные.
COMMIT/ROLLBACK
Все транзакции, выполняемые вручную, заканчиваются либо успешным COMMIT, либо ROLLBACK.
COMMITсохраняет изменения (надежность), внесенные текущей транзакцией.ROLLBACKотменяет изменения, внесенные текущей транзакцией.
Для случая, когда вы не управляете транзакциями вручную, если все запросы в транзакции завершены успешно, они фиксируются (COMMIT). Если происходит какой-либо сбой, изменения во время этой транзакции откатываются (ROLLBACK), чтобы обеспечить атомарность всего действия.
О феноменах
В этих изоляциях могут возникать некоторые феномены чтения, и их понимание важно для отладки ваших систем и поиска несоответствий, которые ваша система может допустить.
Неповторяемые чтения
Как показано на изображении выше, неповторяемые чтения происходят, если вы не можете получить согласованное представление данных между двумя последовательными чтениями во время транзакции. В определенных режимах возможна одновременная модификация базы данных, и могут быть сценарии, в которых значение, которое вы только что прочитали, может быть изменено, что приведет к неповторяемому чтению.
«Грязные» чтения
Точно так же «грязное» чтение происходит, когда вы выполняете чтение, а другая транзакция обновляет ту же строку, но не фиксирует работу, вы выполняете другое чтение и можете получить доступ к незафиксированному («грязному») значению, которое не является устойчивым изменением состояния и несовместимо с состоянием базы данных.
Фантомное чтение
Фантомные чтения — это еще один феномен чтения фиксированных данных (committed read), который чаще всего возникает, когда вы имеете дело с агрегатами. Например, вы запрашиваете количество клиентов в конкретной транзакции. Между двумя последующими чтениями другой клиент регистрируется или удаляет свою учетную запись (committed), в результате чего вы получаете два разных значения, если ваша база данных не поддерживает блокировки диапазона для этих транзакций.
Range Locks (блокировки диапазона) лучше всего описывать, иллюстрируя все возможные уровни блокировки:
- Сериализованный доступ к базе данных — заставляет базу данных выполнять запросы один за другим — ужасный параллелизм, однако высочайший уровень согласованности.
- Блокировка таблицы — блокировка таблицы для вашей транзакции с немного лучшим параллелизмом, но одновременная запись в таблицу по-прежнему замедляется.
- Блокировка строк — блокирует строку, над которой вы работаете, даже лучше, чем при блокировкe таблиц, но если эта строка нужна нескольким транзакциям, им придется подождать.
Блокировки диапазона находятся между двумя последними уровнями блокировок. Они блокируют диапазон значений, захваченных транзакцией, и не позволяют вставлять или обновлять в пределах диапазона, захваченного транзакцией.
4 уровня изоляции
Стандарт SQL определяет 4 стандартных уровня изоляции, которые могут и должны быть настроены глобально (могут произойти неприятные вещи, если мы не отнесемся внимательно к уровням изоляции).
REPEATABLE READ (Повторяемое чтение)
Начнем с REPEATABLE READ. Здесь относительно просто понять и установить таблицу для остальных уровней изоляции. Этот уровень изоляции обеспечивает согласованное чтение в рамках транзакции, установленной первым чтением. Эта изоляция поддерживается несколькими способами. Некоторые из них влияют на общую производительность системы, другие нет, но это выходит за рамки этого поста.
Как только мы делаем наше первое чтение (см. рисунок выше.), это представление блокируется на время транзакции, поэтому все, что происходит вне контекста этой транзакции, не имеет значения — committed или нет.
Этот уровень изоляции защищает нас от нескольких известных проблем с изоляцией, в основном от неповторяющихся и грязных чтений. У него есть небольшая несогласованность данных, хотя он привязан к конкретному представлению базы данных. Здесь выгодно сохранять краткосрочные транзакции.
SERIALIZABLE (Упорядочиваемость)
Этот режим работы может быть наиболее строгим и последовательным, поскольку он позволяет выполнять только один запрос за раз.
Все типы феномена чтения больше невозможны, поскольку база данных выполняет запросы один за другим, переходя из одного стабильного состояния в другое. Здесь больше нюансов, но зато все происходит более-менее точно.
Более новые распределенные базы данных используют преимущества этого уровня изоляции для обеспечения согласованности. CockroachDB — пример такой базы данных.
READ COMMITTED (Чтение фиксированных данных)
Этот режим изоляции отличается от REPEATABLE READ тем, что каждое чтение создает свой собственный непротиворечивый (зафиксированный) моментальный снимок времени. В результате этот режим изоляции подвержен фантомным чтениям, если мы выполняем несколько операций чтения в рамках одной и той же транзакции.
READ UNCOMMITTED (Чтение незафиксированных данных)
В качестве альтернативы уровень изоляции READ UNCOMMITTED не поддерживает блокировку транзакций и может видеть незафиксированные данные по мере их возникновения, что приводит к «грязным» чтениям. В общем, действительно ночной кошмар для некоторых систем.
Комментарии