Coursera
Coursera でイリノイ大学の講義 "Cloud Computing Concepts, Part 1" を受講してる！
Week 3 に関して個人的な勉強メモをまとめた．
Week 3 : 期間
- 2016/09/12 - 2016/09/18
Week 3 : アジェンダ
- Week 3: P2P Systems
- Overview
- Lesson: P2P Systems
- P2P Systems Introduction
- Napster
- Gnutella
- FastTrack and BitTorrent
- Chord
- Failures in Chord
- Pastry
- Kelips
- Interview
- Homework
Lesson: P2P Systems
P2P Systems Introduction
- P2P 技術は最近の KVS や NoSQL に応用されている
- なぜ P2P を学ぶのか？
- 分散システムは大量のノードをスケールする前提で作られている
- 重要なケーススタディになる
- クラウドコンピューティングにも応用されている
Napster
- ファイル交換サービス
- Napster.com はファイル自体を保持しない
- あくまでディレクトリ情報だけを持つ
{ filename, ip_address, portnum }
Gnutella
- ノーテラ or グヌーテラと呼ぶ
- AOLが作った
- Gnutella クライアントはサーバントと呼ばれる
- Napsterと違って個々に繋がる P2P
- 大きく5つのメッセージタイプがある
- Query / QueryHit / Ping / Pong / Push
- ノーテラのクエリ伝播は TTL で制御する
- http で range を返す
- 途中で止まったときに途中から再開させるため
FastTrack and BitTorrent
- FastTrack
- Gnutella と Napster のハイブリッド
- Kazaa / KazaaLite / Grokster を使っている
- スーパーノードという概念がある
- BitTreent
- Tracker がディレクトリを持つ
- Tracker は Peer とハートビートをしている
- Peer には二種類ある
- 一個は seed フルデータを持っている
- leecher はブロックの断片を持っている
Chord
- DHT (Distributed Hash Table)
- 日本語だと「分散ハッシュテーブル」
- Chord
- MIT が考えたアルゴリズム
- https://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf
- 近年の NoSQL 実装でよく使われている
- 特徴
- ノードのアドレスを算出するためにコンシステントハッシュ法を使う
- SHA-1(ip, port) → 160 bit でユニーク性を保証する
- 仮想リングを使う
- 用語解説
- successor : リング上で時計回りに見た次のノードのこと
- predecessor : リング上で時計回りに見た前のノードのこと
- finger table : キーを探索するときのノードの問い合わせ先一覧
- finger table は 線形探索を避けるために O(log N) で探索できる
- ( n + 2i ) mod 2m
- n : ノード
- i : エントリー番号
- m : 空間数
- ( n + 2i ) mod 2m
- ファイル配置
- ファイルも SHA-1(filename) でノードと同じ名前空間に配置される
- ファイルのハッシュ値よりも大きく，1番近接したハッシュ値を持つノードにストアされる
- ようするに，リング上で言えば「次のノード」
- 関連リンク
)
Failures in Chord
- ノード障害の場合
- Node 16 → Node 32 → Node 45 となっているときに Node 32 が落ちたとすると
- Node 16 → Node 45 とする
- 実際には r = 2log(N) 個のノードに影響する（6ノードとすると約1.5ノードに影響する）
- ノード追加の場合
- 追加された位置の一個前のノードの successor を更新する
- 追加されたノードの finger table を生成する
- 周期的に全ノードの finger table を再生成する
Pastry
- ペイストリーも Chord と同様にノードに id を振る
- ただし近接ノードのメンテナンス方法が Chrod とは異なる
- リーフセット (Leaf Set)
- それぞれのノードは successors と predecessors を知っている
- プレフィックスマッチングを使ったルーティングテーブル
- Pastry のルーティングコストは O(log(N)) となる
- N : ノード数
Kelips
- Chord や Pastry と違って仮想リングは使わない
- アフィニティグループを使う
- 仮想グループ
- ペアは同じグループのペアのことは知っている
Chord をまとめてみた
Week 3 で学んだ Chord の理解を整理するために資料を作った．以下の記事に載せてある！
