CAP 定理とは何か
データベースの勉強をしていると CAP 定理なるものに遭遇する。ずっと CAP 定理ってピンと来ないなぁと感じていたが、どうやら提唱者の Eric Brewer いわく CAP 定理は誤解された形で広がっているらしい。以下の記事に詳細がある。
自分が CAP 定理をよく理解できていないのは間違った説明を見ていたからかもしれない。ってことで今回は、上記の Eric Brewer の記事と Wikipediaのページ を参考に CAP 定理についてまとめてみた。(ちなみに、ざっとググってみた感じ CAP 定理について日本語で解説した記事はいくつかあるようだが、Eric Brewer が意図するものとは異なるものが多い印象を受けた。)
準備:"分散" と CAP
前提として、CAP 定理は分散データストア(Distributed data store)の性質に関して述べたのものである。分散データストアでは、ネットワーク上に分散された複数のストレージ(ノード)上にデータが格納されている。分散データストアではユーザのリクエストに対して、各所に散らばっているノードから関連するデータを収集する必要がある。CAP 定理はこのような分散データストアを前提としたものであり、1つのインスタンス内でデータのやりとりが完結するようなデータストアについて述べたものではない。
次に CAP 定理(CAP theorem)を構成する C, A, P の3つに対応する概念を説明する。
C は Consistency の頭文字である
Consistency とは「ユーザの読み取り処理のリクエストに対して、常に最新の書き込みを返せる」という、データストアが持つべき性質である。
そんなの当たり前に満たされるのでは?と思う人は、CAP 定理が分散データストアを対象としていることを思い出して欲しい。どこか遠くのノードに赤の他人が書き込み処理をしたとき、本当に自分が最新のデータを取得できているのか?場合によっては難しい問題であろう。
ちなみに、CAP の Consistency はトランザクションの ACID の Consistency とは別のものである。
A は Availability の頭文字である
Availability とは「ユーザのリクエストに対して、常にエラーでないレスポンスを返せる」という、データストアが持つべき性質である。
データストアのユーザからすると、分散データストアからデータを取得したいのに、エラーばかり返ってきては使い物にならない。こういう事態を避けるのが Availability の意図するところである。ただし、エラーでないレスポンスを返すことが Availability の要件であり、常に最新のデータを返さなくてもこの要件は満たされるものとする。
ちなみに Availability の説明として「単一障害点がないこと」を前提とする説明が見られるが、これは誤りだと思われる。こういうネットワーク構成の話をしているのではなく、あくまでユーザ目線で見たときにすぐにレスポンスを得られるかという観点が重要である。たとえ単一障害点で障害が起きても他のノードで該当するデータをキャッシュしていれば Availability を担保できる場合がある。また、障害のためユーザの更新処理を実行できない場合でも、ユーザに「リクエストを受け付けました」とレスポンスを返せば Availability を担保していると言える。ネットワークが復旧してから裏で更新処理をかければよい。
P は Partition tolerance の頭文字である
Partition tolerance とは「ノード間をつなぐネットワークの分断や遅延が起こってもデータストア全体としては可動し続ける」 という、データストアが満たすべき性質である。
分散データストアを構成するノード数は非常に大きくなる一方で、ネットワークを介した通信は必ずしも安定しないことが知られている。もし一部のノード間で障害が起こっただけでネットワーク全体がダメになってしまうようではデータストアとして使い物にならない。それに対して Partition tolerance が満たされている場合、ネットワークの一部が死んでも全体としては動き続けることが保証される。
CAP 定理とは
ここから CAP 定理の説明に入る。以降に登場する "C", "A", "P" はそれぞれ Consistency, Availability, Partition tolerance の略である。
まず前提として P は分散データストアとして必須の要件である。その理由は、P を想定しない分散データストアは、ネットワークの一部が死んだだけで全体が死ぬような非常に脆い構造であり使い物にならないからである。C, A, P の中にも優先度があり、P が最も優先されるべきということである。
そして CAP 定理は以下を主張するものである。
P を満たす分散データストアでは、C と A を同時に満たすような設計にはできない。
分散データストアを設計するにあたり、P の要件「ネットワークの一部が死んでも全体としては動き続ける」を満たすためには、ネットワークの一部が死んでいるかもしれない前提でユーザのリクエストを処理しなければならない。しかしこのとき、「ユーザに最新のデータを返す」(C の要件)と「ユーザにエラーを返さない」(A の要件)を両立することはできない、というのが CAP 定理の主張である。C と A のトレードオフについて述べたものである。
なぜこのような定理が成り立つのか?理由を考えてみると単純で、常に最新のデータを返す(つまり C を満たす)ことを優先した設計にするとネットワークの障害時にはその復旧を待つことになる。ユーザのリクエストが、障害の起きたネットワークを介するアクセスを必要とする場合、もちろんユーザはレスポンスが得られない(普通はタイムアウトエラーが返ってくる)。つまり A が満たされない。
一方、ネットワーク障害が起こっていても常にユーザに何らかのレスポンスを返すこと(つまり A を満たす)を優先した設計にすると、最新でないにしてもユーザにとって有用そうなデータにアクセスできるようにしておくことが望ましい。過去に使用したデータをキャッシュしたり、ノードのデータ全体を複製しておいたりするのが現実的なアプローチである。もちろん、そのような代替手段によって提供するデータは最新ではない可能性がある。つまり C が満たされない。
CAP 定理をとても簡単に言うと「分散データストアにおいて、最新のデータを提供し続けるならユーザを待たせることは避けられない一方で、ユーザを待たせないなら最新でないデータを提供することは避けられない」ということである。
CAP 定理に対するよくある誤解
ここまで述べたように、CAP 定理の主張はたいして難しいものではないし、分散データストアを設計するにあたりいかにも役立ちそうな知見である。しかし冒頭で述べたように世の中には誤解が広まっていて CAP 定理が意図するものを曖昧にしている。ここでは、生じそうな誤解に対して正しそうな解釈をまとめる。
「2つを選択すると◯◯」
よくある説明として「CAP 定理によると C, A, P のうち2つを選択すると残り1つは保証されない」のようなものがある。C と P、A と P の組み合わせはよいとして、C と A の組み合わせに対して「C と A を選択すると P は満たされない」と言ってしまうのが誤解を招きがちである。
「C と A を選択すると P は満たされない」という表現は、C でもあり A でもある設計にするとネットワーク障害が起きないシステムが構築される かのように聞こえる。そんなはずがない。実際は分散システムにおいて P を無視した時点でシステムとして成立しないのである。上記でも述べたとおり、分散データストアの設計として P が最優先で、C と A が次に考慮されるべきである。P は人間がコントロール不可能な現象に対応するためのものであり、C と A が設計思想として人間がコントロールする部分である。
P を無視して C と A を選択したくなるようなケースはそもそもデータストアに分散性がない状況なのかもしれない。その場合は CAP 定理など考えずに C と A を満たす設計を目指せばよい、とも言える。もっというと ACID を目指した設計にするのが自然である。
「プロダクトごとに CAP を決定する」
CAP 定理から導かれる結論として「プロダクトの方針として C を優先するか A を優先するか決めよう」とするのは早合点である。「このプロダクトは CP を採用していて、このプロダクトは AP を採用している」みたいな分類がこの勘違いを生む原因になっている気がする。
CAP の中でどれを優先するのかはシステムの実行時状態に応じで動的に切り替えればよい。たとえばネットワーク障害が発生していないことが明らかなときは常に C と A を保証するような設計にしておき、障害が発生したときだけ C または A の保証を諦めるような設計にすることもできる。
したがって「このプロダクトは AP を採用しています」と言っているからといって平常時でも C が犠牲にされているとは思わないほうがよさそう。ネットワーク障害が起きていない限りは最新のデータが返ってくる(C である)ことを期待してよい。
「C を捨てれば A が必ず保証される」
CAP 定理の主張は、P のもとでは「C と A を同時に満たすことはできない」というものである。この論理構造を勘違いして「C を否定すれば A が必ず成り立つ」とするのは誤りである。論理学に慣れていない人がしてしまいそうなミスである。
場合によっては C も A も満たされない可能性がある。論理的にいえば、CAP 定理は ¬ (C ∧ A ∧ P) である。P を仮定して導かれるのは ¬(C ∧ A) である。ここから ¬ C → A や ¬ A → C は導かれない。CAP 定理は C と A の両立性について限界を示しているに過ぎない。
もちろん C も A もあえて保証しないような設計にしても構わない。C や A は 0/1 ではなく、0-1 の値を取るファジーなものである。分散データストアに求められる要件を加味したうえで C と A がよいバランスになるような設計を目指すべきである。ただしどちらも 1 にすることはできないことだけ忘れないようにしたい。
ちなみに同様に、論理構造から来る勘違いとして「CAP のうち1つを捨てれば残り2つが満たされる」というものがある。これも誤りである。たとえば P を選択しないこと ¬ P を仮定するだけで CAP 定理 ¬ (C ∧ A ∧ P) は常に成り立つ。C や A が真であることが導かれるわけではない。
最後に
この記事の要約を1枚絵にまとめて終わろうと思う。P は必須で C と A をバランスさせるのが CAP 定理の意図するところである。ちなみに As-Is の絵は Wikipedia から借りてきた。
この記事では CAP 定理のユースケースを述べていないので、それについては Eric Brewer の記事 の記事を見るのがよいと思われる。銀行の ATM を設計するときに C と A のどちらを優先すべきか?みたいなことが書いている。金融システムなんだから C を優先すべきだろうってのが自分の直感だったが、どうやら A を優先することも多いらしい。ATM の利用者が金を預ける分には口座残高が不正になることはない(なので復旧後に口座に反映するのが簡単である)し、金が引き出されて残高がマイナスになるのはレアケースだしそうなっても後から回収したらええやろ、みたいなことらしい。なるほどなぁ。
あと、ネットワークの分断(network partition)から復旧する具体的な考え方なども同じく Eric Brewer の記事を参考にするのがよさそう。分断している間は各ノードで操作列を蓄積しておいて、復旧後にそれらをマージしたりするらしい。考えただけで頭が痛くなりそう。
おしまい。
関連記事:トランザクションの ACID については過去に整理したことがあるのでよかったら。
Redis に入門する
どうやらアプリケーションのキャッシュの用途のために Redis なるデータベースがよく使われるらしい。ってことで調べて動かしてみたメモ。
Redis とは
まずはざっとググってみた。公式サイト と Wikipedia の説明によると Redis には以下の特徴があるらしい。
- key-value 型のデータベースである。キャッシュを実現するためによく用いられる。
- 読み書きするデータがメモリ上に展開される in-memory database としての機能を提供している。もちろん、設定により様々なタイミングでストレージと同期できる。
- 場合によってはメモリめっちゃ食いそう
- データベース上のデータを操作するには特定のデータ構造に対する operation を実行する。SQL のような明示的なクエリを発行する方式ではない。
- このあたりは後で動かしながらイメージを掴みたい。
- Linux 上で動かすことが推奨されている。
Redis を動かしてみる
なんとなく概要をつかんだところで getting started を見ながら環境構築してゆく。
まずは インストラクション 通りに Ubuntu 上で apt-get install redis を実行する。無事インストール完了。
コマンドラインから redis-cli を起動して以下のようにコマンドを実行してみる。
$ redis-cli 127.0.0.1:6379> PING PONG 127.0.0.1:6379> set name t-keita OK 127.0.0.1:6379> get name "t-keita" 127.0.0.1:6379> exit
PING って打つと PONG って返してくれるらしい。これは疎通確認に使う。その後 set コマンドで name
という key をセットして、get コマンドで key に対応する value を取得できている。なるほど。
ちなみに exit してからもう一度以下のように get を実行してみる。
$ redis-cli 127.0.0.1:6379> get name "t-keita"
前回のセッションで設定した name の値が保持されていることが分かる。つまり set した値がストレージ上に保存されているんだけど、どこに保存されてるんだろう。
ちなみに Getting Started にある "Securing Redis" セクションの記載によると、Redis を起動するとサーバを起動し 6379 番ポートで処理を受け付けている。このサーバは、デフォルトではあらゆるアクセスを受け付けているのでセキュリティ的に危ない。少なくともファイアウォールの設定をして、外部からの直接的な命令の実行は避けるべきとのこと。もちろん、必要に応じてアクセス元に対して制約をかけたり認証を設けるべきである。そのための設定ファイルやオプションが提供されている。
データ構造いろいろ
次に Redis でサポートされているデータ構造をざっと眺める。Redis data types tutorial に記載されているサンプルコードを見てゆく。
- get, set コマンドで String 型の値の取得や更新ができる。
- mset, mget コマンドで複数の key-value ペアを扱える。
- exists コマンドでキーの存在確認ができる。
- expire コマンドでそのエントリーの存在期限を設定できる。これはキャッシュの管理に便利そう。ある程度古くなったら削除するみたいな。
- rpush, rpop で List 型の value への要素の追加や削除ができる。lrange で指定した範囲の値を取得できる。おそらく lrange の l は left ではなく list のこと。
- brpop は blocking operation であり rpop できるようになるまで n 秒間待つ。リストの更新内容をリアルタイムにキャッチアップしたいときに使えそう。
- hget, hset コマンドで Hash 型の値の取得や更新ができる。ハッシュマップなので O(1) のアクセスができる。JSON オブジェクトみたいなものを操作するときに便利そう。
あとは Set 型とかもあるが、データ構造や操作についてイメージがつかめたのでここでいったん終わり。
要するに Redis では value として一般的なプログラミング言語でサポートされているようなデータ構造(文字列、リスト、連想配列など)がサポートされていて、それに対して predefined な operation を作用させることでデータベースの状態を更新できる。この操作が atomic になっているので便利なわけだ。
プログラムから Redis を動かしてみる
つぎにプログラムから Redis を動かしてみる。
Redis にアクセスするため様々なプログラミング言語に対してライブラリが 提供されている。言語はなんでもよいんだが、Rust 向けのライブラリである Redis-rs をクライアントとして使ってみる。
GitHub リポジトリの README.md を見ながら以下の操作を試してみた。
まずは cargo の依存関係に以下を追加する。
[dependencies] redis = "0.22.1"
そして以下のようなプログラムを書いてみた。Redis とのコネクションを確立して name
に対応する値を get するだけ。
use redis::Commands; fn get_value_from_redis(name: &str) -> redis::RedisResult<String> { let clinet = redis::Client::open("redis://127.0.0.1/")?; let mut con = clinet.get_connection()?; con.get(name) } fn main() { match get_value_from_redis("name") { Ok(value) => { println!("Got the value {}", value); } Err(_) => { println!("err"); } } }
"get" みたいな operation を示す文字列を Redis に投げるのではなく、redis-rs が提供する get 関数を叩けばよい。
以下のようにビルドして実行してみるとちゃんとデータベースから値を取得できていることが分かる。
$ cargo build $ ./target/debug/redis_sample Got the value t-keita
Redis がサポートする各 operation に対応する Rust の関数が提供されているので、アプリケーションとデータベースのシームレスな接続ができているように思われる。
環境構築にあたり特につまることがなかったのもグッド。
気になったことを調べる
ここまでのチュートリアルで Redis の動作に対するイメージが湧いたので、最後に気になったことを追加で調べて終わりにしたい。
Redis のデータはストレージ上のどこに保存されている?
Redis は in-memory データベースであるが、もちろんストレージ上にデータを保存できる。しかし Redis を起動したときにはすでにデータベースに接続されており、データベースの内容が保存されている場所がユーザからは隠蔽されている。いったいどこに保存されているんだ。
ググってみると、Redis の設定ファイルは /etc/redis/redis.conf
にあるらしく、この中に以下のような作業ディレクトリを指定している箇所がある。
# The working directory. # # The DB will be written inside this directory, with the filename specified # above using the 'dbfilename' configuration directive. # # The Append Only File will also be created inside this directory. # # Note that you must specify a directory here, not a file name. dir /var/lib/redis
自分の環境では作業ディレクトリとして /var/lib/redis
が指定されているようで、確かに以下のように dump.rdb
というファイルが存在している。
$ sudo ls /var/lib/redis/ dump.rdb
このファイルの中身はバイナリだが、xxd コマンドなどで覗いてみると確かにデータベースに保存した内容が格納されているように見える。おそらくこれが正解。
どんなプロトコルを使って Redis とクライアントは通信している?
コマンドラインから起動する redis-cli を見る限り、命令は 127.0.0.1:6379
に投げられているように見える。接続先を IP アドレスとポート番号で指定できるのはよいとして、その上でどんなプロトコルを使って通信が行わているのか気になる。
ググったところ、RESP protocol という独自の通信プロトコルを定義しているらしい。仕様が 公式ページ に思いっきり載っていた。RESP は TCP を前提に定義しているらしく、TCP/IP に従う Application Layer として RESP が定義されている感じか。データベースを作るために独自の通信プロトコルを定義するとは気合いが感じられる。
1つのマシンに複数の Redis インスタンスを保持することは可能か?
ここまでの話で、データが格納されるストレージの情報はクライアントからは隠蔽されているように思われる。たとえばアプリケーションに応じて使用するデータベースインスタンスを切り替えたりするような用途を想定していないように見える。OS とデータベースが一対一対応するようなイメージ。この理解は正しそうか?
ググってみたところ、普通に port を分ける形で複数の Redis インスタンスを起動できるらしい。このページ とかに設定方法が書いてある。port ごとに設定ファイルを作るだけで別々の Redis インスタンスが起動する。
しかしながら、おそらく1つのマシンで複数の Redis インスタンスを起動するような使い方は意図されていないように思われる。Scaling with Redis Cluster のページなどを見る限り、Redis は horizontal scaling に重きを置いており、Redis をホストするコンテナをたくさん作ってデータベースの処理負荷を分散させるようなユースケースに強みがありそう。そのため1つの Redis インスタンスは1つのアプリケーションさえ想定できれば十分なんだろう。知らんけど。
以上、Redis についてざっと調べて動かしてみたメモでした。Redis の公式ページのドキュメントが非常に充実していて人気がある理由も納得。
おしまい。
React Native で全画面表示にする方法
例によって React Native 修行中である。Expo SDK を使って開発して、Expo Go でシミュレータを動かして、EAS でリモートビルドして、たいへん便利である。
ただ全画面(フルスクリーン)表示に問題があったので調べて解決したメモ。
困ったこと
React Native + Expo + EAS で Android アプリの開発をしているとき全画面表示が上手くいかない。Expo SDK のバージョンは 46.0.9。
具体的には、ナビゲーションバーやステータスバーを非表示とするため Expo のドキュメント にしたがって app.json のandroidNavigationBar.visible
属性を immersive
としていた。expo-navigation-bar
をインストールしたうえで以下のように設定する感じである。
{ "androidNavigationBar": { "visible": "immersive" } }
これで Expo Go によるシミュレータではちゃんと全画面表示になる。しかし、EAS でビルドして実機の Android 端末で動かすと全画面表示にならないのである。ビルド時に特にそれらしいエラーが出ていないし解決策が分からない。困った。
解決策
かなり真面目にググったところ以下のようなページがあり、結論から言うと、このページに記載されている方法で EAS ビルドしても全画面表示が保たれるようになった。
fyi/android-navigation-bar-visible-deprecated.md at master · expo/fyi · GitHub
どうやら、Expo の app.json に記述する androidNavigationBar.visible
属性は、ビルドすると Android SDK の View.setSystemUiVisibility
に変換されるようである。そして、この API がAndroid API level 30 から deprecated になっている。API ドキュメント にもそう書いてある。これが原因で、今回のビルド後に全画面表示されない問題が引き起こされているっぽい(定かではないが)。
これを回避する方法として、以下の手順を実施すれば全画面表示を実現できる。
手順1. ライブラリのインストール
まず expo-navigation-bar と expo-status-bar をプロジェクトの依存関係に追加する。expo install とか叩けばオッケー。
手順2. ライブラリの呼び出し
そして、ナビゲーションバーとステータスバーを非表示にするため、プログラム内で以下を呼び出す。自分は常に全画面表示にしたかったので App.js 内で呼び出すようにした。
import * as NavigationBar from "expo-navigation-bar"; import { setStatusBarHidden } from "expo-status-bar"; NavigationBar.setPositionAsync("relative"); NavigationBar.setVisibilityAsync("hidden"); NavigationBar.setBehaviorAsync("inset-swipe"); setStatusBarHidden(true, "none");
手順3. app.json の編集
さきほど記載した androidNavigationBar.visible
の部分を以下に置き換える。
{ "androidStatusBar": { "hidden": true }, "plugins": [ [ "expo-navigation-bar", { "position": "relative", "visibility": "hidden", "behavior": "inset-swipe" } ] ] }
こうすれば EAS ビルドしても全画面表示になる。めでたし。
React Native でテキストを枠内に収める方法
最近子どもがスマホのゲームでよく遊ぶので、自分でも簡単なスマホゲームを作ってあげたい気持ちに溢れている。我が子のツボはよく分かっているので(子にとっては)バチバチに面白いゲーム作れる気がするぞ。
React Native を使ってアプリを作ってみているが、フォントサイズの調整にやや困ったのでメモ。
困ったこと
React Native の利点は、1つのソースコードを書くだけでさまざまな環境で動くモバイルアプリを実装できることである。一方、環境によってはフォントサイズとレイアウトの兼ね合いが悪く、アプリの画面上の見た目が崩れることがある。
今回は、Text コンポーネントのフォントサイズをなるべく大きくしたいが、枠からはみ出ないように調整する方法を調べた。
解決策
以下のように Text コンポーネントの adjustsFontSizeToFit 属性を指定する。
<View style={{ flex: 1, justifyContent: 'center', alignItems: 'center' }}> <View style={{ width: 200, height: 30, borderColor: 'black', borderWidth: 1 }}> <Text style={{ fontSize: 32 }} >This is a sample message.</Text> </View> <View style={{ height: 50 }}></View> <View style={{ width: 200, height: 30, borderColor: 'black', borderWidth: 1 }}> <Text style={{ fontSize: 32 }} adjustsFontSizeToFit>This is a sample message.</Text> </View> </View>
このサンプルコードの実行結果は以下のようになる。
上にある Text コンポーネントではテキストが枠からはみ出してしまっているが、下にある Text コンポーネントではテキスト全体が枠に収まっている(収まるようにフォントサイズが小さくなっている)。いい感じ。
ちなみに Text コンポーネントの adjustsFontSizeToFit 属性のドキュメントは こちら にある。とはいっても、
Specifies whether fonts should be scaled down automatically to fit given style constraints.
ってな説明で、与えられた制約を満たすようにフォントサイズを自動的に小さくするってだけ。具体的な実装は見ていないのでどんな環境でどのくらいいい感じにフォントサイズを調整してくれるのかはよく分からない。
応用
Text コンポーネントは numberOfLines という属性も持っていて、これでテキストを表示するときの最大行数を指定できる。これをadjustsFontSizeToFit 属性を組み合わせることで、改行しない制約のもと、枠からはみ出さないようにフォントサイズを自動調整できる。
サンプルコードは以下である。先ほどの例より長いテキストを表示する例になっている。
<View style={{ flex: 1, justifyContent: 'center', alignItems: 'center' }}> <View style={{ width: 200, height: 50, borderColor: 'black', borderWidth: 1 }}> <Text style={{ fontSize: 32 }} numberOfLines={1}>This is a long long long long long sample message.</Text> </View> <View style={{ height: 50 }}></View> <View style={{ width: 200, height: 50, borderColor: 'black', borderWidth: 1 }}> <Text style={{ fontSize: 32 }} adjustsFontSizeToFit>This is a long long long long long sample message.</Text> </View> <View style={{ height: 50 }}></View> <View style={{ width: 200, height: 50, borderColor: 'black', borderWidth: 1 }}> <Text style={{ fontSize: 32 }} adjustsFontSizeToFit numberOfLines={1}>This is a long long long long long sample message.</Text> </View> </View>
このサンプルコードの実行結果は以下である。
上の Text コンポーネントは特に何も指定していないのでテキストがはみ出ている。真ん中は adjustsFontSizeToFit だけが指定されており、今回は改行すれば枠に収まるので2行で表示されている。最後に、下の Text コンポーネントは numberOfLines 属性が1、つまり最大1行で表示するように指定されているのでフォントサイズをかなり小さくして1行で表示されている。この例ではフォントサイズが小さすぎだが、改行するよりフォントサイズが小さくなったほうがマシというケースは多々あるだろう。
おしまい。
参考:
Flow Free を自動で解く
子どもが「なんかゲームしたい」と言うので、子どもでも出来そうなスマホゲームを探してみた。すると Flow Free というゲームが目に留まった。一言でいうと迷路みたいなゲームで、実際4歳児でも楽しく遊べる感じであった。しかし、問題の規模が大きくなるにつれて大人でも解くのが難しくなる。NP hard っぽさがある。ってことで大人らしく Flow Free のソルバーを書いてみたメモ。これができたらクラスのヒーロー間違いなし。
Flow Free とは?
まずはゲームの説明をする。問題では以下のようなパネルが与えられる。
見ての通り、同じ色の石が2つずつ存在する。クリアの条件は、これらのペアを結ぶ経路ですべてのマスを埋め尽くすことである。たとえばこの問題の正解は以下である。
なんとも簡単である。考える時間は3秒もあれば十分だろう。
しかし、難易度が増すと以下のような問題が出てくる。
これが難しい。「どの色から手を付けようか?」「つないだ経路が間違ってたらいつ気付けるのか?」そんなことばかり考えてマジでなかなか解けない。
アルゴリズムの方針
この問題を自動で解くためのアルゴリズムを考えたとき、まず初めに、問題から必要十分な制約を抽出して SMT ソルバーに投げることを考えた。各マスに対応する変数に値を割り当てる問題として捉えれば解けそう。しかしこの方針はあまりワクワクしないので気が向かなかった。
次に考えたのは探索ベースの手法である。パネルの状態を遷移させながら正解にたどり着くまでトライ&エラーを繰り返すアプローチである。人間が解く時と同じような発想であり、アルゴリズムの実装しがいがありそう。ってことでこっちを採用した。
問題を解くコツを知るため、自分自身で簡単な問題から難しめの問題までいくつか解いてみた。すると、以下の3つの手順の繰り返しでだいたいの問題が解けそうなことが分かった。
これらの手順をすべてのペアが経路でつながるまで繰り返せば終わり。ってことで各手順の詳細を説明する。
手順1. 現在の状態から正解に到達可能か?
探索が進むなかで現在の状態が正解に到達しうるものかを判定する方法を説明する。
まず、以下のようなコの字型の行き止まりが出現した場合は枝刈りを行う。理由は簡単で、2点を結んだ結果すべてのマスをカバーすることが問題を解くために必要であるが、行き止まりが1つでも存在したらすべてのマスを埋め尽くせないからである。
次は微妙なパターンだが、色々な問題を手で解いてみたところ、隣接した4マスを1色でたどる経路は正解に含まれなかった。Flow Free の隠された制約だろう。ってことで以下のパターンが現れたら探索の枝刈りを行う。
そして、以下のパターンが出現したら枝刈りを行う。理由は、この形によって残された2マスを辿るには、上記の隣接4マスの経路が必要になるからである。
最後に、すべての色のペア同士が到達可能であるかを調べる。ある経路によってパネルが複数の 連結成分 に分離された場合、同じ色のペアは同じ連結成分に属する必要がある。たとえば以下の状態では黄色のペアが到達不可能なので正解に至ることはない。
手順2. 決定論的な状態遷移
つぎに「この状態のときはこう状態を遷移させるしかない」というパターンを説明する。ただ説明が面倒なので2つのパターンだけ抜粋して紹介する。
まず、経路の伸ばし方が1通りしかない石があればそれを伸ばす。以下の例の左上の青色はその例である。左上の青色は経路を下に伸ばすしかない。なので下に伸ばす。
あとは、行き止まりを生み出さないことを考えると状態遷移が1通りに定まるパターンがある。たとえば以下の画像はパネルに右上の隅あたりを示したものである。この状態からは緑を右に伸ばす必要がある。というのも、右以外に伸ばすと右上のマスが行き止まりになってしまうからである。
手順3. 非決定論的な状態遷移
いよいよ non-deterministic に状態を遷移させるところまで来た。方針は簡単で、状態を見て経路を伸ばすとよさそうな石を決め、可能なすべての次の状態に遷移させるだけである。
「経路を伸ばすとよさそうな石」の決め方は「状態遷移の選択肢がもっとも少ないもの」とした。左右上下の4つに経路を伸ばせる石より、右と上の2つにしか経路を伸ばせない石を優先するといった感じである。探索問題において自由度の低いところから優先的に分岐させていくのは常套手段である。こうすることで、自由度が高いと思われていた部分の状態遷移も、探索が進むにつれて選択肢が限られてくるものである。
1つの石に着目してすべての状態遷移を列挙するので正解が探索空間から漏れることはない。探索アルゴリズムを設計するときはこういう観点は重要。英語だとアルゴリズムの completeness って言うようね、きっと。
実装してみた
上記の方針でこの規模の問題を解くソルバーを自作した。Rust で書いた。ソースコードは Gist に置いた。
そして冒頭で述べた問題を解いてみる。以下のような配置であった。
ソルバーに食わせるため以下のように文字列にエンコードする。
- - - - A - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - B - - - - - - - - C - - D E F - - G - - - - - - D E - - - - - - - - - - - - - - - - - B - - - - - H - I - - - - - I - - - - - - - - J - - - - J - - - - - - - - - - - - A - - - - - - K - - - - - - - - - - - - - - - - L - - K - G - M - - - - - - - N - M - F - C - - - - - H - - - - - L - - - - - - - - - - - - - N O - - - O
そしてソルバーを実行すると約5秒で以下の結果が得られた。
A A A A A F F F F F F F F F A F F F F F C C C C C C C F A F C C C C C B B M M M C F A F C D D D E F B M G M C F A F F D E E E F B M G M C F A A F F F F F F B M G M C F H A I I I I I I I M G M C F H A A J J J J J J M G M C F H H A A A A A A M M G M C F K H K K K K K M M G G M C F K H K L L L K M G G M M C F K H K K N L M M F F C C C F K H H K N L L L L F F F F F K K K K N N N N N O O O O O
これを元の問題にプロットしてみると以下のようになった。
解けてる。めでたし。
所感
Rust に慣れていこうということで今回はソルバーを書いてみたが割と楽しかった。Rust は速いので安心感がある。今回はデータ構造とかあまりちゃんと考えていないのでデータのコピーとか大量発生している。メモリ上のデータを再利用とかすればもっと速くなると思う。そこまでエンジニアリングの気力は無かったが。
Flow Free のソルバーを書いた例はわりとあるらしく、たとえば以下のページでかなり細かく解説されている。自分も実装が終わった後にこのページを見てみたが、本記事で紹介したアイデアがすべて網羅されているように見えた。どう考えても自分以上のコンピュータサイエンス力がありそうな人だ。世の中にはスゴい人がいるなぁ。
静的リンク・動的リンク・動的ローディングの違い
今日のネタはリンカの仕事について。低レイヤな話としてありがちだが、いかんせんバイナリを入力にバイナリを出力する処理なので直感的に理解しづらい。ってことで調べながらメモる。
リンカ(linker)とは何か
リンカ とは、コンパイルされたファイル(オブジェクトファイル)同士をつないで実行可能なファイルを作るプログラムである。ほとんどの場合、ソースコードはファイルごとにコンパイルされ、ファイルごとにオブジェクトファイルが生成される。他方、プログラム中で外部ファイルで定義されたシンボル(変数名や関数名など)を参照する場合がある。たとえばライブラリ中に定義された関数を呼び出す場合などである。リンカの役割は、このようなファイル内を見ただけでは正体不明のシンボルと外部ファイルに含まれる定義を紐付けることである。
リンカには静的リンクと動的リンクの2種類がある。以下にそれぞれについてざっくりまとめる。
静的リンク
静的リンクは、正体不明のシンボルを定義しているすべてのオブジェクトファイルを、動かしたいオブジェクトファイルの中に静的にコピーするようなやり方である。後述する動的リンクと違い、コンパイル時にすべてのリンク作業を完了できるため、実行時にリンク関連のエラーが起こることがない。一方、あらゆる依存先のファイルを1つのオブジェクトファイルに詰め込むので、ファイルサイズが大きくなる傾向がある。
個人的なイメージとしては、Docker みたいなコンテナにすべての依存関係を封じ込めてしまう発想と似ていると思う。ホストのシステム全体で見ると同じ依存関係があちこちに出てきて冗長であるが、実行時にコケないという性質はかなり重宝される。ストレージの容量が飛躍的に増えた現代では静的リンクがベターな選択肢になることも多いと思われる。
ここからは静的リンクによって実行ファイルを作る実験をしてみる。C 言語でやってもつまらないので C++ と Rust の組み合わせでやってみる。ホストマシンは Ubuntu 20.04.4。
まずはライブラリ側のコードとして適当な C++ のプログラムを定義する。引き算をする minus
関数を定義しているだけである。このファイルを hello.cpp と名付ける。
extern "C" { int minus(int a, int b); } int minus(int a, int b) { return a - b; }
そしてこのファイルをライブラリとしてコンパイルする。まずは 拡張子.o
のオブジェクトファイルを作って、拡張子 .a
のアーカイブファイルに追加する。静的リンクを使うときはアーカイブとしてまとめるのが一般的なやり方である。アーカイブ名を `libxxx.a" のようにするのは守るべき命名規則である。
$ g++ -c -o hello.o -static hello.cpp $ ar rv libhello.a hello.o
次にこのライブラリを呼び出す Rust プログラムを以下のように定義する。リンク時に minus
という関数が正体不明なので、このファイル単体では実行できない。
extern "C" { fn minus(a: i64, b: i64) -> i64; } fn main() { unsafe { println!("100-3 = {}", minus(100, 3)); } }
cargo を使って Rust プロジェクトをコンパイルする。このとき以下のようなビルドスクリプト build.rs
を記述してやる。
fn main() { println!(r"cargo:rustc-link-search=native=/(省略)/clang_lib"); println!(r"cargo:rustc-link-lib=static=hello"); }
1つ目の命令では、正体不明のライブラリがあったら clang_lib
ディレクトリを探しに行けばよいことを教えている。ちなみに /lib
と /usr/lib
はデフォルトで検索対象になっている。(man ld
とかすればデフォルトのディレクトリを確認できる。)2つ目の命令でリンク方法が 静的(static)であることを教えている。
そして、プロジェクトをビルドし、その成果物であるプログラムを実行する。ちゃんとライブラリ側の minus
関数を呼び出して 100-3 を計算できたことが分かる。
$ cargo build Compiling invoke_c v0.1.0 (/(省略)/invoke_c) Finished dev [unoptimized + debuginfo] target(s) in 0.88s $ target/debug/invoke_c 100-3 = 97
静的リンクを実行して得られたオブジェクトファイルを覗いてみる。
$ readelf -s target/debug/invoke_c | grep minus // Num: Value Size Type Bind Vis Ndx Name 572: 0000000000008025 22 FUNC GLOBAL DEFAULT 14 minus
この結果から、オブジェクトファイルが持っているシンボルテーブルに含まれている minus
というシンボルはオフセットが 0x8025
のアドレスに定義があることが分かる。
以上、静的リンクでした。
動的リンク
静的リンクとは対照的に、動的リンクではプログラムの実行開始直後にリンク処理が行われる。コンパイル時にはリンクは行われず、正体不明のシンボルはプログラムが実行されるまで正体不明のままである。ちなみに、この動的なリンク処理はオペレーティング・システムが担う役割である。
実行時に適切なライブラリが見つからないと実行時エラーが起きてしまう。一方で、ライブラリのコードを埋め込むわけではないので、複数のプログラムから利用されるライブラリが存在する場合はストレージ容量の節約になる。この利点が大きいので Linux では基本的に動的リンクが利用される。
ここからは先ほどと同様にして動的リンクの実験をしてみる。
まずは共有オブジェクト(shared object)としてライブラリのコードをコンパイルする。結果として拡張子 .so
のファイルが得られる。
$ g++ -shared -o libhello.so hello.cpp
cargo のビルドスクリプトは以下のようにする。dylib=
によって動的リンクを行うことを示している。また、hello
を指定することで実行時には libhello.so
というライブラリが必要であることを示している。
fn main() { println!(r"cargo:rustc-link-search=native=/(省略)/clang_lib"); println!(r"cargo:rustc-link-lib=dylib=hello"); }
そしてプロジェクトをビルドする。
$ cargo build Compiling invoke_c v0.1.0 (/(省略)/invoke_c) Finished dev [unoptimized + debuginfo] target(s) in 0.46s
まずは何も考えずにビルド成果物を実行してみる。
$ target/debug/invoke_c target/debug/invoke_c: error while loading shared libraries: libhello.so: cannot open shared object file: No such file or directory
このエラーメッセージは libhello.so
という共有ライブラリが見つからないと言っている。この共有ライブラリがコンパイル時に指定されたんだから実行時に必要なはずだけど、それが見つからない状況である。ちなみに以下で libhello.so
が必要であることは確認できる。
$ readelf -a target/debug/invoke_c | grep libhello.so 0x0000000000000001 (NEEDED) Shared library: [libhello.so]
この問題を解決する方法として、動的リンクによってライブラリを検索する場所を環境変数 LD_LIBRARY_PATH
の値として設定すればよい。結果として以下のコマンドで実行に成功する。
$ LD_LIBRARY_PATH=/(省略)/clang_lib/ target/debug/invoke_c 100-3 = 97
ついでに生成されたオブジェクトファイルのシンボルテーブルを見てみる。
$ readelf -a target/debug/invoke_c | grep minus // Num: Value Size Type Bind Vis Ndx Name 571: 0000000000000000 0 FUNC GLOBAL DEFAULT UND minus
以下の結果により minus
というシンボルが未定義(UNDefined)であり、アドレスも適当な値として 0 で埋められていることが分かる。
また以下のコマンドの結果より、オペレーティング・システムがこのバイナリファイルを読んだときに動的にリンク処理を行うための情報が格納されていることが分かる。
$ readelf -a target/debug/invoke_c | grep ld-linux [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] 0x0000000000000001 (NEEDED) Shared library: [ld-linux-x86-64.so.2]
インタプリタとして ld-linux-x86-64.so.2
が必要らしい。リンカなしでは生きてゆけない。
これで動的リンクについてはおしまい。
動的ローディング
最後に、動的リンクと混同されがちな 動的ローディング について説明する。ローディングとはオブジェクトファイルをメモリ上に載せる操作である。この時点でリンクとは別物である。
特に、動的リンクはオペレーティング・システムの仕事であるのに対して、動的ローディングはアプリケーションの仕事である。アプリが好きなタイミングで外部のオブジェクトファイルをメモリに載せて実行するような操作である。動的リンクはプログラム実行開始直後に行われるのに対し、動的ローディングは任意のタイミングで実行される可能性がある。
今日はもう眠いのでやりたくないが、動的ローディングの実験もしてみる。先ほど作った共有ライブラリを Python プログラムから呼び出す。
Python ファイルは以下の通りである。 これを main.py と名付ける。
import ctypes libhello = ctypes.CDLL("/(省略)/libhello.so") print("100-3 =", libhello.minus(100, 3))
ここでは CDLL
という API によって動的ローディングを行っている。これは裏では dlopen などの API を呼び出している。そのソースコードは このあたり だと思われる。(ちなみに dlopen はシステムコールではなく共有ライブラリが提供する API である。最終的には mmap などのシステムコールが呼ばれる。)
プログラムを実行してみるとプログラムを動的にロードできていることが分かる。
$ python3 main.py 100-3 = 97
めでたし。
PyTorch の推論時のオーバーヘッドを調べてみた
論文投稿が終わって解放感がスゴい。勢いあまって PyTorch の推論の高速化について実験したのでその結果をここにまとめる。もちろん機械学習は勉強中なので手探りで実験しながら調べている感じである。アホみたいなことをしている可能性がある。
悩ましい(と思っている)ところ
ニューラルネットワーク用のライブラリといえば今は PyTorch やら TensofFlow やらが主流なんだろうけど、どちらも Python 向けに作られている。Python と聞くと遅いイメージがあるが、Python から API を叩くと裏では C++ でカリカリにチューニングされたプログラムが動いているので学習は効率的に行われる。別に不満はない。一方で推論時は、モデルに入力を食わせて出力が欲しいだけなのに、推論のたびに Python から C++ を呼び出すみたいなことが起こる。自分の機械学習の用途からすると1回の探索につき学習済みモデルを100万回くらい呼び出したいこともある。そうなると、言語をまたいでプログラムを実行するオーバヘッドが膨らみすぎるのである。処理の高速化のために機械学習を使いたいのに、機械学習を使うと実行時間が膨れ上がってしまう。これをどうにかしたい。そこでオーバヘッドを含む推論の高速化の方法を調べながら比較実験してみた。
適当なモデルを作る
まずは今回の実験用に適当なニューラルネットワークを定義する。以下のようにしてみた。
class MyNN(torch.nn.Module): def __init__(self): super().__init__() self.a = nn.Linear(2, 8) self.b = nn.Linear(8, 8) self.c = nn.Linear(8, 1) def forward(self, x): x = nn.ReLU()(self.a(x)) x = nn.ReLU()(self.b(x)) x = self.c(x) return x
隠れ層が1つだけのニューラルネットワークを定義している。そして適当に入力を用意して学習させてみる。PyTorch でよく見る感じの、確率的勾配法によって重みを調整する流れである。最後に、学習したパラメータを保存している。
(省略) model.train() for _ in range(n_epochs): for x, y in zip(X, Y): optimizer.zero_grad() predicted = model(x) loss = loss_fn(predicted, y) loss.backward() optimizer.step() torch.save(model.state_dict(), "model_py.pt")
コード全体は Gist に置いた。本記事のコードはすべて同じ Gist のページに置いている。今回は という関数を近似してみた。どんなパラメータであっても推論速度に差は出ないのでどうでもよいのだが。
Python でロードして呼び出す場合
ここからは推論にかかる時間を計測する。まずはおそらく推論時のもっとも素朴なやり方であるモデルをロードするやり方をやってみる。以下ではモデルをロードした上で100万回の推論を行っている。
size = 1_000_000 input_values = list(map( lambda _: [random.uniform(-10, 10), random.uniform(-10, 10)], range(size))) X = torch.tensor(input_values) model = MyNN() model.eval() model.load_state_dict(torch.load("model.pt")) import time start = time.time() for x in X: model(x) print(time.timeit() - start)
実行時間は 124 秒だった。これは遅い。日が暮れる。
Python で TorchScprit を呼び出す
次にやってみるのは TorchScript というテクノロジーである。モデルを Python の実行環境に依存しない形で保存したりロードしたりできるらしい。Python に非依存である代わりに TorchScript 言語専用のインタプリタが存在しているようなので、ある意味新たな言語を仲介してモデルにアクセスできるようになっていると思ったらよさそう。仕組みはよく分かっていないが Java や C++ からも TorchScript を叩きやすいらしい。もしかして Java から TorchScript を利用する場合は JVM 上で動く TorchScript のインタプリタが存在している?よく分からんが、まずは Python から使ってみよう。
TorchScript のチュートリアル を見ながら進める。モデルを TorchScript の形式で保存するのは簡単で、以下のようにモデルを保存する部分だけ書き換えればよい。
example = torch.tensor([random.uniform(-10, 10), random.uniform(-10, 10)]) traced_script_module = torch.jit.trace(model, example) traced_script_module.save("../model_torchscript.pt")
モデルに適当な入力を食わせる tracing という方法でやってみた。どうやら TorchScript として保存するためには Python インタプリタを動かしてみることに意味があるらしい。動的解析みたいに見えるが、おそらくモデルの保存は安全に行われると思う。謎テクノロジーだ。
そして TorchScript をロードして100万回推論を実行してみた。
model = torch.jit.load("../model_torchscript.pt") start = time.time() for x in X: _ = model(x) print(time.time() - start)
実行時間は 54 秒だった。同じ Python でもオーソドックスなモデルの保存方法より推論時の性能が向上することが分かった。なにか最適化が走っているのだと思われる。Python でモデルを保存するときは TorchScript でやるのが今後の主流になるのかな。
Java で TorchScript を呼び出す
TorchScript として保存したモデルは他のプログラミング言語から呼び出すのが簡単らしい。ってことで次は Java からモデルをロードして推論を実行してみた。このソースコード を参考に実装した。
実装した Java コードは以下である。
Module mod = Module.load("../../model_torchscript.pt"); int size = 1000000; (中略) long start = System.currentTimeMillis(); for (int i = 0; i < size; i++) { Tensor inputs = Tensor.fromBlob( data[i], new long[]{2} // shape ); mod.forward(IValue.from(inputs)); } long elapsed = (System.currentTimeMillis() - start); System.out.println(elapsed);
実行時間は 35 秒であった。わりと速い。
以下、Java から PyTorch を動かすためのメモ:
まず、Java プロジェクトの pom.xml に以下を追加した。これで Pytorch を動かすための Java API が叩けるようになる。
<dependencies> <dependency> <groupId>org.pytorch</groupId> <artifactId>pytorch_java_only</artifactId> <version>1.11</version> </dependency> </dependencies>
また、裏で動く Pytorch として ここの指示 の通りに LibTroch (version 1.11.0) をダウンロードしてきて Java の実行時の VM 引数に -Djava.library.path=/(省略)/libtorch/lib
を指定した。
C++ から TorchScript を呼び出す
同様に、C++ から TorchScript を呼び出してみる。
model = torch::jit::load(argv[1]); int size = 1000000; (中略) std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); for (size_t i = 0; i < size; i++) { int64_t shape[] = {2}; std::vector<torch::jit::IValue> inputs{torch::from_blob(data[i], shape)}; model.forward(inputs); } std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << "[ms]" << std::endl;
実行時間は 44 秒であった。Java より速いかと思ったら意外とそんなことはなかった。なぜだろう。
C++ API からモデルを呼び出す
いろいろ調べたところ、TorchScript すら遅いと感じる場合は PyTorch の C++ API を使うとよいらしい。PyTorch の裏側で実行される LibTorch というライブラリを直接叩けるようだ。TorchScript みたいにインタプリタを挟むのではなく、C++ のピュアなデータ構造として表現されたニューラルネットワークを使って推論を実行できるってことだろう。
今回は学習から C++ API を使ってやる必要がある。このチュートリアル を見ながらやってみた。コードは以下のような感じである。
int main() { (中略) for (size_t epoch = 1; epoch <= n_epochs; epoch++) { for (size_t i = 0; i < size / batch_size; i++) { torch::Tensor x = X[i]; torch::Tensor y = Y[i]; optimizer.zero_grad(); torch::Tensor predicted = model->forward(x).reshape({batch_size}); torch::Tensor loss = torch::mse_loss(predicted, y); loss.backward(); optimizer.step(); } } torch::save(model, "../model_cpp.pt"); }
基本的には Python から PyTorch を使う時と同じような流れで C++ でプログラムが組めるようになっている。
そして例によって100万回推論を実行してみる。
int main() { c10::InferenceMode guard(true); auto model = std::make_shared<MyNN>(); torch::load(model, "../model_cpp.pt"); (中略) std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); for (size_t i = 0; i < size; i++) { model->forward(input_values[i]); } std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << "[ms]" << std::endl; }
実行時間は 9 秒であった。めっちゃ速い。これだ。
まとめ
各設定で推論を100万回実行したときの実行時間を以下にまとめる。
設定 | 実行時間 |
---|---|
Python | 124 秒 |
TorchScript from Python | 54 秒 |
TorchScript from Java | 35 秒 |
TorchScript from C++ | 44 秒 |
C++ API | 9 秒 |
推論時のオーバヘッドを減らせる C++ API が最強だけど、Java から TorchScript を呼び出すくらいでも悪くないケースも多いかもしれない。Rust から C++ API を叩けるラッパーとかもあるっぽいので、そのあたりを触ってみたい。C++ よりは Rust でプログラム書きたいので。
おしまい。