Algoritmo per l'unione di file di grandi dimensioni

Question

Ho diversi file di registro degli eventi (un evento per riga). I registri possono eventualmente sovrapporsi. I registri sono generati su macchine client separate da possibilmente più fusi orari (ma suppongo di conoscere il fuso orario). Ogni evento ha un timestamp che è stato normalizzato in un orario comune (istanziando ogni istanza del calendario dei parser di log con il fuso orario appropriato al file di log e quindi usando getTimeInMillis per ottenere l'ora UTC). I log sono già ordinati per data e ora. Più eventi possono verificarsi contemporaneamente, ma non sono affatto uguali.

Questi file possono essere relativamente grandi, come in, 500000 eventi o più in un singolo registro, quindi la lettura dell'intero contenuto dei registri in un semplice Evento [] non è fattibile.

Quello che sto provando a fare è unire gli eventi di ciascuno dei registri in un unico registro. È un po 'come un'attività di fusione, ma ogni registro è già ordinato, ho solo bisogno di riunirli. Il secondo componente è che lo stesso evento può essere visto in ciascuno dei file di registro separati e desidero "rimuovere gli eventi duplicati" nel registro di output del file.

È possibile farlo "sul posto", come su, lavorando in sequenza su alcuni piccoli buffer di ciascun file di registro? Non posso semplicemente leggere tutti i file in un Evento [], ordinare l'elenco e quindi rimuovere i duplicati, ma finora le mie capacità di programmazione limitate mi consentono di vedere questo come la soluzione. Esiste un approccio più sofisticato che posso usare per farlo mentre leggo gli eventi da ciascuno dei registri contemporaneamente?

Answer 1

1. Leggi la prima riga da ciascuno dei file di registro

2. LOOP

   a. Trova il "più presto" linea.

   b. Inserisci il "primo" linea nel file di registro principale

   c. Leggi la riga successiva dal file che contiene la prima riga

È possibile verificare la presenza di duplicati tra bec, facendo avanzare il puntatore per ciascuno di quei file.

Answer 2

Sicuro: apre tutti i file di registro. Leggere nella prima riga per ciascuna in una matrice di righe "correnti". Quindi selezionare ripetutamente la riga con il timestamp più basso dall'array corrente. Scrivilo sull'output e leggi una nuova riga dal file sorgente appropriato per sostituirlo.

Ecco un esempio in Python, ma rende anche un buon pseudocodice:

def merge_files(files, key_func):
    # Populate the current array with the first line from each file
    current = [file.readline() for file in files]
    while len(current) > 0:
        # Find and return the row with the lowest key according to key_func
        min_idx = min(range(len(files)), key=lambda x: return key_func(current[x]))
        yield current[min_idx]
        new_line = files[min_idx].readline()
        if not new_line:
            # EOF, remove this file from consideration
            del current[min_idx]
            del files[min_idx]
        else:
            current[min_idx] = new_line

Answer 3

Dai un'occhiata a questo link: http : //www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

• Usa un heap (basato su un array). Il numero di elementi in questo heap / array sarà uguale al numero di file di registro che hai.

• Leggi i primi record da tutti i file e inseriscili nel tuo heap.

• Ripeti fino a (non più record in nessuno dei file)

      > remove the max element from the heap
      > write it to the output
      > read the next record from the file to which the (previous) max element belonged
          if there are no more records in that file
              remove it from file list
              continue
      > if it's not the same as the (previous) max element, add it to the heap

Ora hai tutti i tuoi eventi in un unico file di registro, sono ordinati e non ci sono duplicati. La complessità temporale dell'algoritmo è (n log k) dove n è il numero totale di record e k è il numero di file di registro.

È consigliabile utilizzare oggetti buffer e writer bufferizzati durante la lettura da e verso i file per ridurre al minimo il numero di letture e scritture su disco, al fine di ottimizzare in tempo.

Answer 4

Dovevamo unire cronologicamente più file di registro con più righe per una voce di registro (le applicazioni java lo fanno spesso - le loro tracce dello stack sono le stesse). Ho deciso di implementare il semplice script shell + perl. Copre i nostri compiti. Se sei interessato, segui il link http://code.google.com/p/logmerge /

Answer 5

Legge solo una riga alla volta da entrambi i file di origine. Confronta le righe e scrivi quella precedente nel file di output (e passa alla riga successiva). Fallo fino a quando non hai raggiunto la fine di entrambi i file e non hai unito i file.

E assicurati di rimuovere i duplicati :)

Suppongo che questo codice in C # possa illustrare l'approccio:

        StringReader fileStream1;
        StringReader fileStream2;
        Event eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
        Event eventCursorFile2 = Event.Parse(fileStream2.ReadLine());

        while !(fileStream1.EOF && fileStream2.EOF)
        {
            if (eventCursorFile1.TimeStamp < eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
            }
            else if (eventCursorFile1.TimeStamp == eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }
            else
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }  
        }

La condizione di interruzione non è esattamente corretta in quanto si tratta solo di Quick'n'dirty, ma dovrebbe apparire simile ..

Answer 6

O potresti prendere in prestito un'utilità di unione dei log da Awstats che è uno strumento di statistiche del sito Web open source.

logresolvemerge.pl è un script perl che può unire più file di registro: è anche possibile utilizzare più thread per unire i file di registro (è necessario disporre di perl 5.8 per l'utilizzo di più thread). Perché non provi a utilizzare uno strumento facilmente disponibile anziché crearne uno?