Comment gérer l'accès synchronisé à List dans Map <String, List>?

Question

MISE À JOUR: Veuillez noter.
La question que j'ai posée a été répondue. Malheureusement pour moi, la question est plus grande que la question dans le titre. En plus d'ajouter de nouvelles entrées à la carte, j'ai dû gérer les mises à jour et les suppressions en même temps. Le scénario que j'ai à l'esprit ne semble pas possible à mettre en œuvre sans l'un ou l'autre:
a. blocages b. complexe & chèques et serrures qui prennent beaucoup de temps
Vérifiez les dernières réflexions au bas de la question.

POST ORIGINAL:

Salut,

J'ai un grain de printemps avec une carte.

Voici ce que je veux l'utiliser pour:

quelques auditeurs JMS simultanées recevront des messages avec des actions. Chaque action consiste en deux utilisateurs: utilisateur long A et utilisateur long B. Le message aura sa propre file d'attente String replyTo qui sera utilisée pour identifier l'action. Parce que je ne peux pas permettre d'exécuter une action lorsque l'un des utilisateurs participe à une autre action qui est exécutée, je vais utiliser cette carte comme un registre de ce qui se passe et afin de contrôler l'exécution des actions. Alors disons que je reçois trois actions:
1. userA, userB
2. userB, UtilisateurC
3. UtilisateurC, userA

Lors de la première action a reçu la carte est vide, donc je vais enregistrer les informations à propos de l'action et commencer à exécuter l'action.
Lorsque la deuxième action est reçue, je peux voir que l'utilisateur B est 'occupé' par la première action, donc je note simplement des informations sur l'action.
Même chose pour la troisième action.

carte va ressembler à ceci:
[userA: [action1, action3],
userB: [action1, action2],
UtilisateurC: [action2, action3]]

Une fois que la première action est terminée, je vais supprimer les informations à ce sujet du registre et obtenir des informations sur les prochaines actions pour userA et userB [action3, action2]. Ensuite, je vais essayer de les redémarrer.

Je pense que maintenant vous obtenez ce que je veux faire avec cette carte.

Parce que la carte va être accessible à partir de plusieurs threads en même temps, je dois gérer la synchronisation en quelque sorte.

Je vais avoir des méthodes pour ajouter de nouvelles informations à la carte et pour supprimer des informations de la carte lorsque l'action est terminée. La méthode remove renvoie les actions suivantes [s'il y en a] pour les deux utilisateurs pour lesquels l'action vient de se terminer. Comme il peut y avoir des centaines d'actions exécutées en même temps et que le pourcentage d'actions avec des utilisateurs occupés est supposé être faible, je ne veux pas bloquer l'accès à la carte pour chaque opération d'ajout/suppression.

Je pensais à rendre l'accès synchronisé uniquement à chacune des listes dans la carte pour permettre l'accès simultané à plusieurs entrées d'utilisateur en même temps. Cependant ... parce que quand il n'y a aucune action laissée pour l'utilisateur je veux enlever l'entrée pour cet utilisateur de la carte. Aussi ... quand l'utilisateur n'a pas d'entrée dans la carte, je vais devoir en créer un. J'ai un peu peur qu'il puisse y avoir des affrontements quelque part.

Quelle serait la meilleure façon de gérer ce scénario? Est-ce que faire les deux méthodes - ajouter et supprimer - synchronisé (ce que je considère comme le pire des cas) est la seule façon [sûre] de le faire?

De plus, je vais avoir une autre carte qui contiendra l'identifiant de l'action en tant que clés et les identifiants de l'utilisateur en tant que valeurs, donc il est plus facile d'identifier/supprimer les paires d'utilisateurs. Je crois que je peux sauter la synchronisation sur celui-ci puisqu'il n'y a aucun scénario où une action serait exécutée deux fois en même temps.

Bien que le code soit dans Groovy, je crois qu'aucun programmeur Java ne trouvera difficile à lire. C'est Java derrière. S'il vous plaît envisager de suivre comme pseudo code que je suis juste le prototypage.

class UserRegistry { 

    // ['actionA':[userA, userB]] 
    // ['actionB':[userC, userA]] 
    // ['actionC':[userB, userC]] 
    private Map<String, List<Long>> messages = [:] 
    /** 
    * ['userA':['actionA', 'actionB'], 
    * ['userB':['actionA', 'actionC'], 
    * ['userC':['actionB', 'actionC'] 
    */ 
    private Map<long, List<String>> users = [:].asSynchronized() 

    /** 
    * Function will add entries for users and action to the registry. 
    * @param userA 
    * @param userB 
    * @param action 
    * @return true if a new entry was added, false if entries for at least one user already existed 
    */ 
    public boolean add(long userA, long userB, String action) { 
     boolean userABusy = users.containsKey(userA) 
     boolean userBBusy = users.containsKey(userB) 
     boolean retValue 
     if (userABusy || userBBusy) { 
      if (userABusy) { 
       users.get(userA).add(action) 
      } else { 
       users.put(userA, [action].asSynchronized()) 
      } 
      if (userBBusy) { 
       users.get(userB).add(action) 
      } else { 
       users.put(userB, [action].asSynchronized()) 
      } 
      messages.put(action, [userA, userB]) 
      retValue = false 
     } else { 
      users.put(userA, [action].asSynchronized()) 
      users.put(userB, [action].asSynchronized()) 
      messages.put(action, [userA, userB]) 
      retValue = true 
     } 
     return retValue 
    } 

