предисловие

В распределенных системах (базах данных) мы часто слышим некоторые «высокие», но «запутанные» слова, например, одно и то же значение «C» в ACID и CAP, Snapshot Isolation (SI) и Serializable. В чем разница между Snapshot Isolation (SSI), Serializable и Linearizable означают одно и то же, а как насчет согласованности и консенсуса? Если вы не можете четко ответить на эти вопросы, то, надеюсь, эта статья вам поможет.

Согласованность ACID и CAP

Кислота и крышка C являются последовательностью является аббревиатурой, но их значение отличается. Атомальность кислоты, включающая (атомность), консистенцию (согласованность), долговечность (постоянство), изоляцию (изоляция) Четыре аспекта, в котором атомность (атомачность), долговечность (настойчивость) и изоляция (изоляция) хранятся способность защищать при условии , но механизм хранения консистенции (консистенции) не предусмотрен, наоборот, это логическое ограничение уровня бизнеса для передачи наиболее классического примера этого с точки зрения 100 юаней RMB, B 0 юаней RMB, теперь передается на до B 50 юаней RMB, поэтому до и после передачи общее количество A и B должно быть деньги или 100 юаней RMB, очевидно, это только логические ограничения, определяемые только сервисным слоем. В «DDIA» книга на кислоте также имеет следующее описание:

CAP — это аббревиатура Consistency, Availability and Partition Устойчивость. Согласованность здесь на самом деле больше соответствует нашему более интуитивному пониманию согласованности. Она представляет собой своего рода «свежесть данных». «Степень» гарантия, то есть «когда» правильные» данные могут быть прочитаны. Непротиворечивость здесь означает Linearizability Consistency (линейная согласованность).Кроме того, наши общие модели согласованности включают Sequential Consistency (последовательная согласованность) и Casual Consistency (причинно-следственная согласованность) и т. д., которые будут выделены в следующих разделах. В книге "DDIA" также есть некоторые введения в CAP, которые размещены здесь в качестве вспомогательных инструкций:

Последовательность и консенсус

Что смущает Последовательность и Консенсус, так это не их значение, а то, что они выглядят «похожими».На самом деле, пока они переведены на китайский язык, их легко понять. Непротиворечивость означает «непротиворечивость» (что уже неоднократно упоминалось ранее), а «Консенсус» означает «консенсус». В инженерии непротиворечивость означает «когда» вы можете прочитать «правильные» данные.Обычными из них являются Linearizability Consistency (линейная согласованность), Sequential Consistency (последовательная согласованность) и Casual Consistency (причинно-следственная согласованность). Консенсус в основном относится к алгоритму «консенсуса», то есть несколько сторон участвуют в совместном принятии решения. Например, алгоритм Basic Paxos можно использовать для определения значения в группе распределенных узлов (например, в основной операции выборов). . Конечно, непротиворечивость и консенсус не полностью связаны друг с другом.Многие модели согласованности также будут использовать алгоритм консенсуса для завершения.

Сериализуемый и линеаризуемый

Serializable и Linearizable, пожалуй, два самых запутанных понятия. Serializable буквально переводится как «сериализация», а Linearizable буквально переводится как «линеаризация». На первый взгляд они похожи, но на самом деле это два совершенно разных аспекта. Чтобы интуитивно увидеть их отношения, обратитесь к картинке с официального сайта jepsen:

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

следовательно,Так называемая строгая сериализуемая (настоятельно согласованная) модель состоит в том, чтобы удовлетворить как сериализуемые, так и линеаризуемые, то есть все транзакции выполняются в соответствии с уровнем изоляции сериализации (Примечание: это не обязательно верно для сериализованного исполнения, но конечный эффект и некоторые виды сериализованного исполнения. Тай же эффект), а также можно сразу прочитать «исправить» (Примечание: правильно означает, что самые последние письменные данные объекта могут быть считываться немедленно) Модель согласованности данных, а Serializable Snapshot Isolation (SSI) удовлетворяет только Serializable, но не имеет семантики Linearizable, то есть удовлетворяет только последовательное выполнение транзакций в определенном порядке, но не может сразу считывать «правильные» данные. Поскольку Linearizable представляет модель согласованности, а Serializable представляет собой уровень изоляции транзакций, нижеследующее будет описано отдельно от двух аспектов «согласованности» и «изоляции».

