29 January 2014

IdBasedLocking

Website developmentProgrammingJava
У Java отличная поддержка параллелизма (concurrency) и блокировки (locking) — возможно, самая лучшая из тех, что предлагают современные языки. Кроме того, что в самом языке есть встроенная поддержка синхронизации, существует целый ряд полезных утилит на основе AQS framework. К ним относятся CountDownLatches, Barriers, Semaphores и прочие. Однако часто встречается ситуация, не поддерживающаяся напрямую: когда надо блокировать доступ не к конкретному объекту, а к идее этого объекта.



Рассмотрим следующий пример: у нас есть сервис, который отвечает за почтовые ящики (mailbox). В нём есть метод для добавления нового сообщения и метод для того, чтобы сообщение прочитать. Конечно, мы запускаем наш сервис в многопоточной среде — ведь у нас тысячи пользователей, которые посылают несметную кучу сообщений друг другу. Чтобы защитить мэйлбокс от искажения данных, нам нельзя допускать модификацию одного ящика несколькими потоками одновременно:

   public void sendMessage(UserId from, UserId to, Message message) { 
        Mailbox sendersBox = getMailbox(from);
        Mailbox recipientsBox = getMailbox(to);
        min(sendersBox,recipientsBox).lock();
        max(sendersBox, recipientsBox).lock();
        sendersBox.addIncomingMessage(message);
        recipientsBox.addSentMessage(message);
        max(sendersBox, recipientsBox).lock();
        min(sendersBox,recipientsBox).lock();
    }


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

На самом деле, безопасность этого кода зависит от того, как, собственно, реализован метод getMailbox(). Если он может гарантировать возвращение одного и того же объекта (причем именно «того же», а не «такого же»), то мы в безопасности. К сожалению, такую гарантию практически невозможно реализовать. С другой стороны, мы, конечно, могли бы поставить synchronized на весь метод sendMessage(), но это убило бы нашу производительность на корню, так как мы могли бы одновременно отправлять только одно сообщение, невзирая на количество потоков и процессоров в нашем распоряжении.

Вот пример того, как можно неправильно реализовать getMailbox():

  private Mailbox getMailbox(UserId id) {
        Mailbox mailbox = cache.get(id);
        if (mailbox == null) {
            mailbox = new Mailbox();
            cache.put(id, mailbox);
        }
        return mailbox;
    }


Очевидно, что эта реализация небезопасна: она допускает создание одного и того же мэйлбокса по сути (то есть принадлежащего одному и тому же юзеру) из разных потоков одновременно. Это значит, что в какой-то момент в системе могут появится два разных ящика одного пользователя, и только Ктулху будет знать, какой из них выживет. Можно решить эту проблему, заблокировав создание нового мэйлбокса глобально, но это, опять же, грабли с производительностью. Можно начать развлекаться с ConcurrentMap и всякими там putIfAbsent. Но представьте, что мы не только создаём новые почтовые ящики, но и грузим существующие из базы данных. Тогда это будет гораздо сложнее правильно синхронизировать (да и предотвратить лишние запросы в базу было бы неплохо).

К счастью, IdBasedLocking решает именно эту проблему. Вместо блокирования конкретного объекта “мэйлбокс”, мы блокируем концепт мэйлбокса, исходя из того, что у нас по одному ящику на пользователя:

    IdBasedLockManager<UserId> manager = new SafeIdBasedLockManager<UserId>();

    public void sendMessageSafe(UserId from, UserId to, Message message) {

        IdBasedLock<UserId> minLock = manager.obtainLock(min(from, to));
        IdBasedLock<UserId> maxLock = manager.obtainLock(max(from, to));
        minLock.lock();
        maxLock.lock();
        
        try {
            Mailbox sendersBox = getMailbox(from);
            Mailbox recipientsBox = getMailbox(to);
            sendersBox.addIncomingMessage(message);
            recipientsBox.addSentMessage(message);
        } finally {
            maxLock.unlock();
            minLock.unlock();

        }
    }



Пример может показаться искусственно усложненным из-за одновременной модификации двух объектов. IdBasedLocking отлично работает и с одним объектом, как демонстрирует следующий пример счетчика.

Сначала — поломанный вариант:

   public void increaseCounterUnsafe(String id) {
        Counter c = counterCache.get(id);
        if (c == null) {
            c = new Counter();
            counterCache.put(id, c);
        }
        c.increase();
    }


А теперь безопасная версия:

   public void increaseCounterSafely(String id) {
        IdBasedLock<String> lock = lockManager.obtainLock(id);
        lock.lock();
        try{
            Counter c = counterCache.get(id);
            if (c == null) {
                c = new Counter();
                counterCache.put(id, c);
            }
            c.increase();

        } finally {
            lock.unlock();
        }
    }


IdBasedLocking проект на гитхабе.

Взять попользоваться можно maven-ом, gradle или ivy, или просто из central. Или пробилдить на гитхабе самому.

Спасибо за внимание.
Tags:concurrencylocklockslockingмногопоточностьмногопоточное программирование
Hubs: Website development Programming Java
+7
5.3k 37
Comments 31
Top of the last 24 hours