    public List remove(String action) { 
     if(!messages.containsKey(action)) throw new Exception("we're screwed, I'll figure this out later") 
     List nextActions = [] 
     long userA = messages.get(action).get(0) 
     long userB = messages.get(action).get(1) 
     if (users.get(userA).size() > 1) { 
      users.get(userA).remove(0) 
      nextActions.add(users.get(userA).get(0)) 
     } else { 
      users.remove(userA) 
     } 
     if (users.get(userB).size() > 1) { 
      users.get(userB).remove(0) 
      nextActions.add(users.get(userB).get(0)) 
     } else { 
      users.remove(userB) 
     } 
     messages.remove(action) 
     return nextActions 
    } 
} 

EDIT Je pensais à cette solution la nuit dernière et il semble que la carte des messages pourrait partir et les utilisateurs Plan serait:

Map users<String, List<UserRegistryEntry>> 

où
UserRegistryEntry:
cordes actionId
booléen en attente

maintenant supposons que je reçois ces actions:

action1: Usera, UtilisateurC
action2: Usera, UserD
action3: userB, UtilisateurC
action4: userB, UserD

Cela signifie que action1 et action4 peut être exécutée simultanément et action2 et action3 sont bloquées. Carte ressemblerait à ceci:

[ 
[userAId: [actionId: action1, waiting: false],[actionId: action2, waiting: true]], 
[userBId: [actionId: action3, waiting: true], [actionId: action4, waiting: false]], 
[userCId: [actionId: action1, waiting: false],[actionId: action3, waiting: true]], 
[userDId: [actionId: action2, waiting: true], [actionId: action4, waiting: false]] 
] 

De cette façon, lorsque l'exécution de l'action est terminée éleminez l'entrée de la carte en utilisant:
userAId, userBId, actionID
et prendre des détails sur la première non bloqué l'action en attente sur userA et userB [s'il y en a] et transmettez-les pour exécution. Maintenant, les deux méthodes dont j'ai besoin, qui vont écrire des données à la carte et le retirer de la carte.

public boolean add(long userA, long userB, String action) { 
    boolean userAEntryExists = users.containsKey(userA) 
    boolean userBEntryExists = users.containsKey(userB) 
    boolean actionWaiting = true 
    UserRegistryEntry userAEntry = new UserRegistryEntry(actionId: action, waiting: false) 
    UserRegistryEntry userBEntry = new UserRegistryEntry(actionId: action, waiting: false) 
    if (userAEntryExists || userBEntryExists) { 
     if (userAEntryExists) { 
      for (entry in users.get(userA)) { 
       if (!entry.waiting) { 
        userAEntry.waiting = true 
        userBEntry.waiting = true 
        actionWaiting = true 
        break; 
       } 
      } 
     } 

     if (!actionWaiting && userBEntryExists) { 
      for (entry in users.get(userB)) { 
       if (!entry.waiting) { 
        userAEntry.waiting = true 
        userBEntry.waiting = true 
        actionWaiting = true 
        break; 
       } 
      } 
     } 
    } 

    if (userBEntryExists) { 
     users.get(userA).add(userAEntry) 
    } else { 
     users.put(userA, [userAEntry]) 
    } 

    if (userAEntryExists) { 
     users.get(userB).add(userBEntry) 
    } else { 
     users.put(userB, [userBEntry]) 
    } 

    return actionWaiting 
} 

Et pour Enlève

public List remove(long userA, long userB, String action) { 
     List<String> nextActions = [] 
     finishActionAndReturnNew(userA, action, nextActions) 
     finishActionAndReturnNew(userB, action, nextActions) 

     return nextActions; 
    } 

    private def finishActionAndReturnNew(long userA, String action, List<String> nextActions) { 
     boolean userRemoved = false 
     boolean actionFound = false 
     Iterator itA = users.get(userA).iterator() 
     while (itA.hasNext()) { 
      UserRegistryEntry entry = itA.next() 
      if (!userRemoved && entry.actionId == action) { 
       itA.remove() 
      } else { 
       if (!actionFound && isUserFree(entry.otherUser)) { 
        nextActions.add(entry.actionId) 
       } 
      } 
      if (userRemoved && actionFound) break 
     } 
    } 

    public boolean isUserFree(long userId) { 
     boolean userFree = true 
     if (!users.containsKey(userId)) return true 
     for (entry in users.get(userId)) { 
      if (!entry.waiting) userFree = false 
     } 
     return userFree 
    } 

