Кратко и по делу — алгоритмы обнаружения/разблокировки и архитектурные меры против deadlock в распределённых транзакциях.
1) Обнаружение (detection)
- Централизованное WFG (wait‑for graph): каждый узел отсылает зависимости в централизованный детектор, цикл ищется алгоритмом поиска сильных компонент (например, Tarjan) за $\mathcal{O}(V+E)$. Плюс: простота; минус: точка отказа и сеть.
- Распределённые edge‑chasing (Chandy‑Misra‑Haas, probe): при ожидании посылается probe по цепочке держателей; если probe возвращается — найден цикл. Подходит без центрального координатора, но генерирует трафик.
- Path‑pushing / distributed DFS: каждый узел проталкивает пути ожидания, обнаружение цикла при совпадении. Различные варианты по сложности и сообщению.
- Гибрид: шардирование WFG — локальные детекторы + координация для межшардовых циклов.
2) Разблокировка (resolution / recovery)
- Выбор жертвы (victim selection): по политике — самый молодой/старый/минимальная стоимость/наименьшее количество удерживаемых ресурсов. Примеры правил:
- wait‑die: если $\mathrm{TS}(T_i)<\mathrm{TS}(T_j)$ — $T_i$ ждёт, иначе $T_i$ abort'ится.
- wound‑wait: если $\mathrm{TS}(T_i)<\mathrm{TS}(T_j)$ — $T_j$ прерывается (wounded), иначе $T_i$ ждёт.
- Принудительное прерывание (abort) и откат транзакции, освобождение локов, повтор с экспоненциальным бэкофом.
- Преквемпция/прерывание ресурсов (preemption) — взять ресурс у жертвы и продолжить.
- TTL/lease: автоматический таймаут захвата лока, после чего ресурс освобождается.
3) Избежание и профилактика (architectural patterns)
- Глобальный порядок блокировок: задать уникальный строгий порядок ресурсов (по ключу) и всегда брать локи в этом порядке — циклы исключены.
- Минимизировать распределённые блокировки:
- Саги (compensating transactions) вместо двухфазного commit; оркестрация/хореография для разбиения длинных транзакций.
- MVCC / optimistic concurrency control / snapshot isolation — уменьшает блокировки чтений/писей.
- Отказ от 2PC, где возможно; если нужен согласованный commit — использовать consensus (Raft/Paxos) на реплицируемом координаторе вместо распределённых блокировок.
- Централизованный lock service (Zookeeper/etcd/Consul): единый источник локаций и lease; проще контролировать таймауты и избежать распределённых циклов.
- Размещение данных/шардирование так, чтобы транзакции касались минимального числа шардов (локализация).
- Идемпотентность и компенсации: делать операции идемпотентными, чтобы безопасно рестартовать/отменять.
- Проектирование API/контрактов: возвращать предварительные резервации, асинхронные подтверждения, очереди задач — уменьшает число одновременно захваченных ресурсов.
4) Практические рекомендации
- Сочетать: глобальный порядок + TTL/lease + мониторинг WFG (централизованный на контролёре) + политикой выбора жертвы (минимальная стоимость).
- Логи и распределённые трейсеры для быстрой локализации циклов; предусмотреть автоматический откат по SLA.
- Предпочесть паттерны без блокировок (sagas, OCC, event‑driven), если бизнес допускает асинхронность.
Если нужно — могу кратко расписать конкретные реализации (Chandy‑Misra‑Haas, wait‑die/wound‑wait, пример политики выбора жертвы) или пример конфигурации lock service.