Ref и STM: координированные изменения

Главная мысль урока: атом меняет одну ссылку, а ref меняет несколько ссылок сразу и согласованно. Транзакция dosync видит мир как снимок, при конфликте перезапускается с начала и поэтому не терпит побочных эффектов внутри.

Ирма отдаёт Тиму зелье. В мире игры это два изменения: из сумки Ирмы зелье пропадает, в сумке Тима появляется. Если сумки лежат в двух атомах из урока про атом, между двумя swap! есть мгновение, когда зелья нет ни у кого. Посмотри сам:

Здесь всё выполняется по очереди, и «дыру» видишь только ты. В настоящей игре в эту дыру попадёт кто угодно: поток, который сохраняет мир на диск, или поток, который считает предметы для таблицы рекордов. Сохранение запишет мир, где зелье исчезло. Если поменять порядок swap!, будет мир, где зелий два.

Одно решение ты уже знаешь: сложить обе сумки в один атом, и тогда один swap! поменяет обе. Для маленькой игры так и делают. Но когда героев тысячи и каждая пара обменивается вещами независимо, один атом становится бутылочным горлышком: все swap! дерутся за одну ссылку, даже если трогают разных героев. Нужны отдельные ссылки, которые умеют меняться вместе. Это ref.

Ref и dosync

Ref выглядит как атом: создаётся функцией ref, читается через @. Разница в том, как он меняется. Менять ref можно только внутри dosync, и все изменения внутри одного dosync становятся видны другим потокам разом, в момент коммита.

В браузерной песочнице ref нет: ClojureScript однопоточный, и координировать там некого. Поэтому весь код дальше это листинги на настоящем Clojure, проверенные в babashka. Скопируй любой в файл и запусти bb file.clj.

