Базы Данных, 03 лекция (от 14 сентября)

Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Содержание 1 Файловые системы 1.1 Требование #1 — Распределение памяти 1.1.1 Особенности System/360 1.1.2 Два вида представления файлов на уровне пользователя 1.1.3 Две вещи за и против UNIX 1.1.4 Абстрактные типы данных в ОС 1.2 Требование #2 — Именование 1.2.1 Подходы к выбору корня ФС 1.2.1.1 Синхронизация данных во время полёта Союз-Аполлон 1.2.1.2 Компромиссный подход 1.3 Требование #3 — Защита 1.3.1 Два подхода к защите доступа 1.3.1.1 Аутентификация и Авторизация 1.3.1.2 Мандатный подход 1.3.1.3 Дискреционный подход 1.4 Требование #4 — Синхронизация 1.4.1 Контрпример — как работать с файлами в UNIX 1.4.2 Мысль 2 Где не хватает ФС 2.1 Пример простой ИС

[править] Файловые системы

Основной причиной появления ФС стали 4 требования, которые накладывали информационные системы:

1. Распределение внешней памяти
2. Именование
3. Защита (authorisation)
4. Синхронизация совместной работы (concurrency)

Сoncurrency — трудно переводимый на русский язык термин. Доступ к одному объекту нескольких активностей, причем эти доступы должны регулироваться.

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

[править] Требование #1 — Распределение памяти

[править] Особенности System/360

У истоков многих вещей, связанных с управлением данных, связана фирма IBM и, в частностии, их проект System/360. Наиболее важными вещами, появившимися в System/360, являются диски, контроллеры и каналы. В OS/360 наиболее интересной чертой являлось появление впервые в мире понятия файловой системы. IBM руководствовалась этими 4 пунктами при её создании.

Используемые в ней диски — компромисс между лентами и барабанами.

Контроллер — универсальный компьютер, используемый для специальных целей. Правда, для IBM это было не совсем так.

В СССР последним компьютером была машина на основе процессора Motorola — Беста. На памяти лектора, до того, как её перестали выпускать, там контроллеры делались на тех же кристаллах, что и основной процессор. И Motorola ставила на контроллеры процессоры предыдущего поколения (68ххх).

IBM была воодушевлена тем, что контроллеры такие умные и позволяли разгрузить ЦП, и при создании System/360 они очень многие функции ОС пытались реализовать аппаратно:

1. Поддержка на уровне хранения записей постоянного и переменного размера — на уровне контроллера для каждого файла делалась служебная запись фиксированного размера для всех файлов, так что записи в этом файле были определенного размера, и ОС могла ходить вперёд-назад по записям. Для записей переменного размера для каждой записи указывался её размер и при считывании контроллер понимал какого размера запись.
2. Индексация на уровне дисков — файл состоял из записей, каждая запись могла содержать несколько полей. Это похоже на БД, но не то. В файлах можно было объявить поле индексным, и на аппаратном уровне в специальной области диска создавался индекс, что позже позволяло этим воспользоваться.

Почему в IBM были так сделаны файлы: дело в том, что в ОС у программистов, особенно у системных программистов, всегда было желание позволить людям так писать программы, чтобы они не думали, как эти программы будут работать (следить за тонкостями реализации). Давней мечтой программистов было сделать механизм абстракции, при котором при программировании было только некое абстрактное представление о внешнем мире, заключавшееся в абстракции интерфейса. В IBM была предпринята первая попытка абстракции, и в качестве основной абстракции был принят файл. В UNIX так и есть, но для IBM это было плохо. В IBM была предпринята попытка представить всё файлом, и основную нагрузку перенести на контроллер, но в результате получилось, что появился класс интерфейсов, которые похожи, но разные. В System/360 появился Job Control Language (JCL), который позволял при запуске программы сообщить ОС, каким типом файлов та пользовалась. Это был громоздкий язык, на котором нужно было писать громоздкие конструкции для спецификации типов файлов. Ошибка IBM была в том, что они взяли исходно сложное понятие файла, над которым была сделана абстракция.