последовательность

Непротиворечивость — не новая концепция распределенных баз данных, напротив, непротиворечивость существует в каждом уголке компьютера. Например, существует проблема согласованности между кэшами многоядерных процессоров, а также проблема согласованности памяти между несколькими потоками в параллельном программировании. В этой статье в качестве примера будет взято обычное многопоточное программирование, основное внимание будет уделено концепциям и различиям между Linearizability Consistency (линейная согласованность), Sequential Consistency (последовательная согласованность) и Casual Consistency (причинно-следственная согласованность). Модель согласованности в распределенном точно такая же.

Линеаризуемость

Линеаризуемость Постоянство требует двух:

• Любое чтение может прочитать последние записанные данные определенных данных.

• Все процессы в системе видят порядок операций в том же порядке, что и глобальные часы.

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

Последовательная согласованность

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

• Порядок всех процессов в системе последователен и разумен, то есть в любом процессе должен поддерживаться порядок чтения и записи процесса в одну и ту же переменную, и тогда все сформируют консенсус.

• Это не обязательно должно соответствовать порядку глобальных часов.

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

Цитирование изображения из «Распределенные вычисления - принципы, алгоритмы и системы», чтобы дополнительно проиллюстрировать разницу между согласованностью линеаризуемости (линейная согласованность) и последовательной согласованностью (последовательная согласованность):

• Фиг.8 удовлетворяет последовательной консистенции (идентичность последовательности), но не выполняет консистенцию линейности (линейную консистенцию). Причина в том, что с точки зрения глобальных часов, переменные процесса P2 X Read Process Reading после переменных процесса P1 X пишет, но читается из старых данных. Но эта цифра удовлетворена последовательной консистенцией (последовательной консистенцией), поскольку два процесса P1, P2 согласованность и нет конфликта. От угла зрения обоих процессов последовательность должна быть такой, что: запись (y, 2), чтение (x, 0), запись (x, 4), чтение (y, 2), в каждом процессе читает писать Заказ разумно, но ясно видеть, что порядок под порядком глобальных часов не то же самое.

• Рисунок b удовлетворяет непротиворечивости линеаризуемости (линейной согласованности), потому что каждая операция чтения считывает результат последней записи переменной, а порядок операций, видимых двумя процессами, такой же, как порядок глобальных часов, оба Write(y ,2 ), Чтение(x,4) , Запись(x,4), Чтение(y,2).

• Рисунок c не удовлетворяет Sequential Consistency (последовательной согласованности) и, конечно же, не удовлетворяет Linearizability Consistency (линейной согласованности). Потому что с точки зрения процесса P1 его операция чтения переменной Y вернула результат 0. Другими словами, операция чтения переменной Y процессом P1 предшествует операции записи переменной Y процессом P2, что означает, что порядок, который он считает, таков: write(x,4), Read(y ,0) , Write(y,2), Read(x,0) Очевидно, что этот порядок не может быть выполнен, потому что последняя операция чтения переменной x считывает старые данные. Следовательно, этот порядок является конфликтным и не удовлетворяет последовательной непротиворечивости.

Повседневная последовательность

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

• Локальный порядок: в этом процессе порядок, в котором выполняются события, является локальным причинным порядком.

• Неуместный порядок: если операция чтения возвращает значение операции записи, то операция записи должна предшествовать операции чтения по порядку.

• Передача замыкания: как определено в векторе часов, если a->b, b->c, то должно быть a->c.

Чтобы еще больше проиллюстрировать разницу между случайной согласованностью и последовательной согласованностью, процитируйте диаграмму в книге «Распределенные вычисления — принципы, алгоритмы и системы»:

