Java - comment écrire efficacement un fichier séquentiel avec des trous occasionnels

Question

J'ai besoin d'écrire des enregistrements dans un fichier où les données sont écrites à un emplacement de fichier (c.-à-d. Position de recherche) en fonction de la valeur d'une clé numérique . Par exemple, si la clé est 100, je pourrais écrire à la position 400.

Les enregistrements sont constitués de la clé numérique et d'une donnée. L'enregistrement ne sera pas très grand (quelques octets). Cependant, il peut y avoir beaucoup d'enregistrements (millions).

Il existe deux scénarios possibles:

1. Les clés augmentent de façon monotone. Dans ce cas, la meilleure approche consiste à écrire en utilisant un DataOutputStream enveloppant un BufferedOutputStream, en réglant la taille de la mémoire tampon sur un certain nombre (par exemple 64k) pour maximiser le débit d'E/S.

2. Les clés sont en augmentation mais avec des écarts importants possibles. Dans ce cas, l'utilisation d'un OutputStream nécessite l'écriture de zéros dans les espaces du fichier. Pour éviter cela, un RandomAccessFile serait mieux car il pourrait chercher sur les lacunes, économiser de l'espace s'il est possible de chercher sur un bloc entier. L'inconvénient est que, pour autant que je sache, RandomAccessFile ne tampon pas, donc cette méthode va être lente pour les touches séquentielles.

Cependant, la situation probable est que le fichier est un peu des deux. Il existe des séquences de clés monotones croissantes. Il y a quelques clés avec de petits espaces entre et d'autres avec de très grands espaces. Ce que je cherche est une solution qui offre le meilleur des deux mondes. Il se peut que je commute entre les deux modes d'E/S si un écart entre les clés est détecté. Cependant, il serait préférable qu'il existe une classe Java standard capable de faire ces deux choses. J'ai vu FileImageOutputStream, mais je ne suis pas sûr comment cela fonctionne.

Notez que je ne cherche pas d'échantillons de code (bien que cela serait utile pour démontrer des solutions complexes), mais simplement une stratégie générale. Il serait bon de connaître les tailles optimales des tailles de tampon pour les données séquentielles et à quel point (taille de l'écart) vous devez passer d'une stratégie séquentielle à une stratégie d'accès aléatoire.

EDIT:

Pour une réponse soit acceptée, je voudrais une certaine assurance que tous les deux, ne gère solution proposée juste qu'il pourrait. Cela nécessiterait:

• Confirmation que le mode séquentiel est tamponné.
• Confirmation que le mode d'accès aléatoire laisse des trous dans le fichier.

De plus, la solution doit être efficace en mémoire car plusieurs de ces fichiers peuvent être ouverts simultanément.

EDIT 2

Les fichiers peuvent être sur un NAS. Ce n'est pas une question de conception, mais simplement une reconnaissance que dans un environnement d'entreprise, cette architecture est très utilisée et que la solution devrait probablement la gérer (peut-être pas de manière optimale) et ne pas empêcher son utilisation. AFAIK, cela ne devrait pas affecter une solution basée sur write() et lseek(), mais pourrait invalider certaines solutions plus ésotériques. 

Answer 1

J'ai changé d'avis à ce sujet. Vous devriez utiliser MappedByteBuffer. Il est paginé par le système d'exploitation en tant que partie du sous-système de mémoire virtuelle, ce qui satisfait votre exigence de mise en mémoire tampon; c'est aussi rapide qu'une écriture en mémoire lors de l'écriture; et il est sujet au comportement du système d'exploitation lors de l'écriture de fichiers avec des trous, ce qui satisfait à cette exigence.

Answer 2

Édition/avertissement: il y a des pièges potentiels avec cette solution, car elle utilise beaucoup MappedByteBuffer, et on ne sait pas comment/quand les ressources correspondantes sont libérées. Voir this Q&A & JDK-4724038 : (fs) Add unmap method to MappedByteBuffer.

