De la concurrence des requêtes SQL

Sans cité Montaigne, voici un cas académique dans lequel la concurrence des requêtes SQL est souvent oubliée.

Nous avons une table hits qui contient 4 champs : une date (nommé date), une clé étrangère pointant vers un objet du système (nommée object_id) et un compteur implémenté sous ca forme la plus simple : un entier (nommé counter). Puisqu'on travail avec une framework qui implémente de l'active record on ajoute un champ id qui fera office de clé primaire.
A chaque utilisation de l'objet référencé par la clé étrangère on souhaite incrémenter le compteur et recommencer à 0 tous les minuits afin d'avoir un historique journalier de l'utilisation de l'objet. Alors comme on a quand même un peu réfléchi à la performance du système (un billet sur le sujet est en préparation), on définit un index composé des champs date et object_id. Puis on définit la fonction suivante, donnée ci-dessous en pseudo-code, qui incrémente notre compteur et insère un nouveau tuple si aucun n'existe pour le jour courant :

void function hit ( int $object_id ) {
  SELECT FROM hits WHERE object_id = $object_id AND date = NOW()
  if (row_exists)
      UPDATE hits SET counter = counter + 1 WHERE  object_id = $object_id AND date = NOW()
  else
      INSERT INTO hits (object_id, date, counter) VALUES ($object_id, NOW(), 1)
}

Tout se passe bien jusqu'au jour où on se rend compte qu'il y a plusieurs lignes par objet et par jour dans la base de données.

Ce problème vient du fait qu'il peut se passer un temps indéterminé entre la requête SELECT et l'INSERT. Si à 00h01 2 requêtes sont faites en même temps sur le même objet, il est fort probable que 2 requêtes SELECT soient faites avant un INSERT, et donc les 2 tests if (row_exists) vont retourner faux et 2 INSERT seront fait.

Les solutions pour résoudre ce problème sont multiples, elles passent de la redéfinition de la clé primaire en date, object_id plutôt que notre champ id, ce qui aurait comme comportement de faire échouer le 2ème INSERT, erreur qui pourrait être capturée et traitée spécifiquement. Une autre solution serait de mettre un verrou sur la fonction, chose très aisée en Java avec le mot-clé synchronized. La fonction deviendrait void synchronized function hit(int object_id), évitant ainsi ce type de problème de concurrence.

Dans tous les cas les applications web sont aussi (voir même plus) soumises aux problèmes de concurrence, et l'expérience nous montre que la technique de l'autruche de même que les phrases du style "Il ne PEUT PAS y avoir 2 requêtes en même temps" sont à bannir absolument.

Getting Things Done® (GTD® aussi) : le sydrome du "Ca c'est fait !"

Un mot très en vogue en ce moment (cf Google trend sur getting things done), GTD® est une méthodologie d'organisation des tâches quotidiennes à accomplir. Dévoilée dans un livre écrit par David Allen publié en 2001, Getting Things Done®, the art of stress-free productivity, elle reprend un certain nombre de choses connues en matière de gestion du temps mais les systématise dans un processus structuré, gage d'efficacité.

Cette systématique est intéressante car elle peut nous faire prendre conscience de la méthodologie que peut-être certain utilisaient déjà et ainsi nous amener à y réfléchir en vue de l'optimiser à nos besoins.

L'objectif de GTD® est de porter toute la créativité et l'énergie sur la seule action qu'on a délibérément choisi de faire et d'approcher au mieux un état de productivité sans stress annoncé.

Les 2 concepts mis en exergue par cette théorie sont les suivants :

• Les tâches sont interdépendantes
• Les priorités des tâches dépendent d'un contexte

Fort de ce constat, GTD® nous donne une systématique pour

• recenser les tâches et les reporter sur des listes par sujet,
• identifier celle qui peuvent être exécutées immédiatement et les reporter sur une TODO list
  
• les réaliser dans un ordre de priorité dépendant du contexte (temps à disposition, état de fatigue, endroit, ...).
  

