DHT-Positionierung

Forum for developers

DHT-Positionierung

Beitragvon Lotus » Fr Jun 05, 2009 5:46 pm

de.anomic.yacy.dht.VerticalWordPartitionScheme.dhtPosition(byte[], String)
Zeile 67:
// - from the url hash take the (63 - <partitionExponent>) higher bits

Muss es nicht heißen take 65 + <partitionExponent> higher bits?
Oder muss ich noch einmal nachdenken?
Lotus
 
Beiträge: 1699
Registriert: Mi Jun 27, 2007 3:33 pm
Wohnort: Hamburg

Re: DHT-Positionierung

Beitragvon Orbiter » Fr Jun 05, 2009 7:16 pm

also da triffst du ins Herz der DHT Berechnung, dann mal schauen ob alles stimmt: Der ganze Abschnitt lautet:
Code: Alles auswählen
long partitionMask = (1L << (Long.SIZE - 1 - partitionExponent)) - 1L;
        // compute the position using a specific fragment of the word hash and the url hash:
        // - from the word hash take the (63 - <partitionExponent>) lower bits
        // - from the url hash take the (63 - <partitionExponent>) higher bits
        // in case that the partitionExpoent is 1, only one bit is taken from the urlHash,
        // which means that the partition is in two parts.
        // With partitionExponent = 2 it is divided in four parts and so on.
        return (FlatWordPartitionScheme.std.dhtPosition(wordHash, null) & partitionMask) | (FlatWordPartitionScheme.std.dhtPosition(urlHash.getBytes(), null) & ~partitionMask);

d.h. berechnet wird
Code: Alles auswählen
long partitionMask = (1L << (Long.SIZE - 1 - partitionExponent)) - 1L;
return (FlatWordPartitionScheme.std.dhtPosition(wordHash, null) & partitionMask) | (FlatWordPartitionScheme.std.dhtPosition(urlHash.getBytes(), null) & ~partitionMask);

mit der partitionMask wird also einmal der vordere und einmal der hinterer Teil eines Hashes ausgeblendet. Die Frage wo die Grenze gesetzt wird, bestimmt der partitionExponent. Die Absicht ist es, dass bei einem PartitionExponent von 0 eine Abbildung der alten Hashtable statt findet, bei der die URL keine Rolle spielte.
Dazu muss die PartitionMask = 111111111111111111111111111111111111111111111111111111111111111 (63 mal eine 1) sein. Mal sehen ob das klappt:
partitionMask = (1L << (Long.SIZE - 1 - partitionExponent)) - 1L;
für paritionExonent=0 und Long.SIZE=64 gilt
partitionMask = (1L << 63) - 1L;
da 1L << x == 2^^x gilt:
partitionMask = 2^^63 - 1
da 2^^x - 1 = x-mal-eine-1 stimmt die Rechung so weit!

Je größer das partitionExponent nun wird, um so kürzer wird die Folge von 1en.
insbesondere gilt: es werden so viele Bits vom URL-Hash genommen, wie <partitionExponent>, die fehlen dann dem word hash vorne.

Es muss also heissen:
// - from the url hash take the <partitionExponent> higher bits

d.h. du hast heraus gefunden dass die Zeile falsch ist, aber die Antwort war auch nicht richtig.
Orbiter
 
Beiträge: 5798
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: DHT-Positionierung

Beitragvon Lotus » Fr Jun 05, 2009 8:03 pm

Okay, zuerst habe ich 1+exponent geschrieben, aber ich habe mich nachträglich von den Bits irritieren lassen (bei 128 sind wir noch nicht angekommen).

Wenn der alte Hash nur auf 63 Low-Bit relevant war stimmt das alles.
Lotus
 
Beiträge: 1699
Registriert: Mi Jun 27, 2007 3:33 pm
Wohnort: Hamburg


Zurück zu YaCy Coding & Architecture

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron