Chord-Peer-to-peer-2001-usenix-Ion

Chord: A Scalable Peer-to-peer Lokup Service for Internet Applications

Ion Stoica, Rober Morris, David Karger, M. Frans Kasshoek, Hari balakrishnan

MIT Laboratory for Computer Science

SIGCOMM'01

概要

Chordという分散Lookupプロトコルをつくったぜ。

ChordはScalableである。

序章

一つのノードは$O(Log N)$の他のノードだけを知ってればいい。

$O(Log N)$のメッセージでlookupできる。

JoinやLeaveのときは、$O(Log^2 N)$のメッセージですむ。

システムモデル

Load Balance
Decentralization
Scalability
Availability
Flexible nameing

The Base Chord Protocol

名前	意味
k	キー
successor(k)	ID空間の中でkの次にあるノード
predecessor(k)	ID空間の中でkの前にあるノード
n.finger[k].start	(n + 2^(k-1)) mod 2^m
n.finger[k].node	ノードnのfinger Tableの中のi番目のエントリに格納されているノード = successor(finger[k].start)
n.finger[k].interval	finger[k].start ～ finger[k+1].start == finger[k.start] ～ successor(k).start

関数は、find successor⁴

4.1 Overview

4.2 Consistent Hashing

それぞれのノードおよびキーは、m-bit IDを持つ。このIDはノードの場合IPアドレスを、keyの場合key自体をSHA-1でハッシュすることで現在作っている。

キーkおよびそのデータは、successor(k)に格納される。
ノードが入ってきた場合、そのノードの次のノード(successor(n))に割り当てられていたデータが新しいノードに割り当てられる。。
kを持っているノードnがRingから抜ける場合、その一個次のノード (successrsor(n))にデータが委譲される。

4.3 Scalable Key Location

一つのノードはm個のエントリを持つFinger Tableを管理する。

そのi番目のエントリは最初のノードのID $s$ を持つ。

$s = successor(n + 2^(i-1))$

エントリには、キーとIPアドレスとポートナンバーが入っている。

4.4 Node Join

nがjoinした時、⁶

nのfinger tableとpredecessorを初期化する
既存のノードに対してfinger tableとpredecessorにnを追加する
上位にあるアプリケーションにnotifyする

nのfinger tableとpredecessorを初期化する

ノードnは、predecessorとfingerをn_dush(既存のノード。どうやってこれを知るのかは別問題)に、探すように頼んで知る。 (func : init_finger_table)

いくつか最適化の方法が示されている。

既存のノードに対してfinger tableとpredecessorにnを追加する (Updating fingers of existing nodes)

(func : update_finger_table)

Transferring keys

担当するkeyを委譲する。これは上位アプリケーションの仕事になるかもしれないが、プロトコルで行うのがいいだろう。

入ってきたノードnは、nの次のノードが持っているキーの一部を引き受ける。

従って、nは一つのノードとだけ通信すればいい。

5 Concurrent Operation and Failures

joinやLeave時の操作は、「積極的に」整合性を保つための動作である。これに対してStabilizationは、「受動的に」整合性を保つ。つまり、常に一定の間隔を置いて動いている。

Stabilizationは、Successorへのポインタを正しく維持することが目的である。

5.1 Stabilization

Figure 7 および⁷を参照の事。

joinでは、joinはn_dushにnの直後のsuccessorを探すようにたのむ

stabilizeでは、nはnのsuccessorにsuccessorのpredesessorであるpに、頼むようお願いする。なにを頼むかというと、pがnのsuccessorの代わりになってくれるよう頼む。これは、もしも、pが最近joinしてきたノードの場合である。

stabilizeは、nがすでに持っている、nのsuccessorに対して、notifyする。なにをnotifyするかというと、successorに、predecessorをnに変えるチャンスをあたえるように言う。successorは、nよりも近いpredecessorがないときだけ行う。

stabilizationでは、successor-listを管理する。

5.2 Failures and Replication

nがいなくなった場合、nをfigner_tableに含むノードは、nのsuccessorを探さなければならない。また、途中のqueryを混乱させてはならない。

一番重要となるのは、successorがちゃんと管理されていることである。そのために、すべてのノードは一番近いsuccessorをsuccessor-listに登録して、保持しておく必要がある。

stabilizationでは、このように、successor-listを管理する。

listとして管理しておけば、万が一successorがだめになったばあいでも、次の successorにききにいける。

