Внутреннее устройство баз данных

Copyright © 2019 Oleksandr Petrov

Данный документ предоставляется по лицензии Creative Commons Attribution 3.0 License, за исключением разделов со специальными оговорками. http://creativecommons.org/licenses/by/3.0/legalcode

oreilly.com

2019-11-23

Автор

Олександр Петров

Выпускающий редактор

Майкл Лукайдис

Редактор выпуска

Мишель Кроунин

Редактор производства

Кристофер Фаучер

Литературный редактор

Ким Коуфир

Корректор

Соня Саруба

Составитель индекса

Джудит МакКонвил

Художник- декоратор

Дэйвид Футейто

Разработчик обложки

Карен Монтгомери

Иллюстратор

Ребекка Димарест

Питеру Хинтьенсу, от которого я получил свою первую подписанную книгу:

вдохновляющему программисту распределённых систем, автору, философу и другу.

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

Ещё в 2000, когда вы выбирали базу данных, у вас имелось бы лишь несколько вариантов и большинство из них находилось бы в сфере реляционных баз данных, а потому различия между ними были бы относительно малыми. Естественно, это не означает, что все базы данных были бы абсолютно одинаковыми, но их функциональные возможности и варианты применения были бы очень похожими.

Некоторые из этих баз данных были сосредоточены на горизонтальном масштабировании (вширь) - повышении производительности и увеличении ёмкости за счёт запуска нескольких экземпляров базы данных, действующих как единое логическое устройство: Gamma Database Machine Project, Teradata, Greenplum, Parallel DB2 и прочие. И сегодня горизонтальное масштабирование продолжает оставаться одним из наиболее важных свойств, которое клиенты ожидают от баз данных. Это можно объяснить растущей популярностью облачных служб. Часто более простым является раскрутка некого нового экземпляра и добавление его в кластер,чем масштабировать вертикально (вверх), перемещая свою базу данных в большую, более сложную машину. Миграции могут быть длительными и болезненными, причём потенциально приводят к простоям.

Около 2010 года появился некий новый класс в конечном счёте согласованных баз данных и стали популярными такие термины как NoSQL, а впоследствии и big data. За последние 15 лет сообщество разработчиков программного обеспечения с открытым исходным кодом, крупные интернет- компании и производители баз данных создали настолько много баз данных и инструментов, что легко потеряться, пытаясь разобраться в вариантах применения, деталях и особенностях.

Статья Dynamo [DECANDIA07], опубликованная командой Anazon в 2007, оказала настолько сильное влияние на сообщество баз данных, что за короткий переиод вдохновила на множество вариантов и реализаций. Самыми известными из нихбыли созданная Facebook Apache Cassandra, созданный LinkedIn Проект Voldemort и созданный бывшими инженерами Akamai Riak.

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

В обсуждениях на технических конференциях я часто слышу один и тот же вопрос: "Как мне больше узнать о внутреннем устройстве баз данных? Я даже не знаю с чего начать." Большинство книг по системам баз данных не содержат подробностей о реализации механизмов хранения и охватывают сами методы доступа, такие как B- деревья, на достаточно высоком уровне. Имеется очень мало книг, обсуждающих концепции наиболее позднего времени, например, различные варианты B- деревьев и хранилища структурированных журналов (logstructured storage), поэтому обычно я рекомендую читать статьи.

Всякий, кто читает статьи, знает что это не так просто: вам зачастую не хватает контекста, сама формулировка может быть неоднозначной, между статьями имеется лишь малая связь, или её и вовсе нет, а к тому же их трудно искать. Данная книга содержит краткое изложение важных понятий систем баз данных и может служить руководством для тех, кто желал бы погрузиться глубже во всё это или в качестве некой шпаргалки для тех, кто уже знаком с этими понятиями.

Не все хотят быть разработчиками баз данных, но эта книга поможет людям, строящим программное обеспечение, которые используют системы баз данных: разработчиками программного обеспечения, инженерам, архитекторам надёжных решений, а также управляющим инженерами.

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

Эта книга также для пытливых умов: для тех людей, которые желали бы изучать вещи без непосредственной на то необходимости, тех кто тратит своё свободное время на разбирательство чего- то забавного, на создание компиляторов, написание собственных операционных систем, текстовых редакторов, компьютерных игр, изучение языком программирования и всасывающих новые сведения.

Предполагается что читатель имеет некие навыки разработки серверных систем и работы с базами данных в качестве пользователя. Наличие неких первичных знаний по различным структурам данных поможет погружаться в материал быстрее.

