Краткий ответ

Это классическая проблема ABA: CAS сравнивает текущее значение с ранее прочитанным и видит, что ссылка снова равна A, хотя между чтениями состояние успело измениться по схеме A → B → A. В результате CAS может успешно применить решение, основанное на устаревшем состоянии, и нарушить инварианты алгоритма.

Исторический контекст

CAS появился как базовый примитив для построения неблокирующих алгоритмов, которым не нужно удерживать монитор или явную блокировку. Он позволяет атомарно заменить значение только при сохранении ожидаемого состояния.

Проблема возникает потому, что обычный CAS проверяет лишь текущее значение, но не историю его изменений. Для ссылок в AtomicReference сравнивается именно идентичность объекта, поэтому возврат той же ссылки неотличим от отсутствия изменений.

Постановка проблемы

Поток может прочитать ссылку A и связанные с ней данные, после чего приостановиться. Другой поток изменит структуру, временно установит B, а затем снова установит A.

Первый поток выполнит CAS с ожидаемой ссылкой A, операция завершится успешно, но его решение уже не соответствует актуальному состоянию. В структурах вроде неблокирующего стека это может привести к потере узлов, восстановлению устаревшей связи или нарушению порядка элементов.

Подробное решение

Минимальная иллюстрация выглядит так:

import java.util.concurrent.atomic.AtomicReference;

public class AbaDemo {
    public static void main(String[] args) {
        Object a = new Object();
        AtomicReference<Object> ref = new AtomicReference<>(a);
        Object observed = ref.get();
        ref.set(new Object()); // B
        ref.set(a);            // A снова
        boolean success = ref.compareAndSet(observed, new Object());
        System.out.println(success); // true
    }
}

В реальном алгоритме промежуточные изменения выполняет другой поток, а не последовательные вызовы в одном потоке. CAS успешно срабатывает, потому что ссылка снова указывает на тот же объект A; факт промежуточного состояния B нигде не зафиксирован.

Один из вариантов решения — AtomicStampedReference. Вместе со ссылкой хранится метка версии: при каждом изменении увеличивается stamp, поэтому после перехода A → B → A ссылка прежняя, но версия уже другая. CAS проверяет обе части состояния атомарно.

Другой подход — не переиспользовать старые объекты и хранить всё состояние в новых неизменяемых снимках. Это уменьшает вероятность ABA, но требует аккуратной модели владения объектами и может увеличить количество выделений памяти.

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

Ситуация из практики

В неблокирующем стеке поток читает вершину A и её следующий элемент B. Пока он готовит CAS, другой поток снимает A, выполняет операции со стеком и снова помещает тот же объект A на вершину.

Рассматривались три варианта. synchronized проще всего проверить и сопровождать, но сериализует операции. Обычный AtomicReference сохраняет высокую производительность, однако допускает ABA. AtomicStampedReference добавляет метку версии и предотвращает принятие устаревшего снимка, хотя требует обновлять ссылку и stamp согласованно.

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

Что кандидаты часто упускают

Достаточно ли объявить ссылку volatile, чтобы устранить ABA?

Нет. Volatile обеспечивает видимость и определённый порядок публикации операций с этим полем, но не сохраняет историю промежуточных значений. Последовательность A → B → A по-прежнему может выглядеть для CAS как неизменившееся значение. Для защиты перехода состояния нужна версия, блокировка или иной механизм, учитывающий сам факт изменений.

Сравнивает ли AtomicReference значения через equals?

Нет. Для ссылок атомарное сравнение в AtomicReference основано на идентичности ссылок, то есть на том, указывают ли ожидаемое и текущее значения на один объект. Переопределение equals не изменяет поведение CAS.

Это важно: даже логически равные, но разные объекты считаются разными ссылками, а один и тот же объект после промежуточных изменений считается прежним. Поэтому проблема ABA относится не к равенству бизнес-значений, а к недостаточности одного сравниваемого состояния.

Гарантирует ли AtomicStampedReference полное отсутствие ошибок в неблокирующем алгоритме?

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

Кроме ABA остаются ошибки проектирования инвариантов, неправильное освобождение или повторное использование объектов, starvation и чрезмерные повторы CAS при высокой конкуренции. Метка имеет конечный диапазон, поэтому при переполнении версии теоретически возможен повтор старого stamp; если это существенно, применяют более подходящую схему версионирования или блокировку.