Besoin d'un coup de main : comment stocker des fragments petits, nombreux, éparpillés

[Zero]

Salut les devs,

J'ai un problème technique, dont je ne connais pas la solution optimale.

C'est pour créer un genre d'énorme automate cellulaire à 1 dimension. Chaque cellule peut contenir soit rien soit 0 soit 1. Je voudrais que ce soit vraiment énorme, par exemple, capable d'utiliser toute la place disponible dans un disque dur externe. Je voudrais ne pas stocker les cellules vides. Je voudrais que les adresses des cellules soient arbitrairement grandes (bignum). En d'autres termes, c'est un key-value store, où les keys sont des strings potentiellement infinies, et où les values sont un octet (ça suffira largement). Chaud non ?

Comment vous feriez ? Je suppose qu'un SGBD serait une bonne idée, mais lequel ?

Je ne sais pas trop si ma description est claire ? si ce n'est pas le cas, merci de me le faire savoir !

C'est pour faire ce que vous pouvez voir ici, mais à plus grande échelle.

PS : la vitesse n'est pas forcément une priorité

---

PPS :

Je suis en train de regarder BerkeleyDB, et je vois sur cette page descriptive que les clefs et valeurs semblent être de longueur arbitraires (format DBT). Est-ce que je me trompe, ou vous comprenez comme moi ? D'autre part, il semble que BerkerleyDB utilise le storage sur disque, donc ça a l'air de convenir, à vue de nèze. En même temps, je me dis qu'il y aura beaucoup plus d'espace utilisé pour stocker les adresses que pour stocker les données elles-mêmes, donc ce ne serait pas efficace du tout. A moins peut-être de faire un système de pages de 1 giga par exemple. On charge une page en mémoire, on travaille dessus, on passe à la suivante, ...etc.

[Xenos]

Salut,
J'ai compris l'idée de l'automate, mais pas les conditions...

Si c'est un automate géant que tu veux faire, avec des milliers de milliards de cellules, le plus simple me semble être d'utiliser directement le disque dur. Supposons que ce soit dans un plan 2D de 1M x 1M de cellules, la cellule X Y est alors le bit X*1M+Y dans un fichier du disque dur. Un SGDB me semble alors pas approprié.

Un système à clefs, quel qu'il soit, sera carrément plus lourd et ne se justifierai que si l'espace de l'automate est quasi vide (ie: si 1 cellule sur 10k est vivante [1] et les autres mortes [0] alors, ok, on doit pouvoir gagner de l'espace ainsi). Un SGDB est alors envisageable, mais ça me semble plus lourd à l'exécution, et l'hypothèse de "mes cellules sont quasi toutes mortes" va devoir être démontrée.

Donc, cela dépend du contexte de l'automate et de sa taille.

[Zero]

Oui c'est ce que je voulais dire par "éparpillées", je pensais à "sparse array"... Tu peux avoir un groupe de cellules actives près de l'adresse 0, et un autre petit groupe de cellules actives à l'adresse 1000000000000000000000000 par exemple, et rien entre les deux.

C'est un automate en 1 dimension, une simple ligne si tu préfères, pas un plan en 2D.

Mais en fait, j'ai fini par penser un peu comme toi, travailler directement sur le disque dur. Par forcément tout dans un même fichier, mais plutôt dans des dossiers et sous-dossiers portant des noms composés de 4 bits genre "1101", et en s'enfonçant en profondeur dans la hiérarchie, on concatène les noms de dossiers pour obtenir l'adresse. Dans le dossier final, on trouve 16 fichiers nommés eux aussi par 4 bits, qui contiennent chacun 16 cellules.

Après ça peut être 8 bits au lieu de 4 mais tu vois l'idée...

Pour être vraiment optimisé, il faudrait pouvoir gérer un genre de compression, et là ça devient beaucoup plus complexe. Ce qui se passe souvent, c'est que toute une zone se retrouve couverte d'un motif répétitif, donc en termes de stockage, c'est dommage de ne pas s'en servir pour compresser énormément les données. D'un autre côté, je ne ressens pas trop le besoin de troquer de la vitesse contre de la mémoire, parce que la mémoire, il y en a à foison sur le disque dur, alors que la vitesse... rien qu'avec quelques Go à traiter, une seule itération pourrait prendre des heures, donc bon pas la peine d'en rajouter.


