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)$のメッセージですむ。


関連研究

DNS, Freenet, Ohaha, Globe, OceanStore, Pastry, CAN


システムモデル



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].intervalfinger[k].start 〜 finger[k+1].start == finger[k.start] 〜 successor(k).start

関数は、find successor4

4.1 Overview

4.2 Consistent Hashing

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

4.3 Scalable Key Location

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

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

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

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

4.4 Node Join

nがjoinした時、6

  1. nのfinger tableとpredecessorを初期化する
  2. 既存のノードに対してfinger tableとpredecessorにnを追加する
  3. 上位にあるアプリケーションに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 および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



8 Conclusion

chordいいよー。


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

各ノードが持つべき情報

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);

}