Datenstruktur die zufällige Reihenfolge beinhaltet

[feuervogel]

Hallo,

ich grüble schon recht lange über ein Problem nach. Im Prinzip habe ich nur eine Menge Wörter, die ich in einer bestimmten Reihenfolge speichere, ich aber in einer anderen (zufälligen) Reihenfolge auslesen möchte, immer häppchenweise.

Eine MySQL-Datenbank mit einem ORDER BY RAND() LIMIT 0,10000 bietet sich deswegen nicht an, weil ich mindestens 1 Milliarde Einträge habe.

Ein Auslesen mit SELECT ... LIMIT 0,10000 oder LIMIT 234234,10000 geht recht flott, allerdings bekomme ich sie dann so zurück, wie ich sie eingefügt habe, und genau das will ich ja nicht.

Das ganze von vorneherein zufällig in Datei zu schreiben ist auch doof, weil ich wenn ich in Zeile x schreibe muss ich alle höheren Zeilen um eins verschieben.

Nach dem Auslesen zu sortieren ist auch nicht so gut möglich, da das nicht in meinen RAM passt, leider.

Kann ich das ganze also irgendwie zufällig in eine Datenbank schreiben, so dass ich danach nicht mehr sortieren muss? Wenn das Einfügen ein wenig dauert, ist es nicht so schlimm, Hauptsache, ich kann schnell auslesen...

[z0iD]

Hallo feuervogel,

wie wärs denn, wenn Du Deiner Tabelle eine weitere Spalte hinzufügst in der eine Priorität gespeichert wird? Du kannst dann beim Einfügen einer Zeile einen zufälligen Wert aus einem hinreichend großen Universum an diese Stelle schreiben. Jetzt kannst Du beim Auslesen bequem mit Deinem ORDER BY kommen und mit der LIMIT Angabe Deine Häppchen einteilen.

Die Reihenfolge in der ausgelesen wird ist dabei natürlich immer dieselbe. Wenn die immer anders sein soll wirds denke ich schwerer, weil Du das ganze ja "Häppchenweise" lesen willst. Dann müsste die Sortierung für einen kompletten Lesevorgang sozusagen festgehalten werden.
Dazu könnte man eine Streufunktion (Hash) definieren die einen konstanten Parameter erhält, und die Prioritäten abhängig von diesem Parameter permutiert. Dann könnte man mithilfe dieses Parameters immer eine andere Sortierung generieren. Die Streufunktion zu finden dürfte dabei wohl das größte Problem sein, da sie schon universell sein sollte (sonst gibts überall Kollisionen).

So, ich hoffe das hat Dir weitergeholfen.

[feuervogel]

Hallo feuervogel,

wie wärs denn, wenn Du Deiner Tabelle eine weitere Spalte hinzufügst in der eine Priorität gespeichert wird? Du kannst dann beim Einfügen einer Zeile einen zufälligen Wert aus einem hinreichend großen Universum an diese Stelle schreiben. Jetzt kannst Du beim Auslesen bequem mit Deinem ORDER BY kommen und mit der LIMIT Angabe Deine Häppchen einteilen.


Gut gedacht, allerdings ist das genau das, was MySQL macht, wenn man ORDER BY RAND() sagt. und 1 Milliarde zeilen zu sortieren macht keinen Spaß.


Die Reihenfolge in der ausgelesen wird ist dabei natürlich immer dieselbe. Wenn die immer anders sein soll wirds denke ich schwerer, weil Du das ganze ja "Häppchenweise" lesen willst. Dann müsste die Sortierung für einen kompletten Lesevorgang sozusagen festgehalten werden.
Dazu könnte man eine Streufunktion (Hash) definieren die einen konstanten Parameter erhält, und die Prioritäten abhängig von diesem Parameter permutiert. Dann könnte man mithilfe dieses Parameters immer eine andere Sortierung generieren. Die Streufunktion zu finden dürfte dabei wohl das größte Problem sein, da sie schon universell sein sollte (sonst gibts überall Kollisionen).

