Orbital design デザインパターン

技術::technique

TOP
Articles
技術
Orbital design デザインパターン

序

Orbital designについては、すっかり書いたつもりになっていたのだけど、実はちゃんと書いているのは既に削除されたInflatonの記事でだけで、Chienomiにはちゃんとしたものがなかったので、ここでこの斬新で強力なデザインパターンをしっかりと解説していきたいと思う。

Orbital designはどちらかといえば「スパイシーな小さなスクリプト」を書くタイプの私にとって、大きなプログラムを作る上で最大の武器となっている。

普段は小さなことばかりやっているので派手さがないが、実は私はHPC系の人間でもある。そして、そのHPC系プログラミングにおける私の武器なのだ。私は「高速なコードを書く」のに必要なスキルがないため、HPC分野で戦うには独自の武器が必要になる。そこで、「効率よく開発でき、メンテナンスしやすい手法」を編み出すことになった。

概要

Orbital designは、連続的変化のあるデータの扱いや、並列処理をターゲットとしたプログラミング・デザインパターンである。

ビッグデータ解析のために、2001年に私が独自に編み出した手法だ。

データの完全な同期が不可能、あるいは困難な連続可変データのために「ゆるい」設計を採用することで、効率よく動作させると共に実装を容易にする。

「問題を小さくする」ことがメインであり、実装が容易でトラブルが少なくなるというのが利点だ。また、スケールさせるのが容易で、その効率もよくほぼリニアにスケールさせることもできることから、大規模コンピューティングやHPCにおいても活用できるというのもメリット。

Orbital designを適用できるのは、比較的大きな問題に対してである。その「大きな問題」はデータ量や件数など、「並列処理を考えなければ成り立たないようなもの」を指しており、パーソナルコンピューティングというよりは、 SaaS用のアプリケーションなど、規模の大きいものに適している。

元記事掲載の内容

この記事は私がCEO, CTOとして書いたものだから、非常にプロモーショナルであること、そしてあまりハッカー向けの説明でないことには目を瞑ってほしい。

Orbital design

Orbital designはプログラミングにおける設計技法であるデザインパターンのひとつです。これは私がビッグデータ解析に取り組んでいるときに発明しました。

ビッグデータの場合際限なくデータが増えていく上に、切れ目がありません。常に膨大な解析が増えていき、いつ解析を開始すればいいのか分からず、かつ解析中にすらデータは増えていきます。もし解析中はデータを増やさない、ということにしてしまうとかなり効率は悪くなります。

Orbital designがどのようにして成り立つか、ということを説明すると極めて難しい話になってしまいますが、どのような形を目指しているか、ということは人間(会社)を例にしても説明できます。

Orbital designがなされた環境下においては、ワーカー(労働者)は任意のタイミングで仕事に取り掛かることができます。ワーカーが気にするべきは「自分がなにをするか」だけであり、「開始したら用意されている仕事から自分が担当すべきものをひとつ取り、それを処理する」ということだけが決められています。

つまり、仕事を提供する側のペースや状態、他の仕事がどのように進行していてどのような状態にあるか、ということは、結果にこそ影響は出るものの、労働としては全く気にしなくて構いません。これは、他の仕事を担当する労働者にとっても同じできる。で、それぞれが「自分がすべきこと」だけを見ていれば、結果として全体が噛み合って機能します。

生産性や効率がよいかどうかも、全体の結果には影響するものの機能的には影響しません。どこかの仕事の進みが悪いとしても、どれくらいのペースで成果が出るかという点では影響するものの、それによって他の仕事が待たされる、というようなことは発生しません。

Orbital design is universal

Orbital designの「直交的で、それぞれのクロックで動作する」という考え方は、非常にuniversalだと考えています。

たとえば、私達の体内の細胞は他の細胞を前提として動くわけではなく、それぞれがすべきことは明確であり、それぞれがすべきことを遂行することで全体として生命が成り立つようになっています。

また、宇宙においても、互いが影響しつつも天体は本来最も自然であるはずの「均質な状態」ではなく、流動する状態の中で均衡を保って全体をなしています。その中で、個々の天体は全体によって支配されているわけではなく、あくまで自分が影響される範疇のみによってその動きが決まっています。

人間社会はより複雑ですが、生態系もやはり互いに影響しつつも個々は直交し全体を形成します。

Orbital designはこうしたモデルを踏襲します。コンポーネントはシステム全体によって動かされるのではなく、自身に与えられた使命を忠実に遂行することで結果として全体が機能します。

“Orbital design” デザインパターンのルール

基本的に「エージェント」はプログラムのことを、「インスタンス」はプロセスのことを指している。

ただし、「エージェント」と言っているのは同一のレイヤーにあるプログラムのことなので、同一エージェントに複数の実装が存在する場合もある。

エージェントは常に小さく、「ひとつのことを正しくこなす」ものでなくてはならない
インスタンスは自身が動作するにあたり、自身の処理対象として関わらないデータや、他のインスタンスの状態や内容にアクセスしてはならない
あるデータベースまたはデータに対するwrite権限を持つエージェントはひとつでなければならない
データベースからデータを削除するのは、当該データに対するread権を唯一持っているインスタンスか、read権を持つ全てのインスタンスからの通知を受け取るスイーパーでなくてはならない
エージェントは入出力にあたってブロッキングを行ってはならない

