第5回 分散システム本読書会名前付け / Naming 後半@nishio_dens2013/05/31   第5回 分散システム本読書会  
5.4 属性ベース名前付け•  フラットな名前付け、構造化された名前付け  –  多くの場合一つのエンティティを参照するために利用される    •  属性ベース名前付けシステムの特徴  –  エンティティを(属性,  値)  の組で...
5.4.2 階層化された実装: LDAP (1)•  特徴  –  構造化された名前付けと属性ベース名前付けを組み合わせている    2013/05/31   第5回 分散システム本読書会   3  /  8  
5.4.2 階層化された実装 : LDAP (2)•  LDAPの特徴  –  基本的にはDNSのような名前付けサービスと同じ  –  DNSと異なる点は、数多くの探索エペレーションをサポートしている  •  探索の例  –  Vrij...
LDAPの課題: スケーラビリティ•  大規模なディレクトリを対象とする場合  –  ディレクトリ情報木(DIT)を分割し、複数サーバへ分割する  –  検索条件によっては、一つの結果を得るために複数のノードにアクセスする必要があり、スケー...
5.4.3 非集中型の実装 (1)•  P2Pシステムによる属性ベース名前付けシステムの実装  –  スケーラビリティの問題を解決したい  –  課題は、探索オペレーションが効率的に行われるように、  (属性,  値)  の組を効率的...
5.4.3 分散ハッシュテーブルへのマッピング•  各経路に対するハッシュの割当  –  h1  :  hash(type-­‐book)  –  h2:  hash(type-­‐book-­‐author)  –  h3:  ...
5.4.4 セマンティックオーバーレイネットワーク•  非構造化オーバーレイネットワークで効率的な探索を実現  するには?  –  ノードに、意味的に近い情報を持つ近隣ノードへのリンクを持たせる  (クラスタリング?)  –  情報を検...
of 8

Naming 2

分散システム本読書会 第5回資料です
Published on: Mar 3, 2016
Source: www.slideshare.net


Transcripts - Naming 2

  • 1. 第5回 分散システム本読書会名前付け / Naming 後半@nishio_dens2013/05/31   第5回 分散システム本読書会
  • 2. 5.4 属性ベース名前付け•  フラットな名前付け、構造化された名前付け  –  多くの場合一つのエンティティを参照するために利用される    •  属性ベース名前付けシステムの特徴  –  エンティティを(属性,  値)  の組で記述する  –  エンティティは探索に利用可能な属性セットを保持している–  ユーザが興味のあるエンティティの属性を指定することで、  エンティティを絞り込む  –  ユーザの検索条件に一致した一つ以上のエンティティを返す  名前付けシステム      属性ベース名前付けシステムは  ディレクトリサービスとも呼ばれる  2013/05/31   第5回 分散システム本読書会   2  /  8
  • 3. 5.4.2 階層化された実装: LDAP (1)•  特徴  –  構造化された名前付けと属性ベース名前付けを組み合わせている    2013/05/31   第5回 分散システム本読書会   3  /  8
  • 4. 5.4.2 階層化された実装 : LDAP (2)•  LDAPの特徴  –  基本的にはDNSのような名前付けサービスと同じ  –  DNSと異なる点は、数多くの探索エペレーションをサポートしている  •  探索の例  –  Vrije  大学における、すべての主要なサーバのリストが欲しい  •  探索条件  –  Country  (C)  =  NL  –  Organization  (O)  =  Vrije  Universiteit  –  Organization  Unit  (OU)  =  *  –  Common  Name  (CN)  =  Main  Server  •  [Howes,  1997]  において定義されている表記法での記述  –  Answer  =  search(“&(C=NL)(O  =  Vrije  Universiteit)(OU=*)  (CN=Main  Server)”)  2013/05/31   第5回 分散システム本読書会   4  /  8
  • 5. LDAPの課題: スケーラビリティ•  大規模なディレクトリを対象とする場合  –  ディレクトリ情報木(DIT)を分割し、複数サーバへ分割する  –  検索条件によっては、一つの結果を得るために複数のノードにアクセスする必要があり、スケーラビリティに問題がある  •  Active  Directoryが行っている解決策  –  最初に探索されるグローバルなインデックスサーバ(グローバルカタログ)を配置している  –  インデックスサーバに最初にアクセスし、どのLDAPドメインを次に探索すればよいかを決定する  ※  Active  Directory  •  Microsoftのディレクトリサービスシステム  2013/05/31   第5回 分散システム本読書会   5  /  8
  • 6. 5.4.3 非集中型の実装 (1)•  P2Pシステムによる属性ベース名前付けシステムの実装  –  スケーラビリティの問題を解決したい  –  課題は、探索オペレーションが効率的に行われるように、  (属性,  値)  の組を効率的にマッピングすること  •  分散ハッシュテーブル(DHT)へのマッピング  –  DHTを用いることで、特定のサーバ(インデックスサーバ等)を  用いること無く探索が行える  –  属性をDHTシステムで検索可能なキーの集合に変換する    2013/05/31   第5回 分散システム本読書会   6  /  8
  • 7. 5.4.3 分散ハッシュテーブルへのマッピング•  各経路に対するハッシュの割当  –  h1  :  hash(type-­‐book)  –  h2:  hash(type-­‐book-­‐author)  –  h3:  hash(type-­‐book-­‐author-­‐Tolkien)  –  h4:  hash(type-­‐book-­‐title)  –  h5:  hash(type-­‐book-­‐title-­‐LOTR)  –  h6:  hash(genre-­‐fantasy)  •  上記で割り当てられたハッシュに対応するノードが、リソースを  保持している(6ノードが実際のデータを保持)  •  探索の例  2013/05/31   第5回 分散システム本読書会   7  /  8  h1:  hash(type-­‐book)  h2:  hash(type-­‐book-­‐author)  h3:  hash(type-­‐book-­‐author-­‐Tolkien)  h1,  h2,  h3  のhash値を持つノードにアクセスして、データ取得検索条件:          Tolkien  によって          書かれた書籍名を返せ
  • 8. 5.4.4 セマンティックオーバーレイネットワーク•  非構造化オーバーレイネットワークで効率的な探索を実現  するには?  –  ノードに、意味的に近い情報を持つ近隣ノードへのリンクを持たせる  (クラスタリング?)  –  情報を検索するときは、まずその情報を持っているであろうノード群に問い合わせる  •  意味的に近いノードのリストを構築するには?  –  [Voulgaris  and  van  Steen,  2005]  では、単純なセマンティック近傍関数を用いる手法が提案されている  –  単に互いのノードが保持している共通のファイル数をカウントして、その値を元に近傍ノードとするかどうかを判定している  2013/05/31   第5回 分散システム本読書会   8  /  8

Related Documents