Когда я предложил перевести на русский мою последнюю статью Easy Concurrency with Python Shared Objects на английском, поступило предложение "написать в несколько раз короче и понятнее". Просьба более чем обоснована. Поскольку я уже порядка десяти лет пишу многопоточку и БД, то описываемые мной логические связи выглядели самоочевидно, и я ошибочно расчитывал на аудиторию из трех с половиной человек, которые сидят сейчас где-то в яндексе или гугле. Судя по всему, они там и сидят, но тема им не интересна, поскольку в питоне нет настоящих потоков, а значит для этих людей такого языка программирования не существует. Потому я немножко снижаю планку и делаю общий обзор проблематики параллельных вычислений для людей, которые в них разбираются, но не являются экспертами в области.
| Процесс 1 | Процесс 2 |
|---|---|
|
|
Два процесса выполняются параллельно и независимо. Если мы возьмем первую инструкцию процесса 1, то параллельно с ней может выполниться любая из четырех команд. Вторая команда процесса 1 аналогично не ограничивает выполнение в процессе 2, потому она может выполняться параллельно с любой из четырех команд. Для простоты допускаем, что одна команда атомарна. Всего число возможных сценариев выполнения первого процесса 4^4 = 256. Если в аналогичных первом и втором процессах по десять инструкций, то число различных вариантов выполнения равно 1010, то есть, 10 миллиардов. За пару минут мы можем написать 10 миллиардов программ! Вау, мы крутые! А если серьезно, то нам не хватит никакого времени, чтобы отладить все эти 10 миллиардов сценариев выполнения.
По этой причине для успешной реализации параллельных асинхронных задач необходимо беспощадно ограничивать эту параллельность на пересечении задач, в местах согласования и координации.
Что там сложного? Есть конкуренция за ресурс — повесь мьютекс. Я так всегда делаю.
Блокировки, они же семафоры или мьютексы. Если вы только начали осваивать многопоточность в классических императивных языках, то вы знаете про задачу "обедающих философов", и в качестве простейшего решения предложите "официанта", то есть, простую блокировку. Ведь отдельная блокировка на каждую вилку быстро приводит вас к дедлокам.
А еще лучше вообще иметь только одну блокировку на все вилки, ложки, философов, и стол одновременно — создатели питона примерно так и подумали.
Если же вы решили использовать множественные блокировки, то неявные и допускающие вложенность блокировки (Rust std::sync::Mutex или Java synchronized) — путь в никуда, поскольку становится очень легко создать неочевидно дедлочащуюся программу. На самом деле, даже без дедлоков детальные блокировки не являются панацеей, поскольку простые блокировки, они же "семафоры Дейкстры", ограничены в своих способностях:
Хотя задачу курильщиков и возможно решить семафорами Дейкстры, такие "семафоры курильщика" дают сложный в понимании и поддержке алгоритм, при том, что задача, казалось бы, элементарна. Потому вторым по популярности механизмом блокировок стали условные переменные и более общий аспект оных — мониторы (в том числе уже упомянутое Java synchronized). Правда, проблемы дедлоков при множественных блокировках они не решают.
Что же делать? Мы все умрем? Да, но проблему дедлоков можно решить. Одно из остроумных решений для задачи обедающих философов предложил сам Дейкстра — брать детальные блокировки только в одном заранее заданном порядке. Следующий забавный прием — брать блокировки всем скопом одной командой либо отменять взятие блокировки. Такое можно реализовать на любой абстракции с примитивом try-lock (например, compare-and-swap), при помощи бесконечного цикла (например, std::lock из библиотеки C++).
Одна из самых последних и перспективных альтернатив блокировкам — это транзакционная память, по сути атомарный compare-and-swap на большом числе ячеек. Идею транзакционной памяти развил в конкретную программную реализацию, STM, мой любимый автор книг и статей по многопоточности — Нир Шавит. Главное преимущество STM — отсутствие дедлоков. В каком-то смысле транзакционная память достаточно стара, если вспомнить, что реляционные СУБД давно умели в транзакции. Программная транзакционная память, как правило, берет блокировки всем скопом, как в описанном выше алгоритме предварительной блокировки, но делает это не до выполнения операций изменения ячеек памяти, а после — таким образом нам не обязательно до начала работы алгоритма знать список нужных нам блокировок и длительность этих блокировок минимальна. Из популярных готовых решений на эту тему можно вспомнить Clojure и GHC.
У наивной реализации STM есть проблема — при интенсивных конфликтах меж потоками приложение большую часть времени крутит откаты транзакций вхолостую: подробнее.
Решение этой проблемы уже придумано за нас — это алгоритм раннего разрешения конфликтов, при котором реализация не ждет окончания транзакции для того, чтобы осознать невозможность применения ее результатов, а сразу прерывает одну из конфликтующих транзакций. По сути это способ организации детальных блокировок с разрешением дедлоков через откат изменений. Такой подход я и перенял при реализации Python Shared Object.
Коротко: взаимоисключающая блокировка не является основным средством организации доступа к разделяемой памяти и вообще разделяемым ресурсам, но именно этими блокировками чаще всего злоупотребляют.
Разделяемая память не нужна! Только акторная модель и сообщения (Erlang, Tcl)
Подход, известный также как "у меня болит палец — отрежу себе руку!".
Начну издалека. Если мы попытаемся разделить все-все-все алгоритмы и механизмы координации на самые простые винтики и гайки, то получим два основных примитива:
- состояние с последовательными переходами, синхронными и заранее предсказуемыми, потенциально в виде большого вектора, как то SIMD, GPGPU, компьютерные и даже живые нейронные сети. Да, живые организмы чутко воспринимают задержки входных сигналов, потому могут ощущать время и движение;
- асинхронное взаимодействие, как то сообщение в очереди или состояние-флаг, запись которого и чтение условно не зависят от задержек.
На первый взгляд очевидно, что асинхронная координация, то есть, асинхронная акторная модель и асинхронные сообщения, накладывает минимум ограничений на параллельное выполнение, при этом позволяют одинаково успешно передавать сообщения как между потоками одного процесса, так по сети между сильно удаленными компьютерами. Почему же столько разработчиков хотят вернуться в синхронность и детерминированность? Почему живые нейронные сети в значительной степени синхронны?
Асинхронная передача сообщений сама по себе не способна обеспечить строгую согласованность состояния/данных на разрозненных узлах. Если быть точным, то в асинхронной системе с отказами узла (или непредсказуемыми задержками ответа) невозможно детерминированное достижение консенсуса (достижение единого согласованного решения между всеми узлами) в соответствии с FLP-недостижимостью, а также производной теоремой CAP. В случае, если мы имеем некую гарантию времени ответа от узла и отсутствие отказов, мы можем достигнуть некоего условного консенсуса за время порядка нескольких круговых задержек передачи сообщения (то есть, периода выполнения запроса и обратного ответа).
Недетерминированность достижения консенсуса в асинхронной системе с отказами значит, что прийти к единому решению в такой системе — это рулетка, полнейшая случайность, хотя шанс "выиграть" в ней и повышается с течением времени, но он никогда не может быть меньше двух круговых задержек сети. По этой причине в реальности передача сообщений не так уж прозрачна и не так бесплатна при увеличении дистанции, например, при переходе от передачи сообщений между потоками одного процесса ОС к передаче сообщений между удаленными датацентрами. В случае большой круговой задержки протоколы организации распределенных БД, как то Raft, Zab, MultiPaxos, минимизируют проблемы координации, ограничивая ее выборами лидера, и применяют случайную задержку при выборах лидера. Аналогично Ethernet использует случайную задержку при конфликте использования канала.
Забавно, что создатель величайшей платформы Erlang для построения распределенных систем, Джо Армстронг, не строит иллюзий и осознает принципиальную неразрешимость проблемы. Вот диаграмма ситуации, которую Армстронг пытался описать на пальцах:
В любой момент времени любой из двух узлов знает о предыдущем состоянии другого узла, но не знает, получил ли другой узел последнее сообщение, каково сейчас состояние другого узла, и жив ли вообще этот второй узел. Как правило, все системы с распределенным состоянием решают эту проблему одинаково — полагаются на единственное разделяемое состояние, как на эталонное во всей распределенной системе.
По итогу мы пришли к тому, от чего уходили — к разделяемому состоянию. Вся трудность и неопределенность согласования системы, построенной на базе асинхронных сообщений, решается минимальным координатором, внутри себя исполняющим синхронный алгоритм, то есть, механизмом последовательного применения операций к одному-единственному эталонному состоянию.
YandexDB, она же Calvin, использует Zookeeper для организации глобально согласованной истории изменений. Сам Zookeeper использует асинхронные сообщения только для выбора лидера — работа с данными происходит синхронно на выбранном эталонном узле (лидере). Создатели экспериментальной СУБД Tango заявляют, что реализовывает ZooKeeper в 300 строчек кода. Однако, сам оригинальный Tango использует нереплицируемый счетчик в качестве опорного средства координации, потому не обеспечивает гарантий отказоустойчивости ZooKeeper. И по итогу для организации сравнимых гарантий в этой "реализации ZooKeeper" на Tango вам нужно реализовать координацию Tango на… ZooKeeper. Это похоже на игру "горячий пирожок".
Почему в этот горячий пирожок играют? Потому что идеальное решение невозможно чисто теоретически (FLP-недостижимость) — все практически реализации являются тем или иным компромиссом. Но есть желающие "идеальное решение" купить, потому используется популярный маркетинговый прием: недостатки существующих решений уже хорошо известны, а недостатки нашей новой системы еще не известны… значит можно сказать, что их нет. Так и развиваются многие Big Data проекты.
Когда же у вас есть хотя бы общий атомарный счетчик, а еще лучше — общий атомарный список транзакций, дальше вы можете наращивать объем "нагрузочных данных" как угодно, реплицировать их в eventual consistency хранилищах, придавать им произвольную форму (как это сделало в том же Tango, давшем пользователю свободу выбора формы данных) — это всё имеет второстепенное значение и легко меняется, хотя многие люди по прежнему обращают внимание на обёртку, а не на суть. То есть, ходовые качества машины определяются двигателем, трансмиссией, рулевой системой, но большинство видит лишь красивый кузов и отделку салона, к сожалению. Я хочу здесь подчеркнуть, что ZooKeeper в случае Tango, YandexDB, Calvin, ClickHouse и прочих аналогичных проектов — это не "просто вспомогательная штука", как его рисуют, а ключевой компонент и большая часть сложности реализации всей СУБД, и этот компонент, к тому же, полностью определяет число транзакций в секунду, которые сможет обработать весь кластер.
Проблем неопределенности в том числе избегает реализация синхронной передачи сообщений, иначе известная как "взаимодействующие последовательные процессы" (Communicating sequential processes, CSP), которые являются давно известным подходом. В частности, этот подход выбрал в качестве своего фундамента популярный язык Go и сильно менее популярные предшественники оного, языки Limbo и Newsqueak. Атомарная операция отправки сообщения через канал гарантирует, что либо сообщение отправлено и отправка одновременно подтверждена, либо оно не отправлено — для обеспечения этой синхронизации используется разделяемое состояние канала скрытое от программиста на Go.
Коротко: злоупотребление передачей сообщений в архитектуре приложения так же плохо, как злоупотребление разделяемым состоянием. Бездумное следование любой идеологии до добра не доводит.
Золотая середина
Асинхронные алгоритмы и синхронные алгоритмы, передача сообщений и разделяемое состояние дополняют друг друга. Проблемы возникают только когда одним из подходов злоупотребляют, а второй — игнорируют. Невозможность организации простого эффективного разделяемого состояния на питоне привела к появлению массы многочисленных "костылей" — это и простые РСУБД, как то PostgreSQL и MySQL, и NoSQL вроде Redis/MemCached, и очереди сообщений (RabbitMQ). Примерно на этой волне я и решил написать Python Shared Objects. В упомянутом Erlang уже давно есть специальный модуль для организации разделяемой памяти: подробнее.
Также, сама реализация Erlang/OTP неявно использует разделяемую память. Даже если из питона получится жалкое подобие Erlang — это все равно намного лучше, чем тот безнадежно однозадачный (не путать с зелеными потоками/concurrent IO) интерпретатор питона, который мы имеем сейчас.
Состояние/ячейки данных, используемое для координации, должно быть разделяемым и изменяться строго последовательно. Независимые состояния должны оставаться независимыми, асинхронно выполняющиеся задачи должны выполняться асинхронно. Если лишь часть задач требуют координации, то они и должны разделять некоторую часть состояния для своей координации. Если возможно выполнить одинаковый набор инструкций для большого числа в ячеек в векторе — выполните его при помощи SIMD/CUDA/OpenCL, а не созданием асинхронно выполняющихся потоков, которые потом придется обратно синхронизировать.
Например, оригинальная STM от Нир Шавита использует глобальный атомарный счетчик для координации всех задача, но в остальном "общими" ячейки данных становятся только когда они по-настоящему общие для нескольких задач. Аналогичный подход с общим атомарным счетчиком номера/приоритета транзакции и детальными блокировками также применяет моя реализация STM в виде Python Shared Objects.
Тесты, еще тесты, нужно больше тестов
Как же тестировать и отлаживать многозадачные и распределенные системы? Основная проблема многопоточных, многозадачных, распределенных систем — это недетерминированность их поведения. То есть, ваша система может работать пять лет, а потом резко начать падать из-за какого-то незначительного изменения алгоритма.
В общем случае ответ на вопрос "как тестировать?" — "никак", вы подходите к проблемы с неправильной стороны. Но не расстраивайтесь — это нормально, так делает много кто. По этой причине, например, большинство распределенных СУБД, заявлявших про строгую согласованность данных и отказоустойчивость, в жестких тестах на Jepsen показывают, что на самом деле никогда не обеспечивали как минимум одну из этих гарантий: подробнее.
Тестирование — это способ обнаружить наличие проблемы, но тестированием невозможно доказать отсутствие проблем. Если в качестве отказоустойчивого хранилища согласованных данных вы используете не ZooKeeper и не Etcd, то с большой вероятностью ваша система потеряет/испортит данные или вовсе упадет при потере лидера. Если вы уделите пару часов чтению серии статей по ссылке, то вы узнаете, что какой-нибудь Galera Cluster способен нарушать согласованность даже на полностью исправном кластере, а MongoDB не дает даже "eventual consistency" гарантий при отказах (то есть, в MongoDB ваши данные из подтвержденных транзакций может быть сохранятся, а может быть не сохранятся). Однако, даже если вы построили систему на базе условно надежных ZooKeeper или Etcd, вы не знаете, сколько еще проблем возникло из-за некорректного использования оных в самописном коде.
Единственный более-менее гарантированный способ построить работающую систему — это прежде всего грамотно подойти к ее проектированию и реализации, доказать корректность алгоритма, а не полагаться на популярный нынче метод тестирования и "авось". Вторая линия обороны — это тестирование, но не простое. Разработчики должны понимать, что если ошибка есть, то ее необходимо обнаружить, а не замести под ковер и подпереть костылем. То есть, без участия и сотрудничества самих разработчиков невозможно эффективно произвести тестирование. Необходимо тестировать систему в самых неудобных и опасных режимах, предусмотреть в исходном коде отладочные опции для более частого срабатывания редких фрагментов кода — в том числе такой подход я задействовал для своего проекта Python Shared Objects. В случае отказоустойчивых кластеров обязательно необходимо периодически симулировать отказы, как это делает, например, Яндекс.
Поскольку очень часто проблема происходит только один раз и больше никогда не повторяется, то большую ценность имеет логирование, создание снимков состояния системы во время проблемы. Для последнего, например, есть замечательная утилита rr от Mozilla, которая была разработана специально для отладки многопоточного кода в Firefox. Эта утилита позволяет выполнить код в обратном направлении, точно восстанавливая последовательность выполнения асинхронных потоков, приведшую к ошибке. И хотя облака нынче стали популярным хайпом, выбор инструментов для отладки многозадачного кода и распределенных систем на удивление скудный. Для распределенных систем есть упомянутый Jepsen, для многопоточных есть, например, ThreadSanitizer.
К сожалению, для тестирования моего Python Shared Objects мне так и не удалось найти готового решения для неинтрузивного логирования. Неинтрузивного — поскольку для многопоточного кода имеет место так "эффект наблюдателя" — когда при логировании программа ведет себя совсем не так, как без него. Когда-то давно для закрытой разработки я сам реализовывал неинтрузивное логирование на Delphi, но это было давно и неправда, а на сишные программы этот код довольно плохо налазит.
Коротко: при создании сложных многопоточных, многозадачных, и распределенных систем грамотный подход и такие люди, как я, с большим трудом заменяются тестами и "большой дружной командой".
Комментарии (42)
estet
08.11.2021 10:04Вопрос - насколько реально легко использовать вещи вроде Coq для доказательства отсутствия дедлоков? Или это вообще не из той степи?
Если кратко, то нелегко. Доказать отсутствие дедлоков с помощью Coq можно. Но, наверное, более сложный вопрос не в том, можно верифицировать или нет, а в том, как связать верификацию и конкретную реализацию. Один из способов это сделать экстракцию формально верифицированного кода из Coq в OCaml или Haskell и интегрировать в основной проект.
byko3y Автор
08.11.2021 10:22Один из способов это сделать экстракцию формально верифицированного кода из Coq в OCaml или Haskell и интегрировать в основной проект.
Неужели Coq поможет доказать корректность кода, в котором мы хотим реализовать, например, атомарные ячейки памяти Data.Atomics?
https://hackage.haskell.org/package/atomic-primops-0.8.4/docs/Data-Atomics.html
Как я понимаю, программист окажется неприятно стеснен в выразительных средствах, что в том числе выльется в низкую производительность кода. И это один из способов достигнуть верифицируемости алгоритма — связать кодеру руки и ноги, чтобы он сильно не рыпался, и тогда уже для простейших конструкций доказательство будет тривиально. Правда, при таком подходе уже недалеко до чего-то вроде STM/PSO, которое из коробки гарантирует корректность многопоточного доступа безо всяких внешних доказательств.
hard_sign
08.11.2021 13:34+2Остаётся открытым вопрос, зачем Кальвину Zookeeper.
byko3y Автор
08.11.2021 14:32+2Остаётся открытым вопрос, зачем Кальвину Zookeeper.
Я уже не стал вскрывать эту тему. Вы молодые, шутливые, вам все легко. Статейка-то была про многозадачность, я и так сильно растянул про распределенные системы.
Кальвину Zookeeper нужен для того, чтобы определять, какая транзакция после какой будет выполняться, причем, этот порядок должен быть идеально одинаковым для всего кластера, чтобы везде получились одинаковые данные по одинаковому номеру транзакции. Дальше уже локально узел может как угодно медленно применять утвержденный список транзакций.
Задачу же работы со строго согласованным состоянием с гарантиями отказоустойчивости и приемлимой производительностью во всей индустрии умеют решать ровно три софтины -- Zookeeper, Etcd, и Google Chubby. Конечно, может быть есть еще какое-то проприетарное решение, которое публике не показывают.
hard_sign
08.11.2021 14:48+1На счёт молодости можно поспорить, но я бы лучше поспорил на счёт Zookeeper. Не нужен там zookeeper. Тот компонент, который упорядочивает транзакции, называется секвенсер, и он может быть монолитным, т. к. не обязан быть отказоустойчивым. В референсной реализации кальвин-протокола секвенсеров много, они независимы друг от друга, а упорядоченность достигается синхронизацией часов и пакетированием транзакций по 10 мс.
Если есть zookeeper, то никакой кальвин уже не нужен.
byko3y Автор
08.11.2021 15:26+1В референсной реализации кальвин-протокола секвенсеров много, они независимы друг от друга, а упорядоченность достигается синхронизацией часов и пакетированием транзакций по 10 мс.
Советую читать оригинальную статью, а не буклетик по первой ссылке из гугла:
http://cs.yale.edu/homes/thomson/publications/calvin-sigmod12.pdf
At the end of each epoch, all requests that have arrived at a sequencer node are compiled into a batch. This is the point at which replication of transactional inputs (discussed below) occurs.
Calvin currently supports two modes for replicating transactional input: asynchronous replication and Paxos-based synchronous replication
In asynchronous replication mode, one replica is designated as a master replica, and all transaction requests are forwarded immediately to sequencers located at nodes of this replica
Calvin also supports Paxos-based synchronous replication of transactional inputs. In this mode, all sequencers within a replication group use Paxos to agree on a combined batch of transaction requests for each epoch. Calvin’s current implementation uses ZooKeeper
Забавно, как авторы Calvin, ровно как и люди из Яндекса, которые на презентациях рассказывали про YandexDB, упорно маскировали тот факт, что вся их разработка по сути является небольшой надстройкой над Zookeeper.
Если есть zookeeper, то никакой кальвин уже не нужен
Нужен для того, чтобы не гонять терабайты данных через сам zookeeper. Таким образом уменьшается объем строго согласованных данных и можно обрабатывать больше транзакций в секунду. Плюс к тому же эти терабайты можно шардировать, реплицируя по всем шардам только метаданные транзакций, а не сами данные.
hard_sign
08.11.2021 15:43+2Я, конечно, статью ещё раз перечитаю.
Но во-первых, журнал транзакций у Кальвина не сказать чтобы компактный – там передаётся ключ, значение и номер предыдущей версии значения, так что терабайты набираются легко.
А во-вторых я не понимаю, зачем там paxos-based (ну или zab-based) репликация, если можно заранее договориться, в какой последовательности идут транзакции от разных секвенсоров.
byko3y Автор
08.11.2021 16:15Но во-первых, журнал транзакций у Кальвина не сказать чтобы компактный – там передаётся ключ, значение и номер предыдущей версии значения, так что терабайты набираются легко.
Calvin реплицирует входной запрос, он не реплицирует значение самих данных. Если запросы больше, чем сами данные -- да, Calvin не нужен, это можно реализовать на голом ZooKeeper.
А во-вторых я не понимаю, зачем там paxos-based (ну или zab-based) репликация, если можно заранее договориться, в какой последовательности идут транзакции от разных секвенсоров.
Да, можно. Но кто потом будет публиковать эту последовательность? Допустим, публикация происходит "все ко всем". Представь, что во время публикации один из узлов отказывает. К части узлов транзакции с него дошли, к другой части -- нет. Что делать? Нужен консенсус, то есть, одинаковый набор команд на всех узлах кластера. Как делать консенсус? Либо назначить один из узлов Calvin эталонным, и таким образом потерять отказоустойчивость, либо применять внешнее решение для распределенного консенсуса -- а это и есть ZooKeeper.
В принципе, отказ малого числа узлов можно пережить через gossip protocol, то есть, процесс публикации "все ко всем" непрерывно распространяет не только самую последнюю эпоху, но и предыдущие, которые потенциально не дошли всем от умершего узла. Но если целью стоит устойчивость к отказам вплоть до кворума и даже потенциально ниже него со временной остановкой обработки данных, то тут уже никакой gossip не спасет и узлы пойдут в разнобой. Это уже не говоря о том, что gossip protocol сожрет все сетевые каналы.
hard_sign
08.11.2021 17:22Мы точно про один и тот же кальвин говорим? Что такое «входной запрос»?
Кальвин – это чистый key/value, входной запрос там равен данным.
Дополнительную ценность система приобретает, когда кто-то (например, SQL engine в YandexDB) преобразует какой-то осмысленный запрос в последовательность изменения ключей, но и там реплицируется именно эта последовательность, а не SQL. Репликация запросов – это очень стрёмная штука, мне известна реализация только в MySQL. Все остальные реплицируют изменения данных с ключами (любой CDC).
К части узлов транзакции с него дошли, к другой части -- нет. Что делать?
Это проблема того секвенсера, до которого изменения не дошли. Он знает, что у него должна быть последовательность A1 B1 C1 A2 B2 C2 и т. д. Если B2 почему-то нет, можно поинтересоваться у секвенсера B, что у него там было под номером 2?
Raft и прочие ZAB'ы нужны только лишь потому, что никто заранее не знает, что будет в логах. Секвенсеры в кальвине знают это заранее, поэтому им проще. Но конечно, zookeeper туда воткнуть можно – примерно так же, как в наручные часы можно воткнуть атомный механизм. Точно, надёжно, понтово – но не нужно.
byko3y Автор
08.11.2021 18:02Мы точно про один и тот же кальвин говорим? Что такое «входной запрос»?
Кальвин – это чистый key/value, входной запрос там равен данным.
Ну в мире key-value СУБД запросы не ограничиваются простым "запросить по ключу" и "установить по ключу". Потому что в таком случае, как я уже согласился, можно взять ZooKeeper и не морочить голову.
Он знает, что у него должна быть последовательность A1 B1 C1 A2 B2 C2 и т. д. Если B2 почему-то нет, можно поинтересоваться у секвенсера B, что у него там было под номером 2?
Поинтересовался -- получил таймаут, дальше что? А я скажу, что дальше: на части узлов транзакции B2 есть, а на другой части -- нет. Всё, приехали.
Raft и прочие ZAB'ы нужны только лишь потому, что никто заранее не знает, что будет в логах. Секвенсеры в кальвине знают это заранее, поэтому им проще
Заранее? Схема на Figure 1 говорит, что заранее про транзакции знает лишь один набор узлов -- реплики не знают ничего.
hard_sign
08.11.2021 18:14А что же ещё может быть в мире key-value СУБД? Особенно если учесть, что даже в мире реляционных СУБД логическая репликация основана на подходе "установить по ключу"?
получил таймаут, дальше что
Подождал, спросил ещё раз. Совершенно не вижу проблемы собрать кластер высокой доступности для секвенсера.
заранее про транзакции знает лишь один набор узлов
в наборе узлов один секвенсер. И этот секвенсер заранен знает не весь набор транзакций, а последовательность сообщений от других секвенсеров. Этого достаточно.
byko3y Автор
08.11.2021 18:30А что же ещё может быть в мире key-value СУБД? Особенно если учесть, что даже в мире реляционных СУБД логическая репликация основана на подходе "установить по ключу"?
Ну так при логической репликации "установить по ключу" не реплицируется всё содержимое записи. В статье в бенчах упоминается 10% транзакций, затрагивающие сразу несколько шардов -- очевидно, что это не простая установка по ключу, а какая-то сложная операция сразу над большим числом ключей. И такие операции прекрасно реплицируются на уровне входной команды.
Подождал, спросил ещё раз. Совершенно не вижу проблемы собрать кластер высокой доступности для секвенсера.
Один узел сдох. Совсем. Или даже целая реплика пропала, потому что роут к датацентру потерялся. Разве не в этом смысл высокой доступности?
в наборе узлов один секвенсер. И этот секвенсер заранен знает не весь набор транзакций, а последовательность сообщений от других секвенсеров. Этого достаточно.
От каких "других секвенсоров" он будет знать последовательность в условиях отказов? Я и пишу -- от каких-то случайных, случайное подмножество последовательности операций. Без отказов мне ZooKeeper не нужен -- я просто кину SQLite базу на один комп и на этом проблемы мои закончатся.
hard_sign
09.11.2021 12:03транзакций, затрагивающие сразу несколько шардов
Мы точно о разных кальвинах. Какая разница, сколько шардов затрагивает транзакция? Когда идёт двухфазная фиксация, это важно, когда кальвин – никакой разницы вообще.
Или даже целая реплика пропала, потому что роут к датацентру потерялся.
Ну да, согласен, в этом случае надо всем договориться о том, какая была последняя эпоха у пропавшего секвенсера. Для этого действительно проще всего взять готовый Zookeeper. Но из-за этого считать всю систему «надстройкой над Zookeeper’ом» – явное преувеличение.
Без отказов мне ZooKeeper не нужен
Вот и я об этом. Баллонный ключ должен лежать в багажнике на случай прокола колеса, но это не повод называть весь автомобиль «надстройкой над баллонным ключом».
byko3y Автор
09.11.2021 12:15Мы точно о разных кальвинах. Какая разница, сколько шардов затрагивает транзакция? Когда идёт двухфазная фиксация, это важно, когда кальвин – никакой разницы вообще.
Не, я о том, что там не простые входные команды, они скорее всего мельче, чем данные над которыми проводятся превращения. Потому реплицируются входные команды, а промежуточный слой уже размазывает эти команды по большому объему данных. Иначе бы смысла не было всю эту систему городить.
Для этого действительно проще всего взять готовый Zookeeper. Но из-за этого считать всю систему «надстройкой над Zookeeper’ом» – явное преувеличение.
Без ZooKeeper система теряет отказоустойчивость -- checked.
ZooKeeper составляет основную сложность системы и его ничем нельзя заменить -- checked.
ZooKeeper определяет производительность выполнения транзакций -- checked.
Может быть это и большая надстройка, может быть очень большая и сложная надстройка. но по итогу все ключевые характеристики системы определяются ZooKeeper-ом.
hard_sign
09.11.2021 13:37ZooKeeper составляет основную сложность системы и его ничем нельзя заменить -- checked.
ZooKeeper определяет производительность выполнения транзакций -- checked.
Нет. Это ниоткуда не следует.
Ещё раз. У нас есть несколько секвенсеров. Можно назвать их по алфавиту – A, B, C... Можно также договориться, что операции сортируются по номеру эпох, а внутри эпохи – по номеру секвенсера. То есть секвенсер A отправляет свои операции секвенсерам B и C, и никакого консенсуса не нужно, потому что никто, кроме секвенсера A, не может сгенерировать операции от секвенсера A. Никакого Zookeeper’а здесь нет.
Теперь посмотрим на ситуацию глазами секвенсера B. У его есть последовательность операций A42 B42 C42 A43 B43 C43... Он может выполнять все эти операции, ни с кем не согласовывая их выполнения. Никакого Zookeeper’а здесь нет.
Теперь, допустим, у секвенсера B последовательность A666 B666 C666 B667 C667 B668 C668... Видно, что секвенсер A пропал. Вроде как последней его эпохой была 666, но вот этого секвенсер B наверняка знать не может – то ли правда секвенсер пропал, то ли канал связи лёг. Тут необходим консенсус, и вот тут как раз в игру вступает Zookeeper.
Система функционирует нормально в течение 99.9% времени (ну если это не списанные серверы в деревенском сарае). В оставшиеся 0.1% система восстанавливается после сбоев. При восстановлении Zookeeper нужен, и скорость восстановления зависит от производительности Zookeeper. Но скорость нормальной обработки транзакций от Zookeeper’а никак не зависит.
Ну и опять же, «ничем нельзя заменить» – это тоже фантазия. Raft опубликован, бери и реализуй. Другой вопрос, зачем это делать, если есть готовая реализация в виде etcd. А Zookeeper – это даже не Raft, это просто «дело привычки». Вон у Oracle, например, есть DataGuard Broker, который умеет строить консенсус. Но для кластеризации TimesTen они взяли Zookeeper – просто чтобы не возиться.
byko3y Автор
10.11.2021 07:32То есть секвенсер A отправляет свои операции секвенсерам B и C, и никакого консенсуса не нужно, потому что никто, кроме секвенсера A, не может сгенерировать операции от секвенсера A. Никакого Zookeeper’а здесь нет.
У меня тоже складывается ощущение, что мы говорим про какие-то разные Кальвины. Но я перечитываю статью, и вижу подтверждение именно своего кальвина. Узлы в системе имеют два типа взаимоотношений: реплика и шард. То есть, вся БД разделена на несколько шардов с уникальными данными, а потом эти шарды реплицированы. Обычно реплики сидят в разных датацентрах, а шарды -- в одном.
Так вот, ни в каком из двух вариантов взаимоотношений нет ситуации "секвенсер A отправляет операции B, и никто кроме A не может их сгенерировать". Секвенсоры-шарды вообще друг-другу ничего не посылают -- они шлют операции планировщикам всех шардов одной реплики. Секвенсоры-реплики дублируют друг друга, они на равных создают пачки операций и согласовывают их -- весь раздел 2 был уделен обоснованию этого приема, то есть, система продолжает работать как ни в чем ни бывало при отказе одной из реплик. На самом деле такой бесшовный failover невозможен, это тот же "горячий пирожок", который превращается в очередную хитромудрую обертку над ZooKeeper, но я сейчас не об этом -- я о том, что всё создание системы было обосновано только отказоустойчивостью.
Конечно, можно взять модель "асинхронной репликации" с назначением единственного лидера, где, действительно, только один секвенсор будет главным и рассылать пачки операций всем остальным репликам, и тогда потерять всю отказоустойчивость и весь смысл создания системы -- смотри раздел 2.
Система функционирует нормально в течение 99.9% времени (ну если это не списанные серверы в деревенском сарае). В оставшиеся 0.1% система восстанавливается после сбоев. При восстановлении Zookeeper нужен, и скорость восстановления зависит от производительности Zookeeper.
Я не могу придумать архитектуры, при которой через ZooKeeper не будут идти ключевые данные и при отказе не будет теряться случайное количество подтвержденных операций. При отказе будет потеряны именно данные, которые не прошли через ZooKeeper. Это не просто "библиотека для восстановления после отказов", ZooKeeper для каждой своей входящей операции производит сложный алгоритм репликации-сохранения и выдает подтверждение с гарантиями -- без это сложной процедуры гарантий сохранности при отказе нет.
Единственная реально значимая фича Calvin по сравнению с ZooKeeper -- это наличие независимых секвенсоров в шардах, которые реплицируются независимо, за счет чего производительность упирается не в один ZooKeeper, а в несколько ZooKeeper-ов. Правда, преимуществом этим можно воспользоваться ровно настолько, насколько независимы эти шарды. Собственно, с таким же успехом можно было шардировать данные по нескольким экземплярам ZooKeeper безо всяких Cavin.
Ну и опять же, «ничем нельзя заменить» – это тоже фантазия. Raft опубликован, бери и реализуй. Другой вопрос, зачем это делать, если есть готовая реализация в виде etcd
Ха, "реализуй" -- легко сказать, но реализовать сильно сложней. По этой причине столько систем уже наклепали на базе ZooKeeper, но ZooKeeper по прежнему остается почти безальтернативным -- потому что он и составляет самую большую сложность разработки.
Вон у Oracle, например, есть DataGuard Broker, который умеет строить консенсус
Я не могу найти подтверждение того, что сам Data Guard Broker устойчив к отказам.
https://www.oracle.com/technical-resources/articles/smiley-fsfo.html
Здесь указывается, что функция автоматического принятия решения о fail-over производится некоторым внешним агентом. То есть, сам Data Guard Broker этого делать не умеет -- он может только выполнять команды извне. Причем, судя по инструкциям для ручной синхронизации ролей
https://docs.oracle.com/cd/E69294_01/html/E71432/gpxvm.html
я могу предположить, что рассинхронизированные конфиги Data Guard являются нормой.
hard_sign
10.11.2021 10:37Секвенсоры-шарды вообще друг-другу ничего не посылают -- они шлют операции планировщикам всех шардов одной реплики.
Ну ок, я немного упростил картину. Конечно, есть отдельные узлы-планировщики. Но общую ситуацию это не меняет.
Вы же понимаете, что для репликации никакой консенсус (и zookeeper) не нужен. Репликация хоть в MS SQL, хоть в Oracle хоть где прекрасно работает без zookeeper’а. Потому что лидер жёстко зафиксирован. Поэтому гонять все операции через Zookeeper – это, конечно, хорошее быстрое решение для академического проекта, но совсем не обязательное условие для коммерческого продукта.
Секвенсоры-реплики дублируют друг друга, они на равных создают пачки операций и согласовывают их
Зачем секвенсерам их согласовывать? Это совершенно лишнее.
Вам о чём-нибудь говорит аббревиатура CRDT? Так вот, секвенсер – это примерно то же самое. Каждый секвенсер формирует пачку транзакций независимо от остальных секвенсеров. Планировщик (или, как я писал в предыдущих комментариях, секвенсер, но сути это не меняет) руководствуется двумя простыми правилами:
Транзакции упорядочиваются по номеру эпохи, а внутри эпохи – по номеру секвенсера.
Вся эпоха, сгенерированная секвенсером, выполняется подряд, без прерывания.
Этих правил достаточно, чтобы на каждом планировщике последовательность транзакций была одна и та же, не надо ничего согласовывать.
работать как ни в чем ни бывало при отказе одной из реплик
Вот как раз при отказе одной из реплик всем надо договориться, какая последняя эпоха в этой реплике. Это единственное место, где нужен консенсус.
но ZooKeeper по прежнему остается почти безальтернативным
Да в том-то и дело, что через него никто не пускает большой поток данных, поэтому никто и не переделывает. Ну посмотрите, например, много ли людей собирают свои компьютеры, когда можно купить ноутбук или моноблок?
Вот Confluent захотел избавиться от Zookeeper – и избавился. Не до конца понимаю, зачем, но внезапно выяснилось, что так можно.
функция автоматического принятия решения о failover производится некоторым внешним агентом
Давно я не работал с Oracle, забыл фирменную продуктовую линейку :) Этот внешний компонент называется Observer и тоже входит в поставку Oracle RDBMS.
byko3y Автор
10.11.2021 17:42Вы же понимаете, что для репликации никакой консенсус (и zookeeper) не нужен. Репликация хоть в MS SQL, хоть в Oracle хоть где прекрасно работает без zookeeper’а. Потому что лидер жёстко зафиксирован
Это что-то вроде "как попаду в аварию -- так обязательно пристегну ремень". Да, для репликации доступность распределенного консенсуса не обязателена и отказоустойчивость тоже не обязательна, но если нужно при отказе одного узла сохранять работоспособность без потери подтвержденных данных и без публикации неподтвержденных, то придётся "пристёгиваться" заранее. ZooKeeper, для справки, при нормальной работе тоже никаким распределенным консенсусом не занимается -- он работает именно в режиме синхронной репликации с одним стабильным лидером. Вся огромная сложность реализации ZooKeeper заключалась в том, чтобы идеально совместить эту высокопроизводительную репликацию с обработкой отказа. Именно при отказах вся архитектура БД и проверяется на прочность, а без отказов можно хоть SQLite реплицировать.
Транзакции упорядочиваются по номеру эпохи, а внутри эпохи – по номеру секвенсера...
Этих правил достаточно, чтобы на каждом планировщике последовательность транзакций была одна и та же, не надо ничего согласовывать.
Да, я уже понял этот аргумент, и уже ответил, что такая архитектура не дает отказоустойчивости. А отказоустойчивость -- это весь смысл создания Calvin. Масштабируемость у него так-себе, поскольку для достижения оной придется серьезно переосмыслять принципы записи в БД.
Вот как раз при отказе одной из реплик всем надо договориться, какая последняя эпоха в этой реплике. Это единственное место, где нужен консенсус.
Ну, и кто его будет делать? ZooKeeper, в БД которого пусто?
hard_sign
11.11.2021 09:43ZooKeeper, в БД которого пусто?
Да. Достаточно в момент сбоя всем оставшимся секвенсерам/планировщикам написать, какой последний пакет они видели от пропавшего секвенсера, и выбрать наименьший. Ну или пусть тот, у кого есть наибольший, поделится с остальными – можно через Zookeeper.
byko3y Автор
11.11.2021 10:44Достаточно в момент сбоя всем оставшимся секвенсерам/планировщикам написать, какой последний пакет они видели от пропавшего секвенсера, и выбрать наименьший.
Спешу огорчить, что это даже не eventual consistency. Это "может быть подтвержденная транзакция останется в базе, а может быть нет", то есть, никаких гарантий персистентности. Например, клиент отправляет транзакцию секвенсеру, секвенсор подтверждает ее, ставит ее в очередь на отправку через сеть, и в этот момент весело пропадает из сети. Транзакция подтверждена, но про транзакцию никто в оставшейся сети никогда не слышал.
Конечно, можно решить проблему "в лоб" сделав синхронную репликацию. Правда, здесь внезапно возникает проблема -- как засчитывать успешность транзакции? Если по успешному ответу ото всех ведомых узлов, то система умрет при отказе одного ведомого узла. Если делать это через кворум, то по сути повторяешь всю логику подтверждения репликации Zab/Raft/MultiPaxos. И при отказе тебе придется решать, какой из узлов содержит корректные подтвержденные данные на основе данных, содержащихся в узлах. То есть, это копия логики ZooKeeper. Со всеми вытекающими, вроде долгого подтверждения транзакции и необходимостью гонять кучу данных о транзакциях по сети.
hard_sign
11.11.2021 10:54клиент отправляет транзакцию секвенсеру, секвенсор подтверждает ее
Да? А так можно?
А вы понимаете, что в кальвине, в отличие от классических систем типа Oracle, исход транзакции неизвестен до тех пор, пока вся последовательность операций не будет выполнена планировщиком? То есть секвенсер может сказать, что он понял, чего от него хочет приложение, но не может гарантировать выполнение транзакции.
byko3y Автор
11.11.2021 11:40А вы понимаете, что в кальвине, в отличие от классических систем типа Oracle, исход транзакции неизвестен до тех пор, пока вся последовательность операций не будет выполнена планировщиком? То есть секвенсер может сказать, что он понял, чего от него хочет приложение, но не может гарантировать выполнение транзакции.
Так или иначе, это значит одно -- клиент отослал запрос, но не знает, как этот запрос был обработан. Что я могу сказать -- удачи писать клиентский код под это дело.
hard_sign
11.11.2021 12:28удачи писать клиентский код под это дело.
Вот тут соглашусь на 100%.
Я вообще противник любых распределённых БД, поскольку убеждённость в том, что «распределённая БД ничем не отличается от монолитной, кроме размера» – крайне опасное заблуждение. Разработчики всё равно будут писать код как для обычной монолитной базы, и на «домашних» нагрузках это даже будет работать. А вот на реальных нагрузках всегда будут неожиданные трудноуловимые спецэффекты. И ещё раз повторю – это относится не только к Кальвину, а вообще ко всем распределённым БД (за исключением аналитических).
Если хочется строить большую распределённую систему, за образец надо брать Facebook.
byko3y Автор
11.11.2021 14:08Я вообще противник любых распределённых БД, поскольку убеждённость в том, что «распределённая БД ничем не отличается от монолитной, кроме размера» – крайне опасное заблуждение
Распределенные БД прекрасно дают гарантии, strong consistency, eventual consistency, да, их сложно делать, да, только несколько распределенных БД умеют в strong consistency, но это не повод говорить "давайте избегать распределенных БД" -- особенно если есть производственная потребность иметь таковую. Прототип Calvin потому и использовал ZooKeeper -- это был для них единственный способ сделать прототип отказоустойчивым.
Если хочется строить большую распределённую систему, за образец надо брать Facebook.
В каком смысле "брать за образец"? Лепить из чего попало?
hard_sign
11.11.2021 18:44особенно если есть производственная потребность иметь таковую
Не могу придумать «производственную потребность» под распределённую базу (ещё раз подчеркну, речь не об аналитической СУБД). Не поделитесь?
Лепить из чего попало?
Я не это имел в виду. Facebook состоит из множества шардов, данные каждого из которых хранятся в MySQL. При необходимости межшардовых транзакций организуется сага. На мой взгляд, такой подход намного более отказоустойчивый и масштабируемый, чем единая распределённая БД.
byko3y Автор
12.11.2021 13:34Не могу придумать «производственную потребность» под распределённую базу (ещё раз подчеркну, речь не об аналитической СУБД). Не поделитесь?
Поделюсь. 24/7 сервис, в котором нужно выводить из эксплуатации реплики и вводит в эксплуатацию другие, при этом есть ограничения на корректность информации. То есть, грубо говоря, баланс на счету пользователя, где недопустимо, чтобы он временно приобрел непонятное значение, мол "ща засинхронизируемся и всё норм будет" -- потому что начнется вой от пользователей "у вас тут система сломалась". Или пользователи участвуют в редактировании общего документа -- здесь я подчеркну, что достаточно поддерживать согласованность на уровне мелкого общего сервера, который используется для этих пользователей и этого документа, не обязательно иметь глобальную согласованность. Масштабирование через шардирование, короче говоря. И чтоб отдельный шард не выдавал непонятные результаты во время сбоя -- нужна строгая согласованность между репликами шарда. Никакими MySQL и сагами этого не сделать.
При необходимости межшардовых транзакций организуется сага. На мой взгляд, такой подход намного более отказоустойчивый и масштабируемый, чем единая распределённая БД.
Масштабируем -- да, отказоустойчив -- да. Но согласованности данных не будет даже при полном отсутствии отказов. То есть, то что поломано, не может сломаться.
hard_sign
12.11.2021 14:04+1Как человек, последние 15 лет работающий в банковском секторе, а до этого 6 лет в телекоме, я несколько удивлён приведёнными примерами. Достаточно поместить все счета клиента на один монолитный сервер – и никакого воя не будет. А то, что Вася деньги отправил, а Маша получила их только через 5 секунд вообще никого никогда не парило.
Пример с документами тем более непонятен.
Ещё раз подчеркну, я не «против распределённых систем», а против «распределённых БД». Фейсбук – система распределённая, но все БД там монолитные.
нужна строгая согласованность между репликами шарда. Никакими MySQL и сагами этого не сделать.
MySQL – не сделать, хотя вроде Алибаба и к MySQL прикрутила физическую репликацию. А вот любая другая монолитная БД – MS SQL, Oracle, PostgreSQL, DB2 – вполне. Ну и да, над ними маленький raft для автоматизации переключения :)
согласованности данных не будет даже при полном отсутствии отказов.
А это сильно зависит от требований к согласованности.
byko3y Автор
12.11.2021 18:02Как человек, последние 15 лет работающий в банковском секторе, а до этого 6 лет в телекоме, я несколько удивлён приведёнными примерами.
Я не знаю про телеком, мой скромный опыт говорит про то, что там немало годных спецов, но банковский сектор, именно сами банки -- это помойка, ржавая и загнившая с концами, с зависшими банкоматами, с зарезервированными средствами, для пользования которыми нужно ждать окончания операционного дня, говно-SPA на jQuery и React одновременно с кучей ошибок, через которые регулярно не получается то одно оплатить, то другой услугой воспользоваться. Вот чего там точно нет -- так это надежности и отказоустойчивости. Пока всё работает, каналы связи исправны, сервера стоят на ИБП -- вроде бы всё "отказоустойчиво". Как что-то падает -- начинается вой "у меня деньги со счетам списались, а никуда не пришли. Я в поддержку звоню-пишу, меня пускают по кругу".
Достаточно поместить все счета клиента на один монолитный сервер – и никакого воя не будет. А то, что Вася деньги отправил, а Маша получила их только через 5 секунд вообще никого никогда не парило.
Не в этом проблема. Хотя, нет никакого оправдания для того, чтобы транзакция проходила дольше секунды -- все просто привыкли, а разрабам в банке тем боеле пофигу, как работает их система. Проблема в том, что при отказе транзакция зависает в лимбо. Ту проблема, которую решил ZooKeeper, в банках предпочли просто не замечать, будто ее не существует. То есть, проще поставить помощнее UPS, бензиновый электрогенератор, чем париться отказоустойчивостью и распределенностью.
Как в этой системе обновлять сервера без остановки обработки транзакций? Да никак. Просто останавливают всё к чертям и вешают табличку на переднем веб-сервере "ведутся технические работы".
А вот любая другая монолитная БД – MS SQL, Oracle, PostgreSQL, DB2 – вполне. Ну и да, над ними маленький raft для автоматизации переключения
Может быть в лабораториях рейха такая БД и есть, но из публичных софтин ни одно решение не смогло показать отказоустойчивость. Да, реализации рафта и multi-paxos есть -- только они не работают. Ну то есть либо бьют данные при отказе, либо, как упомянутый выше Galera Cluster, портят данные даже при полном отсутствии отказов. Это не "маленький Raft" -- трудоемкость реализации отказоустойчивой БД на Raft сравнима с реализацией чего-то вроде InnoDB с нуля. И очень тяжело пояснить технически неграмотному заказчику/инвестору (а это 95% оных), почему вы пилите реализацию "маленького Raft" уже два года, а не сделали даже половины.
hard_sign
12.11.2021 18:26+1помойка, ржавая и загнившая с концами, с зависшими банкоматами,
Чувствуется, у вас что-то глубоко личное с корнями, уходящими в далёкое детство. В разных банках всё очень по-разному.
нет никакого оправдания для того, чтобы транзакция проходила дольше секунды
Сразу видно человека с богатым практическим опытом. Вот объясните – а зачем быстрее? Ответить человеку «ваша транзакция выполнена» надо быстро, тут SLA обычно полсекунды. Пока он звонит или пишет другу «отправил, лови», деньги дойдут до адресата. Можно вывернуться мехом внутрь и сделать быстрее, но зачем? Банк – это про зарабатывание денег, а не про компаративную фаллометрию.
что при отказе транзакция зависает в лимбо
Не зависает. Прочтите ещё раз, как работает сага.
Как в этой системе обновлять сервера без остановки обработки транзакций?
Смотря что вы понимаете под «обновлять сервера». Если обновление ОС и минорные патчи на СУБД, то спасает физическая репликация на уровне БД (DataGuard, AlwaysOn и т. п.) Если регламентные работы на БД, включая мажорные обновления, и накат новых версий ПО, подразумевающих изменение модели данных, то тут – логическая репликация. С одним, заметьте, лидером.
из публичных софтин ни одно решение не смогло показать отказоустойчивость. Да, реализации рафта и multi-paxos есть -- только они не работают.
Расскажите это разработчикам Oracle Observer и etcd.
Читайте внимательно – маленький raft не для хранения данных, а для автоматизации переключения.
byko3y Автор
12.11.2021 21:24Чувствуется, у вас что-то глубоко личное с корнями, уходящими в далёкое детство. В разных банках всё очень по-разному.
С радостью изменю свое мнение, если узнаю про хотя бы один банк, где это не так.
Сразу видно человека с богатым практическим опытом. Вот объясните – а зачем быстрее?
Можно вывернуться мехом внутрь и сделать быстрее, но зачем? Банк – это про зарабатывание денег, а не про компаративную фаллометрию.
Я сразу написал, что это играет мало значения, но ты решил придраться. Я просто иронично вскользь упомянул забавный феномен IT индустрии "софт будет выполнен настолько плохо, насколько это возможно". То есть, пока этого хватает -- никто не пошевелит и пальцем. И не надо мне рассказывать, что бедный региональный банк с чистой прибылью в $1 млрд в год не может себе позволить потратить пару миллионов на разработку софта. Не говоря уже про крупняк. Проблема не в том, что у них нет денег -- проблема в том, что у них нет исполнителей и они не смогут их найти ни за какие миллиарды. Потому что дворник не сможет организовать конвеерное производство автомобилей.
>что при отказе транзакция зависает в лимбо
Не зависает. Прочтите ещё раз, как работает сага.
Спасибо, я читаю то, что ты мне пишешь. На живой системе не так-то просто вернуть взад сагу по моему хотению, по щучьему велению. Данные меняются, негодники такие. В этом как бы и вся сложность реализации глобально атомарных операций в распределенных системах, и от того, что у этой функции поменялась форма, сложность ее никуда не испарилась -- грамотная реализация саг по прежнему является крайне сложной задачей. Которую, к тому же, придется заново решать под каждую новую операцию -- именно потому возникло желание решить проблему атомарности раз и навсегда, чтобы потом можно было делать любые транзакции и получать атомарность добавлением одной опции.
Если регламентные работы на БД, включая мажорные обновления, и накат новых версий ПО, подразумевающих изменение модели данных, то тут – логическая репликация. С одним, заметьте, лидером.
Я не смог распарсить эту фразу. Лидер -- он на то и лидер, чтобы быть единственным.
Расскажите это разработчикам Oracle Observer и etcd.
Etcd я уже упомянул. Я так понимаю, что и его, и Google Chubby разработали в гугле. То есть, две из 3 существующих в индустрии strong consistency баз данных разработаны в гугле. Oracle Observer сам по себе не является отказоустойчивым, потому сравнивать его с etcd смешно.
hard_sign
12.11.2021 21:43-1хотя бы один банк, где это не так
Из того, что я знаю, – Сбер и Тинькофф.
не может себе позволить потратить пару миллионов на разработку софта
Да может и тратит. Но за эти деньги решаются другие задачи.
сложность реализации глобально атомарных операций в распределенных системах
Зачем «глобальная атомарность»? Что это за фетиш такой?
В научных экспериментах это нужно, в финансовых сервисах – нет.
грамотная реализация саг по прежнему является крайне сложной задачей
Даже не знаю, как это комментировать.
Эта тема столько раз разжёвана и переварена, что – – –
Лидер -- он на то и лидер, чтобы быть единственным.
В Zookeeper, которому мы тут полощем кости, лидер может меняться. В каждый конкретный момент он один, но если вдруг с лидером что-то случится, то Zookeeper сам принимает решение, кто станет новым лидером (собственно, весь zab/raft/paxos – об этом). А Oracle/PostgreSQL/etc сам такое решение принять не может – у него должен быть внешний переключатель, который для принятия решения использует что-то из перечисленного софта.
Я так понимаю, что его .. разработали в гугле.
Нет, это RedHat в рамках проекта CoreOS
Oracle Observer сам по себе не является отказоустойчивым
Я не понимаю, что вы вкладываете в понятие «отказоустойчивость» в данном случае. Он обеспечивает корректный выбор лидера в случае сбоя в HA-кластере Oracle – и этого достаточно. У Microsoft, IBM и Veritas есть аналогичные решения.
byko3y Автор
12.11.2021 22:39Зачем «глобальная атомарность»? Что это за фетиш такой?
Хорошо, локальная для реплицированного шарда. Одна эта задача по факту неподъемна для подавляющей части контор в IT индустрии.
Даже не знаю, как это комментировать.
Эта тема столько раз разжёвана и переварена, что – – –
Какая разница, сколько раз она пережевана -- это не уменьшает сложности реализации саг, и конкретно большого ручного труда по анализу и реализации.
если вдруг с лидером что-то случится, то Zookeeper сам принимает решение, кто станет новым лидером (собственно, весь zab/raft/paxos – об этом)
Нет. Выбрать лидера случайной задержкой ожидания -- это довольно просто. Не побить хранимые данные в результате этого процесса и при этом иметь приемлимую производительность -- это задача, которую удалось решить лишь нескольким разработчиком во всем мире. Ты повторяешь ту же самую ошибку "с данными как-нибудь разберемся". Как нибудь разберемся и что-то на выходе получим -- вот потому сохранности данных при отказах никто не может обеспечить, если не применяет ZooKeeper/etcd.
Я не понимаю, что вы вкладываете в понятие «отказоустойчивость» в данном случае. Он обеспечивает корректный выбор лидера в случае сбоя в HA-кластере Oracle – и этого достаточно.
Я имел в виду, что сам Observer -- это один узел, и с его отказом заканчивается вся отказоустойчивость системы. Но в целом у БД с Observer-ом некая отказоустойчивость есть, бесспорно, это лучше, чем ничего.
zvszvs
10.11.2021 03:58"Если мы возьмем первую инструкцию процесса 1, то параллельно с ней может выполниться любая из четырех команд."
Дальше читать не стал. Даже термин "скромный" мне показался бы оптимистично завышенным.
derKodt1
11.11.2021 10:06Два процесса выполняются параллельно и независимо
Тогда вопрос (по самому первому примеру) насчет независимого выполнения: в обоих потоках используются одни и те же переменные = уже как бы намек,. что жди беды, т.е. что рано или поздно возникнут коллизии (кроме того, насколько это из реальной жизни я имею в виду такое использование переменных)? Кроме того, второй поток - бесконечный цикл. Насколько это корректно, один из потоков делать таковым и насколько эта ситуация из реальной жизни.
Вообще, насколько грамотнее бы было тогда всю программу оформить в виде бесконечного цикла, а внутри него уже потоки организовывать?
byko3y Автор
11.11.2021 10:48Тогда вопрос (по самому первому примеру) насчет независимого выполнения: в обоих потоках используются одни и те же переменные = уже как бы намек,. что жди беды, т.е. что рано или поздно возникнут коллизии (кроме того, насколько это из реальной жизни я имею в виду такое использование переменных)? Кроме того, второй поток - бесконечный цикл. Насколько это корректно, один из потоков делать таковым и насколько эта ситуация из реальной жизни
Этот пример неявно подразумевает, что операция инкремента-декремента атомарна, то есть, это по сути lock-free алгоритм. Даже достаточно простые прикладные lock-free алгоритмы весьма мозгодробильны, потому я постарался не приводить никаких примеров из жизни.
Вообще, насколько грамотнее бы было тогда всю программу оформить в виде бесконечного цикла, а внутри него уже потоки организовывать?
Это очень распространенный прием в асинхронном и многопоточном программировании. Например, браузер, через который ты мне пишешь, в фундаменте своей работы имеет бесконечный цикл обработки событий. Сервер, с которого ты эту страницу получаешь, тоже работает на основе бесконечного цикла опроса соединений.
kein
А мы я вижу от скромности не страдаем :)
А по теме - отличная статья. К концу все-таки потерял нить рассуждения, возможно у моего мозгового слизня упал уровень сахара.
Вопрос - насколько реально легко использовать вещи вроде Coq для доказательства отсутствия дедлоков? Или это вообще не из той степи?
byko3y Автор
Сам себя не похвалишь - никто не похвалит.
Про попытки сделать автоматический доказыватель корректности многопоточной программы я слышал, но я слабо верю в их применимость к задачам сложнее обедающих философов, поскольку достаточно сложный и/или несериализуемый (https://en.wikipedia.org/wiki/Serializability) алгоритм может легко улететь в бесконечную сложность при наивном анализе выполнения. В начале статьи я упоминал пример с простыми четырьмя операциями и циклом из четырех инструкций, но в реальной задаче это может быть два бесконечных цикла с условиями внутри, для которых уже теоретически невозможно реализовать алгоритм, который хотя бы оценил конечность выполнения этих циклов (https://ru.wikipedia.org/wiki/Проблема_остановки), не говоря уже про корректность операций, которые будут в этих циклах исполняться. По этой причине эдак половина ноши "доказательства корректности" прежде всего заключается в том, чтобы не писать некорректные алгоритмы, которые никто не сможет проанализировать. То есть, не наращивать сложность алгоритма без причины.
ladle
Это так. Оставим скромность неудачникам - она их здорово украшает.
Из словаря Ожёгова
invasy
Фамилия лингвиста ведь Óжегов.
А скромности (где про тесты и команду) прибавляет bus factor.
ladle
Спасибо за замечание. Именно так - с ударением на первом слоге. Каюсь - всю жизнь произносил эту фамилию неправильно - и ведь никто, зараза, не поправил. И не подскажете ли - как правильно, Рерих или Рёрих?