“Orbital design” の効果

実装容易性

プログラムは小さく、やることが明確に決まっている。

他の状態などに対してアクセスすることはできず、ブロックもされないので競合状態にさらされるのは禁止だ。

だからプログラムは、あくまで自分のすることだけに専念できる。競合のことを心配しなくていいし、状態を知る必要もない。

実装言語の自由

プログラムは小さく分かれており、自分がすべきこと以外には干渉しない。だから、どんな言語で実装しても良い。

その操作がしやすい言語にしたり、便利なライブラリがある言語にしたりすることもできるし、局所的に速度が必要な場合はそこだけC, C++, Rust, Nimといった高速な言語で実装することも比較的容易。

また、同一エージェントをソースデータの違いなどにより複数の言語で実装するようなことも容易に行える。

並列性と分割性

入出力の経路が制限されていることで、並列実行時の競合が発生しないようになっており、デザインパターンを守ることで並列実行が容易になる。並列処理を書くのが容易なだけでなく、ロッキングや待ち合わせが発生しないことで並列処理によるパフォーマンス向上割合も高い。

また、入出力レイヤーでネットワークを使用するようにすれば、分散コンピューティングへの発展も容易。

シグナルが使える

OSに備わっている基本的な機能であるシグナルだが、実際のところあまりにも単純すぎて積極的に並列実行を助けるものとして利用するのは困難である。

しかし、Orbital Deisgnにおいては比較的シグナルを使った動作が容易だ。これはマルチワーカー型で動作させる上で若干のアドバンテージになるかもしれない。

Systemdとの親和性

Systemdにおいては@.serviceというユニットによってマルチインスタンスを実現できる。

Orbital designによって設計されたエージェントはマルチインスタンスで動作する上で必要な情報がこれによって実現できる「ワーカー名の引数」以上の情報が必要なく、非常に簡単にマルチインスタンスに発展できる。これはマルチワーカースタイルを実現する非常に簡単な方法で、インスタンスの再起動もSystemd側で面倒を見てくれる。

ジョブスケジューラとの親和性

Orbital designはマルチワーカー型マルチインスタンスに特化しているわけではない。むしろ、ジョブスケジューラによって定期的に起動されることのほうを主眼に置いている。

ワーカー型の場合、「処理状態の都合で」処理を開始するのに対し、ジョブスケジューラの場合は「処理状態を無視して」起動されることになる。ワーカー型の実装も面倒だが、タイミングに依存しないコードというのも難しいものだが、Orbital designはタイミングに依存しないコードを書くことになる。

シェルスクリプトで楽に書ける

ひとつひとつのエージェントのやることが明確かつ小さく、エージェント間でデータベース形式を統一する必要がないことから、「シェルスクリプトで楽ができるパートをシェルスクリプトで書く」というのが簡単にできる。

これが開発をものすごく楽にする場合は多い。

コンポーネント置換しやすい

個々のプログラムは小さく、明快なものになるため、使っているライブラリや言語、あるいはパフォーマンスの問題などで置換する必要ができた場合にそのコストが低い。

これは長期に渡ってメンテナンスされるシステムにおいてプログラムが朽ちていくのを避けることができる。

Orbital Deisgn のデメリット

空間効率

メモリ効率に関しては実装で頑張れば改善可能だが、各段階で固有のデータベースを吐くことになるため、ストレージ効率は非常に悪い。

また、単一のHDDのようなランダムアクセス性能の低いストレージを使っている場合、IOの発生量の多さからパフォーマンスが低下する可能性がある。

並列処理向き

あくまでもマルチインスタンスにより性能を向上させることを想定したものであり、単一のプログラムとして容易に書けるものであれば単に余計な処理が増え、パフォーマンスが低下することになる。

一連の処理に段階があり、なおかつ並列処理を期待したいものに適している。

近年はメニーコアプロセッサも増えてきているので、デスクトップPCにおいても有用な設計だとは思うが、4コア程度の一般パソコンではOrbital designは設計の改善には寄与してもパフォーマンス向上にはつながりにくい。

マキシマムパフォーマンスではない

スケールが難しいようなテーマであってもおよそリニアにスケールするプログラムを書きやすい、ということで、Orbital designはパフォーマンスにも寄与するのは確かなのだが、かなり無駄なコストを払う要素があることと、Orbital designにとって相性のいい機能が速くはないということから、最速実装を目指す場合にはあまり向いていない。

特に、計算量が少なく単純な場合は、IOコストが高すぎる上に、非同期より直列のほうがずっと速いという事態になりかねず、このような場合は損失のほうが目立つ。

Orbital designが活きるのは、やはり多くの計算を必要とする大量のソースデータが降り注ぐようなケースである。

ミニマムなコード

あまりおもしろみはないが、まずエージェントA。

