Basho Japanにて構造化オーバレイアルゴリズムGFRT-Chordの仕組みを解説してきました

GFRT-Chordは、構造化オーバレイと呼ばれるP2P型ネットワークを構築するアルゴリズムのひとつであり、あらかじめマシン群をグループとして指定しておくと、グループをまたぐ回数が削減されるように経路を構築する特長があります。

この特長により、一般的な構造化オーバレイアルゴリズムの問題である、スイッチやISP、データセンターをまたぐ通信の増加を大幅に抑制します。そしてその特長は証明によって裏付けられています。

このとき、GFRT-Chordでは経路表サイズを任意に増減可能であり、ノード数が少ない状況においても効率の良いルーティングが可能で、さまざまなサイズのネットワークやグループ数に対応することができます。

例えばシステム構築直後の小規模なネットワークや、グループの数が極端に多い（少ない）状況においても安定して性能を発揮することができます。あらかじめグループ数やノード数を知る必要が無く、未知で構いません。

GFRT-Chordは、オープンソースのキーバリューストアScalarisに実装されており、公開されています（自分が実装したのではなく、気が付いたら実装されていました）。

昨年末、研究室にBashoの方々をお招きして、お互いに発表し合う技術交流会を開催しました。

そのとき、自分に割り当てられた発表時間がとても短くなってしまい、アルゴリズムの仕組みをほとんど紹介できなかったのですが、@itawasa さんが興味を持ってくださって、Basho Japanのオフィスにて、アルゴリズムを細かく解説できることになりました。

Bashoは、RiakというKVSを開発しています。Riakの場合、構造化オーバレイと通常呼ばれるものそのものを利用しているわけではありません。しかし、構造化オーバレイの特殊な場合を利用していると考えることができ、GFRT-Chordはちょうどその特殊な場合と、通常の構造化オーバレイとの間の橋渡しができるようなアルゴリズムです。RiakとGFRT-Chordはそんな関係にあると言えます（あえて言えば）。

こんな経緯で、Basho Japanオフィスにお邪魔してきました。

２時間程度かけて、構造化オーバレイのあまり説明されることのない基本的な特徴・性質から、GFRT-ChordのベースになっているFRT-Chordアルゴリズムの詳細、GFRT-Chordそのものの仕組みや挙動について説明しました。

普段はなかなか話すことのない、アルゴリズムの細かいところまで話すことができました。アルゴリズムの詳細な動作を、かなりしっかりと理解していただけたようで大満足でした。

アルゴリズムの詳細に興味がありましたら、説明に伺えるかも知れません。声をおかけください（知り合いか知り合い経由に限る）。

このアルゴリズムは、今週末に開かれる情報科学若手の会冬の陣2014というイベントでも発表する予定です。発表時間の都合上、概要を話す程度になると思います。

@did2memo 先生がBashoの飯につられているだと…

— Mr. Fiber (@repeatedly) 2014, 1月 22

別にそういうわけじゃ（笑

すごく古いスライドですが、一応スライドがあります（GFRT-Chordという名前にする前でLFRT-Chordという名前です）。

論文は「Flexible Routing Tables: Designing Routing Algorithms for Overlays Based on a Total Order on a Routing Table Set」で検索してみてください。個人ページで無料DL可能にしてあります。