[Algoritme] Veel gegevens ontdubbelen (15 GB+)

[Verwijderd]

Ik ben momenteel met diverse benchmarks bezig geweest om op een zo snel mogelijke mannier gegevens te ontdubbelen.

Het gaat hier om ongeveer 15 tot 25 GB aan plain text files (logs van diverse servers) waar ik uit alle bestanden geen enkele duplicate regel wil. De bestanden zijn netjes opgedeeld in bestanden van ongeveer 600 MB.

Nu wil ik dit dus gaan ontdubbelen op een snelle mannier. Gezien ik niet erg wiskundig aangelegd ben maar wel met wat programmeer talen overweg kan zoek ik hier een uitweg voor (python/perl etc).

Zelf heb ik gedacht aan het volgende linux commando:

cat *.txt | sort | uniq > geendubbelen.txt

Maar dit heeft op 15 GB niet echt een effectieve benadering, en duwt in notime mijn 2 GB ram vol.

Verder heb ik in Python even simpel programmatje gemaakt die 1 file ontdubbeld:

code:

import os
import sys

f = open(sys.argv[1],'r')
m = {}

for l in f:
    l = l.strip()
    m[l] = 1

for k in m:
    # Hier schrijf ik dan naar file

De Python code duurt ongeveer 166 seconden per 600 MB wat opzich nog wel acceptabel is maar ik schiet niet veel verder op met het gehele probleem: alle files ontdubbelen tot 1 grote file zonder dubbele regels.

Heeft iemand hier een oplossing voor, idee, of suggesties?

Bvd.

Woutie

[Soultaker]

Ik neem aan dat je wel wat vrije schijfruimte hebt om in te werken? Dan zou ik alle regels gewoon in een tijdelijke database laden zodat je werkgeheugen ontlast wordt, en dan alles uitprinten.

Bijvoorbeeld in Perl:

Perl:

use DB_File;
tie %H, DB_File, "/tmp/db";
# Of met een btree als je gesorteerde uitvoer wil:
# tie %H, DB_File, "/tmp/db",  O_RDWR|O_CREAT, 0, $DB_BTREE
$H{$_} = "" while(<>);
print while($_ = each %H);
unlink "/tmp/db";

Of op de command line:

perl -MDB_File -e 'tie %H,DB_File,"/tmp/db"; $H{$_}=""while(<>); \
print while($_ = each %H); unlink "/tmp/db"' <bestandsnamen>

Als je bestanden zelf al ongeveer gesorteerd zijn, kan het sowieso waarschijnlijk wel uit om een BTree index te gebruiken in plaats van de (standaard) hash index.

edit:
Overigens kan het ook wel met standaardtools, maar dan moet je je invoer niet via een pipe doorgeven, maar als bestand. (GNU) sort maakt dan zelf tijdelijke bestanden aan.

sort --unique *.txt > geendubbelen.txt

Echt snel zal het allemaal niet zijn, maar zo loop je in ieder geval niet tegen je geheugenlimiet op.

[ Voor 17% gewijzigd door Soultaker op 17-02-2007 19:09 ]

[Spider.007]

Is het niet het snelst om de sort en uniq operators direct op disk los te laten zonder pipes te gebruiken? Het is logische dat daarbij je geheugen zou vollopen. Daarnaast ondersteunt sort zelf ook nog eens unique-checks; dus ontdubbel eerst de individele files en daarna het totaal nog een keer. Iets als dit zou volgens mij moeten werken:

sort --unique $file >>merged
sort --unique merged --output=merged_final

[ Voor 4% gewijzigd door Spider.007 op 17-02-2007 19:15 ]

[Verwijderd]

Het ontdubbelen van de individuele bestanden is geen probleem gezien dit met dat simpele python scriptje van mij enkel 3 minuten duurt per bestandje.

Het geheel ontdubbelen is iets wat via pipes niet lukte, maar mogelijk wel met de suggestie van Spider.007. Ik ga deze mannier zo even benchmarken of dat een optie is.

@Soultaker; schijfruimte is geen probleem, maar de code die je daar laat zien in Perl is voor mij enigsinds wat lastig te begrijpen gezien ik DB_file nog nooit gebruikt hebt binnen Perl. Misschien wat toelichting erbij hoe de performance hiervan is?

Bedankt voor de reacties zo ver! Meer tips zijn uiteraard welkom

