Главная » Хабрахабр » [Перевод] Время фрагментарно; немного о сходстве распределенных систем и слабой модели памяти

[Перевод] Время фрагментарно; немного о сходстве распределенных систем и слабой модели памяти

Привет всем!

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

Это всего лишь ошибки на единицу, связанные с использованием времени. В информатике есть всего одна настоящая проблема: признать, что ошибки инвалидации кэша названы неверно.

– Автор неизвестен

Время – штука странная.

Нам кажется, что любое событие в 15. Время такое странное, поскольку нам очень, очень хочется считать, что оно совершенно упорядочено. 00 – без исключений, доводов или компромиссов. 00 происходит (как мы бы сказали) до любого события в 16.

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

Дело в том, что нам это не известно, поскольку уровень абстракции, над которым мы существуем, не дает ответа на этот вопрос. Почему? Свобода переупорядочивать события зачастую позволяет создавать гораздо более производительные и доступные системы. Случайно это или нет, но наши вычислительные абстракции не дают гарантий относительно порядка действий.

Процессор сам решает, как именно конвейеризовать инструкции и выполняет их не в порядке поступления – то есть, использует свои микросхемы эффективнее, чем догадался бы использовать я. В процессоре может действовать модель упорядочения памяти; в ней отражено, какие гарантии процессор не желает давать вам на этапе выполнения сборки никаких гарантий – например, какая инструкция была выполнена раньше, а какая – позже.

Такое переупорядочивание по определению присуще аппаратной модели памяти и в значительной степени объясняет, почему в компиляторах предоставляется такая «слабая» концепция времени. В языке может действовать модель согласованности памяти (“модель памяти” для краткости); в ней отражено, каких гарантий язык вам не дает при генерировании сборки, например, при распределении инструкций по множеству потоков. Именно в рамках такой модели памяти, реализованной в языке, вы и программируете, когда пишете неблокирующий код.

По умолчанию C++ обеспечивает атомарные операции с синхронизацией, но в нем также можно ослабить модель доступа к памяти для повышения производительности. Знаменитый пример модели памяти, реализованный на уровне языка – это сильная и слабая модели памяти в стандарте C++11. Обеспечиваемое таким образом поведение призвано послужить абстракцией над основными архитектурами процессоров, используемыми сегодня (x86, POWER и ARM).

Переупорядочивания, непосредственно связанные с запаздыванием при коммуникации или с отсутствием синхронизации в основном объясняют, почему в распределенной системе вы не обойдетесь без упомянутой слабой модели времени. Наконец, в распределенной системе может быть своя модель согласованности; в ней отражено, каких гарантий не собирается давать вам система относительно порядка событий на клиентах и репликах в глобальной вычислительной сети. Именно такую модель согласованности вы программируете, когда пишете распределенное приложение.

Во всех подобных ситуациях эти модели описывают (желаемое) поведение системы, наблюдаемое извне этой системы. На практике существует огромный зоопарк моделей согласованности, которыми можно воспользоваться при программировании распределенной системы. Если бы время не было фрагментарным, если бы мы всегда четко представляли, в каком порядке происходят операции в нашей системе – естественно, ответ на этот вопрос был бы утвердительным. Если я – конкретный клиент или конкретный поток – записываю значение, затем немедленно его считываю, гарантируется ли, что я обязательно увижу запись не старше моей? Странно было бы вообще задавать такой вопрос.

Но время фрагментарно – поэтому, ставить такой вопрос приходится.

Модели согласованности – Я имею в виду, модели памяти

Рассуждать о таком фрагментарном порядке зачастую сложно и всегда неприятно. Нам хотелось бы исходить из того, что на всех уровнях стека время всегда абсолютно – будь то при ACID-транзакциях, либо при атомарных операциях/блокировках. Чем строже гарантии, тем, естественно, проще с ними программировать!

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

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

Что же делать? Мы уже представляем, насколько в этом можно запутаться.

