Meilleure approche à utiliser dans Java 6 pour une liste accessible simultanément

Question

Un objet List est utilisé par plusieurs threads. Il existe généralement un seul thread, et dans certains cas deux threads, qui met à jour la liste. Il est possible de lire dans cette liste un à cinq threads, en fonction du nombre de demandes d'utilisateurs en cours de traitement. La liste n'est pas une file de tâches à exécuter, mais une liste d'objets de domaine qui sont récupérés et mis à jour simultanément.

Il existe maintenant plusieurs façons de rendre l'accès à cette liste thread-safe:
à utiliser synchrone
- utiliser un verrou normal (c.-à-d. que les opérations de lecture et d'écriture partagent le même verrou)

-use ReadWriteLock
- utiliser l'une des nouvelles classes de collection ConcurrentBLABLBA

Ma question:
Quelle est l’approche optimale à utiliser, étant donné que les sections cruciales ne contiennent généralement pas beaucoup d’opérations (la plupart du temps simplement pour ajouter / supprimer / insérer ou extraire des éléments de la liste)?
Pouvez-vous recommander une autre approche, non répertoriée ci-dessus?

Certaines contraintes
performances optimales sont critiques, l'utilisation de la mémoire n'est pas si importante
-il doit s'agir d'une liste ordonnée (en cours de synchronisation sur une ArrayList ), bien qu'il ne s'agisse pas d'une liste triée (c'est-à-dire non triée à l'aide de Comparable ou de Comparator, mais en fonction de l'ordre d'insertion)

-la liste est longue et peut contenir jusqu'à 100 000 objets de domaine. Il est donc impossible d'utiliser CopyOnWriteArrayList, par exemple.
-les sections circulaires d'écriture / mise à jour sont généralement très rapides, il suffit d'ajouter / supprimer / insérer ou de remplacer (définir)
-les opérations de lecture effectueront principalement un appel elementAt (index) la plupart du temps, bien que certaines opérations de lecture puissent effectuer une recherche binaire ou indexOf (élément)

-Aucune itération directe sur la liste n'est effectuée, bien qu'une opération comme indexOf (..) traverse la liste

Answer 1

Devez-vous utiliser une liste séquentielle? Si une structure de type map est plus appropriée, vous pouvez utiliser un ConcurrentHashMap . Avec une liste, un ReadWriteLock est probablement le moyen le plus efficace.

Editer pour refléter l'édition de l'OP: Recherche binaire sur l'ordre d'insertion? Stockez-vous un horodatage et utilisez-le à des fins de comparaison dans votre recherche binaire? Si tel est le cas, vous pourrez peut-être utiliser l'horodatage en tant que clé et ConcurrentSkipListMap en tant que conteneur (qui conserve l'ordre des clés).

Answer 2

Que font les fils de lecture? S'ils parcourent la liste, vous devez vous assurer que personne ne touche à la liste pendant tout le processus d'itération, sinon vous pourriez obtenir des résultats très étranges.

Si vous parvenez à définir précisément la sémantique dont vous avez besoin, il devrait être possible de résoudre le problème - mais vous constaterez peut-être que vous devez écrire votre propre type de collection pour le faire correctement et efficacement. Vous pouvez également CopyOnWriteArrayList may bien être assez bon - si potentiellement cher. En gros, plus vous pouvez répondre à vos besoins, plus il peut être efficace.

Answer 3

Je ne sais pas s'il s'agit d'une solution possible au problème, mais ... il me semble logique d'utiliser un gestionnaire de base de données pour stocker cette énorme quantité de données et le laisser gérer les transactions

Answer 4

Je seconde La suggestion de Telcontar de créer une base de données, puisqu'elles sont conçues pour gérer cette échelle de données et négocier entre les threads, contrairement aux collections en mémoire.

Vous dites que les données se trouvent sur une base de données sur le serveur et que la liste locale sur les clients sert uniquement à l'interface utilisateur. Vous ne devriez pas avoir besoin de garder tous les 100 000 articles en même temps sur le client, ou d’y apporter des modifications aussi compliquées. Il me semble que ce que vous voulez sur le client, c'est un cache léger sur la base de données.

Écrivez un cache qui ne stocke que le sous-ensemble actuel de données sur le client. Ce cache client n'effectue pas de modifications complexes multithreads sur ses propres données; au lieu de cela, il transmet toutes les modifications au serveur et écoute les mises à jour. Lorsque les données changent sur le serveur, le client oublie simplement les anciennes données et les charge à nouveau. Un seul thread désigné est autorisé à lire ou à écrire la collection elle-même. De cette façon, le client reflète simplement les modifications apportées sur le serveur, plutôt que de nécessiter des modifications complexes.

Oui, c'est une solution assez compliquée. Les composants sont:

• Un protocole pour charger une plage de données, dites les articles 478712 à 478901, plutôt que le tout
• Un protocole pour recevoir les mises à jour concernant les données modifiées
• Une classe de cache qui stocke les éléments en fonction de leur index connu sur le serveur
• Un thread appartenant à ce cache qui a communiqué avec le serveur. C'est le seul fil qui écrit dans la collection elle-même
• Un thread appartenant à ce cache qui traite les rappels lors de la récupération des données
• Interface implémentée par les composants de l'interface utilisateur pour leur permettre de recevoir des données après leur chargement

Au premier coup, les os de cette mémoire cache peuvent ressembler à ceci:

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 ();
}

Évidemment, vous devrez remplir vous-même de nombreux détails.

Answer 5

Vous pouvez utiliser un wrapper qui implémente la synchronisation:

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... 

C'est une solution facile. J'essaierais cela avant de recourir à des solutions plus complexes.