J'ai environ 750 000 000 fichiers que je dois stocker sur le disque. De plus, c'est que j'ai besoin de pouvoir accéder à ces fichiers au hasard - tout fichier donné à tout moment - dans le temps le plus court possible . Que dois-je faire pour accéder à ces fichiers le plus rapide?
pense à cela comme une table de hachage, seules les clés de hachage sont les noms de fichiers et les valeurs associées sont les données des fichiers.
Un collègue a dit de les organiser dans des répertoires comme celui-ci: si je veux stocker un fichier nommé "foobar.txt" et qu'il est stocké sur le D: lecteur, placez le fichier "D: \ f \ o \ o \ b \ a \ r. \ t \ x \ t ". Il ne pouvait pas expliquer pourquoi c'était une bonne idée cependant. Y a-t-il quelque chose à cette idée?
Des idées?
Le creux de ceci est trouver un fichier. Quel est le moyen le plus rapide de trouver un fichier par nom ouvrir?
EDIT:
EDIT2:
Je veux upvote plusieurs réponses approfondies, qu'ils soient sur place ou non, et ne pouvez pas à cause de mon statut de novembre. Désolé gars!
10 Réponses :
Y a-t-il une relation entre les fichiers individuels? En ce qui concerne les temps d'accès, les dossiers que vous mettez les choses dans lesquels vous n'enfergez pas beaucoup; Les emplacements physiques sur le disque sont ce qui importe.
Cela ressemble à ce que cela va être largement une question de choix de fichiers. Une option à regarder pourrait être ZFS , il est conçu pour les applications à volume élevé.
Vous pouvez également envisager d'utiliser une base de données relationnelle pour ce genre de chose. 750 millions de lignes sont en quelque sorte une base de données de taille moyenne, donc tout SGBD robuste (par exemple, PostgreSQL ) serait capable de le gérer. bien. Vous pouvez également stocker des blobs arbitraires dans la base de données, alors tout ce que vous alliez stocker dans les fichiers sur disque, vous pouvez simplement stocker dans la base de données elle-même.
Mise à jour: Vos informations supplémentaires sont certainement utiles. Compte tenu d'un choix entre FAT32 et NTFS, alors définitivement choisir NTFS. Ne stockez pas trop de fichiers dans un seul répertoire, 100 000 pourraient être une limite supérieure à considérer (bien que vous fassiez expérimenter, il n'y a pas de règle difficile et rapide). La suggestion de votre ami d'un nouveau répertoire pour chaque lettre est probablement trop, vous pourriez envisager de la rompre sur toutes les quatre lettres ou quelque chose du genre. La meilleure valeur à choisir dépend de la forme de votre ensemble de données.
La raison de rompre le nom est une bonne idée, c'est que la performance des systèmes de fichiers diminue, car le nombre de fichiers dans un répertoire augmente. Cela dépend fortement du système de fichiers utilisé, par exemple FAT32, sera horrible avec probablement seulement quelques milliers de fichiers par répertoire. Vous ne voulez pas briser les noms de fichiers trop beaucoup, vous allez donc minimiser le nombre de recherches de répertoires que le système de fichiers devra faire.
La solution de base de données fonctionnera bien mais pourrait ne pas être plus rapide. Je serais très méfiant de deviner sans faire d'abord des tests. Trouver un fichier via un index DB signifie à l'aide d'un arbre de recherche. La solution suggérée d'une implémentation de Trieway basée sur un répertoire permet également d'accéder activement sur un arbre, mais la rompre en lettres signifie que vous n'avez pas autant de contrôle quant à la scission des nœuds. Les modèles dans les noms de fichiers pourraient entraîner un énorme nœud.
Droite, je n'essayerais pas de prétendre qu'une base de données serait plus rapide, mais c'est une autre option à prendre en compte. Cependant, des bases de données sont conçues pour gérer les touches de type chaîne avec des motifs pathologiques arbitraires. :)
Pourquoi ne stocke pas les chemins dans une table de base de données acceptable?
Je suppose qu'il pense à un Structure de données Trie pour créer sur disque où le nœud est un répertoire.
Cela dépend fortement de nombreux facteurs:
Accéder aux fichiers purement au hasard est vraiment coûteux dans les disques traditionnels. Une amélioration significative que vous pouvez obtenir est d'utiliser un lecteur d'état solide.
Si vous pouvez raisonner un modèle d'accès, vous pourriez être en mesure de tirer parti de la localité de référence de placer ces fichiers.
Un autre moyen possible est d'utiliser un système de base de données et de stocker ces fichiers dans la base de données pour tirer parti du mécanisme de mise en cache du système.
mise à jour:
Compte tenu de votre mise à jour, est-ce Possibilité de consolider certains fichiers? Les fichiers 1K ne sont pas très efficaces pour stocker en tant que systèmes de fichiers (FAT32, NTFS) ont une taille de cluster et chaque fichier utilisera de toute façon la taille du cluster, même si elle est inférieure à la taille du cluster. Il existe généralement une limite sur le nombre de fichiers dans chaque dossier, avec des problèmes de performance. Vous pouvez faire un point de repère simple en mettant jusqu'à 10 000 fichiers dans un dossier pour voir la quantité de performance se dégrade.
Si vous êtes prêt à utiliser la structure Trie, je suggérerais d'enquêter sur la distribution des noms de fichiers, puis de les casser dans différents dossiers en fonction de la distribution.
Cela dépend dans une large mesure du système de fichiers que vous allez stocker les fichiers. Les capacités des systèmes de fichiers dans le traitement du grand nombre de fichiers varient considérablement.
Votre collègue suggère essentiellement l'utilisation d'un structure de données Trie . L'utilisation d'une telle structure de répertoires signifierait que, à chaque niveau de répertoire, il n'ya qu'une poignée de fichiers / répertoires à choisir. Cela pourrait aider car le nombre de fichiers dans un répertoire augmente le temps nécessaire pour accéder à l'un d'eux aussi (la différence de temps réelle dépend du type de système de fichiers.)
Cela dit, je n'allais personnellement pas que de nombreux niveaux profond - trois à quatre niveaux doivent être suffisants pour donner les avantages de la performance - la plupart des niveaux après cela aura probablement très des entrées (en supposant que vos noms de fichiers ne soient pas Suivez tous les modèles particuliers.)
En outre, je stockais le fichier lui-même avec son nom entier, cela facilitera également la traversée de cette structure de répertoire manuellement, si nécessaire.
Alors, je stockais foobar.txt comme f / o / o / b / foobar.txt
Tout d'abord, la taille du fichier est très petite. Tout système de fichiers mangera quelque chose comme au moins 4 fois plus d'espace. Je veux dire que tout fichier sur disque occupera 4 Ko pour un fichier 1kb. Surtout sur les disques SSD, le secteur 4 Ko sera la norme.
Vous devez donc regrouper plusieurs fichiers en 1 fichier physique. 1024 Fichier dans 1 fichier de stockage semble raisonnable. Pour localiser les fichiers individuels dans ces fichiers de stockage, vous devez utiliser certains RDBMS (PostgreSQL a été mentionné et il est bon mais SQLite peut être mieux adapté à cela) ou une structure similaire pour faire la cartographie.
La structure de répertoire suggérée par votre ami semble bonne mais elle ne résout pas le problème de stockage physique. Vous pouvez utiliser une structure de répertoire similaire pour stocker les fichiers de stockage. Il vaut mieux les nommer en utilisant un système numérique.
Si vous le pouvez, ne les laissez pas formater comme FAT32, au moins NTFS ou un système de fichiers récent de la saveur UNIX. Comme la taille totale des fichiers n'est pas si grande, NTFS peut être suffisante mais ZFS est la meilleure option ...
Cet algorithme de fichiers fonctionnera, mais ce n'est pas optimal. Je pense que l'utilisation de "segments" de 2 ou 3 caractères serait mieux pour la performance - surtout lorsque vous commencez à envisager de faire des sauvegardes.
Par exemple:
D: \ stockage \ fo \ ob \ ar \ foobar.txt
ou
D: \ Stockage \ FOO \ BAR \ FOOBAR.TXT
Il y a quelques avantages à utiliser ce type d'algorithme:
Il y a des côtés de quelques côtés aussi:
Je sais que c'est quelques années de retard, mais peut-être que cela puisse aider le prochain gars.
Ma suggestion Utilisez un SAN, mappé sur un lecteur Z que d'autres serveurs peuvent aussi bien mapper. Je n'irais pas avec le chemin du dossier que votre ami a dit d'aller avec, mais plus avec un lecteur: \ ClientId \ Année \ Jour \ Jour \ Et si vous ingérez plus de 100 000 documents par jour, vous pouvez ajouter des sous-dossiers pendant une heure. et même minute si nécessaire. De cette façon, vous n'avez jamais plus de 60 sous-dossiers tout en allant jusqu'au bout jusqu'à quelques secondes si nécessaire. Stockez les liens en SQL pour une récupération rapide et des rapports. Cela rend le chemin de dossier assez court par exemple: Z: \ 05 \ 2004 \ 02 \ 26 \ 09 \ 55 \ FileName.txt Vous ne rencontrerez pas de 256 limitations à travers le tableau.
espère que cela aide quelqu'un. :)
Est-ce que ces données statiques (750 mil sont-elles) ou y l'ajoutez (en ajoutant plus de fichiers sur une base périodique)? Peut-il être lu uniquement ou avez-vous également besoin de pouvoir mettre à jour des fichiers? Est-ce que c'est vraiment un accès au fichier aléatoire ou existe-t-il une sorte de modèles d'accès que vous pourriez observer sur une inspection plus étroite?
Question mise à jour pour répondre à cela. (Plus de fichiers ajoutés sur une base périodique, les fichiers sont supprimés quelque peu rarement. L'accès est aléatoire, mais certains fichiers seront accessibles beaucoup plus que d'autres.)
Réservez votre commentaire Edit2, vous n'avez besoin que de réfléchir. Voir Stackoverflow.com/faq pour plus de détails.