Une fois la tâche accomplie, GTD® propose une phase de revue durant laquelle la tâche est notée comme faite (le fameux syndrome du "Ca c'est fait !", qui n'est en réalité rien qu'un petit vu sur la TODO list mais qui procure une satisfaction bien au-delà du consentement, mais là je m'égare...) et le cycle organisationnel peut recommencer.

GTD® ne propose pas de support spécifique pour la liste des tâches à accomplir (TODO list), mais précise que le moyen utilisé doit être fiable.

Une petite corollaire de GTD® que je trouve intéressantes est que les tâches prenant moins de 2 minutes sont faites immédiatement. Car "moins de 2 minutes" est à peu près le temps pris pour la gestion organisationnelle de la tâche.

Pour ceux qui comme moi pensent que la curiosité n'est pas toujours un vilain défaut :

• http://www.davidco.com/what_is_gtd.php
• http://fr.wikipedia.org/wiki/Getting_Things_Done
• http://wiki.43folders.com/index.php/Productivity_pr0n

Getting Things Done® et GTD® sont des marques déposées depuis 2005.

60 millions de hashes md5 !

Sur mon petit projet de revserse md5 lookup database, je viens de dépasser les 60'000'000 de hashes md5 dans la base de données interne, qui fait maintenant 4.2 GB.

En gros j'ai introduit dans la base tous les hashes de 4 lettres composés des caractères a-z, A-Z, 0-9, ., -, _, !, $, *, %, &, /, (, ), =, ?, #, @, +, ", [, ], {, }, et tous les hashes de 5 lettres composés de caractères a-z.

On remarque que sur l'échantillon généré les hashes sont bien uniformément répartis, mais on a une préférence non significative pour les hashes commençant pas 0x46.

La prochaine étape est les hashes de 5 à 7 lettres composés des caractéres a-z et 0-9, ce qui nous fait ~80'000'000'000 de hashes supplémentaires...
Ensuite je prendrais les dictionnaires Openoffice afin de générer les hashes de mots existants.

Happy md5 cracking sur md5.noisette.ch.

Uniqid ou la contre-intuitivité des arguments

D'après le manuel PHP, le prototype de la fonction uniqid est le suivant :

string uniqid ( [string prefix [, bool more_entropy]] )

Le deuxième paramètre à l'air réellement intéressant, dans la mesure où il assure une meilleure unicité de la chaine produite. Une propriété qui de toute évidence nous intéresse si on utilise cette fonction uniqid.

Sans s'étendre sur la probabilité de collision entre les 2 appels (ce que j'étendrai plus longuement dans un autre article), je voulais juste montrer la différence de vitesse d'exécution qu'induisait ce paramètre more_entropy. Un petit script faisant 100 appels à uniqid avec une valeur possible du paramètre, nous donne le résultat suivant (!) :

100 * uniquid(mt_rand()) en 0.799283981323 seconde

100 * uniquid(mt_rand(), true) en 0.00346183776855 seconde

Chose extrêmement intéressante, le temps d'exécution de la fonction est 3 ordres de grandeurs en dessous si on demande une meilleures unicité du résultat.

La question obligée est donc : pourquoi est-ce que cette fonctionne ne prend pas par défaut cette option, puisqu'elle a tous les avantages (meilleures résultats, plus rapide) ?

Optimisation du nombre de requêtes SQL dans les collections d'objets et relation n-m

L'orientation objet de PHP n'est plus contestable, mais les problèmes d'optimisation persistent.

Par exemple le malheureusement célèbre n+1 pattern, qui fait que pour afficher une liste de n objets, le + 1 étant la requête qui sélectionne tous les ids des objets à instancier, n + 1 requêtes SQL seront effectuées.

De même dans des relations n-m, la majorité des implémentations sélectionnent les n objets (en n + 1 requêtes donc), puis pour chacun on sélectionne les m objets de la relation. On obtient donc n * m + 1 requêtes.

Le but de cet article est de présenter deux techniques qui, combinées, réduisent les n * m + 1 requêtes en n + m + 1.