Описание времени как сущности, подразумевающей где-то от двух до восьми видов частичного порядка

В своей книге 2014 года Себастьян Буркхардт пытается дать исчерпывающую характеристику многочисленных вариантов моделей согласованности. При такой характеристике, наряду с другими математическими структурами, применяется два варианта логического упорядочения событий: «видимость» (visibility) и «произвольность» (arbitration), ранее также упоминавшиеся в других работах Буркхардта с соавторами, см. например, статью об указании и проверке реплицируемых типов данных (2014).

Он позволяет отслеживать, какие события (возможно, в других репликах) видны каким другим событиям. “Видимость” – это частичный порядок, присущий потенциальной обусловленности. К видимости не предъявляется никаких требований кроме ацикличности; события в объекте могут быть видимы событиям в другом объекте, а операция считывания или записи события никак не влияет на его видимость для других событий.

“Произвольность” – это общий порядок, позволяющий отслеживать, как распределенная система, в которой возникает ситуация выбора, будет судить, какому событию произойти ранее, а какому позже.

В частности, в приложении к своей статье 2014 года Буркхардт демонстрирует, «насколько близка» слабая модель памяти из C++11 к пообъектной причинной согласованности, но с некоторыми интересными отклонениями. Поскольку модели распределенной согласованности аналогичны моделям памяти, оказывается, что такие феномены видимости и произвольности также могут пригодиться при обсуждении моделей памяти. Об этом и пойдет речь в оставшейся части поста.

При «считывании» видимость между любыми двумя объектами будет учитываться лишь в ситуациях, когда и чтение, и запись касаются одного и того же объекта, а при считывании может быть видна всего одна запись (или не одной).
Это соответствует ситуации, в которой процессор с разделяемой памятью в любой момент времени может записывать информацию всего в одну ячейку памяти для любого конкретного объекта, даже если разные потоки могут обращаться к нему в разные причинно-следственные моменты (с другой стороны, в распределенной системе логический объект может записываться сразу во множество отдельных реплик). Для начала давайте конкретизируем видимость и произвольность с учетом «считывания» и «порядка следования изменений».

Опять же, такая специализация основана на том факте, что при слабой спецификации памяти категорические гарантии даются только на уровне одного объекта. “Порядок модификации” соответствует тому же этапу при конкретизации произвольности, он пообъектный и допускает только записи.

и посмотрим, как они применяются к слабой модели памяти. Далее давайте обсудим аксиомы согласованности, сформулированные Буркхардтом и др. В статье Буркхардта основное внимание уделено свойствам, определяющим кросс-объектную причинную согласованность. Обратите внимание: даже несмотря на слово «аксиомы», это просто свойства, которые могут обеспечиваться или не обеспечиваться в различных моделях памяти.

Согласованность в конечном счете

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

Логически выстроить такие условия в системе со слабой моделью памяти должно быть несколько сложнее: приходится утверждать, что для любой конкретной записи не может существовать бесконечного количества операций считывания, которые бы не считывали эту запись или более ранние записи (в порядке модификации).

В спецификации C++11 соблюдение этой аксиомы не гарантируется, хотя, на практике найти контрпример сложно.

Эфирная согласованность

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

указывают, что эта аксиома «не подтверждается» в спецификации C++11, и неясно, “does not validate” можно ли на практике наблюдать «удовлетворяющие циклы». Буркхардт и др.

Аксиомы обусловленности

