En général ces gros logiciels sont installés sur des stations dédiées dimensionnées spécifiquement pour tenir la charge, c'est pourquoi les algorithmes privilégies les performances plutôt que l'optimisation de consommation mémoire. Sauf que lorsque un serveur nécessite de maintenir plusieurs dizaines d’indexes sur plusieurs dizaines de millions d'objets, la mémoire vive peut se retrouver rapidement saturée engendrant un écroulement des performances globales.
Cet article va traiter d'un algorithme d'indexation que j'ai mis au point pour pallier à ce problème en alliant performance et consommation mémoire lorsque l'on doit travailler avec plusieurs millions d'objets.
La bonne compréhension de cet article nécessite un bon niveau en programmation générale avec des connaissances en langage C#.
Get the English version of this article on CodeProject
Introduction
Il y a quelques années, j'ai développé le système de stockage d'une technologie SGBD NoSQL.
Le serveur devait enregistrer les données sous la forme clé/valeur sur le disque, et être capable de gérer divers aspects comme le système transactionnel, la réplication, le verrouillage, la réparation des segments corrompus, le compactage ainsi que des compteurs sur le nombre de données présentes dans les bases, la place prise, la place perdue, ...
Pour arriver à bout de toutes ces fonctionnalités, les données devaient être enregistrées avec un entête de bloc, et l'ensemble de ces blocs devaient être rangés dans plusieurs indexes à multiples critères.
Au départ, j'ai utilisé les outils classiques offerts par le .NET framework : SortedList, Dictionary, SortedDictionary, mais très vite, des dysfonctionnements se sont révélés lors des tests de charges.
Il a donc été nécessaire de créer ma propre liste pour permettre de réaliser un serveur qui puisse gérer un très grand nombre de données, rapide, peu gourmand en mémoire et capable d'indexer des données en triant les ensembles selon plusieurs clés.
Le serveur devait enregistrer les données sous la forme clé/valeur sur le disque, et être capable de gérer divers aspects comme le système transactionnel, la réplication, le verrouillage, la réparation des segments corrompus, le compactage ainsi que des compteurs sur le nombre de données présentes dans les bases, la place prise, la place perdue, ...
Pour arriver à bout de toutes ces fonctionnalités, les données devaient être enregistrées avec un entête de bloc, et l'ensemble de ces blocs devaient être rangés dans plusieurs indexes à multiples critères.
Au départ, j'ai utilisé les outils classiques offerts par le .NET framework : SortedList, Dictionary, SortedDictionary, mais très vite, des dysfonctionnements se sont révélés lors des tests de charges.
Il a donc été nécessaire de créer ma propre liste pour permettre de réaliser un serveur qui puisse gérer un très grand nombre de données, rapide, peu gourmand en mémoire et capable d'indexer des données en triant les ensembles selon plusieurs clés.
Etat de l'art
Avant de commencer à présenter ma solution, je vais déjà présenter le problème.
Pour cela, nous allons observer le comportement des différents algorithmes offert par le .NET framework en essayant de leurs injecter 10 millions d'objets avec des données aléatoires.
Au cours de ces tests, je vais recueillir la quantité de mémoire utilisée ainsi que le temps passé pour chacun des outils testés.
Voici l'objet qui sera utilisé pour remplir nos indexes :
public class DataObject
{
private static readonly Random Random = new Random();
private readonly Guid _id = Guid.NewGuid();
private readonly DateTime _date = new DateTime(Random.Next(1980, 2020),Random.Next(1,12), Random.Next(1,27));
private readonly int _number = Random.Next();
public Guid ID
{
get { return _id; }
}
public DateTime Date
{
get { return _date; }
}
public int Number
{
get { return _number; }
}
}
Une factory permettra de générer autant d'instance que voulu pour notre test :
public static class DataFactory
{
public static List<dataobject> GetDataObjects(int number)
{
var result = new List<dataobject>();
for(int i = 0; i < number; i++)
result.Add(new DataObject());
return result;
}
}
Vous remarquerez que la factory renvoie directement une liste au lieu d'une énumération. Ceci est fait exprès pour que les calculs de temps ne soient pas faussés par le temps de génération de chaque objet.
Nous mettrons en place aussi un compteur de performance pour collecter les données sur le temps et la quantité de mémoire utilisée par l'algorithme :
public class PerfCounter : IDisposable
{
private readonly Stopwatch _stopwatch = new Stopwatch();
private readonly long _currentMemoryUsage = Process.GetCurrentProcess().WorkingSet64;
private readonly string _filePath;
public PerfCounter(string filePath)
{
if( string.IsNullOrEmpty(filePath) )
throw new FileNotFoundException();
string directoryPath = Path.GetDirectoryName(filePath);
if( string.IsNullOrEmpty(directoryPath) )
throw new FileNotFoundException();
Directory.CreateDirectory(directoryPath);
if (!File.Exists(filePath))
File.AppendAllText(filePath, "Memory\tTime\r\n");
_filePath = filePath;
_stopwatch.Start();
}
public void Dispose()
{
_stopwatch.Stop();
GC.Collect();
long memory = Process.GetCurrentProcess().WorkingSet64 - _currentMemoryUsage;
File.AppendAllText(_filePath, _stopwatch.Elapsed.ToString() + "\t" + memory + "\r\n");
}
}
Maintenant que nous avons tous ce qu'il faut pour commencer notre analyse, enchaînons sur le premier outil disponible.
SortedList
Une SortedList représente une collection de paires clé/valeur triées par la clés qui est accessible par clé et par index.
Nous allons injecter 1 million d'objets aléatoires selon la méthode suivante :
private static void TestSortedList()
{
var sortedList = new SortedList<Guid, DataObject>();
for (int i = 0; i < 10; i++) {
List<DataObject> datas = DataFactory.GetDataObjects(100000);
using (var counter = new PerfCounter("c:\\Indexation\\SortedList.txt")) {
foreach (DataObject dataObject in datas) {
sortedList.Add(dataObject.ID, dataObject);
}
}
}
}
voici le résultat de ce petit programme :
Temps total d'insertion pour 1 million d’éléments : 785 secondes
Mémoire total pour indexer 1 million d’éléments : 54 Mo
Comme vous pouvez le constater, l'insertion dans une SortedList est extrêmement lente car il nous a fallu 13 minutes pour insérer 1 million d'objets. Je rappelle que notre objectif à l'origine est de pouvoir gérer des dizaines de millions d'objets, il est donc inenvisageable d'utiliser cette méthode.
Pourquoi la SortedList est elle si lente ?
Pour une raison très simple : une liste est un tableau d'éléments rangés de façon contigus.
Lorsque l'on ajoute un élément à la fin de la liste, il suffit de l'empiler comme ceci :
Cette opération n'apporte aucun sur coût à l'algorithme. c'est d'ailleurs pour ça que les tests de performances sur des données non aléatoires peuvent faire croire que l'insertion dans une liste est extrêmement rapide du fait que le système ne fait qu'ajouter les données dans la liste.
Par contre, lorsque l'on veut insérer un élément au milieu de la liste (c'est le cas d'une liste triée), nous n'avons pas d'autre choix que de décaler tous le bloc d’élément supérieur pour faire une place à la nouvelle donnée, puis de recoller cette suite à la fin de la liste.
Évidemment, cette opération est fortement coûteuse en terme de temps car plus il y a d’éléments dans la liste, et plus l'opération de copier/coller sera longue, surtout lorsque il faudra insérer des éléments au début de la liste.
Ici, l'équation pour la courbe de tendance sur le temps d'insertion est
Ainsi, importer 10 millions d’éléments aléatoires dans une SortedList prend théoriquement 36 heures !
Un dictionnaire C# est une collection d'objets génériques de type Clé/Valeur qui se base sur l'algorithme HashTable.
Comme précédemment, nous allons obtenir le temps d’exécution et la quantité de mémoire utilisée par l'algorithme pour 10 millions d'objets.
Voici le résultat :
Temps total d'insertion pour 10 millions d’éléments : 2 secondes
Mémoire total pour indexer 10 millions d’éléments : 638 Mo
Le temps d'insertion est beaucoup mieux, mais la mémoire utilisée est trop importante.
Imaginez si nous devions créer 5 indexes pour des objets pesant 20 octets chacun, l'ensemble des éléments pèserait 200 Mo tandis que l'algorithme prendrait 3 Go et 190 Mo en RAM !
Pourquoi la hashtable prend tant de place ?
Lorsque l'on ajoute un élément dans une hashtable, une clé est utilisée pour calculer un numéro relativement unique (appelé hashcode). Je dis "relativement" car il se peut que deux clés différentes est le même hashcode, ce phénomène est appelé une collision.
Pour palier à ce problème, une hashtable possède en interne une table à deux dimensions (appelé buckets) qui contient des entrées sous formes de structures à plusieurs paramètres. ce sont ces entrées qui prennent beaucoup de place.
En général une entrée est composée du hashcode, de la clé, de la valeur et d'un pointeur sur l’élément suivant , car les buckets sont en fait des tableaux de listes chaînées.
L’intérêt de toute cette structure est de pouvoir ranger intelligemment les données indexées par le hashcode
En gros, le hashcode est soumis à un modulo sur la longueur du bucket ce qui donne l'index ou son entrée est stockée. Une fois cet index connu, une boucle parcours l'ensemble des entrées correspondantes pour comparer toutes les clés et leurs hashcodes avec l'élément à insérer.
Si une clé identique est trouvée, le système renvoi une erreur.
Si un hashcode identique est trouvé alors que la clé est différente, une nouvelle entrée est est créée dans la liste chaînée.
Si vous regardez dans le graphique, vous pouvez observez qu'a partir de 6 millions d'objets, la mémoire fait un bon exceptionnel de 100%. Je suppose que ceci est dût à une pré-allocation au niveau du bucket suite à un nombre important de collision.
Ainsi, plus il y a d'objet à indexer, plus la probabilité de collision est importante, ce qui force la hashtable à allouer beaucoup de mémoire pour maintenir son niveau de performance. Cette technique est donc à proscrire lorsque l'on veut traiter un très grand nombre d'objets !
SortedDictionary & SortedDictionary2
D'après le MSDN, la classe SortedDictionnay a été conçue pour palier à la problématique de vitesse d'insertion d'une SortedList. Voyons ce que cela donne avec notre système de test :
Temps total d'insertion pour 10 millions d’éléments : 5 secondes
Mémoire total pour indexer 10 millions d’éléments : 612 Mo
Temps total d'insertion pour 10 millions d’éléments : 5 secondes
Mémoire total pour indexer 10 millions d’éléments : 649 Mo
A la vue des résultats, vous allez vous demander pourquoi utiliser un SortedDictionnary plutôt qu'un Dictionnary simple ? effectivement à consommation de mémoire équivalente, le Dictionnary est deux fois plus rapide !
Nous arrivons ici à une deuxième dimension de notre problème, l'indexation à plusieurs profondeurs.
Tous nos tests sont basés sur la recherche à une seule clé, mais il y existe des cas ou nous désirons par exemple trier les objets par date, puis pour chaque date les ranger par taille, puis par identifiant. Si nous voulions faire cela avec un simple Dictionnary, nous serions obligés de l'implémenter de la façon suivante :
Dictionary<DateTime, Dictionary<int, Dictionary<Guid, DataObject>>> index = new Dictionary<DateTime, Dictionary<int, Dictionary<Guid, DataObject>>>();
Comme vous l'aurez compris, nous imbriquons trois dictionnaires. Non seulement cette méthode apporte de la complexité au niveau de l'implémentation, mais surtout la quantité de mémoire utilisée sera multipliée par 3, nécessitant 2Go de RAM au lieu des 650Mo du SortedDictionnary.
La SortedDictionnary permet de s’affranchir du problème grâce à l'implémentation obligatoire d'un "comparer" qui lui permettra de faire de la recherche dichotomique sur une liste de dictionnaires internes.
Ma solution : la SortedSplitList
Sur le même modèle que les tests précédents, voici ce que donne l'insertion de 10 millions d'objets dans une SortedSplitList
Temps total d'insertion pour 10 millions d’éléments : 5 secondes
Mémoire total pour indexer 10 millions d’éléments : 235 Mo
L'algorithme met autant de temps qu'un SortedDictionnary pour une consommation mémoire presque 3 fois inférieure au Dictionnary ou SortedDictionnary !
Comment fonctionne la SortedSplitList ?
Pour mettre au point cet algorithme, je suis parti de la SortedList et j'ai cherché à améliorer sa vitesse d'insertion.Comme je vous l'ai expliqué lors de l'analyse de performance de la SortedList, sa lenteur viens du fait que pour insérer un élément au début d'une liste, le système doit tout d’abord retirer tous les éléments supérieurs à l’élément à insérer, puis les ré-empiler par la suite.
Pour que vous puissiez vous rendre compte du temps perdu à faire cette opération, empilez soigneusement une centaine d'assiettes les unes sur les autres, puis insérez en une à la dix-huitième position.
La méthode consiste donc à ne pas travailler sur une seule liste qui peut potentiellement être énorme, mais de travailler sur plusieurs petites listes rangées de manière intelligentes :
Structure interne de la SortedSplitList
Imaginons que nous voulons faire l'insertion de l’élément 27. Dans un premier temps, nous faisons une recherche dichotomique sur l'ensemble des listes afin de trouver celle qui devra contenir l’élément;
Recherche de la sous liste devant accueillir le nouvel élément
Une fois la liste obtenue, il suffit de faire une deuxième recherche dichotomique à l'intérieur de celle ci, et d'y insérer l’élément comme dans une liste triée classique :
Recherche de l'emplacement d'insertion dans la sous-liste
Insertion du nouvel élément.
Grâce à cette méthode simple, l'impacte sur le temps d'insertion est fortement diminué tout en conservant l'avantage d'une consommation mémoire optimale !
Utilisation du code
Pour utiliser une SortedSplitList, il faut déclarer en premier lieu un "comparer" par défaut de l'objet que l'on désire indexer :
Objet à indexer :
Comparer par défaut :
Objet à indexer :
public class TestObject
{
public int Id { get; set; }
public int Id2 { get; set; }
public DateTime Date { get; set; }
public string Data { get; set; }
}
Comparer par défaut :
public class CompareById : IComparer<TestObject>
{
public int Compare(TestObject x, TestObject y)
{
if (x.Id == y.Id)
return 0;
if (x.Id < y.Id)
return -1;
return 1;
}
}
Créez ensuite une nouvelle instance de SortedSplitList avec ce comparer :
SortedSplitList<TestObject> sortedSplitList = new SortedSplitList<TestObject>(new CompareById());
Une fois ceci fait, vous pouvez ajouter, retrouver ou supprimer des éléments de la liste à l'aide des méthodes Add(), Retrieve() ou BinarySearch() et Remove(), RemoveAll() ou Clear().
En ce qui concerne la méthode Retrieve, le premier argument doit être une instance d'objet configurée avec les paramètres sur lesquelles on désire effectuer la recherche.
Par exemple, si je veux retrouver un TestObject dont l'identifiant est 78 pour connaître la valeur de son champ Data, je dois m'y prendre de la façon suivante :
var searchObject = new TestObject {Id = 78};
var foundObject = sortedSplitList.Retrieve(searchObject);
Console.WriteLine(foundObject != null ? foundObject.Data : "Data not found.");
La méthode BinarySearch() permet quant à elle de retrouver l'index de l’élément que l'on recherche, donnant la possibilité de parcourir la SortedSplitList en fonction de vos besoins.
Pour savoir comment travailler avec l'index retourné par la méthode BinarySearch(), referez vous à la page MSDN traitant de la méthode BinarySearch() sur les listes génériques
Travailler avec des enregistrements rangés selon des critères multiples
Imaginons que nos TestObject aient une clé composée de Date + Id.
Comment faire pour ranger et retrouver un tel élément dans un SortedSplitList ?
Pour ranger les éléments, rien de plus facile. Il suffit de définir un comparer par défaut comme suit :
public class CompareByDateId : IComparer<TestObject>
{
public int Compare(TestObject x, TestObject y)
{
int dateResult = x.Date.CompareTo(y.Date);
if (dateResult == 0) {
if (x.Id == y.Id)
return 0;
if (x.Id < y.Id)
return -1;
return 1;
}
return dateResult;
}
}
Ainsi, les méthodes Add() et Retrieve() vous permettrons de travailler avec vos éléments à clé composée.
Maintenant, comment s'y prendre si nous voulons connaitre tous les éléments d'une date donnée ?
Voyant que la SortedSplitList permet donne accès à un enumerator, un débutant en programmation serait tenté d'utiliser la méthode suivante :
foreach (var testObject in sortedSplitListSortedById.Where(a => a.Date == DateTime.Parse("2003/01/01")))
Console.WriteLine(testObject.Data);
Cela peut parfaitement fonctionner si votre liste contient peu d’élément, mais les performances de cette ligne de code peuvent s'avérer catastrophique ci la liste contient plusieurs millions d'objets.
La méthode adéquate dans ce cas consiste à faire une recherche binaire selon un comparer spécialisé pour la recherche de date, puis de parcourir les éléments de la liste en sens inverse jusqu’à trouver le premier. Une fois cet élément trouvé, il suffit de reparcourir la liste dans le bon sens en ne renvoyant que les éléments qui correspondent avec les critères de recherche.
Si tous cela vous semble compliqué à mettre en oeuvre, la méthode PartiallyEnumerate() risque de vous être fort utile pour mener à bien cette tache. Voici comment l'utiliser.
Tous d’abord, nous définissions un comparer spéciale pour la recherche par date, et uniquement par date :
public class CompareByDate : IComparer<TestObject>
{
public int Compare(TestObject x, TestObject y)
{
return x.Date.CompareTo(y.Date);
}
}
Ensuite, nous pouvons appeler la méthode PartallyEnumerate() en lui passant un objet de comparaison comportant la date que nous désirons, et le comparer ci dessus :
foreach (var testObject in sortedSplitList.PartiallyEnumerate(new TestObject() { Date = DateTime.Parse("01/01/2003") }, new CompareByDate()) )
Console.WriteLine(testObject.Id);
Avec cette méthode, le foreach affichera tous les id des elements datés du 01/01/2003 sans prendre plusieurs minutes si votre liste contient des millions d'objets.
Conclusion
Bien que les outils d'indexations fournis par le .NET framework soient largement suffisant pour la plupart des besoins logiciel, la SortedSplitList peut s'avérer très utile pour traiter un très grand volume d'objets dans votre application, celle-ci allie l'optimisation mémoire d'une SortedList, la vitesse d'insertion d'un SortedDictionary tout en donnant la possibilité de travailler sur plusieurs clés.
Ainsi, vous pourrez facilement indexer vos données selon plusieurs critères sans craindre de voir trop rapidement apparaître une OutOfMemoryException.
Ainsi, vous pourrez facilement indexer vos données selon plusieurs critères sans craindre de voir trop rapidement apparaître une OutOfMemoryException.
Aucun commentaire:
Enregistrer un commentaire