Как получить блокировку по ключу

Как лучше всего предотвратить одновременное обновление одной записи в наборе ключ-значение без блокировки всего набора? Семантически, Я ищу какую-то блокировку по ключу (в идеале, реализацию Java, но не обязательно):

interface LockByKey {
   void lock(String key); // acquire an exclusive lock for a key   
   void unlock(String key); // release lock for a key
}

Эта блокировка предназначена для синхронизации доступа к удаленному хранилищу, поэтому какая-то синхронизированная коллекция Java не вариант.