мы часто слышим как люди обсуждают базы данных в терминах тех понятий и алгоритмов, которые их реализуют: "Эта база данных использует gossip для распространения участия" (см. Главу 12), "Они реализовали Dynamo" или "Это в точности так же, как было описано в статье Spanner" (см. Главу 13). Или, когда вы обсуждаете алгоритмы и структуры данных, вы можете слышать нечто навроде "ZAB и Raft имеют много общего" (см. Главу 14). "Bw- дереья подобны B- деревьям, реализованным поверх хранилища структурированного журнала" (см. Главу 6), или, "Они пользуются братскими указателями как в B^link- деревьях" (см. Главу 5).

Для обсуждения сложных понятий нам требуются абстракции и мы не можем обсуждать терминологию всякий раз, как только мы начинаем дискуссию. Наличие ярлыков в самой форме общего языка поможет нам сместить наше внимание к прочим проблемам более высокого уровня.

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

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

Это не книга о системах управления реляционными базами данных, и не о базах NoSQL, а об алгоритмах и понятиях, применяемых всеми видами систем баз данных с сосредоточенностью на механизмах хранения и тех компонентах, которые отвечают за распределённость.

некоторые понятия, такие как планирование очередей, оптимизация запросов, составление расписаний, сама реляционная модель и некоторые иные, они все уже обсуждались в некоторых великолепных учебниках по системам баз данных. Ряд этих понятий уже описывался с точки зрения пользователя, но данная книга сосредоточена на внутреннем устройстве. Вы можете обнаружить некие указатели на полезную литературу в Заключение Части II и в Выводах каждой из глав. В этих книгах вы скорее всего обнаружите ответы на множество вопросов относящихся к базам данных, которые могут у вас иметься.

Язык запросов не обсуждается, так как нет единого общего языка для всех упоминающихся в этой книге системах баз данных.

Для сбора материала данной книги я изучил около 15 книг и более 300 статей, бесчисленное множество блог постов и документацию для различных баз данных с открытым исходным кодом. Отлитым в граните правилом того включать или нет конкретное понятие в эту книгу был вопрос: "Обсуждают ли люди из индустрии баз данных и исследовательских кругов эту концепцию?". Когда ответом является "Да", я добавлял такое понятие в длинный перечень предметов для обсуждения.

Существуют некоторые образцы расширяемых баз данных с подключаемыми компонентами (например, [DECANDIA07]), но они достаточно редки. В то же время имеется множество экземпляров в которых базы данных используют подключаемые хранилища. Точно так же мы редко слышим рассуждения производителей баз данных относительно выполнения запросов, в то время как они настоятельно желают обсуждать сохранение состоятельности своих баз данных.

Наиболее существенные различия между системами баз данных сосредоточены вокруг двух аспектов: как они хранят и как они распределяют свои данные. (Порой также и прочие системы могут быть важными, но они не рассматриваются здесь.) Эта книга разбита на части, в которых рассматриваются подсистемы и компоненты, ответственные за хранение Часть I и за распределение Часть II.

Часть I обсуждает процессы локальных узлов и основное внимание уделяется самому механизму хранения, самому центральному компоненту всей системы базы данных и одному из наиболее значимых отличительных факторов. Прежде всего мы начинаем с самой архитектуры системы управления базой данных и представляем несколько способов классификации систем баз данных на основании её первичного носителя и схемы.

Мы продолжаем работу со структурами хранения и пытаемся понять чем отличаются структуры на основе дисков от хранящихся в памяти, представляем B- деревья и рассматриваем алгоритмы действенного сопровождения структур B- деревьев на диске, включая сериализацию, схему страниц и представление на диске. Позднее мы обсуждаем множество вариантов иллюстрации мощности этой концепции и разнообразие структур данных, на которые оказывают влияние и стимуляцию B- деревья.

Наконец, мы обсуждаем несколько вариантов хранилищ со структурированными журналами, обычно используемыми для реализации файловых систем и систем хранения, мотивы и причины их применения.

Часть II о том, как организовать множество узлов в некий кластер базы данных. Мы начинаем с важности понимания теоретических понятий построения отказоустойчивых распределённых систем, того чем распределённые системы отличаются от приложений с единственным узлом, а также с того, с какими проблемами, ограничениями и сложностями мы сталкиваемся в распределённой среде.

После этого мы глубже погружаемся в распределённые алгоритмы. Здесь мы начинаем с алгоритмов для выявления отказов, помогающих повышать производительность и стабильность через уведомления и отчёты об отказах и обход отказавших узлов. Поскольку многие обсуждаемые далее в этой книге алгоритмы полагаются на понятии лидерства, мы представляем несколько алгоритмов для выбора лидера и обсуждаем их пригодность.

Поскольку одной из самых сложных задач в распределённых системах является обеспечение согласованности данных, мы обсуждаем понятия репликаций, за которыми следуют модели согласованности, возможные расхождения между репликами и согласованность в конечном счёте. Так как системы с окончательной согласованностью при распространении данных полагаются антиэнтропию и сплетни (gossip, болтовню), мы обсуждаем некоторые подходы антиэнтропии и сплетен. Наконец, мы обсуждаем логическую состоятельность в контексте транзакций баз данных и заканчиваем алгоритмами консенсуса.

