読者です 読者をやめる 読者になる 読者になる

Coursera で "Cloud Computing Concepts, Part 1" Week 3 を受講した

Coursera

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
  • 特徴
    • ノードのアドレスを算出するためにコンシステントハッシュ法を使う
    • SHA-1(ip, port) → 160 bit でユニーク性を保証する
    • 仮想リングを使う
  • 用語解説
    • successor : リング上で時計回りに見た次のノードのこと
    • predecessor : リング上で時計回りに見た前のノードのこと
    • finger table : キーを探索するときのノードの問い合わせ先一覧
  • finger table は 線形探索を避けるために O(log N) で探索できる
    • ( n + 2i ) mod 2m
      • n : ノード
      • i : エントリー番号
      • m : 空間数
  • ファイル配置
    • ファイルも 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 の理解を整理するために資料を作った.以下の記事に載せてある!

kakakakakku.hatenablog.com