• График a удовлетворяет последовательной непротиворечивости и, следовательно, случайной непротиворечивости, потому что с точки зрения четырех процессов в этой системе все они имеют одинаковый порядок и одинаковую причинность.

• Рисунок b удовлетворяет случайной согласованности, но не последовательной согласованности. Во-первых, нет причинно-следственной связи между записью P1 и P2.С точки зрения P3 чтение (x, 7) означает, что запись (x, 7) P2 должна быть до чтения (x, 7) P3. , и Read(x,7) из P3 2) Это означает, что Write(x,2) из ​​P1 должен быть до Read(x,2) из ​​P3, и поскольку Read(x,7) из P3 предшествует Read(x ,2) (локальный причинный порядок), поэтому с точки зрения P3 порядок выполнения P1 и P2 должен быть: Запись(x,7), Запись(x,2), Запись(x,4). Используя тот же метод анализа, можно сделать вывод, что с точки зрения P4 порядок выполнения P1 и P2 должен быть следующим: Write(x,2), Write(x,4), Write(x,7). Это не удовлетворяет требованию последовательной согласованности, поскольку порядок выполнения, видимый P3 и P4, несовместим.

• На рисунке c показана модель согласованности, которая слабее, чем повседневная согласованность: конвейерная память PRAM (конвейерная оперативная память), которая представляет собой академический отчет «PRAM: масштабируемая общая память» Липтона и Сандберга в 1988 году, предложенный в . Как упоминалось ранее, последовательная согласованность требует, чтобы порядок выполнения программы, наблюдаемый всеми процессами, был согласованным, в то время как случайная согласованность снижает требование согласованности, которое требует, чтобы причинно-следственные операции были видны во всех процессах. снижает требования к согласованности. Сначала взгляните на определение PRAM: «…Записи, выполненные одним процессом, принимаются всеми другими процессами в том порядке, в котором они были отправлены, но записи из разных процессов могут восприниматься разными процессами в другом порядке». в PRAM разные процессы Вы можете видеть разные порядки выполнения, но несколько операций записи в процессе должны отображаться в одном и том же порядке во всех процессах, в то время как операции записи в разных процессах могут выполняться в разных процессах в разном порядке. Для примера, показанного на рисунке c, последовательность операций P1 и P2, рассматриваемая с точки зрения P3, такова: запись (x, 2), запись (x, 4), чтение (x, 4), запись (x, 7). , Удовлетворяет казуальной согласованности. С точки зрения P4: Write(x,2), Read(x,4), Write(x,7), Write(x,4), что явно не соответствует требованиям случайной согласованности.

Как видно из рисунка на официальном сайте jepsen, Casual Consistency (причинно-следственная согласованность) и PRAM также включают в себя такие модели согласованности, как Writes Follow Reads, Monotonic Reads, Monotonic Writes, Read Your Writes и т. д. Они относительно просты из-за космические причины, в этой статье мы их повторять не будем.

изоляция

Как упоминалось ранее, Serializable — это уровень изоляции транзакций (между параллельными транзакциями), что и означает изоляцию в ACID. Однако вначале было всего 4 уровня изоляции для ACID Isolation.С развитием технологий появилось много новых уровней изоляции, которые не были определены первоначальным стандартом, например изоляция моментальных снимков. В следующей таблице подробно описаны 6 уровней изоляции. Сила каждого уровня изоляции прогрессивна, но также существуют или появляются некоторые новые проблемы. Взяв в качестве примера изоляцию моментальных снимков, она может решить проблему фантомного чтения повторяющегося чтения, но это не так. не существует проблемы перекоса записи.

Следующий рисунок более четко отражает соотношение прочности каждого уровня изоляции.

Различные исключения изоляции описаны ниже.

Перед этим определим несколько понятий:

• Долгосрочные блокировки: блокировки, которые снимаются в конце транзакции.
• Кратковременные блокировки: блокировки, которые снимаются после завершения связанных операций с данными.

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