Когда человек работает с памятью, он работает с кусочками, т. н. записями. Но что преследовала IBM, когда она хотела спустить информацию о размере записи до уровня диска? Первая ошибка в том, что IBM'овцам казалось, что при наличии точной информации о длине минимизируется количество записей. Второе ошибочное предположение — в минимизации затрат памяти при записи. В действительности, экономия является ложной, так как собственно запись занимала очень маленькое время. Поэтому сейчас всегда пишут постоянными порциями.

Алгоритма всегда 3:

• первый подходящий
• наиболее подходящий
• наименее подходящий

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

За 30 лет так мало изменилось в ФС и ОС.

[править] Два вида представления файлов на уровне пользователя

Список аспектов по распределению памяти: В современных ОС есть два вида представления файлов на уровне пользователя:

1. От IBM, Digital — последовательные файлы с записями постоянного или произвольного размера — ключевые последовательности
2. UNIX — файл как поток байт

IBM — военные организации, банки Digital — корпорации среднего размера

Базовый файл (???)

Набор блоков (???)

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

[править] Две вещи за и против UNIX

(-) Что в UNIX сделано плохо — уровень пользователя доступа к файлу как к последовательности байт является единственным. Но, если вы имеете права root, вы можете работать с диском напрямую, но почему-то этот уровень пользовательского интерфейса не имеет. UNIX не поддерживает структуру B-деревьев, а вручную их реализовать не удастся, т.к. нет явного доступа к блокам.

(+) Единая байтовая реализация файла позволяет реализовывать всё, что бывает объектом с байтовым потоком, как файл, что позволяет добиться полной абстракции. Это большой успех. UNIX не безгрешна, тем не менее, в ней можно выделить десятка полтора достоинств.

[править] Абстрактные типы данных в ОС

Лектор хочет похвалиться — мы делали ОС всё время, пока существовал СССР, и всегда хотелось, чтобы пользователи ОС с такими проблемами не соприкасались, посему решили под влиянием идей Барбары Лисков о полнотипных ЯП (предлагалось для определения новых структур данных, для начала написания программы, использовать этот тип данных, достаточно определить интерфейс — абстрактный тип данных), было понятно, что это то, чего не хватало при работе с файлами, и в одной из ОС была реализована эта вещь в виде настраиваемого модуля.

Три великих женщины-программистки: Барбара Лисков, Партиция Селенджер, Дороти Дененг.

В разных ФС делается оптимизация организации, причем со странными критериями. В хороших ФС распределение делается в предположении, что чтение делается последовательно с начала до конца. Но обычно чтение/запись хаотичны.

Lockload — стиль работы

[править] Требование #2 — Именование

При линейном одноранговом именовании (в едином пространстве имен) довольно быстро наступает путанница независимо от числа пользователей.

При едином адресном пространстве возникает большое количество проблем, поэтому во всех ФС принято иерархическое именование. Оно предполагает, чито любое имя файла состоит из цепочки имён, разделаемых разделителем (/ или \). Более идиотской борьбы, чем между направлением слешей, лектор не видел никогда.

!!! Лектор не любит слово директория, вместо этого использовать слово каталог, справочник

Файловая система по лектору:

1. Логическая коллекция файлов, ФС как структурированный набор файлов
2. Набор программ, которые работают с ФС

Правильнее говорить ФС и системы управления ФС. Но в отличие от БД и СУБД такая терминология плохо прижилась.

!!! БД называть БД, СУБД называть СУБД

Каждое имя в цепочке — имя каталога. Берётся самый первый каталог в цепочке, в нём ищется имя каталога второго уровня, и т. д. Разные ФС отличается одной вещью — имя корневого каталога. В связи этим имеются два понятия, которые имеют один смысл, но интерпретируются по-разному:

• full pathname — путевое имя, начинающееся из корневого каталога
• short path name — относительное путевое имя.

[править] Подходы к выбору корня ФС

Два подхода, и один компромисный для начала полного имени.

1. IBM, DEC, DOS, Windows — Один корень для каждого логического диска. Плюс — единообразная структура каждой отдельной части ФС, и диск представляет собой отдельную изолированную единицу. В этом случае легко извлекается часть файлов. В этом же и минус — в логической структуре именования файлов выползает физические особенности среды, что страшно неудобно.
2. MULTICS (Multiplexed Information System) — кардинально другой подход. имя предопределённого каталога, который является глобальным корнем — «/». В любом каталоге могут стоять имена объектов, которые находятся на разных дисках. Логическая структура накрывает всю физическую структуру. Плюсы: балансировку распределения памяти брала на себя файловая система, а не пользователь. Второе — в случае Multics, ОС сама следила за тем, какие диски должны быть в рабочем состоянии, и какие не используются. Кроме того, система сама могла взять на себя функцию резервного копирования. Это ужасно красивая вещь. Платить приходилось неотключаемостью частей.

