Brevet FR3050553A1 — publié le 20171027

INTERSEC4.FRD Système de base de données L'invention concerne le domaine des bases de données, et en particulier leurs applications temps réel à grande échelle. Un exemple est la gestion des bases de données des opérateurs de téléphonie mobile. En effet, ces derniers gèrent en permanence une quantité extrêmement importante de données concernant des lignes téléphoniques d'abonnés. Chaque ligne téléphonique génère de nombreux événements de nature passive comme des connexions, déconnexions, changements de cellule, enregistrement auprès des stations de base, etc. Un opérateur mobile à typiquement entre 5 et 25 millions d'abonnés, ce qui représente une base de données dont la taille est comprise entre plusieurs dizaines de gigabits et plusieurs térabits. La fourniture de services dans ce contexte, même basiques, nécessite de pouvoir accéder à l'ensemble des données relatives aux lignes et à traiter ces données de diverses manières en temps réel. Cela est encore plus complexe lorsqu'il s'agit d'offrir des services de type promotionnel, c'est-à-dire accorder des bonus prédéterminés a des abonnés en fonction de leur consommation, ou lorsqu'il s'agit d'analyser en temps réel le comportement des abonnés sur une zone donnée afin de reconfigurer les ressources pour s'adapter aux besoins. Des solutions généralement retenues pour faire face à ces défis impliquent l'utilisation de systèmes de bases de données toujours plus puissants, basés sur des grappes de dimensions toujours plus importantes, et qui ont maintenant atteint leurs limites. L'invention vient améliorer la situation. À cet effet, l'invention propose un système de base de données, comprenant une pluralité de dispositifs informatiques et un allocateur agencé pour répartir les données de la base de données sur les dispositifs informatiques. Les dispositifs informatiques sont chacun désignés par un indice d'hôte et comprennent chacun une mémoire vive. L'allocateur est agencé : 3050553 2 - pour organiser une pluralité d'espaces indexés sur chaque mémoire vive, et pour organiser une partie au moins des données de la base de données en morceaux ayant un indice de morceau, - pour définir une pluralité de séquences distinctes entre elles comprenant chacune une 5 pluralité de couples dont le nombre est égal au nombre de dispositifs informatiques, chaque couple associant une valeur de rang unique et un indice d'hôte, - pour maintenir une liste des dispositifs informatiques fonctionnels au cours du temps, - pour associer chaque morceau à une séquence de la pluralité de séquences, sur la base de la liste des dispositifs informatiques fonctionnels, de sorte que, pour deux morceaux 10 ayant respectivement un premier indice de morceau et un deuxième indice de morceau tels que la différence entre le premier indice de morceau et le deuxième indice de morceau est égale au nombre de séquences de la pluralité de séquences, une séquence donnée de la pluralité de séquences est associée à un unique morceau dont l'indice de morceau est compris entre le premier indice de morceau et le deuxième indice de 15 morceau, - pour définir, pour un morceau d'indice de morceau donné, parmi la liste des dispositifs informatiques fonctionnels, un espace maître sur le dispositif informatique dont l'indice d'hôte est associé au rang le plus bas dans la séquence associée au morceau donné, l'espace maître étant choisi sur le dispositif informatique comme l'espace dont l'indice 20 correspond à l'indice de morceau donné, - pour définir, pour un morceau d'indice de morceau donné, parmi la liste des dispositifs informatiques fonctionnels, une pluralité d'espaces esclaves, choisis sur des dispositif informatiques de telle manière que la somme de rangs associés aux indices d'hôtes de ces dispositifs informatiques dans la séquence associée au morceau donné est minimale, 25 chaque espace esclave étant choisi sur le dispositif informatique respectif comme l'espace dont l'indice correspond à l'indice de morceau donné. Les dispositifs informatiques sont en outre agencés de telle sorte qu'un dispositif informatique qui reçoit un espace maître réplique les données du morceau associé sur 30 les espaces esclaves correspondants. 3050553 3 Ce système est particulièrement avantageux car il permet de réaliser une base de données qui est entièrement stockée en RAM, ce qui permet d'obtenir des performances inégalées. En outre, ce stockage est réalisé de manière répartie, ce qui permet à la fois de répartir la charge sur les divers dispositifs informatiques, mais également de gérer 5 une tolérance aux pannes. Selon diverses variantes, le dispositif peut présenter une ou plusieurs des caractéristiques suivantes : - l'allocateur est agencé pour définir un nombre d'espaces esclaves inférieur au nombre 10 de dispositifs informatiques moins un ; - l'allocateur est agencé pour définir, parmi la pluralité d'espaces esclaves associés à un morceau donné, un ensemble d'espaces esclaves critiques et un ensemble d'espaces esclaves de tolérance, et dans lequel l'espace maître associé à un morceau donné est agencé pour confirmer l'écriture d'une donnée relative au morceau donné uniquement 15 lorsque cette donnée a été répliquée sur l'ensemble d'espaces esclaves critiques du morceau donné ; - l'allocateur est agencé pour définir la pluralité de séquences distinctes et pour associer chaque morceau à une séquence de la pluralité de séquences en initialisant, pour chaque indice de morceau, un indice d'hôte avec l'indice de morceau modulo le nombre de 20 dispositifs informatiques, et en répétant autant de fois que le nombre de dispositifs informatiques une séquence dans laquelle : - si l'indice d'hôte est déjà associé à l'indice de morceau, redéfinir l'indice d'hôte en lui ajoutant un et en réalisant sur le nombre obtenu une opération modulo le nombre de dispositifs informatiques, jusqu'à trouver un indice d'hôte 25 qui n'est pas déjà associé à l'indice de morceau, - l'indice de morceau est associé à l'indice d'hôte, et à un rang dont la valeur est tirée de l'itération de la séquence, - l'indice d'hôte est redéfini en lui ajoutant la valeur un ainsi que l'indice de morceau modulo le résultat de la soustraction d'un entier naturel au nombre de 30 dispositifs informatiques, et en réalisant sur le résultat de ces additions une opération modulo le nombre de dispositifs informatiques, ledit entier naturel étant le même pour toutes les répétitions de la séquence et choisi de sorte que le 3050553 4 nombre de dispositifs informatiques et le nombre de dispositifs informatiques moins ledit entier naturel sont premiers entre eux ; et - l'allocateur est agencé pour définir la pluralité de séquences distinctes sur la base d'une pluralité de couples distincts associant un indice d'initialisation compris entre 0 et 5 le nombre de dispositifs informatiques, et un indice de parcours compris entre 1 et le nombre de dispositifs informatiques moins un, chaque séquence distincte étant générée initialisant un indice d'hôte avec l'indice d'initialisation, et en répétant autant de fois que le nombre de dispositifs informatiques une séquence dans laquelle : - si l'indice d'hôte est déjà associé à l'indice de morceau, redéfinir l'indice 10 d'hôte en lui ajoutant un et en réalisant sur le nombre obtenu une opération modulo le nombre de dispositifs informatiques, jusqu'à trouver un indice d'hôte qui n'est pas déjà associé à un rang, - l'indice d'hôte est associé à un rang dont la valeur est tirée de l'itération de la séquence, 15 - l'indice d'hôte est redéfini en lui ajoutant la valeur de l'indice de parcours, et en réalisant sur le résultat de cette addition une opération modulo le nombre de dispositifs informatiques. L'invention concerne également un procédé de gestion de base de données, comprenant 20 la répartition des données de la base de données sur une pluralité de dispositifs informatiques, comprenant les opérations suivantes : (a) associer un indice d'hôte à chaque dispositif informatique, (b) organiser une pluralité d'espaces indexés sur la mémoire vive de chaque dispositif informatique, 25 (c) organiser une partie au moins des données de la base de données en morceaux ayant un indice de morceau, (d) définir une pluralité de séquences distinctes entre elles comprenant chacune une pluralité de couples dont le nombre est égal au nombre de dispositifs informatiques, chaque couple associant une valeur de rang unique et un indice d'hôte, 30 (e) associer chaque morceau à une séquence de la pluralité de séquences, sur la base de la liste des dispositifs informatiques fonctionnels, de sorte que, pour deux morceaux ayant respectivement un premier indice de morceau et un deuxième indice de morceau 3050553 5 tels que la différence entre le premier indice de morceau et le deuxième indice de morceau est égale au nombre de séquences de la pluralité de séquences, une séquence donnée de la pluralité de séquences est associée à un unique morceau dont l'indice de morceau est compris entre le premier indice de morceau et le deuxième indice de 5 morceau, en (el) définissant, pour un morceau d'indice de morceau donné, parmi la liste des dispositifs informatiques fonctionnels, un espace maître sur le dispositif informatique dont l'indice d'hôte est associé au rang le plus bas dans la séquence associée au morceau donné, l'espace maître étant choisi sur le dispositif 10 informatique comme l'espace dont l'indice correspond à l'indice de morceau donné, (e2) définissant, pour un morceau d'indice de morceau donné, parmi la liste des dispositifs informatiques fonctionnels, une pluralité d'espaces esclaves, choisis sur des dispositif informatiques de telle manière que la somme de rangs associés 15 aux indices d'hôtes de ces dispositifs informatiques dans la séquence associée au morceau donné est minimale, chaque espace esclave étant choisi sur le dispositif informatique respectif comme l'espace dont l'indice correspond à l'indice de morceau donné, (f) stocker les données de chaque morceau donné sur l'espace maître qui lui est associé, 20 (g) répliquer les données stockées sur les espaces maîtres sur les espaces esclaves correspondants. Ce procédé peut comprendre l'une ou plusieurs des caractéristiques suivantes : - l'opération (e2) comprend la définition d'un nombre d'espaces esclaves inférieur au 25 nombre de dispositifs informatiques moins un ; - l'opération (e2) comprend la définition, parmi la pluralité d'espaces esclaves associés à un morceau donné, un ensemble d'espaces esclaves critiques et un ensemble d'espaces esclaves de tolérance, et comprenant en outre l'opération (h) confirmer l'écriture d'une donnée relative à un morceau donné uniquement 30 lorsque l'espace maître associé au morceau donné a répliqué cette donnée sur l'ensemble d'espaces esclaves critiques du morceau donné ; - les opérations (d) et (e) sont réalisées : 3050553 6 - en initialisant, pour chaque indice de morceau, un indice d'hôte avec l'indice de morceau modulo le nombre de dispositifs informatiques, et - en répétant autant de fois que le nombre de dispositifs informatiques une séquence dans laquelle : 5 - si l'indice d'hôte est déjà associé à l'indice de morceau, redéfinir l'indice d'hôte en lui ajoutant un et en réalisant sur le nombre obtenu une opération modulo le nombre de dispositifs informatiques, jusqu'à trouver un indice d'hôte qui n'est pas déjà associé à l'indice de morceau, - l'indice de morceau est associé à l'indice d'hôte, et à un rang dont la 10 valeur est tirée de l'itération de la séquence, - l'indice d'hôte est redéfini en lui ajoutant la valeur un ainsi que l'indice de morceau modulo le résultat de la soustraction d'un entier naturel au nombre de dispositifs informatiques, et en réalisant sur le résultat de ces additions une opération modulo le nombre de dispositifs informatiques, ledit entier 15 naturel étant le même pour toutes les répétitions de la séquence et choisi de sorte que le nombre de dispositifs informatiques et le nombre de dispositifs informatiques moins ledit entier naturel sont premiers entre eux ; et - l'opération (d) comprend : (dl) définir une pluralité de couples distincts associant un indice d'initialisation 20 compris entre 0 et le nombre de dispositifs informatiques, et un indice de parcours compris entre 1 et le nombre de dispositifs informatiques moins un, (d2) pour chaque couple distinct, initialiser un indice d'hôte avec l'indice d'initialisation, et répéter autant de fois que le nombre de dispositifs informatiques les opérations suivantes : 25 (d21) si l'indice d'hôte est déjà associé à l'indice de morceau, redéfinir l'indice d'hôte en lui ajoutant un et en réalisant sur le nombre obtenu une opération modulo le nombre de dispositifs informatiques, jusqu'à trouver un indice d'hôte qui n'est pas déjà associé à un rang, (d22) associer l'indice d'hôte à un rang dont la valeur est tirée du nombre de 30 répétitions de l'opération (d2) déjà réalisées pour le couple distinct courant ; et 3050553 7 (d23) redéfinir l'indice d'hôte en lui ajoutant la valeur de l'indice de parcours, et en réalisant sur le résultat de cette addition une opération modulo le nombre de dispositifs informatiques. 5 L'invention concerne enfin un produit de programme d'ordinateur comprenant des portions de code de programme pour mettre en oeuvre le dispositif ou le procédé décrits plus haut lorsque ledit programme est exécuté sur un ordinateur. D'autres caractéristiques et avantages de l'invention apparaîtront mieux à la lecture de 10 la description qui suit, tirée d'exemples donnés à titre illustratif et non limitatif, tirés des dessins sur lesquels : - la figure 1 représente un système de base de données selon invention dans son environnement, - la figure 2 représente un exemple d'une fonction mise en oeuvre par l'allocateur de la 15 figure 1, et - la figure 3 représente un exemple d'affectation de morceaux à des espaces selon invention. Les dessins et la description ci-après contiennent, pour l'essentiel, des éléments de 20 caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant. La présente description est de nature à faire intervenir des éléments susceptibles de protection par le droit d'auteur et/ou le copyright. Le titulaire des droits n'a pas 25 d'objection à la reproduction à l'identique par quiconque du présent document de brevet ou de sa description, telle qu'elle apparaît dans les dossiers officiels. Pour le reste, il réserve intégralement ses droits. La figure 1 représente un système de base de données 2 selon l'invention dans son 30 environnement. Dans l'exemple décrit ici, le système 2 comprend une pluralité de dispositifs informatiques 4, un allocateur 6 et un terminal 8. Le terminal 8 permet dans l'exemple décrit ici d'offrir des services de gestion de données d'abonnés de téléphonie 3050553 8 mobile, par exemple pour mettre en place des processus de bonus de consommation automatique en fonction du comportement des abonnés. Pour cela, le terminal 8 accède à la base de données de téléphonie mobile qui est stockée sur les dispositifs informatiques 4 et dont la répartition est gérée par l'allocateur 6. Plus précisément, 5 allocateur 6 a pour fonction la répartition des données de la base de données sur les mémoires vives des dispositifs informatiques 4 et l'interactions avec le terminal 8 pour garantir qu'une donnée modifiée a bien été enregistrée dans la base de données et a fait l'objet d'un nombre suffisant de réplications. 10 Les dispositifs informatiques 4 peuvent être tout dispositif informatique propre à être mis en oeuvre dans un réseau de dispositifs gérés par l'allocateur 6. Il peut s'agir d'un ordinateur classique, d'un ordinateur sous forme de lame, ou de tout autre appareil informatique dont la mémoire vive peut être adressée par l'allocateur 6. Par mémoire vive, on entend toute mémoire présentant un temps d'accès inférieur à 100ns. Les 15 dispositifs informatiques 4 peuvent être utilisés à de pures fins de stockage, c'est-à-dire que l'allocateur 6 les commandes entièrement et exclusivement pour le stockage des données de la base de données. En variante, les dispositifs informatiques 4 peuvent également être utilisés comme ressources de calcul aux fins des applications sur la base de données. 20 L'allocateur 6 peut être réalisé sous la forme d'un code informatique exécuté sur un ou plusieurs processeurs. Par processeurs, il doit être compris tout processeur adapté aux calculs décrit plus bas. Un tel processeur peut être réalisé de toute manière connue, sous la forme d'un microprocesseur pour ordinateur personnel, d'une puce dédiée de type 25 FPGA ou SoC (« system on chip » en anglais), d'une ressource de calcul sur une grille, d'un microcontrôleur, ou de toute autre forme propre à fournir la puissance de calcul nécessaire à la réalisation décrite plus bas. Un ou plusieurs de ces éléments peuvent également être réalisés sous la forme de circuits électroniques spécialisés tel un ASIC. Une combinaison de processeur et de circuits électroniques peut également être 30 envisagée. L'allocateur 6 peut également être mis en oeuvre sur un ou plusieurs des dispositifs informatiques 4. 3050553 9 Comme cela sera explicité avec la figure 2, l'allocateur 6 organise les données de la base de données en une pluralité de morceaux indexés. Cela signifie que certaines lignes sont contenues dans un premier morceau, d'autres dans un deuxième morceau, etc. Cela peut également être réalisé table par table, ou par un mélange de ces deux possibilités. 5 Ce découpage est unique, de sorte qu'une donnée particulière de la base de données est située dans un seul et unique morceau. Dans l'exemple décrit ici, l'allocateur 6 organise la totalité de la base de données. En variante, l'allocateur 6 peut organiser une partie seulement de la base de données comme décrit plus bas, et stocker le reste de la base de données d'une manière différente. De la même manière qu'il organise la base de 10 données, l'allocateur 6 organise les mémoires vives des dispositifs informatiques 4. Ainsi, l'allocateur 6 peut accéder à une pluralité d'espaces indexés qui désignent chacun une partie d'une mémoire vive sur les dispositifs informatiques 4. Ici aussi, cet indexage est unique, de sorte qu'un espace donné correspond à une unique portion d'une mémoire vive d'un dispositif informatique 4. 15 Ainsi, l'allocateur 6 organise la réplication d'une manière très spécifique les morceaux indexés de la base de données sur les espaces indexés des mémoires vives des dispositifs informatiques 4. La réplication est d'autant plus importante que les mémoires vives, si elles offrent des performances inégalées pour la rapidité et la capacité de 20 traitement des données, sont particulièrement sensibles aux pannes. En effet, elles ne sont pas capables de maintenir les données qu'elles contiennent si le dispositif informatique 4 qui les reçoit n'est pas alimenté. Ainsi, si pour une quelconque raison un dispositif informatique 4 interrompt son fonctionnement, que ce soit à cause d'une panne système ou d'une panne électrique, les données contenues dans la mémoire vive 25 de ce dispositif informatique 4 seront perdues, et la base de données risque d'être incomplète et/ou corrompue. De plus, afin d'optimiser les performances du système de base de données 2, il peut être intéressant de dimensionner le nombre de dispositifs informatiques 4 et la mémoire vive 30 qu'ils embarquent en fonction des opérations recherchées. En effet, il est important d'équilibrer la charge sur l'ensemble du système de bases de données 2, tant pour un usage instantané et courant que pour une récupération en cas de panne. En répartissant 3050553 10 de manière intelligente les morceaux sur les espaces, la performance du système de base de données 2 peut être optimisée lors d'un fonctionnement normal. Mais cette répartition doit également tenir compte des cas exceptionnels, comme la perte d'un dispositif informatique 4 donné, et la nécessité d'utiliser des espaces contenant des 5 réplicas pour fonctionner. Ces opérations sont d'autant plus complexes que, dans le cas d'une base de données stockée de manière répartie sur des mémoires vives, les risques de panne sont plus importants que dans les systèmes de stockage de base de données classique. 10 Ainsi, l'allocateur 6 définit pour chaque morceau de la base de données un espace qui est qualifié de maître et une pluralité d'espaces sont qualifiés d'esclaves. L'espace maître sera celui qui sera appelé par le terminal 8 pour toute opération de lecture ou d'écriture de la base de données pour le morceau concerné. Une fois les données stockées sur l'espace maître, l'allocateur 6 organise la réplication des données sur 15 l'ensemble des espaces esclaves, dans un ordre indiqué par un rang respectif associé à chacun des espaces esclaves. Selon l'invention, l'allocateur 6 détermine de manière absolue les morceaux de la base de données qui sont accessibles à un instant donné. Pour cela, l'allocateur 6 détermine 20 qu'un morceau donné de la base de données n'est accessible que s'il est présent sur un espace maître et sur au moins un nombre minimum d'espaces esclaves. Dans l'exemple décrit ici, ce nombre est en général égal à 1 ou 2. De la même manière, l'écriture d'une donnée n'est confirmée que lorsque celle-ci a été répliquée au moins dans le nombre minimum d'espaces esclaves. Ces espaces esclaves seront appelés espaces esclaves 25 critiques dans la suite. En outre, l'allocateur 6 peut également fixer un nombre maximum d'espaces esclaves inférieur au nombre de dispositifs informatiques 4. Dans l'exemple décrit ici, le nombre maximum d'espaces esclaves est en général choisi égal au nombre minimum d'espaces 30 esclaves ajouté de 1 ou 2. Dans ce cas, pour un morceau donné, le système de base de données 2 est capable de tolérer la perte d'un nombre de dispositifs informatiques 4 recevant un espace (maître ou esclave) stockant le morceau donné égal au nombre 3050553 11 maximum moins le nombre minimum d'espaces esclaves. Les espaces esclaves au-delà du nombre minimum d'espaces esclaves seront appelés espace esclaves de tolérance dans la suite. 5 La figure 2 représente un exemple d'une fonction mise en oeuvre par l'allocateur 6 pour affecter les morceaux à des espaces et déterminer un rang pour les espaces. Cette fonction est mise en oeuvre à l'initialisation du système de base de données 2, ainsi qu'à chaque fois qu'un dispositif est ajouté ou retiré de manière définitive, c'est-à-dire à chaque fois que l'architecture des dispositifs informatiques 4 utilisés change de manière 10 non temporaire. Dans une opération 200, un indice de morceau k est initialisé avec la valeur 1, un nombre entier j qui est fixé pour toutes les exécutions de cette fonction est reçu, ainsi qu'un nombre de morceaux K et un nombre de dispositifs informatiques H. Dans une opération 210, une boucle est lancée avec l'initialisation à 1 d'un indice d'itération de boucle i. Cette boucle a pour fonction l'attribution d'un rang à chacun des espaces dont l'indice dans les mémoires vives des dispositifs informatiques 4 est égal à l'indice de morceau k courant. La boucle est également initialisée avec une opération 220 dans laquelle un indice d'hôte h est initialisé avec la valeur correspondant l'indice de morceau k courant modulo le nombre de dispositifs informatiques H. 25 Ensuite, dans une opération 230, une fonction Av() qui reçoit comme arguments l'indice de morceau k courant et l'indice d'hôte h est exécutée. Cette fonction détermine si l'espace d'indice k dans le dispositif informatique 4 d'indice h est déjà associé à un morceau. Si c'est le cas, alors l'indice d'hôte h est mis à jour dans une opération 240, et l'opération 230 est répétée jusqu'à trouver un espace libre. Dans l'opération 240, 30 l'indice d'hôte h est mis à jour avec la valeur correspondant à l'indice h ajouté de 1 modulo le nombre de dispositifs informatiques H. 15 20 3050553 12 Ainsi, lorsqu'un nouveau dispositif informatique 4 est ajouté comme ressource, ou lorsqu'un dispositif informatique 4 redevient accessible suite à une panne, seuls les espaces qui n'ont pas un morceau qui leur est attribué se voient mis à jour. 5 Une fois qu'un espace libre a été déterminé, une fonction Sto() recevant comme arguments l'indice d'itération de boucle i, l'indice de morceau k courant, et l'indice d'hôte h est exécutée. La fonction Sto() associe le morceau d'indice k courant à l'espace d'indice k sur le dispositif informatique 4 d'indice h, et affecte à cet espace un rang égal à l'indice d'itération de boucle i. Ainsi, lorsque le rang 0 est attribué à un espace, celui- 10 ci est l'espace maître pour le morceau d'indice k. Les autres itérations associent des espaces esclaves critiques ou de tolérance. La copie, la mise à jour et/ou la réplication des données d'un morceau donné sur un espace nouvellement associé à ce morceau peut être réalisée dès l'affectation du rang ou différée dans le temps. 15 Ensuite, l'indice d'itération de boucle i est comparé au nombre de dispositifs informatiques H-1 dans une opération 260 pour déterminer si tous les espaces d'indice k courant ont été associés au morceau d'indice k courant. Lorsqu'il reste des espaces à associer, l'indice d'hôte h est mis à jour dans une opération 270, l'indice d'itération de boucle i est incrémenté dans une opération 280, et la boucle reprend avec 20 l'opération 230. Dans l'opération 270, l'indice d'hôte h courant est ajouté d'une valeur égale à 1 ajouté de l'indice de morceau k courant modulo la différence entre le nombre de dispositifs informatiques H et le nombre entier j, le tout modulo le nombre de dispositifs informatiques H. 25 Selon l'invention, le nombre entier j est choisi de sorte que le nombre de dispositifs informatiques H et le nombre de dispositifs informatiques H retiré du nombre entier j sont premiers entre eux. La Demanderesse a découvert que cette formule est particulièrement avantageuse car 30 elle offre une répartition de rang statique et indépendante de l'état des morceaux. Ainsi, la mise à jour en temps réel ne nécessite que la liste des dispositifs informatiques 4 3050553 13 disponibles ainsi que l'état de réplication des morceaux, sans qu'il soit nécessaire de tenir compte de la charge des dispositifs informatiques 4. La Demanderesse a également découvert que les résultats les meilleurs étaient obtenus 5 en fixant j égal à 1. En effet, selon l'invention, l'allocateur définit H*(H-j) séquences d'affectation de rangs distinctes. Donc, lorsque K est supérieur à H*(H-j), certaines séquences d'affectation de rangs vont être répétées, et la perte d'un dispositif informatique 4 donné affectera plusieurs morceaux pour lesquels un espace maître ou esclave était affecté à celui-ci. En fixant j égal à 1, il est possible de maximiser la valeur 10 H*(H-j) et donc augmenter la résilience du système de base de données 2. De plus, cette répartition assure une haute stabilité au système de base de données 2 en permettant la désignation d'un nombre d'espaces esclaves calibré pour tolérer un nombre choisi de pannes par morceau. Cela garantit une continuité de service choisie 15 selon les besoins de l'application, et permet également d'équilibrer la charge sur le système de base de données 2 de manière optimale en permettant de choisir de manière optimale les moments auxquels les espaces esclaves de tolérance doivent être mis à jour et/ou récupérés. En effet, il suffit que l'espace maître et les espaces esclaves critiques d'un morceau donné soient à jour pour que le morceau soit considéré comme à jour et 20 actif. Le traitement des espaces esclaves de tolérance peut être réalisé au moment le plus important du point de vue de la charge du système de bases de données. Enfin, cette formule garantit la stabilité de l'assignation des morceaux aux espaces, puisqu'au fur et à mesure que les dispositifs informatiques 4 sont récupérés après des 25 pannes, ce sont toujours les mêmes espaces qui seront affectés comme espace maître, espaces esclaves critiques, et espaces esclaves de tolérance. La Demanderesse a également découvert que des résultats encore meilleurs peuvent être obtenus lorsque le nombre de dispositifs informatiques H est un nombre premier. 30 Une fois que tous les espaces ont été affectés pour un indice de morceau k donné, celui-ci est comparé au nombre de morceaux K dans une opération 290. S'il reste des 3050553 14 morceaux à associer, alors l'indice de morceau k est incrémenté dans une opération 295. Sinon la fonction se termine dans une opération 299. La figure 3 représente un exemple d'allocation obtenu avec la fonction de la figure 2, 5 avec un nombre de dispositifs informatiques H égal à 5 et un nombre de morceaux K égal à 20. Sur la base des associations réalisées avec la fonction décrite sur la figure 2, l'allocateur 6 peut initialiser le système de base de données 2 sur la base des règles 10 suivantes : - pour chaque morceau, l'espace de rang 0 de plus petit rang disposant d'une copie à jour des données du morceau est désigné comme espace maître, - les r espaces accessibles de rang les plus faibles et n'ayant pas été désignés comme maître sont désignés comme espaces esclaves critiques, 15 - les R-r espaces accessibles de rangs suivants sont désignés comme espaces esclaves de tolérance, - les H-R-1 espaces restants (s'ils existent) ne sont pas affectés, et pourront devenir des espaces esclaves de tolérance et/ou critiques si suffisamment de dispositifs informatiques 4 tombent en panne. 20 Ensuite, tous les espaces sont progressivement remplis par ordre d'importance, c'est-à-dire d'abord le maître, puis les esclaves critiques et enfin les esclaves de tolérance. Dès que l'espace maître et les espaces critiques d'un morceau donné sont remplis, le morceau correspondant est déclaré accessible au terminal 8. 25 C'est une étape importante, car, jusqu'à la perte d'un dispositif informatique 4, l'allocateur 6 n'intervient plus directement dans la réplication des données, le maître se chargeant de maintenir les données de ses esclaves à jour. 30 Lorsqu'un dispositif informatique 4 rencontre une défaillance, plusieurs cas sont possibles pour un morceau donné : a. le dispositif informatique 4 contenait un espace non affecté, 3050553 15 b. le dispositif informatique 4 contenait un espace esclave de tolérance, c. le dispositif informatique 4 contenait un espace esclave critique, d. le dispositif informatique 4 contenait l'espace maître. 5 Dans le cas a., rien ne se passe, puisque cet événement est neutre par rapport à l'intégrité des données. Dans le cas b., plusieurs solutions peuvent être mises en oeuvre. Une première solution consiste, si aucun autre morceau n'est impacté par un cas c. ou d., à attendre pour voir si 10 le dispositif informatique 4 recouvre son état, afin d'éviter des échanges de données inutiles. Une autre solution est que l'espace maître accède à une table interne au dispositif informatique 4 qui le reçoit comprenant les rangs des espaces esclaves et détermine l'espace esclave accessible de rang le plus faible pour le morceau donné. Ensuite, l'espace maître organise la réplication de ses données sur cet espace esclave. 15 Selon une troisième solution, l'espace maître appelle l'allocateur 6 qui maintient la table des dispositifs informatiques 4 actifs et indique à l'espace maître le nouvel espace esclave pour organiser la réplication des données. Dans le cas c., deux solutions peuvent être mises en oeuvre. Selon une première 20 solution, l'espace maître accède à une table interne au dispositif informatique 4 qui le reçoit comprenant les rangs des espaces esclaves et détermine l'espace esclave accessible de rang le plus faible pour le morceau donné. Ensuite, l'espace maître organise la réplication de ses données sur cet espace esclave. Selon la deuxième solution, l'espace maître appelle l'allocateur 6 qui maintient la table des dispositifs 25 informatiques 4 actifs et indique à l'espace maître le nouvel espace esclave pour organiser la réplication des données. Dans le cas où aucun espace esclave n'est disponible pour répliquer les données de l'espace maître, le morceau donné est désactivé jusqu'à ce que r espaces esclaves critiques soient à nouveau à jour. 30 Dans le cas d., l'allocateur 6 choisit l'esclave maître parmi les espaces associés au morceau donné dont il est acquis que leurs données sont à jour en désignant celui qui présente le rang le plus faible, et les espaces esclaves se voient réattribuer leur rôle 3050553 16 (espace esclave critique ou espace esclave de tolérance) de telle sorte que la somme des rangs des espaces esclaves sélectionnés est minimale. Pour cela, les solutions décrites en rapport avec les cas b. et c. sont mises en oeuvre. 5 Les dispositifs informatiques 4 sont en outre agencés pour déclarer leur état régulièrement à l'allocateur 6. Ainsi, pour un morceau donné, dès qu'un espace esclave est à jour en termes de réplication de données et qu'il présente un rang inférieur à l'espace maître, l'allocateur 6 déclenche une opération similaire au cas d. afin d'assurer que l'espace maître pour le morceau donné est celui de rang le plus faible, et que les 10 espaces esclaves sont sélectionnés pour minimiser la somme de leurs rangs. Ainsi, les opérations d'écriture, mise à jour et/ou réplication pour chacun des espaces peuvent être réalisées sans faire appel à l'allocateur 6 dans la plupart des cas, ce dernier pouvant n'être sollicité que lorsqu'un espace maître est sur un dispositif informatique 4 15 connaissant une défaillance. Un certain nombre de variantes pourra être envisagé au vu de la figure 2, par exemple en variant l'opération 220 pour changer le premier dispositif informatique 4 qui est testé. Avantageusement, de telles variantes dépendront de l'indice de morceau k 20 courant. Par exemple, l'allocateur 6 pourrait commencer par tirer H*H-k couples (i,j) où i est choisi entre 0 et H, et j entre 1 et H-k, puis, pour chaque série de H*(H-k) morceaux, un couple est tiré au hasard, chaque couple étant tiré une fois, et les rang sont affectés selon 25 une séquence du type : - rang 0 affecté à l'espace de l'hôte d'indice i, - rangs suivants affectés en répétant la formule h = (h+j) modulo H (à la place de l'opération 270, en évitant les espaces auxquels un rang a déjà été affecté comme avec l'opération 240). 30 Selon cette variante, les mêmes séquences d'affectation de rangs seront réalisées qu'avec la figure 5, mais dans un ordre dépendant de l'ordre de tirage des couples (i,j). 3050553 17 D'autres variantes pourront être envisagées dès lors qu'elles permettent d'obtenir une répartition équilibrée et cyclique sur H*(H-j) morceaux. REVENDICATIONS1. Système de base de données, comprenant une pluralité de dispositifs informatiques (4) et un allocateur (6) agencé pour répartir les données de la base de données sur les dispositifs informatiques (4), caractérisé en ce que les dispositifs informatiques (4) sont chacun désignés par un indice d'hôte et comprennent chacun une mémoire vive, en ce que l' allocateur (6) est agencé : - pour organiser une pluralité d'espaces indexés sur chaque mémoire vive, et pour organiser une partie au moins des données de la base de données en morceaux ayant un indice de morceau, - pour définir une pluralité de séquences distinctes entre elles comprenant chacune une pluralité de couples dont le nombre est égal au nombre de dispositifs informatiques (4), chaque couple associant une valeur de rang unique et un indice d'hôte, - pour maintenir une liste des dispositifs informatiques (4) fonctionnels au cours du temps, pour associer chaque morceau à une séquence de la pluralité de séquences, sur la base de la liste des dispositifs informatiques (4) fonctionnels, de sorte que, pour deux morceaux ayant respectivement un premier indice de morceau et un deuxième indice de morceau tels que la différence entre le premier indice de morceau et le deuxième indice de morceau est égale au nombre de séquences de la pluralité de séquences, une séquence donnée de la pluralité de séquences est associée à un unique morceau dont l'indice de morceau est compris entre le premier indice de morceau et le deuxième indice de morceau, - pour définir, pour un morceau d'indice de morceau donné, parmi la liste des dispositifs informatiques (4) fonctionnels, un espace maître sur le dispositif informatique (4) dont l'indice d'hôte est associé au rang le plus bas dans la séquence associée au morceau donné, l'espace maître étant choisi sur le dispositif informatique (4) comme l'espace dont l'indice correspond à l'indice de morceau donné, 3050553 19 - pour définir, pour un morceau d'indice de morceau donné, parmi la liste des dispositifs informatiques (4) fonctionnels, une pluralité d'espaces esclaves, choisis sur des dispositif informatiques (4) de telle manière que la somme de rangs associés aux indices d'hôtes de ces dispositifs informatiques (4) dans la 5 séquence associée au morceau donné est minimale, chaque espace esclave étant choisi sur le dispositif informatique (4) respectif comme l'espace dont l'indice correspond à l'indice de morceau donné, et en ce que les dispositifs informatiques (4) sont en outre agencés de telle sorte qu'un dispositif informatique (4) qui reçoit un espace maître réplique les 10 données du morceau associé sur les espaces esclaves correspondants. 2. Système selon la revendication 1, dans lequel l'allocateur (6) est agencé pour définir un nombre d'espaces esclaves inférieur au nombre de dispositifs informatiques (4) moins un. 15 3. Système selon l'une des revendications précédentes, dans lequel l'allocateur (6) est agencé pour définir, parmi la pluralité d'espaces esclaves associés à un morceau donné, un ensemble d'espaces esclaves critiques et un ensemble d'espaces esclaves de tolérance, et dans lequel l'espace maître associé à un 20 morceau donné est agencé pour confirmer l'écriture d'une donnée relative au morceau donné uniquement lorsque cette donnée a été répliquée sur l'ensemble d'espaces esclaves critiques du morceau donné. 4. Système selon la revendication 1, dans lequel l'allocateur (6) est agencé pour 25 définir la pluralité de séquences distinctes et pour associer chaque morceau à une séquence de la pluralité de séquences en initialisant, pour chaque indice de morceau, un indice d'hôte avec l'indice de morceau modulo le nombre de dispositifs informatiques, et en répétant autant de fois que le nombre de dispositifs informatiques une séquence dans laquelle : 30 - si l'indice d'hôte est déjà associé à l'indice de morceau, redéfinir l'indice d'hôte en lui ajoutant un et en réalisant sur le nombre obtenu une 3050553 20 opération modulo le nombre de dispositifs informatiques (4), jusqu'à trouver un indice d'hôte qui n'est pas déjà associé à l'indice de morceau, - l'indice de morceau est associé à l'indice d'hôte, et à un rang dont la valeur est tirée de l'itération de la séquence, 5 - l'indice d'hôte est redéfini en lui ajoutant la valeur un ainsi que l'indice de morceau modulo le résultat de la soustraction d'un entier naturel au nombre de dispositifs informatiques, et en réalisant sur le résultat de ces additions une opération modulo le nombre de dispositifs informatiques (4), ledit entier naturel étant le même pour toutes les 10 répétitions de la séquence et choisi de sorte que le nombre de dispositifs informatiques (4) et le nombre de dispositifs informatiques (4) moins ledit entier naturel sont premiers entre eux. 5. Système selon l'une des revendications 1 à 4, dans lequel l'allocateur (6) est 15 agencé pour définir la pluralité de séquences distinctes sur la base d'une pluralité de couples distincts associant un indice d'initialisation compris entre 0 et le nombre de dispositifs informatiques (4), et un indice de parcours compris entre 1 et le nombre de dispositifs informatiques (4) moins un, chaque séquence distincte étant générée initialisant un indice d'hôte avec l'indice d'initialisation, 20 et en répétant autant de fois que le nombre de dispositifs informatiques (4) une séquence dans laquelle : - si l'indice d'hôte est déjà associé à l'indice de morceau, redéfinir l'indice d'hôte en lui ajoutant un et en réalisant sur le nombre obtenu une opération modulo le nombre de dispositifs informatiques (4), jusqu'à trouver un 25 indice d'hôte qui n'est pas déjà associé à un rang, - l'indice d'hôte est associé à un rang dont la valeur est tirée de l'itération de la séquence, - l'indice d'hôte est redéfini en lui ajoutant la valeur de l'indice de parcours, et en réalisant sur le résultat de cette addition une opération modulo le 30 nombre de dispositifs informatiques (4). 3050553 21 6. Procédé de gestion de base de données, comprenant la répartition des données de la base de données sur une pluralité de dispositifs informatiques (4), comprenant les opérations suivantes : (a) associer un indice d'hôte à chaque dispositif informatique (4), 5 (b) organiser une pluralité d'espaces indexés sur la mémoire vive de chaque dispositif informatique (4), (c) organiser une partie au moins des données de la base de données en morceaux ayant un indice de morceau, (d) définir une pluralité de séquences distinctes entre elles comprenant chacune 10 une pluralité de couples dont le nombre est égal au nombre de dispositifs informatiques (4), chaque couple associant une valeur de rang unique et un indice d'hôte, (e) associer chaque morceau à une séquence de la pluralité de séquences, sur la base de la liste des dispositifs informatiques (4) fonctionnels, de sorte que, pour 15 deux morceaux ayant respectivement un premier indice de morceau et un deuxième indice de morceau tels que la différence entre le premier indice de morceau et le deuxième indice de morceau est égale au nombre de séquences de la pluralité de séquences, une séquence donnée de la pluralité de séquences est associée à un unique morceau dont l'indice de morceau est compris entre le 20 premier indice de morceau et le deuxième indice de morceau, en (el) définissant, pour un morceau d'indice de morceau donné, parmi la liste des dispositifs informatiques (4) fonctionnels, un espace maître sur le dispositif informatique (4) dont l'indice d'hôte est associé au rang le plus bas dans la séquence associée au morceau donné, l'espace maître 25 étant choisi sur le dispositif informatique (4) comme l'espace dont l'indice correspond à l'indice de morceau donné, (e2) définissant, pour un morceau d'indice de morceau donné, parmi la liste des dispositifs informatiques (4) fonctionnels, une pluralité d'espaces esclaves, choisis sur des dispositif informatiques (4) de telle 30 manière que la somme de rangs associés aux indices d'hôtes de ces dispositifs informatiques (4) dans la séquence associée au morceau donné est minimale, chaque espace esclave étant choisi sur le dispositif 3050553 22 informatique (4) respectif comme l'espace dont l'indice correspond à l'indice de morceau donné, (f) stocker les données de chaque morceau donné sur l'espace maître qui lui est associé, 5 (g) répliquer les données stockées sur les espaces maîtres sur les espaces esclaves correspondants. 7. Procédé selon la revendication 6, dans lequel l'opération (e2) comprend la définition d'un nombre d'espaces esclaves inférieur au nombre de dispositifs 10 informatiques (4) moins un. 8. Procédé selon l'une des revendications 6 et 7, dans lequel l'opération (e2) comprend la définition, parmi la pluralité d'espaces esclaves associés à un morceau donné, un ensemble d'espaces esclaves critiques et un ensemble 15 d'espaces esclaves de tolérance, et comprenant en outre l'opération (h) confirmer l'écriture d'une donnée relative à un morceau donné uniquement lorsque l'espace maître associé au morceau donné a répliqué cette donnée sur l'ensemble d'espaces esclaves critiques du morceau donné. 20 9. Procédé selon l'une des revendications 6 à 8, dans lequel les opérations (d) et (e) sont réalisées : - en initialisant, pour chaque indice de morceau, un indice d'hôte avec l'indice de morceau modulo le nombre de dispositifs informatiques, et - en répétant autant de fois que le nombre de dispositifs informatiques une 25 séquence dans laquelle : - si l'indice d'hôte est déjà associé à l'indice de morceau, redéfinir l'indice d'hôte en lui ajoutant un et en réalisant sur le nombre obtenu une opération modulo le nombre de dispositifs informatiques (4), jusqu'à trouver un indice d'hôte qui n'est pas déjà associé à l'indice de morceau, 30 - l'indice de morceau est associé à l'indice d'hôte, et à un rang dont la valeur est tirée de l'itération de la séquence, 3050553 23 - l'indice d'hôte est redéfini en lui ajoutant la valeur un ainsi que l'indice de morceau modulo le résultat de la soustraction d'un entier naturel au nombre de dispositifs informatiques, et en réalisant sur le résultat de ces additions une opération modulo le nombre de dispositifs 5 informatiques (4), ledit entier naturel étant le même pour toutes les répétitions de la séquence et choisi de sorte que le nombre de dispositifs informatiques (4) et le nombre de dispositifs informatiques (4) moins ledit entier naturel sont premiers entre eux. 10 10. Procédé selon l'une des revendications 6 à 8, dans lequel l'opération (d) comprend : (dl) définir une pluralité de couples distincts associant un indice d'initialisation compris entre 0 et le nombre de dispositifs informatiques (4), et un indice de parcours compris entre 1 et le nombre de dispositifs informatiques (4) moins un, 15 (d2) pour chaque couple distinct, initialiser un indice d'hôte avec l'indice d'initialisation, et répéter autant de fois que le nombre de dispositifs informatiques les opérations suivantes : (d21) si l'indice d'hôte est déjà associé à l'indice de morceau, redéfinir l'indice d'hôte en lui ajoutant un et en réalisant sur le nombre obtenu une 20 opération modulo le nombre de dispositifs informatiques (4), jusqu'à trouver un indice d'hôte qui n'est pas déjà associé à un rang, (d22) associer l'indice d'hôte à un rang dont la valeur est tirée du nombre de répétitions de l'opération (d2) déjà réalisées pour le couple distinct courant, 25 (d23) redéfinir l'indice d'hôte en lui ajoutant la valeur de l'indice de parcours, et en réalisant sur le résultat de cette addition une opération modulo le nombre de dispositifs informatiques (4). 11. Produit de programme d'ordinateur comprenant des portions de code de 30 programme pour mettre en oeuvre le dispositif selon l'une des revendications 1 à 5 ou le procédé selon l'une des revendications 6 à 10 lorsque ledit programme est exécuté sur un ordinateur.