トポロジカルソートを用いて機能実装をした話

フィーチャーフラグマネジメント・A/Bテストプラットフォーム「Bucketeer」チームにてバックエンドエンジニアをしている小野です。

最近、Bucketeer では Feature Flag Dependencies という機能がリリースされました。この機能の内部実装にはトポロジカルソートが用いられており、本稿では開発者である筆者がアルゴリズムの選定理由を含めた経緯についてお話ししていきます。

想定読者

本稿では、以下のような読者を想定しておりフィーチャーフラグの運用方法についてのお話しはしません。

Bucketeer の内部実装の仕組みについて知りたい
トポロジカルソートについて知りたい
アルゴリズムの選定理由について知りたい

Bucketeer について

先述したように、Bucketeer ではフィーチャーフラグをまとめて管理できます。以下に例を示します。

この設定の場合、ユーザーの ID が "foo" の時は true を返し、"bar"、"baz" の時は false を返します。必要に応じて GUI で簡単にフラグの値を変えることができます。

Feature Flag Dependencies とは

Feature Flag Dependencies は対象となるフィーチャーフラグそのものを評価対象とできる機能です。

例えば、フィーチャーフラグAを評価した際に返ってきた値が true である時のみフィーチャーフラグBを評価するというものです。もし、フィーチャーフラグAの値が false だった（期待したものと異なる）場合はフィーチャーフラグBを評価せず、デフォルトの値を返すような仕組みになっています。

少しの違いはあるものの、代表的なフィーチャーフラグマネジメントサービスには以下のようにサポートされている機能になっています。

実装するにあたっての要件

要件は以下のようになっています。

前提条件となっているフィーチャーフラグは全て論理演算子における AND として評価する
フィーチャーフラグ間でサイクルがあってはいけない
前提条件として設定できるフィーチャーフラグの数に制限は設けない

要件をもとに、フィーチャーフラグを頂点としてデータ構造を考えてみると、各辺に向きがあり、閉路を持たないグラフであることが分かります。このようなグラフは有向非巡回グラフ（以下、DAG）と呼ばれ、タスク間での優先順位などを表現する際に用いられるものなっています。

実装方針

データ構造を踏まえて、以下の実装方針に決めました。

トポロジカルソートを行い、先に評価しなければならないフィーチャーフラグから先頭に並んでいる配列を作る
配列を用いて順に評価していく

トポロジカルソートとは

トポロジカルソートは DAG の各頂点を辺の向きに合わせてソートするアルゴリズムです。以下のようなグラフがあったとします。

辺の向きに合わせてソートすると、以下のようになります。

ソート順は一意とは限らず、複数あることもあります。

今回実装したトポロジカルソートについての解説

それでは、実際の実装について紹介をしていきます。トポロジカルソートとは辺の向きに合わせてソートするものだと先ほど述べました。

しかし、今回のケースにおいては、前提条件になっているフィーチャーフラグから評価をする必要があるので、先ほどのグラフを用いると以下のようにソートする必要があります。

注意したいのは、先述したトポロジカルソートとは逆向きにソートしている点です。辺の向きに合わせてソートすると先ほど述べましたが、今回は辺の向きと逆順でソートするようにしています。

実際に Bucketeer に書かれているコードを引用します。

func TopologicalSort(features []*featureproto.Feature) ([]*featureproto.Feature, error) {
	marks := map[string]Mark{}
	mapFeatures := map[string]*featureproto.Feature{}
	for _, f := range features {
		marks[f.Id] = unvisited
		mapFeatures[f.Id] = f
	}
	var sortedFeatures []*featureproto.Feature
	var sort func(f *featureproto.Feature) error
	sort = func(f *featureproto.Feature) error {
		if marks[f.Id] == permanently {
			return nil
		}
		if marks[f.Id] == temporary {
			return ErrCycleExists
		}
		marks[f.Id] = temporary
		for _, p := range f.Prerequisites {
			pf, ok := mapFeatures[p.FeatureId]
			if !ok {
				return errFeatureNotFound
			}
			if err := sort(pf); err != nil {
				return err
			}
		}
		marks[f.Id] = permanently
		sortedFeatures = append(sortedFeatures, f)
		return nil
	}
	for _, f := range features {
		if marks[f.Id] != unvisited {
			continue
		}
		if err := sort(f); err != nil {
			return nil, err
		}
	}
	return sortedFeatures, nil
}

https://github.com/bucketeer-io/bucketeer/blob/v0.2.0/pkg/feature/domain/evaluation.go#L100-L139 より引用

再帰関数で深さ優先探索的に頂点を辿っていき、関数を抜けた順で配列（`sortedFeatures`という変数）に挿入をしています。

関数を抜けた順で挿入をすることで、前提条件となっているフィーチャーフラグ（矢印が向いている先の頂点）から順に挿入がされます。

同時に、フィーチャーフラグ間で閉路がないか確認していて、閉路が存在する場合はエラーを返すようにしています。

閉路については、訪れた頂点の状態を確認することで検出しています。ここでいう状態とは各頂点が探索対象となってから配列に挿入されるまでのことを示しています。各頂点はいずれも以下のように状態を遷移していきます。