Diferentes tipos de conjuntos seguros para threads em Java

135

Parece haver várias implementações diferentes e maneiras de gerar conjuntos seguros para threads em Java. Alguns exemplos incluem

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (conjunto definido)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap (new ConcurrentHashMap ())

5) Outros conjuntos gerados de maneira semelhante a (4)

Estes exemplos vêm das implementações Concurrency Pattern: Concurrent Set em Java 6

Alguém poderia simplesmente explicar as diferenças, vantagens e desvantagens desses exemplos e de outros? Estou tendo problemas para entender e manter direto tudo, desde o Java Std Docs.

Ben
fonte

Respostas:

206

1) A CopyOnWriteArraySetimplementação é bastante simples - basicamente possui uma lista de elementos em uma matriz e, ao alterar a lista, copia a matriz. As iterações e outros acessos em execução no momento continuam com a matriz antiga, evitando a necessidade de sincronização entre leitores e gravadores (embora a própria gravação precise ser sincronizada). As operações de configuração normalmente rápida (especialmente contains()) são bastante lentas aqui, pois as matrizes serão pesquisadas em tempo linear.

Use isso apenas para conjuntos realmente pequenos que serão lidos (iterados) com frequência e alterados raramente. (Swings listener-sets seria um exemplo, mas na verdade não são conjuntos e deve ser usado apenas no EDT de qualquer maneira.)

2) Collections.synchronizedSetsimplesmente envolverá um bloco sincronizado em torno de cada método do conjunto original. Você não deve acessar o conjunto original diretamente. Isso significa que não há dois métodos do conjunto que podem ser executados simultaneamente (um bloqueará até que o outro termine) - isso é seguro para threads, mas você não terá simultaneidade se vários threads realmente estiverem usando o conjunto. Se você usar o iterador, geralmente ainda precisará sincronizar externamente para evitar ConcurrentModificationExceptions ao modificar o conjunto entre as chamadas do iterador. O desempenho será semelhante ao desempenho do conjunto original (mas com alguma sobrecarga de sincronização e bloqueio, se usado simultaneamente).

Use isso se você tiver baixa simultaneidade e desejar garantir que todas as alterações sejam imediatamente visíveis para os outros threads.

3) ConcurrentSkipListSeté a SortedSetimplementação simultânea , com as operações mais básicas em O (log n). Permite adicionar / remover e ler / iterar simultaneamente, onde a iteração pode ou não informar sobre as alterações desde que o iterador foi criado. As operações em massa são simplesmente várias chamadas únicas, e não atomicamente - outros threads podem observar apenas algumas delas.

Obviamente, você pode usar isso apenas se tiver alguma ordem total em seus elementos. Parece um candidato ideal para situações de alta simultaneidade, para conjuntos não muito grandes (por causa do O (log n)).

4) Para o ConcurrentHashMap(e o conjunto derivado dele): Aqui as opções mais básicas são (em média, se você tem um bom e rápido hashCode()) em O (1) (mas pode degenerar em O (n)), como no HashMap / HashSet. Há uma simultaneidade limitada para gravação (a tabela é particionada e o acesso de gravação será sincronizado na partição necessária), enquanto o acesso de leitura é totalmente simultâneo a si e aos encadeamentos de gravação (mas ainda não pode ver os resultados das alterações atualmente sendo escrito). O iterador pode ou não ver alterações desde que foi criado, e as operações em massa não são atômicas. O redimensionamento é lento (como no HashMap / HashSet), portanto, tente evitar isso estimando o tamanho necessário na criação (e usando cerca de 1/3 a mais disso, pois é redimensionado quando 3/4 está cheio).

Use isso quando você tiver conjuntos grandes, uma boa (e rápida) função de hash e puder estimar o tamanho do conjunto e a simultaneidade necessária antes de criar o mapa.

5) Existem outras implementações simultâneas de mapas que alguém poderia usar aqui?

Paŭlo Ebermann
fonte
1
Apenas uma correção visual em 1), o processo de cópia de dados no novo array deve ser bloqueado pela sincronização. Portanto, CopyOnWriteArraySet não evita totalmente a necessidade de sincronização.
precisa saber é o seguinte
No ConcurrentHashMapconjunto baseado ", tente evitar isso estimando o tamanho necessário na criação". O tamanho que você atribui ao mapa deve ser 33% maior que a sua estimativa (ou valor conhecido), pois o conjunto é redimensionado com uma carga de 75%. Eu usoexpectedSize + 4 / 3 + 1
Daren
@ Daren Acho que o primeiro +é para ser um *?
Paŭlo Ebermann
@ PaŭloEbermann Claro ... deve serexpectedSize * 4 / 3 + 1
Daren
1
Para ConcurrentMap(ou HashMap) no Java 8, se o número de entradas mapeadas para o mesmo bucket atingir o valor limite (acredito que seja 16), a lista será alterada para uma árvore de pesquisa binária (árvore vermelha-preta a ser precisa) e, nesse caso, procure o tempo seria O(lg n)e não O(n).
akhil_mittal
20

É possível combinar o contains()desempenho HashSetcom as propriedades relacionadas à simultaneidade CopyOnWriteArraySetusando AtomicReference<Set>e substituindo o conjunto inteiro em cada modificação.

O esboço de implementação:

public abstract class CopyOnWriteSet<E> implements Set<E> {

    private final AtomicReference<Set<E>> ref;