_{Cela dit, s'il vous plaît voir aussi la fin de ce post}

---

je ferais exactement ce que Nim suggested:

wrap ceci dans une classe cartes en « blocs » et puis déplace le bloc le long que vous écrivez .. L'algorithme pour cela est assez simple .. Il suffit de choisir une taille de bloc qui a un sens pour les données que vous écrivez ..

En fait, je l'ai exactement qu'il ya quelques années et juste déterré le code, il va comme ceci (dépouillé au strict minimum pour une démonstration, avec une seule méthode pour écrire des données):

import java.io.IOException; 
import java.io.RandomAccessFile; 
import java.nio.MappedByteBuffer; 
import java.nio.channels.FileChannel; 
import java.nio.file.Path; 

public class SlidingFileWriterThingy { 

    private static final long WINDOW_SIZE = 8*1024*1024L; 
    private final RandomAccessFile file; 
    private final FileChannel channel; 
    private MappedByteBuffer buffer; 
    private long ioOffset; 
    private long mapOffset; 

    public SlidingFileWriterThingy(Path path) throws IOException { 
     file = new RandomAccessFile(path.toFile(), "rw"); 
     channel = file.getChannel(); 
     remap(0); 
    } 

    public void close() throws IOException { 
     file.close(); 
    } 

    public void seek(long offset) { 
     ioOffset = offset; 
    } 

    public void writeBytes(byte[] data) throws IOException { 
     if (data.length > WINDOW_SIZE) { 
      throw new IOException("Data chunk too big, length=" + data.length + ", max=" + WINDOW_SIZE); 
     } 
     boolean dataChunkWontFit = ioOffset < mapOffset || ioOffset + data.length > mapOffset + WINDOW_SIZE; 
     if (dataChunkWontFit) { 
      remap(ioOffset); 
     } 
     int offsetWithinBuffer = (int)(ioOffset - mapOffset); 
     buffer.position(offsetWithinBuffer); 
     buffer.put(data, 0, data.length); 
    } 

    private void remap(long offset) throws IOException { 
     mapOffset = offset; 
     buffer = channel.map(FileChannel.MapMode.READ_WRITE, mapOffset, WINDOW_SIZE); 
    } 

} 

ici est un extrait de test:

SlidingFileWriterThingy t = new SlidingFileWriterThingy(Paths.get("/tmp/hey.txt")); 
t.writeBytes("Hello world\n".getBytes(StandardCharsets.UTF_8)); 
t.seek(1000); 
t.writeBytes("Are we there yet?\n".getBytes(StandardCharsets.UTF_8)); 
t.seek(50_000_000); 
t.writeBytes("No but seriously?\n".getBytes(StandardCharsets.UTF_8)); 

Et le fichier de sortie ressemble à:

$ hexdump -C /tmp/hey.txt 
00000000 48 65 6c 6c 6f 20 77 6f 72 6c 64 0a 00 00 00 00 |Hello world.....| 
00000010 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 
* 
000003e0 00 00 00 00 00 00 00 00 41 72 65 20 77 65 20 74 |........Are we t| 
000003f0 68 65 72 65 20 79 65 74 3f 0a 00 00 00 00 00 00 |here yet?.......| 
00000400 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 
* 
02faf080 4e 6f 20 62 75 74 20 73 65 72 69 6f 75 73 6c 79 |No but seriously| 
02faf090 3f 0a 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |?...............| 
02faf0a0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 
* 
037af080 

^{J'espère que je ne l'ai pas rui n tout en supprimant les bits inutiles et en renommant ... Au moins le calcul de décalage semble correct (0x3e0 + 8 = 1000, et 0x02faf080 = 50000000).}

Nombre de blocs (colonne de gauche) occupés par le fichier, et un autre fichier non clairsemée de la même taille:

$ head -c 58388608 /dev/zero > /tmp/not_sparse.txt 
$ ls -ls /tmp/*.txt 
    8 -rw-r--r-- 1 nug nug 58388608 Jul 19 00:50 /tmp/hey.txt 
57024 -rw-r--r-- 1 nug nug 58388608 Jul 19 00:58 /tmp/not_sparse.txt 

Nombre de blocs (et réelle « faible densité ») dépendra OS & le système de fichiers ci-dessus était sur Debian Buster, ext4 - Les fichiers fragmentés ne sont pas supportés sur HFS + pour macOS, et sous Windows ils demandent au programme de faire quelque chose de spécifique dont je ne sais pas assez, mais cela ne semble pas facile. de Java, pas sûr.

Je n'ai pas de nouveaux chiffres mais à l'époque cette "technique glissante-MappedByteBuffer" était très rapide, et comme vous pouvez le voir ci-dessus, elle laisse des trous dans le fichier.
Vous aurez besoin d'adapter WINDOW_SIZE à quelque chose qui a du sens pour vous, ajouter toutes les méthodes writeThingy dont vous avez besoin, peut-être en enveloppant writeBytes, tout ce qui vous convient. En outre, dans cet état, le fichier sera développé au besoin, mais par blocs de WINDOW_SIZE, que vous devrez peut-être également adapter.

À moins qu'il y ait une très bonne raison de ne pas le faire, il est probablement préférable de rester simple avec ce seul mécanisme, plutôt que de maintenir un système bimode complexe.

---

A propos de la fragilité et de la consommation de mémoire, j'ai couru le stress-test ci-dessous sur Linux sans aucun problème pendant une heure, sur une machine avec 800GB de RAM, et sur une autre machine virtuelle très modeste avec 1G de RAM . Le système semble parfaitement sain, le processus Java n'utilise pas une quantité significative de mémoire de tas.

String path = "/tmp/data.txt"; 
    SlidingFileWriterThingy w = new SlidingFileWriterThingy(Paths.get(path)); 
    final long MAX = 5_000_000_000L; 
    while (true) { 
     long offset = 0; 
     while (offset < MAX) { 
      offset += Math.pow(Math.random(), 4) * 100_000_000; 
      if (offset > MAX/5 && offset < 2*MAX/5 || offset > 3*MAX/5 && offset < 4*MAX/5) { 
       // Keep 2 big "empty" bands in the sparse file 
       continue; 
      } 
      w.seek(offset); 
      w.writeBytes(("---" + new Date() + "---").getBytes(StandardCharsets.UTF_8)); 
     } 
     w.seek(0); 
     System.out.println("---"); 
     Scanner output = new Scanner(new ProcessBuilder("sh", "-c", "ls -ls " + path + "; free") 
       .redirectErrorStream(true).start().getInputStream()); 
     while (output.hasNextLine()) { 
      System.out.println(output.nextLine()); 
     } 
     Runtime r = Runtime.getRuntime(); 
     long memoryUsage = (100 * (r.totalMemory() - r.freeMemory()))/r.totalMemory(); 
     System.out.println("Mem usage: " + memoryUsage + "%"); 
     Thread.sleep(1000); 
    } 

Alors oui c'est empirique, peut-être il ne fonctionne correctement sur les systèmes Linux récents, peut-être il est tout simplement la chance avec cette charge de travail particulier ... mais je commence à penser que c'est une solution valable sur certains systèmes et les charges de travail, cela peut être utile.

Answer 3

Vous dites des millions d'enregistrements de quelques octets. Supposons donc qu'il s'agit de 10 millions de 10 octets, ce qui signifie que le fichier à écrire aura environ 100 mb. À notre époque, ce n'est pas beaucoup.

Je voudrais juste créer une carte dans laquelle toutes les paires de valeur-clé ont été stockées. Alors écrirait une fonction qui sérialiserait le contenu de la carte à byte[]. Et puis simplement Files.write() les octets sur le disque. Remplacez ensuite l'ancien fichier par le nouveau fichier. Ou, mieux encore, déplacez d'abord l'ancien fichier, puis déplacez le nouveau.

Answer 4

Je suppose que lorsque vos clés après avoir augmenté séquentiellement pendant alors faire un écart, il n'y aura pas une autre clé ajoutant à la séquence "fini". Si cela est correct alors je sujest la solution suivante

Tant que vos clés ne cessent d'augmenter garder séquentiellement travailler avec votre 1ère approche:

écriture à l'aide d'un DataOutputStream enveloppant un BufferedOutputStream, le réglage de la taille du tampon à certains nombre (par exemple 64k) pour maximiser le débit d'E/S.

écrivez vos données dans un fichier temporaire. Une fois l'écart enregistré, commencez à écrire dans un fichier temporaire suivant et conservez l'enregistrement de vos fichiers temporaires. De cette façon, vous obtenez un fichier par séquence d'enregistrements sans lacunes. Une fois que vous avez fini de traiter les données de votre fichier principal, vous disposez d'une méthode distincte qui permet de concaténer intelligemment vos fichiers temporaires dans un fichier final. Ce serait une tâche facile puisque vous savez que chaque fichier temporaire n'a pas de trous

Answer 5

Mon premier effort serait d'utiliser naïvement RandomAccessFile et de voir si elle est assez rapide. Je serais en fait surpris si elle est lente - bien que Java ne le tamponnera pas, l'implémentation du système de fichiers le fera.

---

S'il y a vraiment des problèmes de performance, mon prochain effort serait d'envelopper le RandomAccessFile dans une façade tampon, avec la logique d'écriture le long des lignes de (pseudo-code java-ish):

void write(record, location) { 
    if(location != lastLocation + recordLength) { 
      flushBufferToRandomAccessFile(); 
    ) 
    addToBuffer(record); 
    flushBufferToRandomAccessFileIfFull(); 
    lastLocation = location; 
} 

Le tampon serait un byte[]. La victoire potentielle ici est que vous faites moins randomAccessFile.write(buffer, 0, longLength) au lieu de plus randomAccessFile.write(record, 0, shortLength).

Vous pouvez ranger ceci un peu en encapsulant toutes les informations nécessaires sur un bloc tamponné dans une classe Buffer - octets, emplacement de départ, emplacement de fin. Vous devrez également vider le tampon pour le fichier dans une méthode close()).

qui est, vous collectez des blocs d'enregistrements dans la mémoire de tas, bouffées de chaleur à RandomAccessFile:

• lorsque vous atteignez la taille de votre tampon,
• lorsqu'un emplacement d'enregistrement ne soit pas accolée à la après le dernier enregistrement

Je comprends que vous ne voulez pas en cours buffers de blocs

à perdre la mémoire - mais peu importe que ce soit dans le tas ou ailleurs, note ry est de la mémoire, et vous ne pouvez pas avoir de mémoire tampon sans elle. Avec cette solution, vous pouvez ajuster la taille de votre tampon - et même si cela ne suffit que pour deux enregistrements, cela pourrait réduire de moitié le nombre d'écritures.

Si vous voulez être fanatique de l'utilisation de la mémoire, vous utilisez une mauvaise langue.

---

Si cela n'était pas encore assez rapide, je considérerais de déplacer les écritures dans un autre thread. Donc écrivez vos dossiers dans une file d'attente, et laissez le thread d'écriture de fichier consommer de la file d'attente. Cela ne rendra pas l'écriture de fichier plus rapide en soi, mais signifie que le consommateur peut rattraper son retard alors que le producteur fait un travail différent - son utilité dépend donc du fait que le producteur a un autre travail à faire.