Модели согласованности памяти в компьютерных системах

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

13 мин чтения

100%

Источник: Consistency model — Wikipedia

Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.

Содержание

Введение

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

В информатике модель согласованности определяет соглашение между программистом и системой, в рамках которого система гарантирует, что если программист следует правилам операций с памятью, то память будет согласованной, а результаты чтения, записи или обновления памяти будут предсказуемыми. Модели согласованности используются в распределенных системах, таких как системы распределенной общей памяти или распределенные хранилища данных (например, файловые системы, базы данных, системы оптимистической репликации или веб-кэширование). Согласованность отличается от когерентности, которая проявляется в системах с кэшированием или без него, и представляет собой согласованность данных относительно всех процессоров. Когерентность обеспечивает поддержание глобального порядка, в котором записи в одно местоположение или одну переменную видны всем процессорам. Согласованность же определяет порядок операций к нескольким местоположениям относительно всех процессоров. Языки программирования высокого уровня, такие как C++ и Java, поддерживают соглашение о согласованности, преобразуя операции с памятью в операции низкого уровня таким образом, чтобы сохранить семантику памяти, переупорядочивать некоторые инструкции памяти и инкапсулировать необходимую синхронизацию с помощью вызовов библиотечных функций, таких как pthread mutex lock.

Пример

Предположим, что возникает следующая ситуация: существуют два подхода к определению и классификации моделей согласованности: проблема и представление. Подход "проблема" (Issue) описывает ограничения, определяющие, как процесс может выполнять операции. Подход "представление" (View) определяет порядок операций, видимый процессам. Например, модель согласованности может определять, что процессу запрещено выполнять операцию, пока не будут завершены все ранее выполненные операции. Различные модели согласованности накладывают различные условия. Одна модель согласованности считается более строгой, чем другая, если она требует всех условий этой модели и дополнительных. Иными словами, модель с меньшим числом ограничений считается более слабой моделью согласованности. Эти модели определяют, как должно быть организовано аппаратное обеспечение и, на высоком уровне, как программист должен писать код. Выбранная модель также влияет на то, как компилятор может переупорядочивать инструкции. Как правило, если между инструкциями существуют зависимости по управлению и записи в одно и то же место упорядочены, компилятор может переупорядочивать их по мере необходимости. Однако, в случае моделей, описанных ниже, некоторые могут разрешать переупорядочивать записи перед загрузками, а другие – нет.

Соответствие кэша

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

Гарантии сеанса

Эти 4 модели согласованности были предложены в статье 1994 года. Они фокусируются на гарантиях в сценарии, когда изменения данных вносит только один пользователь или одно приложение.

Консистенция выпуска

Модель согласованности при освобождении ослабляет модель слабой согласованности, различая операцию синхронизации входа и операцию синхронизации выхода. При слабом порядке, когда операция синхронизации должна быть видна, все операции во всех процессорах должны быть видны до завершения операции синхронизации и продолжения работы процессора. Однако, в модели согласованности при освобождении, при входе в критическую секцию, называемом "acquire", должны быть завершены все операции относительно локальных переменных памяти. При выходе, называемом "release", все изменения, внесенные локальным процессором, должны быть распространены на все остальные процессоры. Когерентность сохраняется. Операция "acquire" – это загрузка/чтение, выполняемая для доступа к критической секции. Операция "release" – это сохранение/запись, выполняемая для того, чтобы другие процессоры могли использовать общие переменные. Среди переменных синхронизации может поддерживаться последовательная согласованность или согласованность процессора. При использовании SC, все конкурирующие переменные синхронизации должны обрабатываться в порядке их следования. Однако, при использовании PC, только пара конкурирующих переменных должна следовать этому порядку. Более поздние "acquire" могут выполняться раньше более ранних "release".

Консистенция ввода

Это вариант модели согласованности при освобождении (release consistency). Он также требует использования инструкций захвата (acquire) и освобождения (release) для явного указания входа или выхода из критической секции. Однако, в модели согласованности при входе, каждой общей переменной присваивается своя собственная переменная синхронизации. Таким образом, при захвате переменной x, все операции, связанные с x, должны быть завершены относительно данного процессора. Это позволяет одновременно выполнять операции различных критических секций, работающих с разными общими переменными. Одновременность невозможна для критических операций, воздействующих на одну и ту же общую переменную. Такая модель согласованности будет полезна, когда различные элементы матрицы могут обрабатываться параллельно.

