tsort について

はじめに

Ruby Advent Calendar 2017 5日目の記事です。

この記事では、Ruby標準ライブラリにある tsort について、説明します。
tsort を使うことで、依存関係を解決して、順番に処理することなどが簡単にできます。

今回の内容は Meguro.rb #9 での発表資料をベースにしています。

トポロジカルソートとは

• グラフ理論でのアルゴリズムの１つ
• 依存関係を順に処理したいときに使える
• Ruby 標準ライブラリの tsort でトポロジカルソートができる

トポロジカルソートの利用例

Set#divide

標準ライブラリの Set#divide は内部実装で tsort を使っています。

その前に Set#divide について説明しましょう。
以下、るりまでの説明です。

元の集合をブロックで定義される関係で分割し、その結果を集合として返します。

ブロックパラメータが 1 個の場合、block.call(o1) == block.call(o2) が真
ならば、o1 と o2 は同じ分割に属します。

ブロックパラメータが 2 個の場合、block.call(o1, o2) が真ならば、
o1 と o2 は同じ分割に属します。
この場合、block.call(o1, o2) == block.call(o2, o1)
が成立しないブロックを与えると期待通りの結果が得られません。

o1 と o2 が同じ分割に属し、 o2 と o3 が同じ分割に属する場合、 o1 と o3 がたとえブロックの評価結果が偽であっても、 o1 と o3 は同じ分割に属することになります。

下記の例をみると分かりやすいでしょう。

require 'set'
numbers = Set[1, 3, 4, 6, 9, 10, 11]
set = numbers.divide { |i,j| (i - j).abs == 1 }
p set     # => #<Set: {#<Set: {1}>,
          #            #<Set: {11, 9, 10}>,
          #            #<Set: {3, 4}>,
          #            #<Set: {6}>}>

9 と 11が同じ分割に属しています。

Rubygems

Rubygems は内部で依存関係を解決する処理があり、そのために tsort を利用しています。

Bundler

Bundler も Rubygems と同様に内部で依存関係を解決するため、tsort を使っています。

Ruby on Rails

Ruby on Rails の Railtie では tsort を使っています。

ドキュメント によると、

Railtie is the core of the Rails framework and provides several hooks to extend Rails and/or modify the initialization process.

すべての Rails のコンポーネント（Action Mailer, Action Controller, Action View and Active Record）は Railtie です。

Ruby on Rails の Initializer では、:before や :after オプションを渡すことで、特定の Initializer の前後に順に実行するように指定することができます。

この Initializer の実行順を解決するために内部的に tsort が使われています。

tsort の適用例

今回、tsort が必要だった理由

• AWS の運用費用を売上管理と同じ分類で管理したかった。
• AWS では、リソースの費用をタグごとに分類して管理する機能がある
  • detailed billing report with resources and tags
• とはいえ、やってみたところ未分類のコストが多かった
  • 理由： タグがついていないリソースが多く、それらのコストが未分類として計上されていた
  • 　　EC2 にはタグがついていたが、EBS、スナップショット、AMI 等にはタグがなかった
• EC2 に付与されたタグを自動的に関連するリソースにも付与するスクリプトを作ろうと思った

AWS のリソース間の関連

• EC2 を起点として、リソース間の関連性は下図のようになっています。
  • それぞれのリソースの詳細については、今回の主題と異なるので説明を割愛します。

処理内容

詳細は、今回説明しませんが、下記の処理を作成しました。

1. aws describe-instances コマンドで、EC2 と EBS と ENI の関係を取得・EC2 に付与されたタグをすべて取得
2. aws describe-snapshots コマンドで、EBS と スナップショット ID の関係を取得
3. aws describe-images コマンドで、AMI と スナップショットID の関係を取得
4. ①～③の結果生成されたグラフ構造を元に、関連する EC2 に付与されたタグを EBS、ENI、スナップショット、AMI にも同様に付与する

有向グラフの構築

有向グラフを構築する処理の例です。

上記の図を Tree と見立てた場合、ハッシュ @edges の key が親ノード、 value が配列で子ノードとなっています。

@edges = Hash.new{|h, key| h[key] = []}
each_tag_ebs_eni do |instance_id, tags, ebs, eni|
  @edges[instance_id].push *ebs
  @edges[instance_id].push *eni
  …
end
each_ebs_snapshot do |volume_id, snapshot_id|
  @edges[volume_id].push snapshot_id
end
each_snapshot_ami do |snapshot_id, ami_id|
  @edges[snapshot_id].push ami_id
end

TSort 利用のための準備

TSort モジュールを include する場合は、tsort_each_node とtsort_each_child メソッドを実装する必要があります。
tsort_each_node ではグラフのすべてのノードに順にアクセスする処理を実装します。
tsort_each_child では、引数で与えられたノードの直接の子のノードに順にアクセスする処理を実装します。
このように、使う側で必要なメソッドを実装するという仕様になっていることで、TSort モジュールは特定のデータ構造に依存しない、柔軟性が高い設計になっています。

class AwsTSort
  include TSort
  def tsort_each_node
    (snip)
  end

  def tsort_each_child(node)
    @edges.fetch(node, []).each do |child|
      yield child
    end
  end
  …
end

今回の例では、tsort_each_node が必要なメソッドを利用していませんので、省略しています。

TSort のメソッドの呼び出し

TSort#each_strongly_connected_component_from という少々長い名前のメソッドを使うと、そのノードの子孫を順に処理することができます。
本稿の例では、EC2 に関連した EBS、ENI などのリソースを順に取得できます。

def resources_from(start)
  [].tap do |resources|
    each_strongly_connected_component_from(start) do |nodes|
      resources.push *nodes # nodes は Array
    end
    resources.delete(start) # start自身を除外
  end
end

後日談

TSort を使うことで、無事、各リソースにタグ付けする点については見事実現できました。
しかしながら、それでもなお未分類のコストが一定程度残っている状態です。
AWS的なベストプラクティスは、アカウントの分離だそうですが、今から取り組むのはハードルが高いと感じています。

詳しい人教えてください。