    protected CopyOnWriteSet( Collection<? extends E> c ) {
        ref = new AtomicReference<Set<E>>( new HashSet<E>( c ) );
    }

    @Override
    public boolean contains( Object o ) {
        return ref.get().contains( o );
    }

    @Override
    public boolean add( E e ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( current.contains( e ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.add( e );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

    @Override
    public boolean remove( Object o ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( !current.contains( o ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.remove( o );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

}
Oleg Estekhin
fonte
Na verdade, AtomicReferencemarca o valor como volátil. Isso significa que garante que nenhum thread esteja lendo dados obsoletos e fornece happens-beforegarantia, pois o código não pode ser reordenado pelo compilador. Porém, se apenas métodos get / set de AtomicReferencesão usados, na verdade estamos marcando nossa variável volátil de maneira sofisticada.
akhil_mittal
Essa resposta não pode ser votada o suficiente porque (1) a menos que eu tenha perdido algo, funcionará para todos os tipos de coleções (2) nenhuma das outras classes fornece uma maneira de atualizar atomicamente a coleção inteira de uma só vez ... Isso é muito útil .
Gili
Tentei me apropriar literalmente, mas achei que estava rotulado abstract, aparentemente para evitar a necessidade de escrever vários métodos. Comecei a adicioná-los, mas me deparei com um obstáculo iterator(). Não sei como manter um iterador sobre isso sem quebrar o modelo. Parece que eu sempre tenho que passar pelo refe pode ter um conjunto subjacente diferente a cada vez, o que exige a obtenção de um novo iterador no conjunto subjacente, que é inútil para mim, pois começará com o item zero. Alguma ideia?
Nclark 26/09/19
Ok, acho que a garantia é que cada cliente obtém um instantâneo fixo a tempo, para que o iterador da coleção subjacente funcione bem, se é tudo o que você precisa. Meu caso de uso é permitir que os segmentos concorrentes "reivindiquem" recursos individuais nele e não funcionará se eles tiverem versões diferentes do conjunto. Na segunda embora ... Eu acho que meu fio só precisa obter um novo iterador e tente novamente caso CopyOnWriteSet.remove (chosen_item) retorna falso ... O que teria que fazer, independentemente :)
nclark
11

Se os Javadocs não ajudarem, você provavelmente deve encontrar apenas um livro ou artigo para ler sobre estruturas de dados. Num relance:

  • CopyOnWriteArraySet faz uma nova cópia da matriz subjacente toda vez que você modifica a coleção, para que as gravações sejam lentas e os Iteradores sejam rápidos e consistentes.
  • Collections.synchronizedSet () usa chamadas de método sincronizadas à moda antiga para tornar um Set thread-safe. Esta seria uma versão de baixo desempenho.
  • ConcurrentSkipListSet oferece gravações de desempenho com operações inconsistentes em lote (addAll, removeAll, etc.) e Iteradores.
  • Collections.newSetFromMap (new ConcurrentHashMap ()) possui a semântica de ConcurrentHashMap, que acredito não necessariamente otimizada para leituras ou gravações, mas como ConcurrentSkipListSet, possui operações em lote inconsistentes.
Ryan Stewart
fonte
1
developer.com/java/article.php/10922_3829891_2/… <ainda melhor que um livro)
ycomp 18/10/2015
1

Conjunto simultâneo de referências fracas

Outra reviravolta é um conjunto seguro de threads de referências fracas .

Esse conjunto é útil para rastrear assinantes em um cenário pub-sub . Quando um assinante está fora do escopo em outros lugares e, portanto, se torna um candidato à coleta de lixo, o assinante não precisa se incomodar em cancelar a inscrição normalmente. A referência fraca permite que o assinante conclua sua transição para ser um candidato à coleta de lixo. Quando o lixo é finalmente coletado, a entrada no conjunto é removida.

Embora esse conjunto não seja fornecido diretamente com as classes empacotadas, você pode criar um com algumas chamadas.

Primeiro, começamos fazendo Setreferências fracas, aproveitando a WeakHashMapclasse. Isso é mostrado na documentação da classe para Collections.newSetFromMap.

Set< YourClassGoesHere > weakHashSet = 
    Collections
    .newSetFromMap(
        new WeakHashMap< YourClassGoesHere , Boolean >()
    )
;

O Valor do mapa Boolean,, é irrelevante aqui, pois a Chave do mapa compõe a nossa Set.

Em um cenário como pub-sub, precisamos de segurança de thread se os assinantes e editores estiverem operando em threads separados (provavelmente o caso).

Dê um passo adiante envolto como um conjunto sincronizado para torná-lo seguro para threads. Alimente uma chamada para Collections.synchronizedSet.

this.subscribers =
        Collections.synchronizedSet(
                Collections.newSetFromMap(
                        new WeakHashMap <>()  // Parameterized types `< YourClassGoesHere , Boolean >` are inferred, no need to specify.
                )
        );

Agora podemos adicionar e remover assinantes dos nossos resultantes Set. E todos os assinantes "desaparecidos" serão removidos automaticamente após a execução da coleta de lixo. Quando essa execução ocorre, depende da implementação do coletor de lixo da JVM e depende da situação de tempo de execução no momento. Para obter uma discussão e um exemplo de quando e como o subjacente WeakHashMaplimpa as entradas expiradas, consulte esta pergunta: * O WeakHashMap está sempre crescendo ou limpa as chaves de lixo? * .

Basil Bourque
fonte