[Verwijderd]

- Afvragen of 't nut heeft om 20+ GB aan logfiles te bewaren?

- Een database opzetten met een primary key op de velden die er toe doen. Daarna alle log-regels in die DB schieten, en bij een primary key violation die regel gewoon droppen.

- De manier die je nu al gebruikt: iedere file afzonderlijk ontdubbelen, vervolgens 2 files samenvoegen en die weer ontdubbelen, volgende file toevoegen, etc...

Ik zou voor een database oplossing kiezen.

[Soultaker]

Het idee van het Perl scriptje is eigenlijk precies hetzelfde als je Python code: alle regels in een hash stoppen en dan uitprinten. Met Perl kun je met tie ('verbinden') een hash koppelen aan een databasebestand; je kunt 'm dan gewoon gebruiken alsof het een hash variabele in het geheugen is, maar alle data komt in het bestand terecht. Op die manier omzeil je dus de geheugenlimiet.

Overigens denk ik dat sort gebruiken gewoon handiger is.

Verwijderd schreef op zaterdag 17 februari 2007 @ 19:15:
- Een database opzetten met een primary key op de velden die er toe doen. Daarna alle log-regels in die DB schieten, en bij een primary key violation die regel gewoon droppen.

Dat is hetzelfde als de Perl-code nu al doet (met BerkeleyDB backing).

- De manier die je nu al gebruikt: iedere file afzonderlijk ontdubbelen, vervolgens 2 files samenvoegen en die weer ontdubbelen, volgende file toevoegen, etc...

Dat werkt alleen als je genoeg dubbele regels hebt. Als maar, zeg, de helft van de regels dubbel is, dan eindig je nog met 7~8 GB aan data die niet in je geheugen past.

[ Voor 44% gewijzigd door Soultaker op 17-02-2007 19:17 ]

[Verwijderd]

Soultaker schreef op zaterdag 17 februari 2007 @ 19:16:
Dat is hetzelfde als de Perl-code nu al doet (met BerkeleyDB backing).

Dat zal best, maar regels als $H{$_} = "" while(<>); zijn voor gewone stervelingen volstrekt onleesbaar...

[Grum]

Verwijderd schreef op zaterdag 17 februari 2007 @ 20:05:
Dat zal best, maar regels als $H{$_} = "" while(<>); zijn voor gewone stervelingen volstrekt onleesbaar...

Wie zegt dan ook dat Perl voor 'mere mortals' is?

Maar voor de mere mortals:

code:

$H{$_} = "" while(<>);

Is exact het zelfde als:

code:

while( $_ = <STDIN> ) {
    $H{$_} = "";
}

Wat dus meer schrijven is

Het kan nog korter zonder onduidelijker te worden:

code:

use DB_File;
tie %H, DB_File, "db";
$H{$_}++ while(<>);
print for keys %H;
unlink "db";

Of zelfs:

code:

use DB_File;
tie %H, DB_File, "db";
$H{$_}++ or print for (<>);
unlink "db";

Perl

[Verwijderd]

Verwijderd schreef op zaterdag 17 februari 2007 @ 19:15:
- Afvragen of 't nut heeft om 20+ GB aan logfiles te bewaren?

- Een database opzetten met een primary key op de velden die er toe doen. Daarna alle log-regels in die DB schieten, en bij een primary key violation die regel gewoon droppen.

- De manier die je nu al gebruikt: iedere file afzonderlijk ontdubbelen, vervolgens 2 files samenvoegen en die weer ontdubbelen, volgende file toevoegen, etc...

Ik zou voor een database oplossing kiezen.

Ik heb aan de database oplossing ook even zitten denken maar na een performance test van bijv een MySQL database met een unique key op de velden die ontdubbeld moeten worden was het geen snelheid tenopzichte van de python/dictionary oplossing. LOAD DATA of mysql -u -p -e, of mysqldump waren erg traag t.o.v. python.

Gezien de Perlcode mij erg compact en snel lijkt (benchmarks van perl zijn vaak sneller dan python) vroeg ik mij af hoe ik volgende code fragmenten kan gebruiken in mijn situatie. Met Python ben ik wel bekend, perl wat minder.

[twanvl]

Je kan een merge sort achtige oplossing gebruiken:

• Sorteer en uniq eerst alle bestanden afzonderlijk
• Combineer dan de bestanden per paar met 'merge' en verwijder gelijk alle dubbellen. Sla het resultaat op in een nieuw bestand.
• Herhaal dit totdat er 1 bestand over is.