Местная согласованность

В локальной согласованности все копии ячейки памяти в конечном итоге становятся идентичными после завершения всех операций записи всеми процессами.

Расслабленно пишу, чтобы читать и пишу, чтобы писать

Некоторые модели еще больше ослабляют порядок выполнения программы, ослабляя даже ограничения на порядок между записями в различные адреса памяти. Модель частичного упорядочения записи SPARC V8 (PSO) является единственным примером такой модели. Ключевой аппаратной оптимизацией, обеспечиваемой PSO, является возможность конвейеризации и перекрытия записей в разные адреса с одного процессора. PSO аналогичен TSO в отношении требований к атомарности: он позволяет процессору читать значение собственной записи и предотвращает чтение другими процессорами записи другого процессора до того, как эта запись станет видимой для всех остальных процессоров. PSO поддерживает порядок программы между двумя записями с помощью явной инструкции STBAR. В реализациях с FIFO-буферами записи STBAR вставляется в буфер записи. Для определения момента завершения всех записей, предшествующих инструкции STBAR, используется счетчик, что инициирует запись в систему памяти для его увеличения. Подтверждение записи уменьшает счетчик, и когда счетчик достигает нуля, это сигнализирует о завершении всех предыдущих записей. В примерах А и В PSO допускает оба этих результата, не соответствующих последовательной консистентности. Гарантии безопасности, предоставляемые PSO, аналогичны гарантиям TSO: он обеспечивает порядок программы от записи к чтению и гарантирует атомарность записи. Как и в предыдущих моделях, ослабления, допускаемые PSO, недостаточно гибки для оптимизации компилятора, требующей гораздо большей гибкости.

Расслабляющий чтение и чтение для записи программных команд: Alpha, RMO и PowerPC

В некоторых моделях все операции, обращающиеся к разным адресам, ослаблены. Чтение или запись могут быть переупорядочены относительно другого чтения или записи, обращенных к другому адресу. Слабое упорядочение может быть отнесено к этой категории, а также к ней относятся два типа моделей консистентности освобождения (RCsc и RCpc). В рамках этой категории ослабления предлагаются три коммерческие архитектуры: Digital Alpha, SPARC V9 с ослабленным порядком памяти (RMO) и модели IBM PowerPC. Эти три коммерческие архитектуры используют явные инструкции-барьеры в качестве механизма обеспечения безопасности. Модель Alpha предоставляет два типа инструкций-барьеров: барьер памяти (MB) и барьер записи памяти (WMB). Операция MB может использоваться для сохранения порядка программы любых операций памяти, предшествующих MB, относительно операций памяти, следующих за барьером. Аналогично, WMB поддерживает порядок программы только для операций записи. Модель SPARC V9 RMO предоставляет инструкцию MEMBAR, которую можно настроить для упорядочения предыдущих операций чтения и записи относительно последующих операций чтения и записи. Для достижения этого порядка нет необходимости использовать операции чтения-модификации-записи, поскольку инструкция MEMBAR может использоваться для упорядочения записи относительно последующего чтения. Модель PowerPC использует единственную инструкцию-барьер, называемую SYNC. Она аналогична инструкции MB, но с одним небольшим исключением: чтение может выполняться вне порядка программы, даже если SYNC размещена между двумя чтениями в одном и том же адресе. Эта модель также отличается от Alpha и RMO с точки зрения атомарности. Она допускает видимость записи до завершения чтения. Для создания иллюзии атомарности записи может потребоваться комбинация операций чтения-модификации-записи. RMO и PowerPC допускают переупорядочение чтений к одному и тому же адресу. Эти модели нарушают последовательный порядок в примерах А и В. Дополнительное ослабление, допускаемое в этих моделях, заключается в том, что операции памяти, следующие за операцией чтения, могут быть перекрыты и переупорядочены относительно чтения. Alpha и RMO позволяют чтению возвращать значение ранней записи другого процессора. С точки зрения программиста эти модели должны поддерживать иллюзию атомарности записи, даже если они позволяют процессору читать собственную запись раньше, чем она будет завершена.

