J'ai un fichier avec des "trous" dedans et je veux les remplir de données; J'ai aussi besoin de pouvoir libérer l'espace "utilisé" et de faire de l'espace libre.
Je pensais utiliser une bi-carte qui décalage et la longueur. Cependant, je ne suis pas sûr que si c'est la meilleure approche s'il y a des lacunes vraiment minuscules dans le fichier. Un bitmap fonctionnerait mais je ne sais pas comment cela peut être facilement commuté de manière dynamique pour certaines régions d'espace. Peut-être qu'une sorte de radix arbre est la voie à suivre?
Pour ce que ça vaut la peine, je suis au courant de la conception du système de fichiers moderne (ZFS, HFS +, NTFS, XFS, EXT ...) et je trouve leurs solutions malheureusement inadéquates.
Mes objectifs sont d'avoir de très bonnes économies d'espace (d'où la préoccupation des petits fragments). Si je ne me souciais pas de cela, je voudrais juste aller pour deux arbres de spaça ... une sorte de décalage et l'autre triés par longueur avec des liens brisés par décalage. Notez que cela vous donne un journal amorti (N) pour toutes les opérations avec une heure de travail du journal (M) ... Pretty Darn Good ... Mais, comme mentionné précédemment, ne traite pas de problèmes concernant une fragmentation élevée.
4 Réponses :
La solution la plus simple est un Liste libre : Gardez une liste liée des blocs gratuits, réutilisation L'espace libre pour stocker l'adresse du prochain bloc de la liste.
C'est une solution vraiment mauvaise comparée à l'utilisation d'une carte, chaque opération est lente ...
Voulez-vous dire une carte des listes ayant une clé la taille de la taille de «trou» libre? Et si le trou que vous voulez n'est pas disponible? Vous devez numériser le reste de l'arbre pour un trou plus grand que votre demande: c'est O (n).
Une carte triée par décalage est meilleure que cette liste idiote liée. Je peux libérer et ajouter de l'espace dans O (journal n) au lieu d'essayer de conserver une liste liée triée. De plus, je peux parcourir la carte en temps linéaire avec O (log n) espace, un compromis facile à faire ...
@Helen Hunt: Vous n'avez pas besoin de le maintenir trié. C'est une simple file d'attente ou une pile. Regardez comment malloc fonctionne. Je ne dis pas que c'est une bonne solution, mais ce n'est pas aussi mauvais que vous le pensez.
J'ai expédié un logiciel commercial qui fait exactement cela. Dans la dernière itération, nous avons fini par trier des blocs du fichier dans "type" et "index" afin de pouvoir lire ou écrire "le troisième bloc de type FOO". Le fichier a fini par être structuré comme suit:
1) En-tête de fichier. Points sur la liste des types principaux. 2) données. Chaque bloc a une en-tête avec type, index, taille logique et taille rembourrée. 3) Les matrices de tuples (offset, taille) pour chaque type donné. 4) Tableau de (type, décalage, compte) qui garde une trace des types.
Nous l'avons défini pour que chaque bloc était une unité atomique. Vous avez commencé à écrire un nouveau bloc et vous avez terminé d'écrire cela avant de commencer autre chose. Vous pouvez également "définir" le contenu d'un bloc. Démarrage d'un nouveau bloc toujours ajouté à la fin du fichier, vous pouvez donc ajouter autant que vous le souhaitez sans fragmenter le bloc. "Réglage" Un bloc pourrait réutiliser un bloc vide.
Lorsque vous avez ouvert le fichier, nous avons chargé tous les indices en RAM. Lorsque vous avez rougi ou fermé un fichier, nous avons ré-écrit chaque index qui a changé, à la fin du fichier, puis a ré-écrit l'index d'index à la fin du fichier, puis a mis à jour l'en-tête à l'avant. Cela signifie que les modifications apportées au fichier étaient toutes atomiques - soit que vous vous engagez au point où l'en-tête est mis à jour ou que vous ne le faites pas. (Certains systèmes utilisent deux copies de l'en-tête 8 kb à l'écart pour préserver les en-têtes, même si un secteur de disque va mal; nous ne l'avons pas prise aussi loin)
L'un des blocs "Types" était "Bloc libre". Lors de la réécriture des indices modifiés et lors du remplacement du contenu d'un bloc, l'ancien espace sur disque a été fusionné dans la liste GRATUITE conservée dans le tableau des blocs gratuits. Des blocs gratuits adjacents ont été fusionnés dans un seul bloc plus grand. Les blocs gratuits ont été réutilisés lorsque vous "définissez le contenu" ou pour les indices de bloc de type mis à jour, mais pas pour l'indice d'index, qui a toujours été écrit en dernier.
Étant donné que les indices ont toujours été maintenus en mémoire, travailler avec un fichier ouvert était vraiment rapide - généralement une seule lecture pour obtenir les données d'un seul bloc (ou obtenir une poignée à un bloc pour le streaming). L'ouverture et la fermeture étaient un peu plus complexes, car elles devaient charger et rincer les indices. Si cela devient un problème, nous pourrions charger l'indice de type secondaire sur la demande plutôt que vers l'avant pour amortir ce coût, mais cela n'a jamais été un problème pour nous.
Priorité supérieure pour le stockage persistant (sur disque): robustesse! Ne perdez pas de données même si l'ordinateur perd la puissance pendant que vous travaillez avec le fichier! Deuxième priorité pour le stockage sur disque: ne faites pas plus d'E / S que nécessaire! Cherche coûte cher. Sur les lecteurs flash, chaque E / S individuel est coûteux et écrit les écritures sont doublement. Essayez d'aligner et de lotter les E / S. En utilisant quelque chose comme malloc () pour le stockage sur disque est généralement pas grand, parce qu'il fait trop cherche. C'est aussi une raison pour laquelle je ne suis pas comme les fichiers de mémoire mappées beaucoup -. Les gens ont tendance à les traiter comme RAM, puis le modèle I / O devient très cher
Pour la gestion de la mémoire, je suis un fan de l'approche Bibop *, qui est normalement efficace lors de la gestion de la fragmentation.
L'idée est de séparer les données en fonction de leur taille. Cette façon, dans un "sac", vous n'avez que "pages" de petits blocs avec des tailles identiques:
Le sac conserve une simple liste libre des pages disponibles. Chaque page conserve une liste libre des unités de stockage disponibles dans une superposition sur ces unités.
Vous avez besoin d'un index sur la taille de la carte dans son sac correspondant.
Vous avez également besoin d'un traitement spécial pour les demandes "hors de norme" (à savoir les demandes qui demandent une allocation supérieure à la taille de la page).
Ce stockage est extrêmement spatial efficace, en particulier pour les petits objets, car les frais généraux ne sont pas par objet, mais il y a un inconvénient: vous pouvez retrouver des pages "presque vides" qui contiennent encore une ou deux unités de stockage occupées .
Ceci peut être atténué si vous avez la possibilité de "déplacer" les objets existants. Qui permet efficacement de fusionner des pages.
(*) bibop: gros sac de pages
Je recommanderais de créer un système de fichiers personnalisé (peut contenir un fichier bien sûr), basé sur Fuse . Il y a Beaucoup de solutions disponibles pour le fusible Vous pouvez baser sur - Je recommande de choisir des projets non liés mais les plus simples, afin d'apprendre facilement.
Quel algorithme et structure de données à choisir, il approfondit fortement vos besoins. Il peut être: Carte, liste ou fichier divisée en morceaux avec compression / décompression à la volée.
Les structures de données proposées par vous sont de bonnes idées. Comme vous le voyez clairement, il existe un compromis: la fragmentation vs compactage.
D'un côté - Meilleur compactage, fragmentation la plus élevée - SPAY et de nombreux autres types d'arbres.
sur une autre fragmentation la plus basse, la pire liste liée au compactage.
Entre entre il y a des arbres B et autres.
Comme vous, comme vous le comprenez, vous avez déclaré une priorité: sauvegarde de l'espace - tout en prenant soin de la performance.
Je vous recommanderais de la structure de données mixte afin de réaliser toutes les exigences.
Cette solution vous donne une réponse rapide à la demande, tandis que "optimiser" des choses lorsqu'il est utilisé (par exemple, chaque lecture de 10 Mo de données -> défragmentation de 1 Mo) ou dans des moments inactifs.
Il y a beaucoup de compromis dans une conception de systèmes de fichiers (vous faites la partie de l'allocation de l'espace). Je suppose qu'il est préférable de commencer à lire à leur sujet, car les réponses fourniront une image complète.
UM, les systèmes de fichiers ont généralement de très mauvaises représentations d'espace libre ...
@Helen, c'est parce que le système de fichiers habituel n'est pas réglé vers une application spéciale. Vous pouvez concevoir votre politique d'allocation et votre représentation en fonction de vos besoins. N'oubliez pas de commencer vos commentaires avec @Asername, de sorte que l'autre partie soit notifiée.
@belisarius en général, ils sont vraiment inefficaces. Les conceptions des vingt dernières années de conception de systèmes de fichiers ont été rejetées avec les systèmes de fichiers de vache méga-énorme. Remarquez comment les ZFS et les BTRFS n'utilisent pas de bitmaps ... XFS utilise deux arbres B, clairement une structure de données inefficace ... Je comprends la conception des systèmes de fichiers modernes, je veux faire quelque chose qui vaut mieux, pas pire.
@Helen Bon vous avez des informations et des connaissances à jour sur la conception des systèmes de fichiers! Je suggère de mettre à jour votre question avec des antécédents à ce sujet, de sorte que vous ne recevrez pas de réponses naïves et évidentes (telles que mes commentaires précédents!)
Quelle question malheureusement inadéquate! Vous parlez de trous dans les fichiers, mais parlez de systèmes de fichiers. Vous envisagez de créer un système de fichiers par vous-même, qui fonctionne directement avec du matériel sous-jacent? Si oui, quel matériel ciblez-vous (HardDrive / Flash / DVD)? Ou êtes-vous intéressé par un fichier avec des trous sur le dessus d'un système de fichiers existant? Vous dites que vous êtes intéressé à sauver de l'espace, mais je n'ai même pas mentionné les compromis que vous êtes disposé à faire en ce qui concerne l'effet sur les opérations que vous avez l'intention de soutenir. Vous n'avez même pas mentionné quelles opérations vous avez l'intention de soutenir! Bonne chance.
@Moron Le système de fichiers que celui-ci est en cours d'exécution est une variable de confusion que je ne peux pas contrôler et supposera ainsi qu'il est au mieux adversaire dans la raison. De plus, j'ai mentionné quelles opérations je dois appuyer ... alloué et libérant de l'espace dans le fichier ... ce n'est pas un système de fichiers et je ne le décrivais pas comme tel, c'était le fait de Belisarius.
@Helen: "... allouant / libération de l'espace dans le fichier ..." N'a pas suffisamment d'informations. Par exemple, vous auriez probablement besoin d'une certaine opération pour stocker et récupérer des données (lecture / écriture), n'est-ce pas? Veuillez rendre votre question appropriée avant de vous différer sur les systèmes de fichiers actuels ( vous a apporté que BTW) ou des solutions suggérées par des personnes parfaitement correctes (compte tenu de la nature vague de votre question). Fournissez les signatures de l'API que vous envisagez de prendre en charge. Juste, les noms ne suffisent pas non plus.
@Helen Hunt: Votre question a l'air assez similaire à la collection d'allocation / ordures à la mémoire. Vous mentionnez de vous inquiéter de la fragmentation, pouvez-vous «déplacer» l'objet une fois établi ou non?