Extended outer memory module
for my poor native memory.
Posts:
2022/02/13 クラビスの CTO になりました
2020/09/28 gendoc という YAML からドキュメントを生成するコマンドを作った
2020/09/13 ISUCON10 の予選を 7 位で通過した
2019/12/01 Puma の内部構造やアーキテクチャを追う
2019/05/27 Golang の正規表現ライブラリの処理の流れをざっくり掴む
2019/04/29 InnoDB の B+Tree Index について
2019/04/29 InnoDB における index page のデータ構造
2019/04/28 InnoDB はどうやってファイルにデータを保持するのか
2019/01/06 Designing Data-Intensive Applications を読んでいる
2019/01/03 年末年始に読んだ本について、など
2019/01/01 Ruby から ffi を使って Rust を呼ぶ
2018/11/10 ブラウザにおける状態の持ち方
2018/07/01 Rust で web アプリ、 或いは Rust における並列処理
2018/05/14 なぜテストを書くのか
2018/05/13 Rust で wasm 使って lifegame 書いた時のメモ
2018/03/12 qemu で raspbian のエミュレート(環境構築メモ)
2018/03/12 qemu で xv6 のエミュレート(環境構築メモ)
2018/03/03 Ruby の eval をちゃんと知る
2018/02/11 Web のコンセプト
2018/02/03 Rspec のまとめ
2018/02/03 Ruby を関数型っぽく扱う
先日のポストでも最後に少しだけ触れたが、会社の先輩におすすめされた Designing Data-Intensive Applications という本を読んでいる。
著者はケンブリッジ大で分散システムの研究をしている人みたい。詳しい情報はここに色々載っている。 https://dataintensive.net/
読み始めた動機は大きく分けて 2 つある。
一つは、今仕事で開発しているアプリケーションはもちろんのこと、世の中のアプリケーションというのは「何かしらのデータに対してどういう操作を加えるのか」というインターフェースを提供しているものと思えなくもないよな、とコードを書き始めたころからずっと思っていて、そういった視点で現代的なアプリケーションでよく採用されているアーキテクチャとそれぞれの特徴をまとめてくれる本だったらいいなと思ったこと。
もう一つは、英語でちゃんとした技術書を読んでいきたいなと思ったこと。 (英語の技術書自体は Programming Rust や The Docker Book は読んでたので初めてではないんだけど。) 検索エンジンで調べてもよくわからない二次情報がたくさん出てくることが多いような気がしていて、もうちょっと質のいい情報に到達するためには外国語で書かれた情報を摂取するようにしないとこの先つらいなっていうのが見えてきたので、今年は本格的に取り組んでいきたい。
序章なので、アプリケーションが求められる性質についてまとめてある。
割と普通のことばかりが丁寧に書いてあるので、詳しくは取り上げなくてもいいかな。
「アプリケーションのアーキテクチャ部分に変更を加える」という観点でも、アジャイルなアプローチを取れるような方法を模索すると明言しているのは中々いいな。後続の内容に期待。
RDBMS が利用する Relational Model と NoSQL の文脈で出てくる Document Model の対比が紹介されている。現段階だとスキーマの有無がその違いだというふうに僕は理解している。
NoSQL 登場以前のビジネスシーンでは RDBMS が用いられることが多かったが、より大きいデータセットを扱ったり書き込みのスループットを上げたいという観点でのスケーラビリティを手に入れるために NoSQL が出てきたというのが、一番メインの理由っぽい。他にも商用の RDBMS(Oracle や IBM のこと??)ではできない OSS 的な取り組みがしたかったであるとか、もっと動的に扱うデータを変化させるために柔軟なスキーマが必要だったとか、 RDBMS ではできないようなクエリが打ちたかったとか、理由はいくつかあるみたい。
思うに、永続化したいデータの構造が簡単に定めきれないケースというのが発生し始めたんじゃないのかな。どこまで成長するかわからないアプリケーションを小さく始めて、成功したらだんだんとアプリケーション上で複雑なことができるように機能を追加していって、みたいな道筋を考える。すると最初からどこまで厳密にスキーマを定義していくべきかというのはなかなか難しい問題になる気がしていて、であれば柔軟なデータ構造のまま丸っと突っ込んでいける NoSQL みたいなものに魅力を感じるのも一理あるというか。多くの場合 RDBMS においてスキーマの変更というのは高コストの処理になるし。(僕は現時点で RDBMS の方が好きだけど)
加えて Object-oriented なプログラミングパラダイムが流行したことで、 RDBMS の場合にはそこで表現されている Relation を Object に反映する O/R Mapper が必要になる。その複雑さが Document Model への移行を促す原因の一つになったともある。
Document Model の利点として、1 つの Document がいくつもの要素・項目を持つようなデータ構造は表しやすいというのがある。一方で、ある要素・項目が複数の Document 間で同じものであるとしたい場合に、その表現が難しいとのこと。複数の Document が同じもの要素・項目を持つと表したいのに、別の Document への参照ではなく実体を持つとすると Normalize(正規化) できてないじゃん、みたいな話とか。(これに関しては RDBMS 同様 Primary Key を持つことで解決しているらしいが) 加えて、 many-to-many な関係性を表現する場合にも RDBMS の方が優れているということも説明されている。
データ構造ではなくパフォーマンス的な側面でいうと、データ全体にアクセスすることを目的とした場合には全てのデータが一つの Document としてディスク上の連続する領域に集約されている Document Model の方が優れていて、 Relational Model は join 処理が必要なこととディスクの非連続な部分部分へのアクセスが必要なことから劣る場合が多い、みたい。これはそのまま逆の関係性にも適用できて、データに部分的にアクセスしたい場合にも Document Model の場合には Document 全体を引っ張ってこないといけないから無駄が多い、一方で Relational Model の場合には部分のみの抽出が可能。(勿論データの持ち方によるが)
最近では RDBMS においてもグルーピングするような上位の概念を実装することで locality を備えさせようという試みがあるそう。個別の具体的な実現方法はさておき、 Google Spanner, Oracle, Cassandra, HBase などなどで採用されているらしい。
Document Model はスキーマレスだと言われることが多いけどこれは正しくなくて、 read 処理の際にはデータに対してなんらかのスキーマを仮定している。 RDBMS と比較して違いがあるのは write 処理の際にスキーマを仮定しないこと。これはなるほどな。
途中 Relational Model と Document Model の違いを静的型付け言語と動的型付け言語の違いに対応させて説明させている部分がある。こうして見ると、プログラミングの歴史・流行というのは制約とどう向き合うかによって作り上げられてきたと言えなくもないのかな、そんな気がする。
とここまで Document Model と Relational Model の対比構造を説明してきたものの、近年では Relational Model に Document Model 由来のデータ型をサポートする機能が入ったり、 Document Model に対して Document 同士の join の機能を加えるようになったり、ハイブリッドする流れというのがメインになりつつあるそうね。正しいかはさておき順当だな。
それぞれのモデルに対してクエリを投げる時の差異は結構面白かった。 Relational Model の場合には宣言的な言語でどういう結果が欲しいかを記述するので、データベースエンジンの実装や処理をクライアントから隠蔽することができる、これによって Relational Model 独自の最適化が行える余地があるらしい。(例えば抽出処理の並列化など) これは Query Language に限らず宣言的言語全体に言えそうね、なるほどねえ。 Document Model は抽出してきた Document をどう扱うかもクライアントサイドに任せられているので、散々書いてきたけど Document 間でデータ構造が違う場合にも柔軟に対応できるんだろうし、それを魅力と感じる人はいるのだろうね。
後半の Graph Database に関する記述はしばらくはあまり触れることがなさそうだし基本的なアイデアは理解できていると思うので、ぱらぱらと読み飛ばすことに。 CODASYL, SPARQL, Cypher なんて名前が出てきた、聞いたことがあるようなないような。 Document Model が自身のスキーマの変更に柔軟なデータの持ち方であるように、 Graph Model というのはリレーションに対して柔軟なデータの持ち方であると言えるみたいね。
Chapter 2 ではデータベースよりも上のレイヤから見てどういう構造でデータを持つか、ということについて説明していた。 Chapter 3 ではそれを踏まえて、データベースが自身よりも下のレイヤと協調してどうやってデータを管理しているのか、ということについてまとめるそう。
以下のデータ構造が取り上げられている。
そのあとのセクションでは、これまでのデータ構造やアルゴリズム、ミドルウェアはディスクへの永続化をゴールにそのためにいかにメモリを利用するか、という前提の上で議論されてきたが、メモリの価格が下がったことや容量が増えたこと(あるいは不揮発メモリの研究が今後進んでいくこと)で、全データをメモリ上に乗せるという選択肢が出てきた。こうすることでディスク書き込みや読み出しのオーバーヘッドがなくなるのは勿論、ディスクの特性に依存した最適化を行わなくてよくなるので複雑なアルゴリズムが実装しやすくなったらしい。またこの前提であれば、逆にメモリの拡張記憶領域としてディスクを利用するということが可能になる(仮想メモリ領域をディスク上に確保してスワップすればいい)ので、容量的な問題はほとんどないと言ってもいいのかも。
OLTP(Online Transaction Process) と OLAP(Online Analytical Process) の概念についても説明がある。ユーザー起因の処理で実行するクエリとビジネス分析観点で実行するクエリって性質が大きく異なるので、分離すべきだよねって話。説明では SAP の HANA とかが取り上げられているんだけど、こういった OLAP のいかにも大規模エンタープライズ向け領域のミドルウェアって SAP みたいなベンダーの製品がいまだに高いシェアを持っているんだろうか。 OSS のミドルウェアベースにクラウドに乗せる選択肢はあまりない??(そんなことないよね??)
OLAP の場合には欲しい情報の最低粒度のイベントをレコードとするテーブルを核にして、その核テーブルに更に詳細な情報を示すテーブルへの参照(外部キー)を保持するようなスキーマが一般的らしい。中心のテーブルから詳細テーブルに参照が伸びている構造から star scheme とか言うそう。(それらの詳細テーブルから更に細かい情報を保持するテーブルへの参照を持つ場合は snowflake scheme とか言うらしい)
こうしたデータ構造や、そもそもレコード数が非常に多いという前提から、一般的な RDBMS で採用されているような row-oriented なデータ保持はパフォーマンス的に厳しいことが多い。(row 単位でデータがまとまって保存されているような持ち方のこと) そこでこうした OLAP 用途のデータベースでは column-oriented なデータ保持を行う。
column ごとのデータ保持を行う上でもう一つ有利な最適化を行うことができる。ある column に保持されるデータは属するレコードが異なっても同じデータ型を持っているという前提がおける場合が多い。(例えば 64-bit unsigned integer など) また同じデータ型という制約の中でもさらに分布に傾向があるようなケースも存在する。その際、特定の column のデータに対して効率のいい圧縮やインデックス構造の保持を行うことができる余地ができることがあるらしい。(例として挙げられている bitmap encoding ではクエリの WHERE ~~ IN (A, B, C, ...) 条件や WHERE ~~ = A AND ~~ = B ... 条件に対してうまく効率的に結果を抽出しており、賢いな…!!!ってなった)
メモリ上のデータを永続化する・メモリ上に読み直す、という操作に関して書かれた章。いわゆるシリアライズ/デシリアライズのこと。この本ではそれぞれの操作を encoding/decoding と呼んでいる。
(永続化されるべき)データがアプリケーションよりも長生きするという前提に立つと、同一のデータに対してアプリケーションが変化するということが当然起こりうる。その際に問題になるのが Backward Compatibility と Forward Compatibility 。データとアプリケーションコードの関係性だけで考えるならば、新しいアプリケーションが古いアプリケーションによって書かれたデータを読めるのが前者であり、その逆が後者になる。
また単一言語に留まらず複数言語間でデータの表す意味が変化しないように、共通のフォーマットを持つ戦略が一般的に採られている。これがいわゆる JSON のようなファイルフォーマットの役割になる。 この章では XML, JSON, Protocol Buffers, Thrift, Avro を取り上げるようだ。
特定の言語に閉じたシリアライズ/デシリアライズは任意のオブジェクトに対して行うことができることがあり、これはその言語に閉じている限りは言語間でのフォーマットの差などは問題にならず、また効率的にデータを永続化することができる。一方で任意のオブジェクトをメモリ上に読み出せるようになっているせいで、外部からの入力に対してデシリアライズ操作を行うと RCE ができてしまう可能性が出てくる。また前方/後方互換性が重視されないことやパフォーマンスが良くないという問題があるというケースもあるようだ。 (Java に built-in で入っているシリアライゼーションの処理はパフォーマンスが悪いことで有名らしい。)
それでは言語間で共通のフォーマットとして用いられることのある JSON や XML, CSV はどうだろうか。これらはそもそも human-readable であるという特徴を持っており、これは重要な利点と言えそうだ。しかし例えば XML や CSV では数字で構成された文字列と数値を判別するための仕様が存在しない、JSON では整数と浮動小数点を区別するための仕様が存在せずまた 2^53 以上の数を正確に表せない、バイナリの文字列をそのまま表せない (Base64 encode する必要がある)などの不便な点も存在する。
そもそも human-readable な特性をもつ XML や JSON はただデータを表現したいという目的では無駄があり、 binary encoding へのサポートがあると internal な通信などでは効率化が図りやすい。しかし MessagePack を始めとする JSON-base なバイナリをサポートするフォーマットや WBXML などの XML 形式のフォーマットはどれも、 JSON や XML 自身ほどには広く浸透していない。またこうした拡張フォーマットはメタ的に(自分のデータの外側で)情報を定義する術を持っていないので、必ずキー値のようなものが必要になってしまう。
Thrift(Facebook) や Protocol Buffers(Google) といった binary encoding のフォーマットは、 IDL という概念を元にデータのスキーマ(JSON でいう field の名前など)とデータ自身を分離する方針を採用している。 IDL を用いてスキーマを定義するとたくさんの言語に対してそれをシリアライズ/デシリアライズするコードを生やすということを行う。それによってバイナリのエンコーディングと多言語間の差分の吸収を行っている。 これらのフォーマットでは field 名とそのデータタイプごとにユニークな tag number を振って管理している。例えば同じ field 名でのデータタイプが変化すると新しい tag を振って、古い方も新しい方も用意したデータを送り、受け取り側では自分の知らない tag のついたデータは無視するということをすれば、過渡期の Forward Compatibility も Backward Compatibility も達成できる。
Avro は Hadoop project の一環で生まれたフォーマットで、 Thrift が Hadoop に上手く適さなかったために生まれた。 Avro では tag number のような field の抽象化は一切行わず、そういった情報をデータから完全に削ぎ落としている。つまり、 IDL に定義された field が正しい順で一つも過不足なく共有できているという前提の上に成立している。 Thrift や Protocol Buffers と比較して強い仮定をデータに対して置いているので一番少ないバイト数で同じ意味内容のデータを表現できる。 では Avro はどうやってスキーマの変更に対応して Compatibility を担保しているかというと、 read 時に利用するスキーマと write 時に利用するスキーマの両方をアプリケーションは持ち、その差分の変換部分もライブラリが生成するコード部分で行うということらしい。(また新しく追加する field には必ず default 値を設定しておかないと Backward Compatibility を破壊してしまう、などの制約もあるみたい。) しかも最初にデータを送る際に writer のスキーマを reader 側に共有するということを行うらしい。同一スキーマで大量のデータを送る場合には最初のオーバーヘッドを考慮しても削減できるデータ量の方が大きいという判断から来ている。 とはいえ Avro は難しくてちゃんと理解できているかわからないな。