Чтобы конкретизировать, к чему именно относится феномен обусловленности при слабой модели памяти, мы должны в точности определить, какие события могут влиять на результаты каких других событий. Для начала рассмотрим наши стандартные причинно-следственные аксиомы: сеансовые гарантии. Это четыре взаимосвязанные качества отражающие свойства когерентности операций чтения и записи, происходящих в разных потоках, причем, они должны конкретизироваться на уровне каждого объекта (см. рис. 23 у Буркхардта и др.).

  • RYW (Читай твои записи): операция считывания, идущая за операцией записи, делается в той же ячейки, в рамках тех же потока/реплики/сеанса, должна считывать данные не менее актуальные, чем запись. Вариант данного свойства для распределенных систем задается исключительно в терминах видимости, тогда как вариант для слабой модели памяти должна опираться как на порядок считываний, так и на порядок изменения.
  • MR (монолитные считывания): последующие считывания (в рамках того же потока, в той же ячейке) также и в дальнейшем должны видеть не менее актуальные данные.
  • WFR (сначала считывание, потом запись): если запись следует за считыванием в рамках потока, в одной и той же ячейке, то в порядке изменений она должна идти позже, чем операция считывания.
  • MW (Монолитные записи): более поздние записи (в рамках потока, в ту же самую ячейку) должны идти позже в порядке модификации.

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

В частности, при анализе в слабой модели памяти такие явления обусловленности ограничены пределами потока/реплики/сеанса и конкретной ячейки/объекта, куда производится запись: в статье Буркхардта и др. Эти свойства отражают представления об обусловленности, соответствующие нашему здравому смыслу; однако, в них упускается самое интересное. рис. в данном случае говорится о «пообъектной условной видимости» и «пообъектной условной произвольности», также см. Эти феномены совершенно не ограничивают поведение системы, когда разные потоки записывают информацию в разные ячейки. 23.

Затем аксиомы кросс-объектной обусловленности описывают влияние причинно-следственных связей на уровне различных объектов/ячеек памяти.

  • COCV (Кросс-объектная условная видимость): тот же случай, что и RYW, но без условия, что окончательное считывание должно делаться все в том же потоке/реплике/сеансе. Считывания из объекта, объективно более поздние, чем записи в этот объект, должны брать данные не менее актуальные, чем внесены при записи.

В спецификации C++11 отражены эти свойства. Обратите внимание: они определены так, что ограничения на видимость при записи и произвольность порядка модификации не слишком отражаются на этих определениях.

Но это не касается последнего свойства.

  • COCA (Кросс-объектная условная произвольность): подобна монолитным записям, но распространяется на разные потоки, аналогично тому как COCV — это RYW для разных потоков. Однако, поскольку порядок модификации влияет лишь на записи в одном объекте, формулировка для слабой модели памяти допускает в системе несогласованное распределение актов записи в разные объекты, и записи могут не соответствовать ни считываниям, ни порядку внутри потока.

Конкретно, COCA в слабой модели памяти – это значительно более слабое свойство. Именно поэтому при слабой модели памяти следующий код может вернуть .

Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return y

Обратите внимание: при RYW не бывает x := 0 → x := 1 в порядке модификации и для y – аналогично; таким образом, в порядке модификации должно содержаться x := 1 → x := 0 и y := 1 → y := 0. Порядок внутри каждого потока может быть рассогласован с пообъектным порядком и порядком модификации. Речь не о том, что порядок потоков/считываний противоречит порядку модификации, а о том, что каждый поток видит непротиворечивую историю записей. Таким образом, порядок модификации очевидно образует цикл в порядке потоков.
Такой цикл допускается в COCA при слабой модели памяти. Эти истории согласуются с историями других потоков лишь в том случае, если мы пообъектно ограничиваем область их применения.

Что же все это значит?

Время фрагментарно.

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

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

Возможно, нам просто требуется к этому привыкнуть. Время фрагментарно.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Теория счастья. Случайности неслучайны

Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь ...

Снежинки в стилистике StarWars своими руками (upd. 2018)

Для изготовления снежинок вам потребуется: Файл со схемой.2. 1. Ножницы.4. Принтер (думаю лазерный будет предпочтительней).3. Бумага.5. Скальпель.5. Лично мое мнение — при печати на стандартной офисной бумаге плотностью 80г/м2 становится не очень удобно вырезать (все-таки при складывании бумаги получается толстый ...