Параллельные системы: истории, конфликты и завершение
Линеаризуемость, сериализуемость, снимки, CAP и FLP через конкретные истории операций.
Задачи модуля
Начните со спецификации регистра и реальных интервалов вызовов. Затем перейдите к транзакциям, где согласованный снимок ещё не гарантирует сохранение общего ограничения.
В распределённой системе отдельно сформулируйте допустимые результаты и обязанность завершения. Разделение сети и асинхронность ограничивают разные сочетания гарантий.
Находить допустимый последовательный порядок завершённых операций регистра.
Строить конфликтный граф и распознавать write skew между разными строками.
Формулировать ограничения CAP и FLP с явными условиями отказов и времени.
Истории параллельных вычислений
Линеаризуемость: уважать завершившийся вызов
Перекрывающиеся операции можно упорядочить несколькими способами. Но если одна уже завершилась до начала другой, линеаризуемая история обязана сохранить этот порядок вместе с последовательной спецификацией объекта.
Перед началом: Вызов и ответ; Последовательная спецификация регистра.
Ищите порядок внутри временных интервалов
Линеаризуемость требует представить каждую завершённую операцию как мгновенное действие между её вызовом и ответом. Полученный последовательный порядок должен объяснять все возвращённые значения и уважать реальное предшествование неперекрывающихся вызовов. Для перекрывающихся интервалов порядок можно выбирать, но не произвольно менять ответы. В истории с незавершёнными вызовами определение допускает соответствующее дополнение или удаление незавершённых операций; здесь рассматриваем только полностью завершённые истории.
Последовательная согласованность слабее по времени
Она сохраняет порядок операций каждого процесса, но не требует всех межпроцессных отношений реального времени. Поэтому историю иногда можно объяснить некоторым последовательным порядком, который запрещён линеаризуемостью. Чтобы показать различие, нужны как минимум независимые процессы: перестановка внутри одного процесса обычно нарушила бы обе модели. Принятая спецификация объекта также существенна: обычный регистр возвращает последнее записанное значение, а очередь имеет другие правила.
Малую историю можно проверить полным перебором
Строят частичный порядок из завершений до вызовов, перебирают его линейные продолжения и симулируют последовательный объект. Один подходящий порядок доказывает линеаризуемость конечной истории; отсутствие всех вариантов её опровергает. Это не доказательство реализации на всех возможных историях. В системах с распределёнными часами физические метки времени могут иметь погрешность, поэтому реальное предшествование нужно устанавливать надёжно, например по наблюдаемым завершениям и последующим вызовам в тестовом сценарии.
Позднее чтение старого значения
Условие. Регистр сначала 0. Процесс A вызывает write(7) в момент 1, получает ответ в 2. Процесс B вызывает read в 3, получает 0 в 4. Других операций нет.
Запись завершилась до вызова чтения, поэтому обязателен порядок write(7) раньше read.
В последовательном регистре после этой записи хранится 7.
Возвращённый 0 не соответствует единственному допустимому порядку, история не линеаризуема.
Если игнорировать межпроцессное реальное время, порядок read затем write объясняет ответы и не нарушает порядок каждого одиночного процесса.
Ответ. История не линеаризуема, но допускает последовательное объяснение без требования реального времени.
Проверка. Перебор двух перестановок показывает: одна нарушает время, другая значение чтения. Никакого допустимого варианта не остаётся.
Где легко ошибиться. Наличие какого-либо последовательного объяснения недостаточно: нужно ещё проверить обязательные отношения реального предшествования.
Проверьте понимание
Вопросы к этой главе
Что изменится при перекрытии вызовов?
Чтение можно иногда поставить перед записью внутри общего временного перекрытия, если это объясняет ответы и остальные ограничения.
Проверка одной истории доказывает корректность объекта?
Нет. Она относится только к этой конечной трассе; реализация должна удовлетворять условию для всех допустимых историй.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Определение истории и реального предшествования; конечный регистр проверен перебором допустимых порядков. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Векторные часы: несравнимость означает отсутствие порядка событий
Одна большая временная метка не доказывает причинность. Векторные часы сохраняют сведения о том, сколько событий каждого процесса уже известно, и позволяют отличить причинный порядок от конкуренции.
Перед началом: Частичный порядок; Покомпонентное сравнение.
Согласуйте правила обновления
Для n процессов часы имеют n компонент. Перед локальным событием или отправкой процесс увеличивает собственную компоненту. Сообщение несёт текущий вектор. При получении процесс берёт покомпонентный максимум локальных часов и вектора сообщения, затем увеличивает собственную компоненту. Такой порядок обновления нужно соблюдать во всех трассах. Увеличение только чужой компоненты или забытая локальная единица может сделать два разных события неразличимыми и разрушить проверку причинности.
Сравнение является частичным
Вектор u строго предшествует v, если все его компоненты не больше соответствующих компонент v и хотя бы одна меньше. В стандартной модели корректно обновляемых часов это соответствует причинному отношению happened-before между событиями. Если в одной компоненте u больше, а в другой меньше, векторы несравнимы и события конкурентны. Сравнение суммы компонент или лексикографический порядок создаёт искусственную последовательность, которая не отражает причинность.
Часы не сообщают физическую задержку
Они фиксируют логическую зависимость через локальный порядок и сообщения, но не измеряют секунды между событиями. Отсутствие причинного порядка не означает одновременность по настенным часам. Для построения доказательства полезно выписать каждую отправку, приём и локальное событие отдельно, сохраняя вектор именно после обновления события. Допущение фиксированного набора процессов тоже входит в модель: динамическое добавление участников и сжатые часы требуют иных соглашений, которые здесь не рассматриваются.
Векторы разных событий в стандартной модели не должны случайно совпадать: собственное увеличение фиксирует новое событие. При потере или переполнении счётчиков эта предпосылка нарушается, и сравнение уже не имеет заявленной гарантии.
Сообщение между двумя независимыми событиями
Условие. Процессы A,B начинают с (0,0). A выполняет локальное событие a, затем отправляет m. B до приёма делает b, затем принимает m.
После a часы A=(1,0), после отправки m=(2,0).
Независимое событие b на B имеет часы (0,1).
Приём берёт max((0,1),(2,0))=(2,1), затем увеличивает компоненту B: (2,2).
a и b несравнимы; отправка (2,0) причинно предшествует приёму (2,2).
Раздел Vector Clocks: покомпонентный максимум, собственное увеличение и сравнение причинности. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
ABA: совпавшее значение скрывает изменённую историю
Compare-and-swap сравнивает текущее значение, а не всю историю его изменений. Возврат указателя к прежнему адресу может сделать устаревшее решение внешне допустимым, хотя структура уже другая.
Перед началом: Атомарное сравнение с обменом; Связный стек.
Локальный снимок может устареть
Операция извлечения из стека читает head=A и next=A.next, затем пытается заменить head на сохранённый next через CAS. Если другой процесс менял структуру между чтением и CAS, проверка только равенства head=A не сообщает, остались ли прежними связи узлов. Проблема возникает при повторном использовании адресов или возвращении узла в стек. Атомарность самой CAS сохраняется: ошибочным становится предположение, которое процесс сделал до неё.
Версия отличает одинаковые адреса
Можно сравнивать пару (указатель,счётчик изменений), увеличивая счётчик при каждом изменении головы. Тогда A с новой версией не равно старой прочитанной паре, и CAS откажет. Но конечный счётчик способен переполниться, а аппаратная атомарность пары требует подходящей реализации. Версия также не решает автоматически безопасное освобождение памяти: чтение уже освобождённого узла остаётся отдельной проблемой. Для этого применяют соответствующие схемы управления временем жизни, например hazard pointers или эпохи.
Трасса должна показывать потерянную связь
Само изменение A→B→A не всегда вредно для абстрактного объекта. Нужно показать, какое сохранённое значение стало неверным и какой результат CAS нарушит структуру. В нашем примере один узел удаляется и не возвращается, а голова возвращается к тому же адресу. Устаревший next снова вводит удалённый узел. Это конкретное нарушение спецификации, а не только необычная последовательность значений. Проверка ограничена заданным чередованием действий и не доказывает корректность полного алгоритма стека.
Удалённый узел возвращается устаревшим CAS
Условие. Стек A→B→C. T₁ читает head=A,next=B. T₂ извлекает A, затем B, после чего возвращает A с next=C. Что сделает CAS T₁?
После действий T₂ текущая структура A→C; B уже извлечён и не принадлежит стеку.
Голова снова равна адресу A, поэтому CAS(head,A,B) без версии успешно устанавливает B.
Стек ошибочно получает голову B из устаревшего снимка.
С версиями начальная пара (A,0) стала бы (B,1),(C,2),(A,3); сравнение с (A,0) не прошло бы.
Ответ. Обычная CAS пропускает ABA и возвращает B; версионная CAS в этой трассе отвергает устаревшее действие.
Проверка. Конечная голова по актуальному состоянию должна ссылаться на A либо после корректного извлечения на C, но не на уже удалённый B.
Где легко ошибиться. Версионный указатель не является универсальным решением освобождения памяти и требует отдельного анализа переполнения счётчика.
Проверьте понимание
Вопросы к этой главе
CAS при ABA перестала быть атомарной?
Нет. Она правильно сравнила одно текущее значение. Историческое предположение вызывающего кода было слишком слабым.
Можно ли просто запретить возвращать узлы?
Это может устранить конкретную трассу, но повторное использование памяти способно вернуть тот же адрес другим способом.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Версионные пары указателя и счётчика; ограничения memory reclamation. Собственная трасса стека не является переносом кода очереди. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Кворумы: пересечение не заменяет правило выбора версии
Неравенство W+R>N гарантирует общую реплику у записи и чтения. Но чтение должно правильно использовать полученные версии; пересечение множеств само по себе не выбирает свежий ответ.
Перед началом: Репликация; Множества.
Комбинаторная гарантия пересечения
Если из N реплик запись подтверждена W различными узлами, а чтение получает ответы R различных узлов, при W+R>N эти множества пересекаются. Иначе их непересекающееся объединение имело бы больше N элементов. Это точное комбинаторное утверждение. Оно не говорит, какой ответ придёт первым, какие записи конкурентны и как упорядочены версии. Повторные ответы одного узла не увеличивают размер кворума и не могут учитываться как независимые реплики.
Версии требуют согласованного смысла
В простой модели одной завершённой записи и сравнимых монотонных версий чтение выбирает максимальную версию среди всего своего кворума. Тогда пересечение приносит хотя бы один свежий экземпляр. Если вернуть первый полученный ответ, можно взять старую реплику до прихода общей. При нескольких конкурентных писателях, сбоях и переупорядоченных сообщениях нужны дополнительные протокольные правила: присвоение версий, подтверждения, иногда фаза записи назад. Одних двух чисел W,R недостаточно для доказательства линеаризуемого регистра.
Доступность ограничивается теми же числами
Для завершения операции нужно дождаться нужного количества различных доступных реплик. Большой кворум улучшает пересечение, но уменьшает терпимость к недоступным узлам. Условие W>N/2 обеспечивает пересечение двух записывающих кворумов, однако не выбирает порядок конкурентных действий без протокола. Полезный разбор отделяет три слоя: теорему о множествах, модель версий и полный алгоритм работы при отказах. Наша конечная задача проверяет только первый слой и один упрощённый сценарий второго.
Старый первый ответ
Условие. N=5, запись версии 8 подтверждена узлами {1,2,3}, чтение ждёт {3,4,5}. На 4,5 пока версия 7. Найдите W,R и корректный выбор в простой модели.
W=3,R=3, сумма 6>5, поэтому пересечение обязательно.
Конкретно общая реплика равна 3 и хранит подтверждённую версию 8.
Если узел 4 ответил первым, немедленный возврат дал бы старую версию 7.
Ожидание всех трёх ответов и выбор максимальной версии дают 8; перебор всех троек чтения подтверждает пересечение с любой тройкой записи.
Ответ. Пересечение есть; в заданной простой модели нужно выбрать максимальную версию 8 после сбора кворума.
Проверка. У двух троек в пятиэлементном множестве не может быть пустого пересечения. При R=2 чтение {4,5} уже могло бы полностью пропустить запись.
Где легко ошибиться. Не называйте W+R>N самостоятельным доказательством сильной согласованности: это только необходимая часть некоторых кворумных протоколов.
Проверьте понимание
Вопросы к этой главе
Почему R=2 не хватает при W=3,N=5?
Сумма равна N, и множества {1,2,3} и {4,5} могут быть непересекающимися.
Пересекаются ли любые два записывающих кворума размера 3?
Да, в пяти репликах. Но обработка конфликтующих версий всё равно требует правил протокола.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Раздел настраиваемых R,W,N и версий. Сильная согласованность не приписывается одному неравенству кворумов. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Связанные методы
История общего регистра: найдите последовательный порядок внутри интервалов операций
Линеаризуемость требует разместить каждую завершённую операцию в одной точке между её вызовом и ответом. Полученный порядок должен соответствовать последовательной спецификации объекта и сохранять реальный порядок операций, которые не перекрывались во времени.
Конфликтный граф транзакций: цикл запрещает перестановку в последовательное расписание
Две операции конфликтуют, когда принадлежат разным транзакциям, обращаются к одному объекту и хотя бы одна пишет. Направления конфликтов образуют граф предшествования. Его ацикличность эквивалентна возможности переставить неконфликтующие операции в последовательное расписание.
Согласованный снимок не защищает ограничение между разными строками
При изоляции снимка транзакции могут читать один согласованный прошлый снимок и успешно записывать разные строки. Если правило связывает эти строки, обе локально разумные записи вместе способны нарушить инвариант. Такая аномалия называется write skew.