ОС, базы данных и распределённые системы: память, журнал, изоляция, сериализуемость, индексы, зависимости и планы запросов. Задачи и проверка конфликтов.
Запись значения 2 завершилась до начала чтения, а чтение вернуло прежнюю 1. Для линейризуемого регистра без других записей такая история недопустима. Но чтение, пересекающееся с незавершённой записью, может допускать несколько последовательных объяснений.
Темы направления рассматривают истории операций, конфликты транзакций, снимки и границы распределённых гарантий. Сначала задайте объект и модель отказов. Слова «согласованность» и «доступность» без определения операций, ответа и допустимых историй не дают проверяемого утверждения.
Основные идеи
Линеаризуемость истории
Каждая завершённая операция должна допускать точку действия между вызовом и ответом. Последовательное объяснение сохраняет порядок непересекающихся операций и спецификацию объекта.
Если запись 2 завершилась до вызова чтения, позднее чтение регистра не может вернуть 1 без другой объясняющей записи.
Конфликтный граф транзакций
Для обычной проверки конфликтной сериализуемости вершины — транзакции, а ребро фиксирует порядок конфликтующих операций над одним объектом данных, если хотя бы одна является записью. Цикл запрещает эквивалентное последовательное расписание по этому критерию.
Порядки T1→T2 по x и T2→T1 по y образуют цикл, даже если каждая отдельная строка имеет допустимую версию.
Снимок и инвариант
Согласованный снимок предоставляет определённую версию чтений. Он сам по себе не гарантирует сохранение ограничения, связывающего разные записи, при конкурентных изменениях.
Две транзакции могут каждая увидеть двух дежурных и снять с дежурства разных людей. Непересекающиеся записи не защищают условие «хотя бы один остаётся».
Операционные системы
Процесс, поток и системный вызов: три разные границы
Разбираем общий счётчик, отдельную память дочернего процесса и переход в ядро без обязательного переключения задачи.
Перед началом: Адрес переменной и стек вызовов; Пошаговое исполнение программы; Чтение и запись общей памяти.
Одинаковый код не означает одинаковое состояние
Два запуска одной программы могут исполнять одинаковые инструкции, но иметь разные значения глобальной переменной. Процесс задаёт адресное пространство и набор управляемых ядром ресурсов. Поток задаёт отдельную последовательность исполнения внутри процесса: у него свои регистры, указатель текущей инструкции и стек. В многопоточном процессе глобальные данные и куча обычно общие, поэтому ошибка одного потока способна повредить работу остальных.
Наличие отдельного стека не превращает его память в автоматически недоступную другим потокам. Если передать указатель на действующий локальный объект, другой поток может обратиться к нему в пределах правил языка. После окончания времени жизни объекта тот же указатель становится опасным. Различайте организацию стека, права доступа адресного пространства и время жизни переменной: это три самостоятельных свойства.
Общая память требует протокола обновления
Даже атомарные чтение и запись не делают атомарным составное действие «прочитать, прибавить, записать». Два потока могут прочитать старое число до первой записи, а затем сохранить одинаковый результат. Для точного подсчёта используют атомарное увеличение либо блокировку вокруг всей операции. Защита только записи оставляет окно между чтением и изменением общего состояния.
В примере ниже сама ячейка атомарна, а увеличение состоит из отдельных последовательных чтения и записи. Поэтому потеря обновления является определённым поведением нашей модели. Нельзя без оговорки переносить эту трассу на обычную переменную языка C с гонкой данных: там программа может иметь неопределённое поведение, а не только один из удобных вариантов чередования инструкций.
Вход в ядро не равен смене процесса
Системный вызов передаёт управление привилегированному коду через предусмотренный архитектурой механизм. Ядро проверяет номер операции, аргументы, права и пользовательские адреса. Оно не обязано создавать новый процесс или немедленно запускать другой поток. Короткий запрос может выполниться и вернуть управление тому же вызывающему потоку, сохранив его процесс и адресное пространство.
Переключение режима означает переход между пользовательским и привилегированным исполнением. Переключение контекста означает сохранение состояния одной исполняемой задачи и восстановление другой. Эти события могут совпасть, например при ожидании ввода, но не тождественны. И наоборот, таймер способен привести к планированию без добровольного системного вызова программы. Подсчёт вызовов сам по себе не даёт числа переключений.
Изоляция процесса и совместное владение ресурсом
В Unix-подобной модели fork создаёт дочерний процесс с логически отдельной памятью. Копирование при записи позволяет сначала разделять физические страницы, сохраняя нужную изоляцию при последующих изменениях. Поэтому одинаковый виртуальный адрес переменной у родителя и ребёнка не означает одну изменяемую ячейку. В нашей трассе копирование выполняется после завершения двух потоков, чтобы не добавлять ограничения многопоточного fork.
Ресурсы при создании процесса копируются не одинаково: некоторые ссылки могут вести к совместным объектам ядра. Открытые файлы и каналы требуют собственной модели владения. Поток также не получает автоматически независимую таблицу файловых дескрипторов. Для диагностики сначала перечислите, что общее, затем выделите частное состояние каждого участника и только после этого стройте возможные исполнения.
Одно потерянное обновление и одна независимая копия
Условие. У процесса атомарная ячейка g=10. Два потока увеличивают её отдельными load/store: сначала читают оба, затем записывают оба. После их завершения выполняется fork. Ребёнок меняет свою g на 99.
Первый поток читает 10 и вычисляет локальное 11.
Второй поток тоже успевает прочитать 10 и вычисляет 11.
Обе атомарные записи сохраняют 11: два составных увеличения дали только одно изменение значения.
После fork оба процесса логически имеют g=11; запись ребёнком 99 изменяет его копию, родитель сохраняет 11.
Ответ. Перед fork g=11; после записи ребёнка: у родителя 11, у ребёнка 99.
Проверка. Если заменить составные увеличения двумя атомарными fetch_add(1), исходный процесс получит 12. Это изменение протокола, а не следствие появления ещё одного стека.
Где легко ошибиться. Нельзя объяснять любую параллельную ошибку переключением процессов: общая память потоков, граница привилегий и планирование требуют отдельных проверок.
Проверьте понимание
Вопросы к этой главе
Системный вызов обязательно блокирует поток?
Нет. Он может завершиться сразу. Блокировка зависит от операции и готовности ресурса; при ней ядро может передать процессор другой задаче.
Отдельный стек гарантирует отсутствие гонок?
Нет. Потоки разделяют другие области памяти, а указатель на объект стека может быть передан соседнему потоку. Нужны правила доступа и времени жизни.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Первичная документация общих и отдельных свойств POSIX-потоков; соглашения других ОС могут отличаться.
Виртуальная память: адрес, перевод и право доступа
Вычисляем физический адрес, а затем отдельно проверяем, разрешена ли операция с найденной страницей.
Перед началом: Двоичная и шестнадцатеричная запись; Деление с остатком; Различие адреса и хранимого значения.
Найденный кадр ещё не разрешает запись
Адрес 0x5ABC при страницах по 4096 байт разбивается на номер страницы 5 и смещение 0xABC. Пусть таблица переводит страницу 5 в физический кадр 0x27. Физический адрес тогда равен 0x27ABC. Но если страница доступна только для чтения, запись по ней всё равно запрещена. Наличие физической памяти и право изменить её содержимое являются независимыми условиями.
Процесс формирует виртуальные адреса, а оборудование переводит их с использованием настроенных ядром структур. Одинаковые виртуальные числа в разных процессах могут обозначать разные физические кадры. И наоборот, общая библиотека или разделяемая область могут отображать один кадр в несколько адресных пространств. Само сравнение виртуальных чисел без указания процесса почти ничего не говорит о совместном использовании памяти.
Смещение сохраняется, номер страницы заменяется
Для размера страницы P адрес представляют как VPN·P+offset, где offset находится между нулём и P−1. После поиска разрешённого отображения получают PFN·P+offset. При размере, равном степени двойки, смещение удобно выделять младшими битами. Оно не переводится заново: обозначает один и тот же байт внутри выбранной виртуальной страницы и соответствующего физического кадра.
Одна большая таблица полезна для первого расчёта, но расходует место даже на неиспользуемые участки. Многоуровневая структура позволяет не создавать нижние таблицы для отсутствующих диапазонов. Реальные архитектуры определяют собственное разбиение адреса, размеры страниц и допустимые комбинации флагов. Наш пример использует абстрактную страницу размером четыре килобайта и не является полной схемой конкретной архитектуры.
Различайте отсутствие отображения и нарушение защиты
Если перевод отсутствует или страница не находится в оперативной памяти, обращение может вызвать исключение. Ядро сопоставляет адрес с политикой процесса: допустимое ленивое выделение, подкачка и незаконное обращение требуют разных действий. Не каждое исключение заканчивается завершением программы. Но и не каждое означает, что достаточно добавить память: произвольный адрес вне разрешённой области автоматически допустимым не становится.
При существующем переводе проверяются права чтения, записи, исполнения и доступа из пользовательского режима. Запись в защищённую страницу может участвовать в реализации копирования при записи, если это предусмотрено ядром. Для обычной неизменяемой страницы тот же вид нарушения не даёт программе права продолжить. Причину определяет состояние отображения и политика системы, а не только факт возникновения ловушки.
Кеш переводов требует согласованности
Чтобы не обходить таблицы при каждом обращении, процессор кеширует переводы в TLB. Это кеш отображений и прав доступа, а не содержимого пользовательских переменных. Попадание в него уменьшает стоимость перевода, но не отменяет проверку разрешений. Промах TLB и отсутствие страницы — разные события: таблица может содержать корректное отображение даже при пустом кеше переводов.
После изменения таблицы старый кешированный перевод может стать опасным. Ядро использует предусмотренные архитектурой способы инвалидировать записи, в том числе на других ядрах, где исполнялся процесс. Аналогично, освобождённый кадр нельзя преждевременно отдать другому владельцу, пока сохраняется доступ через старое отображение. Виртуальная память поэтому объединяет арифметику адресов, защиту и протокол обновления общих аппаратных структур.
Чтение и запись одного адреса дают разные результаты
Условие. P=4096. Виртуальная страница 5 отображена в кадр 0x27 с разрешённым пользовательским чтением и запрещённой записью. Перевода страницы 7 нет. Рассмотреть адреса 0x5ABC и 0x7ABC.
Деление 0x5ABC на 4096 даёт VPN=5 и offset=0xABC=2748.
Подстановка кадра даёт PA=0x27·4096+2748=162492=0x27ABC.
Чтение по 0x5ABC разрешено; запись вызывает нарушение защиты, хотя кадр найден.
У 0x7ABC тот же offset, но VPN=7 без отображения. Решение о восстановлении доступа принимает ядро по политике области.
Ответ. Для разрешённого чтения PA=0x27ABC. Запись защищена; второй адрес требует обработки отсутствующего перевода.
Проверка. И виртуальный, и физический адреса первого обращения имеют остаток 2748 при делении на 4096. Из совпадения смещений не следует совпадение страниц.
Где легко ошибиться. Успешно вычисленный физический адрес не доказывает законность доступа. Отдельно проверяются отображение, права, режим исполнения и актуальность кеша переводов.
Проверьте понимание
Вопросы к этой главе
Промах TLB обязательно требует чтения с диска?
Нет. Может понадобиться только обход уже находящихся в памяти таблиц. Обращение к диску связано с отсутствием нужных данных в оперативной памяти, а не с каждым промахом TLB.
Почему нельзя просто запоминать физический адрес указателя?
Отображение может измениться. Пользовательская программа работает в согласованной виртуальной модели; физический кадр относится к текущему состоянию управления памятью.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверка разбиения адреса, сохранения смещения и прав в записи таблицы страниц. Адреса и флаги примера выбраны отдельно.
FIFO, LRU и OPT: промахи и аномалия увеличения памяти
Сравниваем политики на собственной трассе и проверяем, почему дополнительный кадр не всегда помогает FIFO.
Перед началом: Очередь и множество; Пошаговая трассировка алгоритма; Нумерация обращений.
Счётчик зависит от политики, а не только от набора страниц
Для одной и той же последовательности FIFO может получить одиннадцать промахов с тремя кадрами и двенадцать с четырьмя. Дополнительная память изменила порядок вытеснений, а не просто добавила запасное место. Чтобы воспроизвести такой результат, нужно фиксировать всю трассу, исходно пустую память и правила обновления состояния при попадании. Одного количества различных страниц недостаточно для сравнения.
В учебной модели каждый номер обозначает страницу одинакового размера. Попадание означает, что она уже резидентна; промах требует загрузки. Пока есть свободный кадр, жертва не выбирается. Модель считает события, а не время: запись грязной страницы, задержка накопителя и предварительная загрузка здесь отсутствуют. Поэтому меньшее число промахов не является универсальным обещанием меньшего времени реальной программы.
Три разных ответа на вопрос о жертве
FIFO удаляет страницу, которая дольше всего находится в памяти после загрузки. Повторное обращение не переставляет её в конец очереди. LRU удаляет страницу, к которой дольше всего не обращались; каждое попадание меняет информацию о давности. Перепутать эти обновления означает реализовать другую политику, даже если список кадров на экране выглядит правдоподобно.
OPT выбирает страницу, следующее обращение к которой дальше всего в будущем. Если страница больше не потребуется, её можно рассматривать как бесконечно далёкую. Полное будущее рабочая ОС обычно не знает, поэтому OPT используется как нижняя граница числа промахов для данной трассы. Несколько равноценных жертв могут дать разные промежуточные наборы кадров при одинаковом оптимальном счётчике.
Больше кадров и свойство вложенности
Аномалия Белади — увеличение числа промахов при добавлении кадров для некоторых политик. FIFO ей подвержена. У LRU при согласованных исходных состояниях есть свойство стека: резидентный набор меньшей ёмкости вложен в набор большей. Поэтому попадание маленького кеша остаётся попаданием большого, и увеличение ёмкости не увеличивает число промахов.
Это свойство не утверждает, что LRU на каждой трассе лучше FIFO. На нашем примере при трёх кадрах LRU получает четырнадцать промахов против одиннадцати у FIFO. Сравнение разных политик и сравнение разных ёмкостей одной политики — разные утверждения. Контрпример к одному не опровергает другое. Именно такое различение защищает от вывода по одному удачному прогону.
Как построить проверяемую трассу
На каждом шаге запишите номер обращения, страницу, попадание или промах, выбранную жертву и состояние политики после обновления. Для FIFO полезнее очередь загрузки, чем просто отсортированное множество кадров. Для LRU нужен порядок недавних обращений. При проверке OPT можно независимо перебрать возможные вытеснения на короткой трассе и сравнить минимальное достижимое число промахов.
В лаборатории задаются от одного до восьми кадров и не более шестидесяти обращений к страницам от нуля до девяноста девяти. Это границы демонстрации, а не ограничения теории. Чтобы проверить аномалию, сохраните трассу и измените только число кадров. Чтобы сравнить политики, сохраните и число кадров. Иначе причины изменения результата окажутся смешаны.
Отдельно сгенерированный контрпример для FIFO
Условие. Пустая память. Обращения: 0,4,3,5,3,2,3,4,2,5,3,0,3,4,3,5,1,0,4. Сравнить три и четыре кадра.
FIFO с тремя кадрами даёт промахи на шагах 1,2,3,4,6,8,11,12,16,17,19: всего 11.
FIFO с четырьмя кадрами даёт промахи на шагах 1,2,3,4,6,12,14,15,16,17,18,19: всего 12.
LRU на той же трассе даёт 14 промахов с тремя кадрами и 10 с четырьмя.
OPT даёт соответственно 9 и 7; эти числа можно проверить независимым перебором будущих состояний.
Проверка. Нумерация шагов начинается с единицы. Счётчик OPT не больше счётчика любой сравниваемой политики при той же ёмкости, но LRU при трёх кадрах здесь проигрывает FIFO.
Где легко ошибиться. Попадание не переставляет элемент FIFO. Если обновлять очередь на каждом обращении, сравнение перестаёт проверять заявленный алгоритм.
Сравнить FIFO, LRU и OPT на одной трассе
От 1 до 8 кадров, до 60 обращений к страницам 0–99. Начальная память пуста. Попадание и промах относятся к учебному кэшу страниц; дисковое время, TLB и реальные политики ядра здесь не моделируются. OPT использует будущие обращения как нижнюю границу числа промахов.
Проверьте понимание
Вопросы к этой главе
Страница с номером ноль считается пустым кадром?
Нет. Ноль — обычный допустимый номер страницы. Пустоту нужно представлять отдельным состоянием, иначе обращения к нулю будут посчитаны неверно.
OPT можно использовать как прогноз реальной ОС?
Только как идеализированную границу для известной полной трассы. Его выбор использует будущие обращения, недоступные обычной онлайн-политике.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверка определений FIFO/LRU/OPT, аномалии и свойства стека. Рабочая трасса получена отдельно и проверена независимым оптимизационным перебором.
Блокировки и взаимная блокировка: доказательство по графу ожидания
На трёх блокировках отделяем защиту данных от гарантии продвижения и проверяем глобальный порядок захвата.
Перед началом: Критическая секция; Ориентированный цикл; Инвариант структуры данных.
Защищённые данные могут оказаться недоступными навсегда
Три потока могут аккуратно защищать каждую структуру отдельным мьютексом и всё же остановить друг друга. Первый держит блокировку 101 и ждёт 205, второй держит 205 и ждёт 309, третий держит 309 и ждёт 101. Нарушения взаимного исключения нет: никто не вошёл в чужую секцию. Нарушено продвижение, потому что каждый ожидает действия другого участника цикла.
Блокировка обеспечивает протокол доступа к состоянию, а не автоматическую корректность всей программы. Нужно определить, какой инвариант защищает мьютекс, кто вправе его освобождать и можно ли ждать другой ресурс, удерживая текущий. Формулировка «добавим ещё один lock» без этих ответов способна заменить гонку данных взаимной блокировкой. Отсутствие гонок и отсутствие зависания проверяются разными рассуждениями.
Четыре условия описывают возможный тупик
Классическая ситуация объединяет взаимное исключение, удержание ресурса во время ожидания другого, отсутствие принудительного изъятия и циклическое ожидание. Убрав хотя бы одно необходимое условие в выбранной модели, можно предотвратить такой тупик. Но обнаружение этих условий по отдельности ещё не доказывает, что конкретное исполнение уже заблокировано. Для диагностики нужна фактическая зависимость участников.
В графе ожидания вершины обозначают потоки, а ребро указывает владельца ресурса, которого ждут. Для эксклюзивных блокировок с единственным владельцем замкнутый цикл заблокированных ожиданий даёт понятное свидетельство. При ресурсах с несколькими экземплярами одного такого рисунка может быть недостаточно. Поэтому сначала фиксируют модель ресурса, затем применяют критерий, а не переносят вывод с двух мьютексов на любую систему очередей.
Глобальный порядок исключает цикл
Назначим всем блокировкам общий строгий порядок и разрешим захватывать их только по возрастанию. Тогда каждый переход ожидания при удержании ранее захваченного ресурса должен продвигаться к большему рангу. Вернуться к исходному меньшему рангу по замкнутому циклу невозможно. Это доказательство работает для всех участвующих путей исполнения, если они действительно соблюдают одну и ту же дисциплину.
Порядок необходимо учитывать и в вызываемых функциях. Функция, незаметно захватывающая меньший мьютекс при удержании большего вызывающим кодом, ломает общее обоснование. Для динамического набора объектов сначала собирают нужные ресурсы, устраняют повторы и сортируют их по согласованному ключу. Освобождение в обратном порядке упрощает структуру кода, хотя основной запрет цикла относится именно к захватам.
Тайм-аут не восстанавливает инвариант сам
Отказ от ожидания по тайм-ауту помогает обнаружить проблему, но не даёт права оставить частично изменённые данные. Нужен предусмотренный откат или доведение операции до согласованного состояния. Повторные попытки тоже могут мешать друг другу: потоки освобождают и снова захватывают ресурсы, выполняют работу, но не завершают запрос. Такое активное отсутствие прогресса отличается от неподвижного цикла ожидания.
Даже корректный порядок блокировок не обещает справедливость планирования. Один участник может долго не получать ресурс из-за более удачливых конкурентов. И наоборот, повышение приоритета владельца помогает при инверсии приоритетов, но не разрывает логический цикл из трёх владельцев. В отчёте о зависании перечислите владельцев, ожидаемые ресурсы и места захвата: слово «deadlock» должно сопровождаться проверяемым свидетельством.
Замыкаем и затем запрещаем цикл
Условие. Эксклюзивные мьютексы 101,205,309. P удерживает 101, Q удерживает 205, R удерживает 309. Далее P просит 205, Q просит 309, R просит 101.
Запрос P создаёт ожидание P→Q.
Запрос Q создаёт ожидание Q→R.
Запрос R создаёт ожидание R→P: все трое заблокированы и не освобождают удерживаемые мьютексы.
При порядке 101<205<309 запрос R к 101 после захвата 309 запрещён протоколом. Ресурсы нужно захватывать в общем порядке с начала операции.
Ответ. В исходной трассе цикл P→Q→R→P. Общий возрастающий порядок исключает такой цикл при соблюдении всеми участниками.
Проверка. В цикле пришлось бы одновременно требовать 101<205<309<101. Строгий порядок этого не допускает; один только порядок в двух из трёх потоков не достаточен.
Где легко ошибиться. Принудительно освободить чужой мьютекс — не универсальное исправление. Владелец мог остановиться посреди изменения защищаемого состояния.
Проверьте понимание
Вопросы к этой главе
Один мьютекс всегда безопасен?
Не обязательно. Повторный захват нерекурсивного мьютекса тем же потоком может заблокировать его. Ожидание завершения другого потока под этим мьютексом тоже требует проверки зависимостей.
Почему фиксированный порядок не гарантирует быструю работу?
Он исключает определённые циклы, но не ограничивает длительность секций, нагрузку, очереди или справедливость планировщика. Безопасность и задержка — разные свойства.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверка условий взаимной блокировки и предотвращения циклического ожидания. Трёхсторонняя трасса и ранги заданы отдельно.
Файловая система после сбоя: журнал и граница зафиксированного изменения
Проверяем атомарную перестановку двух имён и выясняем, почему наличие записи в кеше ещё не означает восстановимость после сбоя.
Перед началом: Файл, каталог и inode; Энергозависимая память; Порядок записи и инвариант.
Два правильных изменения могут дать неправильный промежуток
В двух каталогах находятся имена a/report и b/archive, указывающие на разные файлы. Хотим атомарно поменять соответствия местами. Если сначала записать один каталоговый блок и потерять питание перед вторым, оба имени временно могут указывать на один файл, а другой потеряет имя. Каждая отдельная запись была осмысленной, но совместный инвариант оказался нарушен.
Это учебная транзакция файловой системы, а не обещание, что два обычных вызова rename образуют одну атомарную операцию. Рассматриваем соответствия имён уже существующих обычных файлов; данные файлов не меняются. Реальная реализация дополнительно учитывает свои метаданные. Говорим об атомарности после восстановления; изоляция от параллельных наблюдателей требует отдельного протокола. Чтобы рассуждение было проверяемым, сначала зададим старое и новое состояния и допустимую модель долговременной записи.
Журнал хранит возможность закончить операцию
В модели redo-журнала сначала сохраняются новые образы изменяемых блоков и описание транзакции. Только после их долговременной записи разрешается сохранять запись commit. До commit рабочие места блоков не изменяются. Иначе незавершённая операция могла бы испортить старое состояние, а одних новых образов было бы недостаточно для отката. Это существенная часть выбранного протокола.
После долговременного commit транзакция считается зафиксированной: восстановление имеет право повторить все её изменения. Перенос образов из журнала на обычные места называется checkpoint. Сбой во время этого переноса оставляет смесь старых и новых блоков, но полный зафиксированный журнал позволяет закончить работу. Повторная установка одного и того же образа идемпотентна: она не должна второй раз увеличивать счётчик или повторять внешнее действие.
Порядок обязан переживать кеши устройства
Порядок вызовов записи в программе не всегда совпадает с порядком, в котором данные переживут потерю питания. Протокол использует предусмотренные системой средства ожидания и упорядочения устойчивой записи. Нельзя считать commit надёжным, если соответствующие ему образы ещё могут исчезнуть. Также нужен способ распознать неполную или повреждённую запись журнала: одной красивой строки с номером транзакции недостаточно.
Освобождать место журнала разрешается после устойчивого завершения checkpoint. Если удалить единственную копию описания раньше, следующий сбой может оставить недовосстановимое состояние. Конкретные барьеры, атомарные единицы записи и проверки целостности зависят от файловой системы и устройства. Наш пример предполагает распознаваемый полный commit и соблюдённый порядок; не переносите доказательство на железо, которое этим предположениям не отвечает.
Согласованность метаданных отличается от сохранности данных
Журналирование только метаданных уменьшает объём повторных записей, но не обещает сохранить новое содержимое файла при любой точке сбоя. Файл может быть структурно корректным и содержать более старые данные. Для полного результата нужно отдельно определить гарантии записи содержимого, обновления имён и подтверждения операции приложению. Проверка структуры каталогов не заменяет проверку нужной версии документа.
В прикладном протоколе полезно спрашивать: что считается подтверждением пользователю, какие блоки к этому моменту устойчивы и что восстановление выберет после каждой возможной остановки? Набор таких точек сбоя можно перебрать в маленькой модели. Это не испытание реального диска, зато оно выявляет логические ошибки порядка до дорогостоящих тестов с аварийным отключением. Начните с инварианта, затем проверяйте каждый переход, который делает его временно невидимым.
Перестановка двух имён через полный redo-журнал
Условие. Старое состояние: a/report→inode11, b/archive→inode23. Новое должно быть a/report→23, b/archive→11. Два соответствия находятся в разных блоках каталогов; прочие метаданные в модели опущены.
Записываем в журнал оба новых образа каталоговых блоков и ждём их устойчивости.
Устойчиво записываем полный commit. Теперь оба образа доступны восстановлению.
При checkpoint изменяем только a/report→23 и моделируем сбой до записи второго блока.
Восстановление повторяет оба образа: a/report→23, b/archive→11. Повторное восстановление оставляет то же состояние.
Ответ. После commit сбой приводит к полностью новому состоянию. До commit, при запрете ранней записи рабочих блоков, сохраняется старое.
Проверка. В обоих завершённых состояниях inode11 и inode23 имеют ровно по одному имени. Промежуточные два имени inode23 исправляются журналом; это не новое допустимое состояние.
Где легко ошибиться. Возврат из обычной операции записи, структурная целостность и долговременная сохранность нужной версии данных не являются одним и тем же обещанием.
Проверьте понимание
Вопросы к этой главе
Почему повторная запись образа безопаснее команды «прибавить один»?
Установка окончательного образа идемпотентна. Повторное выполнение приращения могло бы изменить значение дважды и потребовало бы дополнительного протокола.
Любая файловая система с журналом даёт полную сохранность содержимого?
Нет. Важны режим журналирования, порядок данных и метаданных, подтверждение операции и гарантии устройства. Название механизма не заменяет эти условия.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверка write-ahead порядка, commit, checkpoint и различия режимов журналирования. Задача перестановки двух имён и её точки сбоя составлены отдельно.
Базы данных
Изоляция транзакций: стабильный снимок может нарушить общий лимит
Проверяем ограничение на две строки и различаем повторяемое чтение, конфликт записей и сериализуемое исполнение.
Перед началом: Транзакция и commit; Чтение и изменение строки; Инвариант над несколькими значениями.
Две успешные проверки дают несовместимый результат
В двух строках хранится занятая ёмкость a=4 и b=4. Правило допускает суммарно не больше десяти единиц. Первая транзакция хочет добавить две единицы к a, вторая — к b. Каждая видит сумму восемь, проверяет будущее значение десять и разрешает собственную запись. Если обе используют один старый снимок и меняют разные строки, итоговая сумма может стать двенадцать.
Такое отклонение возникает без чтения незавершённых данных и без перезаписи одной строки двумя участниками. Проверка только совпадения записываемых ключей его пропустит. Общий бизнес-инвариант связывает несколько объектов, а каждая отдельная запись выглядит допустимой. Для диагностики нужно восстановить, какие версии были прочитаны, какое решение из них следовало и какие изменения действительно зафиксировались.
Название уровня не заменяет модель видимости
При чтении подтверждённых данных отдельные запросы одной транзакции могут увидеть разные зафиксированные состояния. Повторяемое чтение обещает более стабильную картину, но точные гарантии зависят от системы. В PostgreSQL уровень Repeatable Read использует снимок и предотвращает фантомное чтение, хотя стандартная таблица допускает его для такого названия. При этом сериализационные аномалии всё ещё возможны.
Фантом относится к изменившемуся результату предикатного запроса, например появлению новой строки в выбранном диапазоне. Неповторяемое чтение относится к изменению уже прочитанного объекта. Эти признаки полезны, но их отсутствие само по себе не доказывает эквивалентность последовательному запуску. Рассматривайте обещание уровня целиком, а не как набор удобных флажков, автоматически покрывающих любое ограничение приложения.
Сериализуемость относится ко всему набору решений
Если выполнить наш пример последовательно, первый участник доведёт сумму до десяти. Второй увидит новое состояние и откажется добавлять ещё две единицы. Следовательно, результат двенадцать не соответствует ни одному такому последовательному исполнению с повторной проверкой правила. Это проверяемое свидетельство аномалии, даже если индивидуальные снимки выглядели внутренне согласованными.
Сериализуемая реализация может обнаруживать опасные зависимости и отклонять одну транзакцию. Приложение должно уметь повторить её целиком: заново прочитать состояние, принять решение и выполнить записи. Повтор только последнего SQL-оператора способен использовать уже устаревший вывод. Внешнее письмо или платёж нельзя бездумно повторять вместе с транзакцией; связь с внешними эффектами требует собственного идемпотентного протокола.
Выбирайте защиту по инварианту
Один способ — явно сериализовать проверку и обновление через общий объект блокировки. Другой — выразить нужное ограничение так, чтобы система надёжно проверяла его при конкуренции. Выбор зависит от возможностей конкретной СУБД, диапазона предиката и нагрузки. Блокировка только изменяемой строки может оказаться слишком узкой: две разные записи тогда по-прежнему разрешат несовместимые решения.
В учебной проверке задайте начальное состояние и все допустимые последовательные результаты. Затем сравните с конкурентным выполнением и укажите использованную модель изоляции. Успешный commit является фактом фиксации по правилам системы, но не самостоятельным доказательством любого бизнес-условия. Наконец, отсутствие ошибки на одном тестовом запуске ничего не говорит о другом допустимом чередовании тех же транзакций.
Резервирование двух единиц в разных строках
Условие. Начально a=b=4. Каждая транзакция добавляет 2 к своей строке, только если прочитанная сумма плюс 2 не превышает 10. Обе читают один снимок.
T1 читает (4,4), проверяет 4+4+2=10 и планирует a=6.
T2 читает тот же снимок, проверяет 10 и планирует b=6.
При модели снимка без конфликта этих разных записей обе фиксируются: получается (6,6).
При любом последовательном порядке вторая проверка видит сумму 10 и отклоняет добавление. Итоговая сумма тогда 10.
Ответ. Конкурентный итог 12 нарушает лимит и не совпадает с последовательным результатом этих решений.
Проверка. Последовательные конечные пары — (6,4) или (4,6). Пересечение записываемых строк пусто, поэтому одна проверка write-write конфликтов не обнаруживает проблему.
Где легко ошибиться. Стабильный снимок гарантирует согласованность прочитанной версии, но сам по себе не сериализует решения, основанные на общих предикатах.
Проверьте понимание
Вопросы к этой главе
Достаточно повторить чтение перед записью?
В стабильном снимке оно может вернуть ту же версию. Нужен протокол, который защищает проверяемый инвариант при конкуренции, а не просто ещё один одинаковый запрос.
Ошибка сериализации означает повреждение базы?
Обычно это отказ опасному конкурентному исполнению. Корректное приложение повторяет всю транзакцию по правилам СУБД и заново принимает решение.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверены гарантии уровней и необходимость повторов после serialization failure; наблюдалась документация версии 18. Задача общего лимита составлена отдельно.
Конфликтная сериализуемость: ребро должно иметь пару операций
Строим граф из порядка чтений и записей, предъявляем цикл и проверяем исправленный ациклический вариант.
Перед началом: Ориентированный граф; Топологическая сортировка; Порядок операций внутри транзакции.
Последовательный порядок определяется зависимостями
Расписание R1:x W2:x R2:y W3:y R3:z W1:z требует одновременно поставить первую транзакцию перед второй, вторую перед третьей и третью перед первой. Каждое требование имеет конкретную причину: более раннее чтение пересекается с поздней записью другого участника в тот же объект. Список требований нельзя удовлетворить одним последовательным порядком. Это уже свидетельство, которое можно проверить независимо от картинки.
Конфликт образуют операции разных транзакций над одним логическим объектом, если хотя бы одна является записью. Два чтения между собой не конфликтуют. Две операции одной транзакции сохраняют внутренний порядок, но не создают ребро к самой себе в графе между участниками. Здесь x,y,z — объявленная гранулярность объектов; замена строки на целую таблицу изменит набор конфликтов.
Постройте граф и сохраните доказательства рёбер
Вершина соответствует транзакции. Для каждой подходящей пары позиций i<j добавляем ребро от владельца ранней операции к владельцу поздней. Несколько пар могут объяснять одно ребро: граф удобно хранить без повторов, а свидетельства — отдельно. Это позволяет показать пользователю, какой объект и какой порядок породили зависимость, вместо необъяснимого сообщения о неправильном расписании.
Расписание конфликтно сериализуемо тогда и только тогда, когда такой граф ацикличен. Любая топологическая сортировка даёт допустимый последовательный порядок для сохранения всех конфликтующих пар. При нескольких доступных вершинах возможны разные порядки. Вывод одного найденного порядка не доказывает его единственность, а произвольная сортировка номеров транзакций не заменяет проверку рёбер.
Цикл не означает ожидание ресурсов во время работы
Граф описывает логические ограничения уже заданного порядка операций. Цикл означает невозможность сохранить эти конфликты при последовательном переставлении транзакций. Все перечисленные операции могли успеть выполниться: это не обязательно граф заблокированных потоков и не диагноз взаимной блокировки. Одинаковая форма стрелок в двух задачах не делает их вершины, рёбра и выводы взаимозаменяемыми.
Конфликтная эквивалентность требует того же набора операций и сохранения порядка каждой конфликтующей пары. Она является конкретным, эффективно проверяемым критерием. Более общие понятия эквивалентности могут допускать другие случаи. Поэтому отрицательный результат анализатора относится к конфликтной сериализуемости, а не автоматически ко всем возможным определениям корректного взаимодействия транзакций.
Граница лаборатории определяется входным языком
В лаборатории вводятся только чтения и записи в форме R1:x или W2:y. Номера участников ограничены диапазоном от одного до пяти, длина расписания — сорока восемью операциями. Результат содержит граф, свидетельства и либо цикл, либо топологический порядок. В нём нет версий данных, commit, rollback или предикатных диапазонов, которые не были выражены отдельными объектами.
По такому входу нельзя подтвердить уровень изоляции реальной СУБД, отсутствие грязного чтения незавершённой версии или восстановимость после отката. Успешный анализ означает только заявленное свойство абстрактного расписания. Для самостоятельной проверки выберите одно ребро, найдите обе операции, затем проверьте весь цикл либо каждую стрелку относительно выданного порядка. Так даже небольшой пример становится воспроизводимым доказательством.
В обоих расписаниях x даёт ребро 1→2, а y даёт 2→3.
В A чтение R3:z предшествует W1:z, поэтому есть 3→1.
Получается цикл 1→2→3→1; конфликтно эквивалентного последовательного порядка нет.
В B порядок операций над z обратный: добавляется 1→3. Все рёбра согласованы с порядком 1,2,3.
Ответ. A не конфликтно сериализуемо; для B подходит последовательный порядок 1,2,3.
Проверка. Внутренний порядок операций каждой транзакции сохранён в обоих вариантах. Причина различия находится только в конфликтующей паре над z.
Где легко ошибиться. Не рисуйте ребро только потому, что транзакции присутствуют рядом. Нужны один объект, разные владельцы и хотя бы одна запись.
Конфликтная сериализуемость расписания
До 48 операций, пять транзакций и объекты a–z. Формат R1:x W2:y через пробел. Для конфликтующих операций строится граф порядка. Проверяется только конфликтная сериализуемость; commit, восстановимость и уровни изоляции здесь не моделируются.
Проверьте понимание
Вопросы к этой главе
Два чтения x добавляют зависимость?
Нет: перестановка двух чтений сама по себе не меняет прочитанные значения. Запись хотя бы в одной из двух операций является обязательным условием этого критерия.
Ацикличный граф проверяет Serializable в PostgreSQL?
Лаборатория проверяет только предоставленные абстрактные чтения и записи. Реальные версии, предикаты и протокол фиксации в этот вход не входят.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверены определение конфликтов, граф предшествования и критерий ацикличности. Два расписания и их свидетельства заданы отдельно.
B+ tree: разделитель направляет поиск, листья хранят диапазон
Вставляем ключи в маленькое дерево, проверяем расщепление листа и продолжение диапазонного поиска по соседним листьям.
Перед началом: Отсортированные ключи; Дерево поиска; Страница хранения и указатель.
Внутренний ключ может повторяться в листе
После расщепления листа с ключами 6,14,22,31 корень может содержать разделитель 22, а правый лист по-прежнему хранить запись с ключом 22. Это ожидаемое устройство B+ tree. Внутренний элемент направляет поиск в нужного потомка, а записи находятся в листьях. Удалить копию из листа при переносе разделителя означало бы потерять реальную индексную запись.
Для определённости зададим учебные параметры: лист вмещает три уникальных ключа, внутренний узел — до четырёх потомков. Равенство разделителю направляет поиск вправо. При переполнении четырьмя ключами лист делится на две равные части, а первый ключ правой части копируется наверх. В литературе слово «порядок» определяется по-разному, поэтому числовые вместимости лучше объявить явно.
Баланс относится к глубине и заполнению страниц
Все листья находятся на одной глубине. Поиск спускается по разделителям, каждый из которых отделяет диапазоны потомков. Большое ветвление уменьшает высоту и число переходов между страницами. При вставке переполнение может распространиться вверх; расщепление корня создаёт новый уровень. Корень имеет особые правила минимального заполнения, иначе пустое или маленькое дерево было бы невозможно представить.
В реальной странице место занимают ещё заголовки, ссылки и значения переменной длины. Поэтому вместимость нельзя вывести только из условного числа ключей без размера записей. Кеширование верхних уровней также меняет число физических чтений. Два уровня учебного дерева означают два логических посещения узлов при холодном точечном поиске, а не гарантированные два обращения к накопителю в любой СУБД.
Диапазон начинается спуском и продолжается по листьям
Для интервала сначала находят лист нижней границы, затем просматривают отсортированные записи и соседние листья до превышения верхней. Повторно спускаться от корня для каждого ключа обычно не требуется. В нашем дереве запрос от 13 до 25 начинает с левого листа, пропускает 6, берёт 14 и 18, затем продолжает справа и берёт 22.
Составной индекс упорядочивает кортежи ключей по заданному сравнению. Поиск по ведущему префиксу обычно согласован с этим порядком, а произвольное условие только на позднем компоненте может потребовать другого плана. Дубликаты, NULL и правила сортировки тоже входят в спецификацию индекса. Для неуникальных ключей нужна согласованная организация нескольких записей, например дополнительный идентификатор строки.
Индекс ускоряет доступ ценой поддержки состояния
При изменении таблицы индекс нужно обновлять согласованно с данными. Удаление может оставить узел слишком пустым и потребовать перераспределения или слияния. Правильность проверяется не только поиском вставленного ключа: сохраните диапазоны потомков, отсортированность листьев и возможность найти все прежние записи. Иначе удачная последняя вставка может скрыть повреждение соседнего диапазона.
Сам факт наличия B+ tree ещё не обязывает оптимизатор использовать его. Для запроса, возвращающего почти всю таблицу, последовательное чтение может быть выгоднее множества случайных обращений. Сравнивайте логическую структуру, оценку количества результатов и физическую стоимость плана отдельно. Учебная трасса ниже доказывает корректность конкретного расщепления и диапазона, но не измеряет производительность реального диска.
Пять вставок и один диапазон
Условие. Пустое B+ tree: лист максимум три уникальных ключа. Вставить 6,14,22,31,18; при переполнении делить четыре записи на две пары.
После трёх вставок единственный лист содержит [6,14,22].
Ключ 31 создаёт переполнение: листья становятся [6,14] и [22,31], корень получает разделитель 22.
Ключ 18 идёт влево: итоговые листья [6,14,18] и [22,31].
Диапазон [13,25] читает 14 и 18 слева, затем 22 справа; ключ 31 завершает просмотр.
Ответ. Корень [22]; листья [6,14,18] и [22,31]; результат диапазона [14,18,22].
Проверка. Объединение листьев содержит все пять ключей ровно один раз. Каждый левый ключ меньше 22, каждый правый не меньше 22; оба листа на одной глубине.
Где легко ошибиться. Копирование разделителя в родителя не означает удаления соответствующей записи из листа. Роль внутренних ключей отличается от роли данных на листовом уровне.
Проверьте понимание
Вопросы к этой главе
Почему равенство 22 отправляется вправо?
Так выбрано соглашение о диапазонах: правый лист начинается с 22. Другое соглашение возможно, но сравнения и обновление разделителей должны быть согласованы.
Связанные листья заменяют дерево?
Они помогают продолжать диапазон после первого найденного листа. Для быстрого поиска начального диапазона всё ещё нужен спуск по внутренним узлам.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверены устройство B+ tree и диапазонный проход по листьям. Вместимости, ключи и правило расщепления этой задачи заданы отдельно.
Функциональные зависимости: разложение без потери связей
Разделяем размещение артефактов и конфигурацию каналов, проверяем ключ, соединение без потерь и локальность ограничений.
Перед началом: Отношение и проекция; Ключ таблицы; Естественное соединение.
Повторяемая конфигурация создаёт риск расхождения
Пусть строка содержит артефакт, канал доставки, сервер и стойку. По правилам системы каждый канал направлен на один сервер, а сервер установлен в одной стойке. Если одинаковая конфигурация повторяется в строках разных артефактов, перенос сервера потребует согласованно изменить много записей. Пропуск одной из них создаст два противоречивых ответа о местоположении одного сервера.
Функциональная зависимость X→Y означает: любые две допустимые строки, совпадающие по X, совпадают и по Y. Это правило для всех разрешённых состояний, а не наблюдение об одном небольшом наборе данных. Случайное отсутствие повторов не доказывает зависимость. В нашей модели связь канала с сервером относится к текущей конфигурации; при хранении истории в ключи и правила пришлось бы включить время или версию.
Замыкание помогает доказать ключ
Обозначим атрибуты A,C,S,R и зависимости C→S, S→R. Замыкание набора AC сначала содержит артефакт и канал, затем получает сервер и стойку. Поэтому AC определяет все четыре атрибута. Ни один из двух исходных атрибутов убрать нельзя: артефакт не выводится из конфигурации, а один артефакт может использовать несколько каналов. При заданных зависимостях AC является кандидатным ключом.
Добавление лишних атрибутов к ключу даёт суперключ, но скрывает структуру ограничений. Нормальная форма Бойса–Кодда требует, чтобы детерминант каждой нетривиальной зависимости был суперключом соответствующего отношения. В исходной таблице C и S такими ключами не являются. Именно это позволяет конфигурационным фактам повторяться для нескольких артефактов и порождает риск несогласованного обновления.
Разложение проверяется по обратному соединению
Выделим таблицы AC, CS и SR. Первая хранит использование канала артефактом, вторая — назначение сервера каналу, третья — размещение сервера. Обратное естественное соединение должно восстановить исходные связи без выдуманных комбинаций. Для двух частей достаточный критерий соединения без потерь: общие атрибуты функционально определяют одну из частей при действующих зависимостях.
Сначала отделяем SR от ACS: общий S определяет всю SR. Затем отделяем CS от AC: общий C определяет CS. Обе ступени без потерь, поэтому композиция восстанавливает исходное отношение. Дополнительно C→S проверяется в CS, S→R — в SR. В этой задаче зависимости сохраняются локально; для произвольного разложения в BCNF такое сохранение не гарантируется автоматически.
Форма таблиц не заменяет остальные ограничения
В каждой новой таблице детерминант объявленной нетривиальной зависимости является ключом, значит полученная схема удовлетворяет BCNF относительно этих правил. На практике ещё нужны внешние ключи, допустимость NULL и политика удаления связанной конфигурации. Теоретическое отношение с обычным равенством отличается от SQL-таблицы с NULL и дубликатами, поэтому формальные условия нельзя переносить на запросы без уточнения семантики.
Нормализация помогает хранить один факт в одном месте, но не выбирает за приложение частоту чтений и стоимость соединений. Денормализация может быть осознанной оптимизацией с протоколом поддержки копий. Для проверки проекта предъявите отдельно исходные зависимости, доказанный ключ, критерий соединения без потерь и способ проверки ограничений. Одного утверждения «разбили на три таблицы» недостаточно для любого из этих выводов.
Конфигурация двух каналов
Условие. R(A,C,S,Rack), зависимости C→S и S→Rack. Строки: (p1,c1,s1,r8), (p2,c1,s1,r8), (p2,c2,s2,r9). Предложить разложение.
Замыкание AC содержит A,C,S,Rack; замыкания A и C по отдельности не содержат всех атрибутов.
CS соединяется с SRack однозначно по S; AC присоединяет конфигурацию по C.
Получаются ровно три исходные строки. Обе зависимости проверяются в отдельных конфигурационных таблицах.
Ответ. Разложение AC, CS, SRack без потерь и с сохранением заданных зависимостей.
Проверка. Если CS содержит два разных сервера для c1, нарушено C→S. Это обнаруживается локально, без соединения с таблицей артефактов.
Где легко ошибиться. Наблюдаемая уникальность в текущих трёх строках не определяет все будущие зависимости. Сначала задаются правила предметной области.
Проверьте понимание
Вопросы к этой главе
Любое разбиение на небольшие таблицы без потерь?
Нет. Соединение проекций может породить ложные сочетания. Нужен критерий без потерь относительно действующих зависимостей.
BCNF всегда сохраняет все зависимости локально?
Нет. В нашей задаче это проверено отдельно. В других схемах часть ограничений после разложения может требовать соединения или другого проектного решения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверены функциональные зависимости, BCNF, соединение без потерь и отдельное требование сохранения зависимостей. Схема доставки артефактов составлена отдельно.
Планы соединения: одинаковый ответ и разные промежуточные объёмы
Переставляем три внутренних соединения и считаем строки до выбора физического алгоритма.
Перед началом: Внутреннее соединение; Мультимножество строк; Селективность условия.
Самый большой результат может возникнуть посередине
Таблица R содержит сто разных ключей, S — по сто строк на каждый такой ключ, а T оставляет только ключи 7 и 42. Сначала соединить R с S означает получить десять тысяч строк, из которых позднее останется двести. Сначала соединить R с T означает оставить два ключа до обращения к S. Итог совпадает, но объём первого промежуточного результата различается в пять тысяч раз.
Такое сравнение начинается с логики запроса. Для внутренних соединений по одинаковым условиям допустимы многие перестановки. Внешние соединения, зависимые подзапросы и условия с NULL требуют отдельного обоснования. Не следует переносить правило свободной перестановки на любой текст SQL. Сначала установите эквивалентность результатов, затем сравнивайте физическую работу допустимых вариантов.
Кардинальность определяется кратностями ключей
При соединении по равенству каждый ключ даёт произведение числа строк с этим ключом слева и справа. Если ключ уникален в одной стороне, её совпавшая строка не размножает строки другой стороны сама по себе. Если ключ повторяется в обеих, возникают все соответствующие пары. Простое взятие меньшего размера таблицы поэтому не является общей формулой результата.
Оптимизатор оценивает распределения по статистике: количество разных значений, частоты популярных значений, NULL и селективности фильтров. Равномерность и независимость — полезные приближения, но коррелированные столбцы и сильный перекос способны их нарушить. Предположение о распределении нужно отличать от точного ограничения ключа или внешней ссылки. Ошибка ранней оценки затем распространяется на стоимость следующих операторов плана.
Физический алгоритм добавляет собственную стоимость
Nested loop повторяет работу внутренней стороны для строк внешней; индекс может сделать отдельный поиск дешёвым. Hash join строит хеш-структуру и просматривает другую сторону, а сортировочное соединение использует порядок входов. Размер памяти, необходимость сортировки, случайные чтения и возможность выгрузки на диск меняют выбор. Одна только численность конечного ответа не определяет лучший алгоритм.
В нашем расчёте сравнивается количество промежуточных строк, а не гарантированное время процессора. План с меньшим первым результатом всё ещё может потерять преимущество из-за других расходов. Зато точный подсчёт даёт полезную проверку объяснения плана: если система обещает две строки там, где по кратностям должно быть десять тысяч, причина расхождения заслуживает отдельного исследования.
Читайте оценки рядом с фактом выполнения
План без выполнения показывает прогноз. Профилирование с фактическим выполнением добавляет реально полученные строки и другие показатели, но само запускает запрос. В производственной среде это действие требует понимания стоимости и побочных эффектов. Для учебного анализа достаточно синтетических таблиц и независимого соединения в памяти. Здесь мы не выполняем SQL над пользовательской базой и не объявляем расчёт измерением сервера.
Сравнивая несколько операторов, уточняйте, указано число строк на один цикл или суммарно по всем повторениям. Затем ищите первый участок, где прогноз расходится с фактом, а не только самый медленный верхний узел. Проверьте актуальность статистики, ограничения ключей и корреляцию фильтров. Подсказка оптимизатору может изменить план, но не заменит понимания того, какие строки реально размножаются в соединении.
Два ключа до большой таблицы
Условие. R: по одной строке для ключей 0…99. S: по 100 различимых строк на каждый ключ 0…99. T: по одной строке для 7 и 42. Все соединения внутренние по ключу.
R⋈S содержит 100×100=10000 строк.
Последующее соединение с T оставляет 2×100=200 строк.
R⋈T сначала даёт ровно две строки.
Присоединение S к этим двум строкам также даёт 200 результатов; идентичность сравнивается с учётом каждой различимой строки S.
Ответ. Одинаковые 200 итоговых строк. Первый промежуточный результат: 10000 против 2.
Проверка. В обоих ответах присутствуют все 100 строк S для ключа 7 и все 100 для 42. Остальные ключи отсутствуют независимо от порядка.
Где легко ошибиться. Меньший промежуточный результат полезен, но не является универсальным измерением времени. Выбор физического плана требует дополнительных затрат и предположений.
Проверьте понимание
Вопросы к этой главе
Почему ответ не просто две строки, раз T содержит два ключа?
Каждый ключ T соответствует ста различимым строкам S. Внутреннее соединение сохраняет эти совпавшие пары, а не сворачивает их в одну.
Можно всегда переставлять фильтр раньше любого JOIN?
Нужно доказать эквивалентность, особенно при внешних соединениях и NULL. Расчёт главы относится к указанным внутренним соединениям.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Проверены оценка селективности соединения и различие кардинальности и конкретного физического плана. Синтетические таблицы и точные кратности заданы отдельно.
Темы направления
Параллельные системы: истории, конфликты и завершение
Регистр сначала равен 0. W1 пишет 1 с t=1 до t=4; R1 читает 1 с t=2 до t=3. Затем W2 пишет 2 с t=5 до t=6, а R2 читает 2 с t=7 до t=8. Других операций нет. Допустима ли история?
W1 и R1 пересекаются; можно выбрать точку записи 1 в t=2,2 и точку чтения в t=2,5.
W2 завершается до R2. Выбираем точки 5,5 и 7,5, сохраняя реальный порядок.
Получаем последовательность W1,R1,W2,R2: чтения возвращают 1 и 2 по спецификации регистра. Все точки лежат внутри интервалов.
Ответ: Да, приведённая история линеаризуема.
Проверка: Если изменить только поздний ответ R2 на 1, объяснения уже нет: W2 обязана стоять раньше R2, а других записей после неё нет. Проверка использует полную указанную историю.
Проверьте понимание
Какую гарантию или историю операций нужно проверить?
Выберите модель проверки до вывода о корректности: интервалы операций, конфликты транзакций, общий инвариант или условия распределённого исполнения. Разборы показывают ход проверки, а задания помогают проверить вывод.
Проверить историю общего регистра
В истории две операции: запись значения 1 завершилась до начала чтения, однако чтение вернуло исходный 0. Проверьте, допускает ли спецификация такой порядок.
Указанная история из двух операций не проходит проверку линеаризуемости.
В одном условии сеть разделилась на две части; в другом сообщения могут опаздывать сколь угодно долго. Сначала уточните требуемую гарантию и модель отказа.
Подходящий разбор по его условиям: ответ при разделении сети или гарантированное завершение в асинхронной модели.
Тест с тысячей запусков доказывает отсутствие гонок?
Он может обнаружить конкретную недопустимую историю, но обычно не охватывает все расписания. Гарантия требует модели, аргумента корректности или исчерпывающей проверки ограниченного пространства.
Сериализуемость и линеаризуемость — одно условие?
Они относятся к разным спецификациям и ограничениям порядка. Для транзакций изучают эквивалентность последовательному выполнению; линеаризуемость операций дополнительно связывает объяснение с реальным порядком непересекающихся интервалов.
Почему важно точно задать отказ?
Задержка, потеря связи и остановка процесса дают разные наблюдения и предпосылки теорем. Нельзя переносить невозможность из одной модели на все практически работающие протоколы без проверки условий.