6 シミュレーションと計測結果

割愛～

7 Future Work

Chordは、分割されてしまったchord ringを回復するすべはもたない。
dataはauthenticatedされてないとまずいよね。
AttackerがChord ringにいっぱいデータを入れられるのはよくないよね。
lookupが遅いのならば、別のインターネット上のホストに投げるという手もある。
lookup速度改善の別の手としては、サーバ選択がある。delayを計って、違うところにも投げる

8 Conclusion

chordいいよー。

実装上役に立つ(かもしれない)まとめ

各ノードが持つべき情報

finger_table;
key -> data;
sucessorの場所(ID,IP)
successor_list
predecessorの場所(ID, IP)

Finger Table

#DEFINE M_ID_MAXMUM 2^160;

finger_table[M_ID_MAXMUM] finger_entry;

struct finger_entry{
       struct sockaddr_in ip_address;
       int port_no;
       struct finger_entry *successor  ;
       struct finger_entry *predecessor;
       u_int160_t key; // IDおよびnode と等価

};

Lookup

lookup(u_int160_t key);

find successor from Fingure 4:

^[4]

__BEGIN_DECLS
struct finger_entry find_successor(u_int160_t id);
struct finger_entry find_predecessor(u_int160_t id);
struct finger_entry closest_preceding_finger(u_int160_t id);
__END_DECLS

struct finger_entry
find_successor(u_int160_t id){
   struct finger_entry n;
   n = find_predecessor(u_int160_t id);

   return n.predecessor;
};

struct finger_entry
find_predecessor(u_int160_t id){
  u_int160_t n_self_id, n2, successor_n;

  n2 = n_self_id; // ここでの n_self_idは自ノード自身

  while( n2 < id <= successor_n){
      
      n2 = find_closest_preceding_finger(id);
  } XXX ここらへんかなりあやしい

};

struct finger_entry
find_closest_preceding_finger(u_int160_t  id){
   for ( ; id == M_ID_MAXMUM ; id-- ){
       if( n_self_id < finger_table[i].node < id )
         return finger_table[i].node;
   }
   return n_self_id;
};

Join from figure 6

^[6]

__BEGIN_DECLS

__END_DECLS

void 
node_join(u_int160_t n_dush){
     int i;
     if(n_dush == TRUE){
	init_finger_table(n_dush);
	update_others();
	key_transfer(); // successorから、predecessor < id < nの範囲のデータを委譲する
     } else {// この場合 n_self_id しか世の中に存在しない
	for (i=1 ; i <=M_ID_MAXMUM ; i++){
	    finger_table[i].node = n_self_id;
	}
	predecessor = n_self_id;
     }
};


// n_dushはネットワーク上の既存の任意のノード
void
init_finger_table(u_int160_t n_dush){
    int i;			     

    finger_table[1].node = n_dush.find_successor(finger_table[1].start);
    
    n_self_id.predecessor = successor.predecessor;
    successor.predecessor = n_self_id;

    for (i=1 ; i <= (M_ID_MAXIMUM - 1) ; i++){
	if(n_self <= finger_table[i+1].start < finger_table[i].node){
	    finger_table[i+1].node = finger_table[i].node;
	} else {
	  finger_table[i+1].node = n_dush.find_successor(finger_table[i+1].start);

        }
    }
};

void
update_others(){
    int i;
    u_int160_t p;

    for (i=i ; i <= M_ID_MAXMUM ; i++){
	// i番目のfingerがnである最後のノードp を探す。
	p = find_predecessor(n_self_id - 2^(i-1));
	p.update_finger_table(n_self_id, i);
    }
};

void
update_finger_table(u_int160_t s , u_int160_t i){
    u_int160_t p;

    if( n_self_id <= s < finger_table[i].node ){
	finger_table[i].node = s;
	p = predecessor; nの次の最初のノードを入れる
	p.update_finger_table(s,i );
    }		      

}

Stabilization from Figure 7

^[7]


// n_dushはこれが自分のプロシージャだと思ったら
void
notify(u_int160_t n_dush){
  if ((predecessor == nil) || (predecessor < n_dush <= n_self_id)){
    predecessor = n_dush 
  }
}


// Finger_Tableを定期的に更新する
void
fix_fingers(){
  int i;

  i = Random index 

  finger_table[i].node = find_successor(finger_table[i].start);

}

Updated: 2004-08-09

Index