изменять:blog.CSDN.net/Это стерто/art IC…
Последовательный анализ согласованности
2017 Ele.me, чтобы делать больше живых выступлений в разных местах, моя команда берет на себя трансформацию большего количества живых выступлений в разных местах ZooKeeper. За это время я услышал 2 разных заявления о согласованности.
-
Один из аргументов заключается в том, что ZooKeeper обеспечивает согласованность в конечном итоге, потому что из-за нескольких реплик и протокола Zab, который гарантирует наибольший успех, когда один клиентский процесс записывает новое значение, другой клиентский процесс не может гарантировать, что значение будет прочитано немедленно, но это гарантировано. что это значение может быть прочитано в конце концов.
-
Другой способ сказать, что протокол Zab ZooKeeper похож на протокол Paxos и обеспечивает строгую согласованность.
Всякий раз, когда я слышу эти два утверждения, я хочу их исправить: «Нет, ZooKeeper — это последовательная согласованность».
Но это слишком сложно для объяснения, и для объяснения требуется длинная статья. Я всегда хотел написать эту статью, чтобы объяснить это утверждение, но я не написал ее.Прошло так много времени с тех пор, как закончился проект Ele.me по мультижилью за пределами сайта, я наконец-то нашел время, чтобы написать его и обсудить это со всеми.
Из документации ZooKeeper мы видим, что в документации ZooKeeper четко указано, что его согласованность является последовательной согласованностью (см. справочную ссылку в конце статьи).
Что такое последовательная согласованность?
Последовательная согласованность впервые была предложена Лэмпортом в 1979 году. (См. его статью Как сделать многопроцессорный компьютер, который правильно выполняет многопроцессорные программы) Как определено в статье, последовательная непротиворечивость достигается при соблюдении следующих условий:
the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.
Это английское определение очень неясное (это стиль ломпортского бога, строгого, но неясного, как и протокол Паксос), когда я впервые увидел это определение, возникло ощущение: «Что это, черт возьми, такое?». Почему я знаю каждое английское слово, но я просто не знаю, о чем он говорит. Когда я впервые увидел это предложение, маленькие друзья, которые чувствовали то же, что и я, подняли руки.
Позже в этой статье я переведу это английское определение на китайский.Теперь давайте взглянем на ключевое слово, которое появляется в заголовке и определении этой статьи, чтобы проиллюстрировать область применения последовательной непротиворечивости. Название статьи и это определение содержат слово multiprocessor, что означает многопроцессорность.
С точки зрения этого ключевого слова, последовательная согласованность — это функция, используемая для определения нескольких процессоров и программ, работающих на нескольких процессорах. Название статьи Ломпорта можно перевести как «Как заставить компьютер с несколькими процессорами правильно выполнять многопроцессорные программы», что означает, что если многоядерный процессор обладает характеристиками последовательной согласованности, многоядерный процессор может работать правильно, а позже мы объясним, что означает эта правильная операция (то есть роль последовательной согласованности, упомянутая далее в этой статье). Из этого заголовка мы также можем видеть, что последовательная согласованность должна быть концепцией в области параллельного программирования.
Но мы часто обсуждаем последовательную согласованность в области распределенных систем, например, в этой статье в основном обсуждается согласованность Zookeeper (Zookeeper, очевидно, является распределенной системой). На самом деле несколько программ, работающих на многоядерном процессоре, на самом деле представляют собой распределенную систему (новаторская работа Ломпорта по распределенным системам в его книге «Время, часы и порядок событий в распределенной системе»).
Таким образом, хотя последовательная согласованность была впервые предложена в параллельном программировании, ее можно применять в распределенных системах, таких как распределенная система хранения данных Zookeeper, обсуждаемая в этой статье. Другая более важная линеаризуемость (линейная непротиворечивость) была впервые предложена в параллельном программировании, а также широко используется в области распределенных систем.
Теперь давайте переведем неясное определение выше. Выполнение перевода этого определения дало мне ощущение понимания прочитанного в школе. Я не буду переводить это напрямую, потому что, даже если я переведу это на китайский язык, я думаю, что многие люди все равно не поймут, что это значит. У меня все еще есть это чувство, потому что я понимаю каждое китайское слово, обозначающее Мао, но я все еще не знаю, о чем он говорит.
Во-первых, позвольте мне объяснить некоторые отдельные слова. Первый, любая казнь, что значит любая казнь? У вас есть несколько программ, работающих на многоядерном процессоре, например, у вас есть 2 программы,
第一个程序叫 P1，它的代码如下：
P1_write(x);
P1_read(y);
第二个程序叫 P2，代码如下：
P2_write(u);
P2_read(v);
Теоретически, сколько возможностей выполнения существует для 2 программ, работающих на 2 отдельных процессорных ядрах? Я привожу некоторые из них в качестве примера.
第 1 种：
P1---write(x)--------read(y)--------
P2-----------write(u)-------read(v)-
第 2 种：
P1----------write(x)-read(y)--------
P2--write(u)----------------read(v)-
第 3 种：
P1---read(y)----------write(x)------
P2-----------write(u)---------read(v)-
У нас есть 24 возможных порядка выполнения, то есть любая перестановка и комбинация этих 4-х операций, то есть 4!=24. Такие возможности, как первая и вторая, хорошо понятны. Почему существует возможная реализация, подобная третьей? Это связано с тем, что даже в одной и той же программе из-за многоуровневого кеша и наличия когерентности в процессоре, хотя ваша программа сначала пишет, а затем читает, порядок, который фактически действует в памяти, также может быть таким: сначала чтение, а затем запись.
На самом деле будут и такие исполнения, как следующие, где 2 операции выполняются одновременно на 2 процессорах. P1--запись(x)-чтение(y)-------- P2--запись(u)-------чтение(v)- Если вы добавите этот случай одновременного запуска, возможностей станет больше. Мой расчет не очень хорош, поэтому я не буду продолжать считать здесь, потому что неважно, сколько их, важно, чтобы вы знали, что есть много возможностей. Тогда «любое выполнение» в определении относится к любому возможному выполнению, а также может пониматься как все эти возможные исполнения в определении. Далее, не переводя определение, поясним слово --sequential order. Что такое последовательный порядок? Давайте пролистаем английский словарь (это больше похоже на понимание прочитанного). последовательный: последовательный; последовательный; последовательный заказ: заказ; заказ; правило; [торговый] заказ
последовательный порядок... последовательный порядок, что это, черт возьми, такое? На самом деле последовательный означает один за другим В контексте процессора последовательный означает, что операции выполняются одна за другой, то есть последовательно, и нет перекрытия. Порядок означает, что после определенных корректировок что-то становится упорядоченным в соответствии с определенными правилами. Например, алгоритмом сортировки в алгоритме является упорядочивание, которое заключается в упорядочивании массива по правилам от большего к меньшему или от меньшего к большему. Тогда последовательный порядок означает, что операции расположены одна за другой без перекрытия. Продолжая говорить о приведенном выше примере, если мы расположим 4 операции по правилам одну за другой, мы можем получить 4 в это время! перестановок и комбинаций возможных перестановок (порядок), но неважно, сколько их.
Например:
P1_write(x);P1_read(y);P2_write(u);P2_read(v);
P1_read(y);P1_write(x);P2_write(u);P2:read(v);
P2_write(u);P2_read(v);P1_read(y);P1:write(x);
Я перечислил здесь только 3 из них, остальные вы можете оценить сами. Дело в том, что последовательный порядок позволяет этим 4 операциям выполняться последовательно одна за другой без перекрытия. Обратите внимание, что это расположение не является реальным исполнением, реальным исполнением является любое исполнение, сказанное здесь является логическим предположением, поэтому в определении есть как бы.
С таким большим предзнаменованием, давайте начнем переводить первое предложение в определении:
Эффект от любого возможного выполнения такой же, как эффект от определенного выполнения всех операций на процессоре по порядку.
Обратите внимание, что здесь some означает что-то, а не some, потому что порядок в единственном числе. (занимаюсь пониманием прочитанного) Это означает, что для удовлетворения этому условию процессор должен иметь возможность разрешить существование только тех возможных исполнений, которые удовлетворяют этому условию, а другие возможные исполнения, которые не удовлетворяют этому условию, не появятся.
Из первого предложения видно, что если многоядерный процессор хочет обеспечить последовательную согласованность, то эффект выполнения нескольких программ на нескольких ядрах «эквивалентен» эффекту последовательного выполнения всех операций на одном ядре. Если это так, то мощность многоядерности фактически исчезает. Так что, будь то в 1979 году, когда Ломпорт писал эту статью, или сейчас, не существует настоящего многоядерного процессора, обеспечивающего последовательную согласованность.
Так почему же Бог Ломпорт предложил такую нереальную концепцию? (Должен отметить, что когда Ломпорт писал эту статью, он распространял ее не на область распределенных систем, а на область многоядерных процессоров и параллельного программирования.) Мы не будем говорить об этом сейчас и обсудим позже.
Еще одна вещь, которую следует отметить, это то, что я использовал слово «эффект» в своем переводе, но на самом деле в оригинальном английском определении использовалось слово «результат». Есть ли разница между эффектом и результатом? Поясним, каков результат выполнения? Независимо от фактического или гипотетического выполнения программа выдаст определенный результат, например результат печати. На самом деле, определение говорит, что результат тот же.
Если в определении используется эффект, то это определение является только качественным определением, а если используется эффект, то это определение является количественным определением. Количественный, то есть его можно доказать математически. Из этого мы видим, что Великий Бог другой, любую теорию можно доказать с помощью математики. Доказательство будет упомянуто позже в статье, и мы продадим его здесь. На данный момент, более точный перевод нашего первого определения предложения:
Результат любого возможного выполнения такой же, как и результат определенного выполнения всех процессорных операций по порядку..
Здесь мы также должны отметить, что тот же результат означает, что если кто-то действительно хочет реализовать многоядерный процессор с последовательной согласованностью, потому что результат должен быть одинаковым, у него есть определенное пространство для оптимизации, и он не будет полностью эффект ядерного последовательного исполнения. Но считается, что эта оптимизация также очень ограничена.
Ну наконец-то мы объяснили самое сложное первое предложение, все могут вздохнуть с облегчением, второе предложение очень простое. Мы по-прежнему сначала объясняем слово, а затем завершаем перевод. Это слово представляет собой последовательность, которая появляется во втором предложении. Последовательный порядок, который мы только что объяснили, является последовательным порядком (поэтому он сортируется один за другим), по сути, это действие, действие производит результат, а его результат создает очередь операций. Последовательность, которая появляется во втором предложении, относится к очереди этой операции.
Итак, перевод второго предложения:
И операции каждого отдельного процессора появляются в очереди операций в порядке, заданном программой.
То есть, если программа сначала записывает(х), затем читает(у), то только та очередь операций, которая удовлетворяет этому порядку, является приемлемой. Таким образом, множество возможных казней, о которых мы только что упомянули, намного меньше, и я не буду вычислять, насколько меньше здесь или в том предложении, число не важно, во всяком случае, они есть, и их меньше. Итак, что означает второе предложение? Это означает, что если многоядерный процессор реализует последовательную непротиворечивость, то этот многоядерный процессор в основном прощается с автомобилем самозапуска (кэширования) (хранилища). Вот и продолжаю продавать ключ, и даже оптимизация кеша, которая является самым эффективным способом повышения производительности процессора, пропала.Почему Бог предлагает эту концепцию?
Что ж, здесь мы можем объединить два перевода и посмотреть полностью:
Результат любого возможного выполнения такой же, как у определенного вида выполнения всех операций процессора по порядку, и операции каждого отдельного процессора появляются в очереди операций в порядке, заданном программой.
Из этого определения мы видим, что ядром этой концепции является последовательный порядок, поэтому г-н Ломпорт называет эту модель согласованности последовательной согласованностью. Можно сказать, что название очень подходящее. Я не знаю, лучше ли такое приспособление для понимания носителями английского языка, не должно быть такой ситуации, как «какой, черт возьми, порядок порядка». Если вы читаете эту статью и чувствуете, что последовательный подход очень уместен, значит, я ясно дал понять. Далее, давайте возьмем конкретный пример и объясним его еще раз.
execution A
P0 writex=1-------------------------------
P1 -------write x=2----------------------
P2 -----------------read x==1--read x==2
P3 -----------------read x==1--read x==2
sequetial order: P0_write x=1,P3_read x==1,P4_read x==1,P1_write x=2,P3_read x==2,P4_read x==2
execution B
P0 write=1-------------------------------
P1 -------write x=2----------------------
P2 -----------------read x==2--read x==1
P3 -----------------read x==2--read x==1
sequetial order: P1_write x=2,P3_read x==2,P4_read x==2,P0_write x=1,P3_read x==1,P4_read x==1
execution C
P0 write=1-------------------------------
P1 -------write x=2----------------------
P2 -----------------read x==1--read x==2
P3 -----------------read x==2--read x==1
sequetial order:Вы не можете найти заказ, который соответствует 2 условиям в определении. Таким образом, если многоядерный процессор позволяет появляться только исполнениям A и B и не позволяет появляться C, то этот многоядерный процессор имеет последовательную согласованность. Если это позволяет появиться C, то это не последовательная согласованность.
Здесь мы полностью закончили, что такое последовательная согласованность. Однако осторожные друзья могут спросить, а что, если ваша программа многопоточная? Итак, давайте объясним последнюю деталь в определении: слово программа. Программа относится к последовательности инструкций, которые могут выполняться непосредственно процессором. Это не строгое определение программы, но я хочу отметить, что эта программа представляет собой концепцию, которая существовала в древние времена, когда не существовало операционной системы.В этом определении программа относится к программе той эпохи. В этой Программе нет понятия процесса и потока, это только понятия после операционной системы.
Потому что нет ни операционной системы, ни понятия объема памяти. В отличие от того, что мы сейчас называем программой (Program), разные программы имеют свое собственное независимое адресное пространство памяти. Здесь память разделяется для разных программ. Кроме того, следует отметить, что Program может использоваться для описания различных программ, независимо от того, являетесь ли вы ядром операционной системы или прикладной программой.
Как мы только что сказали, хотя последовательная непротиворечивостьпараллельное программированиеЭто предлагается в области распределенного поля, но на самом деле это концепция распределенного поля, особенно распределенной системы хранения. В книге «Распределенная система: принципы и парадигмы» (автор Эндрю С. Таненбаум, Маартен Ван Стин) автор немного модифицировал определение Ломпорта, чтобы приблизить это определение к понятию в распределенной области. автор Как изменилось:
The result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order and the operations of-each individual process appear in this sequence in the order specified by its program.
Автор заменил процессор на процесс, и добавил ограничение на хранилище данных.В Ломпорте такого ограничения нет.На самом деле дефолт относится к памяти. Процесс относится к процессу. Взяв в качестве примера zookeeper, это относится к процессу приложения, который обращается к zookeeper. программа не такая уж и низкоуровневая концепция, это тоже приложение на базе операционной системы.
Хорошо, теперь пришло время мне раскрыть 2 очка, которые я продал выше. В статье Ломпорта приведен небольшой пример:
process 1
a := 1;
if b = 0 then critical section:
a := 0
else ... fi
process 2
b := 1;
if a = 0 then critical section:
b := 0
else ... fi
Ломпорт сказал в статье, что если многоядерный процесс удовлетворяет условию последовательной непротиворечивости, то в критическую секцию может войти не более одной программы. В статье г-н Ломпорт не объяснил, почему не более одной программы может войти в критическую секцию. Вместо этого это доказательство предоставляется читателю статьи, точно так же, как внеклассные упражнения в наших общих учебниках, читателю.
Старик Ломпорта должен думать, что это доказательство слишком простое, и не должен тратить чернила пера, чтобы доказать это. Этот документ состоит всего из 2 страниц формата А4, и это самые короткие документы, которые я когда-либо видел. Это стиль отца Ломпорта, и в паксосских бумагах Ломпорта есть много подробностей, и они приводятся, оставляя читателей (想). Предположим, теперь мы доказали, что это правильно (хотя я не доказал, в статье есть 2 ссылки, использованные для доказательства этого), этот пример показывает, что? Вы можете заметить, что этот пример не используется ни одной блокировкой, но он реализует критическую секцию, критическая секция представляет собой многопоточный механизм синхронизации. Если мультипроцессор имеет последовательную согласованность, то ваша параллельная программа "естественна" верна.
Но разработчики процессоров, чтобы максимизировать производительность, оставляют задачу обеспечения корректности программ разработчикам программ. На аппаратном уровне предусмотрены только некоторые инструкции, такие как забор и cas.На основе этих инструкций ядро и языковая базовая библиотека реализуют различные механизмы синхронизации для обеспечения корректности операционной системы и корректности прикладной программы. Программисты должны осторожно использовать потоки и эти механизмы синхронизации, иначе могут возникнуть непредвиденные проблемы.
Если вы не отлаживаете баг многопоточности и работаете сверхурочно 2 дня подряд, значит, вы бог. Все эти инструкции имеют более высокий уровень согласованности, то есть линеаризуемость (о линеаризуемости см. в другой моей статье «Линейная согласованность — основа управления параллелизмом», хотя уровень согласованности высокий, но только для отдельных инструкций, процессор As в целом достигается гораздо более низкий уровень согласованности, чем последовательная согласованность, поэтому сложность реализации значительно снижается.
Хотя концепция последовательной непротиворечивости мистера Ломпорта не имеет практического значения в области параллельного программирования, она указывает нам, где находится рай для программиста. В программистском раю нет много(авто)линии(приходит),(авто)редактирования(уезжает), только написание программ. На собеседовании вас никто не спросит о многопоточном программировании, и вас больше не будут спрашивать о различных блокировках.
В распределенном мире более практична последовательная согласованность. Zookeeper реализует последовательную согласованность. Точно так же это должно быть доказуемо, но я не нашел никаких документов в сообществе зоопарков, подтверждающих это. Если вы уже понимаете приведенное выше определение, вы можете ясно представить себе, что zookeeper — это последовательная согласованность. Добро пожаловать, чтобы обсудить вместе.
Консистенция ЗК
На самом деле согласованность ZooKeeper сложнее,Операции чтения ZooKeeper обеспечивают последовательную согласованность, а операции записи ZooKeeper — линеаризуемость.(Что касается линеаризуемости, см. мою другую статью«Линейная согласованность — основа управления параллелизмом».
По поводу этого утверждения в официальной документации ZooKeeper не написано, но есть подробное обсуждение в группе рассылки сообщества. Кроме того, эта точка зрения также упоминается в этой статье о ZooKeeper «Модульная композиция служб координации» (эта статья не является основной статьей ZooKeeper, но всесторонне анализирует характеристики ZooKeeper, а также кросс-машинную комнату ZooKeeper). решение, ZooKeeper от Eleme. Трансформация нескольких живых существ в разных местах также относится к некоторым пунктам в этой статье). Мы можем понять ZooKeeper таким образом,В целом (операция чтения + операция записи) это последовательная согласованность, а операция записи реализует линеаризуемость.
Простым рассуждением мы можем сделать вывод, что также установлен небольшой пример документальной бумаги в зоофире. Мы можем реализовать распределенный замок. Но официальная рекомендация Resookeeper метод реализации не использует этот метод для достижения, но использовать характеристики Zookeeper линеаризуемости распределенного замка (на Zookeeker Official - как добиться распределенного замка, пожалуйста, обратитесь к моей статье«ZooKeeper реализует распределенные блокировки и главные выборы»).
Почему ZK реализует последовательную согласованность?
Основная функция ZooKeeper заключается в оказании координирующей услуги, то есть в распределенной службе блокировки.Как может ZooKeeper быть «естественно правильным» в распределенной среде? Не существует другого механизма синхронизации, гарантирующего правильность ZooKeeper, поэтому, пока zk реализует sc, он может сам обеспечивать правильность, тем самым предоставляя услуги блокировки для внешнего мира.
Справочная документация