Что сохраняется во время работы с бд
информатика
Лекции
1. Введение
ИНФОРМАЦИЯ И ЕЕ РОЛЬ В СОВРЕМЕННОМ ОБЩЕСТВЕ.
ИНФОРМАТИКА- НАУКА, ИЗУЧАЮЩАЯ СПОСОБЫ АВТОМАТИЗИРОВАННОГО СОЗДАНИЯ, ХРАНЕНИЯ, ОБРАБОТКИ, ИСПОЛЬЗОВАНИЯ, ПЕРЕДАЧИ И ЗАЩИТЫ ИНФОРМАЦИИ.
ИНФОРМАЦИЯ – ЭТО НАБОР СИМВОЛОВ, ГРАФИЧЕСКИХ ОБРАЗОВ ИЛИ ЗВУКОВЫХ СИГНАЛОВ, НЕСУЩИХ ОПРЕДЕЛЕННУЮ СМЫСЛОВУЮ НАГРУЗКУ.
В развитых странах большинство работающих заняты не в сфере производства, а в той или иной степени занимаются обработкой информации. Поэтому философы называют нашу эпоху постиндустриальной. В 1983 году американский сенатор Г.Харт охарактеризовал этот процесс так: «Мы переходим от экономики, основанной на тяжелой промышленности, к экономике, которая все больше ориентируется на информацию, новейшую технику и технологию, средства связи и услуги..»
2. КРАТКАЯ ИСТОРИЯ РАЗВИТИЯ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ.
Вся история развития человеческого общества связана с накоплением и обменом информацией (наскальная живопись, письменность, библиотеки, почта, телефон, радио, счеты и механические арифмометры и др.). Коренной перелом в области технологии обработки информации начался после второй мировой войны.
В вычислительных машинах первого поколения основными элементами были электронные лампы. Эти машины занимали громадные залы, весили сотни тонн и расходовали сотни киловатт электроэнергии. Их быстродействие и надежность были низкими, а стоимость достигала 500-700 тысяч долларов.
Появление более мощных и дешевых ЭВМ второго поколения стало возможным благодаря изобретению в 1948 году полупроводниковых устройств- транзисторов. Главный недостаток машин первого и второго поколений заключался в том, что они собирались из большого числа компонент, соединяемых между собой. Точки соединения (пайки) являются самыми ненадежными местами в электронной технике, поэтому эти ЭВМ часто выходили из строя.
В ЭВМ третьего поколения (с середины 60-х годов ХХ века) стали использоваться интегральные микросхемы (чипы)- устройства, содержащие в себе тысячи транзисторов и других элементов, но изготовляемые как единое целое, без сварных или паяных соединений этих элементов между собой. Это привело не только к резкому увеличению надежности ЭВМ, но и к снижению размеров, энергопотребления и стоимости (до 50 тысяч долларов).
История ЭВМ четвертого поколения началась в 1970 году, когда ранее никому не известная американская фирма INTEL создала большую интегральную схему (БИС), содержащую в себе практически всю основную электронику компьютера. Цена одной такой схемы (микропроцессора) составляла всего несколько десятков долларов, что в итоге и привело к снижению цен на ЭВМ до уровня доступных широкому кругу пользователей.
СОВРЕМЕННЫЕ КОМПЬТЕРЫ- ЭТО ЭВМ ЧЕТВЕРТОГО ПОКОЛЕНИЯ, В КОТОРЫХ ИСПОЛЬЗУЮТСЯ БОЛЬШИЕ ИНТЕГРАЛЬНЫЕ СХЕМЫ.
6.ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В КОМПЬЮТЕРЕ И ЕЕ ОБЪЕМ.
ЛЮБОЕ СООБЩЕНИЕ НА ЛЮБОМ ЯЗЫКЕ СОСТОИТ ИЗ ПОСЛЕДОВАТЕЛЬНОСТИ СИМВОЛОВ- БУКВ, ЦИФР, ЗНАКОВ. Действительно, в каждом языке есть свой алфавит из определенного набора букв (например, в русском- 33 буквы, английском- 26, и т.д.). Из этих букв образуются слова, которые в свою очередь, вместе с цифрами и знаками препинания образуют предложения, в результате чего и создается текстовое сообщение. Не является исключением и язык на котором «говорит» компьютер, только набор букв в этом языке является минимально возможным.
В КОМПЬЮТЕРЕ ИСПОЛЬЗУЮТСЯ 2 СИМВОЛА- НОЛЬ И ЕДИНИЦА (0 и 1), АНАЛОГИЧНО ТОМУ, КАК В АЗБУКЕ МОРЗЕ ИСПОЛЬЗУЮТСЯ ТОЧКА И ТИРЕ. Действительно, закодировав привычные человеку символы (буквы, цифры, знаки) в виде нулей и единиц (или точек и тире), можно составить, передать и сохранить любое сообщение.
ЭТО СВЯЗАНО С ТЕМ, ЧТО ИНФОРМАЦИЮ, ПРЕДСТАВЛЕННУЮ В ТАКОМ ВИДЕ, ЛЕГКО ТЕХНИЧЕСКИ СМОДЕЛИРОВАТЬ, НАПРИМЕР, В ВИДЕ ЭЛЕКТРИЧЕСКИХ СИГНАЛОВ. Если в какой-то момент времени по проводнику идет ток, то по нему передается единица, если тока нет- ноль. Аналогично, если направление магнитного поля на каком-то участке поверхности магнитного диска одно- на этом участке записан ноль, другое- единица. Если определенный участок поверхности оптического диска отражает лазерный луч- на нем записан ноль, не отражает- единица.
ОБЪЕМ ИНФОРМАЦИИ, НЕОБХОДИМЫЙ ДЛЯ ЗАПОМИНАНИЯ ОДНОГО ИЗ ДВУХ СИМВОЛОВ-0 ИЛИ 1, НАЗЫВАЕТСЯ 1 БИТ (англ. binary digit- двоичная единица). 1 бит- минимально возможный объем информации. Он соответствует промежутку времени, в течение которого по проводнику передается или не передается электрический сигнал, участку поверхности магнитного диска, частицы которого намагничены в том или другом направлении, участку поверхности оптического диска, который отражает или не отражает лазерный луч, одному триггеру, находящемуся в одном из двух возможных состояний.
Итак, если у нас есть один бит, то с его помощью мы можем закодировать один из двух символов- либо 0, либо 1.
3 бита- 8 вариантов;
Продолжая дальше, получим:
4 бита- 16 вариантов,
7 бит- 128 вариантов,
8 бит- 256 вариантов,
9 бит- 512 вариантов,
10 бит- 1024 варианта,
В обычной жизни нам достаточно 150-160 стандартных символов (больших и маленьких русских и латинских букв, цифр, знаков препинания, арифметических действий и т.п.). Если каждому из них будет соответствовать свой код из нулей и единиц, то 7 бит для этого будет недостаточно (7 бит позволят закодировать только 128 различных символов), поэтому используют 8 бит.
ДЛЯ КОДИРОВАНИЯ ОДНОГО ПРИВЫЧНОГО ЧЕЛОВЕКУ СИМВОЛА В КОМПЬЮТЕРЕ ИСПОЛЬЗУЕТСЯ 8 БИТ, ЧТО ПОЗВОЛЯЕТ ЗАКОДИРОВАТЬ 256 РАЗЛИЧНЫХ СИМВОЛОВ.
СТАНДАРТНЫЙ НАБОР ИЗ 256 СИМВОЛОВ НАЗЫВАЕТСЯ ASCII ( произносится «аски», означает «Американский Стандартный Код для Обмена Информацией»- англ. American Standart Code for Information Interchange).
ОН ВКЛЮЧАЕТ В СЕБЯ БОЛЬШИЕ И МАЛЕНЬКИЕ РУССКИЕ И ЛАТИНСКИЕ БУКВЫ, ЦИФРЫ, ЗНАКИ ПРЕПИНАНИЯ И АРИФМЕТИЧЕСКИХ ДЕЙСТВИЙ И Т.П.
КАЖДОМУ СИМВОЛУ ASCII СООТВЕТСТВУЕТ 8-БИТОВЫЙ ДВОИЧНЫЙ КОД, НАПРИМЕР:
ОБЪЕМ ИНФОРМАЦИИ, НЕОБХОДИМЫЙ ДЛЯ ЗАПОМИНАНИЯ ОДНОГО СИМВОЛА ASCII НАЗЫВАЕТСЯ 1 БАЙТ.
Очевидно что, поскольку под один стандартный ASCII-символ отводится 8 бит,
Остальные единицы объема информации являются производными от байта:
1 КИЛОБАЙТ = 1024 БАЙТА И СООТВЕТСТВУЕТ ПРИМЕРНО ПОЛОВИНЕ СТРАНИЦЫ ТЕКСТА,
1 МЕГАБАЙТ = 1024 КИЛОБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 500 СТРАНИЦАМ ТЕКСТА,
1 ГИГАБАЙТ = 1024 МЕГАБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 2 КОМПЛЕКТАМ ЭНЦИКЛОПЕДИИ,
1 ТЕРАБАЙТ = 1024 ГИГАБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 2000 КОМПЛЕКТАМ ЭНЦИКЛОПЕДИИ.
СКОРОСТЬ ПЕРЕДАЧИ ИНФОРМАЦИИ ПО ЛИНИЯМ СВЯЗИ ИЗМЕРЯЕТСЯ В БОДАХ.
В частности, если говорят, что пропускная способность какого-то устройства составляет 28 Килобод, то это значит, что с его помощью можно передать по линии связи около 28 тысяч нулей и единиц за одну секунду.
7. СЖАТИЕ ИНФОРМАЦИИ НА ДИСКЕ
ИНФОРМАЦИЮ НА ДИСКЕ МОЖНО ОБРАБОТАТЬ С ПОМОЩЬЮ СПЕЦИАЛЬНЫХ ПРОГРАММ ТАКИМ ОБРАЗОМ, ЧТОБЫ ОНА ЗАНИМАЛА МЕНЬШИЙ ОБЪЕМ.
Сжатие информации используют, если объем носителя информации недостаточен для хранения требуемого объема информации или информацию надо послать по электронной почте
Программы, используемые при сжатии отдельных файлов называются архиваторами. Эти программы часто позволяют достичь степени сжатия информации в несколько раз.
Путеводитель по базам данных в 2021 г
Данные — это один из наиболее важных компонентов геопространственных технологий и, пожалуй, любой другой отрасли. К управлению данными сейчас относятся серьезно во всех отраслях, поэтому знания по этой дисциплине имеют важное значение для карьеры ИТ-специалистов. Этот цикл статей задуман как универсальное руководство, в котором мы рассмотрим тему от и до, начиная с вопроса «Что такое данные?» и заканчивая изучением и применением геопространственных запросов.
Основные понятия баз данных
Что такое данные?
Данные могут представлять собой любую информацию, которая сохраняется с целью обращения к ней в будущем. Эта информация может включать числа, текст, аудио- и видеоматериалы, местонахождение, даты и т. д. Она может быть записана на бумаге либо сохранена на жестком диске компьютера или даже в облаке.
Что такое база данных?
Множество записей данных, собранных вместе, образуют базу данных. Базы данных обычно создаются для того, чтобы пользователи могли обращаться к большому количеству данных и массово выполнять с ними определенные операции.База данных может хранить что угодно: представьте себе, например, блокнот вашей бабушки со всеми ее вкусными рецептами, учетную книгу ваших родителей, куда они записывают все доходы и расходы, или свою страницу в Facebook со списком всех ваших друзей. Из этих примеров видно, что все данные в базе данных относятся более-менее к одному типу.
Зачем нужна база данных?
Создание базы данных упрощает разным пользователям доступ к наборам информации. Приведенные выше примеры показывают, что в базе данных мы можем хранить записи с информацией похожего типа, но это правда лишь отчасти, поскольку с появлением баз данных NoSQL это определение меняется (подробнее читайте далее в статье).Так как размер веб-сайтов становится все больше и степень их интерактивности все выше, данные о пользователях, клиентах, заказах и т. д. становятся важными активами компаний, которые испытывают потребность в надежной и масштабируемой базе данных и инженерах, способных в ней разобраться.
Система управления базами данных (СУБД)
Итак, мы уже знаем, что данные и базы данных важны, но как осуществляется работа с базами данных в компьютерных системах? Вот тут на сцену и выходит СУБД. СУБД — это программное обеспечение, предоставляющее нам способ взаимодействия с базами данных на компьютере для выполнения различных операций, таких как создание, редактирование, вставка данных и т. д. Для этого СУБД предоставляет нам соответствующие API. Редко какие программы не используют СУБД для работы с данными, хранящимися на диске.Помимо операций с данными СУБД также берет на себя резервное копирование, проверку допуска, проверку состояния базы данных и т. д. Поэтому рекомендуется всегда использовать СУБД при работе с базами данных.
Пространственные данные и база данных
Особое внимание мы уделим обработке пространственных данных, поэтому я хотел бы обсудить здесь этот тип данных. Пространственные данные несколько отличаются от остальных. Координаты необходимо сохранять в особом формате, который обычно указан в документации на веб-сайте о базе данных. Этот формат позволяет базе считывать и правильно воспринимать координаты. Если обычно для поиска данных мы используем запросы типа Получить все результаты, где возраст > 15, то пространственный запрос выглядит как-то так: Получить все результаты в радиусе 10 км от определенной точки. Поэтому пространственные данные необходимо хранить в надлежащем формате.
Типы баз данных
Базы данных обычно делятся на два типа: реляционные и нереляционные. Оба типа имеют свои плюсы и минусы. Было бы глупо утверждать, что один лучше другого, поскольку это будет зависеть от варианта использования. Конкретно для пространственных данных я в 99 % случаев использую реляционные базы данных, и вы скоро поймете почему.
Реляционные базы данных и РСУБД
Допустим, ваш начальник просит вас создать электронную таблицу с важной информацией, включающей имена, местонахождения, адреса электронной почты, номера телефонов и должности всех сотрудников. Вы сразу же откроете таблицу Excel или Google Spreadsheets, напишете все эти названия столбцов и начнете собирать информацию.
Образец таблицы с информацией
Закономерность здесь заключается в том, что каждая запись содержит ограниченный и фиксированный набор полей, которые нам нужно заполнить. Таким образом мы создали таблицу со всей информацией, где у каждой записи имеется уникальный первичный ключ, который определяет ее однозначным образом и делает ее доступной для всех операций. В реляционных базах данных любая таблица содержит фиксированное количество столбцов, и можно устанавливать связи между разными столбцами.
Связь между двумя столбцами
Взаимосвязи в реляционных базах данных мы подробно рассмотрим позже.
По сравнению с базами данных NoSQL, недостатком реляционных баз данных является относительно медленное получение результатов, когда количество данных стремительно увеличивается (по мнению автора статьи — прим. пер.). Еще один недостаток заключается в том, что при добавлении каждой записи нужно следовать определенным правилам (типы столбцов, количество столбцов и т. д.), — мы не можем просто добавить отдельный столбец только для одной записи.В реляционных базах данных используется SQL (Structured Query Language — язык структурированных запросов), с помощью которого пользователи могут взаимодействовать с данными, хранящимися в таблицах. SQL стал одним из наиболее широко используемых языков для этой цели. Мы подробнее поговорим об SQL чуть позже.Вот примеры некоторых известных и часто используемых реляционных баз данных: PostgreSQL, MySQL, MS SQL и т. д. У каждой крупной компании, занимающейся реляционными базами данных, есть собственная версия SQL. В большинстве аспектов они выглядят одинаково, но иногда требуется немного изменить какой-нибудь запрос, чтобы получить те же результаты в другой базе данных (например, при переходе из PostgreSQL в MySQL).
Нереляционные базы данных (NoSQL)
Все базы данных, не являющиеся реляционными, относятся к категории нереляционных баз данных. Обычно данные хранятся в нетабличном формате, например:
Основное преимущество баз данных NoSQL состоит в том, что все строки независимы и могут иметь разные столбцы. Как показано на изображении ниже, оба пользователя относятся к одной и той же таблице Core_user, но их записи содержат разную информацию.
База данных NoSQL реального времени в Google Firebase
База данных NoSQL реального времени в Google Firebase
При использовании баз данных NoSQL пользователям иногда приходится прописывать собственную логику, чтобы добавить уникальный ключ к каждой записи и тем самым обеспечить доступ к записям. В большинстве стандартных баз данных NoSQL, таких как Firebase и MongoDB, для хранения данных используется формат JSON. Благодаря этому очень легко и удобно выполнять операции с данными из веб-приложений, используя JavaScript, Python, Ruby и т. д.
Рекомендации по выбору типа базы для хранения пространственных данных
Очевидно, что нам хотелось бы сохранить точку, линию, многоугольник, растры и т. д. так, чтобы это имело смысл, вместо того чтобы сохранять просто координаты. Нам нужна СУБД, которая позволяет не только сохранять данные, но и запрашивать их пространственными методами (буфер, пересечение, вычисление расстояния и т. д.). На сегодняшний день для этого лучше всего подходят реляционные базы данных, поскольку в SQL есть функции, помогающие выполнять подобные операции. Использование таких дополнительных средств, как PostGIS для PostgreSQL, открывает разработчикам возможности для написания сложных пространственных запросов. С другой стороны, NoSQL тоже работает в области геопространственных технологий: например, MongoDB предоставляет кое-какие функции для выполнения геопространственных операций. Однако реляционные базы данных все же лидируют на рынке с большим отрывом.
Работа с РСУБД
Основное внимание мы уделим РСУБД, так как именно эти системы в большинстве случаев мы будем использовать для хранения пространственных данных и работы с ними. В качестве примера мы будем использовать PostgreSQL, поскольку это самая перспективная реляционная база данных с открытым исходным кодом, а ее расширение PostGIS позволяет работать и с пространственными данными. Вы можете установить PostgreSQL, следуя инструкциям из документации. Помимо PostgreSQL рекомендуется также загрузить и установить pgAdmin. Платформа pgAdmin предоставляет веб-интерфейс для взаимодействия с базой данных. Также для этого можно загрузить и установить какое-либо другое совместимое ПО или использовать командную строку.
pgAdmin 4 на Mac
Пользователи могут изменять множество настроек для баз данных, включая порт, имя пользователя, пароль, доступность извне, выделение памяти и т. д., но это уже другая тема. В этой статье мы сосредоточимся на работе с данными, находящимися в базе.
Создание базы данных. Нам нужно создать базу данных (в идеале должно быть по одной базе данных для каждого проекта).
Создание новой базы данных для проекта
В инструменте запросов (Query Tool) база данных создается следующим образом:
Создание таблиц. Создание таблицы требует некоторых дополнительных соображений, поскольку именно здесь нам нужно определить все столбцы и типы данных в них. Все типы данных, которые можно использовать в PostgreSQL, вы найдете здесь.
pgAdmin позволяет нам выбрать в таблице различные ключи и ограничения, например Not Null (запрет на отсутствующие значения), Primary Key (первичный ключ) и т. д. Обсудим это подробнее чуть позже.
Создание таблицы пользователей
Заметьте, что мы не добавляли столбец первичного идентификатора в список столбцов, поскольку PostgreSQL делает это автоматически. Мы можем создать сколько угодно таблиц в одной базе данных. После того как таблицы созданы, мы можем установить связи между разными таблицами, используя определенные столбцы (обычно столбцы с идентификаторами).В инструменте запросов таблица создается следующим образом:
CRUD-операции с данными в таблицах
CRUD-операции (создание, чтение, обновление и удаление — Create, Retrieve, Update, Delete) — это своего рода hello world в мире СУБД. Поскольку эти операции используются наиболее часто, команды для их выполнения одинаковы во всех РСУБД. Мы будем писать и выполнять запросы в инструменте запросов в pgAdmin, который вызывается следующим образом:
Инструмент запросов (Query Tool) в pgAdmin
1. Создание новой записи
Для добавления новой записи в таблицу используйте следующую команду:
INSERT, INTO, VALUE являются ключевыми словами в SQL, поэтому их нельзя использовать в качестве переменных, значений и т. д. Чтобы добавить новую запись в нашу таблицу пользователей, мы напишем в инструменте запросов следующий запрос:
Обратите внимание: строки всегда следует заключать в ‘ ‘ (одинарные кавычки), а не в » » (двойные кавычки).
2. Получение записей (всех или нескольких)
Данные, хранящиеся в базе данных, можно извлечь и отобразить на экране. При этом мы можем получить все данные или ограниченное количество записей. Код для получения данных:
Этот код извлекает весь набор данных. Если вы хотите получить только 20 записей, напишите:
Если вы хотите получить данные из всех столбцов, то вместо перечисления названий всех столбцов можно написать:
Если вы хотите получить результат с определенным условием, используйте ключевое слово WHERE, как показано ниже:
Вы можете создавать даже сложные запросы, о которых мы поговорим позже.В нашем примере мы можем получить нужные нам данные:
3. Обновление записей (всех или нескольких)РСУБД позволяет нам обновить все или только некоторые записи данных, указав новые значения для столбцов.
Если вы хотите обновить определенные строки, добавьте условия с использованием ключевого слова WHERE:
В нашем случае мы обновим таблицы с помощью следующих запросов:
Обновление записей
4. Удаление записей (всех или нескольких)Удалять записи в SQL легко. Пользователь может удалить либо все строки, либо только определенные строки, добавив условие WHERE.
Удаление записей из таблицы
CRUD-операции используются очень часто, поскольку выполняют основные функции в базе данных.
Перевод подготовлен в рамках курса «Базы данных». Все желающих приглашаем на бесплатный двухдневный онлайн-интенсив «Бэкапы и репликация PostgreSQL. Практика применения». Цели занятия: настроить бэкапы; восстановить информацию после сбоя. Регистрация здесь.
Подсистемы хранения и извлечение данных. Конспект книги «Designing Data-Intensive Applications»
В этом конспекте рассмотрим, как сохранить полученные от пользователя данные и как найти их снова в случае запроса с точки зрения БД.
Почему разработчика приложений должны волновать внутренние нюансы того, как БД хранит данные и как она их находит? Вряд ли вы собираетесь реализовать собственную подсистему хранения данных с нуля, но вам определенно нужно выбрать из множества существующих подсистему хранения, подходящую именно для вашего приложения. Чтобы настроить его на оптимальную работу при вашей нагрузке, не помешает иметь хотя бы приблизительное представление о том, каковы внутренние механизмы функционирования подсистемы хранения.
Базовые структуры данных БД
Наверное, самой простой БД в мире, реализованная в виде двух функций, является командная оболочка Bash. Обе функции реализуют хранилище типа «ключ — значение». Можно вызвать команду db_set key value для сохранения key и value в базе данных. Затем можно вызвать команду db_get key для поиска последнего относящегося к искомому ключу значения и его возврата.
Рис. 1 – Пример работы db_set и db_get
Лежащий в их основе формат хранения очень прост: он представляет собой текстовый файл, в котором каждая строка содержит пару «ключ — значение», разделенную запятой. Каждый вызов функции db_set приводит к добавлению данных в конец файла, так что при обновлении ключа несколько раз старые версии значений не будут затерты. Такой механизм называется журналом, представляющий собой файл, предназначенный только для добавления данных в его конец.
Производительность функции db_get ужасна в случае большого количества записей в БД. Каждый раз, когда нужно найти ключ, db_get приходится просматривать всю базу от начала до конца, выискивая вхождения ключа. Говоря в алгоритмических терминах, сложность поиска — порядка O(n): при удвоении количества записей n в БД поиск занимает вдвое больше времени.
Для эффективного поиска значения конкретного ключа в БД необходима другая структура данных: индекс. Общая их идея заключается в дополнительном хранении определенных метаданных, служащих своеобразным дорожным указателем, помогающим найти нужные данные.
Индекс — дополнительная структура, производная от основных данных. Многие БД предоставляют возможность добавлять и удалять индексы без какого-либо воздействия на содержимое базы, это влияет только на производительность запросов. Любые индексы обычно замедляют запись, так как индекс тоже приходится обновлять всякий раз при записи данных на диск.
Это важный компромисс в системах хранения данных: хорошо подобранные индексы ускоряют запросы на чтение, но замедляют запись. Поэтому БД обычно не индексируют по умолчанию все, что можно, а заставляют разработчика приложения или администратора БД выбирать индексы вручную, на основе знания типичных для приложения паттернов запросов.
Хеш-индексы
Хранилища данных типа «ключ — значение» очень схожи с типом «словарь», реализуемым обычно в виде хеш-карты (hash map)/хеш-таблицы (hash table).
Предположим, что наше хранилище работает только путем добавления в конец файла. Тогда простейшая стратегия индексации такова: хранить в оперативной памяти хеш-карту, в которой каждому ключу поставлено в соответствие смещение (относительный адрес) в файле данных — место, где находится значение, как показано на рис. 2. При добавлении в файл новой пары «ключ — значение» происходит также обновление хеш-карты для отражения в ней относительного адреса только что записанных данных. Если нужно найти значение, то можно воспользоваться хеш-картой для поиска относительного адреса в файле данных, перейти в это место и прочитать значение.
Представленный подход может показаться некоторым упрощением, но вполне жизнеспособен. Фактически именно так работает Bitcask (подсистема хранения в распределенной NoSQL СУБД Riak). Более подробно можно прочесть в книге.
Пока что рассматривали только запись в конец файла. Как же избежать ситуации исчерпания места на диске? Хорошим решением будет разбить журнал на сегменты определенного размера, закрывая файл сегмента при достижении им определенного размера и записывая последующие данные уже в новый файл. Затем можно выполнить уплотнение (compaction) этих сегментов, как показано на рис. 3. Уплотнение означает отбрасывание дублирующихся ключей из журнала и сохранение только последней версии данных для каждого ключа. Более того, поскольку уплотнение часто приводит к значительному уменьшению размера сегментов, можно также слить несколько сегментов в один во время уплотнения.
Теперь у каждого сегмента имеется своя хеш-таблица в оперативной памяти, ставящая ключам смещение в файле. Чтобы найти значение для ключа, необходимо сначала заглянуть в хеш-карту последнего сегмента: если ключа там нет, то проверяется следующий по времени сегмент и т. д. Благодаря процессу слияния количество сегментов остается небольшим, поэтому при поиске не придется проверять слишком много хеш-карт.
Чтобы воплотить эту простую идею в жизнь, понадобится учесть немало нюансов. Более подробно можно прочесть в книге. Если кратко, то нужно учесть – формат файлов, удаление записи, восстановление после сбоев, недописанные записи, управление конкурентным доступом.
На первый взгляд, журналы, допускающие только добавление в конец файла, кажутся довольно неэкономными: почему бы не обновлять файл на месте, заменяя старое значение новым? Есть несколько причин:
Добавление в конец файла и слияние сегментов — последовательные операции записи, в большинстве случаев выполняющиеся намного быстрее случайной записи.
Конкурентный доступ и восстановление после сбоев сильно упрощаются в случае допускающих только добавление или вообще неизменяемых файлов данных.
Однако у индексов хеш-таблиц тоже есть ограничения.
Хеш-таблица должна помещаться в оперативной памяти, так что если очень много ключей, то данный тип индекса скорее всего не подойдет. В принципе, можно поддерживать хеш-карту на диске, но, к сожалению, добиться хорошей ее производительности непросто.
Запросы по диапазону неэффективны. Например, невозможно с легкостью просмотреть все записи между kitty00000 и kitty99999 — необходимо искать каждый ключ отдельно в хеш-картах.
Далее рассмотрим индексную структуру, у которой нет этих ограничений.
SS-таблицы
Давайте теперь поменяем формат файлов сегментов: потребуем, чтобы последовательность пар «ключ — значение» была отсортирована по ключу.
Назовем новый формат отсортированной строковой таблицей (sorted string table, SSTable) или SS-таблицей. Потребуем также, чтобы каждый ключ встречался лишь один раз в каждом объединенном файле сегмента (процесс уплотнения сразу гарантирует это). У SS-таблиц есть несколько больших преимуществ перед журнальными сегментами с хеш-индексами.
Первое преимущество. Объединение сегментов выполняется просто и эффективно, даже если размер файлов превышает объем доступной оперативной памяти. Этот подход близок к используемому в алгоритме сортировки слиянием (mergesort). Он показан на рис. 4: начинаем с одновременного чтения входных файлов, просматриваем первый ключ в каждом из файлов, копируем ключ в соответствии с порядком сортировки в выходной файл и повторяем эти действия. В результате получаем новый объединенный файл сегмента, также отсортированный по ключу. А если один и тот же ключ встретится в нескольких входных сегментах? Каждый сегмент содержит все записанные в БД значения за некоторый период времени. Это значит, что все значения одного из входных сегментов должны оказаться более свежими, чем все значения другого (при условии обязательного слияния воедино соседних сегментов). Если несколько сегментов содержат один и тот же ключ, то можно взять значение из наиболее нового сегмента и отбросить значения из более старых.
Второе преимущество. Чтобы найти в файле конкретный ключ, не нужно больше хранить индекс всех ключей в оперативной памяти. Например, нам нужен ключ handiwork, но мы не знаем точного смещения этого ключа в файле сегмента. Однако нам известно смещение для ключей handbag и handsome и (благодаря сортировке) то, что handiwork должен находиться между ними. Как следствие, можно перейти по смещению для handbag и просматривать, начиная с этого места, до тех пор, пока не найдем handiwork (впрочем, можем и не найти, если ключ отсутствует в данном файле).
Нам все еще нужен индекс в оперативной памяти, чтобы узнавать смещение для некоторых ключей, но он может быть разреженным: одного ключа для каждых нескольких килобайт файла сегмента вполне достаточно, поскольку несколько килобайт можно просмотреть очень быстро.
Третье преимущество. Поскольку для выполнения запроса на чтение все равно необходимо просмотреть несколько пар «ключ — значение» из заданного диапазона, вполне можно сгруппировать эти записи в блок и сжать его перед записью на диск. Каждая запись разреженного индекса в оперативной памяти затем будет указывать на начало сжатого блока. Помимо экономии пространства на диске, сжатие также снижает использование полосы пропускания ввода/вывода.
Создание и поддержание SS-таблиц
Как же отсортировать данные по ключу? Входящие операции записи могут производиться в любом порядке.
Поддержание отсортированной структуры на диске возможно, но гораздо проще будет делать это в оперативной памяти. Существует множество доступных для использования хорошо известных древовидных структур данных, например, красно-черные деревья. При использовании этих структур можно вставлять ключи в любой последовательности и затем читать их в нужном порядке.
Теперь организуем работу подсистемы хранения следующим образом.
При поступлении записи добавляем ее в располагающуюся в оперативной памяти сбалансированную структуру данных (например, красно-черное дерево). Это располагающееся в оперативной памяти дерево называется MemTable (от memory table — «таблица, расположенная в памяти»).
Когда размер MemTable превышает определенное пороговое значение — обычно несколько мегабайт, — записываем его на диск в виде файла SS-таблицы. Эта операция выполняется достаточно эффективно, поскольку дерево поддерживает пары «ключ — значение» в отсортированном по ключу виде. Новый файл SS-таблицы становится последним сегментом базы данных. А пока SS-таблица записывается на диск, операции записи продолжают выполняться в новый экземпляр MemTable.
Время от времени запускаем в фоне процесс слияния и уплотнения, чтобы объединить файлы сегментов и отбросить перезаписанные или удаленные значения.
Представленная схема работает отлично. У нее есть только одна проблема: если происходит фатальный сбой БД, то записанные позже всего данные (находящиеся в MemTable, но еще не записанные на диск) теряются. Чтобы избежать этой проблемы, можно держать на диске отдельный журнал, в конец которого немедленно добавляются все записываемые данные. Сам журнал не упорядочен, но это неважно, ведь его единственное назначение — восстановление MemTable после сбоя. Всякий раз, когда MemTable записывается в SS-таблицу, соответствующий журнал можно удалять.
Создание LSM-дерева из SS-таблиц
Подсистемы хранения, основанные на принципе слияния и уплотнения отсортированных файлов, часто называются LSM-подсистемами хранения (Log-Structured Merge).
Основная идея LSM-деревьев — применение каскада SS-таблиц, объединяемых в фоновом режиме, — проста и эффективна. Она хорошо работает даже в случае, когда размер набора данных значительно превышает доступный объем оперативной памяти. То, что данные хранятся в отсортированном виде, дает возможность эффективно выполнять запросы по диапазонам (просмотр всех ключей между установленными минимальным и максимальным значениями), а поскольку записи на диск осуществляются последовательно, LSM-дерево способно поддерживать весьма высокую пропускную способность по записи.
B-деревья
Наиболее широко используемая индексная структура — B-дерево. B-деревья очень хорошо выдержали испытание временем. Они остаются стандартной реализацией индексов практически во всех реляционных базах данных, да и многие нереляционные тоже их применяют.
Аналогично SS-таблицам B-деревья хранят пары «ключ — значение» в отсортированном по ключу виде, что позволяет эффективно выполнять поиск значения по ключу и запросы по диапазонам. Но на этом сходство заканчивается: конструктивные принципы B-деревьев совершенно другие.
Журналированные индексы, которые рассматривались ранее, разбивают базу данных на сегменты переменного размера и всегда записывают их на диск последовательно. В отличие от них, B-деревья разбивают БД на блоки или страницы фиксированного размера, обычно 4 Кбайт, и читают/записывают по одной странице за раз. Такая конструкция лучше подходит для нижележащего аппаратного обеспечения, поскольку диски тоже разбиваются на блоки фиксированного размера.
Все страницы имеют свой адрес/местоположение, благодаря чему одни страницы могут ссылаться на другие — аналогично указателям, но на диске, а не в памяти. Этими ссылками на страницы можно воспользоваться для создания дерева страниц, как показано на рис. 6.
Одна из страниц назначается корнем B-дерева, с него начинается любой поиск ключа в индексе. Данная страница содержит несколько ключей и ссылок на дочерние страницы. Каждая из них отвечает за непрерывный диапазон ключей, а ключи, располагающиеся между ссылками, указывают на расположение границ этих диапазонов.
В случае надобности добавить новый ключ следует найти страницу, в чей диапазон попадает новый ключ, и добавить его туда. Если на странице недостаточно места для него, то она разбивается на две полупустые страницы, а родительская страница обновляется, чтобы учесть это разбиение диапазона ключей на части.
Представленный алгоритм гарантирует, что дерево останется сбалансированным, то есть глубина B-дерева с n ключами будет равна O(log n). Большинству баз данных хватает деревьев глубиной три или четыре уровня, поэтому не придется проходить по множеству ссылок на страницы с целью найти нужную (четырехуровневое дерево страниц по 4 Кбайт с коэффициентом ветвления в 500 может хранить до 256 Тбайт информации).
Количество ссылок на дочерние страницы на одной странице B-дерева называется коэффициентом ветвления
При разбиении страницы из-за ее переполнения вследствие вставки необходимо записать две новые страницы, а также перезаписать их родительскую страницу для обновления ссылок на две дочерние страницы. Это опасная операция, ведь в случае фатального сбоя базы данных в тот момент, когда записана только часть страниц, индекс окажется поврежден.
Чтобы сделать БД отказоустойчивой, реализации B-деревьев обычно включают дополнительную структуру данных на диске: журнал упреждающей записи (writeahead log, WAL). Он представляет собой файл, предназначенный только для добавления, в который все модификации B-деревьев должны записываться еще до того, как применяться к самим страницам дерева. Когда база возвращается в норму после сбоя, этот журнал используется для восстановления B-дерева в согласованное состояние.
Поскольку B-деревья применяются уже достаточно долго, то за эти годы они претерпели немало усовершенствований. Более подробно можно прочесть в книге.
Сравнение B- и LSM-деревьев
Хотя реализации B-деревьев в целом более совершенны, чем реализации LSM-деревьев, последние тоже представляют некоторый интерес, благодаря своей производительности. Как правило, LSM-деревья обычно быстрее при записи, а B-деревья — при чтении. Чтение выполняется медленнее на LSM-деревьях потому, что приходится просматривать несколько различных структур данных и SS-таблиц, находящихся на разных стадиях уплотнения. Однако эти оценки часто неубедительны и сильно зависят от нюансов конкретной рабочей нагрузки. Необходимо тестировать системы именно под вашей конкретной нагрузкой, чтобы сравнение было достоверным.
В книге коротко затрагиваются несколько нюансов, которые имеет смысл учесть при оценке производительности подсистемы хранения.
Автор книги затрагивает немного и другие типы индексов, например, составные и нечеткие индексы.
Обработка транзакций или аналитика?
Приложение обычно ищет с помощью индекса небольшое количество записей по какому-либо ключу. На основе вводимых пользователем данных вставляются или обновляются записи. В силу интерактивности этих приложений такой паттерн доступа получил название «обработка транзакций в реальном времени» (online transaction processing, OLTP).
Однако БД все шире используются для аналитической обработки данных (data analytics), паттерны доступа которой совершенно другие. Обычно аналитический запрос должен просматривать огромное количество записей, вычисляя сводные статистические показатели (например, количество, сумму или среднее значение) вместо возврата пользователю необработанных данных.
Эти запросы чаще всего написаны бизнес-аналитиками и вставлены в отчеты, которые руководство компании использует для оптимизации коммерческих решений (бизнес-аналитика, business intelligence). Чтобы отличать этот паттерн применения БД от обработки транзакций, его назвали аналитической обработкой данных в реальном времени (online analytical processing, OLAP).
Смысл слова online в OLAP не вполне четко определен; вероятно, речь идет не только о том, что эти запросы используются для встроенных отчетов, но и что аналитики могут задействовать OLAP-системы интерактивно для исследовательских запросов.
Сначала как для обработки транзакций, так и для аналитических запросов использовались одни и те же базы данных. Язык SQL оказался в этом смысле весьма гибок: он работает при OLTP-запросах ничуть не хуже, чем при OLAP-запросах. Тем не менее в конце 1980-х — начале 1990-х годов возникла такая тенденция: компании прекращали задействовать OLTP-системы для целей аналитики и выполняли анализ на отдельных БД, которые назывались складами данных (data warehouse).
Складирование данных
У предприятия могут быть десятки различных систем обработки транзакций. Все эти системы сложны и требуют команды разработчиков для поддержки, так что в итоге эксплуатируются практически автономно друг от друга.
Обычно от этих OLTP-систем ожидается высокая доступность и обработка транзакций с низкой задержкой, поскольку они зачастую критичны для работы бизнеса. Администраторы БД обычно крайне неохотно разрешают бизнес-аналитикам выполнять произвольные аналитические запросы на этих базах, ведь эти запросы зачастую оказываются ресурсоемкими, связаны с просмотром больших частей набора данных, что может отрицательно сказаться на производительности выполняемых в этот момент транзакций.
Склад данных, напротив, представляет собой отдельную БД, которую аналитики могут опрашивать так, как им заблагорассудится, не влияя при этом на OLTP-операции. Склад содержит предназначенную только для чтения копию данных из всех различных OLTP-систем компании. Данные извлекаются из баз OLTP (с помощью выполнения периодических дампов данных или непрерывного потока обновлений данных), преобразуются в удобный для анализа вид, очищаются и затем загружаются в склад. Процесс их помещения в склад известен под названием «извлечение — преобразование — загрузка» (extract — transform — load, ETL).
Рис. 8 – Упрощенная схема ETL в складе данных
Большим преимуществом использования отдельного склада данных, а не выполнения запросов непосредственно к OLTP-системам является то, что склады можно оптимизировать в расчете на аналитические паттерны доступа.
Более подробно о подсистемах хранения, оптимизированных для целей анализа, можно прочесть в книге.
Резюме
В этом конспекте мы попытались разобраться в том, как БД хранят и извлекают данные. Что же происходит при сохранении данных в базе и что делает база, когда позднее запрашиваются эти данные? На высоком уровне абстракции мы видим, что подсистемы хранения делятся на две широкие категории: оптимизированные для обработки транзакций (OLTP) и оптимизированные для аналитики (OLAP). Между паттернами доступа в этих сценариях использования есть большие различия.
OLTP-системы обычно нацелены на работу с пользователями, и это означает огромное потенциальное количество запросов. Чтобы справиться с такой нагрузкой, приложения обычно затрагивают в каждом запросе только небольшое число строк. Программы запрашивают записи с помощью определенного ключа, а подсистема хранения задействует индекс для поиска данных с соответствующим ключом. Узким местом здесь обычно становится время перехода к нужной позиции на диске.
Склады данных и подобные им аналитические системы менее широко известны, поскольку они в основном применяются бизнес-аналитиками, а не конечными пользователями. Склады обрабатывают намного меньшее количество запросов, чем OLTP-системы, но все запросы обычно очень ресурсоемки и требуют просмотра миллионов строк за короткое время. Узким местом здесь обычно становится пропускная способность диска.
С точки зрения OLTP мы рассмотрели два различных подхода к подсистемам хранения.
Журналированный подход, при котором допускается только дописывание данных в файлы и удаление устаревших файлов, а не обновление записанного файла. Сюда относятся: Bitcask, SS-таблицы, LSM-деревья и другие.
Подход с обновлением на месте, при котором диск рассматривается как набор страниц заданного размера, допускающих перезапись. Крупнейший представитель этой философии — B-деревья, используемые во всех основных реляционных базах данных, а также и во многих нереляционных.