File.open("/var/cache/orbital/#{Time.now.strftime("%y%m%d%H%M%S")}-#{$$}", "w") {|f| f.puts Time.now }

エージェントB

Dir.children("/var/cache/orbital").each do |dent|
  File.open("/var/cache/orbital/#{dent}") do |f|
    f.flock(File::LOCK_EX | File::LOCK_NB) or next
    printf("(%d)READED: %s\n", $$, f.read)
    File.delete("/var/cache/orbital/#{dent}")
    exit
  end
end

全く無意味と思えるコードだが、実際にこれらは「非同期に繰り返しそれぞれのインスタンスが起動する」という状況でも正しく動作する。例えば

(while sleep 3; do agent-a.rb; done) &
(while sleep 5; do agent-a.rb; done) &
(while sleep 10; do agent-a.rb; done) &

(while sleep 2; do agent-b.rb; done) &
(while sleep 5; do agent-b.rb; done) &

wait

という感じで動作させても大丈夫である。

おもしろみこそないものの、わずかこれだけで「非同期」かつ「マルチインスタンス」で問題なく動作させられるということから、Orbital designが比較的難しいこのような要求をコンパクトに書けることが伝わるかと思う。

具体的なOrbital designの利用例

アイディア

ここでは、あるBBSシステムから要約を作成して、チャットチャンネルに送る、というシステムを考えてみよう。

そのBBSシステムには非常に多くの投稿があり、単なるスクレイピングなどでは間に合わない状況だ。

この例はビッグデータを解析・活用するプログラムに応用するためのミニマムなモデルとして扱うことができる。あくまでOrbital designにおけるテクニックを盛り込むことを意識したもので、実用性やそれぞれのテクニックの必要性や適切性には目を瞑ってほしい。

フェッチング・エージェント

まずはBBSシステムからデータを取得するプログラムを作る。

require 'json'

class PostWatcher
  def initialize(category)
    @bcat = category
  end

  def fetch
    data = get_postdata.parse_postdata
    File.open("/var/cache/bbsdigest/fetchdata/#{Time.now.strftime("%h%m%d%H%M%S")}-#{$$}.json", "w") {|f| JSON.dump(data, f) }
  end

  def get_postdata
    #...
  end
end

class PostData
  #...
end

PostWatcher.new(ARGV[0]).fetch

BBSからデータを取得し、それをオブジェクトに変換してJSON形式でファイルに保存する。保存するファイルはこのプロセスに固有なので、特にロックする必要もない。

ここではJSON形式で保存しているが、後段もRubyであることが固定であるならばMarshal形式のほうがコストが低い。

ここではインスタンスは特定のカテゴリからデータを取得することになっており、並列処理が可能。ただし、実際は同一サーバーから並列でデータを取得するのはトラブルの原因にしかならないので推奨はできない。どちらかといえば、ソースごとに異なるインスタンス(解析するためのコードも異なる)とするほうが現実的な対応。

アナライズ・エージェント

require 'json'
require 'drb/drb'
require 'rinda/tuplespace'

class Analyzer
  def initialize
    @sources = []
    DRb.start_service
    @ts = Rinda::TupleSpaceProxy(DRbObject.new(nil, "druby://localhost:10000"))
  end

  def run
    read_source
    write_data parse_data
  end

  def read_source
    count = 0
    Dir.children("/var/cache/bbsdigest/fetchdata").each do |dent|
      break if count >= 10
      begin
        File.open(File.join("/var/cache/bbsdigest/fetchdata", dent), "r") do |f|
          f.flock(File::LOCK_EX || File::LOCK_UN) or next
          @sources.push(JSON.load(f))
          count += 1
          File.delete(File.join("/var/cache/bbsdigest/fetchdata", dent))
        end
      rescue
        next
      end
    end
  end

  def parse_data
    #...
  end

  def write_data(data)
    @ts.write(["parsed", data["id"], data])
  end 
end

Analizer.new.run

データを解析し、結果を書き込む。

このエージェントはフェッチング・エージェントが書いたデータに対するreadとremoveを行い、タプルスペース経由でデータベースに書き込む。 Orbital designではデータのremoveはそのデータの唯一のreaderが行うことになる。

タイミングの問題でファイルがちゃんと書けていない可能性があるので、この場合は例外を捉えてスキップするようにしている。これでタイミングの問題は単純に無視できる。

また、このエージェントはマルチインスタンスで動作した場合に同一のデータを取り合ってしまう可能性がある。そのためファイルロックしているが、ノンブロッキングでロックしているため、ロックに失敗する(他のインスタンスがそのファイルを開いている)場合は即座にそのファイルをスキップするようにしている。

同じような方法でデータを書き込んでもいいのだが、ここではより例の幅を広げるためタプルスペースを利用した。この場合はあまり必要性はない。

データベースドライバ

require 'drb/drb'
require 'rinda/tuplespace'
require 'dbm'

class DBDriver
  def initialize
    DRb.start_service
    @ts = Rinda::TupleSpaceProxy.new(DRbObject.new(nil, "druby://localhost:10000"))
  end

  def run
    while item = ts.take([nil, nil, nil])
      DBM.open("/var/cache/bbsdigest/digest.db", 0666, DBM::WRCREAT) do |dbm|
        dbm[item[1]] = Marshal.dump(item[2])
      end
    end
  end
