Не лги мне, как это тяжело!

Мои требования не высоки, просто переменная

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

a = 1
print(a+1)

Насколько это сложно? Переменная — это атомарный контейнер, что в нее кладется «до», а что вынимается «после». Отображение в память - это просто адрес памяти.

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

UPDATE order SET order_status="arrived" WHERE order_id=10234

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

SELECT order_status FROM order WHERE order_id=10234

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

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

if (amount >= 4) {
   amount = amount - 4
   return SUCCESS
} else {
   return FAILED
}

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

Что касается SQL, наши ожидания на самом деле очень низкие. Он также не требует многострочных транзакций. Когда требуется работать только с одной строкой, операция может быть атомарной. Например, SQL

UPDATE account SET amount = amount - 4 WHERE amount >= 4

Неужели такие высокие требования к БД? Совсем не высоко, правда? Это сложно? Очень сложно! Но если базовые данные не могут предоставить такую базовую гарантию, мы, программисты, пишущие бизнес-код, будем злиться и злиться.

абстрагироваться от проблемы

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

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

Подводя итог, требование, которое мы выдвигаем к базе данных, заключается в том, что нам нужно требование линеаризации. Эта потребность не может быть преувеличена. Смотрите также:Strong consistency models

Правая часть этого рисунка относится к задачам с несколькими переменными, а левая сторона — к задачам с одной переменной. Чтение и запись Linearizable — это самый высокий уровень требований к согласованности, который мы можем дать «переменной». Вы не можете зайти слишком далеко.

Я мало читаю, не ври мне

Подождите минуту. Нет такого базового поведения, как переменное. Например, как Java-программист, я знаю

volatile int a;
a = 1; // thread 1
System.out.println(a+1); // thread 2

Что Линеаризуемость, набор существительных. Смутил меня. Вы, высокопоставленные специалисты по инфраструктуре, умеете ли вы писать PPT?

Разве это не вопрос собеседования по Java? Установив volatile, вы можете гарантировать, что поток 1 запишет a, и по истечении этого времени любой другой поток, читающий a, сможет прочитать ранее записанное значение.

И в этом изменчивом нет ничего сложного. Говорят, что инструкция сборки sfence добавляется после записи volatile переменной. Инструкцию по сборке с mfence добавил перед прочтением (см.:Mechanical-sympathy.blogspot.com/2011/07/ Что…). В чем проблема?Это всего лишь две инструкции процессора.

Что касается CAS, разве это не java.util.concurrent.atomics.AtomicInteger.compareAndSet. Все условные записи можно свести к вызову этой функции.

Говорят, что базовым вызовом является блокировка ассемблерных инструкций cmpxchg. В чем проблема?Это просто инструкция процессора.

Но... как инструкции ЦП реализуют sfence, mfence и блокировку cmpxchg?

Welcome to the rabbit hole

С этим вопросом я долго гуглил. Я нашел еще два четких вступления:

Барьеры памяти: взгляд на аппаратное обеспечение для программных хакеров (скачать:Woohoo.R drop.com/~Пол покупает CK/генерирует…)
Справочник по информатике, 2-е изд., глава 19, автобус

Ебена мать. Наши программисты, занимающиеся разработкой бизнес-логики, очень наивны. a = 1, то print(a+1) действительно не так просто реализовать.

Сначала посмотрите на кусок простейшего кода бизнес-логики

doX() {
  a = 1
  a = a + 1
  b = 2
  b = b + 1
}

Просто как тот. Это простейшая последовательная логика без каких-либо ответвлений и циклов. Мы называем такую последовательную бизнес-логику непараллельной.

Однако бизнес-логика ложится на конкретный механизм исполнения, и процесс исполнения не обязательно «последовательный». Можно и параллельно. Это «не одновременно»! = «не параллельно».

