В информатике модель согласованности определяет контракт между программистом и системой, в котором система гарантирует, что если программист будет следовать правилам операций с памятью, память будет согласованной , а результаты чтения, записи или обновления памяти будут предсказуемо. Модели согласованности используются в распределенных системах, таких как распределенные системы с общей памятью или распределенные хранилища данных (например, файловые системы , базы данных , системы оптимистической репликации или веб-кэширование ). Согласованность отличается от согласованности, которая возникает в системах с кэшем или без него, и представляет собой согласованность данных по отношению ко всем процессорам. Когерентность связана с поддержанием глобального порядка, при котором записи в одно место или одну переменную видны всем процессорам. Согласованность связана с упорядочиванием операций в нескольких местах по отношению ко всем процессорам.
Языки высокого уровня , такие как C++ и Java , поддерживают контракт согласованности, преобразуя операции с памятью в операции низкого уровня таким образом, чтобы сохранять семантику памяти , переупорядочивая некоторые инструкции памяти и инкапсулируя необходимую синхронизацию с библиотечными вызовами, такими как pthread_mutex_lock(). [1]
Предположим, что имеет место следующий случай: [2]
Модель согласованности определяет, увидит ли клиент B запись, выполненную клиентом A, или нет, или не может зависеть от просмотра записи.
Модели согласованности определяют правила очевидного порядка и видимости обновлений и находятся в континууме компромиссов. [2] Существует два метода определения и классификации моделей согласованности; выпуск и просмотр.
Например, модель согласованности может определить, что процессу не разрешено выполнять операцию до тех пор, пока все ранее выполненные операции не будут завершены. Различные модели согласованности предусматривают разные условия. Одна модель согласованности может считаться более сильной, чем другая, если она требует всех условий этой модели и даже большего. Другими словами, модель с меньшим количеством ограничений считается моделью с более слабой согласованностью.
Эти модели определяют, как должно быть размещено аппаратное обеспечение, и на высоком уровне, как программист должен писать код. Выбранная модель также влияет на то, как компилятор может переупорядочивать инструкции. Как правило, если упорядочены зависимости управления между инструкциями и запись в одно и то же место, то компилятор может изменить порядок по мере необходимости. Однако в моделях, описанных ниже, некоторые могут разрешать переупорядочение операций записи перед загрузкой, а некоторые — нет.
Строгая согласованность — самая сильная модель согласованности. Согласно этой модели запись в переменную любым процессором должна быть мгновенно видна всем процессорам.
Диаграмма строгой модели и диаграммы нестрогой модели описывают ограничение по времени – мгновенное. Это можно лучше понять, как если бы существовали глобальные часы, в которых каждая запись должна отражаться во всех кэшах процессора к концу этого периода тактирования. Следующая операция должна произойти только в следующем такте.
Это самая жесткая модель. В этой модели каждый раз будет получен ожидаемый программистом результат. Это детерминированный подход. Его практическая значимость ограничивается мысленным экспериментом и формализмом, поскольку мгновенный обмен сообщениями невозможен. Это не помогает ответить на вопрос разрешения конфликтов при одновременной записи в один и тот же элемент данных, поскольку предполагает, что параллельная запись невозможна.
Модель последовательной согласованности была предложена Лэмпортом (1979). Это более слабая модель памяти, чем модель строгой согласованности. [3] Запись в переменную не обязательно должна происходить мгновенно, однако запись в переменные разными процессорами должна выполняться всеми процессорами в одном и том же порядке. Последовательная согласованность достигается, если «результат любого выполнения такой же, как если бы операции (чтения и записи) всех процессов в хранилище данных выполнялись в некотором последовательном порядке, и операции каждого отдельного процессора появляются в этой последовательности в порядок, указанный в его программе». [3] [4] Адве и Гарачорлоо, 1996 [5] определяют два требования для реализации последовательной согласованности; порядок программы и атомарность записи.
В последовательной согласованности нет понятия времени или последних операций записи. Есть некоторые операции чередования, одинаковые для всех процессов. Процесс может видеть операции записи всех процессов, но он может видеть только свои собственные операции чтения. Должен поддерживаться порядок программ внутри каждого процессора и последовательный порядок операций между процессорами. Чтобы сохранить последовательный порядок выполнения между процессорами, все операции должны выполняться мгновенно или атомарно по отношению к каждому другому процессору.
Эти операции должны только «казаться» завершенными, поскольку отправить информацию мгновенно физически невозможно. Например, в системе, использующей единственную глобально используемую шину, как только линия шины публикуется с информацией, гарантируется, что все процессоры увидят информацию в один и тот же момент. Таким образом, передача информации в линию шины завершает выполнение в отношении всех процессоров и выглядит так, как будто оно выполнено. Архитектуры без кэша или архитектуры с кэшированием и сетями межсоединений, которые не являются мгновенными, могут содержать медленный путь между процессорами и памятью. Эти медленные пути могут привести к последовательной несогласованности, поскольку некоторые памяти получают широковещательные данные быстрее, чем другие.
Последовательная согласованность может привести к недетерминированным результатам. Это связано с тем, что последовательность последовательных операций между процессорами может быть разной при разных запусках программы. Все операции с памятью должны выполняться в программном порядке.
Линеаризуемость [6] (также известная как атомарная согласованность или атомарная память) [7] может быть определена как последовательная согласованность с ограничением реального времени с учетом времени начала и окончания каждой операции. Выполнение является линеаризуемым, если каждая операция выполняется в линеаризуемом порядке путем размещения точки между временем начала и временем окончания и гарантирует последовательную согласованность.
Проверка последовательной согласованности посредством проверки модели в целом неразрешима , даже для протоколов когерентности кэша с конечным состоянием . [8]
Причинная согласованность [4], определенная Хатто и Ахамадом, 1990, [9], представляет собой ослабление модели последовательной согласованности за счет разделения событий на те, которые причинно связаны, и те, которые не являются таковыми. Он определяет, что только операции записи, которые причинно связаны, должны просматриваться всеми процессами в одном и том же порядке. Например, если событие b вступает в силу из более раннего события a, причинно-следственная согласованность гарантирует, что все процессы увидят событие b после события a. Таненбаум и др., 2007 дают более строгое определение: хранилище данных считается причинно-согласованным при следующих условиях: [4]
Эта модель ослабляет последовательную согласованность при одновременной записи процессором и при записи, не связанной причинно-следственной связью. Две записи могут стать причинно-следственными, если одна запись в переменную зависит от предыдущей записи в любую переменную, если процессор, выполняющий вторую запись, только что прочитал первую запись. Две записи могли быть выполнены одним и тем же процессором или разными процессорами.
Как и в случае с последовательной согласованностью, операции чтения не обязательно должны отражать изменения мгновенно, однако они должны отражать все изменения переменной последовательно.
W(x)2 происходит после W(x)1 из-за чтения, сделанного P2 в x до W(x)2, следовательно, этот пример является причинно последовательным согласно определению Хутто и Ахмада (хотя и не согласно Таненбауму и др., поскольку W(x)2 и W(x)3 не отображаются в одном и том же порядке для всех процессов). Однако R(x)2 и R(x)3 встречаются в разном порядке на P3 и P4, поэтому этот пример последовательно несовместим . [10]
Для обеспечения согласованности данных и создания масштабируемых процессорных систем, в которых каждый процессор имеет собственную память, была разработана модель согласованности процессоров . [10] Все процессоры должны быть согласованы в том порядке, в котором они видят записи, выполняемые одним процессором, и в том, как они видят записи, выполняемые разными процессорами в одно и то же место (связность сохраняется). Однако они не обязательно должны быть согласованными, если запись осуществляется разными процессорами в разные места.
Каждую операцию записи можно разделить на несколько подзаписей во все ячейки памяти. Чтение из одной такой памяти может произойти до завершения записи в эту память. Следовательно, считанные данные могут быть устаревшими. Таким образом, процессор ПК может выполнять более молодую нагрузку, когда необходимо остановить работу более старого хранилища. Порядок чтения перед записью, чтения после чтения и записи перед записью в этой модели по-прежнему сохраняется.
Модель согласованности процессора [11] аналогична модели согласованности PRAM с более строгим условием, определяющим, что все записи в одну и ту же ячейку памяти должны выполняться в одном и том же последовательном порядке всеми другими процессами. Согласованность процессора слабее, чем последовательная согласованность, но сильнее, чем модель согласованности PRAM.
Многопроцессорная система Stanford DASH реализует вариант согласованности процессора, который несравним (ни слабее, ни сильнее) с определениями Гудмана. [12] Все процессоры должны быть согласованы в том порядке, в котором они видят записи одним процессором, и в том, как они видят записи разными процессорами в одно и то же место. Однако они не обязательно должны быть согласованными, если запись осуществляется разными процессорами в разные места.
Конвейерная согласованность RAM (согласованность PRAM) была представлена Липтоном и Сэндбергом в 1988 году [13] как одна из первых описанных моделей согласованности. Из-за его неформального определения на самом деле существует как минимум две слегка разные реализации, [12] одна из которых принадлежит Ахамаду и др. и один от Мосбергера.
При согласованности PRAM все процессы просматривают операции одного процесса в том же порядке, в котором они были выполнены этим процессом, тогда как операции, выполняемые разными процессами, можно просматривать в разном порядке из разных процессов. Согласованность PRAM слабее, чем согласованность процессора. PRAM освобождает от необходимости поддерживать согласованность местоположения между всеми своими процессорами. Здесь чтение любой переменной может выполняться до записи в процессоре. Порядок чтения перед записью, чтения после чтения и записи перед записью в этой модели по-прежнему сохраняется.
Согласованность кэша [11] [14] требует, чтобы все операции записи в одну и ту же ячейку памяти выполнялись в некотором последовательном порядке. Согласованность кэша слабее, чем согласованность процессора, и несравнима с согласованностью PRAM.
При медленной согласованности [14] если процесс считывает значение, ранее записанное в ячейку памяти, он не может впоследствии прочитать любое более раннее значение из этой ячейки. Записи, выполняемые процессом, немедленно становятся видимыми для этого процесса. Медленная согласованность — более слабая модель, чем согласованность PRAM и кэша.
Пример. На диаграмме медленной памяти показан пример медленной согласованности. Первый процесс записывает 1 в ячейку памяти X, а затем записывает 1 в ячейку памяти Y. Второй процесс читает 1 из Y, а затем читает 0 из X, даже если X был записан до Y.
Хатто, Филлип В. и Мустак Ахамад (1990) [9] показывают, что при правильном программировании медленная память (последовательность) может быть выразительной и эффективной. Они отмечают, что медленная память имеет два ценных свойства; локальность и поддержка сокращения из атомарной памяти. Они предлагают два алгоритма, позволяющие выявить выраженность медленной памяти.
Эти четыре модели согласованности были предложены в статье 1994 года. Они сосредоточены на гарантиях в ситуации, когда только один пользователь или приложение вносит изменения в данные. [15]
Таненбаум и др., 2007 [4] определяют монотонную согласованность чтения следующим образом:
«Если процесс считывает значение элемента данных x, любая последовательная операция чтения x, выполненная этим процессом, всегда будет возвращать то же самое значение или более новое значение». [4]
Монотонная согласованность чтения гарантирует, что после того, как процесс прочитает значение элемента данных x в момент времени t, он никогда не увидит более старое значение этого элемента данных.
Условие монотонной согласованности записи определено Таненбаумом и др., 2007 [4] следующим образом:
«Операция записи процесса над элементом данных X завершается раньше, чем любая последующая операция записи в X, выполняемая тем же процессом». [4]
Значение, записанное процессом в элементе данных X, всегда будет доступно для последующей операции чтения, выполняемой тем же процессом в элементе данных X. [4]
При согласованности записи и чтения обновления распространяются после выполнения предыдущих операций чтения. Таненбаум и др., 2007 [4] определяют следующее условие согласованности операций записи и чтения:
«Операция записи процесса над элементом данных x, следующая за предыдущей операцией чтения x, выполненной тем же процессом, гарантированно выполняется с тем же или более поздним значением x, которое было прочитано». [4]
Следующие модели требуют специальной синхронизации со стороны программистов.
Слабый порядок классифицирует операции с памятью на две категории: операции с данными и операции синхронизации . Чтобы обеспечить порядок в программе, программисту необходимо найти в программе хотя бы одну операцию синхронизации. Операции синхронизации сигнализируют процессору о том, что он завершил и просмотрел все предыдущие операции, выполненные всеми процессорами. Порядок и атомарность программы поддерживаются только при операциях синхронизации, а не при всех операциях чтения и записи. Это было основано на понимании того, что определенные операции с памятью, например, выполняемые в критическом разделе, не обязательно должны быть видны всем процессорам до тех пор, пока все операции в критическом разделе не будут завершены. Предполагается, что переупорядочение операций памяти в областях данных между операциями синхронизации не влияет на результат программы. При этом используется тот факт, что программы, написанные для выполнения в многопроцессорной системе, содержат необходимую синхронизацию, чтобы гарантировать отсутствие гонок за данными и постоянное получение результатов SC. [16]
В этой модели согласованность не ослаблена. Как только эти требования будут выполнены, все остальные операции с данными можно будет переупорядочить. Это работает так: счетчик отслеживает количество операций с данными, и пока этот счетчик не станет нулевым, операция синхронизации не выполняется. Более того, больше никаких операций с данными не будет выполняться, пока не будут завершены все предыдущие синхронизации. Операции с памятью между двумя переменными синхронизации могут перекрываться и переупорядочиваться, не влияя на корректность программы. Эта модель гарантирует, что атомарность записи всегда сохраняется, поэтому для слабого упорядочения не требуется никакой дополнительной системы безопасности.
Чтобы поддерживать слабый порядок, операции записи перед операцией синхронизации должны выполняться глобально перед операцией синхронизации. Операции, присутствующие после операции синхронизации, также должны выполняться только после завершения операции синхронизации. Таким образом, доступ к переменным синхронизации является последовательным, и любое чтение или запись следует выполнять только после завершения предыдущих операций синхронизации.
В программе широко используется явная синхронизация. Для моделей со слабым упорядочением программист должен использовать инструкции атомарной блокировки, такие как проверка и установка, выборка и операция, условное сохранение, загрузка с привязкой, или должен маркировать переменные синхронизации или использовать ограничения.
Модель согласованности выпуска смягчает модель слабой согласованности, отличая операцию входной синхронизации от операции выходной синхронизации. При слабом упорядочении, когда операция синхронизации должна быть видна, все операции во всех процессорах должны быть видимы до того, как операция синхронизации будет завершена и процессор продолжит работу. Однако в соответствии с моделью согласованности выпуска во время входа в критический раздел, называемый «приобретением», все операции с переменными локальной памяти должны быть завершены. Во время выхода, называемого «освобождением», все изменения, внесенные локальным процессором, должны быть распространены на все остальные процессоры. Согласованность по-прежнему сохраняется.
Операция получения — это загрузка/чтение, выполняемая для доступа к критической секции. Операция освобождения — это операция сохранения/записи, выполняемая для того, чтобы другие процессоры могли использовать общие переменные.
Среди переменных синхронизации можно поддерживать последовательную согласованность или согласованность процессора. При использовании SC все конкурирующие переменные синхронизации должны обрабатываться по порядку. Однако в случае ПК пара конкурирующих переменных должна следовать только этому порядку. Младшие приобретения могут происходить до выпуска старых версий. [ нужна цитата ]
Существует два типа согласованности выпуска: согласованность выпуска с последовательной согласованностью (RCsc) и согласованность выпуска с согласованностью процессора (RCpc). Последний тип обозначает, какой тип согласованности применяется к операциям, обозначенным ниже как специальные.
Существуют специальные (ср. обычные) операции с памятью, которые сами по себе состоят из двух классов операций: операции синхронизации и операции nsync . Последние представляют собой операции, не используемые для синхронизации; первые являются и состоят из операций получения и выпуска . Получение фактически представляет собой операцию чтения памяти, используемую для получения доступа к определенному набору общих мест. С другой стороны, выпуск — это операция записи, которая выполняется для предоставления разрешения на доступ к общим местоположениям.
Для последовательной согласованности (RCsc) существуют следующие ограничения:
Для обеспечения согласованности процессора (RCpc) порядок записи и чтения в программе ослаблен, имея ограничения:
Примечание: приведенное выше обозначение A → B подразумевает, что если операция A предшествует B в порядке программы, то порядок программы применяется.
Это вариант модели согласованности релизов. Это также требует использования инструкций получения и выпуска для явного указания входа или выхода в критический раздел. Однако в соответствии с согласованностью записей каждой общей переменной назначается специфичная для нее переменная синхронизации. Таким образом, только когда получение осуществляется к переменной x, все операции, связанные с x, необходимо выполнить в отношении этого процессора. Это позволяет выполнять одновременные операции с разными критическими разделами разных общих переменных. Параллелизм невозможен для критических операций с одной и той же общей переменной. Такая модель согласованности будет полезна, когда разные элементы матрицы могут обрабатываться одновременно.
В локальной согласованности [14] каждый процесс выполняет свои операции в порядке, определенном его программой. Нет ограничений на порядок выполнения операций записи других процессов. Локальная согласованность — самая слабая модель согласованности в системах с общей памятью.
В целом, [17] все копии ячейки памяти в конечном итоге становятся идентичными после завершения записи всех процессов.
Итоговая согласованность [4] — это модель слабой согласованности в системе с отсутствием одновременных обновлений. Он определяет, что если никакое обновление не занимает очень много времени, все реплики в конечном итоге станут согласованными.
Большинство общих децентрализованных баз данных имеют модель конечной согласованности: BASE: в принципе доступна; мягкое состояние; в конечном итоге последовательный или комбинация ACID и BASE, иногда называемая SALT: последовательная; согласованный; ведомый; устойчивый к взлому, а также симметричный; без администратора; ведомый; и согласованное во времени. [18] [19] [20]
Некоторые различные модели согласованности могут быть определены путем ослабления одного или нескольких требований к последовательной согласованности , называемых моделями смягченной согласованности. [7] Эти модели согласованности не обеспечивают согласованность памяти на аппаратном уровне. Фактически, программисты отвечают за реализацию согласованности памяти, применяя методы синхронизации. Вышеуказанные модели классифицируются по четырем критериям и подробно описаны далее.
Есть четыре сравнения для определения расслабленной согласованности:
Последовательная согласованность имеет два требования: порядок программы и атомарность записи. Ослабляя эти требования, можно получить различные модели смягченной согласованности. Это сделано для того, чтобы вместе со смягчением ограничений увеличивалась производительность, но за реализацию согласованности памяти отвечает программист, применяя методы синхронизации, и он должен хорошо разбираться в аппаратном обеспечении.
Возможные послабления:
Подход к повышению производительности на аппаратном уровне заключается в ослаблении PO записи с последующим чтением, что эффективно скрывает задержку операций записи. Оптимизация, на которую опирается этот тип релаксации, заключается в том, что она позволяет последующим операциям чтения находиться в расслабленном порядке по отношению к предыдущим операциям записи из процессора. Из-за этого ослабления некоторые программы, такие как XXX, могут не давать результатов SC из-за этого ослабления. Принимая во внимание, что такие программы, как YYY, по-прежнему должны давать стабильные результаты из-за соблюдения оставшихся ограничений порядка программы.
В эту категорию попадают три модели. Модель IBM 370 — самая строгая модель. Чтение может быть завершено до более ранней записи по другому адресу, но возврат значения записи запрещен, если все процессоры не увидели запись. Модель общего порядка хранения SPARC V8 (TSO) частично ослабляет модель IBM 370, она позволяет чтению возвращать значение записи своего собственного процессора по отношению к другим операциям записи в то же место, т.е. она возвращает значение своей собственной записи до другие это видят. Как и в предыдущей модели, она не может вернуть значение записи, если все процессоры не увидели запись. Модель согласованности процессора (PC) является наиболее мягкой из трех моделей и ослабляет оба ограничения, так что чтение может завершиться раньше, чем более ранняя запись, даже до того, как оно станет видимым для других процессоров.
В примере A результат возможен только в IBM 370, поскольку чтение (A) не выдается до тех пор, пока в этом процессоре не завершится запись (A). С другой стороны, этот результат возможен в TSO и ПК, поскольку они позволяют читать флаги перед их записью в одном процессоре.
В примере B результат возможен только с ПК, поскольку он позволяет P2 вернуть значение записи еще до того, как оно станет видимым для P3. В двух других моделях это будет невозможно.
Чтобы обеспечить последовательную согласованность в приведенных выше моделях, используются сети безопасности или ограждения для ручного обеспечения соблюдения ограничений. Модель IBM370 имеет несколько специализированных инструкций сериализации , которые вручную помещаются между операциями. Эти инструкции могут состоять из инструкций памяти или инструкций, не связанных с памятью, например ветвей. С другой стороны, модели TSO и ПК не обеспечивают системы безопасности, но программисты все равно могут использовать операции чтения-изменения-записи, чтобы создать впечатление, будто порядок программы все еще сохраняется между записью и последующим чтением. В случае TSO, PO, по-видимому, сохраняется, если R или W, которые уже являются частью R-modify-W, заменяются R-modify-W, для этого требуется, чтобы W в R-modify-W была «пустышка», которая возвращает прочитанное значение. Аналогично для ПК, PO, похоже, сохраняется, если чтение заменяется записью или уже является частью R-modify-W.
Однако оптимизация компилятора не может быть выполнена только после этого расслабления. Оптимизация компилятора требует полной гибкости переупорядочения любых двух операций в PO, поэтому возможность переупорядочения записи относительно чтения в этом случае не является достаточно полезной.
Некоторые модели еще больше ослабляют порядок программы, ослабляя даже ограничения порядка между записью в разные места. Модель частичного заказа в магазине SPARC V8 (PSO) является единственным примером такой модели. Возможность конвейерной и перекрывающейся записи в разные места с одного и того же процессора является ключевой оптимизацией оборудования, обеспечиваемой PSO. PSO похож на TSO с точки зрения требований к атомарности, поскольку он позволяет процессору читать значение своей собственной записи и не позволяет другим процессорам читать запись другого процессора до того, как запись станет видна всем другим процессорам. Порядок программы между двумя операциями записи поддерживается PSO с помощью явной инструкции STBAR. STBAR вставляется в буфер записи в реализациях с буферами записи FIFO. Счетчик используется для определения момента завершения всех операций записи перед инструкцией STBAR, что запускает запись в систему памяти для увеличения счетчика. Подтверждение записи уменьшает счетчик, и когда счетчик становится равным 0, это означает, что все предыдущие записи завершены.
В примерах A и B PSO позволяет получить оба этих непоследовательно согласованных результата. Система безопасности, предоставляемая PSO, аналогична системе TSO: она устанавливает порядок выполнения программы от записи к чтению и обеспечивает атомарность записи.
Как и в предыдущих моделях, послабления, допускаемые PSO, недостаточно гибки, чтобы их можно было использовать для оптимизации компилятора, что требует гораздо более гибкой оптимизации.
В некоторых моделях все операции с разными местоположениями смягчены. Чтение или запись могут быть переупорядочены относительно другого чтения или записи в другом месте. Слабое упорядочение можно отнести к этой категории, и к этой модели также относятся два типа моделей согласованности выпусков (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 позволяют переупорядочивать операции чтения в одно и то же место. Эти модели нарушают последовательный порядок в примерах A и B. Дополнительное послабление, разрешенное в этих моделях, заключается в том, что операции памяти, следующие за операцией чтения, могут перекрываться и переупорядочиваться по отношению к чтению. Alpha и RMO позволяют чтению возвращать значение ранней записи другого процессора. С точки зрения программиста, эти модели должны поддерживать иллюзию атомарности записи, даже несмотря на то, что они позволяют процессору читать свою собственную запись раньше.
Модель транзакционной памяти [7] представляет собой комбинацию моделей когерентности кэша и согласованности памяти в качестве модели связи для систем с общей памятью, поддерживаемых программным или аппаратным обеспечением; Модель транзакционной памяти обеспечивает как согласованность памяти, так и согласованность кэша. Транзакция — это последовательность операций, выполняемых процессом, который преобразует данные из одного согласованного состояния в другое. Транзакция либо фиксируется при отсутствии конфликта, либо прерывается. При фиксации все изменения видны всем другим процессам после завершения транзакции, а при отмене все изменения отменяются. По сравнению с моделями смягченной согласованности транзакционная модель проще в использовании и может обеспечить более высокую производительность, чем модель последовательной согласованности.
Некоторые другие модели согласованности следующие:
Несколько других моделей согласованности были задуманы для выражения ограничений в отношении порядка или видимости операций или для устранения конкретных предположений об ошибках. [24]
Таненбаум и др., 2007 [4] определяют две основные причины репликации; надежность и производительность. Надежность в реплицируемой файловой системе можно обеспечить путем переключения на другую реплику в случае сбоя текущей реплики. Репликация также защищает данные от повреждения, предоставляя несколько копий данных на разных репликах. Это также повышает производительность за счет разделения работы. Хотя репликация может повысить производительность и надежность, она может вызвать проблемы согласованности между несколькими копиями данных. Множественные копии являются согласованными, если операция чтения возвращает одно и то же значение из всех копий, а операция записи в виде одной атомарной операции (транзакции) обновляет все копии до того, как произойдет какая-либо другая операция. Таненбаум, Эндрю и Маартен Ван Стин, 2007 г. [4] называют этот тип согласованности жесткой согласованностью, обеспечиваемой синхронной репликацией. Однако применение глобальной синхронизации для обеспечения согласованности всех копий обходится дорого. Одним из способов снизить стоимость глобальной синхронизации и повысить производительность может быть ослабление ограничений согласованности.
Таненбаум и др., 2007 [4] определяют модель согласованности как контракт между программным обеспечением (процессами) и реализацией памяти (хранилищем данных). Эта модель гарантирует, что если программное обеспечение следует определенным правилам, память работает корректно. Поскольку в системе без глобальных часов определение последней операции среди операций записи затруднено, могут применяться некоторые ограничения на значения, которые могут быть возвращены операцией чтения. Целью моделей согласованности, ориентированных на данные, является обеспечение единообразного представления хранилища данных, в котором процессы могут выполнять параллельные обновления.
Некоторые модели согласованности, такие как модели последовательной, а также модели причинно-следственной согласованности, учитывают порядок операций с общими реплицируемыми данными, чтобы обеспечить согласованность. В этих моделях все реплики должны согласовывать согласованный глобальный порядок обновлений.
При группировке доступ к переменным синхронизации осуществляется последовательно. Процессу разрешен доступ к переменной синхронизации, если все предыдущие записи были завершены. Другими словами, доступ к переменным синхронизации не разрешен до тех пор, пока все операции с переменными синхронизации не будут полностью выполнены. [4]
В распределенных системах важно поддерживать последовательную согласованность для управления параллельными операциями. В некоторых специальных хранилищах данных без одновременных обновлений модели согласованности, ориентированные на клиента, позволяют устранять несоответствия менее затратным способом. Следующие модели представляют собой модели согласованности, ориентированные на клиента: [4]
Реализация модели согласованности определяется протоколом согласованности. Таненбаум и др., 2007 [4] иллюстрируют некоторые протоколы согласованности для моделей, ориентированных на данные.
Непрерывная согласованность, введенная Ю и Вахдатом (2000). [25] В этой модели семантика согласованности приложения описывается с помощью конитов в приложении. Поскольку требования к согласованности могут различаться в зависимости от семантики приложения, Ю и Вахдат (2000) [25] считают, что предопределенная единая модель согласованности может оказаться неподходящим подходом. Приложение должно указать требования согласованности, удовлетворяющие семантике приложения. В этой модели приложение определяет каждое требование согласованности как conit (сокращение от единиц согласованности). Conit может быть физической или логической согласованностью и используется для измерения согласованности. Таненбаум и др., 2007 [4] описывают понятие конита, приводя пример.
Есть три несоответствия, которые могут быть допущены приложениями.
Если все три границы отклонения установлены равными нулю, модель непрерывной согласованности является сильной согласованностью.
Протоколы на основе первичных данных [4] можно рассматривать как класс протоколов согласованности, которые проще реализовать. Например, последовательный порядок является популярной моделью согласованности, когда рассматривается согласованный порядок операций. Последовательный порядок может быть определен как протокол на основе первичного. В этих протоколах для каждого элемента данных в хранилище данных существует связанный первичный объект для координации операций записи этого элемента данных.
В простейшем первичном протоколе, поддерживающем репликацию, также известном как протокол первичного резервного копирования, операции записи перенаправляются на один сервер, а операции чтения могут выполняться локально.
В протоколах локальной записи на основе первичного устройства [4] первичная копия перемещается между процессами, желающими выполнить обновление. Чтобы обновить элемент данных, процесс сначала перемещает его в нужное место. В результате при таком подходе последовательные операции записи могут выполняться локально, в то время как каждый процесс может читать свою локальную копию элементов данных. После того как первичная реплика завершит обновление, обновление пересылается на другие реплики, и все они выполняют обновление локально. Такой неблокирующий подход может привести к улучшению. Диаграмма протокола локальной записи отображает подход локальной записи в первичных протоколах. Процесс запрашивает операцию записи в элемент данных x. Текущий сервер считается новым основным для элемента данных x. Выполняется операция записи, и когда запрос завершается, основной отправляет запрос на обновление другим резервным серверам. Каждая резервная копия отправляет подтверждение основному после завершения операции обновления.
В протоколах реплицируемой записи [4] в отличие от первичного протокола все обновления выполняются для всех реплик.
При активной репликации [4] с каждой репликой связан процесс, выполняющий операцию записи. Другими словами, обновления отправляются каждой реплике в виде операции для выполнения. Все обновления необходимо выполнять в одном и том же порядке во всех репликах. В результате требуется полностью упорядоченный механизм многоадресной рассылки. При реализации такого механизма многоадресной рассылки в больших распределенных системах возникает проблема масштабируемости. Существует другой подход, при котором каждая операция отправляется центральному координатору (секвенсору). Координатор сначала присваивает каждой операции порядковый номер, а затем пересылает операцию всем репликам. Второй подход также не может решить проблему масштабируемости.
Голосование может быть еще одним подходом в протоколах реплицируемой записи. При таком подходе клиент запрашивает и получает разрешение от нескольких серверов на чтение и запись реплицированных данных. В качестве примера предположим, что в распределенной файловой системе файл реплицируется на N серверах. Чтобы обновить файл, клиент должен отправить запрос как минимум N/2 + 1 , чтобы дать согласие на выполнение обновления. После согласования изменения применяются к файлу и обновленному файлу присваивается новый номер версии. Аналогично, для чтения реплицированного файла клиент отправляет запрос на N/2 + 1 сервер, чтобы получить соответствующий номер версии от этих серверов. Операция чтения считается завершенной, если все полученные номера версий являются самыми последними. [4]
В реплицируемой файловой системе протокол согласованности кэша [4] обеспечивает согласованность кэша, тогда как кэши обычно контролируются клиентами. Во многих подходах согласованность кэша обеспечивается базовым оборудованием. Некоторые другие подходы в распределенных системах на основе промежуточного программного обеспечения применяют программные решения для обеспечения согласованности кэша.
Модели согласованности кэша могут различаться стратегиями обнаружения согласованности, которые определяют возникновение несогласованности. Существует два подхода к обнаружению несоответствия; статические и динамические решения. В статическом решении компилятор определяет, какие переменные могут вызвать несогласованность кэша. Таким образом, компилятор применяет инструкцию, чтобы избежать проблемы несогласованности. В динамическом решении сервер проверяет наличие несоответствий во время выполнения, чтобы контролировать согласованность кэшированных данных, которые изменились после их кэширования.
Стратегия обеспечения когерентности — это еще один протокол когерентности кэша. Он определяет , как обеспечить согласованность кэшей с помощью копий, расположенных на сервере. Один из способов обеспечить согласованность данных — никогда не кэшировать общие данные. Сервер может хранить данные и применять некоторый протокол согласованности, например первичные протоколы, для обеспечения согласованности общих данных. В этом решении клиенты могут кэшировать только частные данные. В случае кэширования общих данных существует два подхода для обеспечения согласованности кэша.
При первом подходе, когда общие данные обновляются, сервер отправляет информацию о недействительности во все кэши. При втором подходе распространяется обновление. Большинство систем кэширования применяют эти два подхода или динамически выбирают между ними.
Модель согласованности определяет правила видимости и видимый порядок обновлений. Пример: * Строка X реплицируется на узлах M и N * Клиент A записывает строку X в узел N * Проходит некоторый период времени. * Клиент B читает строку X из узла M * Видит ли клиент B запись от клиента A? Согласованность — это континуум с компромиссами