Было бы невозможно написать эту книгу без всех имеющихся исследований и публикаций. Вы обнаружите множество ссылок на статьи и публикации в самом тексте, в квадратных скобках, например [DECANDIA07]. Вы можете пользоваться этими ссылками для изучения дополнительных подробностей о связанных с ними понятиях.

После каждой главы вы обнаружите раздел Выводов, который содержит связанные с содержимым этой главы материалы для дальнейшего изучения.

В этой книге применяются следующие соглашения:

	Совет
	Этот элемент обозначает некий совет или уловку.

	Замечание
	Данный элемент обозначает некое общее замечание.

	Предостережение
	Этот элемент указывает некое предостережение или предупреждение.

Эта книга здесь для того чтобы помочь вам выполнить ваше задание. В целом, когда пример кода предлагается в этой книге, вы можете использовать его в своих программах или в документации. Вам не требуется обращаться к нам за разрешением, если вы не воспроизводите значительную часть этого кода. К примеру, написание программы, которая пользуется несколькими фрагментами кода из данной книги не требует разрешения. Продажа или распространение CD- ROM с примерами из книг O’Reilly требует разрешение на это. Для ответа на вопрос со ссылкой на данную книгу разрешение не требуется. Включение значительной части кода примера в документацию вашего продукта потребует разрешения.

Мы ценим, но не требуем, указания авторства. Такое указание обычно содержит название, автора, издателя и ISBN, например: "Database Internals by Alex Petrov (O’Reilly). Copyright 2019 Oleksandr Petrov, 978-1-492-04034-7".

Если вы полагаете, что использование примеров кода выходит за рамки указанного выше добросовестного использования или разрешения, свяжитесь с нами через permissions@oreilly.com.

Более 40 лет O’Reilly Media предоставляет обучение технологией и ведением дел, знаний и догадок в помощь успеху предприятий.

Наша уникальная сетевая среда экспертов и новаторов делятся своими знаниями и опытом через книги, статьи, конференции, а также через нашу платформу интерактивного обучения. Платформа интерактивного обучения O’Reilly предоставляет вам доступ по запросу к курсам обучения в реальном масштабе времени, различным тренировочным курсам вживую, пути глубокого изучения, среды интерактивного кодирования и обширную коллекцию текстов и видео от O’Reilly и более чем 200 прочих издательств. Для получения дополнительных сведений обращайтесь, пожалуйста к http://oreilly.com.

Адресуйте, пожалуйста, комментарии и вопросы относительно этой книги самому издательству:

O’Reilly Media, Inc.
1005 Gravenstein Highway North
Sebastopol, CA 95472
800-998-9938 (in the United States or Canada)
707-829-0515 (international or local)
707-829-0104 (fax)
 	   

У нас имеется для данной книги веб страница, в которой мы перечисляем ошибки, примеры и все дополнительные сведения. Вы можете получить доступ к этой странице через http://bit.ly/database-internals.

Для комментариев и технических вопросов относительно данной книги, пожалуйста, направьте электронное письмо по адресу: bookquestions@oreilly.com.

Для дополнительных сведениях о книгах, курсах, конференциях и новостях следите за нашим вебсайтом http://www.oreilly.com.

Найдите нас на Facebook: http://facebook.com/oreilly.

Следуйте за нами в Twitter: http://twitter.com/oreillymedia.

Смотрите нас на YouTube: http://www.youtube.com/oreillymedia.

Эта книга была бы невозможна без тех сотен людей, которые взяли на себя тяжёлый труд исследовательских статей и книг, которые послужили источниками идей, догадок и предоставили справочные сведения для этой книги.

Я бы хотел выразить признательность всем людям, которые просмотрели рукописи и предоставили свои отзывы, что придаёт уверенность в том, что материалы этой книги верны и изложение точное: Dmitry Alimov, Peter Alvaro, Carlos Baquero, Jason Brown, Blake Eggleston, Marcus Eriksson, Francisco Fernández Castaño, Heidi Howard, Vaidehi Joshi, Maximilian Karasz, Stas Kelvich, Michael Klishin, Predrag Knežević, Joel Knighton, Eugene Lazin, Nate McCall, Christopher Meiklejohn, Tyler Neely, Maxim Neverov, Marina Petrova, Stefan Podkowinski, Edward Ribiero, Denis Rytsov, Kir Shatrov, Alex Sorokoumov, Massimiliano Tomassi и Ariel Weisberg.

Конечно же, эта книга не была бы возможной без поддержки от моей семьи: моей жены Марины и моей дочери Александры, которые поддерживали меня на каждом этапе этого пути.