dimanche 28 février 2010

Sockets - Select vs epoll

Je me suis livré à une petite comparaison de la latence de diverses solutions pour écouter sur une liste de sockets. Mon programme de test contient un thread qui mitraille l'interface de loopback avec de petits messages UDP broadcast contenant un timestamp (obtenu avec clock_gettime sur CLOCK_REALTIME, et surtout pas sur CLOCK_PROCESS_CPUTIME_ID qui peut renvoyer des résultats inconsistants depuis des threads différents).

Un autre thread va écouter sur la même interface, décoder le message, et afficher la différence de temps entre le timestamp reçu et l'heure courante.

Cet autre thread est implémenté soit en utilisant la bibliothèque Asio de chez boost, soit un appel à select, soit un epoll. Cet autre thread, en plus d'écouter sur l'interface, va également écouter d'autres sockets qui ne reçoivent rien. L'on a ainsi un socket très occupé, et les autres qui attendent sagement. Voici donc les résultats de latence (en microsecondes) en fonction du nombre de sockets:



Lorsque l'on écoute sur un seul socket, select est le plus rapide, suivi par epoll et asio, bon dernier. Par contre, lorsque l'on veut écouter sur plus d'un socket à la fois, select ne scale pas bien du tout! La raison est que select va regarder tous les descripteurs de fichier entre 0 et le plus élevé de l'appel, et flagger ceux que l'on veut suivre. Epoll (et Asio, qui est basé sur epoll) reposent sur des mécanismes plus évolués, qui permettent de garder une complexité constante au fur et à mesure que le nombre de descripteurs augmente.

samedi 20 février 2010

Feuille de route

Plus à usage personnel qu'autre chose, voici ma feuille de route.

Serveur de logs
La base est faite, l'on peut envoyer ses logs sous le format par défaut
- Ajouter la possibilité de créer des formats spécialisés
- Ajouter un visualisateur de logs

Serveur de listes
Les structures de base pour les listes sont à peu près correctes.
- Ajouter des tests unitaires
- Développer le serveur en lui-même
- Ajouter les mécanismes d'acquisition de verrous sur les listes
- Ajouter les mécanismes de signalement de changements
- Créer un éditeur de listes

Serveur d'authentification
Le code est plus ou moins là, mais complétement épars.
- Créer le serveur d'authentification
- Ajouter des systèmes fins de permissions
- Ajouter un éditeur de comptes

Serveur de jeu
Tyrion a démarré sur les chapeaux de roues avec le système de magie. Il va falloir fournir un cadre solide via des APIs vers les autres sous-systèmes, pour permettre un développement aussi aisé que possible.

dimanche 14 février 2010

Accès concurrent aux listes de propriétés

Je n'allais quand même pas laisser de côté un tel sujet! Récapitulons. Nous avons:



- Une base de données contenant les listes
- Un serveur de listes (unique), qui fournit l'interface vers la base
- Les serveurs, qui communiquent avec le serveur de listes pour récupérer et sauver les listes
- Les clients
- L'interface d'administration Web, qui cause directement à la base de données.

Les clients ne doivent pas modifier les listes directement, mais indiquer leurs actions aux serveurs, qui modifient les listes en fonction. Les serveurs possèdent un cache des listes, et récupèrent auprès du serveur de listes celles dont ils ont besoin. Tentons de dérouler un exemple pour voir comment tout ceci peut fonctionner.