Лектор учился на двух ОС – Multics и 

Лектор учился на мехмате

Лектор учился на двух ОС – Multics и мехмате(ЛОЛ)

[править] Синхронизация данных во время полёта Союз-Аполлон

В 1980-х годах при экспериментальном полёте Союз-Аполлон было 3 центра управления полётом — основной и два резервных. И их надо было синхронизировать в реальном времени. Сначала была протянута сеть Х.25, но она не работала. Поэтому в результате был выбран беспроигрышный вариант — солдат на автомобиле, который ездил и возил копии дисков.

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

[править] Компромиссный подход

UNIX: Нужно оставить понятие отдельной ФС, оставить отдельные цепочки имён с корневого каталога. В UNIX это статическая фрагментация + динамическая сборка. Выделяется логический диск, на котором находится корневая ФС. Это некоторое дерево, листьями которого являются файлы или пустыми каталоги, которые называютмся точками монтирования. Сразу после запуска кроме иерархии от корня ничего не видно, но потом можно монтировать ФС. То есть, называть «/» на другом диске как какую-то директорию на нашем.

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

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

В результате остается независимость по распределению памяти, отключению ФС.

Стандартным способом именования файлов в ФС является имя файла — путевое имя, других имён, других объектов, которые сохраняются в ФС, нет.

[править] Требование #3 — Защита

Защита — Обеспечение доступа к файлам тем и только тем, кому это разрешено.

[править] Два подхода к защите доступа

Как это можно обеспечить? Существуют 2 подхода:

1. Мандатный подход — правила прописываются в индивидуальном порядке
2. Дискреционный — когда разбиваются пользователи на группы

[править] Аутентификация и Авторизация

С этим связано два термина:

1. Аутентификация — процедура идентификации пользователя
2. Авторизация — если доступ к файлу производится мандатным образом, то с файлом связан access control list

[править] Мандатный подход

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

Иванову давать доступ только по будням с 9 до 21 часа. Но только в том случае, если
температура на улице не превышает 35 градусов Цельсия, т.к. иначе он начинает дурить

Все это гибко и удобно. Но казалось, что Администрации не было вообще и что насоздавали кучу файлов, которые нельзя ни прочитать, ни изменить, ни удалить. Ещё один минус — неопределённый размер регламента, и сложная структура области с регламентами. Что порождает большие накладные расходы на очень низком уровне. И при каждой попытке доступа по многоуровневым путям, проверку надо делать на каждом уровне в цепочке имен в пути.

[править] Дискреционный подход

В дискреционной системе всё упрощается – пользователи делятся на три группы – владелец, группа и все остальные. И для проверки полномочий требуется 9 бит (по три на чтение, запись и выполнение). Самая короткая программа, которая проверяет права – 11 комманд.

Несколько групп с разными правами хорошо согласуются с иерархией имен.

В ФС единицей защиты является файл. Каталоги также являются файлами.

[править] Требование #4 — Синхронизация

Как происходит сеанс работы с файлами:

open
   read
   write
close

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

• совместный (shared)
  • блокируется при открытии на запись
  • не блокируется при открытии на чтение
• монопольный (exclusive)
  • блокируется при любом открытии

Аналог транзакции в работе с базой данных

open — точка синхронизации

Единицей синхронизации является файл целиком.

Ритчи, Керниган, Томпсон и ещё один начали разрабатывать UNIX после того, как им запретили разрабатывать MULTICS.

[править] Контрпример — как работать с файлами в UNIX