Зачем? Потому что жизнь процессора непроста. Вы просите его сделать 1, 2, 3 и 4, и вы также просите людей быть очень быстрыми, что действительно сложно. Хитрое решение, найденное ЦП, состоит в том, чтобы поставить бизнес-логику неконкурентного и параллельного выполнения. Как это сделать?

a = 1
a = a + 1

Эта строка и следующие

b = 2
b = b + 1

Кажется, нет никакой связи. Ядро ЦП состоит из нескольких блоков, которые могут выполнять параллельные операции. Тогда разберитесь с этим самостоятельно. это называетсяCPU не по порядку выполнения.

Еще один фрагмент кода

a = 0
doX() {
  if (a == 0) { 
    a = a + 1 
  }
}
doY() {
  if (a == 0) {
     a = a + 2;
  }
}

Этот код является параллельным, поскольку doX и doY — это два независимых операционных процесса или две независимые бизнес-логики. Но «одновременно»! = «параллельно». (видетьblog.golang.org/concurrency…) параллелизм — это параллелизм в бизнес-логике. Однако фактический процесс выполнения не обязательно является параллельным. Например, такая последовательность выполнения

a = 0
doX() {
  if (a == 0) { // 第一步
    a = a + 1 // 第三步
  }
}
doY() {
  if (a == 0) { // 第二步
     a = a + 2; // 第四步
  }
}

Согласно приведенной выше последовательности выполнения, даже при наличии только одного ядра ЦП две части бизнес-логики могут выполняться «одновременно». Но после того, как первый шаг выполнит первую строку doX, почему мы можем перейти к функции doY? Разве функция не является «исключительно» ядром процессора?

Эксклюзивное ядро процессора, использующее параллельную реализацию параллельного выполнения, является схемой выполнения, но не единственной схемой выполнения. Язык программирования может полностью сохранить состояние после выполнения первой строки doX, затем переключиться на выполнение doY, затем переключиться обратно и сразу перейти ко второй строке doX для продолжения выполнения. Также известен как «сопрограммы».

Согласно порядку выполнения только сейчас, хотя только одно ядро процессора работает непараллельно. Но семантически две части бизнес-логики выполняются одновременно. Этот тип параллелизма вызывает проблему параллельного объекта. Потому что состояние a читается и записывается doX и doY одновременно. В соответствии с заданным порядком выполнения расчетный результат равен 3, а не 1 и не 2. То есть в так называемом коде есть параллельная ошибка.

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

Для чистого параллелизма, такого как выполнение ЦП не по порядку. Процессоры Intel x86 очень ответственны. По сути, вы можете думать, что ваша последовательная бизнес-логика действительно выполняется построчно. В большинстве случаев, как студенты, которые пишут бизнес-код, им не нужно заботиться об этих маленьких действиях за процессором. Однако ЦП, такие как arm, не так ответственны и разрушат линеаризуемость одной переменной и сериализуемость нескольких переменных из-за стремления к параллельному выполнению.

Линейное согласованное чтение параллельного объекта

Поскольку ЦП может быть достаточно умным, чтобы использовать неупорядоченное выполнение, параллелизм вводится сам по себе. Кроме того, гарантируется, что выполнение не по порядку не вызовет проблем с видимостью памяти. Поскольку это уже так хорошо, почему бы не «гладко» выполнить параллельную бизнес-логику на нескольких ядрах и не решить проблему видимости памяти, вызванную этим параллелизмом? Как насчет того, чтобы сделать все переменные линейно согласованными?

a = 0
doX() {
  a = 1;
}
doY() {
  print(a);
}

Для двух параллельных процессов выполнения doX и doY, пока doX «действительно» записывает 1 в адрес памяти a, а doY «действительно» считывает значение из адреса памяти a. Разве не реализовано «линейное последовательное чтение»?

Это то, что делают sfence и mfence. Но почему бы не добавить sfence и mfence ко всем операциям чтения и записи памяти?

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

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

По опыту использования БД эта проблема реализации очень большая:

