TuGraph Analyticsのストリームグラフ計算論文が国際トップ会議SIGMODに選出されました

GeaFlow（ブランド名TuGraph-Analytics）が正式にオープンソース化されました。皆さん、ぜひフォローしてください！ 

GitHubで私たちにスターを与えることを忘れないでください👉[https://github.com/TuGraph-family/tugraph-analytics](https://github.com/TuGraph-family/tugraph-analytics)

よりエキサイティングなコンテンツについては、ブログをフォローしてください [https://geaflow.github.io/](https://geaflow.github.io/)

----

Tips：この記事はChatGPT 3.5によって中国語から日本語に翻訳されました。不正確な点がある場合はお詫び申し上げます。




6月18日から23日まで、2023年のACM SIGMODデータベース国際会議がアメリカのシアトルで開催され、Ant Stream Graph Computing Teamの論文が選出されました。

ACM SIGMODは、アメリカコンピュータ協会（ACM）のデータ管理専門委員会（SIGMOD）によって主催され、VLDB、ICDEと並ぶデータベース業界のトップレベルの学術会議です。

この会議に収録された論文は、データベース領域の最高水準を代表し、将来のデータベース技術の発展における重要な指針となります。

Ant Stream Graph Computing Teamの論文「GeaFlow: A Graph Extended and Accelerated Dataflow System」は、SIGMOD 2023に収録され、Ant Stream Graph Computing Teamの成果は産業界だけでなく、学術界でもさらに認められています。

![tu1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3521915/f9ae60b6-246c-480a-26d3-88fc09d36f11.png)


画像の注釈：GeaFlowはAnt Stream Graph Computing Engine TuGraph Analyticsの内部コード名であり、本文では論文で使用されている "GeaFlow"を引き続き使用し、読者が対応できるようにします。

画像のプロジェクトコードのアドレス：[https://github.com/TuGraph-family/tugraph-analytics](https://github.com/TuGraph-family/tugraph-analytics)

## 背景紹介

ストリーム処理技術の発展とともに、監視、推奨、広告など、さまざまなアプリケーション領域で広く使用されています。既存のストリーム処理システムは、ウィンドウ型のクエリセットの処理に非常に効果的であることが証明されていますが、グラフ構造データなどのより複雑なデータ構造に直面すると、多くの課題が発生します。

まず、ストリーム計算では、特に動的に変化するデータに対して、一つのデータが他のストリームから対応するデータを見つけるために、データ物化とシャッフルを含む非常に高コストなジョイン操作が必要です。ストリームグラフ計算では通常、数百回から数千回のグラフイテレーションが必要で、対応するストリーム計算は数百回から数千回のジョイン操作となります。

次に、ストリーム計算では、データ集約の中間状態は通常、固定ウィンドウまたはスライディングウィンドウ内で、ウィンドウの元のデータサイズよりもはるかに小さいデータ量を維持する必要があります。また、ウィンドウは通常、特に大きくなりません。一方、ストリームグラフ計算では、数ヶ月または数年にわたるデータを追跡する必要がある、長くて動的に変化するグラフを維持する必要があります。

これらの問題を解決するために、Ant Stream Graph Computing Teamは、ストリームグラフ計算エンジンGeaFlowを開発・設計しました。GeaFlowは、ストリームグラフのダイナミックな分析、トラバース、計算の要求をうまく解決し、長いウィンドウのデータグラフのデータ状態管理、DSL化されたストリームグラフのタスク開発などの特徴をサポートしています。

GeaFlowは、Antのリスクコントロール、マーケティングなどのシナリオで広く利用され、また、シングルデーイベントでの大規模な成功を収めています。以下で、GeaFlowの実行シーンと内部技術について詳しく説明します。

## 実行シーン

グラフデータベースとは異なり、GeaFlowが解決するのは、高スループットシナリオでの複雑なグラフ分析と計算の問題です。例えば、深度グラフトラバース、サブグラフマッチング、全体グラフ分析などがあります。GeaFlowは、ストリームイベント駆動の方法で計算とクエリを行い、クエリの最適化技術を使用してクエリのマージと加速を行います。以下で、GeaFlowの実行シーンについて説明します。

![tu2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3521915/95fa3e3b-b466-5669-0edc-747d88fe3433.png)


<center>（図1）</center>

図1は、典型的なGeaflowデータフローグラフを表しています。全体のパイプラインから見ると、Geaflowはストリーミングで構築されるデータグラフを行います。データグラフには、メッセージキューやログシステムなど、さまざまなタイプのデータが含まれることがあります。データはETL処理を経て、最終的にグラフストレージに書き込まれるポイントとエッジに変換されます。グラフストレージは定期的にチェックポイントを行い、ExactlyOnceを保証します。

同時に、Geaflowは増分および変化するデータに基づいてグラフ計算を駆動します。たとえば、逆キャッシュシナリオでは、継続的に支払いが行われるユーザーIDなどです。他の一般的なストリーム計算システムとは異なり、グラフ計算は反復計算であるため、GeaFlowはストリーミングリンク上で反復グラフ処理をサポートしています。最後に、グラフ計算の出力データを加工処理することができます。例えば、ウィンドウのTopN計算を行った後に、出力することができます。

## アーキテクチャ設計

上記のシナリオをサポートするために、Geaflowは以下のようなアーキテクチャ設計を行っています：

![tu3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3521915/d357cefb-8b27-22cd-ae93-671bb8094061.png)


<center>（図2）</center>

上記のシナリオをサポートするために、Geaflowは以下のようなアーキテクチャ設計を行いました：

### Hybird DSL
GeaFlowは、表とグラフの意味を革新的に統合し、表DSL SQLとグラフDSL Gremlinを利用して、リアルタイムグラフ計算タスクをSQLのようなプログラミングスタイルで簡単に記述できるようにしました。同時に、クエリプランニングでは、論理実行計画と物理実行計画に対してグラフの意味論の最適化を行い、複数のクエリ文を結合クエリなどで最適化します。

### Core API
GeaFlowは、状態意味論を持つ演算子セットを設計し、複数のストリームやグラフの意味論をサポートしています。これには、標準のストリーム演算子や頂点/エッジ指向のグラフ演算子が含まれます。グラフ演算子では、ユーザーがさまざまなグラフ構造をサポートする優れたプログラミングモデルを構築し、セッションを導入して並行グラフクエリを処理します。

### Streaming Engine
GeaFlowのランタイムは、分散DAG実行レイヤーであり、柔軟にストリームグラフの意味論を切り替えることができます。また、マルチクエリ最適化を効率的にサポートします。実行中には、オフヒープメモリ管理、グラフ状態の共有、バッチ実行などの技術を使用して最適化を行い、全体のスループットを大幅に向上させます。

### GeaFlow State
GeaFlowの状態ストレージは、ストリームやグラフデータの保存とアクセスに使用されます。キーバリュー意味論の状態やグラフ意味論の状態を使用できます。グラフ状態では、効率的なキーレイアウトを設計し、頂点とエッジのアクセスを高速化し、さまざまなバックエンドに対応します。同時に、グラフネイティブなバックエンドも開発しており、CSRのようなインデックス構造と計算とストレージの分離アーキテクチャを活用して、より効率的なグラフアクセスと柔軟なスケーリングをサポートしています。



## 実験結果

ここでは、Geaflowと他のストリーム計算エンジンとの比較を示します。

K-Hop Neighborhoodシナリオでは、LiveJournalとTwitter-2010という2つの公開データセットを使用して、Geaflow、Flink、およびDifferential Dataflowを比較しました。実験は8つのコンテナを持つクラスタでテストされ、各コンテナの仕様は8c16Gです。

実装により、次のことがわかります：

複数のホップのトラバースシナリオでは、GeaFlowのメモリ全体は安定しており、反復の深さによって大幅に増加することはありません。一方、他の一般的なストリーム計算エンジンでは、著しいメモリの増加があり、ホップ数が多すぎるとメモリが不足する可能性があります。

GeaFlowは、典型的なストリームグラフシナリオに対して、Joinを基にした一般的なグラフ計算エンジンに比べて、スループットが大幅に向上しています。

![tu4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3521915/e33e7f67-80ec-361a-d704-0700dd8f118f.png)


<center>（図3）</center>

グラフクエリのシミュレーションシナリオでは、クエリの実行時間と同時実行されるクエリの数の関係を検証しました。

図4では、バッチ内の並行クエリデータ量が増加するに従い、実行時間の増加は特に顕著ではありません。40個のクエリを統合した場合、時間はわずかに22.7％増加し、32.6倍の高速化効果が得られることがわかります。

![tu5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3521915/e5be70e3-37da-d9bc-9703-18819e904210.png)



<center>（図4）</center>

## まとめと計画

Geaflowは、6年前にアリババのビジネスシナリオでの試みから生まれました。当時、既存のストリーム処理アーキテクチャはストリームグラフ処理には適していないことがわかりました。2年の孵化期間を経て、Geaflowはアリババの反詐欺ビジネスをサポートし、2018年のシングルズデーイベントでは秒間数千万件のイベントを処理する高スループットを実現しました。これらのビジネスにおけるストリームグラフのクエリと分析の効果は非常に顕著であり、金融シナリオでのストリームグラフ処理が多くの助けを提供できることを証明しました。その後、DSLのサポートを導入し、ユーザーの開発コストをさらに削減しました。SQL + Gremlinの組み合わせを選択し、クエリオプティマイザーを改良し続けた結果、多くのユーザーがDSLを使用してグラフ計算シナリオをクエリや分析するようになりました。現在、Geaflowはアリババで最も人気のある計算エンジンの一つとなっています。

今後、Geaflowのさらなる発展を以下の領域で計画しています：

* インクリメンタルセマンティクスを持つグラフ計算演算子など、さらに多くのグラフセマンティクスを統合すること。

* OpenCypher、GQL、SQL/PGQなど、より多くの宣言型のグラフクエリ言語を探求すること。同時に、CBO最適化や自動チューニングなどの機能を組み込むこと。

* Rust/C++などの言語を使用して実行エンジンを改良し、パフォーマンスをさらに向上させること。


----
GeaFlow（ブランド名TuGraph-Analytics）が正式にオープンソース化されました。

スターを与えてくれてありがとうございます！

GitHub👉[https://github.com/TuGraph-family/tugraph-analytics](https://github.com/TuGraph-family/tugraph-analytics)

よりエキサイティングなコンテンツについては、ブログをフォローしてください  [https://geaflow.github.io/](https://geaflow.github.io/)