In some models, all operations to different locations are relaxed. A read or write may be reordered with respect to a different read or write in a different location. The weak ordering may be classified under this category and two types of release consistency models (RCsc and RCpc) also come under this model. Three commercial architectures are also proposed under this category of relaxation: the Digital Alpha, SPARC V9 relaxed memory order (RMO), and IBM PowerPC models. These three commercial architectures exhibit explicit fence instructions as their safety nets. The Alpha model provides two types of fence instructions, memory barrier (MB) and write memory barrier (WMB). The MB operation can be used to maintain program order of any memory operation before the MB with a memory operation after the barrier. Similarly, the WMB maintains program order only among writes. The SPARC V9 RMO model provides a MEMBAR instruction which can be customised to order previous reads and writes with respect to future read and write operations. There is no need for using read modify writes to achieve this order because the MEMBAR instruction can be used to order a write with respect to a succeeding read. The PowerPC model uses a single fence instruction called the SYNC instruction. It is similar to the MB instruction, but with a little exception that reads can occur out of program order even if a SYNC is placed between two reads to the same location. This model also differs from Alpha and RMO in terms of atomicity. It allows a write to be seen earlier than a read's completion. A combination of read modify write operations may be required to make an illusion of write atomicity. RMO and PowerPC allow reordering of reads to the same location. These models violate sequential order in examples A and B. An additional relaxation allowed in these models is that memory operations following a read operation can be overlapped and reordered with respect to the read. Alpha and RMO allow a read to return the value of another processor's early write. From a programmer's perspective these models must maintain the illusion of write atomicity even though they allow the processor to read its own write early.

Последовательность и воспроизведение

Tanenbaum et al., 2007 определяет две основные причины репликации: надежность и производительность. Надежность в реплицированной файловой системе может быть достигнута путем переключения на другую реплику в случае отказа текущей реплики. Репликация также защищает данные от повреждений, предоставляя несколько копий данных на различных репликах. Она также повышает производительность за счет распределения нагрузки. Хотя репликация может улучшить производительность и надежность, она может вызывать проблемы с согласованностью между несколькими копиями данных. Копии считаются согласованными, если операция чтения возвращает одно и то же значение со всех копий, а операция записи обновляет все копии как единая атомарная операция (транзакция) до выполнения любых других операций. Tanenbaum, Andrew, & Maarten Van Steen, 2007. В этой модели семантика согласованности приложения описывается с использованием конитов (consistency units) внутри приложения. Поскольку требования к согласованности могут различаться в зависимости от семантики приложения, Ю и Вахдат (2000) полагают, что предопределенная унифицированная модель согласованности может быть не самым подходящим подходом. Приложение должно указывать требования к согласованности, соответствующие его семантике. В этой модели приложение определяет каждое требование к согласованности как конит (сокращение от consistency units). Конит может представлять собой физическую или логическую согласованность и используется для измерения уровня согласованности. Tanenbaum et al., 2007 описывает понятие конита на примере. Существуют три типа несогласованности, которые приложения могут допускать. Отклонение в числовых значениях: числовое отклонение ограничивает разницу между значением конита и относительным значением последнего обновления. Вес может быть присвоен операциям записи, определяя их важность для конкретного приложения. Суммарный вес непросмотренных записей для конита может быть определен как числовое отклонение в приложении. Существуют два типа числового отклонения: абсолютное и относительное. Отклонение в порядке: отклонение в порядке – это расхождение между локальным порядком записей в реплике и их относительным порядком в конечном результате. Отклонение в устаревании между репликами: отклонение в устаревании определяет допустимость самой старой записи, ограничивая разницу между текущим временем и временем самой старой записи на коните, невидимой локально. Каждый сервер имеет локальную очередь неопределенных записей, для которых требуется определить и применить фактический порядок к кониту. Максимальная длина очереди неопределенных записей является границей отклонения в порядке. Когда количество записей превышает лимит, вместо принятия новых поступающих записей сервер попытается зафиксировать неопределенные записи, взаимодействуя с другими серверами на основе порядка, в котором записи должны быть выполнены. Если все три границы отклонения установлены в ноль, то модель непрерывной согласованности соответствует строгой согласованности.