L'objectif de tout ça, c'est de créer un milieu programmable où des formes de vie numérique pourraient s'épanouir
Bon ça c'est le rêve derrière le projet bien sûr...

[Zero]

Je vais quand même vous raconter un peu de quoi il retourne plus précisément.

Imaginez un système dans lequel il n'y a qu'une seule fonction. C'est une fonction de copie, qui prend 3  arguments :
- l'adresse de la zone à copier,
- la taille de la zone à copier,
- et l'adresse à laquelle coller la zone copiée.

Cette fonction de copie a un autre effet : elle définit l'adresse où le système trouvera les arguments pour une copie à effectuer au prochain cycle. La fonction prend donc un 4ème argument :
- l'adresse des arguments d'une fonction de copie à exécuter au prochain cycle.

Voilà, il y a beaucoup de variantes de cette idée. C'est un processeur One-Instruction-Set, il y en a d'autres, mais j'aime celui-ci pour sa simplicité. Et c'est Turing-complet, c'est à dire suffisant pour réaliser n'importe quel calcul ou simulation, en théorie (parce qu'en pratique, ben c'est pas pratique du tout en fait).

Là dessus je suis parti dans un délire à la Matrix, avec des entités super évoluées qui vivraient leur vie dans un tel monde. Limite, ça pourrait se jouer comme on joue à Eve Online, sauf qu'on n'est pas dans l'espace mais dans un univers numérique. En fait je pense que pour faire un jeu de ce type, il ne faudrait pas vraiment faire la simulation exacte des opérations de copie une par une et tout, mais par contre il faudrait avoir une idée précise de comment c'est censé être implémenté, pour pouvoir créer des scénarios qui tiennent la route. Je pense que les entités évoluées elles-mêmes (les joueurs, donc) ne sauraient peut-être pas forcément de quoi est fait leur monde. Elles n'auraient peut-être pas encore inventé le super microscope qui permet d'examiner une cellule précise. Mais par contre il y aurait des villes, des véhicules, et beaucoup de choses qui font écho à ce que nous connaissons sur terre.

Même en imaginant que la surface entière d'une planète est couverte de matériel électronique qui fait fonctionner une telle simulation, un tel univers, il y a quand même des règles à respecter. Par exemple, l'information prend nécessairement du temps à se déplacer, même si elle se déplace à la vitesse de la lumière. On est donc obligé de supposer un système de "partitions" de l'univers : on peut tout à fait passer d'une partition à l'autre, c'est à dire faire des copies depuis et vers d'autres partitions, mais il y a une question de synchronisation à prendre en compte. Chaque partition a son propre rythme, sa cadence, qui peut légèrement différer d'autres partitions "voisines", ce qui suppose des queues pour les copies. Transposé dans l'univers que nous connaissons, ça correspond à groupe d'ordinateurs qui travaillent en peer to peer, en faisant principalement trois choses  : faire tourner la simulation, émettre des ordres de copie vers d'autres ordinateurs du réseau, et traiter les ordres de copie reçus.

Les adresses sont potentiellement infinies, et exprimées de façon relative, en positif ou négatif, pour exprimer un déplacement vers des adresses plus "hautes" ou plus "basses". Chaque partition est donc "au-dessus" d'une partition voisine, en "en dessous" d'une autre partition voisine.

Ce n'est pas du binaire, c'est du ternaire : chaque cellule peut contenir un 1, un 0, ou un vide. Les 1 et les 0 servent à représenter les adresses, les vides servent à distinguer les adresses.

Enfin bref.

[Xenos]

Si tu veux faire du ternaire, en effet, ca marche plus d'utiliser directement les bits sur disque (ou tu utilises 2 bits par ternaire, mais tu perds un peu de "place")

Comment sais-tu d'avance que tes cellules vivantes seront rares?
Sachant qu'il te faudra, au strict minimum, 32 ou 64 bits d'adressage, ça peut n'être rentable que si tu as moins de 1/64e de bits actifs. Et encore, même là, il faudra que les adressages soit ordonnées si tu veux chercher facilement & rapidement là dedans (sinon, en gros, tu as le processeur qui va se pallucher chaque adresse une à une jusqu'à trouver celle que tu cherches). Ce dernier point pouvant être ignoré si tu process de toute façon toutes les cellules, dans un ordre indéterminé/osef, mais apparemment, c'est pas le cas si je comprends bien: tu émules ici une machine de turing avec une seule tête de lecture.*