De 'merge' functie hoeft niet vooruit te kijken, er is maar 1 regel tegelijkertijd nodig per bestand. Als je dit goed implementeert is het geheugengebruik dus geen probleem.

[Verwijderd]

Bedankt voor de input allemaal. Via Wikipedia had ik inderdaad zelf ook naar informatie gezocht. Wilde oorspronkelijk het volgende proberen:

- Ontdubbelen per bestand, en sorteren, dan merge tot 1 file, en dan ontdubbelen via regel compare. echter was dit al trager bij de benchmarks van eerder genoemde code.

Quicksort is ivm met de recursive benadering op files van 500MB+ nogal een probleem want ik krijg dan in Python exceptions dat recursive limit bereikt is.

ik heb zojuist de logbestanden bekeken en het is totaal rond de 10GB per server, en totaal zijn er 3 servers. Ik heb zo het vermoeden dat dit wel even gaat duren voor dit ontdubbeld is...

Bedankt voor de suggesties tot dusver, iemand die kan inschatten hoelang zoiets duurt?

[Soultaker]

Werkt het nu al dan? Wat gebeurt er als je gewoon sort gebruikt zoals o.a. Spider.007 suggereerde? Als je maar één keer hoeft te ontdubbelen zou ik gewoon een methode kiezen (desnoods dat Perl script) en rustig wat anders gaan doen; uitzoeken wat de snelste methode is, duurt waarschijnlijk langer.

Verwijderd schreef op zaterdag 17 februari 2007 @ 22:56:
Gezien de Perlcode mij erg compact en snel lijkt (benchmarks van perl zijn vaak sneller dan python) vroeg ik mij af hoe ik volgende code fragmenten kan gebruiken in mijn situatie. Met Python ben ik wel bekend, perl wat minder.

De bottleneck is hier echt de database storage. De overhead van Perl (of Python als je 'm daarin zou schrijven) is te verwaarlozen. Wat dat betreft maakt het dus niet zoveel uit.

[Soultaker]

Grum schreef op zaterdag 17 februari 2007 @ 22:52:
Wie zegt dan ook dat Perl voor 'mere mortals' is?
Het kan nog korter zonder onduidelijker te worden:

code:

use DB_File;
tie %H, DB_File, "db";
$H{$_}++ while(<>);
print for keys %H;
unlink "db";

Laadt die keys functie nu niet alle keys in het geheugen? Dat werkt voor veel data natuurlijk niet.
Overigens kun je dan net zo goed: print keys %H; doen (scheelt weer een woord).

Of zelfs:

code:

use DB_File;
tie %H, DB_File, "db";
$H{$_}++ or print for (<>);
unlink "db";

Jaaa, die is cool! Overigens hoeven strings niet per se tussen quotes en is de puntkomma een statement seperator, geen terminator, dus het kan ook zo:

Perl:

use DB_File;
tie %H, DB_File, db;
$H{$_}++ or print for (<>);
unlink db

Voordeel van deze methode is dat je tijdens het inlezen al uitvoer krijgt in plaats van op het einde pas (meer parallellisatie als je nog dingen met je uitvoer moet doen), maar nadeel is dat je er geen gesorteerde uitvoer uit krijgt (als je een BTree storage zou gebruiken). Ook zou de performance minder kunnen zijn omdat je bij elke regel je database daadwerkelijk moet updaten, en je meer data opslaat (getallen in plaats van lege strings).

[ Voor 6% gewijzigd door Soultaker op 18-02-2007 16:47 ]

[Verwijderd]

Het is allemaal gelukt met het commando van Spyder.007. Echter heb ik wel gebruik moeten maken van een andere directory dan de default (/tmp) voor het opslaan van de tijdelijke sort files.

Het duurde ongeveer 8 uurtjes om alles te ontdubbelen met dit commando. Mooi optijd voor de maandag ochtend voor rapportje thnx!.

De perl methode zojuist geprobeerd op een kleinere set (6 GB) en performed t.o.v. de linux :

linux cmd (sort) : 43 min 12 sec
perl sort : 32 min 56 sec

Thnx voor de toelichting en uitleg bij de perl code Soultaker! En offcoz ook Spider.007 voor de file-disk approach ipv het laden in geheugen van sort.