Le Roi Minablos se connecte sur un serveur. Le serveur récupère auprès du serveur de listes l'ensemble des listes dont il aura besoin, c'est à dire la liste du personnage, les listes parentes, les sous-listes référencées dans la liste (par exemple l'inventaire), et ainsi de suite (encore un diagramme, je suis chaud sur Dia, là!).



Les premières fois, l'on aura probablement une bonne partie du monde à télécharger depuis le serveur de liste, mais, le cache aidant, les serveurs seront rapidement à jour. Pour chaque liste, le serveur détermine s'il a besoin d'un accès en lecture seule, ou d'un accès en écriture, en différenciant les listes correspondant à des objets réels, qu'il gère (le Roi Minablos, une bouteille d'huile d'olive), et les objets virtuels, qui correspondent à des attributs et des propriétés générales du monde (ainsi, la liste "huile d'olive", dont dérive la bouteille, contient les propriétés générale de l'huile d'olive, et n'est accessible qu'en lecture seule).

Le Roi Minablos se saisit d'une bouteille d'huile d'olive, et envoie la requête correspondante au serveur. Le serveur modifie la liste du Roi Minablos, en y référençant la bouteille, et sauve les nouvelles listes auprès du serveur de liste.

Plus compliqué: le Roi Minablos fait pousser un olivier. C'est un cas à part, puisque le serveur doit créer une nouvelle liste. Plutôt que de gérer un long appel au serveur de listes, l'idée est pour le serveur de demander au démarrage un grand nombre de listes vides, dont il peut user comme bon lui semble, et d'en demander d'autres, de manière asynchrone, quand sa réserve s'épuise. Dans le cas de notre olivier, le serveur assigne une de ses listes vides, la fait dériver de l'objet olivier, lui met le Roi Minablos comme propriétaire, puis la référence auprès du serveur de liste.

Encore plus compliqué! Le maître de jeu gère une malédiction lancée par un sorcier maléfique, qui a rendu toutes les pommes empoisonnées. Il modifie dans son interface d'administration les propriétés des pommes. L'interface modifie la base, qui réveille le serveur de listes, lequel rafraîchit ses listes, et envoie des notifications à tous les serveurs qui avaient dans leur cache la liste des pommes. La prochaine fois qu'un joueur voudra croquer dedans, ça fera mal aux gencives!

jeudi 11 février 2010

Un serveur de données

Un des éléments du framework qui me semble particulièrement important est le serveur de données. L'idée est d'avoir un système centralisé qui maintienne l'état des divers éléments du monde, et qui soit accessible via une API simple à intégrer dans les différents services du framework. Les données étant les plus abstraites possibles, c'est le moment parfait pour ressortir du placard mes vieux hacks autour des listes de propriétés. L'on pourra également jeter un coup d'oeil sur ce fil chez les faiseurs de monde de JeuxOnline.

Avec un serveur de listes de propriétés, il devient facile de sauver et de charger tout un tas de données, d'avoir une API toute simple, et même pourquoi pas une belle interface Web pour aller changer les listes en temps réel.

Ensuite, chaque service peut réclamer les listes dont il a besoin. Gestion des combats? Chercher la liste des personnages, regarder quelle est leur arme courante, aller chercher les listes de leurs armes, faire ses petits calculs, et modifier les points de vie, tout ça dans les listes!

L'écriture pose certains problèmes particulièrement intéressants d'accès concurrent aux données. J'imagine que l'on pourrait demander au serveur de liste un lock en écriture, par exemple lors d'une gestion de combat... Ou simplement s'assurer que chaque liste ne sera jamais utilisée que par un système. Mhhh...

dimanche 7 février 2010

Créer une table coûte cher...

Pour mon serveur de logs, j'ai utilisé le système suivant pour écrire un message dans la base Postgresql:

  • Ouvrir la transaction

  • Créer une table temporaire qui sera détruite automatiquement à la fin de la transaction (on commit drop)

  • Remplir la table avec les éléments de mon message

  • Appeler la fonction qui va cŕeer les entrées dans les tables, à partir de la table temporaire

  • Fermer la transaction, causant la destruction de la table temporaire.

Pour tester un peu tout ceci, j'ai envoyé 10000 messages de log d'un coup. Grosse déception, les performances étaient vraiment ridicules, à environ 60 messages par seconde.

J'ai ensuite réessayé en changeant le mécanisme pour la table temporaire: cette fois-ci, je créé la table une seule fois, au tout début, et je dis à Postgres de se contenter de tronquer la table à la fin de la transaction (on commit delete rows).

Surprise, la base de données s'en trouve beaucoup mieux, et pédale à 600 transactions par seconde!

Autant qu'il soit agréable qu'il ait été si simple de décupler ainsi les performances, je ne suis pas tout à fait satisfait par cette solution. Le problème principal est de gérer les reconnections: comment détecter que la table a disparu, et comment la recréer?

J'ai donc changé mon code de manière à appeler, pour chaque transaction, une fonction qui va détecter si la table existe déjà, et si non la créé. Vivement les blocks anonymes (DO $$ ... $$), mais ce sera pour Postgresql 8.5 (ou plutôt, Postgresql 9.0, puisque c'est ainsi que la prochaine version s'appelle désormais).

Verdict: 400 transactions par secondes. Et une routine qui sera imperméable aux déconnections. Ça me va!

samedi 6 février 2010

C++ - Insertion dans une map et hints

Vous est-il déjà arrivé d'insérer des éléments dans une map, en sachant qu'ils étaient déjà ordonnés? Quelle perte de temps, dans ce cas, de payer une insertion logarithmique lorsque l'on sait déjà où l'élément doit aller. Cela tombe bien, std::map fournit la possibilité d'indiquer où l'élément se situe, via un "hint", et d'insérer en temps constant amorti. La documentation n'est cependant pas très précise sur le sujet. Voyons donc ce que ça donne, aidé de notre fidèle nano-horloge (attention, pour Linux seulement).


#include <iostream>
#include <ctime>
#include <vector>
#include <map>

int main()
{
timespec t1, t2, t3;

std::vector<int> keys;
for(int i = 0; i < 100000; i++)
{
keys.push_back(i);
}

std::map<int, int> m1;
std::map<int, int> m2;

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t1);

for(int i = 0; i < keys.size(); i++)
{
m1.insert(m1.begin(), std::make_pair(i, i));
}

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t2);

for(int i = 0; i < keys.size(); i++)
{
m2.insert(std::make_pair(i, i));
}

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t3);

std::cout << "m1: " << t2.tv_nsec - t1.tv_nsec << std::endl;
std::cout << "m2: " << t3.tv_nsec - t2.tv_nsec << std::endl;

return 0;
}


Voilà comment réduire fortement le temps d'insertion (dans la réalité, l'on pourrait avoir à copier quelque chose d'un peu plus lourd qu'un entier, et les gains seraient plus réduits, mais quand même!). Scénario improbable, me direz-vous? Pas tant que ça. Par exemple, sérialisation / désérialisation vers un fichier, ou un format réseau: si l'on contrôle la sérialisation, l'on peut simplement écrire les éléments dans l'ordre du conteneur, et utiliser les hints au moment de la désérialisation. Facile, et fournissant un gain immédiat!