Можно ли реализовать mutex на хранилище, где только set и get?

Question

[Сергей Соколов]

В Redis есть замечательный алгоритм Redlock, позволяющий надёжно реализовать mutex (взаимное исключение) на распределённых хранилищах. Но он основан на операции вставки-если-ключа-нет (SET ... NX).

Возник вопрос: можно ли реализовать mutex на базе storage ВКонтакте, где есть только операции set( key, value) и get(key)? Есть метод utils.getServerTime() для получения серверного времени с точностью до секунд.

Задача скоординировать между собой несколько независимых агентов, чтобы в любой момент времени кто-то один из них брался за задачу. Единственная связь у них между собой – через это хранилище ВК.

Answer 1

[Сергей]

Нет. Операция проверить-ключ-вставить-новый - не атомарна.

Comments

[Сергей Соколов]

невозможность доказуема? Может, что-то придумать с общим сервером времени, который возвращает время с точностью до секунд? Вписывать ключ, ждать секунду, смотреть, что записалось.

[Сергей]

Есть 2 потока, которые пишут в новый ключ.
1. Первый проверил, в БД нет ключа.
2. Второй проверил, в БД нет ключа.
3. Первый записал 1.
4. Второй записл 2.
Конфуз.

[Сергей Соколов]

Сергей: записывают значение вида "timestamp|worker_id", ждут 2 секунды, считывают значение, если там их id и ts не свежее 1 сек, то ключ их. Развить эту идею. Надеюсь, есть известный всем, кроме меня, алгоритм на сей счёт.

[Сергей]

> если там их id и ts не свежее 1 сек, то ключ их.
а если нет ? сколько ждать ?
а если потоков будет не 2, а 100 ? а 1000 ? все будете ждать 2 сек ?
да ваш мьютекс не сможет заблокироваться нормально.