(def irma-bag (ref #{:potion :rope}))
(def tim-bag (ref #{:sword}))

(defn give! [from to item]
  (dosync
    (when-not (contains? @from item)
      (throw (ex-info "нечего отдавать" {:item item})))
    (alter from disj item)
    (alter to conj item)))

(give! irma-bag tim-bag :potion)
(assert (= #{:rope} @irma-bag))
(assert (= #{:sword :potion} @tim-bag))

;; Исключение откатывает транзакцию целиком: сумки не тронуты.
(println (try (give! irma-bag tim-bag :potion)
              (catch Exception e (ex-message e))))
(assert (= #{:rope} @irma-bag))

alter работает как swap! для ref: берёт функцию и аргументы и применяет их к текущему значению. Его соседа ref-set используют, когда новое значение известно целиком, как reset! у атома. Обе функции вне dosync бросают IllegalStateException: случайно поменять ref мимо транзакции нельзя.

Весь блок dosync это транзакция. Она атомарна: либо обе сумки поменялись, либо ни одна. Второй вызов give! бросил исключение посреди транзакции, и Clojure выбросил всё, что транзакция успела насчитать. Отката руками писать не нужно.

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

(def irma-bag (ref #{:potion}))
(def tim-bag (ref #{}))

(defn give! [from to item]
  (dosync (alter from disj item) (alter to conj item)))

(def seen (atom #{}))
(def observer
  (future
    (dotimes [_ 10000]
      (let [n (dosync (count (filter :potion [@irma-bag @tim-bag])))]
        (swap! seen conj n)))))

(dotimes [_ 1000]
  (give! irma-bag tim-bag :potion)
  (give! tim-bag irma-bag :potion))
@observer

(println "наблюдатель видел зелий:" @seen)
(assert (= #{1} @seen))
(shutdown-agents)

Заметь, что наблюдатель тоже читает внутри dosync. Два @ вне транзакции прочитают ref в разные моменты, и между ними может пройти чужой коммит. Если значения нескольких ref связаны между собой, читай их одной транзакцией.

Как транзакция видит мир

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

Так устроена программная транзакционная память Clojure. Внутри это MVCC, как в PostgreSQL. По шагам:

1. Транзакция стартует и получает точку чтения, номер текущего момента мирового времени.
2. Каждое @ref внутри возвращает значение ref на эту точку. Чужие коммиты, случившиеся позже, транзакция не видит: у ref хранится несколько последних версий.
3. alter и ref-set пишут новое значение в личный журнал транзакции. Сама транзакция видит своё новое значение, остальные потоки видят старое.
4. На выходе из dosync транзакция захватывает ref, которые меняла, и проверяет: не коммитил ли кто-то в них после её точки чтения.
5. Если нет, журнал применяется разом, и все изменения видны миру. Если да, журнал выбрасывается, и тело dosync выполняется заново, с новой точкой чтения.

поток A:  start(t=5) ─ читает @gold=10 ─ alter → 11 ─────── commit? конфликт! ─ повтор(t=6) ─ @gold=11 → 12 ─ commit ✓
поток B:        start(t=5) ─ читает @gold=10 ─ alter → 11 ─ commit ✓ (t=6)

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

Повтор транзакции

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

(def gold (ref 0))
(def attempts (atom 0))

(defn pay! []
  (dosync
    (swap! attempts inc)     ; атом здесь нарочно: он не откатывается
    (alter gold inc)
    (Thread/sleep 5)))       ; длинная транзакция, чтобы потоки столкнулись

(run! deref (doall (repeatedly 10 #(future (pay!)))))

(println "золото:" @gold "попыток:" @attempts)
(assert (= 10 @gold))
(assert (>= @attempts 10))
(shutdown-agents)

На моей машине вышло золото: 10 попыток: 55. Казна сошлась, потому что каждая неудачная попытка выбросила свой журнал. А вот атом откатить нельзя, он насчитал все пятьдесят пять запусков. Замени swap! на println, и строка напечатается пятьдесят пять раз. Замени на списание денег с карты игрока, и игрок заплатит пять раз за одну покупку.

Отсюда правило: тело dosync должно быть чистым по отношению к миру вне ref. Читать ref, считать, писать в ref можно. Печатать, ходить в сеть, писать в файл, трогать атомы нельзя.

Clojure помогает соблюсти правило макросом io!. Оберни им функцию с побочным эффектом, и её вызов внутри транзакции бросит IllegalStateException с сообщением I/O in transaction. Babashka io! не поддерживает, поэтому этот листинг без проверки:

(defn save-world! [world]
  (io! (spit "world.edn" (pr-str world))))

(dosync (save-world! @world))   ; IllegalStateException: I/O in transaction

Что делать, если эффект нужен по итогам транзакции? Отправить его агенту. send внутри dosync придерживается до коммита: сколько бы раз ни повторилось тело, агент получит действие ровно один раз, после успеха.

(def gold (ref 0))
(def journal (agent []))
(def attempts (atom 0))

(run! deref
      (doall (for [hero ["Ирма" "Тим" "Ой" "Ирма" "Тим"]]
               (future
                 (dosync
                   (swap! attempts inc)
                   (alter gold inc)
                   (Thread/sleep 5)
                   (send journal conj (str hero " заплатил")))))))
(await journal)

(println "попыток:" @attempts "записей в журнале:" (count @journal))
(assert (= 5 (count @journal)))
(shutdown-agents)

Про агентов подробно в следующем уроке.

commute: когда порядок не важен

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

Для таких изменений есть commute. Он говорит STM: «эта функция коммутативна, порядок применения не важен». На коммите Clojure не проверяет конфликт по такому ref, а заново применяет функцию к самому свежему значению.

(def kills (ref 0))
(def attempts (atom 0))

(run! deref
      (doall (repeatedly 10 #(future
                               (dosync
                                 (swap! attempts inc)
                                 (commute kills inc)
                                 (Thread/sleep 5))))))

(println "убито:" @kills "попыток:" @attempts)
(assert (= 10 @kills))
(assert (= 10 @attempts))
(shutdown-agents)

Ни одного повтора. Цена в том, что значение, которое транзакция видит после commute, может не совпасть с тем, что попадёт в мир: на коммите функция применится ещё раз к чужому свежему числу. Поэтому commute годится для счётчиков, журналов и множеств, а для перевода между сумками нет. Если give! проверяет, есть ли предмет, ей нужен alter, иначе проверка пройдёт по устаревшему снимку.

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

У отряда правило: на страже всегда стоит хотя бы один целитель. Целителей двое, Ирма и Ой. Каждая хочет отдохнуть и проверяет: «если другая на посту, мне можно уйти».

(defn watch-night [use-ensure?]
  (let [irma (ref :on-duty)
        oi (ref :on-duty)
        rest! (fn [me other]
                (future
                  (dosync
                    (let [status (if use-ensure? (ensure other) @other)]
                      (Thread/sleep 50)
                      (when (= :on-duty status)
                        (ref-set me :resting))))))]
    (run! deref [(rest! irma oi) (rest! oi irma)])
    [@irma @oi]))

(println "без ensure:" (watch-night false))
(println "с ensure:  " (watch-night true))
(assert (= [:resting :resting] (watch-night false)))
(assert (= 1 (count (filter #{:on-duty} (watch-night true)))))
(shutdown-agents)

Без ensure обе ушли отдыхать, и стража пуста. Каждая транзакция по отдельности честная: прочитала соседку на посту, поменяла только себя. Конфликта на коммите нет, потому что они пишут в разные ref, а шаг 4 проверяет только записанные ref. Такая аномалия называется перекос записи, её знают все базы данных с изоляцией снимком.

ensure читает ref и обещает, что до коммита никто другой его не поменяет. Теперь соседка, прочитанная через ensure, защищена, и вторая транзакция при попытке записи упрётся в первую и повторится. На повторе она увидит, что соседка уже отдыхает, и останется на посту.

Три STM рядом

Транзакционная память есть не только в Clojure. Ты мог встретить её в Haskell и в Effect. Идея одна, решения разные:

	Clojure	Haskell	Effect
Ячейка	ref	TVar	TxRef
Граница транзакции	dosync	atomically	Effect.tx
Защита от эффектов	io! во время выполнения, дисциплина	тип STM a: эффект не скомпилируется	дисциплина: в v4 тип эффект внутри не запрещает
Ждать, пока данные изменятся	нет	retry	Effect.txRetry
Что проверяется на коммите	записанные ref и ensure	все прочитанные TVar	все прочитанные ячейки
Коммутативные изменения	commute	нет	нет

Самая заметная разница в первой строке про эффекты. Haskell не даст положить putStrLn в транзакцию: типы не сойдутся. Clojure динамический, и правило «без эффектов» держится на тебе и на io!. Effect четвёртой версии тоже доверяет дисциплине: Effect.tx вокруг обычного Effect.gen пропустит и лог, и сетевой вызов. Вторая разница в проверке на коммите: Haskell и Effect сверяют всё прочитанное, поэтому перекоса записи у них нет. Clojure сверяет только записанное, за это транзакции реже повторяются, а про чтения, от которых зависит решение, ты говоришь сам через ensure.

Когда ref не нужен

Честно о практике: ref в живых проектах на Clojure встречаются редко. Чаще всё состояние приложения лежит в одном атоме, а координацию даёт один swap! с чистой функцией над всем миром. Это проще читать и проще тестировать.

Ref оправдан, когда выполнены три условия сразу:

• сущностей много, и у каждой своя ссылка;
• изменение трогает несколько сущностей и должно быть атомарным;
• разные изменения трогают разные сущности, поэтому один атом стал бы горлышком.

Обмен вещами между тысячами героев подходит. Счётчик посещений сайта нет, ему хватит атома.

Проверь себя

Задание

Дальше

В следующем уроке последний ссылочный тип, агент, и три способа получить значение из будущего: future, promise и delay. А рядом с атомом и ref полезно ещё раз перечитать урок про модель идентичности: ref это та же идентичность, только с транзакцией вместо одного swap!.