Melhor abordagem para uso em Java 6 para uma lista que está sendo acessado simultaneamente

Question

Eu tenho um objeto de lista que está sendo acessado por múltiplos threads. Não é mais um segmento, e em algumas condições dois tópicos, que atualiza a lista. Há um a cinco tópicos que podem ler a partir dessa lista, dependendo do número de solicitações do usuário a ser processados. A lista não é uma fila de tarefas a serem executadas, é uma lista de objetos de domínio que estão sendo recuperados e atualizados simultaneamente.

Agora, existem várias maneiras de tornar o acesso a esta lista thread-safe:
-Use bloco sincronizado
-Use
normal de Bloqueio (ou seja, ler e ops gravação compartilhar mesmo bloqueio) -Use ReadWriteLock
-Use um dos novos ConcurrentBLABLBA classes de coleção

Minha pergunta:
Qual é a melhor abordagem para o uso, dado que as seções cricital normalmente não contêm uma grande quantidade de operações (na maior parte apenas adicionar / remover / inserir ou obter elementos da lista)?
Você pode recomendar outra abordagem, não listados acima?

Algumas restrições
desempenho -optimal é crítica, o uso de memória não tanto
-Deve ser uma lista ordenada (atualmente sincronizando em um ArrayList ), embora não seja uma lista ordenada (ou seja, não classificados usando comparável ou Comparador, mas de acordo com ordem de inserção)
-A lista vontade é grande, contendo até 100000 objetos de domínio, portanto, usando algo como CopyOnWriteArrayList não é viável
-As seções ciritical gravação / atualização são tipicamente muito rápido, fazendo simples adicionar / remover / inserir ou substituir (set)
-a operações de leitura vai fazer primeiramente uma chamada elementAt (index) na maioria das vezes, embora algumas operações de leitura pode fazer uma busca binária, ou indexOf (elemento)
-no iteração direta sobre a lista é feita, embora operação como indexOf (..) irá percorrer lista

Answer 1

Você tem que usar uma lista seqüencial? Se a estrutura do mapa-tipo é mais apropriado, você pode usar um ConcurrentHashMap. Com uma lista, um ReadWriteLock é provavelmente a maneira mais eficaz.

Editar para refletir edição do OP: busca binária na ordem de inserção? Você armazenar um timestamp e uso que para comparação, em sua busca binária? Se assim for, você pode ser capaz de usar o timestamp como a chave, e ConcurrentSkipListMap como o recipiente (que mantém a ordem de chave).

Answer 2

O que são os tópicos de leitura fazendo? Se eles estão iteração sobre a lista, então você realmente precisa para se certificar de que ninguém toques da lista durante todo o processo de iteração, caso contrário você pode obter resultados muito estranhos.

Se você pode definir precisamente o que a semântica que você precisa, deve ser possível para resolver o problema - mas você pode muito bem achar que você precisa para escrever seu próprio tipo de coleção para fazê-lo corretamente e com eficiência. Alternativamente, CopyOnWriteArrayList pode bem ser bom o suficiente - se potencialmente caro. Basicamente, quanto mais você pode amarrar suas necessidades, o mais eficiente possível.

Answer 3

Eu não sei se esta é uma solução possível para o problema, mas ... faz sentido para mim usar um gerenciador de banco de dados para manter essa enorme quantidade de dados e deixá-lo gerenciar as transações

Answer 4

Eu segunda sugestão de Telcontar de um banco de dados, uma vez que eles são realmente concebido para gerir esta escala dos dados e negociação entre threads, enquanto na memória coleções não são.

Você diz que os dados estão em um banco de dados no servidor, ea lista local nos clientes é por causa da interface do usuário. Você não precisa manter todos os 100000 itens no cliente de uma vez, ou realizar tais edições complicadas sobre ele. Parece-me que o que você quer no cliente é um cache leve para o banco de dados.

Escrever um cache que armazena apenas o subconjunto atual de dados no cliente ao mesmo tempo. Esta cache do cliente não executar edições de vários segmentos complexos nos seus próprios dados; em vez disso, alimenta todas as edições até o servidor e escutas para atualizações. Quando os dados de alterações no servidor, o cliente simplesmente esquece e dados antigos e carrega-o novamente. Apenas um segmento designado tem permissão para ler ou escrever a própria coleção. Desta forma, o cliente simplesmente espelhos as edições que acontecem no servidor, ao invés de precisar-se edições complicadas.

Sim, esta é uma solução bastante complicado. Os componentes que são:

• Um protocolo para o carregamento de um intervalo de dados, dizer itens 478712-478901, em vez da coisa toda
• Um protocolo para receber atualizações sobre dados alterados
• Uma classe de cache que armazena itens de seu índice conhecido no servidor
• Um fio pertencente a esse cache que se comunicava com o servidor. Este é o único segmento que escreve para o próprio
coleção
• Um fio pertencente a esse cache que processa retornos de chamada quando os dados são recuperados
• Uma interface que componentes de interface implementar para permitir que eles para receber dados quando ele foi carregado

Na primeira tentativa, os ossos de esta cache pode ser algo como isto:

class ServerCacheViewThingy {
    private static final int ACCEPTABLE_SIZE = 500;
    private int viewStart, viewLength;
    final Map<Integer, Record> items
            = new HashMap<Integer, Record>(1000);
    final ConcurrentLinkedQueue<Callback> callbackQueue
            = new ConcurrentLinkedQueue<Callback>();

    public void getRecords (int start, int length, ViewReciever reciever) {
        // remember the current view, to prevent records within
        // this view from being accidentally pruned.
        viewStart = start;
        viewLenght = length;

        // if the selected area is not already loaded, send a request
        // to load that area
        if (!rangeLoaded(start, length))
            addLoadRequest(start, length);

        // add the reciever to the queue, so it will be processed
        // when the data has arrived
        if (reciever != null)
            callbackQueue.add(new Callback(start, length, reciever));
    }

    class Callback {
        int start;
        int length;
        ViewReciever reciever;
        ...
    }

    class EditorThread extends Thread {

        private void prune () {
            if (items.size() <= ACCEPTABLE_SIZE)
                return;
            for (Map.Entry<Integer, Record> entry : items.entrySet()) {
                int position = entry.key();
                // if the position is outside the current view,
                // remove that item from the cache
                ...
            }
        }

        private void markDirty (int from) { ... }

        ....
    }

    class CallbackThread extends Thread {
        public void notifyCallback (Callback callback);
        private void processCallback (Callback) {
            readRecords
        }
    }
}

interface ViewReciever {
    void recieveData (int viewStart, Record[] records);
    void recieveTimeout ();
}

Há um monte de detalhes que você terá que preencher por si mesmo, obviamente.

Answer 5

Você pode usar um wrapper que sincronização implementos:

import java.util.Collections;
import java.util.ArrayList;

ArrayList list = new ArrayList();
List syncList = Collections.synchronizedList(list);

// make sure you only use syncList for your future calls... 

Esta é uma solução fácil. Eu tentaria isso antes de recorrer a soluções mais complicado.