Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 53
Закреплённые комментарии
Мысли норм, но ужасное LLM-ное оформление с уродскими списками и таблицами очень огорчило. Плюсовал с горьким чувством.
Я так старался с таблицами. Что не так? Наверное, не оформление, а подача материала?
Что не так? Формулировки бесконечных списков от LLM: льёт воду, повторяя одно и то же разными словами. Читать такое - это насилие над мозгом. (imo)
При этом идея статьи - не побоюсь этого слова - шикарная, благодарю! Но реализация...
Ну не умеют LLM писать осмысленные тексты.¯\_(ツ)_/¯
Все так, не обращайте внимание. Нынче и за длинное тире линчуют, потому что якобы так делают только LLM.
Я вот уже 20 лет ставлю длинное тире везде и всегда, где это нужно и возможно, и формулирование мыслей у меня в голове завязано на представление информации в виде таблиц и списков. Даже не знаю, как теперь писать статьи на фоне таких капризов аудитории.
А, понял. Вы принципиально не любите классификаторы. А это статья - классификатор. )
Специально для вас поставлю теги
статья - классификатор, LLM, спискота
P.S. интересный вариант реализации на атомиках. Используется паттерн: фасады над общим State
Извините, сбился на Rust. Не хочу на Java, не понимаю до конца что там происходит.
// Order и Wallet как "view" на общий State
struct OrderView<'a> {
checkout: &'a Checkout,
}
impl<'a> OrderView<'a> {
fn status(&self) -> OrderStatus {
self.checkout.state.load().order.status.clone()
}
fn cancel(&self) -> Result<(), &'static str> {
loop {
let current = self.checkout.state.load();
if !matches!(current.order.status, OrderStatus::Pending) {
return Err("Cannot cancel");
}
let next = CheckoutState {
order: Order {
status: OrderStatus::Cancelled,
..current.order.clone()
},
wallet: current.wallet.clone(), // без изменений
};
if Arc::ptr_eq(
&self.checkout.state.compare_and_swap(¤t, Arc::new(next)),
¤t,
) {
return Ok(());
}
}
}
}
struct WalletView<'a> {
checkout: &'a Checkout,
}
impl<'a> WalletView<'a> {
fn balance(&self) -> i64 {
self.checkout.state.load().wallet.balance
}
fn top_up(&self, amount: i64) -> Result<(), &'static str> {
loop {
let current = self.checkout.state.load();
let next = CheckoutState {
order: current.order.clone(), // без изменений
wallet: Wallet {
balance: current.wallet.balance + amount,
..current.wallet.clone()
},
};
if Arc::ptr_eq(
&self.checkout.state.compare_and_swap(¤t, Arc::new(next)),
¤t,
) {
return Ok(());
}
}
}
}
// Использование
impl Checkout {
fn order_view(&self) -> OrderView {
OrderView { checkout: self }
}
fn wallet_view(&self) -> WalletView {
WalletView { checkout: self }
}
}Интересен тем, что соединяет строгую консистентность и нормальную модульность кода, не скатываясь ни в «гигантский God‑object», ни в «зоопарк из объектов с рассинхронизацией».
Две независимые бизнес логики поведения объектов и единая модель консистентности
Есть одна ячейка (AtomicReference / ArcSwap), где лежит весь State.
Фасады (OrderView, WalletView и т.п.) не держат у себя состояние, они каждый раз:
-читают State из атомика;
-строят на его основе новый State;
-пытаются записать его обратно через CAS;
-при конфликте — повторяют
Извините, сбился на Rust. Не хочу на Java, не понимаю до конца что там происходит.
Ничего удивительно, так как Rust на это в принципе не способен без unsafe (изменять один объект из нескольких потоков)
Согласен.
Не подумал, что Rust умеет лучше. Вот полный код с мьютексом, Compute выполняется ровно один раз, не выбрасывается при конфликте.
use std::sync::{Arc, Mutex, MutexGuard, PoisonError};
// ================== Ошибки ==================
#[derive(Debug)]
enum ShopError {
InsufficientFunds { available: i32, required: i32 },
OrderNotPending,
LockPoisoned,
}
impl<T> From<PoisonError<T>> for ShopError {
fn from(_: PoisonError<T>) -> Self {
ShopError::LockPoisoned
}
}
// ================== Доменные объекты ==================
#[derive(Debug, Clone, PartialEq)]
enum OrderStatus {
Pending,
Paid,
Cancelled,
}
#[derive(Debug)]
struct Order {
id: u32,
status: OrderStatus,
total: i32,
}
#[derive(Debug)]
struct Wallet {
balance: i32,
}
impl Order {
fn mark_paid(&mut self) -> Result<(), ShopError> {
if self.status != OrderStatus::Pending {
return Err(ShopError::OrderNotPending);
}
self.status = OrderStatus::Paid;
Ok(())
}
}
impl Wallet {
fn withdraw(&mut self, amount: i32) -> Result<(), ShopError> {
if self.balance < amount {
return Err(ShopError::InsufficientFunds {
available: self.balance,
required: amount,
});
}
self.balance -= amount;
Ok(())
}
}
// ================== Агрегат ==================
struct CheckoutState {
order: Order,
wallet: Wallet,
}
struct Shop {
state: Mutex<CheckoutState>,
}
impl Shop {
fn new(order: Order, wallet: Wallet) -> Self {
Shop {
state: Mutex::new(CheckoutState { order, wallet }),
}
}
fn pay(&self) -> Result<(), ShopError> {
let mut state = self.state.lock()?;
let amount = state.order.total;
// Сначала списываем деньги
state.wallet.withdraw(amount)?;
// Потом помечаем заказ оплаченным
// Если тут ошибка — деньги уже списаны, но мы под локом,
// поэтому можно откатить или паниковать
if let Err(e) = state.order.mark_paid() {
// Откат
state.wallet.balance += amount;
return Err(e);
}
Ok(())
}
fn get_balance(&self) -> Result<i32, ShopError> {
let state = self.state.lock()?;
Ok(state.wallet.balance)
}
fn get_order_status(&self) -> Result<OrderStatus, ShopError> {
let state = self.state.lock()?;
Ok(state.order.status.clone())
}
}
// ================== Использование ==================
fn main() {
let shop = Arc::new(Shop::new(
Order {
id: 1,
status: OrderStatus::Pending,
total: 100,
},
Wallet { balance: 500 },
));
match shop.pay() {
Ok(()) => println!("Оплата прошла"),
Err(ShopError::InsufficientFunds { available, required }) => {
println!("Недостаточно средств: {} из {}", available, required);
}
Err(ShopError::OrderNotPending) => {
println!("Заказ уже оплачен или отменён");
}
Err(ShopError::LockPoisoned) => {
println!("Критическая ошибка: mutex poisoned");
}
}
// Проверяем состояние
if let Ok(balance) = shop.get_balance() {
println!("Баланс: {}", balance);
}
if let Ok(status) = shop.get_order_status() {
println!("Статус заказа: {:?}", status);
}
}
Спасибо за статью, интересная мысль для расмышления
Параллельная запись разрешена?├── Нет ==> [2] Single Writer (ждём очереди)└── Да ==> Проверяем конфликт? ├── Да ==> [1] First Win (retry/abort) └── Нет ==> [3] Last Win (затирание)
Мне не понравилась таксономия. ждём очереди , а почему например не стоим в стеке? Проверяем конфликт , а зачем проверять если разрешено параллельно? А в какой момент уже можно читать? А CommunicatingSequentialProcesses Хоаре куда отнести?
Классификация мне кажется противоречивой и не исчерпывающей...
Здесь слово «очередь» используется не как структура данных (FIFO), а как механизм сериализации.
Суть Стратегии 2 — Single Writer. Чтобы обеспечить доступ только одного писателя, всех остальных нужно куда-то деть
Стратегия 1 (Optimistic) разрешает параллельное вычисление нового состояния (compute). Но она не может разрешить параллельную запись (commit), иначе мы получим гонку (Strategy 3).
Проверка (compareAndSet) нужна именно для того, чтобы убедиться: пока мы вычисляли S', база S не изменилась.
Дальше
CSP Хоара (как и указанные в статье Go channels) относится к Стратегии 2.2 (Очередь/Single Writer).
В CSP процессы не имеют разделяемой памяти. Они обмениваются сообщениями через каналы.
Если несколько процессов пишут в один канал, а читает из него один процесс-владелец данных — это классическая сериализация доступа через очередь (канал). Владелец данных меняет состояние последовательно, обрабатывая сообщения по одному
Про чтение:
Классификация описывает стратегии разрешения конфликтов при записи (Write Conflict Resolution), так как именно запись нарушает инварианты.
Чтение зависит от реализации:
В Стратегии 1 (CAS) чтение обычно volatile или atomic load (lock-free).
В Стратегии 2 (Mutex) чтение часто тоже под локом (чтобы не прочитать "грязные" данные).
В Стратегии 2.2 (Actor) чтение — это отправка сообщения get и ожидание ответа.
По мне стратегии 1 и 3 очень странные. Два потока никак не могут менять одни и те же данные одновременно, иначе в памяти будет хаос. Даже если вы провели все расчеты параллельно, то перед записью нужно будет кому-то ждать, пока кто-то другой не завершит запись целиком. При таком раскладе в чём вообще суть First Win? Если нужна такая стратегия, то просто не нужно создавать второй поток и грузить систему, если первый уже взялся делать работу, разве нет? А Last Win ничем абсолютно не будет отличаться от Single write. Сначала один записал данные, потом второй. Кто последний - того данные и остались.
За счёт того, что «момент записи» сводится к одной атомарной операции над одной ячейкой памяти.
Вариантов по сути два:
1) Аппаратно‑атомарная инструкция CPU: CAS / атомарный RMW (compare‑and‑swap, fetch‑add и т.п.) над одним машинным словом. На уровне языка это std::atomic<T>, AtomicReference, AtomicLong и т.п. Процессор и протокол кеш‑когерентности гарантируют, что в каждый момент времени только одно ядро «владеет» этой строкой кеша и выполняет операцию целиком.
2) Лок (мьютекс/монитор). Тогда «один момент записи» обеспечивается тем, что в критическую секцию с обычной записью пускают только один поток.
В First Win речь именно о первом варианте: CAS делает read‑modify‑write над одной ячейкой за один неделимый шаг, всё остальное (валидация, вычисления) происходит вне этого шага и может выполняться параллельно.
Автор вынес за скобки обновление структурированных данных, он свёл задачу к обновлению чего-то одного. В примере с OrderService он выкрутился тем, что OrderState - иммутабельный , метод apply() создаёт изменённую копию, и нужно только переставить атомарную глобальную ссылку на созданную копию.
Насчёт того, зачем нужен First Win. Отличие варианта 1 от варианта 2 в том, что вариант 1 - оптимистический: сделал работу, веря, что результат удастся сохранить, потом пытаемся сохранить, а вариант 2 - пессимистический, не верим, что никто не обновит за то время, пока работаем, поэтому блокируемся. В некоторых случаях оптимистичный вариант лучше.
В качестве одного из способов, как сделать single writer (я бы назвал exclusive writer), предложена блокировка/mutex. Кстати, самый распространённый способ, как блокировку можно реализовать - это использовать First Win для ячейки памяти, пометив её идентификатором потока-владельца. И хотя это внутренние детали реализации примитива синхронизации, получается так что способ 2 достигается применением способа 1. С очередями аналогичная история.
Автор вынес за скобки обновление структурированных данных
Именно так. Новый иммутабельный экземпляр и атомарно переставим ссылку. Но что если это слишком дорого?
Копируй только то, что изменилось. Остальное переиспользуй по ссылке. Не разрушать структуру, а разбить её на логические блоки, обернутые в Arc (Rust) или просто объекты (Java/C#). При создании "копии" переносить ссылки на неизменённые блоки. Для больших коллекций использовать Persistent Collections (im в Rust, PCollections в Java).
В Haskell это Линзы (Lenses), Призмы (Prisms) и Оптика, функциональный ответ на вопрос «Как менять глубоко вложенные данные, не копируя весь мир и не сходя с ума от бойлерплейта».
Завтра напишу подробней
First Win для ячейки памяти, пометив её идентификатором потока-владельца
Это есть в статье
я бы назвал exclusive writer
Я бы тоже, но термин уже есть https://www.architecture-weekly.com/p/architecture-weekly-190-queuing-backpressure
При атомарной записи через compare exchange сначала один запишет своё, затем второй. Нужно проверять не изменилось ли значение перед записью. И возникает тот же вопрос - зачем? Два потока грузят процессор, затем один записал свои результаты, второй уничтожил. Смысл было запускать второй? Если нужно, чтобы результаты были только от первого, то второй и не имеет смысла стартовать, пока первый работает.
поток A: read S0 ==> compute S1 ==> CAS(S0==>S1) успех
поток B: read S0 ==> compute S2 ==> CAS(S0==>S2) конфликт
read S1 ==> compute S3 ==> CAS(S1==>S3) успех
Второй уничтожил данные, которые рассчитал, исходя из старого значения ячейки памяти. Он зачитает обновлённые данные, заново пересчитает, скорее всего получит другое значение по сравнению с первой попыткой, и сохранит. Итого в памяти окажется результат выполнения двух действий, а не только первого.
Предположу, что вариант с перерасчётом уместен когда вероятность коллизии не очень высокая, а само вычисление простое (к примеру, сложение значения с переменной - обновление единой суммарной глобальной метрики накопленными в рабочих потоках значениями), и пересчитать дешевле, чем блокировать/отпускать/висеть на спинлоке каждый раз.
В этом подходе есть что-то интересное. Но пока что из него тяжело что-то извлечь. Таксономию можно строить как угодно и в ней может быть столько веток, сколько пожелает автор. Поэтому эти 3 варианта сами по себе ценности не несут.
Вопрос в том, как данной таксономией воспользоваться. Не хватает какого-то описания, как её применить для решения задач. И что гораздо важнее: а какие вообще задачи решаются. Этот вопрос в утрированной форме отражён в комментариях выше: а зачем вообще нужно что-то кроме мютекса?
Говоря о самой таксономии, мне кажется упущен один важный класс: native rmw. Этот класс включает в себя выполнение мутирующей операции за одну инструкцию. Например, атомарный инкремент часто компилируется в одну процессорную инструкцию. Хотя данный класс очень похож на 1-ый(cas-loop), он принципиально отличается отсутствием контеншена.
Last write wins
Вообще говоря так писать не очень хорошо. Поскольку у нас порядка между записями, то что такое "последняя запись" сказать сложно. Эта тонкая неоднозначность формулировок становится особенно видна когда появляются всякие visibility, ordering и happens before. Чуть корректнее говорить "some write wins".
P.S. В языках с gc ABA проблема почти никогда не возникает (разве что в интрузивных структурах данных — и то в каких-то патологических юзкейсах). Поэтому не очень понятно при чём здесь это.
P.P.S. CRDT это вообще не в ту степь. Они вообще не решают проблему мутации одного объекта — они рассматривают проблему мутации нескольких независимых копий. Поэтому кажется совсем не в тему (ну и тогда уже тащить также и OT, т.к. он гораздо чаще используется в рамках одного процесса).
Вопрос в том, как данной таксономией воспользоваться.
да очень просто. Вот делаешь ты систему бронирования билетов в кино(поезд, отель и т.д.) и думаешь. А ведь пользователи-то могут паралельно одно и тоже забукать, вот беда. Что же делать? Ну и тут приходи на ум эта статья: ба, так вариантов всего три, или оптимистиная блокировка (двое выбрали место, потом думают, потом кто раньше оплатил тот молодец, остальные получают ошибку и отваливаются) или пессимистичная - (кто первый выбрал место, то для остальных оно уже недоступно, так что второй увидит надпись - "мест нет". Хотя они могут потом и появится, т.к. блок снимится если не будет оплаты в течении получаса. Ну или третий вариант (кто поледний тот и получил билет) но для реального букинга это конечно не серьезно. ибо первый приедет в аэропорт, а ему - "извините, ваш билет продали другому, не повезло"
Я не сильно вчитывался, но как минимум бросилось в глаза что не учитывается случай когда переменная где-то там валяется в L-кэше и актуальна только для одного потока. В этом случае стратегия LastWin работает несколько непредсказуемо.
Ещё один ньюанс -- меняем что-то не атомарное, а значит при подходе LastWin у нас получаются данные в перемешку, а не "кто последний, тот и записал". Вроде в конце про это заикнулись, но без подробностей.
И вот таких моментов можно указать много и выходит что "сведём всё к трём решениям" обрастает исключениями и уточнениями. И собственно вопрос -- это точно упрощает понимание когда и что делать? Может всё-таки та куча материала по многопоточности появилась не просто так?
Красавчик!
Четко и по делу.
Положу в закладки, джунам рассылать. Очень толковый материал, спасибо!
Ответов ровно три:
Один победит, другой переделает работу (First Win + Retry)
Один подождёт, пока другой закончит (Single Writer)
Последний затрёт первого (Last Win)
меня терзают смутные сомнения: 3. это не то же самое что и 1. ? Что значит Один победит, другой переделает работу ? В каком смысле победит?
Это действительно дает повод подозревать бездумное копирование вывода LLM, потому что выглядит так что не беспокоит как это человек может понять.
1 конфликт обнаруживается и разрешается
3 конфликт игнорируется
что-то очень сомнительно что Retry можно перевести как "разрешается". Насколько я понимаю операция повторяется до тех пор пока не будет подтверждено без конфликтное завершение. Эта формулировка как раз определяет условия применения такой синхронизации, только когда наложения достаточно редки и стоимость повторения операции не большая.
Вообще я тоже хотел когда-нибудь написать что варианты синхронизации по пальцам можно пересчитать. Идея статьи мне нравится, но хотелось бы увидеть больше уважения-человечности (что ли) к читателю. Но может я слишком многого хочу от представителя лучшего мира :) .
Есть ли какой-либо навигатор: какой мат-аппарат может быть применен в рассматриваемом случае? Плюсы и минусы того же CSP Хоара, может Сети Петри могут подобное?
Можно вопрос поконкретнее?
На пальцах: оптимизм полезен когда матожидание плюсов (отсутствие блокировки, узкого горлышка) превышает матожидание минусов (повторный расчёт в случае неудачи). Кстати, есть адаптивный механизм: 3 неудачи и тогда блокировка остальных.
Блокировки на уровне системного потока или на уровне собственной очереди.
Важное наблюдение: классическое ООП не имеет модели конкурентности.
И что теперь - застрелиться?
Только, во-первых, многопоточность внедряется в ООП по щелчку (что уже фактически сделано).. А, во-вторых, важное замечание, параллелизм в ООП можно организовать без всякой многопоточности и тогда что делать с Вашими советами (и первом и втором случаях)?
И еще. Важное наблюдение: если два объекта и более пытаются изменить одновременно один объект, то это или грубейшая ошибка разработчика, или осознанные действия. В первом случае ни какие советы не помогут, да и во втором, кстати, тоже ;)
Не смешно
Согласен - печально. Оказывается, чтобы решить такую достаточно простую проблему, нужно продираться сквозь такие "кушири". Что уж печальнее может быть :(
Например. Как помогут эти знания решить проблему философов? Там, ведь, есть общий ресурс - вилка и минимум два процесса - философы, которые ее домогаются.
Оптимист начнет работу, надеясь что его не опередят.
Пессимист подождёт
Реалист будет всячески избегать блокировок, задержек и ожиданий.
P.s. Хотя, не обязательно. Есть те люди и случаи, когда всё равно (действительно и/или пофигистически :).
В параллельном программировании задержек не избежать, ожиданий, если процессы взаимодействующие, тоже, блокировок - зависит целиком от Вас. От того, как Вы будете решать проблему.
Кстати, что там с лошадью (или телегой?). Задача - философы поставлена, а где "детали"? Или это так - ля-ля? Не мОгем? Минусовать-то много ума не надо... ;)
Хорошая статья. Как пример, как не надо писать статьи. Прям в кабинет мер и весов плохих статей.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Три способа менять один объект из нескольких потоков. Больше нет