Speicher sparen -> Hash-Werte komprimieren

Ideen und Vorschläge sind willkommen.

Speicher sparen -> Hash-Werte komprimieren

Beitragvon PCA42 » Sa Mai 09, 2009 3:22 pm

Yacy verwendet für die URLs und die RWIs zwölf-stellige Hashes. Diese können aus 64 verschiedenen Zeichen bestehen. Sie sind also pro Stelle eigentlich nur 6 Bit notwendig. Macht also für zwölf Stellen 72 Bit. Dafür reichen dann doch 9 Byte. Macht 25% Ersparnis. Vorteil: weniger benutzter Speicher und höhere Perfomance, weil einfach immer weniger Daten bewegt bzw. bearbeitet werden müssen.

Hab ich Nachteile übersehen bzw. mich verrechnet?
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Speicher sparen -> Hash-Werte komprimieren

Beitragvon Orbiter » Mo Mai 18, 2009 10:48 pm

Ja es gibt eine Antwort hier rauf, aber die ist länglich... Ich liste mal alle möglichen Antworten auf.

Also erst mal ist das eine gute Idee,

Antwort (1): das ist prinzipiell eine gute Idee

.. und ich hätte eigentlich beim ersten Design darauf kommen sollen. Nun ist es ein wenig spät, man müsste fürchterlich viel umstellen, und ggf viele Konvertierungen durchführen. Diese Konvertierung existiert tatsächlich schon, sie steht in yacySeed.b64Hash2b256Hash(). Sie wird aber nirgendswo genutzt...

Antwort (2): ständige Konvertierungen sind sehr kostspielig

Nun ist es so, dass die 12-byte Hashes sowohl als Hash für die Terme (Wörter) als auch für die URLs vorkommen. Ein Eintrag in der URL-DB hat aber mehr als 500 Zeichen, so dass 3 Zeichen Ersparnis nicht so weit ins Gewicht fallen. Bei den RWIs ist es so, dass einem Term-Hash einige, machnmal sehr viele URL-Hash + Properties zugeordnet sind. Hier kann man bei den Term-Hashes ähnlich wenig sparen, wohl aber bei den URL-Referenzen, die sehr oft vorkommen. Momentan hat ein URL-Hash + Properties zusammen 40 Bytes, hier könnte man dann 3 Byte sparen, sind rund 7 Prozent. Das ist dann auch das Maximum was man raus holen kann

Antwort (3): maximal lassen sich 7 Prozent bei den RWIs einsparen. Bei den URLs fällts kaum ins Gewicht.

Ein weiterer Punkt ist, dass die Ordnungsrelationen auf die Indexe der Datenbanken lange Zeit auf String-Vergleich basiert haben, aber bei den verkürzten Hashes man auf 8-bit bytes[] vergleichen muss. War in der Vergangenheit eine weitere Hürde, momentan wäre ein Vergleich auf bytes statt b64 eher eine Erleichertung

Antwort (4): früher war eine Umstellung schwer und nicht durchführbar, jetzt wäre es ok und würde sogar performance bringen.

Noch ein weiterer Punkt ist aber, dass es eine Methode zur Indexkompression gibt, die ganz anders funktioniert und noch nirgendswo benutzt wird: die b64-Hashes der URL-Referenzen sind im RWI geordnet, und das bedeutet, dass sie sich von einem zum nächsten Hash kaum unterscheiden. Das würde es erlauben, nur einen Diff zu speichern, der viel kürzer ist als die 12 bytes, schätzungsweise nur 3 Bytes. Das macht aber 9 bytes Einsparung gegenüber den 3 beim Umrechnen in b256:

Antwort (5): die b64-zu-b256 Kompression konkurriert mit der Indexkompression.

Ich hab hier noch nicht entschieden ob ich die Indexkompression machen soll, bin aber dem zugeneigt. Das würde aber sehr viel Umstellung notwendig machen, da habe ich momentan noch wichtigeres vor. Ggf. lässt sich beide Verfahren verbinden, bin aber nicht ganz sicher.
Zum Schluss gibts noch etwas ganz doofes: die 12 Zeichen des URL Hashes setzten sich aus 2 Komponenten zusammen: Path-Hash und Domain-Hash. In manchen Fällen wird der Domain-Hash separat betrachtet, beispielsweise beim site-constraint. Wenn man 9 bytes b256 berechnet, kommt man nicht mehr an den 6-byte hash ran und muss wieder umrechnen .. und das mitten in der Suche wo man sich keine Verzögerungen leisten kann:

