VIOPS - 現役高校生が実装するSkip Graph with Erlang
?
1 like?6,158 views
Convert to study materialsBETA
Transform any presentation into ready-made study material—select from outputs like summaries, definitions, and practice questions.
VIOPS - 現役高校生が実装するSkip Graph with Erlang
- 1. 現役高校生が実装するSkip Graph with Erlang 千々和 大輝 ( @_daiki )
- 2. 自己紹介 千々和 大輝
- 3. P2P を応用した分散処理 P2P 匿名掲示板
- 4. key-value store Twitter: _daiki
- 8. 分散ハッシュテーブルや Skip Graph など 非構造化オーバーレイ 初期の P2P
- 9. Gnutella や Winny など
- 12. 范囲検索が不可能
- 14. DHT とは異なり，キーはそのまま利用される -> 顺序性が保たれる
- 15. -> キーによる範囲検索が可能に！ 挿入 / 探索速度は DHT に劣らず
- 16. Skip List
- 19. 軽量プロセス
- 20. 透过的な分散処理
- 21. 强力な耐障害性を持つ
- 22. OTP(Open Telecom Platform) 似たようなコードの简略化
- 25. gen_server
- 26. gen_event
- 27. etc......
- 28. コード例
- 29. 説明おわり
- 30. Erlang/OTPによる恩恵 OTP (gen_server) 障害発生时は自动的に再起动
- 31. 透过的な分散処理
- 32. コードの一贯性
- 33. Concurrent Join(並行Join)の実装 複数の Join 処理を同期的に実行 複雑
- 34. バグが入りやすい
- 35. 不整合の発生をなるべく防ぐ
- 36. デッドロックの恐れアリ
- 37. 今後の課題 Concurrent Join の改良
- 40. C++ に移植
- 41. ありがとうございました
Editor's Notes
- #2: Skip Graph written in Erlangというテーマで発表させて頂きます．よろしくお願いします．
- #3: 僕について知らない人がほとんどだと思いますので，少し自己紹介をしたいと思います． 僕は以前から，P2Pを応用した分散処理システムに興味を持っておりまして，P2P匿名掲示板などを作ったことがあります．最近は，クラウドコンピューティングの基盤技術として注目されているキーバリュー型データストアの実装に取り組んでいます．
- #4: 今回は Erlang による Skip Graph の実装を紹介するつもりなのですが，その前に，この二つについて簡単に説明したいと思います．
- #5: まず， P2P 構造化オーバーレイのひとつである SkipGraph から先に説明します．
- #6: ピュアP2Pは一般に，構造化オーバーレイと非構造化オーバーレイの二つに分類されています． 構造化オーバーレイとは，ある規則に従って構造化されたP2Pネットワークのことで，代表的なものには分散ハッシュテーブルやSkip Graphなどがあります． 対して非構造化オーバーレイは構造化オーバーレイではないP2Pネットワークを指す言葉で，初期のP2Pネットワーク，代表的なものとしてはGnutellaやWinnyのネットワークがこれにあたります．
- #7: Skip Graphの利点を理解するには，分散ハッシュテーブルについて知っておく必要があります．これはその名の通り「分散化されたハッシュテーブル」で，一般的なハッシュテーブルアルゴリズムと同じように，ハッシュ値を利用して値の探索や挿入を行います． 実行効率については申し分ないこのDHTですが，欠点の一つに，范囲検索が不可能である点が挙げられます． これはハッシュ値の性質上仕方の無いことなのですが，この欠点を克服することができるシステムが，今から紹介するSkip Graphなのです．
- #8: スキップリストアルゴリズムが元となっているこのSkip Graphの場合，キーはハッシュ値などに変換されることなくそのまま利用されるので，範囲検索が可能になっています． また，挿入や探索の速度は，DHTと比べて全く劣っていません．
- #9: これはスキップリストアルゴリズムの図なのですが，Skip Graphもこのような感じだと捉えていただければ結構です． 見て分かる通りルーティングが階層で分けられており，上にいくほど粒度が大きくなっているという特徴を持っています． この特徴のおかげで，キーに特別な操作を加えないまま，DHTに劣らない速度を実現することができているのです．
- #10: 一通り Skip Graph について説明したところで，次は Erlang について説明しようと思います．
- #11: Erlangとは，エリクソン社が開発した並行指向の関数型言語で，OSから独立した軽量プロセスを大量に生成することができます． これらのプロセスは，ネットワーク先のノード上で動作しているモノとローカルで動作しているモノを区別することなく，透過的にメッセージング処理を行うことができるという特徴を持っています． さらに，Erlangを使う上での最も大きな利点として，OTPの存在があります．
- #12: OTP，Open Telecom Platformとは，似たようなコードの简略化を目的とする，汎用的な動作をまとめたライブラリです．煩わしい処理などはこのライブラリによってブラックボックス化されており，開発者は特に意識しなくとも，読みやすく実用性のあるシステムを実装することができます． supervisorビヘイビアやgeneric serverビヘイビアなど，様々な目的に合わせたものが用意されているので，自分の実装したいものに最適なのを選択すれば，強力な道具となるだろうと思います．
- #13: 具体的なコード例を見てみましょう． これは，クイックソートの単純な実装例です． Erlangの最大の特徴である軽量プロセスは利用されていないものの，大体のイメージは掴めると思います．
- #14: さて，Skip GraphとErlangについての簡単な説明が終わったところで，実装の紹介に入ろうかと思います．
- #15: Erlangで実装するにあたって，OTPのひとつである，generic serverビヘイビアがとても役に立ちました． このgeneric serverビヘイビアを利用して実装されたプログラムは，監視ツリーに追加されたサーバプロセスを生成します．これにより，プログラムのバグなどで障害が発生しても，すぐに再起動させるなどの復旧処理の実装を簡単に行えるようになります． さらに先程説明したように，Erlangでのプロセス間通信は，たとえ分散環境であろうと透過的に行うことが可能なため，このサーバプロセスを受け渡しすることにより，メッセージング処理を用意に行うことができました． また，generic serverを利用する際は予め決められたコールバック関数を定義するので，他の開発者が見ても人目で構造がわかるようになっています．
- #16: 次にSkip Graph実装にあたって苦労した部分は，Concurrent Joinです． まず第一に，複雑でバグが入り込みやすい，というのがあります．これは，見落としていた条件があるなどが原因であることが多いです． 第二に，不整合の発生をなるべく防ぐ必要があります．これはネットワーク負荷をできるだけ小さくするためです．これを防ぐにあたって，generic serverビヘイビアが一度に一つしか処理を行わない，つまりJoin処理中は他のJoin処理がロックされるという特徴を利用して実装を行いました． 最後にデッドロックの恐れアリ，というのも，generic serverビヘイビアのこの性質に起因するものです．これは，自ノードと他ノードを区別することで解決しましたが，まだ完全ではありません．
- #17: 最後に，今後の課題をまとめてみました． 「Concurrent Joinの改良」 「あるノードがいきなり死んだ场合の対処」 「より多くのkey-valueペアの保持を可能に」 「C++へ移植」 とりあえずはこれらの達成を目標にして日々精進していきたいと思います．
- #18: 长い间ご清聴いただきありがとうございました．僕も恳亲会に参加する予定なので，质问やツッコミがある方は気軽に话しかけてほしいと思います．