FINAL REFLEXION:
Ce scénario est un tueur:
[ActionID, userA, userB]
[a, 1,2]
[b, 1,3]
[c, 3,4]
[d, 3,1]
Les actions a et c sont exécutées simultanément, b et d sont en attente.
Lorsque a et c sont terminés, les entrées pour les utilisateurs 1, 2, 3, 4 devront être supprimées, ainsi un thread aura 1 et 2 verrouillés, l'autre thread verrouillera 3 et 4. Lorsque ces utilisateurs sont verrouillés, une vérification de l'action suivante pour chacun d'eux doit être effectuée. Lorsque le code détermine que pour l'utilisateur 1 l'action suivante est avec l'utilisateur 3 et pour l'utilisateur 3 l'action suivante est avec l'utilisateur 1, le petit-lait essaiera de les verrouiller. C'est quand l'impasse arrive. Je sais que je pourrais coder autour de cela, mais il semble que cela prendra beaucoup de temps à exécuter et que cela bloquera deux travailleurs.
Pour l'instant je vais poser une autre question sur SO, plus sur le sujet de mon problème et essayer de prototyper la solution en utilisant JMS dans l'intervalle.

Answer 1

Vous devrez peut-être revoir la façon dont la synchronisation (collections) fonctionnent à nouveau:

Ce (comme exemple non exclusif) est thread-safe:

if (users.get(userA).size() > 1) { 
    users.get(userA).remove(0) 

Rappelez-vous que seul individuel " Les méthodes synchronisées sont garanties atomiques sans une portée de verrou plus grande.

Bonne codification.

Juste en utilisant les standards des structures de données que vous pouvez réaliser par-clés serrures en utilisant ConcurrentHashMap - notamment en utilisant le « putIfAbsent: -

Modifier les verrous de synchronisation par utilisateur (mis à jour pour commentaire) ' méthode. (Ceci est significativement différent que juste en utilisant get/put d'un 'HashMap synchronisé', voir ci-dessus.)

Ci-dessous quelques pseudo-code et notes:

public boolean add(long userA, long userB, String action) { 
    // The put-if-absent ensures the *the same* object but may be violated when: 
    // -users is re-assigned 
    // -following approach is violated 
    // A new list is created if needed and the current list is returned if 
    // it already exists (as per the method name). 
    // Since we have synchronized manually here, these lists 
    // themselves do not need to be synchronized, provided: 
    // Access should consistently be protected across the "higher" 
    // structure (per user-entry in the map) when using this approach. 
    List listA = users.putIfAbsent(userA, new List) 
    List listB = users.putIfAbsent(userB, new List) 
    // The locks must be ordered consistently so that 
    // a A B/B A deadlock does not occur. 
    Object lock1, lock2 
    if (userA < userB) { 
     lock1 = listA, lock2 = listB 
    } else { 
     lock1 = listB, lock2 = listA 
    } 
    synchronized (lock1) { synchronized (lock2) {{ // start locks 

    // The rest of the code can be simplified, since the 
    // list items are already *guaranteed* to exist there is no 
    // need to alternate between add and creating a new list. 
    bool eitherUserBusy = listA.length > 0 || listB.length > 0 
    listA.add(action) 
    listB.add(action) 
    // make sure messages allows thread-safe access as well 
    messages.put(action, [userA, userB]) 
    return !eitherUserBusy 

    }} // end locks 
} 

Je n'ai pas comment cette foires dans votre scénario d'utilisation par rapport à un seul objet de verrouillage commun. Il est souvent conseillé d'aller «plus simple» à moins qu'il y ait un net avantage à faire autrement.

Codage HTH et Happy.

Answer 2

Vous pouvez consulter Collections.synchronizedMap() ou Collections.synchronizedList()

Answer 3

Vous avez deux détenteurs mondiaux Etat dans la classe et composé des actions dans chacune des deux méthodes qui modifient les deux. Donc, même si nous avons changé la carte pour être ConcurrentHashMap et la liste à quelque chose comme CopyOnWriteArrayList, cela ne garantirait toujours pas un état cohérent.

Je vois que vous écrirez souvent dans la liste, donc, CopyOnWriteArrayList peut être trop cher de toute façon. ConcurrentHashMap est seulement rayé 16-way. Si vous avez un meilleur matériel, une alternative serait le highscalelib de Cliff Click (après un verrouillage approprié dans les méthodes). Pour revenir à la question de cohérence, que diriez-vous d'utiliser un ReentrantLock au lieu de synchroniser et de voir si vous pouvez exclure certaines instructions de la séquence lock() - to-unlock(). Si vous avez utilisé un ConcurrentMap, les deux premières instructions de la méthode add() qui contient containsKey peuvent être optimistes et vous pouvez les exclure du bloc de verrouillage.

Avez-vous vraiment besoin de la carte des messages? C'est un peu comme un index inverse des utilisateurs. Une autre option serait d'avoir une autre méthode watch() qui met à jour périodiquement la carte des messages en fonction d'un signal de add() après un changement aux utilisateurs. Le rafraîchissement pourrait alternativement être complètement asynchrone. En faisant cela, vous pourriez être en mesure d'utiliser un ReadWriteLock avec readLock() sur les utilisateurs pendant que vous mettez à jour les messages. Dans ce cas, add() peut acquérir en toute sécurité un writeLock() sur les utilisateurs. C'est juste un peu plus de travail pour que cela soit raisonnablement correct.