Синхронизация карты наборов / списков

Question

Я хотел бы реализовать вариант коллекции «Карта наборов», к которому будут постоянно обращаться несколько потоков.Мне интересно, достаточна ли выполняемая мной синхронизация, чтобы гарантировать, что никаких проблем не возникнет.

Итак, учитывая следующий код, где Map, HashMap и Set являются реализациями Java, а Key и Value являются произвольнымиОбъекты:

public class MapOfSets {
    private Map<Key, Set<Value>> map;

    public MapOfLists() {
        map = Collections.synchronizedMap(new HashMap<Key, Set<Value>());
    }

    //adds value to the set mapped to key
    public void add(Key key, Value value) {
        Set<Value> old = map.get(key);

        //if no previous set exists on this key, create it and add value to it
        if(old == null) {
            old = new Set<Value>();
            old.add(value);
            map.put(old);
        }
        //otherwise simply insert the value to the existing set
        else {
            old.add(value);
        }
    }

    //similar to add
    public void remove(Key key, Value value) {...}

    //perform some operation on all elements in the set mapped to key
    public void foo(Key key) {
        Set<Value> set = map.get(key);

        for(Value v : set)
            v.bar();
    }
}

Идея заключается в том, что, поскольку я синхронизировал саму карту, методы get () и put () должны быть атомарными, верно?Поэтому не нужно выполнять дополнительную синхронизацию на карте или наборах, содержащихся в ней.Так будет ли это работать?

В качестве альтернативы приведенный выше код будет иметь преимущество перед другим возможным решением для синхронизации:

public class MapOfSets {
    private Map<Key, Set<Value>> map;

    public MapOfLists() {
        map = new HashMap<Key, Set<Value>();
    }

    public synchronized void add(Key key, Value value) {
        Set<Value> old = map.get(key);

        //if no previous set exists on this key, create it and add value to it
        if(old == null) {
            old = new Set<Value>();
            old.add(value);
            map.put(old);
        }
        //otherwise simply insert the value to the existing set
        else {
            old.add(value);
        }
    }

    //similar to add
    public synchronized void remove(Key key, Value value) {...}

    //perform some operation on all elements in the set mapped to key
    public synchronized void foo(Key key) {
        Set<Value> set = map.get(key);

        for(Value v : set)
            v.bar();
    }
}

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

Answer 1

Ваша вторая реализация будет работать, но она будет удерживать блокировки дольше, чем нужно (неизбежная проблема с использованием синхронизированных методов, а не синхронизированных блоков), что уменьшит параллелизм.Если вы обнаружите, что ограничение параллелизма здесь является узким местом, вы можете немного уменьшить количество заблокированных областей.

В качестве альтернативы вы можете использовать некоторые из коллекций без блокировок, предоставленных java.util.concurrent.Вот моя попытка сделать это;это не проверено и требует, чтобы Key был сопоставим, но он не должен выполнять какую-либо блокировку:

public class MapOfSets {
    private final ConcurrentMap<Key, Set<Value>> map;

    public MapOfSets() {
        map = new ConcurrentSkipListMap<Key, Set<Value>>();
    }

    private static ThreadLocal<Set<Value>> freshSets = new ThreadLocal<Set<Value>>() {
        @Override
        protected Set<Value> initialValue() {
            return new ConcurrentSkipListSet<Value>();
        }
    };

    public void add(Key key, Value value) {
        Set<Value> freshSet = freshSets.get();
        Set<Value> set = map.putIfAbsent(key, freshSet);
        if (set == null) {
            set = freshSet;
            freshSets.remove();
        }
        set.add(value);
    }

    public void remove(Key key, Value value) {
        Set<Value> set = map.get(key);
        if (set != null) {
            set.remove(value);
        }
    }

    //perform some operation on all elements in the set mapped to key
    public void foo(Key key) {
        Set<Value> set = map.get(key);
        if (set != null) {
            for (Value v: set) {
                v.bar();
            }
        }
    }
}

Answer 2

Первая реализованная вами реализация не является поточно-ориентированной. Рассмотрим, что происходит, когда к методу add обращаются два параллельных потока с одинаковым key:

1. thread A выполняет строку 1 метода и получает ссылку null, поскольку отсутствует элемент с данным ключом
2. thread B выполняет строку 1 метода и получает ссылку null, поскольку отсутствует элемент с данным ключом & mdash; это произойдет после того, как A вернется после первого вызова, так как карта синхронизирована
3. thread A оценивает условие if как false
4. thread B оценивает условие if как false

С этого момента два потока продолжат выполнение ветви true оператора if, и вы потеряете один из двух value объектов.

Второй вариант описанного вами метода выглядит безопаснее.

---

Однако, если вы можете использовать сторонние библиотеки, я бы посоветовал вам проверить Google Guava , поскольку они предлагают одновременные мультикарты ( docs ).

Answer 3

Второй правильный, но первый нет.

Подумайте об этом минуту, и предположим, что два потока вызывают add() параллельно. Вот что может произойти:

• Тема 1 вызывает add ("foo", bar ");
• Тема 2 вызывает add ("foo", baz ");
• Поток 1 получает набор для "foo": null
• Поток 2 получает набор для "foo": null
• Поток 1 создает новый набор и добавляет в него «бар»
• Поток 2 создает новый набор и добавляет в него «баз»
• Тема 1 помещает свой набор в карту
• Тема 2 помещает свой набор в карту

В конце истории на карте содержится одно значение «foo» вместо двух.

Синхронизация карты обеспечивает согласованность ее внутреннего состояния и то, что каждый метод, который вы вызываете на карте, является поточно-ориентированным. но это не делает операцию get-then-put атомарной.

Рассмотрите возможность использования одной из реализаций SetMultiMap от Guava, которая сделает все за вас. Оберните его в вызов Multimaps.synchronizedSetMultimap(SetMultimap), чтобы сделать его потокобезопасным.

Answer 4

Для реализации вашей карты вы можете просто использовать ConcurrentHashMap - вам не придется беспокоиться об обеспечении безопасности потоков для доступа, будь то ввод или извлечение, поскольку реализация позаботится об этом за вас.

И если вы действительно хотите использовать Набор, вы можете позвонить

Collections.newSetFromMap(new ConcurrentHashMap<Object,Boolean>()) 

в вашей ConcurrentHashMap.