Il y a 11 ans -
Temps de lecture 1 minute
Java Puzzler
Avant de commencer l’année 2012, je vous propose un petit quiz adapté d’un cas réel.
Un programme standalone parse un fichier et insère les données parsées dans une base de données. Le même programme est exécuté dans trois régions différentes à savoir l’Europe, l’Amérique et l’Asie. Les entités persistées ont toutes un champ uid unique. La valeur de ce champ doit être sous la forme ‘E-1234’ ce qui est interprété comme l’enregistrement n° 1234 d’Europe. La base de données est la même pour les trois régions.
Lorsqu’on lance le programme dans les trois régions en parallèle, une exception est levée, laquelle et pourquoi est-elle levée ?
La solution sera détaillée sur cette même page dans les jours à venir.
N.B. certaines parties du code ont été omises pour garder la simplicité.
public class Region {
public static final char EUROPE = 'E';
public static final char AMERICA = 'U';
public static final char ASIA = 'A';
}
public class UIDGenerator {
private static Map<Character, Integer> ids = new HashMap<Character, Integer>();
public static String generateRegionUid(char regionCode) {
Integer lastId = 0;
if(ids.containsKey(regionCode)) {
lastId = ids.get(regionCode);
}
int nextId = lastId++;
ids.put(regionCode, nextId);
return new StringBuilder(regionCode).append('-').append(nextId).toString();
}
public static void main(String[] args) {
String ordersFileName = args[1];
char region = getRegion(args);
List<Object> parsedOrders = parseOrder(ordersFileName );
for(Order order:parsedOrders) {
order.setUid(UIDGenerator.generateRegionUid(region));
}
//persist orders into dataBase.
}
}
Commentaire
22 réponses pour " Java Puzzler "
Published by M Girard , Il y a 11 ans
Vu que c’est une exécution en parallèle, je pense à un problème de concurrence. Genre le StringBuilder de la méthode « generateRegionUid » qui n’est pas thread-safe.
Sinon je me penche sur le constructeur new HashMap() ça non plus c’est pas thread-safe.
En espérant que ça fasse avancer le schmilblick :)
Published by Damien , Il y a 11 ans
Je penche pour une java.util.ConcurrentModificationException qui est lancée car 3 threads itèrent et modifient la même Map static.
Première solution qui me vient à l’esprit :
– Utiliser une Map thread-safe en utilisant java.util.Collections.synchronizedMap
et/ou (?)
– Ajouter synchronized à la méthode generateRegionUid
Published by Damien , Il y a 11 ans
Ou peut-être encore plus simple : transformer la java.util.HashMap en java.util.concurrent.ConcurrentHashMap.
Published by RenéP , Il y a 11 ans
java.util.ConcurrentModificationException car une écriture est en train de se faire en même qu’une lecture dans le HashMap ids.
La solution consiste à synchronizer la map :
private static Map ids = Collections.synchronizedMap(new HashMap());
Published by Rémi F. , Il y a 11 ans
Je pencherais également pour la java.util.ConcurrentModificationException qui peut être déclenché via l’appel au put sur la hashmap, uniquement lors de l’ajout de la région.
Cf javadoc :
Note that this implementation is not synchronized.
If multiple threads access a hash map concurrently, and at least one of
the threads modifies the map structurally, it must be
synchronized externally. (A structural modification is any operation
that adds or deletes one or more mappings; merely changing the value
associated with a key that an instance already contains is not a
structural modification.)
Coté solution, la plus simple (et la plus performante à priori) serait d’initialiser l’id à 0 pour chacune des régions dans un bloc static.
Cf la partie entre parenthèse de la javadoc ci dessus : la modification d’une valeur associée à une clé déjà existante est « thread safe » et ne nécessiterait donc pas de mécanisme particulier de synchronisation.
Published by Etienne Neveu , Il y a 11 ans
Je vote pour une ConstraintViolationException (ou équivalent) pour non-unicité de l’uid. En effet, la ligne
int nextId = lastId++;
ne stocke pas dans nextId la valeur incrémentée, à cause de l’incrémentation postfix. Si lastId vaut « 0 », nextId sera initialisé à « 0 », avant d’incrémenter lastId. Du coup, l’UID généré vaudra toujours « E-0 », « U-0 », ou « A-0 ».
Le reste du programme cherche à mon avis à brouiller les pistes en introduisant des questions sur la concurrence :)
——————————–
@Mathieu:
StringBuilder ne peut à mon avis pas être en cause ici. Il est utilisé localement dans une méthode, et n’est pas partagé avec d’autres threads. Il n’y a donc aucun souci de concurrence.
Quant au constructeur « new HashMap() », la JVM garantit l’initialisation des membres statiques de manière thread-safe (c’est d’ailleurs un bon moyen pour créer des singletons statiques « simples »: http://en.wikipedia.org/wiki/Singleton_pattern#The_solution_of_Bill_Pugh ). Il ne peut donc pas non plus être en cause.
——————————–
Un point qui n’est pas clair dans l’énoncé:
« Lorsqu’on lance le programme dans les trois régions en parallèle, une exception est levée, laquelle et pourquoi est-elle levée ? »
Lance-t-on trois instances du programmes dans 3 JVMs différentes? Si ce n’est pas le cas, il faut effectivement synchronizer la Map, en utilisant une ConcurrentHashMap.
On pourrait même cette Map par un Multiset de Guava, avec l’implémentation thread-safe ConcurrentHashMultiset. Multiset est une Map stéroïdée.
Published by A Alves , Il y a 11 ans
Il n’y a pas de problèmes de synchro sur les map, puisqu’on lance 3 instances du programme , pas 3 threads …
C’est une erreur d’unicité sur le champ uid.
Le constructeur « new StringBuilder( char ) » ne fait pas ce qu’on pense, le char est converti en int et celà crée un StringBuilder non rempli de taille le code ASCII du char.
La première clé générée par generateRegionUid sera toujours « -1 »;
Pour corriger celà changer le return :
return new StringBuilder().append(regionCode).append(‘-‘).append(nextId).toString();
Published by Max_well , Il y a 11 ans
Personnellement, j’irai dans un autre sens.
En partant du principe que les 3 programmes tournent sur 3 machines (régions) différentes, on ne peut pas avoir de problèmes de threading.
(Le programme est lancé avec en paramètre la région, c’est forcement des map différentes pour chaque région)
** Skip 5 mn **
En testant mon hypothèse (pb de transtypage charCharacter), j’ai compilé le code et trouvé les *deux* bugs du code.
Mon hypothèse s’est avéré fausse, mais j’avais au moins raison sur le résultat, c’est bien une SQLException sur une contrainte d’unicité.
Bonne recherche :D
Published by Osman , Il y a 11 ans
Le problème vient de l’instanciation de StringBuilder… En effet, le constructeur utilisé est StringBuilder(int capacity) car regionCode est un char ! Les UID générés commenceront tous par ‘-‘ et ne seront donc pas spécifiques à chaque région, autrement dit, il y aura des collisions !
Pour corriger le problème il faut modifier la ligne 15 en
return new StringBuilder().append(regionCode).append(‘-‘).append(nextId).toString();
Published by Xtof , Il y a 11 ans
Effectivement il y a plein de problème de concurrence dans le code présenté : HashMap, opération non-atomique (lastId++), etc. mais … en relisant l’énoncé : « Lorsqu’on lance le programme dans les trois régions en parallèle » et compte tenu du fait que la région soit déterminée par les paramètres de la ligne de commande il est évident que le programme est lancé trois fois probablement sur des machines différentes et que chaque instance du programme est donc monothreadé. Donc exit les problèmes de concurrence et donc pas d’idée si ce n’est que le fait de recommencer la numérotation à 0 à chaque exécution du programme posera des problèmes d’unicité de clé dans la base à partir de la deuxième exécution. Mais ça n’est probablement pas la solution.
Published by yves-marie , Il y a 11 ans
Il resterait un problème probable, même avec une Map trheadsafe. La méthode generateRegionUid() n’étant pas synchronize, je pencherai plutôt pour une DuplicateKeyException lors de l’enregistrement des entités en base, la méthode pouvant délivrer des id en double. (Dans le cas où l’on a plus d’un thread par région.)
Published by yves-marie , Il y a 11 ans
(Je me corrige, à la relecture de l’énoncé, il ne semble effectivement pas être question de multithreading, donc l’absence de synchronize n’est effectivement pas la cause du problème.)
Published by Aurélien Pelletier , Il y a 11 ans
CaPeutPasMarcherException
int nextId = lastId++;
ids.put(regionCode, nextId);
Les ids dans la HashMap ids restent à zéro. C’est pas plutôt
int nextId = ++lastId;
Published by Hassan , Il y a 11 ans
Merci pour le quiz, je m’y suis donné à coeur joie, d’autant plus que ça me manque bcp de lire du code.
Bon à mon avis :
– Accès concurrents : C’est à coté de la plaque : Programme standalone, les objets ne sont donc pas mappés dans le même espace mémoire.
– StringBuilder(regionCode).append(‘-‘) donne « – » C’est pour ça que l’exception est levée dès l’exécution càd à la première itération.
– int nextId = lastId++; toujours égale à 0. Mais on ne verra cette erreur que si on corrige la précédente.
–
if(ids.containsKey(regionCode)) {
lastId = ids.get(regionCode);
}
Ne sert à rien à mon avis.
Published by baos , Il y a 11 ans
osman et A Alves ont la bonne réponse.
L’unique problème est sur le StringBuilder et la correction :
return new StringBuilder().append(regionCode).append(‘-’).append(nextId).toString();
est suffisante.
Published by yves-marie , Il y a 11 ans
Tout ça pour ça :)
Alors que dans ce cas précis la forme :
return regionCode + ‘-‘ + nextId;
serait probablement plus adaptée. (Identique, mais plus lisible.)
Published by Sébastien D , Il y a 11 ans
Le vrai soucis dans l’histoire c’est que ce code n’est pas testé correctement! :)
Junit to the rescue!
Published by Stéphan , Il y a 11 ans
Si je peux apporter ma pierre à l’édifice,
Une autre exception peut survenir.
Le code ne vérifie pas qu’on lui donne un fichier à parser en ligne de commande.
> String ordersFileName = args[1];
Dans le cas où le programme se lance sans nom de fichier en paramètre, on aura l’exception ArrayIndexOutOfBoundsException.
Published by thierryler , Il y a 11 ans
+1 pour « ce code n’est pas testé correctement! » et même « ce code n’est pas écrit correctement ». Ce n’est pas un puzzle ça !
Published by Hassan , Il y a 11 ans
C’est facile de balancer « C’est de la merde ! » et disparaitre.
Published by Nabil Gasri , Il y a 11 ans
Merci pour toutes vos contributions. Comme certains d’entre vous l’ont trouvé, le code ci-dessus lancera une exception lors de l’écriture dans la base de données à cause d’une violation de la contrainte d’unicité sur l’uid.
Cette exception est liée à deux problèmes dans le code:
1- « int nextId = lastId++; » l’incrémentation postfix fait que nextId reste toujours à 0. Il suffit d’utiliser l’incrémentation préfix.
2- Le constructeur StringBuilder(char) n’existe pas c’est StringBuilder(int capacity) qui est appelé ici. Tous les UID ont la forme « -0-1234 ». Il suffit de faire une simple concaténation de chaîne de caractères. Dans ce genre de cas StringBuilder n’a aucune valeur ajoutée dans le code source.
Tout le reste du code a été écrit pour vous induire en erreur et vous mettre en situation réelle. La concurrence dans ce contexte était le premier suspect.
Ces deux problèmes, auraient pu être facilement détectés si un minimum de test avait été fait.
La Moralité de ce puzzler étant de ne pas abuser des StringBuilder/StringBuffer (laisser le compilateur les rajouter lorsqu’il n’y a pas un vrai besoin de les utiliser clairement) et de bien écrire les tests.
Published by Noureddine , Il y a 11 ans
Par rapport au StringBuffer/StringBuilder effectivement les nouveaux compilateurs optimisent la concaténation des String, mais ça n’a pas toujours était le cas. Moi j’ai écrit ma première Applet sur une station Sparc avec un compilateur 1.2.x : il y a des habitudes qui sont difficiles à perdre.