Les deux techniques que je vais illustrer ici se nomment object caching et grouped fetching. Elles se combinent très bien, ce qui permet d'optimiser drastiquement les performances d'un script PHP, du points de vue I/O (moins de requêtes), vitesse d'exécution et même mémoire utilisée (les objets ne sont pas dupliqués).

Object caching :

Le principe de l'object caching est de rendre le constructeur de l'objet privé (au pire protégé) et de l'instancier au moyen d'une factory. Puis on ajoute à la classe un tableau statique dans lequel les références des objets instanciés seront placés. La factory va donc regarder dans le tableau de références si l'objet existe, et si ça n'est pas le cas elle va le créer, l'ajouter au tableau et le retourner.

class A {
 protected static $objects_cache = array();

 public static function factory($id, $class = __CLASS__)
 {
   if (array_key_exists($id, $class::$objects_cache)) {
     return $class::$objects_cache[$id];
   } else {
     $o = new $class($id);
     $class::$objects_cache[$id] = $o;
     return $o;
   }
 }
}

Cette solution pourrait encore être améliorée si les objets pouvaient être partagés entre toutes les instances de PHP. Ce n'est pas le cas à cause de l'architecture share nothing de PHP, et c'est un des points forts des serveurs d'applications.
Un autre désavantage de ce concept, si on a un script qui tourne suffisamment longtemps pour que le grabage collector se lance, est que tous les objets créés sont toujours référencés, même ceux qui pourraient être des candidats potentiels à la finalisation. Ce problème est résolu dans d'autres langages, en Java par exemple grâce aux références faibles (WeakReference).

Grouped fetching

Le principe du grouped fetching, dérivé d'une solution proposée par notre ami Colder, est de charger les données des objets de manière asynchrone et en bloque. Quand un objet est instancié, il est marqué comme non chargé, et sa référence est placée dans un tableau global de la classe. Puis lors d'un accès à un champ non chargé, la classe va sélectionner dans la base de données tous les objets instanciés mais pas encore chargés. Plus on retarde les accès aux attributs d'un objet, plus on va paralléliser les requêtes SQL.

class A {
 private static $_to_load = array();
 private $_is_loaded = false;
 public function __construct($id)
 {
   $this->id = $id;
   self::$_to_load[$id] = $this;
 }

 public function __get($attribut)
 {
   if (!$this->_is_loaded) {
     self::_groupedLoad();
   }
   return $this[$attribut];
 }

 private function _setLoaded()
 {
   $this->is_loaded = true;
 }

 private static function _groupedLoad()
 {
   $ids = implode(', ', self::$_to_load);
   $query = 'SELECT * FROM ' . self::$_table . ' WHERE id IN ( ' . $ids . ' ) ';
   $res = db_query($query);
   while ($row = $res->getNext()) {
     self::_to_load[$row['id']]->_initByArray($row);
     self::_to_load[$row['id']]->_setLoaded;
   }
 }
}

L'overhead de ce concept est très faible (un tableau de références supplémentaire), et le nombre d'accès à la base de données sont grandement réduit. Mais le problème de la finalisation des objets se repose aussi.

De l'art d'éviter les requêtes SQL inutiles

Dans le domaine de l'optimisation, une chose simple à faire est d'essayer de réduire au strict minimum le nombre de requêtes à faire à la base de données.

Je souhaite simplement rendre attentif au problème posé par les procédures embarquées et autres tirggers :

Dans le cas d'une mise-à-jour d'un objet mappé sur une table d'une base de données, les champs de l'objet sont remplacés (après nettoyage...) par ceux du formulaire. On pourrait donc penser qu'il est inutile de faire un SELECT juste après un UPDATE, car les données mises-à-jour sont celles fournies.

Cela est vrai sans compter sur les triggers déclenchés en cas de mises-à-jour : sans un SELECT après l'UPDATE, certains champs peuvent contenir des données fausses car non traitées par le trigger. Les champs auto-timestamp de Mysql sont un exemple tout simple de trigger à ne pas oublier...