Доступность: все ЦП успешно записываются. Если один процессор зависнет, то запись не будет неудачной.
Задержка: подождите, пока все процессоры обновят свои кэши. Насколько медленно писать переменную. Цена забора слишком высока.

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

Чтобы уменьшить задержку этой операции записи, вам нужно знать, где возникает задержка:

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

Так же, как ресторанный бизнес настолько хорош, что его нужно звать.

Как конструкторы ЦП решили проблему, что кеш слишком занят и не может вовремя обновляться? расстановка

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

На поверхности a = 1, print(a+1) простая запись и чтение адреса памяти, на самом деле на уровне многоядерного процессора используется передача сообщений, и все участники следуют одному и тому же протоколу MESI (который на самом деле не является такой же, как ваш обработчик http. Разница заключается в коде бизнес-логики, который отвечает на сообщение) для обеспечения согласованности памяти. Вы можете понять, что сеть RPC построена между многоядерными процессорами, предоставляя вам абстракцию, что адреса памяти могут быть прочитаны линейно.

Линейная непротиворечивая запись параллельного объекта

sfence и mfence тоже звучат не так уж плохо. Он просто выполняет некоторую синхронизацию с кешем. Как работает инструкция блокировки cmpxchg? CAS является краеугольным камнем линейного последовательного письма Как это достигается?

Согласно Справочнику по компьютерным наукам, 2-е изд., глава 19, автобус. Процесс на самом деле такой.

Самая простая реализация — выполнить блокировку cmpxchg как атома. Потому что системная шина гарантирует, что только одно ядро процессора может выполнять правильное выполнение в одно и то же время. Ядро процессора может заблокировать всю системную шину, затем выполнить блокировку cmpxchg, а затем разблокировать ее. Можно сказать, что он реализован с очень крупнозернистой пессимистичной блокировкой. Но это приведет к тому, что системная шина не сможет обслуживать другие задачи в течение длительного времени.

Поскольку степень детализации блокировки слишком велика, уменьшите степень детализации блокировки. Операция CAS разбивается на два этапа: чтение и блокировка и запись и разблокировка. Реализуйте на системной шине детализированную пессимистическую блокировку на уровне адресов.

Для того, нам нужны такие несколько обменов новостями

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

Итак, интересно то, что пессимистическая блокировка, предоставляемая операционной системой Linux, на самом деле реализуется оптимистической блокировкой на нижнем уровне (процессор, защищенный CAS, в настоящее время ранжируется в потоке в очереди выполнения). Оптимистическая блокировка ЦП в конечном итоге реализуется блокировкой системной шины на уровне адреса.

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

Расширение до распределенного параллельного объекта

В ходе предыдущего процесса спуска в кроличью нору мы узнали, что очень сложно добиться линейно-непротиворечивого чтения (sfence/mfence) и линейно-непротиворечивой записи ядра (CAS) в случае одномашинного многоядерного непостоянства.

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

Доступность: требуется, чтобы все были в сети, в результате чего общая доступность является продуктом индивидуальной доступности.
Задержка: Задержка зависит от самого медленного взаимодействия репликации.
Постоянство: Режим согласованности памяти ЦП не должен учитывать проблему зависания и восстановления памяти. А требование распределенного хранилища — не класть все яйца в одну корзину.
Нет системной шины: инструкции CAS в конечном итоге полагаются на блокировку адреса, реализованную шиной. В распределенной системе такого общего оборудования для этого нет.

Первые три пункта хороши. Это не что иное, как изменение алгоритма согласованности памяти ЦП, который требует, чтобы все ЦП подтверждали, и изменение его так, чтобы требовался ответ большинства. Будь то задержка, доступность или постоянство через несколько копий, это может быть решено этим большинством. Более того, алгоритм согласованности памяти ЦП также начал меняться по мере увеличения количества ядер ЦП, например:человек. Участвовал. Персик. Квота/Медколледж/пабы/Он…. В условиях увеличения числа ядер снижение задержки, вызванной согласованностью, также стало выгодным делом.

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