So, ich hoffe das hat Dir weitergeholfen.

Hmmmm *grübel*

[rambi]

Kann ich das ganze also irgendwie zufällig in eine Datenbank schreiben, so dass ich danach nicht mehr sortieren muss? Wenn das Einfügen ein wenig dauert, ist es nicht so schlimm, Hauptsache, ich kann schnell auslesen...

Vorschlag:
einmal im Monat
ALTER TABLE worte ORDER BY RAND()
Und deine Tabelle ist gründlich durchwirbelt :D

[z0iD]

Gut gedacht, allerdings ist das genau das, was MySQL macht, wenn man ORDER BY RAND() sagt. und 1 Milliarde zeilen zu sortieren macht keinen Spaß.



Hmmmm *grübel*
Hm müsste das nicht in der gewünschten Reihenfolge (ohne ORDER BY) zurückgegeben werden, wenn man die Prioritätsspalte als Primärschlüssel oder Index (welches von beiden weiß ich nicht, aber eines müsste es tun) definiert?

P.S.: Was meinst Du mit "Hmmmm *grübel*"? Habe ich mich unverständlich ausgedrückt?

[feuervogel]

Hm müsste das nicht in der gewünschten Reihenfolge (ohne ORDER BY) zurückgegeben werden, wenn man die Prioritätsspalte als Primärschlüssel oder Index (welches von beiden weiß ich nicht, aber eines müsste es tun) definiert?


das hab ich auch schon ausprobiert und es funktioniert leider nicht :-(


P.S.: Was meinst Du mit "Hmmmm *grübel*"? Habe ich mich unverständlich ausgedrückt?

ich muss es mir wahrscheinlich nur ein paar mal in ruhe durchlesen, dann hab ichs auch verstanden.

[rambi]

Da du auf mein Posting nicht eingehst, vermute ich mal, dass dir der Weg nicht so richtig zusagt....

Alternative:
Wende es nur einmal an..(oder auch gar nicht :D)

Dann bleibt dir noch das Problem beim Einfügen:
(du hast doch hoffendlich eine autoincrement ID)
1. Mit "COUNT(*) AS anzahl" bestimmen, wieviele Datensätze es gibt
2. mit PHP einen mt_rand(1,$anzahl-1) Wert bestimmen (LIMIT $rand,1)
3. Diesen Datensatz lesen
4. und ans Ende schreiben (INSERT)
5. den neuen an den "frei gewordenen" Platz schreiben (UPDATE)

Ansonsten fällt mit auch nach langer Überlegung nix dazu ein......

[meikel]

und 1 Milliarde zeilen zu sortieren macht keinen Spaß.
Wozu sortieren? Erbsen sortiert man doch nicht in der Tüte.

Selbst wenn Du 1 Mrd. Einträge in der Tabelle hast, wirst Du hoffentlich/wahrscheinlich nicht alle Einträge auf einen Schlag verwursten wollen.

Wieviel Einträge willst Du nach welchen Kriterien selektieren?
Bedenke dabei, daß ein DBMS keine Excel Tabelle ist.

[z0iD]

Ich kenne mich leider mit MySQL nicht sehr gut aus, aber ich meine dass man dort auch selbst definierte Funktionen ausführen kann. Dann könnte man doch mit einem Quickselect die k-te Prioriät (in der von mir vorgeschlagenen Struktur) finden und jeweils alle kleineren mithilfe der WHERE Klausel rauspulen. Der Quickselect ist eine Modifizierung des Quicksorts zum finden des k kleinsten/größten Elements in einem Array und läuft im Erwartungswert in linearer Zeit.

Also sagen wir, Du möchtest ab der m ten Stelle k Elemente lesen, dann Suchst Du mit Quickselect die Priorität von Stelle m (wenn Du sie nicht schon aus vorherigen Operationen kennst) und suchst anschließend die Priorität von Stelle m+k. Dann kannst Du Dir alle Elemente dazwischen bequem ausgeben lassen. Und das in linearer Zeit.

Es ist nur fragwürdig ob man so eine komplizierte Funktion wie den (rekursiven) Quickselect in MySql bekommt. Allerdings ist der Quickselect ja endrekursiv sodass es einfach sein dürfte ihn iterativ zu machen. Nur wiegesagt, ich weiß nicht ob man sowas in eine MySql Abfrage reinquetschen kann.

[z0iD]

Nachtrag: Mit einer (simpel zu implementierenden) Erweiterung von Blum, Floyd, Pratt, Rivest und Tarjan läuft der Quickselect wohl nicht nur im Erwartungswert sondern auch im schlimmsten Fall in linearer Zeit.

[feuervogel]

hallo leute, tut mir leid, dass ich mich so lange nicht mehr gemeldet habe. rambi: deinen vorschlag hab ich glatt überlesen.

ich werde die nächsten tage mal alles testen und morgen (heute bin ich irgendwie zu müde, jaja, das alter) dann die fragen beantworten...

[rambi]

Phuuu... und ich dachte schon fast, ich hätte dich irgendwann einmal verärgert und wäre auf der Ignorierliste (die mit den 10000 (hoffendlich)freien Plätzen) gelandet.... ;-)

