Chord systém

Chord systém

• = Distribuovaná hashovací tabulka

• Chord systém se používá pro organizaci a vyhledávání informací v distribuovaných systémech.

• Navržen tak, aby poskytoval efektivní a spolehlivé řešení pro distribuované uchovávání a vyhledávání klíčů v síti.

• Původně navržen pro peer-to-peer sítě, ale jeho koncepty jsou aplikovatelné i na jiné typy DS.

• Chord vytváří kruhovou strukturu, kde každý uzel (node) v síti má přiřazen jedinečný identifikátor (klíč).

• Uzly jsou uspořádány do kruhu podle hodnot jejich identifikátorů. Identifikátor má $m$ bitů (obvykle $128$ nebo $160$) a celkově je poté v $2^m$ uzlů.

• Uzel s klíčem $k$ je spravován uzlem s klíčem $id$, kde $id\ge k$, tento uzel se nazývá succ(k) (successor)

• Hlavní úkol je pro $k$ efektivně najít succ(k).

Řešení:

• Každý uzel má Finger Table (FT) obsahující $s$ záznamů ($s<m$).
• Záznamy v tabulce pro uzel $p$ vypočítáme následovně: $F{T}_p[i]=\text{succ}(p+2^{i-1})$
• Poté uzel $p$ předá dotaz na klíč k uzlu $q$ na indexu $j$ následovně:$F{T}_p[j]\le k<F{T}_p[j+1]$
  • pokud $p<k<F{T}_p[1]$, pak $q=F{T}_p[1]$ (je menší než první záznam v tabulce)
  • pokud $p<k\text{ and }k>F{T}_p[s]$, pak $q=F{T}_p[s]$ (je větší než všechny záznamy v tabulce)

Přidání uzlu do chord systému

• Proces, který zahrnuje aktualizaci struktury kruhu a redistribuci odpovědnosti za klíče tak, aby nový uzel byl začleněn do sítě.

Postup:

1. Nový uzel $p$, který se chystá připojit k síti, vygeneruje svůj jedinečný identifikátor (klíč).
2. Nový uzel musí najít svého “souseda” v kruhu Chord. tj. succ(p+1). Často provedeno pomocí vyhledávacího dotazu.
3. Každý uzel $q$ si drží aktualizovanou FT:

• $F{T}_q[1]=\text{succ}(q+1)-q$ ví, že první záznam odkazuje na následující uzel v kruhu.
• Každý uzel pravidelně ověřuje podmínku:
  • $q=\text{pred}(\text{succ}(q+1))$
  • Pokud je nepravdivá, pak $q<p<\text{succ}(q+1)$, je třeba nastavit $F{T}_q[1]=p$ (také je třeba ověřit, že $\text{pred}(p)=q$).
  • Musím opravit zbytek $FT$ ($q$ musí najít $\text{succ}(k)$, $k=q+2^{i-1}$)

Smazání (výpadek, havárie) uzlu

• Každý uzel $p$ testuje, zde $\text{pred}(p)$ je naživu.
• Pokud $q$ aktualizuje spojení na dalšího souseda v kruhu a zjistí, že $\text{pred}(q+1)$ není nastaven, pak $\text{pred}(q+1)=q$.

Předchozí otázka Následující otázka

Všechny otázky