$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。

データ指向アプリケーションデザイン 第I部 データシステムの基礎を読んだ

今更ながらデータ指向アプリケーションデザインを読んでいる。第I部 データシステムの基礎まで読んだ。とにかく面白くて良い。

自分は「3章 ストレージと抽出」がもっとも面白いと感じ、とくにSSTableとLSMツリーというシンプルなアルゴリズムで多くの問題を解決できていることに感動を覚えた。昔もマージソートに感動した覚えがあるけど、今回もマージソートはすごいという気持ちになる。また列指向データベースの基本的な考え方や圧縮効率を学べたのも良かった。

「4章 エンコーディングと進化」においては、変化しやすさを担保するための後方互換性(= 新しいコードが古いデータを読める)と前方互換性(=古いコードが新しいデータを読める)についてまとめた上で、いくつかのデータフローの中で何を満たすべきなのかがまとめられていた部分が良かった。たとえばデータベースとのやりとりだと何があれば前方・後方互換性が保たれるか、REST APIだとどうか、非同期のメッセージパッシングの送受信だとどうかなどが具体的に語られていた。

まだまだ先は長いけど地道に読んでいこうと思う。

読書ノート

### 1章 信頼性、スケーラビティ、メンテナンス性に優れたアプリケーション
- 本書はソフトウェアシステムにおける重要な3つの課題に焦点 315
    - 信頼性
        - フォールとがあっても正しく動き続ける
    - スケーラビリティ:負荷の増大に対してシステムが対応できる能力
    - メンテナンス性
        - 運用性:運用チームが扱いやすい
        - 単純性:新しいエンジニアが理解しやすい
        - 進化性:システムを変更しやすい
- レスポンスタイムはクライアント側で計測しなければ、ユーザーの視点に立てない 596

### 2章 データモデルとクエリ言語
- グラフストアは、頂点と辺の概念がある 1462
    - 任意の頂点を辺によって接続できる
    - 任意の頂点に対する入出力の辺を効率的に見つけ出せる。グラフを探索できる
    - 辺に異なるラベルを使うことで、単一グラフの中にさまざまな情報を保存する

まとめ 1761
- リレーショナルデータベース以外だと、以下の二つに分かれる
    - ドキュメントデータベース:データが自己完結しているドキュメント群で、リレーションがそれほど存在しないものをターゲット
    - グラフデータベース:あらゆるもの同士に関係が存在するようなユースケース
        - データのほとんどが多対多の場合リレーションモデルは不得意

### 3章 ストレージと抽出

ハッシュインデックスとlog-structuredなデータ保存
- log-structuredな仕組みでのデータファイルのコンパクションおよびマージ処理 2019
    - ログがあるサイズになったらファイルをクローズする
    - 凍結されたセグメントでは最新の値だけ残しマージする。複数のセグメントも最新のものは後のファイルに入っているはずなので、それを踏まえてマージ
- ハッシュインデックスでは各セグメントにインメモリのハッシュテーブルがある 2019
    - キーに対する値を見つけるには、最新セグメントのハッシュマップチェック -> なければ2番目の、...
- log-structuredな仕組みでは、レコードの削除を特別な削除レコード追加で代替できる 2041
- log-structuredな追記のみの仕組みのメリット 2041
    - セグメントの追記とマージはシーケンシャルな処理なためランダムな書き込みより高速
    - 並行処理やクラッシュリカバリがシンプル
    - データファイルのフラグメンテーションが少ない
- ハッシュテーブルのインデックスの制約 2068
    - メモリ内にキーが収まらなくなるとだめ
    - 範囲クエリの効率が悪い
    - -> SSTableとLSMツリーへ

SSTableとLSMツリー
- ソート済み文字列テーブル(Sorted String Table、SSTable) 2068
    - セグメントファイルのフォーマットに2条件を追加
    - キーでソートされていることという条件を追加
    - マージされたそれぞれのセグメントファイル中には、それぞれキーは一度だけしか現れないという条件を追加
- SSTableの利点 2095
    - マージソートできるためメモリ効率が良い
    - 全てのキーをインデックスに残さなくても、一部だけでどのあたりにそのキーがあるか分かる
- どうやってキーごとにソートしてデータを保存する? 2113
    - 書き込み時点ではメモリで管理、一定より大きくなったらディスクにセグメントとして書き込み
    - クラッシュからの復帰のためだけにディスク上に全ての書き込みを即座に追記するファイルを用意。セグメントをディスクに書き込むたびに削除