end

DBDriver.new.run

こちらはシングルインスタンスでのみ動作するデータベース層。書き込むほうはマルチインスタンスなので、こちらで重い処理をすると間に合わなくなってしまう。そのため、この「シングルスレッドになる箇所」はできるだけ単純で、計算量が少ないものである必要がある。

センダーエージェント

require 'dbm'

class ChatConnector
  #...
end

class Sender
  def initialize
    @chat = ChatConnecter.new
  end

  def run
    DBM.open("/var/cache/bbsdigest/digest.db", 0644) do |dbm|
      while data = dbm.shift
        @chat.push Marshal.load(data) rescue next
      end
    end
    @chat.send
  end
end

Sender.new.run

これもシングルインスタンス。

実際にはここがシングルで一段になる実装というのは、個人的利用の場合しかありえない。サービスとして提供する場合は、解析した結果をマージする層が必要になるだろう。

Orbital designにおける一般的なテクニック

大きなデータを残さない

素のソースデータなどは別として、オブジェクトとして保存する場合はあまり大きなデータを残さず、そのインスタンス内で一貫している処理は済ませたほうが良い。

これは、シリアライズ/デシリアライズ処理のコストを考えてのことで、ひとつの計算途中のデータを受け渡す、というのは、並列性の問題でやむをえないのでなければしないほうが良い。

また、シリアライズにおいてMessagePackのようなデータが小さく、高速な実装がある形式を使用することは全体のパフォーマンスの改善につながる可能性がある。

シングル部分をちゃんと考える

ロックしたりすることができないデザインパターンなので、基本は競合が発生しないように設計するのだが、どうしても競合する箇所については「できるだけ小さく」シングルインスタンスで動作するように分割する。

ちゃんと検討すればシングルにならざるをえない部分というのは極めて小さくできるはずだ。

なお、注意点としては、他のインスタンスの状態を参照したり、リソースを共有することはそもそも禁止なので、そのような必要がある設計にしてはならないということだ。これは多くの場合データの重複を許容することで解決できる。

不完全なデータは「無視する」

タイミング上どうしても発生してしまう「不完全なデータ」は、なるべく発生しにくいようにした上で、「不完全に見える」(assuming)データで例外を吐くようにして、単にスキップするようにするのが良い。

ちなみに、

File.open("afile", "w") {|f| Marshal.dump(data, f)}

のようにした場合、

File.read("afile")

で読むと、ファイルは「空」か「完全」かのどちらかである。これは、Marshal#dumpがデータを一度に書き込むため。

もちろん、これは一度に書き込んだ内容はOSがアトミックであることを保証してくれていることを前提としている。ここらへんは自分が使用するシステムのことをちゃんと理解するようにしよう。

ちなみに、Linuxのwrite(2)はatomicである。

ノンブロッキングファイルロック

マルチワーカー型でワーカーが拾うデータが「他のワーカーに取られていない」ことを保証するためには、ファイルを「ノンブロッキングで排他ロック」するのが良い。

これによってブロッキングすることなく、同じソースを処理してしまうことを避けられる。

この方法は非常に多くのデータをマルチプロセス処理したいケースにおいて有効である。データを書き込む側は次のエージェントにひとまとまりで処理して欲しい内容をまとめてひとつのファイルにして書き出す¹。

これに対してそのデータを読み出すエージェントは「自分がロックすることができるノンエンプティなファイルをロックして処理対象にする」という方法でデータチャンク単位でインスタンスを走らせることができる。

前出の例では10個ずつ読んでいるが、1つずつ読めるようにしたほうがスマートな設計にできる。

やることがないときはsleep

なんからの理由でエージェントが処理すべきデータがたまっていない状態というのは普通にある。

このとき手っ取り早いのは「なにもやることがないときはsleepする」である。

Systemd TimerのOnUnitActiveなどでやることがあるかないかというのがうまく調整されている場合はいいのだが、処理すべきデータがない場合はより長く待機すべきなのにむしろより頻繁にアクティベートされてしまうというような事態が発生するならば、さっさとそのセッションを終わらせずにsleepするほうが良い。

タプルスペースとの相性の良さ

シングルスレッドで動作させたい部分にぱっと投げたり、データを受け渡したりと非常に便利で、まさにOrbital designのためにあるような相性の良さである。

ただ注意しなければならないのが、 タプルスペースはFIFOではない ということ。

SaaSなどで使用する場合、先に処理を開始したユーザーが先に結果を得られることを約束はできない。

分割はデータで

基本的には「インスタンスが処理すべきデータがひとつにまとまった状態で書かれている」というのが理想。

例えば「一度に入力されるのが100万レコードあるけど10並列で処理したいから10万レコードで分割かな」とか、そういう考え方である。

コード例ではインスタンス側で読み込むデータの量を調整しているが、できればインスタンスで調整するのではなく、データ側で調整したほうが良い。

