let!, $ et #

Depuis le dernier billet, nous avons fait évoluer quelque peu la structure du code. D’abord, nous nous sommes débarassés de pa_monad pour le remplacer par notre propre préprocesseur. Première modification :

let! x,y = body in expr

Est transformé automatiquement en :

bind body (fun (x,y) -> expr)

C’est une amélioration par rapport à perform et <-- : la coloration syntactique et l’indentation marchent avec des options par défaut (pas besoin d’ajouter des règles spécifiques à perform), l’interaction avec des ; dans le code est correcte, et il n’y a pas de collision avec des bibliothèques qui définissent une fonction perform (par exemple, cURL).

Une deuxième règle de préprocesseur a fait son apparition : dans un contexte d’expression, #foo devient (fun x -> x # foo). Cela présente un intérêt évident dans la définition des templates HTML :

module Item = Loader.Html(struct
  type t = < name : I18n.text ; email : string option > ;;
  let source  _ = "item"
  let mapping _ = [
    "name",  Mk.trad (#name) ;
    "email",  Mk.esc (#email |- BatOption.default "")
  ]
end)

Enfin, bien que Batteries propose un opérateur **>, nous avons repris l’opérateur $ de Haskell pour alléger les parenthèses :

return $ Some value

Au lieu de :

return (Some value)

pa_monad

Sur RunOrg, nous utilisons l’extension de syntaxe pa_monad avec une fonction bind f g = f g. Il s’agit d’une réécriture syntaxique très simple. Lorsque l’on écrit :

perform x <-- a ; b

Le compilateur voit en réalité :

a (fun x -> b)

Cette forme d’écriture permet de dispose d’une syntaxe proche de let x = a in b dans le cas où a n’est pas une expression qui peut être évaluée suivant des règles normales.

Options

Par exemple, nous avons à beaucoup de reprises dans le code qui reçoit des arguments HTTP des structures de la forme suivante :

match request # args "id" with None -> panic | Some id -> 
  (* Beaucoup de code qui utilise "id" *)

Le code correspondant à panic est souvent le même pour tous les arguments d’une même requête, mais est différent suivant les requêtes: affichage d’un message d’erreur, redirection vers une autre page… Cette structure n’est pas élégante. Nous avons essayé dans un premier temps de la supprimer en utilisant des exceptions:

let expect = function None -> raise WasNone | Some x -> x

try 
  let id = expect (request # args "id") in
  (* Beaucoup de code qui utilise "id" *)
with WasNone -> panic

Mais oublier un try pouvait créer des problèmes graves: il n’y avait pas de vérification statique que le cas “identifiant non fourni” était bien traité. Au final, nous utilisons pa_monad de la façon suivante:

let is_some default opt callback = 
  match opt with None -> default | Some x -> callback x

perform id <-- is_some panic (request # args "id") ;
(* Beaucoup de code qui utilise "id" *)

Le comportement est celui attendu : si la valeur est None, alors panic est renvoyé, sinon la valeur est fournie au code sous le nom id et le résultat est renvoyé.

Assertions

Certains cas d’erreur peuvent se produire pendant les requêtes. Par exemple, si Form.is_valid f est faux, alors il y a une erreur dans le formulaire. Cela prenait en général cette forme :

(* Calcul de "form" *)
if not (Form.is_valid form) then
  Form.response form
else
  (* Continuer à traiter le formulaire *)

C’est assez difficile à lire, d’autant que l’indentation augmente progressivement avec le nombre de conditions à vérifier. Avec pa_monad, nous avons une primitive assert_true qui continue l’exécution uniquement si son paramètre est vrai :

let assert_true failure cond callback = 
  if cond then callback () else failure

(* Calcul de "form" *)
perform () <-- assert_true (Form.response form) (Form.is_valid form) ;
(* Continuer à traiter le formulaire *)

Le code devient plus linéaire, donc plus facile à lire.

Requêtes en base de données

Le point le plus utile est en relation avec le client CouchDB que nous utilisons en interne, Breathe. Celui-ci permet de travailler en combinant ensemble des requêtes élémentaires pour construire des requêtes plus complexes. Les combinateurs peuvent alors effectuer des optimisations ad hoc pour minimiser le nombre d’accès à la base de données, que ce soit par un système de cache ou en regroupant des requêtes.

Un combinateur utilisé de façon quasi universelle est “Effectue la requête X, puis utilise son résultat pour déterminer des paramètres de la requête Y, et renvoie le résultat de cette dernière”. Ce combinateur s’écrit:

(* x_req est une requête, pas le résultat de la requête ! *)
let x_req = MyTable.get id in 

(* x est le résultat de x_req *)
let y_req = fun x -> MyTable.get (x # parent) in 
x_req |-> y_req

Ou de façon plus compacte, mais pas forcément plus agréable:

MyTable.get id |-> fun x -> MyTable.get (x # parent)

Or, cette structure ressemble beaucoup à ce que permet de faire pa_monad. Nous utilisons donc breathe :

let breathe req callback = req |-> callback 

perform x <-- breathe (MyTable.get id) ;
MyTable.get (x # parent)

Ainsi, cette réécriture nous permet de travailler avec des requêtes comme s’il s’agissait de let = in traditionnels, tout en conservant l’évaluation optimisée.

Evaluateurs

Le principe sous-jacent est celui d’évaluateurs : là où let x = a in b utilise l’évaluateur standard de OCaml pour évaluer la valeur de l’expression, perform x <-- eval a ; b utilisera l’évaluateur eval. Chaque évaluateur correspond à un type paramétrique de façon à ce que a soit de type 'a t et x soit de type 'a.

Nous avons déjà vu les évaluateurs suivants :

  • is_some default est un évaluateur pour le type 'a t = 'a option, qui renvoie la valeur de l’option si elle existe et default si elle n’existe pas.
  • breathe est un évaluateur pour le type 'a t = 'a Breathe.t, qui évalue la requête fournie utilise la valeur obtenue pour construire une autre requête.

Nous pouvons également imaginer d’autres évaluateurs, peut-être moins utiles, par exemple pour de l’évaluation paresseuse :

 let facebook_query : http_response Lazy.t = (* ... *)

 (* Version standard *)
 let facebook_name : string Lazy.t = 
   lazy ( (Lazy.force facebook_query) # name ) 

 (* Version avec "of_lazy" *)
 let facebook_name : string Lazy.t =  
   perform response <-- of_lazy facebook_query ;
   response # name

 (* L'évaluateur *)
 let of_lazy v callback = lazy (callback (Lazy.force v))

Ou pour travailler en mode multi-thread :

let resize_png : filename -> filename worker = 
  fun file -> worker ... (* redimensionne x *) 

let png_to_jpg : filename -> filename worker = 
  fun file -> worker ... (* convertit x *)

let resize_and_convert : filename -> filename worker =       
  perform resized <-- from_worker (resize_png file) ; 
  png_to_jpg resized

let convert = work (resize_and_convert "big_file.png") 

(* La définition des workers *)

type 'a worker = (exn,'a) BatStd.result ref * Thread.t

let worker f x =  
  let result = ref BatStd.Bad NotEvaluated in
  result, Thread.create (fun x -> result := BatStd.wrap f x) x ;

let work (result, thread) = 
  Thread.join thread ; BatStd.ok !result

let from_worker (result, thread) callback = 
  worker (callback (work (result, thread)))

Mise à jour de SQLite : 3.7.6.3 -> 3.7.7

La bonne nouvelle de ce matin, après une mise à jour de notre serveur SVN:

$ svn commit -m 'Basic vertical/template creation'
svn: Couldn't perform atomic initialization
svn: database schema has changed

Impossible de faire de nouveaux commits. Après quelques recherches sur internet, il s’agit d’un bug dans la version 3.7.7 de SQLite, qui vient d’être publiée il y a trois jours.

Pas de chance… le problème est cependant connu à la fois de SQLite et de Subversion, qui sont tous deux en train de préparer des patches (côté SQLite pour corriger le bug, et côté Subversion pour être quand même capables de fonctionner avec la 3.7.7 si nécessaire). J’attends de mon côté la version 3.7.7.1 de SQLite (ce ne serait pas la première fois que SQLite réagit à un bug en moins d’une journée) en espérant que les package maintainers de Debian seront également réactifs (ils sont au courant du problème, eux aussi).

Et pendant ce temps, je trouve à m’occuper…

Mise à jour de CouchDB: 0.11.0 -> 1.1.0

Debian propose aujourd’hui une mise à jour vers la version 1.1.0 de CouchDB (précédemment, le package couchdb contenait la version 0.11.0). La mise à jour ne lance aucune alerte de compatibilité, à tort.

La mise à jour lancée, toutes mes bases de données avaient disparu.

Bon, respirez un coup : les données, elles, étaient toujours là. Le point important est que la version 0.11.0 conserve ses fichiers de bases de données dans /var/lib/couchdb/0.11.0/ alors que la version 1.1.0 les attend dans /var/lib/couchdb/.

Je suggère donc, après avoir 1. fait une copie de sauvegarde et 2. éteint le serveur couchdb, le déplacement suivant:

cd /var/lib/couchdb/
mv 0.11.0/* 0.11.0/.* .
rm -r 0.11.0

Cette opération va déplacer à la fois les bases de données (*.couch) et les design (.*_design) vers le nouveau répertoire. On relance alors le serveur. Toutes les bases de données apparaissent à nouveau dans Futon.

Il est possible, cependant, que certaines bases de données apparaissent vides, cela m’est arrivé et ne m’a pas beaucoup rassuré. C’est un problème qui se corrige tout seul, une base de données à la fois, grâce à une tâche de fond non documentée qui semble faire une conversion de format de fichier.

J’ai réussi à provoquer l’exécution immédiate de cette tâche en provoquant manuellement une réplication depuis un autre serveur CouchDB. Effectuer une réplication sur une seule base de données a envoyé les statistiques de beam.smp dans la stratosphère pendant quelques minutes, ce qui a abouti à rendre toutes les bases de données de nouveau disponibles.

Si, en dernier recours, vous n’arrivez pas à retrouver vos données, il vous reste toujours une solution: installez un CouchDB 0.11.0 sur un autre serveur, chargez-y vos données, et effectuez une réplication vers votre serveur CouchDB 1.1.0

Et dans tous les cas, prévoyez un peu de temps à chaque mise à jour de CouchDB pour ce genre de petits agacements.

JSON et autres Joyeusetés

Notre système de configuration interne nous permet de gérer un grand nombre de type d’associations et d’entités de façon efficace. Nous pouvons par exemple décider qu’il existe un type d’entité “Match de Foot”, que les inscrits à ce match ont dans leur formulaire d’inscription un champ “Position” (une liste déroulante avec “Avant”, “Avant-Centre” …), et que ce type d’entité peut être créée dans les associations en relation avec le foot (clubs amateurs, clubs pro, associations multi-sports…)

Puis, nous pouvons ajouter de nouveaux champs ultérieurement, y compris sur des matches de foot qui ont déjà été créés, de même qu’activer ou désactiver sélectivement des fonctionnalités au fur et à mesure de leur développement.

Cette richesse s’accompagne malheureusement d’un langage de description également très riche, capable de rentrer dans le détail des objets configurés et qui évolue au fur et à mesure que de nouvelles fonctionnalités apparaissent.

Comment permettre à nos collaborateurs moins adeptes de la technique de saisir des configurations ?

  • Un système épuré, par exemple un language de configuration, permettrait de se contenter d’un parseur et d’un éditeur de texte. Les objets de configuration sont représentés, en interne, par du JSON assez lisible. Malheureusement, modifier du JSON à la main est source d’erreurs…
  • Un système d’édition par formulaires permet d’éviter les erreurs, mais il faut faire évoluer ce système à chaque nouvelle extension, ce qui devient rapidement insupportable.

J’ai donc pour l’occasion ressorti des cartons un vieux projet à moi, du temps où je travaillais encore en PHP. Il s’agit de Joy, un générateur automatique de formulaires en JavaScript. Il reçoit en entrée une description de formulaire (en JSON), et affiche à l’utilisateur un formulaire HTML capable de modifier des valeurs correspondant à cette description, et qui sont elles-mêmes du JSON.

Il suffit donc de décrire à Joy le format du JSON utilisé en interne par le système, et de le laisser faire tout le travail. Par exemple, plutôt que d’écrire à la main le JSON suivant:

[
  ["Config",
    ["Group_Validation","manual"]],
  ["Column",
    ["Add",{
      "after":["profile","firstname"],
      "sort":true,
      "show":true,
      "eval":["profile","lastname"],
      "view":"t",
      "label":""
    }]]
]

On dispose de ce formulaire:

Joy s’occupe automatiquement d’afficher les bonnes listes de valeurs, des (+) et des (-) pour la gestion des valeurs optionnelles et des tableaux, de mettre un jQuery UI Sortable sur les listes de valeurs …

Côté OCaml, j’ai donc défini une interface permettant de définir le formulaire Joy en même temps qu’on définit le type qui lui est associé. Par exemple, pour décrire une infime partie du type ci-dessus:

module DiffColumn = Joy.Make(struct

  let edit = Joy.obj [
    Joy.field "after" ~label:"Insérer après..." (Joy.optional DiffEval.edit) ;
    Joy.field "sort"  ~label:"Triable?" Joy.bool ;
    Joy.field "show"  ~label:"Visible?" Joy.bool ;
    Joy.field "eval"  ~label:"Source" DiffEval.edit ;
    Joy.field "view"  ~label:"Affichage" View.edit ;
    Joy.field "label" ~label:"Etiquette" (Joy.string ())
  ]

  type json t =   <
    after : DiffEval.t option ;
    sort  : bool ;
    show  : bool ;
    eval  : DiffEval.t ;
    view  : View.t ;
    label : string 
  >

end)

Avec ce pattern, faire évoluer le formulaire en même temps que le format JSON devient extrêmement simple, puisque les deux sont représentés au même endroit.

Optimisation

Afin de garantir une expérience utilisateur aussi fluide que possible, il est important de garder les temps de chargement aussi faibles que possible.

Un point critique de l’architecture RunOrg est que changer de page ne provoque pas un rechargement complet, mais seulement le rechargement des parties de la page qui doivent être modifiées. Ceci permet de gagner du temps:

  • Le navigateur n’a plus besoin de faire tout le travail d’initialisation d’une page (récupération des CSS et scripts, exécution initiale des scripts)
  • Le travail sur le DOM (interprétation du HTML, application du JavaScript) se limite aux parties modifiées.
  • Le temps de chargement est réduit car il y a moins de données à transmettre.
  • Le serveur n’a besoin de recalculer que les parties qui ont changé.

Une fois ces modifications en place, la latence côté client ne représente plus qu’une petite partie du temps de chargement (environ 40-50ms, temps de transfert inclus, sur une bonne connexion). Le nouveau point critique devient le serveur.

Un second point critique de l’architecture RunOrg est que les opérations de modification sont effectuées de façon asynchrone. Il est pour nous préférable d’afficher à l’utilisateur une barre de chargement “modification en cours” qui lui permet d’aller visiter d’autres pages, plutôt que de le laisser attendre plusieurs secondes qu’une modification importante se finisse.

Cette règle ne s’applique pas pour les modifications très simples (changer son mot de passe, par exemple), mais est essentielle pour une opération comme l’import de deux mille utilisateurs d’un groupe vers un autre (avec envoi d’invitations, vérification des droits, propagation des évènements…).

Le principe est simple: la demande de l’utilisateur produit non pas l’opération demandée, mais l’inscription en base de données d’une tâche asynchrone. Un autre serveur (potentiellement beaucoup moins costaud que les serveurs web) va alors récupérer la tâche et l’exécuter.

Et donc, au final, le troisième point critique devient simplement le temps de construction des pages sur le serveur.

Malheureusement, le temps de travail dépend beaucoup de la page qu’on affiche, puisque des pages différentes ont des besoins différents en termes d’accès aux bases de données et calcul de rendu. Pour avoir plus de visibilité sur ces temps, nous avons mis en place un onglet “profileur” qui apparaît directement sur le site, et indique le temps de travail qui a été nécessaire pour construire une partie de la page.

Voici, par exemple, les temps de travail nécessaires pour construire la page “Notifications” ce matin:

Les chiffres en millisecondes sont sujets à variation (la ligne “Fetch Notifications” passe de 84 à 49 sans aucune intervention humaine), mais donnent néanmoins un ordre de grandeur. L’information essentielle se trouve dans le nombre de lectures: économiser une milliseconde sur une lecture est beaucoup plus efficace si cette lecture a lieu une dizaine de fois.

Autre point important: s’il est envisageable de mettre en cache, même temporairement, le résultat de certaines lectures, cela permet de gagner du temps, et la mise en cache a plus de chances de servir s’il y a beaucoup de lectures d’un certain type.

Ici, la ligne “Get Notification Avatar” s’exécute une fois par notification, soit dix fois. Or, il n’y a que quatre avatars différents sur cette page, et pour la majorité des utilisateurs (ceux qui ne sont membres que d’une seule association) il n’y aura qu’un seul avatar.

Je peux donc appliquer une memoization de la valeur, pour obtenir:

Cette opération simple aura permis de gagner environ 20 millisecondes sur la requête, soit environ 10% du temps de calcul.

Changement de Schéma

Je travaille aujourd’hui sur le fil d’actualités de l’association, qui doit regrouper des informations venues de divers endroits dans la base de données. En particulier, le système doit récupérer tous les messages postés récemment n’importe où dans l’association, les filtrer pour garder ceux qui sont pertinents (ceux qui sont visibles par l’utilisateur et n’ont pas été postés par lui), et les afficher/

Petit problème : la base de données ne contient pas d’information permettant de rattacher directement un message à une association ! Un rattachement indirect existe bien, en allant regarder dans quelle conversation se trouve le message, et en utilisant l’association liée à la conversation. Mais ce rattachement ne peut être utilisé tel quel pour des raisons de performances ! On se retrouverait alors avec une requête de cette forme :

SELECT msg.message FROM messages msg 
NATURAL JOIN conversations cnv
WHERE cnv.asso = $asso
ORDER BY msg.time DESC
LIMIT $lim

Et, bien évidemment, impossible d’avoir un index à cheval sur les deux tables et qui permettrait de traiter cette requête comme un parcours de $lim éléments d’un index… en SQL, c’est possible mais lent ; en CouchDB, c’est impossible.

La solution consiste donc à dénormaliser le tout pour aller coller un champ msg.asso au bon endroit, afin que la requête devienne :

SELECT message FROM messages WHERE asso = $asso
ORDER BY time DESC LIMIT $lim

Il suffit alors d’un INDEX (asso, time) pour optimiser complètement cette requête. Effectuer cette transformation de la base de données se fait de façon similaire en CouchDB et en SQL :

Créer le champ, en lui autorisant la valeur NULL. Au niveau de RunOrg, c’est l’application qui contrôle le schéma de la base, on ajoute donc le champ dans la représentation objet d’un message :

type json message = < 
  ...
  ?asso : I.Asso.t option ;
  ...
> ;;

Propager l’ajout du champ dans l’application, cette dernière devant maintenant l’initialiser et le lire correctement. Pour RunOrg, il suffit de compiler : le code est écrit de façon à ce que, si un nouveau champ est ajouté, tous les endroits où ce champ doit être traité deviennent des erreurs de compilation. Cinq minutes plus tard, j’ai fini d’expliciter les endroits où la valeur devait être conservée telle quelle et les endroits où elle devait être extraite de la conversation.

Dès que cette étape est faite, tous les nouveaux messages sont automatiquement placés dans la bonne association et apparaissent donc dans le fil d’actualités. Je vérifie rapidement que c’est le cas, puis je passe à l’étape suivante :

Mettre à jour les anciennes valeurs, et c’est là que l’absence de SQL fait mal. En effet, ce que je veux faire est simplement :

UPDATE message msg NATURAL JOIN conversation cnv
SET msg.asso = cnv.asso

Rien d’aussi simple en CouchDB. Je suis donc obligé de créer une vue qui récupère tous les objets pour lesquels le champ est vide :

let _view = 
  MyDB.Map.view 
    Fmt.Unit.fmt
    Fmt.Unit.fmt
    { CouchDB.design = design ;
      CouchDB.name   = "temp_no_asso" ;
      CouchDB.map    = "if (doc.t == 'msg' && !(''asso' in doc)) emit(null,null);" }

Puis, de créer une procédure qui récupère le premier élément de cette vue :

let _first () =
  match MyDB.Map.query _view ~limit:1 () with 
    | [] -> None 
    | (_,id,_) :: _ -> Some id

Et enfin une procédure qui traite le premier élément si elle le trouve :

let process () = 
  match _first () with None -> false | Some id ->
    log "NoAssoFix : %s" (Id.str id) ;   
    MyDB.transaction id begin function 
      | None -> CouchDB.Keep     
      | Some asso -> CouchDB.Put ( ... )
    end ;
    true

let () = Task.Background.register 1000 process

Cette procédure sera appelée en arrière-plan par le robot d’exécution asynchrone (qui s’occupe aussi de bon nombre d’autres choses). C’est un traitement sans verrou, ce qui permet de le réaliser sans avoir à bloquer le site (même si cela met un moment à être exécuté). Je surveille les logs d’exécution pour voir quand les NoAssoFix cessent d’apparaître (indiquant qu’il n’y a plus de données à traiter). Temps de calcul total sur la base de données de production : cinq secondes.

Rendre le champ NOT NULL est la dernière étape.

type json message = < 
  ...
  asso : I.Asso.t ;
  ...
> ;;

Ceci provoque à nouveau l’ire du compilateur, ce qui permet d’identifier et de corriger rapidement tous les endroits du code qui faisaient l’hypothèse que le champ était optionnel. Il suffit de pousser ces modifications en production, et l’ancien modèle de données aura complètement disparu !

η-expansion

Comme tous les langages fonctionnels, Objective Caml permet à une fonction de renvoyer une autre fonction. En fait, il est même usuel de représenter une fonction à deux arguments par une fonction à un argument qui renvoie une fonction à un argument :

let add a b = a + b
let adds_3 = add 3

let seven = adds_3 4

On définit ci-dessus une fonction adds_3 qui ajoute 3 à son argument, simplement en fournissant à add son premier argument, mais pas le second. Cette façon d’écrire les fonctions s’appelle la curryfication, du nom de Haskell Curry, un pionnier des langages fonctionnels.

Bien que cela puisse paraître un peu confus, ce style permet au contraire de clarifier le code en éliminant les variables supplémentaires qui peuvent apparaître dans du code manipulant des fonctions :

let add a b = a + b 
let short = List.map (add 3) [ 1 ; 2 ; 3 ]
let long  = List.map (fun b -> add 3 b) [ 1 ; 2 ; 3 ]

La première version est plus lisible, car elle n’a pas besoin d’introduire une variable supplémentaire b. Cette élimination de la variable b s’appelle une η-réduction, et l’opération inverse qui ajoute la variable b s’appelle une η-expansion.

Ces deux opérations sont mathématiquement équivalentes dans un langage fonctionnel pur, mais présentent une différence de taille dès qu’il y a des effets de bord. L’exemple classique est celui d’une fonction de memoisation :

let memoize f = 
  let h = Hashtbl.create 10 in
  fun x -> 
    try Hashtbl.find h x with Not_found ->
      let y = f x in
      Hashtbl.add h x y ; y

memoize f est une fonction qui, lorsqu’on lui fournit un argument x pour la première fois, calcule et renvoie f x, et qui lorsqu’on lui fournit un argument x pour la deuxième fois, renvoie directement la valeur déjà calculée pour f x sans la recalculer. Ainsi, si f x est une opération complexe (par exemple, impliquant la connexion à un serveur à distance), elle est effectuée aussi rarement que possible.

Exemple d’utilisation :

let details  = memoize Author.get_details in
let with_authors = 
  List.map (fun item -> item, details (item # author)) items 
in
 ...

Si la liste des éléments contient deux éléments ayant le même auteur, un seul appel à Author.get_details aura lieu, économisant ainsi un accès en base de données.

Tout ceci marche parce qu’un effet de bord a lieu au moment où le premier argument de memoize est fourni. Il y a donc deux bugs possibles si on effectue une η-expansion au mauvais endroit:

  • L’effet de bord a lieu trop tard. Par exemple, écrire let details x = memoize Author.details x va créer une nouvelle table de hachage vide à chaque appel, ce qui non seulement n’économisera aucun accès en base de données, mais coûtera en plus le temps d’initialisation et la mémoire initiale de la table de hachage.
  • L’effet de bord a lieu trop tôt. Si let details est défini au niveau global, par exemple, alors deux requêtes HTTP à deux mois d’intervalle récupèreront les mêmes données pour un même auteur : la première requête enregistre les données obtenues en base, et la deuxième les lit. Si l’auteur a changé de photo entre-temps, le changement ne sera pas visible…

La présence d’effets de bord implique donc d’être très attentif au passage d’arguments. Par principe, let f = calcule sa valeur en fonction de l’état du programme à sa définition, alors que let f x = calcule sa valeur en fonction de l’état du programme à son appel. Une excellente raison d’être prudent, et d’éviter autant que possible les effets de bord !

Consolidation de Feeds

Sur la fiche de profil d’un membre apparaît un résumé de son activité récente sur le site de l’association. C’est une liste hétérogène : elle incorpore des informations issues de plusieurs listes indépendantes :

  • Messages, commentaires et favoris sur les murs et discussions de l’association.
  • Inscription et invitation aux activités de l’association.
  • Création, modification et suppression de sondages, évènements, groupes …

Il est facile d’afficher ces listes de façon indépendante avec un système de pagination pour les parcourir. La difficulté ici est de les regrouper en une seule liste triée par ordre chronologique, et de proposer un système de pagination.

La solution SQL est facile à écrire (je simplifie volontairement la syntaxe) :

  ( SELECT id, time FROM wall_posts WHERE author_id = $id )
UNION   
  ( SELECT id, time FROM event_join WHERE person_id = $id )
UNION 
  ( SELECT id, time FROM event_action WHERE actor_id = $id )
ORDER BY time DESC
LIMIT $lim OFFSET $off

Mais déjà, en SQL, une telle requête n’est pas optimisée : l’effet serait ici de parcourir tous les éléments associés à l’utilisateur (en utilisant des index sur author_id, person_id et actor_id), de trier ces éléments par date et de conserver le nombre souhaité. Autrement dit, pour obtenir 10 lignes, on se retrouve à extraire et trier 100, 1000, 10000 lignes (suivant que l’utilisateur est très actif ou très peu actif).

Et il y a d’autres difficultés : chez RunOrg, ces différentes listes peuvent provenir de bases données différentes, voir même dans certains cas de sources externes au site (flux RSS, messages Twitter). Et il y a également des filtres de visibilité complexes à appliquer aux objets (par exemple, on ne peut pas voir que Mr. FooBar est inscrit à un évènement si on ne peut pas voir cet évènement).

La solution utilisée par RunOrg implique de faire deux sacrifices :

  • Ne plus pouvoir utiliser un OFFSET, autrement dit on ne pourra plus demander la page 5. Au lieu de cela, on se permet des requêtes par date, par exemple les 20 éléments qui ont précédé le 29/03/2011 à 23h12. On retombe sur le modèle de pagination CouchDB, donc pas de changement majeur au niveau de l’interface graphique.
  • Accepter que toutes les “pages” n’auront pas la même taille, en appliquant le filtre après l’extraction. On sélectionne ainsi 20 éléments, puis on applique le filtre qui peut en supprimer 0, 5, 13… ou même 20 ! Le cas particulier où aucun élément extrait n’est visible pourra être traité en effectuant une nouvelle requête pour une date plus avancée.

En termes de pseudo-code SQL, cela ressemble à :

  ( SELECT id, time FROM wall_posts WHERE author_id = $id 
    AND time < $time ORDER BY time DESC LIMIT $lim)
UNION   
  ( SELECT id, time FROM event_join WHERE person_id = $id 
    AND time < $time ORDER BY time DESC LIMIT $lim)
UNION 
  ( SELECT id, time FROM event_action WHERE actor_id = $id 
    AND time < $time ORDER BY time DESC LIMIT $lim)
ORDER BY time DESC
LIMIT $lim

Autrement dit, chaque requête de sélection peut s’appuyer sur un index (author_id,time) qui permet de n’extraire que les valeurs souhaitées. Donc, pour $lim = 10, la requête ci-dessus extrait 30 lignes, les trie et renvoie les dix premières. Il faut noter que mathématiquement, pour consolider 10 lignes venues de 3 listes en seulement trois SELECT, il faut extraire au moins 30 lignes : donc, on ne pourra pas faire mieux.

Initialement, on prend pour $time la valeur +∞ pour sélectionner les éléments les plus récents. Ensuite, on prend la valeur time du dernier élément renvoyé.

En termes de CouchDB, chacun des trois SELECT est un simple accès à une vue :

http://localhost:5984/.../_design/feeds/_view/by_user
  ?startkey=[$id,$time]
  &endkey=[$id,0]
  &descending=true
  &include_docs=true
  &limit=$lim

L’union et le tri ultérieurs se font côté serveur, en OCaml. Pour optimiser le processus, on travaillera ici avec des listes construites sur mesure :

type ('time,'data) partial_list = 
 | PL_empty 
 | PL_unknown of 'time
 | PL_item of 'time * 'data * ('time,'data) partial_list

Cette liste est capable de représenter que :

  • Il n’y a plus d’éléments dans cette liste au niveau de la base de données (PL_empty).
  • Il n’y a plus d’éléments dans cette liste côté OCaml, mais il existe au moins un élément au temps t côté CouchDB (PL_unknown t).
  • Il y a au moins un élément e au temps t dans cette liste (PL_item (t,e,tail)).

Construire la liste se fait en demandant n+1 éléments à la base de données, puis en conservant les n premiers et un dernier élément s’il est présent :

let rec extract time n = function
 | [] -> PL_empty 
 | h :: t -> if n = 0 then PL_unknown (time h) else 
  PL_item (time h, h, extract time (n-1) t)

Par construction, les temps sont triés par ordre décroissant dans chacune de ces listes. Les consolider en une liste unique demande donc juste de trier ces listes suivant le temps de leur premier élément :

let list_time min = function
 | PL_empty -> min
 | PL_unknown t | PL_item (t,_,_) -> t

let sort = List.sort (fun a b -> compare (list_time 0.0 b) (list_time 0.0 a)) 

let initial = [ wall_posts ; event_join ; event_action ])
 |> List.map (extract (fun x -> x # time))
 |> sort

Une fois la liste triée, on maintient cette propriété pour s’assurer que le premier élément de la première liste est le plus récent, et on extrait les éléments un à un.

let rec merge = function
  | [] -> PL_empty
  | PL_empty :: t -> merge t
  | PL_unknown _ as h :: _ -> h
  | PL_item (time,i,rest) :: t -> PL_item (time,i,merge (sort (rest :: t)))

Cette méthode garantit que si trois listes de 10 éléments sont fournies en entrée, alors la liste finale aura entre 10 et 30 éléments triés dans le bon ordre. Le dernier élément de la liste est soit un PL_empty (indiquant qu’il n’y a plus aucun élément dans aucune des listes), soit PL_unknown t qui fournit le temps t à partir duquel afficher les éléments de la page suivante.

Pour résumer, l’affichage d’une liste de N éléments à partir de D listes de taille M en base de données implique :

  • Des requêtes en base de données, d’une complexité de O(D · log M + D · N)
  • Un tri des données côté serveur, O(D · log D)
  • Un parcours de la liste triée, O(D · N)

Soit une complexité totale de :

O(D · log M + D · log D + D · N)

Pour comparaison, la complexité de la première requête SQL présentée est de:

O(D · M · log (D · M) + N)

Il faut noter qu’en pratique, D et N seront des constantes, et que c’est la valeur de M qui augmentera avec le temps. De ce point de vue, la version élaborée est bien plus avantageuse que la version initiale.

Modules Vides

Question rapide : vous savez qu’il va y avoir bientôt un sous-module appelé Fizz dans le code que vous êtes en train d’écrire. Mais vous ne savez pas encore quoi mettre dedans… Vous avez donc le choix entre trois options:

(* OPTION 1 : Ne rien faire, on ajoutera Fizz lorsqu'on le définira *)

(* OPTION 2 : Définir Fizz sur une seule ligne *)
module Fizz = struct end

(* OPTION 3 : Définir Fizz sur deux lignes *)
module Fizz = struct
end

Cela a l’air purement cosmétique, mais cela a une importance lorsqu’on travaille à plusieurs sur un même projet. Si Alice ajoute let x = 10 au module et que Bob ajoute let y = 20 au module, leurs modifications sont compatibles entre elles et devraient donc être fusionnées sans aucune collision.

Dans le cas 1, les modifications seront :

+ module Fizz = struct
+   let x = 10
+ end

+ module Fizz = struct
+   let y = 20
+ end

Et la conséquence sera que deux modules Fizz seront définis dans le code final. Inquiétant !

Dans le cas 2, les modifications seront :

- module Fizz = struct end
+ module Fizz = struct
+   let x = 10
+ end

- module Fizz = struct end
+ module Fizz = struct
+   let y = 20
+ end

Les modifications sur la ligne provoqueront une collision. Il n’y aura donc pas d’erreur, mais la fusion nécessitera une intervention humaine.

Dans le cas 3, les modifications seront :

= module Fizz = struct
+   let x = 10
= end

= module Fizz = struct
+   let y = 20
= end

Le résultat sera, comme on s’y attend, d’insérer let x = 10 et let y = 20 dans le module, sans re-définition ni avertissement de la part du système de fusion des modification. Une bonne raison d’agir de la sorte.