Antwort (6): manche Funktionen basieren auf der 12-byte b64 Form, weil sie einen Teil des Hashes, den domain-Hash betrachten.

Es gibt also einige Vor- und Nachteile, einige Funktionsbereiche könnten ggf. beschleunigt, andere gebremst werden. Daher kann ich mich nicht dazu durchringen, hier eine grundsätzliche Architekturänderung durchzuführen.

Viel mehr Speichergewinn verspricht ein verbesserten Speichern der URLs in BLOBs, die sind nämlich noch platzverschwendend in Eco-Tabellen. Das werde ich auch mal angehen, ggf werden die URL-Dateien dabei ein gutes Stück kleiner.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: Speicher sparen -> Hash-Werte komprimieren

Beitragvon Orbiter » Di Mai 26, 2009 1:12 pm

Im Kontext mit dem Posting zur Komprimierung von idx- und gap- Dateien hab ich hier mal nachgedacht wie man statt einer Umrechung von b64 in b256, was vor allem wegen Problemen mit den Ordnungen auf Hashes und Umrechungen problematisch ist, anders Speicher sparen kann:
Man könnte die Hashes alle ein mal durch gehen, und sehen ab wievielen Stellen der Index noch eindeutig ist, wenn man Stellen weg läßt. Rein rechnerisch wären ja vier Stellen (2^^(6*4) = 2^^24 = 16 Millionen) schon ausreichend für eine Vielfalt von 16 Millionen Indexeinträgen, und ab fünf Stellen schon für eine Milliarde. Man müsste nur eben den ganzen Index ein mal durchgehen, und sehen wieviel ausreichend ist. Hier kommt o.g. Topic ins Spiel: ein Abspeichern des Indexes bedeutet ja, das dieser Check nur ein mal gemacht werden muss, wenn man den Index zwischenzeitlich nicht ändert. Löschen ist kein Problem, denn das ändert nicht die minimale Länge der Hashes. Aber genau dieser Fall liegt bei den RICELL-RWIs vor. Im Kontext zu einer möglichen Kompression der idx-Dateien müsste ich überlegen, ob man nicht gleich ein Format nimmt, dass einen gekürzten Schlüssel beinhalten kann.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: Speicher sparen -> Hash-Werte komprimieren

Beitragvon PCA42 » Di Mai 26, 2009 1:35 pm

Mir ging es grundsätzlich darum, das für einen alphanumerischen Hash ([a-z, A-Z....] - 64 Werte - 6 Bit) gleich ein ganzes Byte verwendet wird. Wenn man das zusammenfasst, spart das Speicher. Ziel war es auch nicht, die Hashes in den Dateien zu kürzen. Sondern vielmehr die im Arbeitsspeicher gehaltenen Indexe, denn dort rechnet sich das.

So wie ich dein neues Posting verstand hab, läuft das ja fast auf individuelle Hashes für jeden Peer heraus. Das macht aber DHT kompliziert bis unmöglich.
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Speicher sparen -> Hash-Werte komprimieren

Beitragvon Orbiter » Di Mai 26, 2009 1:45 pm

ich weiss wie du das gemeint hast, die Idee mit dem Kürzen kam mir im Kontext mit dem gzip-Komprimieren, weil man im File deklarieren müsste wie lang die keys dann nach dem Kürzen noch sind. Das gute ist ja: es gibt kein Problem mit DHT, weil der Index ja nur zum Auffinden der RWIs da sind, aber nicht für irgendwelche Werte. Der Hash, mit der in den gekürzten keys gesucht wird ist ja vorhanden und kann genutzt werden. Ausserdem könnte man das völlig transparent machen, so dass man keine Klasse und dessen Logik ändern muss, wenn nur der Index einen neuen Weg gefunden hat, die Datenmenge zu reduzieren. Daher passt die Idee hier ja auch in den Topic. Aber es ist noch nicht ganz ausgegoren, muss noch ein wenig darüber brüten.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: Speicher sparen -> Hash-Werte komprimieren

