Транзакционная память: проверить и опубликовать вместе

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Нужно перевести пять единиц со счёта A на B и согласованно изменить оба остатка, сохранив общую сумму. Замки отдельных операций корректны, но вызывающая функция должна знать, какие замки захватить и в каком порядке. Можно ли выразить «выполни эти изменения вместе» и поручить конфликты механизму исполнения? Цена такого удобства - возможность отмены уже сделанной работы.

На что это похоже

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

Механизм: от определения к алгоритму

Транзакция памяти задаёт атомарную область чтений и записей. Успешные транзакции должны соответствовать некоторому допустимому последовательному порядку. Сильные модели вроде opacity требуют согласованного наблюдения также для незавершившихся и отменённых попыток: даже временный противоречивый указатель способен вызвать ошибку до проверки на commit. Точный контракт зависит от системы.

В STM типичная попытка собирает множество чтений с версиями и буфер записей. На commit проверяет версии и публикует изменения с необходимой синхронизацией. При конфликте попытка отбрасывается. Простая глобальная блокировка commit достаточна для учебной модели ниже, но снижает параллелизм. Более сложные системы используют раздельные метаданные, проверку в ходе чтения и менеджер конфликтов.

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

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

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

Правило

Повторяемая область должна иметь проверяемый набор зависимостей и отложенную публикацию; побочные эффекты и запасной путь требуют отдельного протокола.

Разбор: проследим вычисление

Ниже последовательно разыграны две конкурирующие попытки с проверкой версий. Обе прочитали старое значение A, первая публикуется, вторая отвергается и пересчитывается. Это модель конфликта и commit, не готовая потокобезопасная библиотека: проверка и публикация показаны одной функцией, в реальном исполнении их нужно защитить атомарным протоколом. Первое чтение сохраняет и значение, и его версию, повторное возвращает сохранённое. Модель считает захват этой пары одним шагом: реальная STM синхронизирует и чтение метаданных. Это ещё не opacity: согласованность разных чтений внутри отменяемой попытки требует более сильного протокола, чем одна проверка перед публикацией.

values = {'A': 20, 'B': 0}
versions = {'A': 0, 'B': 0}

def begin():
    return {'read': {}, 'seen': {}, 'write': {}}

def read(tx, key):
    if key in tx['write']:
        return tx['write'][key]
    if key not in tx['read']:
        tx['read'][key] = versions[key]
        tx['seen'][key] = values[key]
    return tx['seen'][key]

def transfer(tx, amount):
    a, b = read(tx, 'A'), read(tx, 'B')
    assert a >= amount
    tx['write'].update(A=a-amount, B=b+amount)

def commit(tx):
    # В модели другие шаги между проверкой и публикацией не идут.
    if any(versions[k] != v for k, v in tx['read'].items()):
        return False
    for key, value in tx['write'].items():
        values[key] = value
        versions[key] += 1
    return True

first, second = begin(), begin()
transfer(first, 5)
transfer(second, 5)
print('первая', commit(first))
print('вторая устарела', not commit(second))
retry = begin()
transfer(retry, 5)
assert commit(retry)
assert sum(values.values()) == 20
print('после повтора', values)
print('сумма', sum(values.values()))

# Повторное чтение не должно затирать первую версию.
values.update(A=20, B=0)
versions.update(A=0, B=0)
old = begin()
first_a = read(old, 'A')
other = begin()
transfer(other, 5)
assert commit(other)
assert read(old, 'A') == first_a
old['write']['A'] = first_a - 3
print('повторное чтение: устаревшая попытка отклонена', not commit(old))
assert values == {'A': 15, 'B': 5}

первая True
вторая устарела True
после повтора {'A': 10, 'B': 10}
сумма 20
повторное чтение: устаревшая попытка отклонена True

Разбор: где проходит граница

Добавь в transfer немедленную отправку письма «перевод выполнен». Вторая попытка отправит письмо, затем обнаружит конфликт и отменится; повтор отправит его снова. В памяти перевод случился один раз, во внешнем мире письма два. Значит, корректность commit не доказывает корректность всей операции приложения. Нужно хранить намерение отправки и отдельно обеспечивать выбранную семантику доставки.

Что ломается без этого

Проверка версий без защиты публикации позволяет двум commit пройти одну и ту же проверку. Слепой перезапуск операции с побочным эффектом дублирует его. Длинные конфликтующие транзакции могут постоянно отменять друг друга и тратить больше работы, чем замок. HTM без корректного fallback способен зависнуть на транзакции, которая всегда превышает ёмкость отслеживаемых данных. Это ограничение не лечится числом повторов.

Зачем это в работе

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

Теперь сам

Две транзакции прочитали A=10 с версией 3. Первая записала A=9 и версию 4. Может ли вторая успешно публиковаться без повторного чтения? Сколько писем допустимо отправить до commit, если обещана отправка только о состоявшихся переводах?