ダブルスの試合を2コートでまわすときにプレイヤーの重複のない組み合わせを探す
問題設定
ダブルスの試合をたくさんやることになりました。試合組はすでに決まっています。
2面を使って試合をし、2つとも終わった段階で次の2試合を始める方式とします。これを1ターンと呼びます。
全部で20試合あるので理論上10ターンで終わるはずです。しかし、当然1人が同一ターンの2試合に出ることはできません。
これを解消する必要がありますが、適当に組んでたらどうにもうまくいかなかったのでプログラムを書くことになりました。
制約
- 試合ごとにかかる時間は一定ではないので、長い時間がかかる試合と短い時間がかかる試合が同じターンにあるとロスが大きいのですが、ここではかかる時間は一定であるとします
- 連続した試合は当然避けたいものですが、この後のステップでターンごとに並び替えればよいのでここでは気にしないことにします
解法
games は Hash{Integer => Array<String>} で試合IDとプレイヤー名の配列が入っているものとします。
出力はなんでもいいのですが spreadsheet に食わせるので1ターンごとに1行で id_1,id_2 というCSV形式にしました。
方針自体は割と簡単で、とりあえず詰めてみて、制約違反が発覚したら1手戻してみるという形式です。
+ より push して pop すればよかった気はしなくもない。
全部で20ゲーム、ターン内の組み合わせは可換、10ターンの並び替えも可換なので組み合わせ的には 20!/(2^10)/10! ですかね。
手元で実行したら 0.17s でした。
def solve(games, table) if table.size == games.size return table end if table.size % 2 == 0 games.each do |k, v| unless table.include?(k) ans = solve(games, table + [k]) if ans return ans end end end nil else used_id = table[-1] used = games[used_id] games.each do |k, v| unless table.include?(k) if used.none? { |p| v.include?(p) } ans = solve(games, table + [k]) if ans return ans end end end end return nil end end ans = solve(games, []) ans.each_slice(2) do |a, b| puts "#{a},#{b}" end
以下テスト用のデータです。
{ "2": [ "a", "b", "c", "d" ], "3": [ "b", "e", "c", "f" ], "4": [ "a", "g", "f", "d" ], "5": [ "a", "h", "c", "i" ], "6": [ "g", "e", "f", "j" ], "7": [ "a", "k", "f", "i" ], "8": [ "b", "k", "c", "l" ], "9": [ "b", "h", "d", "j" ], "10": [ "a", "e", "f", "l" ], "11": [ "b", "m", "c", "j" ], "12": [ "h", "g", "d", "l" ], "13": [ "h", "e", "i", "l" ], "14": [ "g", "k", "d", "n" ], "15": [ "e", "k", "c", "n" ], "16": [ "a", "m", "i", "j" ], "17": [ "h", "k", "l", "j" ], "18": [ "e", "m", "f", "n" ], "19": [ "g", "m", "i", "n" ], "20": [ "h", "m", "l", "n" ], "21": [ "k", "m", "j", "n" ] }
Rack で transfer-encoding: chunked なレスポンスを返す
each を実装したオブジェクトを body として返してやるといい感じになる。 -> ならないかも。末尾参照（2019-10-28 17:25追記)
Streaming::Stream のように each を実装したオブジェクトを call の戻り値に詰めている。
実際のレスポンスをみると Transfer-Encoding: chunked であることがわかる。
またサーバ側のログからも wrapper end のあとに Stream#each が実行されていることがわかる。なので rack middleware 層を突き抜けた先で each が評価されている。
--raw をつけて実際 chunk ごとにきてることも確認している。chunk が来た瞬間に curl が stdout に書いてくれるわけではないようで、すべて終わってから書かれるのが気になるところではあるがきっとだいじょうぶだろう。
gist9adfaa2234729ad51913b3169064dbc0
2019-10-28 17:25追記
すべて終わってから書かれるのが気になるところではあるがきっとだいじょうぶだろう。
chrome タブで開いてTTFBを見ると 3sec かかっているのでぜんぜん大丈夫じゃなかったっぽい
Amazon SQSでFIFOだからってシステム全体が Exactly-Once になると思ったら大間違いだっていう話
TL; DR
- Amazon SQS で Exactly-Once なキューを使おうとも冪等な処理を書くべき
- キューが Exactly-Once であるという性質はシステム全体が Exactly-Once になることを保証できない
- 結局マルチデータソースへの書き込みの問題が残る
- Designing Data-Intensive Applications (邦訳: データ指向アプリケーションデザイン） が良書でした
- 邦訳は未読1ですが原著の内容がいいのできっとだいじょうぶでしょう
- 作者: Martin Kleppmann
- 出版社/メーカー: O'Reilly Media
- 発売日: 2017/04/02
- メディア: ペーパーバック
- この商品を含むブログを見る
データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理
- 作者: Martin Kleppmann,斉藤太郎,玉川竜司
- 出版社/メーカー: オライリージャパン
- 発売日: 2019/07/18
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
経緯
先日 twitter を見ていたら以下のような発言がありました。
「Amazon SQS は同一メッセージが複数回配信される可能性があるので冪等性を保証する必要がある」という言明がある。しかしこれは FIFO キューを使えば Exactly-Once な配信を保証できるので偽である
しかしこれは正しくありません。FIFOキュー使ってもシステムを堅牢にするためには冪等性を保証しておいたほうがよい、ということを以下で主張します。
複数データソースにおけるトランザクション
本記事では、なんらかの処理をして副作用として永続化を行うような一連のステップのことをトランザクションと呼びます。たぶん一般的な定義ともそんなにずれてないと思います。トランザクションは開始したあとに、コミットあるいはロールバックをして終了します。トランザクションを張りっぱなしで掴んだままのケースもありますが、適当にタイムアウトしてロールバックされるものとします。
複数のデータソースに対してトランザクションを行うとき、正常系ではコミットも複数回行う必要があります。このときに問題になる典型的なパターンがあります。それは、あるデータソースではコミットに成功したが違うデータソースではコミットに失敗するケースです。コミットはいろいろな事情により失敗する可能性があります。RDBのなんらかの制約であったり、ネットワークの不通であったり、あるいはプロセスが殺されたり、もしくはデータセンターに隕石が降ってくるかもしれません。ここで重要なのは、どんなトランザクションでもコミットに失敗しうる、ということです。
例えばよくあるトランザクションの例では、1000円の口座残高をもつAさんと、同じく1000円の口座残高をもつBさんがいたときに、AさんがBさんに100円送金する例が挙げられます。これはトランザクションを張っておきましょうねで済みます。しかし、このときAさんのレコードは mysql に、Bさんのレコードは postgres にいたりすると片方だけコミットに成功し、片方がロールバックされるような状況も起きえます。
この例では「いやいや mysql と postgres って。設計がヤバすぎでしょう」という気持ちにもなりますが、上述のSQSの問題についてもまさに同様のことが起きます。このケースでは我々はRDB2とSQSという2つのデータソースに対して一貫性を保ちたいということを言っているのですから。
SQSというデータソース
SQSにおけるトランザクション
Amazon SQS についてはトランザクションという言葉が（たぶん）出てこないので、本エントリでは Amazon SQS のどういうところを指してトランザクションと言っているのか、またそれがどういった性質をもっているのかを説明します。詳細な仕様は公式ドキュメントを参照してください。
SQSはメッセージキューです。キューの両端には producer と consumer がいます。producer がメッセージを送信して consumer がメッセージを受信します。
メッセージの受信方法が特徴的で3、 consumer は以下のような処理を行います。
- 「タイムアウトの時間を指定しつつ」メッセージを受信する
- メッセージの内容を解釈して実際の処理を行う
- メッセージの削除をおこなう。ただし、タイムアウト時間内にメッセージが削除されなかった場合は、そのメッセージは再度キューから受信できるようになり、1に戻る。
これは上述のトランザクションでいうと、メッセージの取得がトランザクションの開始に、メッセージの削除がコミットに対応すると言えます。ロールバックに関してはタイムアウト時間の経過により引き起こされると捉えることができます4。
対応表を作ると以下のようになります。
| 意味合い\ 実際の処理 | RDBの処理 | SQS の処理 |
|---|---|---|
| トランザクション開始 | BEGIN + 書き込みロック |
メッセージの受信 |
| コミット | COMMIT |
メッセージの削除 |
| ロールバック | ROLLBACK |
タイムアウト |
Exactly-Once なキューとは
SQSにはキューの種類が2種類あります。通常のキューとFIFOキューです。FIFOキューは名前の通り、（同一メッセージグループにおいて）先入れ先出しであることが保証されます。また Exactly-Once という性質があります。Exactly-Once については、あるメッセージが同時に複数の consumer に見えることがない、という意味です（以下抜粋）。
1 回だけの処理は、単一のコンシューマーおよび複数のコンシューマーシナリオの両方に適用されます。FIFO キューを複数のコンシューマー環境で使用する場合、現在のメッセージが削除されるか、可視性タイムアウトの有効期限が切れた後でのみ、メッセージを他のコンシューマーに表示するようキューを設定できます。
https://aws.amazon.com/jp/blogs/news/new-for-amazon-simple-queue-service-fifo-queues-with-exactly-once-delivery-deduplication/ より。
SQSを使ったシステム
SQSについての説明はここまでとし、次はSQSを使ったシステムを考えます。今回は consumer 側だけを考えるので十分です。consumer はメッセージを受け取りRDBに何らかの処理をするものとします。このとき、RDBとSQSの2つのデータソースがあるのでコミット順序についても選択肢が2つあります。
それぞれのケースについて、先にしたコミットだけが成功するケースを考えます。
「1. RDBへのコミットをしてからメッセージの削除を行う」について
RDBへのコミットが成功しメッセージの削除が失敗したケースです。この場合、メッセージの削除に失敗したメッセージは複数回受信されることになります。
重複受信であることを何らかの手段で判断して捨てるなど、処理自体を冪等にしておかないと本当に重複実行されてしまいます。
「2. メッセージの削除が成功してから RDB へのコミットを行う」について
メッセージの削除が成功しRDBへのコミットが失敗したケースです。この場合、メッセージの内容は処理されておらず、キューからも消えているのでメッセージがロストすることになります。
どちらを選択するか
上述の失敗ケースはどちらもSQS上で Exactly-Once が保証されているかに関係ありません。
通常のシステムではメッセージのロストは許されない5と思うので、メッセージの削除に失敗した時に重複処理が起きることを受け容れることになるでしょう。
重複処理が起きるということは当然 Exactly-Once ではありません。これがタイトルでいう「Amazon SQSでFIFOだからってシステム全体が Exactly-Once になると思ったら大間違いだ」という主張でした。具体的には、consumer の処理を冪等にするなどの対策がよいと思います。やっぱり冪等性が大事なんですねえ。
終わりに
本記事は業務での経験と、書籍 Designing Data-Intensive Applications で得た知識によって構成されています。
もうちょい俯瞰した話を Designing Data-Intensive Applications Chapter 11. Stream Processing の Atomic commit revisited から抜粋します。
In order to give the appearance of exactly-once processing in the presence of faults, we need to ensure that all outputs and side effects of processing an event take effect if and only if the processing is successful.
...
If this approach sounds familiar, it is because we discussed it in "Exactly-once message processing" in the context of distributed transactions and two-phase commit.
ここでの exactly-once はSQS本体ではなくて処理全体としての話です。出力と副作用、つまりRDBへのコミットとSQSからの削除は、全部成功したときにしか現れてほしくないと言っています。そしてそれは分散トランザクションや2相コミットに似てると。先程はSQSとRDBだったので分散トランザクションとかは考えなかったのですが、そういうアプローチで解決することも可能なんでしょうね。本では Google Cloud Dataflow や VoldDB、Kafka などにそういった取り組みがあると書いてあります。
同Chapterの Idempotence セクションでは、分散トランザクションではなく冪等性で解決できるよ、ということも書いてあります。
Our goal is to discard the partial output of any failed tasks so that they can be safely retried without taking effect twice. Distributed transactions are one way of achieving that goal, but another way is to rely on idempotence.
この辺りのセクションが特に参考になるかと思いますので気になった方は読んでみてください。全編通して面白いのでおすすめです。日本語版の発売も楽しみですね。
余談
実装上の tips ですがSQSに DeleteMessage を送ってみたらタイムアウトしていた、というのに対応するために、RDBへのコミットまでのタイムアウトを5秒にして、SQSに対するタイムアウト時間を10秒にするなどのバッファをもっておくことで、送ってみたらタイムアウトしていたケースをほぼなくすことができるはずです。
TokyuRuby会議13で『現場のRunyVM::AbstractSyntaxTree』というLTをしました
『Scalaスケーラブルプログラミング第3版』読了
- 作者: Martin Odersky,Lex Spoon,Bill Venners,羽生田栄一,水島宏太,長尾高弘
- 出版社/メーカー: インプレス
- 発売日: 2016/09/20
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (1件) を見る
読了しました。いわゆるコップ本。手を動かした結果は以下のレポジトリに置きました。
注意点
まず最初に手を動かすにあたっての注意点が1つ。 2.12.8 ではパーザコンビネータとSwingに関しては別ライブラリを追加する必要がありました。 過去のバージョンでは標準ライブラリとして添付されていたものが分離したようです。
$ scala -version Scala code runner version 2.12.8 -- Copyright 2002-2018, LAMP/EPFL and Lightbend, Inc.
https://github.com/hkdnet/cup-book/blob/4c855822a4711b2677507f0018f240a43eb1c28d/build.sbt#L14-L15
// build.sbt libraryDependencies += "org.scala-lang.modules" %% "scala-parser-combinators" % "1.1.2" libraryDependencies += "org.scala-lang.modules" %% "scala-swing" % "2.1.1"
感想
Scala 面白いですね。強力な言語だなーと思いました。
特に言語機能として面白いのは implicit ですかね。最初見たときはこれなにが起きてるかわけがわからんのでは……と思ったのですが、4つのリーズナブルな制約のもとでならそんなに変なことにならなそうでした。import をどこにでもかけてそれがレキシカルに参照されるので、読んだ当初は Ruby の refinements っぽいなーという気持ちになりました1。
あと trait に、「これを継承するなら継承するやつはこの型でなければならない」ということを明示できるのは面白かった。
PFDSやTaPLをやんわり読んでいるおかげでかなりスッと腹落ちしやすかったという感じはあります。純粋関数型の Deque とか出てくるし。償却時間とか言い出すし。共変・反変、Top/Bot あたりも出てくるし2。学んだことが別の本に出てくると嬉しいですね。
- 作者: Chris Okasaki,稲葉一浩,遠藤侑介
- 出版社/メーカー: KADOKAWA
- 発売日: 2017/04/28
- メディア: 単行本
- この商品を含むブログ (1件) を見る
- 作者: Benjamin C. Pierce,住井英二郎,遠藤侑介,酒井政裕,今井敬吾,黒木裕介,今井宜洋,才川隆文,今井健男
- 出版社/メーカー: オーム社
- 発売日: 2013/03/26
- メディア: 単行本（ソフトカバー）
- クリック: 68回
- この商品を含むブログ (11件) を見る
一方でなんかちょっと深入りしてないトピックもありそうでした。上述の variance の + - を書けるところのルールとかはかなり難しそうですし。あとパス依存型もさっと出てきて引っ込んでいったのであまりよくわかっていない。パス依存型のほうは言われて気づいたのでそういえばよくわからねえな、くらいのわかってなさです。
コップ本を20章まで読み終わったんだけど、variance annotationsとpath-dependent typeはこの本だけではちょっと理解仕切れないな。。
— y.kaneko (@spikeolaf) May 4, 2019
あとコレクションを自前実装するところ、制約が多くて実装者に知識を要求するなーという印象。まあいくつかの triat を無視しててもあとで必要になったときに実装すればいいのかもですが。
もともと Scala 学習のモチベは elasticmq のソースを読むところだったのですがそっちは全然手がついてません。たぶんこの本では触れられてなかったトピックとして、 Akka とかのことを知る必要がありそう。
elasticmq を読むモチベは仕事で使うからだったのですが、まあなんやかんやあって仕事で使わなくなったのでこの先学習するかはまた気分次第ですね。 別件でCコンパイラとかやってたらCPUの気持ちが知りたくなってきたのでまた別の分野に手を出すかもしれません。
C拡張のある gem を作れるようになる
はじめに
fukuokarb.connpass.com この記事は上記イベント会場で書いています。 Speee さん、 Fukuoka.rb の皆様ありがとうございます。
そういえばC拡張のgemって作ったことないなと思ったので作りました。RubyKaigi いくとなんかこういうことやりたくなりますよね。
https://github.com/hkdnet/fibc
このエントリではC拡張の gem ってどうなってるんだっけの解説、というほど高尚なものでもないですが今回認識したことを書きます。
C拡張を動かす
今回はCで複雑なロジックを書くことは考えず、フィボナッチ数列の n 番目の数を返すメソッドを追加することにする。つまりこんなメソッドを追加することを目的とする。
Fibc.fib(5) # => 8
bundle gem --ext fibc で雛形ができる。 --ext でC拡張用のファイルも作ってくれる。gemspec にTODOとかが追加されているので、以下それを解消しているものとして扱う。
ファイル構成はだいたいこんな感じ。
. ├── Gemfile ├── LICENSE.txt ├── README.md ├── Rakefile ├── bin │ ├── console │ └── setup ├── ext │ └── fibc │ ├── extconf.rb │ ├── fibc.c │ └── fibc.h ├── fibc.gemspec ├── lib │ ├── fibc │ │ └── version.rb │ └── fibc.rb └── spec ├── fibc_spec.rb └── spec_helper.rb
実は Rakefile にもそういう定義が追加されている。さっと確認すると compile などという単語が見え、:default のタスク定義にも compile が追加されているので、ビルドしてからテストするような感じになることがわかる。
$ bundle exec rake -T rake build # Build fibc-0.1.0.gem into the pkg directory rake clean # Remove any temporary products rake clobber # Remove any generated files rake compile # Compile all the extensions rake compile:fibc # Compile fibc rake install # Build and install fibc-0.1.0.gem into system gems rake install:local # Build and install fibc-0.1.0.gem into system gems without net... rake release[remote] # Create tag v0.1.0 and build and push fibc-0.1.0.gem to TODO: ... rake spec # Run RSpec code examples
# Rakefile require "bundler/gem_tasks" require "rspec/core/rake_task" RSpec::Core::RakeTask.new(:spec) require "rake/extensiontask" task :build => :compile Rake::ExtensionTask.new("fibc") do |ext| ext.lib_dir = "lib/fibc" end task :default => [:clobber, :compile, :spec]
gemspec の定義にも spec.extensions = ["ext/fibc/extconf.rb"] という設定があり、gem install 時にどう build すればよいのかを示していることがわかる。extconf.rb については後述する……予定だったがまあ実際 makefile を生成してるっぽいことくらいしかわからなかった。生成後の結果は tmp 配下に吐かれるので確認可能。
rake compile すると lib/fibc/fibc.bundle というファイルができる。これがC拡張をコンパイルしたもの。
最初 gem のエントリポイントである lib/fibc.rb に require 'lib/fibc/fibc' と書いてあって、そんなのないじゃんって思ってたのだけど、コンパイルしたものを require している。
ここまでわかったので、あとは ruby/ruby のコードを参考にしながら雑にメソッドを追加してみる。C言語において Ruby のモジュールを定義しているところを適当に参考にしながらやればよい。RubyKaigi で大人気だった RubyVM::AbstractSyntaxTree.of の定義している箇所を参考にする。ちょうどよく module に1引数のシングルトンメソッドを定義するという意味で非常に似通っている。
ruby/ast.c at 03c6cb5e8f503dcf6bc80a70a48a9775bbd2a47e · ruby/ruby · GitHub
cruby の世界では、Rubyのオブジェクトはすべて VALUE 型であり、また Ruby のメソッドは必ず戻り値をもつ。なので (VALUE self, VALUE n) -> VALUE な関数を定義してそれを使うことにする。とりあえずステップバイステップに実装するために、引数をそのまま戻す関数を定義してみる。
diff --git a/ext/fibc/fibc.c b/ext/fibc/fibc.c index 71788c7..4beb8a1 100644 --- a/ext/fibc/fibc.c +++ b/ext/fibc/fibc.c @@ -2,8 +2,15 @@ VALUE rb_mFibc; +static +VALUE fibc_fib(VALUE self, VALUE n) +{ + return n; +} + void Init_fibc(void) { rb_mFibc = rb_define_module("Fibc"); + rb_define_singleton_method(rb_mFibc, "fib", fibc_fib, 1); }
テストは適当に書いて動作確認おk1。
あとは適当にCで書いた関数を使いつつ FIX2INT, INT2FIX を使いながらCの世界とRubyの世界のオブジェクトを変更しておけば動く。
せっかくなのでベンチマークをとってみる。手元のマシンでやった適当な結果ですけどやっぱはやい。
$ cat bench.rb
require 'benchmark/ips'
require 'fibc'
Benchmark.ips do |x|
# These parameters can also be configured this way
x.time = 5
x.warmup = 2
# Typical mode, runs the block as many times as it can
x.report("naive") { Fibc.naive(10) }
x.report("fib") { Fibc.fib(10) }
# Compare the iterations per second of the various reports!
x.compare!
end
$ bundle exec ruby bench.rb
Warming up --------------------------------------
naive 19.611k i/100ms
fib 223.955k i/100ms
Calculating -------------------------------------
naive 195.295k (± 8.4%) i/s - 980.550k in 5.061215s
fib 4.174M (± 9.1%) i/s - 20.828M in 5.043693s
Comparison:
fib: 4174204.0 i/s
naive: 195295.2 i/s - 21.37x slower
動いてC拡張すごい、という気持ちになったところでおわり。ここまでは特に難しくなかったですね。
C拡張書くときに何が使えるのかとかがわからなかったり、Rubyでの処理がCのどの関数呼べばいいのかとかがわからないので次はもうちょい実践的な何かをチャレンジしていきます。
おまけ
objdump するとダミーシンボル的なものがあることがわかる(わからない(読めない
$ objdump -no-show-raw-insn -arch-name x86-64 -macho -x86-asm-syntax intel -D lib/fibc/fibc.bundle
lib/fibc/fibc.bundle:
(__TEXT,__text) section
_Init_fibc:
ec0: push rbp
ec1: mov rbp, rsp
ec4: lea rdi, [rip + 213] ## literal pool for: "Fibc"
ecb: call 0xf5c ## symbol stub for: _rb_define_module
ed0: mov qword ptr [rip + _rb_mFibc], rax
ed7: lea rsi, [rip + 199] ## literal pool for: "fib"
ede: lea rdx, [rip + _fibc_fib]
ee5: mov ecx, 1
eea: mov rdi, rax
eed: pop rbp
eee: jmp 0xf62 ## symbol stub for: _rb_define_singleton_method
ef3: nop word ptr cs:[rax + rax]
efd: nop dword ptr [rax]
_fibc_fib:
f00: push rbp
f01: mov rbp, rsp
f04: mov rdi, rsi
f07: call 0xf68 ## symbol stub for: _rb_fix2int
f0c: mov edi, eax
f0e: call _fibc_fib_int
f13: cdqe
f15: lea rax, [rax + rax + 1]
f1a: pop rbp
f1b: ret
f1c: nop dword ptr [rax]
_fibc_fib_int:
f20: push rbp
f21: mov rbp, rsp
f24: push r14
f26: push rbx
f27: mov r14d, 1
f2d: cmp edi, 2
f30: jl 0xf53
f32: mov ebx, edi
f34: add ebx, 2
f37: mov r14d, 1
f3d: nop dword ptr [rax]
f40: lea edi, [rbx - 3]
f43: call _fibc_fib_int
f48: add r14d, eax
f4b: add ebx, -2
f4e: cmp ebx, 3
f51: jg 0xf40
f53: mov eax, r14d
f56: pop rbx
f57: pop r14
f59: pop rbp
f5a: ret
-
見たければコミットを追ってください↩
GitHub の PullRequest でもう使ってない外部サービスがチェックに出てきて邪魔なとき
レポジトリ側の Settings > Branches のブランチルールに残っているケースが多い。
ブランチ側のルールの Require status checks to pass before merging から該当のサービスを抜いてやればよい。