Контрпример: как работать с файлами в UNIX в совместном режиме — программисты должны договориться об имени ещё одного отсутствующего файла, который каждый пытается создать. Если создать не удается, то попытка повторяется через некоторое время. Как только была предпринята попытка добавить синхронизацию, оказалось, что существуют полезные приложения, которые используют совместный доступ без блокировки. В результате в fcntl была добавлена синхронизация, то есть сразу после открытия файла нужно вызвать fcntl, который позволяет осуществить синхронизацию. Дополнительно ввели ещё один уровень синхронизации, в котором дополнительно указывается диапазон байтов, которые можно редактировать — контрпример и иллюстрация к тому, что файлы делаются для того, чобы как меньше смылса грузить на ФС.

Как видно, без совместного доспупа не обойтись:

• Тексты программ — Только текстовые редакторы и компиляторы должны знать, как выглядит файл изнутри.
• Объектные модули — компиляторы, редакторы связей (ld — link editor)
• Исполняемые файлы — редактор связей, загрузчик

Примеры правильного использования ФС. ФС не знает о структуре файла, о ней знают только работающие с ними приложения, и это классно.

[править] Мысль

Лектору пришло в голову: есть одна область — Системы Автоматического Проектирования, в которой опять же, он много лет знаком с людьми, которые ноют, что у них бывает очень много структур данных, которые возникают во время создания проекта, и они просят что-нибудь для облегчения жизни, и ни один тип БД их не устраивает. И может быть не просто так все САП сделаны на файлах, потому как по-другому и нельзя. Они не могут её чётко выразить, чтобы её поддерживала программа, и они слишком часто её корежат.

[править] Где не хватает ФС

Информациооная система - система, ориентированная на хранение, выбор и модификацию данных определённой прикладной области. Обычно структурно это таблицы, состоящие из записей, состоящие из полей.

Чтобы какое-то приложение могло работать с файлом, оно должно знать её структуру. Есть 2 возможных варианта:

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

Сколько есть контор, столько возникает информационных систем. Так что второй вариант лучше.

[править] Пример простой ИС

Возьмём простенькую ИС, которая занимается учетом служащих. Что она должна делать:

• Выдавать списки по отделу
  • Руководитель
  • Численность
  • Зарплата
• Обеспечивать
  • Перевод из одного отдела в другой
  • Наем новых сотрудников
  • Увольнение старых сотрудников
• Оперировать данными служащих
  • Уметь находить номер удостоверения по полному имени
  • Уметь находить полное имя по номеру
  • Уметь находить информацию о текущей должности
  • Уметь находить информацию о зарплате

Как эту систему можно делать: Служащие

• Слу_Имя — полное имя (уникальный индекс)
• Слу_Номер — номер удостоверения (уникальный индекс)
• Слу_Стат — статус (неуникальный индекс)
• Слу_Зарп — зарплата (неуникальный индекс)
• Слу_Отд_Номер — номер отдела (неуникальный индекс)
• Слу_Отд_Рук — имя руководителя (неуникальный индекс)

Проблема с управлением отделов. Решение: Служащие

• Слу_Имя — полное имя (уникальный индекс)
• Слу_Номер — номер удостоверения (уникальный индекс)
• Слу_Стат — статус (неуникальный индекс)
• Слу_Зарп — зарплата (неуникальный индекс)
• Слу_Отд_Номер — номер отдела (неуникальный индекс)

Отделы

• Отд_Ном — номер отдела (уникальный индекс)
• Отд_Рук — руководитель отдела (уникальный индекс)
• Отд_Числ — количество служащих в отделе (неуникальный индекс)
• Отд_Сотр_Зарп — общая зарпалата в отделе (неуникальный индекс)
• Отд_Ср_Зп — средняя зарплата в отделе (неуникальный индекс)

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

• Для любого Слу_Отд_Номер должен существовать Отдел, у которого Отд_Ном с тем же значением
• Для любого Отд_Рук должен существовать Слу_Имя с тем же значением, в том же отделе, и со Слу_Стат равным начальнику отдела
• Для всех Отделов Отд_Числ должна равняться количеству Служащих, у которых Слу_Отд_Номер=Отд_Ном
• Для всех Отделов Отд_Ср_Зп должна равняться сумме Слу_Зарп для Служащих, у которых Слу_Отд_Номер=Отд_Ном, поделенной на Отд_Числ

Consistency — согласованное состояние БД.

Integrity — целостностное состояние БД.

Если есть набор файлов, который содержит данные, связанные ограничениями целостности, то вне зависимости от того, какая программа с ними работает, это уже БД.

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