P0 грязная запись

Феномен: На ​​начальном этапе все может происходить без каких-либо блокировок, поэтому первая проблема, с которой приходится сталкиваться, — это грязное письмо. Грязные записи происходят, когда одна транзакция перезаписывает значение, записанное другой выполняющейся транзакцией. Например, в следующем примере ограничение согласованности транзакции состоит в том, что x должен быть равен y, а начальное значение x и y в начале равно 0, тогда транзакция T1 готова записать x=y=1 и транзакция T2 готова записать x=y= 2, но поскольку ни T1, ни T2 не блокируют данные, происходит перезапись (грязная запись) друг друга, что приводит к успешной фиксации, x==2, y==1, что нарушает условия привязки.

Решение. Держите долгосрочные блокировки записи на x и y (блокировки не снимаются до фиксации), чтобы последующий T2 не мог перезаписать x, а T1 не мог перезаписать y. В будущем появится новое явление, грязное чтение, чтобы предотвратить грязную запись.

Грязное чтение P1 (грязное чтение, незафиксированное чтение)

Симптом. Грязные операции чтения происходят, когда одна транзакция считывает значение, записанное другой транзакцией, которая все еще выполняется (не зафиксирована). Например, в следующем примере условием ограничения согласованности транзакций является x + y = 100. В начале начальные значения x и y равны 50. Транзакция T1 планирует переписать x на 10 (добавление длинного блокировка записи термина). В это время транзакция T2 считывает x равно 10 (блокировка не добавляется), считывает y равно 50, для транзакции T2 x+y=60 не удовлетворяет условию привязки.

Решение: в реализации на основе блокировок используются краткосрочные блокировки чтения и долгосрочные блокировки записи.Долгосрочные блокировки записи могут предотвратить чтение транзакцией T2 x прочитанных данных, а краткосрочные блокировки чтения могут позволить продолжить выполнение последующих T1. писать ю. Чтобы решить проблему грязных чтений, нужно столкнуться с проблемой неповторяющихся чтений.

P2 не повторяемый читаемый (не повторяемый чтение)

Явление: Это исключение может существовать после того, как фиксация чтения реализована с использованием краткосрочных блокировок чтения и долгосрочных блокировок записи. Например, в следующем примере условием ограничения согласованности транзакций является x + y = 100. В начале начальные значения x и y равны 50, и T1 считывает x как 50 (добавьте краткосрочное чтение lock на x), а затем транзакция T2 устанавливает x и y на 50. y был изменен (долгосрочные блокировки записи добавлены к x и y), а затем успешно отправлен. После этого T1 считывает y как 90. В это время для T1 x+y=140 не удовлетворяет условию ограничения, поэтому происходит неповторяющееся считывание. (Примечание. Поскольку T2 в это время зафиксирован, так что это не грязное чтение без фиксации, обратите внимание, чтобы отличить его от приведенного выше примера. В то же время также обратите внимание, что многие люди думают, что невозможно прочитать то же самое. объект несколько раз с разными значениями. Повторное чтение на самом деле является узким пониманием. На самом деле, разные объекты могут быть прочитаны несколько раз, если многократное чтение изменит ограничения согласованности, даже если они не являются повторяемым чтением)

Решение. В реализации на основе блокировок используются долгосрочные блокировки чтения и долгосрочные блокировки записи, то есть x транзакции T2 не может быть записано до тех пор, пока транзакция T1 не будет зафиксирована. После решения неповторяемого чтения фантомное чтение все равно будет встречаться.

Фантом P3 (фантомное чтение)

Явление: Фантомное чтение происходит, когда выполняющаяся транзакция T1 имеет чтение утверждения (например, select where), а другая транзакция T2 выполняет операцию вставки, которая пересекается с набором утверждений. Например, T1 читает, что общее количество сотрудников равно 3 до того, как T2 вставит d, но есть пересечение, когда выполняется T2 и вставляются новые данные d. В это время общее количество сотрудников равно 4, но если T1 прочитает его еще раз, обнаружится, что общее количество сотрудников изменилось, оно становится 4 вместо исходных 3, что является фантомным чтением.

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