- このようなSSTableとコンパクション・マージを踏まえたインデックス構築のような構造をLSMツリー(Log-Structured Merge-Tree)と呼ぶ 2136
- 存在しないキーのルックアップの高速化のためにブルームフィルターが使われる 2164

- LSMツリーは通常書き込みを高速に処理でき、Bツリーは読み取りが高速に行えるものとみなされている 2243

オンライン分析処理(OLAP)と列指向データベース
- データウェアハウスではしばしば大量の列を持つことが多い。100〜数百。アクセスパターンは数列しかなく、それを効率化するために列指向データベースが使われる 2578
- 列指向ストレージの考え方:1つの行に含まれる全ての値をまとめて保存するのではなく、それぞれの列に含まれる全ての値をまとめて保存する 2605
- 列指向ストレージは圧縮に適している 2626
    - 行数よりも列の中身の種類数の方が少ないことが多いため
    - ランレングスエンコーディング
        - WHERE句でのOR条件はビットのORに、AND条件はビットのANDにマッピング可能
    - 列ストレージでSSTableのような順序強制の仕組みを使うと列の圧縮を助けられる 2670
- 列ごとに圧縮されていると、ソートされたテーブルの途中に行を挿入しづらい。これはLSMツリーのようにインメモリストアに書き込み -> 十分に貯まったらディスク上の列ファイルとマージ圧縮という方法を使う 2702
    - 読み込みは列データとメモリの両方から見る

まとめ
- ストレージエンジンは、トランザクション処理(OLTP)に最適化されたものと、分析(OLAP)に最適化されたものの2つに分類
    - OLTPでは莫大なリクエストと少数のレコード
    - OLAPでは少量のクエリと、多くのレコードスキャン
        - ディスクの帯域がボトルネックになるので列指向が使われる
    - 気づき: Web APIはOLTP、バッチ処理はOLAP
- OLTPには2つの考え方のストレージエンジン
    - log-structured:ファイルへの追記と古くなったファイルの削除だけ行える。SSTable、LSMツリー
    - インプレース更新:ディスクを更新可能な固定サイズのページの集合として扱う。Bツリー

### 4章 エンコーディングと進化

- ごく一時的な目的の場合以外では、特定の言語の組み込みエンコーディングは使うべきでない 3013
    - 多言語とのポータビリティ
    - 前方および後方互換性の不足
    - 効率性
- Protocol Buffersなどのバイナリフォーマット 3114
    - 前方後方互換性を維持するためには 3155
        - フィールド名は変えられるが、フィールドのタグは変更できない
        - フィールドの追加
            - 新しいタグ番号なら、古いコードはそのフィールドを単純に無視するため問題ない。アノテーションからスキップするバイト数を把握できる。この特性で前方互換性が保たれる
            - タグ番号が変わらないので後方互換性は保たれる。しかし新しいフィールドは必須にできない(MySQLのスキーマと同じ)
        - フィールドの削除
            - 必須フィールドは削除できない、オプションフィールドは削除できる
- JSONなどのスキーマレスなテキスト形式と比較して、スキーマありのバイナリエンコーディングの優れた性質 3342
    - はるかにデータがコンパクト。フィールド名が必要ない
    - スキーマ自体がドキュメントになる
    - スキーマの変更をみるだけで前方後方互換性の維持チェックをデプロイ前にできる
    - コード生成しやすい

データフローと前方後方互換性
- データベースの場合、後方互換性は必須、前方互換性が求められることもしばしばある 3397
    - 新しいフィールドのことを解釈できなくても、古いコードが新しいフィールドに手を加えてはならない
- RPCやRESTの場合、すべてのサーバーがまずアップデートされ、クライアントはその後にアップデートされるという仮定をおいてシンプルにしてもいい 3569
    - 保つ必要があるのは古いクライアントからのリクエストを新しいサーバーが解釈できることと、新しいレスポンスを古いクライアントが壊れずに解釈できること
        - この特性はRPCが使うエンコーディング特性が引き継がれる
- 気づき: メッセージブローカーの場合は、RPCのレスポンスがない版として考えたらいい? 3597
    - 分散アクターフレームワークとかだと難しいとかもある

まとめ
- ローリングアップグレードをする場合、システム内を流れるすべてのデータは、後方互換性と前方互換性が保たれる方法でエンコードされなければならない
    - 後方互換性 = 新しいコードが古いデータを読める
    - 前方互換性 = 古いコードが新しいデータを読める
