Optimiser la répartition de charge avec le “Consistent Hashing”

load balancingQuelques mois d’absences, une publication irrégulière mais vous êtes toujours aussi nombreux à passer sur ce site et à m’écrire, merci !  C’est donc avec plaisir que je publie de nouveau sur ce blog.

Lors de ces quelques mois d’absences, beaucoup de changements et de contacts. Et régulièrement, la question du partitionnement refait surface. C’est pour cette raison que j’ai décidé de revenir vers vous pour vous parler des fonctions de “Consistent Hashing“.

Le modèle classique de répartition de charge utilise un “load balancer” pour aiguiller le trafic sur plusieurs serveurs. Cette répartition est généralement basée sur une formule statique (hash, round robin, etc…), qui affecte à chaque élément entrant, une ressource. Cette allocation est dépendante du nombre de ressources disponibles, et une modification de cette dernière implique un nouveau partitionnement (avec perte de session, cache et autre).

Généralement, c’est donc un hash de l’entrée, modulo le nombre de serveurs qui permet de faire une affectation simple. On ajoute souvent une notion de persistance pour améliorer la gestion des sessions et le cache. Mais ce type de fonction est toujours dépendante du nombre d’éléments disponibles dans le cluster en charge de la réponse. Gros inconvénients de cette méthode, lors de l’ajout ou de la suppression d’un élément (perte d’un serveur web, ajout d’un serveur de base de données, etc…) toute la répartition est à refaire

L’ajout de ressource devient donc coûteuse, et à chaque ajout une réorganisation des données/sessions est nécessaire.

consistent hashing

Les fonctions de “Consistent Hashingcorrigent en grande partie ce problème. Elles sont plus complexes, mais elles disposent d’une forme de “mémoire“, permettant de ne pas modifier les allocations précédemment effectuées au moindre changement. Elles sont aujourd’hui bien implémentées dans les load-balancer web mais pas encore dans les répartiteurs de charge applicatifs développés pour répartir les requêtes sql, memcache ou autre…

Si vous êtes en charge de la répartition des requêtes sur un cluster, je vous conseille vivement de regarder ces liens (notamment celui du blog d’Octo). Ils vous expliquerons en quoi ces fonctions permettent d’optimiser considérablement l’allocation de ressources dynamique faite par votre répartiteur de charge. Vous trouverez également des implémentations de cette technique dans différents langages : ici en Java , ou là en C, Python, PHP (merci Pierre-Yves).

Comme d’habitude, si vous avez déjà utilisé cette technique, merci d’avance pour votre feedback !

Liens et sources :

Sur le même thème :

5 Responses to “Optimiser la répartition de charge avec le “Consistent Hashing””

  1. Pierre-Yves Kerembellec says:

    Une implémentation très performante pour C, PHP et Python : http://github.com/dailymotion/chash

  2. Marc says:

    Merci Pierre-Yves, pour le lien, et la rapidité du commentaire !!!

  3. Quasi-indispensable et donc très utilisé également pour les gros parcs de memcached :)

  4. Marc says:

    Oui effectivement Renaud, très efficace pour partitionner du memcached.

    Et j’imagine que chez Facebook vous en possédez un certain nombre ;-)

  5. [...] la répartition de charge intelligente, je vous propose de faire un tour du coté des reverse-proxy, et notamment de Varnish. Pour ceux [...]

Leave a Reply