だから、場合によってはデータをマージしたり、分割するだけのレイヤーが挟まることもある。

インスタンスの分割基準

ひとつのインスタンスがどの程度まとまったデータを扱うか、というのは、ほぼ「分割する上で分割したいサイズによる」ということになる。

前節では「100万レコードを10並列で10万レコード」というふうにしたが、「入力量によらず10並列にしたいから record.length / 10」という方法でもいいし、もしくは「常に1万レコードを処理して回してほしい」と考えるなら1万レコードずつに分割するのも手。

私がSaaS開発でやった手法だと、「プランによって並列処理数が変わる=上級プランのほうが高速に処理される」という構成が考えられていたので、全体のレコードを契約プランの並列数に分割するというのもあった。

サーバー側からみれば、レコード数が多ければそれだけ長い時間ひとつのインスタンスを走らせることになるから、別に低グレードプランだからサーバー負担が少ないということにはならないのだけれど、ユーザーから見れば分割したほうが高速である。

ただ、その分配があまり公平性のない分配だったので、正直高グレードのプランだから優遇されるという感じはなかった。そこに対するニーズが高かったら別の実装を用意したと思う。

ちなみに、全体レコードが小さい場合分割したほうがコストが高くなってしまうので、分割される最小のレコード数という扱いもあった。

インスタンス数はいくつにするか

「メモリが死なないように」というのが大前提なのだけど、まずウェブからデータをとってくるようなものに関しては「所要時間が不均衡でもいいから、それぞれのインスタンスがひとつのサイトについて責任をもってデータをとってくるようにする」のがまず基本的な設計。

ただ、20や30程度のサイトならいいのだけど、1000とかになってくると「1000並列でダウンロード&フェッチ」というのはなかなかやばい。そのため、複数のプログラムをグループにして、そのグループを呼び出すシェルスクリプトをインスタンスとして扱うことになる。

こうしたインスタンスに関してはOnUnitActiveなどを使ってほぼ回しっぱなしになる。

ローカルにある大量のデータを計算する必要があるような場合、検証の限りでは結局のところ「各エージェントでそのマシンの実コア数」がよいように感じた。

これによってメモリが枯渇するような事態に陥るのは避けなければならないが、仮想スレッドがあるCPUの場合は特にこの設定でおおよそうまくいく。

ただ、あまりにも解析処理が重く、各エージェントに休み時間がないロードアベレージ>1 の環境ではそれだと効率が悪くなるが、その状態に陥っている時点で希望はないのでマシンを乗り換えるべき。

シェルスクリプトエージェントには要注意

「シェルスクリプトでお手軽簡単にエージェントが書けるよ」っていうのはOrbital designのメリットのひとつなのだけど、実際にやるときはちゃんと考えたほうがいい。

なぜならば、シェルスクリプトは単純なループでも信じられないほど遅いので、処理量が多いプログラムでシェルスクリプトをコンポーネントにしてしまうと、全体の足をものすごく引っ張ることがあるのだ。

マネージャを書かない

こういう細かく分割された並列処理プログラムを書こうとすると、システム全体を統括するマネージャを置きたくなる気持ちはわかるのだが、それをやるとOrbital designとしては違反なので、頭を切り替えよう。

それをしないためにOrbital designがあるのだから。

Systemd Timerでのアクティベート

ほとんどの場合OnUnitActiveで良い。

ただし、単一のウェブサイトからデータを引っ張ってくるようなものに関してはOnUnitInactiveで確実にインターバルをとるようにしたほうが良い。

データの参照は避ける

インスタンス間で共有されるデータがあってそれを参照するという状態は避けるべきなので、個々のインスタンスが使用するデータに含めるようにすべき。

スイーパーの利用

スイーパーが必要になるケースは、基本的には複数のエージェントに渡るアトミックな処理がある場合。アトミックな処理が終わらないと元データが削除できないのであれば、最後のエージェントが「終わったよ」と伝えて元データを消すという手順になる。

これは、リジュームのことを考えても必要になる場合がある。「オリジナルのソースデータ」を処理するエージェントは、それを削除ではなく移動してバックアップ状態にして読み込み、最後のエージェントが処理を終えた時点でスイーパーが削除、もしくはログ行きになるようにすると、任意のタイミングでシャットダウンできるようになる。システムの起動時にバックアップをソースデータの位置に移動させるだけでリジュームできるからだ。

任意に停止・再開できるというのは、サーバーメンテナンスが楽になる上に、耐障害性も上がるので意外なほど良い。

同内容のコミットは上書きさせる

Orbital designではコミットが先、デリートが後というルールを徹底すれば任意停止できる設計にしやすい。

だが、これだけだと問題が起きる場合がある。それは、コミット後デリート前に停止してしまい、リジュームしたときに同一のデータを別のデータとしてコミットしてしまい、コミット結果が重複するケースだ。

これは、最初のソースデータにつけられたファイル名やIDを継承するようにすることで同一キーに対して上書きされ、複数回コミットされても結果が変わらないようにすることで解決できる。

これは重複コミットされるという問題自体は変わっていないが、重複コミットされても特に困らないようにすることでゆるい設計を可能にするわけである。

Windowsでのファイルシステム利用

Windowsはファイルをオープンしたまま削除できないので、例で使っているようなflock+deleteという方法が効かない。

この場合、代理サーバーを用意して、これに対してreadを要求するというのが良い。

代理サーバーはこんな感じ。

require 'drb/drb'
require 'rinda/tuplespace'

DRb.start_service
ts = Rinda::TupleSpaceProxy.new(DRbObject.new(nil, "druby://localhost:11000"))

db = []
running = []

while req = ts.take([nil, nil])
  # リクエストに応える前に、データベースを更新
  db |= (Dir.children("/var/cache/orbital") - running)
  if req[0] == "fin"
    # 完了なので、通知されたファイルを削除して処理中リストから削除
    File.delete("/var/cache/orbital/#{req[1]}") rescue nil
    running -= [req[1]]
  elsif req[0] == "req"
    # リクエストなので、処理中に登録して応答
    ent = db.pop
    running.push ent
    ts.write([req[1], ent])
  end
end

これだとエージェント側のRinda::TupleSpaceProxy#takeでブロッキングが発生してしまうので完璧ではないけど、デザインパターン上はIOにおいて発生しているのではなく、そもそも自身が処理すべき対象を知るために発生している(起動コスト)ためセーフではある。これが「データそのものを渡す」という形になっているとデザインパターン的にNGとなる。

Windowsのファイルシステムはあんまりイケてないのでデータベースソフトウェア使ったほうが良いかも。

RDBMSのことは特に考えていない

私がRDBMSが嫌いなので、RDBMSで試したことがなく、RDBMSにおいて有効な設計かどうかはわからない。

Orbital designの考え方からすると、RDBMSのメリットは活きないというか、むしろ足かせになる可能性があるので向いてはいないと思う。ただ、sqliteであれば、特に困ることもないかも知れない。

データを細かく、直行して扱うというOrbital designの特性上、MySQL/MariaDBやPostgreSQLのみならず、MongoDB, Redisといったデータベースとも親和性はあまりない。これらは全てのデータを一元的にこのデータベース上で扱うことを想定しており、Orbital designとは相容れない部分がある。 Orbital designでは同一データベースに対して複数のエージェントが書き込むことは禁止なので、単にやりづらくなるだけである。

ただし、全く使えないかというとそんなことはない。もちろん、不便を承知で使うこともできるが、Orbital designの最終段でwrite権限を持つのがMariaDBやRedisであるという方法がある。この場合、Orbital designで設計されているのはデータコレクタ(パーサーやフォーマッタを含む)であり、集約されたデータを扱うプログラムはOrbital designのコンポーネントではない、という話である。

個人的にはOrbital designにおいては、シリアライズオブジェクトファイルとファイルシステムを組み合わせたり、DBMのようなKVSを使ったりすることが多い。 QDBMやKyoto Cabinetを有難がるケースは今時なかなか見かけないと思うが、Orbital designなプログラムだとQDBMの高速性や、高性能なファイルシステムがどれだけ超高速にインデックス引きしてくれるかということを痛感できる。

ただ、DBMは原則として、更新の競合に対してはファイルロックを要求するという点に注意が必要である。ファイルロックによる排他制御はOrbital designのルールに反することになるからだ。スレッドセーフなDBM実装は自動的にロックされる。これがノンブロッキングであるかというと、実際そうではない。

Orbital designの場合、そもそも競合を発生するようなアクセスをなくしてしまいましょう、という考え方なので、「いかにしてデータを分離するか」のほうが大事である。効率がよく高速な実装にしようとすると工夫が必要になるが、メニーコア環境下で実行する場合は並列化でのパフォーマンス向上率がいいので「まぁ、いっか」となってしまうこともある。

ファイルシステムに関する知識があるとパフォーマンスチューニングでは有利。

ファイルシステムデータベースに関する小技

ファイルシステムは速い

KVSとして見た場合、ファイルシステムは尋常じゃないほど速い。

どんなデータベースもインメモリ処理しない限りはファイルシステムより速く読み書きはできないわけで、最近のファイルシステムはインデックス引きは猛烈に速い。遅いとか言われているbtrfsもインデックス引きに関しては凄まじく速い。

ただし、後述するようにファイルシステムは安全に設計されており、インデックス引きは速いが参照は遅い。 KVSとして見た場合は癖があるのでそのあたりは注意が必要。

データベースとして使うとまた速い

基本的にファイルシステムデータベースはファイル名をキー、データを値としたKVSなので、文字列として書き込むことになる。

なのでシリアライズしたデータをせーので書き込むのだけど、当然ながらシーケンシャルになるのでめちゃくちゃ速い。

ただ、キーに関しては若干の制限が生じることに注意。

シリアライズに関して

Ruby観点だと、必要がなければYAMLやJSONは使わず、Marshalで書くのが良い。また、基本的な型しかないのであればMessagePackが良い。

とか言いたいところだけど、実は話はこれで終わらない。

サイズの小ささでいえば魅力的なMessagePackだけど、実はBSONやOJ-JSONのほうが速い。ここまでなら「へぇ、やるじゃん」で済む話なのだけど、Netflix Fast JSON APIはOJ比10倍とかいうレベルで速い。恐るべしNetflix…

が、それで話は終わらない。RoR用に作られているNetflix Fast JSON APIは単純にシリアライズしたオブジェクトを返してくれない。これはBSONも同様である。 MessagePackよりもOJのほうが速いので、OJを使おう。

Marshalに関して注意すべきことは Timeは使わない ということである。

RubyのTimeオブジェクトの生成は異様に遅くて、DateやDateTimeを使うことで圧倒的に速くなる。中間結果で比較に使うだけで、それが日時である必然性がないのであれば、IntegerかStringとして格納してOJでシリアライズするのがより速い。

ちなみに、YAMLはシリアライズ/デシリアライズともに超遅い。インスタンスが再ロードされるタイプであるならば、そのときの設定ファイルもYAMLで書くのはいいけど、JSONに変換してキャッシュするとかしておこう。

入れ子

ファイルシステムデータベースはKVSだが、ディレクトリを使うことができるので格納できる値は「ハッシュと文字列」である。

これにより、次のエージェントが扱うデータがひとつのファイルにパックしてしまうと重いというような状況で、エージェントの処理対象をディレクトリにして個々のデータをパックするという方法もとれる。

ただし、この場合シリアライズ/デシリアライズのコストが上がるのでその点は注意が必要。ここらへんはメモリとの兼ね合い。

さらにこの場合後述するように読み書き自体が遅くなる要素を含んでいるので、そのインスタンスあるいはエージェントが専有する高速なDBMファイルを用いるほうが良い。

ファイルシステム vs KyotoCabinet

エージェントがアクセスするレコード数が多い場合、 ファイルシステムはかなり遅い。

私はあまりこのような設計にしないので「ファイルシステムは速い」の印象になるのだけれど、どちらかといえば一般的な実装においてはファイルシステムはこの問題にひっかかる可能性のほうが高い。

つまり、「アクセス回数が少なく、読み書きの量は多い」のであればファイルシステムが速く、「アクセス回数が多い」のであればファイルシステムは遅い。

例えばこんなファイルを用意する。

% wc source
  66188  350946 4078964 source

で、こんなベンチマーク用プログラムを書く。キー側をファイルシステムの事情に合わせているので、現実世界ではもう少しKyotoCabinet有利にできる。

ARGF.read.split(/\s+/).each do |word|
  fw = word.delete("/.\\")
  next if fw.empty?
  File.open("fs/#{fw}", "w") {|f| f.write word }
end

require 'kyotocabinet'

KyotoCabinet::DB.process("kc/words.kch") do |db|
  ARGF.read.split(/\s+/).each do |word|
    fw = word.delete("/.\\")
    next if fw.empty?
    db["kc/{fw}"] = word
  end
end

KyotoCabinetを置いているファイルシステムとファイルシステムベンチマークのためのファイルシステムは同じもの。種別はext4である。

結果。ファイルシステム:

% time ruby fs.rb source
ruby fs.rb source  3.28s user 12.84s system 84% cpu 19.049 total

KyotoCabinet:

% time ruby kc.rb source
ruby kc.rb source  0.99s user 0.03s system 99% cpu 1.021 total

圧倒的じゃないか…

それもそのはず、KyotoCabinetは同期的に書き込んでいるわけではないので、非同期に書き込みを終わらせられるから、呼び出すプログラム側では速い。じゃあインメモリにすればええのんかというと、tmpfs上でfs.rbを実行しても

% time ruby fs.rb source
ruby fs.rb source  2.29s user 2.13s system 98% cpu 4.484 total

と、ファイルのオープンクローズを繰り返すこと自体が遅いということがわかる。だから、ファイルシステムをKVSにする場合、たくさんのインデックスにアクセスするのはよろしくないのだ。

もっとも、メリットもある。ファイルシステムは障害時に壊れないように入念に設計されている。それと比べると耐障害性が高いほうであるKyotoCabinetであっても簡単に壊れる。

しかし実は、この点はOrbital designではあまり気にならない。中間レベルで生成されるデータは「だめなら捨てていいもの」だからだ。

なお、RubyGems kyotocabinet はメンテナンスされていないので、kyotocabinet-ruby-reanimatedを使う必要がある。

余談。単純にHashだとどうなるかというと

h = {}

ARGF.read.split(/\s+/).each do |word|
  fw = word.delete("/.\\")
  next if fw.empty?
  h["fs/#{fw}"] = word
end

% time ruby hash.rb source
ruby hash.rb source  0.80s user 0.05s system 99% cpu 0.845 total

というわけで、「組み込みHashよりKyotoCabinetのほうが速い」という主張が掲載されているけれど、Ruby 1.9から9年。Rubyも随分速くなったのでそうは問屋が卸さない(が、それでもかなり近い値が出ていることには驚く)。では、KyotoCabinetのプロトタイプHashDBだとどうか。(ファイル名を-にする)

% time ruby kcpdb.rb source
ruby kcpdb.rb source  0.85s user 0.03s system 99% cpu 0.881 total

さすがに改善されたRuby Hashのほうが速い。Rubyのほうは今後も改善されていくのでなおさらだろう。

なお、ここではデータサイズがかなり小さいので、ファイルハッシュDBのほうがメモリを多く使用するという状態だった。速度に関してもデータサイズが大きくなれば変わってくるかもしれないということは述べておこう。

ただ、Orbital designでインメモリDBが活躍する機会はあまりない。

もう少し実戦的なケースを考えてみよう。Orbital Designでは一度に処理するデータとしてシリアライズドオブジェクトを扱うため、数MBから数十MBほどがせいぜいである。データベース全体のサイズは大きくなりにくく、(単一ファイルではなく)外部データベースを必要とするのは、より小さいデータを数多くひとつのワーカーが処理する必要があり、分割したいというようなケースである。

そのソースデータは3MBほどあるので、100個ほど書いてみよう。先程と比較すると、インデックスが減り、データサイズが大きくなった。

data = ARGF.read
100.times do |i|
  File.open("fs/#{i}", "w") {|f| f.write data.clone }
end

% time ruby fs.rb source
ruby fs.rb source  0.10s user 0.48s system 99% cpu 0.584 total

require 'kyotocabinet'

data = ARGF.read

KyotoCabinet::DB.process("kc/words.kch") do |db|
  100.times do |i|
    db["kc/#{i}"] = data.clone
  end
end

% time ruby kc.rb source
ruby kc.rb source  0.20s user 0.48s system 97% cpu 0.701 total

Orbital designでよく見られる、個々のデータが大きく、分割数が少ないパターンではファイルシステムのほうが速い。小さく分けてしまうと、シリアライズ/デシリアライズのコストが上がるので、適切な設計が必要になる。

ついでにこのデータで消費メモリーを比較してみる。データは300MB以上になる。なお、単純にcloneしただけけだとメモリ消費量が増えなかったので、インデックスを文字列として足した値を追加するようにした。

Hash

462240 415928 pts/0   S+   20:29   0:00 ruby mhash.rb source

KCインメモリハッシュ

487288 439124 pts/0   S+   20:31   0:00 ruby kcm.rb sourc

KCファイルハッシュ

116872 68696 pts/0    S+   20:31   0:01 ruby kcf.rb source

速度的にもハッシュのほうが速く、KCインメモリハッシュがRubyのハッシュに対してアドバンテージを持つことはなさそうである。

データに対するOrbital design的感覚

Orbital designは非同期で動作させるために「結果を出力する」という性質がある。

Orbital designを採用するとコンポーネントはより小さく分割され、それぞれが直交して動作するようになる。これはつまり、一般的には変数として受け渡されるようなインメモリな値をディスクに書き出さなくてはならないということを意味している。

同期していないということも含め、直列的な意味ではパフォーマンスはだいぶ損失する、というのもあるが、この「通常はディスクに書かないデータを書いている」という感覚が重要だ。

つまり、これらのデータは本来永続的なものではないのである。だから、捨ててよいはずだ。そのため、これらのデータの保護はあまり考える必要がない。通常は永続的でないものを永続化していることは、停止及びリジュームにおいて有利な条件を与えるが、その活用の前に、「壊れたら捨てる、必要なくなれば捨てる」という観点が必要である。

「捨てるのにかかるコスト」にも配慮が必要だ。unlinkは意外と重い。

そして、どの段階が「捨ててはいけないデータベースなのか」ということをきっちりと分ける必要がある。

つまり、Orbital designは通常は必要とされない、「処理結果伝達のためのデータ」を出力する。これは捨ててもいいし、インメモリにしても良い(例えばtmpfs上とか)。

でも、Orbital designでなくてもどこかしらのタイミングでデータとしては書き出されるわけだ。最低限最終結果は書くだろうし、ソースを蓄積して再計算するタイプだとソースデータもとっておく必要がある。

つまり、その処理において不可逆的で、計算の起点となるデータというのはたとえコストが高くてもちゃんと残るようにしなければならない。例えば収集データベース→統計化データベース→連想データベースという形に変換される場合、この3つのデータベースは全て残さなければならない。前段のデータベースが更新されることで後段のデータベースもアップデートされていく構造だからだ。

逆に言えば、Orbital designはこのような構造になっているシステムのほうが適性は高い。同期的・直列的に処理できてしまう問題に関してはOrbital designは実行的にはコストのほうが目立つからだ。一方でそれぞれが随時アップデートされる構造であれば、アップデートの段階を区切らなくてよくなるということで、連続性を高められる。

Orbital designの場合は「キューにデータを含めたもの」を書き出すことになるという独特な部分がある。これを保護する必要があるのかどうか、ということだ。もっとも、データはデータベースとして残るべきものであるならば、データはキューではなくデータベースに所属することになり、キューとは独立になるから、データがあるかないかに関わらず「キューとして書いたものは保護しなくて良い」はずである。もちろん、データベースとして残す必要があるデータまでキューに含めてしまうというミスはないものとして。