Aber so:
Mach was draus, und berichte.. :-)

*Ach ja*
Wo bekommt man überhaupt 10^9 Worte her, bzw. was stellst du damit an?

[rambi]

@feuervogel
Gibt es neue Erkenntnisse?

[feuervogel]

okay, ich formuliere es mal so:

es geht um einen webcrawler. und jaaa, ich weiß, es gibt schon 1000 webcrawler, aber wenige, die sich fürs große crawlen eigenen und dauerhaft performant sind. meine abteilung in der uni musste damit einige schmerzhafte erfahrungen sammeln.

im grunde genommen wird der crawler in zwei schritten arbeiten:

1. alle urls der liste abarbeiten und neue urls speichern.
2. die liste durcheinander würfeln und wieder zu 1 springen.

die verwaltung dieser liste hat sich als der größte flaschenhals herausgestellt, daher ist es mir so wichtig, dass es halbwegs performant abläuft. aber hier kann ich mir dann ja einen schnellen sortieralgorithmus ausdenken/implementieren (oder einfach mysql die arbeit machen lassen, kann ja ruhig ein wenig dauern).

alllerdings ist mir auch die idee gekommen, den leuten in der uni eins vorraus zu sein und threads zu benutzen, dann kann ich vielleicht gleichzeitig sortieren und crawlen (je nachdem wie viele resourcen das frisst). aber das kann natürlich immer zu zusätzlichen problemen führen.

[rambi]

So langsam wirds deutlicher, was du vorhast...
(aber so wirklich viel Ahnung habe ich da auch nicht von)

Wozu soll das Würfeln der Liste gut sein?
Wann die Seiten an die Reihe kommen, ist doch relativ wurscht, oder nicht?
Ist da ein Timestamp von letzten Scan nicht viel angebrachter?
Auch über ein Relevanz Flag könnte man nachdenken.

Threads:
Das erscheint mir viel logischer!
KA wie lange dein Script braucht um eine Seite zu analysieren, sagen wir mal 10ms. Die typische Requestzeit dürfte heutzutage bei ca 100 bis 500 ms liegen. Also wären für maximale Auslastung ca 10 bis 50 Threads angesagt, welche die einzelnen URLs abklappern. Ein Thread zum sortieren scheint mir da irgendwie falsch zu sein, das sollte man der DB überlassen.

Vermutlich ist es noch nicht einmal wichtig, ob die Daten sofort und synkron in die DB geschrieben oder gelesen werden. Also Queues einrichten, wo es nur geht.

