Привет всем!
Сегодня мы хотели бы в очередной раз затронуть тему одновременного и последовательного выполнения в различных программах, особенно — в распределенных системах. Еще в сентябре мы публиковали статью "Синхронность — это миф" на эту тему, а теперь публикуем перевод более серьезного исследования, которое, надеемся, поможет вам лучше сориентироваться с распределенными системами.
В информатике есть всего одна настоящая проблема: признать, что ошибки инвалидации кэша названы неверно. Это всего лишь ошибки на единицу, связанные с использованием времени.
– Автор неизвестен
Время – штука странная.
Время такое странное, поскольку нам очень, очень хочется считать, что оно совершенно упорядочено. Нам кажется, что любое событие в 15.00 происходит (как мы бы сказали) до любого события в 16.00 – без исключений, доводов или компромиссов.
Однако, информатика знает массу примеров, когда к данному требованию приходится подходить не столь строго. Оно проявляется на уровне процессоров, компиляторов, узлов сети. Снова и снова при вычислениях, на разных уровнях стека мы оказываемся в ситуациях, когда перед нами два события, и мы не знаем, в каком порядке они произошли. Время очевидно не является тотальным; она фрагментарно.
Почему? Дело в том, что нам это не известно, поскольку уровень абстракции, над которым мы существуем, не дает ответа на этот вопрос. Случайно это или нет, но наши вычислительные абстракции не дают гарантий относительно порядка действий. Свобода переупорядочивать события зачастую позволяет создавать гораздо более производительные и доступные системы.
В процессоре может действовать модель упорядочения памяти; в ней отражено, какие гарантии процессор не желает давать вам на этапе выполнения сборки никаких гарантий – например, какая инструкция была выполнена раньше, а какая – позже. Процессор сам решает, как именно конвейеризовать инструкции и выполняет их не в порядке поступления – то есть, использует свои микросхемы эффективнее, чем догадался бы использовать я.
В языке может действовать модель согласованности памяти (“модель памяти” для краткости); в ней отражено, каких гарантий язык вам не дает при генерировании сборки, например, при распределении инструкций по множеству потоков. Такое переупорядочивание по определению присуще аппаратной модели памяти и в значительной степени объясняет, почему в компиляторах предоставляется такая «слабая» концепция времени. Именно в рамках такой модели памяти, реализованной в языке, вы и программируете, когда пишете неблокирующий код.
Знаменитый пример модели памяти, реализованный на уровне языка – это сильная и слабая модели памяти в стандарте C++11. По умолчанию C++ обеспечивает атомарные операции с синхронизацией, но в нем также можно ослабить модель доступа к памяти для повышения производительности. Обеспечиваемое таким образом поведение призвано послужить абстракцией над основными архитектурами процессоров, используемыми сегодня (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 в слабой модели памяти – это значительно более слабое свойство. Именно поэтому при слабой модели памяти следующий код может вернуть {x ≡ 0, y ≡ 0}.
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 при слабой модели памяти. Речь не о том, что порядок потоков/считываний противоречит порядку модификации, а о том, что каждый поток видит непротиворечивую историю записей. Эти истории согласуются с историями других потоков лишь в том случае, если мы пообъектно ограничиваем область их применения.
Что же все это значит?
Время фрагментарно.
Даже хотя нам и кажется, что время течет совершенно упорядоченно, изучение распределенных систем и слабой модели памяти со всей ясностью вам демонстрирует, что это не так. Именно поэтому в обоих данных ситуациях наша стандартная чрезмерная аппроксимация, согласно которой время тотально, ограничивает производительность – чего мы не можем себе позволить.
Затем, признав, что время действительно фрагментарно, мы обнаружим множество маленьких, но важных отличий между разновидностями такой частичности. Даже два вышеупомянутых поля, которые кажутся настолько схожими на первый взгляд, во множестве тонких нюансов позволяют различать, какие именно виды событий при них считаются взаимовлияющими.
Необходимо подробнее разбираться в технических деталях различных свойств уже после того, как кто-то сможет выразить свойства одного поля на языке другого.
Время фрагментарно. Возможно, нам просто требуется к этому привыкнуть.
Автор: ph_piter