Обновление P4 потеряно

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

Явление: Запись, зафиксированная транзакцией T2, перезаписывается другими транзакциями. Во-первых, это не грязная запись, потому что T2 была зафиксирована, а во-вторых, грязного чтения нет, потому что после записи нет операции чтения. Это явление называется потерял обновление.

Решение: просто перейдите на повторяемое чтение.

Обновление курсора P4C потеряно

Явление: потерянное обновление курсора — это вариант упомянутого выше потерянного обновления, который связан с курсором SQL. В приведенном ниже примере RC(x) означает чтение x под курсором, а WC(x) означает запись x под курсором. Если T2 разрешено записывать данные между RC и WC T1, то обновления T2 также будут потеряны.

Решение: Блокировка не снимается до тех пор, пока курсор не будет перемещен или отпущен.Это эпизод до того, как будет достигнуто повторяемое чтение. Это также происходит после реализации read commit.

A5A перекос чтения

Частичное можно понимать как несоответствие, возникающее при наличии общего ограничения между несколькими данными (логические ограничения на уровне бизнеса).

Феномен: показания также возможны в достижении команды чтения. Предположим, что текущее ограничение - x + y = 100, транзакция t1 сначала прочитала x составляет 50 (T1 Pair x плюс краткосрочный замок с чтением), то транзакция T2 будет переписана как 25 (T2 Pair X Plus Long Bloam), будет Переписан 75 (T2 Pair X расширенного письма), для транзакции T2, X + Y = 100 удовлетворяет, поэтому его можно успешно отправить. T2 успешно отправлен (все замки также выпущены), а T1 все еще работает, T1 READ Y - 75, X + Y> 100, не удовлетворяет ограничению.

Решение: используйте изоляцию снэпшотов, основанную на MVCC. Когда начинается транзакция T, T получает абстрактную временную метку (версию) При чтении данных x он видит не непосредственно последние записанные данные, а все выполнения до начала T Последняя отмеченная версия X в транзакции (если T изменяет x, он видит свою версию). То есть T работает на основе последнего образа текущей базы данных, и версия, полученная при запуске T, является сертификатом этого моментального снимка. Это гарантирует, что все чтения извлекаются на основе согласованного состояния.

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

В приведенном здесь примере y для T1 будет считывать только начальную версию, которая равна 50, а не 75, поэтому ошибка чтения устранена. Однако изоляция снэпшотов по-прежнему не может решить другую проблему — предвзятость записи. Это наша новая проблема.

A5B перекос записи

Феномен: это похоже на предвзятость чтения, за исключением того, что это несоответствие на уровне бизнес-логики. Транзакции T1 и T2 имеют свои версии в начале: T1 читает x как 30 и изменяет y с 10 на 60. С точки зрения самого T1 ограничение (x+y

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

Например, если T1 записывает версию Yeng после чтения Y, зависимости RW (Y), которые читаются после чтения, аналогичные пары T2 T1 составляют зависимость RW (X) первого чтения. Существует два вида безвредной зависимости: чтение (WR) и запись после записи (WW). Документ описан, в результате чего условие списания является кольцевым, и в кольце есть две последовательные RW-зависимости. То есть следующая форма.

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

Это условие заключается в отказе от коммита до тех пор, пока есть две последовательные зависимости rw, даже если нет цикла. Эта проверка происходит при чтении. Если обнаруживается, что прочитанная версия несовместима с версией до ее запуска, она найдет зависимую транзакцию, построит входящее ребро, а другая транзакция построит исходящее ребро. Если транзакция имеет ребро rw на его входящих и исходящих ребрах этот узел будет использоваться как подозрительный. Конечно, есть и другие документы по изоляции Serializable Snapshot Isolation (SSI), на которые вы можете ссылаться.

Суммировать

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