Распределенные данные. Алгоритмы работы современных систем хранения информации E-Book
Алекс Петров
10,99 €
Mehr erfahren.
- Herausgeber: Питер
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Russisch
Когда дело доходит до выбора, использования и обслуживания базы данных, важно понимать ее внутреннее устройство. Как разобраться в огромном море доступных сегодня распределенных баз данных и инструментов? На что они способны? Чем различаются? Алекс Петров знакомит нас с концепциями, лежащими в основе внутренних механизмов современных баз данных и хранилищ. Для этого ему пришлось обобщить и систематизировать разрозненную информацию из многочисленных книг, статей, постов и даже из нескольких баз данных с открытым исходным кодом. Вы узнаете о принципах и концепциях, используемых во всех типах СУБД, с акцентом на подсистеме хранения данных и компонентах, отвечающих за распределение. Эти алгоритмы используются в базах данных, очередях сообщений, планировщиках и в другом важном инфраструктурном программном обеспечении. Вы разберетесь, как работают современные системы хранения информации, и это поможет взвешенно выбирать необходимое программное обеспечение и выявлять потенциальные проблемы.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Seitenzahl: 521
Veröffentlichungsjahr: 2023
Ähnliche
Научный редактор А. Коцюба
Переводчик А. Коцюба
Литературный редактор А. Руденко
Художник В. Мостипан
Корректоры М. Одинокова, Н. Сулейманова
Верстка Е. Неволайнен
Алекс Петров
Распределенные данные. Алгоритмы работы современных систем хранения информации. — СПб.: Питер, 2021.
ISBN 978-5-4461-1640-9
© ООО Издательство "Питер", 2021
Все права защищены. Никакая часть данной книги не может быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских прав.
Оглавление
Питеру Хинтьенсу, от которого я получил свою первую подписанную книгу: вдохновляющему программисту распределенных систем, автору, философу и другу
Предисловие к русскому изданию
С детства я говорил на украинском и русском языках. Но ради того, чтобы как можно больше людей узнало о предмете настолько важном, как базы данных, я решил написать эту книгу на английском. Можете представить себе мой восторг, когда я узнал, что издательство «Питер», технические книги которого я помню еще с университетских лет, занимается переводом моей книги на русский.
Мы приложили все усилия для того, чтобы вы не только познакомились с устройством баз данных, но и могли использовать русский перевод книги как основу для дальнейшего изучения этой темы, и снабдили русские термины их английскими эквивалентами для того, чтобы помочь русскоязычному сообществу разработчиков баз данных стандартизировать терминологию.
Предисловие
Распределенные системы управления базами данных являются неотъемлемой частью большинства предприятий и подавляющего большинства программных приложений. Приложения отвечают за логику и взаимодействие с пользователем, в то время как системы управления базами данных (СУБД) обеспечивают целостность, согласованность и избыточность данных.
В 2000 году вы могли использовать лишь несколько разновидностей баз данных, большинство из которых были реляционными и в силу этого мало чем отличались друг от друга. Конечно, это не означает, что эти базы данных были совершенно одинаковыми, однако они имели много сходства в плане функциональности и сценариев использования.
Некоторые из этих баз данных ориентировались на горизонтальное масштабирование — повышение производительности и увеличение емкости за счет запуска нескольких экземпляров базы данных, действующих как единый логический блок: Gamma Database Machine Project, Teradata, Greenplum, Parallel DB2 и многие другие. Горизонтальное масштабирование и сегодня остается одним из самых востребованных свойств баз данных, что объясняется растущей популярностью облачных сервисов. Зачастую проще развернуть новый экземпляр и добавить его в кластер, чем производить вертикальное масштабирование, перенося базу данных на более крупную и мощную машину. Миграция часто требует больших затрат времени и усилий, что, в свою очередь, может приводить к простоям.
Примерно в 2010 году начал формироваться новый класс баз данных с конечной согласованностью и стали набирать популярность такие термины, как NoSQL и большие данные. За последние 15 лет сообщество разработчиков ПО с открытым исходным кодом, крупные интернет-компании и поставщики баз данных создали так много баз данных и инструментов, что можно легко запутаться, пытаясь разобраться в их специфических особенностях и сценариях использования.
В 2007 году разработчики компании Amazon опубликовали статью с описанием системы хранения данных Dynamo [DECANDIA07], которая произвела столь сильное впечатление на сообщество разработчиков баз данных, что за короткое время на свет появилось множество вариантов и реализаций этой системы. Наиболее известными среди них были такие системы хранения, как Apache Cassandra, разработанная компанией Facebook, Project Voldemort от компании LinkedIn и Riak от бывших разработчиков компании Akamai.
Сегодня ситуация в области систем хранения данных снова меняется: на смену хранилищам типа «ключ–значение», NoSQL и системам с конечной согласованностью стали приходить более масштабируемые и производительные базы данных, способные выполнять сложные поисковые запросы с более высокой гарантией согласованности.
Кому предназначена эта книга
На конференциях мне часто задают один и тот же вопрос: «Как мне узнать больше о внутреннем устройстве баз данных? Я даже не знаю, с чего начать». Авторы большинства книг по СУБД не вдаются в детали реализации подсистем хранения данных, лишь в общих чертах описывая такие методы доступа, как использование B-деревьев. Поскольку лишь очень немногие книги подробно освещают такие актуальные концепции, как различные сценарии использования B-деревьев и журналированные подсистемы хранения, я обычно рекомендую читать статьи.
Каждый, кто пробовал читать статьи, знает, что это не так просто: вам часто не хватает контекста, формулировки могут быть неоднозначными, между статьями мало или вообще нет связи и их трудно найти. Эта книга содержит краткое описание важных концепций систем управления базами данных и может служить в качестве справочника для тех, кто хотел бы копнуть глубже, или в качестве шпаргалки для тех, кто уже знаком с этими концепциями.
Хотя далеко не все хотят стать разработчиками баз данных, эта книга поможет всем, кто создает программное обеспечение, использующее СУБД: разработчикам, специалистам по обеспечению надежности, архитекторам и руководителям проектных работ.
Если ваша компания использует какой-либо компонент инфраструктуры, будь то база данных, очередь сообщений, контейнерная платформа или планировщик задач, то вам следует читать журналы изменений проекта и списки рассылки, чтобы оставаться на связи с сообществом и знать о последних изменениях. Понимание терминологии и знание внутреннего устройства позволят вам извлекать больше информации из этих источников и более продуктивно использовать свои инструменты для поиска и устранения неполадок, выявления и предотвращения рисков и узких мест. Общее понимание принципов работы СУБД будет существенным подспорьем в том случае, если что-то пойдет не так. Используя эти знания, вы сможете выдвинуть некоторую гипотезу, проверить ее, найти первопричину проблемы и предоставить ее описание другим участникам проекта.
Эта книга также предназначена пытливым умам — людей, которые любят изучать что-то без непосредственной необходимости, тем, кто любит проводить время, взламывая что-то из чистого интереса, создавая компиляторы, собственные операционные системы, текстовые редакторы и компьютерные игры, изучая языки программирования и впитывая новую информацию.
Предполагается, что читатель имеет некоторый опыт разработки серверных систем и работы с СУБД в качестве пользователя. Хорошим подспорьем в усвоении материала книги также будет наличие некоторых знаний о различных структурах данных.
Зачем мне читать эту книгу?
СУБД часто описываются в терминах тех концепций и алгоритмов, которые они реализуют, т.е. указывается, что СУБД «использует gossip-протокол для распространения членства» (см. главу 12), «реализует Dynamo» или «соответствует описанию, предоставленному в статье, посвященной протоколу Spanner» (см. главу 13). Если же разговор идет об алгоритмах и структурах данных, часто можно услышать что-то вроде: «У ZAB и Raft есть много общего» (см. главу 14), «Bw-деревья — это что-то наподобие B-деревьев, реализованных поверх журналированной подсистемы хранения» (см. главу 6), или «они используют одноуровневые указатели, как в Blink-деревьях» (см. главу 5).
Чтобы говорить о сложных понятиях, нужны абстракции. Кроме того, невозможно каждый раз заново обсуждать терминологию, начиная какой-либо разговор. Наличие удобного инструмента в виде общего языка помогает переключить внимание на проблемы более высокого уровня.
Одно из преимуществ изучения фундаментальных концепций, доказательств и алгоритмов состоит в том, что они никогда не устаревают. Конечно, всегда будут появляться новые алгоритмы, однако это часто происходит как результат выявления недостатков или возможностей для улучшения в классическом алгоритме. Знание истории помогает лучше понять различия новых алгоритмов и мотивы их создания.
Изучение таких вещей вдохновляет. Вы видите разнообразие алгоритмов, видите, как последовательно решались проблемы в сфере баз данных, и начинаете ценить эту работу. Еще один положительный эффект состоит в том, что разрозненные фрагменты головоломки начинают складываться у вас в голове в цельную картину, которой вы всегда сможете поделиться с другими.
Рассматриваемые темы
Эта книга не посвящена реляционным или нереляционным (NoSQL) СУБД; она посвящена алгоритмам и концепциям, используемым во всех типах СУБД, с акцентом на подсистеме хранения данных и на компонентах, отвечающих за распределение.
Некоторые из рассматриваемых здесь концепций, включая, в частности, планирование и оптимизацию поисковых запросов, диспетчеризацию, реляционную модель и т.д., уже освещены в ряде отличных пособий по СУБД. Некоторые из этих концепций обычно описываются с точки зрения пользователя, в то время как в этой книге акцентируется внимание на их внутреннем устройстве. Вы сможете найти ссылки на полезную литературу в конце части II и в заключительных разделах каждой главы. В этих книгах вы найдете ответы на многие из имеющихся у вас вопросов относительно баз данных.
В этой книге не рассматриваются языки запросов, поскольку не существует общего языка, который можно было бы использовать для всех рассматриваемых здесь СУБД.
Чтобы собрать материал для этой книги, я изучил более 15 книг, более 300 статей и бесчисленное количество записей в блогах, файлы исходного кода и документацию по нескольким СУБД с открытым исходным кодом. Главным критерием при отборе рассматриваемых концепций был вопрос о том, говорят ли о той или иной концепции специалисты и ученые в области баз данных? Если ответ был утвердительным, я включал соответствующую концепцию в длинный список рассматриваемых тем.
Структура книги
Есть несколько примеров расширяемых баз данных с подключаемыми компонентами (например, [SCHWARZ86]), но они довольно редки. В то же время существует множество примеров использования базами данных подключаемого хранилища. Точно так же поставщики баз данных редко говорят о выполнении запросов, но всегда готовы поговорить о том, как поддерживается согласованность в предлагаемых ими базах данных.
Наиболее существенные различия между разными СУБД касаются используемых методов хранения и методов распределения данных. (Иногда играют важную роль и различия в других подсистемах, но мы не будем их рассматривать в этой книге.) Книга разбита на две части, в которых соответственно обсуждаются подсистемы и компоненты, отвечающие за хранение (часть I) и распределение (часть II).
В части I рассматриваются процессы внутри узлов и основное внимание уделяется подсистеме хранения данных — центральному компоненту СУБД и одному из наиболее важных отличительных аспектов. Мы начнем с архитектуры СУБД и рассмотрим несколько способов классификации СУБД в зависимости от среды хранения данных и структуры хранилища.
Затем мы рассмотрим структуры хранения данных и попытаемся понять, чем размещаемые на диске структуры отличаются от структур, размещаемых в оперативной памяти. Мы познакомимся с концепцией B-деревьев и изучим алгоритмы эффективной работы со структурами B-деревьев на диске, включая сериализацию, постраничную компоновку и представление данных на диске. Далее мы обсудим различные варианты концепции B-деревьев, чтобы наглядно увидеть ее мощь и оценить разнообразие структур данных, созданных под ее влиянием.
Наконец, мы обсудим несколько вариантов журналированного хранилища, широко используемых для реализации файловой системы и системы хранения, включая мотивы и причины их использования.
Часть II посвящена объединению нескольких узлов в кластер баз данных. Сначала мы узнаем, почему важно понимать теоретические принципы создания отказоустойчивых распределенных систем, чем распределенные системы отличаются от одноузловых приложений и с какими проблемами, ограничениями и сложностями приходится сталкиваться в распределенной среде.
После этого мы глубоко погрузимся в распределенные алгоритмы. Начнем с алгоритмов обнаружения сбоев, которые помогают повысить производительность и стабильность, выявляя сбои и сообщая о них, а также действуя в обход отказавших узлов. Поскольку для понимания многих алгоритмов, рассматриваемых далее в книге, необходимо понимание концепции «лидера», мы изучим несколько алгоритмов выбора лидера и поговорим о том, в каких случаях их лучше использовать.
Так как одной из самых сложных задач в распределенных системах является обеспечение согласованности данных, мы последовательно рассмотрим такие концепции, как репликация, модели согласованности, возможные расхождения между репликами и конечная согласованность. Поскольку в системах с конечной согласованностью часто применяется механизм антиэнтропии для обеспечения конвергенции, а также gossip-протокол для распространения данных, мы обсудим несколько подходов к их использованию. Завершит эту часть книги рассмотрение логической согласованности в контексте транзакций базы данных и алгоритмов консенсуса.
Было бы невозможно написать эту книгу, не опираясь на исследования и публикации других авторов. По ходу чтения вы встретите множество ссылок на статьи и публикации — они будут заключены в квадратные скобки: например: [DECANDIA07]. Вы можете использовать эти ссылки, чтобы изучить соответствующие концепции более подробно.
В конце каждой главы вы найдете раздел «Итоги», содержащий список дополнительной литературы, имеющей отношение к содержанию главы.
Условные обозначения
В этой книге используются следующие типографские условные обозначения.
Курсивный шрифт
Применяется для выделения новых терминов.
Моноширинный шрифт
Используется для записи листингов программ, а также для выделения в тексте таких элементов, как имена переменных и функций, базы данных, типы данных, переменные среды, операторы и ключевые слова.
Так обозначаются подсказки и советы.
Так обозначаются примечания общего характера.
Так обозначаются предупреждения и предостережения.
Благодарности
Это издание не состоялось бы без сотен людей, упорно работавших над научными трудами и книгами, которые стали источниками идей, вдохновения и служили справочниками.
Я хотел бы поблагодарить всех людей, которые рецензировали рукописи и оставляли отзывы, которые помогали убедиться, что материал в этой книге является корректным, а формулировки — точными: Дмитрий Алимов, Тимур Сафин, Питер Альваро (Peter Alvaro), Карлос Бакеро (Carlos Baquero), Джейсон Браун (Jason Brown), Блейк Эгглстон (Blake Eggleston), Маркус Эрикссон (Marcus Eriksson), Франсиско Фернандес Кастаньо (Francisco Fernandez Castano), Хайди Говард (Heidi Howard), Вайдехи Джоши (Vaidehi Joshi), Максимилиан Карась (Maximilian Karasz), Стас Кельвич (Stas Kelvich), Михаил Клишин, Предраг Кнежевич (Predrag Knežević), Джоэл Найтон (Joel Knighton), Евгений Лазин, Нейт Макколл (Nate McCall), Кристофер Мейклджон (Christopher Meiklejohn), Тайлер Нили (Tyler Neely), Максим Неверов, Марина Петрова, Стефан Подковинский (Stefan Podkowinski), Эдвард Рибьеро (Edward Ribiero), Денис Рысцов, Кир Шатров, Алекс Сорокоумов, Массимилиано Томасси (Massimiliano Tomassi) и Ариэль Вайсберг (Ariel Weisberg).
И конечно, эта книга не появилась бы на свет без поддержки моей семьи: жены Марины и дочери Александры, которые поддерживали меня на каждом шагу этого пути.
От издательства
Ваши замечания, предложения, вопросы отправляйте по адресу [email protected] (издательство «Питер», компьютерная редакция).
Мы будем рады узнать ваше мнение!
На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.
Пока что не вся терминология, связанная со сферой распределенных данных, устоялась в русскоязычном сообществе. Поэтому часть терминов в этой книге сопровождена их английскими вариантами.
ЧАСТЬ I. Подсистема хранения данных
Основной задачей любой СУБД является надежное хранение данных и обеспечение доступа к ним со стороны пользователей. Мы используем базы данных в качестве основного источника данных, помогающего обмениваться данными между различными частями приложений. Вместо того чтобы искать способ хранения и извлечения информации и изобретать новый способ организации данных при создании каждого нового приложения, мы используем базы данных. Таким образом, мы можем сосредоточиться на логике приложений, а не на инфраструктуре.
Для большей компактности вместо громоздкого термина «система управления базами данных» на протяжении этой книги мы будем в основном употреблять соответствующую аббревиатуру (СУБД) или просто выражение «база данных», имея в виду то же самое.
База данных представляет собой модульную систему, включающую в себя несколько составных частей: транспортный уровень, который принимает запросы, обработчик запросов, который выбирает наиболее эффективный способ выполнения запросов, подсистему выполнения, которая производит выполнение операций, и подсистему хранения (см. раздел «Архитектура СУБД» на с. 25).
Подсистема хранения данных (или ядро СУБД) — это программный компонент СУБД, отвечающий за хранение, извлечение и управление данными в памяти и на диске, предназначенный для работы с постоянной, долговременной памятью каждого узла [REED78]. В то время как базы данных могут отвечать на сложные запросы, подсистемы хранения рассматривают данные более детально и предлагают простой API для манипуляций с данными, позволяющий пользователям создавать, обновлять, удалять и извлекать записи. СУБД можно рассматривать как приложение, которое надстроено поверх подсистемы хранения и предлагает некоторую схему данных, язык запросов, индексацию, транзакции и много других полезных функций.
Для обеспечения гибкости и ключи, и значения могут быть произвольными последовательностями байтов без заданной формы. Их классификация и семантика представления определяются в подсистемах более высокого уровня. Например, вы можете использовать int32 (32-разрядное целое число) в качестве ключа в одной из таблиц и ascii (строку в кодировке ASCII) — в другой; с точки зрения подсистемы хранения оба ключа являются просто сериализованными записями.
Такие подсистемы хранения, как BerkeleyDB (https://databass.dev/links/92), LevelDB (https://databass.dev/links/93) и ее потомок RocksDB (https://databass.dev/links/94), LMDB (https://databass.dev/links/95) и ее потомок libmdbx (https://databass.dev/links/96), Sophia (https://databass.dev/links/97), HaloDB (https://databass.dev/links/98) и многие другие, были разработаны независимо от тех СУБД, в которые они теперь встроены. Использование существующих подключаемых подсистем хранения позволило разработчикам СУБД обойти этап их создания и сосредоточиться на других подсистемах.
В то же время четкое разделение между компонентами СУБД открывает возможность переключаться между различными подсистемами, потенциально более подходящими для конкретных сценариев использования. Например, MySQL, популярная система управления базами данных, имеет несколько подсистем хранения (https://databass.dev/links/99), включая InnoDB, MyISAM и RocksDB (https://databass.dev/links/100) (в составе MyRocks (https://databass.dev/links/101)). MongoDB позволяет переключаться между подсистемами хранения WiredTiger (https://databass.dev/links/102), In-Memory и (теперь уже устаревшей) MMAPv1 (https://databass.dev/links/103).
Сравнение баз данных
Выбор той или иной СУБД может иметь долгосрочные последствия. Если есть вероятность того, что база данных не подойдет из-за проблем с производительностью, обеспечением согласованности или выполнением операций, лучше выяснить это на раннем этапе цикла разработки, так как миграция на другую систему может оказаться нетривиальной. В некоторых случаях для этого потребуются существенные изменения в коде приложения.
У каждой СУБД есть свои сильные и слабые стороны. Для снижения риска дорогостоящей миграции можно потратить некоторое время перед принятием решения о выборе конкретной базы данных, чтобы быть уверенным в ее соответствии потребностям вашего приложения.
Попытка сравнить базы данных исходя из их компонентов (например, какую подсистему хранения они используют, каким образом данные совместно используются, реплицируются и распределяются и т.д.), их рейтинга (субъективная оценка, сделанная консалтинговыми агентствами, такими как ThoughtWorks (https://www.thoughtworks.com/de/radar), или сайтами со сравнением баз данных, такими как DB-Engine (https://db-engines.com/de/ranking) или Database of Databases (https://dbdb.io/)) или языка реализации (C++, Java или Go и т.д.) может привести к неверным и поспешным выводам. Такие методы можно использовать только для предварительного сравнения, и они могут быть такими же грубыми, как выбор между HBase и SQLite, поэтому даже поверхностное понимание того, как работает каждая база данных и что находится внутри нее, поможет принять более взвешенное решение.
Каждое сравнение должно начинаться с четкого определения цели, потому что даже малейшая предвзятость может полностью свести на нет все исследование. Если вам нужно, чтобы база данных хорошо подходила для имеющихся у вас (или ожидаемых) рабочих нагрузок, то лучше всего будет смоделировать эти рабочие нагрузки для различных СУБД, измерить важные для вас показатели производительности и сравнить результаты. Некоторые проблемы, особенно когда речь заходит о производительности и масштабируемости, начинают проявляться только через некоторое время или по мере роста емкости. Для выявления потенциальных проблем лучше всего провести длительные тесты в среде, максимально точно имитирующей реальное рабочее окружение.
Моделирование реальных рабочих нагрузок не только помогает понять, как работает база данных, но и позволяет научиться ее использовать и отлаживать, а также выяснить, насколько дружелюбно и полезно сложившееся вокруг нее сообщество. Выбор базы данных всегда определяется сочетанием этих факторов, и производительность часто оказывается не самым важным аспектом: лучше использовать базу данных, которая медленно сохраняет данные, а не быстро их теряет.
Чтобы сравнить базы данных, полезно тщательно изучить сценарий использования и определить текущие и ожидаемые переменные:
• размеры схемы данных и записей;
• количество клиентов;
• типы запросов и паттерны доступа;
• скорость выполнения запросов на чтение и запись;
• ожидаемые изменения в любой из этих переменных.
Знание этих переменных может помочь ответить на следующие вопросы:
• Поддерживает ли база данных необходимые запросы?
• Способна ли база данных обрабатывать тот объем данных, который мы планируем хранить?
• Сколько операций чтения и записи может обрабатывать один узел?
• Сколько узлов должна включать в себя система?
• Как расширить кластер с учетом ожидаемых темпов роста?
• В чем заключается процесс обслуживания?
Получив ответы на эти вопросы, вы сможете построить тестовый кластер и смоделировать свои рабочие нагрузки. Для большинства баз данных уже есть инструменты стресс-анализа, которые можно применить для воспроизведения конкретных сценариев использования. Если в экосистеме базы данных нет стандартного инструментария стресс-анализа для создания реалистичных рандомизированных рабочих нагрузок, это может стать настораживающим знаком. Если что-то мешает вам использовать инструменты, поставляемые вместе с самой базой, можно попробовать один из существующих инструментов общего назначения или реализовать его с нуля.
Если тесты показывают положительные результаты, часто полезно ознакомиться с кодом базы данных. При изучении кода обычно лучше сначала выявить составные части базы данных, понять, как найти код различных компонентов, а затем пройтись по ним. Имея даже приблизительное представление о кодовой базе СУБД, вы сможете лучше разбираться в создаваемых ею записях журнала и ее параметрах конфигурации, а также выявлять проблемы в использующем ее приложении и даже в самом коде СУБД.
Было бы здорово, если бы мы могли использовать базы данных как черные ящики и никогда не заглядывать в них, но практика показывает, что рано или поздно возникает ошибка, сбой, регрессия производительности или какая-то другая проблема и лучше быть готовым к этому. Если вы знаете и понимаете внутренние компоненты базы данных, то можете снизить бизнес-риски и повысить шансы на быстрое восстановление.
Одним из популярных инструментов для тестирования, оценки производительности и сравнения является Yahoo! Cloud Serving Benchmark (YCSB) (https://databass.dev/links/104). YCSB предлагает инфраструктуру и общий набор рабочих нагрузок, которые могут быть применены к различным хранилищам данных. Как и все средства общего назначения, этот инструмент следует использовать с осторожностью, так как можно с легкостью прийти к неправильным выводам. Чтобы провести справедливое сравнение и принять обоснованное решение, необходимо потратить достаточно времени, чтобы понять реальные условия, в которых должна функционировать база данных, и соответствующим образом адаптировать сравнительные тесты.
Сравнительный тест TPC-C
Совет по оценке производительности обработки транзакций (Transaction Processing Performance Council, TPC) предлагает набор сравнительных тестов, которые поставщики баз данных используют для сравнения и рекламирования производительности своих продуктов. TPC-C — это тест обработки транзакций в реальном времени (Online Transaction Processing, OLTP), представляющий собой смесь транзакций только для чтения и обновления, которые имитируют распространенные рабочие нагрузки приложений.
TPC-C тестирует производительность и корректность выполняемых конкурентных транзакций. Основным показателем производительности является пропускная способность: количество транзакций, которые СУБД может обрабатывать в минуту. Выполняемые транзакции должны сохранять ACID-свойства и соответствовать (не противоречить) набору свойств, определяемых самим тестом.
Этот тест не относится к какому-либо конкретному бизнес-сегменту, но предоставляет абстрактный набор действий, важных для большинства приложений, для которых подходят базы данных OLTP. Он включает в себя несколько таблиц и объектов, таких как склады, товарные запасы, заказчики и заказы, и определяет макеты таблиц, сведения о транзакциях, которые могут быть выполнены с этими таблицами, минимальное количество строк в таблице и ограничения на уровень устойчивости данных.
Это не означает, что сравнительные тесты можно использовать только для сравнения баз данных. Сравнительные тесты могут быть полезны для определения и проверки положений соглашения об уровне обслуживания1, определения системных требований, планирования производительности и многого другого. Чем больше вы узнаете о базе данных до ее использования, тем меньше времени придется тратить при эксплуатации.
Выбор базы данных — это долгосрочное решение, и потому желательно отслеживать выход новых версий, понимать, что именно изменилось и почему, и иметь некоторую стратегию обновления. Новые выпуски обычно содержат улучшения и исправления ошибок и проблем безопасности, но могут содержать и новые ошибки, вести к снижению производительности или неожиданному поведению, поэтому новые версии тоже важно тестировать перед их развертыванием. Проверка того, как разработчики базы данных проводили обновления ранее, может дать вам хорошее представление о том, чего ожидать в будущем. Если предыдущие обновления проходили гладко, это еще не гарантирует, что также будет и в дальнейшем, однако если они вызывали затруднения, это может быть признаком того, что будущие обновления тоже дадутся нелегко.
Понимание преимуществ и недостатков
В качестве пользователей мы можем видеть, как базы данных ведут себя в различных условиях, но при разработке баз данных мы должны принимать решения, оказывающие непосредственное влияние на это поведение.
Проектирование подсистемы хранения, безусловно, сложнее, чем просто реализация структуры данных из учебника: здесь имеется много деталей и пограничных случаев, с которыми обычно не удается справиться с первого раза. Нужно спроектировать физический макет данных и организовать указатели, принять решение о формате сериализации, понять, как данные будут удаляться при сборке мусора, как подсистема хранения вписывается в семантику СУБД в целом, выяснить, как заставить ее работать в конкурентном окружении, и, наконец, убедиться, что мы не будем терять данные ни при каких обстоятельствах.
Помимо того что вам нужно принять решения в отношении множества различных вещей, ситуация осложняется еще и тем, что в большинстве случаев эти решения подразумевают нахождение некоторого компромисса. Например, если мы будем сохранять записи в том же порядке, в котором они вносятся в базу данных, их можно будет сохранять быстрее, но если при этом их нужно будет извлекать в лексикографическом порядке, то их потребуется пересортировывать перед возвращением результатов клиенту. Как вы увидите на протяжении этой книги, существует много различных подходов к разработке подсистемы хранения и каждая реализация имеет свои собственные плюсы и минусы.
При рассмотрении различных подсистем хранения мы будем обсуждать все их преимущества и недостатки. Если бы существовала подсистема хранения, идеальным образом подходящая для каждого возможного сценария использования, то все бы просто использовали его. Но поскольку такой подсистемы хранения не существует, мы должны подходить к выбору очень тщательно, принимая в расчет ожидаемые рабочие нагрузки и сценарии использования.
Существует множество различных подсистем хранения, использующих разные структуры данных и реализованных на разных языках, начиная с таких низкоуровневых языков, как C, и заканчивая такими высокоуровневыми языками, как Java. В то же время все подсистемы хранения сталкиваются с одинаковыми проблемами и ограничениями. Это можно сравнить с планированием городской застройки — планируя застройку под конкретное количество людей, вы можете увеличивать город в вертикальном или горизонтальном направлении. Хотя в обоих случаях город сможет принять одинаковое количество людей, эти подходы подразумевают совершенно разный образ жизни. При вертикальном росте застройки люди будут жить в квартирах и высокая плотность населения, вероятно, приведет к высокой интенсивности транспортного движения. С другой стороны, при менее плотном размещении люди, вероятно, будут жить в домах, но дальше от места работы.
Аналогичным образом проектные решения, принимаемые разработчиками подсистем хранения, делают их более подходящими для различных целей: одни из них обеспечивают минимальное время чтения и записи, другие — максимальную плотность (количество хранимых данных, приходящееся на каждый узел), а третьи — максимальную простоту эксплуатации.
В разделе «Итоги» в конце каждой главы вы найдете ссылки на полное описание применяемых в реализации алгоритмов и другую полезную информацию. Чтение этой книги должно хорошо подготовить вас для эффективного использования этих источников и дать прочное понимание того, какие имеются альтернативы для описываемых в них концепций.
1 Соглашение об уровне обслуживания (service-level agreement, SLA) — это обязательство поставщика услуг относительно качества предоставляемых услуг. Помимо прочего, такое соглашение может включать информацию о задержке, пропускной способности, дрожании, а также количестве и частоте отказов.
Глава 1. Введение и обзор
СУБД служат различным целям: некоторые используются в основном для временных «горячих» данных, некоторые служат в качестве долговременного хранилища «холодных» данных, некоторые подходят для сложных аналитических запросов, некоторые позволяют получать доступ к значениям только по ключу, некоторые оптимизированы для хранения данных временных рядов, а некоторые эффективно хранят большие двоичные объекты. Сначала мы рассмотрим и обозначим различия, начав с краткой классификации и обзора, поскольку это поможет оценить масштаб дальнейшей дискуссии.
Терминология иногда может быть неоднозначной и трудной для понимания без принятия во внимание полного контекста. Примером могут служить различия между колоночными хранилищами и хранилищами с широкими столбцами, которые имеют очень мало общего между собой, или взаимосвязь кластеризованных или некластеризованных индексов и индексированных таблиц. Цель данной главы состоит в том, чтобы дать однозначное и точное определение таких терминов.
Мы начнем с обзора архитектуры СУБД (см. раздел «Архитектура СУБД» на с. 25) и обсудим отдельные ее компоненты и их функции. После этого мы осветим различия между различными СУБД с точки зрения используемой среды хранения (см. раздел «Резидентные и дисковые СУБД» на с. 27) и структуры (см. раздел «Колоночные и строчные СУБД» на с. 30).
Эти два способа разделения являются далеко не единственными вариантами классификации СУБД. Например, СУБД часто разделяют на три основные категории:
Базы данных для обработки транзакций в реальном времени (online transaction processing, OLTP)
Они обрабатывают большое количество поступающих со стороны пользователя запросов и транзакций. Запросы часто бывают предопределенными и с коротким жизненным циклом.
Базы данных для аналитической обработки данных в реальном времени (online analytical processing, OLAP)
Они обрабатывают сложные агрегаты данных. OLAP-системы часто используются для аналитики и построения хранилищ данных и способны обрабатывать сложные произвольные специальные запросы с длительным жизненным циклом.
Гибридная транзакционно-аналитическая обработка (hybrid transactional and analytical processing, HTAP)
Эти базы данных сочетают в себе свойства хранилищ OLTP и OLAP.
Существует и множество других терминов и способов классификации: хранилища типа «ключ–значение», реляционные базы данных, документоориентированные хранилища и графовые базы данных. Эти понятия здесь не определяются, так как предполагается, что читатель хорошо знает и понимает их. Поскольку концепции, которые мы здесь обсуждаем, широко применимы и используются в большинстве упомянутых типов хранилищ в том или ином качестве, полная систематика не является необходимой или важной для дальнейшего обсуждения.
Часть I этой книги посвящена структурам хранения и индексирования, поэтому нам необходимо понять высокоуровневые подходы к организации данных и взаимосвязь файлов данных и индексных файлов (см. раздел «Файлы данных и индексные файлы», с. 34).
Наконец, в разделе «Буферизация, неизменяемость и упорядочение» на с. 39 мы обсудим три широко используемых метода разработки эффективных структур хранения данных, а также поговорим о том, как применение этих методов влияет на проектирование и реализацию структур.
Архитектура СУБД
Не существует общего шаблона для проектирования СУБД. Каждая база данных строится немного по-разному, а границы компонентов довольно трудно обнаружить и определить. Даже если эти границы существуют на бумаге (например, в проектной документации), в коде кажущиеся независимыми компоненты могут оказаться связанными из-за оптимизации производительности, обработки граничных случаев или применения определенных архитектурных решений.
Источники, описывающие архитектуру СУБД (например, [HELLERSTEIN07][WEIKUM01][ELMASRI11] и [MOLINA08]), определяют компоненты и отношения между ними по-разному. Архитектура, показанная на рис. 1.1, демонстрирует некоторые общие элементы этих представлений.
СУБД используют модель «клиент — сервер», в которой экземпляры СУБД (узлы) играют роль серверов, а экземпляры приложений — роль клиентов.
Запросы клиентов поступают через транспортную подсистему. Поступающие запросы чаще всего оформлены на каком-либо языке запросов. Транспортная подсистема также отвечает за связь с другими узлами кластера баз данных.
После получения запроса транспортная подсистема передает его обработчику запросов, который анализирует, интерпретирует и проверяет его. Далее проводятся проверки управления доступом, так как для их полного выполнения необходима интерпретация запроса.
Рис. 1.1. Архитектура СУБД
Анализируемый запрос передается оптимизатору запросов, который сначала устраняет невозможные и избыточные части запроса, а затем пытается найти наиболее эффективный способ его выполнения на основе внутренней статистики (мощность индекса, приблизительный размер пересечений и т.д.) и размещения данных (какие узлы в кластере содержат данные и какие затраты требуются для их передачи). Оптимизатор обрабатывает реляционные операции, необходимые для разрешения запросов, обычно представленные в виде дерева зависимостей, и проводит оптимизации, такие как упорядочение индексов, оценка мощности и выбор средств доступа.
Запрос обычно представлен в виде плана выполнения (или плана запроса): последовательности операций, которую необходимо выполнить для того, чтобы результаты запроса считались полными. Поскольку один и тот же запрос может быть выполнен с помощью различных планов выполнения, которые могут отличаться по эффективности, оптимизатор выбирает наиболее эффективный план из всех доступных.
План выполнения обрабатывается подсистемой выполнения, которая собирает результаты выполнения локальных и удаленных операций. Удаленное выполнение обычно сводится к записи и чтению данных на других узлах кластера, а также выполнению репликации.
Локальные запросы (поступающие непосредственно от клиентов или от других узлов) выполняются подсистемой хранения данных, которая включает в себя несколько компонентов с четко заданными функциями:
Диспетчер транзакций
Производит планировку транзакций и гарантирует, что они не оставят базу данных в логически несогласованном состоянии.
Диспетчер блокировок
Блокирует объекты базы данных для выполняемых транзакций, чтобы конкурентные операции не нарушали физическую целостность данных.
Средства доступа (структуры для хранения данных)
Управляют доступом и организацией данных на диске. Средства доступа включают в себя неупорядоченные файлы и такие структуры хранения, как B-деревья (см. раздел «Вездесущие B-деревья», с. 51) или LSM-деревья (см. раздел «LSM-деревья», с. 148).
Диспетчер буферов
Кэширует страницы данных в памяти (см. раздел «Организация буферизации данных», с. 98).
Диспетчер восстановления
Ведет журнал операций и восстанавливает состояние системы в случае сбоя (см. раздел «Восстановление», с. 106).
Вместе диспетчеры транзакций и блокировок отвечают за управление параллелизмом (см. раздел «Управление параллелизмом», с. 111): они гарантируют логическую и физическую целостность данных, обеспечивая при этом максимально эффективное выполнение конкурентных операций.
Резидентные и дисковые СУБД
СУБД хранят данные в оперативной памяти или на диске. Резидентные СУБД (или СУБД в оперативной памяти) хранят данные главным образом в оперативной памяти, а диск используют для восстановления и ведения журнала. Дисковые СУБД хранят бˆольшую часть данных на диске и используют память для кэширования содержимого диска или в качестве временного хранилища. Системы обоих типов в той или иной степени используют диск, но резидентные базы данных хранят содержимое почти исключительно в ОЗУ.
Доступ к памяти был и остается на несколько порядков быстрее доступа к диску2, поэтому есть смысл использовать память в качестве основного хранилища. Такой подход становится все более экономически целесообразным, поскольку цены на память снижаются. Однако цены на оперативную память по-прежнему остаются высокими по сравнению с постоянными устройствами хранения данных, такими как твердотельные накопители и жесткие диски.
Резидентные СУБД отличаются от дисковых не только основной средой хранения данных, но и тем, как они организованы и какие структуры данных и методы оптимизации они используют.
Использование памяти в качестве основного хранилища данных в таких базах данных обусловлено главным образом высокой производительностью, сравнительно низкими затратами на доступ и высокой гранулярностью доступа. С точки зрения программирования работа с оперативной памятью также представляет гораздо меньше сложностей, чем работа с диском. Операционные системы абстрагируют управление памятью и позволяют нам мыслить в терминах выделения и освобождения областей памяти произвольного размера. На диске же мы должны вручную управлять ссылками на местонахождение данных, форматами сериализации, освобожденной памятью и фрагментацией.
Основными ограничивающими факторами роста количества резидентных баз данных являются непостоянство (т. е. недостаточная долговечность) оперативной памяти и высокая стоимость. Поскольку содержимое ОЗУ не является постоянным, программные ошибки, отказы, аппаратные сбои и перебои в подаче электроэнергии могут привести к потере данных. Существуют способы обеспечения долговечности, такие как использование источников бесперебойного питания и оперативной памяти с резервным аккумуляторным питанием, но они требуют дополнительных аппаратных ресурсов и более высокого уровня квалификации обслуживающего персонала. На практике решающую роль часто играет то, что диски проще в обслуживании и гораздо меньше стоят.
Ситуация, вероятно, будет меняться по мере роста доступности и популярности технологии энергонезависимой памяти (Non-Volatile Memory, NVM) [ARULRAJ17]. Энергонезависимое хранилище уменьшает или полностью устраняет (в зависимости от конкретной технологии) асимметрию между временем чтения и записи, дополнительно улучшает производительность чтения и записи и обеспечивает доступ с байтовой адресацией.
Долговечность в резидентных хранилищах
Резидентные СУБД сохраняют резервные копии на диске, чтобы обеспечить долговечность и не допустить потери часто меняющихся данных. Хотя некоторые базы данных хранят данные исключительно в памяти, без каких-либо гарантий долговечности, мы не будем обсуждать их в рамках этой книги.
Прежде чем операция будет считаться завершенной, ее результаты должны быть записаны в последовательно организованный журнал предзаписи. Более подробно мы рассмотрим журналы упреждающей записи в разделе «Восстановление» на с. 106. Чтобы избежать применения полного содержимого журнала во время запуска или после сбоя, резидентные хранилища поддерживают резервную копию. Резервная копия поддерживается в виде упорядоченной структуры на диске; при этом изменения часто вносятся в нее асинхронно (без привязки к запросам клиентов) и применяются пакетами для уменьшения числа операций ввода-вывода. Во время восстановления содержимое базы данных может быть получено из резервной копии и журналов.
Записи журнала обычно применяются к резервной копии пакетами. После обработки пакета записей журнала резервная копия содержит моментальный снимок базы данных, который соответствует некоторому моменту, и все предшествующее содержимое журнала может быть удалено. Этот процесс называется созданием контрольных точек. При таком подходе сокращается время восстановления за счет поддержания дисковой базы данных в предельно актуальном состоянии с помощью записей журнала, без необходимости в блокировке доступа клиентов на время обновления резервной копии.
Не стоит думать, что резидентная база данных представляет собой что-то вроде дисковой базы данных с огромным страничным кэшем (см. раздел «Организация буферизации данных» на с. 98). При кэшировании страниц в памяти формат сериализации и способ представления данных несут с собой дополнительные издержки и не позволяют достичь той же степени оптимизации, которую могут обеспечить резидентные хранилища.
Дисковые базы данных используют специализированные структуры хранения данных, оптимизированные для доступа к диску. Поскольку в памяти сравнительно быстро осуществляются переходы по указателям, произвольный доступ к памяти осуществляется намного быстрее, чем произвольный доступ к диску. Дисковые структуры хранения данных часто имеют вид широкого и низкого дерева (см. подраздел «Деревья для дисковых хранилищ», с. 46), в то время как резидентные хранилища могут использовать больше разновидностей структур данных и способны на такие виды оптимизации, которые невозможно или очень сложно реализовать на диске [MOLINA92]. Точно так же на диске особого внимания требует обработка данных переменного размера, в то время как в памяти это обычно решается путем обращения к значению с помощью указателя.
В случае некоторых сценариев использования уместно предположить, что весь набор данных поместится в памяти. Некоторые наборы данных ограничены природой вещей реального мира, которые они представляют: записи учащихся для школ, записи клиентов для корпораций или товарные запасы в интернет-магазине. Каждая запись занимает не более нескольких КБ, а их количество ограничено.
Колоночные и строчные СУБД
Большинство СУБД хранит некоторый набор записей, состоящий из столбцов и строк таблиц. Поле находится на пересечении столбца и строки и содержит одно значение некоторого типа. Поля, относящиеся к одному столбцу, обычно имеют один и тот же тип данных. Например, если мы определим таблицу, содержащую записи пользователей, все имена будут иметь один и тот же тип и находиться в одном и том же столбце. Набор значений, логически относимых к одной и той же записи (обычно идентифицируемой ключом), образует строку.
Один из способов классификации баз данных сводится к их разделению в зависимости от того, как данные сохраняются на диске: по строкам или по столбцам. Данные таблиц могут разбиваться либо по горизонтали (когда вместе сохраняются значения, относящиеся к одной строке), либо по вертикали (когда вместе сохраняются значения, относящиеся к одному столбцу). Разница между этими способами показана на рис. 1.2: (а) значения разбиваются по столбцам и (б) значения разбиваются по строкам.
Рис. 1.2. Компоновка данных в колоночных и строчных хранилищах
Примеров строчных СУБД очень много: MySQL (https://dev.mysql.com/), PostgreSQL (https://www.postgresql.org/) и большинство традиционных реляционных баз данных. Первыми примерами колоночных хранилищ стали свободно распространяемые СУБД MonetDB (https://databass.dev/links/109) и C-Store (https://databass.dev/links/110) (на основе C-Store впоследствии была создана СУБД Vertica (https://databass.dev/links/111)).
Построчная компоновка данных
Строчные СУБД хранят данные в записях или строках. Этот способ компоновки очень напоминает табличное представление данных, при котором каждая строка имеет один и тот же набор полей. Например, строчная база данных эффективна для хранения записей пользователей, содержащих имена, даты рождения и номера телефонов.
Идентификатор
Имя
Дата рождения
Номер телефона
10
Джон
01 августа 1981
+1 111 222 333
20
Сэм
14 сентября 1988
+1 555 888 999
30
Кит
07 января 1984
+1 333 444 555
Этот подход хорошо работает в тех случаях, когда запись состоит из нескольких полей (имя, дата рождения и номер телефона) и однозначно идентифицируется ключом (в этом примере — монотонно возрастающее число). Все поля, представляющие запись одного пользователя, обычно считываются вместе. При создании записей (например, когда пользователь заполняет регистрационную форму) все поля также записываются вместе. В то же время каждое поле можно изменять по отдельности.
Поскольку строчные хранилища наиболее полезны, когда необходимо получать доступ к данным построчно, хранение целых строк в одном месте повышает степень пространственной локальности3[DENNING68].
Поскольку доступ к данным на персистентном носителе, таком как диск, обычно осуществляется поблочно (другими словами, минимальная единица доступа к диску — это блок), один блок будет содержать данные для всех столбцов. Такой способ отлично подходит для случаев, когда мы хотим получить доступ ко всей записи пользователя, но делает более затратными обращения к отдельным полям нескольких записей (например, запросы для получения только телефонных номеров), так как данные из других полей также будут загружаться в кэш.
Поколоночная компоновка данных
Колоночные СУБД разделяют данные по вертикали (т. е. по столбцам), вместо того чтобы хранить их построчно. В этом случае на диске вместе сохраняются значения отдельных столбцов (а не отдельных строк, как в предыдущем примере). Например, при сохранении исторических данных о ценах на фондовом рынке мы можем сохранять вместе различные котировки цен. Сохранение значений разных столбцов в отдельных файлах или сегментах файлов позволяет эффективно выполнять запросы по столбцам, поскольку столбцы в таком случае могут быть считаны целиком, вместо того, чтобы считывать отдельные строки и отбрасывать данные тех столбцов, которые не были запрошены.
Колоночные хранилища хорошо подходят для аналитической обработки, требующей вычисления агрегатных величин, — для определения тенденций, вычислении средних значений и т.д. Обработка сложных агрегатов может быть использована в тех случаях, когда логические записи имеют несколько полей, но некоторые из них (в данном случае котировки цен) имеют различную значимость и часто используются вместе.
С логической точки зрения данные, представляющие котировки цен на фондовом рынке, также можно представить в виде таблицы:
Идентификатор
Символ
Дата
Цена
1
DOW
08 августа 2018
24314,65
2
DOW
09 августа 2018
24136,16
3
S&P
08 августа 2018
2414,45
4
S&P
09 августа 2018
2232,32
Однако физическая структура колоночной базы данных выглядит совершенно иначе. Здесь вместе сохраняются значения, относящиеся к одному и тому же столбцу:
Символ: 1:DOW; 2:DOW; 3:S&P; 4:S&P
Дата: 1:08 авг 2018; 2:09 авг 2018; 3:08 авг 2018; 4:09 авг 2018
Цена: 1:24 314,65; 2:24 136,16; 3:2 414,45; 4:2 232,32
Для восстановления кортежей данных, которые могут быть полезны для объединения, фильтрации и многорядных агрегатов, нам необходимо сохранить некоторые метаданные на уровне столбцов, чтобы определить, с какими элементами данных из других столбцов они связаны. Если вы сделаете это явно, то каждое значение будет содержать ключ, что приведет к дублированию и увеличению объема хранимых данных. Некоторые колоночные хранилища вместо этого используют неявные идентификаторы (виртуальные идентификаторы) и позиции значений (другими словами, их смещения) для их отображения на связанные значения [ABADI13].
В течение последних нескольких лет, вероятно, из-за растущего спроса на выполнение сложных аналитических запросов по увеличивающимся наборам данных появилось много новых колоночных форматов файлов, таких как Apache Parquet (https://databass.dev/links/112), Apache ORC (https://databass.dev/links/113), RCFile (https://databass.dev/links/114), а также много колоночных хранилищ, таких как Apache Kudu (https://databass.dev/links/115), ClickHouse (https://databass.dev/links/116) и многие другие [ROY12].
Различия и оптимизация
Различия между строчными и колоночными хранилищами заключаются не только в способе хранения данных. Выбор способа компоновки данных — это всего лишь один из шагов в серии возможных оптимизаций, возможных в колоночных хранилищах .
Считывание за один раз нескольких значений отдельного столбца значительно повышает эффективность использования кэша и вычислительную эффективность. Современные процессоры позволяют использовать векторные инструкции, что дает вам возможность обработать множество элементов данных с помощью всего одной инструкции4 процессора [DREPPER07].
Сохранение в одном месте значений с одним типом данных (например, чисел вместе с другими числами, строк вместе с другими строками) открывает возможности для более высокой степени сжатия данных. Мы можем использовать различные алгоритмы сжатия в зависимости от типа данных и выбрать наиболее эффективный метод сжатия для каждого случая.
Чтобы решить, следует ли использовать колоночное или строчное хранилище, вам необходимо изучить паттерны доступа. Если считываемые данные используются в виде записей (т. е. запрашиваются все или почти все столбцы), а рабочая нагрузка включает в себя главным образом точечные запросы и операции сканирования диапазонов, то построчный подход, вероятно, даст лучшие результаты. Если требуется просматривать множество строк или вычислять агрегаты на основе подмножества столбцов, то стоит подумать об использовании поколоночного подхода.
Хранилища с широкими столбцами
Колоночные базы данных не следует путать с хранилищами с широкими столбцами, такими как BigTable (https://databass.dev/links/117) или HBase (https://databass.dev/links/118), где данные представлены в виде многомерной карты, столбцы сгруппированы в семейства столбцов (обычно хранящие данные одного типа), а внутри каждого семейства столбцов данные сохраняются построчно. Такая структура лучше всего подходит для хранения данных, извлекаемых с помощью ключа или последовательности ключей.
Классический пример — Webtable из статьи, посвященной BigTable [CHANG06]. Webtable сохраняет моментальные снимки содержимого веб-страниц, их атрибутов и связей между ними в момент, соответствующий определенной временной метке. Страницы идентифицируются по URL-адресу, записанному в обратном порядке, а все атрибуты (такие, как содержимое страницы и якоря, представляющие ссылки между страницами) идентифицируются по временным меткам, для которых были сделаны эти снимки. В упрощенном виде это можно представить в виде вложенной карты, как показано на рис. 1.3.
Рис. 1.3. Концептуальное представление структуры Webtable
Данные сохраняются в многомерной отсортированной карте с иерархическими индексами: мы можем найти данные, относящиеся к конкретной веб-странице, по ее обращенному URL-адресу и ее содержимое или якоря — по временной метке. Каждая строка индексируется своим ключом строки. Связанные столбцы группируются в семейства столбцов (в данном случае — в семейства contents (содержимое) и anchor (якорь)), которые сохраняются на диске по отдельности. Каждый столбец внутри семейства идентифицируется с помощью ключа столбца, включающего в себя имя семейства столбцов и квалификатор (в данном случае — html, cnnsi.com, my.look.ca). Семейства столбцов хранят несколько версий данных согласно меткам времени. Такая структура позволяет нам быстро находить записи более высокого уровня (веб-страницы в данном случае) и их параметры (версии содержимого и ссылки на другие страницы).
Хотя такое представление полезно для понимания сути хранилищ с широкими столбцами, их физическое расположение выглядит несколько по-другому. Схематическое представление компоновки данных в семействах столбцов показано на рис. 1.4: семейства столбцов сохраняются по отдельности, но в каждом семействе столбцов данные, относящиеся к отдельному ключу, сохраняются вместе.
Рис. 1.4. Физическая структура Webtable
Файлы данных и индексные файлы
Основной целью СУБД являются хранение данных и обеспечение быстрого доступа к ним. Но как организованы эти данные? Почему нужна именно СУБД, а не просто некоторый набор файлов? Как организация файлов повышает эффективность работы?
СУБД используют файлы для хранения данных, но вместо того, чтобы для поиска записей полагаться на иерархию каталогов и файлов файловой системы, они формируют файлы с использованием специальных форматов, зависящих от конкретной реализации системы. Основными причинами использования специальной структуры файлов вместо неструктурированных файлов являются:
Эффективность хранения
Файлы организованы таким образом, чтобы минимизировать затраты на хранение каждой записи данных.
Эффективность доступа
Записи можно получить за наименьшее возможное число шагов.
Эффективность обновления
Обновления записей выполняются таким образом, чтобы свести к минимуму количество внесенных на диск изменений.
СУБД хранят записи данных, состоящие из нескольких полей, в таблицах, а каждая таблица обычно представлена отдельным файлом. Каждую запись в таблице можно найти с помощью ключа поиска. Для поиска записей СУБД используют индексы: вспомогательные структуры данных, которые позволяют эффективно находить записи данных без сканирования всей таблицы при каждой операции доступа. Индексы состоят из подмножества полей, идентифицирующих записи.
В системах баз данных обычно разделяются файлы данных и индексныефайлы: файлы данных хранят записи данных, а индексные файлы хранят метаданные записей, которые используются для поиска записей в файлах данных. Индексные файлы обычно меньше файлов данных. Файлы разбиваются на страницы, которые обычно имеют размер одного или нескольких дисковых блоков. Страницы могут быть организованы как последовательности записей или как слоттированные страницы (slotted page) (см. раздел «Слоттированные страницы», с. 70).
Новые записи (вставки) и обновления существующих записей представлены парами «ключ–значение». Большинство современных систем хранения данных не удаляют данные со страниц явным образом. Вместо этого они используют маркеры удаления (также называемые отметками полного удаления), которые содержат метаданные удаления, такие как ключ и временная метка. Пространство, занимаемое записями, затененными обновлениями или маркерами удаления, освобождается во время сборки мусора, в ходе которой считываются страницы, затем в новое место записываются актуальные (т. е. незатененные) записи и удаляются затененные.
Файлы данных
Файлы данных (иногда называемые первичными файлами) могут быть реализованы в виде индексированной таблицы (index-organized table, IOT), таблицы-кучи (файла-кучи) или хэшированной таблицы (хэшированного файла).
Записи в файлах-кучах не организованы согласно какому-либо определенному порядку и в большинстве случаев размещаются в порядке записи. Таким образом, при добавлении новых страниц не требуется никаких дополнительных действий или реорганизации файлов. Файлы-кучи требуют использования дополнительных индексных структур, указывающих на места хранения записей данных, чтобы можно было производить их поиск.
В хэшированных файлах записи хранятся в сегментах, а хэш-значение ключа определяет, к какому сегменту относится запись. Записи в сегменте могут храниться в порядке добавления или сортироваться по ключам для повышения скорости поиска.
В индексированных таблицах (IOT) данные хранятся в самом индексе. Поскольку записи отсортированы по ключу, сканирование диапазона в IOT можно реализовать путем последовательного сканирования содержимого.
Хранение записей данных в индексе позволяет снизить число операций дискового поиска по крайней мере на единицу, так как после обхода индекса и нахождения искомого ключа нам не нужно обращаться к отдельному файлу, чтобы найти соответствующую запись данных.
Когда записи хранятся в отдельном файле, индексные файлы содержат элементы данных, однозначно идентифицирующие записи данных и содержащие достаточно информации, чтобы найти их в файле данных. Например, мы можем хранить файловые смещения (иногда называемые локаторами строк), позиции записей данных в файле данных или идентификаторы сегментов в случае хэш-файлов. В индексированных таблицах элементы данных содержат непосредственно записи данных.
Индексные файлы
Индекс — это структура, с помощью которой записи данных организуются на диске таким образом, чтобы повысить эффективность операций извлечения. Индексные файлы организованы как специализированные структуры, которые сопоставляют ключи с теми местами в файлах данных, где хранятся записи, идентифицированные этими ключами (в случае файлов-куч) или первичными ключами (в случае индексированных таблиц).
Индекс первичногофайла (файла данных) называется первичным индексом. В большинстве случаев мы также можем принять, что первичный индекс строится на основе первичного ключа или набора ключей, идентифицированных как первичные. Все остальные индексы называются вторичными.
Вторичные индексы могут указывать непосредственно на запись данных или просто хранить ее первичный ключ. Указатель на запись данных может содержать смещение в файле-куче или индексированной таблице. Несколько вторичных индексов могут указывать на одну и ту же запись, что позволяет идентифицировать одну запись данных разными полями и находить ее с помощью разных индексов. Первичные индексные файлы содержат уникальную запись для каждого ключа поиска, а вторичные индексы могут содержать несколько записей для каждого ключа поиска [MOLINA08].
Если порядок записей данных соответствует порядку ключей поиска, такой индекс называется кластеризованным. Записи данных в случае кластеризации обычно хранятся в том же файле или в кластеризованном файле в соответствии с порядком ключей. Если данные хранятся в отдельном файле и их порядок не соответствует порядку ключей, индекс называется некластеризованным (или некластерным).
На рис. 1.5 показана разница между этими двумя подходами:
а) Два индекса ссылаются на записи данных непосредственно из вторичных индексных файлов.
б) Вторичный индекс обращается к уровню косвенности первичного индекса, чтобы найти записи данных.
Многие СУБД используют явный первичный ключ — набор столбцов, которые однозначно идентифицируют запись базы данных. В тех случаях, когда первичный ключ не задан, может создать неявный первичный ключ (например, подсистема хранения InnoDB базы данных MySQL добавляет новый столбец с автоинкрементом индекса и заполняет его значения автоматически).
Эта терминология используется в СУБД различных типов: реляционных СУБД (таких, как MySQL и PostgreSQL), нереляционных хранилищах на основе Dynamo (таких, как Apache Cassandra (https://databass.dev/links/119) и Riak (https://databass.dev/links/120)) и документоориентированных хранилищах (таких, как MongoDB). Понятия могут иметь специфичные для конкретной системы названия, но чаще всего есть четкое сопоставление с этой терминологией.
Рис. 1.5. Хранение записей данных в индексном файле и хранение смещений в пределах файла данных (сегменты индекса показаны белым цветом; сегменты, содержащие записи данных, показаны серым цветом)
Индексированные таблицы хранят информацию в порядке индекса и являются кластеризованными по определению. Первичные индексы являются кластеризованными в большинстве случаев. Вторичные индексы являются некластеризованными по определению, так как служат для облегчения доступа по ключам, отличным от первичных. Кластеризованные индексы могут быть как индексированными файлами, так и иметь отдельные файлы индексов и данных.
Первичный индекс как косвенный уровень
Специалисты по базам данных расходятся во мнениях относительно того, следует ли ссылаться на записи данных напрямую (посредством файлового смещения) или посредством индекса первичного ключа5.
Оба подхода имеют свои плюсы и минусы, и лучше обсуждать их в рамках полной реализации. При непосредственном обращении к данным мы можем сократить число операций дискового поиска, но здесь кроются дополнительные затраты на обновление указателей всякий раз, когда запись обновляется или перемещается в процессе обслуживания. Использование косвенного обращения посредством первичного индекса позволяет снизить затраты на обновление указателей, но при этом возрастает стоимость чтения.
Обновление всего нескольких индексов хорошо подходит в том случае, когда рабочая нагрузка в основном состоит из операций чтения, но этот подход плохо работает для рабочих нагрузок с интенсивной записью данных с использованием нескольких индексов. Для снижения стоимости обновления указателей вместо смещения полезных данных некоторые реализации используют первичные ключи для косвенной адресации. Например, MySQL InnoDB использует первичный индекс и при выполнении запроса производит две операции поиска: по вторичному и по первичному индексам [TARIQ11]. При этом мы несем дополнительные затраты на выполнение поиска по первичному индексу, вместо того чтобы следовать смещению непосредственно из вторичного индекса.
На рис. 1.6 показано различие этих двух подходов:
а) Два индекса ссылаются на записи данных непосредственно из вторичных индексных файлов.
б) Вторичный индекс обращается к уровню косвенности первичного индекса, чтобы найти записи данных.
Также можно использовать гибридный подход и хранить смещения вместе с первичными ключами внутри файлов данных. Во время обработки запроса, вы сперва проверяете, является ли смещение (указатель) на данные все еще действительным, и только в случае если указатель более не действителен, вы будете вынуждены осуществить поиск по первичному ключу, и обновить устарелый указатель.
Рис. 1.6. Прямое обращение к кортежам данных (а) и использование первичного индекса в качестве косвенного уровня (б)
Буферизация, неизменяемость и упорядочение
Каждая подсистема хранения построена на основе некоторой структуры данных. Однако эти структуры не описывают суть кэширования, восстановления, управления транзакциями и других элементов, надстраиваемых подсистемами хранения поверх этих структур.
В следующих главах мы начнем обсуждение с B-деревьев (см. раздел «Вездесущие B-деревья», с. 51) и попытаемся понять, почему существует так много вариантов B-деревьев и почему для баз данных постоянно появляются новые структуры хранения данных.
Структуры хранения имеют три общие переменные: они используют буферизацию (или избегают ее использование), неизменяемые (или изменяемые) файлы и хранят значения в упорядоченном (или неупорядоченном) виде. Большинство из тех различий и оптимизаций в структурах хранения, которые мы рассмотрим в этой книге, связаны с одним из этих трех понятий.
Буферизация
Определяет, будет ли структура хранения накапливать определенный объем данных в памяти перед их размещением на диске. Конечно, каждая дисковая структура должна в какой-то степени использовать буферизацию, так как минимальная единица передачи данных на диск и с диска — это блок и желательно записывать полные блоки. Здесь речь идет о необязательной буферизации, которая реализуется разработчиками подсистем хранения по их усмотрению. Так, одна из первых оптимизаций, обсуждаемых в этой книге, сводится к тому, чтобы добавить резидентные буферы в узлы B-дерева и тем самым снизить затраты на ввод-вывод (см. раздел «Ленивые B-деревья», с. 132). Однако это не единственный способ применения буферизации. Например, двухкомпонентные LSM-деревья (см. подраздел «Двухкомпонентное LSM-дерево», с. 151), несмотря на их сходство с B-деревьями, используют буферизацию совершенно по-другому и сочетают буферизацию с неизменяемостью.
Изменяемость (или неизменяемость)
Определяет, будет ли структура хранения после считывания частей файла и их обновления записывать обновленные результаты в то же место в файле. Неизменяемые структуры доступны только для добавления: после записи содержимое файла не изменяется. Вместо этого изменения добавляются в конец файла. Есть и другие способы реализации неизменяемости. Один из них — копирование при записи (см. раздел «Копирование при записи», с. 129), где измененная страница, содержащая обновленную версию записи, записывается в новое место в файле, а не в ее исходное местоположение. Одно из главных различий между LSM- и B-деревьями состоит в том, что первые являются неизменяемыми структурами, а вторые — структурами с обновлением на месте. В то же время некоторые структуры основаны на идее B-деревьев, но являются при этом неизменяемыми, как, например, Bw-деревья (см. раздел «Bw-деревья», с. 138).
Упорядочение
Определяется тем, совпадает ли порядок (сортировка) записей данных в страницах на диске с порядком ключей в данных. Другими словами, хранятся ли соседние ключи в смежных сегментах на диске. Это свойство часто определяет, можем ли мы эффективно сканировать диапазон записей, а не просто находить отдельные записи данных. Хранение данных в неупорядоченном виде (чаще всего в порядке включения в базу) открывает некоторые возможности для оптимизации времени записи. Например, Bitcask (см. подраздел «Bitcask», с. 171) и WiscKey (см. подраздел «WiscKey», с. 173) хранят записи данных непосредственно в файлах, доступных только для добавления.
Конечно, краткого обсуждения этих трех концепций недостаточно, чтобы показать их силу, и мы продолжим эту дискуссию на протяжении всей книги.
Итоги
В этой главе мы обсудили архитектуру СУБД и рассмотрели ее основные компоненты.
Мы обсудили резидентные и дисковые хранилища, чтобы выяснить, насколько важными являются дисковые структуры и чем они отличаются от структур, размещаемых в оперативной памяти. Мы пришли к выводу, что дисковые структуры важны для обоих типов хранилищ, но используются для разных целей.
Чтобы понять, как схемы доступа влияют на проектирование СУБД, мы обсудили колоночные и строчные СУБД, а также основные их различия. Чтобы начать дискуссию о способах хранения данных, мы рассмотрели файлы данных и индексные файлы.
Наконец, мы ввели три основных понятия: буферизация, неизменяемость и упорядочение. Мы будем использовать их на протяжении всей этой книги, чтобы акцентировать внимание на связанных с ними свойствах подсистем хранения.
Дополнительная литература
Если вы хотите узнать больше о концепциях, упомянутых в этой главе, вы можете обратиться к следующим источникам:
Архитектура баз данных
Hellerstein, Joseph M., Michael Stonebraker, and James Hamilton. 2007. «Architecture of a Database System». Foundations and Trends in Databases 1, no. 2 (February): 141–259. https://doi.org/10.1561/1900000002.
Колоночные СУБД
Abadi, Daniel, Peter Boncz, Stavros Harizopoulos, Stratos Idreaos, and Samuel Madden. 2013. The Design and Implementation of Modern Column-Oriented Database Systems. Hanover, MA: Now Publishers Inc.
Резидентные СУБД
Faerber, Frans, Alfons Kemper, and Per-Åke Alfons. 2017. Main Memory Database Systems. Hanover, MA: Now Publishers Inc.
2 Сравнение задержек доступа к диску и памяти и многих других важных параметров, приведенных за несколько лет, и их графическое представление см. на https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html.
3 Пространственная локальность — это один из принципов локальности, означающий, что если к какой-либо области памяти осуществляется доступ, то в ближайшем будущем будет осуществляться доступ к соседней области.
4 Векторные инструкции, или инструкции с одним потоком команд и несколькими потоками данных (Single Instruction Multiple Data, SIMD), составляют класс инструкций ЦП, выполняющих одну операцию над несколькими элементами данных.
5 Исходная публикация, которая вызвала эту дискуссию, была спорной и односторонней, но вы можете обратиться к презентации, сравнивающей индексы MySQL и PostgreSQL и форматы хранения, которая также ссылается на исходный источник.
Глава 2. Введение в B-деревья
В предыдущей главе мы разделили структуры хранения данных на две группы: изменяемые и неизменяемые, и определили неизменяемость как одно из основных свойств, влияющих на их проектирование и реализацию. Большинство изменяемых структур хранения используют механизм обновления на месте. Во время операций вставки, удаления или обновления записи данных обновляются непосредственно на месте их расположения в целевом файле.
Подсистемы хранения часто допускают наличие в базе данных нескольких версий одной и той же записи данных; например, при использовании многоверсионного управления конкурентным доступом (см. подраздел «Многоверсионное управление конкурентным доступом» на с. 117) или при организации слоттированных страниц (см. раздел «Слоттированные страницы» на с. 70). Для простоты пока давайте предположим, что каждый ключ связан только с одной записью данных, которая имеет уникальное местоположение.
Одной из самых популярных структур хранения данных является B-дерево. Многие СУБД с открытым исходным кодом основаны на B-деревьях, и за прошедшие годы они доказали, что охватывают большинство сценариев использования.
B-деревья не являются недавним изобретением: они были введены Рудольфом Байером и Эдвардом М. Маккрейтом еще в 1971 году и с годами приобрели популярность. К 1979 году существовало уже довольно много вариантов B-деревьев. Дуглас Комер сгруппировал и систематизировал некоторые из них [COMER79].
Прежде чем мы погрузимся в изучение B-деревьев, давайте сначала поговорим о том, почему мы должны рассматривать альтернативы традиционным деревьям поиска, таким как, например, двоичные деревья поиска, 2-3-деревья и АВЛ-деревья [KNUTH98]. Для этого давайте вспомним, что такое двоичные деревья поиска.
Двоичные деревья поиска
Двоичное дерево поиска — это упорядоченная структура данных в оперативной памяти, используемая для эффективного поиска значений по ключу. Двоичные деревья состоят из нескольких узлов. Каждый узел дерева представлен ключом, значением, связанным с этим ключом, и двумя указателями на потомков (отсюда и название — двоичное). Двоичные деревья начинаются с одного узла, называемого корневым. При этом у дерева может быть только один корень. На рис. 2.1 показан пример двоичного дерева поиска.
Рис. 2.1. Двоичное дерево поиска
Каждый узел разделяет пространство поиска на левое и правое поддеревья, как показано на рис. 2.2; при этом ключ узла больше любого ключа, хранящегося в его левом поддереве, и меньше любого ключа, хранящегося в его правом поддереве [SEDGEWICK11].
Рис. 2.2. Инварианты узлов двоичного дерева