- データエンコーディングの互換性について
    - プログラミング言語固有のエンコーディングは、しばしば前方および後方互換性を欠いている
    - JSONなどのテキストフォーマットの互換性は利用の方法に依存する
    - Protocol Buffersなどのスキーマを持つバイナリフォーマットでは、前方および後方互換性の背マンティクスが明確に定義されている
- 互換性について、それぞれのデータフローで気をつける必要がある
    - データベースの書き込みと読み取り
    - RPCやREST APIのリクエストとレスポンス
    - 非同期のメッセージパッシングの送信と受信

MySQLのREPEATABLE READとREAD COMMITTEDのロック状況をdata_locksから観察する

前回MySQLのREPEATABLE READとREAD COMMITTEDの違いを知るために色々試した - $shibayu36->blog;という記事を書いたところ、yoku0825さんにMySQL 8.0以降だとperformance_schema.data_locksが使えると教えてもらったので試した。

テーブル定義

CREATE TABLE `posts` (
  `id` int NOT NULL,
  `title` varchar(255) NOT NULL,
  `body` text NOT NULL,
  UNIQUE KEY `id` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci

両方ともREPEATABLE READ

> select * from posts;
+----+--------+-------+
| id | title  | body  |
+----+--------+-------+
|  1 | title1 | body1 |
|  2 | title2 | body2 |
+----+--------+-------+

# トランザクション1
begin;

# トランザクション2
begin;

# トランザクション1
UPDATE posts SET title = 'title2updated' WHERE id >= 2 and id < 5;

# トランザクション2
insert into posts (id, title, body) values (10, 'title10', 'body10'); # -> lockされる

この時にperformance_schema.data_locksを確認する。

> SELECT ENGINE_LOCK_ID, ENGINE_TRANSACTION_ID, OBJECT_NAME, INDEX_NAME, OBJECT_INSTANCE_BEGIN, LOCK_TYPE, LOCK_MODE, LOCK_STATUS, LOCK_DATA FROM performance_schema.data_locks where OBJECT_SCHEMA = 'repeatable_read_test';
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+
| ENGINE_LOCK_ID                    | ENGINE_TRANSACTION_ID | OBJECT_NAME | INDEX_NAME | OBJECT_INSTANCE_BEGIN | LOCK_TYPE | LOCK_MODE          | LOCK_STATUS | LOCK_DATA              |
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+
| 275347546352:1579:275213534048    | 12672                 | posts       | <null>     | 275213534048          | TABLE     | IX                 | GRANTED     | <null>                 |
| 275347546352:516:4:1:275213531136 | 12672                 | posts       | id         | 275213531136          | RECORD    | X,INSERT_INTENTION | WAITING     | supremum pseudo-record |
| 275347545496:1579:275213527904    | 12670                 | posts       | <null>     | 275213527904          | TABLE     | IX                 | GRANTED     | <null>                 |
| 275347545496:516:4:4:275213524912 | 12670                 | posts       | id         | 275213524912          | RECORD    | X,REC_NOT_GAP      | GRANTED     | 2                      |
| 275347545496:516:4:1:275213525256 | 12670                 | posts       | id         | 275213525256          | RECORD    | X                  | GRANTED     | supremum pseudo-record |
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+--------------------+-------------+------------------------+

これを観察すると

  • トランザクション1がテーブルのIXロック、id 2のレコードロック、ギャップロックを保持している
  • トランザクション2がテーブルのIXロック、INSERTでのギャップロックで待ち状態

という状況を観察できる。確かにREPEATABLE READ時にレコードロック+ギャップロックを取っていることがわかる。

UPDATE側がREAD COMMITTED

# トランザクション1
set session transaction isolation level read committed;
begin;

# トランザクション2
begin;

# トランザクション1
UPDATE posts SET title = 'title2updated' WHERE id >= 2 AND id < 5;

# トランザクション2
insert into posts (id, title, body) values (10, 'title10', 'body10'); # -> lockされない

この時にperformance_schema.data_locksを確認する。

SELECT ENGINE_LOCK_ID, ENGINE_TRANSACTION_ID, OBJECT_NAME, INDEX_NAME, OBJECT_INSTANCE_BEGIN, LOCK_TYPE, LOCK_MODE, LOCK_STATUS, LOCK_DATA FROM performance_schema.data_locks where OBJECT_SCHEMA = 'repeatable_read_test';
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+---------------+-------------+-----------+
| ENGINE_LOCK_ID                    | ENGINE_TRANSACTION_ID | OBJECT_NAME | INDEX_NAME | OBJECT_INSTANCE_BEGIN | LOCK_TYPE | LOCK_MODE     | LOCK_STATUS | LOCK_DATA |
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+---------------+-------------+-----------+
| 275347546352:1579:275213534048    | 12675                 | posts       | <null>     | 275213534048          | TABLE     | IX            | GRANTED     | <null>    |
| 275347545496:1579:275213527904    | 12674                 | posts       | <null>     | 275213527904          | TABLE     | IX            | GRANTED     | <null>    |
| 275347545496:516:4:5:275213524912 | 12674                 | posts       | id         | 275213524912          | RECORD    | X,REC_NOT_GAP | GRANTED     | 2         |
+-----------------------------------+-----------------------+-------------+------------+-----------------------+-----------+---------------+-------------+-----------+
  • トランザクション1がテーブルのIXロック、id 2のレコードロックのみ。ギャップロックはなし
  • トランザクション2がテーブルのIXロック。INSERT時に待たされていないためdata_locksに内容が表示されない

確かにREAD COMMITTEDにするとギャップロックを取っていないことがわかる。

まとめ

performance_schema.data_locksを使うことでロック状況が可視化できた。以前PostgreSQLでこういうものを使ったことがあったが、MySQL 8.0からperformance_schema.data_locksというものが使えると知らなかったのでこれから便利に使えそうだ。

Action Graphを使ってGoのpackageごとのビルド時間を可視化する

前やったことあるがブログに書いてなかったのでメモしておく。

まずGoのビルド時間についてはAnalyzing Go Build Times | howardjohn's blogが非常に分かりやすく参考になる。この中でAction Graphというものに言及があり、これを使うことでパッケージごとのビルド時間を可視化できる。

例えば自分のgo_todo_appというものを使ってみる。 まずgo buildでactiongraph.jsonを吐き出し

$ go build -debug-actiongraph=actiongraph.json ./...

その後時間がかかっている順にランキングを出せる。今回のレポジトリは非常に小さいのでruntime/cgoのビルドが一番重そうだ。

$ actiongraph -f ./actiongraph.json top
  0.956s   6.88%  build runtime/cgo
  0.768s  12.41%  build runtime
  0.560s  16.44%  build net
  0.473s  19.85%  build net/http
  0.401s  22.74%  build debug/dwarf
  0.378s  25.45%  build math/big
  0.354s  28.01%  build vendor/golang.org/x/text/unicode/norm
  0.318s  30.30%  build gopkg.in/yaml.v3
  0.289s  32.38%  build golang.org/x/net/html
  0.275s  34.36%  build github.com/google/go-cmp/cmp
  0.258s  36.22%  link  github.com/shibayu36/go_todo_app
  0.250s  38.01%  build encoding/xml
  0.243s  39.77%  build crypto/tls
  0.239s  41.48%  build encoding/json
  0.222s  43.08%  build golang.org/x/text/internal/language
  0.205s  44.55%  build reflect
  0.190s  45.92%  build testing
  0.186s  47.26%  build database/sql
  0.166s  48.45%  build github.com/jmoiron/sqlx
  0.161s  49.61%  build github.com/go-playground/validator/v10

また、treeを使うことでnestされたpackageのどれに時間がかかっているかを可視化したり

$ actiongraph -f ./actiongraph.json tree -L 2
 13.634s          (root)
 10.935s            std
  1.860s   0.768s     std/runtime
  1.644s   0.012s     std/crypto
  1.293s   0.560s     std/net
  1.037s              std/vendor
  0.861s              std/internal
  0.737s   0.018s     std/encoding
  0.550s   0.089s     std/math
  0.459s              std/debug
  0.245s              std/database
  ...
  1.682s            github.com
  0.357s              github.com/google
  0.261s              github.com/go-playground
  0.197s              github.com/gabriel-vasile
  0.189s              github.com/jmoiron
  0.179s              github.com/stretchr
  0.140s              github.com/shibayu36
  0.103s              github.com/go-sql-driver
  0.068s              github.com/davecgh
  0.057s              github.com/caarlos0
  0.048s              github.com/pmezard
  0.043s              github.com/leodido
  0.040s              github.com/go-chi
  0.699s            golang.org
  0.699s              golang.org/x
  0.318s            gopkg.in
  0.318s   0.318s     gopkg.in/yaml.v3

actiongraphのREADMEに書かれているように、あるパッケージがどこから依存されているかの可視化もできる。

便利ですね。

参考