So, mehr mag dazu nicht sagen...

[feuervogel]

es gibt webseitenbetreiber die dich aussperren wenn du über einen längeren zeitraum ihre seite alle 30 sekunden abfragst. es gibt webseitenbetreiber die richten eine robots.txt ein mit einer vorgeschriebenen pause von 3 minuten. und es gibt webseiten, die zusammenknicken, wenn man sie mit anfragen torpediert, auch zu einem "guten" zweck. (so geschehen durch die uni leipzig beim tüv süd, als nach den urls rückwärs gelesen sortiert wurde.)

daher spielt die reihenfolge sehr wohl eine rolle und es wichtig, dass diese zufällig ist.

ich könnte natürlich für jede domain einen thread aufmachen und dann jeweils den thread warten lassen, aber ich will ja keine breitensuche, sondern möglichst verschiedene webseiten crawlen :-)

[z0iD]

Was hältst Du davon, nach der Quersumme der URL zu sortieren?

Problematisch dabei wären dann wohl so CMS' die solche URLs verwalten wie:
www.domain.de/?id=1
www.domain.de/?id=2
www.domain.de/?id=3
Da die dann immer nah beieinander liegen.

[rambi]

daher spielt die reihenfolge sehr wohl eine rolle und es wichtig, dass diese zufällig ist.
Sicherlich ist eine Reihenfolge irgendwie wichtig. Aber was das mit dem Zufall zu tun haben soll, hast du mir damit noch nicht verkauft.... ;-)
Der Zufall hilft weder bei den 3 Minuten, noch verhindert er das tausendfache Anfragen einer Domain. Es liegt in der Natur der Zufälle, dass sie nicht SO zuverlässig sind und ab und zu die witzigsten Zahlenfolgen liefern.

[feuervogel]

sagen wir so: beim zufall ist die gefahr am kleinsten, dass ich mehrere urls einer domain hintereinander erwische.

und es ist für die datenmenge nunmal am einfachsten zu implementieren. (1 milliarde mal eine quersumme eines strings ausrechnen möchte ich z.b. nicht).

und du kannst dir ziemlich sicher sein, dass es google genau so macht, und deren lösungen sind durchaus sehr performant.

[feuervogel]

So, nachdem meine Tage wieder ein wenig stressfreier geworden sind:

Ich habe nun eine erste pre-alpha des Crawlers implementiert. Er ist in Python geschrieben; Crawling läuft verteilt. Der Code fürs Crawlen wird dynamisch mittels Pyro geladen, die Daten über xmlrpc hin- und hergeschickt.

Ich habe eine Liste mit aktuellen URLs. Diese Crawle ich nach URLs und speichere sie. Wenn die alten URLs alle abgegrast sind, dann sortiere ich beide Listen zufällig und fange wieder von vorne an.

Da ich mit einer MySQL-Datenbank arbeite, erledige ich das faulerweise mit order by `rand` (so heißt die Spalte).

Ansonsten heißt es jetzt eigentlich nur noch Bugtesting und weitere schöne Eigenheiten hinzuzufügen (ausser, dass mir lediglich ein paar hundert Terrabyte fehlen um wirklich loszulegen).

[defabricator]

sagen wir so: beim zufall ist die gefahr am kleinsten, dass ich mehrere urls einer domain hintereinander erwische.Wenn Du die Urls nach domain trennst und immer nur einen link aus der Gruppe nimmst, ist die Wahrscheinlichkeit doch noch geringer, nämlich 0.

[feuervogel]

Wenn Du die Urls nach domain trennst und immer nur einen link aus der Gruppe nimmst, ist die Wahrscheinlichkeit doch noch geringer, nämlich 0.

das ist mir auch schon aufgefallen, nur skaliert das irgendwann nicht mehr so wirklich.

ich wollts mal mit pytables probieren, damit kann man angeblich sehr große datenmengen sehr performant verwalten.