Open Policy Agentの再帰処理を代替するgraph関数の使い方



日立アメリカ IoT Edge Lab　の大崎です。本記事は日立グループ OSS Advent Calendar 2021の第19日目です。
本記事は、Open Policy Agentで再帰処理を実装できない制限を回避して同等ロジックを実装可能とするgraph関数とその使い方を紹介します。

## Open Policy Agentとは

Open Policy Agent (以下OPA) は、汎用ポリシーエンジンです。Kubernetesでのリソース作成許可判定や、Webサービスの認可判定に使われています。

https://www.openpolicyagent.org/

Rego言語は、OPA用に開発されたポリシー記述言語です。Rego言語の特徴は、宣言的に記述することを目指して設計されていることが挙げられます。以下に記載されている通り、どう処理しなければいけないかを命令的に記述するより、何を判定すべきかを宣言的に記述することにフォーカスしています。したがって、簡潔にポリシーを実装できると考えられます。

> Rego is declarative so policy authors can focus on what queries should return rather than how queries should be executed. These queries are simpler and more concise than the equivalent in an imperative language.


https://www.openpolicyagent.org/docs/latest/policy-language/

## OPAの再帰処理に対する制限と、困るケース

Open Policy Agentとそのポリシー記述言語 Rego でたまに困るのは、「**再帰処理が書けない**」ということです。

どのようなケースで困るかを、以下に例で示します。
ポリシー開発者がお互いに依存関係がある複数サービスを持っていて、あるサービスAが依存するすべてのサービスを探したい、というケースを想定します。依存関係は、以下の`service_dependency`というJSONデータで定義されているとします。

```json
{
  "web": [
    "database"
  ],
  "database": [],
  "kafka": []
}
```

ここで、サービス名"web"を入力すると、依存するすべてのサービス(例えば["web", "database"])を見つけて出力する業務ロジックをルールとして実装することを想定します (OPAでは関数のような処理をルールで実装するのが一般的です。必要なら関数も書けます)

試しに以下のような`all_dependencies`ルールを実装します。

```rego
package main

service_dependency = {
  "web": [
    "database"
  ],
  "database": [],
  "kafka": []
}

all_dependencies[serviceName] = rtn {
  service = service_dependency[serviceName][_]
  rtn := {serviceName} + all_dependencies[service]
}

```

このファイルを`main.rego`というファイル名で保存して、同じフォルダ上で`opa`コマンドを使ってこのルールを評価してみます。結果として、`recursive`というエラーが出力され、このルールは`opa`で評価できないことがわかります。

```sh
opa eval -d . 'data.main.all_dependencies["web"]' --format pretty

1 error occurred: main.rego:11: rego_recursion_error: rule all_dependencies is recursive: all_dependencies -> all_dependencies
```

原因は、`all_dependencies`というルールの中で、以下の行で`all_dependencies`自身を使ってしまっていることです。`opa`は再帰処理を許していないため、このような実装を検知してエラーを出力するようになっています。

```rego
  rtn := {serviceName} + all_dependencies[service]
```

## 再帰処理の制限の回避策

ポリシー開発者のゴールは「依存するすべてのサービスを見つけたい」という業務ロジックでした。OPAは、再帰処理の実装をサポートしませんが、同等のゴールを達成するための別の手段を提供しています。その**別の手段が「graph」**です。

簡単にまとめると、for文のような再帰処理をユーザに実装させるのではなく、再帰処理で探索したいグラフ情報だけを定義します。あとの探索処理はOPAのgraphが隠蔽します。

以下のように`main.rego`の実装を変更します。

```rego
package main

service_dependency = {
  "web": [
    "database"
  ],
  "database": [],
  "kafka": []
}

# all_dependencies[serviceName] = rtn {
#   service = service_dependency[serviceName][_]
#   rtn := {serviceName} + all_dependencies[service]
# }

all_dependencies[serviceName] = rtn {
  service_dependency[serviceName]
  rtn := graph.reachable(service_dependency, {serviceName})
}
```

`graphl.reachable()`の部分が、OPAが提供するgraph関数です。さっそく再評価してみます。

```sh
opa eval -d . 'data.main.all_dependencies["web"]' --format pretty

[
  "web",
  "database"
]
```

正しく入力サービス名`"web"`に対して正しく依存するすべてのサービス名のリスト(`["web","database"]`)が出力されていることがわかります。再帰処理は使っていないためエラーは出力されません。


## 回避策が有効なユースケース

以下のような状況でgraph関数を使うことができます。

- 入れ子になっている階層の探索
  - たとえば組織Aの中に組織Bがあり、組織BにCさんが所属する場合には、所属関係はC->B->Aというリンクを持つ有向グラフで表すことができます。Cさんが所属する組織を洗い出す場合、グラフを探索し、すべての組織 BとAを見つけることができます。
- ワークフローのような相互依存関係があるジョブの探索
  - たとえばAが終了していないとBが開始できない、CはBの後、というような場合に、C->B->Aというリンクを張っておくと、これも有向グラフになります。Cを実行するための前提条件となるジョブを洗い出す場合、グラフを探索し、Cから接続するすべてのジョブ BとAを見つけることができます。

## graphの使い方

graphの仕様は下記ドキュメントに記載されています。

https://www.openpolicyagent.org/docs/latest/policy-reference/#graphs

以下では、具体的な手順を示します。

### 手順1. JSONでグラフ記述

OPAが読み込めるグラフデータのフォーマットは、以下のような形式のJSONです。"Parent node *"や"Child node *"はすべて名称等の文字列です。

```json
{
  "Parent node 1": [ "Child node 1", "Child node 2" ],
  "Parent node 2": [ "Child node 3", "Child node 4" ]
}
```

上記サンプルは、リンク元"Parent node 1"が2つのリンク先"Child node 1"と"Child node 2"に接続していることを表します。上記形式のデータが手元になくても、有向グラフのリンク元とリンク先という情報が何かしら含まれている他の形式のデータからOPA上で作り出してもかまいません。

OPAで上記のJSONのグラフ記述を読み込みます。

```rego
graph_data = {
  "Parent node 1": [ "Child node 1", "Child node 2" ],
  "Parent node 2": [ "Child node 3", "Child node 4" ]
}
```

### 手順2. グラフを探索

`graph.reachable`関数は、以下の引数を取ります。

| 引数|概要|
|-|-|
| 第1引数 (graph_data) | 手順1. で準備したグラフデータ |
| 第2引数 (start_points) | グラフ探索のスタート位置となるノード名のセット |

第2引数は以下のように定義します。

```rego
start_points = { "Parent node 1", "Parent node 2" }
```

関数を呼び出すと、返り値としてすべての到達可能なノード名のセットが取得できます。

```rego
nodes := graph.reachable(graph_data, start_points)
```

この他にも、`graph.walk`などの関数が用意されています。簡単に説明すると、`graph.walk(graph_data)`のような呼び方で、パスと呼ばれるグラフの要素の位置情報(たとえば`["web"]`)に対して、その要素の値(`"database"`)がマップされた辞書(key-value型オブジェクト)が返されます。(`{"[\"web\"]": "database"}`)

## まとめ

今回はOPAのgraph関数を紹介しました。
再帰処理を使って実装していたような業務ロジックを、OPAのグラフデータ探索用のgraph関数を用いて実装できました。組織やジョブなど、お互いに依存関係があるものをJSON形式で記述すれば、本手法が適用できます。
今回紹介したgraph関数は、for文などの再帰処理の記述を不要化したという点で、OPAの設計思想であった「命令的よりも宣言的」の最たる機能例だと私は考えます。