Настоящей проблемой является четвертый пункт. Нет общей системной шины для реализации блокировки адреса Как реализовать эту операцию CAS? Без CAS вообще невозможно реализовать безопасную запись в Concurrent Object (безопасность означает соответствие бизнес-логике). Вспомните реализацию CAS ЦП, которая на самом деле реализована в два этапа:

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

И Paxos, единственный правильный алгоритм распределенного консенсуса, состоит из двух шагов (это не случайно):

Подготовьтесь и пообещайте: получить значение и заблокировать его одновременно.
Предложить и принять: напишите значение

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

State is illusion, Log is reality

Я обнаружил, что лучшая перспектива для понимания алгоритмов распределенного консенсуса — установить правильное мировоззрение. То есть состояние — иллюзия, бревно — реальность.

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

Такой журнал имеет две записи изменений. В это время значение a равно 2.

На базе 2, потом -3. Тогда значение a становится -1.

С таким журналом у нас есть логическое понятие времени. То есть смещение каждой записи журнала.

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

Вернемся к нашему вопросу. CAS преследует две цели:

Чтение и блокировка: чтение детерминированной статической истории.
Напишите: Основываясь на этой истории, напишите мою ценность. Запись должна поддерживаться достаточным количеством узлов, чтобы быть успешной.

Это требование ложится на модель бревна. Это борьба за зачет. Например

Предположим, вы хотите написать offset5. В настоящее время это не может быть написано. Поскольку копия 1 и копия 3 все еще пусты по смещению4. То есть ваша история еще меняется. Значение по offset5 зависит от того, какие значения заполнены в этих двух дырках. Как offset5 может получить статическую историю, чтобы получить так называемую блокировку чтения (когда ваша история определена, это эквивалентно блокировке):

Подождите некоторое время и подождите, пока другие писатели закончат писать offset4
Ждать долго не выход, заполню offset4 ярлыком "отменено".

Когда все копии смещения до смещения 5 заполнили дыры. Затем можно гарантировать, что offset5 сможет уверенно читать историю, делать выводы на основе истории, а затем записывать изменения в позиции offset5.

На самом деле очень важно заполнить «пустые дыры всех копий». Более яркий способ сказать - «перемешать запись смещений перед смещением5», чтобы запись этих смещений не была успешной. Как я могу сделать эти офсетные записи неудачными?

Каждое смещение каждой реплики представляет собой отверстие, и это местоположение может быть записано только один раз.
Предполагая, что всего 10 копий, запись 3 будет успешной.
Затем подмешайте смещение к желтому, и оно никогда не будет успешным. Это должно заполнить соответствующие отверстия смещения 8 копий и аннулировать их. Таким образом, никогда не будет 3 дыр, заполненных ценностью. 3+8=11 больше 10

Итак, безопасный процесс записи CAS:

Предположим, всего N копий
Чтобы записать смещение I, поставьте позиции [0, I-1] всех смещений перед I и заполните аннулирование R копий. Убедитесь, что прошлая история статична.
Читайте журналы прошлой истории. Определите, какое значение должно быть записано в текущее смещение.
Запись текущего значения смещения от I до W копий, после чего запись завершается успешно и возвращается вызывающей стороне.
Требуется R + W > N

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

Надеюсь прояснить Паксос.

Суммировать

100% данные не теряются при необходимости. Очень сложно и требовательно добиться линейно-непротиворечивого чтения (SQL передается и может быть найден с помощью следующего SQL-запроса) и линейно-непротиворечивой записи (когда строка SQL и читается, и записывается). Потому что, чтобы никогда не терять обновления, база данных должна использовать multi-paxos или raft для достижения линейной согласованности однострочных данных (не говоря уже о проблеме ACID, связанной с изменениями многострочных данных).

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

Большинству предприятий не требуется 100% потеря данных.Однострочные данные или линейно последовательное чтение и запись одной переменной можно выполнить, и это несложно.