Après, si tu comptes les faire en jeuweb, je ne pense pas que tu puisses créer un fichier de 2To sur le disque du joueur x)

Faire des sous-fichiers/sous-dossiers, je pense que ce n'est pas une bonne idée, vu que tu as dit qu'il y aurait des milliards de bits dans ton automate. Ca va encombrer inutilement les choses, sans améliorer les perfs (par rapport à un seul fichier d'un bloc dans lequel tu accèdes au N-eme bit directement, ou au 2xNeme bit si jamais tu veux faire du ternaire). Mais forcément, ca demandera aux joueurs d'accepter qu'un jeu du genre prenne 2To sur leur disque x)

* Ceci est à matériel constant: entre un accès disque au N-eme bit, ou un accès par adressage 64bits dans la RAM, la RAM sera très probablement plus rapide, même si'lo faut checker 10.000 adresses (mais là, faudrait savoir si vraiment tu as 1/100k-eme des bits actifs, ou si c'est juste du "je pense qu'au feeling ça sera ça"

[Zero]

D'abord merci de te pencher sur mon obscur ... truc.

Je partais du principe que les cellules vivantes seraient "rares" (vraiment entre guillemets) parce que l'espace est infini, mais à bien y réfléchir, c'est pas un critère. Après tout, au bout d'un temps infini, même l'espace infini peut être plein. Mais bon, là on est un peu dans le philosophique donc pas forcément hyper intéressant.

Partons sur du concret.

L'idée d'utiliser des dossiers et sous-dossiers consistait en fait à faire un arbre ; en gros si je ne trouve pas de sous-dossier correspondant à l'adresse que je recherche, je peux arrêter ma traversée parce que je sais qu'à cette adresse, il n'y a que du vide. Plus on fait des gros sous-dossier, plus on va vite, mais plus on gaspille de place. A l'extrême inverse, plus on fait des petits sous-dossiers, plus ça rame, mais par contre les zones vides ne prennent pas de place sur le disque parce qu'elles ne sont tout simplement pas représentées, c'est leur absence qui indique leur valeur.

De toute façon ça reste une procédure très lente effectivement, parce que comme tu dis, le processeur doit se farcir toutes les adresses une par une pour trouver les arguments d'une fonction. En fait je vais être plus précis pour qu'on sache bien de quoi on parle.

On peut représenter l'univers avec une string contenant des caractères espace, 1 et 0. Un 1 entouré d'espace est interprété comme un opcode (l'unique opcode). Une commande complète pourrait être
"   1  0100           110    11000             11  "

Le premier bit est le signe, on est en little-endian, donc on a comme arguments -4, +2, +8, +1, ce qui veut dire "copie la zone commençant à l'adresse -4 et de taille 2, colle-la à l'adresse +8 et créé un 1 à l'adresse +1". Le premier 1 entouré d'espace (l'opcode) est transformé en espace après exécution.

Le système parcourt la mémoire de gauche à droite et réagit à chaque fois qu'il trouve un 1 isolé. Cette description, c'est celle d'une variante du système, j'ai fait beaucoup de variantes en fait. Mais les problèmes se posent toujours un peu à chaque fois.

A partir de là, il y a deux types de jeuweb qu'on peut faire : un jeu "roleplay", et un jeu "automate cellulaire".

Dans le jeu "roleplay", il s'agit d'incarner une entité vivant dans cet univers. Ce qu'on y fait, je ne sais pas encore ce que ça peut être, mais en tout cas le but n'est pas de simuler réellement l'automate cellulaire, mais plutôt de simuler l'univers directement dans sa version "haut niveau", c'est à dire que les joueur évolue dans un monde d'objets, d'entités comme lui, de véhicules, de cités, ...etc. Commerce, traquenards, guerres, la totale. C'est un jeu classique, pas de technologie particulière, mais on a besoin de connaître les propriétés exactes du milieu pour que l'histoire soit crédible (par exemple, est-il possible, avec le véhicule adapté, de se "téléporter" à n'importe quel endroit de l'univers ? si oui, doit-on procéder par "sauts" successifs ? ...etc).

Dans le jeu "automate cellulaire" qu'on pourrait en faire, il s'agit bien de simuler l'univers et donc plutôt de "jouer à dieu" en quelque sorte, c'est à dire élever des entités, les faire évoluer, les partager, ...etc. Dans ce cas, idéalement on aurait un univers réel partagé, sans doute hébergé sur le serveur, soit en flat file soit dans une MySQL ou similaire... ou alors, autre option plus moderne, un réseau peer2peer où chaque joueur a un nœud qui représente un segment de l'univers (qui ne tourne que quand le joueur est connecté). Il faut alors faire passer les infos en lecture / écriture d'un nœud à l'autre et là c'est pas de la tartiflette !

Donc pour résumer,
- deux options pour un projet Jeuweb basé là-dessus,
- je me trompais en disant que la plupart des cellules étaient vides (c'est pas forcément le cas),
- dans tous les cas, il faut une grosse connectivité entre les postes des joueurs,
- les "règles" d'évolution de l'univers sont loin d'être figées, elles me posent notamment des problèmes de stabilité (pour que des entités évoluées apparaissent, les copies de taille énorme à distance énorme posent un problème de design mal foutu à vrai dire, je suis en train de bosser sur la question).

[Xenos]

> Après tout, au bout d'un temps infini, même l'espace infini peut être plein. Mais bon, là on est un peu dans le philosophique donc pas forcément hyper intéressant.

Nope, ce n'est pas de la philosophie Comme ton espace informatique ne sera de toute façon pas "infini", on peut raisonner sur un espace "très grand" (arbitrairement grand, mais fini). Dans ce cas, imaginons un automate très simple disant: une cellule est vivante (1) si elle est morte (0) et si au moins une de ses voisines est vivante. Alors, avec un seul 1 dans ton espace fini "très grand", l'entièreté de cet espace finira couvert de 1

Je ne pense pas que ce soit une bonne idée de garder tes "dossiers": tu perds la possibilité éventuellement de faire un prorotype en RAM, tu perds probablement en place & perf (parce qu'un dossier, c'st une forme d'index dans un système de fichiers sur le disque, or, ici, tu n'as pas besoin d'un tel index au final). Si tu vaux faire cela, je pencherai plutôt pour un index dans le fichier initial. Par exemple, les 1M de premiers bits seraient l'index. L'index en place N contient un 1 si au moins 1 cellule du N-eme groupe de 1G de bits du fichier est un 1. Tu peux alors gagner quelques giga, mais si et seulement si ces blocs sont vides. Ne sachant pas quel automate du définit, je ne sais pas si c'est le cas (j'en doute perso, car alors, l'automate a pas grand intéret?!)

Si tu veux réduire la taille du fichier, je pencherai plutôt pour essayer d'utiliser directement un filesystem compressé (genre, sur windows, tu peux flagger un fichier comme "compressé" sur le disque, et il apparaissait [sous W7] en vert). Il se peut que l'implé de cette compression soit alors bien plus efficace que tout bricolage de dossiers que tu feras (ou d'index en début de fichier).

Donc pour moi, fais simple: un fichier, où 1 bit = 1 cellule de ton automate. Je ne suis en revanche pas fan du tout de ton système "ternaire" (car c'est pas le principe usuel des automates, en tous cas, pas à ma connaissance). Je remplacerai donc les espaces par des 0 et une règle supplémentaire basée sur les 1: on remplace les espaces par des "0", on applique la règle "dès qu'on croise un 1, on entre dans une commande; quand on est dans une commande, les 4x5 prochains bits définissent les paramètres, avec le 1er bit le signe et les 4 suivants la valeur" (par exemple)

Ca te simplifiera énormément le codage et la gestion de l'automate

[Zero]

Au cours de la journée je vais essayer petit à petit de décrire ici les specs de la bête, dans l'état actuel. Sinon pour les impatients, cette page contient déjà un genre de log de l'évolution de l'idée, et il y a une mini-démo ici.

Alors.

Je suis pas particulièrement attaché à l'idée des dossiers, et puis je pense que de toute façon, en faisant un automate vraiment énorme, ce ne serait pas intéressant parce que l'utilisateur attendrait 3 heures pour voir bouger un peu les choses. Donc je laisse tomber cette idée.

Par rapport au système ternaire, ce n'est pas inhabituel du tout d'avoir des cellules pouvant prendre plus de 2 états dans un automate. Par exemple il y en a un assez célèbre (de Von Neumann) qui accepte 29 états. Mais là je pars sur 3 états pour représenter le Yin, le Yang, et le Vide Médian. Un petit côté spirituel.

Dans l'état actuel, il y a maintenant deux fonctions presque similaires. Les deux sont des fonctions de copie / saut, comme décrit dans le post plus haut. Celle qui est activée par un 0 utilise un adressage absolu (relatif au début du secteur), tandis que celle qui est activée par un 1 utilise un adressage relatif (relatif à l'adresse de l'opcode exécutant).

La machine est partitionnée en secteurs, qui sont des segments de mémoire juxtaposés. Les secteurs s'exécutent en parallèle, potentiellement de façon distribuée sur plusieurs machines, et échangent des demandes de transfert d'information. Les demandes sont non-bloquantes, ce qui permet au système de fonctionner malgré les lags, segments inaccessibles (déconnexions), ...etc.

La syntaxe exacte des demandes reste à définir de façon précise. D'une manière générale, ce sont toujours des demandes d'écritures, c'est à dire qu'on demande à une section décrire quelque chose quelque part. Le "quelque chose" qu'il faut écrire est défini soit par l'emplacement où se trouvent les données et leur taille, soit par les données elles-mêmes. Par exemple, on pourrait avoir :
- write( location: 15, size: 10, target: -266 )
- write( content: " 0 11 1 000 1", target: 552 )
- ...etc.

L'attitude à adopter en fonction de la demande est la suivante :

- Si on connaît les données à écrire :

• si c'est ici, on les écrit
  
• si c'est dans un autre segment, on transfert la demande à ce segment
  

- Si on connaît l'adresse des données à écrire :

• si c'est ici, on remplace l'adresse et la taille par les données elles-mêmes et on traite la demande
  
• si c'est dans un autre segment, on transfert la demande à ce segment
  

Voilà pour le moment, je ne sais pas si c'est très clair ni très intéressant...

-----

J'ai eu une autre idée. Puisque l'univers est segmenté, le contenu de chaque segment sera sans doute une partie d'une entité ou d'une organisation couvrant de nombreux segments adjacents. Pour proposer au joueur une représentation visuelle des contenus, on peut s'inspirer de la façon dont l'ADN est "lu" par une tête de lecture qui "tricote" les molécules en avançant. Une certaine façon de faire (qui reste à déterminer) pourrait permettre de générer des représentations en 3D, "tricotées" de la même façon, dans un style "Tron" des années 80. Le contenu de chaque segment serait ainsi représenté en 3D, et potentiellement reconnaissable par l'utilisateur.

Niveau scénario, on peut s'inspirer de la richesse du gnosticisme.

[Zero]

Enfin bref, pour en revenir à nos moutons, et à une question technique précise qui soit dans le thème de notre cher petit forum bien aimé, comment faire pour stocker ces données.

Une contrainte d'abord : les calculs se font probablement chez le client, parce qu'il y en a beaucoup, et parce que je ne vois pas un de mes petits hébergeurs gratuits apprécier de gros traitements en PHP, que de toute façon j'aurais bien du mal à coder vu que je suis une pine d’huître en PHP. Je pars du principe que le nombre de segments est à peu près proportionnel au nombre de joueurs, donc il semble naturel de faire les calculs client-side. Entre parenthèses, ça soulève la question de la triche.

Ensuite il y a la mise à disposition de ces données. Imaginons des segments de quelques dizaines de Ko, je voyais bien des petits fichiers. Encore une fois, l'idée c'est un hébergeur gratuit, donc soit flat-file mais du coup il faut des petits fichiers, soit BDD. On n'est pas sur du temps-réel dur, mais quand même il faut un minimum de réactivité, c'est pas du tour par tour. Ou alors tour par tour mais tous en même temps, et par exemple 1 minute par tour.

--------


En fait je pense que c'est juste pas possible. Dans les jeux on simule les choses, là finalement je voulais réellement faire tous ces calculs lourds, ça peut pas coller.