Beitragvon Orbiter » So Jun 07, 2009 10:56 pm

also ich bin das Thema jetzt mal angegangen, aber erst mal nur mit einer Analysefunktion. Bei jedem Laden von idx-Files wird jetzt mal geschaut, wieviele hash-bytes man denn braucht für einen eindeutigen Key, und ebenso geschaut wieviele bytes man für den anhängenden Pointer braucht. Das ganze wird dann zur Berechnung einer möglichen Speicherersparnis benutzt, und ausgegeben. In SVN 6034 ist das nun drin. Bitte auf die Ausgabe "HeapReader saturation" beim Start achten, da steht drin wieviel man sparen könnte.
Der nächste Schritt ist dann ein umkopieren in einen geeigneten Index, damit man den Spareffekt auch bekommt. Da muss ich mal schauen ob ich das noch vor dem Linuxtag schaffe.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: Speicher sparen -> Hash-Werte komprimieren

Beitragvon PCA42 » Mo Jun 08, 2009 4:50 am

Dann liefer ich mal ein paar Werte ab:
Code: Alles auswählen
I 2009/06/08 05:41:15 HeapReader using a dump of the index of /home/yacy/yacy/DATA/INDEX/freeworld/TEXT/RICELL/index.20090608032115565.blob.
I 2009/06/08 05:41:38 HeapReader saturation of index.20090527165705811.blob.3cHWIrO2yxEX.idx: keylength = 9, vallength = 5, possible saving: 153 MB
I 2009/06/08 05:41:39 HeapReader using a dump of the index of /home/yacy/yacy/DATA/INDEX/freeworld/TEXT/RICELL/index.20090527165705811.blob.
I 2009/06/08 05:41:39 kelondroBLOBHeap BLOB index.20090527165705811.blob: merged 155 free records
I 2009/06/08 05:41:45 HeapReader saturation of index.20090607210158038.blob.WNExYJ60VZ0j.idx: keylength = 7, vallength = 5, possible saving: 73 MB
I 2009/06/08 05:41:45 HeapReader using a dump of the index of /home/yacy/yacy/DATA/INDEX/freeworld/TEXT/RICELL/index.20090607210158038.blob.
I 2009/06/08 05:42:00 HeapReader saturation of index.20090605171037956.blob.zNlNclFKiZXr.idx: keylength = 11, vallength = 5, possible saving: 86 MB
I 2009/06/08 05:42:01 HeapReader using a dump of the index of /home/yacy/yacy/DATA/INDEX/freeworld/TEXT/RICELL/index.20090605171037956.blob.
I 2009/06/08 05:42:01 kelondroBLOBHeap BLOB index.20090605171037956.blob: merged 62 free records
I 2009/06/08 05:42:01 HeapReader saturation of index.20090607230029475.blob.Kjc0Y0TFHqt6.idx: keylength = 5, vallength = 4, possible saving: 4 MB
I 2009/06/08 05:42:01 HeapReader using a dump of the index of /home/yacy/yacy/DATA/INDEX/freeworld/TEXT/RICELL/index.20090607230029475.blob.
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Speicher sparen -> Hash-Werte komprimieren

Beitragvon dulcedo » Mo Jun 08, 2009 8:46 pm

Orbiter hat geschrieben:also ich bin das Thema jetzt mal angegangen, aber erst mal nur mit einer Analysefunktion.

Damit liest er die blobs nun nur noch mit ca. 16M (vorher weit über 100). Verlängert die Startzeit enorm, wenn nur zu Testzwecken natürlich kein Problem.
dulcedo
 
Beiträge: 1006
Registriert: Do Okt 16, 2008 6:36 pm
Wohnort: Bei Karlsruhe

Re: Speicher sparen -> Hash-Werte komprimieren

Beitragvon Orbiter » Mo Jun 08, 2009 10:32 pm

naja, wenn die Komprimierung kommt, dann würde diese Analysefunktion einmal bei read-only indexen laufen, und dann den komprimierten Index wieder abspeichern. Dafür würde dann das Laden des komprimierten Indexes schneller gehen als bisher.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main


Zurück zu Wunschliste

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste