kazuk は null に触れてしまった

C# / .NET 系技術ネタ縛りでお送りしております

Azure Advent Calender–リバーシの全手順探索と最終的には白黒どっちが勝つのか


本記事は Azure Advent Calender 12/06 の記事です。

最初にすいません、コードをべたべた書いたのですが、書きあがりませんでした。

https://github.com/kazuk/AzureReversiFullCover

実際のコードはこちらなのですが書きあがっていません、リファクタリングもできていないので結構見苦しいコードになってます。とりあえず年内には書きあげるつもりで実装は続けますので…

リバーシの全局面の列挙をなぜ題材にしたのか

パブリッククラウドといえば潤沢な処理リソースをオンデマンドで取得できる環境という事で、目下スーパーコンピューターのランキングに入るような物を簡単に利用できるという素晴らしく便利なものでございます。

というわけで、リバーシの全手順探索をする為のソリューション一式作ってみました(出来上がりませんでした

注意事項としては、64個のますに駒の有無で1bit、駒がある場合で白黒どちらかで1bitですので、ますの情報量は1.5bitですから初期状態で置かれてるますの白黒4bit、空きますの60ますが90bitで現在の手番が白黒どちらの1bitを加えて95bitの空間があります。そこそこ効率を考えて実装していますが、バックトラッキングレコードの作成等を含めて膨大なストレージ容量を消費しますし、膨大なストレージトランザクションを発生しますので多分泣けるでは済まない課金額になります。

こんなもん作って意味あるのといえば、単体としては全くくその役にも立たない物なのですが、95bit空間に渡るものを効率的に分散並行処理をする枠組みをどうやって作るか、設計や実装というのがメインになります。

アルゴリズム

局面の列挙

基本的なリバーシの局面列挙については余り変わったことはしていません。 Piece という Empty / Black / White / Outside の4状態を 100要素のバイト既定のenum配列に用意し、10×10要素の周囲をOutsideとして番兵にして置ける場所の判定と、置いた場合の状態の列挙をします。この盤面を文字列化して盤面の状態として使っています。文字列化するときには現在の手番および、駒の埋まり状況の64bit、駒の色の64bitを16進文字列化しています。

ボードで使われる100バイトの配列は内部でスタック管理する事で使いまわすようにしていますのでGC負荷にはならないようになっています。

列挙された各局面は 90度回転、左右反転、上下反転の組み合わせを使って8通りの意味的な同一盤面の中から最も小さい値を持つ代表局面を選出されます。たとえばボードの初期局面から4か所に先手の黒は置くことができますが、実際にはどこにおいても代表局面は一緒になります。このようにすることで1手毎に局面が理論値で8分の1に減ります。

バックトラッキング

局面の列挙時にバックトラッキング用のレコードがTableStorageに生成されます。バックトラッキングレコードは PartitionKey に行きついた局面、RowKeyはWorkerRoleのインスタンスIDと時刻で特に意味はなし(競合防止用ユニーク値)、Sourceプロパティにカンマ区切りで元の局面が入ります。

バックトラッキング用レコードを RowKey = PartitionKey で競合防止をせずに実装した場合、挿入で1トランザクション、キー競合が発生した場合に読み込みを行って更新で計3トランザクションが理論値としてストレージトランザクションが発生します。このキー競合をRowKey を使って防いでいるので必ず1トランザクションでバックトラッキングレコードが生成できます。(この辺、設計変更が追い付いてません)

バックトラッキングレコードは結果反映にも関連しますので、最終的なプロパティ構成等は後述

生成された局面の重複解消

n手目の状態の列挙が完了するとその要素数が1000以下の場合にはそのまま状態をキューにカンマ区切りでメッセージを生成します。キューの先頭文字は A で、2桁の開始からの手数、ハイフン一文字に続いて4文字目からが盤面の状態を示しています。(Aメッセージ)

n手目の状態列挙が1000要素を超えると、Blobストレージに1000局面毎の盤面の列挙を改行区切りで出力し、入力blob名を指定するキューメッセージが生成されるようになります。(Cメッセージ)

CメッセージからはBlob に続く局面の列挙が生成されます、Cメッセージで生成された続く局面の列挙は複数のノードが吐き出した blob を統合する処理が必要になります。

このblobの統合は2つのblob を統合して2つのblob を吐き出す事の繰り返しで行われます。吐き出される2つのblob は入力された2つのblob の重複を除外して文字列表現で昇順に並べた場合の前半と後半に分離されます。

統合の処理的には全部を読み取って Distinct , orderby してあとは個数ベースで前半と後半で分けて書き込むだけで実現できる事なのでそれをベースに実装しています。

この処理の厄介な点は、複数の blob の統合処理を無駄なくかつ分散して行う事で、これの調停には以下のロジックを利用しています。

局面の最大値、最小値、これに関連づくblob名、および、統合中のフラグをもつレコードを Azure Table Storage に作成し。Azure Table Storageからレコードを列挙し、重複する範囲を持つレコードがあれば統合処理を行います、統合結果として出来上がる二つのblob を再度Table Storage に登録し統合元になったレコードは削除します。二つのblobの統合処理の要求は Queue で行われます。

局面の統合順序は登録順と範囲の重なり方で重みがついています。最も古いレコードを起点として統合対象を選択して統合する形になります。

範囲の重なり方のチェック順は、相手を包含すること、自分が相手を包含する事、相手の最小値が自分の最小値より小さいこと、最後に重なりがある事です。

包含関係にあるものを優先するのは、効率よく含まれる範囲が小さくなるからで、範囲が小さくなれば他者との包含関係も生まれやすくなります。

結果的に統合中のレコードも含めて範囲の重なりがなくなったレコードに関連づくblobは次の局面の列挙に回すためにCメッセージの生成に使われます。

最終局面からの結果反映

最終局面では引き分けたのか、黒白どちらかが勝ったのかの3状態になります。この3種に加えて最終局面にまだ到達していないという状態の4状態が各局面の状態を示し、これがバックトラッキングレコードにこの局面の終結として保持されます。

その手順での局面の列挙が完了していれば、そこにたどり着く手のバックトラックレコードには十分なデータが蓄積される事になりますので、その手順での局面列挙が完了したタイミングで結果反映はトリガされます。

結果反映に使用するルールは以下の通りです。局面が黒手番で、黒勝ちの手があればその局面は黒の勝ちです、局面が白手番で白勝ちの手があればその局面は白の勝ちとなります。この場合ほかの手の結果を知るまでもなく元の局面に結果を反映します。自分手番で自分勝ちの手がない場合には引き分ける手か負ける手しかありません。引き分ける手があれば引き分けるのが道理ですのでその局面は引き分けになります。どこに打っても負ける局面であればその局面は負けです。

引き分けおよび負けを前の局面に反映するためにはその局面への結果通知を蓄積する必要があります、この結果通知はバックトラッキング用テーブルに積み上げます。Azure Table Client ではエンティティ型を複数持つクエリーが作れないため、バックトラッキングレコードは一つのエンティティ型になるように双方に必要なプロパティを設けています。

 

Azure での分散処理

結果的にいえば使えるものは Queue 以外にはあまり要素はありません。Queueはその仕組みとして、キューを監視しているノードのいずれかで処理が実行されますのでキューメッセージに処理してほしい事を書いて放り込めば処理がどこかで実行してもらえる。やることが複数発生したら複数のメッセージを書けばきっと平行処理されるでしょう。

その Queue ですが、Azure Storage Queue は単一配信保障はありません。単一配信保障がないというのは、一つのキューメッセージが複数ノードで処理される可能性があるという事になります。結果的に重複処理等が起こりえます。

なぜ単一配信保障がないのかというと、処理ノードがメッセージを受信後に死んでしまう可能性があるからです。処理ノードがメッセージを受信後に死んでしまった場合には、プログラムが指定する一定の期間(visibilityTimeout)ののちにキューメッセージは再度どこかの処理ノードに取得され処理が行われます。これにより単一配信保障を崩すトレードオフとして耐障害性を獲得しています。

Queueメッセージは単純にはバイト列で、一般的には文字列で、キューメッセージは最大64KBのデータを格納する事ができます。

可能であれば Queue メッセージの64KB に処理に必要な全データを格納する事を検討してください。ぶっちゃけて収まらない事は当然に起こりますが、収まってしまえば処理に必要なデータを取得するためのストレージトランザクションを減らす事ができます。ストレージトランザクションは課金対象アクションなので、減れば減っただけ課金額が下がります。

次に Queue メッセージの処理時間の粒度をできるだけ揃えてください。分散並行処理をする主たる目的は処理効率です、QueueからのメッセージをGetMessage で待ち受けするときに指定する visibilityTimeout はメッセージの種別によらず一つしか指定できないため、Queueメッセージの処理時間にばらつきがある場合には最悪としてキューを分離する等を選択する必要が生まれます。処理時間粒度を揃える必要から Queue を監視するのに複数スレッドを使って処理するのは余り薦められません、CPU負担が重いメッセージを複数同時に引き取ってしまうと処理時間の見積もりが大きく崩れることになるからです。スレッドを使うのを避けると結果的にQueueを分離すると別のRoleによってその処理を引き受ける等を選択する必要が生まれますが、各Roleのインスタンス数等の調整が必要になってしまい、設計が複雑化します。

しかし、処理時間の見積もりが困難な場合があります。処理時間の見積もりが困難なケースではキューから取得されたメッセージを UpdateMessage によって適宜 visibilityTimeout を更新し処理が遅延した場合にも別ノードで取得されないように調整する必要が生まれます。

トランザクション

このサンプルの中でも多数の箇所で行われていることですが、Queueメッセージを元に Table Storage やBlob Storage を更新する事はよくあります。結果的に Table を更新した後に Queue メッセージを削除する等の処理をする事になりますが、Queue メッセージの削除メソッドである DeleteMessage と TableやBlob、その他は一つのトランザクションになっていません。(というか単一トランザクションにできません)

結果的にQueueメッセージのDeleteMessage の直前に実行インスタンスに対して戦車砲が直撃したシチュエーションではQueueのDeleteMessageだけが実行されていない状況が発生する事がありえます。QueueメッセージがTable からデータを取得して更新する場合等はこのシチュエーションを想定してください。Queueへの処理要求メッセージが二重処理されてしまっては困る場合にはメッセージ処理が必要とする入力データを Storage Table や Blob から削除してから DeleteMessage を実行する事で DeleteMessage がされずに残った場合にも入力データがないことで Queue メッセージ処理が失敗し多重処理を防ぐことができます。(この場合にRoleインスタンスが死なないようにしてください)

このあたりは結構複雑な考慮をする必要があります。blob にメッセージの入力データを置き、table が参照し、Queueメッセージには Table のキーを入れたとします。処理の完了時には、blob と table から入力データを取り除き、DeleteMessage をするとして、blob とtableのどちらを先に削除する必要があるでしょうか。blob が残存する事によるストレージ容量課金を気にするのであれば blob を先に削除する必要がありますが、blobとtableは単一トランザクションにできないのでその二つの処理の間にロケット弾の直撃の可能性はあります。table を引いてblob を見に行ったら物がなかった場合でもインスタンスは死なないように、そして今や無効となっている table レコードや、メッセージを後始末して処理が抜けれるようにしましょう。

Queueによる保障処理

入力の抹消での Queue メッセージの多重処理の防止の逆として、出力生成物の残存という事態も考慮の必要があります。blobに何等かデータを作成し、table にレコードを作る事で生成データが既存データと関連づく場合に、blob を作成した後で table レコード作成のほんのちょっとの時間差に掃除のおばちゃんが電源ケーブルをひっかけたりするとblob に作られた一生使われない1TBのデータの課金を永遠に払う羽目になります。

このような金銭コストが大きい残存データを残さないためにも Queue は有用です。Queue に初期 visibilityTimeout を設定したメッセージを投入しておき、これをレコード登録後に削除します。結果としてレコードが作られなかった場合には 初期visibilityTimeout の経過後にQueueからメッセージが取得されて処理されますので、このメッセージ処理で登録されなかった残念な blob を削除する事で無駄な容量課金が減るでしょう。(代わりにQueueへのメッセージ投入と削除の2回のストレージトランザクションが増えたことはトレードオフです)

ただし、table レコードの作成後に保障処理用のメッセージを削除するというこの二つの処理の間に掃除のおばちゃんがバケツをひっくり返してインスタンスが水没死する可能性もないわけではありませんから保障処理では正しくレコードが作成されて生きているデータを削除しないようにするなども考慮の必要があるでしょう。

 

まとめ

コードは全然書ききれなかったのですが、Queue と Table / Blob を絡めて動く物をうまく設計すれば大規模分散処理を実行するプラットフォームとしてAzureを生かす事ができるでしょう。

ただし、「失敗する可能性のあるものは失敗する」という法則があります。この法則は可能性がいかに低くても頻度を大きくしていけば確実になるという事であり、大規模分散処理は大規模ゆえの頻度の大きさによりちょっと不具合があれば確実に失敗するという事になりますので正しく実装することの重要度が非常に高い事でもあります。

自分としてはこの題材をとおして、失敗する可能性のある事柄をあぶり出して行きたいと思っています。

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。