Tanenbaum et al., 2007 defines two main reasons for replicating; reliability and performance. Reliability can be achieved in a replicated file system by switching to another replica in the case of the current replica failure. The replication also protects data from being corrupted by providing multiple copies of data on different replicas. It also improves the performance by dividing the work. While replication can improve performance and reliability, it can cause consistency problems between multiple copies of data. The multiple copies are consistent if a read operation returns the same value from all copies and a write operation as a single atomic operation (transaction) updates all copies before any other operation takes place. Tanenbaum, Andrew, & Maarten Van Steen, 2007 In this model, the consistency semantics of an application is described by using conits in the application. Since the consistency requirements can differ based on application semantics, Yu and Vahdat (2000) believe that a predefined uniform consistency model may not be an appropriate approach. The application should specify the consistency requirements that satisfy the application semantics. In this model, an application specifies each consistency requirement as a conit (abbreviation of consistency units). A conit can be a physical or logical consistency and is used to measure the consistency. Tanenbaum et al., 2007 describes the notion of a conit by giving an example. There are three inconsistencies that can be tolerated by applications. Deviation in numerical values Numerical deviation bounds the difference between the conit value and the relative value of the last update. A weight can be assigned to the writes which defines the importance of the writes in a specific application. The total weights of unseen writes for a conit can be defined as a numerical deviation in an application. There are two different types of numerical deviation; absolute and relative numerical deviation. Deviation in ordering Ordering deviation is the discrepancy between the local order of writes in a replica and their relative ordering in the eventual final image. Deviation in staleness between replicas Staleness deviation defines the validity of the oldest write by bounding the difference between the current time and the time of the oldest write on a conit not seen locally. Each server has a local queue of uncertain write that is required an actual order to be determined and applied on a conit. The maximal length of uncertain writes queue is the bound of ordering deviation. When the number of writes exceeds the limit, instead of accepting new submitted write, the server will attempt to commit uncertain writes by communicating with other servers based on the order that writes should be executed. If all three deviation bounds are set to zero, the continuous consistency model is the strong consistency.

Протоколы на основе первичных протоколов

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

Протоколы удаленной записи

В простейшем протоколе, основанном на ведущем сервере, поддерживающем репликацию, также известном как протокол "ведущий-резервный", операции записи перенаправляются на один сервер, а операции чтения могут выполняться локально. Например, Tanenbaum et al., 2007 приводит пример протокола "ведущий-резервный". На диаграмме протокола "ведущий-резервный" показан пример реализации этого протокола. Когда клиент запрашивает запись, запрос на запись пересылается на ведущий сервер. Ведущий сервер отправляет запрос на обновление резервным серверам. Затем сервер получает подтверждение обновления от всех резервных серверов и отправляет клиенту подтверждение завершения записи. Любой клиент может локально прочитать последнее доступное обновление. Недостатком этого протокола является то, что клиент, отправивший запрос на обновление, может быть вынужден долго ждать подтверждения, прежде чем продолжить работу. Эту проблему можно решить, выполняя обновления локально, а затем запрашивая резервные серверы выполнить свои обновления. Неблокирующий протокол "ведущий-резервный" не гарантирует согласованность обновления на всех резервных серверах. Однако он повышает производительность. В протоколе "ведущий-резервный" все процессы видят один и тот же порядок операций записи, поскольку протокол упорядочивает все входящие записи на основе глобально уникального времени. Блокирующие протоколы гарантируют, что процессы видят результат последней операции записи.

Протоколы локальной записи

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

Протоколы репликации

В протоколах реплицированного (или многократного) обновления, в отличие от протокола с первичной базой данных, все изменения применяются ко всем репликам.

Активная репликация

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

Протоколы, основанные на кворуме

Голосование может быть другим подходом в протоколах репликации записи. В этом подходе клиент запрашивает и получает разрешение от нескольких серверов для чтения и записи реплицированных данных. Например, предположим, что в распределенной файловой системе файл реплицируется на N серверах. Для обновления файла клиент должен отправить запрос как минимум N/2 + 1 серверам, чтобы получить их согласие на выполнение обновления. После достижения согласия изменения применяются к файлу, и обновленному файлу присваивается новый номер версии. Аналогично, для чтения реплицированного файла клиент отправляет запрос N/2 + 1 серверам, чтобы получить соответствующий номер версии от этих серверов. Операция чтения завершается, если все полученные номера версий соответствуют самой последней версии.

Протоколы кеширования

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